Understanding the design of containers, iterators, and algorithms

Containers are types that represent collections of elements. These collections can be implemented based on a variety of data structures, each with different semantics: lists, queues, trees, and so on. The standard library provides three categories of containers:

• Sequence containers: vector, deque, list, array, and forward_list
• Associative containers: set, map, multiset, and multimap
• Unordered associative containers: unordered_set, unordered_map, unordered_multiset, and unordered_multimap

In addition to this, there are also container adaptors that provide a different interface for sequence containers. This category includes the stack, queue, and priority_queue classes. Finally, there is a class called span that represents a non-owning view over a contiguous sequence of objects.

The rationale for these containers to be templates was presented in Chapter 1, Introduction to Templates. You don’...