libstdc++
debug/unordered_map
Go to the documentation of this file.
1 // Debugging unordered_map/unordered_multimap implementation -*- C++ -*-
2 
3 // Copyright (C) 2003-2019 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  template<typename _Key, typename _Tp, typename _Hash,
746  typename _Pred, typename _Alloc>
747  inline bool
748  operator!=(const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
749  const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
750  { return !(__x == __y); }
751 
752 
753  /// Class std::unordered_multimap with safety/checking/debug instrumentation.
754  template<typename _Key, typename _Tp,
755  typename _Hash = std::hash<_Key>,
756  typename _Pred = std::equal_to<_Key>,
757  typename _Alloc = std::allocator<std::pair<const _Key, _Tp> > >
758  class unordered_multimap
759  : public __gnu_debug::_Safe_container<
760  unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>, _Alloc,
761  __gnu_debug::_Safe_unordered_container>,
762  public _GLIBCXX_STD_C::unordered_multimap<
763  _Key, _Tp, _Hash, _Pred, _Alloc>
764  {
765  typedef _GLIBCXX_STD_C::unordered_multimap<_Key, _Tp, _Hash,
766  _Pred, _Alloc> _Base;
767  typedef __gnu_debug::_Safe_container<unordered_multimap,
768  _Alloc, __gnu_debug::_Safe_unordered_container> _Safe;
769  typedef typename _Base::const_iterator _Base_const_iterator;
770  typedef typename _Base::iterator _Base_iterator;
771  typedef typename _Base::const_local_iterator _Base_const_local_iterator;
772  typedef typename _Base::local_iterator _Base_local_iterator;
773 
774  template<typename _ItT, typename _SeqT, typename _CatT>
775  friend class ::__gnu_debug::_Safe_iterator;
776  template<typename _ItT, typename _SeqT>
777  friend class ::__gnu_debug::_Safe_local_iterator;
778 
779  public:
780  typedef typename _Base::size_type size_type;
781  typedef typename _Base::hasher hasher;
782  typedef typename _Base::key_equal key_equal;
783  typedef typename _Base::allocator_type allocator_type;
784 
785  typedef typename _Base::key_type key_type;
786  typedef typename _Base::value_type value_type;
787 
788  typedef __gnu_debug::_Safe_iterator<
789  _Base_iterator, unordered_multimap> iterator;
790  typedef __gnu_debug::_Safe_iterator<
791  _Base_const_iterator, unordered_multimap> const_iterator;
792  typedef __gnu_debug::_Safe_local_iterator<
793  _Base_local_iterator, unordered_multimap> local_iterator;
794  typedef __gnu_debug::_Safe_local_iterator<
795  _Base_const_local_iterator, unordered_multimap> const_local_iterator;
796 
797  unordered_multimap() = default;
798 
799  explicit
800  unordered_multimap(size_type __n,
801  const hasher& __hf = hasher(),
802  const key_equal& __eql = key_equal(),
803  const allocator_type& __a = allocator_type())
804  : _Base(__n, __hf, __eql, __a) { }
805 
806  template<typename _InputIterator>
807  unordered_multimap(_InputIterator __first, _InputIterator __last,
808  size_type __n = 0,
809  const hasher& __hf = hasher(),
810  const key_equal& __eql = key_equal(),
811  const allocator_type& __a = allocator_type())
812  : _Base(__gnu_debug::__base(
813  __glibcxx_check_valid_constructor_range(__first, __last)),
814  __gnu_debug::__base(__last), __n,
815  __hf, __eql, __a) { }
816 
817  unordered_multimap(const unordered_multimap&) = default;
818 
819  unordered_multimap(const _Base& __x)
820  : _Base(__x) { }
821 
822  unordered_multimap(unordered_multimap&&) = default;
823 
824  explicit
825  unordered_multimap(const allocator_type& __a)
826  : _Base(__a) { }
827 
828  unordered_multimap(const unordered_multimap& __umap,
829  const allocator_type& __a)
830  : _Base(__umap, __a) { }
831 
832  unordered_multimap(unordered_multimap&& __umap,
833  const allocator_type& __a)
834  noexcept( noexcept(_Base(std::move(__umap._M_base()), __a)) )
835  : _Safe(std::move(__umap._M_safe()), __a),
836  _Base(std::move(__umap._M_base()), __a) { }
837 
838  unordered_multimap(initializer_list<value_type> __l,
839  size_type __n = 0,
840  const hasher& __hf = hasher(),
841  const key_equal& __eql = key_equal(),
842  const allocator_type& __a = allocator_type())
843  : _Base(__l, __n, __hf, __eql, __a) { }
844 
845  unordered_multimap(size_type __n, const allocator_type& __a)
846  : unordered_multimap(__n, hasher(), key_equal(), __a)
847  { }
848 
849  unordered_multimap(size_type __n, const hasher& __hf,
850  const allocator_type& __a)
851  : unordered_multimap(__n, __hf, key_equal(), __a)
852  { }
853 
854  template<typename _InputIterator>
855  unordered_multimap(_InputIterator __first, _InputIterator __last,
856  size_type __n,
857  const allocator_type& __a)
858  : unordered_multimap(__first, __last, __n, hasher(), key_equal(), __a)
859  { }
860 
861  template<typename _InputIterator>
862  unordered_multimap(_InputIterator __first, _InputIterator __last,
863  size_type __n, const hasher& __hf,
864  const allocator_type& __a)
865  : unordered_multimap(__first, __last, __n, __hf, key_equal(), __a)
866  { }
867 
868  unordered_multimap(initializer_list<value_type> __l,
869  size_type __n,
870  const allocator_type& __a)
871  : unordered_multimap(__l, __n, hasher(), key_equal(), __a)
872  { }
873 
874  unordered_multimap(initializer_list<value_type> __l,
875  size_type __n, const hasher& __hf,
876  const allocator_type& __a)
877  : unordered_multimap(__l, __n, __hf, key_equal(), __a)
878  { }
879 
880  ~unordered_multimap() = default;
881 
882  unordered_multimap&
883  operator=(const unordered_multimap&) = default;
884 
885  unordered_multimap&
886  operator=(unordered_multimap&&) = default;
887 
888  unordered_multimap&
889  operator=(initializer_list<value_type> __l)
890  {
891  this->_M_base() = __l;
892  this->_M_invalidate_all();
893  return *this;
894  }
895 
896  void
897  swap(unordered_multimap& __x)
898  noexcept( noexcept(declval<_Base&>().swap(__x)) )
899  {
900  _Safe::_M_swap(__x);
901  _Base::swap(__x);
902  }
903 
904  void
905  clear() noexcept
906  {
907  _Base::clear();
908  this->_M_invalidate_all();
909  }
910 
911  iterator
912  begin() noexcept
913  { return { _Base::begin(), this }; }
914 
915  const_iterator
916  begin() const noexcept
917  { return { _Base::begin(), this }; }
918 
919  iterator
920  end() noexcept
921  { return { _Base::end(), this }; }
922 
923  const_iterator
924  end() const noexcept
925  { return { _Base::end(), this }; }
926 
927  const_iterator
928  cbegin() const noexcept
929  { return { _Base::cbegin(), this }; }
930 
931  const_iterator
932  cend() const noexcept
933  { return { _Base::cend(), this }; }
934 
935  // local versions
936  local_iterator
937  begin(size_type __b)
938  {
939  __glibcxx_check_bucket_index(__b);
940  return { _Base::begin(__b), this };
941  }
942 
943  local_iterator
944  end(size_type __b)
945  {
946  __glibcxx_check_bucket_index(__b);
947  return { _Base::end(__b), this };
948  }
949 
950  const_local_iterator
951  begin(size_type __b) const
952  {
953  __glibcxx_check_bucket_index(__b);
954  return { _Base::begin(__b), this };
955  }
956 
957  const_local_iterator
958  end(size_type __b) const
959  {
960  __glibcxx_check_bucket_index(__b);
961  return { _Base::end(__b), this };
962  }
963 
964  const_local_iterator
965  cbegin(size_type __b) const
966  {
967  __glibcxx_check_bucket_index(__b);
968  return { _Base::cbegin(__b), this };
969  }
970 
971  const_local_iterator
972  cend(size_type __b) const
973  {
974  __glibcxx_check_bucket_index(__b);
975  return { _Base::cend(__b), this };
976  }
977 
978  size_type
979  bucket_size(size_type __b) const
980  {
981  __glibcxx_check_bucket_index(__b);
982  return _Base::bucket_size(__b);
983  }
984 
985  float
986  max_load_factor() const noexcept
987  { return _Base::max_load_factor(); }
988 
989  void
990  max_load_factor(float __f)
991  {
992  __glibcxx_check_max_load_factor(__f);
993  _Base::max_load_factor(__f);
994  }
995 
996  template<typename... _Args>
997  iterator
998  emplace(_Args&&... __args)
999  {
1000  size_type __bucket_count = this->bucket_count();
1001  auto __it = _Base::emplace(std::forward<_Args>(__args)...);
1002  _M_check_rehashed(__bucket_count);
1003  return { __it, this };
1004  }
1005 
1006  template<typename... _Args>
1007  iterator
1008  emplace_hint(const_iterator __hint, _Args&&... __args)
1009  {
1010  __glibcxx_check_insert(__hint);
1011  size_type __bucket_count = this->bucket_count();
1012  auto __it = _Base::emplace_hint(__hint.base(),
1013  std::forward<_Args>(__args)...);
1014  _M_check_rehashed(__bucket_count);
1015  return { __it, this };
1016  }
1017 
1018  iterator
1019  insert(const value_type& __obj)
1020  {
1021  size_type __bucket_count = this->bucket_count();
1022  auto __it = _Base::insert(__obj);
1023  _M_check_rehashed(__bucket_count);
1024  return { __it, this };
1025  }
1026 
1027  // _GLIBCXX_RESOLVE_LIB_DEFECTS
1028  // 2354. Unnecessary copying when inserting into maps with braced-init
1029  iterator
1030  insert(value_type&& __x)
1031  {
1032  size_type __bucket_count = this->bucket_count();
1033  auto __it = _Base::insert(std::move(__x));
1034  _M_check_rehashed(__bucket_count);
1035  return { __it, this };
1036  }
1037 
1038  iterator
1039  insert(const_iterator __hint, const value_type& __obj)
1040  {
1041  __glibcxx_check_insert(__hint);
1042  size_type __bucket_count = this->bucket_count();
1043  auto __it = _Base::insert(__hint.base(), __obj);
1044  _M_check_rehashed(__bucket_count);
1045  return { __it, this };
1046  }
1047 
1048  // _GLIBCXX_RESOLVE_LIB_DEFECTS
1049  // 2354. Unnecessary copying when inserting into maps with braced-init
1050  iterator
1051  insert(const_iterator __hint, value_type&& __x)
1052  {
1053  __glibcxx_check_insert(__hint);
1054  size_type __bucket_count = this->bucket_count();
1055  auto __it = _Base::insert(__hint.base(), std::move(__x));
1056  _M_check_rehashed(__bucket_count);
1057  return { __it, this };
1058  }
1059 
1060  template<typename _Pair, typename = typename
1061  std::enable_if<std::is_constructible<value_type,
1062  _Pair&&>::value>::type>
1063  iterator
1064  insert(_Pair&& __obj)
1065  {
1066  size_type __bucket_count = this->bucket_count();
1067  auto __it = _Base::insert(std::forward<_Pair>(__obj));
1068  _M_check_rehashed(__bucket_count);
1069  return { __it, this };
1070  }
1071 
1072  template<typename _Pair, typename = typename
1073  std::enable_if<std::is_constructible<value_type,
1074  _Pair&&>::value>::type>
1075  iterator
1076  insert(const_iterator __hint, _Pair&& __obj)
1077  {
1078  __glibcxx_check_insert(__hint);
1079  size_type __bucket_count = this->bucket_count();
1080  auto __it = _Base::insert(__hint.base(), std::forward<_Pair>(__obj));
1081  _M_check_rehashed(__bucket_count);
1082  return { __it, this };
1083  }
1084 
1085  void
1086  insert(std::initializer_list<value_type> __l)
1087  { _Base::insert(__l); }
1088 
1089  template<typename _InputIterator>
1090  void
1091  insert(_InputIterator __first, _InputIterator __last)
1092  {
1093  typename __gnu_debug::_Distance_traits<_InputIterator>::__type __dist;
1094  __glibcxx_check_valid_range2(__first, __last, __dist);
1095  size_type __bucket_count = this->bucket_count();
1096 
1097  if (__dist.second >= __gnu_debug::__dp_sign)
1098  _Base::insert(__gnu_debug::__unsafe(__first),
1099  __gnu_debug::__unsafe(__last));
1100  else
1101  _Base::insert(__first, __last);
1102 
1103  _M_check_rehashed(__bucket_count);
1104  }
1105 
1106 #if __cplusplus > 201402L
1107  using node_type = typename _Base::node_type;
1108 
1109  node_type
1110  extract(const_iterator __position)
1111  {
1112  __glibcxx_check_erase(__position);
1113  return _M_extract(__position.base());
1114  }
1115 
1116  node_type
1117  extract(const key_type& __key)
1118  {
1119  const auto __position = _Base::find(__key);
1120  if (__position != _Base::end())
1121  return _M_extract(__position);
1122  return {};
1123  }
1124 
1125  iterator
1126  insert(node_type&& __nh)
1127  { return { _Base::insert(std::move(__nh)), this }; }
1128 
1129  iterator
1130  insert(const_iterator __hint, node_type&& __nh)
1131  {
1132  __glibcxx_check_insert(__hint);
1133  return { _Base::insert(__hint.base(), std::move(__nh)), this };
1134  }
1135 
1136  using _Base::merge;
1137 #endif // C++17
1138 
1139  iterator
1140  find(const key_type& __key)
1141  { return { _Base::find(__key), this }; }
1142 
1143  const_iterator
1144  find(const key_type& __key) const
1145  { return { _Base::find(__key), this }; }
1146 
1147  std::pair<iterator, iterator>
1148  equal_range(const key_type& __key)
1149  {
1150  auto __res = _Base::equal_range(__key);
1151  return { { __res.first, this }, { __res.second, this } };
1152  }
1153 
1154  std::pair<const_iterator, const_iterator>
1155  equal_range(const key_type& __key) const
1156  {
1157  auto __res = _Base::equal_range(__key);
1158  return { { __res.first, this }, { __res.second, this } };
1159  }
1160 
1161  size_type
1162  erase(const key_type& __key)
1163  {
1164  size_type __ret(0);
1165  size_type __bucket_count = this->bucket_count();
1166  auto __pair = _Base::equal_range(__key);
1167  for (auto __victim = __pair.first; __victim != __pair.second;)
1168  {
1169  _M_invalidate(__victim);
1170  __victim = _Base::erase(__victim);
1171  ++__ret;
1172  }
1173 
1174  _M_check_rehashed(__bucket_count);
1175  return __ret;
1176  }
1177 
1178  iterator
1179  erase(const_iterator __it)
1180  {
1181  __glibcxx_check_erase(__it);
1182  return { _M_erase(__it.base()), this };
1183  }
1184 
1185  iterator
1186  erase(iterator __it)
1187  {
1188  __glibcxx_check_erase(__it);
1189  return { _M_erase(__it.base()), this };
1190  }
1191 
1192  iterator
1193  erase(const_iterator __first, const_iterator __last)
1194  {
1195  __glibcxx_check_erase_range(__first, __last);
1196  for (auto __tmp = __first.base(); __tmp != __last.base(); ++__tmp)
1197  {
1198  _GLIBCXX_DEBUG_VERIFY(__tmp != _Base::cend(),
1199  _M_message(__gnu_debug::__msg_valid_range)
1200  ._M_iterator(__first, "first")
1201  ._M_iterator(__last, "last"));
1202  _M_invalidate(__tmp);
1203  }
1204 
1205  size_type __bucket_count = this->bucket_count();
1206  auto __next = _Base::erase(__first.base(), __last.base());
1207  _M_check_rehashed(__bucket_count);
1208  return { __next, this };
1209  }
1210 
1211  _Base&
1212  _M_base() noexcept { return *this; }
1213 
1214  const _Base&
1215  _M_base() const noexcept { return *this; }
1216 
1217  private:
1218  void
1219  _M_check_rehashed(size_type __prev_count)
1220  {
1221  if (__prev_count != this->bucket_count())
1222  this->_M_invalidate_all();
1223  }
1224 
1225  void
1226  _M_invalidate(_Base_const_iterator __victim)
1227  {
1228  this->_M_invalidate_if(
1229  [__victim](_Base_const_iterator __it) { return __it == __victim; });
1230  this->_M_invalidate_local_if(
1231  [__victim](_Base_const_local_iterator __it)
1232  { return __it._M_curr() == __victim._M_cur; });
1233  }
1234 
1235  _Base_iterator
1236  _M_erase(_Base_const_iterator __victim)
1237  {
1238  _M_invalidate(__victim);
1239  size_type __bucket_count = this->bucket_count();
1240  _Base_iterator __next = _Base::erase(__victim);
1241  _M_check_rehashed(__bucket_count);
1242  return __next;
1243  }
1244 
1245 #if __cplusplus > 201402L
1246  node_type
1247  _M_extract(_Base_const_iterator __victim)
1248  {
1249  _M_invalidate(__victim);
1250  return _Base::extract(__victim);
1251  }
1252 #endif
1253  };
1254 
1255 #if __cpp_deduction_guides >= 201606
1256 
1257  template<typename _InputIterator,
1258  typename _Hash = hash<__iter_key_t<_InputIterator>>,
1259  typename _Pred = equal_to<__iter_key_t<_InputIterator>>,
1260  typename _Allocator = allocator<__iter_to_alloc_t<_InputIterator>>,
1261  typename = _RequireInputIter<_InputIterator>,
1262  typename = _RequireNotAllocatorOrIntegral<_Hash>,
1263  typename = _RequireNotAllocator<_Pred>,
1264  typename = _RequireAllocator<_Allocator>>
1265  unordered_multimap(_InputIterator, _InputIterator,
1266  unordered_multimap<int, int>::size_type = {},
1267  _Hash = _Hash(), _Pred = _Pred(),
1268  _Allocator = _Allocator())
1269  -> unordered_multimap<__iter_key_t<_InputIterator>,
1270  __iter_val_t<_InputIterator>, _Hash, _Pred,
1271  _Allocator>;
1272 
1273  template<typename _Key, typename _Tp, typename _Hash = hash<_Key>,
1274  typename _Pred = equal_to<_Key>,
1275  typename _Allocator = allocator<pair<const _Key, _Tp>>,
1276  typename = _RequireNotAllocatorOrIntegral<_Hash>,
1277  typename = _RequireNotAllocator<_Pred>,
1278  typename = _RequireAllocator<_Allocator>>
1279  unordered_multimap(initializer_list<pair<_Key, _Tp>>,
1280  unordered_multimap<int, int>::size_type = {},
1281  _Hash = _Hash(), _Pred = _Pred(),
1282  _Allocator = _Allocator())
1283  -> unordered_multimap<_Key, _Tp, _Hash, _Pred, _Allocator>;
1284 
1285  template<typename _InputIterator, typename _Allocator,
1286  typename = _RequireInputIter<_InputIterator>,
1287  typename = _RequireAllocator<_Allocator>>
1288  unordered_multimap(_InputIterator, _InputIterator,
1289  unordered_multimap<int, int>::size_type, _Allocator)
1290  -> unordered_multimap<__iter_key_t<_InputIterator>,
1291  __iter_val_t<_InputIterator>,
1292  hash<__iter_key_t<_InputIterator>>,
1293  equal_to<__iter_key_t<_InputIterator>>, _Allocator>;
1294 
1295  template<typename _InputIterator, typename _Allocator,
1296  typename = _RequireInputIter<_InputIterator>,
1297  typename = _RequireAllocator<_Allocator>>
1298  unordered_multimap(_InputIterator, _InputIterator, _Allocator)
1299  -> unordered_multimap<__iter_key_t<_InputIterator>,
1300  __iter_val_t<_InputIterator>,
1301  hash<__iter_key_t<_InputIterator>>,
1302  equal_to<__iter_key_t<_InputIterator>>, _Allocator>;
1303 
1304  template<typename _InputIterator, typename _Hash, typename _Allocator,
1305  typename = _RequireInputIter<_InputIterator>,
1306  typename = _RequireNotAllocatorOrIntegral<_Hash>,
1307  typename = _RequireAllocator<_Allocator>>
1308  unordered_multimap(_InputIterator, _InputIterator,
1309  unordered_multimap<int, int>::size_type, _Hash,
1310  _Allocator)
1311  -> unordered_multimap<__iter_key_t<_InputIterator>,
1312  __iter_val_t<_InputIterator>, _Hash,
1313  equal_to<__iter_key_t<_InputIterator>>, _Allocator>;
1314 
1315  template<typename _Key, typename _Tp, typename _Allocator,
1316  typename = _RequireAllocator<_Allocator>>
1317  unordered_multimap(initializer_list<pair<_Key, _Tp>>,
1318  unordered_multimap<int, int>::size_type,
1319  _Allocator)
1320  -> unordered_multimap<_Key, _Tp, hash<_Key>, equal_to<_Key>, _Allocator>;
1321 
1322  template<typename _Key, typename _Tp, typename _Allocator,
1323  typename = _RequireAllocator<_Allocator>>
1324  unordered_multimap(initializer_list<pair<_Key, _Tp>>, _Allocator)
1325  -> unordered_multimap<_Key, _Tp, hash<_Key>, equal_to<_Key>, _Allocator>;
1326 
1327  template<typename _Key, typename _Tp, typename _Hash, typename _Allocator,
1328  typename = _RequireNotAllocatorOrIntegral<_Hash>,
1329  typename = _RequireAllocator<_Allocator>>
1330  unordered_multimap(initializer_list<pair<_Key, _Tp>>,
1331  unordered_multimap<int, int>::size_type,
1332  _Hash, _Allocator)
1333  -> unordered_multimap<_Key, _Tp, _Hash, equal_to<_Key>, _Allocator>;
1334 
1335 #endif
1336 
1337  template<typename _Key, typename _Tp, typename _Hash,
1338  typename _Pred, typename _Alloc>
1339  inline void
1340  swap(unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
1341  unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
1342  noexcept(noexcept(__x.swap(__y)))
1343  { __x.swap(__y); }
1344 
1345  template<typename _Key, typename _Tp, typename _Hash,
1346  typename _Pred, typename _Alloc>
1347  inline bool
1348  operator==(const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
1349  const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
1350  { return __x._M_base() == __y._M_base(); }
1351 
1352  template<typename _Key, typename _Tp, typename _Hash,
1353  typename _Pred, typename _Alloc>
1354  inline bool
1355  operator!=(const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
1356  const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
1357  { return !(__x == __y); }
1358 
1359 } // namespace __debug
1360 } // namespace std
1361 
1362 #endif // C++11
1363 
1364 #endif