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;
127 typedef typename _Hashtable::local_iterator local_iterator;
128 typedef typename _Hashtable::const_local_iterator const_local_iterator;
129 typedef typename _Hashtable::size_type size_type;
130 typedef typename _Hashtable::difference_type difference_type;
133 #if __cplusplus > 201402L
134 using node_type =
typename _Hashtable::node_type;
135 using insert_return_type =
typename _Hashtable::insert_return_type;
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 : _M_h(
std::
move(__umap._M_h), __a)
228 const hasher& __hf = hasher(),
229 const key_equal& __eql = key_equal(),
230 const allocator_type& __a = allocator_type())
231 : _M_h(__l, __n, __hf, __eql, __a)
239 const allocator_type& __a)
243 template<
typename _InputIterator>
246 const allocator_type& __a)
247 :
unordered_map(__first, __last, __n, hasher(), key_equal(), __a)
250 template<
typename _InputIterator>
252 size_type __n,
const hasher& __hf,
253 const allocator_type& __a)
254 :
unordered_map(__first, __last, __n, __hf, key_equal(), __a)
259 const allocator_type& __a)
264 size_type __n,
const hasher& __hf,
265 const allocator_type& __a)
298 {
return _M_h.get_allocator(); }
303 _GLIBCXX_NODISCARD
bool
305 {
return _M_h.empty(); }
310 {
return _M_h.size(); }
315 {
return _M_h.max_size(); }
325 {
return _M_h.begin(); }
334 {
return _M_h.begin(); }
337 cbegin() const noexcept
338 {
return _M_h.begin(); }
347 {
return _M_h.end(); }
356 {
return _M_h.end(); }
359 cend() const noexcept
360 {
return _M_h.end(); }
385 template<
typename... _Args>
388 {
return _M_h.emplace(std::forward<_Args>(__args)...); }
416 template<
typename... _Args>
419 {
return _M_h.emplace_hint(__pos, std::forward<_Args>(__args)...); }
421 #if __cplusplus > 201402L
424 extract(const_iterator __pos)
426 __glibcxx_assert(__pos !=
end());
427 return _M_h.extract(__pos);
433 {
return _M_h.extract(__key); }
438 {
return _M_h._M_reinsert_node(
std::move(__nh)); }
442 insert(const_iterator, node_type&& __nh)
443 {
return _M_h._M_reinsert_node(
std::move(__nh)).position; }
445 #define __cpp_lib_unordered_map_try_emplace 201411
468 template <
typename... _Args>
470 try_emplace(
const key_type& __k, _Args&&... __args)
472 iterator __i =
find(__k);
478 std::forward<_Args>(__args)...))
486 template <
typename... _Args>
488 try_emplace(
key_type&& __k, _Args&&... __args)
490 iterator __i =
find(__k);
496 std::forward<_Args>(__args)...))
531 template <
typename... _Args>
533 try_emplace(const_iterator __hint,
const key_type& __k,
536 iterator __i =
find(__k);
541 std::forward<_Args>(__args)...));
546 template <
typename... _Args>
548 try_emplace(const_iterator __hint,
key_type&& __k, _Args&&... __args)
550 iterator __i =
find(__k);
555 std::forward<_Args>(__args)...));
580 {
return _M_h.insert(__x); }
588 template<
typename _Pair>
589 __enable_if_t<is_constructible<value_type, _Pair&&>::value,
590 pair<iterator, bool>>
592 {
return _M_h.emplace(std::forward<_Pair>(__x)); }
618 insert(const_iterator __hint,
const value_type& __x)
619 {
return _M_h.insert(__hint, __x); }
624 insert(const_iterator __hint, value_type&& __x)
625 {
return _M_h.insert(__hint,
std::move(__x)); }
627 template<
typename _Pair>
628 __enable_if_t<is_constructible<value_type, _Pair&&>::value, iterator>
629 insert(const_iterator __hint, _Pair&& __x)
630 {
return _M_h.emplace_hint(__hint, std::forward<_Pair>(__x)); }
642 template<
typename _InputIterator>
644 insert(_InputIterator __first, _InputIterator __last)
645 { _M_h.insert(__first, __last); }
656 { _M_h.insert(__l); }
659 #if __cplusplus > 201402L
680 template <
typename _Obj>
682 insert_or_assign(
const key_type& __k, _Obj&& __obj)
693 (*__i).second = std::forward<_Obj>(__obj);
698 template <
typename _Obj>
700 insert_or_assign(
key_type&& __k, _Obj&& __obj)
702 iterator __i =
find(__k);
711 (*__i).second = std::forward<_Obj>(__obj);
741 template <
typename _Obj>
743 insert_or_assign(const_iterator __hint,
const key_type& __k,
746 iterator __i =
find(__k);
752 std::forward<_Obj>(__obj)));
754 (*__i).second = std::forward<_Obj>(__obj);
759 template <
typename _Obj>
761 insert_or_assign(const_iterator __hint,
key_type&& __k, _Obj&& __obj)
763 iterator __i =
find(__k);
769 std::forward<_Obj>(__obj)));
771 (*__i).second = std::forward<_Obj>(__obj);
792 {
return _M_h.erase(__position); }
797 {
return _M_h.erase(__position); }
814 {
return _M_h.erase(__x); }
831 erase(const_iterator __first, const_iterator __last)
832 {
return _M_h.erase(__first, __last); }
856 noexcept( noexcept(_M_h.swap(__x._M_h)) )
857 { _M_h.swap(__x._M_h); }
859 #if __cplusplus > 201402L
860 template<
typename,
typename,
typename>
861 friend class std::_Hash_merge_helper;
863 template<
typename _H2,
typename _P2>
867 using _Merge_helper = _Hash_merge_helper<unordered_map, _H2, _P2>;
868 _M_h._M_merge_unique(_Merge_helper::_S_get_table(__source));
871 template<
typename _H2,
typename _P2>
873 merge(unordered_map<_Key, _Tp, _H2, _P2, _Alloc>&& __source)
876 template<
typename _H2,
typename _P2>
878 merge(unordered_multimap<_Key, _Tp, _H2, _P2, _Alloc>& __source)
880 using _Merge_helper = _Hash_merge_helper<unordered_map, _H2, _P2>;
881 _M_h._M_merge_unique(_Merge_helper::_S_get_table(__source));
884 template<
typename _H2,
typename _P2>
886 merge(unordered_multimap<_Key, _Tp, _H2, _P2, _Alloc>&& __source)
896 {
return _M_h.hash_function(); }
902 {
return _M_h.key_eq(); }
920 {
return _M_h.find(__x); }
924 {
return _M_h.find(__x); }
938 {
return _M_h.count(__x); }
940 #if __cplusplus > 201703L
948 {
return _M_h.find(__x) != _M_h.end(); }
962 {
return _M_h.equal_range(__x); }
966 {
return _M_h.equal_range(__x); }
984 {
return _M_h[__k]; }
1001 {
return _M_h.at(__k); }
1005 {
return _M_h.at(__k); }
1013 {
return _M_h.bucket_count(); }
1018 {
return _M_h.max_bucket_count(); }
1026 bucket_size(size_type __n)
const
1027 {
return _M_h.bucket_size(__n); }
1035 bucket(
const key_type& __key)
const
1036 {
return _M_h.bucket(__key); }
1046 {
return _M_h.begin(__n); }
1055 const_local_iterator
1057 {
return _M_h.begin(__n); }
1059 const_local_iterator
1060 cbegin(size_type __n)
const
1061 {
return _M_h.cbegin(__n); }
1072 {
return _M_h.end(__n); }
1081 const_local_iterator
1083 {
return _M_h.end(__n); }
1085 const_local_iterator
1086 cend(size_type __n)
const
1087 {
return _M_h.cend(__n); }
1095 {
return _M_h.load_factor(); }
1101 {
return _M_h.max_load_factor(); }
1109 { _M_h.max_load_factor(__z); }
1120 { _M_h.rehash(__n); }
1131 { _M_h.reserve(__n); }
1133 template<
typename _Key1,
typename _Tp1,
typename _Hash1,
typename _Pred1,
1140 #if __cpp_deduction_guides >= 201606
1142 template<
typename _InputIterator,
1143 typename _Hash = hash<__iter_key_t<_InputIterator>>,
1144 typename _Pred = equal_to<__iter_key_t<_InputIterator>>,
1145 typename _Allocator = allocator<__iter_to_alloc_t<_InputIterator>>,
1146 typename = _RequireInputIter<_InputIterator>,
1147 typename = _RequireNotAllocatorOrIntegral<_Hash>,
1148 typename = _RequireNotAllocator<_Pred>,
1149 typename = _RequireAllocator<_Allocator>>
1150 unordered_map(_InputIterator, _InputIterator,
1151 typename unordered_map<int, int>::size_type = {},
1152 _Hash = _Hash(), _Pred = _Pred(), _Allocator = _Allocator())
1153 -> unordered_map<__iter_key_t<_InputIterator>,
1154 __iter_val_t<_InputIterator>,
1155 _Hash, _Pred, _Allocator>;
1157 template<
typename _Key,
typename _Tp,
typename _Hash = hash<_Key>,
1158 typename _Pred = equal_to<_Key>,
1159 typename _Allocator = allocator<pair<const _Key, _Tp>>,
1160 typename = _RequireNotAllocatorOrIntegral<_Hash>,
1161 typename = _RequireNotAllocator<_Pred>,
1162 typename = _RequireAllocator<_Allocator>>
1163 unordered_map(initializer_list<pair<_Key, _Tp>>,
1164 typename unordered_map<int, int>::size_type = {},
1165 _Hash = _Hash(), _Pred = _Pred(), _Allocator = _Allocator())
1166 -> unordered_map<_Key, _Tp, _Hash, _Pred, _Allocator>;
1168 template<
typename _InputIterator,
typename _Allocator,
1169 typename = _RequireInputIter<_InputIterator>,
1170 typename = _RequireAllocator<_Allocator>>
1171 unordered_map(_InputIterator, _InputIterator,
1172 typename unordered_map<int, int>::size_type, _Allocator)
1173 -> unordered_map<__iter_key_t<_InputIterator>,
1174 __iter_val_t<_InputIterator>,
1175 hash<__iter_key_t<_InputIterator>>,
1176 equal_to<__iter_key_t<_InputIterator>>,
1179 template<
typename _InputIterator,
typename _Allocator,
1180 typename = _RequireInputIter<_InputIterator>,
1181 typename = _RequireAllocator<_Allocator>>
1182 unordered_map(_InputIterator, _InputIterator, _Allocator)
1183 -> unordered_map<__iter_key_t<_InputIterator>,
1184 __iter_val_t<_InputIterator>,
1185 hash<__iter_key_t<_InputIterator>>,
1186 equal_to<__iter_key_t<_InputIterator>>,
1189 template<
typename _InputIterator,
typename _Hash,
typename _Allocator,
1190 typename = _RequireInputIter<_InputIterator>,
1191 typename = _RequireNotAllocatorOrIntegral<_Hash>,
1192 typename = _RequireAllocator<_Allocator>>
1193 unordered_map(_InputIterator, _InputIterator,
1194 typename unordered_map<int, int>::size_type,
1196 -> unordered_map<__iter_key_t<_InputIterator>,
1197 __iter_val_t<_InputIterator>, _Hash,
1198 equal_to<__iter_key_t<_InputIterator>>, _Allocator>;
1200 template<
typename _Key,
typename _Tp,
typename _Allocator,
1201 typename = _RequireAllocator<_Allocator>>
1202 unordered_map(initializer_list<pair<_Key, _Tp>>,
1203 typename unordered_map<int, int>::size_type,
1205 -> unordered_map<_Key, _Tp, hash<_Key>, equal_to<_Key>, _Allocator>;
1207 template<
typename _Key,
typename _Tp,
typename _Allocator,
1208 typename = _RequireAllocator<_Allocator>>
1209 unordered_map(initializer_list<pair<_Key, _Tp>>, _Allocator)
1210 -> unordered_map<_Key, _Tp, hash<_Key>, equal_to<_Key>, _Allocator>;
1212 template<
typename _Key,
typename _Tp,
typename _Hash,
typename _Allocator,
1213 typename = _RequireNotAllocatorOrIntegral<_Hash>,
1214 typename = _RequireAllocator<_Allocator>>
1215 unordered_map(initializer_list<pair<_Key, _Tp>>,
1216 typename unordered_map<int, int>::size_type,
1218 -> unordered_map<_Key, _Tp, _Hash, equal_to<_Key>, _Allocator>;
1245 template<
typename _Key,
typename _Tp,
1246 typename _Hash = hash<_Key>,
1247 typename _Pred = equal_to<_Key>,
1248 typename _Alloc = allocator<std::pair<const _Key, _Tp>>>
1259 typedef typename _Hashtable::value_type value_type;
1260 typedef typename _Hashtable::mapped_type mapped_type;
1261 typedef typename _Hashtable::hasher hasher;
1262 typedef typename _Hashtable::key_equal key_equal;
1263 typedef typename _Hashtable::allocator_type allocator_type;
1269 typedef typename _Hashtable::const_pointer const_pointer;
1270 typedef typename _Hashtable::reference reference;
1271 typedef typename _Hashtable::const_reference const_reference;
1272 typedef typename _Hashtable::iterator iterator;
1273 typedef typename _Hashtable::const_iterator const_iterator;
1274 typedef typename _Hashtable::local_iterator local_iterator;
1275 typedef typename _Hashtable::const_local_iterator const_local_iterator;
1276 typedef typename _Hashtable::size_type size_type;
1277 typedef typename _Hashtable::difference_type difference_type;
1280 #if __cplusplus > 201402L
1281 using node_type =
typename _Hashtable::node_type;
1298 const hasher& __hf = hasher(),
1299 const key_equal& __eql = key_equal(),
1300 const allocator_type& __a = allocator_type())
1301 : _M_h(__n, __hf, __eql, __a)
1317 template<
typename _InputIterator>
1320 const hasher& __hf = hasher(),
1321 const key_equal& __eql = key_equal(),
1322 const allocator_type& __a = allocator_type())
1323 : _M_h(__first, __last, __n, __hf, __eql, __a)
1347 const allocator_type& __a)
1348 : _M_h(__ummap._M_h, __a)
1357 const allocator_type& __a)
1358 : _M_h(
std::
move(__ummap._M_h), __a)
1374 const hasher& __hf = hasher(),
1375 const key_equal& __eql = key_equal(),
1376 const allocator_type& __a = allocator_type())
1377 : _M_h(__l, __n, __hf, __eql, __a)
1385 const allocator_type& __a)
1389 template<
typename _InputIterator>
1392 const allocator_type& __a)
1396 template<
typename _InputIterator>
1398 size_type __n,
const hasher& __hf,
1399 const allocator_type& __a)
1405 const allocator_type& __a)
1410 size_type __n,
const hasher& __hf,
1411 const allocator_type& __a)
1444 {
return _M_h.get_allocator(); }
1449 _GLIBCXX_NODISCARD
bool
1451 {
return _M_h.empty(); }
1456 {
return _M_h.size(); }
1461 {
return _M_h.max_size(); }
1471 {
return _M_h.begin(); }
1480 {
return _M_h.begin(); }
1483 cbegin() const noexcept
1484 {
return _M_h.begin(); }
1493 {
return _M_h.end(); }
1502 {
return _M_h.end(); }
1505 cend() const noexcept
1506 {
return _M_h.end(); }
1526 template<
typename... _Args>
1529 {
return _M_h.emplace(std::forward<_Args>(__args)...); }
1553 template<
typename... _Args>
1556 {
return _M_h.emplace_hint(__pos, std::forward<_Args>(__args)...); }
1570 {
return _M_h.insert(__x); }
1576 template<
typename _Pair>
1577 __enable_if_t<is_constructible<value_type, _Pair&&>::value, iterator>
1579 {
return _M_h.emplace(std::forward<_Pair>(__x)); }
1603 insert(const_iterator __hint,
const value_type& __x)
1604 {
return _M_h.insert(__hint, __x); }
1609 insert(const_iterator __hint, value_type&& __x)
1610 {
return _M_h.insert(__hint,
std::move(__x)); }
1612 template<
typename _Pair>
1613 __enable_if_t<is_constructible<value_type, _Pair&&>::value, iterator>
1614 insert(const_iterator __hint, _Pair&& __x)
1615 {
return _M_h.emplace_hint(__hint, std::forward<_Pair>(__x)); }
1627 template<
typename _InputIterator>
1629 insert(_InputIterator __first, _InputIterator __last)
1630 { _M_h.insert(__first, __last); }
1642 { _M_h.insert(__l); }
1644 #if __cplusplus > 201402L
1647 extract(const_iterator __pos)
1649 __glibcxx_assert(__pos !=
end());
1650 return _M_h.extract(__pos);
1656 {
return _M_h.extract(__key); }
1661 {
return _M_h._M_reinsert_node_multi(cend(),
std::move(__nh)); }
1665 insert(const_iterator __hint, node_type&& __nh)
1666 {
return _M_h._M_reinsert_node_multi(__hint,
std::move(__nh)); }
1685 {
return _M_h.erase(__position); }
1690 {
return _M_h.erase(__position); }
1706 {
return _M_h.erase(__x); }
1724 erase(const_iterator __first, const_iterator __last)
1725 {
return _M_h.erase(__first, __last); }
1749 noexcept( noexcept(_M_h.swap(__x._M_h)) )
1750 { _M_h.swap(__x._M_h); }
1752 #if __cplusplus > 201402L
1753 template<
typename,
typename,
typename>
1754 friend class std::_Hash_merge_helper;
1756 template<
typename _H2,
typename _P2>
1761 = _Hash_merge_helper<unordered_multimap, _H2, _P2>;
1762 _M_h._M_merge_multi(_Merge_helper::_S_get_table(__source));
1765 template<
typename _H2,
typename _P2>
1767 merge(unordered_multimap<_Key, _Tp, _H2, _P2, _Alloc>&& __source)
1768 { merge(__source); }
1770 template<
typename _H2,
typename _P2>
1772 merge(unordered_map<_Key, _Tp, _H2, _P2, _Alloc>& __source)
1775 = _Hash_merge_helper<unordered_multimap, _H2, _P2>;
1776 _M_h._M_merge_multi(_Merge_helper::_S_get_table(__source));
1779 template<
typename _H2,
typename _P2>
1781 merge(unordered_map<_Key, _Tp, _H2, _P2, _Alloc>&& __source)
1782 { merge(__source); }
1791 {
return _M_h.hash_function(); }
1797 {
return _M_h.key_eq(); }
1815 {
return _M_h.find(__x); }
1819 {
return _M_h.find(__x); }
1829 {
return _M_h.count(__x); }
1831 #if __cplusplus > 201703L
1838 contains(
const key_type& __x)
const
1839 {
return _M_h.find(__x) != _M_h.end(); }
1851 {
return _M_h.equal_range(__x); }
1855 {
return _M_h.equal_range(__x); }
1863 {
return _M_h.bucket_count(); }
1868 {
return _M_h.max_bucket_count(); }
1876 bucket_size(size_type __n)
const
1877 {
return _M_h.bucket_size(__n); }
1885 bucket(
const key_type& __key)
const
1886 {
return _M_h.bucket(__key); }
1896 {
return _M_h.begin(__n); }
1905 const_local_iterator
1907 {
return _M_h.begin(__n); }
1909 const_local_iterator
1910 cbegin(size_type __n)
const
1911 {
return _M_h.cbegin(__n); }
1922 {
return _M_h.end(__n); }
1931 const_local_iterator
1933 {
return _M_h.end(__n); }
1935 const_local_iterator
1936 cend(size_type __n)
const
1937 {
return _M_h.cend(__n); }
1945 {
return _M_h.load_factor(); }
1951 {
return _M_h.max_load_factor(); }
1959 { _M_h.max_load_factor(__z); }
1970 { _M_h.rehash(__n); }
1981 { _M_h.reserve(__n); }
1983 template<
typename _Key1,
typename _Tp1,
typename _Hash1,
typename _Pred1,
1987 _Hash1, _Pred1, _Alloc1>&,
1989 _Hash1, _Pred1, _Alloc1>&);
1992 #if __cpp_deduction_guides >= 201606
1994 template<
typename _InputIterator,
1995 typename _Hash = hash<__iter_key_t<_InputIterator>>,
1996 typename _Pred = equal_to<__iter_key_t<_InputIterator>>,
1997 typename _Allocator = allocator<__iter_to_alloc_t<_InputIterator>>,
1998 typename = _RequireInputIter<_InputIterator>,
1999 typename = _RequireNotAllocatorOrIntegral<_Hash>,
2000 typename = _RequireNotAllocator<_Pred>,
2001 typename = _RequireAllocator<_Allocator>>
2002 unordered_multimap(_InputIterator, _InputIterator,
2003 unordered_multimap<int, int>::size_type = {},
2004 _Hash = _Hash(), _Pred = _Pred(),
2005 _Allocator = _Allocator())
2006 -> unordered_multimap<__iter_key_t<_InputIterator>,
2007 __iter_val_t<_InputIterator>, _Hash, _Pred,
2010 template<
typename _Key,
typename _Tp,
typename _Hash = hash<_Key>,
2011 typename _Pred = equal_to<_Key>,
2012 typename _Allocator = allocator<pair<const _Key, _Tp>>,
2013 typename = _RequireNotAllocatorOrIntegral<_Hash>,
2014 typename = _RequireNotAllocator<_Pred>,
2015 typename = _RequireAllocator<_Allocator>>
2016 unordered_multimap(initializer_list<pair<_Key, _Tp>>,
2017 unordered_multimap<int, int>::size_type = {},
2018 _Hash = _Hash(), _Pred = _Pred(),
2019 _Allocator = _Allocator())
2020 -> unordered_multimap<_Key, _Tp, _Hash, _Pred, _Allocator>;
2022 template<
typename _InputIterator,
typename _Allocator,
2023 typename = _RequireInputIter<_InputIterator>,
2024 typename = _RequireAllocator<_Allocator>>
2025 unordered_multimap(_InputIterator, _InputIterator,
2026 unordered_multimap<int, int>::size_type, _Allocator)
2027 -> unordered_multimap<__iter_key_t<_InputIterator>,
2028 __iter_val_t<_InputIterator>,
2029 hash<__iter_key_t<_InputIterator>>,
2030 equal_to<__iter_key_t<_InputIterator>>, _Allocator>;
2032 template<
typename _InputIterator,
typename _Allocator,
2033 typename = _RequireInputIter<_InputIterator>,
2034 typename = _RequireAllocator<_Allocator>>
2035 unordered_multimap(_InputIterator, _InputIterator, _Allocator)
2036 -> unordered_multimap<__iter_key_t<_InputIterator>,
2037 __iter_val_t<_InputIterator>,
2038 hash<__iter_key_t<_InputIterator>>,
2039 equal_to<__iter_key_t<_InputIterator>>, _Allocator>;
2041 template<
typename _InputIterator,
typename _Hash,
typename _Allocator,
2042 typename = _RequireInputIter<_InputIterator>,
2043 typename = _RequireNotAllocatorOrIntegral<_Hash>,
2044 typename = _RequireAllocator<_Allocator>>
2045 unordered_multimap(_InputIterator, _InputIterator,
2046 unordered_multimap<int, int>::size_type, _Hash,
2048 -> unordered_multimap<__iter_key_t<_InputIterator>,
2049 __iter_val_t<_InputIterator>, _Hash,
2050 equal_to<__iter_key_t<_InputIterator>>, _Allocator>;
2052 template<
typename _Key,
typename _Tp,
typename _Allocator,
2053 typename = _RequireAllocator<_Allocator>>
2054 unordered_multimap(initializer_list<pair<_Key, _Tp>>,
2055 unordered_multimap<int, int>::size_type,
2057 -> unordered_multimap<_Key, _Tp, hash<_Key>, equal_to<_Key>, _Allocator>;
2059 template<
typename _Key,
typename _Tp,
typename _Allocator,
2060 typename = _RequireAllocator<_Allocator>>
2061 unordered_multimap(initializer_list<pair<_Key, _Tp>>, _Allocator)
2062 -> unordered_multimap<_Key, _Tp, hash<_Key>, equal_to<_Key>, _Allocator>;
2064 template<
typename _Key,
typename _Tp,
typename _Hash,
typename _Allocator,
2065 typename = _RequireNotAllocatorOrIntegral<_Hash>,
2066 typename = _RequireAllocator<_Allocator>>
2067 unordered_multimap(initializer_list<pair<_Key, _Tp>>,
2068 unordered_multimap<int, int>::size_type,
2070 -> unordered_multimap<_Key, _Tp, _Hash, equal_to<_Key>, _Allocator>;
2074 template<
class _Key,
class _Tp,
class _Hash,
class _Pred,
class _Alloc>
2076 swap(unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
2077 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
2078 noexcept(noexcept(__x.swap(__y)))
2081 template<
class _Key,
class _Tp,
class _Hash,
class _Pred,
class _Alloc>
2083 swap(unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
2084 unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
2085 noexcept(noexcept(__x.swap(__y)))
2088 template<
class _Key,
class _Tp,
class _Hash,
class _Pred,
class _Alloc>
2090 operator==(
const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
2091 const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
2092 {
return __x._M_h._M_equal(__y._M_h); }
2094 #if __cpp_impl_three_way_comparison < 201907L
2095 template<
class _Key,
class _Tp,
class _Hash,
class _Pred,
class _Alloc>
2097 operator!=(
const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
2098 const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
2099 {
return !(__x == __y); }
2102 template<
class _Key,
class _Tp,
class _Hash,
class _Pred,
class _Alloc>
2104 operator==(
const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
2105 const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
2106 {
return __x._M_h._M_equal(__y._M_h); }
2108 #if __cpp_impl_three_way_comparison < 201907L
2109 template<
class _Key,
class _Tp,
class _Hash,
class _Pred,
class _Alloc>
2111 operator!=(
const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
2112 const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
2113 {
return !(__x == __y); }
2116 _GLIBCXX_END_NAMESPACE_CONTAINER
2118 #if __cplusplus > 201402L
2120 template<
typename _Key,
typename _Val,
typename _Hash1,
typename _Eq1,
2121 typename _Alloc,
typename _Hash2,
typename _Eq2>
2122 struct _Hash_merge_helper<
2123 _GLIBCXX_STD_C::unordered_map<_Key, _Val, _Hash1, _Eq1, _Alloc>,
2127 template<
typename... _Tp>
2128 using unordered_map = _GLIBCXX_STD_C::unordered_map<_Tp...>;
2129 template<
typename... _Tp>
2130 using unordered_multimap = _GLIBCXX_STD_C::unordered_multimap<_Tp...>;
2132 friend unordered_map<_Key, _Val, _Hash1, _Eq1, _Alloc>;
2135 _S_get_table(unordered_map<_Key, _Val, _Hash2, _Eq2, _Alloc>& __map)
2136 {
return __map._M_h; }
2139 _S_get_table(unordered_multimap<_Key, _Val, _Hash2, _Eq2, _Alloc>& __map)
2140 {
return __map._M_h; }
2144 template<
typename _Key,
typename _Val,
typename _Hash1,
typename _Eq1,
2145 typename _Alloc,
typename _Hash2,
typename _Eq2>
2146 struct _Hash_merge_helper<
2147 _GLIBCXX_STD_C::unordered_multimap<_Key, _Val, _Hash1, _Eq1, _Alloc>,
2151 template<
typename... _Tp>
2152 using unordered_map = _GLIBCXX_STD_C::unordered_map<_Tp...>;
2153 template<
typename... _Tp>
2154 using unordered_multimap = _GLIBCXX_STD_C::unordered_multimap<_Tp...>;
2156 friend unordered_multimap<_Key, _Val, _Hash1, _Eq1, _Alloc>;
2159 _S_get_table(unordered_map<_Key, _Val, _Hash2, _Eq2, _Alloc>& __map)
2160 {
return __map._M_h; }
2163 _S_get_table(unordered_multimap<_Key, _Val, _Hash2, _Eq2, _Alloc>& __map)
2164 {
return __map._M_h; }
2168 _GLIBCXX_END_NAMESPACE_VERSION
constexpr piecewise_construct_t piecewise_construct
Tag for piecewise construction of std::pair objects.
constexpr std::remove_reference< _Tp >::type && move(_Tp &&__t) noexcept
Convert a value to an rvalue.
constexpr tuple< _Elements &&... > forward_as_tuple(_Elements &&... __args) noexcept
std::forward_as_tuple
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].
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...
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.
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.
std::pair< iterator, iterator > equal_range(const key_type &__x)
Finds a subsequence matching given key.
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.
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.
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.
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.
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 __hint, const value_type &__x)
Attempts to 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.
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.
void rehash(size_type __n)
May rehash the unordered_map.