The STL
The STL is the standard container and algorithm library of C++. STL has a well deserved reputation as both hard to learn and amazingly powerful. This short introduction introduces the core ideas and shows some basic examples of how the library is used.
This is a only quick overview of the STL and how to use it. It glosses over details such as C++ and template syntax, implementation details, value versus reference types, functors, adaptors and allocators. All STL classes and functions are declared in the std namespace, which I've omitted for clarity. The examples assume a "using namespace std;".
Containers
Containers are standard classes for grouping objects. There are two basic types. The first are sequences, which store a group of objects in a particular order, like an array. Unlike standard arrays though, they are unbounded in length. Examples are vectors and lists.
The other type is the associative container. These map one type of object to another, as in an associative array. For example, a string to string associative container could map words to their dictionary definitions. The map and set class are commonly used associative containers.
A key difference between STL containers, and containers in some other languages, is that they are type safe. A vector<int> in C++ can hold only integers and nothing else, and a vector<string> can only hold strings. This differs from, for example, Java (1.4 and earlier, anyway1) where one can put any sort of object into a Vector container.
The most important methods for sequences are:
size() -- returns the number of objects in the container
begin() -- returns an iterator pointing to the first object in the container (see below)
end() -- returns an iterator past the end of the container (see below)
push_back() -- puts an object into the container, behind any other objects
Vectors2 can be dereferenced like arrays with square brackets (e.g. x = seq[n]) to get the nth object.
The following shows how sequences can be used:
vector<int> intvec;
intvec.push_back(1);
intvec.push_back(2);
intvec.push_back(3);
cout << intvec[0] << endl;
The most important methods for associative containers are:
size() -- returns the number of object-pairs in the container
begin() -- returns an iterator pointing to the first object in the container (see below)
end() -- returns an iterator past the end of the container (see below)
insert() -- inserts an object pair into the container; it is not necessarily put in any specific order
Maps can be dereferenced like arrays with square brackets too (e.g. x = map[n]) to get the object that maps to n.
The following shows how associative containers can be used:
map<string, string> dictionary;
dictionary["TLA"] = "Three Letter Acronym";
dictionary["RTFM"] = "Read The Fine Manual";
cout << dictionary["TLA"] << endl;
Iterators
An iterator is a class that has all the logic for "iterating", or going over each element in a container. Each container class has its own particular type of iterator. The iterator type of a container c is typedefed as c::iterator.
The key to iterators is they all behave the same way; they are modelled on the pointer concept. A pointer to type T yields a actual T when the * operator is applied to it. Likewise, an iterator for a container yields the container's value_type3 when * is applied. Similarly, p++ advances p to the next object, regardless of whether p is a pointer or an iterator. And finally, just as pointers have a special invalid sentinel, NULL, each container has a special "end" iterator to indicate it doesn't point to anything.
The type of container determines what you can do with the iterator, but all iterators have these properties:
- *(container::iterator) gives container::value_type
- (container::iterator)++ advances the iterator
- container::iterator will equal container::end() when it has reached the end of the container
The simplest way to grasp iterators is to see an example:
vector<int> intvec;
vector<int>::iterator it;
for (it = intvec.begin(); // a "pointer" to the first value in intvec
it != intvec.end(); // a "pointer" one past the end of intvec
it++) { // advance the iterator by one
int x = *it; // dereference the iterator to get the value
cout << x << endl; // x is like any other int
}
In addition to normal iterators, most types have reverse_iterators, const_iterators, and const_reverse_iterators. These are used for iterating through the container backwards, iterating through const (immutable) containers (and dereference to const types), and a combination of the two, respectively.
Algorithms
Containers and iterators provide a standard way of grouping and accessing objects. The STL builds on this framework to provide generic algorithms. These algorithms can be written once and function with any object4 and they usually yield binary code that is just as efficient as a specialized algorithm. They are also "type safe", meaning that coding errors where the wrong type is used will be caught at compile time.
The standard algorithms take two iterators -- a begin and end -- plus additional arguments (sometimes also iterators). The algorithm uses the iterators to traverse the container and perform whatever magic on the contents within.
Some examples with the find algorithm:
vector<int> intvec;
intvec.push_back(1);
intvec.push_back(10);
intvec.push_back(101);
list<string> strlist;
strlist.push_back("one");
strlist.push_back("ten");
strlist.push_back("one hundred and one");
float floatarray = { 1.0, 10.0, 101.0 };
int found1;
vector<int>::iterator it1;
it1 = find(intvec.begin(), intvec.end(), 10); // find the number in a vector
if (it1 != intvec.end())
found1 = *it1;
string found2;
list<string>::iterator it2;
it2 = find(strlist.begin(), strlist.end(), "ten");
// the same find algorithm works with strings in lists!
if (it2 != strlist.end())
found2 = *it1;
float found3;
float *it3;
it3 = find(floatarray, floatarray + 3, 10.0);
// the same find algorithm also works with floats in an array!
if (it3 != floatarray + 3)
found3 = *it3;
Note the same call to find works with two different container types plus standard non-STL arrays, all containing a different value type. Even more remarkable, this one definition of find will work with any container with an iterator that supports dereferencing and advancing. Likewise, it will work with any value type that can be compared for equality. And lastly, if you try passing the wrong type in for any of the parameters, the compiler will catch it at compile time (whether the error message is meaningful is a different story, though...).
The example above using an array is particularly interesting: it shows that the STL algorithms don't necessarily need to operate on stl containers. As shown, pointers can be used as iterators. So not only are iterators based on the pointer concept, but pointers can actually be used as iterators! Note that the NULL pointer isn't used to signal the end of an iteration. Instead, one past the end is used, so that if pointer p points to the last element, ++p is the "end of iteration" marker.
Miscellaneous
Some examples that tie things together and show some useful tricks.
1. Insert iterators simplify inserting into containers:
list<int> l;
back_inserter back_it(l);
*back_it++ = 0;
*back_it++ = 1;
*back_it++ = 2;
/* l = [0, 1, 2] */
front_inserter front_it(l);
*front_it++ = 0;
*front_it++ = 1;
*front_it++ = 2;
/* l = [2, 1, 0, 0, 1, 2] */
2. The istream_iterator and ostream_iterator classes can be used to read or write entire containers to streams
list<int> l;
copy(istream_iterator<int>(cin), istream_iterator<int>(), back_inserter(l));
copy(l.begin(), l.end(), ostream_iterator<int>(cout, "\n"));
Further Reading
- http://www.cs.brown.edu/people/jak/proglang/cpp/stltut/tut.html - a nice tutorial with diagrams and examples
- http://www.sgi.com/tech/stl/ - an excellent STL reference
- http://www.sgi.com/tech/stl/drdobbs-interview.html - an interview with STL's inventor, Alex Stepanov
- http://www.stlport.org/resources/StepanovUSA.html - listen to Stepanov diss OO, talk philosophy, discuss Italian literature, and of course, talk about the origins of STL
Footnotes
[1] 1.5 has generics, which provide the type safety of templates
[2] strictly speaking, any random access container, of which vector is by far the most commonly used; this contrasts to list, which is not random access
[3] container::value_type is defined in each STL container as the value it holds; e.g. vector<int>::value_type will be int, map<string, string>::value_type will be pair<string, string>
[4] as long as the object follows a few guidelines, like overloading operator== to test for equivalence