\rSec0[containers]{Containers library}

\rSec1[containers.general]{General}

This Clause describes components that \Cpp programs may use to

organize collections of information.

The following subclauses describe

container requirements,

and components for

sequence containers and

associative containers,

as summarized in

Table~\ref{tab:containers.lib.summary}.

\begin{libsumtab}{Containers library summary}{tab:containers.lib.summary}

\ref{container.requirements} & Requirements & \\ \rowsep

\ref{sequences} & Sequence containers & \tcode{<array>} \\

& & \tcode{<deque>} \\

& & \tcode{<forward_list>} \\

& & \tcode{<list>} \\

& & \tcode{<vector>} \\ \rowsep

\ref{associative} & Associative containers & \tcode{<map>} \\

& & \tcode{<set>} \\ \rowsep

\ref{unord} & Unordered associative containers & \tcode{<unordered_map>} \\

& & \tcode{<unordered_set>} \\ \rowsep

\ref{container.adaptors} & Container adaptors & \tcode{<queue>} \\

& & \tcode{<stack>} \\ \rowsep

\end{libsumtab}

\rSec1[container.requirements]{Container requirements}%

\indextext{requirements!container}

\rSec2[container.requirements.general]{General container requirements}

Containers are objects that store other objects.

They control allocation and deallocation of these objects

through constructors, destructors, insert and erase operations.

All of the complexity requirements in this Clause are stated solely

in terms of the number of operations on the contained objects.

\begin{example}

The copy constructor of type

\tcode{vector<vector<int>>}

has linear complexity,

even though the complexity of copying each contained

\tcode{vector<int>}

is itself linear.

\end{example}

For the components affected by this subclause that declare an \tcode{allocator_type},

objects stored in these components shall be constructed using the function

\tcode{allocator_traits<allocator_type>::rebind_traits<U>::\brk{}construct}

and destroyed using the function

\tcode{allocator_traits<allocator_type>::rebind_traits<U>::\brk{}destroy}~(\ref{allocator.traits.members}),

where \tcode{U} is either \tcode{allocator_type::value_type} or

an internal type used by the container.

These functions are called only for the

container's element type, not for internal types used by the container. \begin{note} This

means, for example, that a node-based container might need to construct nodes containing

aligned buffers and call \tcode{construct} to place the element into the buffer.

\end{note}

In Tables~\ref{tab:containers.container.requirements},

\ref{tab:containers.reversible.requirements}, and

\ref{tab:containers.optional.operations}

\tcode{X} denotes a container class containing objects of type

\tcode{T}, \tcode{a} and \tcode{b}

denote values of type \tcode{X}, \tcode{u}

denotes an identifier, \tcode{r} denotes

a non-const value of type \tcode{X}, and \tcode{rv}

denotes a non-const rvalue of type \tcode{X}.

\begin{libreqtab5}

{Container requirements}

{tab:containers.container.requirements}

\\ \topline

\lhdr{Expression} & \chdr{Return type} & \chdr{Operational} &

\chdr{Assertion/note} & \rhdr{Complexity} \\

& & \chdr{semantics} & \chdr{pre-/post-condition} & \\ \capsep

\lhdr{Expression} & \chdr{Return type} & \chdr{Operational} &

\chdr{Assertion/note} & \rhdr{Complexity} \\

& & \chdr{semantics} & \chdr{pre-/post-condition} & \\ \capsep

\tcode{X::value_type} &

\tcode{T} &

&

\requires\ \tcode{T} is \tcode{Erasable} from \tcode{X} (see~\ref{container.requirements.general}, below) &

compile time \\ \rowsep

\tcode{X::reference} &

\tcode{T\&} &

&

&

compile time \\ \rowsep

\tcode{X::const_reference} &

\tcode{const T\&} &

&

&

compile time \\ \rowsep

\tcode{X::iterator} &

iterator type whose value type is \tcode{T} &

&

any iterator category

that meets the forward iterator requirements.

convertible to \tcode{X::const_iterator}. &

compile time \\ \rowsep

\tcode{X::const_iterator} &

constant iterator type whose value type is \tcode{T} &

&

any iterator category

that meets the forward iterator requirements. &

compile time \\ \rowsep

\tcode{X::dif\-ference_type} &

signed integer type &

&

is identical to the difference type of \tcode{X::iterator} and \tcode{X::const_iterator} &

compile time \\ \rowsep

\tcode{X::size_type} &

unsigned integer type &

&

\tcode{size_type} can represent any non-negative value of \tcode{difference_type} &

compile time \\ \rowsep

\tcode{X u;} &

&

&

\postconditions \tcode{u.empty()} &

constant \\ \rowsep

\tcode{X()} &

