13.5. Iterator pattern

The range-for loop works because the function expects a standard interface the loop can use to establish basic facts about the range of elements in the sequence:

Most OO languages solve this problem using a form of the iterator design pattern.

classDiagram client --> map : uses map *-- map_iterator iterator <|-- map_iterator iterator <|-- list_iterator client --> list : uses list *-- list_iterator class iterator { +first() virtual +has_next() virtual +next() virtual } class list_iterator { +first() +has_next() +next() } class map_iterator { +first() +has_next() +next() }

Because design patterns represent general ideas about solving classes of problems, they are language independent. In the case of iterators, the idea has solutions in most modern languages, including C++. Each language generally provides iterators using a design appropriate for the language. C++ is no different.

C++ implements iterators using pointer semantics and an Iterator base class is generally avoided in C++ iterators. Since classes can overload all of the pointer operations, an iterator can be implemented that exposes a pointer interface.

The key advantage to this solution is that functions can be written more generically. Functions interact with a simple, consistent and well-known interface that works both for user defined types, built-in pointer types, and arrays. However, this solution does require an “end” iterator to test for equality.

Each STL container class provides an iterator class that clients can use to retrieve the correct element from the container.

Container iterators

The element defined by begin() is part of the sequence.

The element defined by end() is not part of the sequence. In C++, the end iterator is always one past the end of the sequence. Forgetting this is a common source of error.


More to Explore

You have attempted of activities on this page