The following containers are defined in the current revision of the C++ standard: array, vector, list, forward_list, deque.
Each of these containers implements different algorithms for data storage, which means that they have different speed guarantees for different operations:[1] Since each of the containers needs to be able to copy its elements in order to function properly, the type of the elements must fulfill CopyConstructible and Assignable requirements.
Alexander Stepanov, the primary designer of the STL, bemoans the choice of the name vector, saying that it comes from the older programming languages Scheme and Lisp but is inconsistent with the mathematical meaning of the term.
The forward_list container was added to C++11 as a space-efficient alternative to list when reverse iteration is not needed.
array, vector and deque all support fast random access to the elements.
deque, list and forward_list all support fast insertion or removal of elements anywhere in the container.
[4] Like all dynamic array implementations, vectors have low memory usage and good locality of reference and data cache utilization.
Linked-lists and sets, on the other hand, do not support random access or pointer arithmetic.
When new elements are inserted, if the new size of the vector becomes larger than its capacity, reallocation occurs.
This is inefficient for cases where the vector holds plain old data and additional contiguous space beyond the held block of memory is available for allocation.
The description of this specialization indicates that the implementation should pack the elements so that every bool only uses one bit of memory.
There is a general consensus among the C++ Standard Committee and the Library Working Group that vector
operation that requires a list traversal to find the node that needs to be accessed.
With small data types (such as ints) the memory overhead is much more significant than that of a vector.
It provides similar computational complexity to vector for most operations, with the notable exception that it provides amortized constant-time insertion and removal from both ends of the element sequence.
By design, the container does not support allocators because it's basically a C-style array wrapper.