&

&

\postconditions \tcode{X().empty()} &

constant \\ \rowsep

\tcode{X(a)} &

&

&

\requires \tcode{T} is \tcode{CopyInsertable}

into \tcode{X} (see below).\br \postconditions \tcode{a == X(a)}. &

linear \\ \rowsep

\tcode{X u(a);}\br

\tcode{X u = a;} &

&

&

\requires \tcode{T} is \tcode{CopyInsertable}

into \tcode{X} (see below).\br

\postconditions \tcode{u == a} &

linear \\ \rowsep

\tcode{X u(rv);}\br

\tcode{X u = rv;} &

&

&

\postconditions \tcode{u} shall be equal to the value that \tcode{rv} had before this construction

&

(Note B) \\ \rowsep

\tcode{a = rv} &

\tcode{X\&} &

All existing elements of \tcode{a} are either move assigned to or destroyed &

\tcode{a} shall be equal to the value that \tcode{rv}

had before this assignment &

linear \\ \rowsep

\tcode{(\&a)->\~X()} &

\tcode{void} &

&

the destructor is applied to every element of \tcode{a}; any memory obtained is deallocated. &

linear \\ \rowsep

\tcode{a.begin()} &

\tcode{iterator}; \tcode{const_iterator} for constant \tcode{a} &

&

&

constant \\ \rowsep

\tcode{a.end()} &

\tcode{iterator}; \tcode{const_iterator} for constant \tcode{a} &

&

&

constant \\ \rowsep

\tcode{a.cbegin()} &

\tcode{const_iterator} &

\tcode{const_cast<\brk{}X const\&\brk{}>(a)\brk{}.begin();} &

&

constant \\ \rowsep

\tcode{a.cend()} &

\tcode{const_iterator} &

\tcode{const_cast<\brk{}X const\&\brk{}>(a)\brk{}.end();} &

&

constant \\ \rowsep

\tcode{a == b} &

convertible to \tcode{bool} &

\tcode{==} is an equivalence relation.

\tcode{equal(\brk{}a.begin(), a.end(), b.begin(), b.end())} &

\requires\ \tcode{T} is \tcode{EqualityCompar\-a\-ble} &

Constant if \tcode{a.size() != b.size()},

linear otherwise \\ \rowsep

\tcode{a != b} &

convertible to \tcode{bool} &

Equivalent to \tcode{!(a == b)} &

&

linear \\ \rowsep

\tcode{a.swap(b)} &

\tcode{void} &

&

exchanges the contents of \tcode{a} and \tcode{b} &

(Note A) \\ \rowsep

\tcode{swap(a, b)} &

\tcode{void} &

\tcode{a.swap(b)} &

&

(Note A) \\ \rowsep

\tcode{r = a} &

\tcode{X\&} &

&

\postconditions \tcode{r == a}. &

linear \\ \rowsep

\tcode{a.size()} &

\tcode{size_type} &

\tcode{distance(\brk{}a.begin(), a.end())} &

&

constant \\ \rowsep

\tcode{a.max_size()} &

\tcode{size_type} &

\tcode{distance(\brk{}begin(), end())}

for the largest possible container &

&

constant \\ \rowsep

\tcode{a.empty()} &

convertible to \tcode{bool} &

\tcode{a.begin() == a.end()} &

&

constant \\

\end{libreqtab5}

Those entries marked ``(Note A)'' or ``(Note B)''

have linear complexity for \tcode{array} and have constant complexity

for all other standard containers.

\begin{note}

The algorithm \tcode{equal()} is defined in Clause~\ref{algorithms}.

\end{note}

The member function \tcode{size()} returns the number of elements in the container.

The number of elements is defined by the rules of

constructors, inserts, and erases.

\tcode{begin()}

returns an iterator referring to the first element in the container.

\tcode{end()}

returns an iterator which is the past-the-end value for the container.

If the container is empty, then

\tcode{begin() == end()}.

In the expressions

\begin{codeblock}

i == j

i != j

i < j

i <= j

i >= j

i > j

i - j

\end{codeblock}

where \tcode{i} and \tcode{j} denote objects of a container's \tcode{iterator}

type, either or both may be replaced by an object of the container's

\tcode{const_iterator} type referring to the same element with no change in semantics.

Unless otherwise specified, all containers defined in this clause obtain memory

using an allocator (see~\ref{allocator.requirements}).

\begin{note} In particular, containers and iterators do not store references

to allocated elements other than through the allocator's pointer type,

i.e., as objects of type \tcode{P} or

\tcode{pointer_traits<P>::template re\-bind<\unspec>},

where \tcode{P} is \tcode{allocator_traits<allocator_type>::pointer}. \end{note}

