libstdc++
debug/unordered_set
Go to the documentation of this file.
1// Debugging unordered_set/unordered_multiset implementation -*- C++ -*-
2
3// Copyright (C) 2003-2017 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 <unordered_set>
38
39#include <debug/safe_unordered_container.h>
40#include <debug/safe_container.h>
41#include <debug/safe_iterator.h>
42#include <debug/safe_local_iterator.h>
43
44namespace std _GLIBCXX_VISIBILITY(default)
45{
46namespace __debug
47{
48 /// Class std::unordered_set with safety/checking/debug instrumentation.
49 template<typename _Value,
50 typename _Hash = std::hash<_Value>,
51 typename _Pred = std::equal_to<_Value>,
52 typename _Alloc = std::allocator<_Value> >
53 class unordered_set
54 : public __gnu_debug::_Safe_container<
55 unordered_set<_Value, _Hash, _Pred, _Alloc>, _Alloc,
56 __gnu_debug::_Safe_unordered_container>,
57 public _GLIBCXX_STD_C::unordered_set<_Value, _Hash, _Pred, _Alloc>
58 {
59 typedef _GLIBCXX_STD_C::unordered_set<
60 _Value, _Hash, _Pred, _Alloc> _Base;
61 typedef __gnu_debug::_Safe_container<
62 unordered_set, _Alloc, __gnu_debug::_Safe_unordered_container> _Safe;
63
64 typedef typename _Base::const_iterator _Base_const_iterator;
65 typedef typename _Base::iterator _Base_iterator;
66 typedef typename _Base::const_local_iterator _Base_const_local_iterator;
67 typedef typename _Base::local_iterator _Base_local_iterator;
68
69 public:
70 typedef typename _Base::size_type size_type;
71 typedef typename _Base::hasher hasher;
72 typedef typename _Base::key_equal key_equal;
73 typedef typename _Base::allocator_type allocator_type;
74
75 typedef typename _Base::key_type key_type;
76 typedef typename _Base::value_type value_type;
77
78 typedef __gnu_debug::_Safe_iterator<
79 _Base_iterator, unordered_set> iterator;
80 typedef __gnu_debug::_Safe_iterator<
81 _Base_const_iterator, unordered_set> const_iterator;
82 typedef __gnu_debug::_Safe_local_iterator<
83 _Base_local_iterator, unordered_set> local_iterator;
84 typedef __gnu_debug::_Safe_local_iterator<
85 _Base_const_local_iterator, unordered_set> const_local_iterator;
86
87 unordered_set() = default;
88
89 explicit
90 unordered_set(size_type __n,
91 const hasher& __hf = hasher(),
92 const key_equal& __eql = key_equal(),
93 const allocator_type& __a = allocator_type())
94 : _Base(__n, __hf, __eql, __a) { }
95
96 template<typename _InputIterator>
97 unordered_set(_InputIterator __first, _InputIterator __last,
98 size_type __n = 0,
99 const hasher& __hf = hasher(),
100 const key_equal& __eql = key_equal(),
101 const allocator_type& __a = allocator_type())
102 : _Base(__gnu_debug::__base(__gnu_debug::__check_valid_range(__first,
103 __last)),
104 __gnu_debug::__base(__last), __n,
105 __hf, __eql, __a) { }
106
107 unordered_set(const unordered_set&) = default;
108
109 unordered_set(const _Base& __x)
110 : _Base(__x) { }
111
112 unordered_set(unordered_set&&) = default;
113
114 explicit
115 unordered_set(const allocator_type& __a)
116 : _Base(__a) { }
117
118 unordered_set(const unordered_set& __uset,
119 const allocator_type& __a)
120 : _Base(__uset, __a) { }
121
122 unordered_set(unordered_set&& __uset,
123 const allocator_type& __a)
124 : _Safe(std::move(__uset._M_safe()), __a),
125 _Base(std::move(__uset._M_base()), __a) { }
126
127 unordered_set(initializer_list<value_type> __l,
128 size_type __n = 0,
129 const hasher& __hf = hasher(),
130 const key_equal& __eql = key_equal(),
131 const allocator_type& __a = allocator_type())
132 : _Base(__l, __n, __hf, __eql, __a) { }
133
134 unordered_set(size_type __n, const allocator_type& __a)
135 : unordered_set(__n, hasher(), key_equal(), __a)
136 { }
137
138 unordered_set(size_type __n, const hasher& __hf,
139 const allocator_type& __a)
140 : unordered_set(__n, __hf, key_equal(), __a)
141 { }
142
143 template<typename _InputIterator>
144 unordered_set(_InputIterator __first, _InputIterator __last,
145 size_type __n,
146 const allocator_type& __a)
147 : unordered_set(__first, __last, __n, hasher(), key_equal(), __a)
148 { }
149
150 template<typename _InputIterator>
151 unordered_set(_InputIterator __first, _InputIterator __last,
152 size_type __n, const hasher& __hf,
153 const allocator_type& __a)
154 : unordered_set(__first, __last, __n, __hf, key_equal(), __a)
155 { }
156
157 unordered_set(initializer_list<value_type> __l,
158 size_type __n,
159 const allocator_type& __a)
160 : unordered_set(__l, __n, hasher(), key_equal(), __a)
161 { }
162
163 unordered_set(initializer_list<value_type> __l,
164 size_type __n, const hasher& __hf,
165 const allocator_type& __a)
166 : unordered_set(__l, __n, __hf, key_equal(), __a)
167 { }
168
169 ~unordered_set() = default;
170
171 unordered_set&
172 operator=(const unordered_set&) = default;
173
174 unordered_set&
175 operator=(unordered_set&&) = default;
176
177 unordered_set&
178 operator=(initializer_list<value_type> __l)
179 {
180 _M_base() = __l;
181 this->_M_invalidate_all();
182 return *this;
183 }
184
185 void
186 swap(unordered_set& __x)
187 noexcept( noexcept(declval<_Base&>().swap(__x)) )
188 {
189 _Safe::_M_swap(__x);
190 _Base::swap(__x);
191 }
192
193 void
194 clear() noexcept
195 {
196 _Base::clear();
197 this->_M_invalidate_all();
198 }
199
200 iterator
201 begin() noexcept
202 { return iterator(_Base::begin(), this); }
203
204 const_iterator
205 begin() const noexcept
206 { return const_iterator(_Base::begin(), this); }
207
208 iterator
209 end() noexcept
210 { return iterator(_Base::end(), this); }
211
212 const_iterator
213 end() const noexcept
214 { return const_iterator(_Base::end(), this); }
215
216 const_iterator
217 cbegin() const noexcept
218 { return const_iterator(_Base::begin(), this); }
219
220 const_iterator
221 cend() const noexcept
222 { return const_iterator(_Base::end(), this); }
223
224 // local versions
225 local_iterator
226 begin(size_type __b)
227 {
228 __glibcxx_check_bucket_index(__b);
229 return local_iterator(_Base::begin(__b), this);
230 }
231
232 local_iterator
233 end(size_type __b)
234 {
235 __glibcxx_check_bucket_index(__b);
236 return local_iterator(_Base::end(__b), this);
237 }
238
239 const_local_iterator
240 begin(size_type __b) const
241 {
242 __glibcxx_check_bucket_index(__b);
243 return const_local_iterator(_Base::begin(__b), this);
244 }
245
246 const_local_iterator
247 end(size_type __b) const
248 {
249 __glibcxx_check_bucket_index(__b);
250 return const_local_iterator(_Base::end(__b), this);
251 }
252
253 const_local_iterator
254 cbegin(size_type __b) const
255 {
256 __glibcxx_check_bucket_index(__b);
257 return const_local_iterator(_Base::cbegin(__b), this);
258 }
259
260 const_local_iterator
261 cend(size_type __b) const
262 {
263 __glibcxx_check_bucket_index(__b);
264 return const_local_iterator(_Base::cend(__b), this);
265 }
266
267 size_type
268 bucket_size(size_type __b) const
269 {
270 __glibcxx_check_bucket_index(__b);
271 return _Base::bucket_size(__b);
272 }
273
274 float
275 max_load_factor() const noexcept
276 { return _Base::max_load_factor(); }
277
278 void
279 max_load_factor(float __f)
280 {
281 __glibcxx_check_max_load_factor(__f);
282 _Base::max_load_factor(__f);
283 }
284
285 template<typename... _Args>
286 std::pair<iterator, bool>
287 emplace(_Args&&... __args)
288 {
289 size_type __bucket_count = this->bucket_count();
290 std::pair<_Base_iterator, bool> __res
291 = _Base::emplace(std::forward<_Args>(__args)...);
292 _M_check_rehashed(__bucket_count);
293 return std::make_pair(iterator(__res.first, this), __res.second);
294 }
295
296 template<typename... _Args>
297 iterator
298 emplace_hint(const_iterator __hint, _Args&&... __args)
299 {
300 __glibcxx_check_insert(__hint);
301 size_type __bucket_count = this->bucket_count();
302 _Base_iterator __it = _Base::emplace_hint(__hint.base(),
303 std::forward<_Args>(__args)...);
304 _M_check_rehashed(__bucket_count);
305 return iterator(__it, this);
306 }
307
308 std::pair<iterator, bool>
309 insert(const value_type& __obj)
310 {
311 size_type __bucket_count = this->bucket_count();
312 std::pair<_Base_iterator, bool> __res
313 = _Base::insert(__obj);
314 _M_check_rehashed(__bucket_count);
315 return std::make_pair(iterator(__res.first, this), __res.second);
316 }
317
318 iterator
319 insert(const_iterator __hint, const value_type& __obj)
320 {
321 __glibcxx_check_insert(__hint);
322 size_type __bucket_count = this->bucket_count();
323 _Base_iterator __it = _Base::insert(__hint.base(), __obj);
324 _M_check_rehashed(__bucket_count);
325 return iterator(__it, this);
326 }
327
328 std::pair<iterator, bool>
329 insert(value_type&& __obj)
330 {
331 size_type __bucket_count = this->bucket_count();
332 std::pair<_Base_iterator, bool> __res
333 = _Base::insert(std::move(__obj));
334 _M_check_rehashed(__bucket_count);
335 return std::make_pair(iterator(__res.first, this), __res.second);
336 }
337
338 iterator
339 insert(const_iterator __hint, value_type&& __obj)
340 {
341 __glibcxx_check_insert(__hint);
342 size_type __bucket_count = this->bucket_count();
343 _Base_iterator __it = _Base::insert(__hint.base(), std::move(__obj));
344 _M_check_rehashed(__bucket_count);
345 return iterator(__it, this);
346 }
347
348 void
349 insert(std::initializer_list<value_type> __l)
350 {
351 size_type __bucket_count = this->bucket_count();
352 _Base::insert(__l);
353 _M_check_rehashed(__bucket_count);
354 }
355
356 template<typename _InputIterator>
357 void
358 insert(_InputIterator __first, _InputIterator __last)
359 {
360 typename __gnu_debug::_Distance_traits<_InputIterator>::__type __dist;
361 __glibcxx_check_valid_range2(__first, __last, __dist);
362 size_type __bucket_count = this->bucket_count();
363
364 if (__dist.second >= __gnu_debug::__dp_sign)
365 _Base::insert(__gnu_debug::__unsafe(__first),
366 __gnu_debug::__unsafe(__last));
367 else
368 _Base::insert(__first, __last);
369
370 _M_check_rehashed(__bucket_count);
371 }
372
373#if __cplusplus > 201402L
374 using node_type = typename _Base::node_type;
375
376 struct insert_return_type
377 {
378 bool inserted;
379 iterator position;
380 node_type node;
381 };
382
383 node_type
384 extract(const_iterator __position)
385 {
386 __glibcxx_check_erase(__position);
387 _Base_const_iterator __victim = __position.base();
388 this->_M_invalidate_if(
389 [__victim](_Base_const_iterator __it) { return __it == __victim; }
390 );
391 this->_M_invalidate_local_if(
392 [__victim](_Base_const_local_iterator __it) {
393 return __it._M_curr() == __victim._M_cur;
394 });
395 return _Base::extract(__position.base());
396 }
397
398 node_type
399 extract(const key_type& __key)
400 {
401 const auto __position = find(__key);
402 if (__position != end())
403 return extract(__position);
404 return {};
405 }
406
407 insert_return_type
408 insert(node_type&& __nh)
409 {
410 auto __ret = _Base::insert(std::move(__nh));
411 iterator __pos = iterator(__ret.position, this);
412 return { __ret.inserted, __pos, std::move(__ret.node) };
413 }
414
415 iterator
416 insert(const_iterator __hint, node_type&& __nh)
417 {
418 __glibcxx_check_insert(__hint);
419 return iterator(_Base::insert(__hint.base(), std::move(__nh)), this);
420 }
421
422 using _Base::merge;
423#endif // C++17
424
425 iterator
426 find(const key_type& __key)
427 { return iterator(_Base::find(__key), this); }
428
429 const_iterator
430 find(const key_type& __key) const
431 { return const_iterator(_Base::find(__key), this); }
432
433 std::pair<iterator, iterator>
434 equal_range(const key_type& __key)
435 {
436 std::pair<_Base_iterator, _Base_iterator> __res
437 = _Base::equal_range(__key);
438 return std::make_pair(iterator(__res.first, this),
439 iterator(__res.second, this));
440 }
441
442 std::pair<const_iterator, const_iterator>
443 equal_range(const key_type& __key) const
444 {
445 std::pair<_Base_const_iterator, _Base_const_iterator>
446 __res = _Base::equal_range(__key);
447 return std::make_pair(const_iterator(__res.first, this),
448 const_iterator(__res.second, this));
449 }
450
451 size_type
452 erase(const key_type& __key)
453 {
454 size_type __ret(0);
455 _Base_iterator __victim(_Base::find(__key));
456 if (__victim != _Base::end())
457 {
458 this->_M_invalidate_if(
459 [__victim](_Base_const_iterator __it)
460 { return __it == __victim; });
461 this->_M_invalidate_local_if(
462 [__victim](_Base_const_local_iterator __it)
463 { return __it._M_curr() == __victim._M_cur; });
464 size_type __bucket_count = this->bucket_count();
465 _Base::erase(__victim);
466 _M_check_rehashed(__bucket_count);
467 __ret = 1;
468 }
469 return __ret;
470 }
471
472 iterator
473 erase(const_iterator __it)
474 {
475 __glibcxx_check_erase(__it);
476 _Base_const_iterator __victim = __it.base();
477 this->_M_invalidate_if(
478 [__victim](_Base_const_iterator __it)
479 { return __it == __victim; });
480 this->_M_invalidate_local_if(
481 [__victim](_Base_const_local_iterator __it)
482 { return __it._M_curr() == __victim._M_cur; });
483 size_type __bucket_count = this->bucket_count();
484 _Base_iterator __next = _Base::erase(__it.base());
485 _M_check_rehashed(__bucket_count);
486 return iterator(__next, this);
487 }
488
489 iterator
490 erase(iterator __it)
491 { return erase(const_iterator(__it)); }
492
493 iterator
494 erase(const_iterator __first, const_iterator __last)
495 {
496 __glibcxx_check_erase_range(__first, __last);
497 for (_Base_const_iterator __tmp = __first.base();
498 __tmp != __last.base(); ++__tmp)
499 {
500 _GLIBCXX_DEBUG_VERIFY(__tmp != _Base::end(),
501 _M_message(__gnu_debug::__msg_valid_range)
502 ._M_iterator(__first, "first")
503 ._M_iterator(__last, "last"));
504 this->_M_invalidate_if(
505 [__tmp](_Base_const_iterator __it)
506 { return __it == __tmp; });
507 this->_M_invalidate_local_if(
508 [__tmp](_Base_const_local_iterator __it)
509 { return __it._M_curr() == __tmp._M_cur; });
510 }
511 size_type __bucket_count = this->bucket_count();
512 _Base_iterator __next = _Base::erase(__first.base(),
513 __last.base());
514 _M_check_rehashed(__bucket_count);
515 return iterator(__next, this);
516 }
517
518 _Base&
519 _M_base() noexcept { return *this; }
520
521 const _Base&
522 _M_base() const noexcept { return *this; }
523
524 private:
525 void
526 _M_check_rehashed(size_type __prev_count)
527 {
528 if (__prev_count != this->bucket_count())
529 this->_M_invalidate_locals();
530 }
531 };
532
533 template<typename _Value, typename _Hash, typename _Pred, typename _Alloc>
534 inline void
535 swap(unordered_set<_Value, _Hash, _Pred, _Alloc>& __x,
536 unordered_set<_Value, _Hash, _Pred, _Alloc>& __y)
537 noexcept(noexcept(__x.swap(__y)))
538 { __x.swap(__y); }
539
540 template<typename _Value, typename _Hash, typename _Pred, typename _Alloc>
541 inline bool
542 operator==(const unordered_set<_Value, _Hash, _Pred, _Alloc>& __x,
543 const unordered_set<_Value, _Hash, _Pred, _Alloc>& __y)
544 { return __x._M_base() == __y._M_base(); }
545
546 template<typename _Value, typename _Hash, typename _Pred, typename _Alloc>
547 inline bool
548 operator!=(const unordered_set<_Value, _Hash, _Pred, _Alloc>& __x,
549 const unordered_set<_Value, _Hash, _Pred, _Alloc>& __y)
550 { return !(__x == __y); }
551
552
553 /// Class std::unordered_multiset with safety/checking/debug instrumentation.
554 template<typename _Value,
555 typename _Hash = std::hash<_Value>,
556 typename _Pred = std::equal_to<_Value>,
557 typename _Alloc = std::allocator<_Value> >
558 class unordered_multiset
559 : public __gnu_debug::_Safe_container<
560 unordered_multiset<_Value, _Hash, _Pred, _Alloc>, _Alloc,
561 __gnu_debug::_Safe_unordered_container>,
562 public _GLIBCXX_STD_C::unordered_multiset<_Value, _Hash, _Pred, _Alloc>
563 {
564 typedef _GLIBCXX_STD_C::unordered_multiset<
565 _Value, _Hash, _Pred, _Alloc> _Base;
566 typedef __gnu_debug::_Safe_container<unordered_multiset,
567 _Alloc, __gnu_debug::_Safe_unordered_container> _Safe;
568 typedef typename _Base::const_iterator _Base_const_iterator;
569 typedef typename _Base::iterator _Base_iterator;
570 typedef typename _Base::const_local_iterator
571 _Base_const_local_iterator;
572 typedef typename _Base::local_iterator _Base_local_iterator;
573
574 public:
575 typedef typename _Base::size_type size_type;
576 typedef typename _Base::hasher hasher;
577 typedef typename _Base::key_equal key_equal;
578 typedef typename _Base::allocator_type allocator_type;
579
580 typedef typename _Base::key_type key_type;
581 typedef typename _Base::value_type value_type;
582
583 typedef __gnu_debug::_Safe_iterator<
584 _Base_iterator, unordered_multiset> iterator;
585 typedef __gnu_debug::_Safe_iterator<
586 _Base_const_iterator, unordered_multiset> const_iterator;
587 typedef __gnu_debug::_Safe_local_iterator<
588 _Base_local_iterator, unordered_multiset> local_iterator;
589 typedef __gnu_debug::_Safe_local_iterator<
590 _Base_const_local_iterator, unordered_multiset> const_local_iterator;
591
592 unordered_multiset() = default;
593
594 explicit
595 unordered_multiset(size_type __n,
596 const hasher& __hf = hasher(),
597 const key_equal& __eql = key_equal(),
598 const allocator_type& __a = allocator_type())
599 : _Base(__n, __hf, __eql, __a) { }
600
601 template<typename _InputIterator>
602 unordered_multiset(_InputIterator __first, _InputIterator __last,
603 size_type __n = 0,
604 const hasher& __hf = hasher(),
605 const key_equal& __eql = key_equal(),
606 const allocator_type& __a = allocator_type())
607 : _Base(__gnu_debug::__base(__gnu_debug::__check_valid_range(__first,
608 __last)),
609 __gnu_debug::__base(__last), __n,
610 __hf, __eql, __a) { }
611
612 unordered_multiset(const unordered_multiset&) = default;
613
614 unordered_multiset(const _Base& __x)
615 : _Base(__x) { }
616
617 unordered_multiset(unordered_multiset&&) = default;
618
619 explicit
620 unordered_multiset(const allocator_type& __a)
621 : _Base(__a) { }
622
623 unordered_multiset(const unordered_multiset& __uset,
624 const allocator_type& __a)
625 : _Base(__uset, __a) { }
626
627 unordered_multiset(unordered_multiset&& __uset,
628 const allocator_type& __a)
629 : _Safe(std::move(__uset._M_safe()), __a),
630 _Base(std::move(__uset._M_base()), __a) { }
631
632 unordered_multiset(initializer_list<value_type> __l,
633 size_type __n = 0,
634 const hasher& __hf = hasher(),
635 const key_equal& __eql = key_equal(),
636 const allocator_type& __a = allocator_type())
637 : _Base(__l, __n, __hf, __eql, __a) { }
638
639 unordered_multiset(size_type __n, const allocator_type& __a)
640 : unordered_multiset(__n, hasher(), key_equal(), __a)
641 { }
642
643 unordered_multiset(size_type __n, const hasher& __hf,
644 const allocator_type& __a)
645 : unordered_multiset(__n, __hf, key_equal(), __a)
646 { }
647
648 template<typename _InputIterator>
649 unordered_multiset(_InputIterator __first, _InputIterator __last,
650 size_type __n,
651 const allocator_type& __a)
652 : unordered_multiset(__first, __last, __n, hasher(), key_equal(), __a)
653 { }
654
655 template<typename _InputIterator>
656 unordered_multiset(_InputIterator __first, _InputIterator __last,
657 size_type __n, const hasher& __hf,
658 const allocator_type& __a)
659 : unordered_multiset(__first, __last, __n, __hf, key_equal(), __a)
660 { }
661
662 unordered_multiset(initializer_list<value_type> __l,
663 size_type __n,
664 const allocator_type& __a)
665 : unordered_multiset(__l, __n, hasher(), key_equal(), __a)
666 { }
667
668 unordered_multiset(initializer_list<value_type> __l,
669 size_type __n, const hasher& __hf,
670 const allocator_type& __a)
671 : unordered_multiset(__l, __n, __hf, key_equal(), __a)
672 { }
673
674 ~unordered_multiset() = default;
675
676 unordered_multiset&
677 operator=(const unordered_multiset&) = default;
678
679 unordered_multiset&
680 operator=(unordered_multiset&&) = default;
681
682 unordered_multiset&
683 operator=(initializer_list<value_type> __l)
684 {
685 this->_M_base() = __l;
686 this->_M_invalidate_all();
687 return *this;
688 }
689
690 void
691 swap(unordered_multiset& __x)
692 noexcept( noexcept(declval<_Base&>().swap(__x)) )
693 {
694 _Safe::_M_swap(__x);
695 _Base::swap(__x);
696 }
697
698 void
699 clear() noexcept
700 {
701 _Base::clear();
702 this->_M_invalidate_all();
703 }
704
705 iterator
706 begin() noexcept
707 { return iterator(_Base::begin(), this); }
708
709 const_iterator
710 begin() const noexcept
711 { return const_iterator(_Base::begin(), this); }
712
713 iterator
714 end() noexcept
715 { return iterator(_Base::end(), this); }
716
717 const_iterator
718 end() const noexcept
719 { return const_iterator(_Base::end(), this); }
720
721 const_iterator
722 cbegin() const noexcept
723 { return const_iterator(_Base::begin(), this); }
724
725 const_iterator
726 cend() const noexcept
727 { return const_iterator(_Base::end(), this); }
728
729 // local versions
730 local_iterator
731 begin(size_type __b)
732 {
733 __glibcxx_check_bucket_index(__b);
734 return local_iterator(_Base::begin(__b), this);
735 }
736
737 local_iterator
738 end(size_type __b)
739 {
740 __glibcxx_check_bucket_index(__b);
741 return local_iterator(_Base::end(__b), this);
742 }
743
744 const_local_iterator
745 begin(size_type __b) const
746 {
747 __glibcxx_check_bucket_index(__b);
748 return const_local_iterator(_Base::begin(__b), this);
749 }
750
751 const_local_iterator
752 end(size_type __b) const
753 {
754 __glibcxx_check_bucket_index(__b);
755 return const_local_iterator(_Base::end(__b), this);
756 }
757
758 const_local_iterator
759 cbegin(size_type __b) const
760 {
761 __glibcxx_check_bucket_index(__b);
762 return const_local_iterator(_Base::cbegin(__b), this);
763 }
764
765 const_local_iterator
766 cend(size_type __b) const
767 {
768 __glibcxx_check_bucket_index(__b);
769 return const_local_iterator(_Base::cend(__b), this);
770 }
771
772 size_type
773 bucket_size(size_type __b) const
774 {
775 __glibcxx_check_bucket_index(__b);
776 return _Base::bucket_size(__b);
777 }
778
779 float
780 max_load_factor() const noexcept
781 { return _Base::max_load_factor(); }
782
783 void
784 max_load_factor(float __f)
785 {
786 __glibcxx_check_max_load_factor(__f);
787 _Base::max_load_factor(__f);
788 }
789
790 template<typename... _Args>
791 iterator
792 emplace(_Args&&... __args)
793 {
794 size_type __bucket_count = this->bucket_count();
795 _Base_iterator __it
796 = _Base::emplace(std::forward<_Args>(__args)...);
797 _M_check_rehashed(__bucket_count);
798 return iterator(__it, this);
799 }
800
801 template<typename... _Args>
802 iterator
803 emplace_hint(const_iterator __hint, _Args&&... __args)
804 {
805 __glibcxx_check_insert(__hint);
806 size_type __bucket_count = this->bucket_count();
807 _Base_iterator __it = _Base::emplace_hint(__hint.base(),
808 std::forward<_Args>(__args)...);
809 _M_check_rehashed(__bucket_count);
810 return iterator(__it, this);
811 }
812
813 iterator
814 insert(const value_type& __obj)
815 {
816 size_type __bucket_count = this->bucket_count();
817 _Base_iterator __it = _Base::insert(__obj);
818 _M_check_rehashed(__bucket_count);
819 return iterator(__it, this);
820 }
821
822 iterator
823 insert(const_iterator __hint, const value_type& __obj)
824 {
825 __glibcxx_check_insert(__hint);
826 size_type __bucket_count = this->bucket_count();
827 _Base_iterator __it = _Base::insert(__hint.base(), __obj);
828 _M_check_rehashed(__bucket_count);
829 return iterator(__it, this);
830 }
831
832 iterator
833 insert(value_type&& __obj)
834 {
835 size_type __bucket_count = this->bucket_count();
836 _Base_iterator __it = _Base::insert(std::move(__obj));
837 _M_check_rehashed(__bucket_count);
838 return iterator(__it, this);
839 }
840
841 iterator
842 insert(const_iterator __hint, value_type&& __obj)
843 {
844 __glibcxx_check_insert(__hint);
845 size_type __bucket_count = this->bucket_count();
846 _Base_iterator __it = _Base::insert(__hint.base(), std::move(__obj));
847 _M_check_rehashed(__bucket_count);
848 return iterator(__it, this);
849 }
850
851 void
852 insert(std::initializer_list<value_type> __l)
853 {
854 size_type __bucket_count = this->bucket_count();
855 _Base::insert(__l);
856 _M_check_rehashed(__bucket_count);
857 }
858
859 template<typename _InputIterator>
860 void
861 insert(_InputIterator __first, _InputIterator __last)
862 {
863 typename __gnu_debug::_Distance_traits<_InputIterator>::__type __dist;
864 __glibcxx_check_valid_range2(__first, __last, __dist);
865 size_type __bucket_count = this->bucket_count();
866
867 if (__dist.second >= __gnu_debug::__dp_sign)
868 _Base::insert(__gnu_debug::__unsafe(__first),
869 __gnu_debug::__unsafe(__last));
870 else
871 _Base::insert(__first, __last);
872
873 _M_check_rehashed(__bucket_count);
874 }
875
876#if __cplusplus > 201402L
877 using node_type = typename _Base::node_type;
878
879 node_type
880 extract(const_iterator __position)
881 {
882 __glibcxx_check_erase(__position);
883 _Base_const_iterator __victim = __position.base();
884 this->_M_invalidate_if(
885 [__victim](_Base_const_iterator __it) { return __it == __victim; }
886 );
887 this->_M_invalidate_local_if(
888 [__victim](_Base_const_local_iterator __it) {
889 return __it._M_curr() == __victim._M_cur;
890 });
891 return _Base::extract(__position.base());
892 }
893
894 node_type
895 extract(const key_type& __key)
896 {
897 const auto __position = find(__key);
898 if (__position != end())
899 return extract(__position);
900 return {};
901 }
902
903 iterator
904 insert(node_type&& __nh)
905 { return iterator(_Base::insert(std::move(__nh)), this); }
906
907 iterator
908 insert(const_iterator __hint, node_type&& __nh)
909 {
910 __glibcxx_check_insert(__hint);
911 return iterator(_Base::insert(__hint.base(), std::move(__nh)), this);
912 }
913
914 using _Base::merge;
915#endif // C++17
916
917 iterator
918 find(const key_type& __key)
919 { return iterator(_Base::find(__key), this); }
920
921 const_iterator
922 find(const key_type& __key) const
923 { return const_iterator(_Base::find(__key), this); }
924
925 std::pair<iterator, iterator>
926 equal_range(const key_type& __key)
927 {
928 std::pair<_Base_iterator, _Base_iterator> __res
929 = _Base::equal_range(__key);
930 return std::make_pair(iterator(__res.first, this),
931 iterator(__res.second, this));
932 }
933
934 std::pair<const_iterator, const_iterator>
935 equal_range(const key_type& __key) const
936 {
937 std::pair<_Base_const_iterator, _Base_const_iterator>
938 __res = _Base::equal_range(__key);
939 return std::make_pair(const_iterator(__res.first, this),
940 const_iterator(__res.second, this));
941 }
942
943 size_type
944 erase(const key_type& __key)
945 {
946 size_type __ret(0);
947 std::pair<_Base_iterator, _Base_iterator> __pair =
948 _Base::equal_range(__key);
949 for (_Base_iterator __victim = __pair.first; __victim != __pair.second;)
950 {
951 this->_M_invalidate_if([__victim](_Base_const_iterator __it)
952 { return __it == __victim; });
953 this->_M_invalidate_local_if(
954 [__victim](_Base_const_local_iterator __it)
955 { return __it._M_curr() == __victim._M_cur; });
956 _Base::erase(__victim++);
957 ++__ret;
958 }
959 return __ret;
960 }
961
962 iterator
963 erase(const_iterator __it)
964 {
965 __glibcxx_check_erase(__it);
966 _Base_const_iterator __victim = __it.base();
967 this->_M_invalidate_if([__victim](_Base_const_iterator __it)
968 { return __it == __victim; });
969 this->_M_invalidate_local_if(
970 [__victim](_Base_const_local_iterator __it)
971 { return __it._M_curr() == __victim._M_cur; });
972 return iterator(_Base::erase(__it.base()), this);
973 }
974
975 iterator
976 erase(iterator __it)
977 { return erase(const_iterator(__it)); }
978
979 iterator
980 erase(const_iterator __first, const_iterator __last)
981 {
982 __glibcxx_check_erase_range(__first, __last);
983 for (_Base_const_iterator __tmp = __first.base();
984 __tmp != __last.base(); ++__tmp)
985 {
986 _GLIBCXX_DEBUG_VERIFY(__tmp != _Base::end(),
987 _M_message(__gnu_debug::__msg_valid_range)
988 ._M_iterator(__first, "first")
989 ._M_iterator(__last, "last"));
990 this->_M_invalidate_if([__tmp](_Base_const_iterator __it)
991 { return __it == __tmp; });
992 this->_M_invalidate_local_if(
993 [__tmp](_Base_const_local_iterator __it)
994 { return __it._M_curr() == __tmp._M_cur; });
995 }
996 return iterator(_Base::erase(__first.base(),
997 __last.base()), this);
998 }
999
1000 _Base&
1001 _M_base() noexcept { return *this; }
1002
1003 const _Base&
1004 _M_base() const noexcept { return *this; }
1005
1006 private:
1007 void
1008 _M_check_rehashed(size_type __prev_count)
1009 {
1010 if (__prev_count != this->bucket_count())
1011 this->_M_invalidate_locals();
1012 }
1013 };
1014
1015 template<typename _Value, typename _Hash, typename _Pred, typename _Alloc>
1016 inline void
1017 swap(unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x,
1018 unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y)
1019 noexcept(noexcept(__x.swap(__y)))
1020 { __x.swap(__y); }
1021
1022 template<typename _Value, typename _Hash, typename _Pred, typename _Alloc>
1023 inline bool
1024 operator==(const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x,
1025 const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y)
1026 { return __x._M_base() == __y._M_base(); }
1027
1028 template<typename _Value, typename _Hash, typename _Pred, typename _Alloc>
1029 inline bool
1030 operator!=(const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x,
1031 const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y)
1032 { return !(__x == __y); }
1033
1034} // namespace __debug
1035} // namespace std
1036
1037#endif // C++11
1038
1039#endif