Working Draft, Standard for Programming Language C++ (N4713, 2017 year) - page 29
template<class InputIterator,
class Hash = hash<iter_key_t<InputIterator>>,
class Pred = equal_to<iter_key_t<InputIterator>>,
class Allocator = allocator<iter_to_alloc_t<InputIterator>>>
unordered_map(InputIterator, InputIterator, typename see below ::size_type = see below ,
Hash = Hash(), Pred = Pred(), Allocator = Allocator())
-> unordered_map<iter_key_t<InputIterator>, iter_val_t<InputIterator>, Hash, Pred,
Allocator>;
template<class Key, class T, class Hash = hash<Key>,
class Pred = equal_to<Key>, class Allocator = allocator<pair<const Key, T>>>
unordered_map(initializer_list<pair<const Key, T>>,
typename see below ::size_type = see below , Hash = Hash(),
Pred = Pred(), Allocator = Allocator())
-> unordered_map<Key, T, Hash, Pred, Allocator>;
template<class InputIterator, class Allocator>
unordered_map(InputIterator, InputIterator, typename see below ::size_type, Allocator)
-> unordered_map<iter_key_t<InputIterator>, iter_val_t<InputIterator>,
hash<iter_key_t<InputIterator>>, equal_to<iter_key_t<InputIterator>>,
Allocator>;
template<class InputIterator, class Allocator>
unordered_map(InputIterator, InputIterator, Allocator)
-> unordered_map<iter_key_t<InputIterator>, iter_val_t<InputIterator>,
hash<iter_key_t<InputIterator>>, equal_to<iter_key_t<InputIterator>>,
Allocator>;
template<class InputIterator, class Hash, class Allocator>
unordered_map(InputIterator, InputIterator, typename see below ::size_type, Hash, Allocator)
-> unordered_map<iter_key_t<InputIterator>, iter_val_t<InputIterator>, Hash,
equal_to<iter_key_t<InputIterator>>, Allocator>;
template<class Key, class T, class Allocator>
unordered_map(initializer_list<pair<const Key, T>>, typename see below ::size_type,
Allocator)
-> unordered_map<Key, T, hash<Key>, equal_to<Key>, Allocator>;
template<class Key, class T, class Allocator>
unordered_map(initializer_list<pair<const Key, T>>, Allocator)
-> unordered_map<Key, T, hash<Key>, equal_to<Key>, Allocator>;
template<class Key, class T, class Hash, class Allocator>
unordered_map(initializer_list<pair<const Key, T>>, typename see below ::size_type, Hash,
Allocator)
-> unordered_map<Key, T, Hash, equal_to<Key>, Allocator>;
// 26.5.4.5, swap
template<class Key, class T, class Hash, class Pred, class Alloc>
void swap(unordered_map<Key, T, Hash, Pred, Alloc>& x,
unordered_map<Key, T, Hash, Pred, Alloc>& y)
noexcept(noexcept(x.swap(y)));
}
4
A size_type parameter type in an unordered_map deduction guide refers to the size_type member type
of the type deduced by the deduction guide.
26.5.4.2
unordered_map constructors
[unord.map.cnstr]
unordered_map() : unordered_map(size_type(see below )) { }
explicit unordered_map(size_type n,
const hasher& hf = hasher(),
const key_equal& eql = key_equal(),
§ 26.5.4.2
832
const allocator_type& a = allocator_type());
1
Effects: Constructs an empty unordered_map using the specified hash function, key equality predicate,
and allocator, and using at least n buckets. For the default constructor, the number of buckets is
implementation-defined. max_load_factor() returns 1.0.
2
Complexity: Constant.
template<class InputIterator>
unordered_map(InputIterator f, InputIterator l,
size_type n = see below ,
const hasher& hf = hasher(),
const key_equal& eql = key_equal(),
const allocator_type& a = allocator_type());
unordered_map(initializer_list<value_type> il,
size_type n = see below ,
const hasher& hf = hasher(),
const key_equal& eql = key_equal(),
const allocator_type& a = allocator_type());
3
Effects: Constructs an empty unordered_map using the specified hash function, key equality predicate,
and allocator, and using at least n buckets. If n is not provided, the number of buckets is implementation-
defined. Then inserts elements from the range [f, l) for the first form, or from the range [il.begin(),
il.end()) for the second form. max_load_factor() returns 1.0.
4
Complexity: Average case linear, worst case quadratic.
26.5.4.3
unordered_map element access
[unord.map.elem]
mapped_type& operator[](const key_type& k);
1
Effects: Equivalent to: return try_emplace(k).first->second;
mapped_type& operator[](key_type&& k);
2
Effects: Equivalent to: return try_emplace(move(k)).first->second;
mapped_type& at(const key_type& k);
const mapped_type& at(const key_type& k) const;
3
Returns: A reference to x.second, where x is the (unique) element whose key is equivalent to k.
4
Throws: An exception object of type out_of_range if no such element is present.
26.5.4.4
unordered_map modifiers
[unord.map.modifiers]
template<class P>
pair<iterator, bool> insert(P&& obj);
1
Effects: Equivalent to: return emplace(std::forward<P>(obj));
2
Remarks: This signature shall not participate in overload resolution unless is_constructible_-
v<value_type, P&&> is true.
template<class P>
iterator insert(const_iterator hint, P&& obj);
3
Effects: Equivalent to: return emplace_hint(hint, std::forward<P>(obj));
4
Remarks: This signature shall not participate in overload resolution unless is_constructible_-
v<value_type, P&&> is true.
template<class... Args>
pair<iterator, bool> try_emplace(const key_type& k, Args&&... args);
template<class... Args>
iterator try_emplace(const_iterator hint, const key_type& k, Args&&... args);
5
Requires: value_type shall be EmplaceConstructible into unordered_map from piecewise_con-
struct, forward_as_tuple(k), forward_as_tuple(std::forward<Args>(args)...).
§ 26.5.4.4
833
6
Effects: If the map already contains an element whose key is equivalent to k, there is no effect. Otherwise
inserts an object of type value_type constructed with piecewise_construct, forward_as_tuple(k),
forward_as_tuple(std::forward<Args>(args)...).
7
Returns: In the first overload, the bool component of the returned pair is true if and only if the
insertion took place. The returned iterator points to the map element whose key is equivalent to k.
8
Complexity: The same as emplace and emplace_hint, respectively.
template<class... Args>
pair<iterator, bool> try_emplace(key_type&& k, Args&&... args);
template<class... Args>
iterator try_emplace(const_iterator hint, key_type&& k, Args&&... args);
9
Requires: value_type shall be EmplaceConstructible into unordered_map from piecewise_con-
struct, forward_as_tuple(std::move(k)), forward_as_tuple(std::forward<Args>(args)...).
10
Effects: If the map already contains an element whose key is equivalent to k, there is no effect.
Otherwise inserts an object of type value_type constructed with piecewise_construct, forward_-
as_tuple(std::move(k)), forward_as_tuple(std::forward<Args>(args)...).
11
Returns: In the first overload, the bool component of the returned pair is true if and only if the
insertion took place. The returned iterator points to the map element whose key is equivalent to k.
12
Complexity: The same as emplace and emplace_hint, respectively.
template<class M>
pair<iterator, bool> insert_or_assign(const key_type& k, M&& obj);
template<class M>
iterator insert_or_assign(const_iterator hint, const key_type& k, M&& obj);
13
Requires: is_assignable_v<mapped_type&, M&&> shall be true. value_type shall be Emplace-
Constructible into unordered_map from k, std::forward<M>(obj).
14
Effects: If the map already contains an element e whose key is equivalent to k, assigns std::for-
ward<M>(obj) to e.second. Otherwise inserts an object of type value_type constructed with k,
std::forward<M>(obj).
15
Returns: In the first overload, the bool component of the returned pair is true if and only if the
insertion took place. The returned iterator points to the map element whose key is equivalent to k.
16
Complexity: The same as emplace and emplace_hint, respectively.
template<class M>
pair<iterator, bool> insert_or_assign(key_type&& k, M&& obj);
template<class M>
iterator insert_or_assign(const_iterator hint, key_type&& k, M&& obj);
17
Requires: is_assignable_v<mapped_type&, M&&> shall be true. value_type shall be Emplace-
Constructible into unordered_map from std::move(k), std::forward<M>(obj).
18
Effects: If the map already contains an element e whose key is equivalent to k, assigns std::for-
ward<M>(obj) to e.second. Otherwise inserts an object of type value_type constructed with std::
move(k), std::forward<M>(obj).
19
Returns: In the first overload, the bool component of the returned pair is true if and only if the
insertion took place. The returned iterator points to the map element whose key is equivalent to k.
20
Complexity: The same as emplace and emplace_hint, respectively.
26.5.4.5
unordered_map swap
[unord.map.swap]
template<class Key, class T, class Hash, class Pred, class Alloc>
void swap(unordered_map<Key, T, Hash, Pred, Alloc>& x,
unordered_map<Key, T, Hash, Pred, Alloc>& y)
noexcept(noexcept(x.swap(y)));
1
Effects: As if by x.swap(y).
§ 26.5.4.5
834
26.5.5
Class template unordered_multimap
[unord.multimap]
26.5.5.1
Class template unordered_multimap overview
[unord.multimap.overview]
1
An unordered_multimap is an unordered associative container that supports equivalent keys (an instance of
unordered_multimap may contain multiple copies of each key value) and that associates values of another
type mapped_type with the keys. The unordered_multimap class supports forward iterators.
2
An unordered_multimap satisfies all of the requirements of a container, of an unordered associative container,
and of an allocator-aware container (Table 86). It provides the operations described in the preceding
requirements table for equivalent keys; that is, an unordered_multimap supports the a_eq operations in that
table, not the a_uniq operations. For an unordered_multimap<Key, T> the key type is Key, the mapped
type is T, and the value type is pair<const Key, T>.
3
This subclause only describes operations on unordered_multimap that are not described in one of the
requirement tables, or for which there is additional semantic information.
namespace std {
template<class Key,
class T,
class Hash = hash<Key>,
class Pred = equal_to<Key>,
class Allocator = allocator<pair<const Key, T>>>
class unordered_multimap {
public:
// types
using key_type
= Key;
using mapped_type
= T;
using value_type
= pair<const Key, T>;
using hasher
= Hash;
using key_equal
= Pred;
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 local_iterator
= implementation-defined ; // see 26.2
using const_local_iterator = implementation-defined ; // see 26.2
using node_type
= unspecified ;
// 26.5.5.2, construct/copy/destroy
unordered_multimap();
explicit unordered_multimap(size_type n,
const hasher& hf = hasher(),
const key_equal& eql = key_equal(),
const allocator_type& a = allocator_type());
template<class InputIterator>
unordered_multimap(InputIterator f, InputIterator l,
size_type n = see below ,
const hasher& hf = hasher(),
const key_equal& eql = key_equal(),
const allocator_type& a = allocator_type());
unordered_multimap(const unordered_multimap&);
unordered_multimap(unordered_multimap&&);
explicit unordered_multimap(const Allocator&);
unordered_multimap(const unordered_multimap&, const Allocator&);
unordered_multimap(unordered_multimap&&, const Allocator&);
unordered_multimap(initializer_list<value_type> il,
size_type n = see below ,
const hasher& hf = hasher(),
const key_equal& eql = key_equal(),
§
26.5.5.1
835
const allocator_type& a = allocator_type());
unordered_multimap(size_type n, const allocator_type& a)
: unordered_multimap(n, hasher(), key_equal(), a) { }
unordered_multimap(size_type n, const hasher& hf, const allocator_type& a)
: unordered_multimap(n, hf, key_equal(), a) { }
template<class InputIterator>
unordered_multimap(InputIterator f, InputIterator l, size_type n, const allocator_type&
a)
: unordered_multimap(f, l, n, hasher(), key_equal(), a) { }
template<class InputIterator>
unordered_multimap(InputIterator f, InputIterator l, size_type n, const hasher& hf,
const allocator_type& a)
: unordered_multimap(f, l, n, hf, key_equal(), a) { }
unordered_multimap(initializer_list<value_type> il, size_type n, const
allocator_type&
a)
: unordered_multimap(il, n, hasher(), key_equal(), a) { }
unordered_multimap(initializer_list<value_type> il, size_type n, const
hasher& hf,
const allocator_type& a)
: unordered_multimap(il, n, hf, key_equal(), a) { }
~unordered_multimap();
unordered_multimap& operator=(const unordered_multimap&);
unordered_multimap& operator=(unordered_multimap&&)
noexcept(allocator_traits<Allocator>::is_always_equal::value &&
is_nothrow_move_assignable_v<Hash> &&
is_nothrow_move_assignable_v<Pred>);
unordered_multimap& operator=(initializer_list<value_type>);
allocator_type get_allocator() const noexcept;
// iterators
iterator
begin() noexcept;
const_iterator begin() const noexcept;
iterator
end() noexcept;
const_iterator end() const noexcept;
const_iterator cbegin() const noexcept;
const_iterator cend() const noexcept;
// capacity
[[nodiscard]] bool empty() const noexcept;
size_type size() const noexcept;
size_type max_size() const noexcept;
// 26.5.5.3, modifiers
template<class... Args> iterator emplace(Args&&... args);
template<class... Args> iterator emplace_hint(const_iterator position,
Args&&...
args);
iterator insert(const value_type& obj);
iterator insert(value_type&& obj);
template<class P> iterator insert(P&& obj);
iterator insert(const_iterator hint, const value_type& obj);
iterator insert(const_iterator hint, value_type&& obj);
template<class P> iterator insert(const_iterator hint, P&& obj);
template<class InputIterator> void insert(InputIterator first, InputIterator last);
void insert(initializer_list<value_type>);
node_type extract(const_iterator position);
node_type extract(const key_type& x);
iterator insert(node_type&& nh);
iterator insert(const_iterator hint, node_type&& nh);
iterator erase(iterator position);
iterator erase(const_iterator position);
size_type erase(const key_type& k);
iterator erase(const_iterator first, const_iterator last);
void
swap(unordered_multimap&)
noexcept(allocator_traits<Allocator>::is_always_equal::value &&
is_nothrow_swappable_v<Hash> &&
is_nothrow_swappable_v<Pred>);
§
26.5.5.1
836
void
clear() noexcept;
template<class H2, class P2>
void merge(unordered_multimap<Key, T, H2, P2, Allocator>& source);
template<class H2, class P2>
void merge(unordered_multimap<Key, T, H2, P2, Allocator>&& source);
template<class H2, class P2>
void merge(unordered_map<Key, T, H2, P2, Allocator>& source);
template<class H2, class P2>
void merge(unordered_map<Key, T, H2, P2, Allocator>&& source);
// observers
hasher hash_function() const;
key_equal key_eq() const;
// map operations
iterator
find(const key_type& k);
const_iterator find(const key_type& k) const;
size_type
count(const key_type& k) const;
pair<iterator, iterator>
equal_range(const
key_type&
k);
pair<const_iterator, const_iterator> equal_range(const
key_type&
k) const;
// bucket interface
size_type bucket_count() const noexcept;
size_type max_bucket_count() const noexcept;
size_type bucket_size(size_type n) const;
size_type bucket(const key_type& k) const;
local_iterator begin(size_type n);
const_local_iterator begin(size_type n) const;
local_iterator end(size_type n);
const_local_iterator end(size_type n) const;
const_local_iterator cbegin(size_type n) const;
const_local_iterator cend(size_type n) const;
// hash policy
float load_factor() const noexcept;
float max_load_factor() const noexcept;
void max_load_factor(float z);
void rehash(size_type n);
void reserve(size_type n);
};
template<class InputIterator,
class Hash = hash<iter_key_t<InputIterator>>,
class Pred = equal_to<iter_key_t<InputIterator>>,
class Allocator = allocator<iter_to_alloc_t<InputIterator>>>
unordered_multimap(InputIterator, InputIterator,
typename see below ::size_type = see below ,
Hash = Hash(), Pred = Pred(), Allocator = Allocator())
-> unordered_multimap<iter_key_t<InputIterator>, iter_val_t<InputIterator>,
Hash,
Pred,
Allocator>;
template<class Key, class T, class Hash = hash<Key>,
class Pred = equal_to<Key>, class Allocator = allocator<pair<const Key, T>>>
unordered_multimap(initializer_list<pair<const Key, T>>,
typename see below ::size_type = see below ,
Hash = Hash(), Pred = Pred(), Allocator = Allocator())
-> unordered_multimap<Key, T, Hash, Pred, Allocator>;
template<class InputIterator, class Allocator>
unordered_multimap(InputIterator, InputIterator, typename see below ::size_type, Allocator)
-> unordered_multimap<iter_key_t<InputIterator>, iter_val_t<InputIterator>,
hash<iter_key_t<InputIterator>>,
equal_to<iter_key_t<InputIterator>>, Allocator>;
§
26.5.5.1
837
template<class InputIterator, class Allocator>
unordered_multimap(InputIterator, InputIterator, Allocator)
-> unordered_multimap<iter_key_t<InputIterator>, iter_val_t<InputIterator>,
hash<iter_key_t<InputIterator>>,
equal_to<iter_key_t<InputIterator>>, Allocator>;
template<class InputIterator, class Hash, class Allocator>
unordered_multimap(InputIterator, InputIterator, typename see below ::size_type, Hash,
Allocator)
-> unordered_multimap<iter_key_t<InputIterator>, iter_val_t<InputIterator>, Hash,
equal_to<iter_key_t<InputIterator>>, Allocator>;
template<class Key, class T, class Allocator>
unordered_multimap(initializer_list<pair<const Key, T>>, typename see below ::size_type,
Allocator)
-> unordered_multimap<Key, T, hash<Key>, equal_to<Key>, Allocator>;
template<class Key, class T, class Allocator>
unordered_multimap(initializer_list<pair<const Key, T>>, Allocator)
-> unordered_multimap<Key, T, hash<Key>, equal_to<Key>, Allocator>;
template<class Key, class T, class Hash, class Allocator>
unordered_multimap(initializer_list<pair<const Key, T>>, typename see below ::size_type,
Hash, Allocator)
-> unordered_multimap<Key, T, Hash, equal_to<Key>, Allocator>;
// 26.5.5.4, swap
template<class Key, class T, class Hash, class Pred, class Alloc>
void swap(unordered_multimap<Key, T, Hash, Pred, Alloc>& x,
unordered_multimap<Key, T, Hash, Pred, Alloc>& y)
noexcept(noexcept(x.swap(y)));
}
4
A size_type parameter type in an unordered_multimap deduction guide refers to the size_type member
type of the type deduced by the deduction guide.
26.5.5.2
unordered_multimap constructors
[unord.multimap.cnstr]
unordered_multimap() : unordered_multimap(size_type(see below )) { }
explicit unordered_multimap(size_type n,
const hasher& hf = hasher(),
const key_equal& eql = key_equal(),
const allocator_type& a = allocator_type());
1
Effects: Constructs an empty unordered_multimap using the specified hash function, key equality
predicate, and allocator, and using at least n buckets. For the default constructor, the number of
buckets is implementation-defined. max_load_factor() returns 1.0.
2
Complexity: Constant.
template<class InputIterator>
unordered_multimap(InputIterator f, InputIterator l,
size_type n = see below ,
const hasher& hf = hasher(),
const key_equal& eql = key_equal(),
const allocator_type& a = allocator_type());
unordered_multimap(initializer_list<value_type> il,
size_type n = see below ,
const hasher& hf = hasher(),
const key_equal& eql = key_equal(),
const allocator_type& a = allocator_type());
3
Effects: Constructs an empty unordered_multimap using the specified hash function, key equality
predicate, and allocator, and using at least n buckets. If n is not provided, the number of buckets is
implementation-defined. Then inserts elements from the range [f, l) for the first form, or from the
range [il.begin(), il.end()) for the second form. max_load_factor() returns 1.0.
§ 26.5.5.2
838
4
Complexity: Average case linear, worst case quadratic.
26.5.5.3
unordered_multimap modifiers
[unord.multimap.modifiers]
template<class P>
iterator insert(P&& obj);
1
Effects: Equivalent to: return emplace(std::forward<P>(obj));
2
Remarks: This signature shall not participate in overload resolution unless is_constructible_-
v<value_type, P&&> is true.
template<class P>
iterator insert(const_iterator hint, P&& obj);
3
Effects: Equivalent to: return emplace_hint(hint, std::forward<P>(obj));
4
Remarks: This signature shall not participate in overload resolution unless is_constructible_-
v<value_type, P&&> is true.
26.5.5.4
unordered_multimap swap
[unord.multimap.swap]
template<class Key, class T, class Hash, class Pred, class Alloc>
void swap(unordered_multimap<Key, T, Hash, Pred, Alloc>& x,
unordered_multimap<Key, T, Hash, Pred, Alloc>& y)
noexcept(noexcept(x.swap(y)));
1
Effects: As if by x.swap(y).
26.5.6
Class template unordered_set
[unord.set]
26.5.6.1
Class template unordered_set overview
[unord.set.overview]
1
An unordered_set is an unordered associative container that supports unique keys (an unordered_set
contains at most one of each key value) and in which the elements’ keys are the elements themselves. The
unordered_set class supports forward iterators.
2
An unordered_set satisfies all of the requirements of a container, of an unordered associative container, and
of an allocator-aware container (Table 86). It provides the operations described in the preceding requirements
table for unique keys; that is, an unordered_set supports the a_uniq operations in that table, not the a_eq
operations. For an unordered_set<Key> the key type and the value type are both Key. The iterator and
const_iterator types are both constant iterator types. It is unspecified whether they are the same type.
3
This subclause only describes operations on unordered_set that are not described in one of the requirement
tables, or for which there is additional semantic information.
namespace std {
template<class Key,
class Hash = hash<Key>,
class Pred = equal_to<Key>,
class Allocator = allocator<Key>>
class unordered_set {
public:
// types
using key_type
= Key;
using value_type
= Key;
using hasher
= Hash;
using key_equal
= Pred;
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 local_iterator
= implementation-defined ; // see 26.2
using const_local_iterator = implementation-defined ; // see 26.2
§ 26.5.6.1
839
using node_type
= unspecified ;
using insert_return_type
= INSERT_RETURN_TYPE<iterator, node_type>;
// 26.5.6.2, construct/copy/destroy
unordered_set();
explicit unordered_set(size_type n,
const hasher& hf = hasher(),
const key_equal& eql = key_equal(),
const allocator_type& a = allocator_type());
template<class InputIterator>
unordered_set(InputIterator f, InputIterator l,
size_type n = see below ,
const hasher& hf = hasher(),
const key_equal& eql = key_equal(),
const allocator_type& a = allocator_type());
unordered_set(const unordered_set&);
unordered_set(unordered_set&&);
explicit unordered_set(const Allocator&);
unordered_set(const unordered_set&, const Allocator&);
unordered_set(unordered_set&&, const Allocator&);
unordered_set(initializer_list<value_type> il,
size_type n = see below ,
const hasher& hf = hasher(),
const key_equal& eql = key_equal(),
const allocator_type& a = allocator_type());
unordered_set(size_type n, const allocator_type& a)
: unordered_set(n, hasher(), key_equal(), a) { }
unordered_set(size_type n, const hasher& hf, const allocator_type& a)
: unordered_set(n, hf, key_equal(), a) { }
template<class InputIterator>
unordered_set(InputIterator f, InputIterator l, size_type n, const allocator_type&
a)
: unordered_set(f, l, n, hasher(), key_equal(), a) { }
template<class InputIterator>
unordered_set(InputIterator f, InputIterator l, size_type n, const hasher& hf,
const allocator_type& a)
: unordered_set(f, l, n, hf, key_equal(), a) { }
unordered_set(initializer_list<value_type> il, size_type n, const allocator_type&
a)
: unordered_set(il, n, hasher(), key_equal(), a) { }
unordered_set(initializer_list<value_type> il, size_type n, const hasher& hf,
const allocator_type& a)
: unordered_set(il, n, hf, key_equal(), a) { }
~unordered_set();
unordered_set& operator=(const unordered_set&);
unordered_set& operator=(unordered_set&&)
noexcept(allocator_traits<Allocator>::is_always_equal::value &&
is_nothrow_move_assignable_v<Hash> &&
is_nothrow_move_assignable_v<Pred>);
unordered_set& operator=(initializer_list<value_type>);
allocator_type get_allocator() const noexcept;
// iterators
iterator
begin() noexcept;
const_iterator begin() const noexcept;
iterator
end() noexcept;
const_iterator end() const noexcept;
const_iterator cbegin() const noexcept;
const_iterator cend() const noexcept;
// capacity
[[nodiscard]] bool empty() const noexcept;
size_type size() const noexcept;
size_type max_size() const noexcept;
§ 26.5.6.1
840
// modifiers
template<class... Args> pair<iterator, bool> emplace(Args&&... args);
template<class... Args> iterator emplace_hint(const_iterator position, Args&&... args);
pair<iterator, bool> insert(const value_type& obj);
pair<iterator, bool> insert(value_type&& obj);
iterator insert(const_iterator hint, const value_type& obj);
iterator insert(const_iterator hint, value_type&& obj);
template<class InputIterator> void insert(InputIterator first, InputIterator
last);
void insert(initializer_list<value_type>);
node_type extract(const_iterator position);
node_type extract(const key_type& x);
insert_return_type insert(node_type&& nh);
iterator
insert(const_iterator hint, node_type&& nh);
iterator erase(iterator position);
iterator erase(const_iterator position);
size_type erase(const key_type& k);
iterator erase(const_iterator first, const_iterator last);
void
swap(unordered_set&)
noexcept(allocator_traits<Allocator>::is_always_equal::value &&
is_nothrow_swappable_v<Hash> &&
is_nothrow_swappable_v<Pred>);
void
clear() noexcept;
template<class H2, class P2>
void merge(unordered_set<Key, H2, P2, Allocator>& source);
template<class H2, class P2>
void merge(unordered_set<Key, H2, P2, Allocator>&& source);
template<class H2, class P2>
void merge(unordered_multiset<Key, H2, P2, Allocator>& source);
template<class H2, class P2>
void merge(unordered_multiset<Key, H2, P2, Allocator>&& source);
// observers
hasher hash_function() const;
key_equal key_eq() const;
// set operations
iterator
find(const key_type& k);
const_iterator find(const key_type& k) const;
size_type
count(const key_type& k) const;
pair<iterator, iterator>
equal_range(const
key_type&
k);
pair<const_iterator, const_iterator> equal_range(const
key_type&
k) const;
// bucket interface
size_type bucket_count() const noexcept;
size_type max_bucket_count() const noexcept;
size_type bucket_size(size_type n) const;
size_type bucket(const key_type& k) const;
local_iterator begin(size_type n);
const_local_iterator begin(size_type n) const;
local_iterator end(size_type n);
const_local_iterator end(size_type n) const;
const_local_iterator cbegin(size_type n) const;
const_local_iterator cend(size_type n) const;
// hash policy
float load_factor() const noexcept;
float max_load_factor() const noexcept;
void max_load_factor(float z);
void rehash(size_type n);
void reserve(size_type n);
};
§
26.5.6.1
841
template<class InputIterator,
class Hash = hash<typename iterator_traits<InputIterator>::value_type>,
class Pred = equal_to<typename iterator_traits<InputIterator>::value_type>,
class Allocator = allocator<typename iterator_traits<InputIterator>::value_type>>
unordered_set(InputIterator, InputIterator, typename see below ::size_type = see below ,
Hash = Hash(), Pred = Pred(), Allocator = Allocator())
-> unordered_set<typename iterator_traits<InputIterator>::value_type,
Hash, Pred, Allocator>;
template<class T, class Hash = hash<T>,
class Pred = equal_to<T>, class Allocator = allocator<T>>
unordered_set(initializer_list<T>, typename see below ::size_type = see below ,
Hash = Hash(), Pred = Pred(), Allocator = Allocator())
-> unordered_set<T, Hash, Pred, Allocator>;
template<class InputIterator, class Allocator>
unordered_set(InputIterator, InputIterator, typename see below ::size_type, Allocator)
-> unordered_set<typename iterator_traits<InputIterator>::value_type,
hash<typename iterator_traits<InputIterator>::value_type>,
equal_to<typename iterator_traits<InputIterator>::value_type>,
Allocator>;
template<class InputIterator, class Hash, class Allocator>
unordered_set(InputIterator, InputIterator, typename see below ::size_type,
Hash, Allocator)
-> unordered_set<typename iterator_traits<InputIterator>::value_type, Hash,
equal_to<typename iterator_traits<InputIterator>::value_type>,
Allocator>;
template<class T, class Allocator>
unordered_set(initializer_list<T>, typename see below ::size_type, Allocator)
-> unordered_set<T, hash<T>, equal_to<T>, Allocator>;
template<class T, class Hash, class Allocator>
unordered_set(initializer_list<T>, typename see below ::size_type, Hash, Allocator)
-> unordered_set<T, Hash, equal_to<T>, Allocator>;
// 26.5.6.3, swap
template<class Key, class Hash, class Pred, class Alloc>
void swap(unordered_set<Key, Hash, Pred, Alloc>& x,
unordered_set<Key, Hash, Pred, Alloc>& y)
noexcept(noexcept(x.swap(y)));
}
4
A size_type parameter type in an unordered_set deduction guide refers to the size_type member type
of the type deduced by the deduction guide.
26.5.6.2
unordered_set constructors
[unord.set.cnstr]
unordered_set() : unordered_set(size_type(see below )) { }
explicit unordered_set(size_type n,
const hasher& hf = hasher(),
const key_equal& eql = key_equal(),
const allocator_type& a = allocator_type());
1
Effects: Constructs an empty unordered_set using the specified hash function, key equality predicate,
and allocator, and using at least n buckets. For the default constructor, the number of buckets is
implementation-defined. max_load_factor() returns 1.0.
2
Complexity: Constant.
template<class InputIterator>
unordered_set(InputIterator f, InputIterator l,
size_type n = see below ,
const hasher& hf = hasher(),
const key_equal& eql = key_equal(),
§ 26.5.6.2
842
const allocator_type& a = allocator_type());
unordered_set(initializer_list<value_type> il,
size_type n = see below ,
const hasher& hf = hasher(),
const key_equal& eql = key_equal(),
const allocator_type& a = allocator_type());
3
Effects: Constructs an empty unordered_set using the specified hash function, key equality predicate,
and allocator, and using at least n buckets. If n is not provided, the number of buckets is implementation-
defined. Then inserts elements from the range [f, l) for the first form, or from the range [il.begin(),
il.end()) for the second form. max_load_factor() returns 1.0.
4
Complexity: Average case linear, worst case quadratic.
26.5.6.3
unordered_set swap
[unord.set.swap]
template<class Key, class Hash, class Pred, class Alloc>
void swap(unordered_set<Key, Hash, Pred, Alloc>& x,
unordered_set<Key, Hash, Pred, Alloc>& y)
noexcept(noexcept(x.swap(y)));
1
Effects: As if by x.swap(y).
26.5.7
Class template unordered_multiset
[unord.multiset]
26.5.7.1
Class template unordered_multiset overview
[unord.multiset.overview]
1
An unordered_multiset is an unordered associative container that supports equivalent keys (an instance of
unordered_multiset may contain multiple copies of the same key value) and in which each element’s key is
the element itself. The unordered_multiset class supports forward iterators.
2
An unordered_multiset satisfies all of the requirements of a container, of an unordered associative container,
and of an allocator-aware container (Table 86). It provides the operations described in the preceding
requirements table for equivalent keys; that is, an unordered_multiset supports the a_eq operations in
that table, not the a_uniq operations. For an unordered_multiset<Key> the key type and the value type
are both Key. The iterator and const_iterator types are both constant iterator types. It is unspecified
whether they are the same type.
3
This subclause only describes operations on unordered_multiset that are not described in one of the
requirement tables, or for which there is additional semantic information.
namespace std {
template<class Key,
class Hash = hash<Key>,
class Pred = equal_to<Key>,
class Allocator = allocator<Key>>
class unordered_multiset {
public:
// types
using key_type
= Key;
using value_type
= Key;
using hasher
= Hash;
using key_equal
= Pred;
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 local_iterator
= implementation-defined ; // see 26.2
using const_local_iterator = implementation-defined ; // see 26.2
using node_type
= unspecified ;
§ 26.5.7.1
843
// 26.5.7.2, construct/copy/destroy
unordered_multiset();
explicit unordered_multiset(size_type n,
const hasher& hf = hasher(),
const key_equal& eql = key_equal(),
const allocator_type& a = allocator_type());
template<class InputIterator>
unordered_multiset(InputIterator f, InputIterator l,
size_type n = see below ,
const hasher& hf = hasher(),
const key_equal& eql = key_equal(),
const allocator_type& a = allocator_type());
unordered_multiset(const unordered_multiset&);
unordered_multiset(unordered_multiset&&);
explicit unordered_multiset(const Allocator&);
unordered_multiset(const unordered_multiset&, const Allocator&);
unordered_multiset(unordered_multiset&&, const Allocator&);
unordered_multiset(initializer_list<value_type> il,
size_type n = see below ,
const hasher& hf = hasher(),
const key_equal& eql = key_equal(),
const allocator_type& a = allocator_type());
unordered_multiset(size_type n, const allocator_type& a)
: unordered_multiset(n, hasher(), key_equal(), a) { }
unordered_multiset(size_type n, const hasher& hf, const allocator_type& a)
: unordered_multiset(n, hf, key_equal(), a) { }
template<class InputIterator>
unordered_multiset(InputIterator f, InputIterator l, size_type n, const allocator_type&
a)
: unordered_multiset(f, l, n, hasher(), key_equal(), a) { }
template<class InputIterator>
unordered_multiset(InputIterator f, InputIterator l, size_type n, const hasher& hf,
const allocator_type& a)
: unordered_multiset(f, l, n, hf, key_equal(), a) { }
unordered_multiset(initializer_list<value_type> il, size_type n, const
allocator_type&
a)
: unordered_multiset(il, n, hasher(), key_equal(), a) { }
unordered_multiset(initializer_list<value_type> il, size_type n, const
hasher& hf,
const allocator_type& a)
: unordered_multiset(il, n, hf, key_equal(), a) { }
~unordered_multiset();
unordered_multiset& operator=(const unordered_multiset&);
unordered_multiset& operator=(unordered_multiset&&)
noexcept(allocator_traits<Allocator>::is_always_equal::value &&
is_nothrow_move_assignable_v<Hash> &&
is_nothrow_move_assignable_v<Pred>);
unordered_multiset& operator=(initializer_list<value_type>);
allocator_type get_allocator() const noexcept;
// iterators
iterator
begin() noexcept;
const_iterator begin() const noexcept;
iterator
end() noexcept;
const_iterator end() const noexcept;
const_iterator cbegin() const noexcept;
const_iterator cend() const noexcept;
// capacity
[[nodiscard]] bool empty() const noexcept;
size_type size() const noexcept;
size_type max_size() const noexcept;
// modifiers
template<class... Args> iterator emplace(Args&&... args);
template<class... Args> iterator emplace_hint(const_iterator position,
Args&&... args);
iterator insert(const value_type& obj);
§
26.5.7.1
844
iterator insert(value_type&& obj);
iterator insert(const_iterator hint, const value_type& obj);
iterator insert(const_iterator hint, value_type&& obj);
template<class InputIterator> void insert(InputIterator first, InputIterator
last);
void insert(initializer_list<value_type>);
node_type extract(const_iterator position);
node_type extract(const key_type& x);
iterator insert(node_type&& nh);
iterator insert(const_iterator hint, node_type&& nh);
iterator erase(iterator position);
iterator erase(const_iterator position);
size_type erase(const key_type& k);
iterator erase(const_iterator first, const_iterator last);
void
swap(unordered_multiset&)
noexcept(allocator_traits<Allocator>::is_always_equal::value &&
is_nothrow_swappable_v<Hash> &&
is_nothrow_swappable_v<Pred>);
void
clear() noexcept;
template<class H2, class P2>
void merge(unordered_multiset<Key, H2, P2, Allocator>& source);
template<class H2, class P2>
void merge(unordered_multiset<Key, H2, P2, Allocator>&& source);
template<class H2, class P2>
void merge(unordered_set<Key, H2, P2, Allocator>& source);
template<class H2, class P2>
void merge(unordered_set<Key, H2, P2, Allocator>&& source);
// observers
hasher hash_function() const;
key_equal key_eq() const;
// set operations
iterator
find(const key_type& k);
const_iterator find(const key_type& k) const;
size_type
count(const key_type& k) const;
pair<iterator, iterator>
equal_range(const
key_type&
k);
pair<const_iterator, const_iterator> equal_range(const
key_type&
k) const;
// bucket interface
size_type bucket_count() const noexcept;
size_type max_bucket_count() const noexcept;
size_type bucket_size(size_type n) const;
size_type bucket(const key_type& k) const;
local_iterator begin(size_type n);
const_local_iterator begin(size_type n) const;
local_iterator end(size_type n);
const_local_iterator end(size_type n) const;
const_local_iterator cbegin(size_type n) const;
const_local_iterator cend(size_type n) const;
// hash policy
float load_factor() const noexcept;
float max_load_factor() const noexcept;
void max_load_factor(float z);
void rehash(size_type n);
void reserve(size_type n);
};
§ 26.5.7.1
845
template<class InputIterator,
class Hash = hash<typename iterator_traits<InputIterator>::value_type>,
class Pred = equal_to<typename iterator_traits<InputIterator>::value_type>,
class Allocator = allocator<typename iterator_traits<InputIterator>::value_type>>
unordered_multiset(InputIterator, InputIterator, see below ::size_type = see below ,
Hash = Hash(), Pred = Pred(), Allocator = Allocator())
-> unordered_multiset<typename iterator_traits<InputIterator>::value_type,
Hash, Pred, Allocator>;
template<class T, class Hash = hash<T>,
class Pred = equal_to<T>, class Allocator = allocator<T>>
unordered_multiset(initializer_list<T>, typename see below ::size_type = see below ,
Hash = Hash(), Pred = Pred(), Allocator = Allocator())
-> unordered_multiset<T, Hash, Pred, Allocator>;
template<class InputIterator, class Allocator>
unordered_multiset(InputIterator, InputIterator, typename see below ::size_type, Allocator)
-> unordered_multiset<typename iterator_traits<InputIterator>::value_type,
hash<typename iterator_traits<InputIterator>::value_type>,
equal_to<typename iterator_traits<InputIterator>::value_type>,
Allocator>;
template<class InputIterator, class Hash, class Allocator>
unordered_multiset(InputIterator, InputIterator, typename see below ::size_type,
Hash, Allocator)
-> unordered_multiset<typename iterator_traits<InputIterator>::value_type, Hash,
equal_to<typename iterator_traits<InputIterator>::value_type>,
Allocator>;
template<class T, class Allocator>
unordered_multiset(initializer_list<T>, typename see below ::size_type, Allocator)
-> unordered_multiset<T, hash<T>, equal_to<T>, Allocator>;
template<class T, class Hash, class Allocator>
unordered_multiset(initializer_list<T>, typename see below ::size_type, Hash, Allocator)
-> unordered_multiset<T, Hash, equal_to<T>, Allocator>;
// 26.5.7.3, swap
template<class Key, class Hash, class Pred, class Alloc>
void swap(unordered_multiset<Key, Hash, Pred, Alloc>& x,
unordered_multiset<Key, Hash, Pred, Alloc>& y)
noexcept(noexcept(x.swap(y)));
}
4
A size_type parameter type in an unordered_multiset deduction guide refers to the size_type member
type of the type deduced by the deduction guide.
26.5.7.2
unordered_multiset constructors
[unord.multiset.cnstr]
unordered_multiset() : unordered_multiset(size_type(see below )) { }
explicit unordered_multiset(size_type n,
const hasher& hf = hasher(),
const key_equal& eql = key_equal(),
const allocator_type& a = allocator_type());
1
Effects: Constructs an empty unordered_multiset using the specified hash function, key equality
predicate, and allocator, and using at least n buckets. For the default constructor, the number of
buckets is implementation-defined. max_load_factor() returns 1.0.
2
Complexity: Constant.
template<class InputIterator>
unordered_multiset(InputIterator f, InputIterator l,
size_type n = see below ,
const hasher& hf = hasher(),
const key_equal& eql = key_equal(),
§ 26.5.7.2
846
const allocator_type& a = allocator_type());
unordered_multiset(initializer_list<value_type> il,
size_type n = see below ,
const hasher& hf = hasher(),
const key_equal& eql = key_equal(),
const allocator_type& a = allocator_type());
3
Effects: Constructs an empty unordered_multiset using the specified hash function, key equality
predicate, and allocator, and using at least n buckets. If n is not provided, the number of buckets is
implementation-defined. Then inserts elements from the range [f, l) for the first form, or from the
range [il.begin(), il.end()) for the second form. max_load_factor() returns 1.0.
4
Complexity: Average case linear, worst case quadratic.
26.5.7.3
unordered_multiset swap
[unord.multiset.swap]
template<class Key, class Hash, class Pred, class Alloc>
void swap(unordered_multiset<Key, Hash, Pred, Alloc>& x,
unordered_multiset<Key, Hash, Pred, Alloc>& y)
noexcept(noexcept(x.swap(y)));
1
Effects: As if by x.swap(y).
26.6
Container adaptors
[container.adaptors]
26.6.1
In general
[container.adaptors.general]
1
The headers <queue> and <stack> define the container adaptors queue, priority_queue, and stack.
2
The container adaptors each take a Container template parameter, and each constructor takes a Container
reference argument. This container is copied into the Container member of each adaptor. If the container
takes an allocator, then a compatible allocator may be passed in to the adaptor’s constructor. Otherwise,
normal copy or move construction is used for the container argument. The first template parameter T of the
container adaptors shall denote the same type as Container::value_type.
3
For container adaptors, no swap function throws an exception unless that exception is thrown by the swap of
the adaptor’s Container or Compare object (if any).
4
A deduction guide for a container adaptor shall not participate in overload resolution if any of the following
are true:
(4.1)
—
It has an InputIterator template parameter and a type that does not qualify as an input iterator is
deduced for that parameter.
(4.2)
—
It has a Compare template parameter and a type that qualifies as an allocator is deduced for that
parameter.
(4.3)
—
It has a Container template parameter and a type that qualifies as an allocator is deduced for that
parameter.
(4.4)
—
It has an Allocator template parameter and a type that does not qualify as an allocator is deduced
for that parameter.
(4.5)
—
It has both Container and Allocator template parameters, and uses_allocator_v<Container,
Allocator> is false.
26.6.2
Header <queue> synopsis
[queue.syn]
#include <initializer_list>
namespace std {
template<class T, class Container = deque<T>> class queue;
template<class T, class Container = vector<T>,
class Compare = less<typename Container::value_type>>
class priority_queue;
template<class T, class Container>
bool operator==(const queue<T, Container>& x, const queue<T, Container>& y);
template<class T, class Container>
bool operator< (const queue<T, Container>& x, const queue<T, Container>& y);
§ 26.6.2
847
template<class T, class Container>
bool operator!=(const queue<T, Container>& x, const queue<T, Container>& y);
template<class T, class Container>
bool operator> (const queue<T, Container>& x, const queue<T, Container>& y);
template<class T, class Container>
bool operator>=(const queue<T, Container>& x, const queue<T, Container>& y);
template<class T, class Container>
bool operator<=(const queue<T, Container>& x, const queue<T, Container>& y);
template<class T, class Container>
void swap(queue<T, Container>& x, queue<T, Container>& y) noexcept(noexcept(x.swap(y)));
template<class T, class Container, class Compare>
void swap(priority_queue<T, Container, Compare>& x,
priority_queue<T, Container, Compare>& y) noexcept(noexcept(x.swap(y)));
}
26.6.3
Header <stack> synopsis
[stack.syn]
#include <initializer_list>
namespace std {
template<class T, class Container = deque<T>> class stack;
template<class T, class Container>
bool operator==(const stack<T, Container>& x, const stack<T, Container>& y);
template<class T, class Container>
bool operator< (const stack<T, Container>& x, const stack<T, Container>& y);
template<class T, class Container>
bool operator!=(const stack<T, Container>& x, const stack<T, Container>& y);
template<class T, class Container>
bool operator> (const stack<T, Container>& x, const stack<T, Container>& y);
template<class T, class Container>
bool operator>=(const stack<T, Container>& x, const stack<T, Container>& y);
template<class T, class Container>
bool operator<=(const stack<T, Container>& x, const stack<T, Container>& y);
template<class T, class Container>
void swap(stack<T, Container>& x, stack<T, Container>& y) noexcept(noexcept(x.swap(y)));
}
26.6.4
Class template queue
[queue]
26.6.4.1
queue definition
[queue.defn]
1
Any sequence container supporting operations front(), back(), push_back() and pop_front() can be used
to instantiate queue. In particular, list (26.3.10) and deque (26.3.8) can be used.
namespace std {
template<class T, class Container = deque<T>>
class queue {
public:
using value_type
= typename Container::value_type;
using reference
= typename Container::reference;
using const_reference = typename Container::const_reference;
using size_type
= typename Container::size_type;
using container_type
=
Container;
protected:
Container c;
public:
explicit queue(const Container&);
explicit queue(Container&& = Container());
template<class Alloc> explicit queue(const Alloc&);
template<class Alloc> queue(const Container&, const Alloc&);
template<class Alloc> queue(Container&&, const Alloc&);
§ 26.6.4.1
848
template<class Alloc> queue(const queue&, const Alloc&);
template<class Alloc> queue(queue&&, const Alloc&);
[[nodiscard]] bool empty() const
{ return c.empty(); }
size_type
size() const
{ return c.size(); }
reference
front()
{ return c.front(); }
const_reference
front() const
{ return c.front(); }
reference
back()
{ return c.back(); }
const_reference
back() const
{ return c.back(); }
void push(const value_type& x)
{ c.push_back(x); }
void push(value_type&& x)
{ c.push_back(std::move(x)); }
template<class... Args>
decltype(auto) emplace(Args&&... args)
{ return c.emplace_back(std::forward<Args>(args)...); }
void pop()
{ c.pop_front(); }
void swap(queue& q) noexcept(is_nothrow_swappable_v<Container>)
{ using std::swap; swap(c, q.c); }
};
template<class Container>
queue(Container) -> queue<typename Container::value_type, Container>;
template<class Container, class Allocator>
queue(Container, Allocator) -> queue<typename Container::value_type, Container>;
template<class T, class Container>
void swap(queue<T, Container>& x, queue<T, Container>& y) noexcept(noexcept(x.swap(y)));
template<class T, class Container, class Alloc>
struct uses_allocator<queue<T, Container>, Alloc>
: uses_allocator<Container, Alloc>::type { };
}
26.6.4.2
queue constructors
[queue.cons]
explicit queue(const Container& cont);
1
Effects: Initializes c with cont.
explicit queue(Container&& cont = Container());
2
Effects: Initializes c with std::move(cont).
26.6.4.3
queue constructors with allocators
[queue.cons.alloc]
1
If uses_allocator_v<container_type, Alloc> is false the constructors in this subclause shall not par-
ticipate in overload resolution.
template<class Alloc> explicit queue(const Alloc& a);
2
Effects: Initializes c with a.
template<class Alloc> queue(const container_type& cont, const Alloc& a);
3
Effects: Initializes c with cont as the first argument and a as the second argument.
template<class Alloc> queue(container_type&& cont, const Alloc& a);
4
Effects: Initializes c with std::move(cont) as the first argument and a as the second argument.
template<class Alloc> queue(const queue& q, const Alloc& a);
5
Effects: Initializes c with q.c as the first argument and a as the second argument.
template<class Alloc> queue(queue&& q, const Alloc& a);
6
Effects: Initializes c with std::move(q.c) as the first argument and a as the second argument.
§ 26.6.4.3
849
26.6.4.4
queue operators
[queue.ops]
template<class T, class Container>
bool operator==(const queue<T, Container>& x, const queue<T, Container>& y);
1
Returns: x.c == y.c.
template<class T, class Container>
bool operator!=(const queue<T, Container>& x, const queue<T, Container>& y);
2
Returns: x.c != y.c.
template<class T, class Container>
bool operator< (const queue<T, Container>& x, const queue<T, Container>& y);
3
Returns: x.c < y.c.
template<class T, class Container>
bool operator<=(const queue<T, Container>& x, const queue<T, Container>& y);
4
Returns: x.c <= y.c.
template<class T, class Container>
bool operator> (const queue<T, Container>& x, const queue<T, Container>& y);
5
Returns: x.c > y.c.
template<class T, class Container>
bool operator>=(const queue<T, Container>& x,
const queue<T, Container>& y);
6
Returns: x.c >= y.c.
26.6.4.5
queue specialized algorithms
[queue.special]
template<class T, class Container>
void swap(queue<T, Container>& x, queue<T, Container>& y) noexcept(noexcept(x.swap(y)));
1
Remarks: This function shall not participate in overload resolution unless is_swappable_v<Container>
is true.
2
Effects: As if by x.swap(y).
26.6.5
Class template priority_queue
[priority.queue]
1
Any sequence container with random access iterator and supporting operations front(), push_back() and
pop_back() can be used to instantiate priority_queue. In particular, vector (26.3.11) and deque (26.3.8)
can be used. Instantiating priority_queue also involves supplying a function or function object for
making priority comparisons; the library assumes that the function or function object defines a strict weak
ordering (28.7).
namespace std {
template<class T, class Container = vector<T>,
class Compare = less<typename Container::value_type>>
class priority_queue {
public:
using value_type
= typename Container::value_type;
using reference
= typename Container::reference;
using const_reference = typename Container::const_reference;
using size_type
= typename Container::size_type;
using container_type
= Container;
using value_compare
= Compare;
protected:
Container c;
Compare comp;
public:
priority_queue(const Compare& x, const Container&);
explicit priority_queue(const Compare& x = Compare(), Container&& = Container());
§ 26.6.5
850
template<class InputIterator>
priority_queue(InputIterator first, InputIterator last, const Compare& x,
const Container&);
template<class InputIterator>
priority_queue(InputIterator first, InputIterator last,
const Compare& x = Compare(), Container&& = Container());
template<class Alloc> explicit priority_queue(const Alloc&);
template<class Alloc> priority_queue(const Compare&, const Alloc&);
template<class Alloc> priority_queue(const Compare&, const Container&, const Alloc&);
template<class Alloc> priority_queue(const Compare&, Container&&, const Alloc&);
template<class Alloc> priority_queue(const priority_queue&, const Alloc&);
template<class Alloc> priority_queue(priority_queue&&, const Alloc&);
[[nodiscard]] bool empty() const { return c.empty(); }
size_type size() const
{ return c.size(); }
const_reference top() const
{ return c.front(); }
void push(const value_type& x);
void push(value_type&& x);
template<class... Args> void emplace(Args&&... args);
void pop();
void swap(priority_queue& q) noexcept(is_nothrow_swappable_v<Container> &&
is_nothrow_swappable_v<Compare>)
{ using std::swap; swap(c, q.c); swap(comp, q.comp); }
};
template<class Compare, class Container>
priority_queue(Compare, Container)
-> priority_queue<typename Container::value_type, Container, Compare>;
template<class InputIterator,
class Compare = less<typename iterator_traits<InputIterator>::value_type>,
class Container = vector<typename iterator_traits<InputIterator>::value_type>>
priority_queue(InputIterator, InputIterator, Compare = Compare(), Container = Container())
-> priority_queue<typename iterator_traits<InputIterator>::value_type, Container, Compare>;
template<class Compare, class Container, class Allocator>
priority_queue(Compare, Container, Allocator)
-> priority_queue<typename Container::value_type, Container, Compare>;
// no equality is provided
template<class T, class Container, class Compare>
void swap(priority_queue<T, Container, Compare>& x,
priority_queue<T, Container, Compare>& y) noexcept(noexcept(x.swap(y)));
template<class T, class Container, class Compare, class Alloc>
struct uses_allocator<priority_queue<T, Container, Compare>, Alloc>
: uses_allocator<Container, Alloc>::type { };
}
26.6.5.1
priority_queue constructors
[priqueue.cons]
priority_queue(const Compare& x, const Container& y);
explicit priority_queue(const Compare& x = Compare(), Container&& y = Container());
1
Requires: x shall define a strict weak ordering (28.7).
2
Effects: Initializes comp with x and c with y (copy constructing or move constructing as appropriate);
calls make_heap(c.begin(), c.end(), comp).
template<class InputIterator>
priority_queue(InputIterator first, InputIterator last, const Compare& x, const Container& y);
§ 26.6.5.1
851
template<class InputIterator>
priority_queue(InputIterator first, InputIterator last, const Compare& x = Compare(),
Container&& y = Container());
3
Requires: x shall define a strict weak ordering (28.7).
4
Effects: Initializes comp with x and c with y (copy constructing or move constructing as appropriate);
calls c.insert(c.end(), first, last); and finally calls make_heap(c.begin(), c.end(), comp).
26.6.5.2
priority_queue constructors with allocators
[priqueue.cons.alloc]
1
If uses_allocator_v<container_type, Alloc> is false the constructors in this subclause shall not par-
ticipate in overload resolution.
template<class Alloc> explicit priority_queue(const Alloc& a);
2
Effects: Initializes c with a and value-initializes comp.
template<class Alloc> priority_queue(const Compare& compare, const Alloc& a);
3
Effects: Initializes c with a and initializes comp with compare.
template<class Alloc>
priority_queue(const Compare& compare, const Container& cont, const Alloc& a);
4
Effects: Initializes c with cont as the first argument and a as the second argument, and initializes
comp with compare; calls make_heap(c.begin(), c.end(), comp).
template<class Alloc>
priority_queue(const Compare& compare, Container&& cont, const Alloc& a);
5
Effects: Initializes c with std::move(cont) as the first argument and a as the second argument, and
initializes comp with compare; calls make_heap(c.begin(), c.end(), comp).
template<class Alloc> priority_queue(const priority_queue& q, const Alloc& a);
6
Effects: Initializes c with q.c as the first argument and a as the second argument, and initializes comp
with q.comp.
template<class Alloc> priority_queue(priority_queue&& q,
const Alloc& a);
7
Effects: Initializes c with std::move(q.c) as the first argument and a as the second argument, and
initializes comp with std::move(q.comp).
26.6.5.3
priority_queue members
[priqueue.members]
void push(const value_type& x);
1
Effects: As if by:
c.push_back(x);
push_heap(c.begin(), c.end(), comp);
void push(value_type&& x);
2
Effects: As if by:
c.push_back(std::move(x));
push_heap(c.begin(), c.end(), comp);
template<class... Args> void emplace(Args&&... args)
3
Effects: As if by:
c.emplace_back(std::forward<Args>(args)...);
push_heap(c.begin(), c.end(), comp);
void pop();
4
Effects: As if by:
pop_heap(c.begin(), c.end(), comp);
c.pop_back();
§ 26.6.5.3
852
26.6.5.4
priority_queue specialized algorithms
[priqueue.special]
template<class T, class Container, class Compare>
void swap(priority_queue<T, Container, Compare>& x,
priority_queue<T, Container, Compare>& y) noexcept(noexcept(x.swap(y)));
1
Remarks: This function shall not participate in overload resolution unless is_swappable_v<Container>
is true and is_swappable_v<Compare> is true.
2
Effects: As if by x.swap(y).
26.6.6
Class template stack
[stack]
1
Any sequence container supporting operations back(), push_back() and pop_back() can be used to instan-
tiate stack. In particular, vector (26.3.11), list (26.3.10) and deque (26.3.8) can be used.
26.6.6.1
stack definition
[stack.defn]
namespace std {
template<class T, class Container = deque<T>>
class stack {
public:
using value_type
= typename Container::value_type;
using reference
= typename Container::reference;
using const_reference = typename Container::const_reference;
using size_type
= typename Container::size_type;
using container_type
= Container;
protected:
Container c;
public:
explicit stack(const Container&);
explicit stack(Container&& = Container());
template<class Alloc> explicit stack(const Alloc&);
template<class Alloc> stack(const Container&, const Alloc&);
template<class Alloc> stack(Container&&, const Alloc&);
template<class Alloc> stack(const stack&, const Alloc&);
template<class Alloc> stack(stack&&, const Alloc&);
[[nodiscard]] bool empty() const
{ return c.empty(); }
size_type size() const
{ return c.size(); }
reference
top()
{ return c.back(); }
const_reference
top() const
{ return c.back(); }
void push(const value_type& x)
{ c.push_back(x); }
void push(value_type&& x)
{ c.push_back(std::move(x));
}
template<class... Args>
decltype(auto) emplace(Args&&... args)
{ return c.emplace_back(std::forward<Args>(args)...); }
void pop()
{ c.pop_back(); }
void swap(stack& s) noexcept(is_nothrow_swappable_v<Container>)
{ using std::swap; swap(c, s.c); }
};
template<class Container>
stack(Container) -> stack<typename Container::value_type, Container>;
template<class Container, class Allocator>
stack(Container, Allocator) -> stack<typename Container::value_type, Container>;
template<class T, class Container, class Alloc>
struct uses_allocator<stack<T, Container>, Alloc>
: uses_allocator<Container, Alloc>::type { };
}
§ 26.6.6.1
853
26.6.6.2
stack constructors
[stack.cons]
explicit stack(const Container& cont);
1
Effects: Initializes c with cont.
explicit stack(Container&& cont = Container());
2
Effects: Initializes c with std::move(cont).
26.6.6.3
stack constructors with allocators
[stack.cons.alloc]
1
If uses_allocator_v<container_type, Alloc> is false the constructors in this subclause shall not par-
ticipate in overload resolution.
template<class Alloc> explicit stack(const Alloc& a);
2
Effects: Initializes c with a.
template<class Alloc> stack(const container_type& cont, const Alloc& a);
3
Effects: Initializes c with cont as the first argument and a as the second argument.
template<class Alloc> stack(container_type&& cont, const Alloc& a);
4
Effects: Initializes c with std::move(cont) as the first argument and a as the second argument.
template<class Alloc> stack(const stack& s, const Alloc& a);
5
Effects: Initializes c with s.c as the first argument and a as the second argument.
template<class Alloc> stack(stack&& s, const Alloc& a);
6
Effects: Initializes c with std::move(s.c) as the first argument and a as the second argument.
26.6.6.4
stack operators
[stack.ops]
template<class T, class Container>
bool operator==(const stack<T, Container>& x, const stack<T, Container>& y);
1
Returns: x.c == y.c.
template<class T, class Container>
bool operator!=(const stack<T, Container>& x, const stack<T, Container>& y);
2
Returns: x.c != y.c.
template<class T, class Container>
bool operator< (const stack<T, Container>& x, const stack<T, Container>& y);
3
Returns: x.c < y.c.
template<class T, class Container>
bool operator<=(const stack<T, Container>& x, const stack<T, Container>& y);
4
Returns: x.c <= y.c.
template<class T, class Container>
bool operator> (const stack<T, Container>& x, const stack<T, Container>& y);
5
Returns: x.c > y.c.
template<class T, class Container>
bool operator>=(const stack<T, Container>& x, const stack<T, Container>& y);
6
Returns: x.c >= y.c.
26.6.6.5
stack specialized algorithms
[stack.special]
template<class T, class Container>
void swap(stack<T, Container>& x, stack<T, Container>& y) noexcept(noexcept(x.swap(y)));
1
Remarks: This function shall not participate in overload resolution unless is_swappable_v<Container>
is true.
2
Effects: As if by x.swap(y).
§ 26.6.6.5
854
27
Iterators library
[iterators]
27.1
General
[iterators.general]
1
This Clause describes components that C++ programs may use to perform iterations over containers (Clause
26), streams (30.7), and stream buffers (30.6).
2
The following subclauses describe iterator requirements, and components for iterator primitives, predefined
iterators, and stream iterators, as summarized in Table 92.
Table 92 — Iterators library summary
Subclause
Header(s)
27.2
Requirements
27.4
Iterator primitives
<iterator>
27.5
Predefined iterators
27.6
Stream iterators
27.2
Iterator requirements
[iterator.requirements]
27.2.1
In general
[iterator.requirements.general]
1
Iterators are a generalization of pointers that allow a C++ program to work with different data structures
(containers) in a uniform manner. To be able to construct template algorithms that work correctly and
efficiently on different types of data structures, the library formalizes not just the interfaces but also the
semantics and complexity assumptions of iterators. An input iterator i supports the expression *i, resulting
in a value of some object type T, called the value type of the iterator. An output iterator i has a non-empty
set of types that are writable to the iterator; for each such type T, the expression *i = o is valid where o
is a value of type T. An iterator i for which the expression (*i).m is well-defined supports the expression
i->m with the same semantics as (*i).m. For every iterator type X for which equality is defined, there is a
corresponding signed integer type called the difference type of the iterator.
2
Since iterators are an abstraction of pointers, their semantics is a generalization of most of the semantics of
pointers in C++. This ensures that every function template that takes iterators works as well with regular
pointers. This document defines five categories of iterators, according to the operations defined on them:
input iterators, output iterators, forward iterators, bidirectional iterators and random access iterators, as
shown in Table 93.
Table 93 — Relations among iterator categories
Random Access
→ Bidirectional
→ Forward
→ Input
→ Output
3
Forward iterators satisfy all the requirements of input iterators and can be used whenever an input iterator is
specified; Bidirectional iterators also satisfy all the requirements of forward iterators and can be used whenever
a forward iterator is specified; Random access iterators also satisfy all the requirements of bidirectional
iterators and can be used whenever a bidirectional iterator is specified.
4
Iterators that further satisfy the requirements of output iterators are called mutable iterators. Nonmutable
iterators are referred to as constant iterators.
5
In addition to the requirements in this subclause, the nested typedef-names specified in 27.4.1 shall be
provided for the iterator type.
[Note: Either the iterator type must provide the typedef-names directly
(in which case iterator_traits pick them up automatically), or an iterator_traits specialization must
provide them.
— end note ]
6
Iterators that further satisfy the requirement that, for integral values n and dereferenceable iterator values
a and (a + n), *(a + n) is equivalent to *(addressof(*a) + n), are called contiguous iterators. [Note:
For example, the type “pointer to int” is a contiguous iterator, but reverse_iterator<int *> is not.
§ 27.2.1
855
For a valid iterator range [a,b) with dereferenceable a, the corresponding range denoted by pointers is
[addressof(*a),addressof(*a) + (b - a)); b might not be dereferenceable.
— end note ]
7
Just as a regular pointer to an array guarantees that there is a pointer value pointing past the last element of
the array, so for any iterator type there is an iterator value that points past the last element of a corresponding
sequence. These values are called past-the-end values. Values of an iterator i for which the expression *i is
defined are called dereferenceable. The library never assumes that past-the-end values are dereferenceable.
Iterators can also have singular values that are not associated with any sequence.
[Example: After the
declaration of an uninitialized pointer x (as with int* x;), x must always be assumed to have a singular
value of a pointer.
— end example ] Results of most expressions are undefined for singular values; the
only exceptions are destroying an iterator that holds a singular value, the assignment of a non-singular
value to an iterator that holds a singular value, and, for iterators that satisfy the DefaultConstructible
requirements, using a value-initialized iterator as the source of a copy or move operation.
[Note: This
guarantee is not offered for default-initialization, although the distinction only matters for types with trivial
default constructors such as pointers or aggregates holding pointers.
— end note ] In these cases the singular
value is overwritten the same way as any other value. Dereferenceable values are always non-singular.
8
An iterator j is called reachable from an iterator i if and only if there is a finite sequence of applications of
the expression ++i that makes i == j. If j is reachable from i, they refer to elements of the same sequence.
9
Most of the library’s algorithmic templates that operate on data structures have interfaces that use ranges.
A range is a pair of iterators that designate the beginning and end of the computation. A range [i, i) is an
empty range; in general, a range [i, j) refers to the elements in the data structure starting with the element
pointed to by i and up to but not including the element pointed to by j. Range [i, j) is valid if and only if
j is reachable from i. The result of the application of functions in the library to invalid ranges is undefined.
10
All the categories of iterators require only those functions that are realizable for a given category in constant
time (amortized). Therefore, requirement tables for the iterators do not have a complexity column.
11
Destruction of an iterator may invalidate pointers and references previously obtained from that iterator.
12
An invalid iterator is an iterator that may be singular.264
13
In the following sections, a and b denote values of type X or const X, difference_type and reference refer
to the types iterator_traits<X>::difference_type and iterator_traits<X>::reference, respectively,
n denotes a value of difference_type, u, tmp, and m denote identifiers, r denotes a value of X&, t denotes a
value of value type T, o denotes a value of some type that is writable to the output iterator. [ Note: For an
iterator type X there must be an instantiation of iterator_traits<X> (27.4.1).
— end note ]
27.2.2
Iterator
[iterator.iterators]
1
The Iterator requirements form the basis of the iterator concept taxonomy; every iterator satisfies the
Iterator requirements. This set of requirements specifies operations for dereferencing and incrementing an
iterator. Most algorithms will require additional operations to read (27.2.3) or write (27.2.4) values, or to
provide a richer set of iterator movements (27.2.5, 27.2.6, 27.2.7).
2
A type X satisfies the Iterator requirements if:
(2.1)
—
X satisfies the CopyConstructible, CopyAssignable, and Destructible requirements (20.5.3.1) and
lvalues of type X are swappable (20.5.3.2), and
(2.2)
—
the expressions in Table 94 are valid and have the indicated semantics.
Table 94 — Iterator requirements
Expression
Return type
Operational
Assertion/note
semantics
pre-/post-condition
*r
unspecified
Requires: r is
dereferenceable.
++r
X&
264) This definition applies to pointers, since pointers are iterators. The effect of dereferencing an iterator that has been
invalidated is undefined.
§ 27.2.2
856
27.2.3
Input iterators
[input.iterators]
1
A class or pointer type X satisfies the requirements of an input iterator for the value type T if X satisfies the
Iterator (27.2.2) and EqualityComparable (Table 20) requirements and the expressions in Table 95 are
valid and have the indicated semantics.
2
In Table 95, the term the domain of == is used in the ordinary mathematical sense to denote the set of values
over which == is (required to be) defined. This set can change over time. Each algorithm places additional
requirements on the domain of == for the iterator values it uses. These requirements can be inferred from
the uses that algorithm makes of == and !=. [Example: The call find(a,b,x) is defined only if the value
of a has the property p defined as follows: b has property p and a value i has property p if (*i==x) or if
(*i!=x and ++i has property p).
— end example ]
Table 95 — Input iterator requirements (in addition to Iterator)
Expression
Return type
Operational
Assertion/note
semantics
pre-/post-condition
a != b
contextually
!(a == b)
Requires: (a, b) is in the
convertible to
domain of ==.
bool
*a
reference,
Requires: a is
convertible to T
dereferenceable.
The expression
(void)*a, *a is equivalent
to *a.
If a
== b and (a, b) is in
the domain of == then *a is
equivalent to *b.
a->m
(*a).m
Requires: a is
dereferenceable.
++r
X&
Requires: r is
dereferenceable.
Postconditions: r is
dereferenceable or r is
past-the-end;
any copies of the previous
value of r are no longer
required either to be
dereferenceable or to be in
the domain of ==.
(void)r++
equivalent to (void)++r
*r++
convertible to T
{ T tmp = *r;
++r;
return tmp; }
3
[ Note: For input iterators, a == b does not imply ++a ==
++b. (Equality does not guarantee the substitution
property or referential transparency.) Algorithms on input iterators should never attempt to pass through
the same iterator twice. They should be single pass algorithms. Value type T is not required to be a
CopyAssignable type (Table 26). These algorithms can be used with istreams as the source of the input
data through the istream_iterator class template.
— end note ]
27.2.4
Output iterators
[output.iterators]
1
A class or pointer type X satisfies the requirements of an output iterator if X satisfies the Iterator
requirements (27.2.2) and the expressions in Table 96 are valid and have the indicated semantics.
§ 27.2.4
857
Table 96 — Output iterator requirements (in addition to Iterator)
Expression
Return type
Operational
Assertion/note
semantics
pre-/post-condition
*r = o
result is not
Remarks: After this
used
operation r is not required to
be dereferenceable.
Postconditions: r is
incrementable.
++r
X&
&r == &++r.
Remarks: After this
operation r is not required to
be dereferenceable.
Postconditions: r is
incrementable.
r++
convertible to
{ X tmp = r;
Remarks: After this
const X&
++r;
operation r is not required to
return tmp; }
be dereferenceable.
Postconditions: r is
incrementable.
*r++ = o
result is not
Remarks: After this
used
operation r is not required to
be dereferenceable.
Postconditions: r is
incrementable.
2
[Note: The only valid use of an operator* is on the left side of the assignment statement. Assignment
through the same value of the iterator happens only once. Algorithms on output iterators should never attempt
to pass through the same iterator twice. They should be single pass algorithms. Equality and inequality
might not be defined. Algorithms that take output iterators can be used with ostreams as the destination for
placing data through the ostream_iterator class as well as with insert iterators and insert pointers.
— end
note ]
27.2.5
Forward iterators
[forward.iterators]
1
A class or pointer type X satisfies the requirements of a forward iterator if
(1.1)
—
X satisfies the requirements of an input iterator (27.2.3),
(1.2)
—
X satisfies the DefaultConstructible requirements (20.5.3.1),
(1.3)
—
if X is a mutable iterator, reference is a reference to T; if X is a constant iterator, reference is a
reference to const T,
(1.4)
—
the expressions in Table 97 are valid and have the indicated semantics, and
(1.5)
—
objects of type X offer the multi-pass guarantee, described below.
2
The domain of == for forward iterators is that of iterators over the same underlying sequence. However,
value-initialized iterators may be compared and shall compare equal to other value-initialized iterators of the
same type. [ Note: Value-initialized iterators behave as if they refer past the end of the same empty sequence.
— end note ]
3
Two dereferenceable iterators a and b of type X offer the multi-pass guarantee if:
(3.1)
—
a == b implies ++a == ++b and
(3.2)
—
X is a pointer type or the expression (void)++X(a), *a is equivalent to the expression *a.
4
[ Note: The requirement that a == b implies ++a == ++b (which is not true for input and output iterators)
and the removal of the restrictions on the number of the assignments through a mutable iterator (which
applies to output iterators) allows the use of multi-pass one-directional algorithms with forward iterators.
— end note ]
§ 27.2.5
858
Table 97 — Forward iterator requirements (in addition to input
iterator)
Expression
Return type
Operational
Assertion/note
semantics
pre-/post-condition
r++
convertible to
{ X tmp = r;
const X&
++r;
return tmp; }
*r++
reference
5
If a and b are equal, then either a and b are both dereferenceable or else neither is dereferenceable.
6
If a and b are both dereferenceable, then a == b if and only if *a and *b are bound to the same object.
27.2.6
Bidirectional iterators
[bidirectional.iterators]
1
A class or pointer type X satisfies the requirements of a bidirectional iterator if, in addition to satisfying the
requirements for forward iterators, the following expressions are valid as shown in Table 98.
Table 98 — Bidirectional iterator requirements (in addition to
forward iterator)
Expression
Return type
Operational
Assertion/note
semantics
pre-/post-condition
--r
X&
Requires: there exists s such
that r == ++s.
Postconditions: r is
dereferenceable.
--(++r) == r.
--r == --s implies r == s.
&r == &--r.
r--
convertible to
{ X tmp = r;
const X&
--r;
return tmp; }
*r--
reference
2
[ Note: Bidirectional iterators allow algorithms to move iterators backward as well as forward.
— end note ]
27.2.7
Random access iterators
[random.access.iterators]
1
A class or pointer type X satisfies the requirements of a random access iterator if, in addition to satisfying
the requirements for bidirectional iterators, the following expressions are valid as shown in Table 99.
Table 99 — Random access iterator requirements (in addition to
bidirectional iterator)
Expression
Return type
Operational
Assertion/note
semantics
pre-/post-condition
r += n
X&
{ difference_type m = n;
if (m >= 0)
while (m--)
++r;
else
while (m++)
--r;
return r; }
a + n
X
{ X tmp = a;
a + n == n + a.
n + a
return tmp += n; }
§ 27.2.7
859
Table 99 — Random access iterator requirements (in addition to
bidirectional iterator) (continued)
Expression
Return type
Operational
Assertion/note
semantics
pre-/post-condition
r -= n
X&
return r += -n;
Requires: the absolute value
of n is in the range of
representable values of
difference_type.
a - n
X
{ X tmp = a;
return tmp -= n;
}
b - a
difference_-
return n
Requires: there exists a value
type
n of type difference_type
such that a + n == b.
b == a + (b - a).
a[n]
convertible to
*(a + n)
reference
a < b
contextually
b - a > 0
< is a total ordering relation
convertible to
bool
a > b
contextually
b < a
> is a total ordering relation
convertible to
opposite to <.
bool
a >= b
contextually
!(a < b)
convertible to
bool
a <= b
contextually
!(a > b)
convertible to
bool.
27.3
Header <iterator> synopsis
[iterator.synopsis]
namespace std {
// 27.4, primitives
template<class Iterator> struct iterator_traits;
template<class T> struct iterator_traits<T*>;
struct input_iterator_tag { };
struct output_iterator_tag { };
struct forward_iterator_tag: public input_iterator_tag
{
};
struct bidirectional_iterator_tag: public forward_iterator_tag
{ };
struct random_access_iterator_tag: public bidirectional_iterator_tag
{
};
// 27.4.3, iterator operations
template<class InputIterator, class Distance>
constexpr void
advance(InputIterator& i, Distance n);
template<class InputIterator>
constexpr typename iterator_traits<InputIterator>::difference_type
distance(InputIterator first, InputIterator last);
template<class InputIterator>
constexpr InputIterator
next(InputIterator x,
typename iterator_traits<InputIterator>::difference_type n = 1);
template<class BidirectionalIterator>
constexpr BidirectionalIterator
prev(BidirectionalIterator x,
typename iterator_traits<BidirectionalIterator>::difference_type
n
=
1);
// 27.5, predefined iterators
template<class Iterator> class reverse_iterator;
§
27.3
860
template<class Iterator1, class Iterator2>
constexpr bool operator==(
const reverse_iterator<Iterator1>& x,
const reverse_iterator<Iterator2>& y);
template<class Iterator1, class Iterator2>
constexpr bool operator<(
const reverse_iterator<Iterator1>& x,
const reverse_iterator<Iterator2>& y);
template<class Iterator1, class Iterator2>
constexpr bool operator!=(
const reverse_iterator<Iterator1>& x,
const reverse_iterator<Iterator2>& y);
template<class Iterator1, class Iterator2>
constexpr bool operator>(
const reverse_iterator<Iterator1>& x,
const reverse_iterator<Iterator2>& y);
template<class Iterator1, class Iterator2>
constexpr bool operator>=(
const reverse_iterator<Iterator1>& x,
const reverse_iterator<Iterator2>& y);
template<class Iterator1, class Iterator2>
constexpr bool operator<=(
const reverse_iterator<Iterator1>& x,
const reverse_iterator<Iterator2>& y);
template<class Iterator1, class Iterator2>
constexpr auto operator-(
const reverse_iterator<Iterator1>& x,
const reverse_iterator<Iterator2>& y) ->
decltype(y.base()
-
x.base());
template<class Iterator>
constexpr reverse_iterator<Iterator>
operator+(
typename reverse_iterator<Iterator>::difference_type n,
const reverse_iterator<Iterator>& x);
template<class Iterator>
constexpr reverse_iterator<Iterator> make_reverse_iterator(Iterator i);
template<class Container> class back_insert_iterator;
template<class Container>
back_insert_iterator<Container> back_inserter(Container& x);
template<class Container> class front_insert_iterator;
template<class Container>
front_insert_iterator<Container> front_inserter(Container& x);
template<class Container> class insert_iterator;
template<class Container>
insert_iterator<Container> inserter(Container& x, typename Container::iterator
i);
template<class Iterator> class move_iterator;
template<class Iterator1, class Iterator2>
constexpr bool operator==(
const move_iterator<Iterator1>& x, const move_iterator<Iterator2>& y);
template<class Iterator1, class Iterator2>
constexpr bool operator!=(
const move_iterator<Iterator1>& x, const move_iterator<Iterator2>& y);
template<class Iterator1, class Iterator2>
constexpr bool operator<(
const move_iterator<Iterator1>& x, const move_iterator<Iterator2>& y);
template<class Iterator1, class Iterator2>
constexpr bool operator<=(
const move_iterator<Iterator1>& x, const move_iterator<Iterator2>& y);
§
27.3
861