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