Thinking in C++ Vol 2 - Practical Programming |
Prev |
Home |
Next |
The iterators in the Standard C++ library are classified
into categories that describe their capabilities. The order in which they are
generally described moves from the categories with the most restricted behavior
to those with the most powerful behavior.
Input: read only, one pass
The only predefined implementations of input iterators are istream_iterator and istreambuf_iterator, to read from an istream. As you can
imagine, an input iterator can only be dereferenced once for each element
that s selected, just as you can only read a particular portion of an input
stream once. They can only move forward. A special constructor defines the
past-the-end value. In summary, you can dereference it for reading (once only
for each value) and move it forward.
Output: write only, one pass
This is the complement of an input iterator, but for writing
rather than reading. The only predefined implementations of output iterators
are ostream_iterator and ostreambuf_iterator, to write to an ostream, and the less commonly used raw_storage_iterator. Again, these can only be dereferenced once for each written value, and they can only move forward. There is no concept of
a terminal past-the-end value for an output iterator. Summarizing, you can
dereference it for writing (once only for each value) and move it forward.
Forward: multiple read/write
The forward iterator contains all the functionality of both
the input iterator and the output iterator, plus you can dereference an
iterator location multiple times, so you can read and write to a value multiple
times. As the name implies, you can only move forward. There are no predefined
iterators that are only forward iterators.
Bidirectional: operator
The bidirectional iterator has all the functionality of the forward iterator, and in addition it can be moved backward one location at a time
using
operator--. The iterators returned by the list container are
bidirectional.
Random access: like a pointer
Finally, the random-access iterator has all the functionality of the bidirectional iterator plus all the functionality of a pointer (a
pointer is a random-access iterator), except that there is no null
iterator analogue to a null pointer. Basically, anything you can do with a
pointer you can do with a random-access iterator, including indexing with operator[ ],
adding integral values to a pointer to move it forward or backward by a number
of locations, or comparing one iterator to another with comparison operators.
Is this really important?
Why do you care about this categorization? When you re just
using containers in a straightforward way (for example, just hand-coding all
the operations you want to perform on the objects in the container), it usually
doesn t matter. Things either work or they don t. The iterator categories
become important when:
1. You use some of the fancier built-in iterator types that will be
demonstrated shortly, or you graduate to creating your own iterators
(demonstrated later in this chapter).
2. You use the STL algorithms (the subject of the previous chapter).
Each of the algorithms places requirements on its iterators. Knowledge of the
iterator categories is even more important when you create your own reusable
algorithm templates, because the iterator category required by your algorithm
determines how flexible the algorithm will be. If you require only the most
primitive iterator category (input or output), your algorithm will work with everything
(copy( ) is an example of this).
An iterator s category is identified by a hierarchy of iterator tag classes. The class names correspond to the iterator categories, and their
derivation reflects the relationship between them:
struct input_iterator_tag {};
struct output_iterator_tag {};
struct forward_iterator_tag :
public input_iterator_tag {};
struct bidirectional_iterator_tag :
public forward_iterator_tag {};
struct random_access_iterator_tag :
public bidirectional_iterator_tag {};
The class forward_iterator_tag derives only from input_iterator_tag, not from output_iterator_tag, because we need to have past-the-end
iterator values in algorithms that use forward iterators, but algorithms that
use output iterators always assume that operator* can be dereferenced.
For this reason, it is important to make sure that a past-the-end value is
never passed to an algorithm that expects an output iterator.
For efficiency, certain algorithms provide different
implementations for different iterator types, which they infer from the
iterator tag defined by the iterator. We will use some of these tag classes
later in this chapter when we define our own iterator types.
Thinking in C++ Vol 2 - Practical Programming |
Prev |
Home |
Next |