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