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