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