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 in favor of demonstrating STL classes - containers and support classes. Using the STL containers reduces the time and effort necessary to program a problem solution. 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 a container for the word. 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 implements WordCount with 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 features demonstrated above, achieving the example's final improvement. The Figure 4(c) add_keys function only stores the keys in the list forming 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;
}

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.