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 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 template<typename _Value, typename _Hash, typename _Pred, typename _Alloc> 617 inline bool 618 operator!=(const unordered_set<_Value, _Hash, _Pred, _Alloc>& __x, 619 const unordered_set<_Value, _Hash, _Pred, _Alloc>& __y) 620 { return !(__x == __y); } 621 622 623 /// Class std::unordered_multiset with safety/checking/debug instrumentation. 624 template<typename _Value, 625 typename _Hash = std::hash<_Value>, 626 typename _Pred = std::equal_to<_Value>, 627 typename _Alloc = std::allocator<_Value> > 628 class unordered_multiset 629 : public __gnu_debug::_Safe_container< 630 unordered_multiset<_Value, _Hash, _Pred, _Alloc>, _Alloc, 631 __gnu_debug::_Safe_unordered_container>, 632 public _GLIBCXX_STD_C::unordered_multiset<_Value, _Hash, _Pred, _Alloc> 633 { 634 typedef _GLIBCXX_STD_C::unordered_multiset< 635 _Value, _Hash, _Pred, _Alloc> _Base; 636 typedef __gnu_debug::_Safe_container<unordered_multiset, 637 _Alloc, __gnu_debug::_Safe_unordered_container> _Safe; 638 typedef typename _Base::const_iterator _Base_const_iterator; 639 typedef typename _Base::iterator _Base_iterator; 640 typedef typename _Base::const_local_iterator 641 _Base_const_local_iterator; 642 typedef typename _Base::local_iterator _Base_local_iterator; 643 644 template<typename _ItT, typename _SeqT, typename _CatT> 645 friend class ::__gnu_debug::_Safe_iterator; 646 template<typename _ItT, typename _SeqT> 647 friend class ::__gnu_debug::_Safe_local_iterator; 648 649 public: 650 typedef typename _Base::size_type size_type; 651 typedef typename _Base::hasher hasher; 652 typedef typename _Base::key_equal key_equal; 653 typedef typename _Base::allocator_type allocator_type; 654 655 typedef typename _Base::key_type key_type; 656 typedef typename _Base::value_type value_type; 657 658 typedef __gnu_debug::_Safe_iterator< 659 _Base_iterator, unordered_multiset> iterator; 660 typedef __gnu_debug::_Safe_iterator< 661 _Base_const_iterator, unordered_multiset> const_iterator; 662 typedef __gnu_debug::_Safe_local_iterator< 663 _Base_local_iterator, unordered_multiset> local_iterator; 664 typedef __gnu_debug::_Safe_local_iterator< 665 _Base_const_local_iterator, unordered_multiset> const_local_iterator; 666 667 unordered_multiset() = default; 668 669 explicit 670 unordered_multiset(size_type __n, 671 const hasher& __hf = hasher(), 672 const key_equal& __eql = key_equal(), 673 const allocator_type& __a = allocator_type()) 674 : _Base(__n, __hf, __eql, __a) { } 675 676 template<typename _InputIterator> 677 unordered_multiset(_InputIterator __first, _InputIterator __last, 678 size_type __n = 0, 679 const hasher& __hf = hasher(), 680 const key_equal& __eql = key_equal(), 681 const allocator_type& __a = allocator_type()) 682 : _Base(__gnu_debug::__base( 683 __glibcxx_check_valid_constructor_range(__first, __last)), 684 __gnu_debug::__base(__last), __n, 685 __hf, __eql, __a) { } 686 687 unordered_multiset(const unordered_multiset&) = default; 688 689 unordered_multiset(const _Base& __x) 690 : _Base(__x) { } 691 692 unordered_multiset(unordered_multiset&&) = default; 693 694 explicit 695 unordered_multiset(const allocator_type& __a) 696 : _Base(__a) { } 697 698 unordered_multiset(const unordered_multiset& __uset, 699 const allocator_type& __a) 700 : _Base(__uset, __a) { } 701 702 unordered_multiset(unordered_multiset&& __uset, 703 const allocator_type& __a) 704 noexcept( noexcept(_Base(std::move(__uset._M_base()), __a)) ) 705 : _Safe(std::move(__uset._M_safe()), __a), 706 _Base(std::move(__uset._M_base()), __a) { } 707 708 unordered_multiset(initializer_list<value_type> __l, 709 size_type __n = 0, 710 const hasher& __hf = hasher(), 711 const key_equal& __eql = key_equal(), 712 const allocator_type& __a = allocator_type()) 713 : _Base(__l, __n, __hf, __eql, __a) { } 714 715 unordered_multiset(size_type __n, const allocator_type& __a) 716 : unordered_multiset(__n, hasher(), key_equal(), __a) 717 { } 718 719 unordered_multiset(size_type __n, const hasher& __hf, 720 const allocator_type& __a) 721 : unordered_multiset(__n, __hf, key_equal(), __a) 722 { } 723 724 template<typename _InputIterator> 725 unordered_multiset(_InputIterator __first, _InputIterator __last, 726 size_type __n, 727 const allocator_type& __a) 728 : unordered_multiset(__first, __last, __n, hasher(), key_equal(), __a) 729 { } 730 731 template<typename _InputIterator> 732 unordered_multiset(_InputIterator __first, _InputIterator __last, 733 size_type __n, const hasher& __hf, 734 const allocator_type& __a) 735 : unordered_multiset(__first, __last, __n, __hf, key_equal(), __a) 736 { } 737 738 unordered_multiset(initializer_list<value_type> __l, 739 size_type __n, 740 const allocator_type& __a) 741 : unordered_multiset(__l, __n, hasher(), key_equal(), __a) 742 { } 743 744 unordered_multiset(initializer_list<value_type> __l, 745 size_type __n, const hasher& __hf, 746 const allocator_type& __a) 747 : unordered_multiset(__l, __n, __hf, key_equal(), __a) 748 { } 749 750 ~unordered_multiset() = default; 751 752 unordered_multiset& 753 operator=(const unordered_multiset&) = default; 754 755 unordered_multiset& 756 operator=(unordered_multiset&&) = default; 757 758 unordered_multiset& 759 operator=(initializer_list<value_type> __l) 760 { 761 this->_M_base() = __l; 762 this->_M_invalidate_all(); 763 return *this; 764 } 765 766 void 767 swap(unordered_multiset& __x) 768 noexcept( noexcept(declval<_Base&>().swap(__x)) ) 769 { 770 _Safe::_M_swap(__x); 771 _Base::swap(__x); 772 } 773 774 void 775 clear() noexcept 776 { 777 _Base::clear(); 778 this->_M_invalidate_all(); 779 } 780 781 iterator 782 begin() noexcept 783 { return { _Base::begin(), this }; } 784 785 const_iterator 786 begin() const noexcept 787 { return { _Base::begin(), this }; } 788 789 iterator 790 end() noexcept 791 { return { _Base::end(), this }; } 792 793 const_iterator 794 end() const noexcept 795 { return { _Base::end(), this }; } 796 797 const_iterator 798 cbegin() const noexcept 799 { return { _Base::cbegin(), this }; } 800 801 const_iterator 802 cend() const noexcept 803 { return { _Base::cend(), this }; } 804 805 // local versions 806 local_iterator 807 begin(size_type __b) 808 { 809 __glibcxx_check_bucket_index(__b); 810 return { _Base::begin(__b), this }; 811 } 812 813 local_iterator 814 end(size_type __b) 815 { 816 __glibcxx_check_bucket_index(__b); 817 return { _Base::end(__b), this }; 818 } 819 820 const_local_iterator 821 begin(size_type __b) const 822 { 823 __glibcxx_check_bucket_index(__b); 824 return { _Base::begin(__b), this }; 825 } 826 827 const_local_iterator 828 end(size_type __b) const 829 { 830 __glibcxx_check_bucket_index(__b); 831 return { _Base::end(__b), this }; 832 } 833 834 const_local_iterator 835 cbegin(size_type __b) const 836 { 837 __glibcxx_check_bucket_index(__b); 838 return { _Base::cbegin(__b), this }; 839 } 840 841 const_local_iterator 842 cend(size_type __b) const 843 { 844 __glibcxx_check_bucket_index(__b); 845 return { _Base::cend(__b), this }; 846 } 847 848 size_type 849 bucket_size(size_type __b) const 850 { 851 __glibcxx_check_bucket_index(__b); 852 return _Base::bucket_size(__b); 853 } 854 855 float 856 max_load_factor() const noexcept 857 { return _Base::max_load_factor(); } 858 859 void 860 max_load_factor(float __f) 861 { 862 __glibcxx_check_max_load_factor(__f); 863 _Base::max_load_factor(__f); 864 } 865 866 template<typename... _Args> 867 iterator 868 emplace(_Args&&... __args) 869 { 870 size_type __bucket_count = this->bucket_count(); 871 auto __it = _Base::emplace(std::forward<_Args>(__args)...); 872 _M_check_rehashed(__bucket_count); 873 return { __it, this }; 874 } 875 876 template<typename... _Args> 877 iterator 878 emplace_hint(const_iterator __hint, _Args&&... __args) 879 { 880 __glibcxx_check_insert(__hint); 881 size_type __bucket_count = this->bucket_count(); 882 auto __it = _Base::emplace_hint(__hint.base(), 883 std::forward<_Args>(__args)...); 884 _M_check_rehashed(__bucket_count); 885 return { __it, this }; 886 } 887 888 iterator 889 insert(const value_type& __obj) 890 { 891 size_type __bucket_count = this->bucket_count(); 892 auto __it = _Base::insert(__obj); 893 _M_check_rehashed(__bucket_count); 894 return { __it, this }; 895 } 896 897 iterator 898 insert(const_iterator __hint, const value_type& __obj) 899 { 900 __glibcxx_check_insert(__hint); 901 size_type __bucket_count = this->bucket_count(); 902 auto __it = _Base::insert(__hint.base(), __obj); 903 _M_check_rehashed(__bucket_count); 904 return { __it, this }; 905 } 906 907 iterator 908 insert(value_type&& __obj) 909 { 910 size_type __bucket_count = this->bucket_count(); 911 auto __it = _Base::insert(std::move(__obj)); 912 _M_check_rehashed(__bucket_count); 913 return { __it, this }; 914 } 915 916 iterator 917 insert(const_iterator __hint, value_type&& __obj) 918 { 919 __glibcxx_check_insert(__hint); 920 size_type __bucket_count = this->bucket_count(); 921 auto __it = _Base::insert(__hint.base(), std::move(__obj)); 922 _M_check_rehashed(__bucket_count); 923 return { __it, this }; 924 } 925 926 void 927 insert(std::initializer_list<value_type> __l) 928 { 929 size_type __bucket_count = this->bucket_count(); 930 _Base::insert(__l); 931 _M_check_rehashed(__bucket_count); 932 } 933 934 template<typename _InputIterator> 935 void 936 insert(_InputIterator __first, _InputIterator __last) 937 { 938 typename __gnu_debug::_Distance_traits<_InputIterator>::__type __dist; 939 __glibcxx_check_valid_range2(__first, __last, __dist); 940 size_type __bucket_count = this->bucket_count(); 941 942 if (__dist.second >= __gnu_debug::__dp_sign) 943 _Base::insert(__gnu_debug::__unsafe(__first), 944 __gnu_debug::__unsafe(__last)); 945 else 946 _Base::insert(__first, __last); 947 948 _M_check_rehashed(__bucket_count); 949 } 950 951#if __cplusplus > 201402L 952 using node_type = typename _Base::node_type; 953 954 node_type 955 extract(const_iterator __position) 956 { 957 __glibcxx_check_erase(__position); 958 return _M_extract(__position.base()); 959 } 960 961 node_type 962 extract(const key_type& __key) 963 { 964 const auto __position = _Base::find(__key); 965 if (__position != _Base::end()) 966 return _M_extract(__position); 967 return {}; 968 } 969 970 iterator 971 insert(node_type&& __nh) 972 { return { _Base::insert(std::move(__nh)), this }; } 973 974 iterator 975 insert(const_iterator __hint, node_type&& __nh) 976 { 977 __glibcxx_check_insert(__hint); 978 return { _Base::insert(__hint.base(), std::move(__nh)), this }; 979 } 980 981 using _Base::merge; 982#endif // C++17 983 984 iterator 985 find(const key_type& __key) 986 { return { _Base::find(__key), this }; } 987 988 const_iterator 989 find(const key_type& __key) const 990 { return { _Base::find(__key), this }; } 991 992 std::pair<iterator, iterator> 993 equal_range(const key_type& __key) 994 { 995 auto __res = _Base::equal_range(__key); 996 return { { __res.first, this }, { __res.second, this } }; 997 } 998 999 std::pair<const_iterator, const_iterator> 1000 equal_range(const key_type& __key) const 1001 { 1002 auto __res = _Base::equal_range(__key); 1003 return { { __res.first, this }, { __res.second, this } }; 1004 } 1005 1006 size_type 1007 erase(const key_type& __key) 1008 { 1009 size_type __ret(0); 1010 auto __pair = _Base::equal_range(__key); 1011 for (auto __victim = __pair.first; __victim != __pair.second;) 1012 { 1013 _M_invalidate(__victim); 1014 __victim = _Base::erase(__victim); 1015 ++__ret; 1016 } 1017 1018 return __ret; 1019 } 1020 1021 iterator 1022 erase(const_iterator __it) 1023 { 1024 __glibcxx_check_erase(__it); 1025 return { _M_erase(__it.base()), this }; 1026 } 1027 1028 iterator 1029 erase(iterator __it) 1030 { 1031 __glibcxx_check_erase(__it); 1032 return { _M_erase(__it.base()), this }; 1033 } 1034 1035 iterator 1036 erase(const_iterator __first, const_iterator __last) 1037 { 1038 __glibcxx_check_erase_range(__first, __last); 1039 for (auto __tmp = __first.base(); __tmp != __last.base(); ++__tmp) 1040 { 1041 _GLIBCXX_DEBUG_VERIFY(__tmp != _Base::cend(), 1042 _M_message(__gnu_debug::__msg_valid_range) 1043 ._M_iterator(__first, "first") 1044 ._M_iterator(__last, "last")); 1045 _M_invalidate(__tmp); 1046 } 1047 return { _Base::erase(__first.base(), __last.base()), this }; 1048 } 1049 1050 _Base& 1051 _M_base() noexcept { return *this; } 1052 1053 const _Base& 1054 _M_base() const noexcept { return *this; } 1055 1056 private: 1057 void 1058 _M_check_rehashed(size_type __prev_count) 1059 { 1060 if (__prev_count != this->bucket_count()) 1061 this->_M_invalidate_all(); 1062 } 1063 1064 void 1065 _M_invalidate(_Base_const_iterator __victim) 1066 { 1067 this->_M_invalidate_if( 1068 [__victim](_Base_const_iterator __it) { return __it == __victim; }); 1069 this->_M_invalidate_local_if( 1070 [__victim](_Base_const_local_iterator __it) 1071 { return __it._M_curr() == __victim._M_cur; }); 1072 } 1073 1074 _Base_iterator 1075 _M_erase(_Base_const_iterator __victim) 1076 { 1077 _M_invalidate(__victim); 1078 size_type __bucket_count = this->bucket_count(); 1079 _Base_iterator __next = _Base::erase(__victim); 1080 _M_check_rehashed(__bucket_count); 1081 return __next; 1082 } 1083 1084#if __cplusplus > 201402L 1085 node_type 1086 _M_extract(_Base_const_iterator __victim) 1087 { 1088 _M_invalidate(__victim); 1089 return _Base::extract(__victim); 1090 } 1091#endif 1092 }; 1093 1094#if __cpp_deduction_guides >= 201606 1095 1096 template<typename _InputIterator, 1097 typename _Hash = 1098 hash<typename iterator_traits<_InputIterator>::value_type>, 1099 typename _Pred = 1100 equal_to<typename iterator_traits<_InputIterator>::value_type>, 1101 typename _Allocator = 1102 allocator<typename iterator_traits<_InputIterator>::value_type>, 1103 typename = _RequireInputIter<_InputIterator>, 1104 typename = _RequireNotAllocatorOrIntegral<_Hash>, 1105 typename = _RequireNotAllocator<_Pred>, 1106 typename = _RequireAllocator<_Allocator>> 1107 unordered_multiset(_InputIterator, _InputIterator, 1108 unordered_multiset<int>::size_type = {}, 1109 _Hash = _Hash(), _Pred = _Pred(), 1110 _Allocator = _Allocator()) 1111 -> unordered_multiset<typename iterator_traits<_InputIterator>::value_type, 1112 _Hash, _Pred, _Allocator>; 1113 1114 template<typename _Tp, typename _Hash = hash<_Tp>, 1115 typename _Pred = equal_to<_Tp>, 1116 typename _Allocator = allocator<_Tp>, 1117 typename = _RequireNotAllocatorOrIntegral<_Hash>, 1118 typename = _RequireNotAllocator<_Pred>, 1119 typename = _RequireAllocator<_Allocator>> 1120 unordered_multiset(initializer_list<_Tp>, 1121 unordered_multiset<int>::size_type = {}, 1122 _Hash = _Hash(), _Pred = _Pred(), 1123 _Allocator = _Allocator()) 1124 -> unordered_multiset<_Tp, _Hash, _Pred, _Allocator>; 1125 1126 template<typename _InputIterator, typename _Allocator, 1127 typename = _RequireInputIter<_InputIterator>, 1128 typename = _RequireAllocator<_Allocator>> 1129 unordered_multiset(_InputIterator, _InputIterator, 1130 unordered_multiset<int>::size_type, _Allocator) 1131 -> unordered_multiset<typename iterator_traits<_InputIterator>::value_type, 1132 hash<typename 1133 iterator_traits<_InputIterator>::value_type>, 1134 equal_to<typename 1135 iterator_traits<_InputIterator>::value_type>, 1136 _Allocator>; 1137 1138 template<typename _InputIterator, typename _Hash, typename _Allocator, 1139 typename = _RequireInputIter<_InputIterator>, 1140 typename = _RequireNotAllocatorOrIntegral<_Hash>, 1141 typename = _RequireAllocator<_Allocator>> 1142 unordered_multiset(_InputIterator, _InputIterator, 1143 unordered_multiset<int>::size_type, 1144 _Hash, _Allocator) 1145 -> unordered_multiset<typename 1146 iterator_traits<_InputIterator>::value_type, 1147 _Hash, 1148 equal_to< 1149 typename 1150 iterator_traits<_InputIterator>::value_type>, 1151 _Allocator>; 1152 1153 template<typename _Tp, typename _Allocator, 1154 typename = _RequireAllocator<_Allocator>> 1155 unordered_multiset(initializer_list<_Tp>, 1156 unordered_multiset<int>::size_type, _Allocator) 1157 -> unordered_multiset<_Tp, hash<_Tp>, equal_to<_Tp>, _Allocator>; 1158 1159 template<typename _Tp, typename _Hash, typename _Allocator, 1160 typename = _RequireNotAllocatorOrIntegral<_Hash>, 1161 typename = _RequireAllocator<_Allocator>> 1162 unordered_multiset(initializer_list<_Tp>, 1163 unordered_multiset<int>::size_type, _Hash, _Allocator) 1164 -> unordered_multiset<_Tp, _Hash, equal_to<_Tp>, _Allocator>; 1165 1166#endif 1167 1168 template<typename _Value, typename _Hash, typename _Pred, typename _Alloc> 1169 inline void 1170 swap(unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x, 1171 unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y) 1172 noexcept(noexcept(__x.swap(__y))) 1173 { __x.swap(__y); } 1174 1175 template<typename _Value, typename _Hash, typename _Pred, typename _Alloc> 1176 inline bool 1177 operator==(const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x, 1178 const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y) 1179 { return __x._M_base() == __y._M_base(); } 1180 1181 template<typename _Value, typename _Hash, typename _Pred, typename _Alloc> 1182 inline bool 1183 operator!=(const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x, 1184 const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y) 1185 { return !(__x == __y); } 1186 1187} // namespace __debug 1188} // namespace std 1189 1190#endif // C++11 1191 1192#endif 1193