cppdraft_translate/cppdraft/container/reqmts.md

[container.reqmts]

# 23 Containers library [[containers]](./#containers)

## 23.2 Requirements [[container.requirements]](container.requirements#container.reqmts)

### 23.2.2 General containers [[container.requirements.general]](container.requirements.general#container.reqmts)

#### 23.2.2.2 Container requirements [container.reqmts]

[1](#1)

[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/containers.tex#L132)

A type X meets the [*container*](#def:container "23.2.2.2 Container requirements [container.reqmts]") requirements
if the following types, statements, and expressions are well-formed and
have the specified semantics[.](#1.sentence-1)

[🔗](#lib:value_type,containers)

`typename X::value_type
`

[2](#2)

[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/containers.tex#L143)

*Result*: T

[3](#3)

[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/containers.tex#L147)

*Preconditions*: T is *Cpp17Erasable* from X (see [[container.alloc.reqmts]](container.alloc.reqmts "23.2.2.5 Allocator-aware containers"), below)[.](#3.sentence-1)

[🔗](#lib:reference,containers)

`typename X::reference
`

[4](#4)

[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/containers.tex#L159)

*Result*: T&

[🔗](#lib:const_reference,containers)

`typename X::const_reference
`

[5](#5)

[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/containers.tex#L170)

*Result*: const T&

[🔗](#lib:iterator,containers)

`typename X::iterator
`

[6](#6)

[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/containers.tex#L181)

*Result*: A type that meets the forward iterator requirements ([[forward.iterators]](forward.iterators "24.3.5.5 Forward iterators"))
with value type T[.](#6.sentence-1)

The type X​::​iterator is convertible to X​::​const_iterator[.](#6.sentence-2)

[🔗](#lib:const_iterator,containers)

`typename X::const_iterator
`

[7](#7)

[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/containers.tex#L194)

*Result*: A type that meets the requirements of a constant iterator and
those of a forward iterator with value type T[.](#7.sentence-1)

[🔗](#lib:difference_type,containers)

`typename X::difference_type
`

[8](#8)

[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/containers.tex#L206)

*Result*: A signed integer type,
identical to the difference type ofX​::​iterator and X​::​const_iterator[.](#8.sentence-1)

[🔗](#lib:size_type,containers)

`typename X::size_type
`

[9](#9)

[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/containers.tex#L219)

*Result*: An unsigned integer type
that can represent any non-negative value of X​::​difference_type[.](#9.sentence-1)

[🔗](#itemdecl:8)

`X u;
X u = X();
`

[10](#10)

[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/containers.tex#L231)

*Postconditions*: u.empty()

[11](#11)

[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/containers.tex#L235)

*Complexity*: Constant[.](#11.sentence-1)

[🔗](#itemdecl:9)

`X u(v);
X u = v;
`

[12](#12)

[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/containers.tex#L246)

*Preconditions*: T is *Cpp17CopyInsertable* into X (see below)[.](#12.sentence-1)

[13](#13)

[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/containers.tex#L250)

*Postconditions*: u == v[.](#13.sentence-1)

[14](#14)

[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/containers.tex#L254)

*Complexity*: Linear[.](#14.sentence-1)

[🔗](#itemdecl:10)

`X u(rv);
X u = rv;
`

[15](#15)

[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/containers.tex#L265)

*Postconditions*: u is equal to the value that rv had before this construction[.](#15.sentence-1)

[16](#16)

[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/containers.tex#L269)

*Complexity*: Linear for array and inplace_vector and constant for all other standard containers[.](#16.sentence-1)

[🔗](#lib:operator=,containers)

`t = v;
`

[17](#17)

[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/containers.tex#L280)

*Result*: X&[.](#17.sentence-1)

[18](#18)

[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/containers.tex#L284)

*Postconditions*: t == v[.](#18.sentence-1)

[19](#19)

[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/containers.tex#L288)

*Complexity*: Linear[.](#19.sentence-1)

[🔗](#itemdecl:12)

`t = rv
`

[20](#20)

[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/containers.tex#L298)

*Result*: X&[.](#20.sentence-1)

[21](#21)

[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/containers.tex#L302)

*Effects*: All existing elements of t are either move assigned to or destroyed[.](#21.sentence-1)

[22](#22)

[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/containers.tex#L306)

*Postconditions*: If t and rv do not refer to the same object,t is equal to the value that rv had before this assignment[.](#22.sentence-1)

[23](#23)

[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/containers.tex#L311)

*Complexity*: Linear[.](#23.sentence-1)

[🔗](#itemdecl:13)

`a.~X()
`

[24](#24)

[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/containers.tex#L321)

*Result*: void[.](#24.sentence-1)

[25](#25)

[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/containers.tex#L325)

*Effects*: Destroys every element of a; any memory obtained is deallocated[.](#25.sentence-1)

[26](#26)

[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/containers.tex#L329)

*Complexity*: Linear[.](#26.sentence-1)

[🔗](#lib:begin,containers)

`b.begin()
`

[27](#27)

[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/containers.tex#L340)

*Result*: iterator;const_iterator for constant b[.](#27.sentence-1)

[28](#28)

[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/containers.tex#L345)

*Returns*: An iterator referring to the first element in the container[.](#28.sentence-1)

[29](#29)

[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/containers.tex#L349)

*Complexity*: Constant[.](#29.sentence-1)

[🔗](#lib:end,containers)

`b.end()
`

[30](#30)

[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/containers.tex#L360)

*Result*: iterator;const_iterator for constant b[.](#30.sentence-1)

[31](#31)

[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/containers.tex#L365)

*Returns*: An iterator which is the past-the-end value for the container[.](#31.sentence-1)

[32](#32)

[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/containers.tex#L369)

*Complexity*: Constant[.](#32.sentence-1)

[🔗](#lib:cbegin,containers)

`b.cbegin()
`

[33](#33)

[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/containers.tex#L380)

*Result*: const_iterator[.](#33.sentence-1)

[34](#34)

[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/containers.tex#L384)

*Returns*: const_cast<X const&>(b).begin()

[35](#35)

[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/containers.tex#L388)

*Complexity*: Constant[.](#35.sentence-1)

[🔗](#lib:cend,containers)

`b.cend()
`

[36](#36)

[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/containers.tex#L399)

*Result*: const_iterator[.](#36.sentence-1)

[37](#37)

[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/containers.tex#L403)

*Returns*: const_cast<X const&>(b).end()

[38](#38)

[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/containers.tex#L407)

*Complexity*: Constant[.](#38.sentence-1)

[🔗](#itemdecl:18)

`i <=> j
`

[39](#39)

[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/containers.tex#L417)

*Result*: strong_ordering[.](#39.sentence-1)

[40](#40)

[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/containers.tex#L421)

*Constraints*: X​::​iterator meets the random access iterator requirements[.](#40.sentence-1)

[41](#41)

[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/containers.tex#L425)

*Complexity*: Constant[.](#41.sentence-1)

[🔗](#lib:operator==,containers)

`c == b
`

[42](#42)

[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/containers.tex#L454)

*Preconditions*: T meets the *Cpp17EqualityComparable* requirements[.](#42.sentence-1)

[43](#43)

[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/containers.tex#L458)

*Result*: bool[.](#43.sentence-1)

[44](#44)

[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/containers.tex#L462)

*Returns*: equal(c.begin(), c.end(), b.begin(), b.end())

[*Note [1](#note-1)*:

The algorithm equal is defined in [[alg.equal]](alg.equal "26.6.13 Equal")[.](#44.sentence-2)

— *end note*]

[45](#45)

[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/containers.tex#L470)

*Complexity*: Constant if c.size() != b.size(), linear otherwise[.](#45.sentence-1)

[46](#46)

[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/containers.tex#L474)

*Remarks*: == is an equivalence relation[.](#46.sentence-1)

[🔗](#lib:operator!=,containers)

`c != b
`

[47](#47)

[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/containers.tex#L503)

*Effects*: Equivalent to !(c == b)[.](#47.sentence-1)

[🔗](#lib:swap,containers)

`t.swap(s)
`

[48](#48)

[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/containers.tex#L514)

*Result*: void[.](#48.sentence-1)

[49](#49)

[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/containers.tex#L518)

*Effects*: Exchanges the contents of t and s[.](#49.sentence-1)

[50](#50)

[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/containers.tex#L522)

*Complexity*: Linear for array and inplace_vector, and
constant for all other standard containers[.](#50.sentence-1)

[🔗](#itemdecl:22)

`swap(t, s)
`

[51](#51)

[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/containers.tex#L533)

*Effects*: Equivalent to t.swap(s)[.](#51.sentence-1)

[🔗](#lib:size,containers)

`c.size()
`

[52](#52)

[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/containers.tex#L544)

*Result*: size_type[.](#52.sentence-1)

[53](#53)

[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/containers.tex#L548)

*Returns*: distance(c.begin(), c.end()),
i.e., the number of elements in the container[.](#53.sentence-1)

[54](#54)

[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/containers.tex#L553)

*Complexity*: Constant[.](#54.sentence-1)

[55](#55)

[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/containers.tex#L557)

*Remarks*: The number of elements is defined by the rules of
constructors, inserts, and erases[.](#55.sentence-1)

[🔗](#lib:max_size,containers)

`c.max_size()
`

[56](#56)

[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/containers.tex#L569)

*Result*: size_type[.](#56.sentence-1)

[57](#57)

[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/containers.tex#L573)

*Returns*: distance(begin(), end()) for the largest possible container[.](#57.sentence-1)

[58](#58)

[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/containers.tex#L577)

*Complexity*: Constant[.](#58.sentence-1)

[🔗](#lib:empty,containers)

`c.empty()
`

[59](#59)

[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/containers.tex#L588)

*Result*: bool[.](#59.sentence-1)

[60](#60)

[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/containers.tex#L592)

*Returns*: c.begin() == c.end()

[61](#61)

[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/containers.tex#L596)

*Complexity*: Constant[.](#61.sentence-1)

[62](#62)

[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/containers.tex#L600)

*Remarks*: If the container is empty, then c.empty() is true[.](#62.sentence-1)

[63](#63)

[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/containers.tex#L605)

In the expressionsi == j
i != j
i < j
i <= j
i >= j
i > j
i <=> j
i - j where i and j denote objects of a container's iterator type, either or both may be replaced by an object of the container'sconst_iterator type referring to the same element with no change in semantics[.](#63.sentence-1)

[64](#64)

[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/containers.tex#L621)

Unless otherwise specified, all containers defined in this Clause obtain memory
using an allocator (see [[allocator.requirements]](allocator.requirements "16.4.4.6 Cpp17Allocator requirements"))[.](#64.sentence-1)

[*Note [2](#note-2)*:

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 P orpointer_traits<P>​::​template rebind<*unspecified*>,
where P is allocator_traits<allocator_type>​::​pointer[.](#64.sentence-2)

— *end note*]

Copy constructors for these container types obtain an allocator by callingallocator_traits<allocator_type>​::​select_on_container_copy_construction on the allocator belonging to the container being copied[.](#64.sentence-3)

Move constructors obtain an allocator by move construction from the allocator belonging to
the container being moved[.](#64.sentence-4)

Such move construction of the allocator shall not exit via an
exception[.](#64.sentence-5)

All other constructors for these container types take aconst allocator_type& argument[.](#64.sentence-6)

[*Note [3](#note-3)*:

If an invocation of a constructor uses the default value of an optional
allocator argument, then the allocator type must support value-initialization[.](#64.sentence-7)

— *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[.](#64.sentence-8)

The allocator may be replaced only via assignment orswap()[.](#64.sentence-9)

Allocator replacement is performed by
copy assignment, move assignment, or swapping of the allocator only if

- [(64.1)](#64.1)

allocator_traits<allocator_type>​::​propagate_on_container_copy_assignment​::​value,

- [(64.2)](#64.2)

allocator_traits<allocator_type>​::​propagate_on_container_move_assignment​::​value,
or

- [(64.3)](#64.3)

allocator_traits<allocator_type>​::​propagate_on_container_swap​::​value

is true within the implementation of the corresponding container operation[.](#64.sentence-10)

In all container types defined in this Clause, the member 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[.](#64.sentence-11)

[65](#65)

[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/containers.tex#L661)

The expression a.swap(b), for containers a and b of a standard
container type other than array and inplace_vector,
shall exchange the values of a andb without invoking any move, copy, or swap operations on the individual
container elements[.](#65.sentence-1)

Any Compare, Pred, or Hash types
belonging to a and b shall meet the *Cpp17Swappable* requirements
and shall be exchanged by calling swap as described in [[swappable.requirements]](swappable.requirements "16.4.4.3 Swappable requirements")[.](#65.sentence-2)

Ifallocator_traits<allocator_type>​::​propagate_on_container_swap​::​value istrue, thenallocator_type shall meet the *Cpp17Swappable* requirements and
the allocators of a and b shall also be exchanged
by calling swap as described in [[swappable.requirements]](swappable.requirements "16.4.4.3 Swappable requirements")[.](#65.sentence-3)

Otherwise, the allocators shall not be swapped, and the behavior is
undefined unless a.get_allocator() == b.get_allocator()[.](#65.sentence-4)

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[.](#65.sentence-5)

It is unspecified whether an iterator
with value a.end() before the swap will have value b.end() after the
swap[.](#65.sentence-6)

[66](#66)

[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/containers.tex#L683)

Unless otherwise specified (see [[associative.reqmts.except]](associative.reqmts.except "23.2.7.2 Exception safety guarantees"), [[unord.req.except]](unord.req.except "23.2.8.2 Exception safety guarantees"), [[deque.modifiers]](deque.modifiers "23.3.5.4 Modifiers"), [[inplace.vector.modifiers]](inplace.vector.modifiers "23.3.16.5 Modifiers"), and[[vector.modifiers]](vector.modifiers "23.3.13.5 Modifiers"))
all container types defined in this Clause meet
the following additional requirements:

- [(66.1)](#66.1)

  If an exception is thrown by aninsert() or emplace() function while inserting a single element, that
function has no effects[.](#66.1.sentence-1)

- [(66.2)](#66.2)

  If an exception is thrown by apush_back(),push_front(),emplace_back(), or emplace_front() function, that function has no effects[.](#66.2.sentence-1)

- [(66.3)](#66.3)

  Noerase(),clear(),pop_back() orpop_front() function throws an exception[.](#66.3.sentence-1)

- [(66.4)](#66.4)

  No copy constructor or assignment operator of a returned iterator
throws an exception[.](#66.4.sentence-1)

- [(66.5)](#66.5)

  Noswap() function throws an exception[.](#66.5.sentence-1)

- [(66.6)](#66.6)

  Noswap() function invalidates any references,
pointers, or iterators referring to the elements
of the containers being swapped[.](#66.6.sentence-1)
  [*Note [4](#note-4)*:
  The end() iterator does not refer to any element, so it can be invalidated[.](#66.6.sentence-2)
 — *end note*]

[67](#67)

[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/containers.tex#L726)

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[.](#67.sentence-1)

[68](#68)

[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/containers.tex#L733)

A [*contiguous container*](#def:container,contiguous "23.2.2.2 Container requirements [container.reqmts]") is a container
whose member types iterator and const_iterator meet the*Cpp17RandomAccessIterator* requirements ([[random.access.iterators]](random.access.iterators "24.3.5.7 Random access iterators")) and
model [contiguous_iterator](iterator.concept.contiguous#concept:contiguous_iterator "24.3.4.14 Concept contiguous_­iterator [iterator.concept.contiguous]") ([[iterator.concept.contiguous]](iterator.concept.contiguous "24.3.4.14 Concept contiguous_­iterator"))[.](#68.sentence-1)

[69](#69)

[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/containers.tex#L741)

The behavior of certain container member functions and deduction guides
depends on whether types qualify as input iterators or allocators[.](#69.sentence-1)

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[.](#69.sentence-2)

Likewise, the extent to which an implementation determines that a type cannot be
an allocator is unspecified, except that as a minimum a type A shall not qualify
as an allocator unless it meets both of the following conditions:

- [(69.1)](#69.1)

  The [*qualified-id*](expr.prim.id.qual#nt:qualified-id "7.5.5.3 Qualified names [expr.prim.id.qual]") A​::​value_type is valid and denotes a type ([[temp.deduct]](temp.deduct "13.10.3 Template argument deduction"))[.](#69.1.sentence-1)

- [(69.2)](#69.2)

  The expression declval<A&>().allocate(size_t{}) is well-formed when treated as an unevaluated operand[.](#69.2.sentence-1)