30#ifndef _UNORDERED_MAP_H
31#define _UNORDERED_MAP_H
38namespace std _GLIBCXX_VISIBILITY(default)
40_GLIBCXX_BEGIN_NAMESPACE_VERSION
41_GLIBCXX_BEGIN_NAMESPACE_CONTAINER
47 template<
typename _Key,
53 using __umap_hashtable = _Hashtable<_Key, std::pair<const _Key, _Tp>,
54 _Alloc, __detail::_Select1st,
56 __detail::_Mod_range_hashing,
57 __detail::_Default_ranged_hash,
58 __detail::_Prime_rehash_policy, _Tr>;
64 template<
typename _Key,
70 using __ummap_hashtable = _Hashtable<_Key, std::pair<const _Key, _Tp>,
71 _Alloc, __detail::_Select1st,
73 __detail::_Mod_range_hashing,
74 __detail::_Default_ranged_hash,
75 __detail::_Prime_rehash_policy, _Tr>;
77 template<
class _Key,
class _Tp,
class _Hash,
class _Pred,
class _Alloc>
105 template<
typename _Key,
typename _Tp,
111 typedef __umap_hashtable<_Key, _Tp, _Hash, _Pred, _Alloc> _Hashtable;
121 typedef typename _Hashtable::hasher
hasher;
140#if __cplusplus > 201402L
141 using node_type =
typename _Hashtable::node_type;
142 using insert_return_type =
typename _Hashtable::insert_return_type;
162 : _M_h(__n, __hf, __eql, __a)
178 template<
typename _InputIterator>
184 : _M_h(__first, __last, __n, __hf, __eql, __a)
209 : _M_h(__umap._M_h, __a)
219 noexcept(
noexcept(_Hashtable(
std::move(__umap._M_h), __a)) )
239 : _M_h(__l, __n, __hf, __eql, __a)
251 template<
typename _InputIterator>
258 template<
typename _InputIterator>
306 {
return _M_h.get_allocator(); }
311 _GLIBCXX_NODISCARD
bool
313 {
return _M_h.empty(); }
318 {
return _M_h.size(); }
323 {
return _M_h.max_size(); }
333 {
return _M_h.begin(); }
342 {
return _M_h.begin(); }
346 {
return _M_h.begin(); }
355 {
return _M_h.end(); }
364 {
return _M_h.end(); }
368 {
return _M_h.end(); }
393 template<
typename... _Args>
396 {
return _M_h.emplace(std::forward<_Args>(__args)...); }
424 template<
typename... _Args>
427 {
return _M_h.emplace_hint(__pos, std::forward<_Args>(__args)...); }
429#if __cplusplus > 201402L
434 __glibcxx_assert(__pos !=
end());
435 return _M_h.extract(__pos);
441 {
return _M_h.extract(__key); }
446 {
return _M_h._M_reinsert_node(
std::move(__nh)); }
451 {
return _M_h._M_reinsert_node(
std::move(__nh)).position; }
453#define __cpp_lib_unordered_map_try_emplace 201411L
476 template <
typename... _Args>
480 return _M_h.try_emplace(
cend(), __k, std::forward<_Args>(__args)...);
484 template <
typename... _Args>
489 std::forward<_Args>(__args)...);
520 template <
typename... _Args>
525 return _M_h.try_emplace(__hint, __k,
526 std::forward<_Args>(__args)...).first;
530 template <
typename... _Args>
534 return _M_h.try_emplace(__hint,
std::move(__k),
535 std::forward<_Args>(__args)...).first;
559 {
return _M_h.insert(__x); }
567 template<
typename _Pair>
568 __enable_if_t<is_constructible<value_type, _Pair&&>::value,
571 {
return _M_h.emplace(std::forward<_Pair>(__x)); }
598 {
return _M_h.insert(__hint, __x); }
604 {
return _M_h.insert(__hint,
std::move(__x)); }
606 template<
typename _Pair>
607 __enable_if_t<is_constructible<value_type, _Pair&&>::value,
iterator>
609 {
return _M_h.emplace_hint(__hint, std::forward<_Pair>(__x)); }
621 template<
typename _InputIterator>
623 insert(_InputIterator __first, _InputIterator __last)
624 { _M_h.insert(__first, __last); }
635 { _M_h.insert(__l); }
638#if __cplusplus > 201402L
659 template <
typename _Obj>
663 auto __ret = _M_h.try_emplace(
cend(), __k,
664 std::forward<_Obj>(__obj));
666 __ret.first->second = std::forward<_Obj>(__obj);
671 template <
typename _Obj>
676 std::forward<_Obj>(__obj));
678 __ret.first->second = std::forward<_Obj>(__obj);
708 template <
typename _Obj>
713 auto __ret = _M_h.try_emplace(__hint, __k, std::forward<_Obj>(__obj));
715 __ret.first->second = std::forward<_Obj>(__obj);
720 template <
typename _Obj>
724 auto __ret = _M_h.try_emplace(__hint,
std::move(__k),
725 std::forward<_Obj>(__obj));
727 __ret.first->second = std::forward<_Obj>(__obj);
748 {
return _M_h.erase(__position); }
753 {
return _M_h.erase(__position); }
770 {
return _M_h.erase(__x); }
788 {
return _M_h.erase(__first, __last); }
812 noexcept(
noexcept(_M_h.swap(__x._M_h)) )
813 { _M_h.swap(__x._M_h); }
815#if __cplusplus > 201402L
816 template<
typename,
typename,
typename>
817 friend class std::_Hash_merge_helper;
819 template<
typename _H2,
typename _P2>
823 using _Merge_helper = _Hash_merge_helper<unordered_map, _H2, _P2>;
824 _M_h._M_merge_unique(_Merge_helper::_S_get_table(__source));
827 template<
typename _H2,
typename _P2>
829 merge(unordered_map<_Key, _Tp, _H2, _P2, _Alloc>&& __source)
832 template<
typename _H2,
typename _P2>
834 merge(unordered_multimap<_Key, _Tp, _H2, _P2, _Alloc>& __source)
836 using _Merge_helper = _Hash_merge_helper<unordered_map, _H2, _P2>;
837 _M_h._M_merge_unique(_Merge_helper::_S_get_table(__source));
840 template<
typename _H2,
typename _P2>
842 merge(unordered_multimap<_Key, _Tp, _H2, _P2, _Alloc>&& __source)
852 {
return _M_h.hash_function(); }
858 {
return _M_h.key_eq(); }
876 {
return _M_h.find(__x); }
878#if __cplusplus > 201703L
879 template<
typename _Kt>
881 find(
const _Kt& __x) ->
decltype(_M_h._M_find_tr(__x))
882 {
return _M_h._M_find_tr(__x); }
887 {
return _M_h.find(__x); }
889#if __cplusplus > 201703L
890 template<
typename _Kt>
892 find(
const _Kt& __x)
const ->
decltype(_M_h._M_find_tr(__x))
893 {
return _M_h._M_find_tr(__x); }
909 {
return _M_h.count(__x); }
911#if __cplusplus > 201703L
912 template<
typename _Kt>
914 count(
const _Kt& __x)
const ->
decltype(_M_h._M_count_tr(__x))
915 {
return _M_h._M_count_tr(__x); }
919#if __cplusplus > 201703L
928 {
return _M_h.find(__x) != _M_h.end(); }
930 template<
typename _Kt>
933 ->
decltype(_M_h._M_find_tr(__x), void(),
true)
934 {
return _M_h._M_find_tr(__x) != _M_h.end(); }
949 {
return _M_h.equal_range(__x); }
951#if __cplusplus > 201703L
952 template<
typename _Kt>
955 ->
decltype(_M_h._M_equal_range_tr(__x))
956 {
return _M_h._M_equal_range_tr(__x); }
961 {
return _M_h.equal_range(__x); }
963#if __cplusplus > 201703L
964 template<
typename _Kt>
967 ->
decltype(_M_h._M_equal_range_tr(__x))
968 {
return _M_h._M_equal_range_tr(__x); }
987 {
return _M_h[__k]; }
1004 {
return _M_h.at(__k); }
1008 {
return _M_h.at(__k); }
1016 {
return _M_h.bucket_count(); }
1021 {
return _M_h.max_bucket_count(); }
1030 {
return _M_h.bucket_size(__n); }
1038 bucket(
const key_type& __key)
const
1039 {
return _M_h.bucket(__key); }
1049 {
return _M_h.begin(__n); }
1060 {
return _M_h.begin(__n); }
1064 {
return _M_h.cbegin(__n); }
1075 {
return _M_h.end(__n); }
1086 {
return _M_h.end(__n); }
1090 {
return _M_h.cend(__n); }
1098 {
return _M_h.load_factor(); }
1104 {
return _M_h.max_load_factor(); }
1112 { _M_h.max_load_factor(__z); }
1123 { _M_h.rehash(__n); }
1134 { _M_h.reserve(__n); }
1136 template<
typename _Key1,
typename _Tp1,
typename _Hash1,
typename _Pred1,
1143#if __cpp_deduction_guides >= 201606
1145 template<
typename _InputIterator,
1146 typename _Hash = hash<__iter_key_t<_InputIterator>>,
1147 typename _Pred = equal_to<__iter_key_t<_InputIterator>>,
1148 typename _Allocator = allocator<__iter_to_alloc_t<_InputIterator>>,
1149 typename = _RequireInputIter<_InputIterator>,
1150 typename = _RequireNotAllocatorOrIntegral<_Hash>,
1151 typename = _RequireNotAllocator<_Pred>,
1152 typename = _RequireAllocator<_Allocator>>
1153 unordered_map(_InputIterator, _InputIterator,
1155 _Hash = _Hash(), _Pred = _Pred(), _Allocator = _Allocator())
1156 -> unordered_map<__iter_key_t<_InputIterator>,
1157 __iter_val_t<_InputIterator>,
1158 _Hash, _Pred, _Allocator>;
1160 template<
typename _Key,
typename _Tp,
typename _Hash = hash<_Key>,
1161 typename _Pred = equal_to<_Key>,
1162 typename _Allocator = allocator<pair<const _Key, _Tp>>,
1163 typename = _RequireNotAllocatorOrIntegral<_Hash>,
1164 typename = _RequireNotAllocator<_Pred>,
1165 typename = _RequireAllocator<_Allocator>>
1166 unordered_map(initializer_list<pair<_Key, _Tp>>,
1168 _Hash = _Hash(), _Pred = _Pred(), _Allocator = _Allocator())
1169 -> unordered_map<_Key, _Tp, _Hash, _Pred, _Allocator>;
1171 template<
typename _InputIterator,
typename _Allocator,
1172 typename = _RequireInputIter<_InputIterator>,
1173 typename = _RequireAllocator<_Allocator>>
1174 unordered_map(_InputIterator, _InputIterator,
1176 -> unordered_map<__iter_key_t<_InputIterator>,
1177 __iter_val_t<_InputIterator>,
1178 hash<__iter_key_t<_InputIterator>>,
1179 equal_to<__iter_key_t<_InputIterator>>,
1182 template<
typename _InputIterator,
typename _Allocator,
1183 typename = _RequireInputIter<_InputIterator>,
1184 typename = _RequireAllocator<_Allocator>>
1185 unordered_map(_InputIterator, _InputIterator, _Allocator)
1186 -> unordered_map<__iter_key_t<_InputIterator>,
1187 __iter_val_t<_InputIterator>,
1188 hash<__iter_key_t<_InputIterator>>,
1189 equal_to<__iter_key_t<_InputIterator>>,
1192 template<
typename _InputIterator,
typename _Hash,
typename _Allocator,
1193 typename = _RequireInputIter<_InputIterator>,
1194 typename = _RequireNotAllocatorOrIntegral<_Hash>,
1195 typename = _RequireAllocator<_Allocator>>
1196 unordered_map(_InputIterator, _InputIterator,
1199 -> unordered_map<__iter_key_t<_InputIterator>,
1200 __iter_val_t<_InputIterator>, _Hash,
1201 equal_to<__iter_key_t<_InputIterator>>, _Allocator>;
1203 template<
typename _Key,
typename _Tp,
typename _Allocator,
1204 typename = _RequireAllocator<_Allocator>>
1205 unordered_map(initializer_list<pair<_Key, _Tp>>,
1208 -> unordered_map<_Key, _Tp, hash<_Key>, equal_to<_Key>, _Allocator>;
1210 template<
typename _Key,
typename _Tp,
typename _Allocator,
1211 typename = _RequireAllocator<_Allocator>>
1212 unordered_map(initializer_list<pair<_Key, _Tp>>, _Allocator)
1213 -> unordered_map<_Key, _Tp, hash<_Key>, equal_to<_Key>, _Allocator>;
1215 template<
typename _Key,
typename _Tp,
typename _Hash,
typename _Allocator,
1216 typename = _RequireNotAllocatorOrIntegral<_Hash>,
1217 typename = _RequireAllocator<_Allocator>>
1218 unordered_map(initializer_list<pair<_Key, _Tp>>,
1221 -> unordered_map<_Key, _Tp, _Hash, equal_to<_Key>, _Allocator>;
1250 template<
typename _Key,
typename _Tp,
1251 typename _Hash = hash<_Key>,
1252 typename _Pred = equal_to<_Key>,
1253 typename _Alloc = allocator<std::pair<const _Key, _Tp>>>
1256 typedef __ummap_hashtable<_Key, _Tp, _Hash, _Pred, _Alloc> _Hashtable;
1285#if __cplusplus > 201402L
1286 using node_type =
typename _Hashtable::node_type;
1306 : _M_h(__n, __hf, __eql, __a)
1322 template<
typename _InputIterator>
1328 : _M_h(__first, __last, __n, __hf, __eql, __a)
1353 : _M_h(__ummap._M_h, __a)
1363 noexcept(
noexcept(_Hashtable(
std::move(__ummap._M_h), __a)) )
1383 : _M_h(__l, __n, __hf, __eql, __a)
1395 template<
typename _InputIterator>
1402 template<
typename _InputIterator>
1450 {
return _M_h.get_allocator(); }
1455 _GLIBCXX_NODISCARD
bool
1457 {
return _M_h.empty(); }
1462 {
return _M_h.size(); }
1467 {
return _M_h.max_size(); }
1477 {
return _M_h.begin(); }
1486 {
return _M_h.begin(); }
1490 {
return _M_h.begin(); }
1499 {
return _M_h.end(); }
1508 {
return _M_h.end(); }
1512 {
return _M_h.end(); }
1532 template<
typename... _Args>
1535 {
return _M_h.emplace(std::forward<_Args>(__args)...); }
1559 template<
typename... _Args>
1562 {
return _M_h.emplace_hint(__pos, std::forward<_Args>(__args)...); }
1576 {
return _M_h.insert(__x); }
1582 template<
typename _Pair>
1583 __enable_if_t<is_constructible<value_type, _Pair&&>::value,
iterator>
1585 {
return _M_h.emplace(std::forward<_Pair>(__x)); }
1610 {
return _M_h.insert(__hint, __x); }
1616 {
return _M_h.insert(__hint,
std::move(__x)); }
1618 template<
typename _Pair>
1619 __enable_if_t<is_constructible<value_type, _Pair&&>::value,
iterator>
1621 {
return _M_h.emplace_hint(__hint, std::forward<_Pair>(__x)); }
1633 template<
typename _InputIterator>
1635 insert(_InputIterator __first, _InputIterator __last)
1636 { _M_h.insert(__first, __last); }
1648 { _M_h.insert(__l); }
1650#if __cplusplus > 201402L
1655 __glibcxx_assert(__pos !=
end());
1656 return _M_h.extract(__pos);
1662 {
return _M_h.extract(__key); }
1667 {
return _M_h._M_reinsert_node_multi(
cend(),
std::move(__nh)); }
1672 {
return _M_h._M_reinsert_node_multi(__hint,
std::move(__nh)); }
1691 {
return _M_h.erase(__position); }
1696 {
return _M_h.erase(__position); }
1712 {
return _M_h.erase(__x); }
1731 {
return _M_h.erase(__first, __last); }
1755 noexcept(
noexcept(_M_h.swap(__x._M_h)) )
1756 { _M_h.swap(__x._M_h); }
1758#if __cplusplus > 201402L
1759 template<
typename,
typename,
typename>
1760 friend class std::_Hash_merge_helper;
1762 template<
typename _H2,
typename _P2>
1767 = _Hash_merge_helper<unordered_multimap, _H2, _P2>;
1768 _M_h._M_merge_multi(_Merge_helper::_S_get_table(__source));
1771 template<
typename _H2,
typename _P2>
1773 merge(unordered_multimap<_Key, _Tp, _H2, _P2, _Alloc>&& __source)
1774 { merge(__source); }
1776 template<
typename _H2,
typename _P2>
1778 merge(unordered_map<_Key, _Tp, _H2, _P2, _Alloc>& __source)
1781 = _Hash_merge_helper<unordered_multimap, _H2, _P2>;
1782 _M_h._M_merge_multi(_Merge_helper::_S_get_table(__source));
1785 template<
typename _H2,
typename _P2>
1787 merge(unordered_map<_Key, _Tp, _H2, _P2, _Alloc>&& __source)
1788 { merge(__source); }
1797 {
return _M_h.hash_function(); }
1803 {
return _M_h.key_eq(); }
1821 {
return _M_h.find(__x); }
1823#if __cplusplus > 201703L
1824 template<
typename _Kt>
1826 find(
const _Kt& __x) ->
decltype(_M_h._M_find_tr(__x))
1827 {
return _M_h._M_find_tr(__x); }
1832 {
return _M_h.find(__x); }
1834#if __cplusplus > 201703L
1835 template<
typename _Kt>
1837 find(
const _Kt& __x)
const ->
decltype(_M_h._M_find_tr(__x))
1838 {
return _M_h._M_find_tr(__x); }
1850 {
return _M_h.count(__x); }
1852#if __cplusplus > 201703L
1853 template<
typename _Kt>
1855 count(
const _Kt& __x)
const ->
decltype(_M_h._M_count_tr(__x))
1856 {
return _M_h._M_count_tr(__x); }
1860#if __cplusplus > 201703L
1869 {
return _M_h.find(__x) != _M_h.end(); }
1871 template<
typename _Kt>
1874 ->
decltype(_M_h._M_find_tr(__x), void(),
true)
1875 {
return _M_h._M_find_tr(__x) != _M_h.end(); }
1888 {
return _M_h.equal_range(__x); }
1890#if __cplusplus > 201703L
1891 template<
typename _Kt>
1894 ->
decltype(_M_h._M_equal_range_tr(__x))
1895 {
return _M_h._M_equal_range_tr(__x); }
1900 {
return _M_h.equal_range(__x); }
1902#if __cplusplus > 201703L
1903 template<
typename _Kt>
1906 ->
decltype(_M_h._M_equal_range_tr(__x))
1907 {
return _M_h._M_equal_range_tr(__x); }
1916 {
return _M_h.bucket_count(); }
1921 {
return _M_h.max_bucket_count(); }
1930 {
return _M_h.bucket_size(__n); }
1938 bucket(
const key_type& __key)
const
1939 {
return _M_h.bucket(__key); }
1949 {
return _M_h.begin(__n); }
1960 {
return _M_h.begin(__n); }
1964 {
return _M_h.cbegin(__n); }
1975 {
return _M_h.end(__n); }
1986 {
return _M_h.end(__n); }
1990 {
return _M_h.cend(__n); }
1998 {
return _M_h.load_factor(); }
2004 {
return _M_h.max_load_factor(); }
2012 { _M_h.max_load_factor(__z); }
2023 { _M_h.rehash(__n); }
2034 { _M_h.reserve(__n); }
2036 template<
typename _Key1,
typename _Tp1,
typename _Hash1,
typename _Pred1,
2040 _Hash1, _Pred1, _Alloc1>&,
2042 _Hash1, _Pred1, _Alloc1>&);
2045#if __cpp_deduction_guides >= 201606
2047 template<
typename _InputIterator,
2048 typename _Hash = hash<__iter_key_t<_InputIterator>>,
2049 typename _Pred = equal_to<__iter_key_t<_InputIterator>>,
2050 typename _Allocator = allocator<__iter_to_alloc_t<_InputIterator>>,
2051 typename = _RequireInputIter<_InputIterator>,
2052 typename = _RequireNotAllocatorOrIntegral<_Hash>,
2053 typename = _RequireNotAllocator<_Pred>,
2054 typename = _RequireAllocator<_Allocator>>
2055 unordered_multimap(_InputIterator, _InputIterator,
2057 _Hash = _Hash(), _Pred = _Pred(),
2058 _Allocator = _Allocator())
2059 -> unordered_multimap<__iter_key_t<_InputIterator>,
2060 __iter_val_t<_InputIterator>, _Hash, _Pred,
2063 template<
typename _Key,
typename _Tp,
typename _Hash = hash<_Key>,
2064 typename _Pred = equal_to<_Key>,
2065 typename _Allocator = allocator<pair<const _Key, _Tp>>,
2066 typename = _RequireNotAllocatorOrIntegral<_Hash>,
2067 typename = _RequireNotAllocator<_Pred>,
2068 typename = _RequireAllocator<_Allocator>>
2069 unordered_multimap(initializer_list<pair<_Key, _Tp>>,
2071 _Hash = _Hash(), _Pred = _Pred(),
2072 _Allocator = _Allocator())
2073 -> unordered_multimap<_Key, _Tp, _Hash, _Pred, _Allocator>;
2075 template<
typename _InputIterator,
typename _Allocator,
2076 typename = _RequireInputIter<_InputIterator>,
2077 typename = _RequireAllocator<_Allocator>>
2078 unordered_multimap(_InputIterator, _InputIterator,
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 _Allocator,
2086 typename = _RequireInputIter<_InputIterator>,
2087 typename = _RequireAllocator<_Allocator>>
2088 unordered_multimap(_InputIterator, _InputIterator, _Allocator)
2089 -> unordered_multimap<__iter_key_t<_InputIterator>,
2090 __iter_val_t<_InputIterator>,
2091 hash<__iter_key_t<_InputIterator>>,
2092 equal_to<__iter_key_t<_InputIterator>>, _Allocator>;
2094 template<
typename _InputIterator,
typename _Hash,
typename _Allocator,
2095 typename = _RequireInputIter<_InputIterator>,
2096 typename = _RequireNotAllocatorOrIntegral<_Hash>,
2097 typename = _RequireAllocator<_Allocator>>
2098 unordered_multimap(_InputIterator, _InputIterator,
2101 -> unordered_multimap<__iter_key_t<_InputIterator>,
2102 __iter_val_t<_InputIterator>, _Hash,
2103 equal_to<__iter_key_t<_InputIterator>>, _Allocator>;
2105 template<
typename _Key,
typename _Tp,
typename _Allocator,
2106 typename = _RequireAllocator<_Allocator>>
2107 unordered_multimap(initializer_list<pair<_Key, _Tp>>,
2110 -> unordered_multimap<_Key, _Tp, hash<_Key>, equal_to<_Key>, _Allocator>;
2112 template<
typename _Key,
typename _Tp,
typename _Allocator,
2113 typename = _RequireAllocator<_Allocator>>
2114 unordered_multimap(initializer_list<pair<_Key, _Tp>>, _Allocator)
2115 -> unordered_multimap<_Key, _Tp, hash<_Key>, equal_to<_Key>, _Allocator>;
2117 template<
typename _Key,
typename _Tp,
typename _Hash,
typename _Allocator,
2118 typename = _RequireNotAllocatorOrIntegral<_Hash>,
2119 typename = _RequireAllocator<_Allocator>>
2120 unordered_multimap(initializer_list<pair<_Key, _Tp>>,
2123 -> unordered_multimap<_Key, _Tp, _Hash, equal_to<_Key>, _Allocator>;
2127 template<
class _Key,
class _Tp,
class _Hash,
class _Pred,
class _Alloc>
2129 swap(unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
2130 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
2131 noexcept(
noexcept(__x.swap(__y)))
2134 template<
class _Key,
class _Tp,
class _Hash,
class _Pred,
class _Alloc>
2136 swap(unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
2137 unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
2138 noexcept(
noexcept(__x.swap(__y)))
2141 template<
class _Key,
class _Tp,
class _Hash,
class _Pred,
class _Alloc>
2143 operator==(
const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
2144 const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
2145 {
return __x._M_h._M_equal(__y._M_h); }
2147#if __cpp_impl_three_way_comparison < 201907L
2148 template<
class _Key,
class _Tp,
class _Hash,
class _Pred,
class _Alloc>
2150 operator!=(
const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
2151 const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
2152 {
return !(__x == __y); }
2155 template<
class _Key,
class _Tp,
class _Hash,
class _Pred,
class _Alloc>
2157 operator==(
const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
2158 const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
2159 {
return __x._M_h._M_equal(__y._M_h); }
2161#if __cpp_impl_three_way_comparison < 201907L
2162 template<
class _Key,
class _Tp,
class _Hash,
class _Pred,
class _Alloc>
2164 operator!=(
const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
2165 const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
2166 {
return !(__x == __y); }
2169_GLIBCXX_END_NAMESPACE_CONTAINER
2171#if __cplusplus > 201402L
2173 template<
typename _Key,
typename _Val,
typename _Hash1,
typename _Eq1,
2174 typename _Alloc,
typename _Hash2,
typename _Eq2>
2175 struct _Hash_merge_helper<
2176 _GLIBCXX_STD_C::unordered_map<_Key, _Val, _Hash1, _Eq1, _Alloc>,
2180 template<
typename... _Tp>
2181 using unordered_map = _GLIBCXX_STD_C::unordered_map<_Tp...>;
2182 template<
typename... _Tp>
2183 using unordered_multimap = _GLIBCXX_STD_C::unordered_multimap<_Tp...>;
2185 friend unordered_map<_Key, _Val, _Hash1, _Eq1, _Alloc>;
2188 _S_get_table(unordered_map<_Key, _Val, _Hash2, _Eq2, _Alloc>& __map)
2189 {
return __map._M_h; }
2192 _S_get_table(unordered_multimap<_Key, _Val, _Hash2, _Eq2, _Alloc>& __map)
2193 {
return __map._M_h; }
2197 template<
typename _Key,
typename _Val,
typename _Hash1,
typename _Eq1,
2198 typename _Alloc,
typename _Hash2,
typename _Eq2>
2199 struct _Hash_merge_helper<
2200 _GLIBCXX_STD_C::unordered_multimap<_Key, _Val, _Hash1, _Eq1, _Alloc>,
2204 template<
typename... _Tp>
2205 using unordered_map = _GLIBCXX_STD_C::unordered_map<_Tp...>;
2206 template<
typename... _Tp>
2207 using unordered_multimap = _GLIBCXX_STD_C::unordered_multimap<_Tp...>;
2209 friend unordered_multimap<_Key, _Val, _Hash1, _Eq1, _Alloc>;
2212 _S_get_table(unordered_map<_Key, _Val, _Hash2, _Eq2, _Alloc>& __map)
2213 {
return __map._M_h; }
2216 _S_get_table(unordered_multimap<_Key, _Val, _Hash2, _Eq2, _Alloc>& __map)
2217 {
return __map._M_h; }
2221_GLIBCXX_END_NAMESPACE_VERSION
constexpr std::remove_reference< _Tp >::type && move(_Tp &&__t) noexcept
Convert a value to an rvalue.
ISO C++ entities toplevel namespace is std.
__detail::_Hashtable_traits< _Cache, false, false > __ummap_traits
Base types for unordered_multimap.
__detail::_Hashtable_traits< _Cache, false, true > __umap_traits
Base types for unordered_map.
Primary class template hash.
The standard allocator, as per C++03 [20.4.1].
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.
_Hashtable::reference reference
Iterator-related typedefs.
iterator erase(iterator __position)
Erases an element from an unordered_multimap.
const_iterator end() const noexcept
size_type erase(const key_type &__x)
Erases elements according to the provided key.
std::pair< iterator, iterator > equal_range(const key_type &__x)
Finds a subsequence matching given key.
size_type bucket_count() const noexcept
Returns the number of buckets of the unordered_multimap.
_Hashtable::iterator iterator
Iterator-related typedefs.
size_type max_bucket_count() const noexcept
Returns the maximum number of buckets of the unordered_multimap.
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.
__enable_if_t< is_constructible< value_type, _Pair && >::value, iterator > insert(const_iterator __hint, _Pair &&__x)
Inserts a std::pair into the unordered_multimap.
unordered_multimap & operator=(const unordered_multimap &)=default
Copy assignment operator.
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.
const_iterator find(const key_type &__x) const
Tries to locate an element in an unordered_multimap.
_Hashtable::mapped_type mapped_type
Public typedefs.
auto find(const _Kt &__x) -> decltype(_M_h._M_find_tr(__x))
Tries to locate an element in an unordered_multimap.
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 & operator=(initializer_list< value_type > __l)
Unordered_multimap list assignment operator.
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.
_Hashtable::value_type value_type
Public typedefs.
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.
bool contains(const key_type &__x) const
Finds whether an element with the given key exists.
_Hashtable::const_reference const_reference
Iterator-related typedefs.
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(value_type &&__x)
Inserts a std::pair into the unordered_multimap.
iterator insert(const value_type &__x)
Inserts a std::pair into the unordered_multimap.
unordered_multimap & operator=(unordered_multimap &&)=default
Move assignment operator.
_Hashtable::hasher hasher
Public typedefs.
_Hashtable::local_iterator local_iterator
Iterator-related typedefs.
void reserve(size_type __n)
Prepare the unordered_multimap for a specified number of elements.
std::pair< const_iterator, const_iterator > equal_range(const key_type &__x) const
Finds a subsequence matching given key.
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.
auto count(const _Kt &__x) const -> decltype(_M_h._M_count_tr(__x))
Finds the number of elements.
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.
_Hashtable::allocator_type allocator_type
Public typedefs.
const_local_iterator begin(size_type __n) const
Returns a read-only (constant) iterator pointing to the first bucket element.
auto find(const _Kt &__x) const -> decltype(_M_h._M_find_tr(__x))
Tries to locate an element in an unordered_multimap.
_Hashtable::const_local_iterator const_local_iterator
Iterator-related typedefs.
unordered_multimap(unordered_multimap &&)=default
Move constructor.
unordered_multimap(const allocator_type &__a)
Creates an unordered_multimap with no elements.
_Hashtable::difference_type difference_type
Iterator-related typedefs.
_Hashtable::size_type size_type
Iterator-related typedefs.
_Hashtable::const_pointer const_pointer
Iterator-related typedefs.
__enable_if_t< is_constructible< value_type, _Pair && >::value, iterator > insert(_Pair &&__x)
Inserts a std::pair into the unordered_multimap.
auto contains(const _Kt &__x) const -> decltype(_M_h._M_find_tr(__x), void(), true)
Finds whether an element with the given key exists.
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.
_Hashtable::const_iterator const_iterator
Iterator-related typedefs.
void insert(initializer_list< value_type > __l)
Attempts to insert a list of elements into the unordered_multimap.
const_iterator cend() const noexcept
size_type max_size() const noexcept
Returns the maximum size of the unordered_multimap.
const_local_iterator cbegin(size_type __n) const
Returns a read-only (constant) iterator pointing to the first bucket element.
bool empty() const noexcept
Returns true if the unordered_multimap is empty.
const_iterator cbegin() const noexcept
_Hashtable::key_type key_type
Public typedefs.
node_type extract(const_iterator __pos)
Extract a node.
const_local_iterator cend(size_type __n) const
Returns a read-only (constant) iterator pointing to one past the last bucket elements.
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.
iterator insert(const_iterator __hint, value_type &&__x)
Inserts a std::pair into the unordered_multimap.
auto equal_range(const _Kt &__x) -> decltype(_M_h._M_equal_range_tr(__x))
Finds a subsequence matching given key.
_Hashtable::key_equal key_equal
Public typedefs.
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.
auto equal_range(const _Kt &__x) const -> decltype(_M_h._M_equal_range_tr(__x))
Finds a subsequence matching given key.
A standard container composed of unique keys (containing at most one of each key value) that associat...
iterator insert(const_iterator __hint, value_type &&__x)
Attempts to insert a std::pair into the unordered_map.
_Hashtable::iterator iterator
Iterator-related typedefs.
void max_load_factor(float __z)
Change the unordered_map maximum load factor.
const mapped_type & at(const key_type &__k) const
Access to unordered_map data.
bool contains(const key_type &__x) const
Finds whether an element with the given key exists.
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.
auto find(const _Kt &__x) -> decltype(_M_h._M_find_tr(__x))
Tries to locate an element in an unordered_map.
unordered_map & operator=(initializer_list< value_type > __l)
Unordered_map list assignment operator.
_Hashtable::const_pointer const_pointer
Iterator-related typedefs.
auto find(const _Kt &__x) const -> decltype(_M_h._M_find_tr(__x))
Tries to locate an element in an unordered_map.
void insert(initializer_list< value_type > __l)
Attempts to insert a list of elements into the unordered_map.
__enable_if_t< is_constructible< value_type, _Pair && >::value, iterator > insert(const_iterator __hint, _Pair &&__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.
mapped_type & at(const key_type &__k)
Access to unordered_map data.
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.
std::pair< iterator, bool > insert(const value_type &__x)
Attempts to insert a std::pair into the unordered_map.
void reserve(size_type __n)
Prepare the unordered_map for a specified number of elements.
const_local_iterator cbegin(size_type __n) const
Returns a read-only (constant) iterator pointing to the first bucket element.
std::pair< const_iterator, const_iterator > equal_range(const key_type &__x) const
Finds a subsequence matching given key.
iterator insert(const_iterator, node_type &&__nh)
Re-insert an extracted node.
_Hashtable::reference reference
Iterator-related typedefs.
iterator insert(const_iterator __hint, const value_type &__x)
Attempts to insert a std::pair into the unordered_map.
_Hashtable::allocator_type allocator_type
Public typedefs.
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.
const_iterator find(const key_type &__x) const
Tries to locate an element in an unordered_map.
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.
auto equal_range(const _Kt &__x) -> decltype(_M_h._M_equal_range_tr(__x))
Finds a subsequence matching given key.
auto contains(const _Kt &__x) const -> decltype(_M_h._M_find_tr(__x), void(), true)
Finds whether an element with the given key exists.
size_type max_size() const noexcept
Returns the maximum size of the unordered_map.
const_iterator end() const noexcept
unordered_map()=default
Default constructor.
_Hashtable::mapped_type mapped_type
Public typedefs.
unordered_map & operator=(unordered_map &&)=default
Move assignment operator.
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.
std::pair< iterator, bool > emplace(_Args &&... __args)
Attempts to build and insert a std::pair into the unordered_map.
const_local_iterator cend(size_type __n) const
Returns a read-only (constant) iterator pointing to one past the last bucket elements.
size_type size() const noexcept
Returns the size of the unordered_map.
__enable_if_t< is_constructible< value_type, _Pair && >::value, pair< iterator, bool > > insert(_Pair &&__x)
Attempts to insert a std::pair into the unordered_map.
mapped_type & operator[](key_type &&__k)
Subscript ( [] ) access to unordered_map data.
std::pair< iterator, bool > insert(value_type &&__x)
Attempts to insert a std::pair into the unordered_map.
_Hashtable::hasher hasher
Public typedefs.
pair< iterator, bool > insert_or_assign(const key_type &__k, _Obj &&__obj)
Attempts to insert a std::pair into the unordered_map.
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.
mapped_type & operator[](const key_type &__k)
Subscript ( [] ) access to unordered_map data.
pair< iterator, bool > try_emplace(const key_type &__k, _Args &&... __args)
Attempts to build and insert a std::pair into the unordered_map.
const_iterator begin() const noexcept
key_equal key_eq() const
Returns the key comparison object with which the unordered_map was constructed.
_Hashtable::const_reference const_reference
Iterator-related typedefs.
_Hashtable::key_equal key_equal
Public typedefs.
_Hashtable::local_iterator local_iterator
Iterator-related typedefs.
iterator erase(iterator __position)
Erases an element from an unordered_map.
const_iterator cend() const noexcept
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.
auto equal_range(const _Kt &__x) const -> decltype(_M_h._M_equal_range_tr(__x))
Finds a subsequence matching given key.
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.
_Hashtable::const_iterator const_iterator
Iterator-related typedefs.
_Hashtable::size_type size_type
Iterator-related typedefs.
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.
unordered_map & operator=(const unordered_map &)=default
Copy assignment operator.
_Hashtable::difference_type difference_type
Iterator-related typedefs.
auto count(const _Kt &__x) const -> decltype(_M_h._M_count_tr(__x))
Finds the number of elements.
_Hashtable::const_local_iterator const_local_iterator
Iterator-related typedefs.
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.
_Hashtable::value_type value_type
Public typedefs.
void rehash(size_type __n)
May rehash the unordered_map.
const_iterator cbegin() const noexcept