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