libstdc++
debug/unordered_map
Go to the documentation of this file.
1 // Debugging unordered_map/unordered_multimap implementation -*- C++ -*-
2 
3 // Copyright (C) 2003-2016 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  typename __gnu_debug::_Distance_traits<_InputIterator>::__type __dist;
368  __glibcxx_check_valid_range2(__first, __last, __dist);
369  size_type __bucket_count = this->bucket_count();
370 
371  if (__dist.second >= __gnu_debug::__dp_sign)
372  _Base::insert(__gnu_debug::__unsafe(__first),
373  __gnu_debug::__unsafe(__last));
374  else
375  _Base::insert(__first, __last);
376 
377  _M_check_rehashed(__bucket_count);
378  }
379 
380 #if __cplusplus > 201402L
381  template <typename... _Args>
382  pair<iterator, bool>
383  try_emplace(const key_type& __k, _Args&&... __args)
384  {
385  auto __res = _Base::try_emplace(__k,
386  std::forward<_Args>(__args)...);
387  return { iterator(__res.first, this), __res.second };
388  }
389 
390  template <typename... _Args>
391  pair<iterator, bool>
392  try_emplace(key_type&& __k, _Args&&... __args)
393  {
394  auto __res = _Base::try_emplace(std::move(__k),
395  std::forward<_Args>(__args)...);
396  return { iterator(__res.first, this), __res.second };
397  }
398 
399  template <typename... _Args>
400  iterator
401  try_emplace(const_iterator __hint, const key_type& __k,
402  _Args&&... __args)
403  {
404  __glibcxx_check_insert(__hint);
405  return iterator(_Base::try_emplace(__hint.base(), __k,
406  std::forward<_Args>(__args)...),
407  this);
408  }
409 
410  template <typename... _Args>
411  iterator
412  try_emplace(const_iterator __hint, key_type&& __k, _Args&&... __args)
413  {
414  __glibcxx_check_insert(__hint);
415  return iterator(_Base::try_emplace(__hint.base(), std::move(__k),
416  std::forward<_Args>(__args)...),
417  this);
418  }
419 
420  template <typename _Obj>
421  pair<iterator, bool>
422  insert_or_assign(const key_type& __k, _Obj&& __obj)
423  {
424  auto __res = _Base::insert_or_assign(__k,
425  std::forward<_Obj>(__obj));
426  return { iterator(__res.first, this), __res.second };
427  }
428 
429  template <typename _Obj>
430  pair<iterator, bool>
431  insert_or_assign(key_type&& __k, _Obj&& __obj)
432  {
433  auto __res = _Base::insert_or_assign(std::move(__k),
434  std::forward<_Obj>(__obj));
435  return { iterator(__res.first, this), __res.second };
436  }
437 
438  template <typename _Obj>
439  iterator
440  insert_or_assign(const_iterator __hint, const key_type& __k,
441  _Obj&& __obj)
442  {
443  __glibcxx_check_insert(__hint);
444  return iterator(_Base::insert_or_assign(__hint.base(), __k,
445  std::forward<_Obj>(__obj)),
446  this);
447  }
448 
449  template <typename _Obj>
450  iterator
451  insert_or_assign(const_iterator __hint, key_type&& __k, _Obj&& __obj)
452  {
453  __glibcxx_check_insert(__hint);
454  return iterator(_Base::insert_or_assign(__hint.base(),
455  std::move(__k),
456  std::forward<_Obj>(__obj)),
457  this);
458  }
459 #endif
460 
461 
462  iterator
463  find(const key_type& __key)
464  { return iterator(_Base::find(__key), this); }
465 
466  const_iterator
467  find(const key_type& __key) const
468  { return const_iterator(_Base::find(__key), this); }
469 
470  std::pair<iterator, iterator>
471  equal_range(const key_type& __key)
472  {
473  std::pair<_Base_iterator, _Base_iterator> __res =
474  _Base::equal_range(__key);
475  return std::make_pair(iterator(__res.first, this),
476  iterator(__res.second, this));
477  }
478 
479  std::pair<const_iterator, const_iterator>
480  equal_range(const key_type& __key) const
481  {
482  std::pair<_Base_const_iterator, _Base_const_iterator> __res =
483  _Base::equal_range(__key);
484  return std::make_pair(const_iterator(__res.first, this),
485  const_iterator(__res.second, this));
486  }
487 
488  size_type
489  erase(const key_type& __key)
490  {
491  size_type __ret(0);
492  _Base_iterator __victim(_Base::find(__key));
493  if (__victim != _Base::end())
494  {
495  this->_M_invalidate_if([__victim](_Base_const_iterator __it)
496  { return __it == __victim; });
497  this->_M_invalidate_local_if(
498  [__victim](_Base_const_local_iterator __it)
499  { return __it._M_curr() == __victim._M_cur; });
500  size_type __bucket_count = this->bucket_count();
501  _Base::erase(__victim);
502  _M_check_rehashed(__bucket_count);
503  __ret = 1;
504  }
505  return __ret;
506  }
507 
508  iterator
509  erase(const_iterator __it)
510  {
511  __glibcxx_check_erase(__it);
512  _Base_const_iterator __victim = __it.base();
513  this->_M_invalidate_if([__victim](_Base_const_iterator __it)
514  { return __it == __victim; });
515  this->_M_invalidate_local_if(
516  [__victim](_Base_const_local_iterator __it)
517  { return __it._M_curr() == __victim._M_cur; });
518  size_type __bucket_count = this->bucket_count();
519  _Base_iterator __next = _Base::erase(__it.base());
520  _M_check_rehashed(__bucket_count);
521  return iterator(__next, this);
522  }
523 
524  iterator
525  erase(iterator __it)
526  { return erase(const_iterator(__it)); }
527 
528  iterator
529  erase(const_iterator __first, const_iterator __last)
530  {
531  __glibcxx_check_erase_range(__first, __last);
532  for (_Base_const_iterator __tmp = __first.base();
533  __tmp != __last.base(); ++__tmp)
534  {
535  _GLIBCXX_DEBUG_VERIFY(__tmp != _Base::end(),
536  _M_message(__gnu_debug::__msg_valid_range)
537  ._M_iterator(__first, "first")
538  ._M_iterator(__last, "last"));
539  this->_M_invalidate_if([__tmp](_Base_const_iterator __it)
540  { return __it == __tmp; });
541  this->_M_invalidate_local_if(
542  [__tmp](_Base_const_local_iterator __it)
543  { return __it._M_curr() == __tmp._M_cur; });
544  }
545  size_type __bucket_count = this->bucket_count();
546  _Base_iterator __next = _Base::erase(__first.base(), __last.base());
547  _M_check_rehashed(__bucket_count);
548  return iterator(__next, this);
549  }
550 
551  _Base&
552  _M_base() noexcept { return *this; }
553 
554  const _Base&
555  _M_base() const noexcept { return *this; }
556 
557  private:
558  void
559  _M_check_rehashed(size_type __prev_count)
560  {
561  if (__prev_count != this->bucket_count())
562  this->_M_invalidate_locals();
563  }
564  };
565 
566  template<typename _Key, typename _Tp, typename _Hash,
567  typename _Pred, typename _Alloc>
568  inline void
569  swap(unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
570  unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
571  noexcept(noexcept(__x.swap(__y)))
572  { __x.swap(__y); }
573 
574  template<typename _Key, typename _Tp, typename _Hash,
575  typename _Pred, typename _Alloc>
576  inline bool
577  operator==(const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
578  const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
579  { return __x._M_base() == __y._M_base(); }
580 
581  template<typename _Key, typename _Tp, typename _Hash,
582  typename _Pred, typename _Alloc>
583  inline bool
584  operator!=(const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
585  const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
586  { return !(__x == __y); }
587 
588 
589  /// Class std::unordered_multimap with safety/checking/debug instrumentation.
590  template<typename _Key, typename _Tp,
591  typename _Hash = std::hash<_Key>,
592  typename _Pred = std::equal_to<_Key>,
593  typename _Alloc = std::allocator<std::pair<const _Key, _Tp> > >
594  class unordered_multimap
595  : public __gnu_debug::_Safe_container<
596  unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>, _Alloc,
597  __gnu_debug::_Safe_unordered_container>,
598  public _GLIBCXX_STD_C::unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>
599  {
600  typedef _GLIBCXX_STD_C::unordered_multimap<_Key, _Tp, _Hash,
601  _Pred, _Alloc> _Base;
602  typedef __gnu_debug::_Safe_container<unordered_multimap,
603  _Alloc, __gnu_debug::_Safe_unordered_container> _Safe;
604  typedef typename _Base::const_iterator _Base_const_iterator;
605  typedef typename _Base::iterator _Base_iterator;
606  typedef typename _Base::const_local_iterator _Base_const_local_iterator;
607  typedef typename _Base::local_iterator _Base_local_iterator;
608 
609  public:
610  typedef typename _Base::size_type size_type;
611  typedef typename _Base::hasher hasher;
612  typedef typename _Base::key_equal key_equal;
613  typedef typename _Base::allocator_type allocator_type;
614 
615  typedef typename _Base::key_type key_type;
616  typedef typename _Base::value_type value_type;
617 
618  typedef __gnu_debug::_Safe_iterator<
619  _Base_iterator, unordered_multimap> iterator;
620  typedef __gnu_debug::_Safe_iterator<
621  _Base_const_iterator, unordered_multimap> const_iterator;
622  typedef __gnu_debug::_Safe_local_iterator<
623  _Base_local_iterator, unordered_multimap> local_iterator;
624  typedef __gnu_debug::_Safe_local_iterator<
625  _Base_const_local_iterator, unordered_multimap> const_local_iterator;
626 
627  unordered_multimap() = default;
628 
629  explicit
630  unordered_multimap(size_type __n,
631  const hasher& __hf = hasher(),
632  const key_equal& __eql = key_equal(),
633  const allocator_type& __a = allocator_type())
634  : _Base(__n, __hf, __eql, __a) { }
635 
636  template<typename _InputIterator>
637  unordered_multimap(_InputIterator __first, _InputIterator __last,
638  size_type __n = 0,
639  const hasher& __hf = hasher(),
640  const key_equal& __eql = key_equal(),
641  const allocator_type& __a = allocator_type())
642  : _Base(__gnu_debug::__base(__gnu_debug::__check_valid_range(__first,
643  __last)),
644  __gnu_debug::__base(__last), __n,
645  __hf, __eql, __a) { }
646 
647  unordered_multimap(const unordered_multimap&) = default;
648 
649  unordered_multimap(const _Base& __x)
650  : _Base(__x) { }
651 
652  unordered_multimap(unordered_multimap&&) = default;
653 
654  explicit
655  unordered_multimap(const allocator_type& __a)
656  : _Base(__a) { }
657 
658  unordered_multimap(const unordered_multimap& __umap,
659  const allocator_type& __a)
660  : _Base(__umap, __a) { }
661 
662  unordered_multimap(unordered_multimap&& __umap,
663  const allocator_type& __a)
664  : _Safe(std::move(__umap._M_safe()), __a),
665  _Base(std::move(__umap._M_base()), __a) { }
666 
667  unordered_multimap(initializer_list<value_type> __l,
668  size_type __n = 0,
669  const hasher& __hf = hasher(),
670  const key_equal& __eql = key_equal(),
671  const allocator_type& __a = allocator_type())
672  : _Base(__l, __n, __hf, __eql, __a) { }
673 
674  unordered_multimap(size_type __n, const allocator_type& __a)
675  : unordered_multimap(__n, hasher(), key_equal(), __a)
676  { }
677 
678  unordered_multimap(size_type __n, const hasher& __hf,
679  const allocator_type& __a)
680  : unordered_multimap(__n, __hf, key_equal(), __a)
681  { }
682 
683  template<typename _InputIterator>
684  unordered_multimap(_InputIterator __first, _InputIterator __last,
685  size_type __n,
686  const allocator_type& __a)
687  : unordered_multimap(__first, __last, __n, hasher(), key_equal(), __a)
688  { }
689 
690  template<typename _InputIterator>
691  unordered_multimap(_InputIterator __first, _InputIterator __last,
692  size_type __n, const hasher& __hf,
693  const allocator_type& __a)
694  : unordered_multimap(__first, __last, __n, __hf, key_equal(), __a)
695  { }
696 
697  unordered_multimap(initializer_list<value_type> __l,
698  size_type __n,
699  const allocator_type& __a)
700  : unordered_multimap(__l, __n, hasher(), key_equal(), __a)
701  { }
702 
703  unordered_multimap(initializer_list<value_type> __l,
704  size_type __n, const hasher& __hf,
705  const allocator_type& __a)
706  : unordered_multimap(__l, __n, __hf, key_equal(), __a)
707  { }
708 
709  ~unordered_multimap() = default;
710 
711  unordered_multimap&
712  operator=(const unordered_multimap&) = default;
713 
714  unordered_multimap&
715  operator=(unordered_multimap&&) = default;
716 
717  unordered_multimap&
718  operator=(initializer_list<value_type> __l)
719  {
720  this->_M_base() = __l;
721  this->_M_invalidate_all();
722  return *this;
723  }
724 
725  void
726  swap(unordered_multimap& __x)
727  noexcept( noexcept(declval<_Base&>().swap(__x)) )
728  {
729  _Safe::_M_swap(__x);
730  _Base::swap(__x);
731  }
732 
733  void
734  clear() noexcept
735  {
736  _Base::clear();
737  this->_M_invalidate_all();
738  }
739 
740  iterator
741  begin() noexcept
742  { return iterator(_Base::begin(), this); }
743 
744  const_iterator
745  begin() const noexcept
746  { return const_iterator(_Base::begin(), this); }
747 
748  iterator
749  end() noexcept
750  { return iterator(_Base::end(), this); }
751 
752  const_iterator
753  end() const noexcept
754  { return const_iterator(_Base::end(), this); }
755 
756  const_iterator
757  cbegin() const noexcept
758  { return const_iterator(_Base::begin(), this); }
759 
760  const_iterator
761  cend() const noexcept
762  { return const_iterator(_Base::end(), this); }
763 
764  // local versions
765  local_iterator
766  begin(size_type __b)
767  {
768  __glibcxx_check_bucket_index(__b);
769  return local_iterator(_Base::begin(__b), this);
770  }
771 
772  local_iterator
773  end(size_type __b)
774  {
775  __glibcxx_check_bucket_index(__b);
776  return local_iterator(_Base::end(__b), this);
777  }
778 
779  const_local_iterator
780  begin(size_type __b) const
781  {
782  __glibcxx_check_bucket_index(__b);
783  return const_local_iterator(_Base::begin(__b), this);
784  }
785 
786  const_local_iterator
787  end(size_type __b) const
788  {
789  __glibcxx_check_bucket_index(__b);
790  return const_local_iterator(_Base::end(__b), this);
791  }
792 
793  const_local_iterator
794  cbegin(size_type __b) const
795  {
796  __glibcxx_check_bucket_index(__b);
797  return const_local_iterator(_Base::cbegin(__b), this);
798  }
799 
800  const_local_iterator
801  cend(size_type __b) const
802  {
803  __glibcxx_check_bucket_index(__b);
804  return const_local_iterator(_Base::cend(__b), this);
805  }
806 
807  size_type
808  bucket_size(size_type __b) const
809  {
810  __glibcxx_check_bucket_index(__b);
811  return _Base::bucket_size(__b);
812  }
813 
814  float
815  max_load_factor() const noexcept
816  { return _Base::max_load_factor(); }
817 
818  void
819  max_load_factor(float __f)
820  {
821  __glibcxx_check_max_load_factor(__f);
822  _Base::max_load_factor(__f);
823  }
824 
825  template<typename... _Args>
826  iterator
827  emplace(_Args&&... __args)
828  {
829  size_type __bucket_count = this->bucket_count();
830  _Base_iterator __it
831  = _Base::emplace(std::forward<_Args>(__args)...);
832  _M_check_rehashed(__bucket_count);
833  return iterator(__it, this);
834  }
835 
836  template<typename... _Args>
837  iterator
838  emplace_hint(const_iterator __hint, _Args&&... __args)
839  {
840  __glibcxx_check_insert(__hint);
841  size_type __bucket_count = this->bucket_count();
842  _Base_iterator __it = _Base::emplace_hint(__hint.base(),
843  std::forward<_Args>(__args)...);
844  _M_check_rehashed(__bucket_count);
845  return iterator(__it, this);
846  }
847 
848  iterator
849  insert(const value_type& __obj)
850  {
851  size_type __bucket_count = this->bucket_count();
852  _Base_iterator __it = _Base::insert(__obj);
853  _M_check_rehashed(__bucket_count);
854  return iterator(__it, this);
855  }
856 
857  iterator
858  insert(const_iterator __hint, const value_type& __obj)
859  {
860  __glibcxx_check_insert(__hint);
861  size_type __bucket_count = this->bucket_count();
862  _Base_iterator __it = _Base::insert(__hint.base(), __obj);
863  _M_check_rehashed(__bucket_count);
864  return iterator(__it, this);
865  }
866 
867  template<typename _Pair, typename = typename
868  std::enable_if<std::is_constructible<value_type,
869  _Pair&&>::value>::type>
870  iterator
871  insert(_Pair&& __obj)
872  {
873  size_type __bucket_count = this->bucket_count();
874  _Base_iterator __it = _Base::insert(std::forward<_Pair>(__obj));
875  _M_check_rehashed(__bucket_count);
876  return iterator(__it, this);
877  }
878 
879  template<typename _Pair, typename = typename
880  std::enable_if<std::is_constructible<value_type,
881  _Pair&&>::value>::type>
882  iterator
883  insert(const_iterator __hint, _Pair&& __obj)
884  {
885  __glibcxx_check_insert(__hint);
886  size_type __bucket_count = this->bucket_count();
887  _Base_iterator __it =
888  _Base::insert(__hint.base(), std::forward<_Pair>(__obj));
889  _M_check_rehashed(__bucket_count);
890  return iterator(__it, this);
891  }
892 
893  void
894  insert(std::initializer_list<value_type> __l)
895  { _Base::insert(__l); }
896 
897  template<typename _InputIterator>
898  void
899  insert(_InputIterator __first, _InputIterator __last)
900  {
901  typename __gnu_debug::_Distance_traits<_InputIterator>::__type __dist;
902  __glibcxx_check_valid_range2(__first, __last, __dist);
903  size_type __bucket_count = this->bucket_count();
904 
905  if (__dist.second >= __gnu_debug::__dp_sign)
906  _Base::insert(__gnu_debug::__unsafe(__first),
907  __gnu_debug::__unsafe(__last));
908  else
909  _Base::insert(__first, __last);
910 
911  _M_check_rehashed(__bucket_count);
912  }
913 
914  iterator
915  find(const key_type& __key)
916  { return iterator(_Base::find(__key), this); }
917 
918  const_iterator
919  find(const key_type& __key) const
920  { return const_iterator(_Base::find(__key), this); }
921 
922  std::pair<iterator, iterator>
923  equal_range(const key_type& __key)
924  {
925  std::pair<_Base_iterator, _Base_iterator> __res =
926  _Base::equal_range(__key);
927  return std::make_pair(iterator(__res.first, this),
928  iterator(__res.second, this));
929  }
930 
931  std::pair<const_iterator, const_iterator>
932  equal_range(const key_type& __key) const
933  {
934  std::pair<_Base_const_iterator, _Base_const_iterator> __res =
935  _Base::equal_range(__key);
936  return std::make_pair(const_iterator(__res.first, this),
937  const_iterator(__res.second, this));
938  }
939 
940  size_type
941  erase(const key_type& __key)
942  {
943  size_type __ret(0);
944  size_type __bucket_count = this->bucket_count();
945  std::pair<_Base_iterator, _Base_iterator> __pair =
946  _Base::equal_range(__key);
947  for (_Base_iterator __victim = __pair.first; __victim != __pair.second;)
948  {
949  this->_M_invalidate_if([__victim](_Base_const_iterator __it)
950  { return __it == __victim; });
951  this->_M_invalidate_local_if(
952  [__victim](_Base_const_local_iterator __it)
953  { return __it._M_curr() == __victim._M_cur; });
954  _Base::erase(__victim++);
955  ++__ret;
956  }
957  _M_check_rehashed(__bucket_count);
958  return __ret;
959  }
960 
961  iterator
962  erase(const_iterator __it)
963  {
964  __glibcxx_check_erase(__it);
965  _Base_const_iterator __victim = __it.base();
966  this->_M_invalidate_if([__victim](_Base_const_iterator __it)
967  { return __it == __victim; });
968  this->_M_invalidate_local_if(
969  [__victim](_Base_const_local_iterator __it)
970  { return __it._M_curr() == __victim._M_cur; });
971  size_type __bucket_count = this->bucket_count();
972  _Base_iterator __next = _Base::erase(__it.base());
973  _M_check_rehashed(__bucket_count);
974  return iterator(__next, this);
975  }
976 
977  iterator
978  erase(iterator __it)
979  { return erase(const_iterator(__it)); }
980 
981  iterator
982  erase(const_iterator __first, const_iterator __last)
983  {
984  __glibcxx_check_erase_range(__first, __last);
985  for (_Base_const_iterator __tmp = __first.base();
986  __tmp != __last.base(); ++__tmp)
987  {
988  _GLIBCXX_DEBUG_VERIFY(__tmp != _Base::end(),
989  _M_message(__gnu_debug::__msg_valid_range)
990  ._M_iterator(__first, "first")
991  ._M_iterator(__last, "last"));
992  this->_M_invalidate_if([__tmp](_Base_const_iterator __it)
993  { return __it == __tmp; });
994  this->_M_invalidate_local_if(
995  [__tmp](_Base_const_local_iterator __it)
996  { return __it._M_curr() == __tmp._M_cur; });
997  }
998  size_type __bucket_count = this->bucket_count();
999  _Base_iterator __next = _Base::erase(__first.base(), __last.base());
1000  _M_check_rehashed(__bucket_count);
1001  return iterator(__next, this);
1002  }
1003 
1004  _Base&
1005  _M_base() noexcept { return *this; }
1006 
1007  const _Base&
1008  _M_base() const noexcept { return *this; }
1009 
1010  private:
1011  void
1012  _M_check_rehashed(size_type __prev_count)
1013  {
1014  if (__prev_count != this->bucket_count())
1015  this->_M_invalidate_locals();
1016  }
1017  };
1018 
1019  template<typename _Key, typename _Tp, typename _Hash,
1020  typename _Pred, typename _Alloc>
1021  inline void
1022  swap(unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
1023  unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
1024  noexcept(noexcept(__x.swap(__y)))
1025  { __x.swap(__y); }
1026 
1027  template<typename _Key, typename _Tp, typename _Hash,
1028  typename _Pred, typename _Alloc>
1029  inline bool
1030  operator==(const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
1031  const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
1032  { return __x._M_base() == __y._M_base(); }
1033 
1034  template<typename _Key, typename _Tp, typename _Hash,
1035  typename _Pred, typename _Alloc>
1036  inline bool
1037  operator!=(const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
1038  const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
1039  { return !(__x == __y); }
1040 
1041 } // namespace __debug
1042 } // namespace std
1043 
1044 #endif // C++11
1045 
1046 #endif