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