Thinking In C++. Volume 2: Practical Programming

There is no way to determine whether multiple InputIterators or OutputIterators point within the same range, so there is no way to us multiple such iterators in concert. Just think in terms of iterators to support istreams and ostreams, and InputIterator and OutputIterator will make perfect sense. Also note that algorithms that use InputIterators or OutputIterators put the weakest restrictions on the types of iterators they will accept, which means that you can use any "more sophisticated" type of iterator when you see InputIterator or OutputIterator used as STL algorithm template arguments^.

ForwardIterator. Because you can only read from an InputIterator and write to an OutputIterator, you can’t use either of them to simultaneously read and modify a range, and you can’t dereference such an iterator more than once. With a ForwardIterator these restrictions are relaxed; you can still only move forward using operator++, but you can both write and read, and you can compare such iterators in the same range for equality. Since forward iterators can both read and write, they can of course be used wherever an input or output iterator is called for^.

BidirectionalIterator. Effectively, this is a ForwardIterator that can also go backward. That is, a BidirectionalIterator supports all the operations that a ForwardIterator does, but in addition it has an operator--^.

RandomAccessIterator. This type of iterator supports all the operations that a regular pointer does: you can add and subtract integral values to move it forward and backward by jumps (rather than just one element at a time), you can subscript it with operator[ ], you can subtract one iterator from another, and you can compare iterators to see which is greater using operator<, operator>, and so on. If you’re implementing a sorting routine or something similar, random access iterators are necessary to be able to create an efficient algorithm^.

The names used for the template parameter types in the algorithm descriptions later in this chapter consist of the listed iterator types (sometimes with a ‘1’ or ‘2’ appended to distinguish different template arguments) and can also include other arguments, often function objects^.

When describing the group of elements that an operation is performed on, mathematical "range" notation is often used. In this, the square bracket means "includes the end point," and the parenthesis means "does not include the end point." When using iterators, a range is determined by the iterator pointing to the initial element and by the "past-the-end" iterator, pointing past the last element. Since the past-the-end element is never used, the range determined by a pair of iterators can thus be expressed as [first, last), in which first is the iterator pointing to the initial element, and last is the past-the-end iterator^.

Most books and discussions of the STL algorithms arrange them according to side-effects: non-mutating algorithms don’t change the elements in the range, mutating algorithms do change the elements, and so on. These descriptions are based primarily on the underlying behavior or implementation of the algorithm—that is, on the designer’s perspective. In practice, we don’t find this a useful categorization, so instead we’ll organize them according to the problem you want to solve: are you searching for an element or set of elements, performing an operation on each element, counting elements, replacing elements, and so on. This should help you find the algorithm you want more easily^.

Note that all the algorithms are in the namespace std. If you do not see a different header such as or above the function declarations, it appears in .

Support tools for example creation

It’s useful to create some basic tools with which to test the algorithms. In the examples that follow we’ll use the generators mentioned earlier in Generators.h, as well as what appears below^.

Displaying a range is something that will be done constantly, so here is a templatized function that let you print any sequence, regardless of the type in that sequence:^.

//: C06:PrintSequence.h

// Prints the contents of any sequence

#ifndef PRINTSEQUENCE_H

#define PRINTSEQUENCE_H

#include

#include

template

void print(InputIter first, InputIter last,

  char* nm = "", char* sep = "\n",

  std::ostream& os = std::cout) {

  if(nm != 0 && *nm != '\0')

    os << nm << ": " << sep;

  while(first != last)

    os << *first++ << sep;

  os << std::endl;

}

#endif // PRINTSEQUENCE_H ///:~

The default prints to cout with newlines as separators, but you can change that. You can also provide a message to print at the head of the output^.