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_locals();
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 = _RequireAllocator<_Allocator>>
543  unordered_set(_InputIterator, _InputIterator,
544  unordered_set<int>::size_type = {},
545  _Hash = _Hash(), _Pred = _Pred(), _Allocator = _Allocator())
546  -> unordered_set<typename iterator_traits<_InputIterator>::value_type,
547  _Hash, _Pred, _Allocator>;
548 
549  template<typename _Tp, typename _Hash = hash<_Tp>,
550  typename _Pred = equal_to<_Tp>,
551  typename _Allocator = allocator<_Tp>,
552  typename = _RequireAllocator<_Allocator>>
553  unordered_set(initializer_list<_Tp>,
554  unordered_set<int>::size_type = {},
555  _Hash = _Hash(), _Pred = _Pred(), _Allocator = _Allocator())
556  -> unordered_set<_Tp, _Hash, _Pred, _Allocator>;
557 
558  template<typename _InputIterator, typename _Allocator,
559  typename = _RequireInputIter<_InputIterator>,
560  typename = _RequireAllocator<_Allocator>>
561  unordered_set(_InputIterator, _InputIterator,
562  unordered_set<int>::size_type, _Allocator)
563  -> unordered_set<typename iterator_traits<_InputIterator>::value_type,
564  hash<
565  typename iterator_traits<_InputIterator>::value_type>,
566  equal_to<
567  typename iterator_traits<_InputIterator>::value_type>,
568  _Allocator>;
569 
570  template<typename _InputIterator, typename _Hash, typename _Allocator,
571  typename = _RequireInputIter<_InputIterator>,
572  typename = _RequireAllocator<_Allocator>>
573  unordered_set(_InputIterator, _InputIterator,
574  unordered_set<int>::size_type,
575  _Hash, _Allocator)
576  -> unordered_set<typename iterator_traits<_InputIterator>::value_type,
577  _Hash,
578  equal_to<
579  typename iterator_traits<_InputIterator>::value_type>,
580  _Allocator>;
581 
582  template<typename _Tp, typename _Allocator,
583  typename = _RequireAllocator<_Allocator>>
584  unordered_set(initializer_list<_Tp>,
585  unordered_set<int>::size_type, _Allocator)
586  -> unordered_set<_Tp, hash<_Tp>, equal_to<_Tp>, _Allocator>;
587 
588  template<typename _Tp, typename _Hash, typename _Allocator,
589  typename = _RequireAllocator<_Allocator>>
590  unordered_set(initializer_list<_Tp>,
591  unordered_set<int>::size_type, _Hash, _Allocator)
592  -> unordered_set<_Tp, _Hash, equal_to<_Tp>, _Allocator>;
593 
594 #endif
595 
596  template<typename _Value, typename _Hash, typename _Pred, typename _Alloc>
597  inline void
598  swap(unordered_set<_Value, _Hash, _Pred, _Alloc>& __x,
599  unordered_set<_Value, _Hash, _Pred, _Alloc>& __y)
600  noexcept(noexcept(__x.swap(__y)))
601  { __x.swap(__y); }
602 
603  template<typename _Value, typename _Hash, typename _Pred, typename _Alloc>
604  inline bool
605  operator==(const unordered_set<_Value, _Hash, _Pred, _Alloc>& __x,
606  const unordered_set<_Value, _Hash, _Pred, _Alloc>& __y)
607  { return __x._M_base() == __y._M_base(); }
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 == __y); }
614 
615 
616  /// Class std::unordered_multiset with safety/checking/debug instrumentation.
617  template<typename _Value,
618  typename _Hash = std::hash<_Value>,
619  typename _Pred = std::equal_to<_Value>,
620  typename _Alloc = std::allocator<_Value> >
621  class unordered_multiset
622  : public __gnu_debug::_Safe_container<
623  unordered_multiset<_Value, _Hash, _Pred, _Alloc>, _Alloc,
624  __gnu_debug::_Safe_unordered_container>,
625  public _GLIBCXX_STD_C::unordered_multiset<_Value, _Hash, _Pred, _Alloc>
626  {
627  typedef _GLIBCXX_STD_C::unordered_multiset<
628  _Value, _Hash, _Pred, _Alloc> _Base;
629  typedef __gnu_debug::_Safe_container<unordered_multiset,
630  _Alloc, __gnu_debug::_Safe_unordered_container> _Safe;
631  typedef typename _Base::const_iterator _Base_const_iterator;
632  typedef typename _Base::iterator _Base_iterator;
633  typedef typename _Base::const_local_iterator
634  _Base_const_local_iterator;
635  typedef typename _Base::local_iterator _Base_local_iterator;
636 
637  template<typename _ItT, typename _SeqT, typename _CatT>
638  friend class ::__gnu_debug::_Safe_iterator;
639  template<typename _ItT, typename _SeqT>
640  friend class ::__gnu_debug::_Safe_local_iterator;
641 
642  public:
643  typedef typename _Base::size_type size_type;
644  typedef typename _Base::hasher hasher;
645  typedef typename _Base::key_equal key_equal;
646  typedef typename _Base::allocator_type allocator_type;
647 
648  typedef typename _Base::key_type key_type;
649  typedef typename _Base::value_type value_type;
650 
651  typedef __gnu_debug::_Safe_iterator<
652  _Base_iterator, unordered_multiset> iterator;
653  typedef __gnu_debug::_Safe_iterator<
654  _Base_const_iterator, unordered_multiset> const_iterator;
655  typedef __gnu_debug::_Safe_local_iterator<
656  _Base_local_iterator, unordered_multiset> local_iterator;
657  typedef __gnu_debug::_Safe_local_iterator<
658  _Base_const_local_iterator, unordered_multiset> const_local_iterator;
659 
660  unordered_multiset() = default;
661 
662  explicit
663  unordered_multiset(size_type __n,
664  const hasher& __hf = hasher(),
665  const key_equal& __eql = key_equal(),
666  const allocator_type& __a = allocator_type())
667  : _Base(__n, __hf, __eql, __a) { }
668 
669  template<typename _InputIterator>
670  unordered_multiset(_InputIterator __first, _InputIterator __last,
671  size_type __n = 0,
672  const hasher& __hf = hasher(),
673  const key_equal& __eql = key_equal(),
674  const allocator_type& __a = allocator_type())
675  : _Base(__gnu_debug::__base(
676  __glibcxx_check_valid_constructor_range(__first, __last)),
677  __gnu_debug::__base(__last), __n,
678  __hf, __eql, __a) { }
679 
680  unordered_multiset(const unordered_multiset&) = default;
681 
682  unordered_multiset(const _Base& __x)
683  : _Base(__x) { }
684 
685  unordered_multiset(unordered_multiset&&) = default;
686 
687  explicit
688  unordered_multiset(const allocator_type& __a)
689  : _Base(__a) { }
690 
691  unordered_multiset(const unordered_multiset& __uset,
692  const allocator_type& __a)
693  : _Base(__uset, __a) { }
694 
695  unordered_multiset(unordered_multiset&& __uset,
696  const allocator_type& __a)
697  : _Safe(std::move(__uset._M_safe()), __a),
698  _Base(std::move(__uset._M_base()), __a) { }
699 
700  unordered_multiset(initializer_list<value_type> __l,
701  size_type __n = 0,
702  const hasher& __hf = hasher(),
703  const key_equal& __eql = key_equal(),
704  const allocator_type& __a = allocator_type())
705  : _Base(__l, __n, __hf, __eql, __a) { }
706 
707  unordered_multiset(size_type __n, const allocator_type& __a)
708  : unordered_multiset(__n, hasher(), key_equal(), __a)
709  { }
710 
711  unordered_multiset(size_type __n, const hasher& __hf,
712  const allocator_type& __a)
713  : unordered_multiset(__n, __hf, key_equal(), __a)
714  { }
715 
716  template<typename _InputIterator>
717  unordered_multiset(_InputIterator __first, _InputIterator __last,
718  size_type __n,
719  const allocator_type& __a)
720  : unordered_multiset(__first, __last, __n, hasher(), key_equal(), __a)
721  { }
722 
723  template<typename _InputIterator>
724  unordered_multiset(_InputIterator __first, _InputIterator __last,
725  size_type __n, const hasher& __hf,
726  const allocator_type& __a)
727  : unordered_multiset(__first, __last, __n, __hf, key_equal(), __a)
728  { }
729 
730  unordered_multiset(initializer_list<value_type> __l,
731  size_type __n,
732  const allocator_type& __a)
733  : unordered_multiset(__l, __n, hasher(), key_equal(), __a)
734  { }
735 
736  unordered_multiset(initializer_list<value_type> __l,
737  size_type __n, const hasher& __hf,
738  const allocator_type& __a)
739  : unordered_multiset(__l, __n, __hf, key_equal(), __a)
740  { }
741 
742  ~unordered_multiset() = default;
743 
744  unordered_multiset&
745  operator=(const unordered_multiset&) = default;
746 
747  unordered_multiset&
748  operator=(unordered_multiset&&) = default;
749 
750  unordered_multiset&
751  operator=(initializer_list<value_type> __l)
752  {
753  this->_M_base() = __l;
754  this->_M_invalidate_all();
755  return *this;
756  }
757 
758  void
759  swap(unordered_multiset& __x)
760  noexcept( noexcept(declval<_Base&>().swap(__x)) )
761  {
762  _Safe::_M_swap(__x);
763  _Base::swap(__x);
764  }
765 
766  void
767  clear() noexcept
768  {
769  _Base::clear();
770  this->_M_invalidate_all();
771  }
772 
773  iterator
774  begin() noexcept
775  { return { _Base::begin(), this }; }
776 
777  const_iterator
778  begin() const noexcept
779  { return { _Base::begin(), this }; }
780 
781  iterator
782  end() noexcept
783  { return { _Base::end(), this }; }
784 
785  const_iterator
786  end() const noexcept
787  { return { _Base::end(), this }; }
788 
789  const_iterator
790  cbegin() const noexcept
791  { return { _Base::cbegin(), this }; }
792 
793  const_iterator
794  cend() const noexcept
795  { return { _Base::cend(), this }; }
796 
797  // local versions
798  local_iterator
799  begin(size_type __b)
800  {
801  __glibcxx_check_bucket_index(__b);
802  return { _Base::begin(__b), this };
803  }
804 
805  local_iterator
806  end(size_type __b)
807  {
808  __glibcxx_check_bucket_index(__b);
809  return { _Base::end(__b), this };
810  }
811 
812  const_local_iterator
813  begin(size_type __b) const
814  {
815  __glibcxx_check_bucket_index(__b);
816  return { _Base::begin(__b), this };
817  }
818 
819  const_local_iterator
820  end(size_type __b) const
821  {
822  __glibcxx_check_bucket_index(__b);
823  return { _Base::end(__b), this };
824  }
825 
826  const_local_iterator
827  cbegin(size_type __b) const
828  {
829  __glibcxx_check_bucket_index(__b);
830  return { _Base::cbegin(__b), this };
831  }
832 
833  const_local_iterator
834  cend(size_type __b) const
835  {
836  __glibcxx_check_bucket_index(__b);
837  return { _Base::cend(__b), this };
838  }
839 
840  size_type
841  bucket_size(size_type __b) const
842  {
843  __glibcxx_check_bucket_index(__b);
844  return _Base::bucket_size(__b);
845  }
846 
847  float
848  max_load_factor() const noexcept
849  { return _Base::max_load_factor(); }
850 
851  void
852  max_load_factor(float __f)
853  {
854  __glibcxx_check_max_load_factor(__f);
855  _Base::max_load_factor(__f);
856  }
857 
858  template<typename... _Args>
859  iterator
860  emplace(_Args&&... __args)
861  {
862  size_type __bucket_count = this->bucket_count();
863  auto __it = _Base::emplace(std::forward<_Args>(__args)...);
864  _M_check_rehashed(__bucket_count);
865  return { __it, this };
866  }
867 
868  template<typename... _Args>
869  iterator
870  emplace_hint(const_iterator __hint, _Args&&... __args)
871  {
872  __glibcxx_check_insert(__hint);
873  size_type __bucket_count = this->bucket_count();
874  auto __it = _Base::emplace_hint(__hint.base(),
875  std::forward<_Args>(__args)...);
876  _M_check_rehashed(__bucket_count);
877  return { __it, this };
878  }
879 
880  iterator
881  insert(const value_type& __obj)
882  {
883  size_type __bucket_count = this->bucket_count();
884  auto __it = _Base::insert(__obj);
885  _M_check_rehashed(__bucket_count);
886  return { __it, this };
887  }
888 
889  iterator
890  insert(const_iterator __hint, const value_type& __obj)
891  {
892  __glibcxx_check_insert(__hint);
893  size_type __bucket_count = this->bucket_count();
894  auto __it = _Base::insert(__hint.base(), __obj);
895  _M_check_rehashed(__bucket_count);
896  return { __it, this };
897  }
898 
899  iterator
900  insert(value_type&& __obj)
901  {
902  size_type __bucket_count = this->bucket_count();
903  auto __it = _Base::insert(std::move(__obj));
904  _M_check_rehashed(__bucket_count);
905  return { __it, this };
906  }
907 
908  iterator
909  insert(const_iterator __hint, value_type&& __obj)
910  {
911  __glibcxx_check_insert(__hint);
912  size_type __bucket_count = this->bucket_count();
913  auto __it = _Base::insert(__hint.base(), std::move(__obj));
914  _M_check_rehashed(__bucket_count);
915  return { __it, this };
916  }
917 
918  void
919  insert(std::initializer_list<value_type> __l)
920  {
921  size_type __bucket_count = this->bucket_count();
922  _Base::insert(__l);
923  _M_check_rehashed(__bucket_count);
924  }
925 
926  template<typename _InputIterator>
927  void
928  insert(_InputIterator __first, _InputIterator __last)
929  {
930  typename __gnu_debug::_Distance_traits<_InputIterator>::__type __dist;
931  __glibcxx_check_valid_range2(__first, __last, __dist);
932  size_type __bucket_count = this->bucket_count();
933 
934  if (__dist.second >= __gnu_debug::__dp_sign)
935  _Base::insert(__gnu_debug::__unsafe(__first),
936  __gnu_debug::__unsafe(__last));
937  else
938  _Base::insert(__first, __last);
939 
940  _M_check_rehashed(__bucket_count);
941  }
942 
943 #if __cplusplus > 201402L
944  using node_type = typename _Base::node_type;
945 
946  node_type
947  extract(const_iterator __position)
948  {
949  __glibcxx_check_erase(__position);
950  return _M_extract(__position.base());
951  }
952 
953  node_type
954  extract(const key_type& __key)
955  {
956  const auto __position = _Base::find(__key);
957  if (__position != _Base::end())
958  return _M_extract(__position);
959  return {};
960  }
961 
962  iterator
963  insert(node_type&& __nh)
964  { return { _Base::insert(std::move(__nh)), this }; }
965 
966  iterator
967  insert(const_iterator __hint, node_type&& __nh)
968  {
969  __glibcxx_check_insert(__hint);
970  return { _Base::insert(__hint.base(), std::move(__nh)), this };
971  }
972 
973  using _Base::merge;
974 #endif // C++17
975 
976  iterator
977  find(const key_type& __key)
978  { return { _Base::find(__key), this }; }
979 
980  const_iterator
981  find(const key_type& __key) const
982  { return { _Base::find(__key), this }; }
983 
984  std::pair<iterator, iterator>
985  equal_range(const key_type& __key)
986  {
987  auto __res = _Base::equal_range(__key);
988  return { { __res.first, this }, { __res.second, this } };
989  }
990 
991  std::pair<const_iterator, const_iterator>
992  equal_range(const key_type& __key) const
993  {
994  auto __res = _Base::equal_range(__key);
995  return { { __res.first, this }, { __res.second, this } };
996  }
997 
998  size_type
999  erase(const key_type& __key)
1000  {
1001  size_type __ret(0);
1002  auto __pair = _Base::equal_range(__key);
1003  for (auto __victim = __pair.first; __victim != __pair.second;)
1004  {
1005  _M_invalidate(__victim);
1006  __victim = _Base::erase(__victim);
1007  ++__ret;
1008  }
1009 
1010  return __ret;
1011  }
1012 
1013  iterator
1014  erase(const_iterator __it)
1015  {
1016  __glibcxx_check_erase(__it);
1017  return { _M_erase(__it.base()), this };
1018  }
1019 
1020  iterator
1021  erase(iterator __it)
1022  {
1023  __glibcxx_check_erase(__it);
1024  return { _M_erase(__it.base()), this };
1025  }
1026 
1027  iterator
1028  erase(const_iterator __first, const_iterator __last)
1029  {
1030  __glibcxx_check_erase_range(__first, __last);
1031  for (auto __tmp = __first.base(); __tmp != __last.base(); ++__tmp)
1032  {
1033  _GLIBCXX_DEBUG_VERIFY(__tmp != _Base::cend(),
1034  _M_message(__gnu_debug::__msg_valid_range)
1035  ._M_iterator(__first, "first")
1036  ._M_iterator(__last, "last"));
1037  _M_invalidate(__tmp);
1038  }
1039  return { _Base::erase(__first.base(), __last.base()), this };
1040  }
1041 
1042  _Base&
1043  _M_base() noexcept { return *this; }
1044 
1045  const _Base&
1046  _M_base() const noexcept { return *this; }
1047 
1048  private:
1049  void
1050  _M_check_rehashed(size_type __prev_count)
1051  {
1052  if (__prev_count != this->bucket_count())
1053  this->_M_invalidate_locals();
1054  }
1055 
1056  void
1057  _M_invalidate(_Base_const_iterator __victim)
1058  {
1059  this->_M_invalidate_if(
1060  [__victim](_Base_const_iterator __it) { return __it == __victim; });
1061  this->_M_invalidate_local_if(
1062  [__victim](_Base_const_local_iterator __it)
1063  { return __it._M_curr() == __victim._M_cur; });
1064  }
1065 
1066  _Base_iterator
1067  _M_erase(_Base_const_iterator __victim)
1068  {
1069  _M_invalidate(__victim);
1070  size_type __bucket_count = this->bucket_count();
1071  _Base_iterator __next = _Base::erase(__victim);
1072  _M_check_rehashed(__bucket_count);
1073  return __next;
1074  }
1075 
1076 #if __cplusplus > 201402L
1077  node_type
1078  _M_extract(_Base_const_iterator __victim)
1079  {
1080  _M_invalidate(__victim);
1081  return _Base::extract(__victim);
1082  }
1083 #endif
1084  };
1085 
1086 #if __cpp_deduction_guides >= 201606
1087 
1088  template<typename _InputIterator,
1089  typename _Hash =
1090  hash<typename iterator_traits<_InputIterator>::value_type>,
1091  typename _Pred =
1092  equal_to<typename iterator_traits<_InputIterator>::value_type>,
1093  typename _Allocator =
1094  allocator<typename iterator_traits<_InputIterator>::value_type>,
1095  typename = _RequireInputIter<_InputIterator>,
1096  typename = _RequireAllocator<_Allocator>>
1097  unordered_multiset(_InputIterator, _InputIterator,
1098  unordered_multiset<int>::size_type = {},
1099  _Hash = _Hash(), _Pred = _Pred(),
1100  _Allocator = _Allocator())
1101  -> unordered_multiset<typename iterator_traits<_InputIterator>::value_type,
1102  _Hash, _Pred, _Allocator>;
1103 
1104  template<typename _Tp, typename _Hash = hash<_Tp>,
1105  typename _Pred = equal_to<_Tp>,
1106  typename _Allocator = allocator<_Tp>,
1107  typename = _RequireAllocator<_Allocator>>
1108  unordered_multiset(initializer_list<_Tp>,
1109  unordered_multiset<int>::size_type = {},
1110  _Hash = _Hash(), _Pred = _Pred(),
1111  _Allocator = _Allocator())
1112  -> unordered_multiset<_Tp, _Hash, _Pred, _Allocator>;
1113 
1114  template<typename _InputIterator, typename _Allocator,
1115  typename = _RequireInputIter<_InputIterator>,
1116  typename = _RequireAllocator<_Allocator>>
1117  unordered_multiset(_InputIterator, _InputIterator,
1118  unordered_multiset<int>::size_type, _Allocator)
1119  -> unordered_multiset<typename iterator_traits<_InputIterator>::value_type,
1120  hash<typename
1121  iterator_traits<_InputIterator>::value_type>,
1122  equal_to<typename
1123  iterator_traits<_InputIterator>::value_type>,
1124  _Allocator>;
1125 
1126  template<typename _InputIterator, typename _Hash, typename _Allocator,
1127  typename = _RequireInputIter<_InputIterator>,
1128  typename = _RequireAllocator<_Allocator>>
1129  unordered_multiset(_InputIterator, _InputIterator,
1130  unordered_multiset<int>::size_type,
1131  _Hash, _Allocator)
1132  -> unordered_multiset<typename
1133  iterator_traits<_InputIterator>::value_type,
1134  _Hash,
1135  equal_to<
1136  typename
1137  iterator_traits<_InputIterator>::value_type>,
1138  _Allocator>;
1139 
1140  template<typename _Tp, typename _Allocator,
1141  typename = _RequireAllocator<_Allocator>>
1142  unordered_multiset(initializer_list<_Tp>,
1143  unordered_multiset<int>::size_type, _Allocator)
1144  -> unordered_multiset<_Tp, hash<_Tp>, equal_to<_Tp>, _Allocator>;
1145 
1146  template<typename _Tp, typename _Hash, typename _Allocator,
1147  typename = _RequireAllocator<_Allocator>>
1148  unordered_multiset(initializer_list<_Tp>,
1149  unordered_multiset<int>::size_type, _Hash, _Allocator)
1150  -> unordered_multiset<_Tp, _Hash, equal_to<_Tp>, _Allocator>;
1151 
1152 #endif
1153 
1154  template<typename _Value, typename _Hash, typename _Pred, typename _Alloc>
1155  inline void
1156  swap(unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x,
1157  unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y)
1158  noexcept(noexcept(__x.swap(__y)))
1159  { __x.swap(__y); }
1160 
1161  template<typename _Value, typename _Hash, typename _Pred, typename _Alloc>
1162  inline bool
1163  operator==(const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x,
1164  const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y)
1165  { return __x._M_base() == __y._M_base(); }
1166 
1167  template<typename _Value, typename _Hash, typename _Pred, typename _Alloc>
1168  inline bool
1169  operator!=(const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x,
1170  const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y)
1171  { return !(__x == __y); }
1172 
1173 } // namespace __debug
1174 } // namespace std
1175 
1176 #endif // C++11
1177 
1178 #endif