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