Deitel & Associates, Inc. Logo

Back to
digg.png delicious.png blinkit.png furl.png
C++ How to Program, 5/e

© 2005
pages: 1500
Buy the Book!
Amazon logo
InformIT logo

[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
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.

Page 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12

Tutorial Index