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