Sequence container (C++)

The elements of a vector are stored contiguously.[3] Like all dynamic array implementations, vectors have low memory usage and good locality of reference and data cache utilization. Unlike other STL containers, such as deques and lists, vectors allow the user to denote an initial capacity for the container.

Vectors allow random access; that is, an element of a vector may be referenced in the same manner as elements of arrays (by array indices). Linked-lists and sets, on the other hand, do not support random access or pointer arithmetic.

The vector data structure is able to quickly and easily allocate the necessary memory needed for specific data storage, and it is able to do so in amortized constant time. This is particularly useful for storing data in lists whose length may not be known prior to setting up the list but where removal (other than, perhaps, at the end) is rare. Erasing elements from a vector or even clearing the vector entirely does not necessarily free any of the memory associated with that element.

A typical vector implementation consists, internally, of a pointer to a dynamically allocated array,[1] and possibly data members holding the capacity and size of the vector. The size of the vector refers to the actual number of elements, while the capacity refers to the size of the internal array.

When new elements are inserted, if the new size of the vector becomes larger than its capacity, reallocation occurs.[1][4] This typically causes the vector to allocate a new region of storage, move the previously held elements to the new region of storage, and free the old region.

Because the addresses of the elements change during this process, any references or iterators to elements in the vector become invalidated.[5] Using an invalidated reference causes undefined behaviour.

The reserve() operation may be used to prevent unnecessary reallocations. After a call to reserve(n), the vector's capacity is guaranteed to be at least n.[6]

The vector maintains a certain order of its elements, so that when a new element is inserted at the beginning or in the middle of the vector, subsequent elements are moved backwards in terms of their assignment operator or copy constructor. Consequently, references and iterators to elements after the insertion point become invalidated.[7]

C++ vectors do not support in-place reallocation of memory, by design; i.e., upon reallocation of a vector, the memory it held will always be copied to a new block of memory using its elements' copy constructor, and then released. 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 Standard Library defines a specialization of the vector template for bool. The description of this specialization indicates that the implementation should pack the elements so that every bool only uses one bit of memory.[8] This is widely considered a mistake.[9][10] vector<bool> does not meet the requirements for a C++ Standard Library container. For instance, a container<T>::reference must be a true lvalue of type T. This is not the case with vector<bool>::reference, which is a proxy class convertible to bool.[11] Similarly, the vector<bool>::iterator does not yield a bool& when dereferenced. There is a general consensus among the C++ Standard Committee and the Library Working Group that vector<bool> should be deprecated and subsequently removed from the standard library, while the functionality will be reintroduced under a different name.[12]

The list data structure implements a doubly linked list. Data is stored non-contiguously in memory which allows the list data structure to avoid the reallocation of memory that can be necessary with vectors when new elements are inserted into the list.

The list data structure allocates and deallocates memory as needed; therefore, it does not allocate memory that it is not currently using. Memory is freed when an element is removed from the list.

Lists are efficient when inserting new elements in the list; this is an ${\displaystyle O(1)}$ operation. No shifting is required like with vectors.

Lists do not have random access ability like vectors (${\displaystyle O(1)}$ operation). Accessing a node in a list is an ${\displaystyle O(n)}$ 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. Each node takes up sizeof(type) + 2 * sizeof(type*). Pointers are typically one word (usually four bytes under 32-bit operating systems), which means that a list of four byte integers takes up approximately three times as much memory as a vector of integers.

The forward_list data structure implements a singly linked list.

deque is a container class template that implements a double-ended queue. 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. Unlike vector, deque uses discontiguous blocks of memory, and provides no means to control the capacity of the container and the moment of reallocation of memory. Like vector, deque offers support for random access iterators, and insertion and removal of elements invalidates all iterators to the deque.

array implements a compile-time non-resizable array. The size is determined at compile-time by a template parameter. By design, the container does not support allocators. Unlike the other standard containers, array does not provide constant-time swap.

There are other operations that are available as a part of the list class and there are algorithms that are part of the C++ STL (Algorithm (C++)) that can be used with the list and forward_list class:

• list::merge and forward_list::merge - Merges two sorted lists
• list::splice and forward_list::splice_after - Moves elements from another list
• list::remove and forward_list::remove - Removes elements equal to the given value
• list::remove_if and forward_list::remove_if - Removes elements satisfying specific criteria
• list::reverse and forward_list::reverse - Reverses the order of the elements
• list::unique and forward_list::unique - Removes consecutive duplicate elements
• list::sort and forward_list::sort - Sorts the elements