1// Debugging unordered_set/unordered_multiset implementation -*- C++ -*-
3// Copyright (C) 2003-2019 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>
38namespace 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>
51namespace 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;
82 typedef typename _Base::size_type size_type;
83 typedef typename _Base::hasher hasher;
84 typedef typename _Base::key_equal key_equal;
85 typedef typename _Base::allocator_type allocator_type;
87 typedef typename _Base::key_type key_type;
88 typedef typename _Base::value_type value_type;
90 typedef __gnu_debug::_Safe_iterator<
91 _Base_iterator, unordered_set> iterator;
92 typedef __gnu_debug::_Safe_iterator<
93 _Base_const_iterator, unordered_set> const_iterator;
94 typedef __gnu_debug::_Safe_local_iterator<
95 _Base_local_iterator, unordered_set> local_iterator;
96 typedef __gnu_debug::_Safe_local_iterator<
97 _Base_const_local_iterator, unordered_set> const_local_iterator;
99 unordered_set() = default;
102 unordered_set(size_type __n,
103 const hasher& __hf = hasher(),
104 const key_equal& __eql = key_equal(),
105 const allocator_type& __a = allocator_type())
106 : _Base(__n, __hf, __eql, __a) { }
108 template<typename _InputIterator>
109 unordered_set(_InputIterator __first, _InputIterator __last,
111 const hasher& __hf = hasher(),
112 const key_equal& __eql = key_equal(),
113 const allocator_type& __a = allocator_type())
114 : _Base(__gnu_debug::__base(
115 __glibcxx_check_valid_constructor_range(__first, __last)),
116 __gnu_debug::__base(__last), __n,
117 __hf, __eql, __a) { }
119 unordered_set(const unordered_set&) = default;
121 unordered_set(const _Base& __x)
124 unordered_set(unordered_set&&) = default;
127 unordered_set(const allocator_type& __a)
130 unordered_set(const unordered_set& __uset,
131 const allocator_type& __a)
132 : _Base(__uset, __a) { }
134 unordered_set(unordered_set&& __uset,
135 const allocator_type& __a)
136 noexcept( noexcept(_Base(std::move(__uset._M_base()), __a)) )
137 : _Safe(std::move(__uset._M_safe()), __a),
138 _Base(std::move(__uset._M_base()), __a) { }
140 unordered_set(initializer_list<value_type> __l,
142 const hasher& __hf = hasher(),
143 const key_equal& __eql = key_equal(),
144 const allocator_type& __a = allocator_type())
145 : _Base(__l, __n, __hf, __eql, __a) { }
147 unordered_set(size_type __n, const allocator_type& __a)
148 : unordered_set(__n, hasher(), key_equal(), __a)
151 unordered_set(size_type __n, const hasher& __hf,
152 const allocator_type& __a)
153 : unordered_set(__n, __hf, key_equal(), __a)
156 template<typename _InputIterator>
157 unordered_set(_InputIterator __first, _InputIterator __last,
159 const allocator_type& __a)
160 : unordered_set(__first, __last, __n, hasher(), key_equal(), __a)
163 template<typename _InputIterator>
164 unordered_set(_InputIterator __first, _InputIterator __last,
165 size_type __n, const hasher& __hf,
166 const allocator_type& __a)
167 : unordered_set(__first, __last, __n, __hf, key_equal(), __a)
170 unordered_set(initializer_list<value_type> __l,
172 const allocator_type& __a)
173 : unordered_set(__l, __n, hasher(), key_equal(), __a)
176 unordered_set(initializer_list<value_type> __l,
177 size_type __n, const hasher& __hf,
178 const allocator_type& __a)
179 : unordered_set(__l, __n, __hf, key_equal(), __a)
182 ~unordered_set() = default;
185 operator=(const unordered_set&) = default;
188 operator=(unordered_set&&) = default;
191 operator=(initializer_list<value_type> __l)
194 this->_M_invalidate_all();
199 swap(unordered_set& __x)
200 noexcept( noexcept(declval<_Base&>().swap(__x)) )
210 this->_M_invalidate_all();
215 { return { _Base::begin(), this }; }
218 begin() const noexcept
219 { return { _Base::begin(), this }; }
223 { return { _Base::end(), this }; }
227 { return { _Base::end(), this }; }
230 cbegin() const noexcept
231 { return { _Base::cbegin(), this }; }
234 cend() const noexcept
235 { return { _Base::cend(), this }; }
241 __glibcxx_check_bucket_index(__b);
242 return { _Base::begin(__b), this };
248 __glibcxx_check_bucket_index(__b);
249 return { _Base::end(__b), this };
253 begin(size_type __b) const
255 __glibcxx_check_bucket_index(__b);
256 return { _Base::begin(__b), this };
260 end(size_type __b) const
262 __glibcxx_check_bucket_index(__b);
263 return { _Base::end(__b), this };
267 cbegin(size_type __b) const
269 __glibcxx_check_bucket_index(__b);
270 return { _Base::cbegin(__b), this };
274 cend(size_type __b) const
276 __glibcxx_check_bucket_index(__b);
277 return { _Base::cend(__b), this };
281 bucket_size(size_type __b) const
283 __glibcxx_check_bucket_index(__b);
284 return _Base::bucket_size(__b);
288 max_load_factor() const noexcept
289 { return _Base::max_load_factor(); }
292 max_load_factor(float __f)
294 __glibcxx_check_max_load_factor(__f);
295 _Base::max_load_factor(__f);
298 template<typename... _Args>
299 std::pair<iterator, bool>
300 emplace(_Args&&... __args)
302 size_type __bucket_count = this->bucket_count();
303 auto __res = _Base::emplace(std::forward<_Args>(__args)...);
304 _M_check_rehashed(__bucket_count);
305 return { { __res.first, this }, __res.second };
308 template<typename... _Args>
310 emplace_hint(const_iterator __hint, _Args&&... __args)
312 __glibcxx_check_insert(__hint);
313 size_type __bucket_count = this->bucket_count();
314 auto __it = _Base::emplace_hint(__hint.base(),
315 std::forward<_Args>(__args)...);
316 _M_check_rehashed(__bucket_count);
317 return { __it, this };
320 std::pair<iterator, bool>
321 insert(const value_type& __obj)
323 size_type __bucket_count = this->bucket_count();
324 auto __res = _Base::insert(__obj);
325 _M_check_rehashed(__bucket_count);
326 return { { __res.first, this }, __res.second };
330 insert(const_iterator __hint, const value_type& __obj)
332 __glibcxx_check_insert(__hint);
333 size_type __bucket_count = this->bucket_count();
334 auto __it = _Base::insert(__hint.base(), __obj);
335 _M_check_rehashed(__bucket_count);
336 return { __it, this };
339 std::pair<iterator, bool>
340 insert(value_type&& __obj)
342 size_type __bucket_count = this->bucket_count();
343 auto __res = _Base::insert(std::move(__obj));
344 _M_check_rehashed(__bucket_count);
345 return { { __res.first, this }, __res.second };
349 insert(const_iterator __hint, value_type&& __obj)
351 __glibcxx_check_insert(__hint);
352 size_type __bucket_count = this->bucket_count();
353 auto __it = _Base::insert(__hint.base(), std::move(__obj));
354 _M_check_rehashed(__bucket_count);
355 return { __it, this };
359 insert(std::initializer_list<value_type> __l)
361 size_type __bucket_count = this->bucket_count();
363 _M_check_rehashed(__bucket_count);
366 template<typename _InputIterator>
368 insert(_InputIterator __first, _InputIterator __last)
370 typename __gnu_debug::_Distance_traits<_InputIterator>::__type __dist;
371 __glibcxx_check_valid_range2(__first, __last, __dist);
372 size_type __bucket_count = this->bucket_count();
374 if (__dist.second >= __gnu_debug::__dp_sign)
375 _Base::insert(__gnu_debug::__unsafe(__first),
376 __gnu_debug::__unsafe(__last));
378 _Base::insert(__first, __last);
380 _M_check_rehashed(__bucket_count);
383#if __cplusplus > 201402L
384 using node_type = typename _Base::node_type;
385 using insert_return_type = _Node_insert_return<iterator, node_type>;
388 extract(const_iterator __position)
390 __glibcxx_check_erase(__position);
391 return _M_extract(__position.base());
395 extract(const key_type& __key)
397 const auto __position = _Base::find(__key);
398 if (__position != _Base::end())
399 return _M_extract(__position);
404 insert(node_type&& __nh)
406 auto __ret = _Base::insert(std::move(__nh));
408 { { __ret.position, this }, __ret.inserted, std::move(__ret.node) };
412 insert(const_iterator __hint, node_type&& __nh)
414 __glibcxx_check_insert(__hint);
415 return { _Base::insert(__hint.base(), std::move(__nh)), this };
422 find(const key_type& __key)
423 { return { _Base::find(__key), this }; }
426 find(const key_type& __key) const
427 { return { _Base::find(__key), this }; }
429 std::pair<iterator, iterator>
430 equal_range(const key_type& __key)
432 auto __res = _Base::equal_range(__key);
433 return { { __res.first, this }, { __res.second, this } };
436 std::pair<const_iterator, const_iterator>
437 equal_range(const key_type& __key) const
439 auto __res = _Base::equal_range(__key);
440 return { { __res.first, this }, { __res.second, this } };
444 erase(const key_type& __key)
447 auto __victim = _Base::find(__key);
448 if (__victim != _Base::end())
457 erase(const_iterator __it)
459 __glibcxx_check_erase(__it);
460 return { _M_erase(__it.base()), this };
466 __glibcxx_check_erase(__it);
467 return { _M_erase(__it.base()), this };
471 erase(const_iterator __first, const_iterator __last)
473 __glibcxx_check_erase_range(__first, __last);
474 for (auto __tmp = __first.base(); __tmp != __last.base(); ++__tmp)
476 _GLIBCXX_DEBUG_VERIFY(__tmp != _Base::cend(),
477 _M_message(__gnu_debug::__msg_valid_range)
478 ._M_iterator(__first, "first")
479 ._M_iterator(__last, "last"));
480 _M_invalidate(__tmp);
483 size_type __bucket_count = this->bucket_count();
484 auto __next = _Base::erase(__first.base(), __last.base());
485 _M_check_rehashed(__bucket_count);
486 return { __next, this };
490 _M_base() noexcept { return *this; }
493 _M_base() const noexcept { return *this; }
497 _M_check_rehashed(size_type __prev_count)
499 if (__prev_count != this->bucket_count())
500 this->_M_invalidate_all();
504 _M_invalidate(_Base_const_iterator __victim)
506 this->_M_invalidate_if(
507 [__victim](_Base_const_iterator __it) { return __it == __victim; });
508 this->_M_invalidate_local_if(
509 [__victim](_Base_const_local_iterator __it)
510 { return __it._M_curr() == __victim._M_cur; });
514 _M_erase(_Base_const_iterator __victim)
516 _M_invalidate(__victim);
517 size_type __bucket_count = this->bucket_count();
518 _Base_iterator __next = _Base::erase(__victim);
519 _M_check_rehashed(__bucket_count);
523#if __cplusplus > 201402L
525 _M_extract(_Base_const_iterator __victim)
527 _M_invalidate(__victim);
528 return _Base::extract(__victim);
533#if __cpp_deduction_guides >= 201606
535 template<typename _InputIterator,
537 hash<typename iterator_traits<_InputIterator>::value_type>,
539 equal_to<typename iterator_traits<_InputIterator>::value_type>,
540 typename _Allocator =
541 allocator<typename iterator_traits<_InputIterator>::value_type>,
542 typename = _RequireInputIter<_InputIterator>,
543 typename = _RequireNotAllocatorOrIntegral<_Hash>,
544 typename = _RequireNotAllocator<_Pred>,
545 typename = _RequireAllocator<_Allocator>>
546 unordered_set(_InputIterator, _InputIterator,
547 unordered_set<int>::size_type = {},
548 _Hash = _Hash(), _Pred = _Pred(), _Allocator = _Allocator())
549 -> unordered_set<typename iterator_traits<_InputIterator>::value_type,
550 _Hash, _Pred, _Allocator>;
552 template<typename _Tp, typename _Hash = hash<_Tp>,
553 typename _Pred = equal_to<_Tp>,
554 typename _Allocator = allocator<_Tp>,
555 typename = _RequireNotAllocatorOrIntegral<_Hash>,
556 typename = _RequireNotAllocator<_Pred>,
557 typename = _RequireAllocator<_Allocator>>
558 unordered_set(initializer_list<_Tp>,
559 unordered_set<int>::size_type = {},
560 _Hash = _Hash(), _Pred = _Pred(), _Allocator = _Allocator())
561 -> unordered_set<_Tp, _Hash, _Pred, _Allocator>;
563 template<typename _InputIterator, typename _Allocator,
564 typename = _RequireInputIter<_InputIterator>,
565 typename = _RequireAllocator<_Allocator>>
566 unordered_set(_InputIterator, _InputIterator,
567 unordered_set<int>::size_type, _Allocator)
568 -> unordered_set<typename iterator_traits<_InputIterator>::value_type,
570 typename iterator_traits<_InputIterator>::value_type>,
572 typename iterator_traits<_InputIterator>::value_type>,
575 template<typename _InputIterator, typename _Hash, typename _Allocator,
576 typename = _RequireInputIter<_InputIterator>,
577 typename = _RequireNotAllocatorOrIntegral<_Hash>,
578 typename = _RequireAllocator<_Allocator>>
579 unordered_set(_InputIterator, _InputIterator,
580 unordered_set<int>::size_type,
582 -> unordered_set<typename iterator_traits<_InputIterator>::value_type,
585 typename iterator_traits<_InputIterator>::value_type>,
588 template<typename _Tp, typename _Allocator,
589 typename = _RequireAllocator<_Allocator>>
590 unordered_set(initializer_list<_Tp>,
591 unordered_set<int>::size_type, _Allocator)
592 -> unordered_set<_Tp, hash<_Tp>, equal_to<_Tp>, _Allocator>;
594 template<typename _Tp, typename _Hash, typename _Allocator,
595 typename = _RequireNotAllocatorOrIntegral<_Hash>,
596 typename = _RequireAllocator<_Allocator>>
597 unordered_set(initializer_list<_Tp>,
598 unordered_set<int>::size_type, _Hash, _Allocator)
599 -> unordered_set<_Tp, _Hash, equal_to<_Tp>, _Allocator>;
603 template<typename _Value, typename _Hash, typename _Pred, typename _Alloc>
605 swap(unordered_set<_Value, _Hash, _Pred, _Alloc>& __x,
606 unordered_set<_Value, _Hash, _Pred, _Alloc>& __y)
607 noexcept(noexcept(__x.swap(__y)))
610 template<typename _Value, typename _Hash, typename _Pred, typename _Alloc>
612 operator==(const unordered_set<_Value, _Hash, _Pred, _Alloc>& __x,
613 const unordered_set<_Value, _Hash, _Pred, _Alloc>& __y)
614 { return __x._M_base() == __y._M_base(); }
616 template<typename _Value, typename _Hash, typename _Pred, typename _Alloc>
618 operator!=(const unordered_set<_Value, _Hash, _Pred, _Alloc>& __x,
619 const unordered_set<_Value, _Hash, _Pred, _Alloc>& __y)
620 { return !(__x == __y); }
623 /// Class std::unordered_multiset with safety/checking/debug instrumentation.
624 template<typename _Value,
625 typename _Hash = std::hash<_Value>,
626 typename _Pred = std::equal_to<_Value>,
627 typename _Alloc = std::allocator<_Value> >
628 class unordered_multiset
629 : public __gnu_debug::_Safe_container<
630 unordered_multiset<_Value, _Hash, _Pred, _Alloc>, _Alloc,
631 __gnu_debug::_Safe_unordered_container>,
632 public _GLIBCXX_STD_C::unordered_multiset<_Value, _Hash, _Pred, _Alloc>
634 typedef _GLIBCXX_STD_C::unordered_multiset<
635 _Value, _Hash, _Pred, _Alloc> _Base;
636 typedef __gnu_debug::_Safe_container<unordered_multiset,
637 _Alloc, __gnu_debug::_Safe_unordered_container> _Safe;
638 typedef typename _Base::const_iterator _Base_const_iterator;
639 typedef typename _Base::iterator _Base_iterator;
640 typedef typename _Base::const_local_iterator
641 _Base_const_local_iterator;
642 typedef typename _Base::local_iterator _Base_local_iterator;
644 template<typename _ItT, typename _SeqT, typename _CatT>
645 friend class ::__gnu_debug::_Safe_iterator;
646 template<typename _ItT, typename _SeqT>
647 friend class ::__gnu_debug::_Safe_local_iterator;
650 typedef typename _Base::size_type size_type;
651 typedef typename _Base::hasher hasher;
652 typedef typename _Base::key_equal key_equal;
653 typedef typename _Base::allocator_type allocator_type;
655 typedef typename _Base::key_type key_type;
656 typedef typename _Base::value_type value_type;
658 typedef __gnu_debug::_Safe_iterator<
659 _Base_iterator, unordered_multiset> iterator;
660 typedef __gnu_debug::_Safe_iterator<
661 _Base_const_iterator, unordered_multiset> const_iterator;
662 typedef __gnu_debug::_Safe_local_iterator<
663 _Base_local_iterator, unordered_multiset> local_iterator;
664 typedef __gnu_debug::_Safe_local_iterator<
665 _Base_const_local_iterator, unordered_multiset> const_local_iterator;
667 unordered_multiset() = default;
670 unordered_multiset(size_type __n,
671 const hasher& __hf = hasher(),
672 const key_equal& __eql = key_equal(),
673 const allocator_type& __a = allocator_type())
674 : _Base(__n, __hf, __eql, __a) { }
676 template<typename _InputIterator>
677 unordered_multiset(_InputIterator __first, _InputIterator __last,
679 const hasher& __hf = hasher(),
680 const key_equal& __eql = key_equal(),
681 const allocator_type& __a = allocator_type())
682 : _Base(__gnu_debug::__base(
683 __glibcxx_check_valid_constructor_range(__first, __last)),
684 __gnu_debug::__base(__last), __n,
685 __hf, __eql, __a) { }
687 unordered_multiset(const unordered_multiset&) = default;
689 unordered_multiset(const _Base& __x)
692 unordered_multiset(unordered_multiset&&) = default;
695 unordered_multiset(const allocator_type& __a)
698 unordered_multiset(const unordered_multiset& __uset,
699 const allocator_type& __a)
700 : _Base(__uset, __a) { }
702 unordered_multiset(unordered_multiset&& __uset,
703 const allocator_type& __a)
704 noexcept( noexcept(_Base(std::move(__uset._M_base()), __a)) )
705 : _Safe(std::move(__uset._M_safe()), __a),
706 _Base(std::move(__uset._M_base()), __a) { }
708 unordered_multiset(initializer_list<value_type> __l,
710 const hasher& __hf = hasher(),
711 const key_equal& __eql = key_equal(),
712 const allocator_type& __a = allocator_type())
713 : _Base(__l, __n, __hf, __eql, __a) { }
715 unordered_multiset(size_type __n, const allocator_type& __a)
716 : unordered_multiset(__n, hasher(), key_equal(), __a)
719 unordered_multiset(size_type __n, const hasher& __hf,
720 const allocator_type& __a)
721 : unordered_multiset(__n, __hf, key_equal(), __a)
724 template<typename _InputIterator>
725 unordered_multiset(_InputIterator __first, _InputIterator __last,
727 const allocator_type& __a)
728 : unordered_multiset(__first, __last, __n, hasher(), key_equal(), __a)
731 template<typename _InputIterator>
732 unordered_multiset(_InputIterator __first, _InputIterator __last,
733 size_type __n, const hasher& __hf,
734 const allocator_type& __a)
735 : unordered_multiset(__first, __last, __n, __hf, key_equal(), __a)
738 unordered_multiset(initializer_list<value_type> __l,
740 const allocator_type& __a)
741 : unordered_multiset(__l, __n, hasher(), key_equal(), __a)
744 unordered_multiset(initializer_list<value_type> __l,
745 size_type __n, const hasher& __hf,
746 const allocator_type& __a)
747 : unordered_multiset(__l, __n, __hf, key_equal(), __a)
750 ~unordered_multiset() = default;
753 operator=(const unordered_multiset&) = default;
756 operator=(unordered_multiset&&) = default;
759 operator=(initializer_list<value_type> __l)
761 this->_M_base() = __l;
762 this->_M_invalidate_all();
767 swap(unordered_multiset& __x)
768 noexcept( noexcept(declval<_Base&>().swap(__x)) )
778 this->_M_invalidate_all();
783 { return { _Base::begin(), this }; }
786 begin() const noexcept
787 { return { _Base::begin(), this }; }
791 { return { _Base::end(), this }; }
795 { return { _Base::end(), this }; }
798 cbegin() const noexcept
799 { return { _Base::cbegin(), this }; }
802 cend() const noexcept
803 { return { _Base::cend(), this }; }
809 __glibcxx_check_bucket_index(__b);
810 return { _Base::begin(__b), this };
816 __glibcxx_check_bucket_index(__b);
817 return { _Base::end(__b), this };
821 begin(size_type __b) const
823 __glibcxx_check_bucket_index(__b);
824 return { _Base::begin(__b), this };
828 end(size_type __b) const
830 __glibcxx_check_bucket_index(__b);
831 return { _Base::end(__b), this };
835 cbegin(size_type __b) const
837 __glibcxx_check_bucket_index(__b);
838 return { _Base::cbegin(__b), this };
842 cend(size_type __b) const
844 __glibcxx_check_bucket_index(__b);
845 return { _Base::cend(__b), this };
849 bucket_size(size_type __b) const
851 __glibcxx_check_bucket_index(__b);
852 return _Base::bucket_size(__b);
856 max_load_factor() const noexcept
857 { return _Base::max_load_factor(); }
860 max_load_factor(float __f)
862 __glibcxx_check_max_load_factor(__f);
863 _Base::max_load_factor(__f);
866 template<typename... _Args>
868 emplace(_Args&&... __args)
870 size_type __bucket_count = this->bucket_count();
871 auto __it = _Base::emplace(std::forward<_Args>(__args)...);
872 _M_check_rehashed(__bucket_count);
873 return { __it, this };
876 template<typename... _Args>
878 emplace_hint(const_iterator __hint, _Args&&... __args)
880 __glibcxx_check_insert(__hint);
881 size_type __bucket_count = this->bucket_count();
882 auto __it = _Base::emplace_hint(__hint.base(),
883 std::forward<_Args>(__args)...);
884 _M_check_rehashed(__bucket_count);
885 return { __it, this };
889 insert(const value_type& __obj)
891 size_type __bucket_count = this->bucket_count();
892 auto __it = _Base::insert(__obj);
893 _M_check_rehashed(__bucket_count);
894 return { __it, this };
898 insert(const_iterator __hint, const value_type& __obj)
900 __glibcxx_check_insert(__hint);
901 size_type __bucket_count = this->bucket_count();
902 auto __it = _Base::insert(__hint.base(), __obj);
903 _M_check_rehashed(__bucket_count);
904 return { __it, this };
908 insert(value_type&& __obj)
910 size_type __bucket_count = this->bucket_count();
911 auto __it = _Base::insert(std::move(__obj));
912 _M_check_rehashed(__bucket_count);
913 return { __it, this };
917 insert(const_iterator __hint, value_type&& __obj)
919 __glibcxx_check_insert(__hint);
920 size_type __bucket_count = this->bucket_count();
921 auto __it = _Base::insert(__hint.base(), std::move(__obj));
922 _M_check_rehashed(__bucket_count);
923 return { __it, this };
927 insert(std::initializer_list<value_type> __l)
929 size_type __bucket_count = this->bucket_count();
931 _M_check_rehashed(__bucket_count);
934 template<typename _InputIterator>
936 insert(_InputIterator __first, _InputIterator __last)
938 typename __gnu_debug::_Distance_traits<_InputIterator>::__type __dist;
939 __glibcxx_check_valid_range2(__first, __last, __dist);
940 size_type __bucket_count = this->bucket_count();
942 if (__dist.second >= __gnu_debug::__dp_sign)
943 _Base::insert(__gnu_debug::__unsafe(__first),
944 __gnu_debug::__unsafe(__last));
946 _Base::insert(__first, __last);
948 _M_check_rehashed(__bucket_count);
951#if __cplusplus > 201402L
952 using node_type = typename _Base::node_type;
955 extract(const_iterator __position)
957 __glibcxx_check_erase(__position);
958 return _M_extract(__position.base());
962 extract(const key_type& __key)
964 const auto __position = _Base::find(__key);
965 if (__position != _Base::end())
966 return _M_extract(__position);
971 insert(node_type&& __nh)
972 { return { _Base::insert(std::move(__nh)), this }; }
975 insert(const_iterator __hint, node_type&& __nh)
977 __glibcxx_check_insert(__hint);
978 return { _Base::insert(__hint.base(), std::move(__nh)), this };
985 find(const key_type& __key)
986 { return { _Base::find(__key), this }; }
989 find(const key_type& __key) const
990 { return { _Base::find(__key), this }; }
992 std::pair<iterator, iterator>
993 equal_range(const key_type& __key)
995 auto __res = _Base::equal_range(__key);
996 return { { __res.first, this }, { __res.second, this } };
999 std::pair<const_iterator, const_iterator>
1000 equal_range(const key_type& __key) const
1002 auto __res = _Base::equal_range(__key);
1003 return { { __res.first, this }, { __res.second, this } };
1007 erase(const key_type& __key)
1010 auto __pair = _Base::equal_range(__key);
1011 for (auto __victim = __pair.first; __victim != __pair.second;)
1013 _M_invalidate(__victim);
1014 __victim = _Base::erase(__victim);
1022 erase(const_iterator __it)
1024 __glibcxx_check_erase(__it);
1025 return { _M_erase(__it.base()), this };
1029 erase(iterator __it)
1031 __glibcxx_check_erase(__it);
1032 return { _M_erase(__it.base()), this };
1036 erase(const_iterator __first, const_iterator __last)
1038 __glibcxx_check_erase_range(__first, __last);
1039 for (auto __tmp = __first.base(); __tmp != __last.base(); ++__tmp)
1041 _GLIBCXX_DEBUG_VERIFY(__tmp != _Base::cend(),
1042 _M_message(__gnu_debug::__msg_valid_range)
1043 ._M_iterator(__first, "first")
1044 ._M_iterator(__last, "last"));
1045 _M_invalidate(__tmp);
1047 return { _Base::erase(__first.base(), __last.base()), this };
1051 _M_base() noexcept { return *this; }
1054 _M_base() const noexcept { return *this; }
1058 _M_check_rehashed(size_type __prev_count)
1060 if (__prev_count != this->bucket_count())
1061 this->_M_invalidate_all();
1065 _M_invalidate(_Base_const_iterator __victim)
1067 this->_M_invalidate_if(
1068 [__victim](_Base_const_iterator __it) { return __it == __victim; });
1069 this->_M_invalidate_local_if(
1070 [__victim](_Base_const_local_iterator __it)
1071 { return __it._M_curr() == __victim._M_cur; });
1075 _M_erase(_Base_const_iterator __victim)
1077 _M_invalidate(__victim);
1078 size_type __bucket_count = this->bucket_count();
1079 _Base_iterator __next = _Base::erase(__victim);
1080 _M_check_rehashed(__bucket_count);
1084#if __cplusplus > 201402L
1086 _M_extract(_Base_const_iterator __victim)
1088 _M_invalidate(__victim);
1089 return _Base::extract(__victim);
1094#if __cpp_deduction_guides >= 201606
1096 template<typename _InputIterator,
1098 hash<typename iterator_traits<_InputIterator>::value_type>,
1100 equal_to<typename iterator_traits<_InputIterator>::value_type>,
1101 typename _Allocator =
1102 allocator<typename iterator_traits<_InputIterator>::value_type>,
1103 typename = _RequireInputIter<_InputIterator>,
1104 typename = _RequireNotAllocatorOrIntegral<_Hash>,
1105 typename = _RequireNotAllocator<_Pred>,
1106 typename = _RequireAllocator<_Allocator>>
1107 unordered_multiset(_InputIterator, _InputIterator,
1108 unordered_multiset<int>::size_type = {},
1109 _Hash = _Hash(), _Pred = _Pred(),
1110 _Allocator = _Allocator())
1111 -> unordered_multiset<typename iterator_traits<_InputIterator>::value_type,
1112 _Hash, _Pred, _Allocator>;
1114 template<typename _Tp, typename _Hash = hash<_Tp>,
1115 typename _Pred = equal_to<_Tp>,
1116 typename _Allocator = allocator<_Tp>,
1117 typename = _RequireNotAllocatorOrIntegral<_Hash>,
1118 typename = _RequireNotAllocator<_Pred>,
1119 typename = _RequireAllocator<_Allocator>>
1120 unordered_multiset(initializer_list<_Tp>,
1121 unordered_multiset<int>::size_type = {},
1122 _Hash = _Hash(), _Pred = _Pred(),
1123 _Allocator = _Allocator())
1124 -> unordered_multiset<_Tp, _Hash, _Pred, _Allocator>;
1126 template<typename _InputIterator, typename _Allocator,
1127 typename = _RequireInputIter<_InputIterator>,
1128 typename = _RequireAllocator<_Allocator>>
1129 unordered_multiset(_InputIterator, _InputIterator,
1130 unordered_multiset<int>::size_type, _Allocator)
1131 -> unordered_multiset<typename iterator_traits<_InputIterator>::value_type,
1133 iterator_traits<_InputIterator>::value_type>,
1135 iterator_traits<_InputIterator>::value_type>,
1138 template<typename _InputIterator, typename _Hash, typename _Allocator,
1139 typename = _RequireInputIter<_InputIterator>,
1140 typename = _RequireNotAllocatorOrIntegral<_Hash>,
1141 typename = _RequireAllocator<_Allocator>>
1142 unordered_multiset(_InputIterator, _InputIterator,
1143 unordered_multiset<int>::size_type,
1145 -> unordered_multiset<typename
1146 iterator_traits<_InputIterator>::value_type,
1150 iterator_traits<_InputIterator>::value_type>,
1153 template<typename _Tp, typename _Allocator,
1154 typename = _RequireAllocator<_Allocator>>
1155 unordered_multiset(initializer_list<_Tp>,
1156 unordered_multiset<int>::size_type, _Allocator)
1157 -> unordered_multiset<_Tp, hash<_Tp>, equal_to<_Tp>, _Allocator>;
1159 template<typename _Tp, typename _Hash, typename _Allocator,
1160 typename = _RequireNotAllocatorOrIntegral<_Hash>,
1161 typename = _RequireAllocator<_Allocator>>
1162 unordered_multiset(initializer_list<_Tp>,
1163 unordered_multiset<int>::size_type, _Hash, _Allocator)
1164 -> unordered_multiset<_Tp, _Hash, equal_to<_Tp>, _Allocator>;
1168 template<typename _Value, typename _Hash, typename _Pred, typename _Alloc>
1170 swap(unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x,
1171 unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y)
1172 noexcept(noexcept(__x.swap(__y)))
1175 template<typename _Value, typename _Hash, typename _Pred, typename _Alloc>
1177 operator==(const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x,
1178 const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y)
1179 { return __x._M_base() == __y._M_base(); }
1181 template<typename _Value, typename _Hash, typename _Pred, typename _Alloc>
1183 operator!=(const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x,
1184 const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y)
1185 { return !(__x == __y); }
1187} // namespace __debug