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