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