libstdc++
debug/unordered_set
Go to the documentation of this file.
1// Debugging unordered_set/unordered_multiset implementation -*- C++ -*-
2
3// Copyright (C) 2003-2020 Free Software Foundation, Inc.
4//
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)
9// any later version.
10
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.
15
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.
19
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/>.
24
25/** @file debug/unordered_set
26 * This file is a GNU debug extension to the Standard C++ Library.
27 */
28
29#ifndef _GLIBCXX_DEBUG_UNORDERED_SET
30#define _GLIBCXX_DEBUG_UNORDERED_SET 1
31
32#pragma GCC system_header
33
34#if __cplusplus < 201103L
35# include <bits/c++0x_warning.h>
36#else
37# include <bits/c++config.h>
38namespace std _GLIBCXX_VISIBILITY(default) { namespace __debug {
39 template<typename _Key, typename _Hash, typename _Pred, typename _Allocator>
40 class unordered_set;
41 template<typename _Key, typename _Hash, typename _Pred, typename _Allocator>
42 class unordered_multiset;
43} } // namespace std::__debug
44# include <unordered_set>
45
48#include <debug/safe_iterator.h>
50
51namespace std _GLIBCXX_VISIBILITY(default)
52{
53namespace __debug
54{
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> >
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>
65 {
66 typedef _GLIBCXX_STD_C::unordered_set<
67 _Value, _Hash, _Pred, _Alloc> _Base;
70
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;
75
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;
80
81 public:
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;
86
87 typedef typename _Base::key_type key_type;
88 typedef typename _Base::value_type value_type;
89
91 _Base_iterator, unordered_set> iterator;
93 _Base_const_iterator, unordered_set> const_iterator;
95 _Base_local_iterator, unordered_set> local_iterator;
97 _Base_const_local_iterator, unordered_set> const_local_iterator;
98
99 unordered_set() = default;
100
101 explicit
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) { }
107
108 template<typename _InputIterator>
109 unordered_set(_InputIterator __first, _InputIterator __last,
110 size_type __n = 0,
111 const hasher& __hf = hasher(),
112 const key_equal& __eql = key_equal(),
113 const allocator_type& __a = allocator_type())
115 __glibcxx_check_valid_constructor_range(__first, __last)),
116 __gnu_debug::__base(__last), __n,
117 __hf, __eql, __a) { }
118
119 unordered_set(const unordered_set&) = default;
120
121 unordered_set(const _Base& __x)
122 : _Base(__x) { }
123
124 unordered_set(unordered_set&&) = default;
125
126 explicit
127 unordered_set(const allocator_type& __a)
128 : _Base(__a) { }
129
130 unordered_set(const unordered_set& __uset,
131 const allocator_type& __a)
132 : _Base(__uset, __a) { }
133
135 const allocator_type& __a)
136 : _Safe(std::move(__uset._M_safe()), __a),
137 _Base(std::move(__uset._M_base()), __a) { }
138
140 size_type __n = 0,
141 const hasher& __hf = hasher(),
142 const key_equal& __eql = key_equal(),
143 const allocator_type& __a = allocator_type())
144 : _Base(__l, __n, __hf, __eql, __a) { }
145
146 unordered_set(size_type __n, const allocator_type& __a)
147 : unordered_set(__n, hasher(), key_equal(), __a)
148 { }
149
150 unordered_set(size_type __n, const hasher& __hf,
151 const allocator_type& __a)
152 : unordered_set(__n, __hf, key_equal(), __a)
153 { }
154
155 template<typename _InputIterator>
156 unordered_set(_InputIterator __first, _InputIterator __last,
157 size_type __n,
158 const allocator_type& __a)
159 : unordered_set(__first, __last, __n, hasher(), key_equal(), __a)
160 { }
161
162 template<typename _InputIterator>
163 unordered_set(_InputIterator __first, _InputIterator __last,
164 size_type __n, const hasher& __hf,
165 const allocator_type& __a)
166 : unordered_set(__first, __last, __n, __hf, key_equal(), __a)
167 { }
168
170 size_type __n,
171 const allocator_type& __a)
172 : unordered_set(__l, __n, hasher(), key_equal(), __a)
173 { }
174
176 size_type __n, const hasher& __hf,
177 const allocator_type& __a)
178 : unordered_set(__l, __n, __hf, key_equal(), __a)
179 { }
180
181 ~unordered_set() = default;
182
184 operator=(const unordered_set&) = default;
185
187 operator=(unordered_set&&) = default;
188
190 operator=(initializer_list<value_type> __l)
191 {
192 _M_base() = __l;
193 this->_M_invalidate_all();
194 return *this;
195 }
196
197 void
198 swap(unordered_set& __x)
199 noexcept( noexcept(declval<_Base&>().swap(__x)) )
200 {
201 _Safe::_M_swap(__x);
202 _Base::swap(__x);
203 }
204
205 void
206 clear() noexcept
207 {
208 _Base::clear();
209 this->_M_invalidate_all();
210 }
211
213 begin() noexcept
214 { return { _Base::begin(), this }; }
215
217 begin() const noexcept
218 { return { _Base::begin(), this }; }
219
221 end() noexcept
222 { return { _Base::end(), this }; }
223
225 end() const noexcept
226 { return { _Base::end(), this }; }
227
229 cbegin() const noexcept
230 { return { _Base::cbegin(), this }; }
231
233 cend() const noexcept
234 { return { _Base::cend(), this }; }
235
236 // local versions
238 begin(size_type __b)
239 {
240 __glibcxx_check_bucket_index(__b);
241 return { _Base::begin(__b), this };
242 }
243
245 end(size_type __b)
246 {
247 __glibcxx_check_bucket_index(__b);
248 return { _Base::end(__b), this };
249 }
250
252 begin(size_type __b) const
253 {
254 __glibcxx_check_bucket_index(__b);
255 return { _Base::begin(__b), this };
256 }
257
259 end(size_type __b) const
260 {
261 __glibcxx_check_bucket_index(__b);
262 return { _Base::end(__b), this };
263 }
264
266 cbegin(size_type __b) const
267 {
268 __glibcxx_check_bucket_index(__b);
269 return { _Base::cbegin(__b), this };
270 }
271
273 cend(size_type __b) const
274 {
275 __glibcxx_check_bucket_index(__b);
276 return { _Base::cend(__b), this };
277 }
278
279 size_type
280 bucket_size(size_type __b) const
281 {
282 __glibcxx_check_bucket_index(__b);
283 return _Base::bucket_size(__b);
284 }
285
286 float
287 max_load_factor() const noexcept
288 { return _Base::max_load_factor(); }
289
290 void
291 max_load_factor(float __f)
292 {
293 __glibcxx_check_max_load_factor(__f);
294 _Base::max_load_factor(__f);
295 }
296
297 template<typename... _Args>
299 emplace(_Args&&... __args)
300 {
301 size_type __bucket_count = this->bucket_count();
302 auto __res = _Base::emplace(std::forward<_Args>(__args)...);
303 _M_check_rehashed(__bucket_count);
304 return { { __res.first, this }, __res.second };
305 }
306
307 template<typename... _Args>
309 emplace_hint(const_iterator __hint, _Args&&... __args)
310 {
312 size_type __bucket_count = this->bucket_count();
313 auto __it = _Base::emplace_hint(__hint.base(),
314 std::forward<_Args>(__args)...);
315 _M_check_rehashed(__bucket_count);
316 return { __it, this };
317 }
318
320 insert(const value_type& __obj)
321 {
322 size_type __bucket_count = this->bucket_count();
323 auto __res = _Base::insert(__obj);
324 _M_check_rehashed(__bucket_count);
325 return { { __res.first, this }, __res.second };
326 }
327
329 insert(const_iterator __hint, const value_type& __obj)
330 {
332 size_type __bucket_count = this->bucket_count();
333 auto __it = _Base::insert(__hint.base(), __obj);
334 _M_check_rehashed(__bucket_count);
335 return { __it, this };
336 }
337
339 insert(value_type&& __obj)
340 {
341 size_type __bucket_count = this->bucket_count();
342 auto __res = _Base::insert(std::move(__obj));
343 _M_check_rehashed(__bucket_count);
344 return { { __res.first, this }, __res.second };
345 }
346
348 insert(const_iterator __hint, value_type&& __obj)
349 {
351 size_type __bucket_count = this->bucket_count();
352 auto __it = _Base::insert(__hint.base(), std::move(__obj));
353 _M_check_rehashed(__bucket_count);
354 return { __it, this };
355 }
356
357 void
359 {
360 size_type __bucket_count = this->bucket_count();
361 _Base::insert(__l);
362 _M_check_rehashed(__bucket_count);
363 }
364
365 template<typename _InputIterator>
366 void
367 insert(_InputIterator __first, _InputIterator __last)
368 {
370 __glibcxx_check_valid_range2(__first, __last, __dist);
371 size_type __bucket_count = this->bucket_count();
372
373 if (__dist.second >= __gnu_debug::__dp_sign)
374 _Base::insert(__gnu_debug::__unsafe(__first),
375 __gnu_debug::__unsafe(__last));
376 else
377 _Base::insert(__first, __last);
378
379 _M_check_rehashed(__bucket_count);
380 }
381
382#if __cplusplus > 201402L
383 using node_type = typename _Base::node_type;
384 using insert_return_type = _Node_insert_return<iterator, node_type>;
385
386 node_type
387 extract(const_iterator __position)
388 {
389 __glibcxx_check_erase(__position);
390 return _M_extract(__position.base());
391 }
392
393 node_type
394 extract(const key_type& __key)
395 {
396 const auto __position = _Base::find(__key);
397 if (__position != _Base::end())
398 return _M_extract(__position);
399 return {};
400 }
401
402 insert_return_type
403 insert(node_type&& __nh)
404 {
405 auto __ret = _Base::insert(std::move(__nh));
406 return
407 { { __ret.position, this }, __ret.inserted, std::move(__ret.node) };
408 }
409
411 insert(const_iterator __hint, node_type&& __nh)
412 {
414 return { _Base::insert(__hint.base(), std::move(__nh)), this };
415 }
416
417 using _Base::merge;
418#endif // C++17
419
421 find(const key_type& __key)
422 { return { _Base::find(__key), this }; }
423
425 find(const key_type& __key) const
426 { return { _Base::find(__key), this }; }
427
429 equal_range(const key_type& __key)
430 {
431 auto __res = _Base::equal_range(__key);
432 return { { __res.first, this }, { __res.second, this } };
433 }
434
436 equal_range(const key_type& __key) const
437 {
438 auto __res = _Base::equal_range(__key);
439 return { { __res.first, this }, { __res.second, this } };
440 }
441
442 size_type
443 erase(const key_type& __key)
444 {
445 size_type __ret(0);
446 auto __victim = _Base::find(__key);
447 if (__victim != _Base::end())
448 {
449 _M_erase(__victim);
450 __ret = 1;
451 }
452 return __ret;
453 }
454
456 erase(const_iterator __it)
457 {
459 return { _M_erase(__it.base()), this };
460 }
461
463 erase(iterator __it)
464 {
466 return { _M_erase(__it.base()), this };
467 }
468
470 erase(const_iterator __first, const_iterator __last)
471 {
472 __glibcxx_check_erase_range(__first, __last);
473 for (auto __tmp = __first.base(); __tmp != __last.base(); ++__tmp)
474 {
475 _GLIBCXX_DEBUG_VERIFY(__tmp != _Base::cend(),
476 _M_message(__gnu_debug::__msg_valid_range)
477 ._M_iterator(__first, "first")
478 ._M_iterator(__last, "last"));
479 _M_invalidate(__tmp);
480 }
481
482 size_type __bucket_count = this->bucket_count();
483 auto __next = _Base::erase(__first.base(), __last.base());
484 _M_check_rehashed(__bucket_count);
485 return { __next, this };
486 }
487
488 _Base&
489 _M_base() noexcept { return *this; }
490
491 const _Base&
492 _M_base() const noexcept { return *this; }
493
494 private:
495 void
496 _M_check_rehashed(size_type __prev_count)
497 {
498 if (__prev_count != this->bucket_count())
499 this->_M_invalidate_all();
500 }
501
502 void
503 _M_invalidate(_Base_const_iterator __victim)
504 {
505 this->_M_invalidate_if(
506 [__victim](_Base_const_iterator __it) { return __it == __victim; });
508 [__victim](_Base_const_local_iterator __it)
509 { return __it._M_curr() == __victim._M_cur; });
510 }
511
512 _Base_iterator
513 _M_erase(_Base_const_iterator __victim)
514 {
515 _M_invalidate(__victim);
516 size_type __bucket_count = this->bucket_count();
517 _Base_iterator __next = _Base::erase(__victim);
518 _M_check_rehashed(__bucket_count);
519 return __next;
520 }
521
522#if __cplusplus > 201402L
523 node_type
524 _M_extract(_Base_const_iterator __victim)
525 {
526 _M_invalidate(__victim);
527 return _Base::extract(__victim);
528 }
529#endif
530 };
531
532#if __cpp_deduction_guides >= 201606
533
534 template<typename _InputIterator,
535 typename _Hash =
537 typename _Pred =
539 typename _Allocator =
541 typename = _RequireInputIter<_InputIterator>,
542 typename = _RequireNotAllocatorOrIntegral<_Hash>,
543 typename = _RequireNotAllocator<_Pred>,
544 typename = _RequireAllocator<_Allocator>>
545 unordered_set(_InputIterator, _InputIterator,
546 unordered_set<int>::size_type = {},
547 _Hash = _Hash(), _Pred = _Pred(), _Allocator = _Allocator())
549 _Hash, _Pred, _Allocator>;
550
551 template<typename _Tp, typename _Hash = hash<_Tp>,
552 typename _Pred = equal_to<_Tp>,
553 typename _Allocator = allocator<_Tp>,
554 typename = _RequireNotAllocatorOrIntegral<_Hash>,
555 typename = _RequireNotAllocator<_Pred>,
556 typename = _RequireAllocator<_Allocator>>
558 unordered_set<int>::size_type = {},
559 _Hash = _Hash(), _Pred = _Pred(), _Allocator = _Allocator())
560 -> unordered_set<_Tp, _Hash, _Pred, _Allocator>;
561
562 template<typename _InputIterator, typename _Allocator,
563 typename = _RequireInputIter<_InputIterator>,
564 typename = _RequireAllocator<_Allocator>>
565 unordered_set(_InputIterator, _InputIterator,
566 unordered_set<int>::size_type, _Allocator)
567 -> unordered_set<typename iterator_traits<_InputIterator>::value_type,
568 hash<
569 typename iterator_traits<_InputIterator>::value_type>,
570 equal_to<
571 typename iterator_traits<_InputIterator>::value_type>,
572 _Allocator>;
573
574 template<typename _InputIterator, typename _Hash, typename _Allocator,
575 typename = _RequireInputIter<_InputIterator>,
576 typename = _RequireNotAllocatorOrIntegral<_Hash>,
577 typename = _RequireAllocator<_Allocator>>
578 unordered_set(_InputIterator, _InputIterator,
579 unordered_set<int>::size_type,
580 _Hash, _Allocator)
581 -> unordered_set<typename iterator_traits<_InputIterator>::value_type,
582 _Hash,
583 equal_to<
584 typename iterator_traits<_InputIterator>::value_type>,
585 _Allocator>;
586
587 template<typename _Tp, typename _Allocator,
588 typename = _RequireAllocator<_Allocator>>
589 unordered_set(initializer_list<_Tp>,
590 unordered_set<int>::size_type, _Allocator)
591 -> unordered_set<_Tp, hash<_Tp>, equal_to<_Tp>, _Allocator>;
592
593 template<typename _Tp, typename _Hash, typename _Allocator,
594 typename = _RequireNotAllocatorOrIntegral<_Hash>,
595 typename = _RequireAllocator<_Allocator>>
596 unordered_set(initializer_list<_Tp>,
597 unordered_set<int>::size_type, _Hash, _Allocator)
598 -> unordered_set<_Tp, _Hash, equal_to<_Tp>, _Allocator>;
599
600#endif
601
602 template<typename _Value, typename _Hash, typename _Pred, typename _Alloc>
603 inline void
604 swap(unordered_set<_Value, _Hash, _Pred, _Alloc>& __x,
605 unordered_set<_Value, _Hash, _Pred, _Alloc>& __y)
606 noexcept(noexcept(__x.swap(__y)))
607 { __x.swap(__y); }
608
609 template<typename _Value, typename _Hash, typename _Pred, typename _Alloc>
610 inline bool
611 operator==(const unordered_set<_Value, _Hash, _Pred, _Alloc>& __x,
612 const unordered_set<_Value, _Hash, _Pred, _Alloc>& __y)
613 { return __x._M_base() == __y._M_base(); }
614
615 template<typename _Value, typename _Hash, typename _Pred, typename _Alloc>
616 inline bool
617 operator!=(const unordered_set<_Value, _Hash, _Pred, _Alloc>& __x,
618 const unordered_set<_Value, _Hash, _Pred, _Alloc>& __y)
619 { return !(__x == __y); }
620
621
622 /// Class std::unordered_multiset with safety/checking/debug instrumentation.
623 template<typename _Value,
624 typename _Hash = std::hash<_Value>,
625 typename _Pred = std::equal_to<_Value>,
626 typename _Alloc = std::allocator<_Value> >
629 unordered_multiset<_Value, _Hash, _Pred, _Alloc>, _Alloc,
630 __gnu_debug::_Safe_unordered_container>,
631 public _GLIBCXX_STD_C::unordered_multiset<_Value, _Hash, _Pred, _Alloc>
632 {
633 typedef _GLIBCXX_STD_C::unordered_multiset<
634 _Value, _Hash, _Pred, _Alloc> _Base;
637 typedef typename _Base::const_iterator _Base_const_iterator;
638 typedef typename _Base::iterator _Base_iterator;
639 typedef typename _Base::const_local_iterator
640 _Base_const_local_iterator;
641 typedef typename _Base::local_iterator _Base_local_iterator;
642
643 template<typename _ItT, typename _SeqT, typename _CatT>
644 friend class ::__gnu_debug::_Safe_iterator;
645 template<typename _ItT, typename _SeqT>
646 friend class ::__gnu_debug::_Safe_local_iterator;
647
648 public:
649 typedef typename _Base::size_type size_type;
650 typedef typename _Base::hasher hasher;
651 typedef typename _Base::key_equal key_equal;
652 typedef typename _Base::allocator_type allocator_type;
653
654 typedef typename _Base::key_type key_type;
655 typedef typename _Base::value_type value_type;
656
658 _Base_iterator, unordered_multiset> iterator;
660 _Base_const_iterator, unordered_multiset> const_iterator;
662 _Base_local_iterator, unordered_multiset> local_iterator;
664 _Base_const_local_iterator, unordered_multiset> const_local_iterator;
665
666 unordered_multiset() = default;
667
668 explicit
669 unordered_multiset(size_type __n,
670 const hasher& __hf = hasher(),
671 const key_equal& __eql = key_equal(),
672 const allocator_type& __a = allocator_type())
673 : _Base(__n, __hf, __eql, __a) { }
674
675 template<typename _InputIterator>
676 unordered_multiset(_InputIterator __first, _InputIterator __last,
677 size_type __n = 0,
678 const hasher& __hf = hasher(),
679 const key_equal& __eql = key_equal(),
680 const allocator_type& __a = allocator_type())
682 __glibcxx_check_valid_constructor_range(__first, __last)),
683 __gnu_debug::__base(__last), __n,
684 __hf, __eql, __a) { }
685
686 unordered_multiset(const unordered_multiset&) = default;
687
688 unordered_multiset(const _Base& __x)
689 : _Base(__x) { }
690
692
693 explicit
694 unordered_multiset(const allocator_type& __a)
695 : _Base(__a) { }
696
698 const allocator_type& __a)
699 : _Base(__uset, __a) { }
700
702 const allocator_type& __a)
703 : _Safe(std::move(__uset._M_safe()), __a),
704 _Base(std::move(__uset._M_base()), __a) { }
705
707 size_type __n = 0,
708 const hasher& __hf = hasher(),
709 const key_equal& __eql = key_equal(),
710 const allocator_type& __a = allocator_type())
711 : _Base(__l, __n, __hf, __eql, __a) { }
712
713 unordered_multiset(size_type __n, const allocator_type& __a)
714 : unordered_multiset(__n, hasher(), key_equal(), __a)
715 { }
716
717 unordered_multiset(size_type __n, const hasher& __hf,
718 const allocator_type& __a)
719 : unordered_multiset(__n, __hf, key_equal(), __a)
720 { }
721
722 template<typename _InputIterator>
723 unordered_multiset(_InputIterator __first, _InputIterator __last,
724 size_type __n,
725 const allocator_type& __a)
726 : unordered_multiset(__first, __last, __n, hasher(), key_equal(), __a)
727 { }
728
729 template<typename _InputIterator>
730 unordered_multiset(_InputIterator __first, _InputIterator __last,
731 size_type __n, const hasher& __hf,
732 const allocator_type& __a)
733 : unordered_multiset(__first, __last, __n, __hf, key_equal(), __a)
734 { }
735
737 size_type __n,
738 const allocator_type& __a)
739 : unordered_multiset(__l, __n, hasher(), key_equal(), __a)
740 { }
741
743 size_type __n, const hasher& __hf,
744 const allocator_type& __a)
745 : unordered_multiset(__l, __n, __hf, key_equal(), __a)
746 { }
747
748 ~unordered_multiset() = default;
749
751 operator=(const unordered_multiset&) = default;
752
754 operator=(unordered_multiset&&) = default;
755
757 operator=(initializer_list<value_type> __l)
758 {
759 this->_M_base() = __l;
760 this->_M_invalidate_all();
761 return *this;
762 }
763
764 void
765 swap(unordered_multiset& __x)
766 noexcept( noexcept(declval<_Base&>().swap(__x)) )
767 {
768 _Safe::_M_swap(__x);
769 _Base::swap(__x);
770 }
771
772 void
773 clear() noexcept
774 {
775 _Base::clear();
776 this->_M_invalidate_all();
777 }
778
780 begin() noexcept
781 { return { _Base::begin(), this }; }
782
784 begin() const noexcept
785 { return { _Base::begin(), this }; }
786
788 end() noexcept
789 { return { _Base::end(), this }; }
790
792 end() const noexcept
793 { return { _Base::end(), this }; }
794
796 cbegin() const noexcept
797 { return { _Base::cbegin(), this }; }
798
800 cend() const noexcept
801 { return { _Base::cend(), this }; }
802
803 // local versions
805 begin(size_type __b)
806 {
807 __glibcxx_check_bucket_index(__b);
808 return { _Base::begin(__b), this };
809 }
810
812 end(size_type __b)
813 {
814 __glibcxx_check_bucket_index(__b);
815 return { _Base::end(__b), this };
816 }
817
819 begin(size_type __b) const
820 {
821 __glibcxx_check_bucket_index(__b);
822 return { _Base::begin(__b), this };
823 }
824
826 end(size_type __b) const
827 {
828 __glibcxx_check_bucket_index(__b);
829 return { _Base::end(__b), this };
830 }
831
833 cbegin(size_type __b) const
834 {
835 __glibcxx_check_bucket_index(__b);
836 return { _Base::cbegin(__b), this };
837 }
838
840 cend(size_type __b) const
841 {
842 __glibcxx_check_bucket_index(__b);
843 return { _Base::cend(__b), this };
844 }
845
846 size_type
847 bucket_size(size_type __b) const
848 {
849 __glibcxx_check_bucket_index(__b);
850 return _Base::bucket_size(__b);
851 }
852
853 float
854 max_load_factor() const noexcept
855 { return _Base::max_load_factor(); }
856
857 void
858 max_load_factor(float __f)
859 {
860 __glibcxx_check_max_load_factor(__f);
861 _Base::max_load_factor(__f);
862 }
863
864 template<typename... _Args>
866 emplace(_Args&&... __args)
867 {
868 size_type __bucket_count = this->bucket_count();
869 auto __it = _Base::emplace(std::forward<_Args>(__args)...);
870 _M_check_rehashed(__bucket_count);
871 return { __it, this };
872 }
873
874 template<typename... _Args>
876 emplace_hint(const_iterator __hint, _Args&&... __args)
877 {
879 size_type __bucket_count = this->bucket_count();
880 auto __it = _Base::emplace_hint(__hint.base(),
881 std::forward<_Args>(__args)...);
882 _M_check_rehashed(__bucket_count);
883 return { __it, this };
884 }
885
887 insert(const value_type& __obj)
888 {
889 size_type __bucket_count = this->bucket_count();
890 auto __it = _Base::insert(__obj);
891 _M_check_rehashed(__bucket_count);
892 return { __it, this };
893 }
894
896 insert(const_iterator __hint, const value_type& __obj)
897 {
899 size_type __bucket_count = this->bucket_count();
900 auto __it = _Base::insert(__hint.base(), __obj);
901 _M_check_rehashed(__bucket_count);
902 return { __it, this };
903 }
904
906 insert(value_type&& __obj)
907 {
908 size_type __bucket_count = this->bucket_count();
909 auto __it = _Base::insert(std::move(__obj));
910 _M_check_rehashed(__bucket_count);
911 return { __it, this };
912 }
913
915 insert(const_iterator __hint, value_type&& __obj)
916 {
918 size_type __bucket_count = this->bucket_count();
919 auto __it = _Base::insert(__hint.base(), std::move(__obj));
920 _M_check_rehashed(__bucket_count);
921 return { __it, this };
922 }
923
924 void
926 {
927 size_type __bucket_count = this->bucket_count();
928 _Base::insert(__l);
929 _M_check_rehashed(__bucket_count);
930 }
931
932 template<typename _InputIterator>
933 void
934 insert(_InputIterator __first, _InputIterator __last)
935 {
937 __glibcxx_check_valid_range2(__first, __last, __dist);
938 size_type __bucket_count = this->bucket_count();
939
940 if (__dist.second >= __gnu_debug::__dp_sign)
941 _Base::insert(__gnu_debug::__unsafe(__first),
942 __gnu_debug::__unsafe(__last));
943 else
944 _Base::insert(__first, __last);
945
946 _M_check_rehashed(__bucket_count);
947 }
948
949#if __cplusplus > 201402L
950 using node_type = typename _Base::node_type;
951
952 node_type
953 extract(const_iterator __position)
954 {
955 __glibcxx_check_erase(__position);
956 return _M_extract(__position.base());
957 }
958
959 node_type
960 extract(const key_type& __key)
961 {
962 const auto __position = _Base::find(__key);
963 if (__position != _Base::end())
964 return _M_extract(__position);
965 return {};
966 }
967
969 insert(node_type&& __nh)
970 { return { _Base::insert(std::move(__nh)), this }; }
971
973 insert(const_iterator __hint, node_type&& __nh)
974 {
976 return { _Base::insert(__hint.base(), std::move(__nh)), this };
977 }
978
979 using _Base::merge;
980#endif // C++17
981
983 find(const key_type& __key)
984 { return { _Base::find(__key), this }; }
985
987 find(const key_type& __key) const
988 { return { _Base::find(__key), this }; }
989
991 equal_range(const key_type& __key)
992 {
993 auto __res = _Base::equal_range(__key);
994 return { { __res.first, this }, { __res.second, this } };
995 }
996
998 equal_range(const key_type& __key) const
999 {
1000 auto __res = _Base::equal_range(__key);
1001 return { { __res.first, this }, { __res.second, this } };
1002 }
1003
1004 size_type
1005 erase(const key_type& __key)
1006 {
1007 size_type __ret(0);
1008 auto __pair = _Base::equal_range(__key);
1009 for (auto __victim = __pair.first; __victim != __pair.second;)
1010 {
1011 _M_invalidate(__victim);
1012 __victim = _Base::erase(__victim);
1013 ++__ret;
1014 }
1015
1016 return __ret;
1017 }
1018
1019 iterator
1020 erase(const_iterator __it)
1021 {
1023 return { _M_erase(__it.base()), this };
1024 }
1025
1026 iterator
1027 erase(iterator __it)
1028 {
1030 return { _M_erase(__it.base()), this };
1031 }
1032
1033 iterator
1034 erase(const_iterator __first, const_iterator __last)
1035 {
1036 __glibcxx_check_erase_range(__first, __last);
1037 for (auto __tmp = __first.base(); __tmp != __last.base(); ++__tmp)
1038 {
1039 _GLIBCXX_DEBUG_VERIFY(__tmp != _Base::cend(),
1040 _M_message(__gnu_debug::__msg_valid_range)
1041 ._M_iterator(__first, "first")
1042 ._M_iterator(__last, "last"));
1043 _M_invalidate(__tmp);
1044 }
1045 return { _Base::erase(__first.base(), __last.base()), this };
1046 }
1047
1048 _Base&
1049 _M_base() noexcept { return *this; }
1050
1051 const _Base&
1052 _M_base() const noexcept { return *this; }
1053
1054 private:
1055 void
1056 _M_check_rehashed(size_type __prev_count)
1057 {
1058 if (__prev_count != this->bucket_count())
1059 this->_M_invalidate_all();
1060 }
1061
1062 void
1063 _M_invalidate(_Base_const_iterator __victim)
1064 {
1065 this->_M_invalidate_if(
1066 [__victim](_Base_const_iterator __it) { return __it == __victim; });
1068 [__victim](_Base_const_local_iterator __it)
1069 { return __it._M_curr() == __victim._M_cur; });
1070 }
1071
1072 _Base_iterator
1073 _M_erase(_Base_const_iterator __victim)
1074 {
1075 _M_invalidate(__victim);
1076 size_type __bucket_count = this->bucket_count();
1077 _Base_iterator __next = _Base::erase(__victim);
1078 _M_check_rehashed(__bucket_count);
1079 return __next;
1080 }
1081
1082#if __cplusplus > 201402L
1083 node_type
1084 _M_extract(_Base_const_iterator __victim)
1085 {
1086 _M_invalidate(__victim);
1087 return _Base::extract(__victim);
1088 }
1089#endif
1090 };
1091
1092#if __cpp_deduction_guides >= 201606
1093
1094 template<typename _InputIterator,
1095 typename _Hash =
1097 typename _Pred =
1099 typename _Allocator =
1101 typename = _RequireInputIter<_InputIterator>,
1102 typename = _RequireNotAllocatorOrIntegral<_Hash>,
1103 typename = _RequireNotAllocator<_Pred>,
1104 typename = _RequireAllocator<_Allocator>>
1105 unordered_multiset(_InputIterator, _InputIterator,
1106 unordered_multiset<int>::size_type = {},
1107 _Hash = _Hash(), _Pred = _Pred(),
1108 _Allocator = _Allocator())
1110 _Hash, _Pred, _Allocator>;
1111
1112 template<typename _Tp, typename _Hash = hash<_Tp>,
1113 typename _Pred = equal_to<_Tp>,
1114 typename _Allocator = allocator<_Tp>,
1115 typename = _RequireNotAllocatorOrIntegral<_Hash>,
1116 typename = _RequireNotAllocator<_Pred>,
1117 typename = _RequireAllocator<_Allocator>>
1119 unordered_multiset<int>::size_type = {},
1120 _Hash = _Hash(), _Pred = _Pred(),
1121 _Allocator = _Allocator())
1122 -> unordered_multiset<_Tp, _Hash, _Pred, _Allocator>;
1123
1124 template<typename _InputIterator, typename _Allocator,
1125 typename = _RequireInputIter<_InputIterator>,
1126 typename = _RequireAllocator<_Allocator>>
1127 unordered_multiset(_InputIterator, _InputIterator,
1128 unordered_multiset<int>::size_type, _Allocator)
1129 -> unordered_multiset<typename iterator_traits<_InputIterator>::value_type,
1130 hash<typename
1131 iterator_traits<_InputIterator>::value_type>,
1132 equal_to<typename
1133 iterator_traits<_InputIterator>::value_type>,
1134 _Allocator>;
1135
1136 template<typename _InputIterator, typename _Hash, typename _Allocator,
1137 typename = _RequireInputIter<_InputIterator>,
1138 typename = _RequireNotAllocatorOrIntegral<_Hash>,
1139 typename = _RequireAllocator<_Allocator>>
1140 unordered_multiset(_InputIterator, _InputIterator,
1141 unordered_multiset<int>::size_type,
1142 _Hash, _Allocator)
1143 -> unordered_multiset<typename
1144 iterator_traits<_InputIterator>::value_type,
1145 _Hash,
1146 equal_to<
1147 typename
1148 iterator_traits<_InputIterator>::value_type>,
1149 _Allocator>;
1150
1151 template<typename _Tp, typename _Allocator,
1152 typename = _RequireAllocator<_Allocator>>
1153 unordered_multiset(initializer_list<_Tp>,
1154 unordered_multiset<int>::size_type, _Allocator)
1155 -> unordered_multiset<_Tp, hash<_Tp>, equal_to<_Tp>, _Allocator>;
1156
1157 template<typename _Tp, typename _Hash, typename _Allocator,
1158 typename = _RequireNotAllocatorOrIntegral<_Hash>,
1159 typename = _RequireAllocator<_Allocator>>
1160 unordered_multiset(initializer_list<_Tp>,
1161 unordered_multiset<int>::size_type, _Hash, _Allocator)
1162 -> unordered_multiset<_Tp, _Hash, equal_to<_Tp>, _Allocator>;
1163
1164#endif
1165
1166 template<typename _Value, typename _Hash, typename _Pred, typename _Alloc>
1167 inline void
1168 swap(unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x,
1169 unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y)
1170 noexcept(noexcept(__x.swap(__y)))
1171 { __x.swap(__y); }
1172
1173 template<typename _Value, typename _Hash, typename _Pred, typename _Alloc>
1174 inline bool
1175 operator==(const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x,
1176 const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y)
1177 { return __x._M_base() == __y._M_base(); }
1178
1179 template<typename _Value, typename _Hash, typename _Pred, typename _Alloc>
1180 inline bool
1181 operator!=(const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x,
1182 const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y)
1183 { return !(__x == __y); }
1184
1185} // namespace __debug
1186} // namespace std
1187
1188#endif // C++11
1189
1190#endif
#define __glibcxx_check_insert(_Position)
Definition: macros.h:150
#define __glibcxx_check_erase_range(_First, _Last)
Definition: macros.h:244
#define __glibcxx_check_erase(_Position)
Definition: macros.h:216
constexpr std::remove_reference< _Tp >::type && move(_Tp &&__t) noexcept
Convert a value to an rvalue.
Definition: move.h:101
_T2 second
The second member.
Definition: stl_pair.h:217
ISO C++ entities toplevel namespace is std.
constexpr _Iterator __base(_Iterator __it)
initializer_list
Primary class template hash.
The standard allocator, as per [20.4].
Definition: allocator.h:121
Traits class for iterators.
Struct holding two objects of arbitrary type.
Definition: stl_pair.h:212
A standard container composed of equivalent keys (possibly containing multiple of each key value) in ...
A standard container composed of unique keys (containing at most one of each key value) in which the ...
Definition: unordered_set.h:98
Safe iterator wrapper.
_Iterator & base() noexcept
Return the underlying iterator.
Base class that supports tracking of iterators that reference a sequence.
Definition: safe_base.h:189
Safe class dealing with some allocator dependent operations.
Base class for constructing a safe unordered container type that tracks iterators that reference it.
Class std::unordered_set with safety/checking/debug instrumentation.
Class std::unordered_multiset with safety/checking/debug instrumentation.