1 // Debugging unordered_set/unordered_multiset implementation -*- C++ -*-
3 // Copyright (C) 2003-2020 Free Software Foundation, Inc.
5 // This file is part of the GNU ISO C++ Library. This library is free
6 // software; you can redistribute it and/or modify it under the
7 // terms of the GNU General Public License as published by the
8 // Free Software Foundation; either version 3, or (at your option)
11 // This library is distributed in the hope that it will be useful,
12 // but WITHOUT ANY WARRANTY; without even the implied warranty of
13 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 // GNU General Public License for more details.
16 // Under Section 7 of GPL version 3, you are granted additional
17 // permissions described in the GCC Runtime Library Exception, version
18 // 3.1, as published by the Free Software Foundation.
20 // You should have received a copy of the GNU General Public License and
21 // a copy of the GCC Runtime Library Exception along with this program;
22 // see the files COPYING3 and COPYING.RUNTIME respectively. If not, see
23 // <http://www.gnu.org/licenses/>.
25 /** @file debug/unordered_set
26 * This file is a GNU debug extension to the Standard C++ Library.
29 #ifndef _GLIBCXX_DEBUG_UNORDERED_SET
30 #define _GLIBCXX_DEBUG_UNORDERED_SET 1
32 #pragma GCC system_header
34 #if __cplusplus < 201103L
35 # include <bits/c++0x_warning.h>
37 # include <bits/c++config.h>
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>
42 class unordered_multiset;
43 } } // namespace std::__debug
44 # include <unordered_set>
46 #include <debug/safe_unordered_container.h>
47 #include <debug/safe_container.h>
48 #include <debug/safe_iterator.h>
49 #include <debug/safe_local_iterator.h>
51 namespace std _GLIBCXX_VISIBILITY(default)
55 /// Class std::unordered_set with safety/checking/debug instrumentation.
56 template<typename _Value,
57 typename _Hash = std::hash<_Value>,
58 typename _Pred = std::equal_to<_Value>,
59 typename _Alloc = std::allocator<_Value> >
61 : public __gnu_debug::_Safe_container<
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;
68 typedef __gnu_debug::_Safe_container<
69 unordered_set, _Alloc, __gnu_debug::_Safe_unordered_container> _Safe;
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;
81 // Reference wrapper for base class. See PR libstdc++/90102.
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;
98 typedef __gnu_debug::_Safe_iterator<
99 _Base_iterator, unordered_set> iterator;
100 typedef __gnu_debug::_Safe_iterator<
101 _Base_const_iterator, unordered_set> const_iterator;
102 typedef __gnu_debug::_Safe_local_iterator<
103 _Base_local_iterator, unordered_set> local_iterator;
104 typedef __gnu_debug::_Safe_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>
307 std::pair<iterator, bool>
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)
320 __glibcxx_check_insert(__hint);
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 };
328 std::pair<iterator, bool>
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)
340 __glibcxx_check_insert(__hint);
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 };
347 std::pair<iterator, bool>
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)
359 __glibcxx_check_insert(__hint);
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 };
367 insert(std::initializer_list<value_type> __l)
369 size_type __bucket_count = this->bucket_count();
371 _M_check_rehashed(__bucket_count);
374 template<typename _InputIterator>
376 insert(_InputIterator __first, _InputIterator __last)
378 typename __gnu_debug::_Distance_traits<_InputIterator>::__type __dist;
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)
398 __glibcxx_check_erase(__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)
422 __glibcxx_check_insert(__hint);
423 return { _Base::insert(__hint.base(), std::move(__nh)), this };
430 find(const key_type& __key)
431 { return { _Base::find(__key), this }; }
434 find(const key_type& __key) const
435 { return { _Base::find(__key), this }; }
437 std::pair<iterator, iterator>
438 equal_range(const key_type& __key)
440 auto __res = _Base::equal_range(__key);
441 return { { __res.first, this }, { __res.second, this } };
444 std::pair<const_iterator, const_iterator>
445 equal_range(const key_type& __key) const
447 auto __res = _Base::equal_range(__key);
448 return { { __res.first, this }, { __res.second, this } };
452 erase(const key_type& __key)
455 auto __victim = _Base::find(__key);
456 if (__victim != _Base::end())
465 erase(const_iterator __it)
467 __glibcxx_check_erase(__it);
468 return { _M_erase(__it.base()), this };
474 __glibcxx_check_erase(__it);
475 return { _M_erase(__it.base()), this };
479 erase(const_iterator __first, const_iterator __last)
481 __glibcxx_check_erase_range(__first, __last);
482 for (auto __tmp = __first.base(); __tmp != __last.base(); ++__tmp)
484 _GLIBCXX_DEBUG_VERIFY(__tmp != _Base::cend(),
485 _M_message(__gnu_debug::__msg_valid_range)
486 ._M_iterator(__first, "first")
487 ._M_iterator(__last, "last"));
488 _M_invalidate(__tmp);
491 size_type __bucket_count = this->bucket_count();
492 auto __next = _Base::erase(__first.base(), __last.base());
493 _M_check_rehashed(__bucket_count);
494 return { __next, this };
498 _M_base() noexcept { return *this; }
501 _M_base() const noexcept { return *this; }
505 _M_check_rehashed(size_type __prev_count)
507 if (__prev_count != this->bucket_count())
508 this->_M_invalidate_all();
512 _M_invalidate(_Base_const_iterator __victim)
514 this->_M_invalidate_if(
515 [__victim](_Base_const_iterator __it) { return __it == __victim; });
516 this->_M_invalidate_local_if(
517 [__victim](_Base_const_local_iterator __it)
518 { return __it == __victim; });
522 _M_erase(_Base_const_iterator __victim)
524 _M_invalidate(__victim);
525 size_type __bucket_count = this->bucket_count();
526 _Base_iterator __next = _Base::erase(__victim);
527 _M_check_rehashed(__bucket_count);
531 #if __cplusplus > 201402L
533 _M_extract(_Base_const_iterator __victim)
535 _M_invalidate(__victim);
536 return _Base::extract(__victim);
541 #if __cpp_deduction_guides >= 201606
543 template<typename _InputIterator,
545 hash<typename iterator_traits<_InputIterator>::value_type>,
547 equal_to<typename iterator_traits<_InputIterator>::value_type>,
548 typename _Allocator =
549 allocator<typename iterator_traits<_InputIterator>::value_type>,
550 typename = _RequireInputIter<_InputIterator>,
551 typename = _RequireNotAllocatorOrIntegral<_Hash>,
552 typename = _RequireNotAllocator<_Pred>,
553 typename = _RequireAllocator<_Allocator>>
554 unordered_set(_InputIterator, _InputIterator,
555 unordered_set<int>::size_type = {},
556 _Hash = _Hash(), _Pred = _Pred(), _Allocator = _Allocator())
557 -> unordered_set<typename iterator_traits<_InputIterator>::value_type,
558 _Hash, _Pred, _Allocator>;
560 template<typename _Tp, typename _Hash = hash<_Tp>,
561 typename _Pred = equal_to<_Tp>,
562 typename _Allocator = allocator<_Tp>,
563 typename = _RequireNotAllocatorOrIntegral<_Hash>,
564 typename = _RequireNotAllocator<_Pred>,
565 typename = _RequireAllocator<_Allocator>>
566 unordered_set(initializer_list<_Tp>,
567 unordered_set<int>::size_type = {},
568 _Hash = _Hash(), _Pred = _Pred(), _Allocator = _Allocator())
569 -> unordered_set<_Tp, _Hash, _Pred, _Allocator>;
571 template<typename _InputIterator, typename _Allocator,
572 typename = _RequireInputIter<_InputIterator>,
573 typename = _RequireAllocator<_Allocator>>
574 unordered_set(_InputIterator, _InputIterator,
575 unordered_set<int>::size_type, _Allocator)
576 -> unordered_set<typename iterator_traits<_InputIterator>::value_type,
578 typename iterator_traits<_InputIterator>::value_type>,
580 typename iterator_traits<_InputIterator>::value_type>,
583 template<typename _InputIterator, typename _Hash, typename _Allocator,
584 typename = _RequireInputIter<_InputIterator>,
585 typename = _RequireNotAllocatorOrIntegral<_Hash>,
586 typename = _RequireAllocator<_Allocator>>
587 unordered_set(_InputIterator, _InputIterator,
588 unordered_set<int>::size_type,
590 -> unordered_set<typename iterator_traits<_InputIterator>::value_type,
593 typename iterator_traits<_InputIterator>::value_type>,
596 template<typename _Tp, typename _Allocator,
597 typename = _RequireAllocator<_Allocator>>
598 unordered_set(initializer_list<_Tp>,
599 unordered_set<int>::size_type, _Allocator)
600 -> unordered_set<_Tp, hash<_Tp>, equal_to<_Tp>, _Allocator>;
602 template<typename _Tp, typename _Hash, typename _Allocator,
603 typename = _RequireNotAllocatorOrIntegral<_Hash>,
604 typename = _RequireAllocator<_Allocator>>
605 unordered_set(initializer_list<_Tp>,
606 unordered_set<int>::size_type, _Hash, _Allocator)
607 -> unordered_set<_Tp, _Hash, equal_to<_Tp>, _Allocator>;
611 template<typename _Value, typename _Hash, typename _Pred, typename _Alloc>
613 swap(unordered_set<_Value, _Hash, _Pred, _Alloc>& __x,
614 unordered_set<_Value, _Hash, _Pred, _Alloc>& __y)
615 noexcept(noexcept(__x.swap(__y)))
618 template<typename _Value, typename _Hash, typename _Pred, typename _Alloc>
620 operator==(const unordered_set<_Value, _Hash, _Pred, _Alloc>& __x,
621 const unordered_set<_Value, _Hash, _Pred, _Alloc>& __y)
622 { return __x._M_base() == __y._M_base(); }
624 #if __cpp_impl_three_way_comparison < 201907L
625 template<typename _Value, typename _Hash, typename _Pred, typename _Alloc>
627 operator!=(const unordered_set<_Value, _Hash, _Pred, _Alloc>& __x,
628 const unordered_set<_Value, _Hash, _Pred, _Alloc>& __y)
629 { return !(__x == __y); }
632 /// Class std::unordered_multiset with safety/checking/debug instrumentation.
633 template<typename _Value,
634 typename _Hash = std::hash<_Value>,
635 typename _Pred = std::equal_to<_Value>,
636 typename _Alloc = std::allocator<_Value> >
637 class unordered_multiset
638 : public __gnu_debug::_Safe_container<
639 unordered_multiset<_Value, _Hash, _Pred, _Alloc>, _Alloc,
640 __gnu_debug::_Safe_unordered_container>,
641 public _GLIBCXX_STD_C::unordered_multiset<_Value, _Hash, _Pred, _Alloc>
643 typedef _GLIBCXX_STD_C::unordered_multiset<
644 _Value, _Hash, _Pred, _Alloc> _Base;
645 typedef __gnu_debug::_Safe_container<unordered_multiset,
646 _Alloc, __gnu_debug::_Safe_unordered_container> _Safe;
647 typedef typename _Base::const_iterator _Base_const_iterator;
648 typedef typename _Base::iterator _Base_iterator;
649 typedef typename _Base::const_local_iterator
650 _Base_const_local_iterator;
651 typedef typename _Base::local_iterator _Base_local_iterator;
653 template<typename _ItT, typename _SeqT, typename _CatT>
654 friend class ::__gnu_debug::_Safe_iterator;
655 template<typename _ItT, typename _SeqT>
656 friend class ::__gnu_debug::_Safe_local_iterator;
658 // Reference wrapper for base class. See PR libstdc++/90102.
661 _Base_ref(const _Base& __r) : _M_ref(__r) { }
667 typedef typename _Base::size_type size_type;
668 typedef typename _Base::hasher hasher;
669 typedef typename _Base::key_equal key_equal;
670 typedef typename _Base::allocator_type allocator_type;
672 typedef typename _Base::key_type key_type;
673 typedef typename _Base::value_type value_type;
675 typedef __gnu_debug::_Safe_iterator<
676 _Base_iterator, unordered_multiset> iterator;
677 typedef __gnu_debug::_Safe_iterator<
678 _Base_const_iterator, unordered_multiset> const_iterator;
679 typedef __gnu_debug::_Safe_local_iterator<
680 _Base_local_iterator, unordered_multiset> local_iterator;
681 typedef __gnu_debug::_Safe_local_iterator<
682 _Base_const_local_iterator, unordered_multiset> const_local_iterator;
684 unordered_multiset() = default;
687 unordered_multiset(size_type __n,
688 const hasher& __hf = hasher(),
689 const key_equal& __eql = key_equal(),
690 const allocator_type& __a = allocator_type())
691 : _Base(__n, __hf, __eql, __a) { }
693 template<typename _InputIterator>
694 unordered_multiset(_InputIterator __first, _InputIterator __last,
696 const hasher& __hf = hasher(),
697 const key_equal& __eql = key_equal(),
698 const allocator_type& __a = allocator_type())
699 : _Base(__gnu_debug::__base(
700 __glibcxx_check_valid_constructor_range(__first, __last)),
701 __gnu_debug::__base(__last), __n,
702 __hf, __eql, __a) { }
704 unordered_multiset(const unordered_multiset&) = default;
706 unordered_multiset(_Base_ref __x)
707 : _Base(__x._M_ref) { }
709 unordered_multiset(unordered_multiset&&) = default;
712 unordered_multiset(const allocator_type& __a)
715 unordered_multiset(const unordered_multiset& __uset,
716 const allocator_type& __a)
717 : _Base(__uset, __a) { }
719 unordered_multiset(unordered_multiset&& __uset,
720 const allocator_type& __a)
721 noexcept( noexcept(_Base(std::move(__uset._M_base()), __a)) )
722 : _Safe(std::move(__uset._M_safe()), __a),
723 _Base(std::move(__uset._M_base()), __a) { }
725 unordered_multiset(initializer_list<value_type> __l,
727 const hasher& __hf = hasher(),
728 const key_equal& __eql = key_equal(),
729 const allocator_type& __a = allocator_type())
730 : _Base(__l, __n, __hf, __eql, __a) { }
732 unordered_multiset(size_type __n, const allocator_type& __a)
733 : unordered_multiset(__n, hasher(), key_equal(), __a)
736 unordered_multiset(size_type __n, const hasher& __hf,
737 const allocator_type& __a)
738 : unordered_multiset(__n, __hf, key_equal(), __a)
741 template<typename _InputIterator>
742 unordered_multiset(_InputIterator __first, _InputIterator __last,
744 const allocator_type& __a)
745 : unordered_multiset(__first, __last, __n, hasher(), key_equal(), __a)
748 template<typename _InputIterator>
749 unordered_multiset(_InputIterator __first, _InputIterator __last,
750 size_type __n, const hasher& __hf,
751 const allocator_type& __a)
752 : unordered_multiset(__first, __last, __n, __hf, key_equal(), __a)
755 unordered_multiset(initializer_list<value_type> __l,
757 const allocator_type& __a)
758 : unordered_multiset(__l, __n, hasher(), key_equal(), __a)
761 unordered_multiset(initializer_list<value_type> __l,
762 size_type __n, const hasher& __hf,
763 const allocator_type& __a)
764 : unordered_multiset(__l, __n, __hf, key_equal(), __a)
767 ~unordered_multiset() = default;
770 operator=(const unordered_multiset&) = default;
773 operator=(unordered_multiset&&) = default;
776 operator=(initializer_list<value_type> __l)
778 this->_M_base() = __l;
779 this->_M_invalidate_all();
784 swap(unordered_multiset& __x)
785 noexcept( noexcept(declval<_Base&>().swap(__x)) )
795 this->_M_invalidate_all();
800 { return { _Base::begin(), this }; }
803 begin() const noexcept
804 { return { _Base::begin(), this }; }
808 { return { _Base::end(), this }; }
812 { return { _Base::end(), this }; }
815 cbegin() const noexcept
816 { return { _Base::cbegin(), this }; }
819 cend() const noexcept
820 { return { _Base::cend(), this }; }
826 __glibcxx_check_bucket_index(__b);
827 return { _Base::begin(__b), this };
833 __glibcxx_check_bucket_index(__b);
834 return { _Base::end(__b), this };
838 begin(size_type __b) const
840 __glibcxx_check_bucket_index(__b);
841 return { _Base::begin(__b), this };
845 end(size_type __b) const
847 __glibcxx_check_bucket_index(__b);
848 return { _Base::end(__b), this };
852 cbegin(size_type __b) const
854 __glibcxx_check_bucket_index(__b);
855 return { _Base::cbegin(__b), this };
859 cend(size_type __b) const
861 __glibcxx_check_bucket_index(__b);
862 return { _Base::cend(__b), this };
866 bucket_size(size_type __b) const
868 __glibcxx_check_bucket_index(__b);
869 return _Base::bucket_size(__b);
873 max_load_factor() const noexcept
874 { return _Base::max_load_factor(); }
877 max_load_factor(float __f)
879 __glibcxx_check_max_load_factor(__f);
880 _Base::max_load_factor(__f);
883 template<typename... _Args>
885 emplace(_Args&&... __args)
887 size_type __bucket_count = this->bucket_count();
888 auto __it = _Base::emplace(std::forward<_Args>(__args)...);
889 _M_check_rehashed(__bucket_count);
890 return { __it, this };
893 template<typename... _Args>
895 emplace_hint(const_iterator __hint, _Args&&... __args)
897 __glibcxx_check_insert(__hint);
898 size_type __bucket_count = this->bucket_count();
899 auto __it = _Base::emplace_hint(__hint.base(),
900 std::forward<_Args>(__args)...);
901 _M_check_rehashed(__bucket_count);
902 return { __it, this };
906 insert(const value_type& __obj)
908 size_type __bucket_count = this->bucket_count();
909 auto __it = _Base::insert(__obj);
910 _M_check_rehashed(__bucket_count);
911 return { __it, this };
915 insert(const_iterator __hint, const value_type& __obj)
917 __glibcxx_check_insert(__hint);
918 size_type __bucket_count = this->bucket_count();
919 auto __it = _Base::insert(__hint.base(), __obj);
920 _M_check_rehashed(__bucket_count);
921 return { __it, this };
925 insert(value_type&& __obj)
927 size_type __bucket_count = this->bucket_count();
928 auto __it = _Base::insert(std::move(__obj));
929 _M_check_rehashed(__bucket_count);
930 return { __it, this };
934 insert(const_iterator __hint, value_type&& __obj)
936 __glibcxx_check_insert(__hint);
937 size_type __bucket_count = this->bucket_count();
938 auto __it = _Base::insert(__hint.base(), std::move(__obj));
939 _M_check_rehashed(__bucket_count);
940 return { __it, this };
944 insert(std::initializer_list<value_type> __l)
946 size_type __bucket_count = this->bucket_count();
948 _M_check_rehashed(__bucket_count);
951 template<typename _InputIterator>
953 insert(_InputIterator __first, _InputIterator __last)
955 typename __gnu_debug::_Distance_traits<_InputIterator>::__type __dist;
956 __glibcxx_check_valid_range2(__first, __last, __dist);
957 size_type __bucket_count = this->bucket_count();
959 if (__dist.second >= __gnu_debug::__dp_sign)
960 _Base::insert(__gnu_debug::__unsafe(__first),
961 __gnu_debug::__unsafe(__last));
963 _Base::insert(__first, __last);
965 _M_check_rehashed(__bucket_count);
968 #if __cplusplus > 201402L
969 using node_type = typename _Base::node_type;
972 extract(const_iterator __position)
974 __glibcxx_check_erase(__position);
975 return _M_extract(__position.base());
979 extract(const key_type& __key)
981 const auto __position = _Base::find(__key);
982 if (__position != _Base::end())
983 return _M_extract(__position);
988 insert(node_type&& __nh)
989 { return { _Base::insert(std::move(__nh)), this }; }
992 insert(const_iterator __hint, node_type&& __nh)
994 __glibcxx_check_insert(__hint);
995 return { _Base::insert(__hint.base(), std::move(__nh)), this };
1002 find(const key_type& __key)
1003 { return { _Base::find(__key), this }; }
1006 find(const key_type& __key) const
1007 { return { _Base::find(__key), this }; }
1009 std::pair<iterator, iterator>
1010 equal_range(const key_type& __key)
1012 auto __res = _Base::equal_range(__key);
1013 return { { __res.first, this }, { __res.second, this } };
1016 std::pair<const_iterator, const_iterator>
1017 equal_range(const key_type& __key) const
1019 auto __res = _Base::equal_range(__key);
1020 return { { __res.first, this }, { __res.second, this } };
1024 erase(const key_type& __key)
1027 auto __pair = _Base::equal_range(__key);
1028 for (auto __victim = __pair.first; __victim != __pair.second;)
1030 _M_invalidate(__victim);
1031 __victim = _Base::erase(__victim);
1039 erase(const_iterator __it)
1041 __glibcxx_check_erase(__it);
1042 return { _M_erase(__it.base()), this };
1046 erase(iterator __it)
1048 __glibcxx_check_erase(__it);
1049 return { _M_erase(__it.base()), this };
1053 erase(const_iterator __first, const_iterator __last)
1055 __glibcxx_check_erase_range(__first, __last);
1056 for (auto __tmp = __first.base(); __tmp != __last.base(); ++__tmp)
1058 _GLIBCXX_DEBUG_VERIFY(__tmp != _Base::cend(),
1059 _M_message(__gnu_debug::__msg_valid_range)
1060 ._M_iterator(__first, "first")
1061 ._M_iterator(__last, "last"));
1062 _M_invalidate(__tmp);
1064 return { _Base::erase(__first.base(), __last.base()), this };
1068 _M_base() noexcept { return *this; }
1071 _M_base() const noexcept { return *this; }
1075 _M_check_rehashed(size_type __prev_count)
1077 if (__prev_count != this->bucket_count())
1078 this->_M_invalidate_all();
1082 _M_invalidate(_Base_const_iterator __victim)
1084 this->_M_invalidate_if(
1085 [__victim](_Base_const_iterator __it) { return __it == __victim; });
1086 this->_M_invalidate_local_if(
1087 [__victim](_Base_const_local_iterator __it)
1088 { return __it == __victim; });
1092 _M_erase(_Base_const_iterator __victim)
1094 _M_invalidate(__victim);
1095 size_type __bucket_count = this->bucket_count();
1096 _Base_iterator __next = _Base::erase(__victim);
1097 _M_check_rehashed(__bucket_count);
1101 #if __cplusplus > 201402L
1103 _M_extract(_Base_const_iterator __victim)
1105 _M_invalidate(__victim);
1106 return _Base::extract(__victim);
1111 #if __cpp_deduction_guides >= 201606
1113 template<typename _InputIterator,
1115 hash<typename iterator_traits<_InputIterator>::value_type>,
1117 equal_to<typename iterator_traits<_InputIterator>::value_type>,
1118 typename _Allocator =
1119 allocator<typename iterator_traits<_InputIterator>::value_type>,
1120 typename = _RequireInputIter<_InputIterator>,
1121 typename = _RequireNotAllocatorOrIntegral<_Hash>,
1122 typename = _RequireNotAllocator<_Pred>,
1123 typename = _RequireAllocator<_Allocator>>
1124 unordered_multiset(_InputIterator, _InputIterator,
1125 unordered_multiset<int>::size_type = {},
1126 _Hash = _Hash(), _Pred = _Pred(),
1127 _Allocator = _Allocator())
1128 -> unordered_multiset<typename iterator_traits<_InputIterator>::value_type,
1129 _Hash, _Pred, _Allocator>;
1131 template<typename _Tp, typename _Hash = hash<_Tp>,
1132 typename _Pred = equal_to<_Tp>,
1133 typename _Allocator = allocator<_Tp>,
1134 typename = _RequireNotAllocatorOrIntegral<_Hash>,
1135 typename = _RequireNotAllocator<_Pred>,
1136 typename = _RequireAllocator<_Allocator>>
1137 unordered_multiset(initializer_list<_Tp>,
1138 unordered_multiset<int>::size_type = {},
1139 _Hash = _Hash(), _Pred = _Pred(),
1140 _Allocator = _Allocator())
1141 -> unordered_multiset<_Tp, _Hash, _Pred, _Allocator>;
1143 template<typename _InputIterator, typename _Allocator,
1144 typename = _RequireInputIter<_InputIterator>,
1145 typename = _RequireAllocator<_Allocator>>
1146 unordered_multiset(_InputIterator, _InputIterator,
1147 unordered_multiset<int>::size_type, _Allocator)
1148 -> unordered_multiset<typename iterator_traits<_InputIterator>::value_type,
1150 iterator_traits<_InputIterator>::value_type>,
1152 iterator_traits<_InputIterator>::value_type>,
1155 template<typename _InputIterator, typename _Hash, typename _Allocator,
1156 typename = _RequireInputIter<_InputIterator>,
1157 typename = _RequireNotAllocatorOrIntegral<_Hash>,
1158 typename = _RequireAllocator<_Allocator>>
1159 unordered_multiset(_InputIterator, _InputIterator,
1160 unordered_multiset<int>::size_type,
1162 -> unordered_multiset<typename
1163 iterator_traits<_InputIterator>::value_type,
1167 iterator_traits<_InputIterator>::value_type>,
1170 template<typename _Tp, typename _Allocator,
1171 typename = _RequireAllocator<_Allocator>>
1172 unordered_multiset(initializer_list<_Tp>,
1173 unordered_multiset<int>::size_type, _Allocator)
1174 -> unordered_multiset<_Tp, hash<_Tp>, equal_to<_Tp>, _Allocator>;
1176 template<typename _Tp, typename _Hash, typename _Allocator,
1177 typename = _RequireNotAllocatorOrIntegral<_Hash>,
1178 typename = _RequireAllocator<_Allocator>>
1179 unordered_multiset(initializer_list<_Tp>,
1180 unordered_multiset<int>::size_type, _Hash, _Allocator)
1181 -> unordered_multiset<_Tp, _Hash, equal_to<_Tp>, _Allocator>;
1185 template<typename _Value, typename _Hash, typename _Pred, typename _Alloc>
1187 swap(unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x,
1188 unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y)
1189 noexcept(noexcept(__x.swap(__y)))
1192 template<typename _Value, typename _Hash, typename _Pred, typename _Alloc>
1194 operator==(const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x,
1195 const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y)
1196 { return __x._M_base() == __y._M_base(); }
1198 #if __cpp_impl_three_way_comparison < 201907L
1199 template<typename _Value, typename _Hash, typename _Pred, typename _Alloc>
1201 operator!=(const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x,
1202 const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y)
1203 { return !(__x == __y); }
1206 } // namespace __debug