Professional C__ - Marc Gregoire [189]
Iterators
The STL uses the iterator pattern to provide a generic abstraction for accessing the elements of the containers. Each container provides a container-specific iterator, which is a glorified smart pointer that knows how to iterate over the elements of that specific container. The iterators for all the different containers adhere to a specific interface defined in the C++ standard. Thus, even though the containers provide different functionality, the iterators present a common interface to code that wishes to work with elements of the containers.
You can think of an iterator as a pointer to a specific element of the container. Like pointers to elements in an array, iterators can move to the next element with operator++. Similarly, you can usually use operator* and operator-> on the iterator to access the actual element or field of the element. Some iterators allow comparison with operator== and operator!=, and support operator-- for moving to previous elements. Different containers provide iterators with slightly different capabilities. The standard defines five categories of iterators, summarized in the following table.
ITERATOR CATEGORY OPERATIONS REQUIRED COMMENTS
Read (officially called “input” iterator) operator++
operator*
operator->
copy constructor
operator=
operator==
operator!= Provides read-only access, forward-only (no operator-- to move backward).
Iterators can be assigned and copied with assignment operator and copy constructor.
Iterators can be compared for equality.
Write (officially called “output” iterator) operator++
operator*
copy constructor Provides write-only access, forward only.
Iterators cannot be assigned.
Iterators cannot be compared for equality.
Note the absence of operator->.
Forward operator++
operator*
operator->
copy constructor
default constructor
operator=
operator==
operator!= Provides read/write access, forward only.
Iterators can be assigned and copied with assignment operator and copy constructor.
Iterators can be compared for equality.
Bidirectional Capabilities of forward iterators, plus:
operator-- Provides everything forward iterator provides.
Iterators can also move backward to previous element.
Random Access Bidirectional capability, plus:
operator+
operator-
operator+=
operator-=
operator<
operator>
operator<=
operator>=
operator[] Equivalent to dumb pointers: Iterators support pointer arithmetic, array index syntax, and all forms of comparison.
The standard containers that provide iterators all furnish either random access or bidirectional iterators.
Iterators are implemented similarly to smart pointer classes in that they overload the specific desired operators. Consult Chapter 18 for details on operator overloading. See Chapter 17 for a sample iterator implementation.
The basic iterator operations are similar to those supported by dumb pointers, so a dumb pointer is a legitimate iterator for certain containers. In fact, the vector iterator is often implemented as simply a dumb pointer. However, as a client of the containers, you need not worry about the implementation details; you can simply use the iterator abstraction.
Iterators might not be implemented internally as pointers, so this text uses the term “refers to” instead of “points to” when discussing the elements accessible via an iterator.
Chapters 13 and 17 delve into more detail about iterators and the STL algorithms that use them. This chapter shows you the basics of using the iterators for each container.
Only the sequential containers, associative containers, and unordered associative containers provide iterators. The container adapters and bitset class do not support iteration over their elements.
Common Iterator typedefs and Methods
Every container class in the STL that supports iterators provides public typedefs for its iterator types called iterator and const_iterator.