Copy constructors for these container types obtain an allocator by calling

\tcode{allocator_traits<allocator_type>::select_on_container_copy_construction}

on the allocator belonging to the container being copied.

Move constructors obtain an allocator by move construction from the allocator belonging to

the container being moved. Such move construction of the allocator shall not exit via an

exception.

All other constructors for these container types take a

\tcode{const allocator_type\&} argument.

\begin{note} If an invocation of a constructor uses the default value of an optional

allocator argument, then the \tcode{Allocator} type must support value-initialization.

\end{note}

A copy of this allocator is used for any memory allocation and element construction

performed, by these constructors and by all member functions,

during the lifetime of each container object

or until the allocator is replaced. The allocator may be replaced only via assignment or

\tcode{swap()}. Allocator replacement is performed by

copy assignment, move assignment, or swapping of the allocator only if

\tcode{allocator_traits<allocator_type>::propagate_on_container_copy_assignment::value},

\tcode{allocator_traits<allocator_type>::propagate_on_container_move_assignment::value},

or \tcode{alloca\-tor_traits<allocator_type>::propagate_on_container_swap::value} is \tcode{true}

within the implementation of the corresponding container operation.

In all container types defined in this Clause, the member \tcode{get_allocator()}

returns a copy of the allocator used to construct the container or, if that allocator

has been replaced, a copy of the most recent replacement.

The expression \tcode{a.swap(b)}, for containers \tcode{a} and \tcode{b} of a standard

container type other than \tcode{array}, shall exchange the values of \tcode{a} and

\tcode{b} without invoking any move, copy, or swap operations on the individual

container elements.

Lvalues of any \tcode{Compare}, \tcode{Pred}, or \tcode{Hash} types

belonging to \tcode{a} and \tcode{b} shall be swappable

and shall be exchanged by calling \tcode{swap}

as described in~\ref{swappable.requirements}. If

\tcode{allocator_traits<allocator_type>::propagate_on_container_swap::value} is

\tcode{true}, then

lvalues of type \tcode{allocator_type} shall be swappable and

the allocators of \tcode{a} and \tcode{b} shall also be exchanged

by calling \tcode{swap} as described in~\ref{swappable.requirements}.

Otherwise, the allocators shall not be swapped, and the behavior is

undefined unless \tcode{a.get_allocator() == b.get_allocator()}. Every iterator

referring to an element in one container before the swap shall refer to the same

element in the other container after the swap. It is unspecified whether an iterator

with value \tcode{a.end()} before the swap will have value \tcode{b.end()} after the

swap.

If the iterator type of a container belongs to the bidirectional or

random access iterator categories~(\ref{iterator.requirements}),

the container is called

\term{reversible}

and satisfies the additional requirements

in Table~\ref{tab:containers.reversible.requirements}.

\begin{libreqtab4a}

{Reversible container requirements}

{tab:containers.reversible.requirements}

\\ \topline

\lhdr{Expression} & \chdr{Return type} &

\chdr{Assertion/note} & \rhdr{Complexity} \\

& & \chdr{pre-/post-condition} & \\ \capsep

\lhdr{Expression} & \chdr{Return type} &

\chdr{Assertion/note} & \rhdr{Complexity} \\

& & \chdr{pre-/post-condition} & \\ \capsep

\tcode{X::reverse_iterator} &

iterator type whose value type is \tcode{T} &

\tcode{reverse_iterator<iterator>} &

compile time \\ \rowsep

\tcode{X::const_reverse_iterator} &

constant iterator type whose value type is \tcode{T} &

\tcode{reverse_iterator<const_iterator>} &

compile time \\ \rowsep

\tcode{a.rbegin()} &

\tcode{reverse_iterator; const_reverse_iterator} for constant \tcode{a} &

\tcode{reverse_iterator(end())} &

constant \\ \rowsep

\tcode{a.rend()} &

\tcode{reverse_iterator; const_reverse_iterator} for constant \tcode{a} &

\tcode{reverse_iterator(begin())} &

constant \\ \rowsep

\tcode{a.crbegin()} &

\tcode{const_reverse_iterator} &

\tcode{const_cast<X const\&>(a).rbegin()} &

constant \\ \rowsep

\tcode{a.crend()} &

\tcode{const_reverse_iterator} &

\tcode{const_cast<X const\&>(a).rend()} &

constant \\ \rowsep

\end{libreqtab4a}

Unless otherwise specified (see~\ref{associative.reqmts.except}, \ref{unord.req.except}, \ref{deque.modifiers}, and

\ref{vector.modifiers})

all container types defined in this Clause meet

the following additional requirements:

\begin{itemize}

if an exception is thrown by an

