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(); }
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);
476 std::forward_as_tuple(__k),
477 std::forward_as_tuple(
478 std::forward<_Args>(__args)...))
486 template <
typename... _Args>
488 try_emplace(
key_type&& __k, _Args&&... __args)
490 iterator __i =
find(__k);
494 std::forward_as_tuple(std::move(__k)),
495 std::forward_as_tuple(
496 std::forward<_Args>(__args)...))
531 template <
typename... _Args>
533 try_emplace(const_iterator __hint,
const key_type& __k,
536 iterator __i =
find(__k);
539 std::forward_as_tuple(__k),
540 std::forward_as_tuple(
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);
553 std::forward_as_tuple(std::move(__k)),
554 std::forward_as_tuple(
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)
689 std::forward_as_tuple(__k),
690 std::forward_as_tuple(std::forward<_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);
707 std::forward_as_tuple(std::move(__k)),
708 std::forward_as_tuple(std::forward<_Obj>(__obj)))
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);
751 std::forward_as_tuple(__k),
752 std::forward_as_tuple(
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);
768 std::forward_as_tuple(std::move(__k)),
769 std::forward_as_tuple(
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); }
952 {
return _M_h.equal_range(__x); }
956 {
return _M_h.equal_range(__x); }
974 {
return _M_h[__k]; }
978 {
return _M_h[std::move(__k)]; }
991 {
return _M_h.at(__k); }
995 {
return _M_h.at(__k); }
1003 {
return _M_h.bucket_count(); }
1008 {
return _M_h.max_bucket_count(); }
1016 bucket_size(size_type __n)
const
1017 {
return _M_h.bucket_size(__n); }
1025 bucket(
const key_type& __key)
const
1026 {
return _M_h.bucket(__key); }
1036 {
return _M_h.begin(__n); }
1045 const_local_iterator
1047 {
return _M_h.begin(__n); }
1049 const_local_iterator
1050 cbegin(size_type __n)
const
1051 {
return _M_h.cbegin(__n); }
1062 {
return _M_h.end(__n); }
1071 const_local_iterator
1073 {
return _M_h.end(__n); }
1075 const_local_iterator
1076 cend(size_type __n)
const
1077 {
return _M_h.cend(__n); }
1085 {
return _M_h.load_factor(); }
1091 {
return _M_h.max_load_factor(); }
1099 { _M_h.max_load_factor(__z); }
1110 { _M_h.rehash(__n); }
1121 { _M_h.reserve(__n); }
1123 template<
typename _Key1,
typename _Tp1,
typename _Hash1,
typename _Pred1,
1130 #if __cpp_deduction_guides >= 201606
1132 template<
typename _InputIterator,
1133 typename _Hash = hash<__iter_key_t<_InputIterator>>,
1134 typename _Pred = equal_to<__iter_key_t<_InputIterator>>,
1135 typename _Allocator = allocator<__iter_to_alloc_t<_InputIterator>>,
1136 typename = _RequireInputIter<_InputIterator>,
1137 typename = _RequireAllocator<_Allocator>>
1138 unordered_map(_InputIterator, _InputIterator,
1139 typename unordered_map<int, int>::size_type = {},
1140 _Hash = _Hash(), _Pred = _Pred(), _Allocator = _Allocator())
1141 -> unordered_map<__iter_key_t<_InputIterator>,
1142 __iter_val_t<_InputIterator>,
1143 _Hash, _Pred, _Allocator>;
1145 template<
typename _Key,
typename _Tp,
typename _Hash = hash<_Key>,
1146 typename _Pred = equal_to<_Key>,
1147 typename _Allocator = allocator<pair<const _Key, _Tp>>,
1148 typename = _RequireAllocator<_Allocator>>
1149 unordered_map(initializer_list<pair<_Key, _Tp>>,
1150 typename unordered_map<int, int>::size_type = {},
1151 _Hash = _Hash(), _Pred = _Pred(), _Allocator = _Allocator())
1152 -> unordered_map<_Key, _Tp, _Hash, _Pred, _Allocator>;
1154 template<
typename _InputIterator,
typename _Allocator,
1155 typename = _RequireInputIter<_InputIterator>,
1156 typename = _RequireAllocator<_Allocator>>
1157 unordered_map(_InputIterator, _InputIterator,
1158 typename unordered_map<int, int>::size_type, _Allocator)
1159 -> unordered_map<__iter_key_t<_InputIterator>,
1160 __iter_val_t<_InputIterator>,
1161 hash<__iter_key_t<_InputIterator>>,
1162 equal_to<__iter_key_t<_InputIterator>>,
1165 template<
typename _InputIterator,
typename _Allocator,
1166 typename = _RequireInputIter<_InputIterator>,
1167 typename = _RequireAllocator<_Allocator>>
1168 unordered_map(_InputIterator, _InputIterator, _Allocator)
1169 -> unordered_map<__iter_key_t<_InputIterator>,
1170 __iter_val_t<_InputIterator>,
1171 hash<__iter_key_t<_InputIterator>>,
1172 equal_to<__iter_key_t<_InputIterator>>,
1175 template<
typename _InputIterator,
typename _Hash,
typename _Allocator,
1176 typename = _RequireInputIter<_InputIterator>,
1177 typename = _RequireAllocator<_Allocator>>
1178 unordered_map(_InputIterator, _InputIterator,
1179 typename unordered_map<int, int>::size_type,
1181 -> unordered_map<__iter_key_t<_InputIterator>,
1182 __iter_val_t<_InputIterator>, _Hash,
1183 equal_to<__iter_key_t<_InputIterator>>, _Allocator>;
1185 template<
typename _Key,
typename _Tp,
typename _Allocator,
1186 typename = _RequireAllocator<_Allocator>>
1187 unordered_map(initializer_list<pair<_Key, _Tp>>,
1188 typename unordered_map<int, int>::size_type,
1190 -> unordered_map<_Key, _Tp, hash<_Key>, equal_to<_Key>, _Allocator>;
1192 template<
typename _Key,
typename _Tp,
typename _Allocator,
1193 typename = _RequireAllocator<_Allocator>>
1194 unordered_map(initializer_list<pair<_Key, _Tp>>, _Allocator)
1195 -> unordered_map<_Key, _Tp, hash<_Key>, equal_to<_Key>, _Allocator>;
1197 template<
typename _Key,
typename _Tp,
typename _Hash,
typename _Allocator,
1198 typename = _RequireAllocator<_Allocator>>
1199 unordered_map(initializer_list<pair<_Key, _Tp>>,
1200 typename unordered_map<int, int>::size_type,
1202 -> unordered_map<_Key, _Tp, _Hash, equal_to<_Key>, _Allocator>;
1229 template<
typename _Key,
typename _Tp,
1230 typename _Hash = hash<_Key>,
1231 typename _Pred = equal_to<_Key>,
1232 typename _Alloc = allocator<std::pair<const _Key, _Tp>>>
1243 typedef typename _Hashtable::value_type value_type;
1244 typedef typename _Hashtable::mapped_type mapped_type;
1245 typedef typename _Hashtable::hasher hasher;
1246 typedef typename _Hashtable::key_equal key_equal;
1247 typedef typename _Hashtable::allocator_type allocator_type;
1253 typedef typename _Hashtable::const_pointer const_pointer;
1254 typedef typename _Hashtable::reference reference;
1255 typedef typename _Hashtable::const_reference const_reference;
1256 typedef typename _Hashtable::iterator iterator;
1257 typedef typename _Hashtable::const_iterator const_iterator;
1258 typedef typename _Hashtable::local_iterator local_iterator;
1259 typedef typename _Hashtable::const_local_iterator const_local_iterator;
1260 typedef typename _Hashtable::size_type size_type;
1261 typedef typename _Hashtable::difference_type difference_type;
1264 #if __cplusplus > 201402L
1265 using node_type =
typename _Hashtable::node_type;
1282 const hasher& __hf = hasher(),
1283 const key_equal& __eql = key_equal(),
1284 const allocator_type& __a = allocator_type())
1285 : _M_h(__n, __hf, __eql, __a)
1301 template<
typename _InputIterator>
1304 const hasher& __hf = hasher(),
1305 const key_equal& __eql = key_equal(),
1306 const allocator_type& __a = allocator_type())
1307 : _M_h(__first, __last, __n, __hf, __eql, __a)
1331 const allocator_type& __a)
1332 : _M_h(__ummap._M_h, __a)
1341 const allocator_type& __a)
1342 : _M_h(
std::move(__ummap._M_h), __a)
1358 const hasher& __hf = hasher(),
1359 const key_equal& __eql = key_equal(),
1360 const allocator_type& __a = allocator_type())
1361 : _M_h(__l, __n, __hf, __eql, __a)
1369 const allocator_type& __a)
1373 template<
typename _InputIterator>
1376 const allocator_type& __a)
1380 template<
typename _InputIterator>
1382 size_type __n,
const hasher& __hf,
1383 const allocator_type& __a)
1389 const allocator_type& __a)
1394 size_type __n,
const hasher& __hf,
1395 const allocator_type& __a)
1428 {
return _M_h.get_allocator(); }
1435 {
return _M_h.empty(); }
1440 {
return _M_h.size(); }
1445 {
return _M_h.max_size(); }
1455 {
return _M_h.begin(); }
1464 {
return _M_h.begin(); }
1467 cbegin() const noexcept
1468 {
return _M_h.begin(); }
1477 {
return _M_h.end(); }
1486 {
return _M_h.end(); }
1489 cend() const noexcept
1490 {
return _M_h.end(); }
1510 template<
typename... _Args>
1513 {
return _M_h.emplace(std::forward<_Args>(__args)...); }
1537 template<
typename... _Args>
1540 {
return _M_h.emplace_hint(__pos, std::forward<_Args>(__args)...); }
1554 {
return _M_h.insert(__x); }
1558 {
return _M_h.insert(std::move(__x)); }
1560 template<
typename _Pair>
1561 __enable_if_t<is_constructible<value_type, _Pair&&>::value, iterator>
1563 {
return _M_h.emplace(std::forward<_Pair>(__x)); }
1587 insert(const_iterator __hint,
const value_type& __x)
1588 {
return _M_h.insert(__hint, __x); }
1593 insert(const_iterator __hint, value_type&& __x)
1594 {
return _M_h.insert(__hint, std::move(__x)); }
1596 template<
typename _Pair>
1597 __enable_if_t<is_constructible<value_type, _Pair&&>::value, iterator>
1598 insert(const_iterator __hint, _Pair&& __x)
1599 {
return _M_h.emplace_hint(__hint, std::forward<_Pair>(__x)); }
1611 template<
typename _InputIterator>
1613 insert(_InputIterator __first, _InputIterator __last)
1614 { _M_h.insert(__first, __last); }
1626 { _M_h.insert(__l); }
1628 #if __cplusplus > 201402L
1631 extract(const_iterator __pos)
1633 __glibcxx_assert(__pos !=
end());
1634 return _M_h.extract(__pos);
1640 {
return _M_h.extract(__key); }
1645 {
return _M_h._M_reinsert_node_multi(cend(), std::move(__nh)); }
1649 insert(const_iterator __hint, node_type&& __nh)
1650 {
return _M_h._M_reinsert_node_multi(__hint, std::move(__nh)); }
1669 {
return _M_h.erase(__position); }
1674 {
return _M_h.erase(__position); }
1690 {
return _M_h.erase(__x); }
1708 erase(const_iterator __first, const_iterator __last)
1709 {
return _M_h.erase(__first, __last); }
1733 noexcept( noexcept(_M_h.swap(__x._M_h)) )
1734 { _M_h.swap(__x._M_h); }
1736 #if __cplusplus > 201402L
1737 template<
typename,
typename,
typename>
1738 friend class std::_Hash_merge_helper;
1740 template<
typename _H2,
typename _P2>
1745 = _Hash_merge_helper<unordered_multimap, _H2, _P2>;
1746 _M_h._M_merge_multi(_Merge_helper::_S_get_table(__source));
1749 template<
typename _H2,
typename _P2>
1751 merge(unordered_multimap<_Key, _Tp, _H2, _P2, _Alloc>&& __source)
1752 { merge(__source); }
1754 template<
typename _H2,
typename _P2>
1756 merge(unordered_map<_Key, _Tp, _H2, _P2, _Alloc>& __source)
1759 = _Hash_merge_helper<unordered_multimap, _H2, _P2>;
1760 _M_h._M_merge_multi(_Merge_helper::_S_get_table(__source));
1763 template<
typename _H2,
typename _P2>
1765 merge(unordered_map<_Key, _Tp, _H2, _P2, _Alloc>&& __source)
1766 { merge(__source); }
1775 {
return _M_h.hash_function(); }
1781 {
return _M_h.key_eq(); }
1799 {
return _M_h.find(__x); }
1803 {
return _M_h.find(__x); }
1813 {
return _M_h.count(__x); }
1824 {
return _M_h.equal_range(__x); }
1828 {
return _M_h.equal_range(__x); }
1836 {
return _M_h.bucket_count(); }
1841 {
return _M_h.max_bucket_count(); }
1849 bucket_size(size_type __n)
const
1850 {
return _M_h.bucket_size(__n); }
1858 bucket(
const key_type& __key)
const
1859 {
return _M_h.bucket(__key); }
1869 {
return _M_h.begin(__n); }
1878 const_local_iterator
1880 {
return _M_h.begin(__n); }
1882 const_local_iterator
1883 cbegin(size_type __n)
const
1884 {
return _M_h.cbegin(__n); }
1895 {
return _M_h.end(__n); }
1904 const_local_iterator
1906 {
return _M_h.end(__n); }
1908 const_local_iterator
1909 cend(size_type __n)
const
1910 {
return _M_h.cend(__n); }
1918 {
return _M_h.load_factor(); }
1924 {
return _M_h.max_load_factor(); }
1932 { _M_h.max_load_factor(__z); }
1943 { _M_h.rehash(__n); }
1954 { _M_h.reserve(__n); }
1956 template<
typename _Key1,
typename _Tp1,
typename _Hash1,
typename _Pred1,
1960 _Hash1, _Pred1, _Alloc1>&,
1962 _Hash1, _Pred1, _Alloc1>&);
1965 #if __cpp_deduction_guides >= 201606
1967 template<
typename _InputIterator,
1968 typename _Hash = hash<__iter_key_t<_InputIterator>>,
1969 typename _Pred = equal_to<__iter_key_t<_InputIterator>>,
1970 typename _Allocator = allocator<__iter_to_alloc_t<_InputIterator>>,
1971 typename = _RequireInputIter<_InputIterator>,
1972 typename = _RequireAllocator<_Allocator>>
1973 unordered_multimap(_InputIterator, _InputIterator,
1974 unordered_multimap<int, int>::size_type = {},
1975 _Hash = _Hash(), _Pred = _Pred(),
1976 _Allocator = _Allocator())
1977 -> unordered_multimap<__iter_key_t<_InputIterator>,
1978 __iter_val_t<_InputIterator>, _Hash, _Pred,
1981 template<
typename _Key,
typename _Tp,
typename _Hash = hash<_Key>,
1982 typename _Pred = equal_to<_Key>,
1983 typename _Allocator = allocator<pair<const _Key, _Tp>>,
1984 typename = _RequireAllocator<_Allocator>>
1985 unordered_multimap(initializer_list<pair<_Key, _Tp>>,
1986 unordered_multimap<int, int>::size_type = {},
1987 _Hash = _Hash(), _Pred = _Pred(),
1988 _Allocator = _Allocator())
1989 -> unordered_multimap<_Key, _Tp, _Hash, _Pred, _Allocator>;
1991 template<
typename _InputIterator,
typename _Allocator,
1992 typename = _RequireInputIter<_InputIterator>,
1993 typename = _RequireAllocator<_Allocator>>
1994 unordered_multimap(_InputIterator, _InputIterator,
1995 unordered_multimap<int, int>::size_type, _Allocator)
1996 -> unordered_multimap<__iter_key_t<_InputIterator>,
1997 __iter_val_t<_InputIterator>,
1998 hash<__iter_key_t<_InputIterator>>,
1999 equal_to<__iter_key_t<_InputIterator>>, _Allocator>;
2001 template<
typename _InputIterator,
typename _Allocator,
2002 typename = _RequireInputIter<_InputIterator>,
2003 typename = _RequireAllocator<_Allocator>>
2004 unordered_multimap(_InputIterator, _InputIterator, _Allocator)
2005 -> unordered_multimap<__iter_key_t<_InputIterator>,
2006 __iter_val_t<_InputIterator>,
2007 hash<__iter_key_t<_InputIterator>>,
2008 equal_to<__iter_key_t<_InputIterator>>, _Allocator>;
2010 template<
typename _InputIterator,
typename _Hash,
typename _Allocator,
2011 typename = _RequireInputIter<_InputIterator>,
2012 typename = _RequireAllocator<_Allocator>>
2013 unordered_multimap(_InputIterator, _InputIterator,
2014 unordered_multimap<int, int>::size_type, _Hash,
2016 -> unordered_multimap<__iter_key_t<_InputIterator>,
2017 __iter_val_t<_InputIterator>, _Hash,
2018 equal_to<__iter_key_t<_InputIterator>>, _Allocator>;
2020 template<
typename _Key,
typename _Tp,
typename _Allocator,
2021 typename = _RequireAllocator<_Allocator>>
2022 unordered_multimap(initializer_list<pair<_Key, _Tp>>,
2023 unordered_multimap<int, int>::size_type,
2025 -> unordered_multimap<_Key, _Tp, hash<_Key>, equal_to<_Key>, _Allocator>;
2027 template<
typename _Key,
typename _Tp,
typename _Allocator,
2028 typename = _RequireAllocator<_Allocator>>
2029 unordered_multimap(initializer_list<pair<_Key, _Tp>>, _Allocator)
2030 -> unordered_multimap<_Key, _Tp, hash<_Key>, equal_to<_Key>, _Allocator>;
2032 template<
typename _Key,
typename _Tp,
typename _Hash,
typename _Allocator,
2033 typename = _RequireAllocator<_Allocator>>
2034 unordered_multimap(initializer_list<pair<_Key, _Tp>>,
2035 unordered_multimap<int, int>::size_type,
2037 -> unordered_multimap<_Key, _Tp, _Hash, equal_to<_Key>, _Allocator>;
2041 template<
class _Key,
class _Tp,
class _Hash,
class _Pred,
class _Alloc>
2043 swap(unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
2044 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
2045 noexcept(noexcept(__x.swap(__y)))
2048 template<
class _Key,
class _Tp,
class _Hash,
class _Pred,
class _Alloc>
2050 swap(unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
2051 unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
2052 noexcept(noexcept(__x.swap(__y)))
2055 template<
class _Key,
class _Tp,
class _Hash,
class _Pred,
class _Alloc>
2057 operator==(
const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
2058 const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
2059 {
return __x._M_h._M_equal(__y._M_h); }
2061 template<
class _Key,
class _Tp,
class _Hash,
class _Pred,
class _Alloc>
2063 operator!=(
const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
2064 const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
2065 {
return !(__x == __y); }
2067 template<
class _Key,
class _Tp,
class _Hash,
class _Pred,
class _Alloc>
2069 operator==(
const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
2070 const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
2071 {
return __x._M_h._M_equal(__y._M_h); }
2073 template<
class _Key,
class _Tp,
class _Hash,
class _Pred,
class _Alloc>
2075 operator!=(
const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
2076 const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
2077 {
return !(__x == __y); }
2079 _GLIBCXX_END_NAMESPACE_CONTAINER
2081 #if __cplusplus > 201402L
2083 template<
typename _Key,
typename _Val,
typename _Hash1,
typename _Eq1,
2084 typename _Alloc,
typename _Hash2,
typename _Eq2>
2085 struct _Hash_merge_helper<
2086 _GLIBCXX_STD_C::unordered_map<_Key, _Val, _Hash1, _Eq1, _Alloc>,
2090 template<
typename... _Tp>
2091 using unordered_map = _GLIBCXX_STD_C::unordered_map<_Tp...>;
2092 template<
typename... _Tp>
2093 using unordered_multimap = _GLIBCXX_STD_C::unordered_multimap<_Tp...>;
2095 friend unordered_map<_Key, _Val, _Hash1, _Eq1, _Alloc>;
2098 _S_get_table(unordered_map<_Key, _Val, _Hash2, _Eq2, _Alloc>& __map)
2099 {
return __map._M_h; }
2102 _S_get_table(unordered_multimap<_Key, _Val, _Hash2, _Eq2, _Alloc>& __map)
2103 {
return __map._M_h; }
2107 template<
typename _Key,
typename _Val,
typename _Hash1,
typename _Eq1,
2108 typename _Alloc,
typename _Hash2,
typename _Eq2>
2109 struct _Hash_merge_helper<
2110 _GLIBCXX_STD_C::unordered_multimap<_Key, _Val, _Hash1, _Eq1, _Alloc>,
2114 template<
typename... _Tp>
2115 using unordered_map = _GLIBCXX_STD_C::unordered_map<_Tp...>;
2116 template<
typename... _Tp>
2117 using unordered_multimap = _GLIBCXX_STD_C::unordered_multimap<_Tp...>;
2119 friend unordered_multimap<_Key, _Val, _Hash1, _Eq1, _Alloc>;
2122 _S_get_table(unordered_map<_Key, _Val, _Hash2, _Eq2, _Alloc>& __map)
2123 {
return __map._M_h; }
2126 _S_get_table(unordered_multimap<_Key, _Val, _Hash2, _Eq2, _Alloc>& __map)
2127 {
return __map._M_h; }
2131 _GLIBCXX_END_NAMESPACE_VERSION
constexpr _GLIBCXX17_INLINE 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...
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.