1// Debugging unordered_map/unordered_multimap implementation -*- C++ -*- 2 3// Copyright (C) 2003-2016 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#if __cplusplus < 201103L 33# include <bits/c++0x_warning.h> 34#else 35# include <unordered_map> 36 37#include <debug/safe_unordered_container.h> 38#include <debug/safe_container.h> 39#include <debug/safe_iterator.h> 40#include <debug/safe_local_iterator.h> 41 42namespace std _GLIBCXX_VISIBILITY(default) 43{ 44namespace __debug 45{ 46 /// Class std::unordered_map with safety/checking/debug instrumentation. 47 template<typename _Key, typename _Tp, 48 typename _Hash = std::hash<_Key>, 49 typename _Pred = std::equal_to<_Key>, 50 typename _Alloc = std::allocator<std::pair<const _Key, _Tp> > > 51 class unordered_map 52 : public __gnu_debug::_Safe_container< 53 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>, _Alloc, 54 __gnu_debug::_Safe_unordered_container>, 55 public _GLIBCXX_STD_C::unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc> 56 { 57 typedef _GLIBCXX_STD_C::unordered_map<_Key, _Tp, _Hash, 58 _Pred, _Alloc> _Base; 59 typedef __gnu_debug::_Safe_container<unordered_map, 60 _Alloc, __gnu_debug::_Safe_unordered_container> _Safe; 61 typedef typename _Base::const_iterator _Base_const_iterator; 62 typedef typename _Base::iterator _Base_iterator; 63 typedef typename _Base::const_local_iterator 64 _Base_const_local_iterator; 65 typedef typename _Base::local_iterator _Base_local_iterator; 66 67 public: 68 typedef typename _Base::size_type size_type; 69 typedef typename _Base::hasher hasher; 70 typedef typename _Base::key_equal key_equal; 71 typedef typename _Base::allocator_type allocator_type; 72 73 typedef typename _Base::key_type key_type; 74 typedef typename _Base::value_type value_type; 75 76 typedef __gnu_debug::_Safe_iterator< 77 _Base_iterator, unordered_map> iterator; 78 typedef __gnu_debug::_Safe_iterator< 79 _Base_const_iterator, unordered_map> const_iterator; 80 typedef __gnu_debug::_Safe_local_iterator< 81 _Base_local_iterator, unordered_map> local_iterator; 82 typedef __gnu_debug::_Safe_local_iterator< 83 _Base_const_local_iterator, unordered_map> const_local_iterator; 84 85 unordered_map() = default; 86 87 explicit 88 unordered_map(size_type __n, 89 const hasher& __hf = hasher(), 90 const key_equal& __eql = key_equal(), 91 const allocator_type& __a = allocator_type()) 92 : _Base(__n, __hf, __eql, __a) { } 93 94 template<typename _InputIterator> 95 unordered_map(_InputIterator __first, _InputIterator __last, 96 size_type __n = 0, 97 const hasher& __hf = hasher(), 98 const key_equal& __eql = key_equal(), 99 const allocator_type& __a = allocator_type()) 100 : _Base(__gnu_debug::__base(__gnu_debug::__check_valid_range(__first, 101 __last)), 102 __gnu_debug::__base(__last), __n, 103 __hf, __eql, __a) { } 104 105 unordered_map(const unordered_map&) = default; 106 107 unordered_map(const _Base& __x) 108 : _Base(__x) { } 109 110 unordered_map(unordered_map&&) = default; 111 112 explicit 113 unordered_map(const allocator_type& __a) 114 : _Base(__a) { } 115 116 unordered_map(const unordered_map& __umap, 117 const allocator_type& __a) 118 : _Base(__umap, __a) { } 119 120 unordered_map(unordered_map&& __umap, 121 const allocator_type& __a) 122 : _Safe(std::move(__umap._M_safe()), __a), 123 _Base(std::move(__umap._M_base()), __a) { } 124 125 unordered_map(initializer_list<value_type> __l, 126 size_type __n = 0, 127 const hasher& __hf = hasher(), 128 const key_equal& __eql = key_equal(), 129 const allocator_type& __a = allocator_type()) 130 : _Base(__l, __n, __hf, __eql, __a) { } 131 132 unordered_map(size_type __n, const allocator_type& __a) 133 : unordered_map(__n, hasher(), key_equal(), __a) 134 { } 135 136 unordered_map(size_type __n, 137 const hasher& __hf, 138 const allocator_type& __a) 139 : unordered_map(__n, __hf, key_equal(), __a) 140 { } 141 142 template<typename _InputIterator> 143 unordered_map(_InputIterator __first, _InputIterator __last, 144 size_type __n, 145 const allocator_type& __a) 146 : unordered_map(__first, __last, __n, hasher(), key_equal(), __a) 147 { } 148 149 template<typename _InputIterator> 150 unordered_map(_InputIterator __first, _InputIterator __last, 151 size_type __n, 152 const hasher& __hf, 153 const allocator_type& __a) 154 : unordered_map(__first, __last, __n, __hf, key_equal(), __a) 155 { } 156 157 unordered_map(initializer_list<value_type> __l, 158 size_type __n, 159 const allocator_type& __a) 160 : unordered_map(__l, __n, hasher(), key_equal(), __a) 161 { } 162 163 unordered_map(initializer_list<value_type> __l, 164 size_type __n, 165 const hasher& __hf, 166 const allocator_type& __a) 167 : unordered_map(__l, __n, __hf, key_equal(), __a) 168 { } 169 170 ~unordered_map() = default; 171 172 unordered_map& 173 operator=(const unordered_map&) = default; 174 175 unordered_map& 176 operator=(unordered_map&&) = default; 177 178 unordered_map& 179 operator=(initializer_list<value_type> __l) 180 { 181 _M_base() = __l; 182 this->_M_invalidate_all(); 183 return *this; 184 } 185 186 void 187 swap(unordered_map& __x) 188 noexcept( noexcept(declval<_Base&>().swap(__x)) ) 189 { 190 _Safe::_M_swap(__x); 191 _Base::swap(__x); 192 } 193 194 void 195 clear() noexcept 196 { 197 _Base::clear(); 198 this->_M_invalidate_all(); 199 } 200 201 iterator 202 begin() noexcept 203 { return iterator(_Base::begin(), this); } 204 205 const_iterator 206 begin() const noexcept 207 { return const_iterator(_Base::begin(), this); } 208 209 iterator 210 end() noexcept 211 { return iterator(_Base::end(), this); } 212 213 const_iterator 214 end() const noexcept 215 { return const_iterator(_Base::end(), this); } 216 217 const_iterator 218 cbegin() const noexcept 219 { return const_iterator(_Base::begin(), this); } 220 221 const_iterator 222 cend() const noexcept 223 { return const_iterator(_Base::end(), this); } 224 225 // local versions 226 local_iterator 227 begin(size_type __b) 228 { 229 __glibcxx_check_bucket_index(__b); 230 return local_iterator(_Base::begin(__b), this); 231 } 232 233 local_iterator 234 end(size_type __b) 235 { 236 __glibcxx_check_bucket_index(__b); 237 return local_iterator(_Base::end(__b), this); 238 } 239 240 const_local_iterator 241 begin(size_type __b) const 242 { 243 __glibcxx_check_bucket_index(__b); 244 return const_local_iterator(_Base::begin(__b), this); 245 } 246 247 const_local_iterator 248 end(size_type __b) const 249 { 250 __glibcxx_check_bucket_index(__b); 251 return const_local_iterator(_Base::end(__b), this); 252 } 253 254 const_local_iterator 255 cbegin(size_type __b) const 256 { 257 __glibcxx_check_bucket_index(__b); 258 return const_local_iterator(_Base::cbegin(__b), this); 259 } 260 261 const_local_iterator 262 cend(size_type __b) const 263 { 264 __glibcxx_check_bucket_index(__b); 265 return const_local_iterator(_Base::cend(__b), this); 266 } 267 268 size_type 269 bucket_size(size_type __b) const 270 { 271 __glibcxx_check_bucket_index(__b); 272 return _Base::bucket_size(__b); 273 } 274 275 float 276 max_load_factor() const noexcept 277 { return _Base::max_load_factor(); } 278 279 void 280 max_load_factor(float __f) 281 { 282 __glibcxx_check_max_load_factor(__f); 283 _Base::max_load_factor(__f); 284 } 285 286 template<typename... _Args> 287 std::pair<iterator, bool> 288 emplace(_Args&&... __args) 289 { 290 size_type __bucket_count = this->bucket_count(); 291 std::pair<_Base_iterator, bool> __res 292 = _Base::emplace(std::forward<_Args>(__args)...); 293 _M_check_rehashed(__bucket_count); 294 return std::make_pair(iterator(__res.first, this), __res.second); 295 } 296 297 template<typename... _Args> 298 iterator 299 emplace_hint(const_iterator __hint, _Args&&... __args) 300 { 301 __glibcxx_check_insert(__hint); 302 size_type __bucket_count = this->bucket_count(); 303 _Base_iterator __it = _Base::emplace_hint(__hint.base(), 304 std::forward<_Args>(__args)...); 305 _M_check_rehashed(__bucket_count); 306 return iterator(__it, this); 307 } 308 309 std::pair<iterator, bool> 310 insert(const value_type& __obj) 311 { 312 size_type __bucket_count = this->bucket_count(); 313 std::pair<_Base_iterator, bool> __res = _Base::insert(__obj); 314 _M_check_rehashed(__bucket_count); 315 return std::make_pair(iterator(__res.first, this), __res.second); 316 } 317 318 iterator 319 insert(const_iterator __hint, const value_type& __obj) 320 { 321 __glibcxx_check_insert(__hint); 322 size_type __bucket_count = this->bucket_count(); 323 _Base_iterator __it = _Base::insert(__hint.base(), __obj); 324 _M_check_rehashed(__bucket_count); 325 return iterator(__it, this); 326 } 327 328 template<typename _Pair, typename = typename 329 std::enable_if<std::is_constructible<value_type, 330 _Pair&&>::value>::type> 331 std::pair<iterator, bool> 332 insert(_Pair&& __obj) 333 { 334 size_type __bucket_count = this->bucket_count(); 335 std::pair<_Base_iterator, bool> __res = 336 _Base::insert(std::forward<_Pair>(__obj)); 337 _M_check_rehashed(__bucket_count); 338 return std::make_pair(iterator(__res.first, this), __res.second); 339 } 340 341 template<typename _Pair, typename = typename 342 std::enable_if<std::is_constructible<value_type, 343 _Pair&&>::value>::type> 344 iterator 345 insert(const_iterator __hint, _Pair&& __obj) 346 { 347 __glibcxx_check_insert(__hint); 348 size_type __bucket_count = this->bucket_count(); 349 _Base_iterator __it = 350 _Base::insert(__hint.base(), std::forward<_Pair>(__obj)); 351 _M_check_rehashed(__bucket_count); 352 return iterator(__it, this); 353 } 354 355 void 356 insert(std::initializer_list<value_type> __l) 357 { 358 size_type __bucket_count = this->bucket_count(); 359 _Base::insert(__l); 360 _M_check_rehashed(__bucket_count); 361 } 362 363 template<typename _InputIterator> 364 void 365 insert(_InputIterator __first, _InputIterator __last) 366 { 367 typename __gnu_debug::_Distance_traits<_InputIterator>::__type __dist; 368 __glibcxx_check_valid_range2(__first, __last, __dist); 369 size_type __bucket_count = this->bucket_count(); 370 371 if (__dist.second >= __gnu_debug::__dp_sign) 372 _Base::insert(__gnu_debug::__unsafe(__first), 373 __gnu_debug::__unsafe(__last)); 374 else 375 _Base::insert(__first, __last); 376 377 _M_check_rehashed(__bucket_count); 378 } 379 380#if __cplusplus > 201402L 381 template <typename... _Args> 382 pair<iterator, bool> 383 try_emplace(const key_type& __k, _Args&&... __args) 384 { 385 auto __res = _Base::try_emplace(__k, 386 std::forward<_Args>(__args)...); 387 return { iterator(__res.first, this), __res.second }; 388 } 389 390 template <typename... _Args> 391 pair<iterator, bool> 392 try_emplace(key_type&& __k, _Args&&... __args) 393 { 394 auto __res = _Base::try_emplace(std::move(__k), 395 std::forward<_Args>(__args)...); 396 return { iterator(__res.first, this), __res.second }; 397 } 398 399 template <typename... _Args> 400 iterator 401 try_emplace(const_iterator __hint, const key_type& __k, 402 _Args&&... __args) 403 { 404 __glibcxx_check_insert(__hint); 405 return iterator(_Base::try_emplace(__hint.base(), __k, 406 std::forward<_Args>(__args)...), 407 this); 408 } 409 410 template <typename... _Args> 411 iterator 412 try_emplace(const_iterator __hint, key_type&& __k, _Args&&... __args) 413 { 414 __glibcxx_check_insert(__hint); 415 return iterator(_Base::try_emplace(__hint.base(), std::move(__k), 416 std::forward<_Args>(__args)...), 417 this); 418 } 419 420 template <typename _Obj> 421 pair<iterator, bool> 422 insert_or_assign(const key_type& __k, _Obj&& __obj) 423 { 424 auto __res = _Base::insert_or_assign(__k, 425 std::forward<_Obj>(__obj)); 426 return { iterator(__res.first, this), __res.second }; 427 } 428 429 template <typename _Obj> 430 pair<iterator, bool> 431 insert_or_assign(key_type&& __k, _Obj&& __obj) 432 { 433 auto __res = _Base::insert_or_assign(std::move(__k), 434 std::forward<_Obj>(__obj)); 435 return { iterator(__res.first, this), __res.second }; 436 } 437 438 template <typename _Obj> 439 iterator 440 insert_or_assign(const_iterator __hint, const key_type& __k, 441 _Obj&& __obj) 442 { 443 __glibcxx_check_insert(__hint); 444 return iterator(_Base::insert_or_assign(__hint.base(), __k, 445 std::forward<_Obj>(__obj)), 446 this); 447 } 448 449 template <typename _Obj> 450 iterator 451 insert_or_assign(const_iterator __hint, key_type&& __k, _Obj&& __obj) 452 { 453 __glibcxx_check_insert(__hint); 454 return iterator(_Base::insert_or_assign(__hint.base(), 455 std::move(__k), 456 std::forward<_Obj>(__obj)), 457 this); 458 } 459#endif 460 461 462 iterator 463 find(const key_type& __key) 464 { return iterator(_Base::find(__key), this); } 465 466 const_iterator 467 find(const key_type& __key) const 468 { return const_iterator(_Base::find(__key), this); } 469 470 std::pair<iterator, iterator> 471 equal_range(const key_type& __key) 472 { 473 std::pair<_Base_iterator, _Base_iterator> __res = 474 _Base::equal_range(__key); 475 return std::make_pair(iterator(__res.first, this), 476 iterator(__res.second, this)); 477 } 478 479 std::pair<const_iterator, const_iterator> 480 equal_range(const key_type& __key) const 481 { 482 std::pair<_Base_const_iterator, _Base_const_iterator> __res = 483 _Base::equal_range(__key); 484 return std::make_pair(const_iterator(__res.first, this), 485 const_iterator(__res.second, this)); 486 } 487 488 size_type 489 erase(const key_type& __key) 490 { 491 size_type __ret(0); 492 _Base_iterator __victim(_Base::find(__key)); 493 if (__victim != _Base::end()) 494 { 495 this->_M_invalidate_if([__victim](_Base_const_iterator __it) 496 { return __it == __victim; }); 497 this->_M_invalidate_local_if( 498 [__victim](_Base_const_local_iterator __it) 499 { return __it._M_curr() == __victim._M_cur; }); 500 size_type __bucket_count = this->bucket_count(); 501 _Base::erase(__victim); 502 _M_check_rehashed(__bucket_count); 503 __ret = 1; 504 } 505 return __ret; 506 } 507 508 iterator 509 erase(const_iterator __it) 510 { 511 __glibcxx_check_erase(__it); 512 _Base_const_iterator __victim = __it.base(); 513 this->_M_invalidate_if([__victim](_Base_const_iterator __it) 514 { return __it == __victim; }); 515 this->_M_invalidate_local_if( 516 [__victim](_Base_const_local_iterator __it) 517 { return __it._M_curr() == __victim._M_cur; }); 518 size_type __bucket_count = this->bucket_count(); 519 _Base_iterator __next = _Base::erase(__it.base()); 520 _M_check_rehashed(__bucket_count); 521 return iterator(__next, this); 522 } 523 524 iterator 525 erase(iterator __it) 526 { return erase(const_iterator(__it)); } 527 528 iterator 529 erase(const_iterator __first, const_iterator __last) 530 { 531 __glibcxx_check_erase_range(__first, __last); 532 for (_Base_const_iterator __tmp = __first.base(); 533 __tmp != __last.base(); ++__tmp) 534 { 535 _GLIBCXX_DEBUG_VERIFY(__tmp != _Base::end(), 536 _M_message(__gnu_debug::__msg_valid_range) 537 ._M_iterator(__first, "first") 538 ._M_iterator(__last, "last")); 539 this->_M_invalidate_if([__tmp](_Base_const_iterator __it) 540 { return __it == __tmp; }); 541 this->_M_invalidate_local_if( 542 [__tmp](_Base_const_local_iterator __it) 543 { return __it._M_curr() == __tmp._M_cur; }); 544 } 545 size_type __bucket_count = this->bucket_count(); 546 _Base_iterator __next = _Base::erase(__first.base(), __last.base()); 547 _M_check_rehashed(__bucket_count); 548 return iterator(__next, this); 549 } 550 551 _Base& 552 _M_base() noexcept { return *this; } 553 554 const _Base& 555 _M_base() const noexcept { return *this; } 556 557 private: 558 void 559 _M_check_rehashed(size_type __prev_count) 560 { 561 if (__prev_count != this->bucket_count()) 562 this->_M_invalidate_locals(); 563 } 564 }; 565 566 template<typename _Key, typename _Tp, typename _Hash, 567 typename _Pred, typename _Alloc> 568 inline void 569 swap(unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, 570 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) 571 noexcept(noexcept(__x.swap(__y))) 572 { __x.swap(__y); } 573 574 template<typename _Key, typename _Tp, typename _Hash, 575 typename _Pred, typename _Alloc> 576 inline bool 577 operator==(const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, 578 const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) 579 { return __x._M_base() == __y._M_base(); } 580 581 template<typename _Key, typename _Tp, typename _Hash, 582 typename _Pred, typename _Alloc> 583 inline bool 584 operator!=(const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, 585 const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) 586 { return !(__x == __y); } 587 588 589 /// Class std::unordered_multimap with safety/checking/debug instrumentation. 590 template<typename _Key, typename _Tp, 591 typename _Hash = std::hash<_Key>, 592 typename _Pred = std::equal_to<_Key>, 593 typename _Alloc = std::allocator<std::pair<const _Key, _Tp> > > 594 class unordered_multimap 595 : public __gnu_debug::_Safe_container< 596 unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>, _Alloc, 597 __gnu_debug::_Safe_unordered_container>, 598 public _GLIBCXX_STD_C::unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc> 599 { 600 typedef _GLIBCXX_STD_C::unordered_multimap<_Key, _Tp, _Hash, 601 _Pred, _Alloc> _Base; 602 typedef __gnu_debug::_Safe_container<unordered_multimap, 603 _Alloc, __gnu_debug::_Safe_unordered_container> _Safe; 604 typedef typename _Base::const_iterator _Base_const_iterator; 605 typedef typename _Base::iterator _Base_iterator; 606 typedef typename _Base::const_local_iterator _Base_const_local_iterator; 607 typedef typename _Base::local_iterator _Base_local_iterator; 608 609 public: 610 typedef typename _Base::size_type size_type; 611 typedef typename _Base::hasher hasher; 612 typedef typename _Base::key_equal key_equal; 613 typedef typename _Base::allocator_type allocator_type; 614 615 typedef typename _Base::key_type key_type; 616 typedef typename _Base::value_type value_type; 617 618 typedef __gnu_debug::_Safe_iterator< 619 _Base_iterator, unordered_multimap> iterator; 620 typedef __gnu_debug::_Safe_iterator< 621 _Base_const_iterator, unordered_multimap> const_iterator; 622 typedef __gnu_debug::_Safe_local_iterator< 623 _Base_local_iterator, unordered_multimap> local_iterator; 624 typedef __gnu_debug::_Safe_local_iterator< 625 _Base_const_local_iterator, unordered_multimap> const_local_iterator; 626 627 unordered_multimap() = default; 628 629 explicit 630 unordered_multimap(size_type __n, 631 const hasher& __hf = hasher(), 632 const key_equal& __eql = key_equal(), 633 const allocator_type& __a = allocator_type()) 634 : _Base(__n, __hf, __eql, __a) { } 635 636 template<typename _InputIterator> 637 unordered_multimap(_InputIterator __first, _InputIterator __last, 638 size_type __n = 0, 639 const hasher& __hf = hasher(), 640 const key_equal& __eql = key_equal(), 641 const allocator_type& __a = allocator_type()) 642 : _Base(__gnu_debug::__base(__gnu_debug::__check_valid_range(__first, 643 __last)), 644 __gnu_debug::__base(__last), __n, 645 __hf, __eql, __a) { } 646 647 unordered_multimap(const unordered_multimap&) = default; 648 649 unordered_multimap(const _Base& __x) 650 : _Base(__x) { } 651 652 unordered_multimap(unordered_multimap&&) = default; 653 654 explicit 655 unordered_multimap(const allocator_type& __a) 656 : _Base(__a) { } 657 658 unordered_multimap(const unordered_multimap& __umap, 659 const allocator_type& __a) 660 : _Base(__umap, __a) { } 661 662 unordered_multimap(unordered_multimap&& __umap, 663 const allocator_type& __a) 664 : _Safe(std::move(__umap._M_safe()), __a), 665 _Base(std::move(__umap._M_base()), __a) { } 666 667 unordered_multimap(initializer_list<value_type> __l, 668 size_type __n = 0, 669 const hasher& __hf = hasher(), 670 const key_equal& __eql = key_equal(), 671 const allocator_type& __a = allocator_type()) 672 : _Base(__l, __n, __hf, __eql, __a) { } 673 674 unordered_multimap(size_type __n, const allocator_type& __a) 675 : unordered_multimap(__n, hasher(), key_equal(), __a) 676 { } 677 678 unordered_multimap(size_type __n, const hasher& __hf, 679 const allocator_type& __a) 680 : unordered_multimap(__n, __hf, key_equal(), __a) 681 { } 682 683 template<typename _InputIterator> 684 unordered_multimap(_InputIterator __first, _InputIterator __last, 685 size_type __n, 686 const allocator_type& __a) 687 : unordered_multimap(__first, __last, __n, hasher(), key_equal(), __a) 688 { } 689 690 template<typename _InputIterator> 691 unordered_multimap(_InputIterator __first, _InputIterator __last, 692 size_type __n, const hasher& __hf, 693 const allocator_type& __a) 694 : unordered_multimap(__first, __last, __n, __hf, key_equal(), __a) 695 { } 696 697 unordered_multimap(initializer_list<value_type> __l, 698 size_type __n, 699 const allocator_type& __a) 700 : unordered_multimap(__l, __n, hasher(), key_equal(), __a) 701 { } 702 703 unordered_multimap(initializer_list<value_type> __l, 704 size_type __n, const hasher& __hf, 705 const allocator_type& __a) 706 : unordered_multimap(__l, __n, __hf, key_equal(), __a) 707 { } 708 709 ~unordered_multimap() = default; 710 711 unordered_multimap& 712 operator=(const unordered_multimap&) = default; 713 714 unordered_multimap& 715 operator=(unordered_multimap&&) = default; 716 717 unordered_multimap& 718 operator=(initializer_list<value_type> __l) 719 { 720 this->_M_base() = __l; 721 this->_M_invalidate_all(); 722 return *this; 723 } 724 725 void 726 swap(unordered_multimap& __x) 727 noexcept( noexcept(declval<_Base&>().swap(__x)) ) 728 { 729 _Safe::_M_swap(__x); 730 _Base::swap(__x); 731 } 732 733 void 734 clear() noexcept 735 { 736 _Base::clear(); 737 this->_M_invalidate_all(); 738 } 739 740 iterator 741 begin() noexcept 742 { return iterator(_Base::begin(), this); } 743 744 const_iterator 745 begin() const noexcept 746 { return const_iterator(_Base::begin(), this); } 747 748 iterator 749 end() noexcept 750 { return iterator(_Base::end(), this); } 751 752 const_iterator 753 end() const noexcept 754 { return const_iterator(_Base::end(), this); } 755 756 const_iterator 757 cbegin() const noexcept 758 { return const_iterator(_Base::begin(), this); } 759 760 const_iterator 761 cend() const noexcept 762 { return const_iterator(_Base::end(), this); } 763 764 // local versions 765 local_iterator 766 begin(size_type __b) 767 { 768 __glibcxx_check_bucket_index(__b); 769 return local_iterator(_Base::begin(__b), this); 770 } 771 772 local_iterator 773 end(size_type __b) 774 { 775 __glibcxx_check_bucket_index(__b); 776 return local_iterator(_Base::end(__b), this); 777 } 778 779 const_local_iterator 780 begin(size_type __b) const 781 { 782 __glibcxx_check_bucket_index(__b); 783 return const_local_iterator(_Base::begin(__b), this); 784 } 785 786 const_local_iterator 787 end(size_type __b) const 788 { 789 __glibcxx_check_bucket_index(__b); 790 return const_local_iterator(_Base::end(__b), this); 791 } 792 793 const_local_iterator 794 cbegin(size_type __b) const 795 { 796 __glibcxx_check_bucket_index(__b); 797 return const_local_iterator(_Base::cbegin(__b), this); 798 } 799 800 const_local_iterator 801 cend(size_type __b) const 802 { 803 __glibcxx_check_bucket_index(__b); 804 return const_local_iterator(_Base::cend(__b), this); 805 } 806 807 size_type 808 bucket_size(size_type __b) const 809 { 810 __glibcxx_check_bucket_index(__b); 811 return _Base::bucket_size(__b); 812 } 813 814 float 815 max_load_factor() const noexcept 816 { return _Base::max_load_factor(); } 817 818 void 819 max_load_factor(float __f) 820 { 821 __glibcxx_check_max_load_factor(__f); 822 _Base::max_load_factor(__f); 823 } 824 825 template<typename... _Args> 826 iterator 827 emplace(_Args&&... __args) 828 { 829 size_type __bucket_count = this->bucket_count(); 830 _Base_iterator __it 831 = _Base::emplace(std::forward<_Args>(__args)...); 832 _M_check_rehashed(__bucket_count); 833 return iterator(__it, this); 834 } 835 836 template<typename... _Args> 837 iterator 838 emplace_hint(const_iterator __hint, _Args&&... __args) 839 { 840 __glibcxx_check_insert(__hint); 841 size_type __bucket_count = this->bucket_count(); 842 _Base_iterator __it = _Base::emplace_hint(__hint.base(), 843 std::forward<_Args>(__args)...); 844 _M_check_rehashed(__bucket_count); 845 return iterator(__it, this); 846 } 847 848 iterator 849 insert(const value_type& __obj) 850 { 851 size_type __bucket_count = this->bucket_count(); 852 _Base_iterator __it = _Base::insert(__obj); 853 _M_check_rehashed(__bucket_count); 854 return iterator(__it, this); 855 } 856 857 iterator 858 insert(const_iterator __hint, const value_type& __obj) 859 { 860 __glibcxx_check_insert(__hint); 861 size_type __bucket_count = this->bucket_count(); 862 _Base_iterator __it = _Base::insert(__hint.base(), __obj); 863 _M_check_rehashed(__bucket_count); 864 return iterator(__it, this); 865 } 866 867 template<typename _Pair, typename = typename 868 std::enable_if<std::is_constructible<value_type, 869 _Pair&&>::value>::type> 870 iterator 871 insert(_Pair&& __obj) 872 { 873 size_type __bucket_count = this->bucket_count(); 874 _Base_iterator __it = _Base::insert(std::forward<_Pair>(__obj)); 875 _M_check_rehashed(__bucket_count); 876 return iterator(__it, this); 877 } 878 879 template<typename _Pair, typename = typename 880 std::enable_if<std::is_constructible<value_type, 881 _Pair&&>::value>::type> 882 iterator 883 insert(const_iterator __hint, _Pair&& __obj) 884 { 885 __glibcxx_check_insert(__hint); 886 size_type __bucket_count = this->bucket_count(); 887 _Base_iterator __it = 888 _Base::insert(__hint.base(), std::forward<_Pair>(__obj)); 889 _M_check_rehashed(__bucket_count); 890 return iterator(__it, this); 891 } 892 893 void 894 insert(std::initializer_list<value_type> __l) 895 { _Base::insert(__l); } 896 897 template<typename _InputIterator> 898 void 899 insert(_InputIterator __first, _InputIterator __last) 900 { 901 typename __gnu_debug::_Distance_traits<_InputIterator>::__type __dist; 902 __glibcxx_check_valid_range2(__first, __last, __dist); 903 size_type __bucket_count = this->bucket_count(); 904 905 if (__dist.second >= __gnu_debug::__dp_sign) 906 _Base::insert(__gnu_debug::__unsafe(__first), 907 __gnu_debug::__unsafe(__last)); 908 else 909 _Base::insert(__first, __last); 910 911 _M_check_rehashed(__bucket_count); 912 } 913 914 iterator 915 find(const key_type& __key) 916 { return iterator(_Base::find(__key), this); } 917 918 const_iterator 919 find(const key_type& __key) const 920 { return const_iterator(_Base::find(__key), this); } 921 922 std::pair<iterator, iterator> 923 equal_range(const key_type& __key) 924 { 925 std::pair<_Base_iterator, _Base_iterator> __res = 926 _Base::equal_range(__key); 927 return std::make_pair(iterator(__res.first, this), 928 iterator(__res.second, this)); 929 } 930 931 std::pair<const_iterator, const_iterator> 932 equal_range(const key_type& __key) const 933 { 934 std::pair<_Base_const_iterator, _Base_const_iterator> __res = 935 _Base::equal_range(__key); 936 return std::make_pair(const_iterator(__res.first, this), 937 const_iterator(__res.second, this)); 938 } 939 940 size_type 941 erase(const key_type& __key) 942 { 943 size_type __ret(0); 944 size_type __bucket_count = this->bucket_count(); 945 std::pair<_Base_iterator, _Base_iterator> __pair = 946 _Base::equal_range(__key); 947 for (_Base_iterator __victim = __pair.first; __victim != __pair.second;) 948 { 949 this->_M_invalidate_if([__victim](_Base_const_iterator __it) 950 { return __it == __victim; }); 951 this->_M_invalidate_local_if( 952 [__victim](_Base_const_local_iterator __it) 953 { return __it._M_curr() == __victim._M_cur; }); 954 _Base::erase(__victim++); 955 ++__ret; 956 } 957 _M_check_rehashed(__bucket_count); 958 return __ret; 959 } 960 961 iterator 962 erase(const_iterator __it) 963 { 964 __glibcxx_check_erase(__it); 965 _Base_const_iterator __victim = __it.base(); 966 this->_M_invalidate_if([__victim](_Base_const_iterator __it) 967 { return __it == __victim; }); 968 this->_M_invalidate_local_if( 969 [__victim](_Base_const_local_iterator __it) 970 { return __it._M_curr() == __victim._M_cur; }); 971 size_type __bucket_count = this->bucket_count(); 972 _Base_iterator __next = _Base::erase(__it.base()); 973 _M_check_rehashed(__bucket_count); 974 return iterator(__next, this); 975 } 976 977 iterator 978 erase(iterator __it) 979 { return erase(const_iterator(__it)); } 980 981 iterator 982 erase(const_iterator __first, const_iterator __last) 983 { 984 __glibcxx_check_erase_range(__first, __last); 985 for (_Base_const_iterator __tmp = __first.base(); 986 __tmp != __last.base(); ++__tmp) 987 { 988 _GLIBCXX_DEBUG_VERIFY(__tmp != _Base::end(), 989 _M_message(__gnu_debug::__msg_valid_range) 990 ._M_iterator(__first, "first") 991 ._M_iterator(__last, "last")); 992 this->_M_invalidate_if([__tmp](_Base_const_iterator __it) 993 { return __it == __tmp; }); 994 this->_M_invalidate_local_if( 995 [__tmp](_Base_const_local_iterator __it) 996 { return __it._M_curr() == __tmp._M_cur; }); 997 } 998 size_type __bucket_count = this->bucket_count(); 999 _Base_iterator __next = _Base::erase(__first.base(), __last.base()); 1000 _M_check_rehashed(__bucket_count); 1001 return iterator(__next, this); 1002 } 1003 1004 _Base& 1005 _M_base() noexcept { return *this; } 1006 1007 const _Base& 1008 _M_base() const noexcept { return *this; } 1009 1010 private: 1011 void 1012 _M_check_rehashed(size_type __prev_count) 1013 { 1014 if (__prev_count != this->bucket_count()) 1015 this->_M_invalidate_locals(); 1016 } 1017 }; 1018 1019 template<typename _Key, typename _Tp, typename _Hash, 1020 typename _Pred, typename _Alloc> 1021 inline void 1022 swap(unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, 1023 unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) 1024 noexcept(noexcept(__x.swap(__y))) 1025 { __x.swap(__y); } 1026 1027 template<typename _Key, typename _Tp, typename _Hash, 1028 typename _Pred, typename _Alloc> 1029 inline bool 1030 operator==(const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, 1031 const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) 1032 { return __x._M_base() == __y._M_base(); } 1033 1034 template<typename _Key, typename _Tp, typename _Hash, 1035 typename _Pred, typename _Alloc> 1036 inline bool 1037 operator!=(const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, 1038 const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) 1039 { return !(__x == __y); } 1040 1041} // namespace __debug 1042} // namespace std 1043 1044#endif // C++11 1045 1046#endif 1047