Are You Afraid of The Dark Too? Making More Sense of the STL

Well, you guessed it. If there weren't, I wouldn't be talking about it. Enter the multi-talented map container. map is a Pair Associative Container; it maps a key to a value. More than that, a map is sorted by its key, which has the fortunate effect of making it easily searchable by its key. Correspondingly, the type used for a key in a map container must be Less Than Comparable [Austern1998]^[3].

A map stores two objects per element; one is the key, the other the value. So that both key and value types can be any type, built-in or user-defined, the C++ Standard Library has a helper class called pair, which is parameterised on its first and second types:

template <class _T1, class _T2>
struct pair {
  pair( const _T1 & f, const _t2 & s )
    : first( f ), second( s ) { }
  _T1 first;
  _T2 second;
}; // from [STLPort2001]

map stores elements of type pair and uses first as the key and second as the value. (The pair type is much more generally useful, as we shall see). There is also a helper function for making pairs allowing us to add items to a map like this:

map< string, int > months;
months.insert( make_pair( "Jan", 1 ) );
months.insert( make_pair( "Feb", 2 ) );

Here we create a map with string as the key type and int as the value, and start adding months to the container.

There are two things to note about this piece of code. First, we've created a map and associated the value 1 with the string "Jan" and the value 2 with the string "Feb". This is straightforward enough. The second item of note is that a map is sorted on its key; printing the map "in order" demonstrates this^[4]:

void print_me(const pair<string, int> 
    &value){
  cout << value.first << "," 
       << value.second << "\n";
}
// ...
for_each( months.begin(), months.end(), 
        print_me );
// Output:
// Feb,2
// Jan,1

Remember that the key is the string type for our map months, and so "Feb" comes before "Jan", lexically speaking. Remember also that map stores pairs of elements, so naturally its iterators will point to a pair. There is a third thing to note there: this isn't really what you'd normally do with a map. Sure we can use a map as a method of sorting elements in a container, but its best feature is that it associates elements - keys and values. Being sorted is a side-effect of map's greatest attribute - the ability to efficiently find a value given its key.

map can be used as an associative array; it directly supports the array notation (square brackets [] in C++) to provide a key and obtain its associated value. Because our value type is a built-in integral type (which the switch statement requires) we can do the following:

void function( const string & s ) {
  switch(months[ s ] ) {
  case 1: // Jan
  case 2: // Feb
  }
}

Which is much more like our original requirement^[5].

There is a snag to this; you might ask yourself what does the map do if the element identified by s doesn't exist? We appear to have no way of knowing whether the lookup failed, because it isn't reasonable for operator[] to return an invalid value, since it cannot know what is valid. This suggests that operator[] for map never fails, which is in fact the case. If the lookup fails to locate the key provided, a new element with that key is created. The value for that key will be default constructed. operator[] actually returns a reference to the value, so you can change it using assignment:

months[ "Mar" ] = 3;

The snag is that this may not do what you expect - you may be creating a new element and not know it.

There is another method of searching a map which, in keeping with the standard algorithms, returns an iterator to the found element, or End if the item is not found. map provides its own member function for this because firstly the map contains pairs, so using the find() or find_if() algorithms would be clumsy, and partly because map itself is optimised for searching, and the algorithms don't know about this. Using the member function, you search directly for the key, and an iterator is returned:

map< string, int >::iterator p =
         months.find( "Jan" );
if(p != months.end()) {
  cout << p->second;  // the value
}

The other useful attribute of map is that it is a Unique Associative Container, meaning that it does not store duplicate keys. If you try to insert two values with the same key, the second insertion will fail. This failure is indicated by the return value from map::insert(), which is a pair object containing a map iterator and a bool. The iterator points either to the newly inserted element, in which case the bool is true, or to the already existing element with the same key, in which case the bool is false:

pair<map<string, int>::iterator, bool>
 p =  months.insert( make_pair("Apr", 4));
if(! p->second) { // the insertion failed
  cout << p->first->second;   
// print the value associated with "Mar"
// remember an iterator points to a pair 
// element
}

In practice, you won't need all this syntax. You will either want to know whether the insertion took place, or you will want to do something with value. In the first case, you can use:

