MFC Programmer's SourceBook : Thinking in C++

The Standard Template Library

The C++ STL [53] is a powerful library intended to satisfy the vast bulk of your needs for containers and algorithms, but in a completely portable fashion. This means that not only are your programs easier to port to other platforms, but that your knowledge itself does not depend on the libraries provided by a particular compiler vendor (and the STL is likely to be more tested and scrutinized than a particular vendor’s library). Thus, it will benefit you greatly to look first to the STL for containers and algorithms, before looking at vendor-specific solutions.

A fundamental principle of software design is that all problems can be simplified by introducing an extra level of indirection . This simplicity is achieved in the STL using iterators to perform operations on a data structure while knowing as little as possible about that structure, thus producing data structure independence. With the STL, this means that any operation that can be performed on an array of objects can also be performed on an STL container of objects and vice versa. The STL containers work just as easily with built-in types as they do with user-defined types. If you learn the library, it will work on everything.

The drawback to this independence is that you’ll have to take a little time at first getting used to the way things are done in the STL. However, the STL uses a consistent pattern, so once you fit your mind around it, it doesn’t change from one STL tool to another.

Consider an example using the STL set class. A set will allow only one of each object value to be inserted into itself. Here is a simple set created to work with ints by providing int as the template argument to set:

//: C20:Intset.cpp
// Simple use of STL set
#include <set>
#include <iostream>
using namespace std;

int main() {
 set<int> intset;
  for(int i = 0; i < 25; i++)
    for(int j = 0; j < 10; j++)
      // Try to insert multiple copies:
      intset.insert(j);
  // Print to output:
 copy(intset.begin(), intset.end(),
   ostream_iterator<int>(cout, "\n"));
} ///:~

The insert( ) member does all the work: it tries putting the new element in and rejects it if it’s already there. Very often the activities involved in using a set are simply insertion and a test to see whether it contains the element. You can also form a union, intersection, or difference of sets, and test to see if one set is a subset of another.

In this example, the values 0 - 9 are inserted into the set 25 times, and the results are printed out to show that only one of each of the values is actually retained in the set.

The copy( ) function is actually the instantiation of an STL template function, of which there are many. These template functions are generally referred to as “the STL Algorithms” and will be the subject of the following chapter. However, several of the algorithms are so useful that they will be introduced in this chapter. Here, copy( ) shows the use of iterators. The set member functions begin( ) and end( ) produce iterators as their return values. These are used by copy( ) as beginning and ending points for its operation, which is simply to move between the boundaries established by the iterators and copy the elements to the third argument, which is also an iterator, but in this case, a special type created for iostreams. This places int objects on cout and separates them with a newline.

Because of its genericity, copy( ) is certainly not restricted to printing on a stream. It can be used in virtually any situation: it needs only three iterators to talk to. All of the algorithms follow the form of copy( ) and simply manipulate iterators (the use of iterators is the “extra level of indirection”).

Now consider taking the form of Intset.cpp and reshaping it to display a list of the words used in a document. The solution becomes remarkably simple.

//: C20:WordSet.cpp
#include <string>
#include <fstream>
#include <iostream>
#include <set>
#include "../require.h"
using namespace std;

int main(int argc, char* argv[]) {
  requireArgs(argc, 1);
  ifstream source(argv[1]);
  assure(source, argv[1]);
  string word;
  set<string> words;
  while(source >> word)
    words.insert(word);
  copy(words.begin(), words.end(),
    ostream_iterator<string>(cout, "\n"));
  cout << "Number of unique words:" 
    << words.size() << endl;
} ///:~

The only substantive difference here is that string is used instead of int. The words are pulled from a file, but everything else is the same as in Intset.cpp. The operator>> returns a whitespace-separated group of characters each time it is called, until there’s no more input from the file. So it approximately breaks an input stream up into words. Each string is placed in the set using insert( ), and the copy( ) function is used to display the results. Because of the way set is implemented (as a tree), the words are automatically sorted.

Consider how much effort it would be to accomplish the same task in C, or even in C++ without the STL.

[53] Contributed to the C++ Standard by Alexander Stepanov and Meng Lee at Hewlett-Packard.

Contents | Prev | Next