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