29 #ifndef _GLIBCXX_DEBUG_UNORDERED_SET
30 #define _GLIBCXX_DEBUG_UNORDERED_SET 1
32 #pragma GCC system_header
34 #if __cplusplus < 201103L
38 namespace std _GLIBCXX_VISIBILITY(default) {
namespace __debug {
39 template<
typename _Key,
typename _Hash,
typename _Pred,
typename _Allocator>
41 template<
typename _Key,
typename _Hash,
typename _Pred,
typename _Allocator>
51 namespace std _GLIBCXX_VISIBILITY(default)
56 template<
typename _Value,
62 unordered_set<_Value, _Hash, _Pred, _Alloc>, _Alloc,
63 __gnu_debug::_Safe_unordered_container>,
64 public _GLIBCXX_STD_C::unordered_set<_Value, _Hash, _Pred, _Alloc>
66 typedef _GLIBCXX_STD_C::unordered_set<
67 _Value, _Hash, _Pred, _Alloc> _Base;
71 typedef typename _Base::const_iterator _Base_const_iterator;
72 typedef typename _Base::iterator _Base_iterator;
73 typedef typename _Base::const_local_iterator _Base_const_local_iterator;
74 typedef typename _Base::local_iterator _Base_local_iterator;
76 template<
typename _ItT,
typename _SeqT,
typename _CatT>
77 friend class ::__gnu_debug::_Safe_iterator;
78 template<
typename _ItT,
typename _SeqT>
79 friend class ::__gnu_debug::_Safe_local_iterator;
84 _Base_ref(
const _Base& __r) : _M_ref(__r) { }
90 typedef typename _Base::size_type size_type;
91 typedef typename _Base::hasher hasher;
92 typedef typename _Base::key_equal key_equal;
93 typedef typename _Base::allocator_type allocator_type;
95 typedef typename _Base::key_type key_type;
96 typedef typename _Base::value_type value_type;
99 _Base_iterator, unordered_set> iterator;
101 _Base_const_iterator, unordered_set> const_iterator;
103 _Base_local_iterator, unordered_set> local_iterator;
105 _Base_const_local_iterator, unordered_set> const_local_iterator;
107 unordered_set() =
default;
110 unordered_set(size_type __n,
111 const hasher& __hf = hasher(),
112 const key_equal& __eql = key_equal(),
113 const allocator_type& __a = allocator_type())
114 : _Base(__n, __hf, __eql, __a) { }
116 template<
typename _InputIterator>
117 unordered_set(_InputIterator __first, _InputIterator __last,
119 const hasher& __hf = hasher(),
120 const key_equal& __eql = key_equal(),
121 const allocator_type& __a = allocator_type())
122 : _Base(__gnu_debug::
__base(
123 __glibcxx_check_valid_constructor_range(__first, __last)),
124 __gnu_debug::
__base(__last), __n,
125 __hf, __eql, __a) { }
127 unordered_set(
const unordered_set&) =
default;
129 unordered_set(_Base_ref __x)
130 : _Base(__x._M_ref) { }
132 unordered_set(unordered_set&&) =
default;
135 unordered_set(
const allocator_type& __a)
138 unordered_set(
const unordered_set& __uset,
139 const allocator_type& __a)
140 : _Base(__uset, __a) { }
142 unordered_set(unordered_set&& __uset,
143 const allocator_type& __a)
144 noexcept( noexcept(_Base(
std::move(__uset._M_base()), __a)) )
145 : _Safe(std::
move(__uset._M_safe()), __a),
146 _Base(std::
move(__uset._M_base()), __a) { }
148 unordered_set(initializer_list<value_type> __l,
150 const hasher& __hf = hasher(),
151 const key_equal& __eql = key_equal(),
152 const allocator_type& __a = allocator_type())
153 : _Base(__l, __n, __hf, __eql, __a) { }
155 unordered_set(size_type __n,
const allocator_type& __a)
156 : unordered_set(__n, hasher(), key_equal(), __a)
159 unordered_set(size_type __n,
const hasher& __hf,
160 const allocator_type& __a)
161 : unordered_set(__n, __hf, key_equal(), __a)
164 template<
typename _InputIterator>
165 unordered_set(_InputIterator __first, _InputIterator __last,
167 const allocator_type& __a)
168 : unordered_set(__first, __last, __n, hasher(), key_equal(), __a)
171 template<
typename _InputIterator>
172 unordered_set(_InputIterator __first, _InputIterator __last,
173 size_type __n,
const hasher& __hf,
174 const allocator_type& __a)
175 : unordered_set(__first, __last, __n, __hf, key_equal(), __a)
178 unordered_set(initializer_list<value_type> __l,
180 const allocator_type& __a)
181 : unordered_set(__l, __n, hasher(), key_equal(), __a)
184 unordered_set(initializer_list<value_type> __l,
185 size_type __n,
const hasher& __hf,
186 const allocator_type& __a)
187 : unordered_set(__l, __n, __hf, key_equal(), __a)
190 ~unordered_set() =
default;
193 operator=(
const unordered_set&) =
default;
196 operator=(unordered_set&&) =
default;
199 operator=(initializer_list<value_type> __l)
202 this->_M_invalidate_all();
207 swap(unordered_set& __x)
208 noexcept( noexcept(declval<_Base&>().swap(__x)) )
218 this->_M_invalidate_all();
223 {
return { _Base::begin(),
this }; }
226 begin() const noexcept
227 {
return { _Base::begin(),
this }; }
231 {
return { _Base::end(),
this }; }
235 {
return { _Base::end(),
this }; }
238 cbegin() const noexcept
239 {
return { _Base::cbegin(),
this }; }
242 cend() const noexcept
243 {
return { _Base::cend(),
this }; }
249 __glibcxx_check_bucket_index(__b);
250 return { _Base::begin(__b),
this };
256 __glibcxx_check_bucket_index(__b);
257 return { _Base::end(__b),
this };
261 begin(size_type __b)
const
263 __glibcxx_check_bucket_index(__b);
264 return { _Base::begin(__b),
this };
268 end(size_type __b)
const
270 __glibcxx_check_bucket_index(__b);
271 return { _Base::end(__b),
this };
275 cbegin(size_type __b)
const
277 __glibcxx_check_bucket_index(__b);
278 return { _Base::cbegin(__b),
this };
282 cend(size_type __b)
const
284 __glibcxx_check_bucket_index(__b);
285 return { _Base::cend(__b),
this };
289 bucket_size(size_type __b)
const
291 __glibcxx_check_bucket_index(__b);
292 return _Base::bucket_size(__b);
296 max_load_factor() const noexcept
297 {
return _Base::max_load_factor(); }
300 max_load_factor(
float __f)
302 __glibcxx_check_max_load_factor(__f);
303 _Base::max_load_factor(__f);
306 template<
typename... _Args>
308 emplace(_Args&&... __args)
310 size_type __bucket_count = this->bucket_count();
311 auto __res = _Base::emplace(std::forward<_Args>(__args)...);
312 _M_check_rehashed(__bucket_count);
313 return { { __res.first,
this }, __res.second };
316 template<
typename... _Args>
318 emplace_hint(const_iterator __hint, _Args&&... __args)
321 size_type __bucket_count = this->bucket_count();
322 auto __it = _Base::emplace_hint(__hint.base(),
323 std::forward<_Args>(__args)...);
324 _M_check_rehashed(__bucket_count);
325 return { __it,
this };
329 insert(
const value_type& __obj)
331 size_type __bucket_count = this->bucket_count();
332 auto __res = _Base::insert(__obj);
333 _M_check_rehashed(__bucket_count);
334 return { { __res.first,
this }, __res.second };
338 insert(const_iterator __hint,
const value_type& __obj)
341 size_type __bucket_count = this->bucket_count();
342 auto __it = _Base::insert(__hint.base(), __obj);
343 _M_check_rehashed(__bucket_count);
344 return { __it,
this };
348 insert(value_type&& __obj)
350 size_type __bucket_count = this->bucket_count();
351 auto __res = _Base::insert(
std::move(__obj));
352 _M_check_rehashed(__bucket_count);
353 return { { __res.first,
this }, __res.second };
357 insert(const_iterator __hint, value_type&& __obj)
360 size_type __bucket_count = this->bucket_count();
361 auto __it = _Base::insert(__hint.base(),
std::move(__obj));
362 _M_check_rehashed(__bucket_count);
363 return { __it,
this };
369 size_type __bucket_count = this->bucket_count();
371 _M_check_rehashed(__bucket_count);
374 template<
typename _InputIterator>
376 insert(_InputIterator __first, _InputIterator __last)
379 __glibcxx_check_valid_range2(__first, __last, __dist);
380 size_type __bucket_count = this->bucket_count();
382 if (__dist.
second >= __gnu_debug::__dp_sign)
383 _Base::insert(__gnu_debug::__unsafe(__first),
384 __gnu_debug::__unsafe(__last));
386 _Base::insert(__first, __last);
388 _M_check_rehashed(__bucket_count);
391 #if __cplusplus > 201402L
392 using node_type =
typename _Base::node_type;
393 using insert_return_type = _Node_insert_return<iterator, node_type>;
396 extract(const_iterator __position)
399 return _M_extract(__position.base());
403 extract(
const key_type& __key)
405 const auto __position = _Base::find(__key);
406 if (__position != _Base::end())
407 return _M_extract(__position);
412 insert(node_type&& __nh)
414 auto __ret = _Base::insert(
std::move(__nh));
416 { { __ret.position,
this }, __ret.inserted,
std::move(__ret.node) };
420 insert(const_iterator __hint, node_type&& __nh)
423 return { _Base::insert(__hint.base(),
std::move(__nh)),
this };
430 find(
const key_type& __key)
431 {
return { _Base::find(__key),
this }; }
433 #if __cplusplus > 201703L
434 template<
typename _Kt,
435 typename = std::__has_is_transparent_t<_Hash, _Kt>,
436 typename = std::__has_is_transparent_t<_Pred, _Kt>>
439 {
return { _Base::find(__k),
this }; }
443 find(
const key_type& __key)
const
444 {
return { _Base::find(__key),
this }; }
446 #if __cplusplus > 201703L
447 template<
typename _Kt,
448 typename = std::__has_is_transparent_t<_Hash, _Kt>,
449 typename = std::__has_is_transparent_t<_Pred, _Kt>>
451 find(
const _Kt& __k)
const
452 {
return { _Base::find(__k),
this }; }
456 equal_range(
const key_type& __key)
458 auto __res = _Base::equal_range(__key);
459 return { { __res.first,
this }, { __res.second,
this } };
462 #if __cplusplus > 201703L
463 template<
typename _Kt,
464 typename = std::__has_is_transparent_t<_Hash, _Kt>,
465 typename = std::__has_is_transparent_t<_Pred, _Kt>>
467 equal_range(
const _Kt& __k)
469 auto __res = _Base::equal_range(__k);
470 return { { __res.first,
this }, { __res.second,
this } };
475 equal_range(
const key_type& __key)
const
477 auto __res = _Base::equal_range(__key);
478 return { { __res.first,
this }, { __res.second,
this } };
481 #if __cplusplus > 201703L
482 template<
typename _Kt,
483 typename = std::__has_is_transparent_t<_Hash, _Kt>,
484 typename = std::__has_is_transparent_t<_Pred, _Kt>>
486 equal_range(
const _Kt& __k)
const
488 auto __res = _Base::equal_range(__k);
489 return { { __res.first,
this }, { __res.second,
this } };
494 erase(
const key_type& __key)
497 auto __victim = _Base::find(__key);
498 if (__victim != _Base::end())
507 erase(const_iterator __it)
510 return { _M_erase(__it.base()),
this };
517 return { _M_erase(__it.base()),
this };
521 erase(const_iterator __first, const_iterator __last)
524 for (
auto __tmp = __first.base(); __tmp != __last.
base(); ++__tmp)
526 _GLIBCXX_DEBUG_VERIFY(__tmp != _Base::cend(),
527 _M_message(__gnu_debug::__msg_valid_range)
528 ._M_iterator(__first,
"first")
529 ._M_iterator(__last,
"last"));
530 _M_invalidate(__tmp);
533 size_type __bucket_count = this->bucket_count();
534 auto __next = _Base::erase(__first.base(), __last.base());
535 _M_check_rehashed(__bucket_count);
536 return { __next,
this };
540 _M_base() noexcept {
return *
this; }
543 _M_base() const noexcept {
return *
this; }
547 _M_check_rehashed(size_type __prev_count)
549 if (__prev_count != this->bucket_count())
550 this->_M_invalidate_all();
554 _M_invalidate(_Base_const_iterator __victim)
557 [__victim](_Base_const_iterator __it) {
return __it == __victim; });
559 [__victim](_Base_const_local_iterator __it)
560 {
return __it == __victim; });
564 _M_erase(_Base_const_iterator __victim)
566 _M_invalidate(__victim);
567 size_type __bucket_count = this->bucket_count();
568 _Base_iterator __next = _Base::erase(__victim);
569 _M_check_rehashed(__bucket_count);
573 #if __cplusplus > 201402L
575 _M_extract(_Base_const_iterator __victim)
577 _M_invalidate(__victim);
578 return _Base::extract(__victim);
583 #if __cpp_deduction_guides >= 201606
585 template<
typename _InputIterator,
587 hash<typename iterator_traits<_InputIterator>::value_type>,
589 equal_to<typename iterator_traits<_InputIterator>::value_type>,
590 typename _Allocator =
591 allocator<typename iterator_traits<_InputIterator>::value_type>,
592 typename = _RequireInputIter<_InputIterator>,
593 typename = _RequireNotAllocatorOrIntegral<_Hash>,
594 typename = _RequireNotAllocator<_Pred>,
595 typename = _RequireAllocator<_Allocator>>
596 unordered_set(_InputIterator, _InputIterator,
597 unordered_set<int>::size_type = {},
598 _Hash = _Hash(), _Pred = _Pred(), _Allocator = _Allocator())
599 -> unordered_set<
typename iterator_traits<_InputIterator>::value_type,
600 _Hash, _Pred, _Allocator>;
602 template<
typename _Tp,
typename _Hash = hash<_Tp>,
603 typename _Pred = equal_to<_Tp>,
604 typename _Allocator = allocator<_Tp>,
605 typename = _RequireNotAllocatorOrIntegral<_Hash>,
606 typename = _RequireNotAllocator<_Pred>,
607 typename = _RequireAllocator<_Allocator>>
608 unordered_set(initializer_list<_Tp>,
609 unordered_set<int>::size_type = {},
610 _Hash = _Hash(), _Pred = _Pred(), _Allocator = _Allocator())
611 -> unordered_set<_Tp, _Hash, _Pred, _Allocator>;
613 template<
typename _InputIterator,
typename _Allocator,
614 typename = _RequireInputIter<_InputIterator>,
615 typename = _RequireAllocator<_Allocator>>
616 unordered_set(_InputIterator, _InputIterator,
617 unordered_set<int>::size_type, _Allocator)
618 -> unordered_set<typename iterator_traits<_InputIterator>::value_type,
620 typename iterator_traits<_InputIterator>::value_type>,
622 typename iterator_traits<_InputIterator>::value_type>,
625 template<
typename _InputIterator,
typename _Hash,
typename _Allocator,
626 typename = _RequireInputIter<_InputIterator>,
627 typename = _RequireNotAllocatorOrIntegral<_Hash>,
628 typename = _RequireAllocator<_Allocator>>
629 unordered_set(_InputIterator, _InputIterator,
630 unordered_set<int>::size_type,
632 -> unordered_set<typename iterator_traits<_InputIterator>::value_type,
635 typename iterator_traits<_InputIterator>::value_type>,
638 template<
typename _Tp,
typename _Allocator,
639 typename = _RequireAllocator<_Allocator>>
640 unordered_set(initializer_list<_Tp>,
641 unordered_set<int>::size_type, _Allocator)
642 -> unordered_set<_Tp, hash<_Tp>, equal_to<_Tp>, _Allocator>;
644 template<
typename _Tp,
typename _Hash,
typename _Allocator,
645 typename = _RequireNotAllocatorOrIntegral<_Hash>,
646 typename = _RequireAllocator<_Allocator>>
647 unordered_set(initializer_list<_Tp>,
648 unordered_set<int>::size_type, _Hash, _Allocator)
649 -> unordered_set<_Tp, _Hash, equal_to<_Tp>, _Allocator>;
653 template<
typename _Value,
typename _Hash,
typename _Pred,
typename _Alloc>
655 swap(unordered_set<_Value, _Hash, _Pred, _Alloc>& __x,
656 unordered_set<_Value, _Hash, _Pred, _Alloc>& __y)
657 noexcept(noexcept(__x.swap(__y)))
660 template<
typename _Value,
typename _Hash,
typename _Pred,
typename _Alloc>
662 operator==(
const unordered_set<_Value, _Hash, _Pred, _Alloc>& __x,
663 const unordered_set<_Value, _Hash, _Pred, _Alloc>& __y)
664 {
return __x._M_base() == __y._M_base(); }
666 #if __cpp_impl_three_way_comparison < 201907L
667 template<
typename _Value,
typename _Hash,
typename _Pred,
typename _Alloc>
669 operator!=(
const unordered_set<_Value, _Hash, _Pred, _Alloc>& __x,
670 const unordered_set<_Value, _Hash, _Pred, _Alloc>& __y)
671 {
return !(__x == __y); }
675 template<
typename _Value,
679 class unordered_multiset
681 unordered_multiset<_Value, _Hash, _Pred, _Alloc>, _Alloc,
682 __gnu_debug::_Safe_unordered_container>,
683 public _GLIBCXX_STD_C::unordered_multiset<_Value, _Hash, _Pred, _Alloc>
685 typedef _GLIBCXX_STD_C::unordered_multiset<
686 _Value, _Hash, _Pred, _Alloc> _Base;
689 typedef typename _Base::const_iterator _Base_const_iterator;
690 typedef typename _Base::iterator _Base_iterator;
691 typedef typename _Base::const_local_iterator
692 _Base_const_local_iterator;
693 typedef typename _Base::local_iterator _Base_local_iterator;
695 template<
typename _ItT,
typename _SeqT,
typename _CatT>
696 friend class ::__gnu_debug::_Safe_iterator;
697 template<
typename _ItT,
typename _SeqT>
698 friend class ::__gnu_debug::_Safe_local_iterator;
703 _Base_ref(
const _Base& __r) : _M_ref(__r) { }
709 typedef typename _Base::size_type size_type;
710 typedef typename _Base::hasher hasher;
711 typedef typename _Base::key_equal key_equal;
712 typedef typename _Base::allocator_type allocator_type;
714 typedef typename _Base::key_type key_type;
715 typedef typename _Base::value_type value_type;
718 _Base_iterator, unordered_multiset> iterator;
720 _Base_const_iterator, unordered_multiset> const_iterator;
722 _Base_local_iterator, unordered_multiset> local_iterator;
724 _Base_const_local_iterator, unordered_multiset> const_local_iterator;
726 unordered_multiset() =
default;
729 unordered_multiset(size_type __n,
730 const hasher& __hf = hasher(),
731 const key_equal& __eql = key_equal(),
732 const allocator_type& __a = allocator_type())
733 : _Base(__n, __hf, __eql, __a) { }
735 template<
typename _InputIterator>
736 unordered_multiset(_InputIterator __first, _InputIterator __last,
738 const hasher& __hf = hasher(),
739 const key_equal& __eql = key_equal(),
740 const allocator_type& __a = allocator_type())
741 : _Base(__gnu_debug::
__base(
742 __glibcxx_check_valid_constructor_range(__first, __last)),
743 __gnu_debug::
__base(__last), __n,
744 __hf, __eql, __a) { }
746 unordered_multiset(
const unordered_multiset&) =
default;
748 unordered_multiset(_Base_ref __x)
749 : _Base(__x._M_ref) { }
751 unordered_multiset(unordered_multiset&&) =
default;
754 unordered_multiset(
const allocator_type& __a)
757 unordered_multiset(
const unordered_multiset& __uset,
758 const allocator_type& __a)
759 : _Base(__uset, __a) { }
761 unordered_multiset(unordered_multiset&& __uset,
762 const allocator_type& __a)
763 noexcept( noexcept(_Base(
std::move(__uset._M_base()), __a)) )
764 : _Safe(std::
move(__uset._M_safe()), __a),
765 _Base(std::
move(__uset._M_base()), __a) { }
767 unordered_multiset(initializer_list<value_type> __l,
769 const hasher& __hf = hasher(),
770 const key_equal& __eql = key_equal(),
771 const allocator_type& __a = allocator_type())
772 : _Base(__l, __n, __hf, __eql, __a) { }
774 unordered_multiset(size_type __n,
const allocator_type& __a)
775 : unordered_multiset(__n, hasher(), key_equal(), __a)
778 unordered_multiset(size_type __n,
const hasher& __hf,
779 const allocator_type& __a)
780 : unordered_multiset(__n, __hf, key_equal(), __a)
783 template<
typename _InputIterator>
784 unordered_multiset(_InputIterator __first, _InputIterator __last,
786 const allocator_type& __a)
787 : unordered_multiset(__first, __last, __n, hasher(), key_equal(), __a)
790 template<
typename _InputIterator>
791 unordered_multiset(_InputIterator __first, _InputIterator __last,
792 size_type __n,
const hasher& __hf,
793 const allocator_type& __a)
794 : unordered_multiset(__first, __last, __n, __hf, key_equal(), __a)
797 unordered_multiset(initializer_list<value_type> __l,
799 const allocator_type& __a)
800 : unordered_multiset(__l, __n, hasher(), key_equal(), __a)
803 unordered_multiset(initializer_list<value_type> __l,
804 size_type __n,
const hasher& __hf,
805 const allocator_type& __a)
806 : unordered_multiset(__l, __n, __hf, key_equal(), __a)
809 ~unordered_multiset() =
default;
812 operator=(
const unordered_multiset&) =
default;
815 operator=(unordered_multiset&&) =
default;
818 operator=(initializer_list<value_type> __l)
820 this->_M_base() = __l;
821 this->_M_invalidate_all();
826 swap(unordered_multiset& __x)
827 noexcept( noexcept(declval<_Base&>().swap(__x)) )
837 this->_M_invalidate_all();
842 {
return { _Base::begin(),
this }; }
845 begin() const noexcept
846 {
return { _Base::begin(),
this }; }
850 {
return { _Base::end(),
this }; }
854 {
return { _Base::end(),
this }; }
858 {
return { _Base::cbegin(),
this }; }
861 cend() const noexcept
862 {
return { _Base::cend(),
this }; }
868 __glibcxx_check_bucket_index(__b);
869 return { _Base::begin(__b),
this };
875 __glibcxx_check_bucket_index(__b);
876 return { _Base::end(__b),
this };
880 begin(size_type __b)
const
882 __glibcxx_check_bucket_index(__b);
883 return { _Base::begin(__b),
this };
887 end(size_type __b)
const
889 __glibcxx_check_bucket_index(__b);
890 return { _Base::end(__b),
this };
894 cbegin(size_type __b)
const
896 __glibcxx_check_bucket_index(__b);
897 return { _Base::cbegin(__b),
this };
901 cend(size_type __b)
const
903 __glibcxx_check_bucket_index(__b);
904 return { _Base::cend(__b),
this };
908 bucket_size(size_type __b)
const
910 __glibcxx_check_bucket_index(__b);
911 return _Base::bucket_size(__b);
915 max_load_factor() const noexcept
916 {
return _Base::max_load_factor(); }
919 max_load_factor(
float __f)
921 __glibcxx_check_max_load_factor(__f);
922 _Base::max_load_factor(__f);
925 template<
typename... _Args>
927 emplace(_Args&&... __args)
929 size_type __bucket_count = this->bucket_count();
930 auto __it = _Base::emplace(std::forward<_Args>(__args)...);
931 _M_check_rehashed(__bucket_count);
932 return { __it,
this };
935 template<
typename... _Args>
937 emplace_hint(const_iterator __hint, _Args&&... __args)
940 size_type __bucket_count = this->bucket_count();
941 auto __it = _Base::emplace_hint(__hint.base(),
942 std::forward<_Args>(__args)...);
943 _M_check_rehashed(__bucket_count);
944 return { __it,
this };
948 insert(
const value_type& __obj)
950 size_type __bucket_count = this->bucket_count();
951 auto __it = _Base::insert(__obj);
952 _M_check_rehashed(__bucket_count);
953 return { __it,
this };
957 insert(const_iterator __hint,
const value_type& __obj)
960 size_type __bucket_count = this->bucket_count();
961 auto __it = _Base::insert(__hint.base(), __obj);
962 _M_check_rehashed(__bucket_count);
963 return { __it,
this };
967 insert(value_type&& __obj)
969 size_type __bucket_count = this->bucket_count();
970 auto __it = _Base::insert(
std::move(__obj));
971 _M_check_rehashed(__bucket_count);
972 return { __it,
this };
976 insert(const_iterator __hint, value_type&& __obj)
979 size_type __bucket_count = this->bucket_count();
980 auto __it = _Base::insert(__hint.base(),
std::move(__obj));
981 _M_check_rehashed(__bucket_count);
982 return { __it,
this };
988 size_type __bucket_count = this->bucket_count();
990 _M_check_rehashed(__bucket_count);
993 template<
typename _InputIterator>
995 insert(_InputIterator __first, _InputIterator __last)
998 __glibcxx_check_valid_range2(__first, __last, __dist);
999 size_type __bucket_count = this->bucket_count();
1001 if (__dist.
second >= __gnu_debug::__dp_sign)
1002 _Base::insert(__gnu_debug::__unsafe(__first),
1003 __gnu_debug::__unsafe(__last));
1005 _Base::insert(__first, __last);
1007 _M_check_rehashed(__bucket_count);
1010 #if __cplusplus > 201402L
1011 using node_type =
typename _Base::node_type;
1014 extract(const_iterator __position)
1017 return _M_extract(__position.base());
1021 extract(
const key_type& __key)
1023 const auto __position = _Base::find(__key);
1024 if (__position != _Base::end())
1025 return _M_extract(__position);
1030 insert(node_type&& __nh)
1031 {
return { _Base::insert(
std::move(__nh)),
this }; }
1034 insert(const_iterator __hint, node_type&& __nh)
1037 return { _Base::insert(__hint.base(),
std::move(__nh)),
this };
1044 find(
const key_type& __key)
1045 {
return { _Base::find(__key),
this }; }
1047 #if __cplusplus > 201703L
1048 template<
typename _Kt,
1049 typename = std::__has_is_transparent_t<_Hash, _Kt>,
1050 typename = std::__has_is_transparent_t<_Pred, _Kt>>
1052 find(
const _Kt& __k)
1053 {
return { _Base::find(__k),
this }; }
1057 find(
const key_type& __key)
const
1058 {
return { _Base::find(__key),
this }; }
1060 #if __cplusplus > 201703L
1061 template<
typename _Kt,
1062 typename = std::__has_is_transparent_t<_Hash, _Kt>,
1063 typename = std::__has_is_transparent_t<_Pred, _Kt>>
1065 find(
const _Kt& __k)
const
1066 {
return { _Base::find(__k),
this }; }
1070 equal_range(
const key_type& __key)
1072 auto __res = _Base::equal_range(__key);
1073 return { { __res.first,
this }, { __res.second,
this } };
1076 #if __cplusplus > 201703L
1077 template<
typename _Kt,
1078 typename = std::__has_is_transparent_t<_Hash, _Kt>,
1079 typename = std::__has_is_transparent_t<_Pred, _Kt>>
1081 equal_range(
const _Kt& __k)
1083 auto __res = _Base::equal_range(__k);
1084 return { { __res.first,
this }, { __res.second,
this } };
1089 equal_range(
const key_type& __key)
const
1091 auto __res = _Base::equal_range(__key);
1092 return { { __res.first,
this }, { __res.second,
this } };
1095 #if __cplusplus > 201703L
1096 template<
typename _Kt,
1097 typename = std::__has_is_transparent_t<_Hash, _Kt>,
1098 typename = std::__has_is_transparent_t<_Pred, _Kt>>
1100 equal_range(
const _Kt& __k)
const
1102 auto __res = _Base::equal_range(__k);
1103 return { { __res.first,
this }, { __res.second,
this } };
1108 erase(
const key_type& __key)
1111 auto __pair = _Base::equal_range(__key);
1112 for (
auto __victim = __pair.first; __victim != __pair.second;)
1114 _M_invalidate(__victim);
1115 __victim = _Base::erase(__victim);
1123 erase(const_iterator __it)
1126 return { _M_erase(__it.base()),
this };
1130 erase(iterator __it)
1133 return { _M_erase(__it.base()),
this };
1137 erase(const_iterator __first, const_iterator __last)
1140 for (
auto __tmp = __first.base(); __tmp != __last.base(); ++__tmp)
1142 _GLIBCXX_DEBUG_VERIFY(__tmp != _Base::cend(),
1143 _M_message(__gnu_debug::__msg_valid_range)
1144 ._M_iterator(__first,
"first")
1145 ._M_iterator(__last,
"last"));
1146 _M_invalidate(__tmp);
1148 return { _Base::erase(__first.base(), __last.base()),
this };
1152 _M_base() noexcept {
return *
this; }
1155 _M_base() const noexcept {
return *
this; }
1159 _M_check_rehashed(size_type __prev_count)
1161 if (__prev_count != this->bucket_count())
1162 this->_M_invalidate_all();
1166 _M_invalidate(_Base_const_iterator __victim)
1169 [__victim](_Base_const_iterator __it) {
return __it == __victim; });
1171 [__victim](_Base_const_local_iterator __it)
1172 {
return __it == __victim; });
1176 _M_erase(_Base_const_iterator __victim)
1178 _M_invalidate(__victim);
1179 size_type __bucket_count = this->bucket_count();
1180 _Base_iterator __next = _Base::erase(__victim);
1181 _M_check_rehashed(__bucket_count);
1185 #if __cplusplus > 201402L
1187 _M_extract(_Base_const_iterator __victim)
1189 _M_invalidate(__victim);
1190 return _Base::extract(__victim);
1195 #if __cpp_deduction_guides >= 201606
1197 template<
typename _InputIterator,
1199 hash<typename iterator_traits<_InputIterator>::value_type>,
1201 equal_to<typename iterator_traits<_InputIterator>::value_type>,
1202 typename _Allocator =
1203 allocator<typename iterator_traits<_InputIterator>::value_type>,
1204 typename = _RequireInputIter<_InputIterator>,
1205 typename = _RequireNotAllocatorOrIntegral<_Hash>,
1206 typename = _RequireNotAllocator<_Pred>,
1207 typename = _RequireAllocator<_Allocator>>
1208 unordered_multiset(_InputIterator, _InputIterator,
1209 unordered_multiset<int>::size_type = {},
1210 _Hash = _Hash(), _Pred = _Pred(),
1211 _Allocator = _Allocator())
1212 -> unordered_multiset<
typename iterator_traits<_InputIterator>::value_type,
1213 _Hash, _Pred, _Allocator>;
1215 template<
typename _Tp,
typename _Hash = hash<_Tp>,
1216 typename _Pred = equal_to<_Tp>,
1217 typename _Allocator = allocator<_Tp>,
1218 typename = _RequireNotAllocatorOrIntegral<_Hash>,
1219 typename = _RequireNotAllocator<_Pred>,
1220 typename = _RequireAllocator<_Allocator>>
1221 unordered_multiset(initializer_list<_Tp>,
1222 unordered_multiset<int>::size_type = {},
1223 _Hash = _Hash(), _Pred = _Pred(),
1224 _Allocator = _Allocator())
1225 -> unordered_multiset<_Tp, _Hash, _Pred, _Allocator>;
1227 template<
typename _InputIterator,
typename _Allocator,
1228 typename = _RequireInputIter<_InputIterator>,
1229 typename = _RequireAllocator<_Allocator>>
1230 unordered_multiset(_InputIterator, _InputIterator,
1231 unordered_multiset<int>::size_type, _Allocator)
1232 -> unordered_multiset<typename iterator_traits<_InputIterator>::value_type,
1234 iterator_traits<_InputIterator>::value_type>,
1236 iterator_traits<_InputIterator>::value_type>,
1239 template<
typename _InputIterator,
typename _Hash,
typename _Allocator,
1240 typename = _RequireInputIter<_InputIterator>,
1241 typename = _RequireNotAllocatorOrIntegral<_Hash>,
1242 typename = _RequireAllocator<_Allocator>>
1243 unordered_multiset(_InputIterator, _InputIterator,
1244 unordered_multiset<int>::size_type,
1246 -> unordered_multiset<
typename
1247 iterator_traits<_InputIterator>::value_type,
1251 iterator_traits<_InputIterator>::value_type>,
1254 template<
typename _Tp,
typename _Allocator,
1255 typename = _RequireAllocator<_Allocator>>
1256 unordered_multiset(initializer_list<_Tp>,
1257 unordered_multiset<int>::size_type, _Allocator)
1258 -> unordered_multiset<_Tp, hash<_Tp>, equal_to<_Tp>, _Allocator>;
1260 template<
typename _Tp,
typename _Hash,
typename _Allocator,
1261 typename = _RequireNotAllocatorOrIntegral<_Hash>,
1262 typename = _RequireAllocator<_Allocator>>
1263 unordered_multiset(initializer_list<_Tp>,
1264 unordered_multiset<int>::size_type, _Hash, _Allocator)
1265 -> unordered_multiset<_Tp, _Hash, equal_to<_Tp>, _Allocator>;
1269 template<
typename _Value,
typename _Hash,
typename _Pred,
typename _Alloc>
1271 swap(unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x,
1272 unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y)
1273 noexcept(noexcept(__x.swap(__y)))
1276 template<
typename _Value,
typename _Hash,
typename _Pred,
typename _Alloc>
1278 operator==(
const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x,
1279 const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y)
1280 {
return __x._M_base() == __y._M_base(); }
1282 #if __cpp_impl_three_way_comparison < 201907L
1283 template<
typename _Value,
typename _Hash,
typename _Pred,
typename _Alloc>
1285 operator!=(
const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x,
1286 const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y)
1287 {
return !(__x == __y); }
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.
constexpr std::remove_reference< _Tp >::type && move(_Tp &&__t) noexcept
Convert a value to an rvalue.
Primary class template hash.
void _M_invalidate_local_if(_Predicate __pred)
A standard container composed of unique keys (containing at most one of each key value) in which the ...
Struct holding two objects of arbitrary type.
One of the comparison functors.
_Tp * begin(valarray< _Tp > &__va)
Return an iterator pointing to the first element of the valarray.
Class std::unordered_set with safety/checking/debug instrumentation.
_Tp * end(valarray< _Tp > &__va)
Return an iterator pointing to one past the last element of the valarray.
_Iterator & base() noexcept
Return the underlying iterator.
#define __glibcxx_check_erase(_Position)
void _M_invalidate_if(_Predicate __pred)
Base class for constructing a safe unordered container type that tracks iterators that reference it...
The standard allocator, as per C++03 [20.4.1].
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 _Iterator __base(_Iterator __it)
Safe class dealing with some allocator dependent operations.
_T2 second
The second member.
#define __glibcxx_check_erase_range(_First, _Last)
#define __glibcxx_check_insert(_Position)
Class std::unordered_multiset with safety/checking/debug instrumentation.
auto_ptr & operator=(auto_ptr &__a)
auto_ptr assignment operator.