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