30#ifndef _UNORDERED_MAP_H
31#define _UNORDERED_MAP_H
33namespace 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); }
586 {
return _M_h.insert(std::move(__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
660#define __cpp_lib_unordered_map_insertion 201411
681 template <
typename _Obj>
683 insert_or_assign(
const key_type& __k, _Obj&& __obj)
694 (*__i).second = std::forward<_Obj>(__obj);
699 template <
typename _Obj>
701 insert_or_assign(
key_type&& __k, _Obj&& __obj)
703 iterator __i =
find(__k);
712 (*__i).second = std::forward<_Obj>(__obj);
742 template <
typename _Obj>
744 insert_or_assign(const_iterator __hint,
const key_type& __k,
747 iterator __i =
find(__k);
753 std::forward<_Obj>(__obj)));
755 (*__i).second = std::forward<_Obj>(__obj);
760 template <
typename _Obj>
762 insert_or_assign(const_iterator __hint,
key_type&& __k, _Obj&& __obj)
764 iterator __i =
find(__k);
770 std::forward<_Obj>(__obj)));
772 (*__i).second = std::forward<_Obj>(__obj);
793 {
return _M_h.erase(__position); }
798 {
return _M_h.erase(__position); }
815 {
return _M_h.erase(__x); }
832 erase(const_iterator __first, const_iterator __last)
833 {
return _M_h.erase(__first, __last); }
857 noexcept(
noexcept(_M_h.swap(__x._M_h)) )
858 { _M_h.swap(__x._M_h); }
860#if __cplusplus > 201402L
861 template<
typename,
typename,
typename>
862 friend class std::_Hash_merge_helper;
864 template<
typename _H2,
typename _P2>
868 using _Merge_helper = _Hash_merge_helper<unordered_map, _H2, _P2>;
869 _M_h._M_merge_unique(_Merge_helper::_S_get_table(__source));
872 template<
typename _H2,
typename _P2>
874 merge(unordered_map<_Key, _Tp, _H2, _P2, _Alloc>&& __source)
877 template<
typename _H2,
typename _P2>
879 merge(unordered_multimap<_Key, _Tp, _H2, _P2, _Alloc>& __source)
881 using _Merge_helper = _Hash_merge_helper<unordered_map, _H2, _P2>;
882 _M_h._M_merge_unique(_Merge_helper::_S_get_table(__source));
885 template<
typename _H2,
typename _P2>
887 merge(unordered_multimap<_Key, _Tp, _H2, _P2, _Alloc>&& __source)
897 {
return _M_h.hash_function(); }
903 {
return _M_h.key_eq(); }
921 {
return _M_h.find(__x); }
925 {
return _M_h.find(__x); }
939 {
return _M_h.count(__x); }
941#if __cplusplus > 201703L
949 {
return _M_h.find(__x) != _M_h.end(); }
963 {
return _M_h.equal_range(__x); }
967 {
return _M_h.equal_range(__x); }
985 {
return _M_h[__k]; }
989 {
return _M_h[std::move(__k)]; }
1002 {
return _M_h.at(__k); }
1006 {
return _M_h.at(__k); }
1014 {
return _M_h.bucket_count(); }
1019 {
return _M_h.max_bucket_count(); }
1027 bucket_size(size_type __n)
const
1028 {
return _M_h.bucket_size(__n); }
1036 bucket(
const key_type& __key)
const
1037 {
return _M_h.bucket(__key); }
1047 {
return _M_h.begin(__n); }
1056 const_local_iterator
1058 {
return _M_h.begin(__n); }
1060 const_local_iterator
1061 cbegin(size_type __n)
const
1062 {
return _M_h.cbegin(__n); }
1073 {
return _M_h.end(__n); }
1082 const_local_iterator
1084 {
return _M_h.end(__n); }
1086 const_local_iterator
1087 cend(size_type __n)
const
1088 {
return _M_h.cend(__n); }
1096 {
return _M_h.load_factor(); }
1102 {
return _M_h.max_load_factor(); }
1110 { _M_h.max_load_factor(__z); }
1121 { _M_h.rehash(__n); }
1132 { _M_h.reserve(__n); }
1134 template<
typename _Key1,
typename _Tp1,
typename _Hash1,
typename _Pred1,
1141#if __cpp_deduction_guides >= 201606
1143 template<
typename _InputIterator,
1144 typename _Hash = hash<__iter_key_t<_InputIterator>>,
1145 typename _Pred = equal_to<__iter_key_t<_InputIterator>>,
1146 typename _Allocator = allocator<__iter_to_alloc_t<_InputIterator>>,
1147 typename = _RequireInputIter<_InputIterator>,
1148 typename = _RequireNotAllocatorOrIntegral<_Hash>,
1149 typename = _RequireNotAllocator<_Pred>,
1150 typename = _RequireAllocator<_Allocator>>
1151 unordered_map(_InputIterator, _InputIterator,
1152 typename unordered_map<int, int>::size_type = {},
1153 _Hash = _Hash(), _Pred = _Pred(), _Allocator = _Allocator())
1154 -> unordered_map<__iter_key_t<_InputIterator>,
1155 __iter_val_t<_InputIterator>,
1156 _Hash, _Pred, _Allocator>;
1158 template<
typename _Key,
typename _Tp,
typename _Hash = hash<_Key>,
1159 typename _Pred = equal_to<_Key>,
1160 typename _Allocator = allocator<pair<const _Key, _Tp>>,
1161 typename = _RequireNotAllocatorOrIntegral<_Hash>,
1162 typename = _RequireNotAllocator<_Pred>,
1163 typename = _RequireAllocator<_Allocator>>
1164 unordered_map(initializer_list<pair<_Key, _Tp>>,
1165 typename unordered_map<int, int>::size_type = {},
1166 _Hash = _Hash(), _Pred = _Pred(), _Allocator = _Allocator())
1167 -> unordered_map<_Key, _Tp, _Hash, _Pred, _Allocator>;
1169 template<
typename _InputIterator,
typename _Allocator,
1170 typename = _RequireInputIter<_InputIterator>,
1171 typename = _RequireAllocator<_Allocator>>
1172 unordered_map(_InputIterator, _InputIterator,
1173 typename unordered_map<int, int>::size_type, _Allocator)
1174 -> unordered_map<__iter_key_t<_InputIterator>,
1175 __iter_val_t<_InputIterator>,
1176 hash<__iter_key_t<_InputIterator>>,
1177 equal_to<__iter_key_t<_InputIterator>>,
1180 template<
typename _InputIterator,
typename _Allocator,
1181 typename = _RequireInputIter<_InputIterator>,
1182 typename = _RequireAllocator<_Allocator>>
1183 unordered_map(_InputIterator, _InputIterator, _Allocator)
1184 -> unordered_map<__iter_key_t<_InputIterator>,
1185 __iter_val_t<_InputIterator>,
1186 hash<__iter_key_t<_InputIterator>>,
1187 equal_to<__iter_key_t<_InputIterator>>,
1190 template<
typename _InputIterator,
typename _Hash,
typename _Allocator,
1191 typename = _RequireInputIter<_InputIterator>,
1192 typename = _RequireNotAllocatorOrIntegral<_Hash>,
1193 typename = _RequireAllocator<_Allocator>>
1194 unordered_map(_InputIterator, _InputIterator,
1195 typename unordered_map<int, int>::size_type,
1197 -> unordered_map<__iter_key_t<_InputIterator>,
1198 __iter_val_t<_InputIterator>, _Hash,
1199 equal_to<__iter_key_t<_InputIterator>>, _Allocator>;
1201 template<
typename _Key,
typename _Tp,
typename _Allocator,
1202 typename = _RequireAllocator<_Allocator>>
1203 unordered_map(initializer_list<pair<_Key, _Tp>>,
1204 typename unordered_map<int, int>::size_type,
1206 -> unordered_map<_Key, _Tp, hash<_Key>, equal_to<_Key>, _Allocator>;
1208 template<
typename _Key,
typename _Tp,
typename _Allocator,
1209 typename = _RequireAllocator<_Allocator>>
1210 unordered_map(initializer_list<pair<_Key, _Tp>>, _Allocator)
1211 -> unordered_map<_Key, _Tp, hash<_Key>, equal_to<_Key>, _Allocator>;
1213 template<
typename _Key,
typename _Tp,
typename _Hash,
typename _Allocator,
1214 typename = _RequireNotAllocatorOrIntegral<_Hash>,
1215 typename = _RequireAllocator<_Allocator>>
1216 unordered_map(initializer_list<pair<_Key, _Tp>>,
1217 typename unordered_map<int, int>::size_type,
1219 -> unordered_map<_Key, _Tp, _Hash, equal_to<_Key>, _Allocator>;
1246 template<
typename _Key,
typename _Tp,
1247 typename _Hash = hash<_Key>,
1248 typename _Pred = equal_to<_Key>,
1249 typename _Alloc = allocator<std::pair<const _Key, _Tp>>>
1260 typedef typename _Hashtable::value_type value_type;
1261 typedef typename _Hashtable::mapped_type mapped_type;
1262 typedef typename _Hashtable::hasher hasher;
1263 typedef typename _Hashtable::key_equal key_equal;
1264 typedef typename _Hashtable::allocator_type allocator_type;
1270 typedef typename _Hashtable::const_pointer const_pointer;
1271 typedef typename _Hashtable::reference reference;
1272 typedef typename _Hashtable::const_reference const_reference;
1273 typedef typename _Hashtable::iterator iterator;
1274 typedef typename _Hashtable::const_iterator const_iterator;
1275 typedef typename _Hashtable::local_iterator local_iterator;
1276 typedef typename _Hashtable::const_local_iterator const_local_iterator;
1277 typedef typename _Hashtable::size_type size_type;
1278 typedef typename _Hashtable::difference_type difference_type;
1281#if __cplusplus > 201402L
1282 using node_type =
typename _Hashtable::node_type;
1299 const hasher& __hf = hasher(),
1300 const key_equal& __eql = key_equal(),
1301 const allocator_type& __a = allocator_type())
1302 : _M_h(__n, __hf, __eql, __a)
1318 template<
typename _InputIterator>
1321 const hasher& __hf = hasher(),
1322 const key_equal& __eql = key_equal(),
1323 const allocator_type& __a = allocator_type())
1324 : _M_h(__first, __last, __n, __hf, __eql, __a)
1348 const allocator_type& __a)
1349 : _M_h(__ummap._M_h, __a)
1358 const allocator_type& __a)
1359 : _M_h(
std::move(__ummap._M_h), __a)
1375 const hasher& __hf = hasher(),
1376 const key_equal& __eql = key_equal(),
1377 const allocator_type& __a = allocator_type())
1378 : _M_h(__l, __n, __hf, __eql, __a)
1386 const allocator_type& __a)
1390 template<
typename _InputIterator>
1393 const allocator_type& __a)
1397 template<
typename _InputIterator>
1399 size_type __n,
const hasher& __hf,
1400 const allocator_type& __a)
1406 const allocator_type& __a)
1411 size_type __n,
const hasher& __hf,
1412 const allocator_type& __a)
1445 {
return _M_h.get_allocator(); }
1450 _GLIBCXX_NODISCARD
bool
1452 {
return _M_h.empty(); }
1457 {
return _M_h.size(); }
1462 {
return _M_h.max_size(); }
1472 {
return _M_h.begin(); }
1481 {
return _M_h.begin(); }
1484 cbegin() const noexcept
1485 {
return _M_h.begin(); }
1494 {
return _M_h.end(); }
1503 {
return _M_h.end(); }
1506 cend() const noexcept
1507 {
return _M_h.end(); }
1527 template<
typename... _Args>
1530 {
return _M_h.emplace(std::forward<_Args>(__args)...); }
1554 template<
typename... _Args>
1557 {
return _M_h.emplace_hint(__pos, std::forward<_Args>(__args)...); }
1571 {
return _M_h.insert(__x); }
1575 {
return _M_h.insert(std::move(__x)); }
1577 template<
typename _Pair>
1578 __enable_if_t<is_constructible<value_type, _Pair&&>::value, iterator>
1580 {
return _M_h.emplace(std::forward<_Pair>(__x)); }
1604 insert(const_iterator __hint,
const value_type& __x)
1605 {
return _M_h.insert(__hint, __x); }
1610 insert(const_iterator __hint, value_type&& __x)
1611 {
return _M_h.insert(__hint, std::move(__x)); }
1613 template<
typename _Pair>
1614 __enable_if_t<is_constructible<value_type, _Pair&&>::value, iterator>
1615 insert(const_iterator __hint, _Pair&& __x)
1616 {
return _M_h.emplace_hint(__hint, std::forward<_Pair>(__x)); }
1628 template<
typename _InputIterator>
1630 insert(_InputIterator __first, _InputIterator __last)
1631 { _M_h.insert(__first, __last); }
1643 { _M_h.insert(__l); }
1645#if __cplusplus > 201402L
1648 extract(const_iterator __pos)
1650 __glibcxx_assert(__pos !=
end());
1651 return _M_h.extract(__pos);
1657 {
return _M_h.extract(__key); }
1662 {
return _M_h._M_reinsert_node_multi(cend(), std::move(__nh)); }
1666 insert(const_iterator __hint, node_type&& __nh)
1667 {
return _M_h._M_reinsert_node_multi(__hint, std::move(__nh)); }
1686 {
return _M_h.erase(__position); }
1691 {
return _M_h.erase(__position); }
1707 {
return _M_h.erase(__x); }
1725 erase(const_iterator __first, const_iterator __last)
1726 {
return _M_h.erase(__first, __last); }
1750 noexcept(
noexcept(_M_h.swap(__x._M_h)) )
1751 { _M_h.swap(__x._M_h); }
1753#if __cplusplus > 201402L
1754 template<
typename,
typename,
typename>
1755 friend class std::_Hash_merge_helper;
1757 template<
typename _H2,
typename _P2>
1762 = _Hash_merge_helper<unordered_multimap, _H2, _P2>;
1763 _M_h._M_merge_multi(_Merge_helper::_S_get_table(__source));
1766 template<
typename _H2,
typename _P2>
1768 merge(unordered_multimap<_Key, _Tp, _H2, _P2, _Alloc>&& __source)
1769 { merge(__source); }
1771 template<
typename _H2,
typename _P2>
1773 merge(unordered_map<_Key, _Tp, _H2, _P2, _Alloc>& __source)
1776 = _Hash_merge_helper<unordered_multimap, _H2, _P2>;
1777 _M_h._M_merge_multi(_Merge_helper::_S_get_table(__source));
1780 template<
typename _H2,
typename _P2>
1782 merge(unordered_map<_Key, _Tp, _H2, _P2, _Alloc>&& __source)
1783 { merge(__source); }
1792 {
return _M_h.hash_function(); }
1798 {
return _M_h.key_eq(); }
1816 {
return _M_h.find(__x); }
1820 {
return _M_h.find(__x); }
1830 {
return _M_h.count(__x); }
1832#if __cplusplus > 201703L
1839 contains(
const key_type& __x)
const
1840 {
return _M_h.find(__x) != _M_h.end(); }
1852 {
return _M_h.equal_range(__x); }
1856 {
return _M_h.equal_range(__x); }
1864 {
return _M_h.bucket_count(); }
1869 {
return _M_h.max_bucket_count(); }
1877 bucket_size(size_type __n)
const
1878 {
return _M_h.bucket_size(__n); }
1886 bucket(
const key_type& __key)
const
1887 {
return _M_h.bucket(__key); }
1897 {
return _M_h.begin(__n); }
1906 const_local_iterator
1908 {
return _M_h.begin(__n); }
1910 const_local_iterator
1911 cbegin(size_type __n)
const
1912 {
return _M_h.cbegin(__n); }
1923 {
return _M_h.end(__n); }
1932 const_local_iterator
1934 {
return _M_h.end(__n); }
1936 const_local_iterator
1937 cend(size_type __n)
const
1938 {
return _M_h.cend(__n); }
1946 {
return _M_h.load_factor(); }
1952 {
return _M_h.max_load_factor(); }
1960 { _M_h.max_load_factor(__z); }
1971 { _M_h.rehash(__n); }
1982 { _M_h.reserve(__n); }
1984 template<
typename _Key1,
typename _Tp1,
typename _Hash1,
typename _Pred1,
1988 _Hash1, _Pred1, _Alloc1>&,
1990 _Hash1, _Pred1, _Alloc1>&);
1993#if __cpp_deduction_guides >= 201606
1995 template<
typename _InputIterator,
1996 typename _Hash = hash<__iter_key_t<_InputIterator>>,
1997 typename _Pred = equal_to<__iter_key_t<_InputIterator>>,
1998 typename _Allocator = allocator<__iter_to_alloc_t<_InputIterator>>,
1999 typename = _RequireInputIter<_InputIterator>,
2000 typename = _RequireNotAllocatorOrIntegral<_Hash>,
2001 typename = _RequireNotAllocator<_Pred>,
2002 typename = _RequireAllocator<_Allocator>>
2003 unordered_multimap(_InputIterator, _InputIterator,
2004 unordered_multimap<int, int>::size_type = {},
2005 _Hash = _Hash(), _Pred = _Pred(),
2006 _Allocator = _Allocator())
2007 -> unordered_multimap<__iter_key_t<_InputIterator>,
2008 __iter_val_t<_InputIterator>, _Hash, _Pred,
2011 template<
typename _Key,
typename _Tp,
typename _Hash = hash<_Key>,
2012 typename _Pred = equal_to<_Key>,
2013 typename _Allocator = allocator<pair<const _Key, _Tp>>,
2014 typename = _RequireNotAllocatorOrIntegral<_Hash>,
2015 typename = _RequireNotAllocator<_Pred>,
2016 typename = _RequireAllocator<_Allocator>>
2017 unordered_multimap(initializer_list<pair<_Key, _Tp>>,
2018 unordered_multimap<int, int>::size_type = {},
2019 _Hash = _Hash(), _Pred = _Pred(),
2020 _Allocator = _Allocator())
2021 -> unordered_multimap<_Key, _Tp, _Hash, _Pred, _Allocator>;
2023 template<
typename _InputIterator,
typename _Allocator,
2024 typename = _RequireInputIter<_InputIterator>,
2025 typename = _RequireAllocator<_Allocator>>
2026 unordered_multimap(_InputIterator, _InputIterator,
2027 unordered_multimap<int, int>::size_type, _Allocator)
2028 -> unordered_multimap<__iter_key_t<_InputIterator>,
2029 __iter_val_t<_InputIterator>,
2030 hash<__iter_key_t<_InputIterator>>,
2031 equal_to<__iter_key_t<_InputIterator>>, _Allocator>;
2033 template<
typename _InputIterator,
typename _Allocator,
2034 typename = _RequireInputIter<_InputIterator>,
2035 typename = _RequireAllocator<_Allocator>>
2036 unordered_multimap(_InputIterator, _InputIterator, _Allocator)
2037 -> unordered_multimap<__iter_key_t<_InputIterator>,
2038 __iter_val_t<_InputIterator>,
2039 hash<__iter_key_t<_InputIterator>>,
2040 equal_to<__iter_key_t<_InputIterator>>, _Allocator>;
2042 template<
typename _InputIterator,
typename _Hash,
typename _Allocator,
2043 typename = _RequireInputIter<_InputIterator>,
2044 typename = _RequireNotAllocatorOrIntegral<_Hash>,
2045 typename = _RequireAllocator<_Allocator>>
2046 unordered_multimap(_InputIterator, _InputIterator,
2047 unordered_multimap<int, int>::size_type, _Hash,
2049 -> unordered_multimap<__iter_key_t<_InputIterator>,
2050 __iter_val_t<_InputIterator>, _Hash,
2051 equal_to<__iter_key_t<_InputIterator>>, _Allocator>;
2053 template<
typename _Key,
typename _Tp,
typename _Allocator,
2054 typename = _RequireAllocator<_Allocator>>
2055 unordered_multimap(initializer_list<pair<_Key, _Tp>>,
2056 unordered_multimap<int, int>::size_type,
2058 -> unordered_multimap<_Key, _Tp, hash<_Key>, equal_to<_Key>, _Allocator>;
2060 template<
typename _Key,
typename _Tp,
typename _Allocator,
2061 typename = _RequireAllocator<_Allocator>>
2062 unordered_multimap(initializer_list<pair<_Key, _Tp>>, _Allocator)
2063 -> unordered_multimap<_Key, _Tp, hash<_Key>, equal_to<_Key>, _Allocator>;
2065 template<
typename _Key,
typename _Tp,
typename _Hash,
typename _Allocator,
2066 typename = _RequireNotAllocatorOrIntegral<_Hash>,
2067 typename = _RequireAllocator<_Allocator>>
2068 unordered_multimap(initializer_list<pair<_Key, _Tp>>,
2069 unordered_multimap<int, int>::size_type,
2071 -> unordered_multimap<_Key, _Tp, _Hash, equal_to<_Key>, _Allocator>;
2075 template<
class _Key,
class _Tp,
class _Hash,
class _Pred,
class _Alloc>
2077 swap(unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
2078 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
2079 noexcept(
noexcept(__x.swap(__y)))
2082 template<
class _Key,
class _Tp,
class _Hash,
class _Pred,
class _Alloc>
2084 swap(unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
2085 unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
2086 noexcept(
noexcept(__x.swap(__y)))
2089 template<
class _Key,
class _Tp,
class _Hash,
class _Pred,
class _Alloc>
2091 operator==(
const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
2092 const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
2093 {
return __x._M_h._M_equal(__y._M_h); }
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); }
2101 template<
class _Key,
class _Tp,
class _Hash,
class _Pred,
class _Alloc>
2103 operator==(
const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
2104 const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
2105 {
return __x._M_h._M_equal(__y._M_h); }
2107 template<
class _Key,
class _Tp,
class _Hash,
class _Pred,
class _Alloc>
2109 operator!=(
const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
2110 const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
2111 {
return !(__x == __y); }
2113_GLIBCXX_END_NAMESPACE_CONTAINER
2115#if __cplusplus > 201402L
2117 template<
typename _Key,
typename _Val,
typename _Hash1,
typename _Eq1,
2118 typename _Alloc,
typename _Hash2,
typename _Eq2>
2119 struct _Hash_merge_helper<
2120 _GLIBCXX_STD_C::unordered_map<_Key, _Val, _Hash1, _Eq1, _Alloc>,
2124 template<
typename... _Tp>
2125 using unordered_map = _GLIBCXX_STD_C::unordered_map<_Tp...>;
2126 template<
typename... _Tp>
2127 using unordered_multimap = _GLIBCXX_STD_C::unordered_multimap<_Tp...>;
2129 friend unordered_map<_Key, _Val, _Hash1, _Eq1, _Alloc>;
2132 _S_get_table(unordered_map<_Key, _Val, _Hash2, _Eq2, _Alloc>& __map)
2133 {
return __map._M_h; }
2136 _S_get_table(unordered_multimap<_Key, _Val, _Hash2, _Eq2, _Alloc>& __map)
2137 {
return __map._M_h; }
2141 template<
typename _Key,
typename _Val,
typename _Hash1,
typename _Eq1,
2142 typename _Alloc,
typename _Hash2,
typename _Eq2>
2143 struct _Hash_merge_helper<
2144 _GLIBCXX_STD_C::unordered_multimap<_Key, _Val, _Hash1, _Eq1, _Alloc>,
2148 template<
typename... _Tp>
2149 using unordered_map = _GLIBCXX_STD_C::unordered_map<_Tp...>;
2150 template<
typename... _Tp>
2151 using unordered_multimap = _GLIBCXX_STD_C::unordered_multimap<_Tp...>;
2153 friend unordered_multimap<_Key, _Val, _Hash1, _Eq1, _Alloc>;
2156 _S_get_table(unordered_map<_Key, _Val, _Hash2, _Eq2, _Alloc>& __map)
2157 {
return __map._M_h; }
2160 _S_get_table(unordered_multimap<_Key, _Val, _Hash2, _Eq2, _Alloc>& __map)
2161 {
return __map._M_h; }
2165_GLIBCXX_END_NAMESPACE_VERSION
constexpr tuple< _Elements &&... > forward_as_tuple(_Elements &&... __args) noexcept
std::forward_as_tuple
_GLIBCXX17_INLINE constexpr piecewise_construct_t piecewise_construct
piecewise_construct
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...
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.
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.
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.
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.
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.
iterator emplace(_Args &&... __args)
Attempts to build and insert a std::pair into the unordered_multimap.
_GLIBCXX_NODISCARD bool empty() const noexcept
Returns true if the unordered_multimap is empty.
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.
unordered_multimap & operator=(unordered_multimap &&)=default
Move assignment operator.
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.
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.
_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...
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.
unordered_map & operator=(initializer_list< value_type > __l)
Unordered_map list assignment operator.
void insert(initializer_list< value_type > __l)
Attempts to insert a list of elements 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.
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.
iterator insert(const_iterator __hint, const value_type &__x)
Attempts to insert a std::pair into the unordered_map.
unordered_map(const unordered_map &)=default
Copy constructor.
size_type count(const key_type &__x) const
Finds the number of elements.
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.
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.
size_type size() const noexcept
Returns the size of 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.
const_iterator begin() const noexcept
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(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.
unordered_map & operator=(const unordered_map &)=default
Copy assignment operator.
_GLIBCXX_NODISCARD bool empty() const noexcept
Returns true if the unordered_map is empty.
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.