\tcode{insert()} or \tcode{emplace()}

function while inserting a single element, that

function has no effects.

if an exception is thrown by a

\tcode{push_back()},

\tcode{push_front()},

\tcode{emplace_back()}, or \tcode{emplace_front()}

function, that function has no effects.

no

\tcode{erase()},

\tcode{clear()},

\tcode{pop_back()}

or

\tcode{pop_front()}

function throws an exception.

no copy constructor or assignment operator of a returned iterator

throws an exception.

no

\tcode{swap()}

function throws an exception.

no

\tcode{swap()}

function invalidates any references,

pointers, or iterators referring to the elements

of the containers being swapped. \begin{note} The \tcode{end()} iterator does not refer to any element, so it may be invalidated. \end{note}

\end{itemize}

Unless otherwise specified (either explicitly or by defining a

function in terms of other functions), invoking a container member

function or passing a container as an argument to a library function

shall not invalidate iterators to, or change the values of, objects

within that container.

\indextext{container!contiguous}%

A \defn{contiguous container}

is a container that supports random access iterators~(\ref{random.access.iterators})

and whose member types \tcode{iterator} and \tcode{const_iterator}

are contiguous iterators~(\ref{iterator.requirements.general}).

Table~\ref{tab:containers.optional.operations} lists operations that are provided

for some types of containers but not others. Those containers for which the

listed operations are provided shall implement the semantics described in

Table~\ref{tab:containers.optional.operations} unless otherwise stated.

\begin{libreqtab5}

{Optional container operations}

{tab:containers.optional.operations}

\\ \topline

\lhdr{Expression} & \chdr{Return type} & \chdr{Operational} &

\chdr{Assertion/note} & \rhdr{Complexity} \\

& & \chdr{semantics} & \chdr{pre-/post-condition} & \\ \capsep

\lhdr{Expression} & \chdr{Return type} & \chdr{Operational} &

\chdr{Assertion/note} & \rhdr{Complexity} \\

& & \chdr{semantics} & \chdr{pre-/post-condition} & \\ \capsep

\tcode{a < b} &

convertible to \tcode{bool} &

\tcode{lexicographical_compare( a.begin(), a.end(), b.begin(), b.end())} &

\requires \tcode{<} is defined for values of \tcode{T}. \tcode{<} is a total ordering relationship. &

linear \\ \rowsep

\tcode{a > b} &

convertible to \tcode{bool} &

\tcode{b < a} &

&

linear \\ \rowsep

\tcode{a <= b} &

convertible to \tcode{bool} &

\tcode{!(a > b)} &

&

linear \\ \rowsep

\tcode{a >= b} &

convertible to \tcode{bool} &

\tcode{!(a < b)} &

&

linear \\

\end{libreqtab5}

\begin{note}

The algorithm \tcode{lexicographical_compare()} is defined in Clause~\ref{algorithms}.

\end{note}

All of the containers defined in this Clause and in~\ref{basic.string} except \tcode{array}

meet the additional requirements of an allocator-aware container, as described in

Table~\ref{tab:containers.allocatoraware}.

Given an allocator type \tcode{A}

and given a container type \tcode{X} having a \tcode{value_type} identical to \tcode{T}

and an \tcode{allocator_type} identical to \tcode{allocator_traits<A>::rebind_alloc<T>}

and given an lvalue \tcode{m} of type \tcode{A},

a pointer \tcode{p} of type \tcode{T*},

an expression \tcode{v} of type (possibly \tcode{const}) \tcode{T},

and an rvalue \tcode{rv} of type \tcode{T},

the following terms are defined. If \tcode{X}

is not allocator-aware, the terms below are defined as if \tcode{A} were

\tcode{allocator<T>} --- no allocator object needs to be created

and user specializations of \tcode{allocator<T>} are not instantiated:

\begin{itemize}

\tcode{T} is \defnx{\tcode{DefaultInsertable} into \tcode{X}}

{DefaultInsertable into X@\tcode{DefaultInsertable} into \tcode{X}}

means that the following expression is well-formed:

\begin{codeblock}

allocator_traits<A>::construct(m, p)

\end{codeblock}

An element of \tcode{X} is \defn{default-inserted} if it is initialized

by evaluation of the expression

\begin{codeblock}

allocator_traits<A>::construct(m, p)

\end{codeblock}

where \tcode{p} is the address of the uninitialized storage for the element

allocated within \tcode{X}.

\tcode{T} is \defnx{\tcode{MoveInsertable} into \tcode{X}}

{MoveInsertable into X@\tcode{MoveInsertable} into \tcode{X}}

means that the following expression

is well-formed:

\begin{codeblock}

