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