Structure of the Library

The library contains five main kinds of components:

algorithm: defines a computational procedure. See Algorithms.

container: manages a set of memory locations. See Containers.

iterator: provides a means for an algorithm to traverse through a container. See Iterators.

function object: encapsulates a function in an object for use by other components. See Function objects.

adaptor: adapts a component to provide a different interface. See Adaptors.

Such decomposition allows the user to dramatically reduce the component space. For example, instead of providing a search member function for every kind of container, provide a single version that works with all of them as long as a basic set of requirements is satisfied. The following description helps clarify the structure of the library. If software components are tabulated as a three-dimensional array, where one dimension represents different data types (e.g. int, double), the second dimension represents different containers (e.g. vector, linked-list, file), and the third dimension represents different algorithms on the containers (e.g. searching, sorting, rotation), if i, j, and k are the size of the dimensions, then i \times j \times k different versions of code have to be designed. By using template functions that are parameterized by a data type, only j \times k versions are needed. Further, by making the algorithms work on different containers, merely j+k versions are needed. This significantly simplifies software design work and also makes it possible to use components in the library together with user defined components in a very flexible way. A user may easily define a specialized container class and use the library's sort function to sort it. A user may provide a different comparison function for the sort either as a regular pointer to a comparison function, or as a function object (an object with an operator() defined) that does the comparisons. If a user needs to iterate through a container in the reverse direction, the reverse_iterator adaptor allows that.

The library extends the basic C++ paradigms in a consistent way, so it is easy for a C/C++ programmer to start using the library. For example, the library contains a merge template function. When a user has two arrays a and b to be merged into c it can be done with:

int a[1000];
int b[2000];
int c[3000];
...
merge(a, a + 1000, b, b + 2000, c);

When a user wants to merge a vector and a list (both of which are template classes in the library) and put the result into a freshly allocated uninitialized storage it can be done with:

vector a;
list b;
...
Employee* c = allocate(a.size() + b.size(), (Employee*)0);
merge(a.begin(), a.end(), b.begin(), b.end(),
      raw_storage_iterator(c));

where begin() and end() are member functions of containers that return the right types of iterators or pointer-like objects that allow the merge to do the job and raw_storage_iterator is an adapter that allows algorithms to put results directly into uninitialized memory by calling the appropriate copy constructor.

In many cases it is useful to iterate through input/output streams in the same way as through regular data structures. For example, to merge two data structures and then store them in a file, it would be nice to avoid creation of an auxiliary data structure for the result, instead storing the result directly into the corresponding file. The library provides both istream_iterator and ostream_iterator template classes to make many of the library algorithms work with I/O streams that represent homogenous aggregates of data. Here is a program that reads a file of integers from the standard input, removes all those that are divisible by its command argument, and writes the result to the standard output:

main(int argc, char** argv)
{
    if (argc != 2) throw("usage: remove_if_divides integer\n");
    remove_copy_if(istream_iterator(cin), istream_iterator(),
                   ostream_iterator(cout, "\n"),
                   not1(bind2nd(modulus(), atoi(argv[1]))));
}

All the work is done by remove_copy_if which reads integers one by one until the input iterator becomes equal to the end-of-stream iterator that is constructed by the constructor with no arguments. (In general, all the algorithms work in a "from here to there" fashion taking two iterators that signify the beginning and the end of the input.) Then remove_copy_if ; writes the integers that pass the test onto the output stream through the output iterator that is bound to cout. As a predicate, remove_copy_if uses a function object constructed from a function object, modulus<int>, which takes i and j and returns i%j, as a binary predicate and makes it into a unary predicate by using bind2nd to bind the second argument to the command line argument, atoi(argv[1]). Then the negation of this unary predicate is obtained using function adaptor not1.

A somewhat more realistic example is a filter program that takes a file and randomly shuffles its lines.

main(int argc, char**)
{
    if (argc != 1) throw("usage: shuffle\n");
    vector v;
    copy(istream_iterator(cin), istream_iterator(),
         inserter(v, v.end()));
    random_shuffle(v.begin(), v.end());
    copy(v.begin(), v.end(), ostream_iterator(cout));
}

In this example, copy moves lines from the standard input into a vector, but since the vector is not pre-allocated it uses an insert iterator to insert the lines one by one into the vector. (This technique allows all of the copying functions to work in the usual overwrite mode as well as in the insert mode.) Then random_shuffle shuffles the vector and another call to copy copies it onto the cout stream.