In C++, sequence containers or sequence collections refer to a group of container class templates in the standard library that implement storage of data elements. Being templates, they can be used to store arbitrary elements, such as integers or custom classes. One common property of all sequential containers is that the elements can be accessed sequentially. Like all other standard library components, they reside in namespace <code>std</code>.
The following containers are defined in the current revision of the C++ standard:
Each of these containers implements different algorithms for data storage, which means that they have different speed guarantees for different operations.
There are also versions of these collections in namespace <code>std::pmr</code> (for polymorphic memory resources). These versions specify the optional template parameter <code>Allocator</code> as <code>std::pmr::polymorphic_allocator</code>.
C++ further defines container adapters that wrap a sequence container:
The "flat" collections (<code>std::flat_set</code>, <code>std::flat_map</code>, <code>std::flat_multiset</code>, and <code>std::flat_multimap</code>) use <code>std::vector</code> as the underlying container, unlike their "non-flat" equivalents (<code>std::set</code>, <code>std::map</code>, <code>std::multiset</code>, and <code>std::multimap</code>), which store data as redâÂÂblack trees (hence being "flat").
View container types represent views over non-owning arrays of elements:
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 <code>CopyConstructible</code> and <code>Assignable</code> requirements. For a given container, all elements must belong to the same type. For instance, one cannot store data in the form of both char and int within the same container instance.
Originally, only <code>vector</code>, <code>list</code> and <code>deque</code> were defined. Until the standardization of the C++ language in 1998, they were part of the Standard Template Library (STL), published by SGI. 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 <code>array</code> container at first appeared in several books under various names. Later it was incorporated into a Boost library, and was proposed for inclusion in the standard C++ library. The motivation for inclusion of <code>array</code> was that it solves two problems of the C-style array: the lack of an STL-like interface, and an inability to be copied like any other object. However, unlike C-style arrays, it can only be declared at compile-time, and not at runtime. It firstly appeared in C++ TR1 and later was incorporated into C++11.
The <code>forward_list</code> container was added to C++11 as a space-efficient alternative to <code>list</code> when reverse iteration is not needed.
In C++20, the class <code>std::formatter</code> was introduced for specifying how a class should be formatted when passed to <code>std::format</code> or <code>std::print</code>. This added formatting for various collection types.
In C++26, two new sequence containers were added: <code>inplace_vector</code> and <code>hive</code>.
<code>array</code>, <code>vector</code> and <code>deque</code> all support fast random access to the elements. <code>list</code> supports bidirectional iteration, whereas <code>forward_list</code> supports only unidirectional iteration.
<code>array</code> does not support element insertion or removal. <code>vector</code> supports fast element insertion or removal at the end. Any insertion or removal of an element not at the end of the vector needs elements between the insertion position and the end of the vector to be copied. The iterators to the affected elements are thus invalidated. In fact, any insertion can potentially invalidate all iterators. Also, if the allocated storage in the <code>vector</code> is too small to insert elements, a new array is allocated, all elements are copied or moved to the new array, and the old array is freed. <code>deque</code>, <code>list</code> and <code>forward_list</code> all support fast insertion or removal of elements anywhere in the container. <code>list</code> and <code>forward_list</code> preserves validity of iterators on such operation, whereas <code>deque</code> invalidates all of them.
The collections <code>vector</code>, <code>deque</code>, <code>list</code> and <code>forward_list</code> also have a template parameter <code>Allocator</code> which is default-specified as <code>std::allocator<T></code> (where <code>T</code> is the stored type).
<code>std::array<T, N></code> implements a non-resizable array. The size <code>N</code>, an unsigned integer, must be determined at compile-time by a template parameter (and thus cannot be declared at runtime, like C arrays). By design, the container does not support allocators because it is basically a C-style array wrapper. C++ does not support variable-length arrays.
It is declared in header <code><array></code>.
It is essentially equivalent to core-language arrays such as <code>T[]</code> in Java and .NET or <code>[T; N]</code> in Rust. Traditional C arrays (<code>T[]</code>) do not store information such as length. <code>array</code>, unlike <code>T[]</code>, must always specify its size at declaration, and cannot be inferred by the compiler (unless using class template argument deduction (CTAD)). This is similar to another collection, <code>std::bitset</code>, which acts as a bit array whose size must be known at compile time.
<code>std::span</code> is a close relative of <code>array</code>, for non-owning array views. <code>std::mdspan</code> is a multi-dimensional version of <code>span</code>, however these are view containers.
<code>std::bitset<N></code> implements a non-resizable bit set. The size <code>N</code>, an unsigned integer, must be determined at compile time as a template parameter, much like <code>std::array<T, N></code>. It is much more compact than <code>std::vector<bool></code>, storing just bits and a small amount of padding.
It further supports bitwise operations, as well as accessing and modifying specific bits. It supports conversion to <code>unsigned long</code> as well as to strings, and testing/querying the number of active bits. However, unlike other containers, it does not support iterators.
It is declared in header <code><bitset></code>.
It is essentially equivalent to <code>java.util.BitSet</code> in Java, <code>System.Collections.BitArray</code> in .NET, or the former <code>std::collections::BitSet</code> in Rust.
For a dynamic bit set, third party libraries such as Boost provide classes such as <code>boost::dynamic_bitset<Block, Allocator></code>. While <code>vector<bool></code> does store packed bits and can be dynamically sized, <code>vector<bool>::operator[]</code> returns a proxy type <code>vector<bool>::reference</code> (rather than <code>bool&</code>), and lacks the bitwise operations provided by <code>bitset</code>.
The elements of a <code>std::vector<T></code> are stored contiguously. 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.
It is declared in header <code><vector></code>.
It is essentially equivalent to <code>java.util.ArrayList</code> in Java, <code>System.Collections.Generic.List</code> in .NET, or <code>std::vec::Vec</code> in Rust.
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, 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. 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. Using an invalidated reference causes undefined behaviour.
The <code>reserve()</code> operation may be used to prevent unnecessary reallocations. After a call to <code>reserve(n)</code>, the vector's capacity is guaranteed to be at least n.
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.
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 <code>vector</code> template for <code>bool</code>. The description of this specialization indicates that the implementation should pack the elements so that every <code>bool</code> only uses one bit of memory. <code>vector<bool></code> can be seen as similar to a dynamic bit set, but while <code>vector<bool></code> does store packed bits and can be dynamically sized, <code><vector<bool>::operator[]</code> returns a proxy type <code>vector<bool>::reference</code> (rather than <code>bool&</code>), and lacks the bitwise operations provided by <code>bitset</code>. This is widely considered a mistake. <code>vector<bool></code> does not meet the requirements for a C++ Standard Library container. For instance, a <code>Container<T>::reference</code> must be a true of type <code>T</code>. This is not the case with <code>vector<bool>::reference</code>, which is a proxy class convertible to <code>bool</code>. Similarly, the <code>vector<bool>::iterator</code> does not yield a <code>bool&</code> when dereferenced. There is a general consensus among the C++ Standard Committee and the Library Working Group that <code>vector<bool></code> should be deprecated and subsequently removed from the standard library, while the functionality will be reintroduced under a different name.
If looking to store a list of <code>bool</code> whose size is known at compile time, a <code>std::bitset<N></code> (bit array) is the more reasonable collection to use, due to lower overhead and being overall more efficient. However, <code>bitset</code> unlike <code>vector</code> is not dynamic.
<code>std::inplace_vector<T, N></code> is a dynamically-resizable array with contiguous in-place storage, essentially with a fixed maximum capacity and whose true size can grow and shrink up to <code>N</code>. It does not allocate on the heap.
It is declared in header <code><inplace_vector></code>.
External libraries such as arrayvec exist for Rust, which implement <code>ArrayVec<T, N></code>, as well as <code>ArrayString<N></code>. Prior to its inclusion to C++, alternatives such as <code>boost::container::static_vector</code> and <code>llvm::StaticVector<T, N></code> existed.
<code>std::deque<T></code> is a container class template that implements a double-ended queue. It provides similar computational complexity to <code>vector</code> for most operations, with the notable exception that it provides amortized constant-time insertion and removal from both ends of the element sequence. Unlike <code>vector</code>, <code>deque</code> uses discontiguous blocks of memory, and provides no means to control the capacity of the container and the moment of reallocation of memory. Like <code>vector</code>, <code>deque</code> offers support for random-access iterators, and insertion and removal of elements invalidates all iterators to the deque.
It is declared in header <code><deque></code>.
It is essentially equivalent to <code>java.util.ArrayDeque</code> in Java or <code>std::collections::VecDeque</code> in Rust.
The <code>std::list<T></code> 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.
It is declared in header <code><list></code>.
It is essentially equivalent to <code>java.util.LinkedList</code> in Java, <code>System.Collections.Generic.LinkedList</code> in .NET, or <code>std::collections::LinkedList</code> in Rust.
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 operation. No shifting is required like with vectors.
Lists do not have random-access ability like vectors ( operation). Accessing a node in a list is an operation that requires a list traversal to find the node that needs to be accessed.
With small data types (such as <code>int</code>s) the memory overhead is much more significant than that of a vector. Each node (of type <code>T</code> takes up <code>sizeof(T) + 2 * sizeof(T*)</code>. 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 <code>std::forward_list<T></code> data structure implements a singly linked list.
It is declared in header <code><forward_list></code>.
Few languages have a distinct singly linked list type like <code>forward_list</code>, however external libraries such as fwdlist for Rust exist.
<code>std::hive<T></code> is a collection that reuses erased elements' memory. It can be seen as similar to an object pool. It uses another class, <code>std::hive_limits</code> to store layout information on block capacity limits. Unlike <code>vector</code> which stores data in a single contiguous block of memory, it stores data in a chain of multiple blocks of memory. It can store and erase elements efficiently, and guarantees iterator stability.
Lookup, removal, and iteration are , while insertion is amortised .
It is based on the class <code>plf::colony</code> from the <code>plf</code> library.
It is declared in header <code><hive></code>.
It is essentially equivalent to <code>Microsoft.Extensions.ObjectPool.ObjectPool</code> in .NET. External libraries such as colony exist for Rust, which implement <code>Colony<T></code>.
A container adapter in C++ is for wrapping sequence collection types in an alternate interface. Each collection type has a template parameter <code>Container</code> which is default-specified, but can be configured as needed.
The <code>std::stack<T></code> data structure implements a stack (last-in-first-out structure). Its default underlying collection type is <code>deque</code>.
It is declared in header <code><stack></code>.
It is essentially equivalent to <code>java.util.Stack</code> (however it is considered obsolete in favour of instead using <code>java.util.ArrayDeque</code>) in Java or <code>System.Collections.Generic.Stack</code> in .NET.
The <code>std::queue<T></code> data structure implements a queue (first-in-first-out structure). Its default underlying collection type is <code>deque</code>.
It is declared in header <code><queue></code>.
It is similar to the Java interface <code>java.util.Queue</code> or <code>System.Collections.Generic.Queue</code> in .NET.
The <code>std::priority_queue<T></code> data structure implements a priority queue, which is by default sorted using function object <code>std::less<T></code> (a max heap). Its default underlying collection type is <code>vector</code>.
It is declared in header <code><queue></code>.
It is essentially equivalent to <code>java.util.PriorityQueue</code> in Java (however this is a min-heap), <code>System.Collections.Generic.PriorityQueue</code> in .NET, or <code>std::collections::BinaryHeap</code> in Rust.
The <code>std::flat_set<T></code> data structure implements a "flat set", which stores a collection of unique keys, which is by default sorted using function object <code>std::less<T></code>. Its default underlying collection type is <code>vector</code>.
It is declared in header <code><flat_set></code>.
The <code>std::flat_map<K, V></code> data structure implements a "flat map", which stores a collection of unique key-value pairs, which is by default sorted using function object <code>std::less<K></code>. It has two underlying collections (for the keys and values), both by default <code>vector</code>.
It is declared in header <code><flat_map></code>.
The <code>std::flat_multiset<T></code> data structure implements a "flat multi-set", which stores a collection of keys, which is by default sorted using function object <code>std::less<T></code>. It allows for multiple keys with equivalent values. Its default underlying collection type is <code>vector</code>.
It is declared in header <code><flat_set></code>.
The <code>std::flat_multimap<K, V></code> data structure implements a "flat multi-map", which stores a collection of key-value pairs, which is by default sorted using function object <code>std::less<K></code>. It allows for multiple entries with equivalent keys. It has two underlying collections (for the keys and values), both by default <code>vector</code>.
It is declared in header <code><flat_map></code>.
A view container in C++ is used for interacting with various non-owning arrays of elements.
The <code>std::span<T></code> data structure implements a non-owning view over a single-dimensional contiguous sequence of objects.
It is declared in header <code><nowiki><span></nowiki></code>.
It is similar to the classes <code>java.nio.Buffer</code> and its descendants (which are each non-owning views over primitive arrays) in Java, <code>System.Span</code> in .NET, or <code>&[T]</code>, <code>&mut [T]</code> (slices) in Rust.
The <code>std::mdspan<T></code> data structure implements a non-owning view over a multi-dimensional array.
It is declared in header <code><mdspan></code>.
The containers are defined in headers named after the names of the containers, e.g. <code>vector</code> is defined in header <code><vector></code>. All containers satisfy the requirements of the Container concept, which means they have <code>begin()</code>, <code>end()</code>, <code>size()</code>, <code>max_size()</code>, <code>empty()</code>, and <code>swap()</code> methods.
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 <code>list</code> and <code>forward_list</code> class:
The following example demonstrates various techniques involving a vector and C++ Standard Library algorithms (with C++20 <code>std::ranges</code>), notably shuffling, sorting, finding the largest element, and erasing from a vector using the erase-remove idiom.
The output will be the following: <pre> The largest number is 8 It is located at index 6 (implementation-dependent) The number 5 is located at index 4 1 2 3 4 </pre>