if(!months.insert( 
      make_pair( "May", 5)->second){
// do something if insertion failed
}

and in the second, using the array syntax operator[] works fine:

months[ "Jun" ] = 6;

Whether it is less efficient to overwrite the value of an existing element or search for it first will depend upon what the value type is. As they say on the newsgroups, YMMV.

The set class has similarities with map; for instance, it contains only unique elements (it's a model of Unique Associative Container), is sorted by its key and is optimised for searching. It differs in one very important way: it contains single elements, rather than pairs. It is a Simple Associative Container [Austern1998], which means that its key and value types are the same thing.

In particular, this difference means you cannot use set as an associative array; it does not have an operator[] for array-like access to elements. So why have a set container at all?

Well, OK now we get into the realms of speculation (by some well-respected figures, it has to be said). The STL is not a collection of containers. It has been said that STL is merely a "specification of a library of algorithms" [Henney2001], not actually a collection of anything, really. What it means is that if you write your own container, algorithm, iterator, and it conforms to the requirements that STL places on such things, then it is just as much a part of the STL as those components shipped with the C++ Standard Library.

So back to set, and its raison d'être. We need to look behind the set container, at what makes it useful, before we can see its utility. We can guess that it models the concept of Set from mathematics. In fact, that would be inaccurate; mathematical set theory really concerns the operations on sets: Union; Intersection; Difference; Contains. In fact the STL has algorithms for providing these services, and they require that the range of iterators upon which they operate is sorted. This is a key issue, which we passed over fairly quickly in our last trip. The STL algorithms don't work on containers at all, they work with iterators. The container classes can be easily seen as various convenient ways of providing iterators and iterator ranges.

set is no exception. It is a container which happily allows the STL set algorithms to work according to the expected mathematical concepts of those operations ( [Austern1998]). It makes those operations efficient. For example, let's take set_intersection() as an example.

set< string > girl_names;
set< string > boy_names;
set< string > common_names;
set_intersection(
  girl_names.begin(), girl_names.end(),
  boy_names.begin(), boy_names.end(),
  inserter(common_names, 
            common_names.begin()));

set_intersection() takes two input ranges, and copies its result to an output range. Here we are using a particular type of iterator adaptor, called inserter, to add new elements to an output sequence, common_names in this case. We'll be looking at inserters later in our visit.

If you're familiar at all with mathematical sets, you will know that taking the intersection of two sets results in the elements common to both. The results we might expect from this operation could be:

Sam
Tracey
Nicola
Max
Eddie
Alex
Hilary

The point is that set_intersection() can be used with vector, or list, provided they are sorted in advance. The set container is well suited to this operation, and the other set operations for the same reason, because it is always sorted. We could have used list as the result sequence; it allows efficient random insertion of elements, but the fact is that the intersection of two sets results in a new, possibly empty, set in mathematics. The purpose of the set algorithms in STL is to closely model the mathematical meaning of them, and the set container provides support for that goal [Austern1998].

typedef string author;  
typedef string publication;  
typedef multimap< author, publication > index;
pair< index::iterator, index::iterator > range;

You may find that the enforced uniqueness of elements in a set, and possibly the fact it is an ordered container, useful characteristics in and of themselves, too. set is by no means limited in its use to the standard algorithms.

There are three container adaptors provided with the C++ Standard Library:

stack
queue
priority_queue

In Computer Science, these are discrete data structures in their own right, each with distinct properties and behavioural characteristics. In STL, however, they are implemented in terms of the other containers, simply because they can.

Consider the operations on a stack. You, as the programmer, get access only to the top element in the container. It is a LIFO (last-in, first-out) container. You can add (push) an element, and remove (pop) that element. You cannot look at every element (without popping each one in turn), nor can you sort a stack. In this case, then, we could easily use one of the three sequence containers, and use only those operations permitted by the interface of a stack.

The stack container does this for you, and "adapts" the interface of deque, such that push() becomes deque<>::push_back(), and pop() becomes deque<>::pop_back(). The main utility in using the STL stack adaptor over using deque directly is that you are stating your intent: this program requires a stack, and is restricting its usage to that of a stack.

There is one catch to this. Normally a stack's pop() method will remove the top element of the stack and return it:

my_stack< int > s;
// ...
int p = s.pop();

The STL stack adaptor's pop() method returns nothing, and this may seem rather odd. Looking deeper, however, we notice that there is a method top() which returns a reference to the top element.

The reason for this is efficiency. One of the things you may need to do with a stack is to pop off a number of elements, discarding each one. Since the element is being removed, if pop() were to return it, it would have to make a copy and return it by value. If that value is then discarded, at least one copy of a possibly expensive object has been made. The alternative is to allow a copy to be made prior to its removal if that value is needed:

stack< string > s;
// ...
string name = s.top();
s.pop();

Again, a queue is a well-known data structure which allows first-in, first-out (FIFO) functionality. This means it operates like a double-ended stack, where you have access to the elements at either end of the container. As with stack, you cannot access the other elements. push() adds a new element to the back of the queue, pop() removes one from the front of the queue. The methods back() and front() provide references to those elements respectively, allowing you to make copies if required.

priority_queue is like stack more than queue, the difference being that the top element is always the largest (it doesn't have a good four letter acronym!). Hence, push() adds a new element to the priority_queue, and pop() removes the top one, which will always be the largest, according to some comparison. The default comparison is the standard functor less<>, which by default uses operator<() for the given type, but you can provide your own comparator if required.

All of the container adaptors allow you to choose your own underlying container upon which they will be based. By default, stack and queue use deque as their implementation, and priority_queue uses vector. Any container you provide must conform to the adaptor's requirements. These are ( [Austern1998]):

We cannot change the behaviour of copy() easily, but we could easily create an iterator type that overrides the default meaning of operator=() to perform push_back() on the container.

Enter the Back Insert Iterator. It works with any Back Insertion Sequence (a container with a push_back() method, which means list, vector and deque only, in the C++ Standard Library) and works like this:

list< string > names;
// initialise names with suitable elements
list< string >target;
copy( names.begin(), names.end(),
           back_inserter( target ) );

There is a corresponding Front Insert Iterator which works for containers with push_front(), which means list and deque only.

However, what happens if your target isn't a Back Insertion Sequence, or you wish to add elements to the middle of the container? Ah well, these library designers they think of everything. There is another Insert Iterator called, well, inserter. As well as the container itself, you provide an iterator to where you would like insertions to start. Thus, the following snippet is equivalent to our previous example:

list< string > names;
// initialise names with suitable elements
list< string >target;
copy( names.begin(), names.end(), inserter( target, target.end() ) );

The difference being that inserter requires that the target container has an insert method which takes an iterator as the insertion point as well as the value to be added. This includes the Associative Containers we looked at previously. You will recall that the Associative Containers are all sorted. In their case, this insertion-point iterator is merely a hint - the position at which to start looking for an existing element. When using an inserter into a map or set, it's usually best where possible to use begin() or end() as the iterator argument to inserter.

It sometimes makes sense to read a container backwards. It may be for the purposes of finding any subliminal messages, or perhaps reading in reverse alphabetical order. For whatever reason, there are two ways to do this.

The first and simplest method is when you are working directly with a container. Each of the standard containers provide an rbegin() and rend() method. rbegin() returns a Reverse Iterator, which is the equivalent in position of end(), except that incrementing it moves it backwards. Similarly, rend() has the equivalent position of begin() in the container.

The difficulty comes when you have an algorithm which accepts Forward Iterators, but for reasons of efficiency perhaps wants to work with Reverse Iterators. Consider a function called find_last_of(). It takes an iterator range and a value to find. You don't really wish to expose the implementation too much by requiring Reverse Iterators, but then searching the entire range from start to finish might be very inefficient. You need some way of converting a Forward Iterator into a Reverse Iterator. Once again, the C++ Standard is ahead of you, and provides an Iterator Adaptor for exactly this purpose.

reverse_iterator changes the direction of a given Bi-Directional Iterator. All of the standard containers provide Bi-Directional Iterators from their begin() and end() methods. This means you can now write find_last_of() like this:

template<typename Iterator, typename Value>
Iterator find_last_of(Iterator begin,
       Iterator end, Value v ){
  reverse_iterator<Iterator> rbegin(end);
  reverse_iterator<Iterator> rend(begin);
  reverse_iterator< Iterator > result = 
              find( rbegin, rend, v );
  return result.base();
}

That last line which returns the base() of the Reverse Iterator is needed because a Reverse Iterator cannot just convert back to a normal one. For technical reasons. It has to do with the fact that an iterator range is a half-open range, meaning it contains the first but not the last elements [Love2001], [Josuttis1999]. The reversed End (one after the end) is now one before the start, which is not a valid position. Therefore, some hand-waving is needed to make it valid.