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 std.
The following containers are defined in the current revision of the C++ standard: std::array<T, N> implements a compile-time non-resizable array. std::bitset<N> implements a compile-time bit set. std::vector<T> implements an array with fast random access and an ability to automatically resize when appending elements. std::inplace_vector<T> implements a resizable array with contiguous in-place storage. std::deque<T> implements a double-ended queue with comparatively fast random access. std::list<T> implements a doubly linked list. std::forward_list<T> implements a singly linked list. std::hive<T> implements an object pool.
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 std::pmr (for polymorphic memory resources). These versions specify the optional template parameter Allocator as std::pmr::polymorphic_allocator.
C++ further defines container adapters that wrap a sequence container: std::stack<T> implements a stack with deque as the default underlying container. std::queue<T> implements a queue with deque as the default underlying container. std::priority_queue<T> implements a priority queue (by default max heap) with vector as the default underlying container. std::flat_set<T> implements a "flat set" (stores a sorted set of unique keys) with vector as the default underlying container. std::flat_map<K, V> implements a "flat map" (stores a sorted set of unique key-value pairs) with vector as the default underlying containers. std::flat_multiset<T> implements a "flat multi-set" (stores a sorted set of keys) with vector as the default underlying container. std::flat_multimap<K, V> implements a "flat multi-map" (stores a sorted set of key-value pairs) with vector as the default underlying containers.
The "flat" collections (std::flat_set, std::flat_map, std::flat_multiset, and std::flat_multimap) use std::vector as the underlying container, unlike their "non-flat" equivalents (std::set, std::map, std::multiset, and std::multimap), which store data as red–black trees (hence being "flat").
View container types represent views over non-owning arrays of elements: std::span<T> implements a non-owning view over a contiguous sequence of objects. std::mdspan<T> implements a non-owning view over a multi-dimensional array.
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.ISO/IEC (2003). ISO/IEC 14882:2003(E): Programming Languages - C++ §23.1 Container requirements [lib.container.requirements] para. 4 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.
History
Originally, only vector, list and deque 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 array 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 array 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 forward_list container was added to C++11 as a space-efficient alternative to list when reverse iteration is not needed.
In C++20, the class std::formatter was introduced for specifying how a class should be formatted when passed to std::format or std::print. This added formatting for various collection types.
In C++26, two new sequence containers were added: inplace_vector and hive.
Properties array, vector and deque all support fast random access to the elements. list supports bidirectional iteration, whereas forward_list supports only unidirectional iteration.
array does not support element insertion or removal. vector 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 vector 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. deque, list and forward_list all support fast insertion or removal of elements anywhere in the container. list and forward_list preserves validity of iterators on such operation, whereas deque invalidates all of them.
The collections vector, deque, list and forward_list also have a template parameter Allocator which is default-specified as std::allocator<T> (where T is the stored type).
Containers Array std::array<T, N> implements a non-resizable array. The size N, 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 <array>.
It is essentially equivalent to core-language arrays such as T[] in Java and .NET or [T; N] in Rust. Traditional C arrays (T[]) do not store information such as length. array, unlike T[], 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, std::bitset, which acts as a bit array whose size must be known at compile time.
import std;
using std::array;
array<int, 3> a = {1, 2, 3}; // OK array<int> a = {1, 2, 3}; // not OK: length not specified in declaration array a{1, 2, 3}; // OK: deduces type as array<int, 3> using CTAD
// compare with C-style arrays: int a = {1, 2, 3}; // OK: length specified as 3 int a[] = {1, 2, 3}; // OK: length inferred by compiler
std::span is a close relative of array, for non-owning array views. std::mdspan is a multi-dimensional version of span, however these are view containers.
Bit set std::bitset<N> implements a non-resizable bit set. The size N, an unsigned integer, must be determined at compile time as a template parameter, much like std::array<T, N>. It is much more compact than std::vector<bool>, 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 unsigned long 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 <bitset>.
It is essentially equivalent to java.util.BitSet in Java, System.Collections.BitArray in .NET, or the former std::collections::BitSet in Rust.
For a dynamic bit set, third party libraries such as Boost provide classes such as boost::dynamic_bitset<Block, Allocator>. While vector<bool> does store packed bits and can be dynamically sized, vector<bool>::operator[] returns a proxy type vector<bool>::reference (rather than bool&), and lacks the bitwise operations provided by bitset.
Vectors Vector The elements of a std::vector<T> 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 <vector>.
It is essentially equivalent to java.util.ArrayList in Java, System.Collections.Generic.List in .NET, or std::vec::Vec 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.
Capacity and reallocation 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.ISO/IEC (2003). ISO/IEC 14882:2003(E): Programming Languages - C++ §23.2.4.3 vector modifiers [lib.vector.modifiers] para. 1 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.ISO/IEC (2003). ISO/IEC 14882:2003(E): Programming Languages - C++ §23.2.4.2 vector capacity [lib.vector.capacity] para. 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.ISO/IEC (2003). ISO/IEC 14882:2003(E): Programming Languages - C++ §23.2.4.2 vector capacity [lib.vector.capacity] para. 2
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.ISO/IEC (2003). ISO/IEC 14882:2003(E): Programming Languages - C++ §23.2.4.3 vector modifiers [lib.vector.modifiers] para. 3
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.
Specialization for bool