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