libstdc++
debug/unordered_map
Go to the documentation of this file.
1 // Debugging unordered_map/unordered_multimap 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_map
27  * This file is a GNU debug extension to the Standard C++ Library.
28  */
29 
30 #ifndef _GLIBCXX_DEBUG_UNORDERED_MAP
31 #define _GLIBCXX_DEBUG_UNORDERED_MAP 1
32 
33 #ifndef __GXX_EXPERIMENTAL_CXX0X__
34 # include <bits/c++0x_warning.h>
35 #else
36 # include <unordered_map>
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_map with safety/checking/debug instrumentation.
47  template<typename _Key, typename _Tp,
48  typename _Hash = std::hash<_Key>,
49  typename _Pred = std::equal_to<_Key>,
50  typename _Alloc = std::allocator<_Key> >
51  class unordered_map
52  : public _GLIBCXX_STD_C::unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>,
53  public __gnu_debug::_Safe_unordered_container<unordered_map<_Key, _Tp,
54  _Hash, _Pred, _Alloc> >
55  {
56  typedef _GLIBCXX_STD_C::unordered_map<_Key, _Tp, _Hash,
57  _Pred, _Alloc> _Base;
58  typedef __gnu_debug::_Safe_unordered_container<unordered_map> _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_map> iterator;
75  typedef __gnu_debug::_Safe_iterator<_Base_const_iterator,
76  unordered_map> const_iterator;
77  typedef __gnu_debug::_Safe_local_iterator<_Base_local_iterator,
78  unordered_map> local_iterator;
79  typedef __gnu_debug::_Safe_local_iterator<_Base_const_local_iterator,
80  unordered_map> const_local_iterator;
81 
82  explicit
83  unordered_map(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_map(_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_map(const unordered_map& __x) = default;
101 
102  unordered_map(const _Base& __x)
103  : _Base(__x) { }
104 
105  unordered_map(unordered_map&& __x) = default;
106 
107  unordered_map(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_map() noexcept { }
115 
116  unordered_map&
117  operator=(const unordered_map& __x)
118  {
119  *static_cast<_Base*>(this) = __x;
120  this->_M_invalidate_all();
121  return *this;
122  }
123 
124  unordered_map&
125  operator=(unordered_map&& __x)
126  {
127  // NB: DR 1204.
128  // NB: DR 675.
129  clear();
130  swap(__x);
131  return *this;
132  }
133 
134  unordered_map&
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_map& __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  std::pair<_Base_iterator, bool> __res = _Base::insert(__obj);
233  _M_check_rehashed(__bucket_count);
234  return std::make_pair(iterator(__res.first, this), __res.second);
235  }
236 
237  iterator
238  insert(const_iterator __hint, const value_type& __obj)
239  {
240  __glibcxx_check_insert(__hint);
241  size_type __bucket_count = this->bucket_count();
242  _Base_iterator __it = _Base::insert(__hint.base(), __obj);
243  _M_check_rehashed(__bucket_count);
244  return iterator(__it, this);
245  }
246 
247  template<typename _Pair, typename = typename
248  std::enable_if<std::is_constructible<value_type,
249  _Pair&&>::value>::type>
250  std::pair<iterator, bool>
251  insert(_Pair&& __obj)
252  {
253  size_type __bucket_count = this->bucket_count();
254  std::pair<_Base_iterator, bool> __res =
255  _Base::insert(std::forward<_Pair>(__obj));
256  _M_check_rehashed(__bucket_count);
257  return std::make_pair(iterator(__res.first, this), __res.second);
258  }
259 
260  template<typename _Pair, typename = typename
261  std::enable_if<std::is_constructible<value_type,
262  _Pair&&>::value>::type>
263  iterator
264  insert(const_iterator __hint, _Pair&& __obj)
265  {
266  __glibcxx_check_insert(__hint);
267  size_type __bucket_count = this->bucket_count();
268  _Base_iterator __it =
269  _Base::insert(__hint.base(), std::forward<_Pair>(__obj));
270  _M_check_rehashed(__bucket_count);
271  return iterator(__it, this);
272  }
273 
274  void
275  insert(std::initializer_list<value_type> __l)
276  {
277  size_type __bucket_count = this->bucket_count();
278  _Base::insert(__l);
279  _M_check_rehashed(__bucket_count);
280  }
281 
282  template<typename _InputIterator>
283  void
284  insert(_InputIterator __first, _InputIterator __last)
285  {
286  __glibcxx_check_valid_range(__first, __last);
287  size_type __bucket_count = this->bucket_count();
288  _Base::insert(__gnu_debug::__base(__first),
289  __gnu_debug::__base(__last));
290  _M_check_rehashed(__bucket_count);
291  }
292 
293  iterator
294  find(const key_type& __key)
295  { return iterator(_Base::find(__key), this); }
296 
297  const_iterator
298  find(const key_type& __key) const
299  { return const_iterator(_Base::find(__key), this); }
300 
301  std::pair<iterator, iterator>
302  equal_range(const key_type& __key)
303  {
304  std::pair<_Base_iterator, _Base_iterator> __res =
305  _Base::equal_range(__key);
306  return std::make_pair(iterator(__res.first, this),
307  iterator(__res.second, this));
308  }
309 
310  std::pair<const_iterator, const_iterator>
311  equal_range(const key_type& __key) const
312  {
313  std::pair<_Base_const_iterator, _Base_const_iterator> __res =
314  _Base::equal_range(__key);
315  return std::make_pair(const_iterator(__res.first, this),
316  const_iterator(__res.second, this));
317  }
318 
319  size_type
320  erase(const key_type& __key)
321  {
322  size_type __ret(0);
323  _Base_iterator __victim(_Base::find(__key));
324  if (__victim != _Base::end())
325  {
326  this->_M_invalidate_if([__victim](_Base_const_iterator __it)
327  { return __it == __victim; });
328  _Base_local_iterator __local_victim = _S_to_local(__victim);
329  this->_M_invalidate_local_if(
330  [__local_victim](_Base_const_local_iterator __it)
331  { return __it == __local_victim; });
332  size_type __bucket_count = this->bucket_count();
333  _Base::erase(__victim);
334  _M_check_rehashed(__bucket_count);
335  __ret = 1;
336  }
337  return __ret;
338  }
339 
340  iterator
341  erase(const_iterator __it)
342  {
343  __glibcxx_check_erase(__it);
344  _Base_const_iterator __victim = __it.base();
345  this->_M_invalidate_if([__victim](_Base_const_iterator __it)
346  { return __it == __victim; });
347  _Base_const_local_iterator __local_victim = _S_to_local(__victim);
348  this->_M_invalidate_local_if(
349  [__local_victim](_Base_const_local_iterator __it)
350  { return __it == __local_victim; });
351  size_type __bucket_count = this->bucket_count();
352  _Base_iterator __next = _Base::erase(__it.base());
353  _M_check_rehashed(__bucket_count);
354  return iterator(__next, this);
355  }
356 
357  iterator
358  erase(iterator __it)
359  { return erase(const_iterator(__it)); }
360 
361  iterator
362  erase(const_iterator __first, const_iterator __last)
363  {
364  __glibcxx_check_erase_range(__first, __last);
365  for (_Base_const_iterator __tmp = __first.base();
366  __tmp != __last.base(); ++__tmp)
367  {
368  _GLIBCXX_DEBUG_VERIFY(__tmp != _Base::end(),
369  _M_message(__gnu_debug::__msg_valid_range)
370  ._M_iterator(__first, "first")
371  ._M_iterator(__last, "last"));
372  this->_M_invalidate_if([__tmp](_Base_const_iterator __it)
373  { return __it == __tmp; });
374  _Base_const_local_iterator __local_tmp = _S_to_local(__tmp);
375  this->_M_invalidate_local_if(
376  [__local_tmp](_Base_const_local_iterator __it)
377  { return __it == __local_tmp; });
378  }
379  size_type __bucket_count = this->bucket_count();
380  _Base_iterator __next = _Base::erase(__first.base(), __last.base());
381  _M_check_rehashed(__bucket_count);
382  return iterator(__next, this);
383  }
384 
385  _Base&
386  _M_base() noexcept { return *this; }
387 
388  const _Base&
389  _M_base() const noexcept { return *this; }
390 
391  private:
392  void
393  _M_invalidate_locals()
394  {
395  _Base_local_iterator __local_end = _Base::end(0);
396  this->_M_invalidate_local_if(
397  [__local_end](_Base_const_local_iterator __it)
398  { return __it != __local_end; });
399  }
400 
401  void
402  _M_invalidate_all()
403  {
404  _Base_iterator __end = _Base::end();
405  this->_M_invalidate_if([__end](_Base_const_iterator __it)
406  { return __it != __end; });
407  _M_invalidate_locals();
408  }
409 
410  void
411  _M_check_rehashed(size_type __prev_count)
412  {
413  if (__prev_count != this->bucket_count())
414  _M_invalidate_locals();
415  }
416 
417  static _Base_local_iterator
418  _S_to_local(_Base_iterator __it)
419  {
420  // The returned local iterator will not be incremented so we don't
421  // need to compute __it's node bucket
422  return _Base_local_iterator(__it._M_cur, 0, 0);
423  }
424 
425  static _Base_const_local_iterator
426  _S_to_local(_Base_const_iterator __it)
427  {
428  // The returned local iterator will not be incremented so we don't
429  // need to compute __it's node bucket
430  return _Base_const_local_iterator(__it._M_cur, 0, 0);
431  }
432  };
433 
434  template<typename _Key, typename _Tp, typename _Hash,
435  typename _Pred, typename _Alloc>
436  inline void
437  swap(unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
438  unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
439  { __x.swap(__y); }
440 
441  template<typename _Key, typename _Tp, typename _Hash,
442  typename _Pred, typename _Alloc>
443  inline bool
444  operator==(const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
445  const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
446  { return __x._M_equal(__y); }
447 
448  template<typename _Key, typename _Tp, typename _Hash,
449  typename _Pred, typename _Alloc>
450  inline bool
451  operator!=(const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
452  const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
453  { return !(__x == __y); }
454 
455 
456  /// Class std::unordered_multimap with safety/checking/debug instrumentation.
457  template<typename _Key, typename _Tp,
458  typename _Hash = std::hash<_Key>,
459  typename _Pred = std::equal_to<_Key>,
460  typename _Alloc = std::allocator<_Key> >
461  class unordered_multimap
462  : public _GLIBCXX_STD_C::unordered_multimap<_Key, _Tp, _Hash,
463  _Pred, _Alloc>,
464  public __gnu_debug::_Safe_unordered_container<unordered_multimap<_Key,
465  _Tp, _Hash, _Pred, _Alloc> >
466  {
467  typedef _GLIBCXX_STD_C::unordered_multimap<_Key, _Tp, _Hash,
468  _Pred, _Alloc> _Base;
469  typedef __gnu_debug::_Safe_unordered_container<unordered_multimap>
470  _Safe_base;
471  typedef typename _Base::const_iterator _Base_const_iterator;
472  typedef typename _Base::iterator _Base_iterator;
473  typedef typename _Base::const_local_iterator _Base_const_local_iterator;
474  typedef typename _Base::local_iterator _Base_local_iterator;
475 
476  public:
477  typedef typename _Base::size_type size_type;
478  typedef typename _Base::hasher hasher;
479  typedef typename _Base::key_equal key_equal;
480  typedef typename _Base::allocator_type allocator_type;
481 
482  typedef typename _Base::key_type key_type;
483  typedef typename _Base::value_type value_type;
484 
485  typedef __gnu_debug::_Safe_iterator<_Base_iterator,
486  unordered_multimap> iterator;
487  typedef __gnu_debug::_Safe_iterator<_Base_const_iterator,
488  unordered_multimap> const_iterator;
489  typedef __gnu_debug::_Safe_local_iterator<
490  _Base_local_iterator, unordered_multimap> local_iterator;
491  typedef __gnu_debug::_Safe_local_iterator<
492  _Base_const_local_iterator, unordered_multimap> const_local_iterator;
493 
494  explicit
495  unordered_multimap(size_type __n = 10,
496  const hasher& __hf = hasher(),
497  const key_equal& __eql = key_equal(),
498  const allocator_type& __a = allocator_type())
499  : _Base(__n, __hf, __eql, __a) { }
500 
501  template<typename _InputIterator>
502  unordered_multimap(_InputIterator __first, _InputIterator __last,
503  size_type __n = 0,
504  const hasher& __hf = hasher(),
505  const key_equal& __eql = key_equal(),
506  const allocator_type& __a = allocator_type())
507  : _Base(__gnu_debug::__base(__gnu_debug::__check_valid_range(__first,
508  __last)),
509  __gnu_debug::__base(__last), __n,
510  __hf, __eql, __a) { }
511 
512  unordered_multimap(const unordered_multimap& __x) = default;
513 
514  unordered_multimap(const _Base& __x)
515  : _Base(__x) { }
516 
517  unordered_multimap(unordered_multimap&& __x) = default;
518 
519  unordered_multimap(initializer_list<value_type> __l,
520  size_type __n = 0,
521  const hasher& __hf = hasher(),
522  const key_equal& __eql = key_equal(),
523  const allocator_type& __a = allocator_type())
524  : _Base(__l, __n, __hf, __eql, __a) { }
525 
526  ~unordered_multimap() noexcept { }
527 
528  unordered_multimap&
529  operator=(const unordered_multimap& __x)
530  {
531  *static_cast<_Base*>(this) = __x;
532  this->_M_invalidate_all();
533  return *this;
534  }
535 
536  unordered_multimap&
537  operator=(unordered_multimap&& __x)
538  {
539  // NB: DR 1204.
540  // NB: DR 675.
541  clear();
542  swap(__x);
543  return *this;
544  }
545 
546  unordered_multimap&
547  operator=(initializer_list<value_type> __l)
548  {
549  this->clear();
550  this->insert(__l);
551  return *this;
552  }
553 
554  void
555  swap(unordered_multimap& __x)
556  {
557  _Base::swap(__x);
558  _Safe_base::_M_swap(__x);
559  }
560 
561  void
562  clear() noexcept
563  {
564  _Base::clear();
565  this->_M_invalidate_all();
566  }
567 
568  iterator
569  begin() noexcept
570  { return iterator(_Base::begin(), this); }
571 
572  const_iterator
573  begin() const noexcept
574  { return const_iterator(_Base::begin(), this); }
575 
576  iterator
577  end() noexcept
578  { return iterator(_Base::end(), this); }
579 
580  const_iterator
581  end() const noexcept
582  { return const_iterator(_Base::end(), this); }
583 
584  const_iterator
585  cbegin() const noexcept
586  { return const_iterator(_Base::begin(), this); }
587 
588  const_iterator
589  cend() const noexcept
590  { return const_iterator(_Base::end(), this); }
591 
592  // local versions
593  local_iterator
594  begin(size_type __b)
595  { return local_iterator(_Base::begin(__b), __b, this); }
596 
597  local_iterator
598  end(size_type __b)
599  { return local_iterator(_Base::end(__b), __b, this); }
600 
601  const_local_iterator
602  begin(size_type __b) const
603  { return const_local_iterator(_Base::begin(__b), __b, this); }
604 
605  const_local_iterator
606  end(size_type __b) const
607  { return const_local_iterator(_Base::end(__b), __b, this); }
608 
609  const_local_iterator
610  cbegin(size_type __b) const
611  { return const_local_iterator(_Base::cbegin(__b), __b, this); }
612 
613  const_local_iterator
614  cend(size_type __b) const
615  { return const_local_iterator(_Base::cend(__b), __b, this); }
616 
617  template<typename... _Args>
618  iterator
619  emplace(_Args&&... __args)
620  {
621  size_type __bucket_count = this->bucket_count();
622  _Base_iterator __it
623  = _Base::emplace(std::forward<_Args>(__args)...);
624  _M_check_rehashed(__bucket_count);
625  return iterator(__it, this);
626  }
627 
628  template<typename... _Args>
629  iterator
630  emplace_hint(const_iterator __hint, _Args&&... __args)
631  {
632  __glibcxx_check_insert(__hint);
633  size_type __bucket_count = this->bucket_count();
634  _Base_iterator __it = _Base::emplace_hint(__hint.base(),
635  std::forward<_Args>(__args)...);
636  _M_check_rehashed(__bucket_count);
637  return iterator(__it, this);
638  }
639 
640  iterator
641  insert(const value_type& __obj)
642  {
643  size_type __bucket_count = this->bucket_count();
644  _Base_iterator __it = _Base::insert(__obj);
645  _M_check_rehashed(__bucket_count);
646  return iterator(__it, this);
647  }
648 
649  iterator
650  insert(const_iterator __hint, const value_type& __obj)
651  {
652  __glibcxx_check_insert(__hint);
653  size_type __bucket_count = this->bucket_count();
654  _Base_iterator __it = _Base::insert(__hint.base(), __obj);
655  _M_check_rehashed(__bucket_count);
656  return iterator(__it, this);
657  }
658 
659  template<typename _Pair, typename = typename
660  std::enable_if<std::is_constructible<value_type,
661  _Pair&&>::value>::type>
662  iterator
663  insert(_Pair&& __obj)
664  {
665  size_type __bucket_count = this->bucket_count();
666  _Base_iterator __it = _Base::insert(std::forward<_Pair>(__obj));
667  _M_check_rehashed(__bucket_count);
668  return iterator(__it, this);
669  }
670 
671  template<typename _Pair, typename = typename
672  std::enable_if<std::is_constructible<value_type,
673  _Pair&&>::value>::type>
674  iterator
675  insert(const_iterator __hint, _Pair&& __obj)
676  {
677  __glibcxx_check_insert(__hint);
678  size_type __bucket_count = this->bucket_count();
679  _Base_iterator __it =
680  _Base::insert(__hint.base(), std::forward<_Pair>(__obj));
681  _M_check_rehashed(__bucket_count);
682  return iterator(__it, this);
683  }
684 
685  void
686  insert(std::initializer_list<value_type> __l)
687  { _Base::insert(__l); }
688 
689  template<typename _InputIterator>
690  void
691  insert(_InputIterator __first, _InputIterator __last)
692  {
693  __glibcxx_check_valid_range(__first, __last);
694  size_type __bucket_count = this->bucket_count();
695  _Base::insert(__gnu_debug::__base(__first),
696  __gnu_debug::__base(__last));
697  _M_check_rehashed(__bucket_count);
698  }
699 
700  iterator
701  find(const key_type& __key)
702  { return iterator(_Base::find(__key), this); }
703 
704  const_iterator
705  find(const key_type& __key) const
706  { return const_iterator(_Base::find(__key), this); }
707 
708  std::pair<iterator, iterator>
709  equal_range(const key_type& __key)
710  {
711  std::pair<_Base_iterator, _Base_iterator> __res =
712  _Base::equal_range(__key);
713  return std::make_pair(iterator(__res.first, this),
714  iterator(__res.second, this));
715  }
716 
717  std::pair<const_iterator, const_iterator>
718  equal_range(const key_type& __key) const
719  {
720  std::pair<_Base_const_iterator, _Base_const_iterator> __res =
721  _Base::equal_range(__key);
722  return std::make_pair(const_iterator(__res.first, this),
723  const_iterator(__res.second, this));
724  }
725 
726  size_type
727  erase(const key_type& __key)
728  {
729  size_type __ret(0);
730  size_type __bucket_count = this->bucket_count();
731  std::pair<_Base_iterator, _Base_iterator> __pair =
732  _Base::equal_range(__key);
733  for (_Base_iterator __victim = __pair.first; __victim != __pair.second;)
734  {
735  this->_M_invalidate_if([__victim](_Base_const_iterator __it)
736  { return __it == __victim; });
737  _Base_local_iterator __local_victim = _S_to_local(__victim);
738  this->_M_invalidate_local_if(
739  [__local_victim](_Base_const_local_iterator __it)
740  { return __it == __local_victim; });
741  _Base::erase(__victim++);
742  ++__ret;
743  }
744  _M_check_rehashed(__bucket_count);
745  return __ret;
746  }
747 
748  iterator
749  erase(const_iterator __it)
750  {
751  __glibcxx_check_erase(__it);
752  _Base_const_iterator __victim = __it.base();
753  this->_M_invalidate_if([__victim](_Base_const_iterator __it)
754  { return __it == __victim; });
755  _Base_const_local_iterator __local_victim = _S_to_local(__victim);
756  this->_M_invalidate_local_if(
757  [__local_victim](_Base_const_local_iterator __it)
758  { return __it == __local_victim; });
759  size_type __bucket_count = this->bucket_count();
760  _Base_iterator __next = _Base::erase(__it.base());
761  _M_check_rehashed(__bucket_count);
762  return iterator(__next, this);
763  }
764 
765  iterator
766  erase(iterator __it)
767  { return erase(const_iterator(__it)); }
768 
769  iterator
770  erase(const_iterator __first, const_iterator __last)
771  {
772  __glibcxx_check_erase_range(__first, __last);
773  for (_Base_const_iterator __tmp = __first.base();
774  __tmp != __last.base(); ++__tmp)
775  {
776  _GLIBCXX_DEBUG_VERIFY(__tmp != _Base::end(),
777  _M_message(__gnu_debug::__msg_valid_range)
778  ._M_iterator(__first, "first")
779  ._M_iterator(__last, "last"));
780  this->_M_invalidate_if([__tmp](_Base_const_iterator __it)
781  { return __it == __tmp; });
782  _Base_const_local_iterator __local_tmp = _S_to_local(__tmp);
783  this->_M_invalidate_local_if(
784  [__local_tmp](_Base_const_local_iterator __it)
785  { return __it == __local_tmp; });
786  }
787  size_type __bucket_count = this->bucket_count();
788  _Base_iterator __next = _Base::erase(__first.base(), __last.base());
789  _M_check_rehashed(__bucket_count);
790  return iterator(__next, this);
791  }
792 
793  _Base&
794  _M_base() noexcept { return *this; }
795 
796  const _Base&
797  _M_base() const noexcept { return *this; }
798 
799  private:
800  void
801  _M_invalidate_locals()
802  {
803  _Base_local_iterator __local_end = _Base::end(0);
804  this->_M_invalidate_local_if(
805  [__local_end](_Base_const_local_iterator __it)
806  { return __it != __local_end; });
807  }
808 
809  void
810  _M_invalidate_all()
811  {
812  _Base_iterator __end = _Base::end();
813  this->_M_invalidate_if([__end](_Base_const_iterator __it)
814  { return __it != __end; });
815  _M_invalidate_locals();
816  }
817 
818  void
819  _M_check_rehashed(size_type __prev_count)
820  {
821  if (__prev_count != this->bucket_count())
822  _M_invalidate_locals();
823  }
824 
825  static _Base_local_iterator
826  _S_to_local(_Base_iterator __it)
827  {
828  // The returned local iterator will not be incremented so we don't
829  // need to compute __it's node bucket
830  return _Base_local_iterator(__it._M_cur, 0, 0);
831  }
832 
833  static _Base_const_local_iterator
834  _S_to_local(_Base_const_iterator __it)
835  {
836  // The returned local iterator will not be incremented so we don't
837  // need to compute __it's node bucket
838  return _Base_const_local_iterator(__it._M_cur, 0, 0);
839  }
840  };
841 
842  template<typename _Key, typename _Tp, typename _Hash,
843  typename _Pred, typename _Alloc>
844  inline void
845  swap(unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
846  unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
847  { __x.swap(__y); }
848 
849  template<typename _Key, typename _Tp, typename _Hash,
850  typename _Pred, typename _Alloc>
851  inline bool
852  operator==(const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
853  const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
854  { return __x._M_equal(__y); }
855 
856  template<typename _Key, typename _Tp, typename _Hash,
857  typename _Pred, typename _Alloc>
858  inline bool
859  operator!=(const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
860  const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
861  { return !(__x == __y); }
862 
863 } // namespace __debug
864 } // namespace std
865 
866 #endif // __GXX_EXPERIMENTAL_CXX0X__
867 
868 #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
std::__debug::unordered_multimap
Class std::unordered_multimap with safety/checking/debug instrumentation.
Definition: debug/unordered_map:461
std::is_constructible
is_constructible
Definition: type_traits:916
__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::unordered_map
A standard container composed of unique keys (containing at most one of each key value) that associat...
Definition: unordered_map.h:264
std::equal_to
One of the comparison functors.
Definition: stl_function.h:206
std::enable_if
Define a member typedef type only if a boolean constant is true.
Definition: type_traits:1718
__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
std::__debug::unordered_map
Class std::unordered_map with safety/checking/debug instrumentation.
Definition: debug/unordered_map:51
__gnu_debug::_Safe_sequence_base
Base class that supports tracking of iterators that reference a sequence.
Definition: safe_base.h:178
__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::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::unordered_multimap
A standard container composed of equivalent keys (possibly containing multiple of each key value) tha...
Definition: unordered_map.h:332
std::hash
Primary class template hash.
Definition: system_error:112
__gnu_debug::_Safe_iterator
Safe iterator wrapper.
Definition: formatter.h:47