16.2 Minimum Iterator Requirements

With few exceptions, the Standard Library separates algorithms from containers. This makes it much easier to add new algorithms and to use them with multiple containers. An important part of every container is the type of iterator it supports (Fig. 15.7). This determines which algorithms can be applied to the container. For example, both vectors and arrays support random-access iterators that provide all of the iterator operations shown in Fig. 15.9. All Standard Library algorithms can operate on vectors and those that do not modify a container’s size can also operate on arrays. Each Standard Library algorithm that takes iterator arguments requires those iterators to provide a minimum level of functionality. If an algorithm requires a forward iterator, for example, that algorithm can operate on any container that supports forward iterators, bidirectional iterators or random-access iterators.

Software Engineering Observation 16.1

Standard Library algorithms do not depend on the implementation details of the containers on which they operate. As long as a container’s (or built-in array’s) iterators satisfy the requirements of an algorithm, the algorithm can work on the container.

Software Engineering Observation 16.2

The Standard Library containers are implemented concisely. The algorithms are separated from the containers and operate on elements of the containers only indirectly through iterators. This separation makes it easier to write generic algorithms applicable to a variety of container classes.

Software Engineering Observation 16.3

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.

Iterator Invalidation

Iterators simply point to container elements, so it’s possible for iterators to become invalid when certain container modifications occur. For example, if you invoke clear on a vector, all of its elements are destroyed. Any iterators that pointed to that vector’s elements before clear was called would now be invalid. Section 23 of the C++ standard discusses all the cases in which iterators (and pointers and references) are invalidated for each Standard Library container. Here we summarize when iterators are invalidated during insert and erase operations.

When inserting into

  • a vector—If the vector is reallocated, all iterators pointing to it are invalidated. Otherwise, iterators from the insertion point to the end of the vector are invalidated.

  • a deque—All iterators are invalidated.

  • a list or forward_list—All iterators remain valid.

  • an ordered associative container—All iterators remain valid.

  • an unordered associative container—All iterators are invalidated if the container needs to be reallocated.

When erasing from a container, iterators to the erased elements are invalidated. In addition:

  • for a vector—Iterators from the erased element to the end of the vector are invalidated.

  • for a deque—If an element in the middle of the deque is erased, all iterators are invalidated.

..................Content has been hidden....................

You can't read the all page of ebook, please click here login for view all page.
Reset