1// Debugging unordered_set/unordered_multiset implementation -*- C++ -*- 2 3// Copyright (C) 2003-2018 Free Software Foundation, Inc. 4// 5// This file is part of the GNU ISO C++ Library. This library is free 6// software; you can redistribute it and/or modify it under the 7// terms of the GNU General Public License as published by the 8// Free Software Foundation; either version 3, or (at your option) 9// any later version. 10 11// This library is distributed in the hope that it will be useful, 12// but WITHOUT ANY WARRANTY; without even the implied warranty of 13// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 14// GNU General Public License for more details. 15 16// Under Section 7 of GPL version 3, you are granted additional 17// permissions described in the GCC Runtime Library Exception, version 18// 3.1, as published by the Free Software Foundation. 19 20// You should have received a copy of the GNU General Public License and 21// a copy of the GCC Runtime Library Exception along with this program; 22// see the files COPYING3 and COPYING.RUNTIME respectively. If not, see 23// <http://www.gnu.org/licenses/>. 24 25/** @file debug/unordered_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 using insert_return_type = _Node_insert_return<iterator, node_type>; 376 377 node_type 378 extract(const_iterator __position) 379 { 380 __glibcxx_check_erase(__position); 381 _Base_const_iterator __victim = __position.base(); 382 this->_M_invalidate_if( 383 [__victim](_Base_const_iterator __it) { return __it == __victim; } 384 ); 385 this->_M_invalidate_local_if( 386 [__victim](_Base_const_local_iterator __it) { 387 return __it._M_curr() == __victim._M_cur; 388 }); 389 return _Base::extract(__position.base()); 390 } 391 392 node_type 393 extract(const key_type& __key) 394 { 395 const auto __position = find(__key); 396 if (__position != end()) 397 return extract(__position); 398 return {}; 399 } 400 401 insert_return_type 402 insert(node_type&& __nh) 403 { 404 auto __ret = _Base::insert(std::move(__nh)); 405 iterator __pos = iterator(__ret.position, this); 406 return { __pos, __ret.inserted, std::move(__ret.node) }; 407 } 408 409 iterator 410 insert(const_iterator __hint, node_type&& __nh) 411 { 412 __glibcxx_check_insert(__hint); 413 return iterator(_Base::insert(__hint.base(), std::move(__nh)), this); 414 } 415 416 using _Base::merge; 417#endif // C++17 418 419 iterator 420 find(const key_type& __key) 421 { return iterator(_Base::find(__key), this); } 422 423 const_iterator 424 find(const key_type& __key) const 425 { return const_iterator(_Base::find(__key), this); } 426 427 std::pair<iterator, iterator> 428 equal_range(const key_type& __key) 429 { 430 std::pair<_Base_iterator, _Base_iterator> __res 431 = _Base::equal_range(__key); 432 return std::make_pair(iterator(__res.first, this), 433 iterator(__res.second, this)); 434 } 435 436 std::pair<const_iterator, const_iterator> 437 equal_range(const key_type& __key) const 438 { 439 std::pair<_Base_const_iterator, _Base_const_iterator> 440 __res = _Base::equal_range(__key); 441 return std::make_pair(const_iterator(__res.first, this), 442 const_iterator(__res.second, this)); 443 } 444 445 size_type 446 erase(const key_type& __key) 447 { 448 size_type __ret(0); 449 _Base_iterator __victim(_Base::find(__key)); 450 if (__victim != _Base::end()) 451 { 452 this->_M_invalidate_if( 453 [__victim](_Base_const_iterator __it) 454 { return __it == __victim; }); 455 this->_M_invalidate_local_if( 456 [__victim](_Base_const_local_iterator __it) 457 { return __it._M_curr() == __victim._M_cur; }); 458 size_type __bucket_count = this->bucket_count(); 459 _Base::erase(__victim); 460 _M_check_rehashed(__bucket_count); 461 __ret = 1; 462 } 463 return __ret; 464 } 465 466 iterator 467 erase(const_iterator __it) 468 { 469 __glibcxx_check_erase(__it); 470 _Base_const_iterator __victim = __it.base(); 471 this->_M_invalidate_if( 472 [__victim](_Base_const_iterator __it) 473 { return __it == __victim; }); 474 this->_M_invalidate_local_if( 475 [__victim](_Base_const_local_iterator __it) 476 { return __it._M_curr() == __victim._M_cur; }); 477 size_type __bucket_count = this->bucket_count(); 478 _Base_iterator __next = _Base::erase(__it.base()); 479 _M_check_rehashed(__bucket_count); 480 return iterator(__next, this); 481 } 482 483 iterator 484 erase(iterator __it) 485 { return erase(const_iterator(__it)); } 486 487 iterator 488 erase(const_iterator __first, const_iterator __last) 489 { 490 __glibcxx_check_erase_range(__first, __last); 491 for (_Base_const_iterator __tmp = __first.base(); 492 __tmp != __last.base(); ++__tmp) 493 { 494 _GLIBCXX_DEBUG_VERIFY(__tmp != _Base::end(), 495 _M_message(__gnu_debug::__msg_valid_range) 496 ._M_iterator(__first, "first") 497 ._M_iterator(__last, "last")); 498 this->_M_invalidate_if( 499 [__tmp](_Base_const_iterator __it) 500 { return __it == __tmp; }); 501 this->_M_invalidate_local_if( 502 [__tmp](_Base_const_local_iterator __it) 503 { return __it._M_curr() == __tmp._M_cur; }); 504 } 505 size_type __bucket_count = this->bucket_count(); 506 _Base_iterator __next = _Base::erase(__first.base(), 507 __last.base()); 508 _M_check_rehashed(__bucket_count); 509 return iterator(__next, this); 510 } 511 512 _Base& 513 _M_base() noexcept { return *this; } 514 515 const _Base& 516 _M_base() const noexcept { return *this; } 517 518 private: 519 void 520 _M_check_rehashed(size_type __prev_count) 521 { 522 if (__prev_count != this->bucket_count()) 523 this->_M_invalidate_locals(); 524 } 525 }; 526 527#if __cpp_deduction_guides >= 201606 528 529 template<typename _InputIterator, 530 typename _Hash = 531 hash<typename iterator_traits<_InputIterator>::value_type>, 532 typename _Pred = 533 equal_to<typename iterator_traits<_InputIterator>::value_type>, 534 typename _Allocator = 535 allocator<typename iterator_traits<_InputIterator>::value_type>, 536 typename = _RequireInputIter<_InputIterator>, 537 typename = _RequireAllocator<_Allocator>> 538 unordered_set(_InputIterator, _InputIterator, 539 unordered_set<int>::size_type = {}, 540 _Hash = _Hash(), _Pred = _Pred(), _Allocator = _Allocator()) 541 -> unordered_set<typename iterator_traits<_InputIterator>::value_type, 542 _Hash, _Pred, _Allocator>; 543 544 template<typename _Tp, typename _Hash = hash<_Tp>, 545 typename _Pred = equal_to<_Tp>, 546 typename _Allocator = allocator<_Tp>, 547 typename = _RequireAllocator<_Allocator>> 548 unordered_set(initializer_list<_Tp>, 549 unordered_set<int>::size_type = {}, 550 _Hash = _Hash(), _Pred = _Pred(), _Allocator = _Allocator()) 551 -> unordered_set<_Tp, _Hash, _Pred, _Allocator>; 552 553 template<typename _InputIterator, typename _Allocator, 554 typename = _RequireInputIter<_InputIterator>, 555 typename = _RequireAllocator<_Allocator>> 556 unordered_set(_InputIterator, _InputIterator, 557 unordered_set<int>::size_type, _Allocator) 558 -> unordered_set<typename iterator_traits<_InputIterator>::value_type, 559 hash< 560 typename iterator_traits<_InputIterator>::value_type>, 561 equal_to< 562 typename iterator_traits<_InputIterator>::value_type>, 563 _Allocator>; 564 565 template<typename _InputIterator, typename _Hash, typename _Allocator, 566 typename = _RequireInputIter<_InputIterator>, 567 typename = _RequireAllocator<_Allocator>> 568 unordered_set(_InputIterator, _InputIterator, 569 unordered_set<int>::size_type, 570 _Hash, _Allocator) 571 -> unordered_set<typename iterator_traits<_InputIterator>::value_type, 572 _Hash, 573 equal_to< 574 typename iterator_traits<_InputIterator>::value_type>, 575 _Allocator>; 576 577 template<typename _Tp, typename _Allocator, 578 typename = _RequireAllocator<_Allocator>> 579 unordered_set(initializer_list<_Tp>, 580 unordered_set<int>::size_type, _Allocator) 581 -> unordered_set<_Tp, hash<_Tp>, equal_to<_Tp>, _Allocator>; 582 583 template<typename _Tp, typename _Hash, typename _Allocator, 584 typename = _RequireAllocator<_Allocator>> 585 unordered_set(initializer_list<_Tp>, 586 unordered_set<int>::size_type, _Hash, _Allocator) 587 -> unordered_set<_Tp, _Hash, equal_to<_Tp>, _Allocator>; 588 589#endif 590 591 template<typename _Value, typename _Hash, typename _Pred, typename _Alloc> 592 inline void 593 swap(unordered_set<_Value, _Hash, _Pred, _Alloc>& __x, 594 unordered_set<_Value, _Hash, _Pred, _Alloc>& __y) 595 noexcept(noexcept(__x.swap(__y))) 596 { __x.swap(__y); } 597 598 template<typename _Value, typename _Hash, typename _Pred, typename _Alloc> 599 inline bool 600 operator==(const unordered_set<_Value, _Hash, _Pred, _Alloc>& __x, 601 const unordered_set<_Value, _Hash, _Pred, _Alloc>& __y) 602 { return __x._M_base() == __y._M_base(); } 603 604 template<typename _Value, typename _Hash, typename _Pred, typename _Alloc> 605 inline bool 606 operator!=(const unordered_set<_Value, _Hash, _Pred, _Alloc>& __x, 607 const unordered_set<_Value, _Hash, _Pred, _Alloc>& __y) 608 { return !(__x == __y); } 609 610 611 /// Class std::unordered_multiset with safety/checking/debug instrumentation. 612 template<typename _Value, 613 typename _Hash = std::hash<_Value>, 614 typename _Pred = std::equal_to<_Value>, 615 typename _Alloc = std::allocator<_Value> > 616 class unordered_multiset 617 : public __gnu_debug::_Safe_container< 618 unordered_multiset<_Value, _Hash, _Pred, _Alloc>, _Alloc, 619 __gnu_debug::_Safe_unordered_container>, 620 public _GLIBCXX_STD_C::unordered_multiset<_Value, _Hash, _Pred, _Alloc> 621 { 622 typedef _GLIBCXX_STD_C::unordered_multiset< 623 _Value, _Hash, _Pred, _Alloc> _Base; 624 typedef __gnu_debug::_Safe_container<unordered_multiset, 625 _Alloc, __gnu_debug::_Safe_unordered_container> _Safe; 626 typedef typename _Base::const_iterator _Base_const_iterator; 627 typedef typename _Base::iterator _Base_iterator; 628 typedef typename _Base::const_local_iterator 629 _Base_const_local_iterator; 630 typedef typename _Base::local_iterator _Base_local_iterator; 631 632 public: 633 typedef typename _Base::size_type size_type; 634 typedef typename _Base::hasher hasher; 635 typedef typename _Base::key_equal key_equal; 636 typedef typename _Base::allocator_type allocator_type; 637 638 typedef typename _Base::key_type key_type; 639 typedef typename _Base::value_type value_type; 640 641 typedef __gnu_debug::_Safe_iterator< 642 _Base_iterator, unordered_multiset> iterator; 643 typedef __gnu_debug::_Safe_iterator< 644 _Base_const_iterator, unordered_multiset> const_iterator; 645 typedef __gnu_debug::_Safe_local_iterator< 646 _Base_local_iterator, unordered_multiset> local_iterator; 647 typedef __gnu_debug::_Safe_local_iterator< 648 _Base_const_local_iterator, unordered_multiset> const_local_iterator; 649 650 unordered_multiset() = default; 651 652 explicit 653 unordered_multiset(size_type __n, 654 const hasher& __hf = hasher(), 655 const key_equal& __eql = key_equal(), 656 const allocator_type& __a = allocator_type()) 657 : _Base(__n, __hf, __eql, __a) { } 658 659 template<typename _InputIterator> 660 unordered_multiset(_InputIterator __first, _InputIterator __last, 661 size_type __n = 0, 662 const hasher& __hf = hasher(), 663 const key_equal& __eql = key_equal(), 664 const allocator_type& __a = allocator_type()) 665 : _Base(__gnu_debug::__base(__gnu_debug::__check_valid_range(__first, 666 __last)), 667 __gnu_debug::__base(__last), __n, 668 __hf, __eql, __a) { } 669 670 unordered_multiset(const unordered_multiset&) = default; 671 672 unordered_multiset(const _Base& __x) 673 : _Base(__x) { } 674 675 unordered_multiset(unordered_multiset&&) = default; 676 677 explicit 678 unordered_multiset(const allocator_type& __a) 679 : _Base(__a) { } 680 681 unordered_multiset(const unordered_multiset& __uset, 682 const allocator_type& __a) 683 : _Base(__uset, __a) { } 684 685 unordered_multiset(unordered_multiset&& __uset, 686 const allocator_type& __a) 687 : _Safe(std::move(__uset._M_safe()), __a), 688 _Base(std::move(__uset._M_base()), __a) { } 689 690 unordered_multiset(initializer_list<value_type> __l, 691 size_type __n = 0, 692 const hasher& __hf = hasher(), 693 const key_equal& __eql = key_equal(), 694 const allocator_type& __a = allocator_type()) 695 : _Base(__l, __n, __hf, __eql, __a) { } 696 697 unordered_multiset(size_type __n, const allocator_type& __a) 698 : unordered_multiset(__n, hasher(), key_equal(), __a) 699 { } 700 701 unordered_multiset(size_type __n, const hasher& __hf, 702 const allocator_type& __a) 703 : unordered_multiset(__n, __hf, key_equal(), __a) 704 { } 705 706 template<typename _InputIterator> 707 unordered_multiset(_InputIterator __first, _InputIterator __last, 708 size_type __n, 709 const allocator_type& __a) 710 : unordered_multiset(__first, __last, __n, hasher(), key_equal(), __a) 711 { } 712 713 template<typename _InputIterator> 714 unordered_multiset(_InputIterator __first, _InputIterator __last, 715 size_type __n, const hasher& __hf, 716 const allocator_type& __a) 717 : unordered_multiset(__first, __last, __n, __hf, key_equal(), __a) 718 { } 719 720 unordered_multiset(initializer_list<value_type> __l, 721 size_type __n, 722 const allocator_type& __a) 723 : unordered_multiset(__l, __n, hasher(), key_equal(), __a) 724 { } 725 726 unordered_multiset(initializer_list<value_type> __l, 727 size_type __n, const hasher& __hf, 728 const allocator_type& __a) 729 : unordered_multiset(__l, __n, __hf, key_equal(), __a) 730 { } 731 732 ~unordered_multiset() = default; 733 734 unordered_multiset& 735 operator=(const unordered_multiset&) = default; 736 737 unordered_multiset& 738 operator=(unordered_multiset&&) = default; 739 740 unordered_multiset& 741 operator=(initializer_list<value_type> __l) 742 { 743 this->_M_base() = __l; 744 this->_M_invalidate_all(); 745 return *this; 746 } 747 748 void 749 swap(unordered_multiset& __x) 750 noexcept( noexcept(declval<_Base&>().swap(__x)) ) 751 { 752 _Safe::_M_swap(__x); 753 _Base::swap(__x); 754 } 755 756 void 757 clear() noexcept 758 { 759 _Base::clear(); 760 this->_M_invalidate_all(); 761 } 762 763 iterator 764 begin() noexcept 765 { return iterator(_Base::begin(), this); } 766 767 const_iterator 768 begin() const noexcept 769 { return const_iterator(_Base::begin(), this); } 770 771 iterator 772 end() noexcept 773 { return iterator(_Base::end(), this); } 774 775 const_iterator 776 end() const noexcept 777 { return const_iterator(_Base::end(), this); } 778 779 const_iterator 780 cbegin() const noexcept 781 { return const_iterator(_Base::begin(), this); } 782 783 const_iterator 784 cend() const noexcept 785 { return const_iterator(_Base::end(), this); } 786 787 // local versions 788 local_iterator 789 begin(size_type __b) 790 { 791 __glibcxx_check_bucket_index(__b); 792 return local_iterator(_Base::begin(__b), this); 793 } 794 795 local_iterator 796 end(size_type __b) 797 { 798 __glibcxx_check_bucket_index(__b); 799 return local_iterator(_Base::end(__b), this); 800 } 801 802 const_local_iterator 803 begin(size_type __b) const 804 { 805 __glibcxx_check_bucket_index(__b); 806 return const_local_iterator(_Base::begin(__b), this); 807 } 808 809 const_local_iterator 810 end(size_type __b) const 811 { 812 __glibcxx_check_bucket_index(__b); 813 return const_local_iterator(_Base::end(__b), this); 814 } 815 816 const_local_iterator 817 cbegin(size_type __b) const 818 { 819 __glibcxx_check_bucket_index(__b); 820 return const_local_iterator(_Base::cbegin(__b), this); 821 } 822 823 const_local_iterator 824 cend(size_type __b) const 825 { 826 __glibcxx_check_bucket_index(__b); 827 return const_local_iterator(_Base::cend(__b), this); 828 } 829 830 size_type 831 bucket_size(size_type __b) const 832 { 833 __glibcxx_check_bucket_index(__b); 834 return _Base::bucket_size(__b); 835 } 836 837 float 838 max_load_factor() const noexcept 839 { return _Base::max_load_factor(); } 840 841 void 842 max_load_factor(float __f) 843 { 844 __glibcxx_check_max_load_factor(__f); 845 _Base::max_load_factor(__f); 846 } 847 848 template<typename... _Args> 849 iterator 850 emplace(_Args&&... __args) 851 { 852 size_type __bucket_count = this->bucket_count(); 853 _Base_iterator __it 854 = _Base::emplace(std::forward<_Args>(__args)...); 855 _M_check_rehashed(__bucket_count); 856 return iterator(__it, this); 857 } 858 859 template<typename... _Args> 860 iterator 861 emplace_hint(const_iterator __hint, _Args&&... __args) 862 { 863 __glibcxx_check_insert(__hint); 864 size_type __bucket_count = this->bucket_count(); 865 _Base_iterator __it = _Base::emplace_hint(__hint.base(), 866 std::forward<_Args>(__args)...); 867 _M_check_rehashed(__bucket_count); 868 return iterator(__it, this); 869 } 870 871 iterator 872 insert(const value_type& __obj) 873 { 874 size_type __bucket_count = this->bucket_count(); 875 _Base_iterator __it = _Base::insert(__obj); 876 _M_check_rehashed(__bucket_count); 877 return iterator(__it, this); 878 } 879 880 iterator 881 insert(const_iterator __hint, const value_type& __obj) 882 { 883 __glibcxx_check_insert(__hint); 884 size_type __bucket_count = this->bucket_count(); 885 _Base_iterator __it = _Base::insert(__hint.base(), __obj); 886 _M_check_rehashed(__bucket_count); 887 return iterator(__it, this); 888 } 889 890 iterator 891 insert(value_type&& __obj) 892 { 893 size_type __bucket_count = this->bucket_count(); 894 _Base_iterator __it = _Base::insert(std::move(__obj)); 895 _M_check_rehashed(__bucket_count); 896 return iterator(__it, this); 897 } 898 899 iterator 900 insert(const_iterator __hint, value_type&& __obj) 901 { 902 __glibcxx_check_insert(__hint); 903 size_type __bucket_count = this->bucket_count(); 904 _Base_iterator __it = _Base::insert(__hint.base(), std::move(__obj)); 905 _M_check_rehashed(__bucket_count); 906 return iterator(__it, this); 907 } 908 909 void 910 insert(std::initializer_list<value_type> __l) 911 { 912 size_type __bucket_count = this->bucket_count(); 913 _Base::insert(__l); 914 _M_check_rehashed(__bucket_count); 915 } 916 917 template<typename _InputIterator> 918 void 919 insert(_InputIterator __first, _InputIterator __last) 920 { 921 typename __gnu_debug::_Distance_traits<_InputIterator>::__type __dist; 922 __glibcxx_check_valid_range2(__first, __last, __dist); 923 size_type __bucket_count = this->bucket_count(); 924 925 if (__dist.second >= __gnu_debug::__dp_sign) 926 _Base::insert(__gnu_debug::__unsafe(__first), 927 __gnu_debug::__unsafe(__last)); 928 else 929 _Base::insert(__first, __last); 930 931 _M_check_rehashed(__bucket_count); 932 } 933 934#if __cplusplus > 201402L 935 using node_type = typename _Base::node_type; 936 937 node_type 938 extract(const_iterator __position) 939 { 940 __glibcxx_check_erase(__position); 941 _Base_const_iterator __victim = __position.base(); 942 this->_M_invalidate_if( 943 [__victim](_Base_const_iterator __it) { return __it == __victim; } 944 ); 945 this->_M_invalidate_local_if( 946 [__victim](_Base_const_local_iterator __it) { 947 return __it._M_curr() == __victim._M_cur; 948 }); 949 return _Base::extract(__position.base()); 950 } 951 952 node_type 953 extract(const key_type& __key) 954 { 955 const auto __position = find(__key); 956 if (__position != end()) 957 return extract(__position); 958 return {}; 959 } 960 961 iterator 962 insert(node_type&& __nh) 963 { return iterator(_Base::insert(std::move(__nh)), this); } 964 965 iterator 966 insert(const_iterator __hint, node_type&& __nh) 967 { 968 __glibcxx_check_insert(__hint); 969 return iterator(_Base::insert(__hint.base(), std::move(__nh)), this); 970 } 971 972 using _Base::merge; 973#endif // C++17 974 975 iterator 976 find(const key_type& __key) 977 { return iterator(_Base::find(__key), this); } 978 979 const_iterator 980 find(const key_type& __key) const 981 { return const_iterator(_Base::find(__key), this); } 982 983 std::pair<iterator, iterator> 984 equal_range(const key_type& __key) 985 { 986 std::pair<_Base_iterator, _Base_iterator> __res 987 = _Base::equal_range(__key); 988 return std::make_pair(iterator(__res.first, this), 989 iterator(__res.second, this)); 990 } 991 992 std::pair<const_iterator, const_iterator> 993 equal_range(const key_type& __key) const 994 { 995 std::pair<_Base_const_iterator, _Base_const_iterator> 996 __res = _Base::equal_range(__key); 997 return std::make_pair(const_iterator(__res.first, this), 998 const_iterator(__res.second, this)); 999 } 1000 1001 size_type 1002 erase(const key_type& __key) 1003 { 1004 size_type __ret(0); 1005 std::pair<_Base_iterator, _Base_iterator> __pair = 1006 _Base::equal_range(__key); 1007 for (_Base_iterator __victim = __pair.first; __victim != __pair.second;) 1008 { 1009 this->_M_invalidate_if([__victim](_Base_const_iterator __it) 1010 { return __it == __victim; }); 1011 this->_M_invalidate_local_if( 1012 [__victim](_Base_const_local_iterator __it) 1013 { return __it._M_curr() == __victim._M_cur; }); 1014 _Base::erase(__victim++); 1015 ++__ret; 1016 } 1017 return __ret; 1018 } 1019 1020 iterator 1021 erase(const_iterator __it) 1022 { 1023 __glibcxx_check_erase(__it); 1024 _Base_const_iterator __victim = __it.base(); 1025 this->_M_invalidate_if([__victim](_Base_const_iterator __it) 1026 { return __it == __victim; }); 1027 this->_M_invalidate_local_if( 1028 [__victim](_Base_const_local_iterator __it) 1029 { return __it._M_curr() == __victim._M_cur; }); 1030 return iterator(_Base::erase(__it.base()), this); 1031 } 1032 1033 iterator 1034 erase(iterator __it) 1035 { return erase(const_iterator(__it)); } 1036 1037 iterator 1038 erase(const_iterator __first, const_iterator __last) 1039 { 1040 __glibcxx_check_erase_range(__first, __last); 1041 for (_Base_const_iterator __tmp = __first.base(); 1042 __tmp != __last.base(); ++__tmp) 1043 { 1044 _GLIBCXX_DEBUG_VERIFY(__tmp != _Base::end(), 1045 _M_message(__gnu_debug::__msg_valid_range) 1046 ._M_iterator(__first, "first") 1047 ._M_iterator(__last, "last")); 1048 this->_M_invalidate_if([__tmp](_Base_const_iterator __it) 1049 { return __it == __tmp; }); 1050 this->_M_invalidate_local_if( 1051 [__tmp](_Base_const_local_iterator __it) 1052 { return __it._M_curr() == __tmp._M_cur; }); 1053 } 1054 return iterator(_Base::erase(__first.base(), 1055 __last.base()), this); 1056 } 1057 1058 _Base& 1059 _M_base() noexcept { return *this; } 1060 1061 const _Base& 1062 _M_base() const noexcept { return *this; } 1063 1064 private: 1065 void 1066 _M_check_rehashed(size_type __prev_count) 1067 { 1068 if (__prev_count != this->bucket_count()) 1069 this->_M_invalidate_locals(); 1070 } 1071 }; 1072 1073#if __cpp_deduction_guides >= 201606 1074 1075 template<typename _InputIterator, 1076 typename _Hash = 1077 hash<typename iterator_traits<_InputIterator>::value_type>, 1078 typename _Pred = 1079 equal_to<typename iterator_traits<_InputIterator>::value_type>, 1080 typename _Allocator = 1081 allocator<typename iterator_traits<_InputIterator>::value_type>, 1082 typename = _RequireInputIter<_InputIterator>, 1083 typename = _RequireAllocator<_Allocator>> 1084 unordered_multiset(_InputIterator, _InputIterator, 1085 unordered_multiset<int>::size_type = {}, 1086 _Hash = _Hash(), _Pred = _Pred(), 1087 _Allocator = _Allocator()) 1088 -> unordered_multiset<typename iterator_traits<_InputIterator>::value_type, 1089 _Hash, _Pred, _Allocator>; 1090 1091 template<typename _Tp, typename _Hash = hash<_Tp>, 1092 typename _Pred = equal_to<_Tp>, 1093 typename _Allocator = allocator<_Tp>, 1094 typename = _RequireAllocator<_Allocator>> 1095 unordered_multiset(initializer_list<_Tp>, 1096 unordered_multiset<int>::size_type = {}, 1097 _Hash = _Hash(), _Pred = _Pred(), 1098 _Allocator = _Allocator()) 1099 -> unordered_multiset<_Tp, _Hash, _Pred, _Allocator>; 1100 1101 template<typename _InputIterator, typename _Allocator, 1102 typename = _RequireInputIter<_InputIterator>, 1103 typename = _RequireAllocator<_Allocator>> 1104 unordered_multiset(_InputIterator, _InputIterator, 1105 unordered_multiset<int>::size_type, _Allocator) 1106 -> unordered_multiset<typename iterator_traits<_InputIterator>::value_type, 1107 hash<typename 1108 iterator_traits<_InputIterator>::value_type>, 1109 equal_to<typename 1110 iterator_traits<_InputIterator>::value_type>, 1111 _Allocator>; 1112 1113 template<typename _InputIterator, typename _Hash, typename _Allocator, 1114 typename = _RequireInputIter<_InputIterator>, 1115 typename = _RequireAllocator<_Allocator>> 1116 unordered_multiset(_InputIterator, _InputIterator, 1117 unordered_multiset<int>::size_type, 1118 _Hash, _Allocator) 1119 -> unordered_multiset<typename 1120 iterator_traits<_InputIterator>::value_type, 1121 _Hash, 1122 equal_to< 1123 typename 1124 iterator_traits<_InputIterator>::value_type>, 1125 _Allocator>; 1126 1127 template<typename _Tp, typename _Allocator, 1128 typename = _RequireAllocator<_Allocator>> 1129 unordered_multiset(initializer_list<_Tp>, 1130 unordered_multiset<int>::size_type, _Allocator) 1131 -> unordered_multiset<_Tp, hash<_Tp>, equal_to<_Tp>, _Allocator>; 1132 1133 template<typename _Tp, typename _Hash, typename _Allocator, 1134 typename = _RequireAllocator<_Allocator>> 1135 unordered_multiset(initializer_list<_Tp>, 1136 unordered_multiset<int>::size_type, _Hash, _Allocator) 1137 -> unordered_multiset<_Tp, _Hash, equal_to<_Tp>, _Allocator>; 1138 1139#endif 1140 1141 template<typename _Value, typename _Hash, typename _Pred, typename _Alloc> 1142 inline void 1143 swap(unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x, 1144 unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y) 1145 noexcept(noexcept(__x.swap(__y))) 1146 { __x.swap(__y); } 1147 1148 template<typename _Value, typename _Hash, typename _Pred, typename _Alloc> 1149 inline bool 1150 operator==(const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x, 1151 const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y) 1152 { return __x._M_base() == __y._M_base(); } 1153 1154 template<typename _Value, typename _Hash, typename _Pred, typename _Alloc> 1155 inline bool 1156 operator!=(const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x, 1157 const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y) 1158 { return !(__x == __y); } 1159 1160} // namespace __debug 1161} // namespace std 1162 1163#endif // C++11 1164 1165#endif 1166