Concepts, Refinements, and Models

The STL has several features, such as kinds of iterators, that aren’t expressible in the C++ language. That is, although you can design, say, a class that has the properties of a forward iterator, you can’t have the compiler restrict an algorithm to using only that class. The reason is that the forward iterator is a set of requirements, not a type. The requirements could be satisfied by an iterator class you’ve designed, but they could also be satisfied by an ordinary pointer. An STL algorithm works with any iterator implementation that meets its requirements. STL literature uses the word concept to describe a set of requirements. Thus, there is an input iterator concept, a forward iterator concept, and so on. By the way, if you do need iterators for, say, a container class you’re designing, you can look to the STL, which include iterator templates for the standard varieties.

Concepts can have an inheritance-like relationship. For example, a bidirectional iterator inherits the capabilities of a forward iterator. However, you can’t apply the C++ inheritance mechanism to iterators. For example, you might implement a forward iterator as a class and a bidirectional iterator as a regular pointer. So in terms of the C++ language, this particular bidirectional iterator, being a built-in type, couldn’t be derived from a class. Conceptually, however, it does inherit. Some STL literature uses the term refinement to indicate this conceptual inheritance. Thus, a bidirectional iterator is a refinement of the forward iterator concept.

A particular implementation of a concept is termed a model. Thus, an ordinary pointer-to-int is a model of the concept random access iterator. It’s also a model of a forward iterator, for it satisfies all the requirements of that concept.

The Pointer As Iterator

Iterators are generalizations of pointers, and a pointer satisfies all the iterator requirements. Iterators form the interface for STL algorithms, and pointers are iterators, so STL algorithms can use pointers to operate on non-STL containers that are based on pointers. For example, you can use STL algorithms with arrays. Suppose Receipts is an array of double values, and you would like to sort in ascending order:

const int SIZE = 100;
double Receipts[SIZE];

The STL sort() function, recall, takes as arguments an iterator pointing to the first element in a container and an iterator pointing to past-the-end. Well, &Receipts[0] (or just Receipts) is the address of the first element, and &Receipts[SIZE] (or just Receipts + SIZE) is the address of the element following the last element in the array. Thus, the following function call sorts the array:

sort(Receipts, Receipts + SIZE);

C++ guarantees that the expression Receipts + n is defined as long as the result lies in the array or one past-the-end. Thus, C++ supports the “one-past-the-end” concept for pointers into an array, and this makes it possible to apply STL algorithms to ordinary arrays. Thus, the fact that pointers are iterators and that algorithms are iterator based makes it possible to apply STL algorithms to ordinary arrays. Similarly, you can apply STL algorithms to data forms of your own design, provided that you supply suitable iterators (which may be pointers or objects) and past-the-end indicators.

copy(), ostream_iterator, and istream_iterator

The STL provides some predefined iterators. To see why, let’s establish some background. There is an algorithm called copy() for copying data from one container to another. This algorithm is expressed in terms of iterators, so it can copy from one kind of container to another or even from or to an array, because you can use pointers into an array as iterators. For example, the following copies an array into a vector:

int casts[10] = {6, 7, 2, 9 ,4 , 11, 8, 7, 10, 5};
vector<int> dice[10];
copy(casts, casts + 10, dice.begin());   // copy array to vector

The first two iterator arguments to copy() represent a range to be copied, and the final iterator argument represents the location to which the first item is copied. The first two arguments must be input iterators (or better), and the final argument must be an output iterator (or better). The copy() function overwrites existing data in the destination container, and the container has to be large enough to hold the copied elements. So you can’t use copy() to place data in an empty vector—at least not without resorting to a trick that is revealed later in this chapter.

Now suppose you want to copy information to the display. You could use copy() if there was an iterator representing the output stream. The STL provides such an iterator with the ostream_iterator template. Using STL terminology, this template is a model of the output iterator concept. It is also an example of an adapter—a class or function that converts some other interface to an interface used by the STL. You can create an iterator of this kind by including the iterator (formerly iterator.h) header file and making a declaration:

#include <iterator>
...
ostream_iterator<int, char> out_iter(cout, " ");

The out_iter iterator now becomes an interface that allows you to use cout to display information. The first template argument (int, in this case) indicates the data type being sent to the output stream. The second template argument (char, in this case) indicates the character type used by the output stream. (Another possible value would be wchar_t.) The first constructor argument (cout, in this case) identifies the output stream being used. It could also be a stream used for file output. The final character string argument is a separator to be displayed after each item sent to the output stream.

You could use the iterator like this:

*out_iter++ = 15;   // works like cout << 15 << " ";

