| Thinking in C++ Vol 2 - Practical Programming |
|
Prev |
Home |
Next |
This section provides a quick reference when you re
searching for the appropriate algorithm. We leave the full exploration of all
the STL algorithms to other references (see the end of this chapter, and
Appendix A), along with the more intimate details of issues like performance.
Our goal here is for you to rapidly become comfortable with the algorithms, and
we ll assume you will look into the more specialized references if you need
more detail.
Although you will often see the algorithms described using
their full template declaration syntax, we re not doing that here because you
already know they are templates, and it s quite easy to see what the template
arguments are from the function declarations. The type names for the arguments
provide descriptions for the types of iterators required. We think you ll find
this form is easier to read, and you can quickly find the full declaration in
the template header file if you need it.
The reason for all the fuss about iterators is to
accommodate any type of container that meets the requirements in the standard
library. So far we have illustrated the generic algorithms with only arrays and
vectors as sequences, but in the next chapter you ll see a broad range
of data structures that support less robust iteration. For this reason, the
algorithms are categorized in part by the types of iteration facilities they
require.
The names of the iterator classes describe the iterator type
to which they must conform. There are no interface base classes to enforce
these iteration operations they are just expected to be there. If they are not,
your compiler will complain. The various flavors of iterators are described
briefly as follows.
InputIterator. An input iterator only allows reading
elements of its sequence in a single, forward pass using operator++ and operator*.
Input iterators can also be tested with operator== and operator!=.
That s the extent of the constraints.
OutputIterator. An output iterator only allows
writing elements to a sequence in a single, forward pass using operator++
and operator*. OutputIterators cannot be tested with operator==
and operator!=, however, because you assume that you can just keep
sending elements to the destination and that you don t need to see if the destination s
end marker was reached. That is, the container that an OutputIterator
references can take an infinite number of objects, so no end-checking is
necessary. This requirement is important so that an OutputIterator can
be used with ostreams (via ostream_iterator), but you ll also
commonly use the insert iterators such as are the type of iterator returned
by back_inserter( )).
There is no way to determine whether multiple InputIterators
or OutputIterators point within the same range, so there is no way to use
such iterators together. 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 be used
in place of an InputIterator or OutputIterator.
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 passed to an
operation, 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 be expressed as [first,
last), where 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.
If you do not see a different header such as <utility>
or <numeric> above the function declarations, it appears in <algorithm>.
Also, all the algorithms are in the namespace std.
| Thinking in C++ Vol 2 - Practical Programming |
|
Prev |
Home |
Next |
