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