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