30 #ifndef _UNORDERED_MAP_H
31 #define _UNORDERED_MAP_H
33 namespace std _GLIBCXX_VISIBILITY(default)
35 _GLIBCXX_BEGIN_NAMESPACE_VERSION
36 _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
42 template<
typename _Key,
49 _Alloc, __detail::_Select1st,
59 template<
typename _Key,
66 _Alloc, __detail::_Select1st,
72 template<
class _Key,
class _Tp,
class _Hash,
class _Pred,
class _Alloc>
98 template<
typename _Key,
typename _Tp,
112 typedef typename _Hashtable::value_type value_type;
113 typedef typename _Hashtable::mapped_type mapped_type;
114 typedef typename _Hashtable::hasher hasher;
115 typedef typename _Hashtable::key_equal key_equal;
116 typedef typename _Hashtable::allocator_type allocator_type;
122 typedef typename _Hashtable::const_pointer const_pointer;
123 typedef typename _Hashtable::reference reference;
124 typedef typename _Hashtable::const_reference const_reference;
125 typedef typename _Hashtable::iterator iterator;
126 typedef typename _Hashtable::const_iterator const_iterator;
129 typedef typename _Hashtable::size_type size_type;
130 typedef typename _Hashtable::difference_type difference_type;
133 #if __cplusplus > 201402L
152 const hasher& __hf = hasher(),
153 const key_equal& __eql = key_equal(),
154 const allocator_type& __a = allocator_type())
155 : _M_h(__n, __hf, __eql, __a)
171 template<
typename _InputIterator>
174 const hasher& __hf = hasher(),
175 const key_equal& __eql = key_equal(),
176 const allocator_type& __a = allocator_type())
177 : _M_h(__first, __last, __n, __hf, __eql, __a)
201 const allocator_type& __a)
202 : _M_h(__umap._M_h, __a)
211 const allocator_type& __a)
212 noexcept( noexcept(_Hashtable(
std::move(__umap._M_h), __a)) )
213 : _M_h(
std::
move(__umap._M_h), __a)
229 const hasher& __hf = hasher(),
230 const key_equal& __eql = key_equal(),
231 const allocator_type& __a = allocator_type())
232 : _M_h(__l, __n, __hf, __eql, __a)
240 const allocator_type& __a)
244 template<
typename _InputIterator>
247 const allocator_type& __a)
248 :
unordered_map(__first, __last, __n, hasher(), key_equal(), __a)
251 template<
typename _InputIterator>
253 size_type __n,
const hasher& __hf,
254 const allocator_type& __a)
255 :
unordered_map(__first, __last, __n, __hf, key_equal(), __a)
260 const allocator_type& __a)
265 size_type __n,
const hasher& __hf,
266 const allocator_type& __a)
299 {
return _M_h.get_allocator(); }
304 _GLIBCXX_NODISCARD
bool
306 {
return _M_h.empty(); }
311 {
return _M_h.size(); }
316 {
return _M_h.max_size(); }
326 {
return _M_h.begin(); }
335 {
return _M_h.begin(); }
338 cbegin() const noexcept
339 {
return _M_h.begin(); }
348 {
return _M_h.end(); }
357 {
return _M_h.end(); }
360 cend() const noexcept
361 {
return _M_h.end(); }
386 template<
typename... _Args>
389 {
return _M_h.emplace(std::forward<_Args>(__args)...); }
417 template<
typename... _Args>
420 {
return _M_h.emplace_hint(__pos, std::forward<_Args>(__args)...); }
422 #if __cplusplus > 201402L
427 __glibcxx_assert(__pos !=
end());
428 return _M_h.extract(__pos);
434 {
return _M_h.extract(__key); }
446 #define __cpp_lib_unordered_map_try_emplace 201411
469 template <
typename... _Args>
473 return _M_h.try_emplace(cend(), __k, std::forward<_Args>(__args)...);
477 template <
typename... _Args>
481 return _M_h.try_emplace(cend(),
std::move(__k),
482 std::forward<_Args>(__args)...);
513 template <
typename... _Args>
518 return _M_h.try_emplace(__hint, __k,
519 std::forward<_Args>(__args)...).first;
523 template <
typename... _Args>
527 return _M_h.try_emplace(__hint,
std::move(__k),
528 std::forward<_Args>(__args)...).first;
552 {
return _M_h.insert(__x); }
560 template<
typename _Pair>
561 __enable_if_t<is_constructible<value_type, _Pair&&>::value,
562 pair<iterator, bool>>
564 {
return _M_h.emplace(std::forward<_Pair>(__x)); }
590 insert(const_iterator __hint,
const value_type& __x)
591 {
return _M_h.insert(__hint, __x); }
596 insert(const_iterator __hint, value_type&& __x)
597 {
return _M_h.insert(__hint,
std::move(__x)); }
599 template<
typename _Pair>
600 __enable_if_t<is_constructible<value_type, _Pair&&>::value, iterator>
601 insert(const_iterator __hint, _Pair&& __x)
602 {
return _M_h.emplace_hint(__hint, std::forward<_Pair>(__x)); }
614 template<
typename _InputIterator>
616 insert(_InputIterator __first, _InputIterator __last)
617 { _M_h.insert(__first, __last); }
628 { _M_h.insert(__l); }
631 #if __cplusplus > 201402L
652 template <
typename _Obj>
656 auto __ret = _M_h.try_emplace(cend(), __k,
657 std::forward<_Obj>(__obj));
659 __ret.first->second = std::forward<_Obj>(__obj);
664 template <
typename _Obj>
668 auto __ret = _M_h.try_emplace(cend(),
std::move(__k),
669 std::forward<_Obj>(__obj));
671 __ret.first->second = std::forward<_Obj>(__obj);
701 template <
typename _Obj>
706 auto __ret = _M_h.try_emplace(__hint, __k, std::forward<_Obj>(__obj));
708 __ret.first->second = std::forward<_Obj>(__obj);
713 template <
typename _Obj>
717 auto __ret = _M_h.try_emplace(__hint,
std::move(__k),
718 std::forward<_Obj>(__obj));
720 __ret.first->second = std::forward<_Obj>(__obj);
741 {
return _M_h.erase(__position); }
746 {
return _M_h.erase(__position); }
763 {
return _M_h.erase(__x); }
780 erase(const_iterator __first, const_iterator __last)
781 {
return _M_h.erase(__first, __last); }
805 noexcept( noexcept(_M_h.swap(__x._M_h)) )
806 { _M_h.swap(__x._M_h); }
808 #if __cplusplus > 201402L
809 template<
typename,
typename,
typename>
810 friend class std::_Hash_merge_helper;
812 template<
typename _H2,
typename _P2>
816 using _Merge_helper = _Hash_merge_helper<unordered_map, _H2, _P2>;
820 template<
typename _H2,
typename _P2>
822 merge(unordered_map<_Key, _Tp, _H2, _P2, _Alloc>&& __source)
825 template<
typename _H2,
typename _P2>
827 merge(unordered_multimap<_Key, _Tp, _H2, _P2, _Alloc>& __source)
829 using _Merge_helper = _Hash_merge_helper<unordered_map, _H2, _P2>;
833 template<
typename _H2,
typename _P2>
835 merge(unordered_multimap<_Key, _Tp, _H2, _P2, _Alloc>&& __source)
845 {
return _M_h.hash_function(); }
851 {
return _M_h.key_eq(); }
869 {
return _M_h.find(__x); }
873 {
return _M_h.find(__x); }
887 {
return _M_h.count(__x); }
889 #if __cplusplus > 201703L
897 {
return _M_h.find(__x) != _M_h.end(); }
911 {
return _M_h.equal_range(__x); }
915 {
return _M_h.equal_range(__x); }
933 {
return _M_h[__k]; }
950 {
return _M_h.at(__k); }
954 {
return _M_h.at(__k); }
962 {
return _M_h.bucket_count(); }
967 {
return _M_h.max_bucket_count(); }
975 bucket_size(size_type __n)
const
976 {
return _M_h.bucket_size(__n); }
985 {
return _M_h.bucket(__key); }
995 {
return _M_h.begin(__n); }
1004 const_local_iterator
1006 {
return _M_h.begin(__n); }
1008 const_local_iterator
1009 cbegin(size_type __n)
const
1010 {
return _M_h.cbegin(__n); }
1021 {
return _M_h.end(__n); }
1030 const_local_iterator
1032 {
return _M_h.end(__n); }
1034 const_local_iterator
1035 cend(size_type __n)
const
1036 {
return _M_h.cend(__n); }
1044 {
return _M_h.load_factor(); }
1050 {
return _M_h.max_load_factor(); }
1058 { _M_h.max_load_factor(__z); }
1069 { _M_h.rehash(__n); }
1080 { _M_h.reserve(__n); }
1082 template<
typename _Key1,
typename _Tp1,
typename _Hash1,
typename _Pred1,
1089 #if __cpp_deduction_guides >= 201606
1091 template<
typename _InputIterator,
1092 typename _Hash = hash<__iter_key_t<_InputIterator>>,
1093 typename _Pred = equal_to<__iter_key_t<_InputIterator>>,
1094 typename _Allocator = allocator<__iter_to_alloc_t<_InputIterator>>,
1095 typename = _RequireInputIter<_InputIterator>,
1096 typename = _RequireNotAllocatorOrIntegral<_Hash>,
1097 typename = _RequireNotAllocator<_Pred>,
1098 typename = _RequireAllocator<_Allocator>>
1099 unordered_map(_InputIterator, _InputIterator,
1100 typename unordered_map<int, int>::size_type = {},
1101 _Hash = _Hash(), _Pred = _Pred(), _Allocator = _Allocator())
1102 -> unordered_map<__iter_key_t<_InputIterator>,
1103 __iter_val_t<_InputIterator>,
1104 _Hash, _Pred, _Allocator>;
1106 template<
typename _Key,
typename _Tp,
typename _Hash = hash<_Key>,
1107 typename _Pred = equal_to<_Key>,
1108 typename _Allocator = allocator<pair<const _Key, _Tp>>,
1109 typename = _RequireNotAllocatorOrIntegral<_Hash>,
1110 typename = _RequireNotAllocator<_Pred>,
1111 typename = _RequireAllocator<_Allocator>>
1112 unordered_map(initializer_list<pair<_Key, _Tp>>,
1113 typename unordered_map<int, int>::size_type = {},
1114 _Hash = _Hash(), _Pred = _Pred(), _Allocator = _Allocator())
1115 -> unordered_map<_Key, _Tp, _Hash, _Pred, _Allocator>;
1117 template<
typename _InputIterator,
typename _Allocator,
1118 typename = _RequireInputIter<_InputIterator>,
1119 typename = _RequireAllocator<_Allocator>>
1120 unordered_map(_InputIterator, _InputIterator,
1121 typename unordered_map<int, int>::size_type, _Allocator)
1122 -> unordered_map<__iter_key_t<_InputIterator>,
1123 __iter_val_t<_InputIterator>,
1124 hash<__iter_key_t<_InputIterator>>,
1125 equal_to<__iter_key_t<_InputIterator>>,
1128 template<
typename _InputIterator,
typename _Allocator,
1129 typename = _RequireInputIter<_InputIterator>,
1130 typename = _RequireAllocator<_Allocator>>
1131 unordered_map(_InputIterator, _InputIterator, _Allocator)
1132 -> unordered_map<__iter_key_t<_InputIterator>,
1133 __iter_val_t<_InputIterator>,
1134 hash<__iter_key_t<_InputIterator>>,
1135 equal_to<__iter_key_t<_InputIterator>>,
1138 template<
typename _InputIterator,
typename _Hash,
typename _Allocator,
1139 typename = _RequireInputIter<_InputIterator>,
1140 typename = _RequireNotAllocatorOrIntegral<_Hash>,
1141 typename = _RequireAllocator<_Allocator>>
1142 unordered_map(_InputIterator, _InputIterator,
1143 typename unordered_map<int, int>::size_type,
1145 -> unordered_map<__iter_key_t<_InputIterator>,
1146 __iter_val_t<_InputIterator>, _Hash,
1147 equal_to<__iter_key_t<_InputIterator>>, _Allocator>;
1149 template<
typename _Key,
typename _Tp,
typename _Allocator,
1150 typename = _RequireAllocator<_Allocator>>
1151 unordered_map(initializer_list<pair<_Key, _Tp>>,
1152 typename unordered_map<int, int>::size_type,
1154 -> unordered_map<_Key, _Tp, hash<_Key>, equal_to<_Key>, _Allocator>;
1156 template<
typename _Key,
typename _Tp,
typename _Allocator,
1157 typename = _RequireAllocator<_Allocator>>
1158 unordered_map(initializer_list<pair<_Key, _Tp>>, _Allocator)
1159 -> unordered_map<_Key, _Tp, hash<_Key>, equal_to<_Key>, _Allocator>;
1161 template<
typename _Key,
typename _Tp,
typename _Hash,
typename _Allocator,
1162 typename = _RequireNotAllocatorOrIntegral<_Hash>,
1163 typename = _RequireAllocator<_Allocator>>
1164 unordered_map(initializer_list<pair<_Key, _Tp>>,
1165 typename unordered_map<int, int>::size_type,
1167 -> unordered_map<_Key, _Tp, _Hash, equal_to<_Key>, _Allocator>;
1194 template<
typename _Key,
typename _Tp,
1195 typename _Hash = hash<_Key>,
1196 typename _Pred = equal_to<_Key>,
1197 typename _Alloc = allocator<std::pair<const _Key, _Tp>>>
1208 typedef typename _Hashtable::value_type value_type;
1209 typedef typename _Hashtable::mapped_type mapped_type;
1210 typedef typename _Hashtable::hasher hasher;
1211 typedef typename _Hashtable::key_equal key_equal;
1212 typedef typename _Hashtable::allocator_type allocator_type;
1218 typedef typename _Hashtable::const_pointer const_pointer;
1219 typedef typename _Hashtable::reference reference;
1220 typedef typename _Hashtable::const_reference const_reference;
1221 typedef typename _Hashtable::iterator iterator;
1222 typedef typename _Hashtable::const_iterator const_iterator;
1225 typedef typename _Hashtable::size_type size_type;
1226 typedef typename _Hashtable::difference_type difference_type;
1229 #if __cplusplus > 201402L
1247 const hasher& __hf = hasher(),
1248 const key_equal& __eql = key_equal(),
1249 const allocator_type& __a = allocator_type())
1250 : _M_h(__n, __hf, __eql, __a)
1266 template<
typename _InputIterator>
1269 const hasher& __hf = hasher(),
1270 const key_equal& __eql = key_equal(),
1271 const allocator_type& __a = allocator_type())
1272 : _M_h(__first, __last, __n, __hf, __eql, __a)
1296 const allocator_type& __a)
1297 : _M_h(__ummap._M_h, __a)
1306 const allocator_type& __a)
1307 noexcept( noexcept(_Hashtable(
std::move(__ummap._M_h), __a)) )
1308 : _M_h(
std::
move(__ummap._M_h), __a)
1324 const hasher& __hf = hasher(),
1325 const key_equal& __eql = key_equal(),
1326 const allocator_type& __a = allocator_type())
1327 : _M_h(__l, __n, __hf, __eql, __a)
1335 const allocator_type& __a)
1339 template<
typename _InputIterator>
1342 const allocator_type& __a)
1346 template<
typename _InputIterator>
1348 size_type __n,
const hasher& __hf,
1349 const allocator_type& __a)
1355 const allocator_type& __a)
1360 size_type __n,
const hasher& __hf,
1361 const allocator_type& __a)
1394 {
return _M_h.get_allocator(); }
1399 _GLIBCXX_NODISCARD
bool
1401 {
return _M_h.empty(); }
1406 {
return _M_h.size(); }
1411 {
return _M_h.max_size(); }
1421 {
return _M_h.begin(); }
1430 {
return _M_h.begin(); }
1433 cbegin() const noexcept
1434 {
return _M_h.begin(); }
1443 {
return _M_h.end(); }
1452 {
return _M_h.end(); }
1455 cend() const noexcept
1456 {
return _M_h.end(); }
1476 template<
typename... _Args>
1479 {
return _M_h.emplace(std::forward<_Args>(__args)...); }
1503 template<
typename... _Args>
1506 {
return _M_h.emplace_hint(__pos, std::forward<_Args>(__args)...); }
1520 {
return _M_h.insert(__x); }
1526 template<
typename _Pair>
1527 __enable_if_t<is_constructible<value_type, _Pair&&>::value, iterator>
1529 {
return _M_h.emplace(std::forward<_Pair>(__x)); }
1553 insert(const_iterator __hint,
const value_type& __x)
1554 {
return _M_h.insert(__hint, __x); }
1559 insert(const_iterator __hint, value_type&& __x)
1560 {
return _M_h.insert(__hint,
std::move(__x)); }
1562 template<
typename _Pair>
1563 __enable_if_t<is_constructible<value_type, _Pair&&>::value, iterator>
1564 insert(const_iterator __hint, _Pair&& __x)
1565 {
return _M_h.emplace_hint(__hint, std::forward<_Pair>(__x)); }
1577 template<
typename _InputIterator>
1579 insert(_InputIterator __first, _InputIterator __last)
1580 { _M_h.insert(__first, __last); }
1592 { _M_h.insert(__l); }
1594 #if __cplusplus > 201402L
1599 __glibcxx_assert(__pos !=
end());
1600 return _M_h.extract(__pos);
1606 {
return _M_h.extract(__key); }
1615 insert(const_iterator __hint, node_type&& __nh)
1635 {
return _M_h.erase(__position); }
1640 {
return _M_h.erase(__position); }
1656 {
return _M_h.erase(__x); }
1674 erase(const_iterator __first, const_iterator __last)
1675 {
return _M_h.erase(__first, __last); }
1699 noexcept( noexcept(_M_h.swap(__x._M_h)) )
1700 { _M_h.swap(__x._M_h); }
1702 #if __cplusplus > 201402L
1703 template<
typename,
typename,
typename>
1704 friend class std::_Hash_merge_helper;
1706 template<
typename _H2,
typename _P2>
1711 = _Hash_merge_helper<unordered_multimap, _H2, _P2>;
1715 template<
typename _H2,
typename _P2>
1717 merge(unordered_multimap<_Key, _Tp, _H2, _P2, _Alloc>&& __source)
1718 { merge(__source); }
1720 template<
typename _H2,
typename _P2>
1722 merge(unordered_map<_Key, _Tp, _H2, _P2, _Alloc>& __source)
1725 = _Hash_merge_helper<unordered_multimap, _H2, _P2>;
1729 template<
typename _H2,
typename _P2>
1731 merge(unordered_map<_Key, _Tp, _H2, _P2, _Alloc>&& __source)
1732 { merge(__source); }
1741 {
return _M_h.hash_function(); }
1747 {
return _M_h.key_eq(); }
1765 {
return _M_h.find(__x); }
1769 {
return _M_h.find(__x); }
1779 {
return _M_h.count(__x); }
1781 #if __cplusplus > 201703L
1788 contains(
const key_type& __x)
const
1789 {
return _M_h.find(__x) != _M_h.end(); }
1801 {
return _M_h.equal_range(__x); }
1805 {
return _M_h.equal_range(__x); }
1813 {
return _M_h.bucket_count(); }
1818 {
return _M_h.max_bucket_count(); }
1826 bucket_size(size_type __n)
const
1827 {
return _M_h.bucket_size(__n); }
1835 bucket(
const key_type& __key)
const
1836 {
return _M_h.bucket(__key); }
1846 {
return _M_h.begin(__n); }
1855 const_local_iterator
1857 {
return _M_h.begin(__n); }
1859 const_local_iterator
1860 cbegin(size_type __n)
const
1861 {
return _M_h.cbegin(__n); }
1872 {
return _M_h.end(__n); }
1881 const_local_iterator
1883 {
return _M_h.end(__n); }
1885 const_local_iterator
1886 cend(size_type __n)
const
1887 {
return _M_h.cend(__n); }
1895 {
return _M_h.load_factor(); }
1901 {
return _M_h.max_load_factor(); }
1909 { _M_h.max_load_factor(__z); }
1920 { _M_h.rehash(__n); }
1931 { _M_h.reserve(__n); }
1933 template<
typename _Key1,
typename _Tp1,
typename _Hash1,
typename _Pred1,
1937 _Hash1, _Pred1, _Alloc1>&,
1939 _Hash1, _Pred1, _Alloc1>&);
1942 #if __cpp_deduction_guides >= 201606
1944 template<
typename _InputIterator,
1945 typename _Hash = hash<__iter_key_t<_InputIterator>>,
1946 typename _Pred = equal_to<__iter_key_t<_InputIterator>>,
1947 typename _Allocator = allocator<__iter_to_alloc_t<_InputIterator>>,
1948 typename = _RequireInputIter<_InputIterator>,
1949 typename = _RequireNotAllocatorOrIntegral<_Hash>,
1950 typename = _RequireNotAllocator<_Pred>,
1951 typename = _RequireAllocator<_Allocator>>
1952 unordered_multimap(_InputIterator, _InputIterator,
1953 unordered_multimap<int, int>::size_type = {},
1954 _Hash = _Hash(), _Pred = _Pred(),
1955 _Allocator = _Allocator())
1956 -> unordered_multimap<__iter_key_t<_InputIterator>,
1957 __iter_val_t<_InputIterator>, _Hash, _Pred,
1960 template<
typename _Key,
typename _Tp,
typename _Hash = hash<_Key>,
1961 typename _Pred = equal_to<_Key>,
1962 typename _Allocator = allocator<pair<const _Key, _Tp>>,
1963 typename = _RequireNotAllocatorOrIntegral<_Hash>,
1964 typename = _RequireNotAllocator<_Pred>,
1965 typename = _RequireAllocator<_Allocator>>
1966 unordered_multimap(initializer_list<pair<_Key, _Tp>>,
1967 unordered_multimap<int, int>::size_type = {},
1968 _Hash = _Hash(), _Pred = _Pred(),
1969 _Allocator = _Allocator())
1970 -> unordered_multimap<_Key, _Tp, _Hash, _Pred, _Allocator>;
1972 template<
typename _InputIterator,
typename _Allocator,
1973 typename = _RequireInputIter<_InputIterator>,
1974 typename = _RequireAllocator<_Allocator>>
1975 unordered_multimap(_InputIterator, _InputIterator,
1976 unordered_multimap<int, int>::size_type, _Allocator)
1977 -> unordered_multimap<__iter_key_t<_InputIterator>,
1978 __iter_val_t<_InputIterator>,
1979 hash<__iter_key_t<_InputIterator>>,
1980 equal_to<__iter_key_t<_InputIterator>>, _Allocator>;
1982 template<
typename _InputIterator,
typename _Allocator,
1983 typename = _RequireInputIter<_InputIterator>,
1984 typename = _RequireAllocator<_Allocator>>
1985 unordered_multimap(_InputIterator, _InputIterator, _Allocator)
1986 -> unordered_multimap<__iter_key_t<_InputIterator>,
1987 __iter_val_t<_InputIterator>,
1988 hash<__iter_key_t<_InputIterator>>,
1989 equal_to<__iter_key_t<_InputIterator>>, _Allocator>;
1991 template<
typename _InputIterator,
typename _Hash,
typename _Allocator,
1992 typename = _RequireInputIter<_InputIterator>,
1993 typename = _RequireNotAllocatorOrIntegral<_Hash>,
1994 typename = _RequireAllocator<_Allocator>>
1995 unordered_multimap(_InputIterator, _InputIterator,
1996 unordered_multimap<int, int>::size_type, _Hash,
1998 -> unordered_multimap<__iter_key_t<_InputIterator>,
1999 __iter_val_t<_InputIterator>, _Hash,
2000 equal_to<__iter_key_t<_InputIterator>>, _Allocator>;
2002 template<
typename _Key,
typename _Tp,
typename _Allocator,
2003 typename = _RequireAllocator<_Allocator>>
2004 unordered_multimap(initializer_list<pair<_Key, _Tp>>,
2005 unordered_multimap<int, int>::size_type,
2007 -> unordered_multimap<_Key, _Tp, hash<_Key>, equal_to<_Key>, _Allocator>;
2009 template<
typename _Key,
typename _Tp,
typename _Allocator,
2010 typename = _RequireAllocator<_Allocator>>
2011 unordered_multimap(initializer_list<pair<_Key, _Tp>>, _Allocator)
2012 -> unordered_multimap<_Key, _Tp, hash<_Key>, equal_to<_Key>, _Allocator>;
2014 template<
typename _Key,
typename _Tp,
typename _Hash,
typename _Allocator,
2015 typename = _RequireNotAllocatorOrIntegral<_Hash>,
2016 typename = _RequireAllocator<_Allocator>>
2017 unordered_multimap(initializer_list<pair<_Key, _Tp>>,
2018 unordered_multimap<int, int>::size_type,
2020 -> unordered_multimap<_Key, _Tp, _Hash, equal_to<_Key>, _Allocator>;
2024 template<
class _Key,
class _Tp,
class _Hash,
class _Pred,
class _Alloc>
2026 swap(unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
2027 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
2028 noexcept(noexcept(__x.swap(__y)))
2031 template<
class _Key,
class _Tp,
class _Hash,
class _Pred,
class _Alloc>
2033 swap(unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
2034 unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
2035 noexcept(noexcept(__x.swap(__y)))
2038 template<
class _Key,
class _Tp,
class _Hash,
class _Pred,
class _Alloc>
2040 operator==(
const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
2041 const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
2042 {
return __x._M_h._M_equal(__y._M_h); }
2044 #if __cpp_impl_three_way_comparison < 201907L
2045 template<
class _Key,
class _Tp,
class _Hash,
class _Pred,
class _Alloc>
2047 operator!=(
const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
2048 const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
2049 {
return !(__x == __y); }
2052 template<
class _Key,
class _Tp,
class _Hash,
class _Pred,
class _Alloc>
2054 operator==(
const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
2055 const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
2056 {
return __x._M_h._M_equal(__y._M_h); }
2058 #if __cpp_impl_three_way_comparison < 201907L
2059 template<
class _Key,
class _Tp,
class _Hash,
class _Pred,
class _Alloc>
2061 operator!=(
const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
2062 const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
2063 {
return !(__x == __y); }
2066 _GLIBCXX_END_NAMESPACE_CONTAINER
2068 #if __cplusplus > 201402L
2070 template<
typename _Key,
typename _Val,
typename _Hash1,
typename _Eq1,
2071 typename _Alloc,
typename _Hash2,
typename _Eq2>
2072 struct _Hash_merge_helper<
2073 _GLIBCXX_STD_C::unordered_map<_Key, _Val, _Hash1, _Eq1, _Alloc>,
2077 template<
typename... _Tp>
2078 using unordered_map = _GLIBCXX_STD_C::unordered_map<_Tp...>;
2079 template<
typename... _Tp>
2080 using unordered_multimap = _GLIBCXX_STD_C::unordered_multimap<_Tp...>;
2082 friend unordered_map<_Key, _Val, _Hash1, _Eq1, _Alloc>;
2085 _S_get_table(unordered_map<_Key, _Val, _Hash2, _Eq2, _Alloc>& __map)
2086 {
return __map._M_h; }
2089 _S_get_table(unordered_multimap<_Key, _Val, _Hash2, _Eq2, _Alloc>& __map)
2090 {
return __map._M_h; }
2094 template<
typename _Key,
typename _Val,
typename _Hash1,
typename _Eq1,
2095 typename _Alloc,
typename _Hash2,
typename _Eq2>
2096 struct _Hash_merge_helper<
2097 _GLIBCXX_STD_C::unordered_multimap<_Key, _Val, _Hash1, _Eq1, _Alloc>,
2101 template<
typename... _Tp>
2102 using unordered_map = _GLIBCXX_STD_C::unordered_map<_Tp...>;
2103 template<
typename... _Tp>
2104 using unordered_multimap = _GLIBCXX_STD_C::unordered_multimap<_Tp...>;
2106 friend unordered_multimap<_Key, _Val, _Hash1, _Eq1, _Alloc>;
2109 _S_get_table(unordered_map<_Key, _Val, _Hash2, _Eq2, _Alloc>& __map)
2110 {
return __map._M_h; }
2113 _S_get_table(unordered_multimap<_Key, _Val, _Hash2, _Eq2, _Alloc>& __map)
2114 {
return __map._M_h; }
2118 _GLIBCXX_END_NAMESPACE_VERSION
constexpr std::remove_reference< _Tp >::type && move(_Tp &&__t) noexcept
Convert a value to an rvalue.
void swap(any &__x, any &__y) noexcept
Exchange the states of two any objects.
ISO C++ entities toplevel namespace is std.
constexpr auto cend(const _Container &__cont) noexcept(noexcept(std::end(__cont))) -> decltype(std::end(__cont))
Return an iterator pointing to one past the last element of the const container.
constexpr auto cbegin(const _Container &__cont) noexcept(noexcept(std::begin(__cont))) -> decltype(std::begin(__cont))
Return an iterator pointing to the first element of the const container.
Primary class template hash.
The standard allocator, as per [20.4].
void _M_merge_unique(_Compatible_Hashtable &__src) noexcept
Merge from a compatible container into one with unique keys.
void _M_merge_multi(_Compatible_Hashtable &__src) noexcept
Merge from a compatible container into one with equivalent keys.
insert_return_type _M_reinsert_node(node_type &&__nh)
Re-insert an extracted node into a container with unique keys.
iterator _M_reinsert_node_multi(const_iterator __hint, node_type &&__nh)
Re-insert an extracted node into a container with equivalent keys.
Default range hashing function: use division to fold a large number into the range [0,...
Default ranged hash function H. In principle it should be a function object composed from objects of ...
Default value for rehash policy. Bucket size is (usually) the smallest prime that keeps the load fact...
Node handle type for maps.
Return type of insert(node_handle&&) on unique maps/sets.
One of the comparison functors.
Struct holding two objects of arbitrary type.
A standard container composed of equivalent keys (possibly containing multiple of each key value) tha...
float load_factor() const noexcept
Returns the average number of elements per bucket.
unordered_multimap & operator=(const unordered_multimap &)=default
Copy assignment operator.
const_iterator end() const noexcept
size_type erase(const key_type &__x)
Erases elements according to the provided key.
size_type bucket_count() const noexcept
Returns the number of buckets of the unordered_multimap.
size_type max_bucket_count() const noexcept
Returns the maximum number of buckets of the unordered_multimap.
unordered_multimap & operator=(initializer_list< value_type > __l)
Unordered_multimap list assignment operator.
iterator begin() noexcept
const_iterator begin() const noexcept
hasher hash_function() const
Returns the hash functor object with which the unordered_multimap was constructed.
iterator insert(const_iterator __hint, node_type &&__nh)
Re-insert an extracted node.
key_equal key_eq() const
Returns the key comparison object with which the unordered_multimap was constructed.
size_type count(const key_type &__x) const
Finds the number of elements.
local_iterator end(size_type __n)
Returns a read/write 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(size_type __n, const hasher &__hf=hasher(), const key_equal &__eql=key_equal(), const allocator_type &__a=allocator_type())
Default constructor creates no elements.
iterator emplace(_Args &&... __args)
Attempts to build and insert a std::pair into the unordered_multimap.
node_type extract(const key_type &__key)
Extract a node.
std::pair< iterator, iterator > equal_range(const key_type &__x)
Finds a subsequence matching given key.
iterator insert(node_type &&__nh)
Re-insert an extracted node.
iterator erase(const_iterator __position)
Erases an element from an unordered_multimap.
local_iterator begin(size_type __n)
Returns a read/write iterator pointing to the first bucket element.
float max_load_factor() const noexcept
Returns a positive number that the unordered_multimap tries to keep the load factor less than or equa...
unordered_multimap()=default
Default constructor.
iterator insert(const value_type &__x)
Inserts a std::pair into the unordered_multimap.
void reserve(size_type __n)
Prepare the unordered_multimap for a specified number of elements.
unordered_multimap(_InputIterator __first, _InputIterator __last, 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.
iterator find(const key_type &__x)
Tries to locate an element in an unordered_multimap.
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.
iterator erase(const_iterator __first, const_iterator __last)
Erases a [__first,__last) range of elements 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.
_Hashtable::pointer pointer
Iterator-related typedefs.
const_local_iterator begin(size_type __n) const
Returns a read-only (constant) iterator pointing to the first bucket element.
unordered_multimap(unordered_multimap &&)=default
Move constructor.
unordered_multimap(const allocator_type &__a)
Creates an unordered_multimap with no elements.
void swap(unordered_multimap &__x) noexcept(noexcept(_M_h.swap(__x._M_h)))
Swaps data with another unordered_multimap.
void rehash(size_type __n)
May rehash the unordered_multimap.
unordered_multimap & operator=(unordered_multimap &&)=default
Move assignment operator.
void insert(initializer_list< value_type > __l)
Attempts to insert a list of elements into the unordered_multimap.
size_type max_size() const noexcept
Returns the maximum size of the unordered_multimap.
bool empty() const noexcept
Returns true if the unordered_multimap is empty.
_Hashtable::key_type key_type
Public typedefs.
node_type extract(const_iterator __pos)
Extract a node.
iterator insert(const_iterator __hint, const value_type &__x)
Inserts a std::pair into the unordered_multimap.
size_type size() const noexcept
Returns the size of the unordered_multimap.
unordered_multimap(const unordered_multimap &)=default
Copy constructor.
iterator emplace_hint(const_iterator __pos, _Args &&... __args)
Attempts to build and insert a std::pair into the unordered_multimap.
allocator_type get_allocator() const noexcept
Returns the allocator object used by the unordered_multimap.
void max_load_factor(float __z)
Change the unordered_multimap maximum load factor.
A standard container composed of unique keys (containing at most one of each key value) that associat...
std::pair< iterator, bool > insert(const value_type &__x)
Attempts to insert a std::pair into the unordered_map.
void max_load_factor(float __z)
Change the unordered_map maximum load factor.
node_type extract(const key_type &__key)
Extract a node.
void insert(_InputIterator __first, _InputIterator __last)
A template function that attempts to insert a range of elements.
allocator_type get_allocator() const noexcept
Returns the allocator object used by the unordered_map.
pair< iterator, bool > insert_or_assign(const key_type &__k, _Obj &&__obj)
Attempts to insert a std::pair into the unordered_map.
void insert(initializer_list< value_type > __l)
Attempts to insert a list of elements into the unordered_map.
iterator erase(const_iterator __first, const_iterator __last)
Erases a [__first,__last) range of elements from an unordered_map.
iterator try_emplace(const_iterator __hint, const key_type &__k, _Args &&... __args)
Attempts to build and insert a std::pair into the unordered_map.
node_type extract(const_iterator __pos)
Extract a node.
mapped_type & operator[](const key_type &__k)
Subscript ( [] ) access to unordered_map data.
void reserve(size_type __n)
Prepare the unordered_map for a specified number of elements.
std::pair< iterator, iterator > equal_range(const key_type &__x)
Finds a subsequence matching given key.
iterator insert(const_iterator, node_type &&__nh)
Re-insert an extracted node.
iterator insert(const_iterator __hint, const value_type &__x)
Attempts to insert a std::pair into the unordered_map.
pair< iterator, bool > try_emplace(const key_type &__k, _Args &&... __args)
Attempts to build and insert a std::pair into the unordered_map.
unordered_map & operator=(initializer_list< value_type > __l)
Unordered_map list assignment operator.
unordered_map(const unordered_map &)=default
Copy constructor.
size_type count(const key_type &__x) const
Finds the number of elements.
bool empty() const noexcept
Returns true if the unordered_map is empty.
size_type erase(const key_type &__x)
Erases elements according to the provided key.
unordered_map(unordered_map &&)=default
Move constructor.
const_local_iterator end(size_type __n) const
Returns a read-only (constant) iterator pointing to one past the last bucket elements.
size_type max_size() const noexcept
Returns the maximum size of the unordered_map.
const_iterator end() const noexcept
unordered_map()=default
Default constructor.
const_local_iterator begin(size_type __n) const
Returns a read-only (constant) iterator pointing to the first bucket element.
unordered_map(size_type __n, const hasher &__hf=hasher(), const key_equal &__eql=key_equal(), const allocator_type &__a=allocator_type())
Default constructor creates no elements.
size_type size() const noexcept
Returns the size of the unordered_map.
unordered_map & operator=(unordered_map &&)=default
Move assignment operator.
mapped_type & at(const key_type &__k)
Access to unordered_map data.
unordered_map(_InputIterator __first, _InputIterator __last, 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.
const_iterator begin() const noexcept
std::pair< iterator, bool > emplace(_Args &&... __args)
Attempts to build and insert a std::pair into the unordered_map.
key_equal key_eq() const
Returns the key comparison object with which the unordered_map was constructed.
local_iterator end(size_type __n)
Returns a read/write iterator pointing to one past the last bucket elements.
_Hashtable::pointer pointer
Iterator-related typedefs.
iterator insert_or_assign(const_iterator __hint, const key_type &__k, _Obj &&__obj)
Attempts to insert a std::pair into the unordered_map.
unordered_map(const allocator_type &__a)
Creates an unordered_map with no elements.
_Hashtable::key_type key_type
Public typedefs.
size_type bucket_count() const noexcept
Returns the number of buckets of the unordered_map.
iterator begin() noexcept
hasher hash_function() const
Returns the hash functor object with which the unordered_map was constructed.
unordered_map & operator=(const unordered_map &)=default
Copy assignment operator.
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.
iterator find(const key_type &__x)
Tries to locate an element in an unordered_map.
float load_factor() const noexcept
Returns the average number of elements per bucket.
iterator erase(const_iterator __position)
Erases an element from an unordered_map.
void swap(unordered_map &__x) noexcept(noexcept(_M_h.swap(__x._M_h)))
Swaps data with another unordered_map.
local_iterator begin(size_type __n)
Returns a read/write iterator pointing to the first bucket element.
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.
size_type max_bucket_count() const noexcept
Returns the maximum number of buckets of the unordered_map.
iterator emplace_hint(const_iterator __pos, _Args &&... __args)
Attempts to build and insert a std::pair into the unordered_map.
insert_return_type insert(node_type &&__nh)
Re-insert an extracted node.
void rehash(size_type __n)
May rehash the unordered_map.