1// Debugging unordered_map/unordered_multimap implementation -*- C++ -*- 2 3// Copyright (C) 2003-2022 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#pragma GCC system_header 33 34#if __cplusplus < 201103L 35# include <bits/c++0x_warning.h> 36#else 37# include <bits/c++config.h> 38namespace std _GLIBCXX_VISIBILITY(default) { namespace __debug { 39 template<typename _Key, typename _Tp, typename _Hash, typename _Pred, 40 typename _Allocator> 41 class unordered_map; 42 template<typename _Key, typename _Tp, typename _Hash, typename _Pred, 43 typename _Allocator> 44 class unordered_multimap; 45} } // namespace std::__debug 46 47# include <unordered_map> 48 49#include <debug/safe_unordered_container.h> 50#include <debug/safe_container.h> 51#include <debug/safe_iterator.h> 52#include <debug/safe_local_iterator.h> 53 54namespace std _GLIBCXX_VISIBILITY(default) 55{ 56namespace __debug 57{ 58 /// Class std::unordered_map with safety/checking/debug instrumentation. 59 template<typename _Key, typename _Tp, 60 typename _Hash = std::hash<_Key>, 61 typename _Pred = std::equal_to<_Key>, 62 typename _Alloc = std::allocator<std::pair<const _Key, _Tp> > > 63 class unordered_map 64 : public __gnu_debug::_Safe_container< 65 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>, _Alloc, 66 __gnu_debug::_Safe_unordered_container>, 67 public _GLIBCXX_STD_C::unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc> 68 { 69 typedef _GLIBCXX_STD_C::unordered_map<_Key, _Tp, _Hash, 70 _Pred, _Alloc> _Base; 71 typedef __gnu_debug::_Safe_container<unordered_map, 72 _Alloc, __gnu_debug::_Safe_unordered_container> _Safe; 73 typedef typename _Base::const_iterator _Base_const_iterator; 74 typedef typename _Base::iterator _Base_iterator; 75 typedef typename _Base::const_local_iterator 76 _Base_const_local_iterator; 77 typedef typename _Base::local_iterator _Base_local_iterator; 78 79 template<typename _ItT, typename _SeqT, typename _CatT> 80 friend class ::__gnu_debug::_Safe_iterator; 81 template<typename _ItT, typename _SeqT> 82 friend class ::__gnu_debug::_Safe_local_iterator; 83 84 // Reference wrapper for base class. See PR libstdc++/90102. 85 struct _Base_ref 86 { 87 _Base_ref(const _Base& __r) : _M_ref(__r) { } 88 89 const _Base& _M_ref; 90 }; 91 92 public: 93 typedef typename _Base::size_type size_type; 94 typedef typename _Base::hasher hasher; 95 typedef typename _Base::key_equal key_equal; 96 typedef typename _Base::allocator_type allocator_type; 97 98 typedef typename _Base::key_type key_type; 99 typedef typename _Base::value_type value_type; 100 typedef typename _Base::mapped_type mapped_type; 101 102 typedef typename _Base::pointer pointer; 103 typedef typename _Base::const_pointer const_pointer; 104 typedef typename _Base::reference reference; 105 typedef typename _Base::const_reference const_reference; 106 typedef __gnu_debug::_Safe_iterator< 107 _Base_iterator, unordered_map> iterator; 108 typedef __gnu_debug::_Safe_iterator< 109 _Base_const_iterator, unordered_map> const_iterator; 110 typedef __gnu_debug::_Safe_local_iterator< 111 _Base_local_iterator, unordered_map> local_iterator; 112 typedef __gnu_debug::_Safe_local_iterator< 113 _Base_const_local_iterator, unordered_map> const_local_iterator; 114 typedef typename _Base::difference_type difference_type; 115 116 unordered_map() = default; 117 118 explicit 119 unordered_map(size_type __n, 120 const hasher& __hf = hasher(), 121 const key_equal& __eql = key_equal(), 122 const allocator_type& __a = allocator_type()) 123 : _Base(__n, __hf, __eql, __a) { } 124 125 template<typename _InputIterator> 126 unordered_map(_InputIterator __first, _InputIterator __last, 127 size_type __n = 0, 128 const hasher& __hf = hasher(), 129 const key_equal& __eql = key_equal(), 130 const allocator_type& __a = allocator_type()) 131 : _Base(__gnu_debug::__base( 132 __glibcxx_check_valid_constructor_range(__first, __last)), 133 __gnu_debug::__base(__last), __n, 134 __hf, __eql, __a) { } 135 136 unordered_map(const unordered_map&) = default; 137 138 unordered_map(_Base_ref __x) 139 : _Base(__x._M_ref) { } 140 141 unordered_map(unordered_map&&) = default; 142 143 explicit 144 unordered_map(const allocator_type& __a) 145 : _Base(__a) { } 146 147 unordered_map(const unordered_map& __umap, 148 const allocator_type& __a) 149 : _Base(__umap, __a) { } 150 151 unordered_map(unordered_map&& __umap, 152 const allocator_type& __a) 153 noexcept( noexcept(_Base(std::move(__umap), __a)) ) 154 : _Safe(std::move(__umap), __a), 155 _Base(std::move(__umap), __a) { } 156 157 unordered_map(initializer_list<value_type> __l, 158 size_type __n = 0, 159 const hasher& __hf = hasher(), 160 const key_equal& __eql = key_equal(), 161 const allocator_type& __a = allocator_type()) 162 : _Base(__l, __n, __hf, __eql, __a) { } 163 164 unordered_map(size_type __n, const allocator_type& __a) 165 : unordered_map(__n, hasher(), key_equal(), __a) 166 { } 167 168 unordered_map(size_type __n, 169 const hasher& __hf, 170 const allocator_type& __a) 171 : unordered_map(__n, __hf, key_equal(), __a) 172 { } 173 174 template<typename _InputIterator> 175 unordered_map(_InputIterator __first, _InputIterator __last, 176 size_type __n, 177 const allocator_type& __a) 178 : unordered_map(__first, __last, __n, hasher(), key_equal(), __a) 179 { } 180 181 template<typename _InputIterator> 182 unordered_map(_InputIterator __first, _InputIterator __last, 183 size_type __n, 184 const hasher& __hf, 185 const allocator_type& __a) 186 : unordered_map(__first, __last, __n, __hf, key_equal(), __a) 187 { } 188 189 unordered_map(initializer_list<value_type> __l, 190 size_type __n, 191 const allocator_type& __a) 192 : unordered_map(__l, __n, hasher(), key_equal(), __a) 193 { } 194 195 unordered_map(initializer_list<value_type> __l, 196 size_type __n, 197 const hasher& __hf, 198 const allocator_type& __a) 199 : unordered_map(__l, __n, __hf, key_equal(), __a) 200 { } 201 202 ~unordered_map() = default; 203 204 unordered_map& 205 operator=(const unordered_map&) = default; 206 207 unordered_map& 208 operator=(unordered_map&&) = default; 209 210 unordered_map& 211 operator=(initializer_list<value_type> __l) 212 { 213 _Base::operator=(__l); 214 this->_M_invalidate_all(); 215 return *this; 216 } 217 218 using _Base::get_allocator; 219 using _Base::empty; 220 using _Base::size; 221 using _Base::max_size; 222 223 void 224 swap(unordered_map& __x) 225 noexcept( noexcept(declval<_Base&>().swap(__x)) ) 226 { 227 _Safe::_M_swap(__x); 228 _Base::swap(__x); 229 } 230 231 void 232 clear() noexcept 233 { 234 _Base::clear(); 235 this->_M_invalidate_all(); 236 } 237 238 iterator 239 begin() noexcept 240 { return { _Base::begin(), this }; } 241 242 const_iterator 243 begin() const noexcept 244 { return { _Base::begin(), this }; } 245 246 iterator 247 end() noexcept 248 { return { _Base::end(), this }; } 249 250 const_iterator 251 end() const noexcept 252 { return { _Base::end(), this }; } 253 254 const_iterator 255 cbegin() const noexcept 256 { return { _Base::cbegin(), this }; } 257 258 const_iterator 259 cend() const noexcept 260 { return { _Base::cend(), this }; } 261 262 // local versions 263 local_iterator 264 begin(size_type __b) 265 { 266 __glibcxx_check_bucket_index(__b); 267 return { _Base::begin(__b), this }; 268 } 269 270 local_iterator 271 end(size_type __b) 272 { 273 __glibcxx_check_bucket_index(__b); 274 return { _Base::end(__b), this }; 275 } 276 277 const_local_iterator 278 begin(size_type __b) const 279 { 280 __glibcxx_check_bucket_index(__b); 281 return { _Base::begin(__b), this }; 282 } 283 284 const_local_iterator 285 end(size_type __b) const 286 { 287 __glibcxx_check_bucket_index(__b); 288 return { _Base::end(__b), this }; 289 } 290 291 const_local_iterator 292 cbegin(size_type __b) const 293 { 294 __glibcxx_check_bucket_index(__b); 295 return { _Base::cbegin(__b), this }; 296 } 297 298 const_local_iterator 299 cend(size_type __b) const 300 { 301 __glibcxx_check_bucket_index(__b); 302 return { _Base::cend(__b), this }; 303 } 304 305 using _Base::bucket_count; 306 using _Base::max_bucket_count; 307 using _Base::bucket; 308 309 size_type 310 bucket_size(size_type __b) const 311 { 312 __glibcxx_check_bucket_index(__b); 313 return _Base::bucket_size(__b); 314 } 315 316 using _Base::load_factor; 317 318 float 319 max_load_factor() const noexcept 320 { return _Base::max_load_factor(); } 321 322 void 323 max_load_factor(float __f) 324 { 325 __glibcxx_check_max_load_factor(__f); 326 _Base::max_load_factor(__f); 327 } 328 329 template<typename... _Args> 330 std::pair<iterator, bool> 331 emplace(_Args&&... __args) 332 { 333 size_type __bucket_count = this->bucket_count(); 334 auto __res = _Base::emplace(std::forward<_Args>(__args)...); 335 _M_check_rehashed(__bucket_count); 336 return { { __res.first, this }, __res.second }; 337 } 338 339 template<typename... _Args> 340 iterator 341 emplace_hint(const_iterator __hint, _Args&&... __args) 342 { 343 __glibcxx_check_insert(__hint); 344 size_type __bucket_count = this->bucket_count(); 345 auto __it = _Base::emplace_hint(__hint.base(), 346 std::forward<_Args>(__args)...); 347 _M_check_rehashed(__bucket_count); 348 return { __it, this }; 349 } 350 351 std::pair<iterator, bool> 352 insert(const value_type& __obj) 353 { 354 size_type __bucket_count = this->bucket_count(); 355 auto __res = _Base::insert(__obj); 356 _M_check_rehashed(__bucket_count); 357 return { { __res.first, this }, __res.second }; 358 } 359 360 // _GLIBCXX_RESOLVE_LIB_DEFECTS 361 // 2354. Unnecessary copying when inserting into maps with braced-init 362 std::pair<iterator, bool> 363 insert(value_type&& __x) 364 { 365 size_type __bucket_count = this->bucket_count(); 366 auto __res = _Base::insert(std::move(__x)); 367 _M_check_rehashed(__bucket_count); 368 return { { __res.first, this }, __res.second }; 369 } 370 371 template<typename _Pair, typename = typename 372 std::enable_if<std::is_constructible<value_type, 373 _Pair&&>::value>::type> 374 std::pair<iterator, bool> 375 insert(_Pair&& __obj) 376 { 377 size_type __bucket_count = this->bucket_count(); 378 auto __res = _Base::insert(std::forward<_Pair>(__obj)); 379 _M_check_rehashed(__bucket_count); 380 return { { __res.first, this }, __res.second }; 381 } 382 383 iterator 384 insert(const_iterator __hint, const value_type& __obj) 385 { 386 __glibcxx_check_insert(__hint); 387 size_type __bucket_count = this->bucket_count(); 388 auto __it = _Base::insert(__hint.base(), __obj); 389 _M_check_rehashed(__bucket_count); 390 return { __it, this }; 391 } 392 393 // _GLIBCXX_RESOLVE_LIB_DEFECTS 394 // 2354. Unnecessary copying when inserting into maps with braced-init 395 iterator 396 insert(const_iterator __hint, value_type&& __x) 397 { 398 __glibcxx_check_insert(__hint); 399 size_type __bucket_count = this->bucket_count(); 400 auto __it = _Base::insert(__hint.base(), std::move(__x)); 401 _M_check_rehashed(__bucket_count); 402 return { __it, this }; 403 } 404 405 template<typename _Pair, typename = typename 406 std::enable_if<std::is_constructible<value_type, 407 _Pair&&>::value>::type> 408 iterator 409 insert(const_iterator __hint, _Pair&& __obj) 410 { 411 __glibcxx_check_insert(__hint); 412 size_type __bucket_count = this->bucket_count(); 413 auto __it = _Base::insert(__hint.base(), std::forward<_Pair>(__obj)); 414 _M_check_rehashed(__bucket_count); 415 return { __it, this }; 416 } 417 418 void 419 insert(std::initializer_list<value_type> __l) 420 { 421 size_type __bucket_count = this->bucket_count(); 422 _Base::insert(__l); 423 _M_check_rehashed(__bucket_count); 424 } 425 426 template<typename _InputIterator> 427 void 428 insert(_InputIterator __first, _InputIterator __last) 429 { 430 typename __gnu_debug::_Distance_traits<_InputIterator>::__type __dist; 431 __glibcxx_check_valid_range2(__first, __last, __dist); 432 size_type __bucket_count = this->bucket_count(); 433 434 if (__dist.second >= __gnu_debug::__dp_sign) 435 _Base::insert(__gnu_debug::__unsafe(__first), 436 __gnu_debug::__unsafe(__last)); 437 else 438 _Base::insert(__first, __last); 439 440 _M_check_rehashed(__bucket_count); 441 } 442 443#if __cplusplus > 201402L 444 template <typename... _Args> 445 pair<iterator, bool> 446 try_emplace(const key_type& __k, _Args&&... __args) 447 { 448 auto __res = _Base::try_emplace(__k, 449 std::forward<_Args>(__args)...); 450 return { { __res.first, this }, __res.second }; 451 } 452 453 template <typename... _Args> 454 pair<iterator, bool> 455 try_emplace(key_type&& __k, _Args&&... __args) 456 { 457 auto __res = _Base::try_emplace(std::move(__k), 458 std::forward<_Args>(__args)...); 459 return { { __res.first, this }, __res.second }; 460 } 461 462 template <typename... _Args> 463 iterator 464 try_emplace(const_iterator __hint, const key_type& __k, 465 _Args&&... __args) 466 { 467 __glibcxx_check_insert(__hint); 468 return { _Base::try_emplace(__hint.base(), __k, 469 std::forward<_Args>(__args)...), 470 this }; 471 } 472 473 template <typename... _Args> 474 iterator 475 try_emplace(const_iterator __hint, key_type&& __k, _Args&&... __args) 476 { 477 __glibcxx_check_insert(__hint); 478 return { _Base::try_emplace(__hint.base(), std::move(__k), 479 std::forward<_Args>(__args)...), 480 this }; 481 } 482 483 template <typename _Obj> 484 pair<iterator, bool> 485 insert_or_assign(const key_type& __k, _Obj&& __obj) 486 { 487 auto __res = _Base::insert_or_assign(__k, 488 std::forward<_Obj>(__obj)); 489 return { { __res.first, this }, __res.second }; 490 } 491 492 template <typename _Obj> 493 pair<iterator, bool> 494 insert_or_assign(key_type&& __k, _Obj&& __obj) 495 { 496 auto __res = _Base::insert_or_assign(std::move(__k), 497 std::forward<_Obj>(__obj)); 498 return { { __res.first, this }, __res.second }; 499 } 500 501 template <typename _Obj> 502 iterator 503 insert_or_assign(const_iterator __hint, const key_type& __k, 504 _Obj&& __obj) 505 { 506 __glibcxx_check_insert(__hint); 507 return { _Base::insert_or_assign(__hint.base(), __k, 508 std::forward<_Obj>(__obj)), 509 this }; 510 } 511 512 template <typename _Obj> 513 iterator 514 insert_or_assign(const_iterator __hint, key_type&& __k, _Obj&& __obj) 515 { 516 __glibcxx_check_insert(__hint); 517 return { _Base::insert_or_assign(__hint.base(), std::move(__k), 518 std::forward<_Obj>(__obj)), 519 this }; 520 } 521#endif // C++17 522 523#if __cplusplus > 201402L 524 using node_type = typename _Base::node_type; 525 using insert_return_type = _Node_insert_return<iterator, node_type>; 526 527 node_type 528 extract(const_iterator __position) 529 { 530 __glibcxx_check_erase(__position); 531 return _M_extract(__position.base()); 532 } 533 534 node_type 535 extract(const key_type& __key) 536 { 537 const auto __position = _Base::find(__key); 538 if (__position != _Base::end()) 539 return _M_extract(__position); 540 return {}; 541 } 542 543 insert_return_type 544 insert(node_type&& __nh) 545 { 546 auto __ret = _Base::insert(std::move(__nh)); 547 return 548 { { __ret.position, this }, __ret.inserted, std::move(__ret.node) }; 549 } 550 551 iterator 552 insert(const_iterator __hint, node_type&& __nh) 553 { 554 __glibcxx_check_insert(__hint); 555 return { _Base::insert(__hint.base(), std::move(__nh)), this }; 556 } 557 558 template<typename _H2, typename _P2> 559 void 560 merge(unordered_map<_Key, _Tp, _H2, _P2, _Alloc>& __source) 561 { 562 auto __guard 563 = _Safe::_S_uc_guard(std::__detail::_Select1st{}, __source); 564 _Base::merge(__source); 565 } 566 567 template<typename _H2, typename _P2> 568 void 569 merge(unordered_map<_Key, _Tp, _H2, _P2, _Alloc>&& __source) 570 { merge(__source); } 571 572 template<typename _H2, typename _P2> 573 void 574 merge(unordered_multimap<_Key, _Tp, _H2, _P2, _Alloc>& __source) 575 { 576 auto __guard 577 = _Safe::_S_umc_guard(std::__detail::_Select1st{}, __source); 578 _Base::merge(__source); 579 } 580 581 template<typename _H2, typename _P2> 582 void 583 merge(unordered_multimap<_Key, _Tp, _H2, _P2, _Alloc>&& __source) 584 { merge(__source); } 585#endif // C++17 586 587 using _Base::hash_function; 588 using _Base::key_eq; 589 590 iterator 591 find(const key_type& __key) 592 { return { _Base::find(__key), this }; } 593 594#if __cplusplus > 201703L 595 template<typename _Kt, 596 typename = std::__has_is_transparent_t<_Hash, _Kt>, 597 typename = std::__has_is_transparent_t<_Pred, _Kt>> 598 iterator 599 find(const _Kt& __k) 600 { return { _Base::find(__k), this }; } 601#endif 602 603 const_iterator 604 find(const key_type& __key) const 605 { return { _Base::find(__key), this }; } 606 607#if __cplusplus > 201703L 608 template<typename _Kt, 609 typename = std::__has_is_transparent_t<_Hash, _Kt>, 610 typename = std::__has_is_transparent_t<_Pred, _Kt>> 611 const_iterator 612 find(const _Kt& __k) const 613 { return { _Base::find(__k), this }; } 614#endif 615 616 using _Base::count; 617#if __cplusplus > 201703L 618 using _Base::contains; 619#endif 620 621 std::pair<iterator, iterator> 622 equal_range(const key_type& __key) 623 { 624 auto __res = _Base::equal_range(__key); 625 return { { __res.first, this }, { __res.second, this } }; 626 } 627 628#if __cplusplus > 201703L 629 template<typename _Kt, 630 typename = std::__has_is_transparent_t<_Hash, _Kt>, 631 typename = std::__has_is_transparent_t<_Pred, _Kt>> 632 std::pair<iterator, iterator> 633 equal_range(const _Kt& __k) 634 { 635 auto __res = _Base::equal_range(__k); 636 return { { __res.first, this }, { __res.second, this } }; 637 } 638#endif 639 640 std::pair<const_iterator, const_iterator> 641 equal_range(const key_type& __key) const 642 { 643 auto __res = _Base::equal_range(__key); 644 return { { __res.first, this }, { __res.second, this } }; 645 } 646 647#if __cplusplus > 201703L 648 template<typename _Kt, 649 typename = std::__has_is_transparent_t<_Hash, _Kt>, 650 typename = std::__has_is_transparent_t<_Pred, _Kt>> 651 std::pair<const_iterator, const_iterator> 652 equal_range(const _Kt& __k) const 653 { 654 auto __res = _Base::equal_range(__k); 655 return { { __res.first, this }, { __res.second, this } }; 656 } 657#endif 658 659 using _Base::operator[]; 660 using _Base::at; 661 662 size_type 663 erase(const key_type& __key) 664 { 665 size_type __ret(0); 666 auto __victim = _Base::find(__key); 667 if (__victim != _Base::end()) 668 { 669 _M_erase(__victim); 670 __ret = 1; 671 } 672 return __ret; 673 } 674 675 iterator 676 erase(const_iterator __it) 677 { 678 __glibcxx_check_erase(__it); 679 return { _M_erase(__it.base()), this }; 680 } 681 682 _Base_iterator 683 erase(_Base_const_iterator __it) 684 { 685 __glibcxx_check_erase2(__it); 686 return _M_erase(__it); 687 } 688 689 iterator 690 erase(iterator __it) 691 { 692 __glibcxx_check_erase(__it); 693 return { _M_erase(__it.base()), this }; 694 } 695 696 iterator 697 erase(const_iterator __first, const_iterator __last) 698 { 699 __glibcxx_check_erase_range(__first, __last); 700 for (auto __tmp = __first.base(); __tmp != __last.base(); ++__tmp) 701 { 702 _GLIBCXX_DEBUG_VERIFY(__tmp != _Base::cend(), 703 _M_message(__gnu_debug::__msg_valid_range) 704 ._M_iterator(__first, "first") 705 ._M_iterator(__last, "last")); 706 _M_invalidate(__tmp); 707 } 708 709 size_type __bucket_count = this->bucket_count(); 710 auto __next = _Base::erase(__first.base(), __last.base()); 711 _M_check_rehashed(__bucket_count); 712 return { __next, this }; 713 } 714 715 using _Base::rehash; 716 using _Base::reserve; 717 718 _Base& 719 _M_base() noexcept { return *this; } 720 721 const _Base& 722 _M_base() const noexcept { return *this; } 723 724 private: 725 void 726 _M_check_rehashed(size_type __prev_count) 727 { 728 if (__prev_count != this->bucket_count()) 729 this->_M_invalidate_all(); 730 } 731 732 void 733 _M_invalidate(_Base_const_iterator __victim) 734 { 735 this->_M_invalidate_if( 736 [__victim](_Base_const_iterator __it) { return __it == __victim; }); 737 this->_M_invalidate_local_if( 738 [__victim](_Base_const_local_iterator __it) 739 { return __it == __victim; }); 740 } 741 742 _Base_iterator 743 _M_erase(_Base_const_iterator __victim) 744 { 745 _M_invalidate(__victim); 746 size_type __bucket_count = this->bucket_count(); 747 _Base_iterator __next = _Base::erase(__victim); 748 _M_check_rehashed(__bucket_count); 749 return __next; 750 } 751 752#if __cplusplus > 201402L 753 node_type 754 _M_extract(_Base_const_iterator __victim) 755 { 756 _M_invalidate(__victim); 757 return _Base::extract(__victim); 758 } 759#endif 760 }; 761 762#if __cpp_deduction_guides >= 201606 763 764 template<typename _InputIterator, 765 typename _Hash = hash<__iter_key_t<_InputIterator>>, 766 typename _Pred = equal_to<__iter_key_t<_InputIterator>>, 767 typename _Allocator = allocator<__iter_to_alloc_t<_InputIterator>>, 768 typename = _RequireInputIter<_InputIterator>, 769 typename = _RequireNotAllocatorOrIntegral<_Hash>, 770 typename = _RequireNotAllocator<_Pred>, 771 typename = _RequireAllocator<_Allocator>> 772 unordered_map(_InputIterator, _InputIterator, 773 typename unordered_map<int, int>::size_type = {}, 774 _Hash = _Hash(), _Pred = _Pred(), _Allocator = _Allocator()) 775 -> unordered_map<__iter_key_t<_InputIterator>, 776 __iter_val_t<_InputIterator>, 777 _Hash, _Pred, _Allocator>; 778 779 template<typename _Key, typename _Tp, typename _Hash = hash<_Key>, 780 typename _Pred = equal_to<_Key>, 781 typename _Allocator = allocator<pair<const _Key, _Tp>>, 782 typename = _RequireNotAllocatorOrIntegral<_Hash>, 783 typename = _RequireNotAllocator<_Pred>, 784 typename = _RequireAllocator<_Allocator>> 785 unordered_map(initializer_list<pair<_Key, _Tp>>, 786 typename unordered_map<int, int>::size_type = {}, 787 _Hash = _Hash(), _Pred = _Pred(), _Allocator = _Allocator()) 788 -> unordered_map<_Key, _Tp, _Hash, _Pred, _Allocator>; 789 790 template<typename _InputIterator, typename _Allocator, 791 typename = _RequireInputIter<_InputIterator>, 792 typename = _RequireAllocator<_Allocator>> 793 unordered_map(_InputIterator, _InputIterator, 794 typename unordered_map<int, int>::size_type, _Allocator) 795 -> unordered_map<__iter_key_t<_InputIterator>, 796 __iter_val_t<_InputIterator>, 797 hash<__iter_key_t<_InputIterator>>, 798 equal_to<__iter_key_t<_InputIterator>>, 799 _Allocator>; 800 801 template<typename _InputIterator, typename _Allocator, 802 typename = _RequireInputIter<_InputIterator>, 803 typename = _RequireAllocator<_Allocator>> 804 unordered_map(_InputIterator, _InputIterator, _Allocator) 805 -> unordered_map<__iter_key_t<_InputIterator>, 806 __iter_val_t<_InputIterator>, 807 hash<__iter_key_t<_InputIterator>>, 808 equal_to<__iter_key_t<_InputIterator>>, 809 _Allocator>; 810 811 template<typename _InputIterator, typename _Hash, typename _Allocator, 812 typename = _RequireInputIter<_InputIterator>, 813 typename = _RequireNotAllocatorOrIntegral<_Hash>, 814 typename = _RequireAllocator<_Allocator>> 815 unordered_map(_InputIterator, _InputIterator, 816 typename unordered_map<int, int>::size_type, 817 _Hash, _Allocator) 818 -> unordered_map<__iter_key_t<_InputIterator>, 819 __iter_val_t<_InputIterator>, _Hash, 820 equal_to<__iter_key_t<_InputIterator>>, _Allocator>; 821 822 template<typename _Key, typename _Tp, typename _Allocator, 823 typename = _RequireAllocator<_Allocator>> 824 unordered_map(initializer_list<pair<_Key, _Tp>>, 825 typename unordered_map<int, int>::size_type, 826 _Allocator) 827 -> unordered_map<_Key, _Tp, hash<_Key>, equal_to<_Key>, _Allocator>; 828 829 template<typename _Key, typename _Tp, typename _Allocator, 830 typename = _RequireAllocator<_Allocator>> 831 unordered_map(initializer_list<pair<_Key, _Tp>>, _Allocator) 832 -> unordered_map<_Key, _Tp, hash<_Key>, equal_to<_Key>, _Allocator>; 833 834 template<typename _Key, typename _Tp, typename _Hash, typename _Allocator, 835 typename = _RequireNotAllocatorOrIntegral<_Hash>, 836 typename = _RequireAllocator<_Allocator>> 837 unordered_map(initializer_list<pair<_Key, _Tp>>, 838 typename unordered_map<int, int>::size_type, 839 _Hash, _Allocator) 840 -> unordered_map<_Key, _Tp, _Hash, equal_to<_Key>, _Allocator>; 841 842#endif 843 844 template<typename _Key, typename _Tp, typename _Hash, 845 typename _Pred, typename _Alloc> 846 inline void 847 swap(unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, 848 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) 849 noexcept(noexcept(__x.swap(__y))) 850 { __x.swap(__y); } 851 852 template<typename _Key, typename _Tp, typename _Hash, 853 typename _Pred, typename _Alloc> 854 inline bool 855 operator==(const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, 856 const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) 857 { return __x._M_base() == __y._M_base(); } 858 859#if __cpp_impl_three_way_comparison < 201907L 860 template<typename _Key, typename _Tp, typename _Hash, 861 typename _Pred, typename _Alloc> 862 inline bool 863 operator!=(const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, 864 const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) 865 { return !(__x == __y); } 866#endif 867 868 /// Class std::unordered_multimap with safety/checking/debug instrumentation. 869 template<typename _Key, typename _Tp, 870 typename _Hash = std::hash<_Key>, 871 typename _Pred = std::equal_to<_Key>, 872 typename _Alloc = std::allocator<std::pair<const _Key, _Tp> > > 873 class unordered_multimap 874 : public __gnu_debug::_Safe_container< 875 unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>, _Alloc, 876 __gnu_debug::_Safe_unordered_container>, 877 public _GLIBCXX_STD_C::unordered_multimap< 878 _Key, _Tp, _Hash, _Pred, _Alloc> 879 { 880 typedef _GLIBCXX_STD_C::unordered_multimap<_Key, _Tp, _Hash, 881 _Pred, _Alloc> _Base; 882 typedef __gnu_debug::_Safe_container<unordered_multimap, 883 _Alloc, __gnu_debug::_Safe_unordered_container> _Safe; 884 typedef typename _Base::const_iterator _Base_const_iterator; 885 typedef typename _Base::iterator _Base_iterator; 886 typedef typename _Base::const_local_iterator _Base_const_local_iterator; 887 typedef typename _Base::local_iterator _Base_local_iterator; 888 889 template<typename _ItT, typename _SeqT, typename _CatT> 890 friend class ::__gnu_debug::_Safe_iterator; 891 template<typename _ItT, typename _SeqT> 892 friend class ::__gnu_debug::_Safe_local_iterator; 893 894 // Reference wrapper for base class. See PR libstdc++/90102. 895 struct _Base_ref 896 { 897 _Base_ref(const _Base& __r) : _M_ref(__r) { } 898 899 const _Base& _M_ref; 900 }; 901 902 public: 903 typedef typename _Base::size_type size_type; 904 typedef typename _Base::hasher hasher; 905 typedef typename _Base::key_equal key_equal; 906 typedef typename _Base::allocator_type allocator_type; 907 908 typedef typename _Base::key_type key_type; 909 typedef typename _Base::value_type value_type; 910 typedef typename _Base::mapped_type mapped_type; 911 912 typedef typename _Base::pointer pointer; 913 typedef typename _Base::const_pointer const_pointer; 914 typedef typename _Base::reference reference; 915 typedef typename _Base::const_reference const_reference; 916 typedef __gnu_debug::_Safe_iterator< 917 _Base_iterator, unordered_multimap> iterator; 918 typedef __gnu_debug::_Safe_iterator< 919 _Base_const_iterator, unordered_multimap> const_iterator; 920 typedef __gnu_debug::_Safe_local_iterator< 921 _Base_local_iterator, unordered_multimap> local_iterator; 922 typedef __gnu_debug::_Safe_local_iterator< 923 _Base_const_local_iterator, unordered_multimap> const_local_iterator; 924 typedef typename _Base::difference_type difference_type; 925 926 unordered_multimap() = default; 927 928 explicit 929 unordered_multimap(size_type __n, 930 const hasher& __hf = hasher(), 931 const key_equal& __eql = key_equal(), 932 const allocator_type& __a = allocator_type()) 933 : _Base(__n, __hf, __eql, __a) { } 934 935 template<typename _InputIterator> 936 unordered_multimap(_InputIterator __first, _InputIterator __last, 937 size_type __n = 0, 938 const hasher& __hf = hasher(), 939 const key_equal& __eql = key_equal(), 940 const allocator_type& __a = allocator_type()) 941 : _Base(__gnu_debug::__base( 942 __glibcxx_check_valid_constructor_range(__first, __last)), 943 __gnu_debug::__base(__last), __n, 944 __hf, __eql, __a) { } 945 946 unordered_multimap(const unordered_multimap&) = default; 947 948 unordered_multimap(_Base_ref __x) 949 : _Base(__x._M_ref) { } 950 951 unordered_multimap(unordered_multimap&&) = default; 952 953 explicit 954 unordered_multimap(const allocator_type& __a) 955 : _Base(__a) { } 956 957 unordered_multimap(const unordered_multimap& __umap, 958 const allocator_type& __a) 959 : _Base(__umap, __a) { } 960 961 unordered_multimap(unordered_multimap&& __umap, 962 const allocator_type& __a) 963 noexcept( noexcept(_Base(std::move(__umap), __a)) ) 964 : _Safe(std::move(__umap), __a), 965 _Base(std::move(__umap), __a) { } 966 967 unordered_multimap(initializer_list<value_type> __l, 968 size_type __n = 0, 969 const hasher& __hf = hasher(), 970 const key_equal& __eql = key_equal(), 971 const allocator_type& __a = allocator_type()) 972 : _Base(__l, __n, __hf, __eql, __a) { } 973 974 unordered_multimap(size_type __n, const allocator_type& __a) 975 : unordered_multimap(__n, hasher(), key_equal(), __a) 976 { } 977 978 unordered_multimap(size_type __n, const hasher& __hf, 979 const allocator_type& __a) 980 : unordered_multimap(__n, __hf, key_equal(), __a) 981 { } 982 983 template<typename _InputIterator> 984 unordered_multimap(_InputIterator __first, _InputIterator __last, 985 size_type __n, 986 const allocator_type& __a) 987 : unordered_multimap(__first, __last, __n, hasher(), key_equal(), __a) 988 { } 989 990 template<typename _InputIterator> 991 unordered_multimap(_InputIterator __first, _InputIterator __last, 992 size_type __n, const hasher& __hf, 993 const allocator_type& __a) 994 : unordered_multimap(__first, __last, __n, __hf, key_equal(), __a) 995 { } 996 997 unordered_multimap(initializer_list<value_type> __l, 998 size_type __n, 999 const allocator_type& __a) 1000 : unordered_multimap(__l, __n, hasher(), key_equal(), __a) 1001 { } 1002 1003 unordered_multimap(initializer_list<value_type> __l, 1004 size_type __n, const hasher& __hf, 1005 const allocator_type& __a) 1006 : unordered_multimap(__l, __n, __hf, key_equal(), __a) 1007 { } 1008 1009 ~unordered_multimap() = default; 1010 1011 unordered_multimap& 1012 operator=(const unordered_multimap&) = default; 1013 1014 unordered_multimap& 1015 operator=(unordered_multimap&&) = default; 1016 1017 unordered_multimap& 1018 operator=(initializer_list<value_type> __l) 1019 { 1020 _Base::operator=(__l); 1021 this->_M_invalidate_all(); 1022 return *this; 1023 } 1024 1025 using _Base::get_allocator; 1026 using _Base::empty; 1027 using _Base::size; 1028 using _Base::max_size; 1029 1030 void 1031 swap(unordered_multimap& __x) 1032 noexcept( noexcept(declval<_Base&>().swap(__x)) ) 1033 { 1034 _Safe::_M_swap(__x); 1035 _Base::swap(__x); 1036 } 1037 1038 void 1039 clear() noexcept 1040 { 1041 _Base::clear(); 1042 this->_M_invalidate_all(); 1043 } 1044 1045 iterator 1046 begin() noexcept 1047 { return { _Base::begin(), this }; } 1048 1049 const_iterator 1050 begin() const noexcept 1051 { return { _Base::begin(), this }; } 1052 1053 iterator 1054 end() noexcept 1055 { return { _Base::end(), this }; } 1056 1057 const_iterator 1058 end() const noexcept 1059 { return { _Base::end(), this }; } 1060 1061 const_iterator 1062 cbegin() const noexcept 1063 { return { _Base::cbegin(), this }; } 1064 1065 const_iterator 1066 cend() const noexcept 1067 { return { _Base::cend(), this }; } 1068 1069 // local versions 1070 local_iterator 1071 begin(size_type __b) 1072 { 1073 __glibcxx_check_bucket_index(__b); 1074 return { _Base::begin(__b), this }; 1075 } 1076 1077 local_iterator 1078 end(size_type __b) 1079 { 1080 __glibcxx_check_bucket_index(__b); 1081 return { _Base::end(__b), this }; 1082 } 1083 1084 const_local_iterator 1085 begin(size_type __b) const 1086 { 1087 __glibcxx_check_bucket_index(__b); 1088 return { _Base::begin(__b), this }; 1089 } 1090 1091 const_local_iterator 1092 end(size_type __b) const 1093 { 1094 __glibcxx_check_bucket_index(__b); 1095 return { _Base::end(__b), this }; 1096 } 1097 1098 const_local_iterator 1099 cbegin(size_type __b) const 1100 { 1101 __glibcxx_check_bucket_index(__b); 1102 return { _Base::cbegin(__b), this }; 1103 } 1104 1105 const_local_iterator 1106 cend(size_type __b) const 1107 { 1108 __glibcxx_check_bucket_index(__b); 1109 return { _Base::cend(__b), this }; 1110 } 1111 1112 using _Base::bucket_count; 1113 using _Base::max_bucket_count; 1114 using _Base::bucket; 1115 1116 size_type 1117 bucket_size(size_type __b) const 1118 { 1119 __glibcxx_check_bucket_index(__b); 1120 return _Base::bucket_size(__b); 1121 } 1122 1123 float 1124 max_load_factor() const noexcept 1125 { return _Base::max_load_factor(); } 1126 1127 void 1128 max_load_factor(float __f) 1129 { 1130 __glibcxx_check_max_load_factor(__f); 1131 _Base::max_load_factor(__f); 1132 } 1133 1134 template<typename... _Args> 1135 iterator 1136 emplace(_Args&&... __args) 1137 { 1138 size_type __bucket_count = this->bucket_count(); 1139 auto __it = _Base::emplace(std::forward<_Args>(__args)...); 1140 _M_check_rehashed(__bucket_count); 1141 return { __it, this }; 1142 } 1143 1144 template<typename... _Args> 1145 iterator 1146 emplace_hint(const_iterator __hint, _Args&&... __args) 1147 { 1148 __glibcxx_check_insert(__hint); 1149 size_type __bucket_count = this->bucket_count(); 1150 auto __it = _Base::emplace_hint(__hint.base(), 1151 std::forward<_Args>(__args)...); 1152 _M_check_rehashed(__bucket_count); 1153 return { __it, this }; 1154 } 1155 1156 iterator 1157 insert(const value_type& __obj) 1158 { 1159 size_type __bucket_count = this->bucket_count(); 1160 auto __it = _Base::insert(__obj); 1161 _M_check_rehashed(__bucket_count); 1162 return { __it, this }; 1163 } 1164 1165 // _GLIBCXX_RESOLVE_LIB_DEFECTS 1166 // 2354. Unnecessary copying when inserting into maps with braced-init 1167 iterator 1168 insert(value_type&& __x) 1169 { 1170 size_type __bucket_count = this->bucket_count(); 1171 auto __it = _Base::insert(std::move(__x)); 1172 _M_check_rehashed(__bucket_count); 1173 return { __it, this }; 1174 } 1175 1176 iterator 1177 insert(const_iterator __hint, const value_type& __obj) 1178 { 1179 __glibcxx_check_insert(__hint); 1180 size_type __bucket_count = this->bucket_count(); 1181 auto __it = _Base::insert(__hint.base(), __obj); 1182 _M_check_rehashed(__bucket_count); 1183 return { __it, this }; 1184 } 1185 1186 // _GLIBCXX_RESOLVE_LIB_DEFECTS 1187 // 2354. Unnecessary copying when inserting into maps with braced-init 1188 iterator 1189 insert(const_iterator __hint, value_type&& __x) 1190 { 1191 __glibcxx_check_insert(__hint); 1192 size_type __bucket_count = this->bucket_count(); 1193 auto __it = _Base::insert(__hint.base(), std::move(__x)); 1194 _M_check_rehashed(__bucket_count); 1195 return { __it, this }; 1196 } 1197 1198 template<typename _Pair, typename = typename 1199 std::enable_if<std::is_constructible<value_type, 1200 _Pair&&>::value>::type> 1201 iterator 1202 insert(_Pair&& __obj) 1203 { 1204 size_type __bucket_count = this->bucket_count(); 1205 auto __it = _Base::insert(std::forward<_Pair>(__obj)); 1206 _M_check_rehashed(__bucket_count); 1207 return { __it, this }; 1208 } 1209 1210 template<typename _Pair, typename = typename 1211 std::enable_if<std::is_constructible<value_type, 1212 _Pair&&>::value>::type> 1213 iterator 1214 insert(const_iterator __hint, _Pair&& __obj) 1215 { 1216 __glibcxx_check_insert(__hint); 1217 size_type __bucket_count = this->bucket_count(); 1218 auto __it = _Base::insert(__hint.base(), std::forward<_Pair>(__obj)); 1219 _M_check_rehashed(__bucket_count); 1220 return { __it, this }; 1221 } 1222 1223 void 1224 insert(std::initializer_list<value_type> __l) 1225 { _Base::insert(__l); } 1226 1227 template<typename _InputIterator> 1228 void 1229 insert(_InputIterator __first, _InputIterator __last) 1230 { 1231 typename __gnu_debug::_Distance_traits<_InputIterator>::__type __dist; 1232 __glibcxx_check_valid_range2(__first, __last, __dist); 1233 size_type __bucket_count = this->bucket_count(); 1234 1235 if (__dist.second >= __gnu_debug::__dp_sign) 1236 _Base::insert(__gnu_debug::__unsafe(__first), 1237 __gnu_debug::__unsafe(__last)); 1238 else 1239 _Base::insert(__first, __last); 1240 1241 _M_check_rehashed(__bucket_count); 1242 } 1243 1244#if __cplusplus > 201402L 1245 using node_type = typename _Base::node_type; 1246 1247 node_type 1248 extract(const_iterator __position) 1249 { 1250 __glibcxx_check_erase(__position); 1251 return _M_extract(__position.base()); 1252 } 1253 1254 node_type 1255 extract(const key_type& __key) 1256 { 1257 const auto __position = _Base::find(__key); 1258 if (__position != _Base::end()) 1259 return _M_extract(__position); 1260 return {}; 1261 } 1262 1263 iterator 1264 insert(node_type&& __nh) 1265 { return { _Base::insert(std::move(__nh)), this }; } 1266 1267 iterator 1268 insert(const_iterator __hint, node_type&& __nh) 1269 { 1270 __glibcxx_check_insert(__hint); 1271 return { _Base::insert(__hint.base(), std::move(__nh)), this }; 1272 } 1273 1274 template<typename _H2, typename _P2> 1275 void 1276 merge(unordered_multimap<_Key, _Tp, _H2, _P2, _Alloc>& __source) 1277 { 1278 auto __guard 1279 = _Safe::_S_umc_guard(std::__detail::_Select1st{}, __source); 1280 _Base::merge(__source); 1281 } 1282 1283 template<typename _H2, typename _P2> 1284 void 1285 merge(unordered_multimap<_Key, _Tp, _H2, _P2, _Alloc>&& __source) 1286 { merge(__source); } 1287 1288 template<typename _H2, typename _P2> 1289 void 1290 merge(unordered_map<_Key, _Tp, _H2, _P2, _Alloc>& __source) 1291 { 1292 auto __guard 1293 = _Safe::_S_uc_guard(std::__detail::_Select1st{}, __source); 1294 _Base::merge(__source); 1295 } 1296 1297 template<typename _H2, typename _P2> 1298 void 1299 merge(unordered_map<_Key, _Tp, _H2, _P2, _Alloc>&& __source) 1300 { merge(__source); } 1301#endif // C++17 1302 1303 using _Base::hash_function; 1304 using _Base::key_eq; 1305 1306 iterator 1307 find(const key_type& __key) 1308 { return { _Base::find(__key), this }; } 1309 1310#if __cplusplus > 201703L 1311 template<typename _Kt, 1312 typename = std::__has_is_transparent_t<_Hash, _Kt>, 1313 typename = std::__has_is_transparent_t<_Pred, _Kt>> 1314 iterator 1315 find(const _Kt& __k) 1316 { return { _Base::find(__k), this }; } 1317#endif 1318 1319 const_iterator 1320 find(const key_type& __key) const 1321 { return { _Base::find(__key), this }; } 1322 1323#if __cplusplus > 201703L 1324 template<typename _Kt, 1325 typename = std::__has_is_transparent_t<_Hash, _Kt>, 1326 typename = std::__has_is_transparent_t<_Pred, _Kt>> 1327 const_iterator 1328 find(const _Kt& __k) const 1329 { return { _Base::find(__k), this }; } 1330#endif 1331 1332 using _Base::count; 1333#if __cplusplus > 201703L 1334 using _Base::contains; 1335#endif 1336 1337 std::pair<iterator, iterator> 1338 equal_range(const key_type& __key) 1339 { 1340 auto __res = _Base::equal_range(__key); 1341 return { { __res.first, this }, { __res.second, this } }; 1342 } 1343 1344#if __cplusplus > 201703L 1345 template<typename _Kt, 1346 typename = std::__has_is_transparent_t<_Hash, _Kt>, 1347 typename = std::__has_is_transparent_t<_Pred, _Kt>> 1348 std::pair<iterator, iterator> 1349 equal_range(const _Kt& __k) 1350 { 1351 auto __res = _Base::equal_range(__k); 1352 return { { __res.first, this }, { __res.second, this } }; 1353 } 1354#endif 1355 1356 std::pair<const_iterator, const_iterator> 1357 equal_range(const key_type& __key) const 1358 { 1359 auto __res = _Base::equal_range(__key); 1360 return { { __res.first, this }, { __res.second, this } }; 1361 } 1362 1363#if __cplusplus > 201703L 1364 template<typename _Kt, 1365 typename = std::__has_is_transparent_t<_Hash, _Kt>, 1366 typename = std::__has_is_transparent_t<_Pred, _Kt>> 1367 std::pair<const_iterator, const_iterator> 1368 equal_range(const _Kt& __k) const 1369 { 1370 auto __res = _Base::equal_range(__k); 1371 return { { __res.first, this }, { __res.second, this } }; 1372 } 1373#endif 1374 1375 size_type 1376 erase(const key_type& __key) 1377 { 1378 size_type __ret(0); 1379 size_type __bucket_count = this->bucket_count(); 1380 auto __pair = _Base::equal_range(__key); 1381 for (auto __victim = __pair.first; __victim != __pair.second;) 1382 { 1383 _M_invalidate(__victim); 1384 __victim = _Base::erase(__victim); 1385 ++__ret; 1386 } 1387 1388 _M_check_rehashed(__bucket_count); 1389 return __ret; 1390 } 1391 1392 iterator 1393 erase(const_iterator __it) 1394 { 1395 __glibcxx_check_erase(__it); 1396 return { _M_erase(__it.base()), this }; 1397 } 1398 1399 _Base_iterator 1400 erase(_Base_const_iterator __it) 1401 { 1402 __glibcxx_check_erase2(__it); 1403 return _M_erase(__it); 1404 } 1405 1406 iterator 1407 erase(iterator __it) 1408 { 1409 __glibcxx_check_erase(__it); 1410 return { _M_erase(__it.base()), this }; 1411 } 1412 1413 iterator 1414 erase(const_iterator __first, const_iterator __last) 1415 { 1416 __glibcxx_check_erase_range(__first, __last); 1417 for (auto __tmp = __first.base(); __tmp != __last.base(); ++__tmp) 1418 { 1419 _GLIBCXX_DEBUG_VERIFY(__tmp != _Base::cend(), 1420 _M_message(__gnu_debug::__msg_valid_range) 1421 ._M_iterator(__first, "first") 1422 ._M_iterator(__last, "last")); 1423 _M_invalidate(__tmp); 1424 } 1425 1426 size_type __bucket_count = this->bucket_count(); 1427 auto __next = _Base::erase(__first.base(), __last.base()); 1428 _M_check_rehashed(__bucket_count); 1429 return { __next, this }; 1430 } 1431 1432 using _Base::rehash; 1433 using _Base::reserve; 1434 1435 _Base& 1436 _M_base() noexcept { return *this; } 1437 1438 const _Base& 1439 _M_base() const noexcept { return *this; } 1440 1441 private: 1442 void 1443 _M_check_rehashed(size_type __prev_count) 1444 { 1445 if (__prev_count != this->bucket_count()) 1446 this->_M_invalidate_all(); 1447 } 1448 1449 void 1450 _M_invalidate(_Base_const_iterator __victim) 1451 { 1452 this->_M_invalidate_if( 1453 [__victim](_Base_const_iterator __it) { return __it == __victim; }); 1454 this->_M_invalidate_local_if( 1455 [__victim](_Base_const_local_iterator __it) 1456 { return __it == __victim; }); 1457 } 1458 1459 _Base_iterator 1460 _M_erase(_Base_const_iterator __victim) 1461 { 1462 _M_invalidate(__victim); 1463 size_type __bucket_count = this->bucket_count(); 1464 _Base_iterator __next = _Base::erase(__victim); 1465 _M_check_rehashed(__bucket_count); 1466 return __next; 1467 } 1468 1469#if __cplusplus > 201402L 1470 node_type 1471 _M_extract(_Base_const_iterator __victim) 1472 { 1473 _M_invalidate(__victim); 1474 return _Base::extract(__victim); 1475 } 1476#endif 1477 }; 1478 1479#if __cpp_deduction_guides >= 201606 1480 1481 template<typename _InputIterator, 1482 typename _Hash = hash<__iter_key_t<_InputIterator>>, 1483 typename _Pred = equal_to<__iter_key_t<_InputIterator>>, 1484 typename _Allocator = allocator<__iter_to_alloc_t<_InputIterator>>, 1485 typename = _RequireInputIter<_InputIterator>, 1486 typename = _RequireNotAllocatorOrIntegral<_Hash>, 1487 typename = _RequireNotAllocator<_Pred>, 1488 typename = _RequireAllocator<_Allocator>> 1489 unordered_multimap(_InputIterator, _InputIterator, 1490 unordered_multimap<int, int>::size_type = {}, 1491 _Hash = _Hash(), _Pred = _Pred(), 1492 _Allocator = _Allocator()) 1493 -> unordered_multimap<__iter_key_t<_InputIterator>, 1494 __iter_val_t<_InputIterator>, _Hash, _Pred, 1495 _Allocator>; 1496 1497 template<typename _Key, typename _Tp, typename _Hash = hash<_Key>, 1498 typename _Pred = equal_to<_Key>, 1499 typename _Allocator = allocator<pair<const _Key, _Tp>>, 1500 typename = _RequireNotAllocatorOrIntegral<_Hash>, 1501 typename = _RequireNotAllocator<_Pred>, 1502 typename = _RequireAllocator<_Allocator>> 1503 unordered_multimap(initializer_list<pair<_Key, _Tp>>, 1504 unordered_multimap<int, int>::size_type = {}, 1505 _Hash = _Hash(), _Pred = _Pred(), 1506 _Allocator = _Allocator()) 1507 -> unordered_multimap<_Key, _Tp, _Hash, _Pred, _Allocator>; 1508 1509 template<typename _InputIterator, typename _Allocator, 1510 typename = _RequireInputIter<_InputIterator>, 1511 typename = _RequireAllocator<_Allocator>> 1512 unordered_multimap(_InputIterator, _InputIterator, 1513 unordered_multimap<int, int>::size_type, _Allocator) 1514 -> unordered_multimap<__iter_key_t<_InputIterator>, 1515 __iter_val_t<_InputIterator>, 1516 hash<__iter_key_t<_InputIterator>>, 1517 equal_to<__iter_key_t<_InputIterator>>, _Allocator>; 1518 1519 template<typename _InputIterator, typename _Allocator, 1520 typename = _RequireInputIter<_InputIterator>, 1521 typename = _RequireAllocator<_Allocator>> 1522 unordered_multimap(_InputIterator, _InputIterator, _Allocator) 1523 -> unordered_multimap<__iter_key_t<_InputIterator>, 1524 __iter_val_t<_InputIterator>, 1525 hash<__iter_key_t<_InputIterator>>, 1526 equal_to<__iter_key_t<_InputIterator>>, _Allocator>; 1527 1528 template<typename _InputIterator, typename _Hash, typename _Allocator, 1529 typename = _RequireInputIter<_InputIterator>, 1530 typename = _RequireNotAllocatorOrIntegral<_Hash>, 1531 typename = _RequireAllocator<_Allocator>> 1532 unordered_multimap(_InputIterator, _InputIterator, 1533 unordered_multimap<int, int>::size_type, _Hash, 1534 _Allocator) 1535 -> unordered_multimap<__iter_key_t<_InputIterator>, 1536 __iter_val_t<_InputIterator>, _Hash, 1537 equal_to<__iter_key_t<_InputIterator>>, _Allocator>; 1538 1539 template<typename _Key, typename _Tp, typename _Allocator, 1540 typename = _RequireAllocator<_Allocator>> 1541 unordered_multimap(initializer_list<pair<_Key, _Tp>>, 1542 unordered_multimap<int, int>::size_type, 1543 _Allocator) 1544 -> unordered_multimap<_Key, _Tp, hash<_Key>, equal_to<_Key>, _Allocator>; 1545 1546 template<typename _Key, typename _Tp, typename _Allocator, 1547 typename = _RequireAllocator<_Allocator>> 1548 unordered_multimap(initializer_list<pair<_Key, _Tp>>, _Allocator) 1549 -> unordered_multimap<_Key, _Tp, hash<_Key>, equal_to<_Key>, _Allocator>; 1550 1551 template<typename _Key, typename _Tp, typename _Hash, typename _Allocator, 1552 typename = _RequireNotAllocatorOrIntegral<_Hash>, 1553 typename = _RequireAllocator<_Allocator>> 1554 unordered_multimap(initializer_list<pair<_Key, _Tp>>, 1555 unordered_multimap<int, int>::size_type, 1556 _Hash, _Allocator) 1557 -> unordered_multimap<_Key, _Tp, _Hash, equal_to<_Key>, _Allocator>; 1558 1559#endif 1560 1561 template<typename _Key, typename _Tp, typename _Hash, 1562 typename _Pred, typename _Alloc> 1563 inline void 1564 swap(unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, 1565 unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) 1566 noexcept(noexcept(__x.swap(__y))) 1567 { __x.swap(__y); } 1568 1569 template<typename _Key, typename _Tp, typename _Hash, 1570 typename _Pred, typename _Alloc> 1571 inline bool 1572 operator==(const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, 1573 const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) 1574 { return __x._M_base() == __y._M_base(); } 1575 1576#if __cpp_impl_three_way_comparison < 201907L 1577 template<typename _Key, typename _Tp, typename _Hash, 1578 typename _Pred, typename _Alloc> 1579 inline bool 1580 operator!=(const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, 1581 const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) 1582 { return !(__x == __y); } 1583#endif 1584 1585} // namespace __debug 1586} // namespace std 1587 1588#endif // C++11 1589 1590#endif 1591