allocator_traits<A>::construct(m, p, rv)

\end{codeblock}

and its evaluation causes the following postcondition to hold: The value

of \tcode{*p} is equivalent to the value of \tcode{rv} before the evaluation.

\begin{note} \tcode{rv} remains a valid object. Its state is unspecified \end{note}

\tcode{T} is \defnx{\tcode{CopyInsertable} into \tcode{X}}

{CopyInsertable into X@\tcode{CopyInsertable} into \tcode{X}}

means that, in addition to \tcode{T} being \tcode{MoveInsertable} into

\tcode{X}, the following expression is well-formed:

\begin{codeblock}

allocator_traits<A>::construct(m, p, v)

\end{codeblock}

and its evaluation causes the following postcondition to hold:

The value of \tcode{v} is unchanged and is equivalent to \tcode{*p}.

\tcode{T} is

\defnx{\tcode{EmplaceConstructible} into \tcode{X} from \tcode{args}}

{EmplaceConstructible into X from args@\tcode{EmplaceConstructible} into \tcode{X} from \tcode{args}},

for zero

or more arguments \tcode{args}, means that the following expression is well-formed:

\begin{codeblock}

allocator_traits<A>::construct(m, p, args)

\end{codeblock}

\tcode{T} is

\defnx{\tcode{Erasable} from \tcode{X}}

{Erasable from X@\tcode{Erasable} from \tcode{X}}

means that the following expression is well-formed:

\begin{codeblock}

allocator_traits<A>::destroy(m, p)

\end{codeblock}

\end{itemize}

\begin{note}

A container calls \tcode{allocator_traits<A>::construct(m, p, args)}

to construct an element at \tcode{p} using \tcode{args},

with \tcode{m == get_allocator()}.

The default \tcode{construct} in \tcode{allocator} will

call \tcode{::new((void*)p) T(args)},

but specialized allocators may choose a different definition.

\end{note}

In Table~\ref{tab:containers.allocatoraware}, \tcode{X} denotes an allocator-aware container class

with a \tcode{value_type} of \tcode{T} using allocator of type \tcode{A}, \tcode{u} denotes a

variable,

\tcode{a} and \tcode{b} denote non-const lvalues of type \tcode{X},

\tcode{t} denotes an lvalue or a const rvalue of type \tcode{X}, \tcode{rv} denotes a

non-const rvalue of type \tcode{X}, and \tcode{m} is a value of type \tcode{A}.

\begin{libreqtab4a}

{Allocator-aware container requirements}

{tab:containers.allocatoraware}

\\ \topline

\lhdr{Expression} & \chdr{Return type} &

\chdr{Assertion/note} & \rhdr{Complexity} \\

& & \chdr{pre-/post-condition} & \\ \capsep

\lhdr{Expression} & \chdr{Return type} &

\chdr{Assertion/note} & \rhdr{Complexity} \\

& & \chdr{pre-/post-condition} & \\ \capsep

\tcode{allocator_type} &

\tcode{A} &

\requires \tcode{allocator_type::value_type} is the same as \tcode{X::value_type}. &

compile time \\ \rowsep

\tcode{get_-} \tcode{allocator()} &

\tcode{A} &

&

constant \\ \rowsep

\tcode{X()}\br

\tcode{X u;} &

&

\requires\ \tcode{A} is \tcode{DefaultConstructible}.\br

\postconditions \tcode{u.empty()} returns \tcode{true},

\tcode{u.get_allocator() == A()} &

constant \\ \rowsep

\tcode{X(m)} &

&

\postconditions \tcode{u.empty()} returns \tcode{true}, &

constant \\

\tcode{X u(m);} &

&

\tcode{u.get_allocator() == m} &

\\ \rowsep

\tcode{X(t, m)}\br

\tcode{X u(t, m);} &

&

\requires\ \tcode{T} is \tcode{CopyInsertable} into \tcode{X}.\br

\postconditions \tcode{u == t}, \tcode{u.get_allocator() == m} &

linear \\ \rowsep

\tcode{X(rv)}\br

\tcode{X u(rv);}

&

&

\postconditions \tcode{u} shall have the same elements as \tcode{rv} had before this

construction; the value of \tcode{u.get_allocator()} shall be the same as the

value of \tcode{rv.get_allocator()} before this construction. &

constant \\ \rowsep

\tcode{X(rv, m)}\br

\tcode{X u(rv, m);} &

&

\requires\ \tcode{T} is

\tcode{MoveInsertable} into \tcode{X}.\br

\postconditions \tcode{u} shall have the same elements,

or copies of the elements, that \tcode{rv} had before

this construction, \tcode{u.get_allocator() == m} &

