Using the STL

The STL is a library whose parts are designed to work together. The STL components are tools, but they are also building blocks to create other tools. Let’s illustrate this with an example. Suppose you want to write a program that lets the user enter words. At the end, you’d like a record of the words as they were entered, an alphabetical list of the words used (capitalization differences ignored), and a record of how many times each word was entered. To keep things simple, let’s assume that the input contains no numbers or punctuation.

Entering and saving the list of words is simple enough. Following the example of Listings 16.8 and 16.9, you can create a vector<string> object and use push_back() to add input words to the vector:

vector<string> words;
string input;
while (cin >> input && input != "quit")
    words.push_back(input);

What about getting the alphabetic word list? You can use sort() followed by unique(), but that approach overwrites the original data because sort() is an in-place algorithm. There is an easier way that avoids this problem. You can create a set<string> object and copy (using an insert iterator) the words from the vector to the set. A set automatically sorts its contents, which means you don’t have to call sort(), and a set allows only one copy of a key, so that takes the place of calling unique(). Wait! The specification called for ignoring the case differences. One way to handle that is to use transform() instead of copy() to copy data from the vector to the set. For the transformation function, you can use one that converts a string to lowercase:

set<string> wordset;
transform(words.begin(), words.end(),
    insert_iterator<set<string> > (wordset, wordset.begin()), ToLower);

The ToLower() function is easy to write. You just use transform() to apply the tolower() function to each element in the string, using the string both as source and destination. Remember, string objects, too, can use the STL functions. Passing and returning the string as a reference means the algorithm works on the original string without having to make copies. Here’s the code for ToLower():

string & ToLower(string & st)
{
    transform(st.begin(), st.end(), st.begin(), tolower);
    return st;
}

One possible problem is that the tolower() function is defined as int tolower(int), and some compilers want the function to match the element type, which is char. One solution is to replace tolower with toLower and to provide the following definition:

char toLower(char ch) { return tolower(ch); }

To get the number of times each word appears in the input, you can use the count() function. It takes a range and a value as arguments, and it returns the number of times the value appears in the range. You can use the vector object to provide the range and the set object to provide the list of words to count. That is, for each word in the set, you can count how many times it appears in the vector. To keep the resulting count associated with the correct word, you can store the word and the count as a pair<const string, int> object in a map object. The word will be the key (just one copy), and the count will be the value. This can be done in a single loop:

map<string, int> wordmap;
set<string>::iterator  si;
for (si = wordset.begin(); si != wordset.end(); si++)
    wordmap.insert(pair<string, int>(*si, count(words.begin(),
    words.end(), *si)));

The map class has an interesting feature: You can use array notation with keys that serve as indexes to access the stored values. For example, wordmap["the"] would represent the value associated with the key "the", which in this case is the number of occurrences of the string "the". Because the wordset container holds all the keys used by wordmap, you can use the following code as an alternative and more attractive way of storing results:

for (si = wordset.begin(); si != wordset.end(); si++)
    wordmap[*si] = count(words.begin(), words.end(), *si);

Because si points to a string in the wordset container, *si is a string and can serve as a key for wordmap. This code places both keys and values into the wordmap map.

Similarly, you can use the array notation to report results:

for (si = wordset.begin(); si != wordset.end(); si++)
    cout << *si << ": " << wordmap[*si] << endl;

If a key is invalid, the corresponding value is 0.

Listing 16.19 puts these ideas together and includes code to display the contents of the three containers (a vector with the input, a set with a word list, and a map with a word count).

Listing 16.19. usealgo.cpp

//usealgo.cpp -- using several STL elements
#include <iostream>
#include <string>
#include <vector>
#include <set>
#include <map>
#include <iterator>
#include <algorithm>
#include <cctype>
using namespace std;

char toLower(char ch) { return tolower(ch); }
string & ToLower(string & st);
void display(const string & s);

int main()
{
    vector<string> words;
    cout << "Enter words (enter quit to quit): ";
    string input;
    while (cin >> input && input != "quit")
        words.push_back(input);

    cout << "You entered the following words: ";
    for_each(words.begin(), words.end(), display);
    cout << endl;

    // place words in set, converting to lowercase
    set<string> wordset;
    transform(words.begin(), words.end(),
        insert_iterator<set<string> > (wordset, wordset.begin()),
        ToLower);
    cout << " Alphabetic list of words: ";
    for_each(wordset.begin(), wordset.end(), display);
    cout << endl;

    // place word and frequency in map
    map<string, int> wordmap;
    set<string>::iterator si;
    for (si = wordset.begin(); si != wordset.end(); si++)
        wordmap[*si] = count(words.begin(), words.end(), *si);

    // display map contents
    cout << " Word frequency: ";
    for (si = wordset.begin(); si != wordset.end(); si++)
        cout << *si << ": " << wordmap[*si] << endl;

    return 0;
}

string & ToLower(string & st)
{
    transform(st.begin(), st.end(), st.begin(), toLower);
    return st;
}

void display(const string & s)
{
    cout << s << " ";
}

Here is a sample run of the program in Listing 16.19:

Enter words (enter quit to quit):
The dog saw the cat and thought the cat fat
The cat thought the cat perfect
quit
You entered the following words:
The dog saw the cat and thought the cat fat The cat thought the cat perfect

Alphabetic list of words:
and cat dog fat perfect saw the thought

Word frequency:
and: 1
cat: 4
dog: 1
fat: 1
perfect: 1
saw: 1
the: 5
thought: 2

The moral here is that your attitude when using the STL should be to avoid writing as much code as possible. STL’s generic and flexible design should save you lots of work. Also the STL designers are algorithm people who are very much concerned with efficiency. So the algorithms are well chosen and inline.

Other Libraries

C++ provides some other class libraries that are more specialized than the examples covered so far in this chapter. For instance, the complex header file provides a complex class template for complex numbers, with specializations for float, long, and long double. The class provides standard complex number operations, along with standard functions that can be used with complex numbers. The C++11 random header file extends random number functionality.

Chapter 14 introduced another example, the valarray template class, supported by the valarray header file. This class template is designed to represent numeric arrays and provides support for a variety of numeric array operations, such as adding the contents of one array to another, applying math functions to each element of an array and applying linear algebra operations to arrays.