Delving into the STL: Containers and Iterators

If you store pointers in containers, we recommend using reference-counted smart pointers in order to handle the memory management properly. However, you cannot use the C++ auto_ptr class in containers because it does not implement copying correctly (as far as the STL is concerned). See Chapter 25 for a SuperSmartPointer class that you can use in the STL containers.

The specific requirements on elements in containers are shown in the following table:

Method	Desription	Notes
Copy	Creates a new element that is “equal”	Used every time you insert an element.
Constructor	to the old one, but that can safely
	be destructed without affecting the
	old one.

Assignment	Replaces the contents of an element
Operator	with a copy of the source element.
Destructor	Cleans up an element.
Default	Constructs an element without any
Constructor	arguments.
operator==	Compares two elements for equality.
operator<	Determines if one element is less
	than another.

Used every time you modify an element.

Used every time you remove an element.

Required only for certain operations such as vector resize() method and the map operator[] access.

Required only for certain operations such as operator== on two containers.

Required only for certain operations such as operator< on two containers. operator< is also the default comparison for keys in associative containers.

Consult Chapters 9 and 16 for details about writing these methods.

The STL containers call the copy constructor and assignment operator for elements often, so make those operations efficient.

Exceptions and Error Checking

The STL containers provide limited error checking. Clients are expected to ensure that their uses are valid. However, some container methods and functions throw exceptions in certain conditions such as out-of-bounds indexing. This chapter mentions exceptions where appropriate. The Standard Library Reference resource on the Web site attempts to catalog the possible exceptions thrown from each method. However, it is impossible to list exhaustively the exceptions that can be thrown from these methods because they perform operations on user-specified types with unknown exception characteristics.

563

Chapter 21

Iterators

As described in Chapter 4, 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 Supported	Comments
Input	operator++	Provides read-only access, forward-only (no
	operator*	operator-- to move backward).
	operator->	Iterators can be assigned and copied with
	copy constructor	assignment operator and copy constructor.
	operator=	Iterators can be compared for equality.
	operator==
	operator!=

Output	operator++
	operator*
	copy constructor
Forward	operator++
	operator*
	operator->
	copy constructor
	default constructor
	operator=
	operator==
	operator!=
Bidirectional	Capbilities of Forward
	iterators, plus:
	operator--
Random Access	Bidirectional capability, plus:
	operator+, operator-,
	operator+=, operator-=
	operator<, operator>,
	operator<=, operator>=
	operator[]

Provides write-only access, forward only. Iterators cannot be assigned or copied. Iterators cannot be compared for equality. Note the absence of 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.

Provides everything forward iterator provides Iterators can also move backward to previous element.

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.

564