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