libstdc++
debug/unordered_map
Go to the documentation of this file.
1 // Debugging unordered_map/unordered_multimap implementation -*- C++ -*-
2 
3 // Copyright (C) 2003-2021 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 <bits/c++config.h>
38 namespace std _GLIBCXX_VISIBILITY(default) { namespace __debug {
39  template<typename _Key, typename _Tp, typename _Hash, typename _Pred,
40  typename _Allocator>
41  class unordered_map;
42  template<typename _Key, typename _Tp, typename _Hash, typename _Pred,
43  typename _Allocator>
44  class unordered_multimap;
45 } } // namespace std::__debug
46 
47 # include <unordered_map>
48 
50 #include <debug/safe_container.h>
51 #include <debug/safe_iterator.h>
53 
54 namespace std _GLIBCXX_VISIBILITY(default)
55 {
56 namespace __debug
57 {
58  /// Class std::unordered_map with safety/checking/debug instrumentation.
59  template<typename _Key, typename _Tp,
60  typename _Hash = std::hash<_Key>,
61  typename _Pred = std::equal_to<_Key>,
62  typename _Alloc = std::allocator<std::pair<const _Key, _Tp> > >
65  unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>, _Alloc,
66  __gnu_debug::_Safe_unordered_container>,
67  public _GLIBCXX_STD_C::unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>
68  {
69  typedef _GLIBCXX_STD_C::unordered_map<_Key, _Tp, _Hash,
70  _Pred, _Alloc> _Base;
73  typedef typename _Base::const_iterator _Base_const_iterator;
74  typedef typename _Base::iterator _Base_iterator;
75  typedef typename _Base::const_local_iterator
76  _Base_const_local_iterator;
77  typedef typename _Base::local_iterator _Base_local_iterator;
78 
79  template<typename _ItT, typename _SeqT, typename _CatT>
80  friend class ::__gnu_debug::_Safe_iterator;
81  template<typename _ItT, typename _SeqT>
82  friend class ::__gnu_debug::_Safe_local_iterator;
83 
84  // Reference wrapper for base class. See PR libstdc++/90102.
85  struct _Base_ref
86  {
87  _Base_ref(const _Base& __r) : _M_ref(__r) { }
88 
89  const _Base& _M_ref;
90  };
91 
92  public:
93  typedef typename _Base::size_type size_type;
94  typedef typename _Base::hasher hasher;
95  typedef typename _Base::key_equal key_equal;
96  typedef typename _Base::allocator_type allocator_type;
97 
98  typedef typename _Base::key_type key_type;
99  typedef typename _Base::value_type value_type;
100 
102  _Base_iterator, unordered_map> iterator;
104  _Base_const_iterator, unordered_map> const_iterator;
106  _Base_local_iterator, unordered_map> local_iterator;
108  _Base_const_local_iterator, unordered_map> const_local_iterator;
109 
110  unordered_map() = default;
111 
112  explicit
113  unordered_map(size_type __n,
114  const hasher& __hf = hasher(),
115  const key_equal& __eql = key_equal(),
116  const allocator_type& __a = allocator_type())
117  : _Base(__n, __hf, __eql, __a) { }
118 
119  template<typename _InputIterator>
120  unordered_map(_InputIterator __first, _InputIterator __last,
121  size_type __n = 0,
122  const hasher& __hf = hasher(),
123  const key_equal& __eql = key_equal(),
124  const allocator_type& __a = allocator_type())
126  __glibcxx_check_valid_constructor_range(__first, __last)),
127  __gnu_debug::__base(__last), __n,
128  __hf, __eql, __a) { }
129 
130  unordered_map(const unordered_map&) = default;
131 
132  unordered_map(_Base_ref __x)
133  : _Base(__x._M_ref) { }
134 
135  unordered_map(unordered_map&&) = default;
136 
137  explicit
138  unordered_map(const allocator_type& __a)
139  : _Base(__a) { }
140 
141  unordered_map(const unordered_map& __umap,
142  const allocator_type& __a)
143  : _Base(__umap, __a) { }
144 
145  unordered_map(unordered_map&& __umap,
146  const allocator_type& __a)
147  noexcept( noexcept(_Base(std::move(__umap._M_base()), __a)) )
148  : _Safe(std::move(__umap._M_safe()), __a),
149  _Base(std::move(__umap._M_base()), __a) { }
150 
152  size_type __n = 0,
153  const hasher& __hf = hasher(),
154  const key_equal& __eql = key_equal(),
155  const allocator_type& __a = allocator_type())
156  : _Base(__l, __n, __hf, __eql, __a) { }
157 
158  unordered_map(size_type __n, const allocator_type& __a)
159  : unordered_map(__n, hasher(), key_equal(), __a)
160  { }
161 
162  unordered_map(size_type __n,
163  const hasher& __hf,
164  const allocator_type& __a)
165  : unordered_map(__n, __hf, key_equal(), __a)
166  { }
167 
168  template<typename _InputIterator>
169  unordered_map(_InputIterator __first, _InputIterator __last,
170  size_type __n,
171  const allocator_type& __a)
172  : unordered_map(__first, __last, __n, hasher(), key_equal(), __a)
173  { }
174 
175  template<typename _InputIterator>
176  unordered_map(_InputIterator __first, _InputIterator __last,
177  size_type __n,
178  const hasher& __hf,
179  const allocator_type& __a)
180  : unordered_map(__first, __last, __n, __hf, key_equal(), __a)
181  { }
182 
184  size_type __n,
185  const allocator_type& __a)
186  : unordered_map(__l, __n, hasher(), key_equal(), __a)
187  { }
188 
190  size_type __n,
191  const hasher& __hf,
192  const allocator_type& __a)
193  : unordered_map(__l, __n, __hf, key_equal(), __a)
194  { }
195 
196  ~unordered_map() = default;
197 
199  operator=(const unordered_map&) = default;
200 
202  operator=(unordered_map&&) = default;
203 
205  operator=(initializer_list<value_type> __l)
206  {
207  _M_base() = __l;
208  this->_M_invalidate_all();
209  return *this;
210  }
211 
212  void
213  swap(unordered_map& __x)
214  noexcept( noexcept(declval<_Base&>().swap(__x)) )
215  {
216  _Safe::_M_swap(__x);
217  _Base::swap(__x);
218  }
219 
220  void
221  clear() noexcept
222  {
223  _Base::clear();
224  this->_M_invalidate_all();
225  }
226 
227  iterator
228  begin() noexcept
229  { return { _Base::begin(), this }; }
230 
232  begin() const noexcept
233  { return { _Base::begin(), this }; }
234 
235  iterator
236  end() noexcept
237  { return { _Base::end(), this }; }
238 
240  end() const noexcept
241  { return { _Base::end(), this }; }
242 
244  cbegin() const noexcept
245  { return { _Base::cbegin(), this }; }
246 
248  cend() const noexcept
249  { return { _Base::cend(), this }; }
250 
251  // local versions
253  begin(size_type __b)
254  {
255  __glibcxx_check_bucket_index(__b);
256  return { _Base::begin(__b), this };
257  }
258 
260  end(size_type __b)
261  {
262  __glibcxx_check_bucket_index(__b);
263  return { _Base::end(__b), this };
264  }
265 
267  begin(size_type __b) const
268  {
269  __glibcxx_check_bucket_index(__b);
270  return { _Base::begin(__b), this };
271  }
272 
274  end(size_type __b) const
275  {
276  __glibcxx_check_bucket_index(__b);
277  return { _Base::end(__b), this };
278  }
279 
281  cbegin(size_type __b) const
282  {
283  __glibcxx_check_bucket_index(__b);
284  return { _Base::cbegin(__b), this };
285  }
286 
288  cend(size_type __b) const
289  {
290  __glibcxx_check_bucket_index(__b);
291  return { _Base::cend(__b), this };
292  }
293 
294  size_type
295  bucket_size(size_type __b) const
296  {
297  __glibcxx_check_bucket_index(__b);
298  return _Base::bucket_size(__b);
299  }
300 
301  float
302  max_load_factor() const noexcept
303  { return _Base::max_load_factor(); }
304 
305  void
306  max_load_factor(float __f)
307  {
308  __glibcxx_check_max_load_factor(__f);
309  _Base::max_load_factor(__f);
310  }
311 
312  template<typename... _Args>
314  emplace(_Args&&... __args)
315  {
316  size_type __bucket_count = this->bucket_count();
317  auto __res = _Base::emplace(std::forward<_Args>(__args)...);
318  _M_check_rehashed(__bucket_count);
319  return { { __res.first, this }, __res.second };
320  }
321 
322  template<typename... _Args>
323  iterator
324  emplace_hint(const_iterator __hint, _Args&&... __args)
325  {
326  __glibcxx_check_insert(__hint);
327  size_type __bucket_count = this->bucket_count();
328  auto __it = _Base::emplace_hint(__hint.base(),
329  std::forward<_Args>(__args)...);
330  _M_check_rehashed(__bucket_count);
331  return { __it, this };
332  }
333 
335  insert(const value_type& __obj)
336  {
337  size_type __bucket_count = this->bucket_count();
338  auto __res = _Base::insert(__obj);
339  _M_check_rehashed(__bucket_count);
340  return { { __res.first, this }, __res.second };
341  }
342 
343  // _GLIBCXX_RESOLVE_LIB_DEFECTS
344  // 2354. Unnecessary copying when inserting into maps with braced-init
346  insert(value_type&& __x)
347  {
348  size_type __bucket_count = this->bucket_count();
349  auto __res = _Base::insert(std::move(__x));
350  _M_check_rehashed(__bucket_count);
351  return { { __res.first, this }, __res.second };
352  }
353 
354  template<typename _Pair, typename = typename
356  _Pair&&>::value>::type>
358  insert(_Pair&& __obj)
359  {
360  size_type __bucket_count = this->bucket_count();
361  auto __res = _Base::insert(std::forward<_Pair>(__obj));
362  _M_check_rehashed(__bucket_count);
363  return { { __res.first, this }, __res.second };
364  }
365 
366  iterator
367  insert(const_iterator __hint, const value_type& __obj)
368  {
369  __glibcxx_check_insert(__hint);
370  size_type __bucket_count = this->bucket_count();
371  auto __it = _Base::insert(__hint.base(), __obj);
372  _M_check_rehashed(__bucket_count);
373  return { __it, this };
374  }
375 
376  // _GLIBCXX_RESOLVE_LIB_DEFECTS
377  // 2354. Unnecessary copying when inserting into maps with braced-init
378  iterator
379  insert(const_iterator __hint, value_type&& __x)
380  {
381  __glibcxx_check_insert(__hint);
382  size_type __bucket_count = this->bucket_count();
383  auto __it = _Base::insert(__hint.base(), std::move(__x));
384  _M_check_rehashed(__bucket_count);
385  return { __it, this };
386  }
387 
388  template<typename _Pair, typename = typename
390  _Pair&&>::value>::type>
391  iterator
392  insert(const_iterator __hint, _Pair&& __obj)
393  {
394  __glibcxx_check_insert(__hint);
395  size_type __bucket_count = this->bucket_count();
396  auto __it = _Base::insert(__hint.base(), std::forward<_Pair>(__obj));
397  _M_check_rehashed(__bucket_count);
398  return { __it, this };
399  }
400 
401  void
403  {
404  size_type __bucket_count = this->bucket_count();
405  _Base::insert(__l);
406  _M_check_rehashed(__bucket_count);
407  }
408 
409  template<typename _InputIterator>
410  void
411  insert(_InputIterator __first, _InputIterator __last)
412  {
414  __glibcxx_check_valid_range2(__first, __last, __dist);
415  size_type __bucket_count = this->bucket_count();
416 
417  if (__dist.second >= __gnu_debug::__dp_sign)
418  _Base::insert(__gnu_debug::__unsafe(__first),
419  __gnu_debug::__unsafe(__last));
420  else
421  _Base::insert(__first, __last);
422 
423  _M_check_rehashed(__bucket_count);
424  }
425 
426 #if __cplusplus > 201402L
427  template <typename... _Args>
429  try_emplace(const key_type& __k, _Args&&... __args)
430  {
431  auto __res = _Base::try_emplace(__k,
432  std::forward<_Args>(__args)...);
433  return { { __res.first, this }, __res.second };
434  }
435 
436  template <typename... _Args>
438  try_emplace(key_type&& __k, _Args&&... __args)
439  {
440  auto __res = _Base::try_emplace(std::move(__k),
441  std::forward<_Args>(__args)...);
442  return { { __res.first, this }, __res.second };
443  }
444 
445  template <typename... _Args>
446  iterator
447  try_emplace(const_iterator __hint, const key_type& __k,
448  _Args&&... __args)
449  {
450  __glibcxx_check_insert(__hint);
451  return { _Base::try_emplace(__hint.base(), __k,
452  std::forward<_Args>(__args)...),
453  this };
454  }
455 
456  template <typename... _Args>
457  iterator
458  try_emplace(const_iterator __hint, key_type&& __k, _Args&&... __args)
459  {
460  __glibcxx_check_insert(__hint);
461  return { _Base::try_emplace(__hint.base(), std::move(__k),
462  std::forward<_Args>(__args)...),
463  this };
464  }
465 
466  template <typename _Obj>
468  insert_or_assign(const key_type& __k, _Obj&& __obj)
469  {
470  auto __res = _Base::insert_or_assign(__k,
471  std::forward<_Obj>(__obj));
472  return { { __res.first, this }, __res.second };
473  }
474 
475  template <typename _Obj>
477  insert_or_assign(key_type&& __k, _Obj&& __obj)
478  {
479  auto __res = _Base::insert_or_assign(std::move(__k),
480  std::forward<_Obj>(__obj));
481  return { { __res.first, this }, __res.second };
482  }
483 
484  template <typename _Obj>
485  iterator
486  insert_or_assign(const_iterator __hint, const key_type& __k,
487  _Obj&& __obj)
488  {
489  __glibcxx_check_insert(__hint);
490  return { _Base::insert_or_assign(__hint.base(), __k,
491  std::forward<_Obj>(__obj)),
492  this };
493  }
494 
495  template <typename _Obj>
496  iterator
497  insert_or_assign(const_iterator __hint, key_type&& __k, _Obj&& __obj)
498  {
499  __glibcxx_check_insert(__hint);
500  return { _Base::insert_or_assign(__hint.base(), std::move(__k),
501  std::forward<_Obj>(__obj)),
502  this };
503  }
504 #endif // C++17
505 
506 #if __cplusplus > 201402L
507  using node_type = typename _Base::node_type;
509 
510  node_type
511  extract(const_iterator __position)
512  {
513  __glibcxx_check_erase(__position);
514  return _M_extract(__position.base());
515  }
516 
517  node_type
518  extract(const key_type& __key)
519  {
520  const auto __position = _Base::find(__key);
521  if (__position != _Base::end())
522  return _M_extract(__position);
523  return {};
524  }
525 
527  insert(node_type&& __nh)
528  {
529  auto __ret = _Base::insert(std::move(__nh));
530  return
531  { { __ret.position, this }, __ret.inserted, std::move(__ret.node) };
532  }
533 
534  iterator
535  insert(const_iterator __hint, node_type&& __nh)
536  {
537  __glibcxx_check_insert(__hint);
538  return { _Base::insert(__hint.base(), std::move(__nh)), this };
539  }
540 
541  using _Base::merge;
542 #endif // C++17
543 
544  iterator
545  find(const key_type& __key)
546  { return { _Base::find(__key), this }; }
547 
549  find(const key_type& __key) const
550  { return { _Base::find(__key), this }; }
551 
553  equal_range(const key_type& __key)
554  {
555  auto __res = _Base::equal_range(__key);
556  return { { __res.first, this }, { __res.second, this } };
557  }
558 
560  equal_range(const key_type& __key) const
561  {
562  auto __res = _Base::equal_range(__key);
563  return { { __res.first, this }, { __res.second, this } };
564  }
565 
566  size_type
567  erase(const key_type& __key)
568  {
569  size_type __ret(0);
570  auto __victim = _Base::find(__key);
571  if (__victim != _Base::end())
572  {
573  _M_erase(__victim);
574  __ret = 1;
575  }
576  return __ret;
577  }
578 
579  iterator
580  erase(const_iterator __it)
581  {
582  __glibcxx_check_erase(__it);
583  return { _M_erase(__it.base()), this };
584  }
585 
586  iterator
587  erase(iterator __it)
588  {
589  __glibcxx_check_erase(__it);
590  return { _M_erase(__it.base()), this };
591  }
592 
593  iterator
594  erase(const_iterator __first, const_iterator __last)
595  {
596  __glibcxx_check_erase_range(__first, __last);
597  for (auto __tmp = __first.base(); __tmp != __last.base(); ++__tmp)
598  {
599  _GLIBCXX_DEBUG_VERIFY(__tmp != _Base::cend(),
600  _M_message(__gnu_debug::__msg_valid_range)
601  ._M_iterator(__first, "first")
602  ._M_iterator(__last, "last"));
603  _M_invalidate(__tmp);
604  }
605 
606  size_type __bucket_count = this->bucket_count();
607  auto __next = _Base::erase(__first.base(), __last.base());
608  _M_check_rehashed(__bucket_count);
609  return { __next, this };
610  }
611 
612  _Base&
613  _M_base() noexcept { return *this; }
614 
615  const _Base&
616  _M_base() const noexcept { return *this; }
617 
618  private:
619  void
620  _M_check_rehashed(size_type __prev_count)
621  {
622  if (__prev_count != this->bucket_count())
623  this->_M_invalidate_all();
624  }
625 
626  void
627  _M_invalidate(_Base_const_iterator __victim)
628  {
629  this->_M_invalidate_if(
630  [__victim](_Base_const_iterator __it) { return __it == __victim; });
632  [__victim](_Base_const_local_iterator __it)
633  { return __it == __victim; });
634  }
635 
636  _Base_iterator
637  _M_erase(_Base_const_iterator __victim)
638  {
639  _M_invalidate(__victim);
640  size_type __bucket_count = this->bucket_count();
641  _Base_iterator __next = _Base::erase(__victim);
642  _M_check_rehashed(__bucket_count);
643  return __next;
644  }
645 
646 #if __cplusplus > 201402L
647  node_type
648  _M_extract(_Base_const_iterator __victim)
649  {
650  _M_invalidate(__victim);
651  return _Base::extract(__victim);
652  }
653 #endif
654  };
655 
656 #if __cpp_deduction_guides >= 201606
657 
658  template<typename _InputIterator,
659  typename _Hash = hash<__iter_key_t<_InputIterator>>,
660  typename _Pred = equal_to<__iter_key_t<_InputIterator>>,
661  typename _Allocator = allocator<__iter_to_alloc_t<_InputIterator>>,
662  typename = _RequireInputIter<_InputIterator>,
663  typename = _RequireNotAllocatorOrIntegral<_Hash>,
664  typename = _RequireNotAllocator<_Pred>,
665  typename = _RequireAllocator<_Allocator>>
666  unordered_map(_InputIterator, _InputIterator,
667  typename unordered_map<int, int>::size_type = {},
668  _Hash = _Hash(), _Pred = _Pred(), _Allocator = _Allocator())
669  -> unordered_map<__iter_key_t<_InputIterator>,
670  __iter_val_t<_InputIterator>,
671  _Hash, _Pred, _Allocator>;
672 
673  template<typename _Key, typename _Tp, typename _Hash = hash<_Key>,
674  typename _Pred = equal_to<_Key>,
675  typename _Allocator = allocator<pair<const _Key, _Tp>>,
676  typename = _RequireNotAllocatorOrIntegral<_Hash>,
677  typename = _RequireNotAllocator<_Pred>,
678  typename = _RequireAllocator<_Allocator>>
680  typename unordered_map<int, int>::size_type = {},
681  _Hash = _Hash(), _Pred = _Pred(), _Allocator = _Allocator())
682  -> unordered_map<_Key, _Tp, _Hash, _Pred, _Allocator>;
683 
684  template<typename _InputIterator, typename _Allocator,
685  typename = _RequireInputIter<_InputIterator>,
686  typename = _RequireAllocator<_Allocator>>
687  unordered_map(_InputIterator, _InputIterator,
688  typename unordered_map<int, int>::size_type, _Allocator)
689  -> unordered_map<__iter_key_t<_InputIterator>,
690  __iter_val_t<_InputIterator>,
691  hash<__iter_key_t<_InputIterator>>,
692  equal_to<__iter_key_t<_InputIterator>>,
693  _Allocator>;
694 
695  template<typename _InputIterator, typename _Allocator,
696  typename = _RequireInputIter<_InputIterator>,
697  typename = _RequireAllocator<_Allocator>>
698  unordered_map(_InputIterator, _InputIterator, _Allocator)
699  -> unordered_map<__iter_key_t<_InputIterator>,
700  __iter_val_t<_InputIterator>,
701  hash<__iter_key_t<_InputIterator>>,
702  equal_to<__iter_key_t<_InputIterator>>,
703  _Allocator>;
704 
705  template<typename _InputIterator, typename _Hash, typename _Allocator,
706  typename = _RequireInputIter<_InputIterator>,
707  typename = _RequireNotAllocatorOrIntegral<_Hash>,
708  typename = _RequireAllocator<_Allocator>>
709  unordered_map(_InputIterator, _InputIterator,
710  typename unordered_map<int, int>::size_type,
711  _Hash, _Allocator)
712  -> unordered_map<__iter_key_t<_InputIterator>,
713  __iter_val_t<_InputIterator>, _Hash,
714  equal_to<__iter_key_t<_InputIterator>>, _Allocator>;
715 
716  template<typename _Key, typename _Tp, typename _Allocator,
717  typename = _RequireAllocator<_Allocator>>
718  unordered_map(initializer_list<pair<_Key, _Tp>>,
719  typename unordered_map<int, int>::size_type,
720  _Allocator)
721  -> unordered_map<_Key, _Tp, hash<_Key>, equal_to<_Key>, _Allocator>;
722 
723  template<typename _Key, typename _Tp, typename _Allocator,
724  typename = _RequireAllocator<_Allocator>>
725  unordered_map(initializer_list<pair<_Key, _Tp>>, _Allocator)
726  -> unordered_map<_Key, _Tp, hash<_Key>, equal_to<_Key>, _Allocator>;
727 
728  template<typename _Key, typename _Tp, typename _Hash, typename _Allocator,
729  typename = _RequireNotAllocatorOrIntegral<_Hash>,
730  typename = _RequireAllocator<_Allocator>>
731  unordered_map(initializer_list<pair<_Key, _Tp>>,
732  typename unordered_map<int, int>::size_type,
733  _Hash, _Allocator)
734  -> unordered_map<_Key, _Tp, _Hash, equal_to<_Key>, _Allocator>;
735 
736 #endif
737 
738  template<typename _Key, typename _Tp, typename _Hash,
739  typename _Pred, typename _Alloc>
740  inline void
741  swap(unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
742  unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
743  noexcept(noexcept(__x.swap(__y)))
744  { __x.swap(__y); }
745 
746  template<typename _Key, typename _Tp, typename _Hash,
747  typename _Pred, typename _Alloc>
748  inline bool
749  operator==(const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
750  const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
751  { return __x._M_base() == __y._M_base(); }
752 
753 #if __cpp_impl_three_way_comparison < 201907L
754  template<typename _Key, typename _Tp, typename _Hash,
755  typename _Pred, typename _Alloc>
756  inline bool
757  operator!=(const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
758  const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
759  { return !(__x == __y); }
760 #endif
761 
762  /// Class std::unordered_multimap with safety/checking/debug instrumentation.
763  template<typename _Key, typename _Tp,
764  typename _Hash = std::hash<_Key>,
765  typename _Pred = std::equal_to<_Key>,
766  typename _Alloc = std::allocator<std::pair<const _Key, _Tp> > >
769  unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>, _Alloc,
770  __gnu_debug::_Safe_unordered_container>,
771  public _GLIBCXX_STD_C::unordered_multimap<
772  _Key, _Tp, _Hash, _Pred, _Alloc>
773  {
774  typedef _GLIBCXX_STD_C::unordered_multimap<_Key, _Tp, _Hash,
775  _Pred, _Alloc> _Base;
778  typedef typename _Base::const_iterator _Base_const_iterator;
779  typedef typename _Base::iterator _Base_iterator;
780  typedef typename _Base::const_local_iterator _Base_const_local_iterator;
781  typedef typename _Base::local_iterator _Base_local_iterator;
782 
783  template<typename _ItT, typename _SeqT, typename _CatT>
784  friend class ::__gnu_debug::_Safe_iterator;
785  template<typename _ItT, typename _SeqT>
786  friend class ::__gnu_debug::_Safe_local_iterator;
787 
788  // Reference wrapper for base class. See PR libstdc++/90102.
789  struct _Base_ref
790  {
791  _Base_ref(const _Base& __r) : _M_ref(__r) { }
792 
793  const _Base& _M_ref;
794  };
795 
796  public:
797  typedef typename _Base::size_type size_type;
798  typedef typename _Base::hasher hasher;
799  typedef typename _Base::key_equal key_equal;
800  typedef typename _Base::allocator_type allocator_type;
801 
802  typedef typename _Base::key_type key_type;
803  typedef typename _Base::value_type value_type;
804 
806  _Base_iterator, unordered_multimap> iterator;
808  _Base_const_iterator, unordered_multimap> const_iterator;
810  _Base_local_iterator, unordered_multimap> local_iterator;
812  _Base_const_local_iterator, unordered_multimap> const_local_iterator;
813 
814  unordered_multimap() = default;
815 
816  explicit
817  unordered_multimap(size_type __n,
818  const hasher& __hf = hasher(),
819  const key_equal& __eql = key_equal(),
820  const allocator_type& __a = allocator_type())
821  : _Base(__n, __hf, __eql, __a) { }
822 
823  template<typename _InputIterator>
824  unordered_multimap(_InputIterator __first, _InputIterator __last,
825  size_type __n = 0,
826  const hasher& __hf = hasher(),
827  const key_equal& __eql = key_equal(),
828  const allocator_type& __a = allocator_type())
830  __glibcxx_check_valid_constructor_range(__first, __last)),
831  __gnu_debug::__base(__last), __n,
832  __hf, __eql, __a) { }
833 
834  unordered_multimap(const unordered_multimap&) = default;
835 
836  unordered_multimap(_Base_ref __x)
837  : _Base(__x._M_ref) { }
838 
840 
841  explicit
842  unordered_multimap(const allocator_type& __a)
843  : _Base(__a) { }
844 
846  const allocator_type& __a)
847  : _Base(__umap, __a) { }
848 
850  const allocator_type& __a)
851  noexcept( noexcept(_Base(std::move(__umap._M_base()), __a)) )
852  : _Safe(std::move(__umap._M_safe()), __a),
853  _Base(std::move(__umap._M_base()), __a) { }
854 
856  size_type __n = 0,
857  const hasher& __hf = hasher(),
858  const key_equal& __eql = key_equal(),
859  const allocator_type& __a = allocator_type())
860  : _Base(__l, __n, __hf, __eql, __a) { }
861 
862  unordered_multimap(size_type __n, const allocator_type& __a)
863  : unordered_multimap(__n, hasher(), key_equal(), __a)
864  { }
865 
866  unordered_multimap(size_type __n, const hasher& __hf,
867  const allocator_type& __a)
868  : unordered_multimap(__n, __hf, key_equal(), __a)
869  { }
870 
871  template<typename _InputIterator>
872  unordered_multimap(_InputIterator __first, _InputIterator __last,
873  size_type __n,
874  const allocator_type& __a)
875  : unordered_multimap(__first, __last, __n, hasher(), key_equal(), __a)
876  { }
877 
878  template<typename _InputIterator>
879  unordered_multimap(_InputIterator __first, _InputIterator __last,
880  size_type __n, const hasher& __hf,
881  const allocator_type& __a)
882  : unordered_multimap(__first, __last, __n, __hf, key_equal(), __a)
883  { }
884 
886  size_type __n,
887  const allocator_type& __a)
888  : unordered_multimap(__l, __n, hasher(), key_equal(), __a)
889  { }
890 
892  size_type __n, const hasher& __hf,
893  const allocator_type& __a)
894  : unordered_multimap(__l, __n, __hf, key_equal(), __a)
895  { }
896 
897  ~unordered_multimap() = default;
898 
900  operator=(const unordered_multimap&) = default;
901 
903  operator=(unordered_multimap&&) = default;
904 
906  operator=(initializer_list<value_type> __l)
907  {
908  this->_M_base() = __l;
909  this->_M_invalidate_all();
910  return *this;
911  }
912 
913  void
914  swap(unordered_multimap& __x)
915  noexcept( noexcept(declval<_Base&>().swap(__x)) )
916  {
917  _Safe::_M_swap(__x);
918  _Base::swap(__x);
919  }
920 
921  void
922  clear() noexcept
923  {
924  _Base::clear();
925  this->_M_invalidate_all();
926  }
927 
928  iterator
929  begin() noexcept
930  { return { _Base::begin(), this }; }
931 
933  begin() const noexcept
934  { return { _Base::begin(), this }; }
935 
936  iterator
937  end() noexcept
938  { return { _Base::end(), this }; }
939 
941  end() const noexcept
942  { return { _Base::end(), this }; }
943 
945  cbegin() const noexcept
946  { return { _Base::cbegin(), this }; }
947 
949  cend() const noexcept
950  { return { _Base::cend(), this }; }
951 
952  // local versions
954  begin(size_type __b)
955  {
956  __glibcxx_check_bucket_index(__b);
957  return { _Base::begin(__b), this };
958  }
959 
961  end(size_type __b)
962  {
963  __glibcxx_check_bucket_index(__b);
964  return { _Base::end(__b), this };
965  }
966 
968  begin(size_type __b) const
969  {
970  __glibcxx_check_bucket_index(__b);
971  return { _Base::begin(__b), this };
972  }
973 
975  end(size_type __b) const
976  {
977  __glibcxx_check_bucket_index(__b);
978  return { _Base::end(__b), this };
979  }
980 
982  cbegin(size_type __b) const
983  {
984  __glibcxx_check_bucket_index(__b);
985  return { _Base::cbegin(__b), this };
986  }
987 
989  cend(size_type __b) const
990  {
991  __glibcxx_check_bucket_index(__b);
992  return { _Base::cend(__b), this };
993  }
994 
995  size_type
996  bucket_size(size_type __b) const
997  {
998  __glibcxx_check_bucket_index(__b);
999  return _Base::bucket_size(__b);
1000  }
1001 
1002  float
1003  max_load_factor() const noexcept
1004  { return _Base::max_load_factor(); }
1005 
1006  void
1007  max_load_factor(float __f)
1008  {
1009  __glibcxx_check_max_load_factor(__f);
1010  _Base::max_load_factor(__f);
1011  }
1012 
1013  template<typename... _Args>
1014  iterator
1015  emplace(_Args&&... __args)
1016  {
1017  size_type __bucket_count = this->bucket_count();
1018  auto __it = _Base::emplace(std::forward<_Args>(__args)...);
1019  _M_check_rehashed(__bucket_count);
1020  return { __it, this };
1021  }
1022 
1023  template<typename... _Args>
1024  iterator
1025  emplace_hint(const_iterator __hint, _Args&&... __args)
1026  {
1027  __glibcxx_check_insert(__hint);
1028  size_type __bucket_count = this->bucket_count();
1029  auto __it = _Base::emplace_hint(__hint.base(),
1030  std::forward<_Args>(__args)...);
1031  _M_check_rehashed(__bucket_count);
1032  return { __it, this };
1033  }
1034 
1035  iterator
1036  insert(const value_type& __obj)
1037  {
1038  size_type __bucket_count = this->bucket_count();
1039  auto __it = _Base::insert(__obj);
1040  _M_check_rehashed(__bucket_count);
1041  return { __it, this };
1042  }
1043 
1044  // _GLIBCXX_RESOLVE_LIB_DEFECTS
1045  // 2354. Unnecessary copying when inserting into maps with braced-init
1046  iterator
1047  insert(value_type&& __x)
1048  {
1049  size_type __bucket_count = this->bucket_count();
1050  auto __it = _Base::insert(std::move(__x));
1051  _M_check_rehashed(__bucket_count);
1052  return { __it, this };
1053  }
1054 
1055  iterator
1056  insert(const_iterator __hint, const value_type& __obj)
1057  {
1058  __glibcxx_check_insert(__hint);
1059  size_type __bucket_count = this->bucket_count();
1060  auto __it = _Base::insert(__hint.base(), __obj);
1061  _M_check_rehashed(__bucket_count);
1062  return { __it, this };
1063  }
1064 
1065  // _GLIBCXX_RESOLVE_LIB_DEFECTS
1066  // 2354. Unnecessary copying when inserting into maps with braced-init
1067  iterator
1068  insert(const_iterator __hint, value_type&& __x)
1069  {
1070  __glibcxx_check_insert(__hint);
1071  size_type __bucket_count = this->bucket_count();
1072  auto __it = _Base::insert(__hint.base(), std::move(__x));
1073  _M_check_rehashed(__bucket_count);
1074  return { __it, this };
1075  }
1076 
1077  template<typename _Pair, typename = typename
1079  _Pair&&>::value>::type>
1080  iterator
1081  insert(_Pair&& __obj)
1082  {
1083  size_type __bucket_count = this->bucket_count();
1084  auto __it = _Base::insert(std::forward<_Pair>(__obj));
1085  _M_check_rehashed(__bucket_count);
1086  return { __it, this };
1087  }
1088 
1089  template<typename _Pair, typename = typename
1091  _Pair&&>::value>::type>
1092  iterator
1093  insert(const_iterator __hint, _Pair&& __obj)
1094  {
1095  __glibcxx_check_insert(__hint);
1096  size_type __bucket_count = this->bucket_count();
1097  auto __it = _Base::insert(__hint.base(), std::forward<_Pair>(__obj));
1098  _M_check_rehashed(__bucket_count);
1099  return { __it, this };
1100  }
1101 
1102  void
1104  { _Base::insert(__l); }
1105 
1106  template<typename _InputIterator>
1107  void
1108  insert(_InputIterator __first, _InputIterator __last)
1109  {
1111  __glibcxx_check_valid_range2(__first, __last, __dist);
1112  size_type __bucket_count = this->bucket_count();
1113 
1114  if (__dist.second >= __gnu_debug::__dp_sign)
1115  _Base::insert(__gnu_debug::__unsafe(__first),
1116  __gnu_debug::__unsafe(__last));
1117  else
1118  _Base::insert(__first, __last);
1119 
1120  _M_check_rehashed(__bucket_count);
1121  }
1122 
1123 #if __cplusplus > 201402L
1124  using node_type = typename _Base::node_type;
1125 
1126  node_type
1127  extract(const_iterator __position)
1128  {
1129  __glibcxx_check_erase(__position);
1130  return _M_extract(__position.base());
1131  }
1132 
1133  node_type
1134  extract(const key_type& __key)
1135  {
1136  const auto __position = _Base::find(__key);
1137  if (__position != _Base::end())
1138  return _M_extract(__position);
1139  return {};
1140  }
1141 
1142  iterator
1143  insert(node_type&& __nh)
1144  { return { _Base::insert(std::move(__nh)), this }; }
1145 
1146  iterator
1147  insert(const_iterator __hint, node_type&& __nh)
1148  {
1149  __glibcxx_check_insert(__hint);
1150  return { _Base::insert(__hint.base(), std::move(__nh)), this };
1151  }
1152 
1153  using _Base::merge;
1154 #endif // C++17
1155 
1156  iterator
1157  find(const key_type& __key)
1158  { return { _Base::find(__key), this }; }
1159 
1161  find(const key_type& __key) const
1162  { return { _Base::find(__key), this }; }
1163 
1165  equal_range(const key_type& __key)
1166  {
1167  auto __res = _Base::equal_range(__key);
1168  return { { __res.first, this }, { __res.second, this } };
1169  }
1170 
1172  equal_range(const key_type& __key) const
1173  {
1174  auto __res = _Base::equal_range(__key);
1175  return { { __res.first, this }, { __res.second, this } };
1176  }
1177 
1178  size_type
1179  erase(const key_type& __key)
1180  {
1181  size_type __ret(0);
1182  size_type __bucket_count = this->bucket_count();
1183  auto __pair = _Base::equal_range(__key);
1184  for (auto __victim = __pair.first; __victim != __pair.second;)
1185  {
1186  _M_invalidate(__victim);
1187  __victim = _Base::erase(__victim);
1188  ++__ret;
1189  }
1190 
1191  _M_check_rehashed(__bucket_count);
1192  return __ret;
1193  }
1194 
1195  iterator
1196  erase(const_iterator __it)
1197  {
1198  __glibcxx_check_erase(__it);
1199  return { _M_erase(__it.base()), this };
1200  }
1201 
1202  iterator
1203  erase(iterator __it)
1204  {
1205  __glibcxx_check_erase(__it);
1206  return { _M_erase(__it.base()), this };
1207  }
1208 
1209  iterator
1210  erase(const_iterator __first, const_iterator __last)
1211  {
1212  __glibcxx_check_erase_range(__first, __last);
1213  for (auto __tmp = __first.base(); __tmp != __last.base(); ++__tmp)
1214  {
1215  _GLIBCXX_DEBUG_VERIFY(__tmp != _Base::cend(),
1216  _M_message(__gnu_debug::__msg_valid_range)
1217  ._M_iterator(__first, "first")
1218  ._M_iterator(__last, "last"));
1219  _M_invalidate(__tmp);
1220  }
1221 
1222  size_type __bucket_count = this->bucket_count();
1223  auto __next = _Base::erase(__first.base(), __last.base());
1224  _M_check_rehashed(__bucket_count);
1225  return { __next, this };
1226  }
1227 
1228  _Base&
1229  _M_base() noexcept { return *this; }
1230 
1231  const _Base&
1232  _M_base() const noexcept { return *this; }
1233 
1234  private:
1235  void
1236  _M_check_rehashed(size_type __prev_count)
1237  {
1238  if (__prev_count != this->bucket_count())
1239  this->_M_invalidate_all();
1240  }
1241 
1242  void
1243  _M_invalidate(_Base_const_iterator __victim)
1244  {
1245  this->_M_invalidate_if(
1246  [__victim](_Base_const_iterator __it) { return __it == __victim; });
1247  this->_M_invalidate_local_if(
1248  [__victim](_Base_const_local_iterator __it)
1249  { return __it == __victim; });
1250  }
1251 
1252  _Base_iterator
1253  _M_erase(_Base_const_iterator __victim)
1254  {
1255  _M_invalidate(__victim);
1256  size_type __bucket_count = this->bucket_count();
1257  _Base_iterator __next = _Base::erase(__victim);
1258  _M_check_rehashed(__bucket_count);
1259  return __next;
1260  }
1261 
1262 #if __cplusplus > 201402L
1263  node_type
1264  _M_extract(_Base_const_iterator __victim)
1265  {
1266  _M_invalidate(__victim);
1267  return _Base::extract(__victim);
1268  }
1269 #endif
1270  };
1271 
1272 #if __cpp_deduction_guides >= 201606
1273 
1274  template<typename _InputIterator,
1275  typename _Hash = hash<__iter_key_t<_InputIterator>>,
1276  typename _Pred = equal_to<__iter_key_t<_InputIterator>>,
1277  typename _Allocator = allocator<__iter_to_alloc_t<_InputIterator>>,
1278  typename = _RequireInputIter<_InputIterator>,
1279  typename = _RequireNotAllocatorOrIntegral<_Hash>,
1280  typename = _RequireNotAllocator<_Pred>,
1281  typename = _RequireAllocator<_Allocator>>
1282  unordered_multimap(_InputIterator, _InputIterator,
1283  unordered_multimap<int, int>::size_type = {},
1284  _Hash = _Hash(), _Pred = _Pred(),
1285  _Allocator = _Allocator())
1286  -> unordered_multimap<__iter_key_t<_InputIterator>,
1287  __iter_val_t<_InputIterator>, _Hash, _Pred,
1288  _Allocator>;
1289 
1290  template<typename _Key, typename _Tp, typename _Hash = hash<_Key>,
1291  typename _Pred = equal_to<_Key>,
1292  typename _Allocator = allocator<pair<const _Key, _Tp>>,
1293  typename = _RequireNotAllocatorOrIntegral<_Hash>,
1294  typename = _RequireNotAllocator<_Pred>,
1295  typename = _RequireAllocator<_Allocator>>
1297  unordered_multimap<int, int>::size_type = {},
1298  _Hash = _Hash(), _Pred = _Pred(),
1299  _Allocator = _Allocator())
1300  -> unordered_multimap<_Key, _Tp, _Hash, _Pred, _Allocator>;
1301 
1302  template<typename _InputIterator, typename _Allocator,
1303  typename = _RequireInputIter<_InputIterator>,
1304  typename = _RequireAllocator<_Allocator>>
1305  unordered_multimap(_InputIterator, _InputIterator,
1306  unordered_multimap<int, int>::size_type, _Allocator)
1307  -> unordered_multimap<__iter_key_t<_InputIterator>,
1308  __iter_val_t<_InputIterator>,
1309  hash<__iter_key_t<_InputIterator>>,
1310  equal_to<__iter_key_t<_InputIterator>>, _Allocator>;
1311 
1312  template<typename _InputIterator, typename _Allocator,
1313  typename = _RequireInputIter<_InputIterator>,
1314  typename = _RequireAllocator<_Allocator>>
1315  unordered_multimap(_InputIterator, _InputIterator, _Allocator)
1316  -> unordered_multimap<__iter_key_t<_InputIterator>,
1317  __iter_val_t<_InputIterator>,
1318  hash<__iter_key_t<_InputIterator>>,
1319  equal_to<__iter_key_t<_InputIterator>>, _Allocator>;
1320 
1321  template<typename _InputIterator, typename _Hash, typename _Allocator,
1322  typename = _RequireInputIter<_InputIterator>,
1323  typename = _RequireNotAllocatorOrIntegral<_Hash>,
1324  typename = _RequireAllocator<_Allocator>>
1325  unordered_multimap(_InputIterator, _InputIterator,
1326  unordered_multimap<int, int>::size_type, _Hash,
1327  _Allocator)
1328  -> unordered_multimap<__iter_key_t<_InputIterator>,
1329  __iter_val_t<_InputIterator>, _Hash,
1330  equal_to<__iter_key_t<_InputIterator>>, _Allocator>;
1331 
1332  template<typename _Key, typename _Tp, typename _Allocator,
1333  typename = _RequireAllocator<_Allocator>>
1334  unordered_multimap(initializer_list<pair<_Key, _Tp>>,
1335  unordered_multimap<int, int>::size_type,
1336  _Allocator)
1337  -> unordered_multimap<_Key, _Tp, hash<_Key>, equal_to<_Key>, _Allocator>;
1338 
1339  template<typename _Key, typename _Tp, typename _Allocator,
1340  typename = _RequireAllocator<_Allocator>>
1341  unordered_multimap(initializer_list<pair<_Key, _Tp>>, _Allocator)
1342  -> unordered_multimap<_Key, _Tp, hash<_Key>, equal_to<_Key>, _Allocator>;
1343 
1344  template<typename _Key, typename _Tp, typename _Hash, typename _Allocator,
1345  typename = _RequireNotAllocatorOrIntegral<_Hash>,
1346  typename = _RequireAllocator<_Allocator>>
1347  unordered_multimap(initializer_list<pair<_Key, _Tp>>,
1348  unordered_multimap<int, int>::size_type,
1349  _Hash, _Allocator)
1350  -> unordered_multimap<_Key, _Tp, _Hash, equal_to<_Key>, _Allocator>;
1351 
1352 #endif
1353 
1354  template<typename _Key, typename _Tp, typename _Hash,
1355  typename _Pred, typename _Alloc>
1356  inline void
1357  swap(unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
1358  unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
1359  noexcept(noexcept(__x.swap(__y)))
1360  { __x.swap(__y); }
1361 
1362  template<typename _Key, typename _Tp, typename _Hash,
1363  typename _Pred, typename _Alloc>
1364  inline bool
1365  operator==(const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
1366  const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
1367  { return __x._M_base() == __y._M_base(); }
1368 
1369 #if __cpp_impl_three_way_comparison < 201907L
1370  template<typename _Key, typename _Tp, typename _Hash,
1371  typename _Pred, typename _Alloc>
1372  inline bool
1373  operator!=(const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
1374  const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
1375  { return !(__x == __y); }
1376 #endif
1377 
1378 } // namespace __debug
1379 } // namespace std
1380 
1381 #endif // C++11
1382 
1383 #endif
#define __glibcxx_check_insert(_Position)
Definition: macros.h:140
#define __glibcxx_check_erase_range(_First, _Last)
Definition: macros.h:234
#define __glibcxx_check_erase(_Position)
Definition: macros.h:206
_T2 second
The second member.
Definition: stl_pair.h:218
constexpr std::remove_reference< _Tp >::type && move(_Tp &&__t) noexcept
Convert a value to an rvalue.
Definition: move.h:101
ISO C++ entities toplevel namespace is std.
constexpr _Iterator __base(_Iterator __it)
initializer_list
Primary class template hash.
is_constructible
Definition: type_traits:913
Define a member typedef type only if a boolean constant is true.
Definition: type_traits:2143
The standard allocator, as per [20.4].
Definition: allocator.h:117
Return type of insert(node_handle&&) on unique maps/sets.
Definition: node_handle.h:364
One of the comparison functors.
Definition: stl_function.h:352
Struct holding two objects of arbitrary type.
Definition: stl_pair.h:213
A standard container composed of equivalent keys (possibly containing multiple of each key value) tha...
A standard container composed of unique keys (containing at most one of each key value) that associat...
Safe iterator wrapper.
_Iterator & base() noexcept
Return the underlying iterator.
Base class that supports tracking of iterators that reference a sequence.
Definition: safe_base.h:189
Safe class dealing with some allocator dependent operations.
Base class for constructing a safe unordered container type that tracks iterators that reference it.
Class std::unordered_map with safety/checking/debug instrumentation.
Class std::unordered_multimap with safety/checking/debug instrumentation.