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