30#ifndef _UNORDERED_SET_H
31#define _UNORDERED_SET_H
37#if __glibcxx_ranges_to_container
41namespace std _GLIBCXX_VISIBILITY(default)
43_GLIBCXX_BEGIN_NAMESPACE_VERSION
44_GLIBCXX_BEGIN_NAMESPACE_CONTAINER
50 template<
typename _Value,
55 using __uset_hashtable = _Hashtable<_Value, _Value, _Alloc,
56 __detail::_Identity, _Pred, _Hash,
57 __detail::_Mod_range_hashing,
58 __detail::_Default_ranged_hash,
59 __detail::_Prime_rehash_policy, _Tr>;
65 template<
typename _Value,
70 using __umset_hashtable = _Hashtable<_Value, _Value, _Alloc,
73 __detail::_Mod_range_hashing,
74 __detail::_Default_ranged_hash,
75 __detail::_Prime_rehash_policy, _Tr>;
77 template<
class _Value,
class _Hash,
class _Pred,
class _Alloc>
103 template<
typename _Value,
109 typedef __uset_hashtable<_Value, _Hash, _Pred, _Alloc> _Hashtable;
118 typedef typename _Hashtable::hasher
hasher;
137#ifdef __glibcxx_node_extract
138 using node_type =
typename _Hashtable::node_type;
139 using insert_return_type =
typename _Hashtable::insert_return_type;
159 : _M_h(__n, __hf, __eql, __a)
175 template<
typename _InputIterator>
181 : _M_h(__first, __last, __n, __hf, __eql, __a)
206 : _M_h(__uset._M_h, __a)
216 noexcept(
noexcept(_Hashtable(
std::move(__uset._M_h), __a)) )
236 : _M_h(__l, __n, __hf, __eql, __a)
248 template<
typename _InputIterator>
255 template<
typename _InputIterator>
274#if __glibcxx_ranges_to_container
288 template<__detail::__container_compatible_range<_Value> _Rg>
294 : _M_h(__n, __hf, __eql, __a)
295 { insert_range(std::forward<_Rg>(__rg)); }
297 template<__detail::__container_compatible_range<_Value> _Rg>
301 { insert_range(std::forward<_Rg>(__rg)); }
303 template<__detail::__container_compatible_range<_Value> _Rg>
307 { insert_range(std::forward<_Rg>(__rg)); }
339 {
return _M_h.get_allocator(); }
344 _GLIBCXX_NODISCARD
bool
346 {
return _M_h.empty(); }
351 {
return _M_h.size(); }
356 {
return _M_h.max_size(); }
367 {
return _M_h.begin(); }
371 {
return _M_h.begin(); }
381 {
return _M_h.end(); }
385 {
return _M_h.end(); }
394 {
return _M_h.begin(); }
402 {
return _M_h.end(); }
421 template<
typename... _Args>
424 {
return _M_h.emplace(std::forward<_Args>(__args)...); }
447 template<
typename... _Args>
450 {
return _M_h.emplace_hint(__pos, std::forward<_Args>(__args)...); }
468 {
return _M_h.insert(__x); }
497 {
return _M_h.insert(__hint, __x); }
501 {
return _M_h.insert(__hint,
std::move(__x)); }
513 template<
typename _InputIterator>
515 insert(_InputIterator __first, _InputIterator __last)
516 { _M_h.insert(__first, __last); }
527 { _M_h.insert(__l); }
529#if __glibcxx_ranges_to_container
536 template<__detail::__container_compatible_range<_Value> _Rg>
538 insert_range(_Rg&& __rg)
540 auto __first = ranges::begin(__rg);
541 const auto __last = ranges::end(__rg);
542 for (; __first != __last; ++__first)
543 _M_h.emplace(*__first);
547#ifdef __glibcxx_node_extract
552 __glibcxx_assert(__pos !=
end());
553 return _M_h.extract(__pos);
559 {
return _M_h.extract(__key); }
564 {
return _M_h._M_reinsert_node(
std::move(__nh)); }
569 {
return _M_h._M_reinsert_node(
std::move(__nh)).position; }
588 {
return _M_h.erase(__position); }
593 {
return _M_h.erase(__position); }
610 {
return _M_h.erase(__x); }
628 {
return _M_h.erase(__first, __last); }
651 noexcept(
noexcept(_M_h.swap(__x._M_h)) )
652 { _M_h.swap(__x._M_h); }
654#ifdef __glibcxx_node_extract
655 template<
typename,
typename,
typename>
656 friend class std::_Hash_merge_helper;
658 template<
typename _H2,
typename _P2>
662 if constexpr (is_same_v<_H2, _Hash> && is_same_v<_P2, _Pred>)
666 using _Merge_helper = _Hash_merge_helper<unordered_set, _H2, _P2>;
667 _M_h._M_merge_unique(_Merge_helper::_S_get_table(__source));
670 template<
typename _H2,
typename _P2>
672 merge(unordered_set<_Value, _H2, _P2, _Alloc>&& __source)
674 using _Merge_helper = _Hash_merge_helper<unordered_set, _H2, _P2>;
675 _M_h._M_merge_unique(_Merge_helper::_S_get_table(__source));
678 template<
typename _H2,
typename _P2>
680 merge(unordered_multiset<_Value, _H2, _P2, _Alloc>& __source)
682 using _Merge_helper = _Hash_merge_helper<unordered_set, _H2, _P2>;
683 _M_h._M_merge_unique(_Merge_helper::_S_get_table(__source));
686 template<
typename _H2,
typename _P2>
688 merge(unordered_multiset<_Value, _H2, _P2, _Alloc>&& __source)
698 {
return _M_h.hash_function(); }
704 {
return _M_h.key_eq(); }
722 {
return _M_h.find(__x); }
724#if __cplusplus > 201703L
725 template<
typename _Kt>
728 ->
decltype(_M_h._M_find_tr(__k))
729 {
return _M_h._M_find_tr(__k); }
734 {
return _M_h.find(__x); }
736#if __cplusplus > 201703L
737 template<
typename _Kt>
740 ->
decltype(_M_h._M_find_tr(__k))
741 {
return _M_h._M_find_tr(__k); }
757 {
return _M_h.count(__x); }
759#if __cplusplus > 201703L
760 template<
typename _Kt>
763 ->
decltype(_M_h._M_count_tr(__k))
764 {
return _M_h._M_count_tr(__k); }
768#if __cplusplus > 201703L
777 {
return _M_h.find(__x) != _M_h.end(); }
779 template<
typename _Kt>
782 ->
decltype(_M_h._M_find_tr(__k), void(),
true)
783 {
return _M_h._M_find_tr(__k) != _M_h.end(); }
798 {
return _M_h.equal_range(__x); }
800#if __cplusplus > 201703L
801 template<
typename _Kt>
804 ->
decltype(_M_h._M_equal_range_tr(__k))
805 {
return _M_h._M_equal_range_tr(__k); }
810 {
return _M_h.equal_range(__x); }
812#if __cplusplus > 201703L
813 template<
typename _Kt>
816 ->
decltype(_M_h._M_equal_range_tr(__k))
817 {
return _M_h._M_equal_range_tr(__k); }
826 {
return _M_h.bucket_count(); }
831 {
return _M_h.max_bucket_count(); }
840 {
return _M_h.bucket_size(__n); }
849 {
return _M_h.bucket(__key); }
860 {
return _M_h.begin(__n); }
864 {
return _M_h.begin(__n); }
868 {
return _M_h.cbegin(__n); }
880 {
return _M_h.end(__n); }
884 {
return _M_h.end(__n); }
888 {
return _M_h.cend(__n); }
896 {
return _M_h.load_factor(); }
902 {
return _M_h.max_load_factor(); }
910 { _M_h.max_load_factor(__z); }
921 { _M_h.rehash(__n); }
932 { _M_h.reserve(__n); }
934 template<
typename _Value1,
typename _Hash1,
typename _Pred1,
941#if __cpp_deduction_guides >= 201606
943 template<
typename _InputIterator,
945 hash<typename iterator_traits<_InputIterator>::value_type>,
947 equal_to<typename iterator_traits<_InputIterator>::value_type>,
948 typename _Allocator =
949 allocator<typename iterator_traits<_InputIterator>::value_type>,
950 typename = _RequireInputIter<_InputIterator>,
951 typename = _RequireNotAllocatorOrIntegral<_Hash>,
952 typename = _RequireNotAllocator<_Pred>,
953 typename = _RequireAllocator<_Allocator>>
954 unordered_set(_InputIterator, _InputIterator,
956 _Hash = _Hash(), _Pred = _Pred(), _Allocator = _Allocator())
957 -> unordered_set<
typename iterator_traits<_InputIterator>::value_type,
958 _Hash, _Pred, _Allocator>;
960 template<
typename _Tp,
typename _Hash = hash<_Tp>,
961 typename _Pred = equal_to<_Tp>,
962 typename _Allocator = allocator<_Tp>,
963 typename = _RequireNotAllocatorOrIntegral<_Hash>,
964 typename = _RequireNotAllocator<_Pred>,
965 typename = _RequireAllocator<_Allocator>>
966 unordered_set(initializer_list<_Tp>,
968 _Hash = _Hash(), _Pred = _Pred(), _Allocator = _Allocator())
969 -> unordered_set<_Tp, _Hash, _Pred, _Allocator>;
971 template<
typename _InputIterator,
typename _Allocator,
972 typename = _RequireInputIter<_InputIterator>,
973 typename = _RequireAllocator<_Allocator>>
974 unordered_set(_InputIterator, _InputIterator,
976 -> unordered_set<typename iterator_traits<_InputIterator>::value_type,
978 typename iterator_traits<_InputIterator>::value_type>,
980 typename iterator_traits<_InputIterator>::value_type>,
983 template<
typename _InputIterator,
typename _Hash,
typename _Allocator,
984 typename = _RequireInputIter<_InputIterator>,
985 typename = _RequireNotAllocatorOrIntegral<_Hash>,
986 typename = _RequireAllocator<_Allocator>>
987 unordered_set(_InputIterator, _InputIterator,
990 -> unordered_set<typename iterator_traits<_InputIterator>::value_type,
993 typename iterator_traits<_InputIterator>::value_type>,
996 template<
typename _Tp,
typename _Allocator,
997 typename = _RequireAllocator<_Allocator>>
998 unordered_set(initializer_list<_Tp>,
1000 -> unordered_set<_Tp, hash<_Tp>, equal_to<_Tp>, _Allocator>;
1002 template<
typename _Tp,
typename _Hash,
typename _Allocator,
1003 typename = _RequireNotAllocatorOrIntegral<_Hash>,
1004 typename = _RequireAllocator<_Allocator>>
1005 unordered_set(initializer_list<_Tp>,
1007 -> unordered_set<_Tp, _Hash, equal_to<_Tp>, _Allocator>;
1009#if __glibcxx_ranges_to_container
1010 template<ranges::input_range _Rg,
1011 __not_allocator_like _Hash = hash<ranges::range_value_t<_Rg>>,
1012 __not_allocator_like _Pred = equal_to<ranges::range_value_t<_Rg>>,
1013 __allocator_like _Allocator = allocator<ranges::range_value_t<_Rg>>>
1015 _Hash = _Hash(), _Pred = _Pred(), _Allocator = _Allocator())
1016 -> unordered_set<ranges::range_value_t<_Rg>, _Hash, _Pred, _Allocator>;
1018 template<ranges::input_range _Rg,
1019 __allocator_like _Allocator>
1022 -> unordered_set<ranges::range_value_t<_Rg>,
1023 hash<ranges::range_value_t<_Rg>>,
1024 equal_to<ranges::range_value_t<_Rg>>,
1027 template<ranges::input_range _Rg,
1028 __allocator_like _Allocator>
1029 unordered_set(from_range_t, _Rg&&, _Allocator)
1030 -> unordered_set<ranges::range_value_t<_Rg>,
1031 hash<ranges::range_value_t<_Rg>>,
1032 equal_to<ranges::range_value_t<_Rg>>,
1035 template<ranges::input_range _Rg,
1036 __not_allocator_like _Hash,
1037 __allocator_like _Allocator>
1040 -> unordered_set<ranges::range_value_t<_Rg>, _Hash,
1041 equal_to<ranges::range_value_t<_Rg>>,
1067 template<
typename _Value,
1068 typename _Hash = hash<_Value>,
1069 typename _Pred = equal_to<_Value>,
1070 typename _Alloc = allocator<_Value>>
1073 typedef __umset_hashtable<_Value, _Hash, _Pred, _Alloc> _Hashtable;
1101#ifdef __glibcxx_node_extract
1102 using node_type =
typename _Hashtable::node_type;
1122 : _M_h(__n, __hf, __eql, __a)
1138 template<
typename _InputIterator>
1144 : _M_h(__first, __last, __n, __hf, __eql, __a)
1169 : _M_h(__l, __n, __hf, __eql, __a)
1196 : _M_h(__umset._M_h, __a)
1206 noexcept(
noexcept(_Hashtable(
std::move(__umset._M_h), __a)) )
1219 template<
typename _InputIterator>
1226 template<
typename _InputIterator>
1245#if __glibcxx_ranges_to_container
1259 template<__detail::__container_compatible_range<_Value> _Rg>
1265 : _M_h(__n, __hf, __eql, __a)
1266 { insert_range(std::forward<_Rg>(__rg)); }
1268 template<__detail::__container_compatible_range<_Value> _Rg>
1272 { insert_range(std::forward<_Rg>(__rg)); }
1274 template<__detail::__container_compatible_range<_Value> _Rg>
1278 { insert_range(std::forward<_Rg>(__rg)); }
1303 {
return _M_h.get_allocator(); }
1308 _GLIBCXX_NODISCARD
bool
1310 {
return _M_h.empty(); }
1315 {
return _M_h.size(); }
1320 {
return _M_h.max_size(); }
1331 {
return _M_h.begin(); }
1335 {
return _M_h.begin(); }
1345 {
return _M_h.end(); }
1349 {
return _M_h.end(); }
1358 {
return _M_h.begin(); }
1366 {
return _M_h.end(); }
1377 template<
typename... _Args>
1380 {
return _M_h.emplace(std::forward<_Args>(__args)...); }
1399 template<
typename... _Args>
1402 {
return _M_h.emplace_hint(__pos, std::forward<_Args>(__args)...); }
1414 {
return _M_h.insert(__x); }
1440 {
return _M_h.insert(__hint, __x); }
1444 {
return _M_h.insert(__hint,
std::move(__x)); }
1455 template<
typename _InputIterator>
1457 insert(_InputIterator __first, _InputIterator __last)
1458 { _M_h.insert(__first, __last); }
1469 { _M_h.insert(__l); }
1471#if __glibcxx_ranges_to_container
1478 template<__detail::__container_compatible_range<_Value> _Rg>
1480 insert_range(_Rg&& __rg)
1482 auto __first = ranges::begin(__rg);
1483 const auto __last = ranges::end(__rg);
1484 if (__first == __last)
1487 if constexpr (ranges::forward_range<_Rg> || ranges::sized_range<_Rg>)
1488 _M_h._M_rehash_insert(ranges::distance(__rg));
1490 _M_h._M_rehash_insert(1);
1492 for (; __first != __last; ++__first)
1493 _M_h.emplace(*__first);
1497#ifdef __glibcxx_node_extract
1502 __glibcxx_assert(__pos !=
end());
1503 return _M_h.extract(__pos);
1509 {
return _M_h.extract(__key); }
1514 {
return _M_h._M_reinsert_node_multi(
cend(),
std::move(__nh)); }
1519 {
return _M_h._M_reinsert_node_multi(__hint,
std::move(__nh)); }
1539 {
return _M_h.erase(__position); }
1544 {
return _M_h.erase(__position); }
1562 {
return _M_h.erase(__x); }
1582 {
return _M_h.erase(__first, __last); }
1606 noexcept(
noexcept(_M_h.swap(__x._M_h)) )
1607 { _M_h.swap(__x._M_h); }
1609#ifdef __glibcxx_node_extract
1610 template<
typename,
typename,
typename>
1611 friend class std::_Hash_merge_helper;
1613 template<
typename _H2,
typename _P2>
1617 if constexpr (is_same_v<_H2, _Hash> && is_same_v<_P2, _Pred>)
1622 = _Hash_merge_helper<unordered_multiset, _H2, _P2>;
1623 _M_h._M_merge_multi(_Merge_helper::_S_get_table(__source));
1626 template<
typename _H2,
typename _P2>
1628 merge(unordered_multiset<_Value, _H2, _P2, _Alloc>&& __source)
1631 = _Hash_merge_helper<unordered_multiset, _H2, _P2>;
1632 _M_h._M_merge_multi(_Merge_helper::_S_get_table(__source));
1635 template<
typename _H2,
typename _P2>
1637 merge(unordered_set<_Value, _H2, _P2, _Alloc>& __source)
1640 = _Hash_merge_helper<unordered_multiset, _H2, _P2>;
1641 _M_h._M_merge_multi(_Merge_helper::_S_get_table(__source));
1644 template<
typename _H2,
typename _P2>
1646 merge(unordered_set<_Value, _H2, _P2, _Alloc>&& __source)
1647 { merge(__source); }
1656 {
return _M_h.hash_function(); }
1662 {
return _M_h.key_eq(); }
1680 {
return _M_h.find(__x); }
1682#if __cplusplus > 201703L
1683 template<
typename _Kt>
1686 ->
decltype(_M_h._M_find_tr(__x))
1687 {
return _M_h._M_find_tr(__x); }
1692 {
return _M_h.find(__x); }
1694#if __cplusplus > 201703L
1695 template<
typename _Kt>
1698 ->
decltype(_M_h._M_find_tr(__x))
1699 {
return _M_h._M_find_tr(__x); }
1711 {
return _M_h.count(__x); }
1713#if __cplusplus > 201703L
1714 template<
typename _Kt>
1716 count(
const _Kt& __x)
const ->
decltype(_M_h._M_count_tr(__x))
1717 {
return _M_h._M_count_tr(__x); }
1721#if __cplusplus > 201703L
1730 {
return _M_h.find(__x) != _M_h.end(); }
1732 template<
typename _Kt>
1735 ->
decltype(_M_h._M_find_tr(__x), void(),
true)
1736 {
return _M_h._M_find_tr(__x) != _M_h.end(); }
1749 {
return _M_h.equal_range(__x); }
1751#if __cplusplus > 201703L
1752 template<
typename _Kt>
1755 ->
decltype(_M_h._M_equal_range_tr(__x))
1756 {
return _M_h._M_equal_range_tr(__x); }
1761 {
return _M_h.equal_range(__x); }
1763#if __cplusplus > 201703L
1764 template<
typename _Kt>
1767 ->
decltype(_M_h._M_equal_range_tr(__x))
1768 {
return _M_h._M_equal_range_tr(__x); }
1777 {
return _M_h.bucket_count(); }
1782 {
return _M_h.max_bucket_count(); }
1791 {
return _M_h.bucket_size(__n); }
1799 bucket(
const key_type& __key)
const
1800 {
return _M_h.bucket(__key); }
1811 {
return _M_h.begin(__n); }
1815 {
return _M_h.begin(__n); }
1819 {
return _M_h.cbegin(__n); }
1831 {
return _M_h.end(__n); }
1835 {
return _M_h.end(__n); }
1839 {
return _M_h.cend(__n); }
1847 {
return _M_h.load_factor(); }
1853 {
return _M_h.max_load_factor(); }
1861 { _M_h.max_load_factor(__z); }
1872 { _M_h.rehash(__n); }
1883 { _M_h.reserve(__n); }
1885 template<
typename _Value1,
typename _Hash1,
typename _Pred1,
1893#if __cpp_deduction_guides >= 201606
1895 template<
typename _InputIterator,
1897 hash<typename iterator_traits<_InputIterator>::value_type>,
1899 equal_to<typename iterator_traits<_InputIterator>::value_type>,
1900 typename _Allocator =
1901 allocator<typename iterator_traits<_InputIterator>::value_type>,
1902 typename = _RequireInputIter<_InputIterator>,
1903 typename = _RequireNotAllocatorOrIntegral<_Hash>,
1904 typename = _RequireNotAllocator<_Pred>,
1905 typename = _RequireAllocator<_Allocator>>
1906 unordered_multiset(_InputIterator, _InputIterator,
1908 _Hash = _Hash(), _Pred = _Pred(),
1909 _Allocator = _Allocator())
1910 -> unordered_multiset<
typename iterator_traits<_InputIterator>::value_type,
1911 _Hash, _Pred, _Allocator>;
1913 template<
typename _Tp,
typename _Hash = hash<_Tp>,
1914 typename _Pred = equal_to<_Tp>,
1915 typename _Allocator = allocator<_Tp>,
1916 typename = _RequireNotAllocatorOrIntegral<_Hash>,
1917 typename = _RequireNotAllocator<_Pred>,
1918 typename = _RequireAllocator<_Allocator>>
1919 unordered_multiset(initializer_list<_Tp>,
1921 _Hash = _Hash(), _Pred = _Pred(),
1922 _Allocator = _Allocator())
1923 -> unordered_multiset<_Tp, _Hash, _Pred, _Allocator>;
1925 template<
typename _InputIterator,
typename _Allocator,
1926 typename = _RequireInputIter<_InputIterator>,
1927 typename = _RequireAllocator<_Allocator>>
1928 unordered_multiset(_InputIterator, _InputIterator,
1930 -> unordered_multiset<typename iterator_traits<_InputIterator>::value_type,
1932 iterator_traits<_InputIterator>::value_type>,
1934 iterator_traits<_InputIterator>::value_type>,
1937 template<
typename _InputIterator,
typename _Hash,
typename _Allocator,
1938 typename = _RequireInputIter<_InputIterator>,
1939 typename = _RequireNotAllocatorOrIntegral<_Hash>,
1940 typename = _RequireAllocator<_Allocator>>
1941 unordered_multiset(_InputIterator, _InputIterator,
1944 -> unordered_multiset<
typename
1945 iterator_traits<_InputIterator>::value_type,
1949 iterator_traits<_InputIterator>::value_type>,
1952 template<
typename _Tp,
typename _Allocator,
1953 typename = _RequireAllocator<_Allocator>>
1954 unordered_multiset(initializer_list<_Tp>,
1956 -> unordered_multiset<_Tp, hash<_Tp>, equal_to<_Tp>, _Allocator>;
1958 template<
typename _Tp,
typename _Hash,
typename _Allocator,
1959 typename = _RequireNotAllocatorOrIntegral<_Hash>,
1960 typename = _RequireAllocator<_Allocator>>
1961 unordered_multiset(initializer_list<_Tp>,
1963 -> unordered_multiset<_Tp, _Hash, equal_to<_Tp>, _Allocator>;
1965#if __glibcxx_ranges_to_container
1966 template<ranges::input_range _Rg,
1967 __not_allocator_like _Hash = hash<ranges::range_value_t<_Rg>>,
1968 __not_allocator_like _Pred = equal_to<ranges::range_value_t<_Rg>>,
1969 __allocator_like _Allocator = allocator<ranges::range_value_t<_Rg>>>
1970 unordered_multiset(from_range_t, _Rg&&,
1972 _Hash = _Hash(), _Pred = _Pred(),
1973 _Allocator = _Allocator())
1974 -> unordered_multiset<ranges::range_value_t<_Rg>, _Hash, _Pred, _Allocator>;
1976 template<ranges::input_range _Rg,
1977 __allocator_like _Allocator>
1978 unordered_multiset(from_range_t, _Rg&&, _Allocator)
1979 -> unordered_multiset<ranges::range_value_t<_Rg>,
1980 hash<ranges::range_value_t<_Rg>>,
1981 equal_to<ranges::range_value_t<_Rg>>,
1984 template<ranges::input_range _Rg,
1985 __allocator_like _Allocator>
1988 -> unordered_multiset<ranges::range_value_t<_Rg>,
1989 hash<ranges::range_value_t<_Rg>>,
1990 equal_to<ranges::range_value_t<_Rg>>,
1993 template<ranges::input_range _Rg,
1994 __not_allocator_like _Hash,
1995 __allocator_like _Allocator>
1996 unordered_multiset(from_range_t, _Rg&&,
1999 -> unordered_multiset<ranges::range_value_t<_Rg>, _Hash,
2000 equal_to<ranges::range_value_t<_Rg>>,
2005 template<
class _Value,
class _Hash,
class _Pred,
class _Alloc>
2007 swap(unordered_set<_Value, _Hash, _Pred, _Alloc>& __x,
2008 unordered_set<_Value, _Hash, _Pred, _Alloc>& __y)
2009 noexcept(
noexcept(__x.swap(__y)))
2012 template<
class _Value,
class _Hash,
class _Pred,
class _Alloc>
2014 swap(unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x,
2015 unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y)
2016 noexcept(
noexcept(__x.swap(__y)))
2019 template<
class _Value,
class _Hash,
class _Pred,
class _Alloc>
2021 operator==(
const unordered_set<_Value, _Hash, _Pred, _Alloc>& __x,
2022 const unordered_set<_Value, _Hash, _Pred, _Alloc>& __y)
2023 {
return __x._M_h._M_equal(__y._M_h); }
2025#if __cpp_impl_three_way_comparison < 201907L
2026 template<
class _Value,
class _Hash,
class _Pred,
class _Alloc>
2028 operator!=(
const unordered_set<_Value, _Hash, _Pred, _Alloc>& __x,
2029 const unordered_set<_Value, _Hash, _Pred, _Alloc>& __y)
2030 {
return !(__x == __y); }
2033 template<
class _Value,
class _Hash,
class _Pred,
class _Alloc>
2035 operator==(
const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x,
2036 const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y)
2037 {
return __x._M_h._M_equal(__y._M_h); }
2039#if __cpp_impl_three_way_comparison < 201907L
2040 template<
class _Value,
class _Hash,
class _Pred,
class _Alloc>
2042 operator!=(
const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x,
2043 const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y)
2044 {
return !(__x == __y); }
2047_GLIBCXX_END_NAMESPACE_CONTAINER
2049#ifdef __glibcxx_node_extract
2051 template<
typename _Val,
typename _Hash1,
typename _Eq1,
typename _Alloc,
2052 typename _Hash2,
typename _Eq2>
2053 struct _Hash_merge_helper<
2054 _GLIBCXX_STD_C::unordered_set<_Val, _Hash1, _Eq1, _Alloc>, _Hash2, _Eq2>
2057 template<
typename... _Tp>
2058 using unordered_set = _GLIBCXX_STD_C::unordered_set<_Tp...>;
2059 template<
typename... _Tp>
2060 using unordered_multiset = _GLIBCXX_STD_C::unordered_multiset<_Tp...>;
2062 friend unordered_set<_Val, _Hash1, _Eq1, _Alloc>;
2065 _S_get_table(unordered_set<_Val, _Hash2, _Eq2, _Alloc>& __set)
2066 {
return __set._M_h; }
2069 _S_get_table(unordered_multiset<_Val, _Hash2, _Eq2, _Alloc>& __set)
2070 {
return __set._M_h; }
2074 template<
typename _Val,
typename _Hash1,
typename _Eq1,
typename _Alloc,
2075 typename _Hash2,
typename _Eq2>
2076 struct _Hash_merge_helper<
2077 _GLIBCXX_STD_C::unordered_multiset<_Val, _Hash1, _Eq1, _Alloc>,
2081 template<
typename... _Tp>
2082 using unordered_set = _GLIBCXX_STD_C::unordered_set<_Tp...>;
2083 template<
typename... _Tp>
2084 using unordered_multiset = _GLIBCXX_STD_C::unordered_multiset<_Tp...>;
2086 friend unordered_multiset<_Val, _Hash1, _Eq1, _Alloc>;
2089 _S_get_table(unordered_set<_Val, _Hash2, _Eq2, _Alloc>& __set)
2090 {
return __set._M_h; }
2093 _S_get_table(unordered_multiset<_Val, _Hash2, _Eq2, _Alloc>& __set)
2094 {
return __set._M_h; }
2098_GLIBCXX_END_NAMESPACE_VERSION
constexpr std::remove_reference< _Tp >::type && move(_Tp &&__t) noexcept
Convert a value to an rvalue.
constexpr _Tp * __addressof(_Tp &__r) noexcept
Same as C++11 std::addressof.
ISO C++ entities toplevel namespace is std.
__detail::_Hashtable_traits< _Cache, true, true > __uset_traits
Base types for unordered_set.
__detail::_Hashtable_traits< _Cache, true, false > __umset_traits
Base types for unordered_multiset.
Primary class template hash.
The standard allocator, as per C++03 [20.4.1].
One of the comparison functors.
Struct holding two objects of arbitrary type.
A standard container composed of equivalent keys (possibly containing multiple of each key value) in ...
auto find(const _Kt &__x) const -> decltype(_M_h._M_find_tr(__x))
Tries to locate an element in an unordered_multiset.
iterator begin() noexcept
auto find(const _Kt &__x) -> decltype(_M_h._M_find_tr(__x))
Tries to locate an element in an unordered_multiset.
iterator insert(const_iterator __hint, const value_type &__x)
Inserts an element into the unordered_multiset.
_Hashtable::difference_type difference_type
Iterator-related typedefs.
void insert(initializer_list< value_type > __l)
Inserts a list of elements into the unordered_multiset.
_Hashtable::pointer pointer
Iterator-related typedefs.
bool contains(const key_type &__x) const
Finds whether an element with the given key exists.
void rehash(size_type __n)
May rehash the unordered_multiset.
local_iterator begin(size_type __n)
Returns a read-only (constant) iterator pointing to the first bucket element.
size_type bucket_count() const noexcept
Returns the number of buckets of the unordered_multiset.
float max_load_factor() const noexcept
Returns a positive number that the unordered_multiset tries to keep the load factor less than or equa...
bool empty() const noexcept
Returns true if the unordered_multiset is empty.
const_iterator cend() const noexcept
_Hashtable::local_iterator local_iterator
Iterator-related typedefs.
node_type extract(const key_type &__key)
Extract a node.
const_local_iterator begin(size_type __n) const
Returns a read-only (constant) iterator pointing to the first bucket element.
iterator emplace(_Args &&... __args)
Builds and insert an element into the unordered_multiset.
unordered_multiset(_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_multiset from a range.
_Hashtable::const_iterator const_iterator
Iterator-related typedefs.
unordered_multiset(const allocator_type &__a)
Creates an unordered_multiset with no elements.
_Hashtable::allocator_type allocator_type
Public typedefs.
const_local_iterator end(size_type __n) const
Returns a read-only (constant) iterator pointing to one past the last bucket elements.
iterator find(const key_type &__x)
Tries to locate an element in an unordered_multiset.
_Hashtable::value_type value_type
Public typedefs.
unordered_multiset & operator=(unordered_multiset &&)=default
Move assignment operator.
float load_factor() const noexcept
Returns the average number of elements per bucket.
unordered_multiset()=default
Default constructor.
iterator insert(const_iterator __hint, node_type &&__nh)
Re-insert an extracted node.
_Hashtable::size_type size_type
Iterator-related typedefs.
auto equal_range(const _Kt &__x) -> decltype(_M_h._M_equal_range_tr(__x))
Finds a subsequence matching given key.
_Hashtable::key_type key_type
Public typedefs.
unordered_multiset & operator=(const unordered_multiset &)=default
Copy assignment operator.
hasher hash_function() const
Returns the hash functor object with which the unordered_multiset was constructed.
unordered_multiset(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_multiset from an initializer_list.
auto contains(const _Kt &__x) const -> decltype(_M_h._M_find_tr(__x), void(), true)
Finds whether an element with the given key exists.
auto count(const _Kt &__x) const -> decltype(_M_h._M_count_tr(__x))
Finds the number of elements.
size_type count(const key_type &__x) const
Finds the number of elements.
iterator erase(const_iterator __position)
Erases an element from an unordered_multiset.
unordered_multiset(unordered_multiset &&)=default
Move constructor.
_Hashtable::reference reference
Iterator-related typedefs.
iterator emplace_hint(const_iterator __pos, _Args &&... __args)
Inserts an element into the unordered_multiset.
void swap(unordered_multiset &__x) noexcept(noexcept(_M_h.swap(__x._M_h)))
Swaps data with another unordered_multiset.
const_iterator begin() const noexcept
iterator erase(const_iterator __first, const_iterator __last)
Erases a [__first,__last) range of elements from an unordered_multiset.
const_iterator cbegin() const noexcept
void insert(_InputIterator __first, _InputIterator __last)
A template function that inserts a range of elements.
std::pair< const_iterator, const_iterator > equal_range(const key_type &__x) const
Finds a subsequence matching given key.
key_equal key_eq() const
Returns the key comparison object with which the unordered_multiset was constructed.
_Hashtable::const_pointer const_pointer
Iterator-related typedefs.
std::pair< iterator, iterator > equal_range(const key_type &__x)
Finds a subsequence matching given key.
iterator insert(value_type &&__x)
Inserts an element into the unordered_multiset.
iterator insert(const value_type &__x)
Inserts an element into the unordered_multiset.
const_iterator end() const noexcept
void reserve(size_type __n)
Prepare the unordered_multiset for a specified number of elements.
iterator insert(const_iterator __hint, value_type &&__x)
Inserts an element into the unordered_multiset.
_Hashtable::const_reference const_reference
Iterator-related typedefs.
iterator erase(iterator __position)
Erases an element from an unordered_multiset.
const_local_iterator cend(size_type __n) const
Returns a read-only (constant) iterator pointing to one past the last bucket elements.
size_type max_bucket_count() const noexcept
Returns the maximum number of buckets of the unordered_multiset.
iterator insert(node_type &&__nh)
Re-insert an extracted node.
_Hashtable::hasher hasher
Public typedefs.
unordered_multiset(size_type __n, const hasher &__hf=hasher(), const key_equal &__eql=key_equal(), const allocator_type &__a=allocator_type())
Default constructor creates no elements.
unordered_multiset & operator=(initializer_list< value_type > __l)
Unordered_multiset list assignment operator.
size_type size() const noexcept
Returns the size of the unordered_multiset.
_Hashtable::iterator iterator
Iterator-related typedefs.
local_iterator end(size_type __n)
Returns a read-only (constant) iterator pointing to one past the last bucket elements.
auto equal_range(const _Kt &__x) const -> decltype(_M_h._M_equal_range_tr(__x))
Finds a subsequence matching given key.
node_type extract(const_iterator __pos)
Extract a node.
size_type max_size() const noexcept
Returns the maximum size of the unordered_multiset.
const_local_iterator cbegin(size_type __n) const
Returns a read-only (constant) iterator pointing to the first bucket element.
unordered_multiset(const unordered_multiset &)=default
Copy constructor.
_Hashtable::const_local_iterator const_local_iterator
Iterator-related typedefs.
size_type erase(const key_type &__x)
Erases elements according to the provided key.
const_iterator find(const key_type &__x) const
Tries to locate an element in an unordered_multiset.
allocator_type get_allocator() const noexcept
Returns the allocator object used by the unordered_multiset.
_Hashtable::key_equal key_equal
Public typedefs.
void max_load_factor(float __z)
Change the unordered_multiset maximum load factor.
A standard container composed of unique keys (containing at most one of each key value) in which the ...
std::pair< iterator, bool > insert(const value_type &__x)
Attempts to insert an element into the unordered_set.
_Hashtable::iterator iterator
Iterator-related typedefs.
unordered_set(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_set from an initializer_list.
void max_load_factor(float __z)
Change the unordered_set maximum load factor.
_Hashtable::reference reference
Iterator-related typedefs.
const_local_iterator end(size_type __n) const
Returns a read-only (constant) iterator pointing to one past the last bucket elements.
_Hashtable::value_type value_type
Public typedefs.
const_iterator cend() const noexcept
auto find(const _Kt &__k) -> decltype(_M_h._M_find_tr(__k))
Tries to locate an element in an unordered_set.
const_iterator find(const key_type &__x) const
Tries to locate an element in an unordered_set.
_Hashtable::key_type key_type
Public typedefs.
size_type count(const key_type &__x) const
Finds the number of elements.
const_local_iterator begin(size_type __n) const
Returns a read-only (constant) iterator pointing to the first bucket element.
auto equal_range(const _Kt &__k) -> decltype(_M_h._M_equal_range_tr(__k))
Finds a subsequence matching given key.
const_local_iterator cbegin(size_type __n) const
Returns a read-only (constant) iterator pointing to the first bucket element.
auto count(const _Kt &__k) const -> decltype(_M_h._M_count_tr(__k))
Finds the number of elements.
const_iterator begin() const noexcept
_Hashtable::hasher hasher
Public typedefs.
_Hashtable::local_iterator local_iterator
Iterator-related typedefs.
insert_return_type insert(node_type &&__nh)
Re-insert an extracted node.
_Hashtable::size_type size_type
Iterator-related typedefs.
const_iterator cbegin() const noexcept
bool empty() const noexcept
Returns true if the unordered_set is empty.
unordered_set & operator=(initializer_list< value_type > __l)
Unordered_set list assignment operator.
iterator erase(iterator __position)
Erases an element from an unordered_set.
unordered_set(unordered_set &&)=default
Move constructor.
unordered_set(const allocator_type &__a)
Creates an unordered_set with no elements.
const_local_iterator cend(size_type __n) const
Returns a read-only (constant) iterator pointing to one past the last bucket elements.
auto contains(const _Kt &__k) const -> decltype(_M_h._M_find_tr(__k), void(), true)
Finds whether an element with the given key exists.
_Hashtable::const_pointer const_pointer
Iterator-related typedefs.
std::pair< const_iterator, const_iterator > equal_range(const key_type &__x) const
Finds a subsequence matching given key.
void swap(unordered_set &__x) noexcept(noexcept(_M_h.swap(__x._M_h)))
Swaps data with another unordered_set.
iterator insert(const_iterator __hint, const value_type &__x)
Attempts to insert an element into the unordered_set.
std::pair< iterator, bool > insert(value_type &&__x)
Attempts to insert an element into the unordered_set.
float load_factor() const noexcept
Returns the average number of elements per bucket.
void rehash(size_type __n)
May rehash the unordered_set.
local_iterator end(size_type __n)
Returns a read-only (constant) iterator pointing to one past the last bucket elements.
_Hashtable::key_equal key_equal
Public typedefs.
size_type size() const noexcept
Returns the size of the unordered_set.
iterator insert(const_iterator, node_type &&__nh)
Re-insert an extracted node.
_Hashtable::const_iterator const_iterator
Iterator-related typedefs.
_Hashtable::difference_type difference_type
Iterator-related typedefs.
_Hashtable::const_reference const_reference
Iterator-related typedefs.
hasher hash_function() const
Returns the hash functor object with which the unordered_set was constructed.
unordered_set(const unordered_set &)=default
Copy constructor.
std::pair< iterator, iterator > equal_range(const key_type &__x)
Finds a subsequence matching given key.
auto find(const _Kt &__k) const -> decltype(_M_h._M_find_tr(__k))
Tries to locate an element in an unordered_set.
iterator emplace_hint(const_iterator __pos, _Args &&... __args)
Attempts to insert an element into the unordered_set.
key_equal key_eq() const
Returns the key comparison object with which the unordered_set was constructed.
_Hashtable::allocator_type allocator_type
Public typedefs.
iterator insert(const_iterator __hint, value_type &&__x)
Attempts to insert an element into the unordered_set.
const_iterator end() const noexcept
node_type extract(const key_type &__key)
Extract a node.
local_iterator begin(size_type __n)
Returns a read-only (constant) iterator pointing to the first bucket element.
unordered_set()=default
Default constructor.
unordered_set & operator=(unordered_set &&)=default
Move assignment operator.
void insert(_InputIterator __first, _InputIterator __last)
A template function that attempts to insert a range of elements.
float max_load_factor() const noexcept
Returns a positive number that the unordered_set tries to keep the load factor less than or equal to.
bool contains(const key_type &__x) const
Finds whether an element with the given key exists.
std::pair< iterator, bool > emplace(_Args &&... __args)
Attempts to build and insert an element into the unordered_set.
unordered_set & operator=(const unordered_set &)=default
Copy assignment operator.
size_type erase(const key_type &__x)
Erases elements according to the provided key.
unordered_set(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 erase(const_iterator __first, const_iterator __last)
Erases a [__first,__last) range of elements from an unordered_set.
iterator erase(const_iterator __position)
Erases an element from an unordered_set.
allocator_type get_allocator() const noexcept
Returns the allocator object used by the unordered_set.
auto equal_range(const _Kt &__k) const -> decltype(_M_h._M_equal_range_tr(__k))
Finds a subsequence matching given key.
_Hashtable::const_local_iterator const_local_iterator
Iterator-related typedefs.
void insert(initializer_list< value_type > __l)
Attempts to insert a list of elements into the unordered_set.
unordered_set(_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_set from a range.
size_type bucket_count() const noexcept
Returns the number of buckets of the unordered_set.
void reserve(size_type __n)
Prepare the unordered_set for a specified number of elements.
node_type extract(const_iterator __pos)
Extract a node.
_Hashtable::pointer pointer
Iterator-related typedefs.
iterator begin() noexcept
iterator find(const key_type &__x)
Tries to locate an element in an unordered_set.
size_type max_size() const noexcept
Returns the maximum size of the unordered_set.
size_type max_bucket_count() const noexcept
Returns the maximum number of buckets of the unordered_set.