Chapter 5. Effective Data Structures beyond STL

The C++ Standard Library provides a rich set of generic containers that can be employed for a wide variety of common programming tasks. These include sequence containers like std::vector, std::deque, std::list, std::forward_list, and ordered and unordered associative containers like std::map, std::set, std::unordered_map, std::unordered_set, and so on.

Containers are traversed, and their individual elements accessed, using iterators. C++ defines a hierarchy of iterator categories based on the kind of access they provide to the elements of the container (read, write, forward traversal, bidirectional traversal, and random access). The type of iterator available for traversing a container is dependent on the internal structure of a container.

Available alongside the containers is a library of generic algorithms that read and manipulate generic containers, using one or more iterators. These libraries heavily rely on generic programming...