In computing, sequence containers refer to a group of
container
A container is any receptacle or enclosure for holding a product used in storage, packaging, and transportation, including shipping.
Things kept inside of a container are protected on several sides by being inside of its structure. The term ...
class templates in the
standard library of the
C++ programming language that implement storage of data elements. Being
templates
Template may refer to:
Tools
* Die (manufacturing), used to cut or shape material
* Mold, in a molding process
* Stencil, a pattern or overlay used in graphic arts (drawing, painting, etc.) and sewing to replicate letters, shapes or designs
Co ...
, 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
In computing, a namespace is a set of signs (''names'') that are used to identify and refer to objects of various kinds. A namespace ensures that all of a given set of objects have unique names so that they can be easily identified.
Namespaces ...
''std''.
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:
*
array
implements a compile-time non-resizable array.
*
vector
implements an array with fast
random access and an ability to automatically resize when appending elements.
*
deque
implements a
double-ended queue
In computer science, a double-ended queue (abbreviated to deque, pronounced ''deck'', like "cheque") is an abstract data type that generalizes a queue, for which elements can be added to or removed from either the front (head) or back (tail). ...
with comparatively fast random access.
*
list
implements a
doubly linked list
In computer science, a doubly linked list is a linked data structure that consists of a set of sequentially linked records called nodes. Each node contains three fields: two link fields (references to the previous and to the next node in the s ...
.
*
forward_list
implements a
singly linked list
In computer science, a linked list is a linear collection of data elements whose order is not given by their physical placement in memory. Instead, each element points to the next. It is a data structure consisting of a collection of nodes which ...
.
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
ISO is the most common abbreviation for the International Organization for Standardization.
ISO or Iso may also refer to: Business and finance
* Iso (supermarket), a chain of Danish supermarkets incorporated into the SuperBest chain in 2007
* Iso ...
/ IEC (2003). '' ISO/IEC 14882:2003(E): Programming Languages - C++ §23.1 Container requirements ib.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
The Standard Template Library (STL) is a software library originally designed by Alexander Stepanov for the C++ programming language that influenced many parts of the C++ Standard Library. It provides four components called ''algorithms'', '' ...
(STL), published by
SGI.
Alexander Stepanov
Alexander Alexandrovich Stepanov (russian: Алекса́ндр Алекса́ндрович Степа́нов; born November 16, 1950, Moscow) is a Russian-American computer programmer, best known as an advocate of generic programming and as th ...
, 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. It firstly appeared in
C++ TR1 and later was incorporated into
C++11
C++11 is a version of the ISO/ IEC 14882 standard for the C++ programming language. C++11 replaced the prior version of the C++ standard, called C++03, and was later replaced by C++14. The name follows the tradition of naming language versions b ...
.
The
forward_list
container was added to C++11 as a space-efficient alternative to
list
when reverse iteration is not needed.
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
iterator
In computer programming, an iterator is an object that enables a programmer to traverse a container, particularly lists. Various types of iterators are often provided via a container's interface. Though the interface and semantics of a given iterat ...
s 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.
Vector
The elements of a
vector
are stored contiguously.
ISO
ISO is the most common abbreviation for the International Organization for Standardization.
ISO or Iso may also refer to: Business and finance
* Iso (supermarket), a chain of Danish supermarkets incorporated into the SuperBest chain in 2007
* Iso ...
/ IEC (2003). '' ISO/IEC 14882:2003(E): Programming Languages - C++ §23.2.4 Class template vector ib.vector' para. 1 Like all
dynamic array implementations, vectors have low memory usage and good
locality of reference
In computer science, locality of reference, also known as the principle of locality, is the tendency of a processor to access the same set of memory locations repetitively over a short period of time. There are two basic types of reference localit ...
and
data cache
A CPU cache is a hardware cache used by the central processing unit (CPU) of a computer to reduce the average cost (time or energy) to access data from the main memory. A cache is a smaller, faster memory, located closer to a processor core, whi ...
utilization. Unlike other STL containers, such as
deque
In computer science, a double-ended queue (abbreviated to deque, pronounced ''deck'', like "cheque") is an abstract data type that generalizes a queue, for which elements can be added to or removed from either the front (head) or back (tail). ...
s 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.
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
ISO is the most common abbreviation for the International Organization for Standardization.
ISO or Iso may also refer to: Business and finance
* Iso (supermarket), a chain of Danish supermarkets incorporated into the SuperBest chain in 2007
* Iso ...
/ IEC (2003). '' ISO/IEC 14882:2003(E): Programming Languages - C++ §23.2.4.3 vector modifiers ib.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
iterator
In computer programming, an iterator is an object that enables a programmer to traverse a container, particularly lists. Various types of iterators are often provided via a container's interface. Though the interface and semantics of a given iterat ...
s to elements in the vector become invalidated.
ISO
ISO is the most common abbreviation for the International Organization for Standardization.
ISO or Iso may also refer to: Business and finance
* Iso (supermarket), a chain of Danish supermarkets incorporated into the SuperBest chain in 2007
* Iso ...
/ IEC (2003). '' ISO/IEC 14882:2003(E): Programming Languages - C++ §23.2.4.2 vector capacity ib.vector.capacity' para. 5 Using an invalidated reference causes
undefined behaviour
In computer programming, undefined behavior (UB) is the result of executing a program whose behavior is prescribed to be unpredictable, in the language specification to which the computer code adheres. This is different from unspecified behavior ...
.
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
ISO is the most common abbreviation for the International Organization for Standardization.
ISO or Iso may also refer to: Business and finance
* Iso (supermarket), a chain of Danish supermarkets incorporated into the SuperBest chain in 2007
* Iso ...
/ IEC (2003). '' ISO/IEC 14882:2003(E): Programming Languages - C++ §23.2.4.2 vector capacity ib.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
Assignment, assign or The Assignment may refer to:
* Homework
* Sex assignment
* The process of sending National Basketball Association players to its development league; see
Computing
* Assignment (computer science), a type of modification t ...
or
copy constructor. Consequently, references and iterators to elements after the insertion point become invalidated.
ISO
ISO is the most common abbreviation for the International Organization for Standardization.
ISO or Iso may also refer to: Business and finance
* Iso (supermarket), a chain of Danish supermarkets incorporated into the SuperBest chain in 2007
* Iso ...
/ IEC (2003). '' ISO/IEC 14882:2003(E): Programming Languages - C++ §23.2.4.3 vector modifiers ib.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
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.
ISO
ISO is the most common abbreviation for the International Organization for Standardization.
ISO or Iso may also refer to: Business and finance
* Iso (supermarket), a chain of Danish supermarkets incorporated into the SuperBest chain in 2007
* Iso ...
/ IEC (2003). '' ISO/IEC 14882:2003(E): Programming Languages - C++ §23.2.5 Class vector ib.vector.bool' para. 1 This is widely considered a mistake.
vector
does not meet the requirements for a
C++ Standard Library
The C standard library or libc is the standard library for the C programming language, as specified in the ISO C standard. ISO/IEC (2018). '' ISO/IEC 9899:2018(E): Programming Languages - C §7'' Starting from the original ANSI C standard, it was ...
container. For instance, a
container::reference
must be a true
lvalue of type
T
. This is not the case with
vector::reference
, which is a
proxy class convertible to
bool
.
ISO
ISO is the most common abbreviation for the International Organization for Standardization.
ISO or Iso may also refer to: Business and finance
* Iso (supermarket), a chain of Danish supermarkets incorporated into the SuperBest chain in 2007
* Iso ...
/ IEC (2003). '' ISO/IEC 14882:2003(E): Programming Languages - C++ §23.2.5 Class vector ib.vector.bool' para. 2 Similarly, the
vector::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
should be deprecated and subsequently removed from the standard library, while the functionality will be reintroduced under a different name.
List
The
list
data structure implements a
doubly linked list
In computer science, a doubly linked list is a linked data structure that consists of a set of sequentially linked records called nodes. Each node contains three fields: two link fields (references to the previous and to the next node in the s ...
. 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 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 ints) the memory overhead is much more significant than that of a vector. Each node takes up
sizeof
sizeof is a unary operator in the programming languages C and C++. It generates the storage size of an expression or a data type, measured in the number of ''char''-sized units. Consequently, the construct ''sizeof (char)'' is guaranteed to be ' ...
(type) + 2 * sizeof
sizeof is a unary operator in the programming languages C and C++. It generates the storage size of an expression or a data type, measured in the number of ''char''-sized units. Consequently, the construct ''sizeof (char)'' is guaranteed to be ' ...
(type*)
. Pointers are typically one
word
A word is a basic element of language that carries an objective or practical meaning, can be used on its own, and is uninterruptible. Despite the fact that language speakers often have an intuitive grasp of what a word is, there is no conse ...
(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
forward_list
data structure implements a
singly linked list
In computer science, a linked list is a linear collection of data elements whose order is not given by their physical placement in memory. Instead, each element points to the next. It is a data structure consisting of a collection of nodes which ...
.
Deque
deque
is a container class template that implements a
double-ended queue
In computer science, a double-ended queue (abbreviated to deque, pronounced ''deck'', like "cheque") is an abstract data type that generalizes a queue, for which elements can be added to or removed from either the front (head) or back (tail). ...
. 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
array
implements a non-resizable
array
An array is a systematic arrangement of similar objects, usually in rows and columns.
Things called an array include:
{{TOC right
Music
* In twelve-tone and serial composition, the presentation of simultaneous twelve-tone sets such that the ...
. The size is determined at compile-time by a template parameter. By design, the container does not support
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.
vector
is defined in header
. All containers satisfy the requirements of th
Containerconcept
Concepts are defined as abstract ideas. They are understood to be the fundamental building blocks of the concept behind principles, thoughts and beliefs.
They play an important role in all aspects of cognition. As such, concepts are studied by ...
, which means they have
begin()
,
end()
,
size()
,
max_size()
,
empty()
, and
swap()
methods.
Member functions
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:
Operations
*
list::merge
/code> and forward_list::merge
/code> - Merges two sorted lists
*list::splice
/code> and forward_list::splice_after
/code> - Moves elements from another list
*list::remove
/code> and forward_list::remove
/code> - Removes elements equal to the given value
*list::remove_if
/code> and forward_list::remove_if
/code> - Removes elements satisfying specific criteria
*list::reverse
/code> and forward_list::reverse
/code> - Reverses the order of the elements
*list::unique
/code> and forward_list::unique
/code> - Removes consecutive duplicate elements
*list::sort
/code> and 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
The C standard library or libc is the standard library for the C programming language, as specified in the ISO C standard. ISO/IEC (2018). '' ISO/IEC 9899:2018(E): Programming Languages - C §7'' Starting from the original ANSI C standard, it was ...
algorithms, notably shuffling
Shuffling is a procedure used to randomize a deck of playing cards to provide an element of chance in card games. Shuffling is often followed by a cut, to help ensure that the shuffler has not manipulated the outcome.
__TOC__
Techniques
Over ...
, sorting, finding the largest element, and erasing from a vector using the erase-remove idiom.
#include
#include
#include
#include // sort, max_element, random_shuffle, remove_if, lower_bound
#include // greater
#include // begin, end, cbegin, cend, distance
// used here for convenience, use judiciously in real programs.
using namespace std;
int main()
The output will be the following:
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
References
* William Ford, William Topp. ''Data Structures with C++ and STL'', Second Edition. Prentice Hall, 2002. . Chapter 4: The Vector Class, pp. 195–203.
*
Notes
{{reflist
C++ Standard Library
Articles with example C++ code