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); }
871 #if __cplusplus > 201703L
872 template<
typename _Kt>
874 find(
const _Kt& __x) -> decltype(_M_h._M_find_tr(__x))
875 {
return _M_h._M_find_tr(__x); }
880 {
return _M_h.find(__x); }
882 #if __cplusplus > 201703L
883 template<
typename _Kt>
885 find(
const _Kt& __x)
const -> decltype(_M_h._M_find_tr(__x))
886 {
return _M_h._M_find_tr(__x); }
902 {
return _M_h.count(__x); }
904 #if __cplusplus > 201703L
905 template<
typename _Kt>
907 count(
const _Kt& __x)
const -> decltype(_M_h._M_count_tr(__x))
908 {
return _M_h._M_count_tr(__x); }
912 #if __cplusplus > 201703L
921 {
return _M_h.find(__x) != _M_h.end(); }
923 template<
typename _Kt>
925 contains(
const _Kt& __x)
const
926 -> decltype(_M_h._M_find_tr(__x),
void(),
true)
927 {
return _M_h._M_find_tr(__x) != _M_h.end(); }
942 {
return _M_h.equal_range(__x); }
944 #if __cplusplus > 201703L
945 template<
typename _Kt>
948 -> decltype(_M_h._M_equal_range_tr(__x))
949 {
return _M_h._M_equal_range_tr(__x); }
954 {
return _M_h.equal_range(__x); }
956 #if __cplusplus > 201703L
957 template<
typename _Kt>
960 -> decltype(_M_h._M_equal_range_tr(__x))
961 {
return _M_h._M_equal_range_tr(__x); }
980 {
return _M_h[__k]; }
997 {
return _M_h.at(__k); }
1001 {
return _M_h.at(__k); }
1009 {
return _M_h.bucket_count(); }
1014 {
return _M_h.max_bucket_count(); }
1022 bucket_size(size_type __n)
const
1023 {
return _M_h.bucket_size(__n); }
1031 bucket(
const key_type& __key)
const
1032 {
return _M_h.bucket(__key); }
1042 {
return _M_h.begin(__n); }
1051 const_local_iterator
1053 {
return _M_h.begin(__n); }
1055 const_local_iterator
1056 cbegin(size_type __n)
const
1057 {
return _M_h.cbegin(__n); }
1068 {
return _M_h.end(__n); }
1077 const_local_iterator
1079 {
return _M_h.end(__n); }
1081 const_local_iterator
1082 cend(size_type __n)
const
1083 {
return _M_h.cend(__n); }
1091 {
return _M_h.load_factor(); }
1097 {
return _M_h.max_load_factor(); }
1105 { _M_h.max_load_factor(__z); }
1116 { _M_h.rehash(__n); }
1127 { _M_h.reserve(__n); }
1129 template<
typename _Key1,
typename _Tp1,
typename _Hash1,
typename _Pred1,
1136 #if __cpp_deduction_guides >= 201606
1138 template<
typename _InputIterator,
1139 typename _Hash = hash<__iter_key_t<_InputIterator>>,
1140 typename _Pred = equal_to<__iter_key_t<_InputIterator>>,
1141 typename _Allocator = allocator<__iter_to_alloc_t<_InputIterator>>,
1142 typename = _RequireInputIter<_InputIterator>,
1143 typename = _RequireNotAllocatorOrIntegral<_Hash>,
1144 typename = _RequireNotAllocator<_Pred>,
1145 typename = _RequireAllocator<_Allocator>>
1146 unordered_map(_InputIterator, _InputIterator,
1147 typename unordered_map<int, int>::size_type = {},
1148 _Hash = _Hash(), _Pred = _Pred(), _Allocator = _Allocator())
1149 -> unordered_map<__iter_key_t<_InputIterator>,
1150 __iter_val_t<_InputIterator>,
1151 _Hash, _Pred, _Allocator>;
1153 template<
typename _Key,
typename _Tp,
typename _Hash = hash<_Key>,
1154 typename _Pred = equal_to<_Key>,
1155 typename _Allocator = allocator<pair<const _Key, _Tp>>,
1156 typename = _RequireNotAllocatorOrIntegral<_Hash>,
1157 typename = _RequireNotAllocator<_Pred>,
1158 typename = _RequireAllocator<_Allocator>>
1159 unordered_map(initializer_list<pair<_Key, _Tp>>,
1160 typename unordered_map<int, int>::size_type = {},
1161 _Hash = _Hash(), _Pred = _Pred(), _Allocator = _Allocator())
1162 -> unordered_map<_Key, _Tp, _Hash, _Pred, _Allocator>;
1164 template<
typename _InputIterator,
typename _Allocator,
1165 typename = _RequireInputIter<_InputIterator>,
1166 typename = _RequireAllocator<_Allocator>>
1167 unordered_map(_InputIterator, _InputIterator,
1168 typename unordered_map<int, int>::size_type, _Allocator)
1169 -> unordered_map<__iter_key_t<_InputIterator>,
1170 __iter_val_t<_InputIterator>,
1171 hash<__iter_key_t<_InputIterator>>,
1172 equal_to<__iter_key_t<_InputIterator>>,
1175 template<
typename _InputIterator,
typename _Allocator,
1176 typename = _RequireInputIter<_InputIterator>,
1177 typename = _RequireAllocator<_Allocator>>
1178 unordered_map(_InputIterator, _InputIterator, _Allocator)
1179 -> unordered_map<__iter_key_t<_InputIterator>,
1180 __iter_val_t<_InputIterator>,
1181 hash<__iter_key_t<_InputIterator>>,
1182 equal_to<__iter_key_t<_InputIterator>>,
1185 template<
typename _InputIterator,
typename _Hash,
typename _Allocator,
1186 typename = _RequireInputIter<_InputIterator>,
1187 typename = _RequireNotAllocatorOrIntegral<_Hash>,
1188 typename = _RequireAllocator<_Allocator>>
1189 unordered_map(_InputIterator, _InputIterator,
1190 typename unordered_map<int, int>::size_type,
1192 -> unordered_map<__iter_key_t<_InputIterator>,
1193 __iter_val_t<_InputIterator>, _Hash,
1194 equal_to<__iter_key_t<_InputIterator>>, _Allocator>;
1196 template<
typename _Key,
typename _Tp,
typename _Allocator,
1197 typename = _RequireAllocator<_Allocator>>
1198 unordered_map(initializer_list<pair<_Key, _Tp>>,
1199 typename unordered_map<int, int>::size_type,
1201 -> unordered_map<_Key, _Tp, hash<_Key>, equal_to<_Key>, _Allocator>;
1203 template<
typename _Key,
typename _Tp,
typename _Allocator,
1204 typename = _RequireAllocator<_Allocator>>
1205 unordered_map(initializer_list<pair<_Key, _Tp>>, _Allocator)
1206 -> unordered_map<_Key, _Tp, hash<_Key>, equal_to<_Key>, _Allocator>;
1208 template<
typename _Key,
typename _Tp,
typename _Hash,
typename _Allocator,
1209 typename = _RequireNotAllocatorOrIntegral<_Hash>,
1210 typename = _RequireAllocator<_Allocator>>
1211 unordered_map(initializer_list<pair<_Key, _Tp>>,
1212 typename unordered_map<int, int>::size_type,
1214 -> unordered_map<_Key, _Tp, _Hash, equal_to<_Key>, _Allocator>;
1241 template<
typename _Key,
typename _Tp,
1242 typename _Hash = hash<_Key>,
1243 typename _Pred = equal_to<_Key>,
1244 typename _Alloc = allocator<std::pair<const _Key, _Tp>>>
1255 typedef typename _Hashtable::value_type value_type;
1256 typedef typename _Hashtable::mapped_type mapped_type;
1257 typedef typename _Hashtable::hasher hasher;
1258 typedef typename _Hashtable::key_equal key_equal;
1259 typedef typename _Hashtable::allocator_type allocator_type;
1265 typedef typename _Hashtable::const_pointer const_pointer;
1266 typedef typename _Hashtable::reference reference;
1267 typedef typename _Hashtable::const_reference const_reference;
1268 typedef typename _Hashtable::iterator iterator;
1269 typedef typename _Hashtable::const_iterator const_iterator;
1272 typedef typename _Hashtable::size_type size_type;
1273 typedef typename _Hashtable::difference_type difference_type;
1276 #if __cplusplus > 201402L
1294 const hasher& __hf = hasher(),
1295 const key_equal& __eql = key_equal(),
1296 const allocator_type& __a = allocator_type())
1297 : _M_h(__n, __hf, __eql, __a)
1313 template<
typename _InputIterator>
1316 const hasher& __hf = hasher(),
1317 const key_equal& __eql = key_equal(),
1318 const allocator_type& __a = allocator_type())
1319 : _M_h(__first, __last, __n, __hf, __eql, __a)
1343 const allocator_type& __a)
1344 : _M_h(__ummap._M_h, __a)
1353 const allocator_type& __a)
1354 noexcept( noexcept(_Hashtable(
std::move(__ummap._M_h), __a)) )
1355 : _M_h(
std::
move(__ummap._M_h), __a)
1371 const hasher& __hf = hasher(),
1372 const key_equal& __eql = key_equal(),
1373 const allocator_type& __a = allocator_type())
1374 : _M_h(__l, __n, __hf, __eql, __a)
1382 const allocator_type& __a)
1386 template<
typename _InputIterator>
1389 const allocator_type& __a)
1393 template<
typename _InputIterator>
1395 size_type __n,
const hasher& __hf,
1396 const allocator_type& __a)
1402 const allocator_type& __a)
1407 size_type __n,
const hasher& __hf,
1408 const allocator_type& __a)
1441 {
return _M_h.get_allocator(); }
1446 _GLIBCXX_NODISCARD
bool
1448 {
return _M_h.empty(); }
1453 {
return _M_h.size(); }
1458 {
return _M_h.max_size(); }
1468 {
return _M_h.begin(); }
1477 {
return _M_h.begin(); }
1480 cbegin() const noexcept
1481 {
return _M_h.begin(); }
1490 {
return _M_h.end(); }
1499 {
return _M_h.end(); }
1502 cend() const noexcept
1503 {
return _M_h.end(); }
1523 template<
typename... _Args>
1526 {
return _M_h.emplace(std::forward<_Args>(__args)...); }
1550 template<
typename... _Args>
1553 {
return _M_h.emplace_hint(__pos, std::forward<_Args>(__args)...); }
1567 {
return _M_h.insert(__x); }
1573 template<
typename _Pair>
1574 __enable_if_t<is_constructible<value_type, _Pair&&>::value, iterator>
1576 {
return _M_h.emplace(std::forward<_Pair>(__x)); }
1600 insert(const_iterator __hint,
const value_type& __x)
1601 {
return _M_h.insert(__hint, __x); }
1606 insert(const_iterator __hint, value_type&& __x)
1607 {
return _M_h.insert(__hint,
std::move(__x)); }
1609 template<
typename _Pair>
1610 __enable_if_t<is_constructible<value_type, _Pair&&>::value, iterator>
1611 insert(const_iterator __hint, _Pair&& __x)
1612 {
return _M_h.emplace_hint(__hint, std::forward<_Pair>(__x)); }
1624 template<
typename _InputIterator>
1626 insert(_InputIterator __first, _InputIterator __last)
1627 { _M_h.insert(__first, __last); }
1639 { _M_h.insert(__l); }
1641 #if __cplusplus > 201402L
1646 __glibcxx_assert(__pos !=
end());
1647 return _M_h.extract(__pos);
1653 {
return _M_h.extract(__key); }
1662 insert(const_iterator __hint, node_type&& __nh)
1682 {
return _M_h.erase(__position); }
1687 {
return _M_h.erase(__position); }
1703 {
return _M_h.erase(__x); }
1721 erase(const_iterator __first, const_iterator __last)
1722 {
return _M_h.erase(__first, __last); }
1746 noexcept( noexcept(_M_h.swap(__x._M_h)) )
1747 { _M_h.swap(__x._M_h); }
1749 #if __cplusplus > 201402L
1750 template<
typename,
typename,
typename>
1751 friend class std::_Hash_merge_helper;
1753 template<
typename _H2,
typename _P2>
1758 = _Hash_merge_helper<unordered_multimap, _H2, _P2>;
1762 template<
typename _H2,
typename _P2>
1764 merge(unordered_multimap<_Key, _Tp, _H2, _P2, _Alloc>&& __source)
1765 { merge(__source); }
1767 template<
typename _H2,
typename _P2>
1769 merge(unordered_map<_Key, _Tp, _H2, _P2, _Alloc>& __source)
1772 = _Hash_merge_helper<unordered_multimap, _H2, _P2>;
1776 template<
typename _H2,
typename _P2>
1778 merge(unordered_map<_Key, _Tp, _H2, _P2, _Alloc>&& __source)
1779 { merge(__source); }
1788 {
return _M_h.hash_function(); }
1794 {
return _M_h.key_eq(); }
1812 {
return _M_h.find(__x); }
1814 #if __cplusplus > 201703L
1815 template<
typename _Kt>
1817 find(
const _Kt& __x) -> decltype(_M_h._M_find_tr(__x))
1818 {
return _M_h._M_find_tr(__x); }
1823 {
return _M_h.find(__x); }
1825 #if __cplusplus > 201703L
1826 template<
typename _Kt>
1828 find(
const _Kt& __x)
const -> decltype(_M_h._M_find_tr(__x))
1829 {
return _M_h._M_find_tr(__x); }
1841 {
return _M_h.count(__x); }
1843 #if __cplusplus > 201703L
1844 template<
typename _Kt>
1846 count(
const _Kt& __x)
const -> decltype(_M_h._M_count_tr(__x))
1847 {
return _M_h._M_count_tr(__x); }
1851 #if __cplusplus > 201703L
1859 contains(
const key_type& __x)
const
1860 {
return _M_h.find(__x) != _M_h.end(); }
1862 template<
typename _Kt>
1864 contains(
const _Kt& __x)
const
1865 -> decltype(_M_h._M_find_tr(__x),
void(),
true)
1866 {
return _M_h._M_find_tr(__x) != _M_h.end(); }
1879 {
return _M_h.equal_range(__x); }
1881 #if __cplusplus > 201703L
1882 template<
typename _Kt>
1885 -> decltype(_M_h._M_equal_range_tr(__x))
1886 {
return _M_h._M_equal_range_tr(__x); }
1891 {
return _M_h.equal_range(__x); }
1893 #if __cplusplus > 201703L
1894 template<
typename _Kt>
1897 -> decltype(_M_h._M_equal_range_tr(__x))
1898 {
return _M_h._M_equal_range_tr(__x); }
1907 {
return _M_h.bucket_count(); }
1912 {
return _M_h.max_bucket_count(); }
1920 bucket_size(size_type __n)
const
1921 {
return _M_h.bucket_size(__n); }
1929 bucket(
const key_type& __key)
const
1930 {
return _M_h.bucket(__key); }
1940 {
return _M_h.begin(__n); }
1949 const_local_iterator
1951 {
return _M_h.begin(__n); }
1953 const_local_iterator
1954 cbegin(size_type __n)
const
1955 {
return _M_h.cbegin(__n); }
1966 {
return _M_h.end(__n); }
1975 const_local_iterator
1977 {
return _M_h.end(__n); }
1979 const_local_iterator
1980 cend(size_type __n)
const
1981 {
return _M_h.cend(__n); }
1989 {
return _M_h.load_factor(); }
1995 {
return _M_h.max_load_factor(); }
2003 { _M_h.max_load_factor(__z); }
2014 { _M_h.rehash(__n); }
2025 { _M_h.reserve(__n); }
2027 template<
typename _Key1,
typename _Tp1,
typename _Hash1,
typename _Pred1,
2031 _Hash1, _Pred1, _Alloc1>&,
2033 _Hash1, _Pred1, _Alloc1>&);
2036 #if __cpp_deduction_guides >= 201606
2038 template<
typename _InputIterator,
2039 typename _Hash = hash<__iter_key_t<_InputIterator>>,
2040 typename _Pred = equal_to<__iter_key_t<_InputIterator>>,
2041 typename _Allocator = allocator<__iter_to_alloc_t<_InputIterator>>,
2042 typename = _RequireInputIter<_InputIterator>,
2043 typename = _RequireNotAllocatorOrIntegral<_Hash>,
2044 typename = _RequireNotAllocator<_Pred>,
2045 typename = _RequireAllocator<_Allocator>>
2046 unordered_multimap(_InputIterator, _InputIterator,
2047 unordered_multimap<int, int>::size_type = {},
2048 _Hash = _Hash(), _Pred = _Pred(),
2049 _Allocator = _Allocator())
2050 -> unordered_multimap<__iter_key_t<_InputIterator>,
2051 __iter_val_t<_InputIterator>, _Hash, _Pred,
2054 template<
typename _Key,
typename _Tp,
typename _Hash = hash<_Key>,
2055 typename _Pred = equal_to<_Key>,
2056 typename _Allocator = allocator<pair<const _Key, _Tp>>,
2057 typename = _RequireNotAllocatorOrIntegral<_Hash>,
2058 typename = _RequireNotAllocator<_Pred>,
2059 typename = _RequireAllocator<_Allocator>>
2060 unordered_multimap(initializer_list<pair<_Key, _Tp>>,
2061 unordered_multimap<int, int>::size_type = {},
2062 _Hash = _Hash(), _Pred = _Pred(),
2063 _Allocator = _Allocator())
2064 -> unordered_multimap<_Key, _Tp, _Hash, _Pred, _Allocator>;
2066 template<
typename _InputIterator,
typename _Allocator,
2067 typename = _RequireInputIter<_InputIterator>,
2068 typename = _RequireAllocator<_Allocator>>
2069 unordered_multimap(_InputIterator, _InputIterator,
2070 unordered_multimap<int, int>::size_type, _Allocator)
2071 -> unordered_multimap<__iter_key_t<_InputIterator>,
2072 __iter_val_t<_InputIterator>,
2073 hash<__iter_key_t<_InputIterator>>,
2074 equal_to<__iter_key_t<_InputIterator>>, _Allocator>;
2076 template<
typename _InputIterator,
typename _Allocator,
2077 typename = _RequireInputIter<_InputIterator>,
2078 typename = _RequireAllocator<_Allocator>>
2079 unordered_multimap(_InputIterator, _InputIterator, _Allocator)
2080 -> unordered_multimap<__iter_key_t<_InputIterator>,
2081 __iter_val_t<_InputIterator>,
2082 hash<__iter_key_t<_InputIterator>>,
2083 equal_to<__iter_key_t<_InputIterator>>, _Allocator>;
2085 template<
typename _InputIterator,
typename _Hash,
typename _Allocator,
2086 typename = _RequireInputIter<_InputIterator>,
2087 typename = _RequireNotAllocatorOrIntegral<_Hash>,
2088 typename = _RequireAllocator<_Allocator>>
2089 unordered_multimap(_InputIterator, _InputIterator,
2090 unordered_multimap<int, int>::size_type, _Hash,
2092 -> unordered_multimap<__iter_key_t<_InputIterator>,
2093 __iter_val_t<_InputIterator>, _Hash,
2094 equal_to<__iter_key_t<_InputIterator>>, _Allocator>;
2096 template<
typename _Key,
typename _Tp,
typename _Allocator,
2097 typename = _RequireAllocator<_Allocator>>
2098 unordered_multimap(initializer_list<pair<_Key, _Tp>>,
2099 unordered_multimap<int, int>::size_type,
2101 -> unordered_multimap<_Key, _Tp, hash<_Key>, equal_to<_Key>, _Allocator>;
2103 template<
typename _Key,
typename _Tp,
typename _Allocator,
2104 typename = _RequireAllocator<_Allocator>>
2105 unordered_multimap(initializer_list<pair<_Key, _Tp>>, _Allocator)
2106 -> unordered_multimap<_Key, _Tp, hash<_Key>, equal_to<_Key>, _Allocator>;
2108 template<
typename _Key,
typename _Tp,
typename _Hash,
typename _Allocator,
2109 typename = _RequireNotAllocatorOrIntegral<_Hash>,
2110 typename = _RequireAllocator<_Allocator>>
2111 unordered_multimap(initializer_list<pair<_Key, _Tp>>,
2112 unordered_multimap<int, int>::size_type,
2114 -> unordered_multimap<_Key, _Tp, _Hash, equal_to<_Key>, _Allocator>;
2118 template<
class _Key,
class _Tp,
class _Hash,
class _Pred,
class _Alloc>
2120 swap(unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
2121 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
2122 noexcept(noexcept(__x.swap(__y)))
2125 template<
class _Key,
class _Tp,
class _Hash,
class _Pred,
class _Alloc>
2127 swap(unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
2128 unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
2129 noexcept(noexcept(__x.swap(__y)))
2132 template<
class _Key,
class _Tp,
class _Hash,
class _Pred,
class _Alloc>
2134 operator==(
const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
2135 const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
2136 {
return __x._M_h._M_equal(__y._M_h); }
2138 #if __cpp_impl_three_way_comparison < 201907L
2139 template<
class _Key,
class _Tp,
class _Hash,
class _Pred,
class _Alloc>
2141 operator!=(
const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
2142 const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
2143 {
return !(__x == __y); }
2146 template<
class _Key,
class _Tp,
class _Hash,
class _Pred,
class _Alloc>
2148 operator==(
const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
2149 const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
2150 {
return __x._M_h._M_equal(__y._M_h); }
2152 #if __cpp_impl_three_way_comparison < 201907L
2153 template<
class _Key,
class _Tp,
class _Hash,
class _Pred,
class _Alloc>
2155 operator!=(
const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
2156 const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
2157 {
return !(__x == __y); }
2160 _GLIBCXX_END_NAMESPACE_CONTAINER
2162 #if __cplusplus > 201402L
2164 template<
typename _Key,
typename _Val,
typename _Hash1,
typename _Eq1,
2165 typename _Alloc,
typename _Hash2,
typename _Eq2>
2166 struct _Hash_merge_helper<
2167 _GLIBCXX_STD_C::unordered_map<_Key, _Val, _Hash1, _Eq1, _Alloc>,
2171 template<
typename... _Tp>
2172 using unordered_map = _GLIBCXX_STD_C::unordered_map<_Tp...>;
2173 template<
typename... _Tp>
2174 using unordered_multimap = _GLIBCXX_STD_C::unordered_multimap<_Tp...>;
2176 friend unordered_map<_Key, _Val, _Hash1, _Eq1, _Alloc>;
2179 _S_get_table(unordered_map<_Key, _Val, _Hash2, _Eq2, _Alloc>& __map)
2180 {
return __map._M_h; }
2183 _S_get_table(unordered_multimap<_Key, _Val, _Hash2, _Eq2, _Alloc>& __map)
2184 {
return __map._M_h; }
2188 template<
typename _Key,
typename _Val,
typename _Hash1,
typename _Eq1,
2189 typename _Alloc,
typename _Hash2,
typename _Eq2>
2190 struct _Hash_merge_helper<
2191 _GLIBCXX_STD_C::unordered_multimap<_Key, _Val, _Hash1, _Eq1, _Alloc>,
2195 template<
typename... _Tp>
2196 using unordered_map = _GLIBCXX_STD_C::unordered_map<_Tp...>;
2197 template<
typename... _Tp>
2198 using unordered_multimap = _GLIBCXX_STD_C::unordered_multimap<_Tp...>;
2200 friend unordered_multimap<_Key, _Val, _Hash1, _Eq1, _Alloc>;
2203 _S_get_table(unordered_map<_Key, _Val, _Hash2, _Eq2, _Alloc>& __map)
2204 {
return __map._M_h; }
2207 _S_get_table(unordered_multimap<_Key, _Val, _Hash2, _Eq2, _Alloc>& __map)
2208 {
return __map._M_h; }
2212 _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.