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