13.6.1. STL Examples: map, list, pair, and iterator

We continue the practice in this section of using the word count program to explore containers. In practice, programmers select a container whose behaviors best match a specific problem. However, some examples use containers that are ill-suited to the word count problem, instead favoring the demonstration of STL classes, including containers and support classes. Using STL containers reduces the time and effort required to program a solution to a problem. In the following examples, the basic program logic remains unchanged from the KVTree version: the program reads the input file one character at a time, converts the alphabetic characters to lower case, and appends them to a word. When the word is complete, the program searches for the word in a container. If the word isn't in the container, the program adds it with a count of 1; otherwise, it increments the word's count. Please see the earlier example for details omitted for brevity.

STL Iterators

Reiterating (did you see what I did there?) our previous definition, "iterators are objects that sequentially access the elements stored in a container object," allowing a program to loop or iterate through them. The rudimentary iterator we created for the KVTree is quite limited compared with the STL iterators. Although the iterators used by the following programs are all named iterator, their full names, formed with a container class name and the scope resolution operator, are unique - they are not the same iterator.

While programs instantiate the STL iterators from distinct classes, they share several crucial features:

• Containers using iterators provide numerous functions for creating them, e.g., begin, end, rbegin, and rend
• The functions return pointers to the iterators, so they are often dereferenced or used with the arrow operator
• Programs move forward or backward through the iterator elements with the increment (++) and decrement (--) operators

The pair Structure

The pair structure builds an association between two values whose types it represents with template variables. In Chapter 9, I claimed, "The only real difference between a struct and a class is the default visibility: structures have public visibility, and classes have private visibility. Nevertheless, C++ programmers generally only use structures to represent packaged data and reserve classes for truly object-oriented situations (i.e., when an entity should have attributes and operations packaged together)." pair is an exception: programmers often access both fields or members, but giving it functions eases its use.

template <class T1, class T2>
struct pair
{
    T1 first;
    T2 second;
};

WordCount_list1: list, iterator, and Client Structure

Lists are linear data structures whose insert and search operations run in time proportional to n, where n is the number of elements in the list. This proportionality means that doubling the data size doubles the insert and search runtimes, making them ill-suited for the word count problem. Although not an optimal solution, the following example demonstrates how to implement WordCount using an STL list. The list-based solution could use the pair class, but a client structure better illuminates the underlying program structure.

#include <iostream>
#include <fstream>
#include <iomanip>
#include <string>
#include <cctype>
#include <list>											// (a)
using namespace std;

struct w_count											// (b)
{
    string	word;
    int		count;
};

int main()
{
    list<w_count>	words;									// (c)
    ifstream		file("alice.txt");
    int			c;
    string		word;

    while ((c = file.get()) != EOF)
    {
        if (isalpha(c))
            word += tolower(c);
        else if (word.length() > 0)
        {
            list<w_count>::iterator i = words.begin();						// (d)
            while (i != words.end() && word > i->word)
                i++;
            
            if (word == i->word)								// (e)
                i->count++;
            else
            {
                w_count node;
                node.word = word;
                node.count = 1;
                words.insert(i, node);
            }

            word.clear();
        }
    }

    for (list<w_count>::iterator i = words.begin(); i != words.end(); i++)	         	// (f)
        cout << left << setw(20) << i->word << right << setw(3) << i->count << endl;

    return 0;
}

WordCount_list2: list, pair, and iterator

#include <iostream>
#include <fstream>
#include <iomanip>
#include <string>
#include <cctype>
#include <list>											// (a)
using namespace std;


int main()
{
    list<pair<string,int>>	words;								// (b)
    ifstream			file("alice.txt");
    int				c;
    string			word;

    while ((c = file.get()) != EOF)
    {
        if (isalpha(c))
            word += tolower(c);
        else if (word.length() > 0)
        {
            list<pair<string,int>>::iterator i = words.begin();
            while (i != words.end() && word > i->first)
                i++;
            
            if (word == i->first)
                i->second++;
            else
                words.insert(i, make_pair(word,1));						// (c)

            word.clear();
        }
    }

    for (list<pair<string,int>>::iterator i = words.begin(); i != words.end(); i++)
        cout << left << setw(20) << i->first << right << setw(3) << i->second << endl;

    return 0;
}

