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