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