]>
Commit | Line | Data |
---|---|---|
1 | // Debugging unordered_set/unordered_multiset implementation -*- C++ -*- | |
2 | ||
3 | // Copyright (C) 2003-2024 Free Software Foundation, Inc. | |
4 | // | |
5 | // This file is part of the GNU ISO C++ Library. This library is free | |
6 | // software; you can redistribute it and/or modify it under the | |
7 | // terms of the GNU General Public License as published by the | |
8 | // Free Software Foundation; either version 3, or (at your option) | |
9 | // any later version. | |
10 | ||
11 | // This library is distributed in the hope that it will be useful, | |
12 | // but WITHOUT ANY WARRANTY; without even the implied warranty of | |
13 | // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the | |
14 | // GNU General Public License for more details. | |
15 | ||
16 | // Under Section 7 of GPL version 3, you are granted additional | |
17 | // permissions described in the GCC Runtime Library Exception, version | |
18 | // 3.1, as published by the Free Software Foundation. | |
19 | ||
20 | // You should have received a copy of the GNU General Public License and | |
21 | // a copy of the GCC Runtime Library Exception along with this program; | |
22 | // see the files COPYING3 and COPYING.RUNTIME respectively. If not, see | |
23 | // <http://www.gnu.org/licenses/>. | |
24 | ||
25 | /** @file debug/unordered_set | |
26 | * This file is a GNU debug extension to the Standard C++ Library. | |
27 | */ | |
28 | ||
29 | #ifndef _GLIBCXX_DEBUG_UNORDERED_SET | |
30 | #define _GLIBCXX_DEBUG_UNORDERED_SET 1 | |
31 | ||
32 | #pragma GCC system_header | |
33 | ||
34 | #if __cplusplus < 201103L | |
35 | # include <bits/c++0x_warning.h> | |
36 | #else | |
37 | # include <bits/c++config.h> | |
38 | namespace std _GLIBCXX_VISIBILITY(default) { namespace __debug { | |
39 | template<typename _Key, typename _Hash, typename _Pred, typename _Allocator> | |
40 | class unordered_set; | |
41 | template<typename _Key, typename _Hash, typename _Pred, typename _Allocator> | |
42 | class unordered_multiset; | |
43 | } } // namespace std::__debug | |
44 | # include <unordered_set> | |
45 | ||
46 | #include <debug/safe_unordered_container.h> | |
47 | #include <debug/safe_container.h> | |
48 | #include <debug/safe_iterator.h> | |
49 | #include <debug/safe_local_iterator.h> | |
50 | ||
51 | namespace std _GLIBCXX_VISIBILITY(default) | |
52 | { | |
53 | namespace __debug | |
54 | { | |
55 | /// Class std::unordered_set with safety/checking/debug instrumentation. | |
56 | template<typename _Value, | |
57 | typename _Hash = std::hash<_Value>, | |
58 | typename _Pred = std::equal_to<_Value>, | |
59 | typename _Alloc = std::allocator<_Value> > | |
60 | class unordered_set | |
61 | : public __gnu_debug::_Safe_container< | |
62 | unordered_set<_Value, _Hash, _Pred, _Alloc>, _Alloc, | |
63 | __gnu_debug::_Safe_unordered_container>, | |
64 | public _GLIBCXX_STD_C::unordered_set<_Value, _Hash, _Pred, _Alloc> | |
65 | { | |
66 | typedef _GLIBCXX_STD_C::unordered_set< | |
67 | _Value, _Hash, _Pred, _Alloc> _Base; | |
68 | typedef __gnu_debug::_Safe_container< | |
69 | unordered_set, _Alloc, __gnu_debug::_Safe_unordered_container> _Safe; | |
70 | ||
71 | typedef typename _Base::const_iterator _Base_const_iterator; | |
72 | typedef typename _Base::iterator _Base_iterator; | |
73 | typedef typename _Base::const_local_iterator _Base_const_local_iterator; | |
74 | typedef typename _Base::local_iterator _Base_local_iterator; | |
75 | ||
76 | template<typename _ItT, typename _SeqT, typename _CatT> | |
77 | friend class ::__gnu_debug::_Safe_iterator; | |
78 | template<typename _ItT, typename _SeqT> | |
79 | friend class ::__gnu_debug::_Safe_local_iterator; | |
80 | ||
81 | // 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::difference_type difference_type; | |
92 | typedef typename _Base::hasher hasher; | |
93 | typedef typename _Base::key_equal key_equal; | |
94 | typedef typename _Base::allocator_type allocator_type; | |
95 | ||
96 | typedef typename _Base::key_type key_type; | |
97 | typedef typename _Base::value_type value_type; | |
98 | ||
99 | typedef typename _Base::pointer pointer; | |
100 | typedef typename _Base::const_pointer const_pointer; | |
101 | typedef typename _Base::reference reference; | |
102 | typedef typename _Base::const_reference const_reference; | |
103 | typedef __gnu_debug::_Safe_iterator< | |
104 | _Base_iterator, unordered_set> iterator; | |
105 | typedef __gnu_debug::_Safe_iterator< | |
106 | _Base_const_iterator, unordered_set> const_iterator; | |
107 | typedef __gnu_debug::_Safe_local_iterator< | |
108 | _Base_local_iterator, unordered_set> local_iterator; | |
109 | typedef __gnu_debug::_Safe_local_iterator< | |
110 | _Base_const_local_iterator, unordered_set> const_local_iterator; | |
111 | ||
112 | unordered_set() = default; | |
113 | ||
114 | explicit | |
115 | unordered_set(size_type __n, | |
116 | const hasher& __hf = hasher(), | |
117 | const key_equal& __eql = key_equal(), | |
118 | const allocator_type& __a = allocator_type()) | |
119 | : _Base(__n, __hf, __eql, __a) { } | |
120 | ||
121 | template<typename _InputIterator> | |
122 | unordered_set(_InputIterator __first, _InputIterator __last, | |
123 | size_type __n = 0, | |
124 | const hasher& __hf = hasher(), | |
125 | const key_equal& __eql = key_equal(), | |
126 | const allocator_type& __a = allocator_type()) | |
127 | : _Base(__gnu_debug::__base( | |
128 | __glibcxx_check_valid_constructor_range(__first, __last)), | |
129 | __gnu_debug::__base(__last), __n, | |
130 | __hf, __eql, __a) { } | |
131 | ||
132 | unordered_set(const unordered_set&) = default; | |
133 | ||
134 | unordered_set(_Base_ref __x) | |
135 | : _Base(__x._M_ref) { } | |
136 | ||
137 | unordered_set(unordered_set&&) = default; | |
138 | ||
139 | explicit | |
140 | unordered_set(const allocator_type& __a) | |
141 | : _Base(__a) { } | |
142 | ||
143 | unordered_set(const unordered_set& __uset, | |
144 | const allocator_type& __a) | |
145 | : _Base(__uset, __a) { } | |
146 | ||
147 | unordered_set(unordered_set&& __uset, | |
148 | const allocator_type& __a) | |
149 | noexcept( noexcept(_Base(std::move(__uset), __a)) ) | |
150 | : _Safe(std::move(__uset), __a), | |
151 | _Base(std::move(__uset), __a) { } | |
152 | ||
153 | unordered_set(initializer_list<value_type> __l, | |
154 | size_type __n = 0, | |
155 | const hasher& __hf = hasher(), | |
156 | const key_equal& __eql = key_equal(), | |
157 | const allocator_type& __a = allocator_type()) | |
158 | : _Base(__l, __n, __hf, __eql, __a) { } | |
159 | ||
160 | unordered_set(size_type __n, const allocator_type& __a) | |
161 | : unordered_set(__n, hasher(), key_equal(), __a) | |
162 | { } | |
163 | ||
164 | unordered_set(size_type __n, const hasher& __hf, | |
165 | const allocator_type& __a) | |
166 | : unordered_set(__n, __hf, key_equal(), __a) | |
167 | { } | |
168 | ||
169 | template<typename _InputIterator> | |
170 | unordered_set(_InputIterator __first, _InputIterator __last, | |
171 | size_type __n, | |
172 | const allocator_type& __a) | |
173 | : unordered_set(__first, __last, __n, hasher(), key_equal(), __a) | |
174 | { } | |
175 | ||
176 | template<typename _InputIterator> | |
177 | unordered_set(_InputIterator __first, _InputIterator __last, | |
178 | size_type __n, const hasher& __hf, | |
179 | const allocator_type& __a) | |
180 | : unordered_set(__first, __last, __n, __hf, key_equal(), __a) | |
181 | { } | |
182 | ||
183 | unordered_set(initializer_list<value_type> __l, | |
184 | size_type __n, | |
185 | const allocator_type& __a) | |
186 | : unordered_set(__l, __n, hasher(), key_equal(), __a) | |
187 | { } | |
188 | ||
189 | unordered_set(initializer_list<value_type> __l, | |
190 | size_type __n, const hasher& __hf, | |
191 | const allocator_type& __a) | |
192 | : unordered_set(__l, __n, __hf, key_equal(), __a) | |
193 | { } | |
194 | ||
195 | ~unordered_set() = default; | |
196 | ||
197 | unordered_set& | |
198 | operator=(const unordered_set&) = default; | |
199 | ||
200 | unordered_set& | |
201 | operator=(unordered_set&&) = default; | |
202 | ||
203 | unordered_set& | |
204 | operator=(initializer_list<value_type> __l) | |
205 | { | |
206 | _Base::operator=(__l); | |
207 | this->_M_invalidate_all(); | |
208 | return *this; | |
209 | } | |
210 | ||
211 | using _Base::get_allocator; | |
212 | using _Base::empty; | |
213 | using _Base::size; | |
214 | using _Base::max_size; | |
215 | ||
216 | void | |
217 | swap(unordered_set& __x) | |
218 | noexcept( noexcept(declval<_Base&>().swap(__x)) ) | |
219 | { | |
220 | _Safe::_M_swap(__x); | |
221 | _Base::swap(__x); | |
222 | } | |
223 | ||
224 | void | |
225 | clear() noexcept | |
226 | { | |
227 | _Base::clear(); | |
228 | this->_M_invalidate_all(); | |
229 | } | |
230 | ||
231 | iterator | |
232 | begin() noexcept | |
233 | { return { _Base::begin(), this }; } | |
234 | ||
235 | const_iterator | |
236 | begin() const noexcept | |
237 | { return { _Base::begin(), this }; } | |
238 | ||
239 | iterator | |
240 | end() noexcept | |
241 | { return { _Base::end(), this }; } | |
242 | ||
243 | const_iterator | |
244 | end() const noexcept | |
245 | { return { _Base::end(), this }; } | |
246 | ||
247 | const_iterator | |
248 | cbegin() const noexcept | |
249 | { return { _Base::cbegin(), this }; } | |
250 | ||
251 | const_iterator | |
252 | cend() const noexcept | |
253 | { return { _Base::cend(), this }; } | |
254 | ||
255 | // local versions | |
256 | local_iterator | |
257 | begin(size_type __b) | |
258 | { | |
259 | __glibcxx_check_bucket_index(__b); | |
260 | return { _Base::begin(__b), this }; | |
261 | } | |
262 | ||
263 | local_iterator | |
264 | end(size_type __b) | |
265 | { | |
266 | __glibcxx_check_bucket_index(__b); | |
267 | return { _Base::end(__b), this }; | |
268 | } | |
269 | ||
270 | const_local_iterator | |
271 | begin(size_type __b) const | |
272 | { | |
273 | __glibcxx_check_bucket_index(__b); | |
274 | return { _Base::begin(__b), this }; | |
275 | } | |
276 | ||
277 | const_local_iterator | |
278 | end(size_type __b) const | |
279 | { | |
280 | __glibcxx_check_bucket_index(__b); | |
281 | return { _Base::end(__b), this }; | |
282 | } | |
283 | ||
284 | const_local_iterator | |
285 | cbegin(size_type __b) const | |
286 | { | |
287 | __glibcxx_check_bucket_index(__b); | |
288 | return { _Base::cbegin(__b), this }; | |
289 | } | |
290 | ||
291 | const_local_iterator | |
292 | cend(size_type __b) const | |
293 | { | |
294 | __glibcxx_check_bucket_index(__b); | |
295 | return { _Base::cend(__b), this }; | |
296 | } | |
297 | ||
298 | using _Base::bucket_count; | |
299 | using _Base::max_bucket_count; | |
300 | ||
301 | size_type | |
302 | bucket_size(size_type __b) const | |
303 | { | |
304 | __glibcxx_check_bucket_index(__b); | |
305 | return _Base::bucket_size(__b); | |
306 | } | |
307 | ||
308 | using _Base::bucket; | |
309 | using _Base::load_factor; | |
310 | ||
311 | float | |
312 | max_load_factor() const noexcept | |
313 | { return _Base::max_load_factor(); } | |
314 | ||
315 | void | |
316 | max_load_factor(float __f) | |
317 | { | |
318 | __glibcxx_check_max_load_factor(__f); | |
319 | _Base::max_load_factor(__f); | |
320 | } | |
321 | ||
322 | using _Base::rehash; | |
323 | using _Base::reserve; | |
324 | ||
325 | template<typename... _Args> | |
326 | std::pair<iterator, bool> | |
327 | emplace(_Args&&... __args) | |
328 | { | |
329 | size_type __bucket_count = this->bucket_count(); | |
330 | auto __res = _Base::emplace(std::forward<_Args>(__args)...); | |
331 | _M_check_rehashed(__bucket_count); | |
332 | return { { __res.first, this }, __res.second }; | |
333 | } | |
334 | ||
335 | template<typename... _Args> | |
336 | iterator | |
337 | emplace_hint(const_iterator __hint, _Args&&... __args) | |
338 | { | |
339 | __glibcxx_check_insert(__hint); | |
340 | size_type __bucket_count = this->bucket_count(); | |
341 | auto __it = _Base::emplace_hint(__hint.base(), | |
342 | std::forward<_Args>(__args)...); | |
343 | _M_check_rehashed(__bucket_count); | |
344 | return { __it, this }; | |
345 | } | |
346 | ||
347 | std::pair<iterator, bool> | |
348 | insert(const value_type& __obj) | |
349 | { | |
350 | size_type __bucket_count = this->bucket_count(); | |
351 | auto __res = _Base::insert(__obj); | |
352 | _M_check_rehashed(__bucket_count); | |
353 | return { { __res.first, this }, __res.second }; | |
354 | } | |
355 | ||
356 | iterator | |
357 | insert(const_iterator __hint, const value_type& __obj) | |
358 | { | |
359 | __glibcxx_check_insert(__hint); | |
360 | size_type __bucket_count = this->bucket_count(); | |
361 | auto __it = _Base::insert(__hint.base(), __obj); | |
362 | _M_check_rehashed(__bucket_count); | |
363 | return { __it, this }; | |
364 | } | |
365 | ||
366 | std::pair<iterator, bool> | |
367 | insert(value_type&& __obj) | |
368 | { | |
369 | size_type __bucket_count = this->bucket_count(); | |
370 | auto __res = _Base::insert(std::move(__obj)); | |
371 | _M_check_rehashed(__bucket_count); | |
372 | return { { __res.first, this }, __res.second }; | |
373 | } | |
374 | ||
375 | iterator | |
376 | insert(const_iterator __hint, value_type&& __obj) | |
377 | { | |
378 | __glibcxx_check_insert(__hint); | |
379 | size_type __bucket_count = this->bucket_count(); | |
380 | auto __it = _Base::insert(__hint.base(), std::move(__obj)); | |
381 | _M_check_rehashed(__bucket_count); | |
382 | return { __it, this }; | |
383 | } | |
384 | ||
385 | void | |
386 | insert(std::initializer_list<value_type> __l) | |
387 | { | |
388 | size_type __bucket_count = this->bucket_count(); | |
389 | _Base::insert(__l); | |
390 | _M_check_rehashed(__bucket_count); | |
391 | } | |
392 | ||
393 | template<typename _InputIterator> | |
394 | void | |
395 | insert(_InputIterator __first, _InputIterator __last) | |
396 | { | |
397 | typename __gnu_debug::_Distance_traits<_InputIterator>::__type __dist; | |
398 | __glibcxx_check_valid_range2(__first, __last, __dist); | |
399 | size_type __bucket_count = this->bucket_count(); | |
400 | ||
401 | if (__dist.second >= __gnu_debug::__dp_sign) | |
402 | _Base::insert(__gnu_debug::__unsafe(__first), | |
403 | __gnu_debug::__unsafe(__last)); | |
404 | else | |
405 | _Base::insert(__first, __last); | |
406 | ||
407 | _M_check_rehashed(__bucket_count); | |
408 | } | |
409 | ||
410 | #if __cplusplus > 201402L | |
411 | using node_type = typename _Base::node_type; | |
412 | using insert_return_type = _Node_insert_return<iterator, node_type>; | |
413 | ||
414 | node_type | |
415 | extract(const_iterator __position) | |
416 | { | |
417 | __glibcxx_check_erase(__position); | |
418 | return _M_extract(__position.base()); | |
419 | } | |
420 | ||
421 | node_type | |
422 | extract(const key_type& __key) | |
423 | { | |
424 | const auto __position = _Base::find(__key); | |
425 | if (__position != _Base::end()) | |
426 | return _M_extract(__position); | |
427 | return {}; | |
428 | } | |
429 | ||
430 | insert_return_type | |
431 | insert(node_type&& __nh) | |
432 | { | |
433 | auto __ret = _Base::insert(std::move(__nh)); | |
434 | return | |
435 | { { __ret.position, this }, __ret.inserted, std::move(__ret.node) }; | |
436 | } | |
437 | ||
438 | iterator | |
439 | insert(const_iterator __hint, node_type&& __nh) | |
440 | { | |
441 | __glibcxx_check_insert(__hint); | |
442 | return { _Base::insert(__hint.base(), std::move(__nh)), this }; | |
443 | } | |
444 | ||
445 | template<typename _H2, typename _P2> | |
446 | void | |
447 | merge(unordered_set<_Value, _H2, _P2, _Alloc>& __source) | |
448 | { | |
449 | auto __guard | |
450 | = _Safe::_S_uc_guard(std::__detail::_Identity{}, __source); | |
451 | _Base::merge(__source); | |
452 | } | |
453 | ||
454 | template<typename _H2, typename _P2> | |
455 | void | |
456 | merge(unordered_set<_Value, _H2, _P2, _Alloc>&& __source) | |
457 | { merge(__source); } | |
458 | ||
459 | template<typename _H2, typename _P2> | |
460 | void | |
461 | merge(unordered_multiset<_Value, _H2, _P2, _Alloc>& __source) | |
462 | { | |
463 | auto __guard | |
464 | = _Safe::_S_umc_guard(std::__detail::_Identity{}, __source); | |
465 | _Base::merge(__source); | |
466 | } | |
467 | ||
468 | template<typename _H2, typename _P2> | |
469 | void | |
470 | merge(unordered_multiset<_Value, _H2, _P2, _Alloc>&& __source) | |
471 | { merge(__source); } | |
472 | #endif // C++17 | |
473 | ||
474 | using _Base::hash_function; | |
475 | using _Base::key_eq; | |
476 | ||
477 | iterator | |
478 | find(const key_type& __key) | |
479 | { return { _Base::find(__key), this }; } | |
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 | iterator | |
486 | find(const _Kt& __k) | |
487 | { return { _Base::find(__k), this }; } | |
488 | #endif | |
489 | ||
490 | const_iterator | |
491 | find(const key_type& __key) const | |
492 | { return { _Base::find(__key), this }; } | |
493 | ||
494 | #if __cplusplus > 201703L | |
495 | template<typename _Kt, | |
496 | typename = std::__has_is_transparent_t<_Hash, _Kt>, | |
497 | typename = std::__has_is_transparent_t<_Pred, _Kt>> | |
498 | const_iterator | |
499 | find(const _Kt& __k) const | |
500 | { return { _Base::find(__k), this }; } | |
501 | #endif | |
502 | ||
503 | using _Base::count; | |
504 | ||
505 | #if __cplusplus > 201703L | |
506 | using _Base::contains; | |
507 | #endif | |
508 | ||
509 | std::pair<iterator, iterator> | |
510 | equal_range(const key_type& __key) | |
511 | { | |
512 | auto __res = _Base::equal_range(__key); | |
513 | return { { __res.first, this }, { __res.second, this } }; | |
514 | } | |
515 | ||
516 | #if __cplusplus > 201703L | |
517 | template<typename _Kt, | |
518 | typename = std::__has_is_transparent_t<_Hash, _Kt>, | |
519 | typename = std::__has_is_transparent_t<_Pred, _Kt>> | |
520 | std::pair<iterator, iterator> | |
521 | equal_range(const _Kt& __k) | |
522 | { | |
523 | auto __res = _Base::equal_range(__k); | |
524 | return { { __res.first, this }, { __res.second, this } }; | |
525 | } | |
526 | #endif | |
527 | ||
528 | std::pair<const_iterator, const_iterator> | |
529 | equal_range(const key_type& __key) const | |
530 | { | |
531 | auto __res = _Base::equal_range(__key); | |
532 | return { { __res.first, this }, { __res.second, this } }; | |
533 | } | |
534 | ||
535 | #if __cplusplus > 201703L | |
536 | template<typename _Kt, | |
537 | typename = std::__has_is_transparent_t<_Hash, _Kt>, | |
538 | typename = std::__has_is_transparent_t<_Pred, _Kt>> | |
539 | std::pair<const_iterator, const_iterator> | |
540 | equal_range(const _Kt& __k) const | |
541 | { | |
542 | auto __res = _Base::equal_range(__k); | |
543 | return { { __res.first, this }, { __res.second, this } }; | |
544 | } | |
545 | #endif | |
546 | ||
547 | size_type | |
548 | erase(const key_type& __key) | |
549 | { | |
550 | size_type __ret(0); | |
551 | auto __victim = _Base::find(__key); | |
552 | if (__victim != _Base::end()) | |
553 | { | |
554 | _M_erase(__victim); | |
555 | __ret = 1; | |
556 | } | |
557 | return __ret; | |
558 | } | |
559 | ||
560 | iterator | |
561 | erase(const_iterator __it) | |
562 | { | |
563 | __glibcxx_check_erase(__it); | |
564 | return { _M_erase(__it.base()), this }; | |
565 | } | |
566 | ||
567 | _Base_iterator | |
568 | erase(_Base_const_iterator __it) | |
569 | { | |
570 | __glibcxx_check_erase2(__it); | |
571 | return _M_erase(__it); | |
572 | } | |
573 | ||
574 | iterator | |
575 | erase(iterator __it) | |
576 | { | |
577 | __glibcxx_check_erase(__it); | |
578 | return { _M_erase(__it.base()), this }; | |
579 | } | |
580 | ||
581 | iterator | |
582 | erase(const_iterator __first, const_iterator __last) | |
583 | { | |
584 | __glibcxx_check_erase_range(__first, __last); | |
585 | for (auto __tmp = __first.base(); __tmp != __last.base(); ++__tmp) | |
586 | { | |
587 | _GLIBCXX_DEBUG_VERIFY(__tmp != _Base::cend(), | |
588 | _M_message(__gnu_debug::__msg_valid_range) | |
589 | ._M_iterator(__first, "first") | |
590 | ._M_iterator(__last, "last")); | |
591 | _M_invalidate(__tmp); | |
592 | } | |
593 | ||
594 | size_type __bucket_count = this->bucket_count(); | |
595 | auto __next = _Base::erase(__first.base(), __last.base()); | |
596 | _M_check_rehashed(__bucket_count); | |
597 | return { __next, this }; | |
598 | } | |
599 | ||
600 | _Base& | |
601 | _M_base() noexcept { return *this; } | |
602 | ||
603 | const _Base& | |
604 | _M_base() const noexcept { return *this; } | |
605 | ||
606 | private: | |
607 | void | |
608 | _M_check_rehashed(size_type __prev_count) | |
609 | { | |
610 | if (__prev_count != this->bucket_count()) | |
611 | this->_M_invalidate_all(); | |
612 | } | |
613 | ||
614 | void | |
615 | _M_invalidate(_Base_const_iterator __victim) | |
616 | { | |
617 | this->_M_invalidate_if( | |
618 | [__victim](_Base_const_iterator __it) { return __it == __victim; }); | |
619 | this->_M_invalidate_local_if( | |
620 | [__victim](_Base_const_local_iterator __it) | |
621 | { return __it == __victim; }); | |
622 | } | |
623 | ||
624 | _Base_iterator | |
625 | _M_erase(_Base_const_iterator __victim) | |
626 | { | |
627 | _M_invalidate(__victim); | |
628 | size_type __bucket_count = this->bucket_count(); | |
629 | _Base_iterator __next = _Base::erase(__victim); | |
630 | _M_check_rehashed(__bucket_count); | |
631 | return __next; | |
632 | } | |
633 | ||
634 | #if __cplusplus > 201402L | |
635 | node_type | |
636 | _M_extract(_Base_const_iterator __victim) | |
637 | { | |
638 | _M_invalidate(__victim); | |
639 | return _Base::extract(__victim); | |
640 | } | |
641 | #endif | |
642 | }; | |
643 | ||
644 | #if __cpp_deduction_guides >= 201606 | |
645 | ||
646 | template<typename _InputIterator, | |
647 | typename _Hash = | |
648 | hash<typename iterator_traits<_InputIterator>::value_type>, | |
649 | typename _Pred = | |
650 | equal_to<typename iterator_traits<_InputIterator>::value_type>, | |
651 | typename _Allocator = | |
652 | allocator<typename iterator_traits<_InputIterator>::value_type>, | |
653 | typename = _RequireInputIter<_InputIterator>, | |
654 | typename = _RequireNotAllocatorOrIntegral<_Hash>, | |
655 | typename = _RequireNotAllocator<_Pred>, | |
656 | typename = _RequireAllocator<_Allocator>> | |
657 | unordered_set(_InputIterator, _InputIterator, | |
658 | unordered_set<int>::size_type = {}, | |
659 | _Hash = _Hash(), _Pred = _Pred(), _Allocator = _Allocator()) | |
660 | -> unordered_set<typename iterator_traits<_InputIterator>::value_type, | |
661 | _Hash, _Pred, _Allocator>; | |
662 | ||
663 | template<typename _Tp, typename _Hash = hash<_Tp>, | |
664 | typename _Pred = equal_to<_Tp>, | |
665 | typename _Allocator = allocator<_Tp>, | |
666 | typename = _RequireNotAllocatorOrIntegral<_Hash>, | |
667 | typename = _RequireNotAllocator<_Pred>, | |
668 | typename = _RequireAllocator<_Allocator>> | |
669 | unordered_set(initializer_list<_Tp>, | |
670 | unordered_set<int>::size_type = {}, | |
671 | _Hash = _Hash(), _Pred = _Pred(), _Allocator = _Allocator()) | |
672 | -> unordered_set<_Tp, _Hash, _Pred, _Allocator>; | |
673 | ||
674 | template<typename _InputIterator, typename _Allocator, | |
675 | typename = _RequireInputIter<_InputIterator>, | |
676 | typename = _RequireAllocator<_Allocator>> | |
677 | unordered_set(_InputIterator, _InputIterator, | |
678 | unordered_set<int>::size_type, _Allocator) | |
679 | -> unordered_set<typename iterator_traits<_InputIterator>::value_type, | |
680 | hash< | |
681 | typename iterator_traits<_InputIterator>::value_type>, | |
682 | equal_to< | |
683 | typename iterator_traits<_InputIterator>::value_type>, | |
684 | _Allocator>; | |
685 | ||
686 | template<typename _InputIterator, typename _Hash, typename _Allocator, | |
687 | typename = _RequireInputIter<_InputIterator>, | |
688 | typename = _RequireNotAllocatorOrIntegral<_Hash>, | |
689 | typename = _RequireAllocator<_Allocator>> | |
690 | unordered_set(_InputIterator, _InputIterator, | |
691 | unordered_set<int>::size_type, | |
692 | _Hash, _Allocator) | |
693 | -> unordered_set<typename iterator_traits<_InputIterator>::value_type, | |
694 | _Hash, | |
695 | equal_to< | |
696 | typename iterator_traits<_InputIterator>::value_type>, | |
697 | _Allocator>; | |
698 | ||
699 | template<typename _Tp, typename _Allocator, | |
700 | typename = _RequireAllocator<_Allocator>> | |
701 | unordered_set(initializer_list<_Tp>, | |
702 | unordered_set<int>::size_type, _Allocator) | |
703 | -> unordered_set<_Tp, hash<_Tp>, equal_to<_Tp>, _Allocator>; | |
704 | ||
705 | template<typename _Tp, typename _Hash, typename _Allocator, | |
706 | typename = _RequireNotAllocatorOrIntegral<_Hash>, | |
707 | typename = _RequireAllocator<_Allocator>> | |
708 | unordered_set(initializer_list<_Tp>, | |
709 | unordered_set<int>::size_type, _Hash, _Allocator) | |
710 | -> unordered_set<_Tp, _Hash, equal_to<_Tp>, _Allocator>; | |
711 | ||
712 | #endif | |
713 | ||
714 | template<typename _Value, typename _Hash, typename _Pred, typename _Alloc> | |
715 | inline void | |
716 | swap(unordered_set<_Value, _Hash, _Pred, _Alloc>& __x, | |
717 | unordered_set<_Value, _Hash, _Pred, _Alloc>& __y) | |
718 | noexcept(noexcept(__x.swap(__y))) | |
719 | { __x.swap(__y); } | |
720 | ||
721 | template<typename _Value, typename _Hash, typename _Pred, typename _Alloc> | |
722 | inline bool | |
723 | operator==(const unordered_set<_Value, _Hash, _Pred, _Alloc>& __x, | |
724 | const unordered_set<_Value, _Hash, _Pred, _Alloc>& __y) | |
725 | { return __x._M_base() == __y._M_base(); } | |
726 | ||
727 | #if __cpp_impl_three_way_comparison < 201907L | |
728 | template<typename _Value, typename _Hash, typename _Pred, typename _Alloc> | |
729 | inline bool | |
730 | operator!=(const unordered_set<_Value, _Hash, _Pred, _Alloc>& __x, | |
731 | const unordered_set<_Value, _Hash, _Pred, _Alloc>& __y) | |
732 | { return !(__x == __y); } | |
733 | #endif | |
734 | ||
735 | /// Class std::unordered_multiset with safety/checking/debug instrumentation. | |
736 | template<typename _Value, | |
737 | typename _Hash = std::hash<_Value>, | |
738 | typename _Pred = std::equal_to<_Value>, | |
739 | typename _Alloc = std::allocator<_Value> > | |
740 | class unordered_multiset | |
741 | : public __gnu_debug::_Safe_container< | |
742 | unordered_multiset<_Value, _Hash, _Pred, _Alloc>, _Alloc, | |
743 | __gnu_debug::_Safe_unordered_container>, | |
744 | public _GLIBCXX_STD_C::unordered_multiset<_Value, _Hash, _Pred, _Alloc> | |
745 | { | |
746 | typedef _GLIBCXX_STD_C::unordered_multiset< | |
747 | _Value, _Hash, _Pred, _Alloc> _Base; | |
748 | typedef __gnu_debug::_Safe_container<unordered_multiset, | |
749 | _Alloc, __gnu_debug::_Safe_unordered_container> _Safe; | |
750 | typedef typename _Base::const_iterator _Base_const_iterator; | |
751 | typedef typename _Base::iterator _Base_iterator; | |
752 | typedef typename _Base::const_local_iterator | |
753 | _Base_const_local_iterator; | |
754 | typedef typename _Base::local_iterator _Base_local_iterator; | |
755 | ||
756 | template<typename _ItT, typename _SeqT, typename _CatT> | |
757 | friend class ::__gnu_debug::_Safe_iterator; | |
758 | template<typename _ItT, typename _SeqT> | |
759 | friend class ::__gnu_debug::_Safe_local_iterator; | |
760 | ||
761 | // Reference wrapper for base class. See PR libstdc++/90102. | |
762 | struct _Base_ref | |
763 | { | |
764 | _Base_ref(const _Base& __r) : _M_ref(__r) { } | |
765 | ||
766 | const _Base& _M_ref; | |
767 | }; | |
768 | ||
769 | public: | |
770 | typedef typename _Base::size_type size_type; | |
771 | typedef typename _Base::difference_type difference_type; | |
772 | typedef typename _Base::hasher hasher; | |
773 | typedef typename _Base::key_equal key_equal; | |
774 | typedef typename _Base::allocator_type allocator_type; | |
775 | ||
776 | typedef typename _Base::key_type key_type; | |
777 | typedef typename _Base::value_type value_type; | |
778 | ||
779 | typedef typename _Base::pointer pointer; | |
780 | typedef typename _Base::const_pointer const_pointer; | |
781 | typedef typename _Base::reference reference; | |
782 | typedef typename _Base::const_reference const_reference; | |
783 | typedef __gnu_debug::_Safe_iterator< | |
784 | _Base_iterator, unordered_multiset> iterator; | |
785 | typedef __gnu_debug::_Safe_iterator< | |
786 | _Base_const_iterator, unordered_multiset> const_iterator; | |
787 | typedef __gnu_debug::_Safe_local_iterator< | |
788 | _Base_local_iterator, unordered_multiset> local_iterator; | |
789 | typedef __gnu_debug::_Safe_local_iterator< | |
790 | _Base_const_local_iterator, unordered_multiset> const_local_iterator; | |
791 | ||
792 | unordered_multiset() = default; | |
793 | ||
794 | explicit | |
795 | unordered_multiset(size_type __n, | |
796 | const hasher& __hf = hasher(), | |
797 | const key_equal& __eql = key_equal(), | |
798 | const allocator_type& __a = allocator_type()) | |
799 | : _Base(__n, __hf, __eql, __a) { } | |
800 | ||
801 | template<typename _InputIterator> | |
802 | unordered_multiset(_InputIterator __first, _InputIterator __last, | |
803 | size_type __n = 0, | |
804 | const hasher& __hf = hasher(), | |
805 | const key_equal& __eql = key_equal(), | |
806 | const allocator_type& __a = allocator_type()) | |
807 | : _Base(__gnu_debug::__base( | |
808 | __glibcxx_check_valid_constructor_range(__first, __last)), | |
809 | __gnu_debug::__base(__last), __n, | |
810 | __hf, __eql, __a) { } | |
811 | ||
812 | unordered_multiset(const unordered_multiset&) = default; | |
813 | ||
814 | unordered_multiset(_Base_ref __x) | |
815 | : _Base(__x._M_ref) { } | |
816 | ||
817 | unordered_multiset(unordered_multiset&&) = default; | |
818 | ||
819 | explicit | |
820 | unordered_multiset(const allocator_type& __a) | |
821 | : _Base(__a) { } | |
822 | ||
823 | unordered_multiset(const unordered_multiset& __uset, | |
824 | const allocator_type& __a) | |
825 | : _Base(__uset, __a) { } | |
826 | ||
827 | unordered_multiset(unordered_multiset&& __uset, | |
828 | const allocator_type& __a) | |
829 | noexcept( noexcept(_Base(std::move(__uset), __a)) ) | |
830 | : _Safe(std::move(__uset), __a), | |
831 | _Base(std::move(__uset), __a) { } | |
832 | ||
833 | unordered_multiset(initializer_list<value_type> __l, | |
834 | size_type __n = 0, | |
835 | const hasher& __hf = hasher(), | |
836 | const key_equal& __eql = key_equal(), | |
837 | const allocator_type& __a = allocator_type()) | |
838 | : _Base(__l, __n, __hf, __eql, __a) { } | |
839 | ||
840 | unordered_multiset(size_type __n, const allocator_type& __a) | |
841 | : unordered_multiset(__n, hasher(), key_equal(), __a) | |
842 | { } | |
843 | ||
844 | unordered_multiset(size_type __n, const hasher& __hf, | |
845 | const allocator_type& __a) | |
846 | : unordered_multiset(__n, __hf, key_equal(), __a) | |
847 | { } | |
848 | ||
849 | template<typename _InputIterator> | |
850 | unordered_multiset(_InputIterator __first, _InputIterator __last, | |
851 | size_type __n, | |
852 | const allocator_type& __a) | |
853 | : unordered_multiset(__first, __last, __n, hasher(), key_equal(), __a) | |
854 | { } | |
855 | ||
856 | template<typename _InputIterator> | |
857 | unordered_multiset(_InputIterator __first, _InputIterator __last, | |
858 | size_type __n, const hasher& __hf, | |
859 | const allocator_type& __a) | |
860 | : unordered_multiset(__first, __last, __n, __hf, key_equal(), __a) | |
861 | { } | |
862 | ||
863 | unordered_multiset(initializer_list<value_type> __l, | |
864 | size_type __n, | |
865 | const allocator_type& __a) | |
866 | : unordered_multiset(__l, __n, hasher(), key_equal(), __a) | |
867 | { } | |
868 | ||
869 | unordered_multiset(initializer_list<value_type> __l, | |
870 | size_type __n, const hasher& __hf, | |
871 | const allocator_type& __a) | |
872 | : unordered_multiset(__l, __n, __hf, key_equal(), __a) | |
873 | { } | |
874 | ||
875 | ~unordered_multiset() = default; | |
876 | ||
877 | unordered_multiset& | |
878 | operator=(const unordered_multiset&) = default; | |
879 | ||
880 | unordered_multiset& | |
881 | operator=(unordered_multiset&&) = default; | |
882 | ||
883 | unordered_multiset& | |
884 | operator=(initializer_list<value_type> __l) | |
885 | { | |
886 | _Base::operator=(__l); | |
887 | this->_M_invalidate_all(); | |
888 | return *this; | |
889 | } | |
890 | ||
891 | using _Base::get_allocator; | |
892 | using _Base::empty; | |
893 | using _Base::size; | |
894 | using _Base::max_size; | |
895 | ||
896 | void | |
897 | swap(unordered_multiset& __x) | |
898 | noexcept( noexcept(declval<_Base&>().swap(__x)) ) | |
899 | { | |
900 | _Safe::_M_swap(__x); | |
901 | _Base::swap(__x); | |
902 | } | |
903 | ||
904 | void | |
905 | clear() noexcept | |
906 | { | |
907 | _Base::clear(); | |
908 | this->_M_invalidate_all(); | |
909 | } | |
910 | ||
911 | iterator | |
912 | begin() noexcept | |
913 | { return { _Base::begin(), this }; } | |
914 | ||
915 | const_iterator | |
916 | begin() const noexcept | |
917 | { return { _Base::begin(), this }; } | |
918 | ||
919 | iterator | |
920 | end() noexcept | |
921 | { return { _Base::end(), this }; } | |
922 | ||
923 | const_iterator | |
924 | end() const noexcept | |
925 | { return { _Base::end(), this }; } | |
926 | ||
927 | const_iterator | |
928 | cbegin() const noexcept | |
929 | { return { _Base::cbegin(), this }; } | |
930 | ||
931 | const_iterator | |
932 | cend() const noexcept | |
933 | { return { _Base::cend(), this }; } | |
934 | ||
935 | // local versions | |
936 | local_iterator | |
937 | begin(size_type __b) | |
938 | { | |
939 | __glibcxx_check_bucket_index(__b); | |
940 | return { _Base::begin(__b), this }; | |
941 | } | |
942 | ||
943 | local_iterator | |
944 | end(size_type __b) | |
945 | { | |
946 | __glibcxx_check_bucket_index(__b); | |
947 | return { _Base::end(__b), this }; | |
948 | } | |
949 | ||
950 | const_local_iterator | |
951 | begin(size_type __b) const | |
952 | { | |
953 | __glibcxx_check_bucket_index(__b); | |
954 | return { _Base::begin(__b), this }; | |
955 | } | |
956 | ||
957 | const_local_iterator | |
958 | end(size_type __b) const | |
959 | { | |
960 | __glibcxx_check_bucket_index(__b); | |
961 | return { _Base::end(__b), this }; | |
962 | } | |
963 | ||
964 | const_local_iterator | |
965 | cbegin(size_type __b) const | |
966 | { | |
967 | __glibcxx_check_bucket_index(__b); | |
968 | return { _Base::cbegin(__b), this }; | |
969 | } | |
970 | ||
971 | const_local_iterator | |
972 | cend(size_type __b) const | |
973 | { | |
974 | __glibcxx_check_bucket_index(__b); | |
975 | return { _Base::cend(__b), this }; | |
976 | } | |
977 | ||
978 | using _Base::bucket_count; | |
979 | using _Base::max_bucket_count; | |
980 | ||
981 | size_type | |
982 | bucket_size(size_type __b) const | |
983 | { | |
984 | __glibcxx_check_bucket_index(__b); | |
985 | return _Base::bucket_size(__b); | |
986 | } | |
987 | ||
988 | using _Base::bucket; | |
989 | using _Base::load_factor; | |
990 | ||
991 | float | |
992 | max_load_factor() const noexcept | |
993 | { return _Base::max_load_factor(); } | |
994 | ||
995 | void | |
996 | max_load_factor(float __f) | |
997 | { | |
998 | __glibcxx_check_max_load_factor(__f); | |
999 | _Base::max_load_factor(__f); | |
1000 | } | |
1001 | ||
1002 | using _Base::rehash; | |
1003 | using _Base::reserve; | |
1004 | ||
1005 | template<typename... _Args> | |
1006 | iterator | |
1007 | emplace(_Args&&... __args) | |
1008 | { | |
1009 | size_type __bucket_count = this->bucket_count(); | |
1010 | auto __it = _Base::emplace(std::forward<_Args>(__args)...); | |
1011 | _M_check_rehashed(__bucket_count); | |
1012 | return { __it, this }; | |
1013 | } | |
1014 | ||
1015 | template<typename... _Args> | |
1016 | iterator | |
1017 | emplace_hint(const_iterator __hint, _Args&&... __args) | |
1018 | { | |
1019 | __glibcxx_check_insert(__hint); | |
1020 | size_type __bucket_count = this->bucket_count(); | |
1021 | auto __it = _Base::emplace_hint(__hint.base(), | |
1022 | std::forward<_Args>(__args)...); | |
1023 | _M_check_rehashed(__bucket_count); | |
1024 | return { __it, this }; | |
1025 | } | |
1026 | ||
1027 | iterator | |
1028 | insert(const value_type& __obj) | |
1029 | { | |
1030 | size_type __bucket_count = this->bucket_count(); | |
1031 | auto __it = _Base::insert(__obj); | |
1032 | _M_check_rehashed(__bucket_count); | |
1033 | return { __it, this }; | |
1034 | } | |
1035 | ||
1036 | iterator | |
1037 | insert(const_iterator __hint, const value_type& __obj) | |
1038 | { | |
1039 | __glibcxx_check_insert(__hint); | |
1040 | size_type __bucket_count = this->bucket_count(); | |
1041 | auto __it = _Base::insert(__hint.base(), __obj); | |
1042 | _M_check_rehashed(__bucket_count); | |
1043 | return { __it, this }; | |
1044 | } | |
1045 | ||
1046 | iterator | |
1047 | insert(value_type&& __obj) | |
1048 | { | |
1049 | size_type __bucket_count = this->bucket_count(); | |
1050 | auto __it = _Base::insert(std::move(__obj)); | |
1051 | _M_check_rehashed(__bucket_count); | |
1052 | return { __it, this }; | |
1053 | } | |
1054 | ||
1055 | iterator | |
1056 | insert(const_iterator __hint, value_type&& __obj) | |
1057 | { | |
1058 | __glibcxx_check_insert(__hint); | |
1059 | size_type __bucket_count = this->bucket_count(); | |
1060 | auto __it = _Base::insert(__hint.base(), std::move(__obj)); | |
1061 | _M_check_rehashed(__bucket_count); | |
1062 | return { __it, this }; | |
1063 | } | |
1064 | ||
1065 | void | |
1066 | insert(std::initializer_list<value_type> __l) | |
1067 | { | |
1068 | size_type __bucket_count = this->bucket_count(); | |
1069 | _Base::insert(__l); | |
1070 | _M_check_rehashed(__bucket_count); | |
1071 | } | |
1072 | ||
1073 | template<typename _InputIterator> | |
1074 | void | |
1075 | insert(_InputIterator __first, _InputIterator __last) | |
1076 | { | |
1077 | typename __gnu_debug::_Distance_traits<_InputIterator>::__type __dist; | |
1078 | __glibcxx_check_valid_range2(__first, __last, __dist); | |
1079 | size_type __bucket_count = this->bucket_count(); | |
1080 | ||
1081 | if (__dist.second >= __gnu_debug::__dp_sign) | |
1082 | _Base::insert(__gnu_debug::__unsafe(__first), | |
1083 | __gnu_debug::__unsafe(__last)); | |
1084 | else | |
1085 | _Base::insert(__first, __last); | |
1086 | ||
1087 | _M_check_rehashed(__bucket_count); | |
1088 | } | |
1089 | ||
1090 | #if __cplusplus > 201402L | |
1091 | using node_type = typename _Base::node_type; | |
1092 | ||
1093 | node_type | |
1094 | extract(const_iterator __position) | |
1095 | { | |
1096 | __glibcxx_check_erase(__position); | |
1097 | return _M_extract(__position.base()); | |
1098 | } | |
1099 | ||
1100 | node_type | |
1101 | extract(const key_type& __key) | |
1102 | { | |
1103 | const auto __position = _Base::find(__key); | |
1104 | if (__position != _Base::end()) | |
1105 | return _M_extract(__position); | |
1106 | return {}; | |
1107 | } | |
1108 | ||
1109 | iterator | |
1110 | insert(node_type&& __nh) | |
1111 | { return { _Base::insert(std::move(__nh)), this }; } | |
1112 | ||
1113 | iterator | |
1114 | insert(const_iterator __hint, node_type&& __nh) | |
1115 | { | |
1116 | __glibcxx_check_insert(__hint); | |
1117 | return { _Base::insert(__hint.base(), std::move(__nh)), this }; | |
1118 | } | |
1119 | ||
1120 | template<typename _H2, typename _P2> | |
1121 | void | |
1122 | merge(unordered_multiset<_Value, _H2, _P2, _Alloc>& __source) | |
1123 | { | |
1124 | auto __guard | |
1125 | = _Safe::_S_umc_guard(std::__detail::_Identity{}, __source); | |
1126 | _Base::merge(__source); | |
1127 | } | |
1128 | ||
1129 | template<typename _H2, typename _P2> | |
1130 | void | |
1131 | merge(unordered_multiset<_Value, _H2, _P2, _Alloc>&& __source) | |
1132 | { merge(__source); } | |
1133 | ||
1134 | template<typename _H2, typename _P2> | |
1135 | void | |
1136 | merge(unordered_set<_Value, _H2, _P2, _Alloc>& __source) | |
1137 | { | |
1138 | auto __guard | |
1139 | = _Safe::_S_uc_guard(std::__detail::_Identity{}, __source); | |
1140 | _Base::merge(__source); | |
1141 | } | |
1142 | ||
1143 | template<typename _H2, typename _P2> | |
1144 | void | |
1145 | merge(unordered_set<_Value, _H2, _P2, _Alloc>&& __source) | |
1146 | { merge(__source); } | |
1147 | #endif // C++17 | |
1148 | ||
1149 | using _Base::hash_function; | |
1150 | using _Base::key_eq; | |
1151 | ||
1152 | iterator | |
1153 | find(const key_type& __key) | |
1154 | { return { _Base::find(__key), this }; } | |
1155 | ||
1156 | #if __cplusplus > 201703L | |
1157 | template<typename _Kt, | |
1158 | typename = std::__has_is_transparent_t<_Hash, _Kt>, | |
1159 | typename = std::__has_is_transparent_t<_Pred, _Kt>> | |
1160 | iterator | |
1161 | find(const _Kt& __k) | |
1162 | { return { _Base::find(__k), this }; } | |
1163 | #endif | |
1164 | ||
1165 | const_iterator | |
1166 | find(const key_type& __key) const | |
1167 | { return { _Base::find(__key), this }; } | |
1168 | ||
1169 | #if __cplusplus > 201703L | |
1170 | template<typename _Kt, | |
1171 | typename = std::__has_is_transparent_t<_Hash, _Kt>, | |
1172 | typename = std::__has_is_transparent_t<_Pred, _Kt>> | |
1173 | const_iterator | |
1174 | find(const _Kt& __k) const | |
1175 | { return { _Base::find(__k), this }; } | |
1176 | #endif | |
1177 | ||
1178 | using _Base::count; | |
1179 | ||
1180 | #if __cplusplus > 201703L | |
1181 | using _Base::contains; | |
1182 | #endif | |
1183 | ||
1184 | std::pair<iterator, iterator> | |
1185 | equal_range(const key_type& __key) | |
1186 | { | |
1187 | auto __res = _Base::equal_range(__key); | |
1188 | return { { __res.first, this }, { __res.second, this } }; | |
1189 | } | |
1190 | ||
1191 | #if __cplusplus > 201703L | |
1192 | template<typename _Kt, | |
1193 | typename = std::__has_is_transparent_t<_Hash, _Kt>, | |
1194 | typename = std::__has_is_transparent_t<_Pred, _Kt>> | |
1195 | std::pair<iterator, iterator> | |
1196 | equal_range(const _Kt& __k) | |
1197 | { | |
1198 | auto __res = _Base::equal_range(__k); | |
1199 | return { { __res.first, this }, { __res.second, this } }; | |
1200 | } | |
1201 | #endif | |
1202 | ||
1203 | std::pair<const_iterator, const_iterator> | |
1204 | equal_range(const key_type& __key) const | |
1205 | { | |
1206 | auto __res = _Base::equal_range(__key); | |
1207 | return { { __res.first, this }, { __res.second, this } }; | |
1208 | } | |
1209 | ||
1210 | #if __cplusplus > 201703L | |
1211 | template<typename _Kt, | |
1212 | typename = std::__has_is_transparent_t<_Hash, _Kt>, | |
1213 | typename = std::__has_is_transparent_t<_Pred, _Kt>> | |
1214 | std::pair<const_iterator, const_iterator> | |
1215 | equal_range(const _Kt& __k) const | |
1216 | { | |
1217 | auto __res = _Base::equal_range(__k); | |
1218 | return { { __res.first, this }, { __res.second, this } }; | |
1219 | } | |
1220 | #endif | |
1221 | ||
1222 | size_type | |
1223 | erase(const key_type& __key) | |
1224 | { | |
1225 | size_type __ret(0); | |
1226 | auto __pair = _Base::equal_range(__key); | |
1227 | for (auto __victim = __pair.first; __victim != __pair.second;) | |
1228 | { | |
1229 | _M_invalidate(__victim); | |
1230 | __victim = _Base::erase(__victim); | |
1231 | ++__ret; | |
1232 | } | |
1233 | ||
1234 | return __ret; | |
1235 | } | |
1236 | ||
1237 | iterator | |
1238 | erase(const_iterator __it) | |
1239 | { | |
1240 | __glibcxx_check_erase(__it); | |
1241 | return { _M_erase(__it.base()), this }; | |
1242 | } | |
1243 | ||
1244 | _Base_iterator | |
1245 | erase(_Base_const_iterator __it) | |
1246 | { | |
1247 | __glibcxx_check_erase2(__it); | |
1248 | return _M_erase(__it); | |
1249 | } | |
1250 | ||
1251 | iterator | |
1252 | erase(iterator __it) | |
1253 | { | |
1254 | __glibcxx_check_erase(__it); | |
1255 | return { _M_erase(__it.base()), this }; | |
1256 | } | |
1257 | ||
1258 | iterator | |
1259 | erase(const_iterator __first, const_iterator __last) | |
1260 | { | |
1261 | __glibcxx_check_erase_range(__first, __last); | |
1262 | for (auto __tmp = __first.base(); __tmp != __last.base(); ++__tmp) | |
1263 | { | |
1264 | _GLIBCXX_DEBUG_VERIFY(__tmp != _Base::cend(), | |
1265 | _M_message(__gnu_debug::__msg_valid_range) | |
1266 | ._M_iterator(__first, "first") | |
1267 | ._M_iterator(__last, "last")); | |
1268 | _M_invalidate(__tmp); | |
1269 | } | |
1270 | return { _Base::erase(__first.base(), __last.base()), this }; | |
1271 | } | |
1272 | ||
1273 | _Base& | |
1274 | _M_base() noexcept { return *this; } | |
1275 | ||
1276 | const _Base& | |
1277 | _M_base() const noexcept { return *this; } | |
1278 | ||
1279 | private: | |
1280 | void | |
1281 | _M_check_rehashed(size_type __prev_count) | |
1282 | { | |
1283 | if (__prev_count != this->bucket_count()) | |
1284 | this->_M_invalidate_all(); | |
1285 | } | |
1286 | ||
1287 | void | |
1288 | _M_invalidate(_Base_const_iterator __victim) | |
1289 | { | |
1290 | this->_M_invalidate_if( | |
1291 | [__victim](_Base_const_iterator __it) { return __it == __victim; }); | |
1292 | this->_M_invalidate_local_if( | |
1293 | [__victim](_Base_const_local_iterator __it) | |
1294 | { return __it == __victim; }); | |
1295 | } | |
1296 | ||
1297 | _Base_iterator | |
1298 | _M_erase(_Base_const_iterator __victim) | |
1299 | { | |
1300 | _M_invalidate(__victim); | |
1301 | size_type __bucket_count = this->bucket_count(); | |
1302 | _Base_iterator __next = _Base::erase(__victim); | |
1303 | _M_check_rehashed(__bucket_count); | |
1304 | return __next; | |
1305 | } | |
1306 | ||
1307 | #if __cplusplus > 201402L | |
1308 | node_type | |
1309 | _M_extract(_Base_const_iterator __victim) | |
1310 | { | |
1311 | _M_invalidate(__victim); | |
1312 | return _Base::extract(__victim); | |
1313 | } | |
1314 | #endif | |
1315 | }; | |
1316 | ||
1317 | #if __cpp_deduction_guides >= 201606 | |
1318 | ||
1319 | template<typename _InputIterator, | |
1320 | typename _Hash = | |
1321 | hash<typename iterator_traits<_InputIterator>::value_type>, | |
1322 | typename _Pred = | |
1323 | equal_to<typename iterator_traits<_InputIterator>::value_type>, | |
1324 | typename _Allocator = | |
1325 | allocator<typename iterator_traits<_InputIterator>::value_type>, | |
1326 | typename = _RequireInputIter<_InputIterator>, | |
1327 | typename = _RequireNotAllocatorOrIntegral<_Hash>, | |
1328 | typename = _RequireNotAllocator<_Pred>, | |
1329 | typename = _RequireAllocator<_Allocator>> | |
1330 | unordered_multiset(_InputIterator, _InputIterator, | |
1331 | unordered_multiset<int>::size_type = {}, | |
1332 | _Hash = _Hash(), _Pred = _Pred(), | |
1333 | _Allocator = _Allocator()) | |
1334 | -> unordered_multiset<typename iterator_traits<_InputIterator>::value_type, | |
1335 | _Hash, _Pred, _Allocator>; | |
1336 | ||
1337 | template<typename _Tp, typename _Hash = hash<_Tp>, | |
1338 | typename _Pred = equal_to<_Tp>, | |
1339 | typename _Allocator = allocator<_Tp>, | |
1340 | typename = _RequireNotAllocatorOrIntegral<_Hash>, | |
1341 | typename = _RequireNotAllocator<_Pred>, | |
1342 | typename = _RequireAllocator<_Allocator>> | |
1343 | unordered_multiset(initializer_list<_Tp>, | |
1344 | unordered_multiset<int>::size_type = {}, | |
1345 | _Hash = _Hash(), _Pred = _Pred(), | |
1346 | _Allocator = _Allocator()) | |
1347 | -> unordered_multiset<_Tp, _Hash, _Pred, _Allocator>; | |
1348 | ||
1349 | template<typename _InputIterator, typename _Allocator, | |
1350 | typename = _RequireInputIter<_InputIterator>, | |
1351 | typename = _RequireAllocator<_Allocator>> | |
1352 | unordered_multiset(_InputIterator, _InputIterator, | |
1353 | unordered_multiset<int>::size_type, _Allocator) | |
1354 | -> unordered_multiset<typename iterator_traits<_InputIterator>::value_type, | |
1355 | hash<typename | |
1356 | iterator_traits<_InputIterator>::value_type>, | |
1357 | equal_to<typename | |
1358 | iterator_traits<_InputIterator>::value_type>, | |
1359 | _Allocator>; | |
1360 | ||
1361 | template<typename _InputIterator, typename _Hash, typename _Allocator, | |
1362 | typename = _RequireInputIter<_InputIterator>, | |
1363 | typename = _RequireNotAllocatorOrIntegral<_Hash>, | |
1364 | typename = _RequireAllocator<_Allocator>> | |
1365 | unordered_multiset(_InputIterator, _InputIterator, | |
1366 | unordered_multiset<int>::size_type, | |
1367 | _Hash, _Allocator) | |
1368 | -> unordered_multiset<typename | |
1369 | iterator_traits<_InputIterator>::value_type, | |
1370 | _Hash, | |
1371 | equal_to< | |
1372 | typename | |
1373 | iterator_traits<_InputIterator>::value_type>, | |
1374 | _Allocator>; | |
1375 | ||
1376 | template<typename _Tp, typename _Allocator, | |
1377 | typename = _RequireAllocator<_Allocator>> | |
1378 | unordered_multiset(initializer_list<_Tp>, | |
1379 | unordered_multiset<int>::size_type, _Allocator) | |
1380 | -> unordered_multiset<_Tp, hash<_Tp>, equal_to<_Tp>, _Allocator>; | |
1381 | ||
1382 | template<typename _Tp, typename _Hash, typename _Allocator, | |
1383 | typename = _RequireNotAllocatorOrIntegral<_Hash>, | |
1384 | typename = _RequireAllocator<_Allocator>> | |
1385 | unordered_multiset(initializer_list<_Tp>, | |
1386 | unordered_multiset<int>::size_type, _Hash, _Allocator) | |
1387 | -> unordered_multiset<_Tp, _Hash, equal_to<_Tp>, _Allocator>; | |
1388 | ||
1389 | #endif | |
1390 | ||
1391 | template<typename _Value, typename _Hash, typename _Pred, typename _Alloc> | |
1392 | inline void | |
1393 | swap(unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x, | |
1394 | unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y) | |
1395 | noexcept(noexcept(__x.swap(__y))) | |
1396 | { __x.swap(__y); } | |
1397 | ||
1398 | template<typename _Value, typename _Hash, typename _Pred, typename _Alloc> | |
1399 | inline bool | |
1400 | operator==(const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x, | |
1401 | const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y) | |
1402 | { return __x._M_base() == __y._M_base(); } | |
1403 | ||
1404 | #if __cpp_impl_three_way_comparison < 201907L | |
1405 | template<typename _Value, typename _Hash, typename _Pred, typename _Alloc> | |
1406 | inline bool | |
1407 | operator!=(const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x, | |
1408 | const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y) | |
1409 | { return !(__x == __y); } | |
1410 | #endif | |
1411 | ||
1412 | } // namespace __debug | |
1413 | } // namespace std | |
1414 | ||
1415 | #endif // C++11 | |
1416 | ||
1417 | #endif |