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 
40 #include <debug/safe_container.h>
41 #include <debug/safe_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> > >
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;
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 
79  _Base_iterator, unordered_map> iterator;
81  _Base_const_iterator, unordered_map> const_iterator;
83  _Base_local_iterator, unordered_map> 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 
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 
160  size_type __n,
161  const allocator_type& __a)
162  : unordered_map(__l, __n, hasher(), key_equal(), __a)
163  { }
164 
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 
175  operator=(const unordered_map&) = default;
176 
178  operator=(unordered_map&&) = default;
179 
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 
208  begin() const noexcept
209  { return const_iterator(_Base::begin(), this); }
210 
211  iterator
212  end() noexcept
213  { return iterator(_Base::end(), this); }
214 
216  end() const noexcept
217  { return const_iterator(_Base::end(), this); }
218 
220  cbegin() const noexcept
221  { return const_iterator(_Base::begin(), this); }
222 
224  cend() const noexcept
225  { return const_iterator(_Base::end(), this); }
226 
227  // local versions
229  begin(size_type __b)
230  {
231  __glibcxx_check_bucket_index(__b);
232  return local_iterator(_Base::begin(__b), this);
233  }
234 
236  end(size_type __b)
237  {
238  __glibcxx_check_bucket_index(__b);
239  return local_iterator(_Base::end(__b), this);
240  }
241 
243  begin(size_type __b) const
244  {
245  __glibcxx_check_bucket_index(__b);
246  return const_local_iterator(_Base::begin(__b), this);
247  }
248 
250  end(size_type __b) const
251  {
252  __glibcxx_check_bucket_index(__b);
253  return const_local_iterator(_Base::end(__b), this);
254  }
255 
257  cbegin(size_type __b) const
258  {
259  __glibcxx_check_bucket_index(__b);
260  return const_local_iterator(_Base::cbegin(__b), this);
261  }
262 
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>
290  emplace(_Args&&... __args)
291  {
292  size_type __bucket_count = this->bucket_count();
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 
312  insert(const value_type& __obj)
313  {
314  size_type __bucket_count = this->bucket_count();
315  auto __res = _Base::insert(__obj);
316  _M_check_rehashed(__bucket_count);
317  return { iterator(__res.first, this), __res.second };
318  }
319 
320  // _GLIBCXX_RESOLVE_LIB_DEFECTS
321  // 2354. Unnecessary copying when inserting into maps with braced-init
323  insert(value_type&& __x)
324  {
325  size_type __bucket_count = this->bucket_count();
326  auto __res = _Base::insert(std::move(__x));
327  _M_check_rehashed(__bucket_count);
328  return { iterator(__res.first, this), __res.second };
329  }
330 
331  template<typename _Pair, typename = typename
332  std::enable_if<std::is_constructible<value_type,
333  _Pair&&>::value>::type>
335  insert(_Pair&& __obj)
336  {
337  size_type __bucket_count = this->bucket_count();
339  _Base::insert(std::forward<_Pair>(__obj));
340  _M_check_rehashed(__bucket_count);
341  return std::make_pair(iterator(__res.first, this), __res.second);
342  }
343 
344  iterator
345  insert(const_iterator __hint, const value_type& __obj)
346  {
347  __glibcxx_check_insert(__hint);
348  size_type __bucket_count = this->bucket_count();
349  _Base_iterator __it = _Base::insert(__hint.base(), __obj);
350  _M_check_rehashed(__bucket_count);
351  return iterator(__it, this);
352  }
353 
354  // _GLIBCXX_RESOLVE_LIB_DEFECTS
355  // 2354. Unnecessary copying when inserting into maps with braced-init
356  iterator
357  insert(const_iterator __hint, value_type&& __x)
358  {
359  __glibcxx_check_insert(__hint);
360  size_type __bucket_count = this->bucket_count();
361  auto __it = _Base::insert(__hint.base(), std::move(__x));
362  _M_check_rehashed(__bucket_count);
363  return iterator(__it, this);
364  }
365 
366  template<typename _Pair, typename = typename
367  std::enable_if<std::is_constructible<value_type,
368  _Pair&&>::value>::type>
369  iterator
370  insert(const_iterator __hint, _Pair&& __obj)
371  {
372  __glibcxx_check_insert(__hint);
373  size_type __bucket_count = this->bucket_count();
374  _Base_iterator __it =
375  _Base::insert(__hint.base(), std::forward<_Pair>(__obj));
376  _M_check_rehashed(__bucket_count);
377  return iterator(__it, this);
378  }
379 
380  void
382  {
383  size_type __bucket_count = this->bucket_count();
384  _Base::insert(__l);
385  _M_check_rehashed(__bucket_count);
386  }
387 
388  template<typename _InputIterator>
389  void
390  insert(_InputIterator __first, _InputIterator __last)
391  {
393  __glibcxx_check_valid_range2(__first, __last, __dist);
394  size_type __bucket_count = this->bucket_count();
395 
396  if (__dist.second >= __gnu_debug::__dp_sign)
397  _Base::insert(__gnu_debug::__unsafe(__first),
398  __gnu_debug::__unsafe(__last));
399  else
400  _Base::insert(__first, __last);
401 
402  _M_check_rehashed(__bucket_count);
403  }
404 
405 #if __cplusplus > 201402L
406  template <typename... _Args>
408  try_emplace(const key_type& __k, _Args&&... __args)
409  {
410  auto __res = _Base::try_emplace(__k,
411  std::forward<_Args>(__args)...);
412  return { iterator(__res.first, this), __res.second };
413  }
414 
415  template <typename... _Args>
417  try_emplace(key_type&& __k, _Args&&... __args)
418  {
419  auto __res = _Base::try_emplace(std::move(__k),
420  std::forward<_Args>(__args)...);
421  return { iterator(__res.first, this), __res.second };
422  }
423 
424  template <typename... _Args>
425  iterator
426  try_emplace(const_iterator __hint, const key_type& __k,
427  _Args&&... __args)
428  {
429  __glibcxx_check_insert(__hint);
430  return iterator(_Base::try_emplace(__hint.base(), __k,
431  std::forward<_Args>(__args)...),
432  this);
433  }
434 
435  template <typename... _Args>
436  iterator
437  try_emplace(const_iterator __hint, key_type&& __k, _Args&&... __args)
438  {
439  __glibcxx_check_insert(__hint);
440  return iterator(_Base::try_emplace(__hint.base(), std::move(__k),
441  std::forward<_Args>(__args)...),
442  this);
443  }
444 
445  template <typename _Obj>
447  insert_or_assign(const key_type& __k, _Obj&& __obj)
448  {
449  auto __res = _Base::insert_or_assign(__k,
450  std::forward<_Obj>(__obj));
451  return { iterator(__res.first, this), __res.second };
452  }
453 
454  template <typename _Obj>
456  insert_or_assign(key_type&& __k, _Obj&& __obj)
457  {
458  auto __res = _Base::insert_or_assign(std::move(__k),
459  std::forward<_Obj>(__obj));
460  return { iterator(__res.first, this), __res.second };
461  }
462 
463  template <typename _Obj>
464  iterator
465  insert_or_assign(const_iterator __hint, const key_type& __k,
466  _Obj&& __obj)
467  {
468  __glibcxx_check_insert(__hint);
469  return iterator(_Base::insert_or_assign(__hint.base(), __k,
470  std::forward<_Obj>(__obj)),
471  this);
472  }
473 
474  template <typename _Obj>
475  iterator
476  insert_or_assign(const_iterator __hint, key_type&& __k, _Obj&& __obj)
477  {
478  __glibcxx_check_insert(__hint);
479  return iterator(_Base::insert_or_assign(__hint.base(),
480  std::move(__k),
481  std::forward<_Obj>(__obj)),
482  this);
483  }
484 #endif // C++17
485 
486 #if __cplusplus > 201402L
487  using node_type = typename _Base::node_type;
488 
489  struct insert_return_type
490  {
491  bool inserted;
492  iterator position;
493  node_type node;
494  };
495 
496  node_type
497  extract(const_iterator __position)
498  {
499  __glibcxx_check_erase(__position);
500  _Base_const_iterator __victim = __position.base();
501  this->_M_invalidate_if(
502  [__victim](_Base_const_iterator __it) { return __it == __victim; }
503  );
505  [__victim](_Base_const_local_iterator __it) {
506  return __it._M_curr() == __victim._M_cur;
507  });
508  return _Base::extract(__position.base());
509  }
510 
511  node_type
512  extract(const key_type& __key)
513  {
514  const auto __position = find(__key);
515  if (__position != end())
516  return extract(__position);
517  return {};
518  }
519 
520  insert_return_type
521  insert(node_type&& __nh)
522  {
523  auto __ret = _Base::insert(std::move(__nh));
524  iterator __pos = iterator(__ret.position, this);
525  return { __ret.inserted, __pos, std::move(__ret.node) };
526  }
527 
528  iterator
529  insert(const_iterator __hint, node_type&& __nh)
530  {
531  __glibcxx_check_insert(__hint);
532  return iterator(_Base::insert(__hint.base(), std::move(__nh)), this);
533  }
534 
535  using _Base::merge;
536 #endif // C++17
537 
538  iterator
539  find(const key_type& __key)
540  { return iterator(_Base::find(__key), this); }
541 
543  find(const key_type& __key) const
544  { return const_iterator(_Base::find(__key), this); }
545 
547  equal_range(const key_type& __key)
548  {
550  _Base::equal_range(__key);
551  return std::make_pair(iterator(__res.first, this),
552  iterator(__res.second, this));
553  }
554 
556  equal_range(const key_type& __key) const
557  {
559  _Base::equal_range(__key);
560  return std::make_pair(const_iterator(__res.first, this),
561  const_iterator(__res.second, this));
562  }
563 
564  size_type
565  erase(const key_type& __key)
566  {
567  size_type __ret(0);
568  _Base_iterator __victim(_Base::find(__key));
569  if (__victim != _Base::end())
570  {
571  this->_M_invalidate_if([__victim](_Base_const_iterator __it)
572  { return __it == __victim; });
574  [__victim](_Base_const_local_iterator __it)
575  { return __it._M_curr() == __victim._M_cur; });
576  size_type __bucket_count = this->bucket_count();
577  _Base::erase(__victim);
578  _M_check_rehashed(__bucket_count);
579  __ret = 1;
580  }
581  return __ret;
582  }
583 
584  iterator
585  erase(const_iterator __it)
586  {
587  __glibcxx_check_erase(__it);
588  _Base_const_iterator __victim = __it.base();
589  this->_M_invalidate_if([__victim](_Base_const_iterator __it)
590  { return __it == __victim; });
592  [__victim](_Base_const_local_iterator __it)
593  { return __it._M_curr() == __victim._M_cur; });
594  size_type __bucket_count = this->bucket_count();
595  _Base_iterator __next = _Base::erase(__it.base());
596  _M_check_rehashed(__bucket_count);
597  return iterator(__next, this);
598  }
599 
600  iterator
601  erase(iterator __it)
602  { return erase(const_iterator(__it)); }
603 
604  iterator
605  erase(const_iterator __first, const_iterator __last)
606  {
607  __glibcxx_check_erase_range(__first, __last);
608  for (_Base_const_iterator __tmp = __first.base();
609  __tmp != __last.base(); ++__tmp)
610  {
611  _GLIBCXX_DEBUG_VERIFY(__tmp != _Base::end(),
612  _M_message(__gnu_debug::__msg_valid_range)
613  ._M_iterator(__first, "first")
614  ._M_iterator(__last, "last"));
615  this->_M_invalidate_if([__tmp](_Base_const_iterator __it)
616  { return __it == __tmp; });
618  [__tmp](_Base_const_local_iterator __it)
619  { return __it._M_curr() == __tmp._M_cur; });
620  }
621  size_type __bucket_count = this->bucket_count();
622  _Base_iterator __next = _Base::erase(__first.base(), __last.base());
623  _M_check_rehashed(__bucket_count);
624  return iterator(__next, this);
625  }
626 
627  _Base&
628  _M_base() noexcept { return *this; }
629 
630  const _Base&
631  _M_base() const noexcept { return *this; }
632 
633  private:
634  void
635  _M_check_rehashed(size_type __prev_count)
636  {
637  if (__prev_count != this->bucket_count())
638  this->_M_invalidate_locals();
639  }
640  };
641 
642  template<typename _Key, typename _Tp, typename _Hash,
643  typename _Pred, typename _Alloc>
644  inline void
647  noexcept(noexcept(__x.swap(__y)))
648  { __x.swap(__y); }
649 
650  template<typename _Key, typename _Tp, typename _Hash,
651  typename _Pred, typename _Alloc>
652  inline bool
655  { return __x._M_base() == __y._M_base(); }
656 
657  template<typename _Key, typename _Tp, typename _Hash,
658  typename _Pred, typename _Alloc>
659  inline bool
660  operator!=(const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
661  const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
662  { return !(__x == __y); }
663 
664 
665  /// Class std::unordered_multimap with safety/checking/debug instrumentation.
666  template<typename _Key, typename _Tp,
667  typename _Hash = std::hash<_Key>,
668  typename _Pred = std::equal_to<_Key>,
669  typename _Alloc = std::allocator<std::pair<const _Key, _Tp> > >
672  unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>, _Alloc,
673  __gnu_debug::_Safe_unordered_container>,
674  public _GLIBCXX_STD_C::unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>
675  {
676  typedef _GLIBCXX_STD_C::unordered_multimap<_Key, _Tp, _Hash,
677  _Pred, _Alloc> _Base;
680  typedef typename _Base::const_iterator _Base_const_iterator;
681  typedef typename _Base::iterator _Base_iterator;
682  typedef typename _Base::const_local_iterator _Base_const_local_iterator;
683  typedef typename _Base::local_iterator _Base_local_iterator;
684 
685  public:
686  typedef typename _Base::size_type size_type;
687  typedef typename _Base::hasher hasher;
688  typedef typename _Base::key_equal key_equal;
689  typedef typename _Base::allocator_type allocator_type;
690 
691  typedef typename _Base::key_type key_type;
692  typedef typename _Base::value_type value_type;
693 
695  _Base_iterator, unordered_multimap> iterator;
697  _Base_const_iterator, unordered_multimap> const_iterator;
699  _Base_local_iterator, unordered_multimap> local_iterator;
701  _Base_const_local_iterator, unordered_multimap> const_local_iterator;
702 
703  unordered_multimap() = default;
704 
705  explicit
706  unordered_multimap(size_type __n,
707  const hasher& __hf = hasher(),
708  const key_equal& __eql = key_equal(),
709  const allocator_type& __a = allocator_type())
710  : _Base(__n, __hf, __eql, __a) { }
711 
712  template<typename _InputIterator>
713  unordered_multimap(_InputIterator __first, _InputIterator __last,
714  size_type __n = 0,
715  const hasher& __hf = hasher(),
716  const key_equal& __eql = key_equal(),
717  const allocator_type& __a = allocator_type())
718  : _Base(__gnu_debug::__base(__gnu_debug::__check_valid_range(__first,
719  __last)),
720  __gnu_debug::__base(__last), __n,
721  __hf, __eql, __a) { }
722 
723  unordered_multimap(const unordered_multimap&) = default;
724 
725  unordered_multimap(const _Base& __x)
726  : _Base(__x) { }
727 
729 
730  explicit
731  unordered_multimap(const allocator_type& __a)
732  : _Base(__a) { }
733 
735  const allocator_type& __a)
736  : _Base(__umap, __a) { }
737 
739  const allocator_type& __a)
740  : _Safe(std::move(__umap._M_safe()), __a),
741  _Base(std::move(__umap._M_base()), __a) { }
742 
744  size_type __n = 0,
745  const hasher& __hf = hasher(),
746  const key_equal& __eql = key_equal(),
747  const allocator_type& __a = allocator_type())
748  : _Base(__l, __n, __hf, __eql, __a) { }
749 
750  unordered_multimap(size_type __n, const allocator_type& __a)
751  : unordered_multimap(__n, hasher(), key_equal(), __a)
752  { }
753 
754  unordered_multimap(size_type __n, const hasher& __hf,
755  const allocator_type& __a)
756  : unordered_multimap(__n, __hf, key_equal(), __a)
757  { }
758 
759  template<typename _InputIterator>
760  unordered_multimap(_InputIterator __first, _InputIterator __last,
761  size_type __n,
762  const allocator_type& __a)
763  : unordered_multimap(__first, __last, __n, hasher(), key_equal(), __a)
764  { }
765 
766  template<typename _InputIterator>
767  unordered_multimap(_InputIterator __first, _InputIterator __last,
768  size_type __n, const hasher& __hf,
769  const allocator_type& __a)
770  : unordered_multimap(__first, __last, __n, __hf, key_equal(), __a)
771  { }
772 
774  size_type __n,
775  const allocator_type& __a)
776  : unordered_multimap(__l, __n, hasher(), key_equal(), __a)
777  { }
778 
780  size_type __n, const hasher& __hf,
781  const allocator_type& __a)
782  : unordered_multimap(__l, __n, __hf, key_equal(), __a)
783  { }
784 
785  ~unordered_multimap() = default;
786 
788  operator=(const unordered_multimap&) = default;
789 
791  operator=(unordered_multimap&&) = default;
792 
794  operator=(initializer_list<value_type> __l)
795  {
796  this->_M_base() = __l;
797  this->_M_invalidate_all();
798  return *this;
799  }
800 
801  void
802  swap(unordered_multimap& __x)
803  noexcept( noexcept(declval<_Base&>().swap(__x)) )
804  {
805  _Safe::_M_swap(__x);
806  _Base::swap(__x);
807  }
808 
809  void
810  clear() noexcept
811  {
812  _Base::clear();
813  this->_M_invalidate_all();
814  }
815 
816  iterator
817  begin() noexcept
818  { return iterator(_Base::begin(), this); }
819 
821  begin() const noexcept
822  { return const_iterator(_Base::begin(), this); }
823 
824  iterator
825  end() noexcept
826  { return iterator(_Base::end(), this); }
827 
829  end() const noexcept
830  { return const_iterator(_Base::end(), this); }
831 
833  cbegin() const noexcept
834  { return const_iterator(_Base::begin(), this); }
835 
837  cend() const noexcept
838  { return const_iterator(_Base::end(), this); }
839 
840  // local versions
842  begin(size_type __b)
843  {
844  __glibcxx_check_bucket_index(__b);
845  return local_iterator(_Base::begin(__b), this);
846  }
847 
849  end(size_type __b)
850  {
851  __glibcxx_check_bucket_index(__b);
852  return local_iterator(_Base::end(__b), this);
853  }
854 
856  begin(size_type __b) const
857  {
858  __glibcxx_check_bucket_index(__b);
859  return const_local_iterator(_Base::begin(__b), this);
860  }
861 
863  end(size_type __b) const
864  {
865  __glibcxx_check_bucket_index(__b);
866  return const_local_iterator(_Base::end(__b), this);
867  }
868 
870  cbegin(size_type __b) const
871  {
872  __glibcxx_check_bucket_index(__b);
873  return const_local_iterator(_Base::cbegin(__b), this);
874  }
875 
877  cend(size_type __b) const
878  {
879  __glibcxx_check_bucket_index(__b);
880  return const_local_iterator(_Base::cend(__b), this);
881  }
882 
883  size_type
884  bucket_size(size_type __b) const
885  {
886  __glibcxx_check_bucket_index(__b);
887  return _Base::bucket_size(__b);
888  }
889 
890  float
891  max_load_factor() const noexcept
892  { return _Base::max_load_factor(); }
893 
894  void
895  max_load_factor(float __f)
896  {
897  __glibcxx_check_max_load_factor(__f);
898  _Base::max_load_factor(__f);
899  }
900 
901  template<typename... _Args>
902  iterator
903  emplace(_Args&&... __args)
904  {
905  size_type __bucket_count = this->bucket_count();
906  _Base_iterator __it
907  = _Base::emplace(std::forward<_Args>(__args)...);
908  _M_check_rehashed(__bucket_count);
909  return iterator(__it, this);
910  }
911 
912  template<typename... _Args>
913  iterator
914  emplace_hint(const_iterator __hint, _Args&&... __args)
915  {
916  __glibcxx_check_insert(__hint);
917  size_type __bucket_count = this->bucket_count();
918  _Base_iterator __it = _Base::emplace_hint(__hint.base(),
919  std::forward<_Args>(__args)...);
920  _M_check_rehashed(__bucket_count);
921  return iterator(__it, this);
922  }
923 
924  iterator
925  insert(const value_type& __obj)
926  {
927  size_type __bucket_count = this->bucket_count();
928  _Base_iterator __it = _Base::insert(__obj);
929  _M_check_rehashed(__bucket_count);
930  return iterator(__it, this);
931  }
932 
933  // _GLIBCXX_RESOLVE_LIB_DEFECTS
934  // 2354. Unnecessary copying when inserting into maps with braced-init
935  iterator
936  insert(value_type&& __x)
937  {
938  size_type __bucket_count = this->bucket_count();
939  auto __it = _Base::insert(std::move(__x));
940  _M_check_rehashed(__bucket_count);
941  return { __it, this };
942  }
943 
944  iterator
945  insert(const_iterator __hint, const value_type& __obj)
946  {
947  __glibcxx_check_insert(__hint);
948  size_type __bucket_count = this->bucket_count();
949  _Base_iterator __it = _Base::insert(__hint.base(), __obj);
950  _M_check_rehashed(__bucket_count);
951  return iterator(__it, this);
952  }
953 
954  // _GLIBCXX_RESOLVE_LIB_DEFECTS
955  // 2354. Unnecessary copying when inserting into maps with braced-init
956  iterator
957  insert(const_iterator __hint, value_type&& __x)
958  {
959  __glibcxx_check_insert(__hint);
960  size_type __bucket_count = this->bucket_count();
961  auto __it = _Base::insert(__hint.base(), std::move(__x));
962  _M_check_rehashed(__bucket_count);
963  return iterator(__it, this);
964  }
965 
966  template<typename _Pair, typename = typename
967  std::enable_if<std::is_constructible<value_type,
968  _Pair&&>::value>::type>
969  iterator
970  insert(_Pair&& __obj)
971  {
972  size_type __bucket_count = this->bucket_count();
973  _Base_iterator __it = _Base::insert(std::forward<_Pair>(__obj));
974  _M_check_rehashed(__bucket_count);
975  return iterator(__it, this);
976  }
977 
978  template<typename _Pair, typename = typename
979  std::enable_if<std::is_constructible<value_type,
980  _Pair&&>::value>::type>
981  iterator
982  insert(const_iterator __hint, _Pair&& __obj)
983  {
984  __glibcxx_check_insert(__hint);
985  size_type __bucket_count = this->bucket_count();
986  _Base_iterator __it =
987  _Base::insert(__hint.base(), std::forward<_Pair>(__obj));
988  _M_check_rehashed(__bucket_count);
989  return iterator(__it, this);
990  }
991 
992  void
994  { _Base::insert(__l); }
995 
996  template<typename _InputIterator>
997  void
998  insert(_InputIterator __first, _InputIterator __last)
999  {
1001  __glibcxx_check_valid_range2(__first, __last, __dist);
1002  size_type __bucket_count = this->bucket_count();
1003 
1004  if (__dist.second >= __gnu_debug::__dp_sign)
1005  _Base::insert(__gnu_debug::__unsafe(__first),
1006  __gnu_debug::__unsafe(__last));
1007  else
1008  _Base::insert(__first, __last);
1009 
1010  _M_check_rehashed(__bucket_count);
1011  }
1012 
1013 #if __cplusplus > 201402L
1014  using node_type = typename _Base::node_type;
1015 
1016  node_type
1017  extract(const_iterator __position)
1018  {
1019  __glibcxx_check_erase(__position);
1020  _Base_const_iterator __victim = __position.base();
1021  this->_M_invalidate_if(
1022  [__victim](_Base_const_iterator __it) { return __it == __victim; }
1023  );
1024  this->_M_invalidate_local_if(
1025  [__victim](_Base_const_local_iterator __it) {
1026  return __it._M_curr() == __victim._M_cur;
1027  });
1028  return _Base::extract(__position.base());
1029  }
1030 
1031  node_type
1032  extract(const key_type& __key)
1033  {
1034  const auto __position = find(__key);
1035  if (__position != end())
1036  return extract(__position);
1037  return {};
1038  }
1039 
1040  iterator
1041  insert(node_type&& __nh)
1042  { return iterator(_Base::insert(std::move(__nh)), this); }
1043 
1044  iterator
1045  insert(const_iterator __hint, node_type&& __nh)
1046  {
1047  __glibcxx_check_insert(__hint);
1048  return iterator(_Base::insert(__hint.base(), std::move(__nh)), this);
1049  }
1050 
1051  using _Base::merge;
1052 #endif // C++17
1053 
1054  iterator
1055  find(const key_type& __key)
1056  { return iterator(_Base::find(__key), this); }
1057 
1059  find(const key_type& __key) const
1060  { return const_iterator(_Base::find(__key), this); }
1061 
1063  equal_range(const key_type& __key)
1064  {
1066  _Base::equal_range(__key);
1067  return std::make_pair(iterator(__res.first, this),
1068  iterator(__res.second, this));
1069  }
1070 
1072  equal_range(const key_type& __key) const
1073  {
1075  _Base::equal_range(__key);
1076  return std::make_pair(const_iterator(__res.first, this),
1077  const_iterator(__res.second, this));
1078  }
1079 
1080  size_type
1081  erase(const key_type& __key)
1082  {
1083  size_type __ret(0);
1084  size_type __bucket_count = this->bucket_count();
1086  _Base::equal_range(__key);
1087  for (_Base_iterator __victim = __pair.first; __victim != __pair.second;)
1088  {
1089  this->_M_invalidate_if([__victim](_Base_const_iterator __it)
1090  { return __it == __victim; });
1091  this->_M_invalidate_local_if(
1092  [__victim](_Base_const_local_iterator __it)
1093  { return __it._M_curr() == __victim._M_cur; });
1094  _Base::erase(__victim++);
1095  ++__ret;
1096  }
1097  _M_check_rehashed(__bucket_count);
1098  return __ret;
1099  }
1100 
1101  iterator
1102  erase(const_iterator __it)
1103  {
1104  __glibcxx_check_erase(__it);
1105  _Base_const_iterator __victim = __it.base();
1106  this->_M_invalidate_if([__victim](_Base_const_iterator __it)
1107  { return __it == __victim; });
1108  this->_M_invalidate_local_if(
1109  [__victim](_Base_const_local_iterator __it)
1110  { return __it._M_curr() == __victim._M_cur; });
1111  size_type __bucket_count = this->bucket_count();
1112  _Base_iterator __next = _Base::erase(__it.base());
1113  _M_check_rehashed(__bucket_count);
1114  return iterator(__next, this);
1115  }
1116 
1117  iterator
1118  erase(iterator __it)
1119  { return erase(const_iterator(__it)); }
1120 
1121  iterator
1122  erase(const_iterator __first, const_iterator __last)
1123  {
1124  __glibcxx_check_erase_range(__first, __last);
1125  for (_Base_const_iterator __tmp = __first.base();
1126  __tmp != __last.base(); ++__tmp)
1127  {
1128  _GLIBCXX_DEBUG_VERIFY(__tmp != _Base::end(),
1129  _M_message(__gnu_debug::__msg_valid_range)
1130  ._M_iterator(__first, "first")
1131  ._M_iterator(__last, "last"));
1132  this->_M_invalidate_if([__tmp](_Base_const_iterator __it)
1133  { return __it == __tmp; });
1134  this->_M_invalidate_local_if(
1135  [__tmp](_Base_const_local_iterator __it)
1136  { return __it._M_curr() == __tmp._M_cur; });
1137  }
1138  size_type __bucket_count = this->bucket_count();
1139  _Base_iterator __next = _Base::erase(__first.base(), __last.base());
1140  _M_check_rehashed(__bucket_count);
1141  return iterator(__next, this);
1142  }
1143 
1144  _Base&
1145  _M_base() noexcept { return *this; }
1146 
1147  const _Base&
1148  _M_base() const noexcept { return *this; }
1149 
1150  private:
1151  void
1152  _M_check_rehashed(size_type __prev_count)
1153  {
1154  if (__prev_count != this->bucket_count())
1155  this->_M_invalidate_locals();
1156  }
1157  };
1158 
1159  template<typename _Key, typename _Tp, typename _Hash,
1160  typename _Pred, typename _Alloc>
1161  inline void
1164  noexcept(noexcept(__x.swap(__y)))
1165  { __x.swap(__y); }
1166 
1167  template<typename _Key, typename _Tp, typename _Hash,
1168  typename _Pred, typename _Alloc>
1169  inline bool
1172  { return __x._M_base() == __y._M_base(); }
1173 
1174  template<typename _Key, typename _Tp, typename _Hash,
1175  typename _Pred, typename _Alloc>
1176  inline bool
1177  operator!=(const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
1178  const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
1179  { return !(__x == __y); }
1180 
1181 } // namespace __debug
1182 } // namespace std
1183 
1184 #endif // C++11
1185 
1186 #endif
Safe iterator wrapper.
Definition: formatter.h:59
A standard container composed of unique keys (containing at most one of each key value) that associat...
constexpr pair< typename __decay_and_strip< _T1 >::__type, typename __decay_and_strip< _T2 >::__type > make_pair(_T1 &&__x, _T2 &&__y)
A convenience wrapper for creating a pair from two objects.
Definition: stl_pair.h:519
_Iterator & base() noexcept
Return the underlying iterator.
Primary class template hash.
Definition: system_error:142
Base class for constructing a safe unordered container type that tracks iterators that reference it...
Class std::unordered_multimap with safety/checking/debug instrumentation.
The standard allocator, as per [20.4].
Definition: allocator.h:108
#define __glibcxx_check_erase_range(_First, _Last)
Definition: macros.h:173
One of the comparison functors.
Definition: stl_function.h:331
#define __glibcxx_check_insert(_Position)
Definition: macros.h:79
Safe class dealing with some allocator dependent operations.
Base class that supports tracking of iterators that reference a sequence.
Definition: safe_base.h:188
Class std::unordered_map with safety/checking/debug instrumentation.
initializer_list
_T2 second
first is a copy of the first object
Definition: stl_pair.h:204
Safe iterator wrapper.
Definition: formatter.h:56
Struct holding two objects of arbitrary type.
Definition: stl_pair.h:198
_T1 first
second_type is the second bound type
Definition: stl_pair.h:203
A standard container composed of equivalent keys (possibly containing multiple of each key value) tha...
Definition: unordered_map.h:72
#define __glibcxx_check_erase(_Position)
Definition: macros.h:145