Previous Table of Contents Next


What is nice about this copy algorithm, though, is that it works with the library containers also. Among the operations supported by the sequential containers are begin and end, which yield appropriate iterators that refer to the first and one past the last elements of the container, and back_inserter, which is a nonmember function that yields an output iterator that can be used to append new elements at the back of the container. Therefore, if we wanted to copy the elements of x into a vector called v, we might say

   vector<int> v;
   copy(x, x+100, back_inserter(v));

and to copy the elements of v back into x, we might say

   copy(v.begin(), v.end(), x);

and hope that x had enough elements to contain it.

Another interesting source of iterators in the library is the templates istream_iterator and ostream_iterator. They take input and output files and yield iterators that read from or write to the files. As a simple example, we can print all the elements of v by executing

   copy(v.begin(), v.end(), ostream_iterator<int>(cout, “\n”));

Here, the call to ostream_iterator<int> constructs an object that acts like an output iterator; each time we dereference, assign, and increment that object, it writes the value assigned onto cout followed by a newline (the second argument to ostream_iterator).

If an iterator is capable of acting as an input iterator and an output iterator at the same time, we call it a forward iterator. We can think of a forward iterator as an idealization of a singly-linked list, or of any sequence that permits reading and writing but not backspacing. An example of an algorithm that requires a forward iterator is replace:

   template<class Iter, class X>
   void replace(Iter begin, Iter end, const X& x, const X& y)
   {
       while (begin != end) {
           if (*begin == x)
               *begin = y;
           ++begin;
       }
   }

This algorithm examines the elements of a sequence described by its first two arguments, replacing any element that is equal to the third argument by the fourth argument. So, for example, if we have a list of strings, we can replace any null strings by the string (null):

   list<string> ls;
   // ...
   replace(ls.begin(), ls.end(), “”, “(null)”);

Note that this algorithm works on lists in exactly the same way that it works on arrays; the iterators are different types, but the compiler takes that into account during template instantiation.

An iterator that has all the forward-iterator properties and also supports -- is called a reverse iterator. Reverse iterators capture the idea of a doubly linked list; the reverse function that we saw earlier is an example of a standard library algorithm that takes advantage of reverse-iterator properties.

Finally, an iterator that has all the reverse-iterator properties and also supports arithmetic and subscripting the same way pointers do is called a random-access iterator. Among the algorithms that requires a random-access iterator is binary search.

Although iterators are related to each other in a way that suggests inheritance, that inheritance is entirely conceptual and not part of the language. In particular, pointers to ordinary array elements have all the random-access iterator properties, yet although pointers are iterators, they cannot participate in inheritance. The notion of the five kinds of iterators is part of the intellectual framework that the library provides; this framework allows users to write new containers or new algorithms and have them work with the containers and algorithms that already exist.

7.6.6. Algorithms

Many of the algorithms in the library are seemingly simple; yet they can do quite a bit in combination. We have already seen a few; although there are more of them than we can cover in detail, we can still summarize them.

The simplest algorithms deal with sequences without modifying them. These include linear searches, counting algorithms, comparisons, and subsequence searches. Among the most common of these algorithms is find:

   template <class In, class X>
   In find(In begin, In end, const X& x)
   {
       while (begin != end && *begin != x)
             ++begin;
       return begin;
   }

This algorithm is typical in several ways. It takes a pair of iterators to delimit the beginning and end of the sequence to be searched, which makes it easy to search subsequences of a container. It returns an iterator that refers to the element sought. If it does not find an element, it returns the one-past-the-end iterator end rather than trying to construct a unique iterator value. Most of the algorithms share one or more of these properties.

Other algorithms modify, or potentially modify, the sequences they use. They include copying, reversing, swapping, and other transformations such as replace. Finally, there are algorithms that are less easy to characterize. They include sorting, merging, heap manipulation, partitioning, and shuffling and other permutation algorithms.


Previous Table of Contents Next