30 #ifndef _UNORDERED_SET_H
31 #define _UNORDERED_SET_H
38 namespace std _GLIBCXX_VISIBILITY(default)
40 _GLIBCXX_BEGIN_NAMESPACE_VERSION
41 _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
47 template<
typename _Value,
52 using __uset_hashtable = _Hashtable<_Value, _Value, _Alloc,
53 __detail::_Identity, _Pred, _Hash,
54 __detail::_Mod_range_hashing,
55 __detail::_Default_ranged_hash,
56 __detail::_Prime_rehash_policy, _Tr>;
62 template<
typename _Value,
67 using __umset_hashtable = _Hashtable<_Value, _Value, _Alloc,
70 __detail::_Mod_range_hashing,
71 __detail::_Default_ranged_hash,
72 __detail::_Prime_rehash_policy, _Tr>;
74 template<
class _Value,
class _Hash,
class _Pred,
class _Alloc>
100 template<
typename _Value,
106 typedef __uset_hashtable<_Value, _Hash, _Pred, _Alloc> _Hashtable;
115 typedef typename _Hashtable::hasher
hasher;
134 #if __cplusplus > 201402L
135 using node_type =
typename _Hashtable::node_type;
136 using insert_return_type =
typename _Hashtable::insert_return_type;
156 : _M_h(__n, __hf, __eql, __a)
172 template<
typename _InputIterator>
178 : _M_h(__first, __last, __n, __hf, __eql, __a)
203 : _M_h(__uset._M_h, __a)
213 noexcept( noexcept(_Hashtable(
std::move(__uset._M_h), __a)) )
214 : _M_h(
std::
move(__uset._M_h), __a)
233 : _M_h(__l, __n, __hf, __eql, __a)
245 template<
typename _InputIterator>
252 template<
typename _InputIterator>
300 {
return _M_h.get_allocator(); }
305 _GLIBCXX_NODISCARD
bool
307 {
return _M_h.empty(); }
312 {
return _M_h.size(); }
317 {
return _M_h.max_size(); }
328 {
return _M_h.begin(); }
332 {
return _M_h.begin(); }
342 {
return _M_h.end(); }
346 {
return _M_h.end(); }
355 {
return _M_h.begin(); }
363 {
return _M_h.end(); }
382 template<
typename... _Args>
385 {
return _M_h.emplace(std::forward<_Args>(__args)...); }
408 template<
typename... _Args>
411 {
return _M_h.emplace_hint(__pos, std::forward<_Args>(__args)...); }
429 {
return _M_h.insert(__x); }
458 {
return _M_h.insert(__hint, __x); }
462 {
return _M_h.insert(__hint,
std::move(__x)); }
474 template<
typename _InputIterator>
476 insert(_InputIterator __first, _InputIterator __last)
477 { _M_h.insert(__first, __last); }
488 { _M_h.insert(__l); }
490 #if __cplusplus > 201402L
495 __glibcxx_assert(__pos !=
end());
496 return _M_h.extract(__pos);
502 {
return _M_h.extract(__key); }
507 {
return _M_h._M_reinsert_node(
std::move(__nh)); }
512 {
return _M_h._M_reinsert_node(
std::move(__nh)).position; }
531 {
return _M_h.erase(__position); }
536 {
return _M_h.erase(__position); }
553 {
return _M_h.erase(__x); }
571 {
return _M_h.erase(__first, __last); }
594 noexcept( noexcept(_M_h.swap(__x._M_h)) )
595 { _M_h.swap(__x._M_h); }
597 #if __cplusplus > 201402L
598 template<
typename,
typename,
typename>
599 friend class std::_Hash_merge_helper;
601 template<
typename _H2,
typename _P2>
605 using _Merge_helper = _Hash_merge_helper<unordered_set, _H2, _P2>;
606 _M_h._M_merge_unique(_Merge_helper::_S_get_table(__source));
609 template<
typename _H2,
typename _P2>
611 merge(unordered_set<_Value, _H2, _P2, _Alloc>&& __source)
614 template<
typename _H2,
typename _P2>
616 merge(unordered_multiset<_Value, _H2, _P2, _Alloc>& __source)
618 using _Merge_helper = _Hash_merge_helper<unordered_set, _H2, _P2>;
619 _M_h._M_merge_unique(_Merge_helper::_S_get_table(__source));
622 template<
typename _H2,
typename _P2>
624 merge(unordered_multiset<_Value, _H2, _P2, _Alloc>&& __source)
634 {
return _M_h.hash_function(); }
640 {
return _M_h.key_eq(); }
658 {
return _M_h.find(__x); }
660 #if __cplusplus > 201703L
661 template<
typename _Kt>
664 -> decltype(_M_h._M_find_tr(__k))
665 {
return _M_h._M_find_tr(__k); }
670 {
return _M_h.find(__x); }
672 #if __cplusplus > 201703L
673 template<
typename _Kt>
676 -> decltype(_M_h._M_find_tr(__k))
677 {
return _M_h._M_find_tr(__k); }
693 {
return _M_h.count(__x); }
695 #if __cplusplus > 201703L
696 template<
typename _Kt>
699 -> decltype(_M_h._M_count_tr(__k))
700 {
return _M_h._M_count_tr(__k); }
704 #if __cplusplus > 201703L
713 {
return _M_h.find(__x) != _M_h.end(); }
715 template<
typename _Kt>
718 -> decltype(_M_h._M_find_tr(__k),
void(),
true)
719 {
return _M_h._M_find_tr(__k) != _M_h.end(); }
734 {
return _M_h.equal_range(__x); }
736 #if __cplusplus > 201703L
737 template<
typename _Kt>
740 -> decltype(_M_h._M_equal_range_tr(__k))
741 {
return _M_h._M_equal_range_tr(__k); }
746 {
return _M_h.equal_range(__x); }
748 #if __cplusplus > 201703L
749 template<
typename _Kt>
752 -> decltype(_M_h._M_equal_range_tr(__k))
753 {
return _M_h._M_equal_range_tr(__k); }
762 {
return _M_h.bucket_count(); }
767 {
return _M_h.max_bucket_count(); }
776 {
return _M_h.bucket_size(__n); }
785 {
return _M_h.bucket(__key); }
796 {
return _M_h.begin(__n); }
800 {
return _M_h.begin(__n); }
804 {
return _M_h.cbegin(__n); }
816 {
return _M_h.end(__n); }
820 {
return _M_h.end(__n); }
824 {
return _M_h.cend(__n); }
832 {
return _M_h.load_factor(); }
838 {
return _M_h.max_load_factor(); }
846 { _M_h.max_load_factor(__z); }
857 { _M_h.rehash(__n); }
868 { _M_h.reserve(__n); }
870 template<
typename _Value1,
typename _Hash1,
typename _Pred1,
877 #if __cpp_deduction_guides >= 201606
879 template<
typename _InputIterator,
881 hash<typename iterator_traits<_InputIterator>::value_type>,
883 equal_to<typename iterator_traits<_InputIterator>::value_type>,
884 typename _Allocator =
885 allocator<typename iterator_traits<_InputIterator>::value_type>,
886 typename = _RequireInputIter<_InputIterator>,
887 typename = _RequireNotAllocatorOrIntegral<_Hash>,
888 typename = _RequireNotAllocator<_Pred>,
889 typename = _RequireAllocator<_Allocator>>
890 unordered_set(_InputIterator, _InputIterator,
892 _Hash = _Hash(), _Pred = _Pred(), _Allocator = _Allocator())
893 -> unordered_set<
typename iterator_traits<_InputIterator>::value_type,
894 _Hash, _Pred, _Allocator>;
896 template<
typename _Tp,
typename _Hash = hash<_Tp>,
897 typename _Pred = equal_to<_Tp>,
898 typename _Allocator = allocator<_Tp>,
899 typename = _RequireNotAllocatorOrIntegral<_Hash>,
900 typename = _RequireNotAllocator<_Pred>,
901 typename = _RequireAllocator<_Allocator>>
902 unordered_set(initializer_list<_Tp>,
904 _Hash = _Hash(), _Pred = _Pred(), _Allocator = _Allocator())
905 -> unordered_set<_Tp, _Hash, _Pred, _Allocator>;
907 template<
typename _InputIterator,
typename _Allocator,
908 typename = _RequireInputIter<_InputIterator>,
909 typename = _RequireAllocator<_Allocator>>
910 unordered_set(_InputIterator, _InputIterator,
914 typename iterator_traits<_InputIterator>::value_type>,
916 typename iterator_traits<_InputIterator>::value_type>,
919 template<
typename _InputIterator,
typename _Hash,
typename _Allocator,
920 typename = _RequireInputIter<_InputIterator>,
921 typename = _RequireNotAllocatorOrIntegral<_Hash>,
922 typename = _RequireAllocator<_Allocator>>
923 unordered_set(_InputIterator, _InputIterator,
929 typename iterator_traits<_InputIterator>::value_type>,
932 template<
typename _Tp,
typename _Allocator,
933 typename = _RequireAllocator<_Allocator>>
934 unordered_set(initializer_list<_Tp>,
936 -> unordered_set<_Tp, hash<_Tp>, equal_to<_Tp>, _Allocator>;
938 template<
typename _Tp,
typename _Hash,
typename _Allocator,
939 typename = _RequireNotAllocatorOrIntegral<_Hash>,
940 typename = _RequireAllocator<_Allocator>>
941 unordered_set(initializer_list<_Tp>,
943 -> unordered_set<_Tp, _Hash, equal_to<_Tp>, _Allocator>;
968 template<
typename _Value,
969 typename _Hash = hash<_Value>,
970 typename _Pred = equal_to<_Value>,
971 typename _Alloc = allocator<_Value>>
972 class unordered_multiset
974 typedef __umset_hashtable<_Value, _Hash, _Pred, _Alloc> _Hashtable;
983 typedef typename _Hashtable::hasher
hasher;
1002 #if __cplusplus > 201402L
1003 using node_type =
typename _Hashtable::node_type;
1023 : _M_h(__n, __hf, __eql, __a)
1039 template<
typename _InputIterator>
1045 : _M_h(__first, __last, __n, __hf, __eql, __a)
1070 : _M_h(__l, __n, __hf, __eql, __a)
1097 : _M_h(__umset._M_h, __a)
1107 noexcept( noexcept(_Hashtable(
std::move(__umset._M_h), __a)) )
1108 : _M_h(
std::
move(__umset._M_h), __a)
1120 template<
typename _InputIterator>
1127 template<
typename _InputIterator>
1167 {
return _M_h.get_allocator(); }
1172 _GLIBCXX_NODISCARD
bool
1174 {
return _M_h.empty(); }
1179 {
return _M_h.size(); }
1184 {
return _M_h.max_size(); }
1195 {
return _M_h.begin(); }
1199 {
return _M_h.begin(); }
1209 {
return _M_h.end(); }
1213 {
return _M_h.end(); }
1222 {
return _M_h.begin(); }
1230 {
return _M_h.end(); }
1241 template<
typename... _Args>
1244 {
return _M_h.emplace(std::forward<_Args>(__args)...); }
1263 template<
typename... _Args>
1266 {
return _M_h.emplace_hint(__pos, std::forward<_Args>(__args)...); }
1278 {
return _M_h.insert(__x); }
1304 {
return _M_h.insert(__hint, __x); }
1308 {
return _M_h.insert(__hint,
std::move(__x)); }
1319 template<
typename _InputIterator>
1321 insert(_InputIterator __first, _InputIterator __last)
1322 { _M_h.insert(__first, __last); }
1333 { _M_h.insert(__l); }
1335 #if __cplusplus > 201402L
1340 __glibcxx_assert(__pos !=
end());
1341 return _M_h.extract(__pos);
1347 {
return _M_h.extract(__key); }
1352 {
return _M_h._M_reinsert_node_multi(
cend(),
std::move(__nh)); }
1357 {
return _M_h._M_reinsert_node_multi(__hint,
std::move(__nh)); }
1377 {
return _M_h.erase(__position); }
1382 {
return _M_h.erase(__position); }
1400 {
return _M_h.erase(__x); }
1420 {
return _M_h.erase(__first, __last); }
1444 noexcept( noexcept(_M_h.swap(__x._M_h)) )
1445 { _M_h.swap(__x._M_h); }
1447 #if __cplusplus > 201402L
1448 template<
typename,
typename,
typename>
1449 friend class std::_Hash_merge_helper;
1451 template<
typename _H2,
typename _P2>
1456 = _Hash_merge_helper<unordered_multiset, _H2, _P2>;
1457 _M_h._M_merge_multi(_Merge_helper::_S_get_table(__source));
1460 template<
typename _H2,
typename _P2>
1462 merge(unordered_multiset<_Value, _H2, _P2, _Alloc>&& __source)
1463 { merge(__source); }
1465 template<
typename _H2,
typename _P2>
1467 merge(unordered_set<_Value, _H2, _P2, _Alloc>& __source)
1470 = _Hash_merge_helper<unordered_multiset, _H2, _P2>;
1471 _M_h._M_merge_multi(_Merge_helper::_S_get_table(__source));
1474 template<
typename _H2,
typename _P2>
1476 merge(unordered_set<_Value, _H2, _P2, _Alloc>&& __source)
1477 { merge(__source); }
1486 {
return _M_h.hash_function(); }
1492 {
return _M_h.key_eq(); }
1510 {
return _M_h.find(__x); }
1512 #if __cplusplus > 201703L
1513 template<
typename _Kt>
1516 -> decltype(_M_h._M_find_tr(__x))
1517 {
return _M_h._M_find_tr(__x); }
1522 {
return _M_h.find(__x); }
1524 #if __cplusplus > 201703L
1525 template<
typename _Kt>
1528 -> decltype(_M_h._M_find_tr(__x))
1529 {
return _M_h._M_find_tr(__x); }
1541 {
return _M_h.count(__x); }
1543 #if __cplusplus > 201703L
1544 template<
typename _Kt>
1546 count(
const _Kt& __x)
const -> decltype(_M_h._M_count_tr(__x))
1547 {
return _M_h._M_count_tr(__x); }
1551 #if __cplusplus > 201703L
1560 {
return _M_h.find(__x) != _M_h.end(); }
1562 template<
typename _Kt>
1565 -> decltype(_M_h._M_find_tr(__x),
void(),
true)
1566 {
return _M_h._M_find_tr(__x) != _M_h.end(); }
1579 {
return _M_h.equal_range(__x); }
1581 #if __cplusplus > 201703L
1582 template<
typename _Kt>
1585 -> decltype(_M_h._M_equal_range_tr(__x))
1586 {
return _M_h._M_equal_range_tr(__x); }
1591 {
return _M_h.equal_range(__x); }
1593 #if __cplusplus > 201703L
1594 template<
typename _Kt>
1597 -> decltype(_M_h._M_equal_range_tr(__x))
1598 {
return _M_h._M_equal_range_tr(__x); }
1607 {
return _M_h.bucket_count(); }
1612 {
return _M_h.max_bucket_count(); }
1621 {
return _M_h.bucket_size(__n); }
1629 bucket(
const key_type& __key)
const
1630 {
return _M_h.bucket(__key); }
1641 {
return _M_h.begin(__n); }
1645 {
return _M_h.begin(__n); }
1649 {
return _M_h.cbegin(__n); }
1661 {
return _M_h.end(__n); }
1665 {
return _M_h.end(__n); }
1669 {
return _M_h.cend(__n); }
1677 {
return _M_h.load_factor(); }
1683 {
return _M_h.max_load_factor(); }
1691 { _M_h.max_load_factor(__z); }
1702 { _M_h.rehash(__n); }
1713 { _M_h.reserve(__n); }
1715 template<
typename _Value1,
typename _Hash1,
typename _Pred1,
1723 #if __cpp_deduction_guides >= 201606
1725 template<
typename _InputIterator,
1727 hash<typename iterator_traits<_InputIterator>::value_type>,
1729 equal_to<typename iterator_traits<_InputIterator>::value_type>,
1730 typename _Allocator =
1731 allocator<typename iterator_traits<_InputIterator>::value_type>,
1732 typename = _RequireInputIter<_InputIterator>,
1733 typename = _RequireNotAllocatorOrIntegral<_Hash>,
1734 typename = _RequireNotAllocator<_Pred>,
1735 typename = _RequireAllocator<_Allocator>>
1736 unordered_multiset(_InputIterator, _InputIterator,
1738 _Hash = _Hash(), _Pred = _Pred(),
1739 _Allocator = _Allocator())
1740 -> unordered_multiset<
typename iterator_traits<_InputIterator>::value_type,
1741 _Hash, _Pred, _Allocator>;
1743 template<
typename _Tp,
typename _Hash = hash<_Tp>,
1744 typename _Pred = equal_to<_Tp>,
1745 typename _Allocator = allocator<_Tp>,
1746 typename = _RequireNotAllocatorOrIntegral<_Hash>,
1747 typename = _RequireNotAllocator<_Pred>,
1748 typename = _RequireAllocator<_Allocator>>
1749 unordered_multiset(initializer_list<_Tp>,
1751 _Hash = _Hash(), _Pred = _Pred(),
1752 _Allocator = _Allocator())
1753 -> unordered_multiset<_Tp, _Hash, _Pred, _Allocator>;
1755 template<
typename _InputIterator,
typename _Allocator,
1756 typename = _RequireInputIter<_InputIterator>,
1757 typename = _RequireAllocator<_Allocator>>
1758 unordered_multiset(_InputIterator, _InputIterator,
1762 iterator_traits<_InputIterator>::value_type>,
1764 iterator_traits<_InputIterator>::value_type>,
1767 template<
typename _InputIterator,
typename _Hash,
typename _Allocator,
1768 typename = _RequireInputIter<_InputIterator>,
1769 typename = _RequireNotAllocatorOrIntegral<_Hash>,
1770 typename = _RequireAllocator<_Allocator>>
1771 unordered_multiset(_InputIterator, _InputIterator,
1774 -> unordered_multiset<
typename
1775 iterator_traits<_InputIterator>::value_type,
1779 iterator_traits<_InputIterator>::value_type>,
1782 template<
typename _Tp,
typename _Allocator,
1783 typename = _RequireAllocator<_Allocator>>
1784 unordered_multiset(initializer_list<_Tp>,
1786 -> unordered_multiset<_Tp, hash<_Tp>, equal_to<_Tp>, _Allocator>;
1788 template<
typename _Tp,
typename _Hash,
typename _Allocator,
1789 typename = _RequireNotAllocatorOrIntegral<_Hash>,
1790 typename = _RequireAllocator<_Allocator>>
1791 unordered_multiset(initializer_list<_Tp>,
1793 -> unordered_multiset<_Tp, _Hash, equal_to<_Tp>, _Allocator>;
1797 template<
class _Value,
class _Hash,
class _Pred,
class _Alloc>
1799 swap(unordered_set<_Value, _Hash, _Pred, _Alloc>& __x,
1800 unordered_set<_Value, _Hash, _Pred, _Alloc>& __y)
1801 noexcept(noexcept(__x.swap(__y)))
1804 template<
class _Value,
class _Hash,
class _Pred,
class _Alloc>
1806 swap(unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x,
1807 unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y)
1808 noexcept(noexcept(__x.swap(__y)))
1811 template<
class _Value,
class _Hash,
class _Pred,
class _Alloc>
1813 operator==(
const unordered_set<_Value, _Hash, _Pred, _Alloc>& __x,
1814 const unordered_set<_Value, _Hash, _Pred, _Alloc>& __y)
1815 {
return __x._M_h._M_equal(__y._M_h); }
1817 #if __cpp_impl_three_way_comparison < 201907L
1818 template<
class _Value,
class _Hash,
class _Pred,
class _Alloc>
1820 operator!=(
const unordered_set<_Value, _Hash, _Pred, _Alloc>& __x,
1821 const unordered_set<_Value, _Hash, _Pred, _Alloc>& __y)
1822 {
return !(__x == __y); }
1825 template<
class _Value,
class _Hash,
class _Pred,
class _Alloc>
1827 operator==(
const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x,
1828 const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y)
1829 {
return __x._M_h._M_equal(__y._M_h); }
1831 #if __cpp_impl_three_way_comparison < 201907L
1832 template<
class _Value,
class _Hash,
class _Pred,
class _Alloc>
1834 operator!=(
const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x,
1835 const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y)
1836 {
return !(__x == __y); }
1839 _GLIBCXX_END_NAMESPACE_CONTAINER
1841 #if __cplusplus > 201402L
1843 template<
typename _Val,
typename _Hash1,
typename _Eq1,
typename _Alloc,
1844 typename _Hash2,
typename _Eq2>
1845 struct _Hash_merge_helper<
1846 _GLIBCXX_STD_C::unordered_set<_Val, _Hash1, _Eq1, _Alloc>, _Hash2, _Eq2>
1849 template<
typename... _Tp>
1850 using unordered_set = _GLIBCXX_STD_C::unordered_set<_Tp...>;
1851 template<
typename... _Tp>
1852 using unordered_multiset = _GLIBCXX_STD_C::unordered_multiset<_Tp...>;
1854 friend unordered_set<_Val, _Hash1, _Eq1, _Alloc>;
1857 _S_get_table(unordered_set<_Val, _Hash2, _Eq2, _Alloc>& __set)
1858 {
return __set._M_h; }
1861 _S_get_table(unordered_multiset<_Val, _Hash2, _Eq2, _Alloc>& __set)
1862 {
return __set._M_h; }
1866 template<
typename _Val,
typename _Hash1,
typename _Eq1,
typename _Alloc,
1867 typename _Hash2,
typename _Eq2>
1868 struct _Hash_merge_helper<
1869 _GLIBCXX_STD_C::unordered_multiset<_Val, _Hash1, _Eq1, _Alloc>,
1873 template<
typename... _Tp>
1874 using unordered_set = _GLIBCXX_STD_C::unordered_set<_Tp...>;
1875 template<
typename... _Tp>
1876 using unordered_multiset = _GLIBCXX_STD_C::unordered_multiset<_Tp...>;
1878 friend unordered_multiset<_Val, _Hash1, _Eq1, _Alloc>;
1881 _S_get_table(unordered_set<_Val, _Hash2, _Eq2, _Alloc>& __set)
1882 {
return __set._M_h; }
1885 _S_get_table(unordered_multiset<_Val, _Hash2, _Eq2, _Alloc>& __set)
1886 {
return __set._M_h; }
1890 _GLIBCXX_END_NAMESPACE_VERSION