For a regular pointer, this would mean assigning the value 15 to the pointed-to location and then incrementing the pointer. For this ostream_iterator, however, the statement means send 15 and then a string consisting of a space to the output stream managed by cout. Then it should get ready for the next output operation. You could use the iterator with copy() as follows:

copy(dice.begin(), dice.end(), out_iter);    // copy vector to output stream

This would mean to copy the entire range of the dice container to the output stream—that is, to display the contents of the container.

Or you could skip creating a named iterator and construct an anonymous iterator instead. That is, you could use the adapter like this:

copy(dice.begin(), dice.end(), ostream_iterator<int, char>(cout, " ") );

Similarly, the iterator header file defines an istream_iterator template for adapting istream input to the iterator interface. It is a model of the input iterator concept. You could use two istream_iterator objects to define an input range for copy():

copy(istream_iterator<int, char>(cin),
     istream_iterator<int, char>(), dice.begin());

Like ostream_iterator, istream_iterator uses two template arguments. The first indicates the data type to be read, and the second indicates the character type used by the input stream. Using a constructor argument of cin means to use the input stream managed by cin. Omitting the constructor argument indicates input failure, so the previous code means to read from the input stream until end-of-file, type mismatch, or some other input failure.

Other Useful Iterators

The iterator header file provides some other special-purpose predefined iterator types in addition to ostream_iterator and istream_iterator. They are reverse_iterator, back_insert_iterator, front_insert_iterator, and insert_iterator.

Let’s start with seeing what a reverse iterator does. In essence, incrementing a reverse iterator causes it to decrement. Why not just decrement a regular iterator? The main reason is to simplify using existing functions. Suppose you want to display the contents of the dice container. As you just saw, you can use copy() and ostream_iterator to copy the contents to the output stream:

ostream_iterator<int, char> out_iter(cout, " ");
copy(dice.begin(), dice.end(), out_iter);  // display in forward order

Now suppose you want to print the contents in reverse order. (Perhaps you are performing time-reversal studies.) There are several approaches that don’t work, but rather than wallow in them, let’s go to one that does. The vector class has a member function called rbegin() that returns a reverse iterator pointing to past-the-end and a member rend() that returns a reverse iterator pointing to the first element. Because incrementing a reverse iterator makes it decrement, you can use the following statement to display the contents backward:

copy(dice.rbegin(), dice.rend(), out_iter); // display in reverse order

You don’t even have to declare a reverse iterator.

Reverse pointers have to make a special compensation. Suppose rp is a reverse pointer initialized to dice.rbegin(). What should *rp be? Because rbegin() returns past-the-end, you shouldn’t try to dereference that address. Similarly, if rend() is really the location of the first element, copy() stops one location earlier because the end of the range is not in a range. Reverse pointers solve both problems by decrementing first and then dereferencing. That is, *rp dereferences the iterator value immediately preceding the current value of *rp. If rp points to position six, *rp is the value of position five, and so on. Listing 16.10 illustrates using copy(), an ostream iterator, and a reverse iterator.

Listing 16.10. copyit.cpp

// copyit.cpp -- copy() and iterators
#include <iostream>
#include <iterator>
#include <vector>

int main()
{
    using namespace std;

    int casts[10] = {6, 7, 2, 9 ,4 , 11, 8, 7, 10, 5};
    vector<int> dice(10);
    // copy from array to vector
    copy(casts, casts + 10, dice.begin());
    cout << "Let the dice be cast! ";
    // create an ostream iterator
    ostream_iterator<int, char> out_iter(cout, " ");
    // copy from vector to output
    copy(dice.begin(), dice.end(), out_iter);
    cout << endl;
    cout <<"Implicit use of reverse iterator. ";
    copy(dice.rbegin(), dice.rend(), out_iter);
    cout << endl;
    cout <<"Explicit use of reverse iterator. ";
    vector<int>::reverse_iterator ri;
    for (ri = dice.rbegin(); ri != dice.rend(); ++ri)
        cout << *ri << ' ';
    cout << endl;

    return 0;
}

Here is the output of the program in Listing 16.10:

Let the dice be cast!
6 7 2 9 4 11 8 7 10 5
Implicit use of reverse iterator.
5 10 7 8 11 4 9 2 7 6
Explicit use of reverse iterator.
5 10 7 8 11 4 9 2 7 6

If you have the choice of explicitly declaring iterators or using STL functions to handle the matter internally, for example, by passing an rbegin() return value to a function, you should take the latter course. It’s one less thing to do and one less opportunity to experience human fallibility.