constant if \tcode{m ==} \tcode{rv.get_allocator()}, otherwise linear \\ \rowsep

\tcode{a = t} &

\tcode{X\&} &

\requires\ \tcode{T} is

\tcode{CopyInsertable} into \tcode{X}

and \tcode{CopyAssignable}.\br

\postconditions \tcode{a == t} &

linear \\ \rowsep

\tcode{a = rv} &

\tcode{X\&} &

\requires\ If \tcode{allocator_-}\br

\tcode{traits<allocator_type>}\br

\tcode{::propagate_on_container_-}\br

\tcode{move_assignment::value} is\br

\tcode{false}, \tcode{T} is

\tcode{MoveInsertable} into \tcode{X} and

\tcode{MoveAssignable}. All existing elements of \tcode{a}

are either move assigned to or destroyed.\br

\postconditions \tcode{a} shall be equal to the value that \tcode{rv} had before

this assignment. &

linear \\ \rowsep

\tcode{a.swap(b)} &

\tcode{void} &

exchanges the contents of \tcode{a} and \tcode{b} &

constant \\ \rowsep

\end{libreqtab4a}

The behavior of certain container member functions and deduction guides

depends on whether types qualify as input iterators or allocators.

The extent to which an implementation determines that a type cannot be an input

iterator is unspecified, except that as a minimum integral types shall not qualify

as input iterators.

Likewise, the extent to which an implementation determines that a type cannot be

an allocator is unspecified, except that as a minimum a type \tcode{A} shall not qualify

as an allocator unless it satisfies both of the following conditions:

\begin{itemize}

\item The \grammarterm{qualified-id} \tcode{A::value_type}

is valid and denotes a type~(\ref{temp.deduct}).

\item The expression \tcode{declval<A\&>().allocate(size_t\{\})}

is well-formed when treated as an unevaluated operand.

\end{itemize}

\rSec2[container.requirements.dataraces]{Container data races}

For purposes of avoiding data races~(\ref{res.on.data.races}), implementations shall

consider the following functions to be \tcode{const}: \tcode{begin}, \tcode{end},

\tcode{rbegin}, \tcode{rend}, \tcode{front}, \tcode{back}, \tcode{data}, \tcode{find},

\tcode{lower_bound}, \tcode{upper_bound}, \tcode{equal_range}, \tcode{at} and, except in

associative or unordered associative containers, \tcode{operator[]}.

Notwithstanding~\ref{res.on.data.races}, implementations are required to avoid data

races when the contents of the contained object in different elements in the same

container, excepting \tcode{vector<bool>}, are modified concurrently.

\begin{note} For a \tcode{vector<int> x} with a size greater than one, \tcode{x[1] = 5}

and \tcode{*x.begin() = 10} can be executed concurrently without a data race, but

\tcode{x[0] = 5} and \tcode{*x.begin() = 10} executed concurrently may result in a data

race.

As an exception to the general rule, for a \tcode{vector<bool> y}, \tcode{y[0] = true}

may race with \tcode{y[1] = true}.

\end{note}

\rSec2[sequence.reqmts]{Sequence containers}

A sequence container organizes a finite set of objects, all of the same type, into a strictly

linear arrangement. The library provides four basic kinds of sequence containers:

\tcode{vector}, \tcode{forward_list}, \tcode{list}, and \tcode{deque}. In addition,

\tcode{array} is provided as a sequence container which provides limited sequence operations

because it has a fixed number of elements. The library also provides container adaptors that

make it easy to construct abstract data types, such as \tcode{stack}s or \tcode{queue}s, out of

the basic sequence container kinds (or out of other kinds of sequence containers that the user

might define).

The sequence containers

offer the programmer different complexity trade-offs and should be used

accordingly.

\tcode{vector} or \tcode{array}

is the type of sequence container that should be used by default.

\tcode{list} or \tcode{forward_list}

should be used when there are frequent insertions and deletions from the

middle of the sequence.

\tcode{deque}

is the data structure of choice

when most insertions and deletions take place at the beginning or at the

end of the sequence.

In Tables~\ref{tab:containers.sequence.requirements}

and \ref{tab:containers.sequence.optional},

\tcode{X} denotes a sequence container class,

\tcode{a} denotes a value of type \tcode{X} containing elements of type \tcode{T},

\tcode{u} denotes the name of a variable being declared,

\tcode{A} denotes \tcode{X::allocator_type} if

the \grammarterm{qualified-id} \tcode{X::allocator_type} is valid and denotes a

type~(\ref{temp.deduct}) and

\tcode{allocator<T>} if it doesn't,

\tcode{i} and \tcode{j}

denote iterators satisfying input iterator requirements

