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