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 nonowning view over a contiguous sequence of objects.

The most used containers

The rationale for these containers to be templates was presented in the “Template Basics” section. We don’t want to write the same implementation again and again for each different type of element that we need to store in a container. Arguably, the most used containers from the standard library are the following:

• vector: This is a variable-size collection of elements stored contiguously in memory. It’s the default container we would choose, provided no special requirements are defined. The internal storage expands or shrinks automatically as needed to accommodate the stored elements. The vector allocates more memory than needed so that the risk of having to expand is low. The expansion is a costly operation because new memory needs to be allocated, the content of the current storage needs to be copied to the new one, and lastly, the previous storage needs to be discarded. Because elements are stored contiguously in memory, they can be randomly accessed by an index in constant time.

• array: This is a fixed-size collection of elements stored contiguously in memory. The size must be a compile-time constant expression. The semantics of the array class is the same as a structure holding a C-style array (T[n]). Just like the vector type, the elements of the array class can be accessed randomly in constant time.