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