libstdc++
debug/unordered_set
Go to the documentation of this file.
1 // Debugging unordered_set/unordered_multiset implementation -*- C++ -*-
2 
3 // Copyright (C) 2003, 2004, 2005, 2006, 2007, 2008, 2009, 2010, 2011, 2013
4 // Free Software Foundation, Inc.
5 //
6 // This file is part of the GNU ISO C++ Library. This library is free
7 // software; you can redistribute it and/or modify it under the
8 // terms of the GNU General Public License as published by the
9 // Free Software Foundation; either version 3, or (at your option)
10 // any later version.
11 
12 // This library is distributed in the hope that it will be useful,
13 // but WITHOUT ANY WARRANTY; without even the implied warranty of
14 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15 // GNU General Public License for more details.
16 
17 // Under Section 7 of GPL version 3, you are granted additional
18 // permissions described in the GCC Runtime Library Exception, version
19 // 3.1, as published by the Free Software Foundation.
20 
21 // You should have received a copy of the GNU General Public License and
22 // a copy of the GCC Runtime Library Exception along with this program;
23 // see the files COPYING3 and COPYING.RUNTIME respectively. If not, see
24 // <http://www.gnu.org/licenses/>.
25 
26 /** @file debug/unordered_set
27  * This file is a GNU debug extension to the Standard C++ Library.
28  */
29 
30 #ifndef _GLIBCXX_DEBUG_UNORDERED_SET
31 #define _GLIBCXX_DEBUG_UNORDERED_SET 1
32 
33 #ifndef __GXX_EXPERIMENTAL_CXX0X__
34 # include <bits/c++0x_warning.h>
35 #else
36 # include <unordered_set>
37 
38 #include <debug/safe_unordered_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 _GLIBCXX_STD_C::unordered_set<_Value, _Hash, _Pred, _Alloc>,
53  public __gnu_debug::_Safe_unordered_container<unordered_set<_Value, _Hash,
54  _Pred, _Alloc> >
55  {
56  typedef _GLIBCXX_STD_C::unordered_set<_Value, _Hash,
57  _Pred, _Alloc> _Base;
58  typedef __gnu_debug::_Safe_unordered_container<unordered_set> _Safe_base;
59  typedef typename _Base::const_iterator _Base_const_iterator;
60  typedef typename _Base::iterator _Base_iterator;
61  typedef typename _Base::const_local_iterator _Base_const_local_iterator;
62  typedef typename _Base::local_iterator _Base_local_iterator;
63 
64  public:
65  typedef typename _Base::size_type size_type;
66  typedef typename _Base::hasher hasher;
67  typedef typename _Base::key_equal key_equal;
68  typedef typename _Base::allocator_type allocator_type;
69 
70  typedef typename _Base::key_type key_type;
71  typedef typename _Base::value_type value_type;
72 
73  typedef __gnu_debug::_Safe_iterator<_Base_iterator,
74  unordered_set> iterator;
75  typedef __gnu_debug::_Safe_iterator<_Base_const_iterator,
76  unordered_set> const_iterator;
77  typedef __gnu_debug::_Safe_local_iterator<_Base_local_iterator,
78  unordered_set> local_iterator;
79  typedef __gnu_debug::_Safe_local_iterator<_Base_const_local_iterator,
80  unordered_set> const_local_iterator;
81 
82  explicit
83  unordered_set(size_type __n = 10,
84  const hasher& __hf = hasher(),
85  const key_equal& __eql = key_equal(),
86  const allocator_type& __a = allocator_type())
87  : _Base(__n, __hf, __eql, __a) { }
88 
89  template<typename _InputIterator>
90  unordered_set(_InputIterator __first, _InputIterator __last,
91  size_type __n = 0,
92  const hasher& __hf = hasher(),
93  const key_equal& __eql = key_equal(),
94  const allocator_type& __a = allocator_type())
95  : _Base(__gnu_debug::__base(__gnu_debug::__check_valid_range(__first,
96  __last)),
97  __gnu_debug::__base(__last), __n,
98  __hf, __eql, __a) { }
99 
100  unordered_set(const unordered_set& __x) = default;
101 
102  unordered_set(const _Base& __x)
103  : _Base(__x) { }
104 
105  unordered_set(unordered_set&& __x) = default;
106 
107  unordered_set(initializer_list<value_type> __l,
108  size_type __n = 0,
109  const hasher& __hf = hasher(),
110  const key_equal& __eql = key_equal(),
111  const allocator_type& __a = allocator_type())
112  : _Base(__l, __n, __hf, __eql, __a) { }
113 
114  ~unordered_set() noexcept { }
115 
116  unordered_set&
117  operator=(const unordered_set& __x)
118  {
119  *static_cast<_Base*>(this) = __x;
120  this->_M_invalidate_all();
121  return *this;
122  }
123 
124  unordered_set&
125  operator=(unordered_set&& __x)
126  {
127  // NB: DR 1204.
128  // NB: DR 675.
129  clear();
130  swap(__x);
131  return *this;
132  }
133 
134  unordered_set&
135  operator=(initializer_list<value_type> __l)
136  {
137  this->clear();
138  this->insert(__l);
139  return *this;
140  }
141 
142  void
143  swap(unordered_set& __x)
144  {
145  _Base::swap(__x);
146  _Safe_base::_M_swap(__x);
147  }
148 
149  void
150  clear() noexcept
151  {
152  _Base::clear();
153  this->_M_invalidate_all();
154  }
155 
156  iterator
157  begin() noexcept
158  { return iterator(_Base::begin(), this); }
159 
160  const_iterator
161  begin() const noexcept
162  { return const_iterator(_Base::begin(), this); }
163 
164  iterator
165  end() noexcept
166  { return iterator(_Base::end(), this); }
167 
168  const_iterator
169  end() const noexcept
170  { return const_iterator(_Base::end(), this); }
171 
172  const_iterator
173  cbegin() const noexcept
174  { return const_iterator(_Base::begin(), this); }
175 
176  const_iterator
177  cend() const noexcept
178  { return const_iterator(_Base::end(), this); }
179 
180  // local versions
181  local_iterator
182  begin(size_type __b)
183  { return local_iterator(_Base::begin(__b), __b, this); }
184 
185  local_iterator
186  end(size_type __b)
187  { return local_iterator(_Base::end(__b), __b, this); }
188 
189  const_local_iterator
190  begin(size_type __b) const
191  { return const_local_iterator(_Base::begin(__b), __b, this); }
192 
193  const_local_iterator
194  end(size_type __b) const
195  { return const_local_iterator(_Base::end(__b), __b, this); }
196 
197  const_local_iterator
198  cbegin(size_type __b) const
199  { return const_local_iterator(_Base::cbegin(__b), __b, this); }
200 
201  const_local_iterator
202  cend(size_type __b) const
203  { return const_local_iterator(_Base::cend(__b), __b, this); }
204 
205  template<typename... _Args>
206  std::pair<iterator, bool>
207  emplace(_Args&&... __args)
208  {
209  size_type __bucket_count = this->bucket_count();
210  std::pair<_Base_iterator, bool> __res
211  = _Base::emplace(std::forward<_Args>(__args)...);
212  _M_check_rehashed(__bucket_count);
213  return std::make_pair(iterator(__res.first, this), __res.second);
214  }
215 
216  template<typename... _Args>
217  iterator
218  emplace_hint(const_iterator __hint, _Args&&... __args)
219  {
220  __glibcxx_check_insert(__hint);
221  size_type __bucket_count = this->bucket_count();
222  _Base_iterator __it = _Base::emplace_hint(__hint.base(),
223  std::forward<_Args>(__args)...);
224  _M_check_rehashed(__bucket_count);
225  return iterator(__it, this);
226  }
227 
228  std::pair<iterator, bool>
229  insert(const value_type& __obj)
230  {
231  size_type __bucket_count = this->bucket_count();
232  typedef std::pair<_Base_iterator, bool> __pair_type;
233  __pair_type __res = _Base::insert(__obj);
234  _M_check_rehashed(__bucket_count);
235  return std::make_pair(iterator(__res.first, this), __res.second);
236  }
237 
238  iterator
239  insert(const_iterator __hint, const value_type& __obj)
240  {
241  __glibcxx_check_insert(__hint);
242  size_type __bucket_count = this->bucket_count();
243  _Base_iterator __it = _Base::insert(__hint.base(), __obj);
244  _M_check_rehashed(__bucket_count);
245  return iterator(__it, this);
246  }
247 
248  std::pair<iterator, bool>
249  insert(value_type&& __obj)
250  {
251  size_type __bucket_count = this->bucket_count();
252  typedef std::pair<typename _Base::iterator, bool> __pair_type;
253  __pair_type __res = _Base::insert(std::move(__obj));
254  _M_check_rehashed(__bucket_count);
255  return std::make_pair(iterator(__res.first, this), __res.second);
256  }
257 
258  iterator
259  insert(const_iterator __hint, value_type&& __obj)
260  {
261  __glibcxx_check_insert(__hint);
262  size_type __bucket_count = this->bucket_count();
263  _Base_iterator __it = _Base::insert(__hint.base(), std::move(__obj));
264  _M_check_rehashed(__bucket_count);
265  return iterator(__it, this);
266  }
267 
268  void
269  insert(std::initializer_list<value_type> __l)
270  {
271  size_type __bucket_count = this->bucket_count();
272  _Base::insert(__l);
273  _M_check_rehashed(__bucket_count);
274  }
275 
276  template<typename _InputIterator>
277  void
278  insert(_InputIterator __first, _InputIterator __last)
279  {
280  __glibcxx_check_valid_range(__first, __last);
281  size_type __bucket_count = this->bucket_count();
282  _Base::insert(__gnu_debug::__base(__first),
283  __gnu_debug::__base(__last));
284  _M_check_rehashed(__bucket_count);
285  }
286 
287  iterator
288  find(const key_type& __key)
289  { return iterator(_Base::find(__key), this); }
290 
291  const_iterator
292  find(const key_type& __key) const
293  { return const_iterator(_Base::find(__key), this); }
294 
295  std::pair<iterator, iterator>
296  equal_range(const key_type& __key)
297  {
298  typedef std::pair<_Base_iterator, _Base_iterator> __pair_type;
299  __pair_type __res = _Base::equal_range(__key);
300  return std::make_pair(iterator(__res.first, this),
301  iterator(__res.second, this));
302  }
303 
304  std::pair<const_iterator, const_iterator>
305  equal_range(const key_type& __key) const
306  {
307  std::pair<_Base_const_iterator, _Base_const_iterator>
308  __res = _Base::equal_range(__key);
309  return std::make_pair(const_iterator(__res.first, this),
310  const_iterator(__res.second, this));
311  }
312 
313  size_type
314  erase(const key_type& __key)
315  {
316  size_type __ret(0);
317  _Base_iterator __victim(_Base::find(__key));
318  if (__victim != _Base::end())
319  {
320  this->_M_invalidate_if(
321  [__victim](_Base_const_iterator __it)
322  { return __it == __victim; });
323  _Base_local_iterator __local_victim = _S_to_local(__victim);
324  this->_M_invalidate_local_if(
325  [__local_victim](_Base_const_local_iterator __it)
326  { return __it == __local_victim; });
327  size_type __bucket_count = this->bucket_count();
328  _Base::erase(__victim);
329  _M_check_rehashed(__bucket_count);
330  __ret = 1;
331  }
332  return __ret;
333  }
334 
335  iterator
336  erase(const_iterator __it)
337  {
338  __glibcxx_check_erase(__it);
339  _Base_const_iterator __victim = __it.base();
340  this->_M_invalidate_if(
341  [__victim](_Base_const_iterator __it)
342  { return __it == __victim; });
343  _Base_const_local_iterator __local_victim = _S_to_local(__victim);
344  this->_M_invalidate_local_if(
345  [__local_victim](_Base_const_local_iterator __it)
346  { return __it == __local_victim; });
347  size_type __bucket_count = this->bucket_count();
348  _Base_iterator __next = _Base::erase(__it.base());
349  _M_check_rehashed(__bucket_count);
350  return iterator(__next, this);
351  }
352 
353  iterator
354  erase(iterator __it)
355  { return erase(const_iterator(__it)); }
356 
357  iterator
358  erase(const_iterator __first, const_iterator __last)
359  {
360  __glibcxx_check_erase_range(__first, __last);
361  for (_Base_const_iterator __tmp = __first.base();
362  __tmp != __last.base(); ++__tmp)
363  {
364  _GLIBCXX_DEBUG_VERIFY(__tmp != _Base::end(),
365  _M_message(__gnu_debug::__msg_valid_range)
366  ._M_iterator(__first, "first")
367  ._M_iterator(__last, "last"));
368  this->_M_invalidate_if(
369  [__tmp](_Base_const_iterator __it)
370  { return __it == __tmp; });
371  _Base_const_local_iterator __local_tmp = _S_to_local(__tmp);
372  this->_M_invalidate_local_if(
373  [__local_tmp](_Base_const_local_iterator __it)
374  { return __it == __local_tmp; });
375  }
376  size_type __bucket_count = this->bucket_count();
377  _Base_iterator __next = _Base::erase(__first.base(),
378  __last.base());
379  _M_check_rehashed(__bucket_count);
380  return iterator(__next, this);
381  }
382 
383  _Base&
384  _M_base() noexcept { return *this; }
385 
386  const _Base&
387  _M_base() const noexcept { return *this; }
388 
389  private:
390  void
391  _M_invalidate_locals()
392  {
393  _Base_local_iterator __local_end = _Base::end(0);
394  this->_M_invalidate_local_if(
395  [__local_end](_Base_const_local_iterator __it)
396  { return __it != __local_end; });
397  }
398 
399  void
400  _M_invalidate_all()
401  {
402  _Base_iterator __end = _Base::end();
403  this->_M_invalidate_if(
404  [__end](_Base_const_iterator __it)
405  { return __it != __end; });
406  _M_invalidate_locals();
407  }
408 
409  void
410  _M_check_rehashed(size_type __prev_count)
411  {
412  if (__prev_count != this->bucket_count())
413  _M_invalidate_locals();
414  }
415 
416  static _Base_local_iterator
417  _S_to_local(_Base_iterator __it)
418  {
419  // The returned local iterator will not be incremented so we don't
420  // need to compute __it's node bucket
421  return _Base_local_iterator(__it._M_cur, 0, 0);
422  }
423 
424  static _Base_const_local_iterator
425  _S_to_local(_Base_const_iterator __it)
426  {
427  // The returned local iterator will not be incremented so we don't
428  // need to compute __it's node bucket
429  return _Base_const_local_iterator(__it._M_cur, 0, 0);
430  }
431  };
432 
433  template<typename _Value, typename _Hash, typename _Pred, typename _Alloc>
434  inline void
435  swap(unordered_set<_Value, _Hash, _Pred, _Alloc>& __x,
436  unordered_set<_Value, _Hash, _Pred, _Alloc>& __y)
437  { __x.swap(__y); }
438 
439  template<typename _Value, typename _Hash, typename _Pred, typename _Alloc>
440  inline bool
441  operator==(const unordered_set<_Value, _Hash, _Pred, _Alloc>& __x,
442  const unordered_set<_Value, _Hash, _Pred, _Alloc>& __y)
443  { return __x._M_equal(__y); }
444 
445  template<typename _Value, typename _Hash, typename _Pred, typename _Alloc>
446  inline bool
447  operator!=(const unordered_set<_Value, _Hash, _Pred, _Alloc>& __x,
448  const unordered_set<_Value, _Hash, _Pred, _Alloc>& __y)
449  { return !(__x == __y); }
450 
451 
452  /// Class std::unordered_multiset with safety/checking/debug instrumentation.
453  template<typename _Value,
454  typename _Hash = std::hash<_Value>,
455  typename _Pred = std::equal_to<_Value>,
456  typename _Alloc = std::allocator<_Value> >
457  class unordered_multiset
458  : public _GLIBCXX_STD_C::unordered_multiset<_Value, _Hash, _Pred, _Alloc>,
459  public __gnu_debug::_Safe_unordered_container<
460  unordered_multiset<_Value, _Hash, _Pred, _Alloc> >
461  {
462  typedef _GLIBCXX_STD_C::unordered_multiset<_Value, _Hash,
463  _Pred, _Alloc> _Base;
464  typedef __gnu_debug::_Safe_unordered_container<unordered_multiset>
465  _Safe_base;
466  typedef typename _Base::const_iterator _Base_const_iterator;
467  typedef typename _Base::iterator _Base_iterator;
468  typedef typename _Base::const_local_iterator _Base_const_local_iterator;
469  typedef typename _Base::local_iterator _Base_local_iterator;
470 
471  public:
472  typedef typename _Base::size_type size_type;
473  typedef typename _Base::hasher hasher;
474  typedef typename _Base::key_equal key_equal;
475  typedef typename _Base::allocator_type allocator_type;
476 
477  typedef typename _Base::key_type key_type;
478  typedef typename _Base::value_type value_type;
479 
480  typedef __gnu_debug::_Safe_iterator<_Base_iterator,
481  unordered_multiset> iterator;
482  typedef __gnu_debug::_Safe_iterator<_Base_const_iterator,
483  unordered_multiset> const_iterator;
484  typedef __gnu_debug::_Safe_local_iterator<
485  _Base_local_iterator, unordered_multiset> local_iterator;
486  typedef __gnu_debug::_Safe_local_iterator<
487  _Base_const_local_iterator, unordered_multiset> const_local_iterator;
488 
489  explicit
490  unordered_multiset(size_type __n = 10,
491  const hasher& __hf = hasher(),
492  const key_equal& __eql = key_equal(),
493  const allocator_type& __a = allocator_type())
494  : _Base(__n, __hf, __eql, __a) { }
495 
496  template<typename _InputIterator>
497  unordered_multiset(_InputIterator __first, _InputIterator __last,
498  size_type __n = 0,
499  const hasher& __hf = hasher(),
500  const key_equal& __eql = key_equal(),
501  const allocator_type& __a = allocator_type())
502  : _Base(__gnu_debug::__base(__gnu_debug::__check_valid_range(__first,
503  __last)),
504  __gnu_debug::__base(__last), __n,
505  __hf, __eql, __a) { }
506 
507  unordered_multiset(const unordered_multiset& __x) = default;
508 
509  unordered_multiset(const _Base& __x)
510  : _Base(__x) { }
511 
512  unordered_multiset(unordered_multiset&& __x) = default;
513 
514  unordered_multiset(initializer_list<value_type> __l,
515  size_type __n = 0,
516  const hasher& __hf = hasher(),
517  const key_equal& __eql = key_equal(),
518  const allocator_type& __a = allocator_type())
519  : _Base(__l, __n, __hf, __eql, __a) { }
520 
521  ~unordered_multiset() noexcept { }
522 
523  unordered_multiset&
524  operator=(const unordered_multiset& __x)
525  {
526  *static_cast<_Base*>(this) = __x;
527  this->_M_invalidate_all();
528  return *this;
529  }
530 
531  unordered_multiset&
532  operator=(unordered_multiset&& __x)
533  {
534  // NB: DR 1204.
535  // NB: DR 675.
536  clear();
537  swap(__x);
538  return *this;
539  }
540 
541  unordered_multiset&
542  operator=(initializer_list<value_type> __l)
543  {
544  this->clear();
545  this->insert(__l);
546  return *this;
547  }
548 
549  void
550  swap(unordered_multiset& __x)
551  {
552  _Base::swap(__x);
553  _Safe_base::_M_swap(__x);
554  }
555 
556  void
557  clear() noexcept
558  {
559  _Base::clear();
560  this->_M_invalidate_all();
561  }
562 
563  iterator
564  begin() noexcept
565  { return iterator(_Base::begin(), this); }
566 
567  const_iterator
568  begin() const noexcept
569  { return const_iterator(_Base::begin(), this); }
570 
571  iterator
572  end() noexcept
573  { return iterator(_Base::end(), this); }
574 
575  const_iterator
576  end() const noexcept
577  { return const_iterator(_Base::end(), this); }
578 
579  const_iterator
580  cbegin() const noexcept
581  { return const_iterator(_Base::begin(), this); }
582 
583  const_iterator
584  cend() const noexcept
585  { return const_iterator(_Base::end(), this); }
586 
587  // local versions
588  local_iterator
589  begin(size_type __b)
590  { return local_iterator(_Base::begin(__b), __b, this); }
591 
592  local_iterator
593  end(size_type __b)
594  { return local_iterator(_Base::end(__b), __b, this); }
595 
596  const_local_iterator
597  begin(size_type __b) const
598  { return const_local_iterator(_Base::begin(__b), __b, this); }
599 
600  const_local_iterator
601  end(size_type __b) const
602  { return const_local_iterator(_Base::end(__b), __b, this); }
603 
604  const_local_iterator
605  cbegin(size_type __b) const
606  { return const_local_iterator(_Base::cbegin(__b), __b, this); }
607 
608  const_local_iterator
609  cend(size_type __b) const
610  { return const_local_iterator(_Base::cend(__b), __b, this); }
611 
612  template<typename... _Args>
613  iterator
614  emplace(_Args&&... __args)
615  {
616  size_type __bucket_count = this->bucket_count();
617  _Base_iterator __it
618  = _Base::emplace(std::forward<_Args>(__args)...);
619  _M_check_rehashed(__bucket_count);
620  return iterator(__it, this);
621  }
622 
623  template<typename... _Args>
624  iterator
625  emplace_hint(const_iterator __hint, _Args&&... __args)
626  {
627  __glibcxx_check_insert(__hint);
628  size_type __bucket_count = this->bucket_count();
629  _Base_iterator __it = _Base::emplace_hint(__hint.base(),
630  std::forward<_Args>(__args)...);
631  _M_check_rehashed(__bucket_count);
632  return iterator(__it, this);
633  }
634 
635  iterator
636  insert(const value_type& __obj)
637  {
638  size_type __bucket_count = this->bucket_count();
639  _Base_iterator __it = _Base::insert(__obj);
640  _M_check_rehashed(__bucket_count);
641  return iterator(__it, this);
642  }
643 
644  iterator
645  insert(const_iterator __hint, const value_type& __obj)
646  {
647  __glibcxx_check_insert(__hint);
648  size_type __bucket_count = this->bucket_count();
649  _Base_iterator __it = _Base::insert(__hint.base(), __obj);
650  _M_check_rehashed(__bucket_count);
651  return iterator(__it, this);
652  }
653 
654  iterator
655  insert(value_type&& __obj)
656  {
657  size_type __bucket_count = this->bucket_count();
658  _Base_iterator __it = _Base::insert(std::move(__obj));
659  _M_check_rehashed(__bucket_count);
660  return iterator(__it, this);
661  }
662 
663  iterator
664  insert(const_iterator __hint, value_type&& __obj)
665  {
666  __glibcxx_check_insert(__hint);
667  size_type __bucket_count = this->bucket_count();
668  _Base_iterator __it = _Base::insert(__hint.base(), std::move(__obj));
669  _M_check_rehashed(__bucket_count);
670  return iterator(__it, this);
671  }
672 
673  void
674  insert(std::initializer_list<value_type> __l)
675  {
676  size_type __bucket_count = this->bucket_count();
677  _Base::insert(__l);
678  _M_check_rehashed(__bucket_count);
679  }
680 
681  template<typename _InputIterator>
682  void
683  insert(_InputIterator __first, _InputIterator __last)
684  {
685  __glibcxx_check_valid_range(__first, __last);
686  size_type __bucket_count = this->bucket_count();
687  _Base::insert(__gnu_debug::__base(__first),
688  __gnu_debug::__base(__last));
689  _M_check_rehashed(__bucket_count);
690  }
691 
692  iterator
693  find(const key_type& __key)
694  { return iterator(_Base::find(__key), this); }
695 
696  const_iterator
697  find(const key_type& __key) const
698  { return const_iterator(_Base::find(__key), this); }
699 
700  std::pair<iterator, iterator>
701  equal_range(const key_type& __key)
702  {
703  typedef std::pair<_Base_iterator, _Base_iterator> __pair_type;
704  __pair_type __res = _Base::equal_range(__key);
705  return std::make_pair(iterator(__res.first, this),
706  iterator(__res.second, this));
707  }
708 
709  std::pair<const_iterator, const_iterator>
710  equal_range(const key_type& __key) const
711  {
712  std::pair<_Base_const_iterator, _Base_const_iterator>
713  __res = _Base::equal_range(__key);
714  return std::make_pair(const_iterator(__res.first, this),
715  const_iterator(__res.second, this));
716  }
717 
718  size_type
719  erase(const key_type& __key)
720  {
721  size_type __ret(0);
722  std::pair<_Base_iterator, _Base_iterator> __pair =
723  _Base::equal_range(__key);
724  for (_Base_iterator __victim = __pair.first; __victim != __pair.second;)
725  {
726  this->_M_invalidate_if([__victim](_Base_const_iterator __it)
727  { return __it == __victim; });
728  _Base_local_iterator __local_victim = _S_to_local(__victim);
729  this->_M_invalidate_local_if(
730  [__local_victim](_Base_const_local_iterator __it)
731  { return __it == __local_victim; });
732  _Base::erase(__victim++);
733  ++__ret;
734  }
735  return __ret;
736  }
737 
738  iterator
739  erase(const_iterator __it)
740  {
741  __glibcxx_check_erase(__it);
742  _Base_const_iterator __victim = __it.base();
743  this->_M_invalidate_if([__victim](_Base_const_iterator __it)
744  { return __it == __victim; });
745  _Base_const_local_iterator __local_victim = _S_to_local(__victim);
746  this->_M_invalidate_local_if(
747  [__local_victim](_Base_const_local_iterator __it)
748  { return __it == __local_victim; });
749  return iterator(_Base::erase(__it.base()), this);
750  }
751 
752  iterator
753  erase(iterator __it)
754  { return erase(const_iterator(__it)); }
755 
756  iterator
757  erase(const_iterator __first, const_iterator __last)
758  {
759  __glibcxx_check_erase_range(__first, __last);
760  for (_Base_const_iterator __tmp = __first.base();
761  __tmp != __last.base(); ++__tmp)
762  {
763  _GLIBCXX_DEBUG_VERIFY(__tmp != _Base::end(),
764  _M_message(__gnu_debug::__msg_valid_range)
765  ._M_iterator(__first, "first")
766  ._M_iterator(__last, "last"));
767  this->_M_invalidate_if([__tmp](_Base_const_iterator __it)
768  { return __it == __tmp; });
769  _Base_const_local_iterator __local_tmp = _S_to_local(__tmp);
770  this->_M_invalidate_local_if(
771  [__local_tmp](_Base_const_local_iterator __it)
772  { return __it == __local_tmp; });
773  }
774  return iterator(_Base::erase(__first.base(),
775  __last.base()), this);
776  }
777 
778  _Base&
779  _M_base() noexcept { return *this; }
780 
781  const _Base&
782  _M_base() const noexcept { return *this; }
783 
784  private:
785  void
786  _M_invalidate_locals()
787  {
788  _Base_local_iterator __local_end = _Base::end(0);
789  this->_M_invalidate_local_if(
790  [__local_end](_Base_const_local_iterator __it)
791  { return __it != __local_end; });
792  }
793 
794  void
795  _M_invalidate_all()
796  {
797  _Base_iterator __end = _Base::end();
798  this->_M_invalidate_if([__end](_Base_const_iterator __it)
799  { return __it != __end; });
800  _M_invalidate_locals();
801  }
802 
803  void
804  _M_check_rehashed(size_type __prev_count)
805  {
806  if (__prev_count != this->bucket_count())
807  _M_invalidate_locals();
808  }
809 
810  static _Base_local_iterator
811  _S_to_local(_Base_iterator __it)
812  {
813  // The returned local iterator will not be incremented so we don't
814  // need to compute __it's node bucket
815  return _Base_local_iterator(__it._M_cur, 0, 0);
816  }
817 
818  static _Base_const_local_iterator
819  _S_to_local(_Base_const_iterator __it)
820  {
821  // The returned local iterator will not be incremented so we don't
822  // need to compute __it's node bucket
823  return _Base_const_local_iterator(__it._M_cur, 0, 0);
824  }
825  };
826 
827  template<typename _Value, typename _Hash, typename _Pred, typename _Alloc>
828  inline void
829  swap(unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x,
830  unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y)
831  { __x.swap(__y); }
832 
833  template<typename _Value, typename _Hash, typename _Pred, typename _Alloc>
834  inline bool
835  operator==(const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x,
836  const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y)
837  { return __x._M_equal(__y); }
838 
839  template<typename _Value, typename _Hash, typename _Pred, typename _Alloc>
840  inline bool
841  operator!=(const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x,
842  const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y)
843  { return !(__x == __y); }
844 
845 } // namespace __debug
846 } // namespace std
847 
848 #endif // __GXX_EXPERIMENTAL_CXX0X__
849 
850 #endif
std::initializer_list
initializer_list
Definition: initializer_list:47
__gnu_debug::__base
_Siter_base< _Iterator >::iterator_type __base(_Iterator __it)
Definition: safe_iterator.h:743
std::pair::first
_T1 first
second_type is the second bound type
Definition: stl_pair.h:93
__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
std::pair::second
_T2 second
first is a copy of the first object
Definition: stl_pair.h:94
std::allocator
The standard allocator, as per [20.4].
Definition: bits/alloc_traits.h:43
__glibcxx_check_erase_range
#define __glibcxx_check_erase_range(_First, _Last)
Definition: macros.h:164
__gnu_debug::_Safe_iterator::base
_Iterator base() const
Return the underlying iterator.
Definition: safe_iterator.h:395
__glibcxx_check_erase
#define __glibcxx_check_erase(_Position)
Definition: macros.h:136
std::equal_to
One of the comparison functors.
Definition: stl_function.h:206
std::unordered_set
A standard container composed of unique keys (containing at most one of each key value) in which the ...
Definition: unordered_set.h:281
__gnu_debug::_Safe_unordered_container_base::_M_swap
void _M_swap(_Safe_unordered_container_base &__x)
__gnu_debug::_Safe_local_iterator
Safe iterator wrapper.
Definition: formatter.h:50
__gnu_debug::_Safe_sequence_base
Base class that supports tracking of iterators that reference a sequence.
Definition: safe_base.h:178
std::__debug::unordered_set
Class std::unordered_set with safety/checking/debug instrumentation.
Definition: debug/unordered_set:51
std::unordered_multiset
A standard container composed of equivalent keys (possibly containing multiple of each key value) in ...
Definition: unordered_set.h:346
__glibcxx_check_insert
#define __glibcxx_check_insert(_Position)
Definition: macros.h:74
std::pair
Struct holding two objects of arbitrary type.
Definition: stl_pair.h:88
std::__debug::unordered_multiset
Class std::unordered_multiset with safety/checking/debug instrumentation.
Definition: debug/unordered_set:457
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:268
std::hash
Primary class template hash.
Definition: system_error:112
__gnu_debug::_Safe_iterator
Safe iterator wrapper.
Definition: formatter.h:47