and refer to elements implicitly convertible to \tcode{value_type},

\tcode{[i, j)}

denotes a valid range,

\tcode{il} designates an object of type \tcode{initializer_list<value_type>},

\tcode{n}

denotes a value of type \tcode{X::size_type},

\tcode{p} denotes a valid constant iterator to

\tcode{a}, \tcode{q}

denotes a valid dereferenceable constant iterator to

\tcode{a}, \tcode{[q1, q2)}

denotes a valid range of constant iterators in

\tcode{a}, \tcode{t}

denotes an lvalue or a const rvalue of

\tcode{X::value_type}, and \tcode{rv} denotes

a non-const rvalue of \tcode{X::value_type}.

\tcode{Args} denotes a template parameter pack;

\tcode{args} denotes a function parameter pack with the pattern \tcode{Args\&\&}.

The complexities of the expressions are sequence dependent.

\begin{libreqtab3}

{Sequence container requirements (in addition to container)}

{tab:containers.sequence.requirements}

\\ \topline

\lhdr{Expression} & \chdr{Return type} & \rhdr{Assertion/note} \\

& & \rhdr{pre-/post-condition} \\ \capsep

\lhdr{Expression} & \chdr{Return type} & \rhdr{Assertion/note} \\

& & \rhdr{pre-/post-condition} \\ \capsep

\tcode{X(n, t)}\br

\tcode{X u(n, t);} &

&

\requires\ \tcode{T} shall be

\tcode{CopyInsertable} into \tcode{X}.\br

\postconditions \tcode{distance(begin(), end()) == n}\br

Constructs a sequence container with \tcode{n} copies of \tcode{t} \\ \rowsep

\tcode{X(i, j)}\br

\tcode{X u(i, j);} &

&

\requires\ \tcode{T} shall be \tcode{EmplaceConstructible} into \tcode{X} from \tcode{*i}.

For \tcode{vector}, if the iterator does

not meet the forward iterator requirements~(\ref{forward.iterators}), \tcode{T}

shall also be

\tcode{MoveInsertable} into \tcode{X}.

Each iterator in the range \range{i}{j} shall be dereferenced exactly once.\br

\postconditions \tcode{distance(begin(), end()) ==}

\tcode{distance(i, j)}\br

Constructs a sequence container equal to the range \tcode{[i, j)} \\ \rowsep

\tcode{X(il)} &

&

Equivalent to \tcode{X(il.begin(), il.end())} \\ \rowsep

\tcode{a = il} &

\tcode{X\&} &

\requires\ \tcode{T} is

\tcode{CopyInsertable} into \tcode{X}

and \tcode{CopyAssignable}.

Assigns the range \range{il.begin()}{il.end()} into \tcode{a}. All existing

elements of \tcode{a} are either assigned to or destroyed.\br

\returns\ \tcode{*this}.

\\ \rowsep

\tcode{a.emplace(p, args)} &

\tcode{iterator} &

\requires\ \tcode{T} is \tcode{EmplaceConstructible} into \tcode{X} from \tcode{args}. For \tcode{vector} and \tcode{deque},

\tcode{T} is also

\tcode{MoveInsertable} into \tcode{X} and \tcode{MoveAssignable}.

\effects\ Inserts an object of type \tcode{T} constructed with

\tcode{std::forward<\brk{}Args\brk{}>(\brk{}args)...} before \tcode{p}. \\ \rowsep

\tcode{a.insert(p,t)} &

\tcode{iterator} &

\requires\ \tcode{T} shall be

\tcode{CopyInsertable} into \tcode{X}. For \tcode{vector} and \tcode{deque},

\tcode{T} shall also be \tcode{CopyAssignable}.\br

\effects\ Inserts a copy of \tcode{t} before \tcode{p}. \\ \rowsep

\tcode{a.insert(p,rv)} &

\tcode{iterator} &

\requires\ \tcode{T} shall be

\tcode{MoveInsertable} into \tcode{X}. For \tcode{vector} and \tcode{deque},

\tcode{T} shall also be \tcode{MoveAssignable}.\br

\effects\ Inserts a copy of \tcode{rv} before \tcode{p}. \\ \rowsep

\tcode{a.insert(p,n,t)} &

\tcode{iterator} &

\requires\ \tcode{T} shall be

\tcode{CopyInsertable} into \tcode{X}

and \tcode{CopyAssignable}.\br

Inserts \tcode{n} copies of \tcode{t} before \tcode{p}. \\ \rowsep

\tcode{a.insert(p,i,j)} &

\tcode{iterator} &

\requires\ \tcode{T} shall be \tcode{EmplaceConstructible} into \tcode{X} from \tcode{*i}.

