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 1418
Indexes created Sun Mar 01 05:31:48 UTC 2026