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 
548 #if __cplusplus > 201703L
549  template<typename _Kt,
550  typename = std::__has_is_transparent_t<_Hash, _Kt>,
551  typename = std::__has_is_transparent_t<_Pred, _Kt>>
552  iterator
553  find(const _Kt& __k)
554  { return { _Base::find(__k), this }; }
555 #endif
556 
558  find(const key_type& __key) const
559  { return { _Base::find(__key), this }; }
560 
561 #if __cplusplus > 201703L
562  template<typename _Kt,
563  typename = std::__has_is_transparent_t<_Hash, _Kt>,
564  typename = std::__has_is_transparent_t<_Pred, _Kt>>
566  find(const _Kt& __k) const
567  { return { _Base::find(__k), this }; }
568 #endif
569 
571  equal_range(const key_type& __key)
572  {
573  auto __res = _Base::equal_range(__key);
574  return { { __res.first, this }, { __res.second, this } };
575  }
576 
577 #if __cplusplus > 201703L
578  template<typename _Kt,
579  typename = std::__has_is_transparent_t<_Hash, _Kt>,
580  typename = std::__has_is_transparent_t<_Pred, _Kt>>
582  equal_range(const _Kt& __k)
583  {
584  auto __res = _Base::equal_range(__k);
585  return { { __res.first, this }, { __res.second, this } };
586  }
587 #endif
588 
590  equal_range(const key_type& __key) const
591  {
592  auto __res = _Base::equal_range(__key);
593  return { { __res.first, this }, { __res.second, this } };
594  }
595 
596 #if __cplusplus > 201703L
597  template<typename _Kt,
598  typename = std::__has_is_transparent_t<_Hash, _Kt>,
599  typename = std::__has_is_transparent_t<_Pred, _Kt>>
601  equal_range(const _Kt& __k) const
602  {
603  auto __res = _Base::equal_range(__k);
604  return { { __res.first, this }, { __res.second, this } };
605  }
606 #endif
607 
608  size_type
609  erase(const key_type& __key)
610  {
611  size_type __ret(0);
612  auto __victim = _Base::find(__key);
613  if (__victim != _Base::end())
614  {
615  _M_erase(__victim);
616  __ret = 1;
617  }
618  return __ret;
619  }
620 
621  iterator
622  erase(const_iterator __it)
623  {
624  __glibcxx_check_erase(__it);
625  return { _M_erase(__it.base()), this };
626  }
627 
628  iterator
629  erase(iterator __it)
630  {
631  __glibcxx_check_erase(__it);
632  return { _M_erase(__it.base()), this };
633  }
634 
635  iterator
636  erase(const_iterator __first, const_iterator __last)
637  {
638  __glibcxx_check_erase_range(__first, __last);
639  for (auto __tmp = __first.base(); __tmp != __last.base(); ++__tmp)
640  {
641  _GLIBCXX_DEBUG_VERIFY(__tmp != _Base::cend(),
642  _M_message(__gnu_debug::__msg_valid_range)
643  ._M_iterator(__first, "first")
644  ._M_iterator(__last, "last"));
645  _M_invalidate(__tmp);
646  }
647 
648  size_type __bucket_count = this->bucket_count();
649  auto __next = _Base::erase(__first.base(), __last.base());
650  _M_check_rehashed(__bucket_count);
651  return { __next, this };
652  }
653 
654  _Base&
655  _M_base() noexcept { return *this; }
656 
657  const _Base&
658  _M_base() const noexcept { return *this; }
659 
660  private:
661  void
662  _M_check_rehashed(size_type __prev_count)
663  {
664  if (__prev_count != this->bucket_count())
665  this->_M_invalidate_all();
666  }
667 
668  void
669  _M_invalidate(_Base_const_iterator __victim)
670  {
671  this->_M_invalidate_if(
672  [__victim](_Base_const_iterator __it) { return __it == __victim; });
674  [__victim](_Base_const_local_iterator __it)
675  { return __it == __victim; });
676  }
677 
678  _Base_iterator
679  _M_erase(_Base_const_iterator __victim)
680  {
681  _M_invalidate(__victim);
682  size_type __bucket_count = this->bucket_count();
683  _Base_iterator __next = _Base::erase(__victim);
684  _M_check_rehashed(__bucket_count);
685  return __next;
686  }
687 
688 #if __cplusplus > 201402L
689  node_type
690  _M_extract(_Base_const_iterator __victim)
691  {
692  _M_invalidate(__victim);
693  return _Base::extract(__victim);
694  }
695 #endif
696  };
697 
698 #if __cpp_deduction_guides >= 201606
699 
700  template<typename _InputIterator,
701  typename _Hash = hash<__iter_key_t<_InputIterator>>,
702  typename _Pred = equal_to<__iter_key_t<_InputIterator>>,
703  typename _Allocator = allocator<__iter_to_alloc_t<_InputIterator>>,
704  typename = _RequireInputIter<_InputIterator>,
705  typename = _RequireNotAllocatorOrIntegral<_Hash>,
706  typename = _RequireNotAllocator<_Pred>,
707  typename = _RequireAllocator<_Allocator>>
708  unordered_map(_InputIterator, _InputIterator,
709  typename unordered_map<int, int>::size_type = {},
710  _Hash = _Hash(), _Pred = _Pred(), _Allocator = _Allocator())
711  -> unordered_map<__iter_key_t<_InputIterator>,
712  __iter_val_t<_InputIterator>,
713  _Hash, _Pred, _Allocator>;
714 
715  template<typename _Key, typename _Tp, typename _Hash = hash<_Key>,
716  typename _Pred = equal_to<_Key>,
717  typename _Allocator = allocator<pair<const _Key, _Tp>>,
718  typename = _RequireNotAllocatorOrIntegral<_Hash>,
719  typename = _RequireNotAllocator<_Pred>,
720  typename = _RequireAllocator<_Allocator>>
723  _Hash = _Hash(), _Pred = _Pred(), _Allocator = _Allocator())
724  -> unordered_map<_Key, _Tp, _Hash, _Pred, _Allocator>;
725 
726  template<typename _InputIterator, typename _Allocator,
727  typename = _RequireInputIter<_InputIterator>,
728  typename = _RequireAllocator<_Allocator>>
729  unordered_map(_InputIterator, _InputIterator,
730  typename unordered_map<int, int>::size_type, _Allocator)
731  -> unordered_map<__iter_key_t<_InputIterator>,
732  __iter_val_t<_InputIterator>,
733  hash<__iter_key_t<_InputIterator>>,
734  equal_to<__iter_key_t<_InputIterator>>,
735  _Allocator>;
736 
737  template<typename _InputIterator, typename _Allocator,
738  typename = _RequireInputIter<_InputIterator>,
739  typename = _RequireAllocator<_Allocator>>
740  unordered_map(_InputIterator, _InputIterator, _Allocator)
741  -> unordered_map<__iter_key_t<_InputIterator>,
742  __iter_val_t<_InputIterator>,
743  hash<__iter_key_t<_InputIterator>>,
744  equal_to<__iter_key_t<_InputIterator>>,
745  _Allocator>;
746 
747  template<typename _InputIterator, typename _Hash, typename _Allocator,
748  typename = _RequireInputIter<_InputIterator>,
749  typename = _RequireNotAllocatorOrIntegral<_Hash>,
750  typename = _RequireAllocator<_Allocator>>
751  unordered_map(_InputIterator, _InputIterator,
752  typename unordered_map<int, int>::size_type,
753  _Hash, _Allocator)
754  -> unordered_map<__iter_key_t<_InputIterator>,
755  __iter_val_t<_InputIterator>, _Hash,
756  equal_to<__iter_key_t<_InputIterator>>, _Allocator>;
757 
758  template<typename _Key, typename _Tp, typename _Allocator,
759  typename = _RequireAllocator<_Allocator>>
760  unordered_map(initializer_list<pair<_Key, _Tp>>,
761  typename unordered_map<int, int>::size_type,
762  _Allocator)
763  -> unordered_map<_Key, _Tp, hash<_Key>, equal_to<_Key>, _Allocator>;
764 
765  template<typename _Key, typename _Tp, typename _Allocator,
766  typename = _RequireAllocator<_Allocator>>
767  unordered_map(initializer_list<pair<_Key, _Tp>>, _Allocator)
768  -> unordered_map<_Key, _Tp, hash<_Key>, equal_to<_Key>, _Allocator>;
769 
770  template<typename _Key, typename _Tp, typename _Hash, typename _Allocator,
771  typename = _RequireNotAllocatorOrIntegral<_Hash>,
772  typename = _RequireAllocator<_Allocator>>
773  unordered_map(initializer_list<pair<_Key, _Tp>>,
774  typename unordered_map<int, int>::size_type,
775  _Hash, _Allocator)
776  -> unordered_map<_Key, _Tp, _Hash, equal_to<_Key>, _Allocator>;
777 
778 #endif
779 
780  template<typename _Key, typename _Tp, typename _Hash,
781  typename _Pred, typename _Alloc>
782  inline void
783  swap(unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
784  unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
785  noexcept(noexcept(__x.swap(__y)))
786  { __x.swap(__y); }
787 
788  template<typename _Key, typename _Tp, typename _Hash,
789  typename _Pred, typename _Alloc>
790  inline bool
791  operator==(const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
792  const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
793  { return __x._M_base() == __y._M_base(); }
794 
795 #if __cpp_impl_three_way_comparison < 201907L
796  template<typename _Key, typename _Tp, typename _Hash,
797  typename _Pred, typename _Alloc>
798  inline bool
799  operator!=(const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
800  const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
801  { return !(__x == __y); }
802 #endif
803 
804  /// Class std::unordered_multimap with safety/checking/debug instrumentation.
805  template<typename _Key, typename _Tp,
806  typename _Hash = std::hash<_Key>,
807  typename _Pred = std::equal_to<_Key>,
808  typename _Alloc = std::allocator<std::pair<const _Key, _Tp> > >
811  unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>, _Alloc,
812  __gnu_debug::_Safe_unordered_container>,
813  public _GLIBCXX_STD_C::unordered_multimap<
814  _Key, _Tp, _Hash, _Pred, _Alloc>
815  {
816  typedef _GLIBCXX_STD_C::unordered_multimap<_Key, _Tp, _Hash,
817  _Pred, _Alloc> _Base;
820  typedef typename _Base::const_iterator _Base_const_iterator;
821  typedef typename _Base::iterator _Base_iterator;
822  typedef typename _Base::const_local_iterator _Base_const_local_iterator;
823  typedef typename _Base::local_iterator _Base_local_iterator;
824 
825  template<typename _ItT, typename _SeqT, typename _CatT>
826  friend class ::__gnu_debug::_Safe_iterator;
827  template<typename _ItT, typename _SeqT>
828  friend class ::__gnu_debug::_Safe_local_iterator;
829 
830  // Reference wrapper for base class. See PR libstdc++/90102.
831  struct _Base_ref
832  {
833  _Base_ref(const _Base& __r) : _M_ref(__r) { }
834 
835  const _Base& _M_ref;
836  };
837 
838  public:
839  typedef typename _Base::size_type size_type;
840  typedef typename _Base::hasher hasher;
841  typedef typename _Base::key_equal key_equal;
842  typedef typename _Base::allocator_type allocator_type;
843 
844  typedef typename _Base::key_type key_type;
845  typedef typename _Base::value_type value_type;
846 
848  _Base_iterator, unordered_multimap> iterator;
850  _Base_const_iterator, unordered_multimap> const_iterator;
852  _Base_local_iterator, unordered_multimap> local_iterator;
854  _Base_const_local_iterator, unordered_multimap> const_local_iterator;
855 
856  unordered_multimap() = default;
857 
858  explicit
859  unordered_multimap(size_type __n,
860  const hasher& __hf = hasher(),
861  const key_equal& __eql = key_equal(),
862  const allocator_type& __a = allocator_type())
863  : _Base(__n, __hf, __eql, __a) { }
864 
865  template<typename _InputIterator>
866  unordered_multimap(_InputIterator __first, _InputIterator __last,
867  size_type __n = 0,
868  const hasher& __hf = hasher(),
869  const key_equal& __eql = key_equal(),
870  const allocator_type& __a = allocator_type())
872  __glibcxx_check_valid_constructor_range(__first, __last)),
873  __gnu_debug::__base(__last), __n,
874  __hf, __eql, __a) { }
875 
876  unordered_multimap(const unordered_multimap&) = default;
877 
878  unordered_multimap(_Base_ref __x)
879  : _Base(__x._M_ref) { }
880 
882 
883  explicit
884  unordered_multimap(const allocator_type& __a)
885  : _Base(__a) { }
886 
888  const allocator_type& __a)
889  : _Base(__umap, __a) { }
890 
892  const allocator_type& __a)
893  noexcept( noexcept(_Base(std::move(__umap._M_base()), __a)) )
894  : _Safe(std::move(__umap._M_safe()), __a),
895  _Base(std::move(__umap._M_base()), __a) { }
896 
898  size_type __n = 0,
899  const hasher& __hf = hasher(),
900  const key_equal& __eql = key_equal(),
901  const allocator_type& __a = allocator_type())
902  : _Base(__l, __n, __hf, __eql, __a) { }
903 
904  unordered_multimap(size_type __n, const allocator_type& __a)
905  : unordered_multimap(__n, hasher(), key_equal(), __a)
906  { }
907 
908  unordered_multimap(size_type __n, const hasher& __hf,
909  const allocator_type& __a)
910  : unordered_multimap(__n, __hf, key_equal(), __a)
911  { }
912 
913  template<typename _InputIterator>
914  unordered_multimap(_InputIterator __first, _InputIterator __last,
915  size_type __n,
916  const allocator_type& __a)
917  : unordered_multimap(__first, __last, __n, hasher(), key_equal(), __a)
918  { }
919 
920  template<typename _InputIterator>
921  unordered_multimap(_InputIterator __first, _InputIterator __last,
922  size_type __n, const hasher& __hf,
923  const allocator_type& __a)
924  : unordered_multimap(__first, __last, __n, __hf, key_equal(), __a)
925  { }
926 
928  size_type __n,
929  const allocator_type& __a)
930  : unordered_multimap(__l, __n, hasher(), key_equal(), __a)
931  { }
932 
934  size_type __n, const hasher& __hf,
935  const allocator_type& __a)
936  : unordered_multimap(__l, __n, __hf, key_equal(), __a)
937  { }
938 
939  ~unordered_multimap() = default;
940 
942  operator=(const unordered_multimap&) = default;
943 
945  operator=(unordered_multimap&&) = default;
946 
948  operator=(initializer_list<value_type> __l)
949  {
950  this->_M_base() = __l;
951  this->_M_invalidate_all();
952  return *this;
953  }
954 
955  void
956  swap(unordered_multimap& __x)
957  noexcept( noexcept(declval<_Base&>().swap(__x)) )
958  {
959  _Safe::_M_swap(__x);
960  _Base::swap(__x);
961  }
962 
963  void
964  clear() noexcept
965  {
966  _Base::clear();
967  this->_M_invalidate_all();
968  }
969 
970  iterator
971  begin() noexcept
972  { return { _Base::begin(), this }; }
973 
975  begin() const noexcept
976  { return { _Base::begin(), this }; }
977 
978  iterator
979  end() noexcept
980  { return { _Base::end(), this }; }
981 
983  end() const noexcept
984  { return { _Base::end(), this }; }
985 
987  cbegin() const noexcept
988  { return { _Base::cbegin(), this }; }
989 
991  cend() const noexcept
992  { return { _Base::cend(), this }; }
993 
994  // local versions
996  begin(size_type __b)
997  {
998  __glibcxx_check_bucket_index(__b);
999  return { _Base::begin(__b), this };
1000  }
1001 
1003  end(size_type __b)
1004  {
1005  __glibcxx_check_bucket_index(__b);
1006  return { _Base::end(__b), this };
1007  }
1008 
1010  begin(size_type __b) const
1011  {
1012  __glibcxx_check_bucket_index(__b);
1013  return { _Base::begin(__b), this };
1014  }
1015 
1017  end(size_type __b) const
1018  {
1019  __glibcxx_check_bucket_index(__b);
1020  return { _Base::end(__b), this };
1021  }
1022 
1024  cbegin(size_type __b) const
1025  {
1026  __glibcxx_check_bucket_index(__b);
1027  return { _Base::cbegin(__b), this };
1028  }
1029 
1031  cend(size_type __b) const
1032  {
1033  __glibcxx_check_bucket_index(__b);
1034  return { _Base::cend(__b), this };
1035  }
1036 
1037  size_type
1038  bucket_size(size_type __b) const
1039  {
1040  __glibcxx_check_bucket_index(__b);
1041  return _Base::bucket_size(__b);
1042  }
1043 
1044  float
1045  max_load_factor() const noexcept
1046  { return _Base::max_load_factor(); }
1047 
1048  void
1049  max_load_factor(float __f)
1050  {
1051  __glibcxx_check_max_load_factor(__f);
1052  _Base::max_load_factor(__f);
1053  }
1054 
1055  template<typename... _Args>
1056  iterator
1057  emplace(_Args&&... __args)
1058  {
1059  size_type __bucket_count = this->bucket_count();
1060  auto __it = _Base::emplace(std::forward<_Args>(__args)...);
1061  _M_check_rehashed(__bucket_count);
1062  return { __it, this };
1063  }
1064 
1065  template<typename... _Args>
1066  iterator
1067  emplace_hint(const_iterator __hint, _Args&&... __args)
1068  {
1069  __glibcxx_check_insert(__hint);
1070  size_type __bucket_count = this->bucket_count();
1071  auto __it = _Base::emplace_hint(__hint.base(),
1072  std::forward<_Args>(__args)...);
1073  _M_check_rehashed(__bucket_count);
1074  return { __it, this };
1075  }
1076 
1077  iterator
1078  insert(const value_type& __obj)
1079  {
1080  size_type __bucket_count = this->bucket_count();
1081  auto __it = _Base::insert(__obj);
1082  _M_check_rehashed(__bucket_count);
1083  return { __it, this };
1084  }
1085 
1086  // _GLIBCXX_RESOLVE_LIB_DEFECTS
1087  // 2354. Unnecessary copying when inserting into maps with braced-init
1088  iterator
1089  insert(value_type&& __x)
1090  {
1091  size_type __bucket_count = this->bucket_count();
1092  auto __it = _Base::insert(std::move(__x));
1093  _M_check_rehashed(__bucket_count);
1094  return { __it, this };
1095  }
1096 
1097  iterator
1098  insert(const_iterator __hint, const value_type& __obj)
1099  {
1100  __glibcxx_check_insert(__hint);
1101  size_type __bucket_count = this->bucket_count();
1102  auto __it = _Base::insert(__hint.base(), __obj);
1103  _M_check_rehashed(__bucket_count);
1104  return { __it, this };
1105  }
1106 
1107  // _GLIBCXX_RESOLVE_LIB_DEFECTS
1108  // 2354. Unnecessary copying when inserting into maps with braced-init
1109  iterator
1110  insert(const_iterator __hint, value_type&& __x)
1111  {
1112  __glibcxx_check_insert(__hint);
1113  size_type __bucket_count = this->bucket_count();
1114  auto __it = _Base::insert(__hint.base(), std::move(__x));
1115  _M_check_rehashed(__bucket_count);
1116  return { __it, this };
1117  }
1118 
1119  template<typename _Pair, typename = typename
1121  _Pair&&>::value>::type>
1122  iterator
1123  insert(_Pair&& __obj)
1124  {
1125  size_type __bucket_count = this->bucket_count();
1126  auto __it = _Base::insert(std::forward<_Pair>(__obj));
1127  _M_check_rehashed(__bucket_count);
1128  return { __it, this };
1129  }
1130 
1131  template<typename _Pair, typename = typename
1133  _Pair&&>::value>::type>
1134  iterator
1135  insert(const_iterator __hint, _Pair&& __obj)
1136  {
1137  __glibcxx_check_insert(__hint);
1138  size_type __bucket_count = this->bucket_count();
1139  auto __it = _Base::insert(__hint.base(), std::forward<_Pair>(__obj));
1140  _M_check_rehashed(__bucket_count);
1141  return { __it, this };
1142  }
1143 
1144  void
1146  { _Base::insert(__l); }
1147 
1148  template<typename _InputIterator>
1149  void
1150  insert(_InputIterator __first, _InputIterator __last)
1151  {
1153  __glibcxx_check_valid_range2(__first, __last, __dist);
1154  size_type __bucket_count = this->bucket_count();
1155 
1156  if (__dist.second >= __gnu_debug::__dp_sign)
1157  _Base::insert(__gnu_debug::__unsafe(__first),
1158  __gnu_debug::__unsafe(__last));
1159  else
1160  _Base::insert(__first, __last);
1161 
1162  _M_check_rehashed(__bucket_count);
1163  }
1164 
1165 #if __cplusplus > 201402L
1166  using node_type = typename _Base::node_type;
1167 
1168  node_type
1169  extract(const_iterator __position)
1170  {
1171  __glibcxx_check_erase(__position);
1172  return _M_extract(__position.base());
1173  }
1174 
1175  node_type
1176  extract(const key_type& __key)
1177  {
1178  const auto __position = _Base::find(__key);
1179  if (__position != _Base::end())
1180  return _M_extract(__position);
1181  return {};
1182  }
1183 
1184  iterator
1185  insert(node_type&& __nh)
1186  { return { _Base::insert(std::move(__nh)), this }; }
1187 
1188  iterator
1189  insert(const_iterator __hint, node_type&& __nh)
1190  {
1191  __glibcxx_check_insert(__hint);
1192  return { _Base::insert(__hint.base(), std::move(__nh)), this };
1193  }
1194 
1195  using _Base::merge;
1196 #endif // C++17
1197 
1198  iterator
1199  find(const key_type& __key)
1200  { return { _Base::find(__key), this }; }
1201 
1202 #if __cplusplus > 201703L
1203  template<typename _Kt,
1204  typename = std::__has_is_transparent_t<_Hash, _Kt>,
1205  typename = std::__has_is_transparent_t<_Pred, _Kt>>
1206  iterator
1207  find(const _Kt& __k)
1208  { return { _Base::find(__k), this }; }
1209 #endif
1210 
1212  find(const key_type& __key) const
1213  { return { _Base::find(__key), this }; }
1214 
1215 #if __cplusplus > 201703L
1216  template<typename _Kt,
1217  typename = std::__has_is_transparent_t<_Hash, _Kt>,
1218  typename = std::__has_is_transparent_t<_Pred, _Kt>>
1220  find(const _Kt& __k) const
1221  { return { _Base::find(__k), this }; }
1222 #endif
1223 
1225  equal_range(const key_type& __key)
1226  {
1227  auto __res = _Base::equal_range(__key);
1228  return { { __res.first, this }, { __res.second, this } };
1229  }
1230 
1231 #if __cplusplus > 201703L
1232  template<typename _Kt,
1233  typename = std::__has_is_transparent_t<_Hash, _Kt>,
1234  typename = std::__has_is_transparent_t<_Pred, _Kt>>
1236  equal_range(const _Kt& __k)
1237  {
1238  auto __res = _Base::equal_range(__k);
1239  return { { __res.first, this }, { __res.second, this } };
1240  }
1241 #endif
1242 
1244  equal_range(const key_type& __key) const
1245  {
1246  auto __res = _Base::equal_range(__key);
1247  return { { __res.first, this }, { __res.second, this } };
1248  }
1249 
1250 #if __cplusplus > 201703L
1251  template<typename _Kt,
1252  typename = std::__has_is_transparent_t<_Hash, _Kt>,
1253  typename = std::__has_is_transparent_t<_Pred, _Kt>>
1255  equal_range(const _Kt& __k) const
1256  {
1257  auto __res = _Base::equal_range(__k);
1258  return { { __res.first, this }, { __res.second, this } };
1259  }
1260 #endif
1261 
1262  size_type
1263  erase(const key_type& __key)
1264  {
1265  size_type __ret(0);
1266  size_type __bucket_count = this->bucket_count();
1267  auto __pair = _Base::equal_range(__key);
1268  for (auto __victim = __pair.first; __victim != __pair.second;)
1269  {
1270  _M_invalidate(__victim);
1271  __victim = _Base::erase(__victim);
1272  ++__ret;
1273  }
1274 
1275  _M_check_rehashed(__bucket_count);
1276  return __ret;
1277  }
1278 
1279  iterator
1280  erase(const_iterator __it)
1281  {
1282  __glibcxx_check_erase(__it);
1283  return { _M_erase(__it.base()), this };
1284  }
1285 
1286  iterator
1287  erase(iterator __it)
1288  {
1289  __glibcxx_check_erase(__it);
1290  return { _M_erase(__it.base()), this };
1291  }
1292 
1293  iterator
1294  erase(const_iterator __first, const_iterator __last)
1295  {
1296  __glibcxx_check_erase_range(__first, __last);
1297  for (auto __tmp = __first.base(); __tmp != __last.base(); ++__tmp)
1298  {
1299  _GLIBCXX_DEBUG_VERIFY(__tmp != _Base::cend(),
1300  _M_message(__gnu_debug::__msg_valid_range)
1301  ._M_iterator(__first, "first")
1302  ._M_iterator(__last, "last"));
1303  _M_invalidate(__tmp);
1304  }
1305 
1306  size_type __bucket_count = this->bucket_count();
1307  auto __next = _Base::erase(__first.base(), __last.base());
1308  _M_check_rehashed(__bucket_count);
1309  return { __next, this };
1310  }
1311 
1312  _Base&
1313  _M_base() noexcept { return *this; }
1314 
1315  const _Base&
1316  _M_base() const noexcept { return *this; }
1317 
1318  private:
1319  void
1320  _M_check_rehashed(size_type __prev_count)
1321  {
1322  if (__prev_count != this->bucket_count())
1323  this->_M_invalidate_all();
1324  }
1325 
1326  void
1327  _M_invalidate(_Base_const_iterator __victim)
1328  {
1329  this->_M_invalidate_if(
1330  [__victim](_Base_const_iterator __it) { return __it == __victim; });
1331  this->_M_invalidate_local_if(
1332  [__victim](_Base_const_local_iterator __it)
1333  { return __it == __victim; });
1334  }
1335 
1336  _Base_iterator
1337  _M_erase(_Base_const_iterator __victim)
1338  {
1339  _M_invalidate(__victim);
1340  size_type __bucket_count = this->bucket_count();
1341  _Base_iterator __next = _Base::erase(__victim);
1342  _M_check_rehashed(__bucket_count);
1343  return __next;
1344  }
1345 
1346 #if __cplusplus > 201402L
1347  node_type
1348  _M_extract(_Base_const_iterator __victim)
1349  {
1350  _M_invalidate(__victim);
1351  return _Base::extract(__victim);
1352  }
1353 #endif
1354  };
1355 
1356 #if __cpp_deduction_guides >= 201606
1357 
1358  template<typename _InputIterator,
1359  typename _Hash = hash<__iter_key_t<_InputIterator>>,
1360  typename _Pred = equal_to<__iter_key_t<_InputIterator>>,
1361  typename _Allocator = allocator<__iter_to_alloc_t<_InputIterator>>,
1362  typename = _RequireInputIter<_InputIterator>,
1363  typename = _RequireNotAllocatorOrIntegral<_Hash>,
1364  typename = _RequireNotAllocator<_Pred>,
1365  typename = _RequireAllocator<_Allocator>>
1366  unordered_multimap(_InputIterator, _InputIterator,
1367  unordered_multimap<int, int>::size_type = {},
1368  _Hash = _Hash(), _Pred = _Pred(),
1369  _Allocator = _Allocator())
1370  -> unordered_multimap<__iter_key_t<_InputIterator>,
1371  __iter_val_t<_InputIterator>, _Hash, _Pred,
1372  _Allocator>;
1373 
1374  template<typename _Key, typename _Tp, typename _Hash = hash<_Key>,
1375  typename _Pred = equal_to<_Key>,
1376  typename _Allocator = allocator<pair<const _Key, _Tp>>,
1377  typename = _RequireNotAllocatorOrIntegral<_Hash>,
1378  typename = _RequireNotAllocator<_Pred>,
1379  typename = _RequireAllocator<_Allocator>>
1382  _Hash = _Hash(), _Pred = _Pred(),
1383  _Allocator = _Allocator())
1384  -> unordered_multimap<_Key, _Tp, _Hash, _Pred, _Allocator>;
1385 
1386  template<typename _InputIterator, typename _Allocator,
1387  typename = _RequireInputIter<_InputIterator>,
1388  typename = _RequireAllocator<_Allocator>>
1389  unordered_multimap(_InputIterator, _InputIterator,
1390  unordered_multimap<int, int>::size_type, _Allocator)
1391  -> unordered_multimap<__iter_key_t<_InputIterator>,
1392  __iter_val_t<_InputIterator>,
1393  hash<__iter_key_t<_InputIterator>>,
1394  equal_to<__iter_key_t<_InputIterator>>, _Allocator>;
1395 
1396  template<typename _InputIterator, typename _Allocator,
1397  typename = _RequireInputIter<_InputIterator>,
1398  typename = _RequireAllocator<_Allocator>>
1399  unordered_multimap(_InputIterator, _InputIterator, _Allocator)
1400  -> unordered_multimap<__iter_key_t<_InputIterator>,
1401  __iter_val_t<_InputIterator>,
1402  hash<__iter_key_t<_InputIterator>>,
1403  equal_to<__iter_key_t<_InputIterator>>, _Allocator>;
1404 
1405  template<typename _InputIterator, typename _Hash, typename _Allocator,
1406  typename = _RequireInputIter<_InputIterator>,
1407  typename = _RequireNotAllocatorOrIntegral<_Hash>,
1408  typename = _RequireAllocator<_Allocator>>
1409  unordered_multimap(_InputIterator, _InputIterator,
1410  unordered_multimap<int, int>::size_type, _Hash,
1411  _Allocator)
1412  -> unordered_multimap<__iter_key_t<_InputIterator>,
1413  __iter_val_t<_InputIterator>, _Hash,
1414  equal_to<__iter_key_t<_InputIterator>>, _Allocator>;
1415 
1416  template<typename _Key, typename _Tp, typename _Allocator,
1417  typename = _RequireAllocator<_Allocator>>
1418  unordered_multimap(initializer_list<pair<_Key, _Tp>>,
1419  unordered_multimap<int, int>::size_type,
1420  _Allocator)
1421  -> unordered_multimap<_Key, _Tp, hash<_Key>, equal_to<_Key>, _Allocator>;
1422 
1423  template<typename _Key, typename _Tp, typename _Allocator,
1424  typename = _RequireAllocator<_Allocator>>
1425  unordered_multimap(initializer_list<pair<_Key, _Tp>>, _Allocator)
1426  -> unordered_multimap<_Key, _Tp, hash<_Key>, equal_to<_Key>, _Allocator>;
1427 
1428  template<typename _Key, typename _Tp, typename _Hash, typename _Allocator,
1429  typename = _RequireNotAllocatorOrIntegral<_Hash>,
1430  typename = _RequireAllocator<_Allocator>>
1431  unordered_multimap(initializer_list<pair<_Key, _Tp>>,
1432  unordered_multimap<int, int>::size_type,
1433  _Hash, _Allocator)
1434  -> unordered_multimap<_Key, _Tp, _Hash, equal_to<_Key>, _Allocator>;
1435 
1436 #endif
1437 
1438  template<typename _Key, typename _Tp, typename _Hash,
1439  typename _Pred, typename _Alloc>
1440  inline void
1441  swap(unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
1442  unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
1443  noexcept(noexcept(__x.swap(__y)))
1444  { __x.swap(__y); }
1445 
1446  template<typename _Key, typename _Tp, typename _Hash,
1447  typename _Pred, typename _Alloc>
1448  inline bool
1449  operator==(const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
1450  const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
1451  { return __x._M_base() == __y._M_base(); }
1452 
1453 #if __cpp_impl_three_way_comparison < 201907L
1454  template<typename _Key, typename _Tp, typename _Hash,
1455  typename _Pred, typename _Alloc>
1456  inline bool
1457  operator!=(const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
1458  const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
1459  { return !(__x == __y); }
1460 #endif
1461 
1462 } // namespace __debug
1463 } // namespace std
1464 
1465 #endif // C++11
1466 
1467 #endif
#define __glibcxx_check_insert(_Position)
Definition: macros.h:146
#define __glibcxx_check_erase_range(_First, _Last)
Definition: macros.h:240
#define __glibcxx_check_erase(_Position)
Definition: macros.h:212
constexpr std::remove_reference< _Tp >::type && move(_Tp &&__t) noexcept
Convert a value to an rvalue.
Definition: move.h:104
ISO C++ entities toplevel namespace is std.
constexpr _Iterator __base(_Iterator __it)
initializer_list
Primary class template hash.
is_constructible
Definition: type_traits:954
Define a member typedef type only if a boolean constant is true.
Definition: type_traits:2200
The standard allocator, as per C++03 [20.4.1].
Definition: allocator.h:141
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:202
_T2 second
The second member.
Definition: stl_pair.h:207
A standard container composed of equivalent keys (possibly containing multiple of each key value) tha...
_Hashtable::size_type size_type
Iterator-related typedefs.
A standard container composed of unique keys (containing at most one of each key value) that associat...
_Hashtable::size_type size_type
Iterator-related typedefs.
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.