C/C++ Users Journal December, 2005
The Standard Template Library (STL) is one of the most important additions to the C++ Standard Library [1]. By refining the general notion of a sequence of data objects, the STL makes it possible to apply generic programming techniques to manage data collections. The TR1 Library enhances the STL by providing five new forms of data collections and four new callable types to manipulate data objects. We'll look at all of these in the next few months, but first, we'll look at the fundamental design ideas behind the STL.
The STL's fundamental programming constructs for managing data are iterators and algorithms. Iterators point into sequences of data objects. Algorithms manipulate iterators and the data objects that they point to. Some algorithms manipulate their data objects directly; others manipulate them with callable objects supplied by the algorithm's caller. Sometimes a program uses a container to manage a sequence of data objects for an algorithm; at other times, the sequence is managed by some other data structure, such as an istream, an ostream, or a C-style array. It doesn't matter what the data structure that manages a sequence is; if you can get suitable iterators from the data structure, you can apply an algorithm to the sequence that it controls.
A sequence is zero or more data objects that follow each other in a well-defined order [2]. For example, if we break the previous sentence into individual words, we get a sequence consisting of "A," "sequence," "is," and so on. If we sort the words into alphabetical order, we get a different sequence containing "A," "a," "data," and so on. If, instead, we break the same sentence into individual letters, we get the sequence 'A,' ' ,' 's,' and so on. As you can see, elements of any sequence that aren't at the ends always have a predecessor and a successor, and if we don't change the sequence, the predecessor and successor of an element also don't change.
An iterator is like a bookmark—it can be used to keep track of where you are in a sequence. When you know where you are in a sequence, there are three basic things you can do: You can look at the element at your current position, you can move to that element's successor in the sequence, and you can move to that element's predecessor in the sequence. When you have an iterator [3], you do these things by dereferencing the iterator with operator*, incrementing the iterator with operator++, and decrementing the iterator with operator--. Thus, an iterator can be used to examine elements in a sequence and to move through a sequence.
When you're looking at an element in a sequence, you might want to write a value to it, and you might want to read its value. In most cases, these two operations are done on separate sequences [4], so a sequence can usually be either an output sequence (for writing) or an input sequence (for reading).
When an algorithm writes data to a sequence, it uses what the C++ Standard calls an "output iterator." There aren't many things you can do with an output iterator. You can copy it, you can dereference it and assign a value to the dereferenced iterator, and you can increment it. In fact, that's the definition of an output iterator. A type Iter is an output iterator if it is copy constructible and assignable (as defined by the Standard), and the following expressions are valid:
*dest = value; *dest++ = value;
These two expressions each write a value to the output sequence at the position pointed to by dest. In the first expression, dest can be an object of type Iter or it can be an object of type const Iter. The second expression also advances the iterator to point to the next element in the output sequence, so the type of dest here must be Iter and not const Iter.
++dest; dest++;
These two expressions advance the iterator to point to the next element in the output sequence.
Output iterators usually stand alone. An algorithm that writes to an output sequence takes a single iterator that designates that sequence. The algorithm can't determine where the end of the sequence is, so it's up to the caller to make sure that the output sequence is long enough for whatever the algorithm is going to do. Sometimes that's done by passing an unbounded sequence, such as an output stream. Sometimes it's done by passing an insert iterator that knows how to insert a new element at the end of a sequence. And sometimes it's done by passing length information, in the form of an explicit element count or a bounded input sequence that is no longer than the output sequence; see Listing 1 for examples.
When a program reads data, it has to know when it has reached the end of the data, so most STL algorithms that read data expect an input sequence that is delineated by a pair of iterators, the first pointing to the first element in the sequence and the second pointing to the end of the sequence. The end of the sequence is not the last element; conceptually, it's a possibly nonexistent element that comes after the last element in the sequence. So most algorithms move through their input sequence with code that looks something like this:
template <class Iter>
void algorithm(Iter first, Iter last)
{ // apply algorithm to each element in
//sequence
while(first != last)
{ // apply algorithm to current element
// do something with *first
++first;
}
}
This algorithm is a template function that takes any iterator type as its template parameter. For this algorithm to work, the type Iter must be comparable so that we can use operator!= to terminate the while loop; it must be dereferenceable so we can get to the element that it points to; and it must be incrementable so we can move to the next element in the sequence. These three requirements, expressed a bit more formally, are the essence of what the C++ Standard calls an "input iterator." A type Iter is an input iterator if it is copy constructible, assignable, equality comparable, and the following expressions are valid:
*iter *iter++ iter->mbr
These three expressions dereference the iterator object iter. In the first, iter can be an object of type Iter or an object of type const Iter. The expression evaluates to an object that is convertible to Ty [5], where Ty is the type of the element in the sequence. In the second, iter must be an object of type Iter. The expression evaluates to an object that is convertible to Ty, and it advances the iterator to point to the next element in the sequence. In the third, iter can again be an object of type Iter or of type const Iter. The expression is equivalent to (*iter).mbr. Of course, (*iter).mbr must be well defined for this use of operator-> to be meaningful.
++iter iter++
In these two expressions, iter must be of type Iter. They both advance the iterator to point to the next element in the sequence.
One of the most important things to remember about input iterators is that, after you increment an input iterator, any copies of that iterator are no longer usable.
Input iterators can't do much and with good reason: They're used with input sequences that are fragile. The most common example of such an input sequence is a sequence of characters typed at the console. There's no way to go backwards through the sequence; once the characters have been read, they're gone. Some algorithms don't need more than that, though. For example, std::copy can copy from a sequence that is defined by an input iterator:
template <class InIt, class OutIt>
InIt copy(InIt first, InIt last, OutIt dest)
{ // copy input range to dest
while (first != last)
*dest++ = *first++;
}
Note that the only operations performed on the input iterators first and last are those that we saw earlier in the requirements: The code compares them for equality, it dereferences first, and it increments first. So we know that this code will work with any iterator that satisfies the requirements for an input iterator. That doesn't mean that we can't call copy with more powerful iterators, which we'll look at shortly. It means that copy doesn't need more powerful iterators to do its job. It also doesn't mean that we can only copy a sequence that doesn't allow backing up. It means that copy will work on any sequence at all.
Some algorithms can't be written without being able to look back at earlier elements. For example, the algorithm adjacent_find looks for a pair of adjacent elements that compare equal. It can be written like this:
template <FwdIt>
FwdIt adjacent_find(FwdIt first, FwdIt last)
{ // find first pair of equal elements
if (first == last)
return last;
FwdIt prev = first++;
while (first != last)
if (*prev == *first)
return prev;
else
prev = first++;
return last;
}
The iterator prev trails behind first. Because we have to look at the value of the element that prev points to, we can't use an input iterator here: Incrementing first would make prev unusable. We need a more powerful iterator, one that allows hanging on to an old position. We can do this with a forward iterator. A forward iterator satisfies all the requirements for an input iterator, plus a few more:
*iter *iter++ iter->mbr
The first expression evaluates to an object of type Ty if iter points to an element of a sequence whose elements can't be modified, or Ty& if iter points to an element of a sequence whose elements can be modified. The second expression does the same thing, and in addition, advances iter to point to the next element in the sequence. The third expression evaluates to a const reference to (*iter).mbr if iter points to an element of a sequence whose elements can't be modified; otherwise, it evaluates to a reference to (*iter).mbr. In addition, incrementing a forward iterator does not affect the usability of copies of that iterator. Having operator* return a reference when the iterator points into a sequence whose elements can be modified means that forward iterators can also be used in algorithms that require output iterators.
The next step up in iterator power is to a bidirectional iterator. As the name suggests, a bidirectional iterator can move through a sequence in two directions. It meets all the requirements of a forward iterator, plus these:
--iter iter-- *iter--
All of these expressions change the iterator to point to the previous element in the sequence. The third expression returns a copy of the element that the iterator pointed to before it moved the iterator. For example:
template <class BidIt>
void reverse(BidIt first, BidIt last)
{ // reverse elements in a range
while (first != last && first != --last)
swap(*first++, *last);
}
This algorithm compares two iterators, and it increments and decrements various iterators. Thus, it requires a bidirectional iterator. In addition, because it swaps the elements that the iterators point to, the elements must be both readable and writable. That is, the sequence designated by the pair of iterators first and last is both a bounded input sequence and an output sequence. The most powerful algorithms, which require the most powerful iterators, often examine and modify the contents of their input range.
The most powerful form of iterator is a random access iterator. As the name suggests, it doesn't require an algorithm to examine elements of the underlying sequence in order; it permits random movements within the sequence. It meets all the requirements for a bidirectional iterator, plus these:
iter += n iter + n n + iter iter -= n iter - n
Each of these moves n positions from the element that the iterator points to.
iter1 - iter2
This expression evaluates to the number of elements traversed in moving from the element pointed to by iter1 to the element pointed to by iter2. The value can, of course, be negative.
iter[n]
This expression evaluates to a const reference to the element that is n elements beyond the element pointed to by iter, or before that element if n is negative.
iter1 < iter2 iter1 <= iter2 iter1 > iter2 iter1 >= iter2
The first expression evaluates to a value that is convertible to bool and tells you whether the element pointed to by iter1 precedes the element pointed to by iter2. The second expression is equivalent to !(iter2 < iter1); the third expression is equivalent to (iter2 < iter1); and the fourth expression is equivalent to !(iter1 < iter2).
Random access iterators let an algorithm wander wherever it needs to within a sequence of elements. For example:
template <class RanIt>
void random_shuffle(RanIt first, RanIt last)
{
if (first == last)
return;
RanIt top = first;
for (unsigned long idx = 2; ++top != last; ++idx)
swap(*next, *(first + random(idx));
}
where the function random returns a value from 0 to idx-1, inclusive. Note that the algorithm combines sequential movement through the sequence with a random selection of elements.
The behavior of the algorithms we've looked at so far is determined only by the algorithm itself. Sometimes, though, it's necessary to customize an algorithm in various ways. For example, to find the first element in a sequence that satisfies some condition, it's necessary to tell the algorithm what condition to test for. This is done by passing a predicate as one of the algorithm's arguments. The predicate is an object that can be used on the left side of a function call operator. The predicate is called with an element in the sequence as its argument, and it returns true or false to tell the algorithm whether the condition was met. For example, Listing 2 finds the first element with the value 5.
I looked at the vocabulary for function objects in a previous column [6]. To briefly recap, a callable type is a pointer to function, a pointer to member function, a pointer to member data, or class type whose objects can appear to the left of a function call operator. A callable object is an object of a callable type. A call wrapper type is a type that holds a callable object and supports a call operation that forwards to that object; and a call wrapper is an object of a call wrapper type.
You've probably noticed that I've said very little so far about what most people see as the main feature of the STL: its containers. From a programmer's perspective, things like vectors, lists, and multimaps are extremely important—they're where you store your data. From the design perspective of STL, containers are one of several ways of creating sequences. We've seen a couple of other ways of creating sequences, though; in Listing 1 we used both an array and an ostream_iterator. So while containers are often the first thing you think of when you need data for an algorithm, keep in mind that there are other sources of sequences.
The TR1 Library provides four new call wrapper types, which we'll look at in more detail in the next few months. Briefly, there are two templates, reference_wrapper and function, that define call wrapper types. In addition, there are two template functions, mem_fn and bind, that return call wrappers. These call wrapper types are more powerful than the call wrapper types currently in the C++ Standard Library. This is a mixed blessing because they can do more than the current types, but they are in some ways incompatible with the current types.
The TR1 Library also provides five new kinds of containers. The simplest is the class template array—it holds a fixed-size array of objects and can be initialized with an aggregate initializer. The Library also provides four kinds of hashed containers, named unordered_set, unordered_multiset, unordered_map, and unordered_multimap. They do the same things as their ordered counterparts, except that they use a hash table to hold their elements. The use of a hash table produces two significant differences from the current versions of these containers. First, there are more template arguments and more member functions, so that you can control some aspects of the hash table's behavior. And second, as their names suggest, the sequence that the container manages has no predefined order. When you move through the sequence, you get the elements in the order that the hash table determines, which usually has very little relation to the natural sort order that you get from the current containers. In exchange for this unpredictability, you get faster insertions and lookups, so the unordered containers will often be a better choice for your data storage than the ordered containers.
Next month, we'll start looking at these new additions in depth, beginning with the class template array.