advertisement

Print

What Is an Iterator in C++, Part 2

by Ryan Stephens, coauthor of C++ Cookbook
11/21/2005
Iterator
An iterator in C++ is a concept that refines the iterator design pattern into a specific set of behaviors that work well with the C++ standard library. The standard library uses iterators to expose elements in a range, in a consistent, familiar way. Anything that implements this set of behaviors is called an iterator. This paves the way for generic algorithms and makes it easy to implement your own iterators and have them integrate smoothly with the standard library.

In This Article:

  1. Reverse Iterators
  2. Stream Iterators
  3. Homemade Iterators

In part one of this two-part series, I described what an iterator is, both in terms of the iterator pattern and its implementation in C++. That explanation is sufficient when you are using the standard containers, but there are other kinds of iterators I didn't discuss that you should know about: reverse iterators, stream iterators, and custom iterators. I discuss each of these in this article.

Reverse Iterators

Say you want to start at the end of a range of elements in a standard container and move toward the beginning. No problem. If your container supports bidirectional or random access iterators, you can simply move backward using the decrement operator, right? Well, yes, you can, but this approach has its problems. Consider looping backward through a container of elements:

list<string> lst;
// fill lst with data...
list<string>::iterator it;
for (it = lst.end(), it--;    // Init on last
   it != lst.begin(); --it) { // element
      cout << *it << endl; // Uh-oh, skipped
                           // first element!
}

This snippet works, although it actually omits the first element in the list, which is the first pain-in-the-neck with this approach. The one-past-the-end semantics don't work when you're going backward, so you have to treat the first element as a special case. You can add an if statement here and there to accommodate this, but you're still not out of the woods.

If you write an algorithm that operates on a range, or you want to use standard algorithms on a range in reverse order (without copying it to another container in reverse), the naive approach above won't work. Say you write a simple function template to print each element in a range, like this:

template<typename Fwd>
void printRange(Fwd first, Fwd last,
   char delim = ',', ostream& out = cout) {
    out << "{";
    while (first != last) {
        out << *first;
        if (++first != last)
            out << delim << ' ';
    }
    out << "}" << endl;
}

This won't work on the same range forward and backward, because it uses the pre-increment operator to advance the iterator from the beginning to the end of the range. You have to write two functions, printRangeForward and printRangeBackward, to work in both directions. If you have lots of algorithms like this, then you will be writing a lot of duplicate code.

Reverse iterators solve this problem. A reverse iterator is an adapter class on a container's iterator class that lets you go backward using the same one-past-the-end semantics, except that it is one-past-the-beginning instead. You can retrieve a reverse_iterator using the rbegin and rend member functions (instead of begin and end), like this:

for (list<string>::reverse_iterator it = lst.rbegin();
     it != lst.rend(); ++it) {
   cout << *it << endl;
}

You can also use a const_reverse_iterator if you are working with a const container. With reverse iterators, the printRange function template above can print the same container's elements forward or backward:

printRange(lst.begin(), lst.end());
printRange(lst.rbegin(), lst.rend());

You can also use the standard algorithms with reverse iterators. Consider the standard copy algorithm:

list<string> lst2(lst.size());
copy(lst.rbegin(), lst.rend(), lst2.begin());

This will copy the elements in lst to lst2 in reverse order.

All is not rosy with reverse iterators though, because some container member functions take an iterator parameter, and arguments of type reverse_iterator won't compile. Consider finding and erasing an element that you know to be near the end of a container. You would probably want to begin your search at the end of the iterator, if you use the standard find algorithm, like this:

lst.erase(find(lst.rbegin(), // Won't compile
   lst.rend(), "boat"));

This won't work, though, because find's return value is the same type as its arguments, which, in this case, are reverse_iterators, and list::erase requires a parameter of the type iterator. There's a quick way around this, though, with the base member function, which is provided by reverse_iterator to let you get at its underlying iterator for just this reason. Here's a version that will compile and run:

lst.erase(find(lst.rbegin(), lst.rend(), "boat").base());

Using base may feel like a hack, but it works.

The moral of this discussion on reverse iterators is that you should keep them in mind so that you don't waste processor cycles by copying your containers into reverse order, or waste your mental cycles writing goofy for loops to iterate backward using for loops.

C++ Cookbook

Related Reading

C++ Cookbook
By Ryan Stephens, Christopher Diggins, Jonathan Turkanis, Jeff Cogswell

Pages: 1, 2, 3, 4, 5

Next Pagearrow