1// Debugging unordered_set/unordered_multiset implementation -*- C++ -*- 2 3// Copyright (C) 2003-2015 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 __glibcxx_check_valid_range(__first, __last); 359 size_type __bucket_count = this->bucket_count(); 360 _Base::insert(__gnu_debug::__base(__first), 361 __gnu_debug::__base(__last)); 362 _M_check_rehashed(__bucket_count); 363 } 364 365 iterator 366 find(const key_type& __key) 367 { return iterator(_Base::find(__key), this); } 368 369 const_iterator 370 find(const key_type& __key) const 371 { return const_iterator(_Base::find(__key), this); } 372 373 std::pair<iterator, iterator> 374 equal_range(const key_type& __key) 375 { 376 std::pair<_Base_iterator, _Base_iterator> __res 377 = _Base::equal_range(__key); 378 return std::make_pair(iterator(__res.first, this), 379 iterator(__res.second, this)); 380 } 381 382 std::pair<const_iterator, const_iterator> 383 equal_range(const key_type& __key) const 384 { 385 std::pair<_Base_const_iterator, _Base_const_iterator> 386 __res = _Base::equal_range(__key); 387 return std::make_pair(const_iterator(__res.first, this), 388 const_iterator(__res.second, this)); 389 } 390 391 size_type 392 erase(const key_type& __key) 393 { 394 size_type __ret(0); 395 _Base_iterator __victim(_Base::find(__key)); 396 if (__victim != _Base::end()) 397 { 398 this->_M_invalidate_if( 399 [__victim](_Base_const_iterator __it) 400 { return __it == __victim; }); 401 this->_M_invalidate_local_if( 402 [__victim](_Base_const_local_iterator __it) 403 { return __it._M_curr() == __victim._M_cur; }); 404 size_type __bucket_count = this->bucket_count(); 405 _Base::erase(__victim); 406 _M_check_rehashed(__bucket_count); 407 __ret = 1; 408 } 409 return __ret; 410 } 411 412 iterator 413 erase(const_iterator __it) 414 { 415 __glibcxx_check_erase(__it); 416 _Base_const_iterator __victim = __it.base(); 417 this->_M_invalidate_if( 418 [__victim](_Base_const_iterator __it) 419 { return __it == __victim; }); 420 this->_M_invalidate_local_if( 421 [__victim](_Base_const_local_iterator __it) 422 { return __it._M_curr() == __victim._M_cur; }); 423 size_type __bucket_count = this->bucket_count(); 424 _Base_iterator __next = _Base::erase(__it.base()); 425 _M_check_rehashed(__bucket_count); 426 return iterator(__next, this); 427 } 428 429 iterator 430 erase(iterator __it) 431 { return erase(const_iterator(__it)); } 432 433 iterator 434 erase(const_iterator __first, const_iterator __last) 435 { 436 __glibcxx_check_erase_range(__first, __last); 437 for (_Base_const_iterator __tmp = __first.base(); 438 __tmp != __last.base(); ++__tmp) 439 { 440 _GLIBCXX_DEBUG_VERIFY(__tmp != _Base::end(), 441 _M_message(__gnu_debug::__msg_valid_range) 442 ._M_iterator(__first, "first") 443 ._M_iterator(__last, "last")); 444 this->_M_invalidate_if( 445 [__tmp](_Base_const_iterator __it) 446 { return __it == __tmp; }); 447 this->_M_invalidate_local_if( 448 [__tmp](_Base_const_local_iterator __it) 449 { return __it._M_curr() == __tmp._M_cur; }); 450 } 451 size_type __bucket_count = this->bucket_count(); 452 _Base_iterator __next = _Base::erase(__first.base(), 453 __last.base()); 454 _M_check_rehashed(__bucket_count); 455 return iterator(__next, this); 456 } 457 458 _Base& 459 _M_base() noexcept { return *this; } 460 461 const _Base& 462 _M_base() const noexcept { return *this; } 463 464 private: 465 void 466 _M_check_rehashed(size_type __prev_count) 467 { 468 if (__prev_count != this->bucket_count()) 469 this->_M_invalidate_locals(); 470 } 471 }; 472 473 template<typename _Value, typename _Hash, typename _Pred, typename _Alloc> 474 inline void 475 swap(unordered_set<_Value, _Hash, _Pred, _Alloc>& __x, 476 unordered_set<_Value, _Hash, _Pred, _Alloc>& __y) 477 { __x.swap(__y); } 478 479 template<typename _Value, typename _Hash, typename _Pred, typename _Alloc> 480 inline bool 481 operator==(const unordered_set<_Value, _Hash, _Pred, _Alloc>& __x, 482 const unordered_set<_Value, _Hash, _Pred, _Alloc>& __y) 483 { return __x._M_base() == __y._M_base(); } 484 485 template<typename _Value, typename _Hash, typename _Pred, typename _Alloc> 486 inline bool 487 operator!=(const unordered_set<_Value, _Hash, _Pred, _Alloc>& __x, 488 const unordered_set<_Value, _Hash, _Pred, _Alloc>& __y) 489 { return !(__x == __y); } 490 491 492 /// Class std::unordered_multiset with safety/checking/debug instrumentation. 493 template<typename _Value, 494 typename _Hash = std::hash<_Value>, 495 typename _Pred = std::equal_to<_Value>, 496 typename _Alloc = std::allocator<_Value> > 497 class unordered_multiset 498 : public __gnu_debug::_Safe_container< 499 unordered_multiset<_Value, _Hash, _Pred, _Alloc>, _Alloc, 500 __gnu_debug::_Safe_unordered_container>, 501 public _GLIBCXX_STD_C::unordered_multiset<_Value, _Hash, _Pred, _Alloc> 502 { 503 typedef _GLIBCXX_STD_C::unordered_multiset< 504 _Value, _Hash, _Pred, _Alloc> _Base; 505 typedef __gnu_debug::_Safe_container<unordered_multiset, 506 _Alloc, __gnu_debug::_Safe_unordered_container> _Safe; 507 typedef typename _Base::const_iterator _Base_const_iterator; 508 typedef typename _Base::iterator _Base_iterator; 509 typedef typename _Base::const_local_iterator 510 _Base_const_local_iterator; 511 typedef typename _Base::local_iterator _Base_local_iterator; 512 513 public: 514 typedef typename _Base::size_type size_type; 515 typedef typename _Base::hasher hasher; 516 typedef typename _Base::key_equal key_equal; 517 typedef typename _Base::allocator_type allocator_type; 518 519 typedef typename _Base::key_type key_type; 520 typedef typename _Base::value_type value_type; 521 522 typedef __gnu_debug::_Safe_iterator< 523 _Base_iterator, unordered_multiset> iterator; 524 typedef __gnu_debug::_Safe_iterator< 525 _Base_const_iterator, unordered_multiset> const_iterator; 526 typedef __gnu_debug::_Safe_local_iterator< 527 _Base_local_iterator, unordered_multiset> local_iterator; 528 typedef __gnu_debug::_Safe_local_iterator< 529 _Base_const_local_iterator, unordered_multiset> const_local_iterator; 530 531 unordered_multiset() = default; 532 533 explicit 534 unordered_multiset(size_type __n, 535 const hasher& __hf = hasher(), 536 const key_equal& __eql = key_equal(), 537 const allocator_type& __a = allocator_type()) 538 : _Base(__n, __hf, __eql, __a) { } 539 540 template<typename _InputIterator> 541 unordered_multiset(_InputIterator __first, _InputIterator __last, 542 size_type __n = 0, 543 const hasher& __hf = hasher(), 544 const key_equal& __eql = key_equal(), 545 const allocator_type& __a = allocator_type()) 546 : _Base(__gnu_debug::__base(__gnu_debug::__check_valid_range(__first, 547 __last)), 548 __gnu_debug::__base(__last), __n, 549 __hf, __eql, __a) { } 550 551 unordered_multiset(const unordered_multiset&) = default; 552 553 unordered_multiset(const _Base& __x) 554 : _Base(__x) { } 555 556 unordered_multiset(unordered_multiset&&) = default; 557 558 explicit 559 unordered_multiset(const allocator_type& __a) 560 : _Base(__a) { } 561 562 unordered_multiset(const unordered_multiset& __uset, 563 const allocator_type& __a) 564 : _Base(__uset, __a) { } 565 566 unordered_multiset(unordered_multiset&& __uset, 567 const allocator_type& __a) 568 : _Safe(std::move(__uset._M_safe()), __a), 569 _Base(std::move(__uset._M_base()), __a) { } 570 571 unordered_multiset(initializer_list<value_type> __l, 572 size_type __n = 0, 573 const hasher& __hf = hasher(), 574 const key_equal& __eql = key_equal(), 575 const allocator_type& __a = allocator_type()) 576 : _Base(__l, __n, __hf, __eql, __a) { } 577 578 unordered_multiset(size_type __n, const allocator_type& __a) 579 : unordered_multiset(__n, hasher(), key_equal(), __a) 580 { } 581 582 unordered_multiset(size_type __n, const hasher& __hf, 583 const allocator_type& __a) 584 : unordered_multiset(__n, __hf, key_equal(), __a) 585 { } 586 587 template<typename _InputIterator> 588 unordered_multiset(_InputIterator __first, _InputIterator __last, 589 size_type __n, 590 const allocator_type& __a) 591 : unordered_multiset(__first, __last, __n, hasher(), key_equal(), __a) 592 { } 593 594 template<typename _InputIterator> 595 unordered_multiset(_InputIterator __first, _InputIterator __last, 596 size_type __n, const hasher& __hf, 597 const allocator_type& __a) 598 : unordered_multiset(__first, __last, __n, __hf, key_equal(), __a) 599 { } 600 601 unordered_multiset(initializer_list<value_type> __l, 602 size_type __n, 603 const allocator_type& __a) 604 : unordered_multiset(__l, __n, hasher(), key_equal(), __a) 605 { } 606 607 unordered_multiset(initializer_list<value_type> __l, 608 size_type __n, const hasher& __hf, 609 const allocator_type& __a) 610 : unordered_multiset(__l, __n, __hf, key_equal(), __a) 611 { } 612 613 ~unordered_multiset() = default; 614 615 unordered_multiset& 616 operator=(const unordered_multiset&) = default; 617 618 unordered_multiset& 619 operator=(unordered_multiset&&) = default; 620 621 unordered_multiset& 622 operator=(initializer_list<value_type> __l) 623 { 624 this->_M_base() = __l; 625 this->_M_invalidate_all(); 626 return *this; 627 } 628 629 void 630 swap(unordered_multiset& __x) 631 noexcept( noexcept(declval<_Base>().swap(__x)) ) 632 { 633 _Safe::_M_swap(__x); 634 _Base::swap(__x); 635 } 636 637 void 638 clear() noexcept 639 { 640 _Base::clear(); 641 this->_M_invalidate_all(); 642 } 643 644 iterator 645 begin() noexcept 646 { return iterator(_Base::begin(), this); } 647 648 const_iterator 649 begin() const noexcept 650 { return const_iterator(_Base::begin(), this); } 651 652 iterator 653 end() noexcept 654 { return iterator(_Base::end(), this); } 655 656 const_iterator 657 end() const noexcept 658 { return const_iterator(_Base::end(), this); } 659 660 const_iterator 661 cbegin() const noexcept 662 { return const_iterator(_Base::begin(), this); } 663 664 const_iterator 665 cend() const noexcept 666 { return const_iterator(_Base::end(), this); } 667 668 // local versions 669 local_iterator 670 begin(size_type __b) 671 { 672 __glibcxx_check_bucket_index(__b); 673 return local_iterator(_Base::begin(__b), this); 674 } 675 676 local_iterator 677 end(size_type __b) 678 { 679 __glibcxx_check_bucket_index(__b); 680 return local_iterator(_Base::end(__b), this); 681 } 682 683 const_local_iterator 684 begin(size_type __b) const 685 { 686 __glibcxx_check_bucket_index(__b); 687 return const_local_iterator(_Base::begin(__b), this); 688 } 689 690 const_local_iterator 691 end(size_type __b) const 692 { 693 __glibcxx_check_bucket_index(__b); 694 return const_local_iterator(_Base::end(__b), this); 695 } 696 697 const_local_iterator 698 cbegin(size_type __b) const 699 { 700 __glibcxx_check_bucket_index(__b); 701 return const_local_iterator(_Base::cbegin(__b), this); 702 } 703 704 const_local_iterator 705 cend(size_type __b) const 706 { 707 __glibcxx_check_bucket_index(__b); 708 return const_local_iterator(_Base::cend(__b), this); 709 } 710 711 size_type 712 bucket_size(size_type __b) const 713 { 714 __glibcxx_check_bucket_index(__b); 715 return _Base::bucket_size(__b); 716 } 717 718 float 719 max_load_factor() const noexcept 720 { return _Base::max_load_factor(); } 721 722 void 723 max_load_factor(float __f) 724 { 725 __glibcxx_check_max_load_factor(__f); 726 _Base::max_load_factor(__f); 727 } 728 729 template<typename... _Args> 730 iterator 731 emplace(_Args&&... __args) 732 { 733 size_type __bucket_count = this->bucket_count(); 734 _Base_iterator __it 735 = _Base::emplace(std::forward<_Args>(__args)...); 736 _M_check_rehashed(__bucket_count); 737 return iterator(__it, this); 738 } 739 740 template<typename... _Args> 741 iterator 742 emplace_hint(const_iterator __hint, _Args&&... __args) 743 { 744 __glibcxx_check_insert(__hint); 745 size_type __bucket_count = this->bucket_count(); 746 _Base_iterator __it = _Base::emplace_hint(__hint.base(), 747 std::forward<_Args>(__args)...); 748 _M_check_rehashed(__bucket_count); 749 return iterator(__it, this); 750 } 751 752 iterator 753 insert(const value_type& __obj) 754 { 755 size_type __bucket_count = this->bucket_count(); 756 _Base_iterator __it = _Base::insert(__obj); 757 _M_check_rehashed(__bucket_count); 758 return iterator(__it, this); 759 } 760 761 iterator 762 insert(const_iterator __hint, const value_type& __obj) 763 { 764 __glibcxx_check_insert(__hint); 765 size_type __bucket_count = this->bucket_count(); 766 _Base_iterator __it = _Base::insert(__hint.base(), __obj); 767 _M_check_rehashed(__bucket_count); 768 return iterator(__it, this); 769 } 770 771 iterator 772 insert(value_type&& __obj) 773 { 774 size_type __bucket_count = this->bucket_count(); 775 _Base_iterator __it = _Base::insert(std::move(__obj)); 776 _M_check_rehashed(__bucket_count); 777 return iterator(__it, this); 778 } 779 780 iterator 781 insert(const_iterator __hint, value_type&& __obj) 782 { 783 __glibcxx_check_insert(__hint); 784 size_type __bucket_count = this->bucket_count(); 785 _Base_iterator __it = _Base::insert(__hint.base(), std::move(__obj)); 786 _M_check_rehashed(__bucket_count); 787 return iterator(__it, this); 788 } 789 790 void 791 insert(std::initializer_list<value_type> __l) 792 { 793 size_type __bucket_count = this->bucket_count(); 794 _Base::insert(__l); 795 _M_check_rehashed(__bucket_count); 796 } 797 798 template<typename _InputIterator> 799 void 800 insert(_InputIterator __first, _InputIterator __last) 801 { 802 __glibcxx_check_valid_range(__first, __last); 803 size_type __bucket_count = this->bucket_count(); 804 _Base::insert(__gnu_debug::__base(__first), 805 __gnu_debug::__base(__last)); 806 _M_check_rehashed(__bucket_count); 807 } 808 809 iterator 810 find(const key_type& __key) 811 { return iterator(_Base::find(__key), this); } 812 813 const_iterator 814 find(const key_type& __key) const 815 { return const_iterator(_Base::find(__key), this); } 816 817 std::pair<iterator, iterator> 818 equal_range(const key_type& __key) 819 { 820 std::pair<_Base_iterator, _Base_iterator> __res 821 = _Base::equal_range(__key); 822 return std::make_pair(iterator(__res.first, this), 823 iterator(__res.second, this)); 824 } 825 826 std::pair<const_iterator, const_iterator> 827 equal_range(const key_type& __key) const 828 { 829 std::pair<_Base_const_iterator, _Base_const_iterator> 830 __res = _Base::equal_range(__key); 831 return std::make_pair(const_iterator(__res.first, this), 832 const_iterator(__res.second, this)); 833 } 834 835 size_type 836 erase(const key_type& __key) 837 { 838 size_type __ret(0); 839 std::pair<_Base_iterator, _Base_iterator> __pair = 840 _Base::equal_range(__key); 841 for (_Base_iterator __victim = __pair.first; __victim != __pair.second;) 842 { 843 this->_M_invalidate_if([__victim](_Base_const_iterator __it) 844 { return __it == __victim; }); 845 this->_M_invalidate_local_if( 846 [__victim](_Base_const_local_iterator __it) 847 { return __it._M_curr() == __victim._M_cur; }); 848 _Base::erase(__victim++); 849 ++__ret; 850 } 851 return __ret; 852 } 853 854 iterator 855 erase(const_iterator __it) 856 { 857 __glibcxx_check_erase(__it); 858 _Base_const_iterator __victim = __it.base(); 859 this->_M_invalidate_if([__victim](_Base_const_iterator __it) 860 { return __it == __victim; }); 861 this->_M_invalidate_local_if( 862 [__victim](_Base_const_local_iterator __it) 863 { return __it._M_curr() == __victim._M_cur; }); 864 return iterator(_Base::erase(__it.base()), this); 865 } 866 867 iterator 868 erase(iterator __it) 869 { return erase(const_iterator(__it)); } 870 871 iterator 872 erase(const_iterator __first, const_iterator __last) 873 { 874 __glibcxx_check_erase_range(__first, __last); 875 for (_Base_const_iterator __tmp = __first.base(); 876 __tmp != __last.base(); ++__tmp) 877 { 878 _GLIBCXX_DEBUG_VERIFY(__tmp != _Base::end(), 879 _M_message(__gnu_debug::__msg_valid_range) 880 ._M_iterator(__first, "first") 881 ._M_iterator(__last, "last")); 882 this->_M_invalidate_if([__tmp](_Base_const_iterator __it) 883 { return __it == __tmp; }); 884 this->_M_invalidate_local_if( 885 [__tmp](_Base_const_local_iterator __it) 886 { return __it._M_curr() == __tmp._M_cur; }); 887 } 888 return iterator(_Base::erase(__first.base(), 889 __last.base()), this); 890 } 891 892 _Base& 893 _M_base() noexcept { return *this; } 894 895 const _Base& 896 _M_base() const noexcept { return *this; } 897 898 private: 899 void 900 _M_check_rehashed(size_type __prev_count) 901 { 902 if (__prev_count != this->bucket_count()) 903 this->_M_invalidate_locals(); 904 } 905 }; 906 907 template<typename _Value, typename _Hash, typename _Pred, typename _Alloc> 908 inline void 909 swap(unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x, 910 unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y) 911 { __x.swap(__y); } 912 913 template<typename _Value, typename _Hash, typename _Pred, typename _Alloc> 914 inline bool 915 operator==(const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x, 916 const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y) 917 { return __x._M_base() == __y._M_base(); } 918 919 template<typename _Value, typename _Hash, typename _Pred, typename _Alloc> 920 inline bool 921 operator!=(const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x, 922 const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y) 923 { return !(__x == __y); } 924 925} // namespace __debug 926} // namespace std 927 928#endif // C++11 929 930#endif 931