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