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