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