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 
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  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
std::allocator
The standard allocator, as per [20.4].
Definition: allocator.h:108
std::initializer_list
initializer_list
Definition: initializer_list:47
__glibcxx_check_erase_range
#define __glibcxx_check_erase_range(_First, _Last)
Definition: macros.h:173
std::equal_to
One of the comparison functors.
Definition: stl_function.h:331
std::begin
constexpr const _Tp * begin(initializer_list< _Tp > __ils) noexcept
Return an iterator pointing to the first element of the initializer_list.
Definition: initializer_list:89
__gnu_debug::_Safe_unordered_container
Base class for constructing a safe unordered container type that tracks iterators that reference it...
Definition: safe_unordered_container.h:58
__gnu_debug::_Safe_local_iterator
Safe iterator wrapper.
Definition: formatter.h:59
__gnu_debug::_Safe_container
Safe class dealing with some allocator dependent operations.
Definition: safe_container.h:41
std::cend
constexpr auto cend(const _Container &__cont) noexcept(noexcept(std::end(__cont))) -> decltype(std::end(__cont))
Return an iterator pointing to one past the last element of the const container.
Definition: range_access.h:127
std::pair::first
_T1 first
second_type is the second bound type
Definition: stl_pair.h:199
__glibcxx_check_erase
#define __glibcxx_check_erase(_Position)
Definition: macros.h:145
std::cbegin
constexpr auto cbegin(const _Container &__cont) noexcept(noexcept(std::begin(__cont))) -> decltype(std::begin(__cont))
Return an iterator pointing to the first element of the const container.
Definition: range_access.h:116
std
ISO C++ entities toplevel namespace is std.
__gnu_debug::_Safe_iterator::base
_Iterator & base() noexcept
Return the underlying iterator.
Definition: safe_iterator.h:404
std::hash
Primary class template hash.
Definition: system_error:134
__gnu_debug::_Safe_iterator
Safe iterator wrapper.
Definition: formatter.h:56
__gnu_debug::_Safe_sequence_base
Base class that supports tracking of iterators that reference a sequence.
Definition: safe_base.h:186
std::end
constexpr const _Tp * end(initializer_list< _Tp > __ils) noexcept
Return an iterator pointing to one past the last element of the initializer_list. ...
Definition: initializer_list:99
std::__debug::unordered_multiset
Class std::unordered_multiset with safety/checking/debug instrumentation.
Definition: debug/unordered_set:504
__glibcxx_check_insert
#define __glibcxx_check_insert(_Position)
Definition: macros.h:79
std::make_pair
constexpr pair< typename __decay_and_strip< _T1 >::__type, typename __decay_and_strip< _T2 >::__type > make_pair(_T1 &&__x, _T2 &&__y)
A convenience wrapper for creating a pair from two objects.
Definition: stl_pair.h:497
std::pair
Struct holding two objects of arbitrary type.
Definition: stl_pair.h:194
std::pair::second
_T2 second
first is a copy of the first object
Definition: stl_pair.h:200
std::__debug::unordered_set
Class std::unordered_set with safety/checking/debug instrumentation.
Definition: debug/unordered_set:51