WordCount_tree: KVTree, list and iterator

The initial KVTree example included an iterator constructed with an array and implemented as a nested class. The iterator's description suggested replacing the array with a list and, using its iterator, eliminating the nested class. The following example demonstrates this solution.

public:
    class iterator;
    list<K> keys;

    ~KVTree();
    V* insert(K key, V value);
    V* search(K key);
    void remove(K key);

    void list() { if (right != nullptr) right->_list(); }
    void tree_view(int level = -1);
    int count(int number = 0);

    iterator get_keys() { iterator i(this); return i; }
    auto get_keys() { fill_list(); return keys.begin(); }
    auto get_end() { return keys.end(); }

private:
    void fill_list();
    void add_keys(KVTree<K,V>* tree);
    void remove(KVTree<K, V>* top, KVTree<K, V>* bottom);
    void _list();
    int  subtrees();

template<class K, class V>
void KVTree<K,V>::fill_list()
{
    keys.clear();

    if (right != nullptr)
        add_keys(right);
}

template <class K, class V>
void KVTree<K, V>::add_keys(KVTree<K,V>* tree)
{
    if (tree->left != nullptr)
        add_keys(tree->left);
    keys.push_back(tree->key);
    if (tree->right != nullptr)
        add_keys(tree->right);
}

KVTree<string, int>::iterator keys = tree.get_keys();

while (keys.has_next())
{
    string  word = keys.next();
    int     count = *tree.search(word);
    cout << left << setw(20) << word <<
        right << setw(3) << count << endl;
}

list<string>::iterator keys = tree.get_keys();
list<string>::iterator end = tree.get_end();
while (keys != end)
{
    string  word = *keys++;
    int     count = *tree.search(word);
    cout << left << setw(20) << word <<
        right << setw(3) << count << endl;
}

Through several variations, the KVTree and its associate WordCount program has demonstrated templates and numerous STL features. The final version doesn't add any new features but integrates the features demonstrated above, achieving the example's final improvement. The add_keys function in Figure 4 (c) only stores the keys in the list that forms the tree's iterator. Consequently, the client must search the tree for each key or word (e).

public:
    list<K> keys;
    list<pair<K,V>> keys;

template <class K, class V>
void KVTree<K, V>::add_keys(KVTree<K,V>* tree)
{
    if (tree->left != nullptr)
        add_keys(tree->left);
    keys.push_back(tree->key);
    keys.push_back(make_pair(tree->key, tree->value));
    if (tree->right != nullptr)
        add_keys(tree->right);
}

list<string>::iterator keys = tree.get_keys();
list<string>::iterator end = tree.get_end();
list<pair<string, int>>::iterator keys = tree.get_keys();
list<pair<string, int>>::iterator end = tree.get_end();
while (keys != end)
{
    string  word = *keys++;
    int     count = *tree.search(word);
    cout << left << setw(20) << word << right <<
        setw(3) << count << endl;
    cout << left << setw(20) << keys->first << right <<
        setw(3) << keys->second << endl;
    keys++;
}

WordCount_map: map and iterator

The STL implements a map with a binary tree, providing fast insert and search operations. Although the operations slow as the tree becomes larger, the degradation is gradual, with the runtime generally (ignoring some worst-case scenarios) proportional to log n, where n is the number of tree nodes. In my opinion, the most striking feature of the STL map is its overloading of the index operator, [], to operate as both the insert and search functions. It functions as the search operation on the right-hand side of the assignment operator (i.e., when used as an r-value) and as the insert operation on the left-hand side (i.e., when used as an l-value).

#include <iostream>
#include <fstream>
#include <iomanip>
#include <string>
#include <cctype>
#include <map>											// (a)
using namespace std;

