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