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