1// Debugging unordered_map/unordered_multimap implementation -*- C++ -*- 2 3// Copyright (C) 2003-2014 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<std::pair<const _Key, _Tp> > > 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 typedef __gnu_cxx::__alloc_traits<typename 64 _Base::allocator_type> _Alloc_traits; 65 66 public: 67 typedef typename _Base::size_type size_type; 68 typedef typename _Base::hasher hasher; 69 typedef typename _Base::key_equal key_equal; 70 typedef typename _Base::allocator_type allocator_type; 71 72 typedef typename _Base::key_type key_type; 73 typedef typename _Base::value_type value_type; 74 75 typedef __gnu_debug::_Safe_iterator<_Base_iterator, 76 unordered_map> iterator; 77 typedef __gnu_debug::_Safe_iterator<_Base_const_iterator, 78 unordered_map> const_iterator; 79 typedef __gnu_debug::_Safe_local_iterator<_Base_local_iterator, 80 unordered_map> local_iterator; 81 typedef __gnu_debug::_Safe_local_iterator<_Base_const_local_iterator, 82 unordered_map> const_local_iterator; 83 84 explicit 85 unordered_map(size_type __n = 10, 86 const hasher& __hf = hasher(), 87 const key_equal& __eql = key_equal(), 88 const allocator_type& __a = allocator_type()) 89 : _Base(__n, __hf, __eql, __a) { } 90 91 template<typename _InputIterator> 92 unordered_map(_InputIterator __first, _InputIterator __last, 93 size_type __n = 0, 94 const hasher& __hf = hasher(), 95 const key_equal& __eql = key_equal(), 96 const allocator_type& __a = allocator_type()) 97 : _Base(__gnu_debug::__base(__gnu_debug::__check_valid_range(__first, 98 __last)), 99 __gnu_debug::__base(__last), __n, 100 __hf, __eql, __a) { } 101 102 unordered_map(const unordered_map&) = default; 103 104 unordered_map(const _Base& __x) 105 : _Base(__x) { } 106 107 unordered_map(unordered_map&&) = default; 108 109 explicit 110 unordered_map(const allocator_type& __a) 111 : _Base(__a) 112 { } 113 114 unordered_map(const unordered_map& __umap, 115 const allocator_type& __a) 116 : _Base(__umap._M_base(), __a) 117 { } 118 119 unordered_map(unordered_map&& __umap, 120 const allocator_type& __a) 121 : _Base(std::move(__umap._M_base()), __a) 122 { } 123 124 unordered_map(initializer_list<value_type> __l, 125 size_type __n = 0, 126 const hasher& __hf = hasher(), 127 const key_equal& __eql = key_equal(), 128 const allocator_type& __a = allocator_type()) 129 : _Base(__l, __n, __hf, __eql, __a) { } 130 131 ~unordered_map() noexcept { } 132 133 unordered_map& 134 operator=(const unordered_map& __x) 135 { 136 _M_base() = __x._M_base(); 137 this->_M_invalidate_all(); 138 return *this; 139 } 140 141 unordered_map& 142 operator=(unordered_map&& __x) 143 noexcept(_Alloc_traits::_S_nothrow_move()) 144 { 145 __glibcxx_check_self_move_assign(__x); 146 bool __xfer_memory = _Alloc_traits::_S_propagate_on_move_assign() 147 || __x.get_allocator() == this->get_allocator(); 148 _M_base() = std::move(__x._M_base()); 149 if (__xfer_memory) 150 this->_M_swap(__x); 151 else 152 this->_M_invalidate_all(); 153 __x._M_invalidate_all(); 154 return *this; 155 } 156 157 unordered_map& 158 operator=(initializer_list<value_type> __l) 159 { 160 _M_base() = __l; 161 this->_M_invalidate_all(); 162 return *this; 163 } 164 165 void 166 swap(unordered_map& __x) 167 noexcept(_Alloc_traits::_S_nothrow_swap()) 168 { 169 if (!_Alloc_traits::_S_propagate_on_swap()) 170 __glibcxx_check_equal_allocs(__x); 171 _Base::swap(__x); 172 _Safe_base::_M_swap(__x); 173 } 174 175 void 176 clear() noexcept 177 { 178 _Base::clear(); 179 this->_M_invalidate_all(); 180 } 181 182 iterator 183 begin() noexcept 184 { return iterator(_Base::begin(), this); } 185 186 const_iterator 187 begin() const noexcept 188 { return const_iterator(_Base::begin(), this); } 189 190 iterator 191 end() noexcept 192 { return iterator(_Base::end(), this); } 193 194 const_iterator 195 end() const noexcept 196 { return const_iterator(_Base::end(), this); } 197 198 const_iterator 199 cbegin() const noexcept 200 { return const_iterator(_Base::begin(), this); } 201 202 const_iterator 203 cend() const noexcept 204 { return const_iterator(_Base::end(), this); } 205 206 // local versions 207 local_iterator 208 begin(size_type __b) 209 { 210 __glibcxx_check_bucket_index(__b); 211 return local_iterator(_Base::begin(__b), this); 212 } 213 214 local_iterator 215 end(size_type __b) 216 { 217 __glibcxx_check_bucket_index(__b); 218 return local_iterator(_Base::end(__b), this); 219 } 220 221 const_local_iterator 222 begin(size_type __b) const 223 { 224 __glibcxx_check_bucket_index(__b); 225 return const_local_iterator(_Base::begin(__b), this); 226 } 227 228 const_local_iterator 229 end(size_type __b) const 230 { 231 __glibcxx_check_bucket_index(__b); 232 return const_local_iterator(_Base::end(__b), this); 233 } 234 235 const_local_iterator 236 cbegin(size_type __b) const 237 { 238 __glibcxx_check_bucket_index(__b); 239 return const_local_iterator(_Base::cbegin(__b), this); 240 } 241 242 const_local_iterator 243 cend(size_type __b) const 244 { 245 __glibcxx_check_bucket_index(__b); 246 return const_local_iterator(_Base::cend(__b), this); 247 } 248 249 size_type 250 bucket_size(size_type __b) const 251 { 252 __glibcxx_check_bucket_index(__b); 253 return _Base::bucket_size(__b); 254 } 255 256 float 257 max_load_factor() const noexcept 258 { return _Base::max_load_factor(); } 259 260 void 261 max_load_factor(float __f) 262 { 263 __glibcxx_check_max_load_factor(__f); 264 _Base::max_load_factor(__f); 265 } 266 267 template<typename... _Args> 268 std::pair<iterator, bool> 269 emplace(_Args&&... __args) 270 { 271 size_type __bucket_count = this->bucket_count(); 272 std::pair<_Base_iterator, bool> __res 273 = _Base::emplace(std::forward<_Args>(__args)...); 274 _M_check_rehashed(__bucket_count); 275 return std::make_pair(iterator(__res.first, this), __res.second); 276 } 277 278 template<typename... _Args> 279 iterator 280 emplace_hint(const_iterator __hint, _Args&&... __args) 281 { 282 __glibcxx_check_insert(__hint); 283 size_type __bucket_count = this->bucket_count(); 284 _Base_iterator __it = _Base::emplace_hint(__hint.base(), 285 std::forward<_Args>(__args)...); 286 _M_check_rehashed(__bucket_count); 287 return iterator(__it, this); 288 } 289 290 std::pair<iterator, bool> 291 insert(const value_type& __obj) 292 { 293 size_type __bucket_count = this->bucket_count(); 294 std::pair<_Base_iterator, bool> __res = _Base::insert(__obj); 295 _M_check_rehashed(__bucket_count); 296 return std::make_pair(iterator(__res.first, this), __res.second); 297 } 298 299 iterator 300 insert(const_iterator __hint, const value_type& __obj) 301 { 302 __glibcxx_check_insert(__hint); 303 size_type __bucket_count = this->bucket_count(); 304 _Base_iterator __it = _Base::insert(__hint.base(), __obj); 305 _M_check_rehashed(__bucket_count); 306 return iterator(__it, this); 307 } 308 309 template<typename _Pair, typename = typename 310 std::enable_if<std::is_constructible<value_type, 311 _Pair&&>::value>::type> 312 std::pair<iterator, bool> 313 insert(_Pair&& __obj) 314 { 315 size_type __bucket_count = this->bucket_count(); 316 std::pair<_Base_iterator, bool> __res = 317 _Base::insert(std::forward<_Pair>(__obj)); 318 _M_check_rehashed(__bucket_count); 319 return std::make_pair(iterator(__res.first, this), __res.second); 320 } 321 322 template<typename _Pair, typename = typename 323 std::enable_if<std::is_constructible<value_type, 324 _Pair&&>::value>::type> 325 iterator 326 insert(const_iterator __hint, _Pair&& __obj) 327 { 328 __glibcxx_check_insert(__hint); 329 size_type __bucket_count = this->bucket_count(); 330 _Base_iterator __it = 331 _Base::insert(__hint.base(), std::forward<_Pair>(__obj)); 332 _M_check_rehashed(__bucket_count); 333 return iterator(__it, this); 334 } 335 336 void 337 insert(std::initializer_list<value_type> __l) 338 { 339 size_type __bucket_count = this->bucket_count(); 340 _Base::insert(__l); 341 _M_check_rehashed(__bucket_count); 342 } 343 344 template<typename _InputIterator> 345 void 346 insert(_InputIterator __first, _InputIterator __last) 347 { 348 __glibcxx_check_valid_range(__first, __last); 349 size_type __bucket_count = this->bucket_count(); 350 _Base::insert(__gnu_debug::__base(__first), 351 __gnu_debug::__base(__last)); 352 _M_check_rehashed(__bucket_count); 353 } 354 355 iterator 356 find(const key_type& __key) 357 { return iterator(_Base::find(__key), this); } 358 359 const_iterator 360 find(const key_type& __key) const 361 { return const_iterator(_Base::find(__key), this); } 362 363 std::pair<iterator, iterator> 364 equal_range(const key_type& __key) 365 { 366 std::pair<_Base_iterator, _Base_iterator> __res = 367 _Base::equal_range(__key); 368 return std::make_pair(iterator(__res.first, this), 369 iterator(__res.second, this)); 370 } 371 372 std::pair<const_iterator, const_iterator> 373 equal_range(const key_type& __key) const 374 { 375 std::pair<_Base_const_iterator, _Base_const_iterator> __res = 376 _Base::equal_range(__key); 377 return std::make_pair(const_iterator(__res.first, this), 378 const_iterator(__res.second, this)); 379 } 380 381 size_type 382 erase(const key_type& __key) 383 { 384 size_type __ret(0); 385 _Base_iterator __victim(_Base::find(__key)); 386 if (__victim != _Base::end()) 387 { 388 this->_M_invalidate_if([__victim](_Base_const_iterator __it) 389 { return __it == __victim; }); 390 this->_M_invalidate_local_if( 391 [__victim](_Base_const_local_iterator __it) 392 { return __it._M_curr() == __victim._M_cur; }); 393 size_type __bucket_count = this->bucket_count(); 394 _Base::erase(__victim); 395 _M_check_rehashed(__bucket_count); 396 __ret = 1; 397 } 398 return __ret; 399 } 400 401 iterator 402 erase(const_iterator __it) 403 { 404 __glibcxx_check_erase(__it); 405 _Base_const_iterator __victim = __it.base(); 406 this->_M_invalidate_if([__victim](_Base_const_iterator __it) 407 { return __it == __victim; }); 408 this->_M_invalidate_local_if( 409 [__victim](_Base_const_local_iterator __it) 410 { return __it._M_curr() == __victim._M_cur; }); 411 size_type __bucket_count = this->bucket_count(); 412 _Base_iterator __next = _Base::erase(__it.base()); 413 _M_check_rehashed(__bucket_count); 414 return iterator(__next, this); 415 } 416 417 iterator 418 erase(iterator __it) 419 { return erase(const_iterator(__it)); } 420 421 iterator 422 erase(const_iterator __first, const_iterator __last) 423 { 424 __glibcxx_check_erase_range(__first, __last); 425 for (_Base_const_iterator __tmp = __first.base(); 426 __tmp != __last.base(); ++__tmp) 427 { 428 _GLIBCXX_DEBUG_VERIFY(__tmp != _Base::end(), 429 _M_message(__gnu_debug::__msg_valid_range) 430 ._M_iterator(__first, "first") 431 ._M_iterator(__last, "last")); 432 this->_M_invalidate_if([__tmp](_Base_const_iterator __it) 433 { return __it == __tmp; }); 434 this->_M_invalidate_local_if( 435 [__tmp](_Base_const_local_iterator __it) 436 { return __it._M_curr() == __tmp._M_cur; }); 437 } 438 size_type __bucket_count = this->bucket_count(); 439 _Base_iterator __next = _Base::erase(__first.base(), __last.base()); 440 _M_check_rehashed(__bucket_count); 441 return iterator(__next, this); 442 } 443 444 _Base& 445 _M_base() noexcept { return *this; } 446 447 const _Base& 448 _M_base() const noexcept { return *this; } 449 450 private: 451 void 452 _M_invalidate_locals() 453 { 454 _Base_local_iterator __local_end = _Base::end(0); 455 this->_M_invalidate_local_if( 456 [__local_end](_Base_const_local_iterator __it) 457 { return __it != __local_end; }); 458 } 459 460 void 461 _M_invalidate_all() 462 { 463 _Base_iterator __end = _Base::end(); 464 this->_M_invalidate_if([__end](_Base_const_iterator __it) 465 { return __it != __end; }); 466 _M_invalidate_locals(); 467 } 468 469 void 470 _M_check_rehashed(size_type __prev_count) 471 { 472 if (__prev_count != this->bucket_count()) 473 _M_invalidate_locals(); 474 } 475 }; 476 477 template<typename _Key, typename _Tp, typename _Hash, 478 typename _Pred, typename _Alloc> 479 inline void 480 swap(unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, 481 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) 482 { __x.swap(__y); } 483 484 template<typename _Key, typename _Tp, typename _Hash, 485 typename _Pred, typename _Alloc> 486 inline bool 487 operator==(const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, 488 const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) 489 { return __x._M_base() == __y._M_base(); } 490 491 template<typename _Key, typename _Tp, typename _Hash, 492 typename _Pred, typename _Alloc> 493 inline bool 494 operator!=(const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, 495 const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) 496 { return !(__x == __y); } 497 498 499 /// Class std::unordered_multimap with safety/checking/debug instrumentation. 500 template<typename _Key, typename _Tp, 501 typename _Hash = std::hash<_Key>, 502 typename _Pred = std::equal_to<_Key>, 503 typename _Alloc = std::allocator<std::pair<const _Key, _Tp> > > 504 class unordered_multimap 505 : public _GLIBCXX_STD_C::unordered_multimap<_Key, _Tp, _Hash, 506 _Pred, _Alloc>, 507 public __gnu_debug::_Safe_unordered_container<unordered_multimap<_Key, 508 _Tp, _Hash, _Pred, _Alloc> > 509 { 510 typedef _GLIBCXX_STD_C::unordered_multimap<_Key, _Tp, _Hash, 511 _Pred, _Alloc> _Base; 512 typedef __gnu_debug::_Safe_unordered_container<unordered_multimap> 513 _Safe_base; 514 typedef typename _Base::const_iterator _Base_const_iterator; 515 typedef typename _Base::iterator _Base_iterator; 516 typedef typename _Base::const_local_iterator _Base_const_local_iterator; 517 typedef typename _Base::local_iterator _Base_local_iterator; 518 519 typedef __gnu_cxx::__alloc_traits<typename 520 _Base::allocator_type> _Alloc_traits; 521 522 public: 523 typedef typename _Base::size_type size_type; 524 typedef typename _Base::hasher hasher; 525 typedef typename _Base::key_equal key_equal; 526 typedef typename _Base::allocator_type allocator_type; 527 528 typedef typename _Base::key_type key_type; 529 typedef typename _Base::value_type value_type; 530 531 typedef __gnu_debug::_Safe_iterator<_Base_iterator, 532 unordered_multimap> iterator; 533 typedef __gnu_debug::_Safe_iterator<_Base_const_iterator, 534 unordered_multimap> const_iterator; 535 typedef __gnu_debug::_Safe_local_iterator< 536 _Base_local_iterator, unordered_multimap> local_iterator; 537 typedef __gnu_debug::_Safe_local_iterator< 538 _Base_const_local_iterator, unordered_multimap> const_local_iterator; 539 540 explicit 541 unordered_multimap(size_type __n = 10, 542 const hasher& __hf = hasher(), 543 const key_equal& __eql = key_equal(), 544 const allocator_type& __a = allocator_type()) 545 : _Base(__n, __hf, __eql, __a) { } 546 547 template<typename _InputIterator> 548 unordered_multimap(_InputIterator __first, _InputIterator __last, 549 size_type __n = 0, 550 const hasher& __hf = hasher(), 551 const key_equal& __eql = key_equal(), 552 const allocator_type& __a = allocator_type()) 553 : _Base(__gnu_debug::__base(__gnu_debug::__check_valid_range(__first, 554 __last)), 555 __gnu_debug::__base(__last), __n, 556 __hf, __eql, __a) { } 557 558 unordered_multimap(const unordered_multimap&) = default; 559 560 unordered_multimap(const _Base& __x) 561 : _Base(__x) { } 562 563 unordered_multimap(unordered_multimap&&) = default; 564 565 explicit 566 unordered_multimap(const allocator_type& __a) 567 : _Base(__a) 568 { } 569 570 unordered_multimap(const unordered_multimap& __umap, 571 const allocator_type& __a) 572 : _Base(__umap._M_base(), __a) 573 { } 574 575 unordered_multimap(unordered_multimap&& __umap, 576 const allocator_type& __a) 577 : _Base(std::move(__umap._M_base()), __a) 578 { } 579 580 unordered_multimap(initializer_list<value_type> __l, 581 size_type __n = 0, 582 const hasher& __hf = hasher(), 583 const key_equal& __eql = key_equal(), 584 const allocator_type& __a = allocator_type()) 585 : _Base(__l, __n, __hf, __eql, __a) { } 586 587 ~unordered_multimap() noexcept { } 588 589 unordered_multimap& 590 operator=(const unordered_multimap& __x) 591 { 592 _M_base() = __x._M_base(); 593 this->_M_invalidate_all(); 594 return *this; 595 } 596 597 unordered_multimap& 598 operator=(unordered_multimap&& __x) 599 noexcept(_Alloc_traits::_S_nothrow_move()) 600 { 601 __glibcxx_check_self_move_assign(__x); 602 bool __xfer_memory = _Alloc_traits::_S_propagate_on_move_assign() 603 || __x.get_allocator() == this->get_allocator(); 604 _M_base() = std::move(__x._M_base()); 605 if (__xfer_memory) 606 this->_M_swap(__x); 607 else 608 this->_M_invalidate_all(); 609 __x._M_invalidate_all(); 610 return *this; 611 } 612 613 unordered_multimap& 614 operator=(initializer_list<value_type> __l) 615 { 616 _M_base() = __l; 617 this->_M_invalidate_all(); 618 return *this; 619 } 620 621 void 622 swap(unordered_multimap& __x) 623 noexcept(_Alloc_traits::_S_nothrow_swap()) 624 { 625 if (!_Alloc_traits::_S_propagate_on_swap()) 626 __glibcxx_check_equal_allocs(__x); 627 _Base::swap(__x); 628 _Safe_base::_M_swap(__x); 629 } 630 631 void 632 clear() noexcept 633 { 634 _Base::clear(); 635 this->_M_invalidate_all(); 636 } 637 638 iterator 639 begin() noexcept 640 { return iterator(_Base::begin(), this); } 641 642 const_iterator 643 begin() const noexcept 644 { return const_iterator(_Base::begin(), this); } 645 646 iterator 647 end() noexcept 648 { return iterator(_Base::end(), this); } 649 650 const_iterator 651 end() const noexcept 652 { return const_iterator(_Base::end(), this); } 653 654 const_iterator 655 cbegin() const noexcept 656 { return const_iterator(_Base::begin(), this); } 657 658 const_iterator 659 cend() const noexcept 660 { return const_iterator(_Base::end(), this); } 661 662 // local versions 663 local_iterator 664 begin(size_type __b) 665 { 666 __glibcxx_check_bucket_index(__b); 667 return local_iterator(_Base::begin(__b), this); 668 } 669 670 local_iterator 671 end(size_type __b) 672 { 673 __glibcxx_check_bucket_index(__b); 674 return local_iterator(_Base::end(__b), this); 675 } 676 677 const_local_iterator 678 begin(size_type __b) const 679 { 680 __glibcxx_check_bucket_index(__b); 681 return const_local_iterator(_Base::begin(__b), this); 682 } 683 684 const_local_iterator 685 end(size_type __b) const 686 { 687 __glibcxx_check_bucket_index(__b); 688 return const_local_iterator(_Base::end(__b), this); 689 } 690 691 const_local_iterator 692 cbegin(size_type __b) const 693 { 694 __glibcxx_check_bucket_index(__b); 695 return const_local_iterator(_Base::cbegin(__b), this); 696 } 697 698 const_local_iterator 699 cend(size_type __b) const 700 { 701 __glibcxx_check_bucket_index(__b); 702 return const_local_iterator(_Base::cend(__b), this); 703 } 704 705 size_type 706 bucket_size(size_type __b) const 707 { 708 __glibcxx_check_bucket_index(__b); 709 return _Base::bucket_size(__b); 710 } 711 712 float 713 max_load_factor() const noexcept 714 { return _Base::max_load_factor(); } 715 716 void 717 max_load_factor(float __f) 718 { 719 __glibcxx_check_max_load_factor(__f); 720 _Base::max_load_factor(__f); 721 } 722 723 template<typename... _Args> 724 iterator 725 emplace(_Args&&... __args) 726 { 727 size_type __bucket_count = this->bucket_count(); 728 _Base_iterator __it 729 = _Base::emplace(std::forward<_Args>(__args)...); 730 _M_check_rehashed(__bucket_count); 731 return iterator(__it, this); 732 } 733 734 template<typename... _Args> 735 iterator 736 emplace_hint(const_iterator __hint, _Args&&... __args) 737 { 738 __glibcxx_check_insert(__hint); 739 size_type __bucket_count = this->bucket_count(); 740 _Base_iterator __it = _Base::emplace_hint(__hint.base(), 741 std::forward<_Args>(__args)...); 742 _M_check_rehashed(__bucket_count); 743 return iterator(__it, this); 744 } 745 746 iterator 747 insert(const value_type& __obj) 748 { 749 size_type __bucket_count = this->bucket_count(); 750 _Base_iterator __it = _Base::insert(__obj); 751 _M_check_rehashed(__bucket_count); 752 return iterator(__it, this); 753 } 754 755 iterator 756 insert(const_iterator __hint, const value_type& __obj) 757 { 758 __glibcxx_check_insert(__hint); 759 size_type __bucket_count = this->bucket_count(); 760 _Base_iterator __it = _Base::insert(__hint.base(), __obj); 761 _M_check_rehashed(__bucket_count); 762 return iterator(__it, this); 763 } 764 765 template<typename _Pair, typename = typename 766 std::enable_if<std::is_constructible<value_type, 767 _Pair&&>::value>::type> 768 iterator 769 insert(_Pair&& __obj) 770 { 771 size_type __bucket_count = this->bucket_count(); 772 _Base_iterator __it = _Base::insert(std::forward<_Pair>(__obj)); 773 _M_check_rehashed(__bucket_count); 774 return iterator(__it, this); 775 } 776 777 template<typename _Pair, typename = typename 778 std::enable_if<std::is_constructible<value_type, 779 _Pair&&>::value>::type> 780 iterator 781 insert(const_iterator __hint, _Pair&& __obj) 782 { 783 __glibcxx_check_insert(__hint); 784 size_type __bucket_count = this->bucket_count(); 785 _Base_iterator __it = 786 _Base::insert(__hint.base(), std::forward<_Pair>(__obj)); 787 _M_check_rehashed(__bucket_count); 788 return iterator(__it, this); 789 } 790 791 void 792 insert(std::initializer_list<value_type> __l) 793 { _Base::insert(__l); } 794 795 template<typename _InputIterator> 796 void 797 insert(_InputIterator __first, _InputIterator __last) 798 { 799 __glibcxx_check_valid_range(__first, __last); 800 size_type __bucket_count = this->bucket_count(); 801 _Base::insert(__gnu_debug::__base(__first), 802 __gnu_debug::__base(__last)); 803 _M_check_rehashed(__bucket_count); 804 } 805 806 iterator 807 find(const key_type& __key) 808 { return iterator(_Base::find(__key), this); } 809 810 const_iterator 811 find(const key_type& __key) const 812 { return const_iterator(_Base::find(__key), this); } 813 814 std::pair<iterator, iterator> 815 equal_range(const key_type& __key) 816 { 817 std::pair<_Base_iterator, _Base_iterator> __res = 818 _Base::equal_range(__key); 819 return std::make_pair(iterator(__res.first, this), 820 iterator(__res.second, this)); 821 } 822 823 std::pair<const_iterator, const_iterator> 824 equal_range(const key_type& __key) const 825 { 826 std::pair<_Base_const_iterator, _Base_const_iterator> __res = 827 _Base::equal_range(__key); 828 return std::make_pair(const_iterator(__res.first, this), 829 const_iterator(__res.second, this)); 830 } 831 832 size_type 833 erase(const key_type& __key) 834 { 835 size_type __ret(0); 836 size_type __bucket_count = this->bucket_count(); 837 std::pair<_Base_iterator, _Base_iterator> __pair = 838 _Base::equal_range(__key); 839 for (_Base_iterator __victim = __pair.first; __victim != __pair.second;) 840 { 841 this->_M_invalidate_if([__victim](_Base_const_iterator __it) 842 { return __it == __victim; }); 843 this->_M_invalidate_local_if( 844 [__victim](_Base_const_local_iterator __it) 845 { return __it._M_curr() == __victim._M_cur; }); 846 _Base::erase(__victim++); 847 ++__ret; 848 } 849 _M_check_rehashed(__bucket_count); 850 return __ret; 851 } 852 853 iterator 854 erase(const_iterator __it) 855 { 856 __glibcxx_check_erase(__it); 857 _Base_const_iterator __victim = __it.base(); 858 this->_M_invalidate_if([__victim](_Base_const_iterator __it) 859 { return __it == __victim; }); 860 this->_M_invalidate_local_if( 861 [__victim](_Base_const_local_iterator __it) 862 { return __it._M_curr() == __victim._M_cur; }); 863 size_type __bucket_count = this->bucket_count(); 864 _Base_iterator __next = _Base::erase(__it.base()); 865 _M_check_rehashed(__bucket_count); 866 return iterator(__next, this); 867 } 868 869 iterator 870 erase(iterator __it) 871 { return erase(const_iterator(__it)); } 872 873 iterator 874 erase(const_iterator __first, const_iterator __last) 875 { 876 __glibcxx_check_erase_range(__first, __last); 877 for (_Base_const_iterator __tmp = __first.base(); 878 __tmp != __last.base(); ++__tmp) 879 { 880 _GLIBCXX_DEBUG_VERIFY(__tmp != _Base::end(), 881 _M_message(__gnu_debug::__msg_valid_range) 882 ._M_iterator(__first, "first") 883 ._M_iterator(__last, "last")); 884 this->_M_invalidate_if([__tmp](_Base_const_iterator __it) 885 { return __it == __tmp; }); 886 this->_M_invalidate_local_if( 887 [__tmp](_Base_const_local_iterator __it) 888 { return __it._M_curr() == __tmp._M_cur; }); 889 } 890 size_type __bucket_count = this->bucket_count(); 891 _Base_iterator __next = _Base::erase(__first.base(), __last.base()); 892 _M_check_rehashed(__bucket_count); 893 return iterator(__next, this); 894 } 895 896 _Base& 897 _M_base() noexcept { return *this; } 898 899 const _Base& 900 _M_base() const noexcept { return *this; } 901 902 private: 903 void 904 _M_invalidate_locals() 905 { 906 _Base_local_iterator __local_end = _Base::end(0); 907 this->_M_invalidate_local_if( 908 [__local_end](_Base_const_local_iterator __it) 909 { return __it != __local_end; }); 910 } 911 912 void 913 _M_invalidate_all() 914 { 915 _Base_iterator __end = _Base::end(); 916 this->_M_invalidate_if([__end](_Base_const_iterator __it) 917 { return __it != __end; }); 918 _M_invalidate_locals(); 919 } 920 921 void 922 _M_check_rehashed(size_type __prev_count) 923 { 924 if (__prev_count != this->bucket_count()) 925 _M_invalidate_locals(); 926 } 927 }; 928 929 template<typename _Key, typename _Tp, typename _Hash, 930 typename _Pred, typename _Alloc> 931 inline void 932 swap(unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, 933 unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) 934 { __x.swap(__y); } 935 936 template<typename _Key, typename _Tp, typename _Hash, 937 typename _Pred, typename _Alloc> 938 inline bool 939 operator==(const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, 940 const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) 941 { return __x._M_base() == __y._M_base(); } 942 943 template<typename _Key, typename _Tp, typename _Hash, 944 typename _Pred, typename _Alloc> 945 inline bool 946 operator!=(const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, 947 const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) 948 { return !(__x == __y); } 949 950} // namespace __debug 951} // namespace std 952 953#endif // C++11 954 955#endif 956