 |
ISBN: |
[Note: This tutorial is an excerpt (Sections 23.1) of Chapter 23, Standard Template Library (STL), from our textbook C++ How to Program, 5/e. These tutorials may refer to other chapters or sections of the book that are not included here. Permission Information: Deitel, Harvey M. and Paul J., C++ HOW TO PROGRAM, ©2005, pp.1112-1123. Electronically reproduced by permission of Pearson Education, Inc., Upper Saddle River, New Jersey.]
23.1.2 Introduction to Iterators (Continued)
Iterator Categories and Iterator Category Hierarchy
Figure 23.6 shows the categories of iterators used by the STL. Each category provides a specific set of functionality. Figure 23.7 illustrates the hierarchy of iterator categories. As you follow the hierarchy from top to bottom, each iterator category supports all the functionality of the categories above it in the figure. Thus the “weakest” iterator types are at the top and the most powerful one is at the bottom. Note that this is not an inheritance hierarchy.
| Category | Description |
| input | Used to read an element from a container. An input iterator can move only in the forward direction (i.e., from the beginning of the container to the end) one element at a time. Input iterators support only one-pass algorithms-the same input iterator cannot be used to pass through a sequence twice. |
| output | Used to write an element to a container. An output iterator can move only in the forward direction one element at a time. Output iterators support only one-pass algorithms-the same output iterator cannot be used to pass through a sequence twice. |
| forward | Combines the capabilities of input and output iterators and retains their position in the container (as state information). |
| bidirectional | Combines the capabilities of a forward iterator with the ability to move in the backward direction (i.e., from the end of the container toward the beginning). Bidirectional iterators support multipass algorithms. |
| random access | Combines the capabilities of a bidirectional iterator with the ability to directly access any element of the container, i.e., to jump forward or backward by an arbitrary number of elements. |
Fig. 23.6 Iterator categories.
Fig. 23.7 Iterator category hierarchy.
The iterator category that each container supports determines whether that container can be used with specific algorithms in the STL. Containers that support random-access iterators can be used with all algorithms in the STL. As we will see, pointers into arrays can be used in place of iterators in most STL algorithms, including those that require random-access iterators. Figure 23.8 shows the iterator category of each of the STL containers. Note that only vectors, deques, lists, sets, multisets, maps and multimaps (i.e., the first-class containers) are traversable with iterators.
 |
Software Engineering Observation 23.4 |
| Using the “weakest iterator” that yields acceptable performance helps produce maximally reusable components. For example, if an algorithm requires only forward iterators, it can be used with any container that supports forward iterators, bidirectional iterators or random-access iterators. However, an algorithm that requires random-access iterators can be used only with containers that have random-access iterators. |
| Container | Type of iterator supported |
| Sequence containers (first class) | |
vector |
random access |
deque |
random access |
list |
bidirectional |
| Associative containers (first class) | |
set |
bidirectional |
multiset |
bidirectional |
map |
bidirectional |
multimap |
bidirectional |
| Container adapters | |
stack |
no iterators supported |
queue |
no iterators supported |
priority_queue |
no iterators supported |
Fig. 23.8 Iterator types supported by each Standard Library container.