30 #ifndef _UNORDERED_MAP_H 31 #define _UNORDERED_MAP_H 33 namespace std _GLIBCXX_VISIBILITY(default)
35 _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
41 template<
typename _Key,
48 _Alloc, __detail::_Select1st,
58 template<
typename _Key,
65 _Alloc, __detail::_Select1st,
67 __detail::_Mod_range_hashing,
68 __detail::_Default_ranged_hash,
69 __detail::_Prime_rehash_policy, _Tr>;
93 template<
class _Key,
class _Tp,
109 typedef typename _Hashtable::hasher
hasher;
116 typedef typename allocator_type::pointer
pointer;
139 const hasher& __hf =
hasher(),
142 : _M_h(__n, __hf, __eql, __a)
158 template<
typename _InputIterator>
161 const hasher& __hf =
hasher(),
164 : _M_h(__f, __l, __n, __hf, __eql, __a)
186 const hasher& __hf =
hasher(),
189 : _M_h(__l, __n, __hf, __eql, __a)
222 {
return _M_h.get_allocator(); }
229 {
return _M_h.empty(); }
234 {
return _M_h.size(); }
239 {
return _M_h.max_size(); }
249 {
return _M_h.begin(); }
258 {
return _M_h.begin(); }
262 {
return _M_h.begin(); }
271 {
return _M_h.end(); }
280 {
return _M_h.end(); }
284 {
return _M_h.end(); }
308 template<
typename... _Args>
311 {
return _M_h.emplace(std::forward<_Args>(__args)...); }
338 template<
typename... _Args>
341 {
return _M_h.emplace_hint(__pos, std::forward<_Args>(__args)...); }
363 {
return _M_h.insert(__x); }
365 template<
typename _Pair,
typename =
typename 366 std::enable_if<std::is_constructible<
value_type,
367 _Pair&&>::value>::type>
370 {
return _M_h.insert(std::forward<_Pair>(__x)); }
396 insert(const_iterator __hint,
const value_type& __x)
397 {
return _M_h.insert(__hint, __x); }
399 template<
typename _Pair,
typename =
typename 400 std::enable_if<std::is_constructible<
value_type,
401 _Pair&&>::value>::type>
403 insert(const_iterator __hint, _Pair&& __x)
404 {
return _M_h.insert(__hint, std::forward<_Pair>(__x)); }
416 template<
typename _InputIterator>
418 insert(_InputIterator __first, _InputIterator __last)
419 { _M_h.insert(__first, __last); }
430 { _M_h.insert(__l); }
448 {
return _M_h.erase(__position); }
453 {
return _M_h.erase(__it); }
470 {
return _M_h.erase(__x); }
487 erase(const_iterator __first, const_iterator __last)
488 {
return _M_h.erase(__first, __last); }
511 { _M_h.swap(__x._M_h); }
519 {
return _M_h.hash_function(); }
525 {
return _M_h.key_eq(); }
543 {
return _M_h.find(__x); }
546 find(
const key_type& __x)
const 547 {
return _M_h.find(__x); }
561 {
return _M_h.count(__x); }
574 {
return _M_h.equal_range(__x); }
578 {
return _M_h.equal_range(__x); }
596 {
return _M_h[__k]; }
612 at(
const key_type& __k)
613 {
return _M_h.at(__k); }
616 at(
const key_type& __k)
const 617 {
return _M_h.at(__k); }
625 {
return _M_h.bucket_count(); }
630 {
return _M_h.max_bucket_count(); }
638 bucket_size(size_type __n)
const 639 {
return _M_h.bucket_size(__n); }
647 bucket(
const key_type& __key)
const 648 {
return _M_h.bucket(__key); }
658 {
return _M_h.begin(__n); }
669 {
return _M_h.begin(__n); }
673 {
return _M_h.cbegin(__n); }
684 {
return _M_h.end(__n); }
695 {
return _M_h.end(__n); }
699 {
return _M_h.cend(__n); }
707 {
return _M_h.load_factor(); }
713 {
return _M_h.max_load_factor(); }
721 { _M_h.max_load_factor(__z); }
732 { _M_h.rehash(__n); }
743 { _M_h.reserve(__n); }
745 template<
typename _Key1,
typename _Tp1,
typename _Hash1,
typename _Pred1,
774 template<
class _Key,
class _Tp,
790 typedef typename _Hashtable::hasher
hasher;
797 typedef typename allocator_type::pointer
pointer;
820 const hasher& __hf =
hasher(),
823 : _M_h(__n, __hf, __eql, __a)
839 template<
typename _InputIterator>
842 const hasher& __hf =
hasher(),
845 : _M_h(__f, __l, __n, __hf, __eql, __a)
867 const hasher& __hf =
hasher(),
870 : _M_h(__l, __n, __hf, __eql, __a)
903 {
return _M_h.get_allocator(); }
910 {
return _M_h.empty(); }
915 {
return _M_h.size(); }
920 {
return _M_h.max_size(); }
930 {
return _M_h.begin(); }
939 {
return _M_h.begin(); }
943 {
return _M_h.begin(); }
952 {
return _M_h.end(); }
961 {
return _M_h.end(); }
965 {
return _M_h.end(); }
985 template<
typename... _Args>
988 {
return _M_h.emplace(std::forward<_Args>(__args)...); }
1011 template<
typename... _Args>
1014 {
return _M_h.emplace_hint(__pos, std::forward<_Args>(__args)...); }
1028 {
return _M_h.insert(__x); }
1030 template<
typename _Pair,
typename =
typename 1031 std::enable_if<std::is_constructible<
value_type,
1032 _Pair&&>::value>::type>
1035 {
return _M_h.insert(std::forward<_Pair>(__x)); }
1059 insert(const_iterator __hint,
const value_type& __x)
1060 {
return _M_h.insert(__hint, __x); }
1062 template<
typename _Pair,
typename =
typename 1063 std::enable_if<std::is_constructible<
value_type,
1064 _Pair&&>::value>::type>
1067 {
return _M_h.insert(__hint, std::forward<_Pair>(__x)); }
1079 template<
typename _InputIterator>
1081 insert(_InputIterator __first, _InputIterator __last)
1082 { _M_h.insert(__first, __last); }
1094 { _M_h.insert(__l); }
1112 {
return _M_h.erase(__position); }
1117 {
return _M_h.erase(__it); }
1133 {
return _M_h.erase(__x); }
1151 erase(const_iterator __first, const_iterator __last)
1152 {
return _M_h.erase(__first, __last); }
1176 { _M_h.swap(__x._M_h); }
1184 {
return _M_h.hash_function(); }
1190 {
return _M_h.key_eq(); }
1208 {
return _M_h.find(__x); }
1212 {
return _M_h.find(__x); }
1222 {
return _M_h.count(__x); }
1233 {
return _M_h.equal_range(__x); }
1237 {
return _M_h.equal_range(__x); }
1245 {
return _M_h.bucket_count(); }
1250 {
return _M_h.max_bucket_count(); }
1258 bucket_size(size_type __n)
const 1259 {
return _M_h.bucket_size(__n); }
1267 bucket(
const key_type& __key)
const 1268 {
return _M_h.bucket(__key); }
1278 {
return _M_h.begin(__n); }
1287 const_local_iterator
1289 {
return _M_h.begin(__n); }
1291 const_local_iterator
1293 {
return _M_h.cbegin(__n); }
1304 {
return _M_h.end(__n); }
1313 const_local_iterator
1315 {
return _M_h.end(__n); }
1317 const_local_iterator
1319 {
return _M_h.cend(__n); }
1327 {
return _M_h.load_factor(); }
1333 {
return _M_h.max_load_factor(); }
1341 { _M_h.max_load_factor(__z); }
1352 { _M_h.rehash(__n); }
1363 { _M_h.reserve(__n); }
1365 template<
typename _Key1,
typename _Tp1,
typename _Hash1,
typename _Pred1,
1369 _Hash1, _Pred1, _Alloc1>&,
1371 _Hash1, _Pred1, _Alloc1>&);
1374 template<
class _Key,
class _Tp,
class _Hash,
class _Pred,
class _Alloc>
1380 template<
class _Key,
class _Tp,
class _Hash,
class _Pred,
class _Alloc>
1386 template<
class _Key,
class _Tp,
class _Hash,
class _Pred,
class _Alloc>
1390 {
return __x._M_h._M_equal(__y._M_h); }
1392 template<
class _Key,
class _Tp,
class _Hash,
class _Pred,
class _Alloc>
1396 {
return !(__x == __y); }
1398 template<
class _Key,
class _Tp,
class _Hash,
class _Pred,
class _Alloc>
1402 {
return __x._M_h._M_equal(__y._M_h); }
1404 template<
class _Key,
class _Tp,
class _Hash,
class _Pred,
class _Alloc>
1408 {
return !(__x == __y); }
1410 _GLIBCXX_END_NAMESPACE_CONTAINER
size_type count(const key_type &__x) const
Finds the number of elements.
size_type max_bucket_count() const noexcept
Returns the maximum number of buckets of the unordered_map.
allocator_type::const_pointer const_pointer
Iterator-related typedefs.
mapped_type & at(const key_type &__k)
Access to unordered_map data.
const_local_iterator begin(size_type __n) const
Returns a read-only (constant) iterator pointing to the first bucket element.
iterator erase(iterator __it)
Erases an element from an unordered_map.
_Hashtable::local_iterator local_iterator
Iterator-related typedefs.
_Hashtable::size_type size_type
Iterator-related typedefs.
const mapped_type & at(const key_type &__k) const
Access to unordered_map data.
key_equal key_eq() const
Returns the key comparison object with which the unordered_multimap was constructed.
_Hashtable::size_type size_type
Iterator-related typedefs.
void swap(unordered_multimap &__x)
Swaps data with another unordered_multimap.
iterator insert(const_iterator __hint, const value_type &__x)
Inserts a std::pair into the unordered_multimap.
allocator_type::pointer pointer
Iterator-related typedefs.
iterator begin() noexcept
_Hashtable::const_local_iterator const_local_iterator
Iterator-related typedefs.
key_equal key_eq() const
Returns the key comparison object with which the unordered_map was constructed.
void insert(initializer_list< value_type > __l)
Attempts to insert a list of elements into the unordered_map.
Default range hashing function: use division to fold a large number into the range [0...
void rehash(size_type __n)
May rehash the unordered_map.
const_local_iterator cbegin(size_type __n) const
Returns a read-only (constant) iterator pointing to the first bucket element.
size_type bucket_count() const noexcept
Returns the number of buckets of the unordered_map.
iterator find(const key_type &__x)
Tries to locate an element in an unordered_multimap.
_Hashtable::iterator iterator
Iterator-related typedefs.
unordered_map(initializer_list< value_type > __l, size_type __n=0, const hasher &__hf=hasher(), const key_equal &__eql=key_equal(), const allocator_type &__a=allocator_type())
Builds an unordered_map from an initializer_list.
ISO C++ entities toplevel namespace is std.
iterator erase(iterator __it)
Erases an element from an unordered_multimap.
const_local_iterator end(size_type __n) const
Returns a read-only (constant) iterator pointing to one past the last bucket elements.
void reserve(size_type __n)
Prepare the unordered_multimap for a specified number of elements.
size_type size() const noexcept
Returns the size of the unordered_map.
const_iterator cend() const noexcept
unordered_map & operator=(initializer_list< value_type > __l)
Unordered_map list assignment operator.
iterator erase(const_iterator __position)
Erases an element from an unordered_multimap.
allocator_type::reference reference
Iterator-related typedefs.
allocator_type::reference reference
Iterator-related typedefs.
_Hashtable::value_type value_type
Public typedefs.
_Hashtable::value_type value_type
Public typedefs.
_Hashtable::mapped_type mapped_type
Public typedefs.
size_type erase(const key_type &__x)
Erases elements according to the provided key.
_Hashtable::key_equal key_equal
Public typedefs.
float max_load_factor() const noexcept
Returns a positive number that the unordered_map tries to keep the load factor less than or equal to...
allocator_type get_allocator() const noexcept
Returns the allocator object with which the unordered_map was constructed.
iterator insert(const_iterator __hint, _Pair &&__x)
Attempts to insert a std::pair into the unordered_map.
const_iterator begin() const noexcept
iterator erase(const_iterator __position)
Erases an element from an unordered_map.
allocator_type::const_reference const_reference
Iterator-related typedefs.
float load_factor() const noexcept
Returns the average number of elements per bucket.
_Hashtable::const_iterator const_iterator
Iterator-related typedefs.
const_local_iterator cend(size_type __n) const
Returns a read-only (constant) iterator pointing to one past the last bucket elements.
void insert(_InputIterator __first, _InputIterator __last)
A template function that attempts to insert a range of elements.
unordered_multimap(initializer_list< value_type > __l, size_type __n=0, const hasher &__hf=hasher(), const key_equal &__eql=key_equal(), const allocator_type &__a=allocator_type())
Builds an unordered_multimap from an initializer_list.
unordered_multimap(_InputIterator __f, _InputIterator __l, size_type __n=0, const hasher &__hf=hasher(), const key_equal &__eql=key_equal(), const allocator_type &__a=allocator_type())
Builds an unordered_multimap from a range.
_Hashtable::difference_type difference_type
Iterator-related typedefs.
_Hashtable::iterator iterator
Iterator-related typedefs.
iterator emplace_hint(const_iterator __pos, _Args &&...__args)
Attempts to build and insert a std::pair into the unordered_multimap.
unordered_multimap & operator=(initializer_list< value_type > __l)
Unordered_multimap list assignment operator.
const_local_iterator end(size_type __n) const
Returns a read-only (constant) iterator pointing to one past the last bucket elements.
A standard container composed of equivalent keys (possibly containing multiple of each key value) tha...
size_type count(const key_type &__x) const
Finds the number of elements.
allocator_type get_allocator() const noexcept
Returns the allocator object with which the unordered_multimap was constructed.
std::pair< iterator, bool > emplace(_Args &&...__args)
Attempts to build and insert a std::pair into the unordered_map.
_Hashtable::allocator_type allocator_type
Public typedefs.
_Hashtable::key_equal key_equal
Public typedefs.
Struct holding two objects of arbitrary type.
const_iterator cbegin() const noexcept
local_iterator begin(size_type __n)
Returns a read/write iterator pointing to the first bucket element.
const_local_iterator cend(size_type __n) const
Returns a read-only (constant) iterator pointing to one past the last bucket elements.
local_iterator end(size_type __n)
Returns a read/write iterator pointing to one past the last bucket elements.
Default value for rehash policy. Bucket size is (usually) the smallest prime that keeps the load fact...
The standard allocator, as per [20.4].
bool empty() const noexcept
Returns true if the unordered_multimap is empty.
unordered_map(_InputIterator __f, _InputIterator __l, size_type __n=0, const hasher &__hf=hasher(), const key_equal &__eql=key_equal(), const allocator_type &__a=allocator_type())
Builds an unordered_map from a range.
constexpr std::remove_reference< _Tp >::type && move(_Tp &&__t) noexcept
Convert a value to an rvalue.
_Hashtable::key_type key_type
Public typedefs.
std::pair< const_iterator, const_iterator > equal_range(const key_type &__x) const
Finds a subsequence matching given key.
mapped_type & operator[](key_type &&__k)
Subscript ( [] ) access to unordered_map data.
_Hashtable::key_type key_type
Public typedefs.
_Hashtable::local_iterator local_iterator
Iterator-related typedefs.
iterator insert(const_iterator __hint, _Pair &&__x)
Inserts a std::pair into the unordered_multimap.
void insert(_InputIterator __first, _InputIterator __last)
A template function that attempts to insert a range of elements.
unordered_map & operator=(const unordered_map &)=default
Copy assignment operator.
size_type max_size() const noexcept
Returns the maximum size of the unordered_multimap.
local_iterator end(size_type __n)
Returns a read/write iterator pointing to one past the last bucket elements.
hasher hash_function() const
Returns the hash functor object with which the unordered_multimap was constructed.
Primary class template hash.
iterator emplace(_Args &&...__args)
Attempts to build and insert a std::pair into the unordered_multimap.
iterator insert(const_iterator __hint, const value_type &__x)
Attempts to insert a std::pair into the unordered_map.
std::pair< iterator, iterator > equal_range(const key_type &__x)
Finds a subsequence matching given key.
_Hashtable::difference_type difference_type
Iterator-related typedefs.
const_local_iterator begin(size_type __n) const
Returns a read-only (constant) iterator pointing to the first bucket element.
size_type erase(const key_type &__x)
Erases elements according to the provided key.
float load_factor() const noexcept
Returns the average number of elements per bucket.
size_type max_bucket_count() const noexcept
Returns the maximum number of buckets of the unordered_multimap.
unordered_multimap(size_type __n=10, const hasher &__hf=hasher(), const key_equal &__eql=key_equal(), const allocator_type &__a=allocator_type())
Default constructor creates no elements.
void swap(unordered_map &__x)
Swaps data with another unordered_map.
size_type bucket_count() const noexcept
Returns the number of buckets of the unordered_multimap.
A standard container composed of unique keys (containing at most one of each key value) that associat...
void reserve(size_type __n)
Prepare the unordered_map for a specified number of elements.
mapped_type & operator[](const key_type &__k)
Subscript ( [] ) access to unordered_map data.
const_iterator begin() const noexcept
_Hashtable::hasher hasher
Public typedefs.
void rehash(size_type __n)
May rehash the unordered_multimap.
allocator_type::const_pointer const_pointer
Iterator-related typedefs.
std::pair< iterator, bool > insert(const value_type &__x)
Attempts to insert a std::pair into the unordered_map.
Default ranged hash function H. In principle it should be a function object composed from objects of ...
const_local_iterator cbegin(size_type __n) const
Returns a read-only (constant) iterator pointing to the first bucket element.
iterator insert(const value_type &__x)
Inserts a std::pair into the unordered_multimap.
hasher hash_function() const
Returns the hash functor object with which the unordered_map was constructed.
const_iterator end() const noexcept
_Hashtable::mapped_type mapped_type
Public typedefs.
iterator erase(const_iterator __first, const_iterator __last)
Erases a [__first,__last) range of elements from an unordered_map.
std::pair< iterator, bool > insert(_Pair &&__x)
Attempts to insert a std::pair into the unordered_map.
One of the comparison functors.
void max_load_factor(float __z)
Change the unordered_map maximum load factor.
const_iterator end() const noexcept
iterator emplace_hint(const_iterator __pos, _Args &&...__args)
Attempts to build and insert a std::pair into the unordered_map.
float max_load_factor() const noexcept
Returns a positive number that the unordered_multimap tries to keep the load factor less than or equa...
std::pair< iterator, iterator > equal_range(const key_type &__x)
Finds a subsequence matching given key.
const_iterator cbegin() const noexcept
iterator erase(const_iterator __first, const_iterator __last)
Erases a [__first,__last) range of elements from an unordered_multimap.
size_type size() const noexcept
Returns the size of the unordered_multimap.
std::pair< const_iterator, const_iterator > equal_range(const key_type &__x) const
Finds a subsequence matching given key.
void max_load_factor(float __z)
Change the unordered_multimap maximum load factor.
local_iterator begin(size_type __n)
Returns a read/write iterator pointing to the first bucket element.
allocator_type::pointer pointer
Iterator-related typedefs.
iterator find(const key_type &__x)
Tries to locate an element in an unordered_map.
_Hashtable::hasher hasher
Public typedefs.
const_iterator find(const key_type &__x) const
Tries to locate an element in an unordered_multimap.
_Hashtable::const_iterator const_iterator
Iterator-related typedefs.
iterator insert(_Pair &&__x)
Inserts a std::pair into the unordered_multimap.
const_iterator find(const key_type &__x) const
Tries to locate an element in an unordered_map.
unordered_map(size_type __n=10, const hasher &__hf=hasher(), const key_equal &__eql=key_equal(), const allocator_type &__a=allocator_type())
Default constructor creates no elements.
iterator begin() noexcept
_Hashtable::const_local_iterator const_local_iterator
Iterator-related typedefs.
size_type max_size() const noexcept
Returns the maximum size of the unordered_map.
bool empty() const noexcept
Returns true if the unordered_map is empty.
_Hashtable::allocator_type allocator_type
Public typedefs.
const_iterator cend() const noexcept
void insert(initializer_list< value_type > __l)
Attempts to insert a list of elements into the unordered_multimap.
allocator_type::const_reference const_reference
Iterator-related typedefs.