View source for Sequence container (C++)

{{Short description|Group of standard library class templates}}
{{Use dmy dates|date=January 2021}}
{{C++ Standard library}}
In computing, '''sequence containers''' refer to a group of [[container (data structure)|container]] [[class template]]s in the [[C++ Standard Library|standard library]] of the [[C++|C++ programming language]] that implement storage of data elements. Being [[Template (programming)|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 (C++)|namespace]] ''std''.
The following containers are defined in the current revision of the C++ standard: <code>array</code>, <code>vector</code>, <code>list</code>, <code>forward_list</code>, <code>deque</code>. Each of these containers implements different algorithms for data storage, which means that they have different speed guarantees for different operations:<ref name="josuttis">{{cite book | first = Nicolai | last = Josuttis | author-link = Nicolai Josuttis | year = 1999 | title = C++ Standard Library - A Tutorial and Reference | publisher = Addison-Wesley}}</ref>
*<code>array</code> implements a compile-time non-resizable array.
*<code>vector</code> implements an array with fast [[random access]] and an ability to automatically resize when appending elements.
*<code>deque</code> implements a [[double-ended queue]] with comparatively fast random access.
*<code>list</code> implements a [[doubly linked list]].
*<code>forward_list</code> implements a [[singly linked list]].
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.<ref name="C++03 23.1/4">[[International Organization for Standardization|ISO]]/[[International Electrotechnical Commission|IEC]] (2003). ''[[ISO/IEC 14882|ISO/IEC 14882:2003(E): Programming Languages - C++]] §23.1 Container requirements [lib.container.requirements]'' para. 4</ref> For a given container, all elements must belong to the same type. For instance, one cannot store data in the form of both [[Character (computing)|char]] and [[Integer (computer science)|int]] within the same container instance.
== History ==
{{expand section|date=December 2011}}
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 [[Silicon Graphics|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 (programming language)|Scheme]] and [[Lisp (programming language)|Lisp]] but is inconsistent with the mathematical meaning of the term.<ref>{{Cite book |last=Stepanov |first=Alexander A. |url=https://www.worldcat.org/oclc/898036481 |title=From mathematics to generic programming |date=2015 |others=Daniel E. Rose |isbn=978-0-13-349179-1 |location=Upper Saddle River, NJ |oclc=898036481}}</ref>
The <code>array</code> container at first appeared in several books under various names. Later it was incorporated into a [[Boost (C++ libraries)|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. It firstly appeared in [[C++ Technical Report 1|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.
== Properties ==
<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 [[iterator]]s 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.
=== Vector ===
The elements of a <code>vector</code> are stored contiguously.<ref name="C++03 23.2.4/1">{{cite tech report| publisher=[[International Organization for Standardization|ISO]]/[[International Electrotechnical Commission|IEC]] | date=2003 |title= ISO/IEC 14882 ISO/IEC 14882:2003(E): Programming Languages - C++ §23.2.4 Class template vector (lib.vector) paragraph.1|url=http://staff.ustc.edu.cn/~zhuang/cpp/specs/ISO_IEC%2014882%202003.pdf| page=489 | archive-url=https://web.archive.org/web/20220225224452/http://staff.ustc.edu.cn/~zhuang/cpp/specs/ISO_IEC%2014882%202003.pdf | quote=elements of a vector are stored contiguously, meaning that if v is a vector where T is some type other than bool, then it obeys the identity &v[n] == &v[0] + n for all 0 <= n < v.size(). | archive-date=2022-02-25}}</ref> 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 [[deque]]s and [[list (computing)|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 [[set (computing)|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 [[dynamic allocation|dynamically allocated]] array,<ref name="josuttis"/> 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.<ref name="josuttis"/><ref name="C++03 23.2.4.3/1">[[International Organization for Standardization|ISO]]/[[International Electrotechnical Commission|IEC]] (2003). ''[[ISO/IEC 14882|ISO/IEC 14882:2003(E): Programming Languages - C++]] §23.2.4.3 vector modifiers [lib.vector.modifiers]'' para. 1</ref> 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 [[memory address|addresses]] of the elements change during this process, any references or [[iterator]]s to elements in the vector become invalidated.<ref name="C++03 23.2.4.2/5">[[International Organization for Standardization|ISO]]/[[International Electrotechnical Commission|IEC]] (2003). ''[[ISO/IEC 14882|ISO/IEC 14882:2003(E): Programming Languages - C++]] §23.2.4.2 vector capacity [lib.vector.capacity]'' para. 5</ref> 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.<ref name="C++03 23.2.4.2/2">[[International Organization for Standardization|ISO]]/[[International Electrotechnical Commission|IEC]] (2003). ''[[ISO/IEC 14882|ISO/IEC 14882:2003(E): Programming Languages - C++]] §23.2.4.2 vector capacity [lib.vector.capacity]'' para. 2</ref>
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.<ref name="C++03 23.2.4.3/3">[[International Organization for Standardization|ISO]]/[[International Electrotechnical Commission|IEC]] (2003). ''[[ISO/IEC 14882|ISO/IEC 14882:2003(E): Programming Languages - C++]] §23.2.4.3 vector modifiers [lib.vector.modifiers]'' para. 3</ref>
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 structure|plain old data]] and additional contiguous space beyond the held block of memory is available for allocation.
==== Specialization for bool ====
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.<ref name="C++03 23.2.5/1">[[International Organization for Standardization|ISO]]/[[International Electrotechnical Commission|IEC]] (2003). ''[[ISO/IEC 14882|ISO/IEC 14882:2003(E): Programming Languages - C++]] §23.2.5 Class vector<bool> [lib.vector.bool]'' para. 1</ref> This is widely considered a mistake.<ref>{{cite web| title=vector<bool>: More Problems, Better Solutions | url=http://www.gotw.ca/publications/N1211.pdf|accessdate= 28 November 2017 |date=August 1999 }}</ref><ref>{{cite web| title=A Specification to deprecate vector<bool>| url=http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2007/n2204.html |accessdate= 28 November 2017 |date=March 2007 }}</ref> <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 [[Value (computer science)#In C: lvalues and rvalues|lvalue]] 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>.<ref name="C++03 23.2.5/2">[[International Organization for Standardization|ISO]]/[[International Electrotechnical Commission|IEC]] (2003). ''[[ISO/IEC 14882|ISO/IEC 14882:2003(E): Programming Languages - C++]] §23.2.5 Class vector<bool> [lib.vector.bool]'' para. 2</ref> Similarly, the <code>vector<bool>::iterator</code> does not yield a <code>bool&</code> when [[Dereference operator|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.<ref>{{cite web| title=96. Vector<bool> is not a container | url=http://www.open-std.org/Jtc1/sc22/wg21/docs/lwg-closed.html#96 |accessdate= 28 June 2018}}</ref>
=== List ===
The <code>list</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.
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 {{tmath|O(1)}} operation. No shifting is required like with vectors.
Lists do not have random-access ability like vectors ({{tmath|O(1)}} operation). Accessing a node in a list is an {{tmath|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 <code>[[sizeof]](type) + 2 * [[sizeof]](type*)</code>. Pointers are typically one [[word (computer architecture)|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.
=== Forward list ===
The <code>forward_list</code> data structure implements a [[singly linked list]].
=== Deque ===
<code>deque</code> is a container class template that implements a [[double-ended queue]]. It provides similar [[Computational complexity theory|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 iterator]]s, and insertion and removal of elements invalidates all iterators to the deque.
=== Array ===
<code>array</code> implements a non-resizable [[array data structure|array]]. The size is determined at compile-time by a template parameter. By design, the container does not support [[allocator (C++)|allocators]] because it's basically a C-style array wrapper.
== Overview of functions ==
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 [http://www.sgi.com/tech/stl/Container.html Container] [[concept (generic programming)|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.
=== Member functions ===
{| class="wikitable" style="font-size:en"
|-
! Functions
! <code>[http://en.cppreference.com/w/cpp/container/array array]</code><br>([[C++11]])
! <code>[http://en.cppreference.com/w/cpp/container/vector vector]</code><br>
! <code>[http://en.cppreference.com/w/cpp/container/deque deque]</code><br>
! <code>[http://en.cppreference.com/w/cpp/container/list list]</code><br>
! <code>[http://en.cppreference.com/w/cpp/container/forward_list forward_list]</code><br>([[C++11]])
! Description
|-
! rowspan=4 | Basics
| rowspan=3 {{n/a|(implicit)}}
| [http://en.cppreference.com/w/cpp/container/vector/vector (constructor)]
| [http://en.cppreference.com/w/cpp/container/deque/deque (constructor)]
| [http://en.cppreference.com/w/cpp/container/list/list (constructor)]
| [http://en.cppreference.com/w/cpp/container/forward_list/forward_list (constructor)]
| Constructs the container from variety of sources
|-
| [http://en.cppreference.com/w/cpp/container/vector/~vector (destructor)]
| [http://en.cppreference.com/w/cpp/container/deque/~deque (destructor)]
| [http://en.cppreference.com/w/cpp/container/list/~list (destructor)]
| [http://en.cppreference.com/w/cpp/container/forward_list/~forward_list (destructor)]
| Destructs the container and the contained elements
|-
| <code>[http://en.cppreference.com/w/cpp/container/vector/operator= operator=]</code>
| <code>[http://en.cppreference.com/w/cpp/container/deque/operator= operator=]</code>
| <code>[http://en.cppreference.com/w/cpp/container/list/operator= operator=]</code>
| <code>[http://en.cppreference.com/w/cpp/container/forward_list/operator= operator=]</code>
| Assigns values to the container
|-
| rowspan=2 {{n/a}}
| <code>[http://en.cppreference.com/w/cpp/container/vector/assign assign]</code>
| <code>[http://en.cppreference.com/w/cpp/container/deque/assign assign]</code>
| <code>[http://en.cppreference.com/w/cpp/container/list/assign assign]</code>
| <code>[http://en.cppreference.com/w/cpp/container/forward_list/assign assign]</code>
| Assigns values to the container
|-
! rowspan=1| Allocators
| <code>[http://en.cppreference.com/w/cpp/container/vector/get_allocator get_allocator]</code>
| <code>[http://en.cppreference.com/w/cpp/container/deque/get_allocator get_allocator]</code>
| <code>[http://en.cppreference.com/w/cpp/container/list/get_allocator get_allocator]</code>
| <code>[http://en.cppreference.com/w/cpp/container/forward_list/get_allocator get_allocator]</code>
| Returns the allocator used to allocate memory for the elements
|-
! rowspan=5 | Element<br>access
| <code>[http://en.cppreference.com/w/cpp/container/array/at at]</code>
| <code>[http://en.cppreference.com/w/cpp/container/vector/at at]</code>
| <code>[http://en.cppreference.com/w/cpp/container/deque/at at]</code>
| rowspan=2 {{n/a}} || rowspan=2 {{n/a}} || Accesses specified element with bounds checking.
|-
| <code>[http://en.cppreference.com/w/cpp/container/array/operator_at operator[]]</code>
| <code>[http://en.cppreference.com/w/cpp/container/vector/operator_at operator[]]</code>
| <code>[http://en.cppreference.com/w/cpp/container/deque/operator_at operator[]]</code>
| Accesses specified element without bounds checking.
|-
| <code>[http://en.cppreference.com/w/cpp/container/array/front front]</code>
| <code>[http://en.cppreference.com/w/cpp/container/vector/front front]</code>
| <code>[http://en.cppreference.com/w/cpp/container/deque/front front]</code>
| <code>[http://en.cppreference.com/w/cpp/container/list/front front]</code>
| <code>[http://en.cppreference.com/w/cpp/container/forward_list/front front]</code>
| Accesses the first element
|-
| <code>[http://en.cppreference.com/w/cpp/container/array/back back]</code>
| <code>[http://en.cppreference.com/w/cpp/container/vector/back back]</code>
| <code>[http://en.cppreference.com/w/cpp/container/deque/back back]</code>
| <code>[http://en.cppreference.com/w/cpp/container/list/back back]</code>
| rowspan=2 {{n/a}} || Accesses the last element
|-
| <code>[http://en.cppreference.com/w/cpp/container/array/data data]</code>
| <code>[http://en.cppreference.com/w/cpp/container/vector/data data]</code>
| {{n/a}} || {{n/a}} || Accesses the underlying array
|-
! rowspan=4 | Iterators
| <code>[http://en.cppreference.com/w/cpp/container/array/begin begin<br/>cbegin]</code>
| <code>[http://en.cppreference.com/w/cpp/container/vector/begin begin<br/>cbegin]</code>
| <code>[http://en.cppreference.com/w/cpp/container/deque/begin begin<br/>cbegin]</code>
| <code>[http://en.cppreference.com/w/cpp/container/list/begin begin<br/>cbegin]</code>
| <code>[http://en.cppreference.com/w/cpp/container/forward_list/begin begin<br/>cbegin]</code>
| Returns an iterator to the beginning of the container
|-
| <code>[http://en.cppreference.com/w/cpp/container/array/end end<br/>cend]</code>
| <code>[http://en.cppreference.com/w/cpp/container/vector/end end<br/>cend]</code>
| <code>[http://en.cppreference.com/w/cpp/container/deque/end end<br/>cend]</code>
| <code>[http://en.cppreference.com/w/cpp/container/list/end end<br/>cend]</code>
| <code>[http://en.cppreference.com/w/cpp/container/forward_list/end end<br/>cend]</code>
| Returns an iterator to the end of the container
|-
| <code>[http://en.cppreference.com/w/cpp/container/array/rbegin rbegin<br/>crbegin]</code>
| <code>[http://en.cppreference.com/w/cpp/container/vector/rbegin rbegin<br/>crbegin]</code>
| <code>[http://en.cppreference.com/w/cpp/container/deque/rbegin rbegin<br/>crbegin]</code>
| <code>[http://en.cppreference.com/w/cpp/container/list/rbegin rbegin<br/>crbegin]</code>
| rowspan=2 {{n/a}} || Returns a reverse iterator to the reverse beginning of the container
|-
| <code>[http://en.cppreference.com/w/cpp/container/array/rend rend<br/>crend]</code>
| <code>[http://en.cppreference.com/w/cpp/container/vector/rend rend<br/>crend]</code>
| <code>[http://en.cppreference.com/w/cpp/container/deque/rend rend<br/>crend]</code>
| <code>[http://en.cppreference.com/w/cpp/container/list/rend rend<br/>crend]</code>
| Returns a reverse iterator to the reverse end of the container
|-
! rowspan=6 | Capacity
| <code>[http://en.cppreference.com/w/cpp/container/array/empty empty]</code>
| <code>[http://en.cppreference.com/w/cpp/container/vector/empty empty]</code>
| <code>[http://en.cppreference.com/w/cpp/container/deque/empty empty]</code>
| <code>[http://en.cppreference.com/w/cpp/container/list/empty empty]</code>
| <code>[http://en.cppreference.com/w/cpp/container/forward_list/empty empty]</code>
| Checks whether the container is empty
|-
| <code>[http://en.cppreference.com/w/cpp/container/array/size size]</code>
| <code>[http://en.cppreference.com/w/cpp/container/vector/size size]</code>
| <code>[http://en.cppreference.com/w/cpp/container/deque/size size]</code>
| <code>[http://en.cppreference.com/w/cpp/container/list/size size]</code>
| {{n/a}} || Returns the number of elements in the container.
|-
| <code>[http://en.cppreference.com/w/cpp/container/array/max_size max_size]</code>
| <code>[http://en.cppreference.com/w/cpp/container/vector/max_size max_size]</code>
| <code>[http://en.cppreference.com/w/cpp/container/deque/max_size max_size]</code>
| <code>[http://en.cppreference.com/w/cpp/container/list/max_size max_size]</code>
| <code>[http://en.cppreference.com/w/cpp/container/forward_list/max_size max_size]</code>
| Returns the maximum possible number of elements in the container.
|-
| rowspan=17 {{n/a}}
| <code>[http://en.cppreference.com/w/cpp/container/vector/reserve reserve]</code>
| rowspan=2 {{n/a}} || rowspan=3 {{n/a}} || rowspan=3 {{n/a}} || Reserves storage in the container
|-
| <code>[http://en.cppreference.com/w/cpp/container/vector/capacity capacity]</code>
| Returns the number of elements that can be held in currently allocated storage
|-
| <code>[http://en.cppreference.com/w/cpp/container/vector/shrink_to_fit shrink_to_fit]</code>
| <code>[http://en.cppreference.com/w/cpp/container/deque/shrink_to_fit shrink_to_fit]</code>
| Reduces memory usage by freeing unused memory ([[C++11]])
|-
! rowspan=16 | Modifiers
| <code>[http://en.cppreference.com/w/cpp/container/vector/clear clear]</code>
| <code>[http://en.cppreference.com/w/cpp/container/deque/clear clear]</code>
| <code>[http://en.cppreference.com/w/cpp/container/list/clear clear]</code>
| <code>[http://en.cppreference.com/w/cpp/container/forward_list/clear clear]</code>
| Clears the contents
|-
| <code>[http://en.cppreference.com/w/cpp/container/vector/insert insert]</code>
| <code>[http://en.cppreference.com/w/cpp/container/deque/insert insert]</code>
| <code>[http://en.cppreference.com/w/cpp/container/list/insert insert]</code>
| rowspan=3 {{n/a}} || Inserts elements
|-
| <code>[http://en.cppreference.com/w/cpp/container/vector/emplace emplace]</code>
| <code>[http://en.cppreference.com/w/cpp/container/deque/emplace emplace]</code>
| <code>[http://en.cppreference.com/w/cpp/container/list/emplace emplace]</code>
| Constructs elements in-place ([[C++11]])
|-
| <code>[http://en.cppreference.com/w/cpp/container/vector/erase erase]</code>
| <code>[http://en.cppreference.com/w/cpp/container/deque/erase erase]</code>
| <code>[http://en.cppreference.com/w/cpp/container/list/erase erase]</code>
| Erases elements
|-
| rowspan=3 {{n/a}} || <code>[http://en.cppreference.com/w/cpp/container/deque/push_front push_front]</code>
| <code>[http://en.cppreference.com/w/cpp/container/list/push_front push_front]</code>
| <code>[http://en.cppreference.com/w/cpp/container/forward_list/push_front push_front]</code>
|  Inserts elements to the beginning
|-
| <code>[http://en.cppreference.com/w/cpp/container/deque/emplace_front emplace_front]</code>
| <code>[http://en.cppreference.com/w/cpp/container/list/emplace_front emplace_front]</code>
| <code>[http://en.cppreference.com/w/cpp/container/forward_list/emplace_front emplace_front]</code>
| Constructs elements in-place at the beginning ([[C++11]])
|-
| <code>[http://en.cppreference.com/w/cpp/container/deque/pop_front pop_front]</code>
| <code>[http://en.cppreference.com/w/cpp/container/list/pop_front pop_front]</code>
| <code>[http://en.cppreference.com/w/cpp/container/forward_list/pop_front pop_front]</code>
| Removes the first element
|-
| <code>[http://en.cppreference.com/w/cpp/container/vector/push_back push_back]</code>
| <code>[http://en.cppreference.com/w/cpp/container/deque/push_back push_back]</code>
| <code>[http://en.cppreference.com/w/cpp/container/list/push_back push_back]</code>
| rowspan=3 {{n/a}} || Inserts elements to the end
|-
| <code>[http://en.cppreference.com/w/cpp/container/vector/emplace_back emplace_back]</code>
| <code>[http://en.cppreference.com/w/cpp/container/deque/emplace_back emplace_back]</code>
| <code>[http://en.cppreference.com/w/cpp/container/list/emplace_back emplace_back]</code>
| Constructs elements in-place at the end ([[C++11]])
|-
| <code>[http://en.cppreference.com/w/cpp/container/vector/pop_back pop_back]</code>
| <code>[http://en.cppreference.com/w/cpp/container/deque/pop_back pop_back]</code>
| <code>[http://en.cppreference.com/w/cpp/container/list/pop_back pop_back]</code>
| Removes the last element
|-
| rowspan=3 {{n/a}} || rowspan=3 {{n/a}} || rowspan=3 {{n/a}}
| <code>[http://en.cppreference.com/w/cpp/container/forward_list/insert_after insert_after]</code>
| Inserts elements after specified position ([[C++11]])
|-
| <code>[http://en.cppreference.com/w/cpp/container/forward_list/emplace_after emplace_after]</code>
| Constructs elements in-place after specified position ([[C++11]])
|-
| <code>[http://en.cppreference.com/w/cpp/container/forward_list/erase_after erase_after]</code>
| Erases elements in-place after specified position ([[C++11]])
|-
| <code>[http://en.cppreference.com/w/cpp/container/vector/resize resize]</code>
| <code>[http://en.cppreference.com/w/cpp/container/deque/resize resize]</code>
| <code>[http://en.cppreference.com/w/cpp/container/list/resize resize]</code>
| <code>[http://en.cppreference.com/w/cpp/container/forward_list/resize resize]</code>
| Changes the number of stored elements
|-
| <code>[http://en.cppreference.com/w/cpp/container/array/swap swap]</code>
| <code>[http://en.cppreference.com/w/cpp/container/vector/swap swap]</code>
| <code>[http://en.cppreference.com/w/cpp/container/deque/swap swap]</code>
| <code>[http://en.cppreference.com/w/cpp/container/list/swap swap]</code>
| <code>[http://en.cppreference.com/w/cpp/container/forward_list/swap swap]</code>
| Swaps the contents with another container of the same type
|-
| <code>[http://en.cppreference.com/w/cpp/container/array/fill fill]</code>
| {{n/a}} || {{n/a}} || {{n/a}} || {{n/a}} || Fills the array with the given value
|}
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:
==== Operations ====
*<code>[http://en.cppreference.com/w/cpp/container/list/merge list::merge]</code> and <code>[http://en.cppreference.com/w/cpp/container/forward_list/merge forward_list::merge]</code> - Merges two sorted lists
*<code>[http://en.cppreference.com/w/cpp/container/list/splice list::splice]</code> and <code>[http://en.cppreference.com/w/cpp/container/forward_list/merge forward_list::splice_after]</code> - Moves elements from another list
*<code>[http://en.cppreference.com/w/cpp/container/list/remove list::remove]</code> and <code>[http://en.cppreference.com/w/cpp/container/forward_list/remove forward_list::remove]</code> - Removes elements equal to the given value
*<code>[http://en.cppreference.com/w/cpp/container/list/remove list::remove_if]</code> and <code>[http://en.cppreference.com/w/cpp/container/forward_list/remove forward_list::remove_if]</code> - Removes elements satisfying specific criteria
*<code>[http://en.cppreference.com/w/cpp/container/list/reverse list::reverse]</code> and <code>[http://en.cppreference.com/w/cpp/container/forward_list/reverse forward_list::reverse]</code> - Reverses the order of the elements
*<code>[http://en.cppreference.com/w/cpp/container/list/unique list::unique]</code> and <code>[http://en.cppreference.com/w/cpp/container/forward_list/unique forward_list::unique]</code> - Removes consecutive duplicate elements
*<code>[http://en.cppreference.com/w/cpp/container/list/sort list::sort]</code> and <code>[http://en.cppreference.com/w/cpp/container/forward_list/sort forward_list::sort]</code> - Sorts the elements
=== Non-member functions ===
== Usage example ==
The following example demonstrates various techniques involving a vector and [[C++ Standard Library]] algorithms, notably [[shuffle|shuffling]], [[sorting]], finding the largest element, and erasing from a vector using the [[erase-remove idiom]].
<syntaxhighlight lang="cpp">
#include <iostream>
#include <vector>
#include <array>
#include <algorithm> // sort, max_element, random_shuffle, remove_if, lower_bound
#include <functional> // greater
#include <iterator> // begin, end, cbegin, cend, distance
// used here for convenience, use judiciously in real programs.
using namespace std;
int main()
{
array arr{ 1, 2, 3, 4 };
// initialize a vector from an array
vector<int> numbers(cbegin(arr), cend(arr));
// insert more numbers into the vector
numbers.push_back(5);
numbers.push_back(6);
numbers.push_back(7);
numbers.push_back(8);
// the vector currently holds { 1, 2, 3, 4, 5, 6, 7, 8 }
// randomly shuffle the elements
shuffle(begin(numbers), end(numbers));
// locate the largest element, O(n)
auto largest = max_element(cbegin(numbers), cend(numbers));
cout << "The largest number is " << *largest << "\n";
cout << "It is located at index " << distance(largest, cbegin(numbers)) << "\n";
// sort the elements
sort(begin(numbers), end(numbers));
// find the position of the number 5 in the vector
auto five = lower_bound(cbegin(numbers), cend(numbers), 5);
cout << "The number 5 is located at index " << distance(five, cbegin(numbers)) << ‘\n’;
// erase all the elements greater than 4
numbers.erase(
remove_if(begin(numbers),
end(numbers),
[](auto n) constexpr { return n > 4; });
// print all the remaining numbers
for (const auto& element : numbers)
cout << element << " ";
}
</syntaxhighlight>
'''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>
== References ==
* William Ford, William Topp. ''Data Structures with C++ and STL'', Second Edition. Prentice Hall, 2002. {{ISBN|0-13-085850-1}}. Chapter 4: The Vector Class, pp.&nbsp;195&ndash;203.
* {{Cite book |first=Nicolai M. |last=Josuttis |title=The C++ Standard Library |year=1999 |publisher=Addison-Wesley |isbn=0-201-37926-0 |url-access=registration |url=https://archive.org/details/cstandardlibrary00josu }}
== Notes ==
{{reflist}}
[[Category:C++ Standard Library]]
[[Category:Articles with example C++ code]]