\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

\tref{containers.summary}.

\begin{libsumtab}{Containers library summary}{containers.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

\ref{views} & Views & \tcode{<span>} \\

\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}\iref{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 would need to construct nodes containing

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

\end{note}

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

\ref{tab:container.rev.req}, and

\ref{tab:container.opt},

\begin{itemize}

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

\tcode{a} and \tcode{b} denote values of type \tcode{X},

\tcode{i} and \tcode{j} denote values of type (possibly const) \tcode{X::iterator},

\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}.

\end{itemize}

\begin{libreqtab5}

{Container requirements}

{container.req}

\\ \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} &

&

\expects \tcode{T} is \oldconcept{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;} &

&

&

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

constant \\ \rowsep

\tcode{X()} &

&

&

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

constant \\ \rowsep

\tcode{X(a)} &

&

&

\expects \tcode{T} is \oldconcept{CopyInsertable}

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

linear \\ \rowsep

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

\tcode{X u = a;} &

&

&

\expects \tcode{T} is \oldconcept{CopyInsertable}

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

\ensures \tcode{u == a} &

linear \\ \rowsep

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

\tcode{X u = rv;} &

&

&

\ensures \tcode{u} is 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 &

\ensures If \tcode{a} and \tcode{rv} do not refer to the same object,

\tcode{a} is equal to the value that \tcode{rv}

had before this assignment. &

linear \\ \rowsep

\tcode{a.\~X()} &

\tcode{void} &

&

\effects destroys 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{i <=> j} &

\tcode{strong_ordering} &

&

\constraints \tcode{X::iterator} meets the random access iterator requirements. &

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())} &

\expects \tcode{T} meets the \oldconcept{\-Equal\-ity\-Compar\-a\-ble} requirements &

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} &

&

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

(Note A) \\ \rowsep

\tcode{swap(a, b)} &

\tcode{void} &

Equivalent to \tcode{a.swap(b)} &

&

(Note A) \\ \rowsep

\tcode{r = a} &

\tcode{X\&} &

&

\ensures \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 \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

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 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

\begin{itemize}

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

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

or

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

\end{itemize}

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.

\indextext{reversible container|see{container, reversible}}%

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

random access iterator categories\iref{iterator.requirements},

the container is called

\defnx{reversible}{container!reversible}

and meets the additional requirements

in \tref{container.rev.req}.

\begin{libreqtab4a}

{Reversible container requirements}

{container.rev.req}

\\ \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 \\

\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 can 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.

A \defnadj{contiguous}{container}

is a container

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

meet the

\oldconcept{RandomAccessIterator} requirements\iref{random.access.iterators} and

model \libconcept{contiguous_iterator}\iref{iterator.concept.contiguous}.

\tref{container.opt} 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

\tref{container.opt} unless otherwise stated.

If the iterators passed to \tcode{lexicographical_compare_three_way}

meet the constexpr iterator requirements\iref{iterator.requirements.general}

then the operations described in \tref{container.opt}

are implemented by constexpr functions.

\begin{libreqtab5}

{Optional container operations}

{container.opt}

\\ \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} &

\tcode{\placeholdernc{synth-three-\brk{}way-result}\brk{}<value_type>} &

\tcode{lexicographical_compare_three_way(a.begin(), a.end(),

b.begin(), b.end(), \placeholdernc{synth-three-way})} &

\expects

Either \tcode{<=>} is defined for values of type (possibly const) \tcode{T},

or \tcode{<} is defined for values of type (possibly const) \tcode{T} and

\tcode{<} is a total ordering relationship. &

linear \\

\end{libreqtab5}

\begin{note}

The algorithm \tcode{lexicographical_compare_three_way}

is defined in \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

\tref{container.alloc.req}.

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{\oldconcept{DefaultInsertable} into \tcode{X}}