For \tcode{vector} and \tcode{deque}, \tcode{T} shall also be

\tcode{MoveInsertable} into \tcode{X}, \tcode{MoveConstructible}, \tcode{MoveAssignable},

and swappable~(\ref{swappable.requirements}).

Each iterator in the range \range{i}{j} shall be dereferenced exactly once.\br

\requires \tcode{i} and \tcode{j} are not iterators into \tcode{a}.\br

Inserts copies of elements in \tcode{[i, j)} before \tcode{p} \\ \rowsep

\tcode{a.insert(p, il)} &

\tcode{iterator} &

\tcode{a.insert(p, il.begin(), il.end())}. \\ \rowsep

\tcode{a.erase(q)} &

\tcode{iterator} &

\requires\ For \tcode{vector} and \tcode{deque},

\tcode{T} shall be \tcode{MoveAssignable}.\br

\effects\ Erases the element pointed to by \tcode{q}. \\ \rowsep

\tcode{a.erase(q1,q2)} &

\tcode{iterator} &

\requires\ For \tcode{vector} and \tcode{deque},

\tcode{T} shall be \tcode{MoveAssignable}.\br

\effects\ Erases the elements in the range \tcode{[q1, q2)}. \\ \rowsep

\tcode{a.clear()} &

\tcode{void} &

Destroys all elements in \tcode{a}. Invalidates all references, pointers, and

iterators referring to the elements of \tcode{a} and may invalidate the past-the-end iterator.\br

\postconditions \tcode{a.empty()} returns \tcode{true}.\br

\complexity Linear. \\ \rowsep

\tcode{a.assign(i,j)} &

\tcode{void} &

\requires\ \tcode{T} shall be \tcode{EmplaceConstructible} into \tcode{X} from \tcode{*i}

and assignable from \tcode{*i}. For \tcode{vector}, if the iterator does not

meet the forward iterator requirements~(\ref{forward.iterators}), \tcode{T}

shall also be

\tcode{MoveInsertable} into \tcode{X}.\br

Each iterator in the range \range{i}{j} shall be dereferenced exactly once.\br

\requires \tcode{i}, \tcode{j} are not iterators into \tcode{a}.\br

Replaces elements in \tcode{a} with a copy of \tcode{[i, j)}.\br

Invalidates all references, pointers and iterators

referring to the elements of \tcode{a}.

For \tcode{vector} and \tcode{deque},

also invalidates the past-the-end iterator. \\ \rowsep

\tcode{a.assign(il)} &

\tcode{void} &

\tcode{a.assign(il.begin(), il.end())}. \\ \rowsep

\tcode{a.assign(n,t)} &

\tcode{void} &

\requires\ \tcode{T} shall be

\tcode{CopyInsertable} into \tcode{X}

and \tcode{CopyAssignable}.\br

\requires \tcode{t} is not a reference into \tcode{a}.\br

Replaces elements in \tcode{a} with \tcode{n} copies of \tcode{t}.\br

Invalidates all references, pointers and iterators

referring to the elements of \tcode{a}.

For \tcode{vector} and \tcode{deque},

also invalidates the past-the-end iterator. \\

\end{libreqtab3}

The iterator returned from

\tcode{a.insert(p, t)}

points to the copy of

\tcode{t}

inserted into

\tcode{a}.

The iterator returned from \tcode{a.insert(p, rv)} points to the copy of \tcode{rv}

inserted into \tcode{a}.

The iterator returned from \tcode{a.insert(p, n, t)} points to the copy of the first

element inserted into \tcode{a}, or \tcode{p} if \tcode{n == 0}.

The iterator returned from \tcode{a.insert(p, i, j)} points to the copy of the first

element inserted into \tcode{a}, or \tcode{p} if \tcode{i == j}.

The iterator returned from \tcode{a.insert(p, il)} points to the copy of the first

element inserted into \tcode{a}, or \tcode{p} if \tcode{il} is empty.

The iterator returned from \tcode{a.emplace(p, args)} points to the new element

constructed from \tcode{args} into \tcode{a}.

The iterator returned from

\tcode{a.erase(q)}

points to the element immediately following

\tcode{q}

prior to the element being erased.

If no such element exists,

\tcode{a.end()}

is returned.

The iterator returned by

\tcode{a.erase(q1, q2)}

points to the element pointed to by

\tcode{q2}

prior to any elements being erased.

If no such element exists,

\tcode{a.end()}

is returned.

For every sequence container defined in this Clause and in Clause~\ref{strings}:

\begin{itemize}

\item If the constructor

\begin{codeblock}

template <class InputIterator>

X(InputIterator first, InputIterator last,

const allocator_type& alloc = allocator_type());

\end{codeblock}