int main()
{
    map<string, int>	words;									// (b)
    ifstream		file("alice.txt");
    int			c;
    string		word;

    while ((c = file.get()) != EOF)
    {
        if (isalpha(c))
            word += tolower(c);
        else if (word.length() > 0)
        {
            words[word]++;									// (c)
            word.clear();
        }
    }

    for (map<string,int>::iterator i = words.begin(); i != words.end(); i++)			// (d)
        cout << left << setw(20) << i->first << right << setw(3) << i->second << endl;		// (e)

    return 0;
}

STL Functions And Containers With Comparators

The previous examples demonstrated STL containers and functions storing and operating on relatively simple data. The final examples revisit the Employee class and its functors to demonstrate how the STL works with complex objects. The examples organize objects based on their contents, requiring additional support from the client or application program. Programmers provide that support in the form of specialized functors called comparators. The examples reuse the Employee class and its two comparator functions with minor modifications noted in the figures, so they only present the application or main function. The omitted code is described in the first presentation and included with the downloadable code at the bottom of the page.

int main()
{
    vector<Employee> employees;								// (a)

    employees.push_back(Employee("Dilbert", ENGINEER, 400));
    employees.push_back(Employee("Alice", ENGINEER, 100));
    employees.push_back(Employee("Wally", ENGINEER, 200));
    employees.push_back(Employee("Asok", ENGINEER, 700));
    employees.push_back(Employee("PHB", MANAGER, 600));
    employees.push_back(Employee("Richard", MANAGER, 500));
    employees.push_back(Employee("Catbert", OFFICER, 300));

    sort(employees.begin(), employees.end(), compByName());				// (b)

    for (int i = 0; i < employees.size(); i++)
        cout << employees[i] << endl;
    cout << endl;

    sort(employees.begin(), employees.end(), compByNumber());				// (c)

    for (vector<Employee>::iterator i = employees.begin(); i != employees.end(); i++)
        cout << *i << endl;

    return 0;
}

Alice     2  100
Asok      2  700
Catbert   0  300
Dilbert   2  400
PHB       1  600
Richard   1  500
Wally     2  200

Catbert   0  300
Richard   1  500
PHB       1  600
Alice     2  100
Wally     2  200
Dilbert   2  400
Asok      2  700

int main()
{
    map<Employee, Employee, compByName> employees;								// (a)
    //map<Employee, Employee, compByNumber> employees;								// (b)

    Employee e1("Dilbert", ENGINEER, 400);									// (c)
    Employee e2("Alice", ENGINEER, 100);
    Employee e3("Wally", ENGINEER, 200);
    Employee e4("Asok", ENGINEER, 700);
    Employee e5("PHB", MANAGER, 600);
    Employee e6("Richard", MANAGER, 500);
    Employee e7("Catbert", OFFICER, 300);

    employees[e1] = e5;												// (d)
    employees[e2] = e5;
    employees[e3] = e6;
    employees[e4] = e6;
    employees[e5] = e7;
    employees[e5] = e7;
    employees[e7] = e7;

    for (map<Employee, Employee>::iterator i = employees.begin(); i != employees.end(); i++)
        cout << i->first << "Reports to: " << i->second << endl;

    return 0;
}

Alice     2  100  Reports to: PHB       1  600
Asok      2  700  Reports to: Richard   1  500
Catbert   0  300  Reports to: Catbert   0  300
Dilbert   2  400  Reports to: PHB       1  600
PHB       1  600  Reports to: Catbert   0  300
PHB       1  600  Reports to: Catbert   0  300
Wally     2  200  Reports to: Richard   1  500

Catbert   0  300  Reports to: Catbert   0  300
PHB       1  600  Reports to: Catbert   0  300
PHB       1  600  Reports to: Catbert   0  300
Alice     2  100  Reports to: PHB       1  600
Wally     2  200  Reports to: Richard   1  500
Dilbert   2  400  Reports to: PHB       1  600
Asok      2  700  Reports to: Richard   1  500

Downloadable Code

Four versions of the WordCount program count the unique words in a book and display the words and their counts to the console, demonstrating template classes and STL containers.