advertisement

Print

What Is an Iterator in C++, Part 1
Pages: 1, 2, 3, 4

Categories

An iterator category is a set of requirements that defines a certain type of behavior. A category is an interface, though not in any mechanical sense, i.e. it is not an abstract base class.



Since an iterator is just a collection of requirements, and not a class hierarchy, expressing different kinds of iterators is a little unusual in this object-oriented world we live in. The way the standard describes it, there are five sets of requirements that define five different categories of iterators: input, output, forward, bidirectional, and random access.

The requirements for each category are little more than the list of member functions each iterator category supports and their associated semantics, with a few footnotes about behavior. Table 2 shows which member functions are supported by each iterator category. Assume that Iter is the iterator type, and x and y are variables of type Iter.

Table 2. Iterator categories and required member functions

Member Function Input Output Forward Bidirectional Random Access
Iter x(y) Y Y Y Y Y
Iter x = y Y Y Y Y Y
x == y Y N Y Y Y
x != y Y N Y Y Y
x++, ++x Y Y Y Y Y
x--, --x N N N Y Y
*x As rvalue As lvalue Y Y Y
(*x).f Y N Y Y Y
x->f Y N Y Y Y
x + n N N N N Y
x += n N N N N Y
x - n N N N N Y
X -= n N N N N Y
X[n] N N N N Y

In Table 2, the categories become more functional as you move from left to right. Input and output iterators permit relatively few operations, while random access iterators do everything.

The most basic iterator categories are input and output iterators. Input iterators are generally for reading elements from some collection in a single pass, such as an input stream. The idea is that the input iterator refers to a range of elements that can be read from, but not written to. As a result, the dereference operator yields rvalues. An output iterator is just the opposite, where you write elements to a collection that will only be traversed once. The biggest difference between the two is that dereferencing an output iterator yields an lvalue, so you can write to it, but you cannot read from it. And output iterators do not support testing for equality.

A forward iterator can do everything an input or output iterator can do, which means you can read from a dereferenced value or write to it, but since it is a "forward" iterator, not surprisingly, you can only go forward using a prefix or postfix ++ operator; for example, ++p or p++.

Bidirectional and random access iterators do what their name implies. With a bidirectional iterator, you can advance forward or backward with the ++ or -- operators. A random access iterator can do everything any other iterator can do, and it can advance a given number of places a la pointer arithmetic. For example, the standard container vector supports random access iterators, which means that the following code will move the iterator around in various ways:

vector<string> v;
// Fill up v with some data
vector<string>::iterator p = v.begin();
p += 5;  // Now p refers to the 5th element
p[5];    // Now p refers to the 10th element
p -= 10; // Back to the beginning...

Different standard containers offer different types of iterators, depending on what can be efficiently supported, based on the type of data structure that is used by the container. For example, a list (declared in the <list> header) provides bidirectional iterators because lists are usually implemented as a doubly-linked list, which makes it efficient to iterate forward and backward one element at a time. list does not provide random access iterators, though, not because it's impossible to implement, but because it can't be implemented efficiently. Random access in a list would require linear complexity for advancing forward or backward more than one element.

Each standard container supports the category of iterator it can implement efficiently. Standard algorithms advertise their requirements for an iterator by the category of iterator each requires. This declaration of iterator categories by algorithms and containers is what determines which algorithms will work with which containers. Table 3 contains a list of the standard containers and the category of iterator each supports.

Table 3. Iterator categories for standard containers

Container Iterator Category
basic_string Random access
deque Random access
list Bidirectional
map, multimap Bidirectional
set, multiset Bidirectional
vector Random access

basic_string isn't a standard container proper, but it supports most of the same operations as a container, so I included it in the table. If the name basic_string doesn't look familiar to you, it might be because you've been using its typedef'd shortcut: string or wstring.

Right now, if you glance back up at Table 2 you might say, "What happened to the input, output, and forward iterators?" And you'd be making a good point, if perhaps whining a little. Those categories aren't supplied by the containers; they're used for other things. In particular, input and output iterators are used with input and output stream iterators (which I will describe in the second part of this article). Forward iterators, even if they aren't supplied by any container, allow algorithms to make it clear that they only require the iterators to go forward. Consider the remove standard algorithm. It operates on a range, but only needs to go forward, so its declaration looks like this:

template<typename Fwd, typename Val>
Fwd remove(Fwd start, Fwd end, const Val& val)

The Fwd template parameter is supposed to let you know that its type is a forward iterator. Val is the type of elements in the range. (All elements that are equal to val are moved to the end of the range and an iterator to the first one of these elements is returned so you can erase them with the container's erase member function.)

Recap

The C++ standard library contains iterators for the standard containers that implement the iterator pattern, although not literally. Using iterators (or const iterators) is the preferred method of traversing elements in a container. The exact type of an iterator is implementation-defined, but that doesn't matter to you because regardless of exactly what it is, it still supports the interface its category requires. And finally, iterator categories define groups of requirements that each container or algorithm (standard or otherwise) can supply or require.

In part two of this article, I'll describe some more flavors of iterator (namely reverse iterators and stream iterators), and show you how to write an iterator for your own class.

Ryan Stephens is a software engineer, writer, and student living in Tempe, Arizona. He enjoys programming in virtually any language, especially C++.


Return to the O'Reilly Network