The other three iterators (back_insert_iterator, front_insert_iterator, and insert_iterator) also increase the generality of the STL algorithms. Many STL functions are like copy() in that they send their results to a location indicated by an output iterator. Recall that the following copies values to the location beginning at dice.begin():

copy(casts, casts + 10, dice.begin());

These values overwrite the prior contents in dice, and the function assumes that dice has enough room to hold the values. That is, copy() does not automatically adjust the size of the destination to fit the information sent to it. Listing 16.10 takes care of that situation by declaring dice to have 10 elements, but suppose you don’t know in advance how big dice should be. Or suppose you want to add elements to dice rather than overwrite existing ones.

The three insert iterators solve these problems by converting the copying process to an insertion process. Insertion adds new elements without overwriting existing data, and it uses automatic memory allocation to ensure that the new information fits. A back_insert_iterator inserts items at the end of the container, and a front_insert_iterator inserts items at the front. Finally, the insert_iterator inserts items in front of the location specified as an argument to the insert_iterator constructor. All three of these iterators are models of the output container concept.

There are restrictions. A back_insert_iterator can be used only with container types that allow rapid insertion at the end. (Rapid refers to a constant time algorithm; the section “Container Concepts,” later in this chapter, discusses the constant time concept further.) The vector class qualifies. A front_insert_iterator can be used only with container types that allow constant time insertion at the beginning. Here the vector class doesn’t qualify, but the queue class does. The insert_iterator doesn’t have these restrictions. Thus, you can use it to insert material at the front of a vector. However, a front_insert_iterator does so faster for the container types that support it.

These iterators take the container type as a template argument and the actual container identifier as a constructor argument. That is, to create a back_insert_iterator for a vector<int> container called dice, you use this:

back_insert_iterator<vector<int> > back_iter(dice);

The reason you have to declare the container type is that the iterator has to make use of the appropriate container method. The code for the back_insert_iterator constructor will assume that a push_back() method exists for the type passed to it. The copy() function, being a standalone function, doesn’t have the access rights to resize a container. But the declaration just shown allows back_iter to use the vector<int>::push_back() method, which does have access rights.

Declaring a front_insert_iterator has the same form. An insert_iterator declaration has an additional constructor argument to identify the insertion location:

insert_iterator<vector<int> > insert_iter(dice, dice.begin() );

Listing 16.11 illustrates using two of these iterators. Also it uses for_each() instead of an ostream iterator for output.

Listing 16.11. inserts.cpp

// inserts.cpp -- copy() and insert iterators
#include <iostream>
#include <string>
#include <iterator>
#include <vector>
#include <algorithm>

void output(const std::string & s) {std::cout << s << " ";}

int main()
{
    using namespace std;
    string s1[4] = {"fine", "fish", "fashion", "fate"};
    string s2[2] = {"busy", "bats"};
    string s3[2] = {"silly", "singers"};
    vector<string> words(4);
    copy(s1, s1 + 4, words.begin());
    for_each(words.begin(), words.end(), output);
    cout << endl;
// construct anonymous back_insert_iterator object
    copy(s2, s2 + 2, back_insert_iterator<vector<string> >(words));
    for_each(words.begin(), words.end(), output);
    cout << endl;

// construct anonymous insert_iterator object
    copy(s3, s3 + 2, insert_iterator<vector<string> >(words,
                                            words.begin()));
    for_each(words.begin(), words.end(), output);
    cout << endl;
    return 0;
}

Here is the output of the program in Listing 16.11:

fine fish fashion fate
fine fish fashion fate busy bats
silly singers fine fish fashion fate busy bats

The first copy()copies the four strings from s1 into words. This works in part because words is declared to hold four strings, which equals the number of strings being copied. Then the back_insert_iterator inserts the strings from s2 just in front of the end of the words array, expanding the size of words to six elements. Finally, the insert_iterator inserts the two strings from s3 just in front of the first element of words, expanding the size of words to eight elements. If the program attempted to copy s2 and s3 into words by using words.end() and words.begin() as iterators, there would be no room in words for the new data, and the program would probably abort because of memory violations.

If you’re feeling overwhelmed by all the iterator varieties, keep in mind that using them will make them familiar. Also keep in mind that these predefined iterators expand the generality of the STL algorithms. Thus, not only can copy() copy information from one container to another, it can copy information from a container to the output stream and from the input stream to a container. And you can also use copy() to insert material into another container. So you wind up with a single function doing the work of many. And because copy() is just one of several STL functions that use an output iterator, these predefined iterators multiply the capabilities of those functions, too.