What Is an Iterator in C++, Part 1by Ryan Stephens, coauthor of C++ Cookbook
- 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:
When I buy fresh meat at my supermarket, I don't care how it got there. I want to start at one end of the refrigerated glass case and examine the contents of each bin until I'm at the other end. Along the way, if I see something on the other side of the glass that I want, I will summon the butcher to weigh it and pack it up. It makes no difference to me that the meat in one bin came from Montana, and another from a local farm. The interface is the important part; from one supermarket to another I know what to expect.
Such is the case with the iterator pattern. The iterator pattern describes a set of requirements that allows a consumer of some data structure to access elements in it with a familiar interface, regardless of the internal details of the data structure. The C++ standard library containers supply iterator interfaces, which makes them convenient to use and interoperable with the standard algorithms.
This is the first part of a two-part article. In this installment, I'll give a brief overview of the iterator pattern and what an iterator is in C++. In the second installment, I will show you how to implement your own iterator in the same manner as the standard library containers.
Iterators are not unique to C++. The concept of an iterator is something that allows two parties--generally the consumer of some data structure or "client code", and the implementer of the data structure, or "library code"--to communicate without concern for the other's internal details. This principle of intentional ignorance is what lets a collection of elements (in any language) expose those elements to the outside world without revealing the details of the collection's internal implementation, i.e. whether it is a hash table, linked list, tree, or some other sort of data structure.
Probably the best definition of the iterator pattern is in Design Patterns, by Erich Gamma, et al, (Addison-Wesley). The authors provide a short description of the intent of iterators:
Provide a way to access the elements of an aggregate object sequentially without exposing its underlying representation.
The use cases they reference use iterators to access elements in one of these "aggregate objects," a la the C++ standard containers
map, and so on, and in fact, the sample implementation they give is in C++. But most modern languages provide iterators in some form: Java has an
Iterator class, and C# has enumerators.
A great deal of programming has to do with manipulating sequences of elements, which is why, despite its simplicity, the notion of an iterator is so broadly applicable. You usually do the same sorts of things to a sequence of elements regardless of its type: iterating through every element, searching, sorting, inserting, deleting, and so on. Without a common interface (whether an iterator or something else), you would have to do the same things to different data structures in different ways. This would be a sad state of affairs; luckily we have iterators.
The iterator pattern defines a handful of simple requirements. An iterator should allow its consumers to:
- Move to the beginning of the range of elements
- Advance to the next element
- Return the value referred to, often called the referent
- Interrogate it to see if it is at the end of the range
If all of these requirements are met, then consumers of an iterator will be able to traverse a range of elements in some aggregate object with a minimum of effort. As you will see, C++ iterators provided by the standard library satisfy all of these requirements, though not exactly as they are outlined in Design Patterns. With that in mind, let's discuss what a C++ iterator is.