An iterator is an abstraction of a pointer used for pointing
into containers and other sequences. An ordinary pointer can point to
different elements in an array. The ++
operator advances the pointer to the next
element, and the *
operator
dereferences the pointer to return a value from the array. Iterators
generalize the concept so that the same operators have the same behavior
for any container, even trees and lists. See the <iterator>
section of Chapter 13 for more details.
There are five categories of iterators:
Permits you to read a sequence in one pass. The increment (++
)
operator advances to the next element, but there is no decrement
operator. The dereference (*
)
operator returns an rvalue, not an lvalue, so you can read
elements but not modify them.
Permits you to write a sequence in one pass. The increment
(++
) operator advances to the
next element, but there is no decrement operator. You can
dereference an element only to assign a value to it. You cannot
compare output iterators.
Permits unidirectional access to a sequence. You can refer to and assign to an item as many times as you want. You can use a forward iterator wherever an input iterator is required or wherever an output iterator is required.
Similar to a forward iterator but also supports the
--
(decrement) operator to
move the iterator back one position.
Similar to a bidirectional iterator but also supports the
[]
(subscript) operator to
access any index in the sequence. Also, you can
add or subtract an integer to move a random access iterator by
more than one position at a time. Subtracting two random access
iterators yields an integer distance between them. Thus, a
random access iterator is most like a conventional pointer, and
a pointer can be used as a random access iterator.
An input, forward, bidirectional, or random access iterator can
be a const_iterator
. Dereferencing
a const_iterator
yields a constant
value, but otherwise behaves as described previously. See Section 10.2.5 later in this
chapter for details.
The most important point to remember about iterators is that they are inherently unsafe. Like pointers, an iterator can point to a container that has been destroyed or to an element that has been erased. You can advance an iterator past the end of the container the same way a pointer can point past the end of an array. With a little care and caution, however, iterators are safe to use.
The first key to safe use of iterators is to make sure a program
never dereferences an iterator that marks the end of a range.
Two iterators can denote a range of values, typically in a container.
One iterator points to the start of the range and another marks the
end of the range by pointing to a position one past the last element
in the range. The mathematical notation of [first
, last
) tells you that the item that first
points to is included in the range,
but the item that last
points to is
excluded from the range.
A program must never dereference an iterator that points to one
past the end of a range (e.g., last
) because that iterator might not be
valid. It might be pointing to one past the end of the elements of a
container, for example.
Even a valid iterator can become invalid and therefore unsafe to
use, for example if the item to which the iterator points is erased.
The detailed descriptions in Chapter
13 tell you this information for each container type. In
general, iterators for the node-based containers (list
, set
, multiset
, map
, multimap
) become invalid only when they
point to an erased node. Iterators for the array-based containers
(deque
, vector
) become invalid when the underlying
array is reallocated, which might happen for any insertion and for
some erasures.
Iterators are often used with containers, but they have many more uses. You can define iterators for almost any sequence of objects. The standard library includes several examples of non-container iterators, most notably I/O iterators and inserters.
At the lowest level, a stream is nothing more than a sequence of
characters. At a slightly higher level, you can think of a stream as a
sequence of objects, which would be read with operator>>
or written with operator<<
. Thus, the standard library
includes the following I/O iterators: istreambuf_iterator
, ostreambuf_iterator
, istream_iterator
, and ostream_iterator
. Example 10-4 shows how to use
streambuf
iterators to copy one
stream to another.
Another kind of output iterator is an insert
iterator , which inserts items into a sequence collection. The
insert iterator requires a container and an optional iterator to
specify the position where the new items should be inserted. You can
insert at the back of a sequence with back_insert_iterator
, at the front of a sequence with front_insert_iterator
, or at a specific position in any kind of container
with insert_iterator
. Each of these iterator class templates has an
associated function template that creates the iterator for you and
lets the compiler deduce the container type. Example 10-5 shows how to read a
series of numbers from a stream, store them in reverse order in a
list, and print the list, one number per line.
Example 10-5. Inserting numbers in a vector
#include <algorithm> #include <iostream> #include <iterator> #include <list> int main( ) { using namespace std; list<double> data; copy(istream_iterator<double>(cin), istream_iterator<double>( ), front_inserter(data)); // Use the data... // Write the data, one number per line. copy(data.begin( ), data.end( ), ostream_iterator<double>(cout, "\n")); }
The simplest way to write your own iterator is to derive
from the iterator
class template.
Specify the iterator category as the first template parameter and the
item type as the second parameter. In most cases, you can use the
default template arguments for the remaining parameters. (See <iterator>
in Chapter 13 for details.) The slist
container from Example 10-1 needs an iterator
and a const_iterator
. The only difference is that
a const_iterator
returns rvalues
instead of lvalues. Most of the iteration logic can be factored into a
base class. Example 10-6
shows iterator
and base_iterator
; const_iterator
is almost identical to
iterator
, so it is not
shown.
Example 10-6. Writing a custom iterator
// The declaration for iterator_base is nested in slist. class iterator_base : public std::iterator<std::forward_iterator_tag, T> { friend class slist; public: bool operator==(const iterator_base& iter) const { return node_ == iter.node_; } bool operator!=(const iterator_base& iter) const { return ! (*this == iter); } protected: iterator_base(const iterator_base& iter) : prev_(iter.prev_), node_(iter.node_) {} iterator_base(slist::link_type* prev, slist::link_type* node) : prev_(prev), node_(node) {} // If node_ == 0, the iterator == end( ). slist::link_type* node_; // A pointer to the node before node_ is needed to support erase( ). If // prev_ == 0, the iterator points to the head of the list. slist::link_type* prev_; private: iterator_base( ); }; // The declaration for iterator is nested in slist. class iterator : public iterator_base { friend class slist; public: iterator(const iterator& iter) : iterator_base(iter) {} iterator& operator++( ) { // Pre-increment this->prev_ = this->node_; this->node_ = this->node_->next; return *this; } iterator operator++(int) { // Post-increment iterator tmp = *this; operator++( ); return tmp; } T& operator*( ) { return this->node_->value; } T* operator->( ) { return &this->node_->value; } private: iterator(slist::link_type* prev, slist::link_type* node) : iterator_base(prev, node) {} };
Every container must provide an iterator
type and a const_iterator
type. Functions such as begin
and end
return iterator
when called on a non-const
container and return const_iterator
when called on a const
container.
Note that a const_iterator
(with underscore) is quite different from a const
iterator
(without underscore). A const
iterator
is a constant object of type
iterator
. Being constant, it cannot
change, so it cannot advance to point to a different position. A
const_iterator
, on the other hand,
is a non-const
object of type
const_iterator
. It is not constant,
so its value can change. The key difference between iterator
and const_iterator
is that iterator
returns lvalues of type T
, and const_iterator
returns unmodifiable objects,
either rvalues or const
lvalues of
type T
. The standard requires that
a plain iterator
be convertible to
const_iterator
, but not vice
versa.
One problem is that some members of the standard containers
(most notably erase
and insert
) take iterator
as a parameter, not const_iterator
. If you have a const_iterator
, you cannot use it as an
insertion or erasure position.
Another problem is that it might be difficult to compare an
iterator
with a const_iterator
. If the compiler reports an
error when you try to compare iterators for equality or inequality,
try swapping the order of the iterators, that is, if a
==
b
fails to compile, try b
==
a
. Most likely, the problem is that
b
is a const_iterator
and a
is a plain iterator
. By swapping the order, you let the
compiler convert a
to a const_iterator
and allow the
comparison.
For a full explanation of how best to work with const_iterator
s, see Scott Meyers's
Effective STL
(Addison-Wesley).
Every container that supports bidirectional or random access
iterators also provides reverse iterators, that is, iterators that start with
the last element and "advance" toward the first element of the
container. These iterators are named reverse_iterator
and const_reverse_iterator
.
The standard library includes the reverse_iterator
class template as a
convenient way to implement the reverse_iterator
type. The reverse_iterator
class template is an
iterator adapter that runs in the reverse direction of the adapted
iterator. The adapted iterator must be a bidirectional or random
access iterator. You can obtain the adapted iterator, given a reverse
iterator, by calling the base
function.
On paper, the reverse iterator seems like a good idea. After
all, a bidirectional iterator can run in two directions. There is no
reason why an iterator adapter could not implement operator++
by calling the adapted iterator's
operator--
function.
Reverse iterators share a problem with const_iterator
s, namely that several
members, such as insert
and
erase
, do not take an iterator
template parameter but require the exact iterator
type, as declared in the container
class. The reverse_iterator
type is
not accepted, so you must pass the adapted iterator instead, which is
returned from the base
function.
As an insertion point, the base
iterator works fine, but for erasing,
it is one off from the desired position. The solution is to increment
the reverse iterator, then call base
, as shown in Example 10-7.
Example 10-7. A reverse iterator
int main( ) { std::list<int> l; l.push_back(10); l.push_back(42); l.push_back(99); print(l); std::list<int>::reverse_iterator ri; ri = std::find(l.rbegin( ), l.rend( ), 42); l.insert(ri.base( ), 33); // OK: 33 inserted before 42, from the point of view of a reverse iterator, // that is, 33 inserted after 42 ri = std::find(l.rbegin( ), l.rend( ), 42); l.erase(ri.base( )); // Oops! Item 33 is deleted, not item 42. ri = std::find(l.rbegin( ), l.rend( ), 42); l.erase((++ri).base( )); // That's right! In order to delete the item ri points to, you must advance ri // first, then delete the item. }
For a full explanation of how best to work with reverse
iterators, see Scott Meyer's Effective
STL
(Addison-Wesley).