Working Draft, Standard for Programming Language C++ (N4713, 2017 year) - page 27

 

  Главная      Manuals     Working Draft, Standard for Programming Language C++ (N4713, 2017 year)

 

Search            copyright infringement  

 

 

 

 

 

 

 

 

  

 

 

Content      ..     25      26      27      28     ..

 

 

 

Working Draft, Standard for Programming Language C++ (N4713, 2017 year) - page 27

 

 

and k2 in the same container, calling pred(k1, k2) shall always return the same value. For any key k in a
container, calling hash(k) shall always return the same value.
6
An unordered associative container supports unique keys if it may contain at most one element for each
key. Otherwise, it supports equivalent keys. unordered_set and unordered_map support unique keys.
unordered_multiset and unordered_multimap support equivalent keys. In containers that support equiva-
lent keys, elements with equivalent keys are adjacent to each other in the iteration order of the container.
Thus, although the absolute order of elements in an unordered container is not specified, its elements are
grouped into equivalent-key groups such that all elements of each group have equivalent keys. Mutating
operations on unordered containers shall preserve the relative order of elements within each equivalent-key
group unless otherwise specified.
7
For unordered_set and unordered_multiset the value type is the same as the key type. For unordered_map
and unordered_multimap it is pair<const Key, T>.
8
For unordered containers where the value type is the same as the key type, both iterator and const_-
iterator are constant iterators. It is unspecified whether or not iterator and const_iterator are the same
type. [ Note: iterator and const_iterator have identical semantics in this case, and iterator is convertible
to const_iterator. Users can avoid violating the one-definition rule by always using const_iterator in
their function parameter lists.
— end note ]
9
The elements of an unordered associative container are organized into buckets. Keys with the same hash
code appear in the same bucket. The number of buckets is automatically increased as elements are added
to an unordered associative container, so that the average number of elements per bucket is kept below
a bound. Rehashing invalidates iterators, changes ordering between elements, and changes which buckets
elements appear in, but does not invalidate pointers or references to elements. For unordered_multiset and
unordered_multimap, rehashing preserves the relative ordering of equivalent elements.
10
The unordered associative containers meet all the requirements of Allocator-aware containers (26.2.1), except
that for unordered_map and unordered_multimap, the requirements placed on value_type in Table 83 apply
instead to key_type and mapped_type. [Note: For example, key_type and mapped_type are sometimes
required to be CopyAssignable even though the associated value_type, pair<const key_type, mapped_-
type>, is not CopyAssignable.
— end note ]
11
In Table 91: X denotes an unordered associative container class, a denotes a value of type X, a2 denotes
a value of a type with nodes compatible with type X (Table 89), b denotes a possibly const value of type
X, a_uniq denotes a value of type X when X supports unique keys, a_eq denotes a value of type X when X
supports equivalent keys, i and j denote input iterators that refer to value_type, [i, j) denotes a valid
range, p and q2 denote valid constant iterators to a, q and q1 denote valid dereferenceable constant iterators
to a, r denotes a valid dereferenceable iterator to a, [q1, q2) denotes a valid range in a, il denotes a
value of type initializer_list<value_type>, t denotes a value of type X::value_type, k denotes a value
of type key_type, hf denotes a possibly const value of type hasher, eq denotes a possibly const value of
type key_equal, n denotes a value of type size_type, z denotes a value of type float, and nh denotes a
non-const rvalue of type X::node_type.
Table 91 — Unordered associative container requirements (in addi-
tion to container)
Expression
Return type
Assertion/note
Complexity
pre-/post-condition
X::key_type
Key
compile time
X::mapped_type
T
compile time
(unordered_map and
unordered_multimap
only)
X::value_type
Key
Requires: value_type is
compile time
(unordered_set and
Erasable from X
unordered_multiset
only)
§ 26.2.7
772
Table 91 — Unordered associative container requirements (in addi-
tion to container) (continued)
Expression
Return type
Assertion/note
Complexity
pre-/post-condition
X::value_type
pair<const Key, T>
Requires: value_type is
compile time
(unordered_map and
Erasable from X
unordered_multimap
only)
X::hasher
Hash
Hash shall be a unary function
compile time
object type such that the
expression hf(k) has type
size_t.
X::key_equal
Pred
Requires: Pred is
compile time
CopyConstructible.
Pred shall be a binary predicate
that takes two arguments of
type Key. Pred is an equivalence
relation.
X::local_iterator
An iterator type whose
A local_iterator object may
compile time
category, value type,
be used to iterate through a
difference type, and
single bucket, but may not be
pointer and reference
used to iterate across buckets.
types are the same as
X::iterator’s.
X::const_local_-
An iterator type whose
A const_local_iterator
compile time
iterator
category, value type,
object may be used to iterate
difference type, and
through a single bucket, but
pointer and reference
may not be used to iterate
types are the same as
across buckets.
X::const_iterator’s.
X::node_type
a specialization of a
see 26.2.4
compile time
node_handle class
template, such that the
public nested types are
the same types as the
corresponding types in
X.
X(n, hf, eq)
X
Effects: Constructs an empty
O(n)
X a(n, hf, eq);
container with at least n
buckets, using hf as the hash
function and eq as the key
equality predicate.
X(n, hf)
X
Requires: key_equal is
O(n)
X a(n, hf);
DefaultConstructible.
Effects: Constructs an empty
container with at least n
buckets, using hf as the hash
function and key_equal() as
the key equality predicate.
X(n)
X
Requires: hasher and
O(n)
X a(n);
key_equal are
DefaultConstructible.
Effects: Constructs an empty
container with at least n
buckets, using hasher() as the
hash function and key_equal()
as the key equality predicate.
§ 26.2.7
773
Table 91 — Unordered associative container requirements (in addi-
tion to container) (continued)
Expression
Return type
Assertion/note
Complexity
pre-/post-condition
X()
X
Requires: hasher and
constant
X a;
key_equal are
DefaultConstructible.
Effects: Constructs an empty
container with an unspecified
number of buckets, using
hasher() as the hash function
and key_equal() as the key
equality predicate.
X(i, j, n, hf, eq)
X
Requires: value_type is
Average case
X a(i, j, n, hf,
EmplaceConstructible into X
O(N ) (N is
eq);
from *i.
distance(i,
Effects: Constructs an empty
j)), worst case
container with at least n
O(N2)
buckets, using hf as the hash
function and eq as the key
equality predicate, and inserts
elements from [i, j) into it.
X(i, j, n, hf)
X
Requires: key_equal is
Average case
X a(i, j, n, hf);
DefaultConstructible.
O(N ) (N is
value_type is
distance(i,
EmplaceConstructible into X
j)), worst case
from *i.
O(N2)
Effects: Constructs an empty
container with at least n buckets,
using hf as the hash function
and key_equal() as the key
equality predicate, and inserts
elements from [i, j) into it.
X(i, j, n)
X
Requires: hasher and
Average case
X a(i, j, n);
key_equal are
O(N ) (N is
DefaultConstructible.
distance(i,
value_type is
j)), worst case
EmplaceConstructible into X
O(N2)
from *i.
Effects: Constructs an empty
container with at least n
buckets, using hasher() as the
hash function and key_equal()
as the key equality predicate,
and inserts elements from [i,
j) into it.
§ 26.2.7
774
Table 91 — Unordered associative container requirements (in addi-
tion to container) (continued)
Expression
Return type
Assertion/note
Complexity
pre-/post-condition
X(i, j)
X
Requires: hasher and
Average case
X a(i, j);
key_equal are
O(N ) (N is
DefaultConstructible.
distance(i,
value_type is
j)), worst case
EmplaceConstructible into X
O(N2)
from *i.
Effects: Constructs an empty
container with an unspecified
number of buckets, using
hasher() as the hash function
and key_equal() as the key
equality predicate, and inserts
elements from [i, j) into it.
X(il)
X
Same as X(il.begin(),
Same as
il.end()).
X(il.begin(),
il.end()).
X(il, n)
X
Same as X(il.begin(),
Same as
il.end(), n).
X(il.begin(),
il.end(), n).
X(il, n,
hf)
X
Same as X(il.begin(),
Same as
il.end(), n, hf).
X(il.begin(),
il.end(), n,
hf).
X(il, n,
hf,
eq)
X
Same as X(il.begin(),
Same as
il.end(), n, hf, eq).
X(il.begin(),
il.end(), n,
hf, eq).
X(b)
X
Copy constructor. In addition to
Average case
X a(b);
the requirements of Table 83,
linear in
copies the hash function,
b.size(),
predicate, and maximum load
worst case
factor.
quadratic.
a = b
X&
Copy assignment operator. In
Average case
addition to the requirements of
linear in
Table 83, copies the hash
b.size(),
function, predicate, and
worst case
maximum load factor.
quadratic.
a = il
X&
Requires: value_type is
Same as a =
CopyInsertable into X and
X(il).
CopyAssignable.
Effects: Assigns the range
[il.begin(), il.end()) into
a. All existing elements of a are
either assigned to or destroyed.
b.hash_function()
hasher
Returns b’s hash function.
constant
b.key_eq()
key_equal
Returns b’s key equality
constant
predicate.
§ 26.2.7
775
Table 91 — Unordered associative container requirements (in addi-
tion to container) (continued)
Expression
Return type
Assertion/note
Complexity
pre-/post-condition
a_uniq.
pair<iterator, bool>
Requires: value_type shall be
Average case
emplace(args)
EmplaceConstructible into X
O(1), worst
from args.
case O(a_uniq.
Effects: Inserts a value_type
size()).
object t constructed with
std::forward<Args>(args)...
if and only if there is no element
in the container with key
equivalent to the key of t. The
bool component of the returned
pair is true if and only if the
insertion takes place, and the
iterator component of the pair
points to the element with key
equivalent to the key of t.
a_eq.emplace(args)
iterator
Requires: value_type shall be
Average case
EmplaceConstructible into X
O(1), worst
from args.
case O(a_eq.
Effects: Inserts a value_type
size()).
object t constructed with
std::forward<Args>(args)...
and returns the iterator pointing
to the newly inserted element.
a.emplace_hint(p,
iterator
Requires: value_type shall be
Average case
args)
EmplaceConstructible into X
O(1), worst case
from args.
O(a.size()).
Effects: Equivalent to
a.emplace( std::forward<
Args>(args)...). Return value
is an iterator pointing to the
element with the key equivalent
to the newly inserted element.
The const_iterator p is a hint
pointing to where the search
should start. Implementations
are permitted to ignore the hint.
a_uniq.insert(t)
pair<iterator,
Requires: If t is a non-const
Average case
bool>
rvalue expression, value_type
O(1), worst
shall be MoveInsertable into X;
case O(a_uniq.
otherwise, value_type shall be
size()).
CopyInsertable into X.
Effects: Inserts t if and only if
there is no element in the
container with key equivalent to
the key of t. The bool
component of the returned pair
indicates whether the insertion
takes place, and the iterator
component points to the element
with key equivalent to the key of
t.
§ 26.2.7
776
Table 91 — Unordered associative container requirements (in addi-
tion to container) (continued)
Expression
Return type
Assertion/note
Complexity
pre-/post-condition
a_eq.insert(t)
iterator
Requires: If t is a non-const
Average case
rvalue expression, value_type
O(1), worst
shall be MoveInsertable into X;
case O(a_eq.
otherwise, value_type shall be
size()).
CopyInsertable into X.
Effects: Inserts t, and returns
an iterator pointing to the newly
inserted element.
a.insert(p,
t)
iterator
Requires: If t is a non-const
Average case
rvalue expression, value_type
O(1), worst case
shall be MoveInsertable into X;
O(a.size()).
otherwise, value_type shall be
CopyInsertable into X.
Effects: Equivalent to
a.insert(t). Return value is
an iterator pointing to the
element with the key equivalent
to that of t. The iterator p is a
hint pointing to where the
search should start.
Implementations are permitted
to ignore the hint.
a.insert(i,
j)
void
Requires: value_type shall be
Average case
EmplaceConstructible into X
O(N ), where N
from *i.
is distance(i,
Requires: i and j are not
j). Worst case
iterators in a.
O(N (a.size()
Effects: Equivalent to
+ 1)).
a.insert(t) for each element
in [i,j).
a.insert(il)
void
Same as a.insert(il.begin(),
Same as
il.end()).
a.insert(
il.begin(),
il.end()).
§ 26.2.7
777
Table 91 — Unordered associative container requirements (in addi-
tion to container) (continued)
Expression
Return type
Assertion/note
Complexity
pre-/post-condition
a_uniq.
insert_return_type
Requires: nh is empty or
Average case
insert(nh)
a_uniq.get_allocator() ==
O(1), worst
nh.get_allocator().
case O(a_uniq.
Effects: If nh is empty, has no
size()).
effect. Otherwise, inserts the
element owned by nh if and only
if there is no element in the
container with a key equivalent
to nh.key().
Postconditions: If nh is empty,
inserted is false, position is
end(), and node is empty.
Otherwise if the insertion took
place, inserted is true,
position points to the inserted
element, and node is empty; if
the insertion failed, inserted is
false, node has the previous
value of nh, and position
points to an element with a key
equivalent to nh.key().
a_eq.
iterator
Requires: nh is empty or
Average case
insert(nh)
a_eq.get_allocator() ==
O(1), worst
nh.get_allocator().
case O(a_eq.
Effects: If nh is empty, has no
size()).
effect and returns a_eq.end().
Otherwise, inserts the element
owned by nh and returns an
iterator pointing to the newly
inserted element.
Postconditions: nh is empty.
§ 26.2.7
778
Table 91 — Unordered associative container requirements (in addi-
tion to container) (continued)
Expression
Return type
Assertion/note
Complexity
pre-/post-condition
a.insert(q, nh)
iterator
Requires: nh is empty or
Average case
a.get_allocator() ==
O(1), worst case
nh.get_allocator().
O(a.size()).
Effects: If nh is empty, has no
effect and returns a.end().
Otherwise, inserts the element
owned by nh if and only if there
is no element with key
equivalent to nh.key() in
containers with unique keys;
always inserts the element
owned by nh in containers with
equivalent keys. Always returns
the iterator pointing to the
element with key equivalent to
nh.key(). The iterator q is a
hint pointing to where the
search should start.
Implementations are permitted
to ignore the hint.
Postconditions: nh is empty if
insertion succeeds, unchanged if
insertion fails.
a.extract(k)
node_type
Removes an element in the
Average case
container with key equivalent to
O(1), worst case
k. Returns a node_type owning
O(a.size()).
the element if found, otherwise
an empty node_type.
a.extract(q)
node_type
Removes the element pointed to
Average case
by q. Returns a node_type
O(1), worst case
owning that element.
O(a.size()).
a.merge(a2)
void
Requires: a.get_allocator()
Average case
== a2.get_allocator().
O(N ), where N
Attempts to extract each
is a2.size().
element in a2 and insert it into
Worst case
a using the hash function and
O(N *a.size()
key equality predicate of a. In
+N ).
containers with unique keys, if
there is an element in a with key
equivalent to the key of an
element from a2, then that
element is not extracted from
a2.
Postconditions: Pointers and
references to the transferred
elements of a2 refer to those
same elements but as members
of a. Iterators referring to the
transferred elements and all
iterators referring to a will be
invalidated, but iterators to
elements remaining in a2 will
remain valid.
§ 26.2.7
779
Table 91 — Unordered associative container requirements (in addi-
tion to container) (continued)
Expression
Return type
Assertion/note
Complexity
pre-/post-condition
a.erase(k)
size_type
Erases all elements with key
Average case
equivalent to k. Returns the
O(a.count(k)).
number of elements erased.
Worst case
O(a.size()).
a.erase(q)
iterator
Erases the element pointed to by
Average case
q. Returns the iterator
O(1), worst case
immediately following q prior to
O(a.size()).
the erasure.
a.erase(r)
iterator
Erases the element pointed to by
Average case
r. Returns the iterator
O(1), worst case
immediately following r prior to
O(a.size()).
the erasure.
a.erase(q1,
q2)
iterator
Erases all elements in the range
Average case
[q1, q2). Returns the iterator
linear in
immediately following the erased
distance(q1,
elements prior to the erasure.
q2), worst case
O(a.size()).
a.clear()
void
Erases all elements in the
Linear in
container. Postconditions:
a.size().
a.empty() returns true
b.find(k)
iterator;
Returns an iterator pointing to
Average case
const_iterator for
an element with key equivalent
O(1), worst case
const b.
to k, or b.end() if no such
O(b.size()).
element exists.
b.count(k)
size_type
Returns the number of elements
Average case
with key equivalent to k.
O(b.count(k)),
worst case
O(b.size()).
b.equal_range(k)
pair<iterator,
Returns a range containing all
Average case
iterator>;
elements with keys equivalent to
O(b.count(k)).
pair<const_iterator,
k. Returns
Worst case
const_iterator> for
make_pair(b.end(), b.end())
O(b.size()).
const b.
if no such elements exist.
b.bucket_count()
size_type
Returns the number of buckets
Constant
that b contains.
b.max_bucket_-
size_type
Returns an upper bound on the
Constant
count()
number of buckets that b might
ever contain.
b.bucket(k)
size_type
Requires: b.bucket_count() >
Constant
0.
Returns the index of the bucket
in which elements with keys
equivalent to k would be found,
if any such element existed.
Postconditions: the return value
shall be in the range [0,
b.bucket_count()).
b.bucket_size(n)
size_type
Requires: n shall be in the range
O(b.bucket_-
[0, b.bucket_count()).
size(n))
Returns the number of elements
in the nth bucket.
§ 26.2.7
780
Table 91 — Unordered associative container requirements (in addi-
tion to container) (continued)
Expression
Return type
Assertion/note
Complexity
pre-/post-condition
b.begin(n)
local_iterator;
Requires: n shall be in the range
Constant
const_local_-
[0, b.bucket_count()).
iterator for const
b.begin(n) returns an iterator
b.
referring to the first element in
the bucket. If the bucket is
empty, then b.begin(n) ==
b.end(n).
b.end(n)
local_iterator;
Requires: n shall be in the range
Constant
const_local_-
[0, b.bucket_count()).
iterator for const
b.end(n) returns an iterator
b.
which is the past-the-end value
for the bucket.
b.cbegin(n)
const_local_-
Requires: n shall be in the range
Constant
iterator
[0, b.bucket_count()).
b.cbegin(n) returns an iterator
referring to the first element in
the bucket. If the bucket is
empty, then b.cbegin(n) ==
b.cend(n).
b.cend(n)
const_local_-
Requires: n shall be in the range
Constant
iterator
[0,
b.bucket_count()).b.cend(n)
returns an iterator which is the
past-the-end value for the
bucket.
b.load_factor()
float
Returns the average number of
Constant
elements per bucket.
b.max_load_factor()
float
Returns a positive number that
Constant
the container attempts to keep
the load factor less than or equal
to. The container automatically
increases the number of buckets
as necessary to keep the load
factor below this number.
a.max_load_-
void
Requires: z shall be positive.
Constant
factor(z)
May change the container’s
maximum load factor, using z as
a hint.
a.rehash(n)
void
Postconditions:
Average case
a.bucket_count() >=
linear in
a.size() /
a.size(),
a.max_load_factor() and
worst case
a.bucket_count() >= n.
quadratic.
a.reserve(n)
void
Same as a.rehash(ceil(n /
Average case
a.max_load_factor())).
linear in
a.size(),
worst case
quadratic.
12
Two unordered containers a and b compare equal if a.size() == b.size() and, for every equivalent-key
group [Ea1, Ea2) obtained from a.equal_range(Ea1), there exists an equivalent-key group [Eb1, Eb2)
obtained from b.equal_range(Ea1), such that is_permutation(Ea1, Ea2, Eb1, Eb2) returns true. For
unordered_set and unordered_map, the complexity of operator== (i.e., the number of calls to the ==
§ 26.2.7
781
operator of the value_type, to the predicate returned by key_eq(), and to the hasher returned by hash_-
function()) is proportional to N in the average case and to N2 in the worst case, where N is a.size(). For
unordered_multiset and unordered_multimap, the complexity of operator== is proportional to
∑E2
i in
the average case and to N2 in the worst case, where N is a.size(), and Ei is the size of the ith equivalent-key
group in a. However, if the respective elements of each corresponding pair of equivalent-key groups Eai and
Ebi are arranged in the same order (as is commonly the case, e.g., if a and b are unmodified copies of the same
container), then the average-case complexity for unordered_multiset and unordered_multimap becomes
proportional to N (but worst-case complexity remains O(N2), e.g., for a pathologically bad hash function).
The behavior of a program that uses operator== or operator!= on unordered containers is undefined unless
the Hash and Pred function objects respectively have the same behavior for both containers and the equality
comparison function for Key is a refinement260 of the partition into equivalent-key groups produced by Pred.
13
The iterator types iterator and const_iterator of an unordered associative container are of at least the
forward iterator category. For unordered associative containers where the key type and value type are the
same, both iterator and const_iterator are constant iterators.
14
The insert and emplace members shall not affect the validity of references to container elements, but may
invalidate all iterators to the container. The erase members shall invalidate only iterators and references to
the erased elements, and preserve the relative order of the elements that are not erased.
15
The insert and emplace members shall not affect the validity of iterators if (N+n) <= z * B, where N is
the number of elements in the container prior to the insert operation, n is the number of elements inserted, B
is the container’s bucket count, and z is the container’s maximum load factor.
16
The extract members invalidate only iterators to the removed element, and preserve the relative order of
the elements that are not erased; pointers and references to the removed element remain valid. However,
accessing the element through such pointers and references while the element is owned by a node_type is
undefined behavior. References and pointers to an element obtained while it is owned by a node_type are
invalidated if the element is successfully inserted.
17
A deduction guide for an unordered associative container shall not participate in overload resolution if any of
the following are true:
(17.1)
—
It has an InputIterator template parameter and a type that does not qualify as an input iterator is
deduced for that parameter.
(17.2)
—
It has an Allocator template parameter and a type that does not qualify as an allocator is deduced
for that parameter.
(17.3)
—
It has a Hash template parameter and an integral type or a type that qualifies as an allocator is deduced
for that parameter.
(17.4)
—
It has a Pred template parameter and a type that qualifies as an allocator is deduced for that parameter.
26.2.7.1
Exception safety guarantees
[unord.req.except]
1
For unordered associative containers, no clear() function throws an exception. erase(k) does not throw an
exception unless that exception is thrown by the container’s Hash or Pred object (if any).
2
For unordered associative containers, if an exception is thrown by any operation other than the container’s
hash function from within an insert or emplace function inserting a single element, the insertion has no
effect.
3
For unordered associative containers, no swap function throws an exception unless that exception is thrown
by the swap of the container’s Hash or Pred object (if any).
4
For unordered associative containers, if an exception is thrown from within a rehash() function other than
by the container’s hash function or comparison function, the rehash() function has no effect.
26.3
Sequence containers
[sequences]
26.3.1
In general
[sequences.general]
1
The headers <array>, <deque>, <forward_list>, <list>, and <vector> define class templates that meet
the requirements for sequence containers.
260) Equality comparison is a refinement of partitioning if no two objects that compare equal fall into different partitions.
§ 26.3.1
782
26.3.2
Header <array> synopsis
[array.syn]
#include <initializer_list>
namespace std {
// 26.3.7, class template array
template<class T, size_t N> struct array;
template<class T, size_t N>
bool operator==(const array<T, N>& x, const array<T, N>& y);
template<class T, size_t N>
bool operator!=(const array<T, N>& x, const array<T, N>& y);
template<class T, size_t N>
bool operator< (const array<T, N>& x, const array<T, N>& y);
template<class T, size_t N>
bool operator> (const array<T, N>& x, const array<T, N>& y);
template<class T, size_t N>
bool operator<=(const array<T, N>& x, const array<T, N>& y);
template<class T, size_t N>
bool operator>=(const array<T, N>& x, const array<T, N>& y);
template<class T, size_t N>
void swap(array<T, N>& x, array<T, N>& y) noexcept(noexcept(x.swap(y)));
template<class T> class tuple_size;
template<size_t I, class T> class tuple_element;
template<class T, size_t N>
struct tuple_size<array<T, N>>;
template<size_t I, class T, size_t N>
struct tuple_element<I, array<T, N>>;
template<size_t I, class T, size_t N>
constexpr T& get(array<T, N>&) noexcept;
template<size_t I, class T, size_t N>
constexpr T&& get(array<T, N>&&) noexcept;
template<size_t I, class T, size_t N>
constexpr const T& get(const array<T, N>&) noexcept;
template<size_t I, class T, size_t N>
constexpr const T&& get(const array<T, N>&&) noexcept;
}
26.3.3
Header <deque> synopsis
[deque.syn]
#include <initializer_list>
namespace std {
// 26.3.8, class template deque
template<class T, class Allocator = allocator<T>> class deque;
template<class T, class Allocator>
bool operator==(const deque<T, Allocator>& x, const deque<T,
Allocator>&
y);
template<class T, class Allocator>
bool operator< (const deque<T, Allocator>& x, const deque<T,
Allocator>&
y);
template<class T, class Allocator>
bool operator!=(const deque<T, Allocator>& x, const deque<T,
Allocator>&
y);
template<class T, class Allocator>
bool operator> (const deque<T, Allocator>& x, const deque<T,
Allocator>&
y);
template<class T, class Allocator>
bool operator>=(const deque<T, Allocator>& x, const deque<T,
Allocator>&
y);
template<class T, class Allocator>
bool operator<=(const deque<T, Allocator>& x, const deque<T,
Allocator>&
y);
template<class T, class Allocator>
void swap(deque<T, Allocator>& x, deque<T, Allocator>& y)
noexcept(noexcept(x.swap(y)));
§ 26.3.3
783
namespace pmr {
template<class T>
using deque = std::deque<T, polymorphic_allocator<T>>;
}
}
26.3.4
Header <forward_list> synopsis
[forward_list.syn]
#include <initializer_list>
namespace std {
// 26.3.9, class template forward_list
template<class T, class Allocator = allocator<T>> class forward_list;
template<class T, class Allocator>
bool operator==(const forward_list<T, Allocator>& x, const forward_list<T,
Allocator>& y);
template<class T, class Allocator>
bool operator< (const forward_list<T, Allocator>& x, const forward_list<T,
Allocator>& y);
template<class T, class Allocator>
bool operator!=(const forward_list<T, Allocator>& x, const forward_list<T,
Allocator>& y);
template<class T, class Allocator>
bool operator> (const forward_list<T, Allocator>& x, const forward_list<T,
Allocator>& y);
template<class T, class Allocator>
bool operator>=(const forward_list<T, Allocator>& x, const forward_list<T,
Allocator>& y);
template<class T, class Allocator>
bool operator<=(const forward_list<T, Allocator>& x, const forward_list<T,
Allocator>& y);
template<class T, class Allocator>
void swap(forward_list<T, Allocator>& x, forward_list<T, Allocator>& y)
noexcept(noexcept(x.swap(y)));
namespace pmr {
template<class T>
using forward_list = std::forward_list<T, polymorphic_allocator<T>>;
}
}
26.3.5
Header <list> synopsis
[list.syn]
#include <initializer_list>
namespace std {
// 26.3.10, class template list
template<class T, class Allocator = allocator<T>> class list;
template<class T, class Allocator>
bool operator==(const list<T, Allocator>& x, const list<T, Allocator>&
y);
template<class T, class Allocator>
bool operator< (const list<T, Allocator>& x, const list<T, Allocator>&
y);
template<class T, class Allocator>
bool operator!=(const list<T, Allocator>& x, const list<T, Allocator>&
y);
template<class T, class Allocator>
bool operator> (const list<T, Allocator>& x, const list<T, Allocator>&
y);
template<class T, class Allocator>
bool operator>=(const list<T, Allocator>& x, const list<T, Allocator>&
y);
template<class T, class Allocator>
bool operator<=(const list<T, Allocator>& x, const list<T, Allocator>&
y);
template<class T, class Allocator>
void swap(list<T, Allocator>& x, list<T, Allocator>& y)
noexcept(noexcept(x.swap(y)));
namespace pmr {
template<class T>
using list = std::list<T, polymorphic_allocator<T>>;
§ 26.3.5
784
}
}
26.3.6
Header <vector> synopsis
[vector.syn]
#include <initializer_list>
namespace std {
// 26.3.11, class template vector
template<class T, class Allocator = allocator<T>> class vector;
template<class T, class Allocator>
bool operator==(const vector<T, Allocator>& x, const vector<T,
Allocator>&
y);
template<class T, class Allocator>
bool operator< (const vector<T, Allocator>& x, const vector<T,
Allocator>&
y);
template<class T, class Allocator>
bool operator!=(const vector<T, Allocator>& x, const vector<T,
Allocator>&
y);
template<class T, class Allocator>
bool operator> (const vector<T, Allocator>& x, const vector<T,
Allocator>&
y);
template<class T, class Allocator>
bool operator>=(const vector<T, Allocator>& x, const vector<T,
Allocator>&
y);
template<class T, class Allocator>
bool operator<=(const vector<T, Allocator>& x, const vector<T,
Allocator>&
y);
template<class T, class Allocator>
void swap(vector<T, Allocator>& x, vector<T, Allocator>& y)
noexcept(noexcept(x.swap(y)));
// 26.3.12, class vector<bool>
template<class Allocator> class vector<bool, Allocator>;
// hash support
template<class T> struct hash;
template<class Allocator> struct hash<vector<bool, Allocator>>;
namespace pmr {
template<class T>
using vector = std::vector<T, polymorphic_allocator<T>>;
}
}
26.3.7
Class template array
[array]
26.3.7.1
Class template array overview
[array.overview]
1
The header <array> defines a class template for storing fixed-size sequences of objects. An array is a
contiguous container (26.2.1). An instance of array<T, N> stores N elements of type T, so that size() == N
is an invariant.
2
An array is an aggregate (11.6.1) that can be list-initialized with up to N elements whose types are convertible
to T.
3
An array satisfies all of the requirements of a container and of a reversible container (26.2), except that a
default constructed array object is not empty and that swap does not have constant complexity. An array
satisfies some of the requirements of a sequence container (26.2.3). Descriptions are provided here only for
operations on array that are not described in one of these tables and for operations where there is additional
semantic information.
namespace std {
template<class T, size_t N>
struct array {
// types
using value_type
= T;
using pointer
= T*;
using const_pointer
= const T*;
using reference
= T&;
using const_reference
= const T&;
§ 26.3.7.1
785
using size_type
= size_t;
using difference_type
= ptrdiff_t;
using iterator
= implementation-defined ; // see 26.2
using const_iterator
= implementation-defined ; // see 26.2
using reverse_iterator
= std::reverse_iterator<iterator>;
using const_reverse_iterator = std::reverse_iterator<const_iterator>;
// no explicit construct/copy/destroy for aggregate type
void fill(const T& u);
void swap(array&) noexcept(is_nothrow_swappable_v<T>);
// iterators
constexpr iterator
begin() noexcept;
constexpr const_iterator
begin() const noexcept;
constexpr iterator
end() noexcept;
constexpr const_iterator
end() const noexcept;
constexpr reverse_iterator
rbegin() noexcept;
constexpr const_reverse_iterator rbegin() const noexcept;
constexpr reverse_iterator
rend() noexcept;
constexpr const_reverse_iterator rend() const noexcept;
constexpr const_iterator
cbegin() const noexcept;
constexpr const_iterator
cend() const noexcept;
constexpr const_reverse_iterator crbegin() const noexcept;
constexpr const_reverse_iterator crend() const noexcept;
// capacity
[[nodiscard]] constexpr bool empty() const noexcept;
constexpr size_type size() const noexcept;
constexpr size_type max_size() const noexcept;
// element access
constexpr reference
operator[](size_type n);
constexpr const_reference operator[](size_type n) const;
constexpr reference
at(size_type n);
constexpr const_reference at(size_type n) const;
constexpr reference
front();
constexpr const_reference front() const;
constexpr reference
back();
constexpr const_reference back() const;
constexpr T *
data() noexcept;
constexpr const T * data() const noexcept;
};
template<class T, class... U>
array(T, U...) -> array<T, 1 + sizeof...(U)>;
}
26.3.7.2
array constructors, copy, and assignment
[array.cons]
1
The conditions for an aggregate (11.6.1) shall be met. Class array relies on the implicitly-declared special
member functions (15.1, 15.4, and 15.8) to conform to the container requirements table in 26.2. In addition
to the requirements specified in the container requirements table, the implicit move constructor and move
assignment operator for array require that T be MoveConstructible or MoveAssignable, respectively.
template<class T, class... U>
array(T, U...) -> array<T, 1 + sizeof...(U)>;
2
Requires: (is_same_v<T, U> && ...) is true. Otherwise the program is ill-formed.
§ 26.3.7.2
786
26.3.7.3
array member functions
[array.members]
constexpr size_type size() const noexcept;
1
Returns: N.
constexpr T* data() noexcept;
constexpr const T* data() const noexcept;
2
Returns: A pointer such that data() == addressof(front()), and [data(), data() + size()) is
a valid range.
void fill(const T& u);
3
Effects: As if by fill_n(begin(), N, u).
void swap(array& y) noexcept(is_nothrow_swappable_v<T>);
4
Effects: Equivalent to swap_ranges(begin(), end(), y.begin()).
5
[ Note: Unlike the swap function for other containers, array::swap takes linear time, may exit via an
exception, and does not cause iterators to become associated with the other container.
— end note ]
26.3.7.4
array specialized algorithms
[array.special]
template<class T, size_t N>
void swap(array<T, N>& x, array<T, N>& y) noexcept(noexcept(x.swap(y)));
1
Remarks: This function shall not participate in overload resolution unless N == 0 or is_swappable_v<T>
is true.
2
Effects: As if by x.swap(y).
3
Complexity: Linear in N.
26.3.7.5
Zero sized arrays
[array.zero]
1
array shall provide support for the special case N == 0.
2
In the case that N == 0, begin() == end() == unique value. The return value of data() is unspecified.
3
The effect of calling front() or back() for a zero-sized array is undefined.
4
Member function swap() shall have a non-throwing exception specification.
26.3.7.6
Tuple interface to class template array
[array.tuple]
template<class T, size_t N>
struct tuple_size<array<T, N>> : integral_constant<size_t, N> { };
tuple_element<I, array<T, N>>::type
1
Requires: I < N. The program is ill-formed if I is out of bounds.
2
Value: The type T.
template<size_t I, class T, size_t N>
constexpr T& get(array<T, N>& a) noexcept;
template<size_t I, class T, size_t N>
constexpr T&& get(array<T, N>&& a) noexcept;
template<size_t I, class T, size_t N>
constexpr const T& get(const array<T, N>& a) noexcept;
template<size_t I, class T, size_t N>
constexpr const T&& get(const array<T, N>&& a) noexcept;
3
Requires: I < N. The program is ill-formed if I is out of bounds.
4
Returns: A reference to the Ith element of a, where indexing is zero-based.
26.3.8
Class template deque
[deque]
26.3.8.1
Class template deque overview
[deque.overview]
1
A deque is a sequence container that supports random access iterators (27.2.7).
In addition, it supports
constant time insert and erase operations at the beginning or the end; insert and erase in the middle take
§ 26.3.8.1
787
linear time. That is, a deque is especially optimized for pushing and popping elements at the beginning and
end. Storage management is handled automatically.
2
A deque satisfies all of the requirements of a container, of a reversible container (given in tables in 26.2), of a
sequence container, including the optional sequence container requirements (26.2.3), and of an allocator-aware
container (Table 86). Descriptions are provided here only for operations on deque that are not described in
one of these tables or for operations where there is additional semantic information.
namespace std {
template<class T, class Allocator = allocator<T>>
class deque {
public:
// types
using value_type
= T;
using allocator_type
= Allocator;
using pointer
= typename allocator_traits<Allocator>::pointer;
using const_pointer
= typename allocator_traits<Allocator>::const_pointer;
using reference
= value_type&;
using const_reference
= const value_type&;
using size_type
= implementation-defined ; // see 26.2
using difference_type
= implementation-defined ; // see 26.2
using iterator
= implementation-defined ; // see 26.2
using const_iterator
= implementation-defined ; // see 26.2
using reverse_iterator
= std::reverse_iterator<iterator>;
using const_reverse_iterator = std::reverse_iterator<const_iterator>;
// 26.3.8.2, construct/copy/destroy
deque() : deque(Allocator()) { }
explicit deque(const Allocator&);
explicit deque(size_type n, const Allocator& = Allocator());
deque(size_type n, const T& value, const Allocator& = Allocator());
template<class InputIterator>
deque(InputIterator first, InputIterator last, const Allocator&
=
Allocator());
deque(const deque& x);
deque(deque&&);
deque(const deque&, const Allocator&);
deque(deque&&, const Allocator&);
deque(initializer_list<T>, const Allocator& = Allocator());
~deque();
deque& operator=(const deque& x);
deque& operator=(deque&& x)
noexcept(allocator_traits<Allocator>::is_always_equal::value);
deque& operator=(initializer_list<T>);
template<class InputIterator>
void assign(InputIterator first, InputIterator last);
void assign(size_type n, const T& t);
void assign(initializer_list<T>);
allocator_type get_allocator() const noexcept;
// iterators
iterator
begin() noexcept;
const_iterator
begin() const noexcept;
iterator
end() noexcept;
const_iterator
end() const noexcept;
reverse_iterator
rbegin() noexcept;
const_reverse_iterator rbegin() const noexcept;
reverse_iterator
rend() noexcept;
const_reverse_iterator rend() const noexcept;
const_iterator
cbegin() const noexcept;
const_iterator
cend() const noexcept;
const_reverse_iterator crbegin() const noexcept;
const_reverse_iterator crend() const noexcept;
§
26.3.8.1
788
// 26.3.8.3, capacity
[[nodiscard]] bool empty() const noexcept;
size_type size() const noexcept;
size_type max_size() const noexcept;
void
resize(size_type sz);
void
resize(size_type sz, const T& c);
void
shrink_to_fit();
// element access
reference
operator[](size_type n);
const_reference operator[](size_type n) const;
reference
at(size_type n);
const_reference at(size_type n) const;
reference
front();
const_reference front() const;
reference
back();
const_reference back() const;
// 26.3.8.4, modifiers
template<class... Args> reference emplace_front(Args&&... args);
template<class... Args> reference emplace_back(Args&&... args);
template<class... Args> iterator emplace(const_iterator position,
Args&&...
args);
void push_front(const T& x);
void push_front(T&& x);
void push_back(const T& x);
void push_back(T&& x);
iterator insert(const_iterator position, const T& x);
iterator insert(const_iterator position, T&& x);
iterator insert(const_iterator position, size_type n, const T& x);
template<class InputIterator>
iterator insert(const_iterator position, InputIterator first, InputIterator last);
iterator insert(const_iterator position, initializer_list<T>);
void pop_front();
void pop_back();
iterator erase(const_iterator position);
iterator erase(const_iterator first, const_iterator last);
void
swap(deque&)
noexcept(allocator_traits<Allocator>::is_always_equal::value);
void
clear() noexcept;
};
template<class InputIterator,
class Allocator = allocator<typename iterator_traits<InputIterator>::value_type>>
deque(InputIterator, InputIterator, Allocator = Allocator())
-> deque<typename iterator_traits<InputIterator>::value_type, Allocator>;
// 26.3.8.5, specialized algorithms
template<class T, class Allocator>
void swap(deque<T, Allocator>& x, deque<T, Allocator>& y)
noexcept(noexcept(x.swap(y)));
}
26.3.8.2
deque constructors, copy, and assignment
[deque.cons]
explicit deque(const Allocator&);
1
Effects: Constructs an empty deque, using the specified allocator.
2
Complexity: Constant.
§ 26.3.8.2
789
explicit deque(size_type n, const Allocator& = Allocator());
3
Effects: Constructs a deque with n default-inserted elements using the specified allocator.
4
Requires: T shall be DefaultInsertable into *this.
5
Complexity: Linear in n.
deque(size_type n, const T& value, const Allocator& = Allocator());
6
Effects: Constructs a deque with n copies of value, using the specified allocator.
7
Requires: T shall be CopyInsertable into *this.
8
Complexity: Linear in n.
template<class InputIterator>
deque(InputIterator first, InputIterator last, const Allocator& = Allocator());
9
Effects: Constructs a deque equal to the range [first, last), using the specified allocator.
10
Complexity: Linear in distance(first, last).
26.3.8.3
deque capacity
[deque.capacity]
void resize(size_type sz);
1
Effects: If sz
< size(), erases the last size() - sz elements from the sequence. Otherwise, appends
sz - size() default-inserted elements to the sequence.
2
Requires: T shall be MoveInsertable and DefaultInsertable into *this.
void resize(size_type sz, const T& c);
3
Effects: If sz
< size(), erases the last size() - sz elements from the sequence. Otherwise, appends
sz - size() copies of c to the sequence.
4
Requires: T shall be CopyInsertable into *this.
void shrink_to_fit();
5
Requires: T shall be MoveInsertable into *this.
6
Effects: shrink_to_fit is a non-binding request to reduce memory use but does not change the
size of the sequence. [Note: The request is non-binding to allow latitude for implementation-specific
optimizations.
— end note ] If an exception is thrown other than by the move constructor of a
non-CopyInsertable T there are no effects.
7
Complexity: Linear in the size of the sequence.
8
Remarks: shrink_to_fit invalidates all the references, pointers, and iterators referring to the elements
in the sequence as well as the past-the-end iterator.
26.3.8.4
deque modifiers
[deque.modifiers]
iterator insert(const_iterator position, const T& x);
iterator insert(const_iterator position, T&& x);
iterator insert(const_iterator position, size_type n, const T& x);
template<class InputIterator>
iterator insert(const_iterator position,
InputIterator first, InputIterator last);
iterator insert(const_iterator position, initializer_list<T>);
template<class... Args> reference emplace_front(Args&&... args);
template<class... Args> reference emplace_back(Args&&... args);
template<class... Args> iterator emplace(const_iterator position, Args&&... args);
void push_front(const T& x);
void push_front(T&& x);
void push_back(const T& x);
void push_back(T&& x);
1
Effects: An insertion in the middle of the deque invalidates all the iterators and references to elements
of the deque. An insertion at either end of the deque invalidates all the iterators to the deque, but has
no effect on the validity of references to elements of the deque.
§ 26.3.8.4
790
2
Remarks: If an exception is thrown other than by the copy constructor, move constructor, assignment
operator, or move assignment operator of T there are no effects. If an exception is thrown while inserting
a single element at either end, there are no effects. Otherwise, if an exception is thrown by the move
constructor of a non-CopyInsertable T, the effects are unspecified.
3
Complexity: The complexity is linear in the number of elements inserted plus the lesser of the distances
to the beginning and end of the deque. Inserting a single element either at the beginning or end of a
deque always takes constant time and causes a single call to a constructor of T.
iterator erase(const_iterator position);
iterator erase(const_iterator first, const_iterator last);
void pop_front();
void pop_back();
4
Effects: An erase operation that erases the last element of a deque invalidates only the past-the-end
iterator and all iterators and references to the erased elements. An erase operation that erases the
first element of a deque but not the last element invalidates only iterators and references to the erased
elements. An erase operation that erases neither the first element nor the last element of a deque
invalidates the past-the-end iterator and all iterators and references to all the elements of the deque.
[ Note: pop_front and pop_back are erase operations.
— end note ]
5
Complexity: The number of calls to the destructor of T is the same as the number of elements erased,
but the number of calls to the assignment operator of T is no more than the lesser of the number of
elements before the erased elements and the number of elements after the erased elements.
6
Throws: Nothing unless an exception is thrown by the assignment operator of T.
26.3.8.5
deque specialized algorithms
[deque.special]
template<class T, class Allocator>
void swap(deque<T, Allocator>& x, deque<T, Allocator>& y)
noexcept(noexcept(x.swap(y)));
1
Effects: As if by x.swap(y).
26.3.9
Class template forward_list
[forwardlist]
26.3.9.1
Class template forward_list overview
[forwardlist.overview]
1
A forward_list is a container that supports forward iterators and allows constant time insert and erase
operations anywhere within the sequence, with storage management handled automatically. Fast random
access to list elements is not supported. [Note: It is intended that forward_list have zero space or time
overhead relative to a hand-written C-style singly linked list. Features that would conflict with that goal
have been omitted. — end note ]
2
A forward_list satisfies all of the requirements of a container (Table 83), except that the size() member
function is not provided and operator== has linear complexity. A forward_list also satisfies all of the
requirements for an allocator-aware container (Table 86). In addition, a forward_list provides the assign
member functions (Table 87) and several of the optional container requirements (Table 88). Descriptions are
provided here only for operations on forward_list that are not described in that table or for operations
where there is additional semantic information.
3
[Note: Modifying any list requires access to the element preceding the first element of interest, but in a
forward_list there is no constant-time way to access a preceding element. For this reason, ranges that are
modified, such as those supplied to erase and splice, must be open at the beginning.
— end note ]
namespace std {
template<class T, class Allocator = allocator<T>>
class forward_list {
public:
// types
using value_type
= T;
using allocator_type
= Allocator;
using pointer
= typename allocator_traits<Allocator>::pointer;
using const_pointer
= typename allocator_traits<Allocator>::const_pointer;
using reference
= value_type&;
using const_reference = const value_type&;
using size_type
= implementation-defined ; // see 26.2
§ 26.3.9.1
791
using difference_type = implementation-defined ; // see 26.2
using iterator
= implementation-defined ; // see 26.2
using const_iterator
= implementation-defined ; // see 26.2
// 26.3.9.2, construct/copy/destroy
forward_list() : forward_list(Allocator()) { }
explicit forward_list(const Allocator&);
explicit forward_list(size_type n, const Allocator& = Allocator());
forward_list(size_type n, const T& value, const Allocator& = Allocator());
template<class InputIterator>
forward_list(InputIterator first, InputIterator last, const Allocator&
=
Allocator());
forward_list(const forward_list& x);
forward_list(forward_list&& x);
forward_list(const forward_list& x, const Allocator&);
forward_list(forward_list&& x, const Allocator&);
forward_list(initializer_list<T>, const Allocator& = Allocator());
~forward_list();
forward_list& operator=(const forward_list& x);
forward_list& operator=(forward_list&& x)
noexcept(allocator_traits<Allocator>::is_always_equal::value);
forward_list& operator=(initializer_list<T>);
template<class InputIterator>
void assign(InputIterator first, InputIterator last);
void assign(size_type n, const T& t);
void assign(initializer_list<T>);
allocator_type get_allocator() const noexcept;
// 26.3.9.3, iterators
iterator before_begin() noexcept;
const_iterator before_begin() const noexcept;
iterator begin() noexcept;
const_iterator begin() const noexcept;
iterator end() noexcept;
const_iterator end() const noexcept;
const_iterator cbegin() const noexcept;
const_iterator cbefore_begin() const noexcept;
const_iterator cend() const noexcept;
// capacity
[[nodiscard]] bool empty() const noexcept;
size_type max_size() const noexcept;
// 26.3.9.4, element access
reference front();
const_reference front() const;
// 26.3.9.5, modifiers
template<class... Args> reference emplace_front(Args&&...
args);
void push_front(const T& x);
void push_front(T&& x);
void pop_front();
template<class... Args> iterator emplace_after(const_iterator position,
Args&&...
args);
iterator insert_after(const_iterator position, const T& x);
iterator insert_after(const_iterator position, T&& x);
iterator insert_after(const_iterator position, size_type n, const T& x);
template<class InputIterator>
iterator insert_after(const_iterator position, InputIterator first, InputIterator last);
iterator insert_after(const_iterator position, initializer_list<T> il);
iterator erase_after(const_iterator position);
iterator erase_after(const_iterator position, const_iterator last);
§
26.3.9.1
792
void swap(forward_list&)
noexcept(allocator_traits<Allocator>::is_always_equal::value);
void resize(size_type sz);
void resize(size_type sz, const value_type& c);
void clear() noexcept;
// 26.3.9.6, forward_list operations
void splice_after(const_iterator position, forward_list& x);
void splice_after(const_iterator position, forward_list&& x);
void splice_after(const_iterator position, forward_list& x, const_iterator i);
void splice_after(const_iterator position, forward_list&& x, const_iterator i);
void splice_after(const_iterator position, forward_list& x,
const_iterator first, const_iterator last);
void splice_after(const_iterator position, forward_list&& x,
const_iterator first, const_iterator last);
void remove(const T& value);
template<class Predicate> void remove_if(Predicate pred);
void unique();
template<class BinaryPredicate> void unique(BinaryPredicate binary_pred);
void merge(forward_list& x);
void merge(forward_list&& x);
template<class Compare> void merge(forward_list& x, Compare comp);
template<class Compare> void merge(forward_list&& x, Compare comp);
void sort();
template<class Compare> void sort(Compare comp);
void reverse() noexcept;
};
template<class InputIterator,
class Allocator = allocator<typename iterator_traits<InputIterator>::value_type>>
forward_list(InputIterator, InputIterator, Allocator = Allocator())
-> forward_list<typename iterator_traits<InputIterator>::value_type, Allocator>;
// 26.3.9.7, specialized algorithms
template<class T, class Allocator>
void swap(forward_list<T, Allocator>& x, forward_list<T, Allocator>& y)
noexcept(noexcept(x.swap(y)));
}
4
An incomplete type T may be used when instantiating forward_list if the allocator satisfies the allocator
completeness requirements (20.5.3.5.1). T shall be complete before any member of the resulting specialization
of forward_list is referenced.
26.3.9.2
forward_list constructors, copy, assignment
[forwardlist.cons]
explicit forward_list(const Allocator&);
1
Effects: Constructs an empty forward_list object using the specified allocator.
2
Complexity: Constant.
explicit forward_list(size_type n, const Allocator& = Allocator());
3
Effects: Constructs a forward_list object with n default-inserted elements using the specified allocator.
4
Requires: T shall be DefaultInsertable into *this.
5
Complexity: Linear in n.
forward_list(size_type n, const T& value, const Allocator& = Allocator());
6
Effects: Constructs a forward_list object with n copies of value using the specified allocator.
§ 26.3.9.2
793
7
Requires: T shall be CopyInsertable into *this.
8
Complexity: Linear in n.
template<class InputIterator>
forward_list(InputIterator first, InputIterator last, const Allocator& = Allocator());
9
Effects: Constructs a forward_list object equal to the range [first, last).
10
Complexity: Linear in distance(first, last).
26.3.9.3
forward_list iterators
[forwardlist.iter]
iterator before_begin() noexcept;
const_iterator before_begin() const noexcept;
const_iterator cbefore_begin() const noexcept;
1
Returns: A non-dereferenceable iterator that, when incremented, is equal to the iterator returned by
begin().
2
Effects: cbefore_begin() is equivalent to const_cast<forward_list const&>(*this).before_-
begin().
3
Remarks: before_begin() == end() shall equal false.
26.3.9.4
forward_list element access
[forwardlist.access]
reference front();
const_reference front() const;
1
Returns: *begin()
26.3.9.5
forward_list modifiers
[forwardlist.modifiers]
1
None of the overloads of insert_after shall affect the validity of iterators and references, and erase_after
shall invalidate only iterators and references to the erased elements. If an exception is thrown during
insert_after there shall be no effect. Inserting n elements into a forward_list is linear in n, and the
number of calls to the copy or move constructor of T is exactly equal to n. Erasing n elements from a
forward_list is linear in n and the number of calls to the destructor of type T is exactly equal to n.
template<class... Args> reference emplace_front(Args&&... args);
2
Effects: Inserts an object of type value_type constructed with value_type(std::forward<Args>(
args)...) at the beginning of the list.
void push_front(const T& x);
void push_front(T&& x);
3
Effects: Inserts a copy of x at the beginning of the list.
void pop_front();
4
Effects: As if by erase_after(before_begin()).
iterator insert_after(const_iterator position, const T& x);
iterator insert_after(const_iterator position, T&& x);
5
Requires: position is before_begin() or is a dereferenceable iterator in the range [begin(), end()).
6
Effects: Inserts a copy of x after position.
7
Returns: An iterator pointing to the copy of x.
iterator insert_after(const_iterator position, size_type n, const T& x);
8
Requires: position is before_begin() or is a dereferenceable iterator in the range [begin(), end()).
9
Effects: Inserts n copies of x after position.
10
Returns: An iterator pointing to the last inserted copy of x or position if n == 0.
§ 26.3.9.5
794
template<class InputIterator>
iterator insert_after(const_iterator position, InputIterator first, InputIterator last);
11
Requires: position is before_begin() or is a dereferenceable iterator in the range [begin(), end()).
first and last are not iterators in *this.
12
Effects: Inserts copies of elements in [first, last) after position.
13
Returns: An iterator pointing to the last inserted element or position if first == last.
iterator insert_after(const_iterator position, initializer_list<T> il);
14
Effects: insert_after(p, il.begin(), il.end()).
15
Returns: An iterator pointing to the last inserted element or position if il is empty.
template<class... Args>
iterator emplace_after(const_iterator position, Args&&... args);
16
Requires: position is before_begin() or is a dereferenceable iterator in the range [begin(), end()).
17
Effects: Inserts an object of type value_type constructed with value_type(std::forward<Args>(
args)...) after position.
18
Returns: An iterator pointing to the new object.
iterator erase_after(const_iterator position);
19
Requires: The iterator following position is dereferenceable.
20
Effects: Erases the element pointed to by the iterator following position.
21
Returns: An iterator pointing to the element following the one that was erased, or end() if no such
element exists.
22
Throws: Nothing.
iterator erase_after(const_iterator position, const_iterator last);
23
Requires: All iterators in the range (position, last) are dereferenceable.
24
Effects: Erases the elements in the range (position, last).
25
Returns: last.
26
Throws: Nothing.
void resize(size_type sz);
27
Effects: If sz
< distance(begin(), end()), erases the last distance(begin(), end()) - sz ele-
ments from the list. Otherwise, inserts sz - distance(begin(), end()) default-inserted elements at
the end of the list.
28
Requires: T shall be DefaultInsertable into *this.
void resize(size_type sz, const value_type& c);
29
Effects: If sz
< distance(begin(), end()), erases the last distance(begin(), end()) - sz ele-
ments from the list. Otherwise, inserts sz - distance(begin(), end()) copies of c at the end of the
list.
30
Requires: T shall be CopyInsertable into *this.
void clear() noexcept;
31
Effects: Erases all elements in the range [begin(), end()).
32
Remarks: Does not invalidate past-the-end iterators.
26.3.9.6
forward_list operations
[forwardlist.ops]
1
In this subclause, arguments for a template parameter named Predicate or BinaryPredicate shall meet
the corresponding requirements in 28.3. For merge and sort, the definitions and requirements in 28.7 apply.
void splice_after(const_iterator position, forward_list& x);
§ 26.3.9.6
795
void
splice_after(const_iterator position, forward_list&& x);
2
Requires: position is before_begin() or is a dereferenceable iterator in the range [begin(), end()).
get_allocator() == x.get_allocator(). &x != this.
3
Effects: Inserts the contents of x after position, and x becomes empty. Pointers and references to the
moved elements of x now refer to those same elements but as members of *this. Iterators referring
to the moved elements will continue to refer to their elements, but they now behave as iterators into
*this, not into x.
4
Throws: Nothing.
5
Complexity: O(distance(x.begin(), x.end()))
void
splice_after(const_iterator position, forward_list& x, const_iterator i);
void
splice_after(const_iterator position, forward_list&& x, const_iterator i);
6
Requires: position is before_begin() or is a dereferenceable iterator in the range [begin(), end()).
The iterator following i is a dereferenceable iterator in x. get_allocator() == x.get_allocator().
7
Effects: Inserts the element following i into *this, following position, and removes it from x. The
result is unchanged if position == i or position == ++i. Pointers and references to *++i continue
to refer to the same element but as a member of *this. Iterators to *++i continue to refer to the same
element, but now behave as iterators into *this, not into x.
8
Throws: Nothing.
9
Complexity: O(1)
void
splice_after(const_iterator position, forward_list& x,
const_iterator first, const_iterator last);
void
splice_after(const_iterator position, forward_list&& x,
const_iterator first, const_iterator last);
10
Requires: position is before_begin() or is a dereferenceable iterator in the range [begin(), end()).
(first, last) is a valid range in x, and all iterators in the range (first, last) are dereferenceable.
position is not an iterator in the range (first, last). get_allocator() == x.get_allocator().
11
Effects: Inserts elements in the range (first, last) after position and removes the elements from x.
Pointers and references to the moved elements of x now refer to those same elements but as members
of *this. Iterators referring to the moved elements will continue to refer to their elements, but they
now behave as iterators into *this, not into x.
12
Complexity: O(distance(first, last))
void
remove(const T& value);
template<class Predicate> void remove_if(Predicate pred);
13
Effects: Erases all the elements in the list referred by a list iterator i for which the following conditions
hold: *i == value (for remove()), pred(*i) is true (for remove_if()). Invalidates only the iterators
and references to the erased elements.
14
Throws: Nothing unless an exception is thrown by the equality comparison or the predicate.
15
Remarks: Stable (20.5.5.7).
16
Complexity: Exactly distance(begin(), end()) applications of the corresponding predicate.
void unique();
template<class BinaryPredicate> void unique(BinaryPredicate pred);
17
Effects: Erases all but the first element from every consecutive group of equal elements referred to
by the iterator i in the range [first + 1, last) for which *i == *(i-1) (for the version with no
arguments) or pred(*i, *(i - 1)) (for the version with a predicate argument) holds. Invalidates
only the iterators and references to the erased elements.
18
Throws: Nothing unless an exception is thrown by the equality comparison or the predicate.
19
Complexity: If the range [first, last) is not empty, exactly (last - first) - 1 applications of
the corresponding predicate, otherwise no applications of the predicate.
void merge(forward_list& x);
§ 26.3.9.6
796
void merge(forward_list&& x);
template<class Compare> void merge(forward_list& x, Compare comp);
template<class Compare> void merge(forward_list&& x, Compare comp);
20
Requires: *this and x are both sorted with respect to the comparator operator< (for the first two
overloads) or comp (for the last two overloads), and get_allocator() == x.get_allocator() is true.
21
Effects: Merges the two sorted ranges [begin(), end()) and [x.begin(), x.end()). x is empty
after the merge. If an exception is thrown other than by a comparison there are no effects. Pointers
and references to the moved elements of x now refer to those same elements but as members of *this.
Iterators referring to the moved elements will continue to refer to their elements, but they now behave
as iterators into *this, not into x.
22
Remarks: Stable (20.5.5.7). The behavior is undefined if get_allocator() != x.get_allocator().
23
Complexity: At most distance(begin(), end()) + distance(x.begin(), x.end()) - 1 compar-
isons.
void sort();
template<class Compare> void sort(Compare comp);
24
Effects: Sorts the list according to the operator< or the comp function object. If an exception is
thrown, the order of the elements in *this is unspecified. Does not affect the validity of iterators and
references.
25
Remarks: Stable (20.5.5.7).
26
Complexity: Approximately N log N comparisons, where N is distance(begin(), end()).
void reverse() noexcept;
27
Effects: Reverses the order of the elements in the list. Does not affect the validity of iterators and
references.
28
Complexity: Linear time.
26.3.9.7
forward_list specialized algorithms
[forwardlist.spec]
template<class T, class Allocator>
void swap(forward_list<T, Allocator>& x, forward_list<T, Allocator>& y)
noexcept(noexcept(x.swap(y)));
1
Effects: As if by x.swap(y).
26.3.10
Class template list
[list]
26.3.10.1
Class template list overview
[list.overview]
1
A list is a sequence container that supports bidirectional iterators and allows constant time insert and
erase operations anywhere within the sequence, with storage management handled automatically. Unlike
vectors (26.3.11) and deques (26.3.8), fast random access to list elements is not supported, but many
algorithms only need sequential access anyway.
2
A list satisfies all of the requirements of a container, of a reversible container (given in two tables in 26.2),
of a sequence container, including most of the optional sequence container requirements (26.2.3), and of an
allocator-aware container (Table 86). The exceptions are the operator[] and at member functions, which
are not provided.261 Descriptions are provided here only for operations on list that are not described in
one of these tables or for operations where there is additional semantic information.
namespace std {
template<class T, class Allocator = allocator<T>>
class list {
public:
// types
using value_type
= T;
using allocator_type
= Allocator;
using pointer
= typename allocator_traits<Allocator>::pointer;
using const_pointer
= typename allocator_traits<Allocator>::const_pointer;
using reference
= value_type&;
261) These member functions are only provided by containers whose iterators are random access iterators.
§ 26.3.10.1
797
using const_reference
= const value_type&;
using size_type
= implementation-defined ; // see 26.2
using difference_type
= implementation-defined ; // see 26.2
using iterator
= implementation-defined ; // see 26.2
using const_iterator
= implementation-defined ; // see 26.2
using reverse_iterator
= std::reverse_iterator<iterator>;
using const_reverse_iterator = std::reverse_iterator<const_iterator>;
// 26.3.10.2, construct/copy/destroy
list() : list(Allocator()) { }
explicit list(const Allocator&);
explicit list(size_type n, const Allocator& = Allocator());
list(size_type n, const T& value, const Allocator& = Allocator());
template<class InputIterator>
list(InputIterator first, InputIterator last, const Allocator&
=
Allocator());
list(const list& x);
list(list&& x);
list(const list&, const Allocator&);
list(list&&, const Allocator&);
list(initializer_list<T>, const Allocator& = Allocator());
~list();
list& operator=(const list& x);
list& operator=(list&& x)
noexcept(allocator_traits<Allocator>::is_always_equal::value);
list& operator=(initializer_list<T>);
template<class InputIterator>
void assign(InputIterator first, InputIterator
last);
void assign(size_type n, const T& t);
void assign(initializer_list<T>);
allocator_type get_allocator() const noexcept;
// iterators
iterator
begin() noexcept;
const_iterator
begin() const noexcept;
iterator
end() noexcept;
const_iterator
end() const noexcept;
reverse_iterator
rbegin() noexcept;
const_reverse_iterator rbegin() const noexcept;
reverse_iterator
rend() noexcept;
const_reverse_iterator rend() const noexcept;
const_iterator
cbegin() const noexcept;
const_iterator
cend() const noexcept;
const_reverse_iterator crbegin() const noexcept;
const_reverse_iterator crend() const noexcept;
// 26.3.10.3, capacity
[[nodiscard]] bool empty() const noexcept;
size_type size() const noexcept;
size_type max_size() const noexcept;
void
resize(size_type sz);
void
resize(size_type sz, const T& c);
// element access
reference
front();
const_reference front() const;
reference
back();
const_reference back() const;
// 26.3.10.4, modifiers
template<class... Args> reference emplace_front(Args&&...
args);
template<class... Args> reference emplace_back(Args&&... args);
void push_front(const T& x);
void push_front(T&& x);
§
26.3.10.1
798
void pop_front();
void push_back(const T& x);
void push_back(T&& x);
void pop_back();
template<class... Args> iterator emplace(const_iterator position, Args&&... args);
iterator insert(const_iterator position, const T& x);
iterator insert(const_iterator position, T&& x);
iterator insert(const_iterator position, size_type n, const T& x);
template<class InputIterator>
iterator insert(const_iterator position, InputIterator first, InputIterator last);
iterator insert(const_iterator position, initializer_list<T> il);
iterator erase(const_iterator position);
iterator erase(const_iterator position, const_iterator last);
void
swap(list&) noexcept(allocator_traits<Allocator>::is_always_equal::value);
void
clear() noexcept;
// 26.3.10.5, list operations
void splice(const_iterator position, list& x);
void splice(const_iterator position, list&& x);
void splice(const_iterator position, list& x, const_iterator i);
void splice(const_iterator position, list&& x, const_iterator i);
void splice(const_iterator position, list& x, const_iterator first, const_iterator last);
void splice(const_iterator position, list&& x, const_iterator first, const_iterator last);
void remove(const T& value);
template<class Predicate> void remove_if(Predicate pred);
void unique();
template<class BinaryPredicate>
void unique(BinaryPredicate binary_pred);
void merge(list& x);
void merge(list&& x);
template<class Compare> void merge(list& x, Compare comp);
template<class Compare> void merge(list&& x, Compare comp);
void sort();
template<class Compare> void sort(Compare comp);
void reverse() noexcept;
};
template<class InputIterator,
class Allocator = allocator<typename iterator_traits<InputIterator>::value_type>>
list(InputIterator, InputIterator, Allocator = Allocator())
-> list<typename iterator_traits<InputIterator>::value_type, Allocator>;
// 26.3.10.6, specialized algorithms
template<class T, class Allocator>
void swap(list<T, Allocator>& x, list<T, Allocator>& y)
noexcept(noexcept(x.swap(y)));
}
3
An incomplete type T may be used when instantiating list if the allocator satisfies the allocator completeness
requirements (20.5.3.5.1). T shall be complete before any member of the resulting specialization of list is
referenced.
26.3.10.2
list constructors, copy, and assignment
[list.cons]
explicit list(const Allocator&);
1
Effects: Constructs an empty list, using the specified allocator.
2
Complexity: Constant.
§ 26.3.10.2
799
explicit list(size_type n, const Allocator& = Allocator());
3
Effects: Constructs a list with n default-inserted elements using the specified allocator.
4
Requires: T shall be DefaultInsertable into *this.
5
Complexity: Linear in n.
list(size_type n, const T& value, const Allocator& = Allocator());
6
Effects: Constructs a list with n copies of value, using the specified allocator.
7
Requires: T shall be CopyInsertable into *this.
8
Complexity: Linear in n.
template<class InputIterator>
list(InputIterator first, InputIterator last, const Allocator& = Allocator());
9
Effects: Constructs a list equal to the range [first, last).
10
Complexity: Linear in distance(first, last).
26.3.10.3
list capacity
[list.capacity]
void resize(size_type sz);
1
Effects: If size() < sz, appends sz - size() default-inserted elements to the sequence. If sz <=
size(), equivalent to:
list<T>::iterator it = begin();
advance(it, sz);
erase(it, end());
2
Requires: T shall be DefaultInsertable into *this.
void resize(size_type sz, const T& c);
3
Effects: As if by:
if (sz > size())
insert(end(), sz-size(), c);
else if (sz < size()) {
iterator i = begin();
advance(i, sz);
erase(i, end());
}
else
;
// do nothing
4
Requires: T shall be CopyInsertable into *this.
26.3.10.4
list modifiers
[list.modifiers]
iterator insert(const_iterator position, const T& x);
iterator insert(const_iterator position, T&& x);
iterator insert(const_iterator position, size_type n, const T& x);
template<class InputIterator>
iterator insert(const_iterator position, InputIterator first,
InputIterator last);
iterator insert(const_iterator position, initializer_list<T>);
template<class... Args> reference emplace_front(Args&&... args);
template<class... Args> reference emplace_back(Args&&... args);
template<class... Args> iterator emplace(const_iterator position, Args&&...
args);
void push_front(const T& x);
void push_front(T&& x);
void push_back(const T& x);
void push_back(T&& x);
1
Remarks: Does not affect the validity of iterators and references. If an exception is thrown there are no
effects.
§ 26.3.10.4
800
2
Complexity: Insertion of a single element into a list takes constant time and exactly one call to a
constructor of T. Insertion of multiple elements into a list is linear in the number of elements inserted,
and the number of calls to the copy constructor or move constructor of T is exactly equal to the number
of elements inserted.
iterator erase(const_iterator position);
iterator erase(const_iterator first, const_iterator last);
void pop_front();
void pop_back();
void clear() noexcept;
3
Effects: Invalidates only the iterators and references to the erased elements.
4
Throws: Nothing.
5
Complexity: Erasing a single element is a constant time operation with a single call to the destructor
of T. Erasing a range in a list is linear time in the size of the range and the number of calls to the
destructor of type T is exactly equal to the size of the range.
26.3.10.5
list operations
[list.ops]
1
Since lists allow fast insertion and erasing from the middle of a list, certain operations are provided specifically
for them.262 In this subclause, arguments for a template parameter named Predicate or BinaryPredicate
shall meet the corresponding requirements in 28.3. For merge and sort, the definitions and requirements in
28.7 apply.
2
list provides three splice operations that destructively move elements from one list to another. The behavior
of splice operations is undefined if get_allocator() != x.get_allocator().
void
splice(const_iterator position, list& x);
void
splice(const_iterator position, list&& x);
3
Requires: &x != this.
4
Effects: Inserts the contents of x before position and x becomes empty. Pointers and references to the
moved elements of x now refer to those same elements but as members of *this. Iterators referring
to the moved elements will continue to refer to their elements, but they now behave as iterators into
*this, not into x.
5
Throws: Nothing.
6
Complexity: Constant time.
void
splice(const_iterator position, list& x, const_iterator i);
void
splice(const_iterator position, list&& x, const_iterator i);
7
Requires: i is a valid dereferenceable iterator of x.
8
Effects: Inserts an element pointed to by i from list x before position and removes the element from
x. The result is unchanged if position == i or position == ++i. Pointers and references to *i
continue to refer to this same element but as a member of *this. Iterators to *i (including i itself)
continue to refer to the same element, but now behave as iterators into *this, not into x.
9
Throws: Nothing.
10
Complexity: Constant time.
void
splice(const_iterator position, list& x, const_iterator first,
const_iterator last);
void
splice(const_iterator position, list&& x, const_iterator first,
const_iterator last);
11
Requires: [first, last) is a valid range in x. The program has undefined behavior if position is an
iterator in the range [first, last).
12
Effects: Inserts elements in the range [first, last) before position and removes the elements from
x. Pointers and references to the moved elements of x now refer to those same elements but as members
262) As specified in 20.5.3.5, the requirements in this Clause apply only to lists whose allocators compare equal.
§ 26.3.10.5
801

 

 

 

 

 

 

 

Content      ..     25      26      27      28     ..