The sequential containers, which are listed in Table 9.1, all provide fast sequential access to their elements. However, these containers offer different performance trade-offs relative to
• The costs to add or delete elements to the container
• The costs to perform nonsequential access to elements of the container
With the exception of array
, which is a fixed-size container, the containers provide efficient, flexible memory management. We can add and remove elements, growing and shrinking the size of the container. The strategies that the containers use for storing their elements have inherent, and sometimes significant, impact on the efficiency of these operations. In some cases, these strategies also affect whether a particular container supplies a particular operation.
For example, string
and vector
hold their elements in contiguous memory. Because elements are contiguous, it is fast to compute the address of an element from its index. However, adding or removing elements in the middle of one of these containers takes time: All the elements after the one inserted or removed have to be moved to maintain contiguity. Moreover, adding an element can sometimes require that additional storage be allocated. In that case, every element must be moved into the new storage.
The list
and forward_list
containers are designed to make it fast to add or remove an element anywhere in the container. In exchange, these types do not support random access to elements: We can access an element only by iterating through the container. Moreover, the memory overhead for these containers is often substantial, when compared to vector, deque
, and array
.
A deque
is a more complicated data structure. Like string
and vector, deque
supports fast random access. As with string
and vector
, adding or removing elements in the middle of a deque
is a (potentially) expensive operation. However, adding or removing elements at either end of the deque
is a fast operation, comparable to adding an element to a list
or forward_list
.
The forward_list
and array
types were added by the new standard. An array
is a safer, easier-to-use alternative to built-in arrays. Like built-in arrays, library array
s have fixed size. As a result, array
does not support operations to add and remove elements or to resize the container. A forward_list
is intended to be comparable to the best handwritten, singly linked list. Consequently, forward_list
does not have the size
operation because storing or computing its size would entail overhead compared to a handwritten list. For the other containers, size
is guaranteed to be a fast, constant-time operation.
For reasons we’ll explain in § 13.6 (p. 531), the new library containers are dramatically faster than in previous releases. The library containers almost certainly perform as well as (and usually better than) even the most carefully crafted alternatives. Modern C++ programs should use the library containers rather than more primitive structures like arrays.