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