libstdc++
debug/unordered_map
Go to the documentation of this file.
1 // Debugging unordered_map/unordered_multimap implementation -*- C++ -*-
2 
3 // Copyright (C) 2003-2017 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 #pragma GCC system_header
33 
34 #if __cplusplus < 201103L
35 # include <bits/c++0x_warning.h>
36 #else
37 # include <unordered_map>
38 
39 #include <debug/safe_unordered_container.h>
40 #include <debug/safe_container.h>
41 #include <debug/safe_iterator.h>
42 #include <debug/safe_local_iterator.h>
43 
44 namespace std _GLIBCXX_VISIBILITY(default)
45 {
46 namespace __debug
47 {
48  /// Class std::unordered_map with safety/checking/debug instrumentation.
49  template<typename _Key, typename _Tp,
50  typename _Hash = std::hash<_Key>,
51  typename _Pred = std::equal_to<_Key>,
52  typename _Alloc = std::allocator<std::pair<const _Key, _Tp> > >
53  class unordered_map
54  : public __gnu_debug::_Safe_container<
55  unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>, _Alloc,
56  __gnu_debug::_Safe_unordered_container>,
57  public _GLIBCXX_STD_C::unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>
58  {
59  typedef _GLIBCXX_STD_C::unordered_map<_Key, _Tp, _Hash,
60  _Pred, _Alloc> _Base;
61  typedef __gnu_debug::_Safe_container<unordered_map,
62  _Alloc, __gnu_debug::_Safe_unordered_container> _Safe;
63  typedef typename _Base::const_iterator _Base_const_iterator;
64  typedef typename _Base::iterator _Base_iterator;
65  typedef typename _Base::const_local_iterator
66  _Base_const_local_iterator;
67  typedef typename _Base::local_iterator _Base_local_iterator;
68 
69  public:
70  typedef typename _Base::size_type size_type;
71  typedef typename _Base::hasher hasher;
72  typedef typename _Base::key_equal key_equal;
73  typedef typename _Base::allocator_type allocator_type;
74 
75  typedef typename _Base::key_type key_type;
76  typedef typename _Base::value_type value_type;
77 
78  typedef __gnu_debug::_Safe_iterator<
79  _Base_iterator, unordered_map> iterator;
80  typedef __gnu_debug::_Safe_iterator<
81  _Base_const_iterator, unordered_map> const_iterator;
82  typedef __gnu_debug::_Safe_local_iterator<
83  _Base_local_iterator, unordered_map> local_iterator;
84  typedef __gnu_debug::_Safe_local_iterator<
85  _Base_const_local_iterator, unordered_map> const_local_iterator;
86 
87  unordered_map() = default;
88 
89  explicit
90  unordered_map(size_type __n,
91  const hasher& __hf = hasher(),
92  const key_equal& __eql = key_equal(),
93  const allocator_type& __a = allocator_type())
94  : _Base(__n, __hf, __eql, __a) { }
95 
96  template<typename _InputIterator>
97  unordered_map(_InputIterator __first, _InputIterator __last,
98  size_type __n = 0,
99  const hasher& __hf = hasher(),
100  const key_equal& __eql = key_equal(),
101  const allocator_type& __a = allocator_type())
102  : _Base(__gnu_debug::__base(__gnu_debug::__check_valid_range(__first,
103  __last)),
104  __gnu_debug::__base(__last), __n,
105  __hf, __eql, __a) { }
106 
107  unordered_map(const unordered_map&) = default;
108 
109  unordered_map(const _Base& __x)
110  : _Base(__x) { }
111 
112  unordered_map(unordered_map&&) = default;
113 
114  explicit
115  unordered_map(const allocator_type& __a)
116  : _Base(__a) { }
117 
118  unordered_map(const unordered_map& __umap,
119  const allocator_type& __a)
120  : _Base(__umap, __a) { }
121 
122  unordered_map(unordered_map&& __umap,
123  const allocator_type& __a)
124  : _Safe(std::move(__umap._M_safe()), __a),
125  _Base(std::move(__umap._M_base()), __a) { }
126 
127  unordered_map(initializer_list<value_type> __l,
128  size_type __n = 0,
129  const hasher& __hf = hasher(),
130  const key_equal& __eql = key_equal(),
131  const allocator_type& __a = allocator_type())
132  : _Base(__l, __n, __hf, __eql, __a) { }
133 
134  unordered_map(size_type __n, const allocator_type& __a)
135  : unordered_map(__n, hasher(), key_equal(), __a)
136  { }
137 
138  unordered_map(size_type __n,
139  const hasher& __hf,
140  const allocator_type& __a)
141  : unordered_map(__n, __hf, key_equal(), __a)
142  { }
143 
144  template<typename _InputIterator>
145  unordered_map(_InputIterator __first, _InputIterator __last,
146  size_type __n,
147  const allocator_type& __a)
148  : unordered_map(__first, __last, __n, hasher(), key_equal(), __a)
149  { }
150 
151  template<typename _InputIterator>
152  unordered_map(_InputIterator __first, _InputIterator __last,
153  size_type __n,
154  const hasher& __hf,
155  const allocator_type& __a)
156  : unordered_map(__first, __last, __n, __hf, key_equal(), __a)
157  { }
158 
159  unordered_map(initializer_list<value_type> __l,
160  size_type __n,
161  const allocator_type& __a)
162  : unordered_map(__l, __n, hasher(), key_equal(), __a)
163  { }
164 
165  unordered_map(initializer_list<value_type> __l,
166  size_type __n,
167  const hasher& __hf,
168  const allocator_type& __a)
169  : unordered_map(__l, __n, __hf, key_equal(), __a)
170  { }
171 
172  ~unordered_map() = default;
173 
174  unordered_map&
175  operator=(const unordered_map&) = default;
176 
177  unordered_map&
178  operator=(unordered_map&&) = default;
179 
180  unordered_map&
181  operator=(initializer_list<value_type> __l)
182  {
183  _M_base() = __l;
184  this->_M_invalidate_all();
185  return *this;
186  }
187 
188  void
189  swap(unordered_map& __x)
190  noexcept( noexcept(declval<_Base&>().swap(__x)) )
191  {
192  _Safe::_M_swap(__x);
193  _Base::swap(__x);
194  }
195 
196  void
197  clear() noexcept
198  {
199  _Base::clear();
200  this->_M_invalidate_all();
201  }
202 
203  iterator
204  begin() noexcept
205  { return iterator(_Base::begin(), this); }
206 
207  const_iterator
208  begin() const noexcept
209  { return const_iterator(_Base::begin(), this); }
210 
211  iterator
212  end() noexcept
213  { return iterator(_Base::end(), this); }
214 
215  const_iterator
216  end() const noexcept
217  { return const_iterator(_Base::end(), this); }
218 
219  const_iterator
220  cbegin() const noexcept
221  { return const_iterator(_Base::begin(), this); }
222 
223  const_iterator
224  cend() const noexcept
225  { return const_iterator(_Base::end(), this); }
226 
227  // local versions
228  local_iterator
229  begin(size_type __b)
230  {
231  __glibcxx_check_bucket_index(__b);
232  return local_iterator(_Base::begin(__b), this);
233  }
234 
235  local_iterator
236  end(size_type __b)
237  {
238  __glibcxx_check_bucket_index(__b);
239  return local_iterator(_Base::end(__b), this);
240  }
241 
242  const_local_iterator
243  begin(size_type __b) const
244  {
245  __glibcxx_check_bucket_index(__b);
246  return const_local_iterator(_Base::begin(__b), this);
247  }
248 
249  const_local_iterator
250  end(size_type __b) const
251  {
252  __glibcxx_check_bucket_index(__b);
253  return const_local_iterator(_Base::end(__b), this);
254  }
255 
256  const_local_iterator
257  cbegin(size_type __b) const
258  {
259  __glibcxx_check_bucket_index(__b);
260  return const_local_iterator(_Base::cbegin(__b), this);
261  }
262 
263  const_local_iterator
264  cend(size_type __b) const
265  {
266  __glibcxx_check_bucket_index(__b);
267  return const_local_iterator(_Base::cend(__b), this);
268  }
269 
270  size_type
271  bucket_size(size_type __b) const
272  {
273  __glibcxx_check_bucket_index(__b);
274  return _Base::bucket_size(__b);
275  }
276 
277  float
278  max_load_factor() const noexcept
279  { return _Base::max_load_factor(); }
280 
281  void
282  max_load_factor(float __f)
283  {
284  __glibcxx_check_max_load_factor(__f);
285  _Base::max_load_factor(__f);
286  }
287 
288  template<typename... _Args>
289  std::pair<iterator, bool>
290  emplace(_Args&&... __args)
291  {
292  size_type __bucket_count = this->bucket_count();
293  std::pair<_Base_iterator, bool> __res
294  = _Base::emplace(std::forward<_Args>(__args)...);
295  _M_check_rehashed(__bucket_count);
296  return std::make_pair(iterator(__res.first, this), __res.second);
297  }
298 
299  template<typename... _Args>
300  iterator
301  emplace_hint(const_iterator __hint, _Args&&... __args)
302  {
303  __glibcxx_check_insert(__hint);
304  size_type __bucket_count = this->bucket_count();
305  _Base_iterator __it = _Base::emplace_hint(__hint.base(),
306  std::forward<_Args>(__args)...);
307  _M_check_rehashed(__bucket_count);
308  return iterator(__it, this);
309  }
310 
311  std::pair<iterator, bool>
312  insert(const value_type& __obj)
313  {
314  size_type __bucket_count = this->bucket_count();
315  std::pair<_Base_iterator, bool> __res = _Base::insert(__obj);
316  _M_check_rehashed(__bucket_count);
317  return std::make_pair(iterator(__res.first, this), __res.second);
318  }
319 
320  iterator
321  insert(const_iterator __hint, const value_type& __obj)
322  {
323  __glibcxx_check_insert(__hint);
324  size_type __bucket_count = this->bucket_count();
325  _Base_iterator __it = _Base::insert(__hint.base(), __obj);
326  _M_check_rehashed(__bucket_count);
327  return iterator(__it, this);
328  }
329 
330  template<typename _Pair, typename = typename
331  std::enable_if<std::is_constructible<value_type,
332  _Pair&&>::value>::type>
333  std::pair<iterator, bool>
334  insert(_Pair&& __obj)
335  {
336  size_type __bucket_count = this->bucket_count();
337  std::pair<_Base_iterator, bool> __res =
338  _Base::insert(std::forward<_Pair>(__obj));
339  _M_check_rehashed(__bucket_count);
340  return std::make_pair(iterator(__res.first, this), __res.second);
341  }
342 
343  template<typename _Pair, typename = typename
344  std::enable_if<std::is_constructible<value_type,
345  _Pair&&>::value>::type>
346  iterator
347  insert(const_iterator __hint, _Pair&& __obj)
348  {
349  __glibcxx_check_insert(__hint);
350  size_type __bucket_count = this->bucket_count();
351  _Base_iterator __it =
352  _Base::insert(__hint.base(), std::forward<_Pair>(__obj));
353  _M_check_rehashed(__bucket_count);
354  return iterator(__it, this);
355  }
356 
357  void
358  insert(std::initializer_list<value_type> __l)
359  {
360  size_type __bucket_count = this->bucket_count();
361  _Base::insert(__l);
362  _M_check_rehashed(__bucket_count);
363  }
364 
365  template<typename _InputIterator>
366  void
367  insert(_InputIterator __first, _InputIterator __last)
368  {
369  typename __gnu_debug::_Distance_traits<_InputIterator>::__type __dist;
370  __glibcxx_check_valid_range2(__first, __last, __dist);
371  size_type __bucket_count = this->bucket_count();
372 
373  if (__dist.second >= __gnu_debug::__dp_sign)
374  _Base::insert(__gnu_debug::__unsafe(__first),
375  __gnu_debug::__unsafe(__last));
376  else
377  _Base::insert(__first, __last);
378 
379  _M_check_rehashed(__bucket_count);
380  }
381 
382 #if __cplusplus > 201402L
383  template <typename... _Args>
384  pair<iterator, bool>
385  try_emplace(const key_type& __k, _Args&&... __args)
386  {
387  auto __res = _Base::try_emplace(__k,
388  std::forward<_Args>(__args)...);
389  return { iterator(__res.first, this), __res.second };
390  }
391 
392  template <typename... _Args>
393  pair<iterator, bool>
394  try_emplace(key_type&& __k, _Args&&... __args)
395  {
396  auto __res = _Base::try_emplace(std::move(__k),
397  std::forward<_Args>(__args)...);
398  return { iterator(__res.first, this), __res.second };
399  }
400 
401  template <typename... _Args>
402  iterator
403  try_emplace(const_iterator __hint, const key_type& __k,
404  _Args&&... __args)
405  {
406  __glibcxx_check_insert(__hint);
407  return iterator(_Base::try_emplace(__hint.base(), __k,
408  std::forward<_Args>(__args)...),
409  this);
410  }
411 
412  template <typename... _Args>
413  iterator
414  try_emplace(const_iterator __hint, key_type&& __k, _Args&&... __args)
415  {
416  __glibcxx_check_insert(__hint);
417  return iterator(_Base::try_emplace(__hint.base(), std::move(__k),
418  std::forward<_Args>(__args)...),
419  this);
420  }
421 
422  template <typename _Obj>
423  pair<iterator, bool>
424  insert_or_assign(const key_type& __k, _Obj&& __obj)
425  {
426  auto __res = _Base::insert_or_assign(__k,
427  std::forward<_Obj>(__obj));
428  return { iterator(__res.first, this), __res.second };
429  }
430 
431  template <typename _Obj>
432  pair<iterator, bool>
433  insert_or_assign(key_type&& __k, _Obj&& __obj)
434  {
435  auto __res = _Base::insert_or_assign(std::move(__k),
436  std::forward<_Obj>(__obj));
437  return { iterator(__res.first, this), __res.second };
438  }
439 
440  template <typename _Obj>
441  iterator
442  insert_or_assign(const_iterator __hint, const key_type& __k,
443  _Obj&& __obj)
444  {
445  __glibcxx_check_insert(__hint);
446  return iterator(_Base::insert_or_assign(__hint.base(), __k,
447  std::forward<_Obj>(__obj)),
448  this);
449  }
450 
451  template <typename _Obj>
452  iterator
453  insert_or_assign(const_iterator __hint, key_type&& __k, _Obj&& __obj)
454  {
455  __glibcxx_check_insert(__hint);
456  return iterator(_Base::insert_or_assign(__hint.base(),
457  std::move(__k),
458  std::forward<_Obj>(__obj)),
459  this);
460  }
461 #endif // C++17
462 
463 #if __cplusplus > 201402L
464  using node_type = typename _Base::node_type;
465 
466  struct insert_return_type
467  {
468  bool inserted;
469  iterator position;
470  node_type node;
471  };
472 
473  node_type
474  extract(const_iterator __position)
475  {
476  __glibcxx_check_erase(__position);
477  _Base_const_iterator __victim = __position.base();
478  this->_M_invalidate_if(
479  [__victim](_Base_const_iterator __it) { return __it == __victim; }
480  );
481  this->_M_invalidate_local_if(
482  [__victim](_Base_const_local_iterator __it) {
483  return __it._M_curr() == __victim._M_cur;
484  });
485  return _Base::extract(__position.base());
486  }
487 
488  node_type
489  extract(const key_type& __key)
490  {
491  const auto __position = find(__key);
492  if (__position != end())
493  return extract(__position);
494  return {};
495  }
496 
497  insert_return_type
498  insert(node_type&& __nh)
499  {
500  auto __ret = _Base::insert(std::move(__nh));
501  iterator __pos = iterator(__ret.position, this);
502  return { __ret.inserted, __pos, std::move(__ret.node) };
503  }
504 
505  iterator
506  insert(const_iterator __hint, node_type&& __nh)
507  {
508  __glibcxx_check_insert(__hint);
509  return iterator(_Base::insert(__hint.base(), std::move(__nh)), this);
510  }
511 
512  using _Base::merge;
513 #endif // C++17
514 
515  iterator
516  find(const key_type& __key)
517  { return iterator(_Base::find(__key), this); }
518 
519  const_iterator
520  find(const key_type& __key) const
521  { return const_iterator(_Base::find(__key), this); }
522 
523  std::pair<iterator, iterator>
524  equal_range(const key_type& __key)
525  {
526  std::pair<_Base_iterator, _Base_iterator> __res =
527  _Base::equal_range(__key);
528  return std::make_pair(iterator(__res.first, this),
529  iterator(__res.second, this));
530  }
531 
532  std::pair<const_iterator, const_iterator>
533  equal_range(const key_type& __key) const
534  {
535  std::pair<_Base_const_iterator, _Base_const_iterator> __res =
536  _Base::equal_range(__key);
537  return std::make_pair(const_iterator(__res.first, this),
538  const_iterator(__res.second, this));
539  }
540 
541  size_type
542  erase(const key_type& __key)
543  {
544  size_type __ret(0);
545  _Base_iterator __victim(_Base::find(__key));
546  if (__victim != _Base::end())
547  {
548  this->_M_invalidate_if([__victim](_Base_const_iterator __it)
549  { return __it == __victim; });
550  this->_M_invalidate_local_if(
551  [__victim](_Base_const_local_iterator __it)
552  { return __it._M_curr() == __victim._M_cur; });
553  size_type __bucket_count = this->bucket_count();
554  _Base::erase(__victim);
555  _M_check_rehashed(__bucket_count);
556  __ret = 1;
557  }
558  return __ret;
559  }
560 
561  iterator
562  erase(const_iterator __it)
563  {
564  __glibcxx_check_erase(__it);
565  _Base_const_iterator __victim = __it.base();
566  this->_M_invalidate_if([__victim](_Base_const_iterator __it)
567  { return __it == __victim; });
568  this->_M_invalidate_local_if(
569  [__victim](_Base_const_local_iterator __it)
570  { return __it._M_curr() == __victim._M_cur; });
571  size_type __bucket_count = this->bucket_count();
572  _Base_iterator __next = _Base::erase(__it.base());
573  _M_check_rehashed(__bucket_count);
574  return iterator(__next, this);
575  }
576 
577  iterator
578  erase(iterator __it)
579  { return erase(const_iterator(__it)); }
580 
581  iterator
582  erase(const_iterator __first, const_iterator __last)
583  {
584  __glibcxx_check_erase_range(__first, __last);
585  for (_Base_const_iterator __tmp = __first.base();
586  __tmp != __last.base(); ++__tmp)
587  {
588  _GLIBCXX_DEBUG_VERIFY(__tmp != _Base::end(),
589  _M_message(__gnu_debug::__msg_valid_range)
590  ._M_iterator(__first, "first")
591  ._M_iterator(__last, "last"));
592  this->_M_invalidate_if([__tmp](_Base_const_iterator __it)
593  { return __it == __tmp; });
594  this->_M_invalidate_local_if(
595  [__tmp](_Base_const_local_iterator __it)
596  { return __it._M_curr() == __tmp._M_cur; });
597  }
598  size_type __bucket_count = this->bucket_count();
599  _Base_iterator __next = _Base::erase(__first.base(), __last.base());
600  _M_check_rehashed(__bucket_count);
601  return iterator(__next, this);
602  }
603 
604  _Base&
605  _M_base() noexcept { return *this; }
606 
607  const _Base&
608  _M_base() const noexcept { return *this; }
609 
610  private:
611  void
612  _M_check_rehashed(size_type __prev_count)
613  {
614  if (__prev_count != this->bucket_count())
615  this->_M_invalidate_locals();
616  }
617  };
618 
619  template<typename _Key, typename _Tp, typename _Hash,
620  typename _Pred, typename _Alloc>
621  inline void
622  swap(unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
623  unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
624  noexcept(noexcept(__x.swap(__y)))
625  { __x.swap(__y); }
626 
627  template<typename _Key, typename _Tp, typename _Hash,
628  typename _Pred, typename _Alloc>
629  inline bool
630  operator==(const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
631  const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
632  { return __x._M_base() == __y._M_base(); }
633 
634  template<typename _Key, typename _Tp, typename _Hash,
635  typename _Pred, typename _Alloc>
636  inline bool
637  operator!=(const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
638  const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
639  { return !(__x == __y); }
640 
641 
642  /// Class std::unordered_multimap with safety/checking/debug instrumentation.
643  template<typename _Key, typename _Tp,
644  typename _Hash = std::hash<_Key>,
645  typename _Pred = std::equal_to<_Key>,
646  typename _Alloc = std::allocator<std::pair<const _Key, _Tp> > >
647  class unordered_multimap
648  : public __gnu_debug::_Safe_container<
649  unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>, _Alloc,
650  __gnu_debug::_Safe_unordered_container>,
651  public _GLIBCXX_STD_C::unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>
652  {
653  typedef _GLIBCXX_STD_C::unordered_multimap<_Key, _Tp, _Hash,
654  _Pred, _Alloc> _Base;
655  typedef __gnu_debug::_Safe_container<unordered_multimap,
656  _Alloc, __gnu_debug::_Safe_unordered_container> _Safe;
657  typedef typename _Base::const_iterator _Base_const_iterator;
658  typedef typename _Base::iterator _Base_iterator;
659  typedef typename _Base::const_local_iterator _Base_const_local_iterator;
660  typedef typename _Base::local_iterator _Base_local_iterator;
661 
662  public:
663  typedef typename _Base::size_type size_type;
664  typedef typename _Base::hasher hasher;
665  typedef typename _Base::key_equal key_equal;
666  typedef typename _Base::allocator_type allocator_type;
667 
668  typedef typename _Base::key_type key_type;
669  typedef typename _Base::value_type value_type;
670 
671  typedef __gnu_debug::_Safe_iterator<
672  _Base_iterator, unordered_multimap> iterator;
673  typedef __gnu_debug::_Safe_iterator<
674  _Base_const_iterator, unordered_multimap> const_iterator;
675  typedef __gnu_debug::_Safe_local_iterator<
676  _Base_local_iterator, unordered_multimap> local_iterator;
677  typedef __gnu_debug::_Safe_local_iterator<
678  _Base_const_local_iterator, unordered_multimap> const_local_iterator;
679 
680  unordered_multimap() = default;
681 
682  explicit
683  unordered_multimap(size_type __n,
684  const hasher& __hf = hasher(),
685  const key_equal& __eql = key_equal(),
686  const allocator_type& __a = allocator_type())
687  : _Base(__n, __hf, __eql, __a) { }
688 
689  template<typename _InputIterator>
690  unordered_multimap(_InputIterator __first, _InputIterator __last,
691  size_type __n = 0,
692  const hasher& __hf = hasher(),
693  const key_equal& __eql = key_equal(),
694  const allocator_type& __a = allocator_type())
695  : _Base(__gnu_debug::__base(__gnu_debug::__check_valid_range(__first,
696  __last)),
697  __gnu_debug::__base(__last), __n,
698  __hf, __eql, __a) { }
699 
700  unordered_multimap(const unordered_multimap&) = default;
701 
702  unordered_multimap(const _Base& __x)
703  : _Base(__x) { }
704 
705  unordered_multimap(unordered_multimap&&) = default;
706 
707  explicit
708  unordered_multimap(const allocator_type& __a)
709  : _Base(__a) { }
710 
711  unordered_multimap(const unordered_multimap& __umap,
712  const allocator_type& __a)
713  : _Base(__umap, __a) { }
714 
715  unordered_multimap(unordered_multimap&& __umap,
716  const allocator_type& __a)
717  : _Safe(std::move(__umap._M_safe()), __a),
718  _Base(std::move(__umap._M_base()), __a) { }
719 
720  unordered_multimap(initializer_list<value_type> __l,
721  size_type __n = 0,
722  const hasher& __hf = hasher(),
723  const key_equal& __eql = key_equal(),
724  const allocator_type& __a = allocator_type())
725  : _Base(__l, __n, __hf, __eql, __a) { }
726 
727  unordered_multimap(size_type __n, const allocator_type& __a)
728  : unordered_multimap(__n, hasher(), key_equal(), __a)
729  { }
730 
731  unordered_multimap(size_type __n, const hasher& __hf,
732  const allocator_type& __a)
733  : unordered_multimap(__n, __hf, key_equal(), __a)
734  { }
735 
736  template<typename _InputIterator>
737  unordered_multimap(_InputIterator __first, _InputIterator __last,
738  size_type __n,
739  const allocator_type& __a)
740  : unordered_multimap(__first, __last, __n, hasher(), key_equal(), __a)
741  { }
742 
743  template<typename _InputIterator>
744  unordered_multimap(_InputIterator __first, _InputIterator __last,
745  size_type __n, const hasher& __hf,
746  const allocator_type& __a)
747  : unordered_multimap(__first, __last, __n, __hf, key_equal(), __a)
748  { }
749 
750  unordered_multimap(initializer_list<value_type> __l,
751  size_type __n,
752  const allocator_type& __a)
753  : unordered_multimap(__l, __n, hasher(), key_equal(), __a)
754  { }
755 
756  unordered_multimap(initializer_list<value_type> __l,
757  size_type __n, const hasher& __hf,
758  const allocator_type& __a)
759  : unordered_multimap(__l, __n, __hf, key_equal(), __a)
760  { }
761 
762  ~unordered_multimap() = default;
763 
764  unordered_multimap&
765  operator=(const unordered_multimap&) = default;
766 
767  unordered_multimap&
768  operator=(unordered_multimap&&) = default;
769 
770  unordered_multimap&
771  operator=(initializer_list<value_type> __l)
772  {
773  this->_M_base() = __l;
774  this->_M_invalidate_all();
775  return *this;
776  }
777 
778  void
779  swap(unordered_multimap& __x)
780  noexcept( noexcept(declval<_Base&>().swap(__x)) )
781  {
782  _Safe::_M_swap(__x);
783  _Base::swap(__x);
784  }
785 
786  void
787  clear() noexcept
788  {
789  _Base::clear();
790  this->_M_invalidate_all();
791  }
792 
793  iterator
794  begin() noexcept
795  { return iterator(_Base::begin(), this); }
796 
797  const_iterator
798  begin() const noexcept
799  { return const_iterator(_Base::begin(), this); }
800 
801  iterator
802  end() noexcept
803  { return iterator(_Base::end(), this); }
804 
805  const_iterator
806  end() const noexcept
807  { return const_iterator(_Base::end(), this); }
808 
809  const_iterator
810  cbegin() const noexcept
811  { return const_iterator(_Base::begin(), this); }
812 
813  const_iterator
814  cend() const noexcept
815  { return const_iterator(_Base::end(), this); }
816 
817  // local versions
818  local_iterator
819  begin(size_type __b)
820  {
821  __glibcxx_check_bucket_index(__b);
822  return local_iterator(_Base::begin(__b), this);
823  }
824 
825  local_iterator
826  end(size_type __b)
827  {
828  __glibcxx_check_bucket_index(__b);
829  return local_iterator(_Base::end(__b), this);
830  }
831 
832  const_local_iterator
833  begin(size_type __b) const
834  {
835  __glibcxx_check_bucket_index(__b);
836  return const_local_iterator(_Base::begin(__b), this);
837  }
838 
839  const_local_iterator
840  end(size_type __b) const
841  {
842  __glibcxx_check_bucket_index(__b);
843  return const_local_iterator(_Base::end(__b), this);
844  }
845 
846  const_local_iterator
847  cbegin(size_type __b) const
848  {
849  __glibcxx_check_bucket_index(__b);
850  return const_local_iterator(_Base::cbegin(__b), this);
851  }
852 
853  const_local_iterator
854  cend(size_type __b) const
855  {
856  __glibcxx_check_bucket_index(__b);
857  return const_local_iterator(_Base::cend(__b), this);
858  }
859 
860  size_type
861  bucket_size(size_type __b) const
862  {
863  __glibcxx_check_bucket_index(__b);
864  return _Base::bucket_size(__b);
865  }
866 
867  float
868  max_load_factor() const noexcept
869  { return _Base::max_load_factor(); }
870 
871  void
872  max_load_factor(float __f)
873  {
874  __glibcxx_check_max_load_factor(__f);
875  _Base::max_load_factor(__f);
876  }
877 
878  template<typename... _Args>
879  iterator
880  emplace(_Args&&... __args)
881  {
882  size_type __bucket_count = this->bucket_count();
883  _Base_iterator __it
884  = _Base::emplace(std::forward<_Args>(__args)...);
885  _M_check_rehashed(__bucket_count);
886  return iterator(__it, this);
887  }
888 
889  template<typename... _Args>
890  iterator
891  emplace_hint(const_iterator __hint, _Args&&... __args)
892  {
893  __glibcxx_check_insert(__hint);
894  size_type __bucket_count = this->bucket_count();
895  _Base_iterator __it = _Base::emplace_hint(__hint.base(),
896  std::forward<_Args>(__args)...);
897  _M_check_rehashed(__bucket_count);
898  return iterator(__it, this);
899  }
900 
901  iterator
902  insert(const value_type& __obj)
903  {
904  size_type __bucket_count = this->bucket_count();
905  _Base_iterator __it = _Base::insert(__obj);
906  _M_check_rehashed(__bucket_count);
907  return iterator(__it, this);
908  }
909 
910  iterator
911  insert(const_iterator __hint, const value_type& __obj)
912  {
913  __glibcxx_check_insert(__hint);
914  size_type __bucket_count = this->bucket_count();
915  _Base_iterator __it = _Base::insert(__hint.base(), __obj);
916  _M_check_rehashed(__bucket_count);
917  return iterator(__it, this);
918  }
919 
920  template<typename _Pair, typename = typename
921  std::enable_if<std::is_constructible<value_type,
922  _Pair&&>::value>::type>
923  iterator
924  insert(_Pair&& __obj)
925  {
926  size_type __bucket_count = this->bucket_count();
927  _Base_iterator __it = _Base::insert(std::forward<_Pair>(__obj));
928  _M_check_rehashed(__bucket_count);
929  return iterator(__it, this);
930  }
931 
932  template<typename _Pair, typename = typename
933  std::enable_if<std::is_constructible<value_type,
934  _Pair&&>::value>::type>
935  iterator
936  insert(const_iterator __hint, _Pair&& __obj)
937  {
938  __glibcxx_check_insert(__hint);
939  size_type __bucket_count = this->bucket_count();
940  _Base_iterator __it =
941  _Base::insert(__hint.base(), std::forward<_Pair>(__obj));
942  _M_check_rehashed(__bucket_count);
943  return iterator(__it, this);
944  }
945 
946  void
947  insert(std::initializer_list<value_type> __l)
948  { _Base::insert(__l); }
949 
950  template<typename _InputIterator>
951  void
952  insert(_InputIterator __first, _InputIterator __last)
953  {
954  typename __gnu_debug::_Distance_traits<_InputIterator>::__type __dist;
955  __glibcxx_check_valid_range2(__first, __last, __dist);
956  size_type __bucket_count = this->bucket_count();
957 
958  if (__dist.second >= __gnu_debug::__dp_sign)
959  _Base::insert(__gnu_debug::__unsafe(__first),
960  __gnu_debug::__unsafe(__last));
961  else
962  _Base::insert(__first, __last);
963 
964  _M_check_rehashed(__bucket_count);
965  }
966 
967 #if __cplusplus > 201402L
968  using node_type = typename _Base::node_type;
969 
970  node_type
971  extract(const_iterator __position)
972  {
973  __glibcxx_check_erase(__position);
974  _Base_const_iterator __victim = __position.base();
975  this->_M_invalidate_if(
976  [__victim](_Base_const_iterator __it) { return __it == __victim; }
977  );
978  this->_M_invalidate_local_if(
979  [__victim](_Base_const_local_iterator __it) {
980  return __it._M_curr() == __victim._M_cur;
981  });
982  return _Base::extract(__position.base());
983  }
984 
985  node_type
986  extract(const key_type& __key)
987  {
988  const auto __position = find(__key);
989  if (__position != end())
990  return extract(__position);
991  return {};
992  }
993 
994  iterator
995  insert(node_type&& __nh)
996  { return iterator(_Base::insert(std::move(__nh)), this); }
997 
998  iterator
999  insert(const_iterator __hint, node_type&& __nh)
1000  {
1001  __glibcxx_check_insert(__hint);
1002  return iterator(_Base::insert(__hint.base(), std::move(__nh)), this);
1003  }
1004 
1005  using _Base::merge;
1006 #endif // C++17
1007 
1008  iterator
1009  find(const key_type& __key)
1010  { return iterator(_Base::find(__key), this); }
1011 
1012  const_iterator
1013  find(const key_type& __key) const
1014  { return const_iterator(_Base::find(__key), this); }
1015 
1016  std::pair<iterator, iterator>
1017  equal_range(const key_type& __key)
1018  {
1019  std::pair<_Base_iterator, _Base_iterator> __res =
1020  _Base::equal_range(__key);
1021  return std::make_pair(iterator(__res.first, this),
1022  iterator(__res.second, this));
1023  }
1024 
1025  std::pair<const_iterator, const_iterator>
1026  equal_range(const key_type& __key) const
1027  {
1028  std::pair<_Base_const_iterator, _Base_const_iterator> __res =
1029  _Base::equal_range(__key);
1030  return std::make_pair(const_iterator(__res.first, this),
1031  const_iterator(__res.second, this));
1032  }
1033 
1034  size_type
1035  erase(const key_type& __key)
1036  {
1037  size_type __ret(0);
1038  size_type __bucket_count = this->bucket_count();
1039  std::pair<_Base_iterator, _Base_iterator> __pair =
1040  _Base::equal_range(__key);
1041  for (_Base_iterator __victim = __pair.first; __victim != __pair.second;)
1042  {
1043  this->_M_invalidate_if([__victim](_Base_const_iterator __it)
1044  { return __it == __victim; });
1045  this->_M_invalidate_local_if(
1046  [__victim](_Base_const_local_iterator __it)
1047  { return __it._M_curr() == __victim._M_cur; });
1048  _Base::erase(__victim++);
1049  ++__ret;
1050  }
1051  _M_check_rehashed(__bucket_count);
1052  return __ret;
1053  }
1054 
1055  iterator
1056  erase(const_iterator __it)
1057  {
1058  __glibcxx_check_erase(__it);
1059  _Base_const_iterator __victim = __it.base();
1060  this->_M_invalidate_if([__victim](_Base_const_iterator __it)
1061  { return __it == __victim; });
1062  this->_M_invalidate_local_if(
1063  [__victim](_Base_const_local_iterator __it)
1064  { return __it._M_curr() == __victim._M_cur; });
1065  size_type __bucket_count = this->bucket_count();
1066  _Base_iterator __next = _Base::erase(__it.base());
1067  _M_check_rehashed(__bucket_count);
1068  return iterator(__next, this);
1069  }
1070 
1071  iterator
1072  erase(iterator __it)
1073  { return erase(const_iterator(__it)); }
1074 
1075  iterator
1076  erase(const_iterator __first, const_iterator __last)
1077  {
1078  __glibcxx_check_erase_range(__first, __last);
1079  for (_Base_const_iterator __tmp = __first.base();
1080  __tmp != __last.base(); ++__tmp)
1081  {
1082  _GLIBCXX_DEBUG_VERIFY(__tmp != _Base::end(),
1083  _M_message(__gnu_debug::__msg_valid_range)
1084  ._M_iterator(__first, "first")
1085  ._M_iterator(__last, "last"));
1086  this->_M_invalidate_if([__tmp](_Base_const_iterator __it)
1087  { return __it == __tmp; });
1088  this->_M_invalidate_local_if(
1089  [__tmp](_Base_const_local_iterator __it)
1090  { return __it._M_curr() == __tmp._M_cur; });
1091  }
1092  size_type __bucket_count = this->bucket_count();
1093  _Base_iterator __next = _Base::erase(__first.base(), __last.base());
1094  _M_check_rehashed(__bucket_count);
1095  return iterator(__next, this);
1096  }
1097 
1098  _Base&
1099  _M_base() noexcept { return *this; }
1100 
1101  const _Base&
1102  _M_base() const noexcept { return *this; }
1103 
1104  private:
1105  void
1106  _M_check_rehashed(size_type __prev_count)
1107  {
1108  if (__prev_count != this->bucket_count())
1109  this->_M_invalidate_locals();
1110  }
1111  };
1112 
1113  template<typename _Key, typename _Tp, typename _Hash,
1114  typename _Pred, typename _Alloc>
1115  inline void
1116  swap(unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
1117  unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
1118  noexcept(noexcept(__x.swap(__y)))
1119  { __x.swap(__y); }
1120 
1121  template<typename _Key, typename _Tp, typename _Hash,
1122  typename _Pred, typename _Alloc>
1123  inline bool
1124  operator==(const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
1125  const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
1126  { return __x._M_base() == __y._M_base(); }
1127 
1128  template<typename _Key, typename _Tp, typename _Hash,
1129  typename _Pred, typename _Alloc>
1130  inline bool
1131  operator!=(const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
1132  const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
1133  { return !(__x == __y); }
1134 
1135 } // namespace __debug
1136 } // namespace std
1137 
1138 #endif // C++11
1139 
1140 #endif