1 // Debugging unordered_set/unordered_multiset implementation -*- C++ -*- 2 3 // Copyright (C) 2003-2014 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 #if __cplusplus < 201103L 33 # include <bits/c++0x_warning.h> 34 #else 35 # include <unordered_set> 36 37 #include <debug/safe_unordered_container.h> 38 #include <debug/safe_iterator.h> 39 #include <debug/safe_local_iterator.h> 40 41 namespace std _GLIBCXX_VISIBILITY(default) 42 { 43 namespace __debug 44 { 45 /// Class std::unordered_set with safety/checking/debug instrumentation. 46 template<typename _Value, 47 typename _Hash = std::hash<_Value>, 48 typename _Pred = std::equal_to<_Value>, 49 typename _Alloc = std::allocator<_Value> > 50 class unordered_set 51 : public _GLIBCXX_STD_C::unordered_set<_Value, _Hash, _Pred, _Alloc>, 52 public __gnu_debug::_Safe_unordered_container<unordered_set<_Value, _Hash, 53 _Pred, _Alloc> > 54 { 55 typedef _GLIBCXX_STD_C::unordered_set<_Value, _Hash, 56 _Pred, _Alloc> _Base; 57 typedef __gnu_debug::_Safe_unordered_container<unordered_set> _Safe_base; 58 typedef typename _Base::const_iterator _Base_const_iterator; 59 typedef typename _Base::iterator _Base_iterator; 60 typedef typename _Base::const_local_iterator _Base_const_local_iterator; 61 typedef typename _Base::local_iterator _Base_local_iterator; 62 63 typedef __gnu_cxx::__alloc_traits<typename 64 _Base::allocator_type> _Alloc_traits; 65 public: 66 typedef typename _Base::size_type size_type; 67 typedef typename _Base::hasher hasher; 68 typedef typename _Base::key_equal key_equal; 69 typedef typename _Base::allocator_type allocator_type; 70 71 typedef typename _Base::key_type key_type; 72 typedef typename _Base::value_type value_type; 73 74 typedef __gnu_debug::_Safe_iterator<_Base_iterator, 75 unordered_set> iterator; 76 typedef __gnu_debug::_Safe_iterator<_Base_const_iterator, 77 unordered_set> const_iterator; 78 typedef __gnu_debug::_Safe_local_iterator<_Base_local_iterator, 79 unordered_set> local_iterator; 80 typedef __gnu_debug::_Safe_local_iterator<_Base_const_local_iterator, 81 unordered_set> const_local_iterator; 82 83 explicit 84 unordered_set(size_type __n = 10, 85 const hasher& __hf = hasher(), 86 const key_equal& __eql = key_equal(), 87 const allocator_type& __a = allocator_type()) 88 : _Base(__n, __hf, __eql, __a) { } 89 90 template<typename _InputIterator> 91 unordered_set(_InputIterator __first, _InputIterator __last, 92 size_type __n = 0, 93 const hasher& __hf = hasher(), 94 const key_equal& __eql = key_equal(), 95 const allocator_type& __a = allocator_type()) 96 : _Base(__gnu_debug::__base(__gnu_debug::__check_valid_range(__first, 97 __last)), 98 __gnu_debug::__base(__last), __n, 99 __hf, __eql, __a) { } 100 101 unordered_set(const unordered_set&) = default; 102 103 unordered_set(const _Base& __x) 104 : _Base(__x) { } 105 106 unordered_set(unordered_set&&) = default; 107 108 explicit 109 unordered_set(const allocator_type& __a) 110 : _Base(__a) 111 { } 112 113 unordered_set(const unordered_set& __uset, 114 const allocator_type& __a) 115 : _Base(__uset._M_base(), __a) 116 { } 117 118 unordered_set(unordered_set&& __uset, 119 const allocator_type& __a) 120 : _Base(std::move(__uset._M_base()), __a) 121 { } 122 123 unordered_set(initializer_list<value_type> __l, 124 size_type __n = 0, 125 const hasher& __hf = hasher(), 126 const key_equal& __eql = key_equal(), 127 const allocator_type& __a = allocator_type()) 128 : _Base(__l, __n, __hf, __eql, __a) { } 129 130 ~unordered_set() noexcept { } 131 132 unordered_set& 133 operator=(const unordered_set& __x) 134 { 135 _M_base() = __x._M_base(); 136 this->_M_invalidate_all(); 137 return *this; 138 } 139 140 unordered_set& 141 operator=(unordered_set&& __x) 142 noexcept(_Alloc_traits::_S_nothrow_move()) 143 { 144 __glibcxx_check_self_move_assign(__x); 145 bool __xfer_memory = _Alloc_traits::_S_propagate_on_move_assign() 146 || __x.get_allocator() == this->get_allocator(); 147 _M_base() = std::move(__x._M_base()); 148 if (__xfer_memory) 149 this->_M_swap(__x); 150 else 151 this->_M_invalidate_all(); 152 __x._M_invalidate_all(); 153 return *this; 154 } 155 156 unordered_set& 157 operator=(initializer_list<value_type> __l) 158 { 159 _M_base() = __l; 160 this->_M_invalidate_all(); 161 return *this; 162 } 163 164 void 165 swap(unordered_set& __x) 166 noexcept(_Alloc_traits::_S_nothrow_swap()) 167 { 168 if (!_Alloc_traits::_S_propagate_on_swap()) 169 __glibcxx_check_equal_allocs(__x); 170 _Base::swap(__x); 171 _Safe_base::_M_swap(__x); 172 } 173 174 void 175 clear() noexcept 176 { 177 _Base::clear(); 178 this->_M_invalidate_all(); 179 } 180 181 iterator 182 begin() noexcept 183 { return iterator(_Base::begin(), this); } 184 185 const_iterator 186 begin() const noexcept 187 { return const_iterator(_Base::begin(), this); } 188 189 iterator 190 end() noexcept 191 { return iterator(_Base::end(), this); } 192 193 const_iterator 194 end() const noexcept 195 { return const_iterator(_Base::end(), this); } 196 197 const_iterator 198 cbegin() const noexcept 199 { return const_iterator(_Base::begin(), this); } 200 201 const_iterator 202 cend() const noexcept 203 { return const_iterator(_Base::end(), this); } 204 205 // local versions 206 local_iterator 207 begin(size_type __b) 208 { 209 __glibcxx_check_bucket_index(__b); 210 return local_iterator(_Base::begin(__b), this); 211 } 212 213 local_iterator 214 end(size_type __b) 215 { 216 __glibcxx_check_bucket_index(__b); 217 return local_iterator(_Base::end(__b), this); 218 } 219 220 const_local_iterator 221 begin(size_type __b) const 222 { 223 __glibcxx_check_bucket_index(__b); 224 return const_local_iterator(_Base::begin(__b), this); 225 } 226 227 const_local_iterator 228 end(size_type __b) const 229 { 230 __glibcxx_check_bucket_index(__b); 231 return const_local_iterator(_Base::end(__b), this); 232 } 233 234 const_local_iterator 235 cbegin(size_type __b) const 236 { 237 __glibcxx_check_bucket_index(__b); 238 return const_local_iterator(_Base::cbegin(__b), this); 239 } 240 241 const_local_iterator 242 cend(size_type __b) const 243 { 244 __glibcxx_check_bucket_index(__b); 245 return const_local_iterator(_Base::cend(__b), this); 246 } 247 248 size_type 249 bucket_size(size_type __b) const 250 { 251 __glibcxx_check_bucket_index(__b); 252 return _Base::bucket_size(__b); 253 } 254 255 float 256 max_load_factor() const noexcept 257 { return _Base::max_load_factor(); } 258 259 void 260 max_load_factor(float __f) 261 { 262 __glibcxx_check_max_load_factor(__f); 263 _Base::max_load_factor(__f); 264 } 265 266 template<typename... _Args> 267 std::pair<iterator, bool> 268 emplace(_Args&&... __args) 269 { 270 size_type __bucket_count = this->bucket_count(); 271 std::pair<_Base_iterator, bool> __res 272 = _Base::emplace(std::forward<_Args>(__args)...); 273 _M_check_rehashed(__bucket_count); 274 return std::make_pair(iterator(__res.first, this), __res.second); 275 } 276 277 template<typename... _Args> 278 iterator 279 emplace_hint(const_iterator __hint, _Args&&... __args) 280 { 281 __glibcxx_check_insert(__hint); 282 size_type __bucket_count = this->bucket_count(); 283 _Base_iterator __it = _Base::emplace_hint(__hint.base(), 284 std::forward<_Args>(__args)...); 285 _M_check_rehashed(__bucket_count); 286 return iterator(__it, this); 287 } 288 289 std::pair<iterator, bool> 290 insert(const value_type& __obj) 291 { 292 size_type __bucket_count = this->bucket_count(); 293 typedef std::pair<_Base_iterator, bool> __pair_type; 294 __pair_type __res = _Base::insert(__obj); 295 _M_check_rehashed(__bucket_count); 296 return std::make_pair(iterator(__res.first, this), __res.second); 297 } 298 299 iterator 300 insert(const_iterator __hint, const value_type& __obj) 301 { 302 __glibcxx_check_insert(__hint); 303 size_type __bucket_count = this->bucket_count(); 304 _Base_iterator __it = _Base::insert(__hint.base(), __obj); 305 _M_check_rehashed(__bucket_count); 306 return iterator(__it, this); 307 } 308 309 std::pair<iterator, bool> 310 insert(value_type&& __obj) 311 { 312 size_type __bucket_count = this->bucket_count(); 313 typedef std::pair<typename _Base::iterator, bool> __pair_type; 314 __pair_type __res = _Base::insert(std::move(__obj)); 315 _M_check_rehashed(__bucket_count); 316 return std::make_pair(iterator(__res.first, this), __res.second); 317 } 318 319 iterator 320 insert(const_iterator __hint, value_type&& __obj) 321 { 322 __glibcxx_check_insert(__hint); 323 size_type __bucket_count = this->bucket_count(); 324 _Base_iterator __it = _Base::insert(__hint.base(), std::move(__obj)); 325 _M_check_rehashed(__bucket_count); 326 return iterator(__it, this); 327 } 328 329 void 330 insert(std::initializer_list<value_type> __l) 331 { 332 size_type __bucket_count = this->bucket_count(); 333 _Base::insert(__l); 334 _M_check_rehashed(__bucket_count); 335 } 336 337 template<typename _InputIterator> 338 void 339 insert(_InputIterator __first, _InputIterator __last) 340 { 341 __glibcxx_check_valid_range(__first, __last); 342 size_type __bucket_count = this->bucket_count(); 343 _Base::insert(__gnu_debug::__base(__first), 344 __gnu_debug::__base(__last)); 345 _M_check_rehashed(__bucket_count); 346 } 347 348 iterator 349 find(const key_type& __key) 350 { return iterator(_Base::find(__key), this); } 351 352 const_iterator 353 find(const key_type& __key) const 354 { return const_iterator(_Base::find(__key), this); } 355 356 std::pair<iterator, iterator> 357 equal_range(const key_type& __key) 358 { 359 typedef std::pair<_Base_iterator, _Base_iterator> __pair_type; 360 __pair_type __res = _Base::equal_range(__key); 361 return std::make_pair(iterator(__res.first, this), 362 iterator(__res.second, this)); 363 } 364 365 std::pair<const_iterator, const_iterator> 366 equal_range(const key_type& __key) const 367 { 368 std::pair<_Base_const_iterator, _Base_const_iterator> 369 __res = _Base::equal_range(__key); 370 return std::make_pair(const_iterator(__res.first, this), 371 const_iterator(__res.second, this)); 372 } 373 374 size_type 375 erase(const key_type& __key) 376 { 377 size_type __ret(0); 378 _Base_iterator __victim(_Base::find(__key)); 379 if (__victim != _Base::end()) 380 { 381 this->_M_invalidate_if( 382 [__victim](_Base_const_iterator __it) 383 { return __it == __victim; }); 384 this->_M_invalidate_local_if( 385 [__victim](_Base_const_local_iterator __it) 386 { return __it._M_curr() == __victim._M_cur; }); 387 size_type __bucket_count = this->bucket_count(); 388 _Base::erase(__victim); 389 _M_check_rehashed(__bucket_count); 390 __ret = 1; 391 } 392 return __ret; 393 } 394 395 iterator 396 erase(const_iterator __it) 397 { 398 __glibcxx_check_erase(__it); 399 _Base_const_iterator __victim = __it.base(); 400 this->_M_invalidate_if( 401 [__victim](_Base_const_iterator __it) 402 { return __it == __victim; }); 403 this->_M_invalidate_local_if( 404 [__victim](_Base_const_local_iterator __it) 405 { return __it._M_curr() == __victim._M_cur; }); 406 size_type __bucket_count = this->bucket_count(); 407 _Base_iterator __next = _Base::erase(__it.base()); 408 _M_check_rehashed(__bucket_count); 409 return iterator(__next, this); 410 } 411 412 iterator 413 erase(iterator __it) 414 { return erase(const_iterator(__it)); } 415 416 iterator 417 erase(const_iterator __first, const_iterator __last) 418 { 419 __glibcxx_check_erase_range(__first, __last); 420 for (_Base_const_iterator __tmp = __first.base(); 421 __tmp != __last.base(); ++__tmp) 422 { 423 _GLIBCXX_DEBUG_VERIFY(__tmp != _Base::end(), 424 _M_message(__gnu_debug::__msg_valid_range) 425 ._M_iterator(__first, "first") 426 ._M_iterator(__last, "last")); 427 this->_M_invalidate_if( 428 [__tmp](_Base_const_iterator __it) 429 { return __it == __tmp; }); 430 this->_M_invalidate_local_if( 431 [__tmp](_Base_const_local_iterator __it) 432 { return __it._M_curr() == __tmp._M_cur; }); 433 } 434 size_type __bucket_count = this->bucket_count(); 435 _Base_iterator __next = _Base::erase(__first.base(), 436 __last.base()); 437 _M_check_rehashed(__bucket_count); 438 return iterator(__next, this); 439 } 440 441 _Base& 442 _M_base() noexcept { return *this; } 443 444 const _Base& 445 _M_base() const noexcept { return *this; } 446 447 private: 448 void 449 _M_invalidate_locals() 450 { 451 _Base_local_iterator __local_end = _Base::end(0); 452 this->_M_invalidate_local_if( 453 [__local_end](_Base_const_local_iterator __it) 454 { return __it != __local_end; }); 455 } 456 457 void 458 _M_invalidate_all() 459 { 460 _Base_iterator __end = _Base::end(); 461 this->_M_invalidate_if( 462 [__end](_Base_const_iterator __it) 463 { return __it != __end; }); 464 _M_invalidate_locals(); 465 } 466 467 void 468 _M_check_rehashed(size_type __prev_count) 469 { 470 if (__prev_count != this->bucket_count()) 471 _M_invalidate_locals(); 472 } 473 }; 474 475 template<typename _Value, typename _Hash, typename _Pred, typename _Alloc> 476 inline void 477 swap(unordered_set<_Value, _Hash, _Pred, _Alloc>& __x, 478 unordered_set<_Value, _Hash, _Pred, _Alloc>& __y) 479 { __x.swap(__y); } 480 481 template<typename _Value, typename _Hash, typename _Pred, typename _Alloc> 482 inline bool 483 operator==(const unordered_set<_Value, _Hash, _Pred, _Alloc>& __x, 484 const unordered_set<_Value, _Hash, _Pred, _Alloc>& __y) 485 { return __x._M_base() == __y._M_base(); } 486 487 template<typename _Value, typename _Hash, typename _Pred, typename _Alloc> 488 inline bool 489 operator!=(const unordered_set<_Value, _Hash, _Pred, _Alloc>& __x, 490 const unordered_set<_Value, _Hash, _Pred, _Alloc>& __y) 491 { return !(__x == __y); } 492 493 494 /// Class std::unordered_multiset with safety/checking/debug instrumentation. 495 template<typename _Value, 496 typename _Hash = std::hash<_Value>, 497 typename _Pred = std::equal_to<_Value>, 498 typename _Alloc = std::allocator<_Value> > 499 class unordered_multiset 500 : public _GLIBCXX_STD_C::unordered_multiset<_Value, _Hash, _Pred, _Alloc>, 501 public __gnu_debug::_Safe_unordered_container< 502 unordered_multiset<_Value, _Hash, _Pred, _Alloc> > 503 { 504 typedef _GLIBCXX_STD_C::unordered_multiset<_Value, _Hash, 505 _Pred, _Alloc> _Base; 506 typedef __gnu_debug::_Safe_unordered_container<unordered_multiset> 507 _Safe_base; 508 typedef typename _Base::const_iterator _Base_const_iterator; 509 typedef typename _Base::iterator _Base_iterator; 510 typedef typename _Base::const_local_iterator _Base_const_local_iterator; 511 typedef typename _Base::local_iterator _Base_local_iterator; 512 513 typedef __gnu_cxx::__alloc_traits<typename 514 _Base::allocator_type> _Alloc_traits; 515 516 public: 517 typedef typename _Base::size_type size_type; 518 typedef typename _Base::hasher hasher; 519 typedef typename _Base::key_equal key_equal; 520 typedef typename _Base::allocator_type allocator_type; 521 522 typedef typename _Base::key_type key_type; 523 typedef typename _Base::value_type value_type; 524 525 typedef __gnu_debug::_Safe_iterator<_Base_iterator, 526 unordered_multiset> iterator; 527 typedef __gnu_debug::_Safe_iterator<_Base_const_iterator, 528 unordered_multiset> const_iterator; 529 typedef __gnu_debug::_Safe_local_iterator< 530 _Base_local_iterator, unordered_multiset> local_iterator; 531 typedef __gnu_debug::_Safe_local_iterator< 532 _Base_const_local_iterator, unordered_multiset> const_local_iterator; 533 534 explicit 535 unordered_multiset(size_type __n = 10, 536 const hasher& __hf = hasher(), 537 const key_equal& __eql = key_equal(), 538 const allocator_type& __a = allocator_type()) 539 : _Base(__n, __hf, __eql, __a) { } 540 541 template<typename _InputIterator> 542 unordered_multiset(_InputIterator __first, _InputIterator __last, 543 size_type __n = 0, 544 const hasher& __hf = hasher(), 545 const key_equal& __eql = key_equal(), 546 const allocator_type& __a = allocator_type()) 547 : _Base(__gnu_debug::__base(__gnu_debug::__check_valid_range(__first, 548 __last)), 549 __gnu_debug::__base(__last), __n, 550 __hf, __eql, __a) { } 551 552 unordered_multiset(const unordered_multiset&) = default; 553 554 unordered_multiset(const _Base& __x) 555 : _Base(__x) { } 556 557 unordered_multiset(unordered_multiset&&) = default; 558 559 explicit 560 unordered_multiset(const allocator_type& __a) 561 : _Base(__a) 562 { } 563 564 unordered_multiset(const unordered_multiset& __uset, 565 const allocator_type& __a) 566 : _Base(__uset._M_base(), __a) 567 { } 568 569 unordered_multiset(unordered_multiset&& __uset, 570 const allocator_type& __a) 571 : _Base(std::move(__uset._M_base()), __a) 572 { } 573 574 unordered_multiset(initializer_list<value_type> __l, 575 size_type __n = 0, 576 const hasher& __hf = hasher(), 577 const key_equal& __eql = key_equal(), 578 const allocator_type& __a = allocator_type()) 579 : _Base(__l, __n, __hf, __eql, __a) { } 580 581 ~unordered_multiset() noexcept { } 582 583 unordered_multiset& 584 operator=(const unordered_multiset& __x) 585 { 586 _M_base() = __x._M_base(); 587 this->_M_invalidate_all(); 588 return *this; 589 } 590 591 unordered_multiset& 592 operator=(unordered_multiset&& __x) 593 noexcept(_Alloc_traits::_S_nothrow_move()) 594 { 595 __glibcxx_check_self_move_assign(__x); 596 bool __xfer_memory = _Alloc_traits::_S_propagate_on_move_assign() 597 || __x.get_allocator() == this->get_allocator(); 598 _M_base() = std::move(__x._M_base()); 599 if (__xfer_memory) 600 this->_M_swap(__x); 601 else 602 this->_M_invalidate_all(); 603 __x._M_invalidate_all(); 604 return *this; 605 } 606 607 unordered_multiset& 608 operator=(initializer_list<value_type> __l) 609 { 610 _M_base() = __l; 611 this->_M_invalidate_all(); 612 return *this; 613 } 614 615 void 616 swap(unordered_multiset& __x) 617 noexcept(_Alloc_traits::_S_nothrow_swap()) 618 { 619 if (!_Alloc_traits::_S_propagate_on_swap()) 620 __glibcxx_check_equal_allocs(__x); 621 _Base::swap(__x); 622 _Safe_base::_M_swap(__x); 623 } 624 625 void 626 clear() noexcept 627 { 628 _Base::clear(); 629 this->_M_invalidate_all(); 630 } 631 632 iterator 633 begin() noexcept 634 { return iterator(_Base::begin(), this); } 635 636 const_iterator 637 begin() const noexcept 638 { return const_iterator(_Base::begin(), this); } 639 640 iterator 641 end() noexcept 642 { return iterator(_Base::end(), this); } 643 644 const_iterator 645 end() const noexcept 646 { return const_iterator(_Base::end(), this); } 647 648 const_iterator 649 cbegin() const noexcept 650 { return const_iterator(_Base::begin(), this); } 651 652 const_iterator 653 cend() const noexcept 654 { return const_iterator(_Base::end(), this); } 655 656 // local versions 657 local_iterator 658 begin(size_type __b) 659 { 660 __glibcxx_check_bucket_index(__b); 661 return local_iterator(_Base::begin(__b), this); 662 } 663 664 local_iterator 665 end(size_type __b) 666 { 667 __glibcxx_check_bucket_index(__b); 668 return local_iterator(_Base::end(__b), this); 669 } 670 671 const_local_iterator 672 begin(size_type __b) const 673 { 674 __glibcxx_check_bucket_index(__b); 675 return const_local_iterator(_Base::begin(__b), this); 676 } 677 678 const_local_iterator 679 end(size_type __b) const 680 { 681 __glibcxx_check_bucket_index(__b); 682 return const_local_iterator(_Base::end(__b), this); 683 } 684 685 const_local_iterator 686 cbegin(size_type __b) const 687 { 688 __glibcxx_check_bucket_index(__b); 689 return const_local_iterator(_Base::cbegin(__b), this); 690 } 691 692 const_local_iterator 693 cend(size_type __b) const 694 { 695 __glibcxx_check_bucket_index(__b); 696 return const_local_iterator(_Base::cend(__b), this); 697 } 698 699 size_type 700 bucket_size(size_type __b) const 701 { 702 __glibcxx_check_bucket_index(__b); 703 return _Base::bucket_size(__b); 704 } 705 706 float 707 max_load_factor() const noexcept 708 { return _Base::max_load_factor(); } 709 710 void 711 max_load_factor(float __f) 712 { 713 __glibcxx_check_max_load_factor(__f); 714 _Base::max_load_factor(__f); 715 } 716 717 template<typename... _Args> 718 iterator 719 emplace(_Args&&... __args) 720 { 721 size_type __bucket_count = this->bucket_count(); 722 _Base_iterator __it 723 = _Base::emplace(std::forward<_Args>(__args)...); 724 _M_check_rehashed(__bucket_count); 725 return iterator(__it, this); 726 } 727 728 template<typename... _Args> 729 iterator 730 emplace_hint(const_iterator __hint, _Args&&... __args) 731 { 732 __glibcxx_check_insert(__hint); 733 size_type __bucket_count = this->bucket_count(); 734 _Base_iterator __it = _Base::emplace_hint(__hint.base(), 735 std::forward<_Args>(__args)...); 736 _M_check_rehashed(__bucket_count); 737 return iterator(__it, this); 738 } 739 740 iterator 741 insert(const value_type& __obj) 742 { 743 size_type __bucket_count = this->bucket_count(); 744 _Base_iterator __it = _Base::insert(__obj); 745 _M_check_rehashed(__bucket_count); 746 return iterator(__it, this); 747 } 748 749 iterator 750 insert(const_iterator __hint, const value_type& __obj) 751 { 752 __glibcxx_check_insert(__hint); 753 size_type __bucket_count = this->bucket_count(); 754 _Base_iterator __it = _Base::insert(__hint.base(), __obj); 755 _M_check_rehashed(__bucket_count); 756 return iterator(__it, this); 757 } 758 759 iterator 760 insert(value_type&& __obj) 761 { 762 size_type __bucket_count = this->bucket_count(); 763 _Base_iterator __it = _Base::insert(std::move(__obj)); 764 _M_check_rehashed(__bucket_count); 765 return iterator(__it, this); 766 } 767 768 iterator 769 insert(const_iterator __hint, value_type&& __obj) 770 { 771 __glibcxx_check_insert(__hint); 772 size_type __bucket_count = this->bucket_count(); 773 _Base_iterator __it = _Base::insert(__hint.base(), std::move(__obj)); 774 _M_check_rehashed(__bucket_count); 775 return iterator(__it, this); 776 } 777 778 void 779 insert(std::initializer_list<value_type> __l) 780 { 781 size_type __bucket_count = this->bucket_count(); 782 _Base::insert(__l); 783 _M_check_rehashed(__bucket_count); 784 } 785 786 template<typename _InputIterator> 787 void 788 insert(_InputIterator __first, _InputIterator __last) 789 { 790 __glibcxx_check_valid_range(__first, __last); 791 size_type __bucket_count = this->bucket_count(); 792 _Base::insert(__gnu_debug::__base(__first), 793 __gnu_debug::__base(__last)); 794 _M_check_rehashed(__bucket_count); 795 } 796 797 iterator 798 find(const key_type& __key) 799 { return iterator(_Base::find(__key), this); } 800 801 const_iterator 802 find(const key_type& __key) const 803 { return const_iterator(_Base::find(__key), this); } 804 805 std::pair<iterator, iterator> 806 equal_range(const key_type& __key) 807 { 808 typedef std::pair<_Base_iterator, _Base_iterator> __pair_type; 809 __pair_type __res = _Base::equal_range(__key); 810 return std::make_pair(iterator(__res.first, this), 811 iterator(__res.second, this)); 812 } 813 814 std::pair<const_iterator, const_iterator> 815 equal_range(const key_type& __key) const 816 { 817 std::pair<_Base_const_iterator, _Base_const_iterator> 818 __res = _Base::equal_range(__key); 819 return std::make_pair(const_iterator(__res.first, this), 820 const_iterator(__res.second, this)); 821 } 822 823 size_type 824 erase(const key_type& __key) 825 { 826 size_type __ret(0); 827 std::pair<_Base_iterator, _Base_iterator> __pair = 828 _Base::equal_range(__key); 829 for (_Base_iterator __victim = __pair.first; __victim != __pair.second;) 830 { 831 this->_M_invalidate_if([__victim](_Base_const_iterator __it) 832 { return __it == __victim; }); 833 this->_M_invalidate_local_if( 834 [__victim](_Base_const_local_iterator __it) 835 { return __it._M_curr() == __victim._M_cur; }); 836 _Base::erase(__victim++); 837 ++__ret; 838 } 839 return __ret; 840 } 841 842 iterator 843 erase(const_iterator __it) 844 { 845 __glibcxx_check_erase(__it); 846 _Base_const_iterator __victim = __it.base(); 847 this->_M_invalidate_if([__victim](_Base_const_iterator __it) 848 { return __it == __victim; }); 849 this->_M_invalidate_local_if( 850 [__victim](_Base_const_local_iterator __it) 851 { return __it._M_curr() == __victim._M_cur; }); 852 return iterator(_Base::erase(__it.base()), this); 853 } 854 855 iterator 856 erase(iterator __it) 857 { return erase(const_iterator(__it)); } 858 859 iterator 860 erase(const_iterator __first, const_iterator __last) 861 { 862 __glibcxx_check_erase_range(__first, __last); 863 for (_Base_const_iterator __tmp = __first.base(); 864 __tmp != __last.base(); ++__tmp) 865 { 866 _GLIBCXX_DEBUG_VERIFY(__tmp != _Base::end(), 867 _M_message(__gnu_debug::__msg_valid_range) 868 ._M_iterator(__first, "first") 869 ._M_iterator(__last, "last")); 870 this->_M_invalidate_if([__tmp](_Base_const_iterator __it) 871 { return __it == __tmp; }); 872 this->_M_invalidate_local_if( 873 [__tmp](_Base_const_local_iterator __it) 874 { return __it._M_curr() == __tmp._M_cur; }); 875 } 876 return iterator(_Base::erase(__first.base(), 877 __last.base()), this); 878 } 879 880 _Base& 881 _M_base() noexcept { return *this; } 882 883 const _Base& 884 _M_base() const noexcept { return *this; } 885 886 private: 887 void 888 _M_invalidate_locals() 889 { 890 _Base_local_iterator __local_end = _Base::end(0); 891 this->_M_invalidate_local_if( 892 [__local_end](_Base_const_local_iterator __it) 893 { return __it != __local_end; }); 894 } 895 896 void 897 _M_invalidate_all() 898 { 899 _Base_iterator __end = _Base::end(); 900 this->_M_invalidate_if([__end](_Base_const_iterator __it) 901 { return __it != __end; }); 902 _M_invalidate_locals(); 903 } 904 905 void 906 _M_check_rehashed(size_type __prev_count) 907 { 908 if (__prev_count != this->bucket_count()) 909 _M_invalidate_locals(); 910 } 911 }; 912 913 template<typename _Value, typename _Hash, typename _Pred, typename _Alloc> 914 inline void 915 swap(unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x, 916 unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y) 917 { __x.swap(__y); } 918 919 template<typename _Value, typename _Hash, typename _Pred, typename _Alloc> 920 inline bool 921 operator==(const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x, 922 const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y) 923 { return __x._M_base() == __y._M_base(); } 924 925 template<typename _Value, typename _Hash, typename _Pred, typename _Alloc> 926 inline bool 927 operator!=(const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x, 928 const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y) 929 { return !(__x == __y); } 930 931 } // namespace __debug 932 } // namespace std 933 934 #endif // C++11 935 936 #endif 937
