%!TEX root = std.tex

\rSec0[containers]{Containers library}

\rSec1[containers.general]{General}

\pnum

This Clause describes components that \Cpp programs may use to

organize collections of information.

\pnum

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}

\pnum

Containers are objects that store other objects.

They control allocation and deallocation of these objects

through constructors, destructors, insert and erase operations.

\pnum

All of the complexity requirements in this Clause are stated solely

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

\enterexample

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.

\exitexample

\pnum

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

stored in these components shall be constructed using

the \tcode{allocator_traits<allocator_type>::construct} function and destroyed using the

\tcode{allocator_traits<allocator_type>::destroy}

function~(\ref{allocator.traits.members}). These functions are called only for the

container's element type, not for internal types used by the container. \enternote 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.

\exitnote

\pnum

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

\endfirsthead

\continuedcaption\\

\topline

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

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

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

\endhead

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

&

&

post: \tcode{u.empty()} &

constant \\ \rowsep

\tcode{X()} &

&

&

post: \tcode{X().empty()} &

constant \\ \rowsep

\tcode{X(a)} &

&

&

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

into \tcode{X} (see below).\br post: \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

post: \tcode{u == a} &

linear \\ \rowsep

\tcode{X u(rv)}\br

\tcode{X u = rv} &

&

&

post: \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<X const\&>(a).begin();} &

&

constant \\ \rowsep

\tcode{a.cend()} &

\tcode{const_iterator} &

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

&

constant \\ \rowsep

\tcode{a == b} &

convertible to \tcode{bool} &

\tcode{==} is an equivalence relation.

\tcode{equal(a.begin(),}

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

\tcode{b.end())} &

\requires\ \tcode{T} is \tcode{EqualityComparable} &

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

&

post: \tcode{r == a}. &

linear \\ \rowsep

\tcode{a.size()} &

\tcode{size_type} &

\tcode{distance(a.begin(),}

\tcode{a.end())} &

&

constant \\ \rowsep

\tcode{a.max_size()} &

\tcode{size_type} &

\tcode{distance(begin(),}

\tcode{end())}

for the largest possible container &

&

constant \\ \rowsep

\tcode{a.empty()} &

convertible to \tcode{bool} &

\tcode{a.begin() ==}

\tcode{a.end()} &

&

constant \\

\end{libreqtab5}

Notes: the algorithm

\tcode{equal()}

is defined in Clause~\ref{algorithms}.

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

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

for all other standard containers.

\pnum

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.

\pnum

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

\pnum

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.

\pnum

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

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

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.

\enternote If an invocation of a constructor uses the default value of an optional

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

\exitnote

A copy of this allocator is used for any memory allocation 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 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.

\pnum

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.

\pnum

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

\endfirsthead

\continuedcaption\\

\hline

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

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

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

\endhead

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

\pnum

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}

\item

if an exception is thrown by an

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

function while inserting a single element, that

function has no effects.

\item

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.

\item

no

\tcode{erase()},

\tcode{clear()},

\tcode{pop_back()}

or

\tcode{pop_front()}

function throws an exception.

\item

no copy constructor or assignment operator of a returned iterator

throws an exception.

\item

no

\tcode{swap()}

function throws an exception.

\item

no

\tcode{swap()}

function invalidates any references,

pointers, or iterators referring to the elements

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

\end{itemize}

\pnum

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.

\pnum

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

\pnum

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

\endfirsthead

\continuedcaption\\

\topline

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

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

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

\endhead

\tcode{a < b} &

convertible to \tcode{bool} &

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

pre: \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}

Note: the algorithm

\tcode{lexicographical_compare()}

is defined in Clause~\ref{algorithms}.

\pnum

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 a container type \tcode{X} having an \tcode{allocator_type}

identical to \tcode{A} and a

\tcode{value_type} identical to \tcode{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 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{std::allocator<T>} --- no allocator object needs to be created

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

\begin{itemize}

\item

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

\item

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

\item

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

\enternote rv remains a valid object. Its state is unspecified \exitnote

\item

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

\item

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

\item

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

\enternote

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

at \tcode{p} using \tcode{args}. The default \tcode{construct} in \tcode{std::allocator} will

call \tcode{::new((void*)p) T(args)}, but specialized allocators may choose a different

definition.

\exitnote

\pnum

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

\endfirsthead

\continuedcaption\\

\hline

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

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

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

\endhead

\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

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

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

constant \\ \rowsep

\tcode{X(m)} &

&

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

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

linear \\ \rowsep

\tcode{X(rv)}\br

\tcode{X u(rv)}

&

&

\requires move construction of \tcode{A} shall not exit via an exception.\br

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

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

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

post: \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}

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

\pnum

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[]}.

\pnum

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.

\pnum

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

\exitnote

\rSec2[sequence.reqmts]{Sequence containers}

\pnum

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

\pnum

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.

\pnum

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{std::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 const iterator to

\tcode{a}, \tcode{q}

denotes a valid dereferenceable const iterator to

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

denotes a valid range of const 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\&\&}.

\pnum

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

\endfirsthead

\continuedcaption\\

\hline

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

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

\endhead

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

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

&

\requires\ \tcode{T} shall be

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

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

post: \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},

T is also

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

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

\tcode{std::forward<Args>(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

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

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

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

Replaces elements in \tcode{a} with a copy of \tcode{[i, j)}. \\ \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

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

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

\end{libreqtab3}

\pnum

\tcode{iterator}

and

\tcode{const_iterator}

types for sequence containers shall be at least of the forward iterator category.

\pnum

The iterator returned from

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

points to the copy of

\tcode{t}

inserted into

\tcode{a}.

\pnum

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

inserted into \tcode{a}.

\pnum

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

\pnum

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

\pnum

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.

\pnum

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

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

\pnum

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.

\pnum

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.

\pnum

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}

is called with a type \tcode{InputIterator} that does not qualify as an input

iterator, then the constructor

shall not participate in overload resolution.

\item If the member functions of the forms:

\begin{codeblock}

template <class InputIterator> // such as insert()

rt fx1(const_iterator p, InputIterator first, InputIterator last);

template <class InputIterator> // such as append(), assign()

rt fx2(InputIterator first, InputIterator last);

template <class InputIterator> // such as replace()

rt fx3(const_iterator i1, const_iterator i2, InputIterator first, InputIterator last);

\end{codeblock}

are called with a type \tcode{InputIterator} that does not qualify as an input

iterator, then these functions

shall not participate in overload resolution.

\end{itemize}