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,
114 typedef typename _Hashtable::hasher
hasher;
133 #if __cplusplus > 201402L
155 : _M_h(__n, __hf, __eql, __a)
171 template<
typename _InputIterator>
177 : _M_h(__first, __last, __n, __hf, __eql, __a)
202 : _M_h(__umap._M_h, __a)
212 noexcept( noexcept(_Hashtable(
std::move(__umap._M_h), __a)) )
213 : _M_h(
std::
move(__umap._M_h), __a)
232 : _M_h(__l, __n, __hf, __eql, __a)
244 template<
typename _InputIterator>
251 template<
typename _InputIterator>
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(); }
339 {
return _M_h.begin(); }
348 {
return _M_h.end(); }
357 {
return _M_h.end(); }
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>
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,
564 {
return _M_h.emplace(std::forward<_Pair>(__x)); }
591 {
return _M_h.insert(__hint, __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>
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>
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); }
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(); }
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); }
1053 {
return _M_h.begin(__n); }
1057 {
return _M_h.cbegin(__n); }
1068 {
return _M_h.end(__n); }
1079 {
return _M_h.end(__n); }
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,
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>>,
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,
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,
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>>,
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>>,
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>>>
1276 #if __cplusplus > 201402L
1297 : _M_h(__n, __hf, __eql, __a)
1313 template<
typename _InputIterator>
1319 : _M_h(__first, __last, __n, __hf, __eql, __a)
1344 : _M_h(__ummap._M_h, __a)
1354 noexcept( noexcept(_Hashtable(
std::move(__ummap._M_h), __a)) )
1355 : _M_h(
std::
move(__ummap._M_h), __a)
1374 : _M_h(__l, __n, __hf, __eql, __a)
1386 template<
typename _InputIterator>
1393 template<
typename _InputIterator>
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(); }
1481 {
return _M_h.begin(); }
1490 {
return _M_h.end(); }
1499 {
return _M_h.end(); }
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)); }
1601 {
return _M_h.insert(__hint, __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>
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); }
1682 {
return _M_h.erase(__position); }
1687 {
return _M_h.erase(__position); }
1703 {
return _M_h.erase(__x); }
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(); }
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); }
1951 {
return _M_h.begin(__n); }
1955 {
return _M_h.cbegin(__n); }
1966 {
return _M_h.end(__n); }
1977 {
return _M_h.end(__n); }
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,
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>>,
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,
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,
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>>,
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>>,
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.
Primary class template hash.
The standard allocator, as per C++03 [20.4.1].
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.
_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.
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.
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.
const_iterator find(const key_type &__x) const
Tries to locate an element in an unordered_multimap.
_Hashtable::mapped_type mapped_type
Public typedefs.
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.
_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.
std::pair< iterator, iterator > equal_range(const key_type &__x)
Finds a subsequence matching given key.
_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.
std::pair< const_iterator, const_iterator > equal_range(const key_type &__x) const
Finds a subsequence matching given key.
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.
_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.
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.
_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.
_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.
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.
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.
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.
__enable_if_t< is_constructible< value_type, _Pair && >::value, iterator > insert(_Pair &&__x)
Inserts a std::pair into the unordered_multimap.
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.
__enable_if_t< is_constructible< value_type, _Pair && >::value, iterator > insert(const_iterator __hint, _Pair &&__x)
Inserts a std::pair into the unordered_multimap.
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.
_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.
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.
std::pair< iterator, bool > insert(const 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.
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.
_Hashtable::const_pointer const_pointer
Iterator-related typedefs.
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.
const mapped_type & at(const key_type &__k) const
Access to unordered_map data.
mapped_type & operator[](key_type &&__k)
Subscript ( [] ) access to unordered_map data.
std::pair< const_iterator, const_iterator > equal_range(const key_type &__x) const
Finds a subsequence matching given key.
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.
const_local_iterator cbegin(size_type __n) const
Returns a read-only (constant) iterator pointing to the first bucket element.
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.
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.
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.
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.
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.
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.
unordered_map & operator=(unordered_map &&)=default
Move assignment operator.
mapped_type & at(const key_type &__k)
Access to unordered_map data.
_Hashtable::hasher hasher
Public typedefs.
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.
_Hashtable::const_reference const_reference
Iterator-related typedefs.
_Hashtable::key_equal key_equal
Public typedefs.
_Hashtable::local_iterator local_iterator
Iterator-related typedefs.
__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.
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.
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.
_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.
std::pair< iterator, bool > insert(value_type &&__x)
Attempts to insert a std::pair into the 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.
__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.
_Hashtable::difference_type difference_type
Iterator-related typedefs.
_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