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