libstdc++
debug/unordered_set
Go to the documentation of this file.
1 // Debugging unordered_set/unordered_multiset implementation -*- C++ -*-
2 
3 // Copyright (C) 2003-2015 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 
42 namespace std _GLIBCXX_VISIBILITY(default)
43 {
44 namespace __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  __glibcxx_check_valid_range(__first, __last);
359  size_type __bucket_count = this->bucket_count();
360  _Base::insert(__gnu_debug::__base(__first),
361  __gnu_debug::__base(__last));
362  _M_check_rehashed(__bucket_count);
363  }
364 
365  iterator
366  find(const key_type& __key)
367  { return iterator(_Base::find(__key), this); }
368 
369  const_iterator
370  find(const key_type& __key) const
371  { return const_iterator(_Base::find(__key), this); }
372 
373  std::pair<iterator, iterator>
374  equal_range(const key_type& __key)
375  {
376  std::pair<_Base_iterator, _Base_iterator> __res
377  = _Base::equal_range(__key);
378  return std::make_pair(iterator(__res.first, this),
379  iterator(__res.second, this));
380  }
381 
382  std::pair<const_iterator, const_iterator>
383  equal_range(const key_type& __key) const
384  {
385  std::pair<_Base_const_iterator, _Base_const_iterator>
386  __res = _Base::equal_range(__key);
387  return std::make_pair(const_iterator(__res.first, this),
388  const_iterator(__res.second, this));
389  }
390 
391  size_type
392  erase(const key_type& __key)
393  {
394  size_type __ret(0);
395  _Base_iterator __victim(_Base::find(__key));
396  if (__victim != _Base::end())
397  {
398  this->_M_invalidate_if(
399  [__victim](_Base_const_iterator __it)
400  { return __it == __victim; });
401  this->_M_invalidate_local_if(
402  [__victim](_Base_const_local_iterator __it)
403  { return __it._M_curr() == __victim._M_cur; });
404  size_type __bucket_count = this->bucket_count();
405  _Base::erase(__victim);
406  _M_check_rehashed(__bucket_count);
407  __ret = 1;
408  }
409  return __ret;
410  }
411 
412  iterator
413  erase(const_iterator __it)
414  {
415  __glibcxx_check_erase(__it);
416  _Base_const_iterator __victim = __it.base();
417  this->_M_invalidate_if(
418  [__victim](_Base_const_iterator __it)
419  { return __it == __victim; });
420  this->_M_invalidate_local_if(
421  [__victim](_Base_const_local_iterator __it)
422  { return __it._M_curr() == __victim._M_cur; });
423  size_type __bucket_count = this->bucket_count();
424  _Base_iterator __next = _Base::erase(__it.base());
425  _M_check_rehashed(__bucket_count);
426  return iterator(__next, this);
427  }
428 
429  iterator
430  erase(iterator __it)
431  { return erase(const_iterator(__it)); }
432 
433  iterator
434  erase(const_iterator __first, const_iterator __last)
435  {
436  __glibcxx_check_erase_range(__first, __last);
437  for (_Base_const_iterator __tmp = __first.base();
438  __tmp != __last.base(); ++__tmp)
439  {
440  _GLIBCXX_DEBUG_VERIFY(__tmp != _Base::end(),
441  _M_message(__gnu_debug::__msg_valid_range)
442  ._M_iterator(__first, "first")
443  ._M_iterator(__last, "last"));
444  this->_M_invalidate_if(
445  [__tmp](_Base_const_iterator __it)
446  { return __it == __tmp; });
447  this->_M_invalidate_local_if(
448  [__tmp](_Base_const_local_iterator __it)
449  { return __it._M_curr() == __tmp._M_cur; });
450  }
451  size_type __bucket_count = this->bucket_count();
452  _Base_iterator __next = _Base::erase(__first.base(),
453  __last.base());
454  _M_check_rehashed(__bucket_count);
455  return iterator(__next, this);
456  }
457 
458  _Base&
459  _M_base() noexcept { return *this; }
460 
461  const _Base&
462  _M_base() const noexcept { return *this; }
463 
464  private:
465  void
466  _M_check_rehashed(size_type __prev_count)
467  {
468  if (__prev_count != this->bucket_count())
469  this->_M_invalidate_locals();
470  }
471  };
472 
473  template<typename _Value, typename _Hash, typename _Pred, typename _Alloc>
474  inline void
475  swap(unordered_set<_Value, _Hash, _Pred, _Alloc>& __x,
476  unordered_set<_Value, _Hash, _Pred, _Alloc>& __y)
477  { __x.swap(__y); }
478 
479  template<typename _Value, typename _Hash, typename _Pred, typename _Alloc>
480  inline bool
481  operator==(const unordered_set<_Value, _Hash, _Pred, _Alloc>& __x,
482  const unordered_set<_Value, _Hash, _Pred, _Alloc>& __y)
483  { return __x._M_base() == __y._M_base(); }
484 
485  template<typename _Value, typename _Hash, typename _Pred, typename _Alloc>
486  inline bool
487  operator!=(const unordered_set<_Value, _Hash, _Pred, _Alloc>& __x,
488  const unordered_set<_Value, _Hash, _Pred, _Alloc>& __y)
489  { return !(__x == __y); }
490 
491 
492  /// Class std::unordered_multiset with safety/checking/debug instrumentation.
493  template<typename _Value,
494  typename _Hash = std::hash<_Value>,
495  typename _Pred = std::equal_to<_Value>,
496  typename _Alloc = std::allocator<_Value> >
497  class unordered_multiset
498  : public __gnu_debug::_Safe_container<
499  unordered_multiset<_Value, _Hash, _Pred, _Alloc>, _Alloc,
500  __gnu_debug::_Safe_unordered_container>,
501  public _GLIBCXX_STD_C::unordered_multiset<_Value, _Hash, _Pred, _Alloc>
502  {
503  typedef _GLIBCXX_STD_C::unordered_multiset<
504  _Value, _Hash, _Pred, _Alloc> _Base;
505  typedef __gnu_debug::_Safe_container<unordered_multiset,
506  _Alloc, __gnu_debug::_Safe_unordered_container> _Safe;
507  typedef typename _Base::const_iterator _Base_const_iterator;
508  typedef typename _Base::iterator _Base_iterator;
509  typedef typename _Base::const_local_iterator
510  _Base_const_local_iterator;
511  typedef typename _Base::local_iterator _Base_local_iterator;
512 
513  public:
514  typedef typename _Base::size_type size_type;
515  typedef typename _Base::hasher hasher;
516  typedef typename _Base::key_equal key_equal;
517  typedef typename _Base::allocator_type allocator_type;
518 
519  typedef typename _Base::key_type key_type;
520  typedef typename _Base::value_type value_type;
521 
522  typedef __gnu_debug::_Safe_iterator<
523  _Base_iterator, unordered_multiset> iterator;
524  typedef __gnu_debug::_Safe_iterator<
525  _Base_const_iterator, unordered_multiset> const_iterator;
526  typedef __gnu_debug::_Safe_local_iterator<
527  _Base_local_iterator, unordered_multiset> local_iterator;
528  typedef __gnu_debug::_Safe_local_iterator<
529  _Base_const_local_iterator, unordered_multiset> const_local_iterator;
530 
531  unordered_multiset() = default;
532 
533  explicit
534  unordered_multiset(size_type __n,
535  const hasher& __hf = hasher(),
536  const key_equal& __eql = key_equal(),
537  const allocator_type& __a = allocator_type())
538  : _Base(__n, __hf, __eql, __a) { }
539 
540  template<typename _InputIterator>
541  unordered_multiset(_InputIterator __first, _InputIterator __last,
542  size_type __n = 0,
543  const hasher& __hf = hasher(),
544  const key_equal& __eql = key_equal(),
545  const allocator_type& __a = allocator_type())
546  : _Base(__gnu_debug::__base(__gnu_debug::__check_valid_range(__first,
547  __last)),
548  __gnu_debug::__base(__last), __n,
549  __hf, __eql, __a) { }
550 
551  unordered_multiset(const unordered_multiset&) = default;
552 
553  unordered_multiset(const _Base& __x)
554  : _Base(__x) { }
555 
556  unordered_multiset(unordered_multiset&&) = default;
557 
558  explicit
559  unordered_multiset(const allocator_type& __a)
560  : _Base(__a) { }
561 
562  unordered_multiset(const unordered_multiset& __uset,
563  const allocator_type& __a)
564  : _Base(__uset, __a) { }
565 
566  unordered_multiset(unordered_multiset&& __uset,
567  const allocator_type& __a)
568  : _Safe(std::move(__uset._M_safe()), __a),
569  _Base(std::move(__uset._M_base()), __a) { }
570 
571  unordered_multiset(initializer_list<value_type> __l,
572  size_type __n = 0,
573  const hasher& __hf = hasher(),
574  const key_equal& __eql = key_equal(),
575  const allocator_type& __a = allocator_type())
576  : _Base(__l, __n, __hf, __eql, __a) { }
577 
578  unordered_multiset(size_type __n, const allocator_type& __a)
579  : unordered_multiset(__n, hasher(), key_equal(), __a)
580  { }
581 
582  unordered_multiset(size_type __n, const hasher& __hf,
583  const allocator_type& __a)
584  : unordered_multiset(__n, __hf, key_equal(), __a)
585  { }
586 
587  template<typename _InputIterator>
588  unordered_multiset(_InputIterator __first, _InputIterator __last,
589  size_type __n,
590  const allocator_type& __a)
591  : unordered_multiset(__first, __last, __n, hasher(), key_equal(), __a)
592  { }
593 
594  template<typename _InputIterator>
595  unordered_multiset(_InputIterator __first, _InputIterator __last,
596  size_type __n, const hasher& __hf,
597  const allocator_type& __a)
598  : unordered_multiset(__first, __last, __n, __hf, key_equal(), __a)
599  { }
600 
601  unordered_multiset(initializer_list<value_type> __l,
602  size_type __n,
603  const allocator_type& __a)
604  : unordered_multiset(__l, __n, hasher(), key_equal(), __a)
605  { }
606 
607  unordered_multiset(initializer_list<value_type> __l,
608  size_type __n, const hasher& __hf,
609  const allocator_type& __a)
610  : unordered_multiset(__l, __n, __hf, key_equal(), __a)
611  { }
612 
613  ~unordered_multiset() = default;
614 
615  unordered_multiset&
616  operator=(const unordered_multiset&) = default;
617 
618  unordered_multiset&
619  operator=(unordered_multiset&&) = default;
620 
621  unordered_multiset&
622  operator=(initializer_list<value_type> __l)
623  {
624  this->_M_base() = __l;
625  this->_M_invalidate_all();
626  return *this;
627  }
628 
629  void
630  swap(unordered_multiset& __x)
631  noexcept( noexcept(declval<_Base>().swap(__x)) )
632  {
633  _Safe::_M_swap(__x);
634  _Base::swap(__x);
635  }
636 
637  void
638  clear() noexcept
639  {
640  _Base::clear();
641  this->_M_invalidate_all();
642  }
643 
644  iterator
645  begin() noexcept
646  { return iterator(_Base::begin(), this); }
647 
648  const_iterator
649  begin() const noexcept
650  { return const_iterator(_Base::begin(), this); }
651 
652  iterator
653  end() noexcept
654  { return iterator(_Base::end(), this); }
655 
656  const_iterator
657  end() const noexcept
658  { return const_iterator(_Base::end(), this); }
659 
660  const_iterator
661  cbegin() const noexcept
662  { return const_iterator(_Base::begin(), this); }
663 
664  const_iterator
665  cend() const noexcept
666  { return const_iterator(_Base::end(), this); }
667 
668  // local versions
669  local_iterator
670  begin(size_type __b)
671  {
672  __glibcxx_check_bucket_index(__b);
673  return local_iterator(_Base::begin(__b), this);
674  }
675 
676  local_iterator
677  end(size_type __b)
678  {
679  __glibcxx_check_bucket_index(__b);
680  return local_iterator(_Base::end(__b), this);
681  }
682 
683  const_local_iterator
684  begin(size_type __b) const
685  {
686  __glibcxx_check_bucket_index(__b);
687  return const_local_iterator(_Base::begin(__b), this);
688  }
689 
690  const_local_iterator
691  end(size_type __b) const
692  {
693  __glibcxx_check_bucket_index(__b);
694  return const_local_iterator(_Base::end(__b), this);
695  }
696 
697  const_local_iterator
698  cbegin(size_type __b) const
699  {
700  __glibcxx_check_bucket_index(__b);
701  return const_local_iterator(_Base::cbegin(__b), this);
702  }
703 
704  const_local_iterator
705  cend(size_type __b) const
706  {
707  __glibcxx_check_bucket_index(__b);
708  return const_local_iterator(_Base::cend(__b), this);
709  }
710 
711  size_type
712  bucket_size(size_type __b) const
713  {
714  __glibcxx_check_bucket_index(__b);
715  return _Base::bucket_size(__b);
716  }
717 
718  float
719  max_load_factor() const noexcept
720  { return _Base::max_load_factor(); }
721 
722  void
723  max_load_factor(float __f)
724  {
725  __glibcxx_check_max_load_factor(__f);
726  _Base::max_load_factor(__f);
727  }
728 
729  template<typename... _Args>
730  iterator
731  emplace(_Args&&... __args)
732  {
733  size_type __bucket_count = this->bucket_count();
734  _Base_iterator __it
735  = _Base::emplace(std::forward<_Args>(__args)...);
736  _M_check_rehashed(__bucket_count);
737  return iterator(__it, this);
738  }
739 
740  template<typename... _Args>
741  iterator
742  emplace_hint(const_iterator __hint, _Args&&... __args)
743  {
744  __glibcxx_check_insert(__hint);
745  size_type __bucket_count = this->bucket_count();
746  _Base_iterator __it = _Base::emplace_hint(__hint.base(),
747  std::forward<_Args>(__args)...);
748  _M_check_rehashed(__bucket_count);
749  return iterator(__it, this);
750  }
751 
752  iterator
753  insert(const value_type& __obj)
754  {
755  size_type __bucket_count = this->bucket_count();
756  _Base_iterator __it = _Base::insert(__obj);
757  _M_check_rehashed(__bucket_count);
758  return iterator(__it, this);
759  }
760 
761  iterator
762  insert(const_iterator __hint, const value_type& __obj)
763  {
764  __glibcxx_check_insert(__hint);
765  size_type __bucket_count = this->bucket_count();
766  _Base_iterator __it = _Base::insert(__hint.base(), __obj);
767  _M_check_rehashed(__bucket_count);
768  return iterator(__it, this);
769  }
770 
771  iterator
772  insert(value_type&& __obj)
773  {
774  size_type __bucket_count = this->bucket_count();
775  _Base_iterator __it = _Base::insert(std::move(__obj));
776  _M_check_rehashed(__bucket_count);
777  return iterator(__it, this);
778  }
779 
780  iterator
781  insert(const_iterator __hint, value_type&& __obj)
782  {
783  __glibcxx_check_insert(__hint);
784  size_type __bucket_count = this->bucket_count();
785  _Base_iterator __it = _Base::insert(__hint.base(), std::move(__obj));
786  _M_check_rehashed(__bucket_count);
787  return iterator(__it, this);
788  }
789 
790  void
791  insert(std::initializer_list<value_type> __l)
792  {
793  size_type __bucket_count = this->bucket_count();
794  _Base::insert(__l);
795  _M_check_rehashed(__bucket_count);
796  }
797 
798  template<typename _InputIterator>
799  void
800  insert(_InputIterator __first, _InputIterator __last)
801  {
802  __glibcxx_check_valid_range(__first, __last);
803  size_type __bucket_count = this->bucket_count();
804  _Base::insert(__gnu_debug::__base(__first),
805  __gnu_debug::__base(__last));
806  _M_check_rehashed(__bucket_count);
807  }
808 
809  iterator
810  find(const key_type& __key)
811  { return iterator(_Base::find(__key), this); }
812 
813  const_iterator
814  find(const key_type& __key) const
815  { return const_iterator(_Base::find(__key), this); }
816 
817  std::pair<iterator, iterator>
818  equal_range(const key_type& __key)
819  {
820  std::pair<_Base_iterator, _Base_iterator> __res
821  = _Base::equal_range(__key);
822  return std::make_pair(iterator(__res.first, this),
823  iterator(__res.second, this));
824  }
825 
826  std::pair<const_iterator, const_iterator>
827  equal_range(const key_type& __key) const
828  {
829  std::pair<_Base_const_iterator, _Base_const_iterator>
830  __res = _Base::equal_range(__key);
831  return std::make_pair(const_iterator(__res.first, this),
832  const_iterator(__res.second, this));
833  }
834 
835  size_type
836  erase(const key_type& __key)
837  {
838  size_type __ret(0);
839  std::pair<_Base_iterator, _Base_iterator> __pair =
840  _Base::equal_range(__key);
841  for (_Base_iterator __victim = __pair.first; __victim != __pair.second;)
842  {
843  this->_M_invalidate_if([__victim](_Base_const_iterator __it)
844  { return __it == __victim; });
845  this->_M_invalidate_local_if(
846  [__victim](_Base_const_local_iterator __it)
847  { return __it._M_curr() == __victim._M_cur; });
848  _Base::erase(__victim++);
849  ++__ret;
850  }
851  return __ret;
852  }
853 
854  iterator
855  erase(const_iterator __it)
856  {
857  __glibcxx_check_erase(__it);
858  _Base_const_iterator __victim = __it.base();
859  this->_M_invalidate_if([__victim](_Base_const_iterator __it)
860  { return __it == __victim; });
861  this->_M_invalidate_local_if(
862  [__victim](_Base_const_local_iterator __it)
863  { return __it._M_curr() == __victim._M_cur; });
864  return iterator(_Base::erase(__it.base()), this);
865  }
866 
867  iterator
868  erase(iterator __it)
869  { return erase(const_iterator(__it)); }
870 
871  iterator
872  erase(const_iterator __first, const_iterator __last)
873  {
874  __glibcxx_check_erase_range(__first, __last);
875  for (_Base_const_iterator __tmp = __first.base();
876  __tmp != __last.base(); ++__tmp)
877  {
878  _GLIBCXX_DEBUG_VERIFY(__tmp != _Base::end(),
879  _M_message(__gnu_debug::__msg_valid_range)
880  ._M_iterator(__first, "first")
881  ._M_iterator(__last, "last"));
882  this->_M_invalidate_if([__tmp](_Base_const_iterator __it)
883  { return __it == __tmp; });
884  this->_M_invalidate_local_if(
885  [__tmp](_Base_const_local_iterator __it)
886  { return __it._M_curr() == __tmp._M_cur; });
887  }
888  return iterator(_Base::erase(__first.base(),
889  __last.base()), this);
890  }
891 
892  _Base&
893  _M_base() noexcept { return *this; }
894 
895  const _Base&
896  _M_base() const noexcept { return *this; }
897 
898  private:
899  void
900  _M_check_rehashed(size_type __prev_count)
901  {
902  if (__prev_count != this->bucket_count())
903  this->_M_invalidate_locals();
904  }
905  };
906 
907  template<typename _Value, typename _Hash, typename _Pred, typename _Alloc>
908  inline void
909  swap(unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x,
910  unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y)
911  { __x.swap(__y); }
912 
913  template<typename _Value, typename _Hash, typename _Pred, typename _Alloc>
914  inline bool
915  operator==(const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x,
916  const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y)
917  { return __x._M_base() == __y._M_base(); }
918 
919  template<typename _Value, typename _Hash, typename _Pred, typename _Alloc>
920  inline bool
921  operator!=(const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x,
922  const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y)
923  { return !(__x == __y); }
924 
925 } // namespace __debug
926 } // namespace std
927 
928 #endif // C++11
929 
930 #endif