{\oldconceptname{DefaultInsertable} into X@\oldconcept{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{\oldconcept{MoveInsertable} into \tcode{X}}

{\oldconceptname{MoveInsertable} into X@\oldconcept{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{\oldconcept{CopyInsertable} into \tcode{X}}

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

means that, in addition to \tcode{T} being \oldconcept{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{\oldconcept{EmplaceConstructible} into \tcode{X} from \tcode{args}}

{\oldconceptname{EmplaceConstructible} into X from args@\oldconcept{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{\oldconcept{Erasable} from \tcode{X}}

{\oldconceptname{Erasable} from X@\oldconcept{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 can choose a different definition.

\end{note}

In \tref{container.alloc.req},

\begin{itemize}

\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}.

\end{itemize}

\begin{libreqtab4a}

{Allocator-aware container requirements}

{container.alloc.req}

\\ \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} &

\mandates \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;} &

&

\expects \tcode{A} meets the \oldconcept{DefaultConstructible} requirements.\br

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

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

constant \\ \rowsep

\tcode{X(m)} &

&

\ensures

\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);} &

&

\expects

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

\ensures

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

linear \\ \rowsep

\tcode{X(rv)}\br

\tcode{X u(rv);}

&

&

\ensures \tcode{u} has the same elements as \tcode{rv} had before this

construction; the value of \tcode{u.get_allocator()} is 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);} &

&

\expects \tcode{T} is

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

\ensures \tcode{u} has 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\&} &

\expects \tcode{T} is

\oldconcept{CopyInsertable} into \tcode{X}

and \oldconcept{CopyAssignable}.\br

\ensures \tcode{a == t} &

linear \\ \rowsep

\tcode{a = rv} &

\tcode{X\&} &

\expects 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

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

\oldconcept{MoveAssignable}.\br

\effects All existing elements of \tcode{a}

are either move assigned to or destroyed.\br

\ensures If \tcode{a} and \tcode{rv} do not refer to the same object,

\tcode{a} is equal to the value that \tcode{rv} had before

this assignment. &

linear \\ \rowsep

\tcode{a.swap(b)} &

\tcode{void} &

\effects 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 meets both of the following conditions:

\begin{itemize}

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

is valid and denotes a type\iref{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\iref{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 can result in a data

race.

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

can 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 defines).

\begin{note}

The sequence containers

offer the programmer different complexity trade-offs.

\tcode{vector}

is appropriate in most circumstances.

\tcode{array}

has a fixed size known during translation.

\tcode{list} or \tcode{forward_list}

support frequent insertions and deletions from the

middle of the sequence.

\tcode{deque}

supports efficient insertions and deletions taking place at the beginning or at the

end of the sequence.

When choosing a container, remember \tcode{vector} is best;

leave a comment to explain if you choose from the rest!

\end{note}

In Tables~\ref{tab:container.seq.req}

and \ref{tab:container.seq.opt},

\begin{itemize}

\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\iref{temp.deduct} and

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

\tcode{i} and \tcode{j}

denote iterators that meet the \oldconcept{InputIterator} 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\&\&}.

\end{itemize}

The complexities of the expressions are sequence dependent.

\begin{libreqtab3}

{Sequence container requirements (in addition to container)}

{container.seq.req}

\\ \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);} &

&

\expects \tcode{T} is

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

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

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

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

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

&

\expects \tcode{T} is \oldconcept{EmplaceConstructible} into \tcode{X} from \tcode{*i}.

For \tcode{vector}, if the iterator does

not meet the \oldconcept{\-Forward\-Iterator} requirements\iref{forward.iterators}, \tcode{T}

is also

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

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

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

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

Each iterator in the range \range{i}{j} is dereferenced exactly once. \\ \rowsep

\tcode{X(il)} &

&

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

\tcode{a = il} &

\tcode{X\&} &

\expects \tcode{T} is

\oldconcept{CopyInsertable} into \tcode{X}

and \oldconcept{CopyAssignable}.\br

\effects 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} &

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

\tcode{T} is also

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

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

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

\begin{tailnote}

\tcode{args} can directly or indirectly refer to

a value in \tcode{a}.

\end{tailnote}

\\ \rowsep

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

\tcode{iterator} &

\expects \tcode{T} is

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

\tcode{T} is also \oldconcept{CopyAssignable}.\br

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

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

\tcode{iterator} &

\expects \tcode{T} is

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

\tcode{T} is also \oldconcept{MoveAssignable}.\br

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

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

\tcode{iterator} &

\expects \tcode{T} is

\oldconcept{CopyInsertable} into \tcode{X}

and \oldconcept{CopyAssignable}.\br

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

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

\tcode{iterator} &

\expects \tcode{T} is \oldconcept{EmplaceConstructible} into \tcode{X} from \tcode{*i}.

For \tcode{vector} and \tcode{deque}, \tcode{T} is also

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

and swappable\iref{swappable.requirements}.

Neither \tcode{i} nor \tcode{j} are iterators into \tcode{a}.\br

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

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

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

\tcode{iterator} &

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

\tcode{a.erase(q)} &

\tcode{iterator} &

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

\tcode{T} is \oldconcept{MoveAssignable}.\br

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

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

\tcode{iterator} &

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

\tcode{T} is \oldconcept{MoveAssignable}.\br

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

\tcode{a.clear()} &

\tcode{void} &

\effects 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

\ensures \tcode{a.empty()} is \tcode{true}.\br

\complexity Linear. \\ \rowsep

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

\tcode{void} &

\expects \tcode{T} is \oldconcept{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\iref{forward.iterators}, \tcode{T}

is also

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

Neither \tcode{i} nor \tcode{j} are iterators into \tcode{a}.\br

\effects

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

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.

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

\tcode{a.assign(il)} &

\tcode{void} &

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

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

\tcode{void} &

\expects \tcode{T} is

\oldconcept{CopyInsertable} into \tcode{X}

and \oldconcept{CopyAssignable}.

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

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

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. \\