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