Where Online Learning is simpler!
The C and C++ Include Header Files
cat -n /usr/include/c++/15/debug/multiset.h
1 // Debugging multiset implementation -*- C++ -*- 2 3 // Copyright (C) 2003-2025 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/multiset.h 26 * This file is a GNU debug extension to the Standard C++ Library. 27 */ 28 29 #ifndef _GLIBCXX_DEBUG_MULTISET_H 30 #define _GLIBCXX_DEBUG_MULTISET_H 1 31 32 #include <debug/safe_sequence.h> 33 #include <debug/safe_container.h> 34 #include <debug/safe_iterator.h> 35 #include <bits/stl_pair.h> 36 37 namespace std _GLIBCXX_VISIBILITY(default) 38 { 39 namespace __debug 40 { 41 /// Class std::multiset with safety/checking/debug instrumentation. 42 template<typename _Key, typename _Compare = std::less<_Key>, 43 typename _Allocator = std::allocator<_Key> > 44 class multiset 45 : public __gnu_debug::_Safe_container< 46 multiset<_Key, _Compare, _Allocator>, _Allocator, 47 __gnu_debug::_Safe_node_sequence>, 48 public _GLIBCXX_STD_C::multiset<_Key, _Compare, _Allocator> 49 { 50 typedef _GLIBCXX_STD_C::multiset<_Key, _Compare, _Allocator> _Base; 51 typedef __gnu_debug::_Safe_container< 52 multiset, _Allocator, __gnu_debug::_Safe_node_sequence> _Safe; 53 54 typedef typename _Base::const_iterator _Base_const_iterator; 55 typedef typename _Base::iterator _Base_iterator; 56 typedef __gnu_debug::_Equal_to<_Base_const_iterator> _Equal; 57 58 template<typename _ItT, typename _SeqT, typename _CatT> 59 friend class ::__gnu_debug::_Safe_iterator; 60 61 // Reference wrapper for base class. Disambiguates multiset(const _Base&) 62 // from copy constructor by requiring a user-defined conversion. 63 // See PR libstdc++/90102. 64 struct _Base_ref 65 { 66 _Base_ref(const _Base& __r) : _M_ref(__r) { } 67 68 const _Base& _M_ref; 69 }; 70 71 public: 72 // types: 73 typedef _Key key_type; 74 typedef _Key value_type; 75 typedef _Compare key_compare; 76 typedef _Compare value_compare; 77 typedef _Allocator allocator_type; 78 typedef typename _Base::reference reference; 79 typedef typename _Base::const_reference const_reference; 80 81 typedef __gnu_debug::_Safe_iterator<_Base_iterator, multiset> 82 iterator; 83 typedef __gnu_debug::_Safe_iterator<_Base_const_iterator, 84 multiset> const_iterator; 85 86 typedef typename _Base::size_type size_type; 87 typedef typename _Base::difference_type difference_type; 88 typedef typename _Base::pointer pointer; 89 typedef typename _Base::const_pointer const_pointer; 90 typedef std::reverse_iterator<iterator> reverse_iterator; 91 typedef std::reverse_iterator<const_iterator> const_reverse_iterator; 92 93 // 23.3.3.1 construct/copy/destroy: 94 95 #if __cplusplus < 201103L 96 multiset() : _Base() { } 97 98 multiset(const multiset& __x) 99 : _Base(__x) { } 100 101 ~multiset() { } 102 #else 103 multiset() = default; 104 multiset(const multiset&) = default; 105 multiset(multiset&&) = default; 106 107 multiset(initializer_list<value_type> __l, 108 const _Compare& __comp = _Compare(), 109 const allocator_type& __a = allocator_type()) 110 : _Base(__l, __comp, __a) { } 111 112 explicit 113 multiset(const allocator_type& __a) 114 : _Base(__a) { } 115 116 multiset(const multiset& __m, 117 const __type_identity_t<allocator_type>& __a) 118 : _Base(__m, __a) { } 119 120 multiset(multiset&& __m, const __type_identity_t<allocator_type>& __a) 121 noexcept( noexcept(_Base(std::move(__m), __a)) ) 122 : _Safe(std::move(__m), __a), 123 _Base(std::move(__m), __a) { } 124 125 multiset(initializer_list<value_type> __l, const allocator_type& __a) 126 : _Base(__l, __a) 127 { } 128 129 template<typename _InputIterator> 130 multiset(_InputIterator __first, _InputIterator __last, 131 const allocator_type& __a) 132 : _Base(__gnu_debug::__base( 133 __glibcxx_check_valid_constructor_range(__first, __last)), 134 __gnu_debug::__base(__last), __a) { } 135 136 #if __glibcxx_containers_ranges // C++ >= 23 137 /** 138 * @brief Construct a multiset from a range. 139 * @since C++23 140 */ 141 template<std::__detail::__container_compatible_range<value_type> _Rg> 142 multiset(std::from_range_t __t, _Rg&& __rg, 143 const _Compare& __c, 144 const allocator_type& __a = allocator_type()) 145 : _Base(__t, std::forward<_Rg>(__rg), __c, __a) 146 { } 147 148 template<std::__detail::__container_compatible_range<value_type> _Rg> 149 multiset(std::from_range_t __t, _Rg&& __rg, 150 const allocator_type& __a = allocator_type()) 151 : _Base(__t, std::forward<_Rg>(__rg), __a) 152 { } 153 #endif 154 155 ~multiset() = default; 156 #endif 157 158 explicit multiset(const _Compare& __comp, 159 const _Allocator& __a = _Allocator()) 160 : _Base(__comp, __a) { } 161 162 template<typename _InputIterator> 163 multiset(_InputIterator __first, _InputIterator __last, 164 const _Compare& __comp = _Compare(), 165 const _Allocator& __a = _Allocator()) 166 : _Base(__gnu_debug::__base( 167 __glibcxx_check_valid_constructor_range(__first, __last)), 168 __gnu_debug::__base(__last), 169 __comp, __a) { } 170 171 multiset(_Base_ref __x) 172 : _Base(__x._M_ref) { } 173 174 #if __cplusplus >= 201103L 175 multiset& 176 operator=(const multiset&) = default; 177 178 multiset& 179 operator=(multiset&&) = default; 180 181 multiset& 182 operator=(initializer_list<value_type> __l) 183 { 184 _Base::operator=(__l); 185 this->_M_invalidate_all(); 186 return *this; 187 } 188 #endif 189 190 using _Base::get_allocator; 191 192 // iterators: 193 iterator 194 begin() _GLIBCXX_NOEXCEPT 195 { return iterator(_Base::begin(), this); } 196 197 const_iterator 198 begin() const _GLIBCXX_NOEXCEPT 199 { return const_iterator(_Base::begin(), this); } 200 201 iterator 202 end() _GLIBCXX_NOEXCEPT 203 { return iterator(_Base::end(), this); } 204 205 const_iterator 206 end() const _GLIBCXX_NOEXCEPT 207 { return const_iterator(_Base::end(), this); } 208 209 reverse_iterator 210 rbegin() _GLIBCXX_NOEXCEPT 211 { return reverse_iterator(end()); } 212 213 const_reverse_iterator 214 rbegin() const _GLIBCXX_NOEXCEPT 215 { return const_reverse_iterator(end()); } 216 217 reverse_iterator 218 rend() _GLIBCXX_NOEXCEPT 219 { return reverse_iterator(begin()); } 220 221 const_reverse_iterator 222 rend() const _GLIBCXX_NOEXCEPT 223 { return const_reverse_iterator(begin()); } 224 225 #if __cplusplus >= 201103L 226 const_iterator 227 cbegin() const noexcept 228 { return const_iterator(_Base::begin(), this); } 229 230 const_iterator 231 cend() const noexcept 232 { return const_iterator(_Base::end(), this); } 233 234 const_reverse_iterator 235 crbegin() const noexcept 236 { return const_reverse_iterator(end()); } 237 238 const_reverse_iterator 239 crend() const noexcept 240 { return const_reverse_iterator(begin()); } 241 #endif 242 243 // capacity: 244 using _Base::empty; 245 using _Base::size; 246 using _Base::max_size; 247 248 // modifiers: 249 #if __cplusplus >= 201103L 250 template<typename... _Args> 251 iterator 252 emplace(_Args&&... __args) 253 { return { _Base::emplace(std::forward<_Args>(__args)...), this }; } 254 255 template<typename... _Args> 256 iterator 257 emplace_hint(const_iterator __pos, _Args&&... __args) 258 { 259 __glibcxx_check_insert(__pos); 260 return 261 { 262 _Base::emplace_hint(__pos.base(), std::forward<_Args>(__args)...), 263 this 264 }; 265 } 266 #endif 267 268 iterator 269 insert(const value_type& __x) 270 { return iterator(_Base::insert(__x), this); } 271 272 #if __cplusplus >= 201103L 273 iterator 274 insert(value_type&& __x) 275 { return { _Base::insert(std::move(__x)), this }; } 276 #endif 277 278 iterator 279 insert(const_iterator __position, const value_type& __x) 280 { 281 __glibcxx_check_insert(__position); 282 return iterator(_Base::insert(__position.base(), __x), this); 283 } 284 285 #if __cplusplus >= 201103L 286 iterator 287 insert(const_iterator __position, value_type&& __x) 288 { 289 __glibcxx_check_insert(__position); 290 return { _Base::insert(__position.base(), std::move(__x)), this }; 291 } 292 #endif 293 294 template<typename _InputIterator> 295 void 296 insert(_InputIterator __first, _InputIterator __last) 297 { 298 typename __gnu_debug::_Distance_traits<_InputIterator>::__type __dist; 299 __glibcxx_check_valid_range2(__first, __last, __dist); 300 301 if (__dist.second >= __gnu_debug::__dp_sign) 302 _Base::insert(__gnu_debug::__unsafe(__first), 303 __gnu_debug::__unsafe(__last)); 304 else 305 _Base::insert(__first, __last); 306 } 307 308 #if __cplusplus >= 201103L 309 void 310 insert(initializer_list<value_type> __l) 311 { _Base::insert(__l); } 312 #endif 313 314 #if __cplusplus > 201402L 315 using node_type = typename _Base::node_type; 316 317 node_type 318 extract(const_iterator __position) 319 { 320 __glibcxx_check_erase(__position); 321 this->_M_invalidate_if(_Equal(__position.base())); 322 return _Base::extract(__position.base()); 323 } 324 325 node_type 326 extract(const key_type& __key) 327 { 328 const auto __position = find(__key); 329 if (__position != end()) 330 return extract(__position); 331 return {}; 332 } 333 334 iterator 335 insert(node_type&& __nh) 336 { return { _Base::insert(std::move(__nh)), this }; } 337 338 iterator 339 insert(const_iterator __hint, node_type&& __nh) 340 { 341 __glibcxx_check_insert(__hint); 342 return { _Base::insert(__hint.base(), std::move(__nh)), this }; 343 } 344 345 using _Base::merge; 346 #endif // C++17 347 348 #if __cplusplus >= 201103L 349 _GLIBCXX_ABI_TAG_CXX11 350 iterator 351 erase(const_iterator __position) 352 { 353 __glibcxx_check_erase(__position); 354 return { erase(__position.base()), this }; 355 } 356 357 _Base_iterator 358 erase(_Base_const_iterator __position) 359 { 360 __glibcxx_check_erase2(__position); 361 this->_M_invalidate_if(_Equal(__position)); 362 return _Base::erase(__position); 363 } 364 #else 365 void 366 erase(iterator __position) 367 { 368 __glibcxx_check_erase(__position); 369 this->_M_invalidate_if(_Equal(__position.base())); 370 _Base::erase(__position.base()); 371 } 372 #endif 373 374 size_type 375 erase(const key_type& __x) 376 { 377 std::pair<_Base_iterator, _Base_iterator> __victims = 378 _Base::equal_range(__x); 379 size_type __count = 0; 380 _Base_iterator __victim = __victims.first; 381 while (__victim != __victims.second) 382 { 383 this->_M_invalidate_if(_Equal(__victim)); 384 _Base::erase(__victim++); 385 ++__count; 386 } 387 return __count; 388 } 389 390 #if __cplusplus >= 201103L 391 _GLIBCXX_ABI_TAG_CXX11 392 iterator 393 erase(const_iterator __first, const_iterator __last) 394 { 395 // _GLIBCXX_RESOLVE_LIB_DEFECTS 396 // 151. can't currently clear() empty container 397 __glibcxx_check_erase_range(__first, __last); 398 for (_Base_const_iterator __victim = __first.base(); 399 __victim != __last.base(); ++__victim) 400 { 401 _GLIBCXX_DEBUG_VERIFY(__victim != _Base::cend(), 402 _M_message(__gnu_debug::__msg_valid_range) 403 ._M_iterator(__first, "first") 404 ._M_iterator(__last, "last")); 405 this->_M_invalidate_if(_Equal(__victim)); 406 } 407 408 return { _Base::erase(__first.base(), __last.base()), this }; 409 } 410 #else 411 void 412 erase(iterator __first, iterator __last) 413 { 414 // _GLIBCXX_RESOLVE_LIB_DEFECTS 415 // 151. can't currently clear() empty container 416 __glibcxx_check_erase_range(__first, __last); 417 for (_Base_iterator __victim = __first.base(); 418 __victim != __last.base(); ++__victim) 419 { 420 _GLIBCXX_DEBUG_VERIFY(__victim != _Base::end(), 421 _M_message(__gnu_debug::__msg_valid_range) 422 ._M_iterator(__first, "first") 423 ._M_iterator(__last, "last")); 424 this->_M_invalidate_if(_Equal(__victim)); 425 } 426 _Base::erase(__first.base(), __last.base()); 427 } 428 #endif 429 430 void 431 swap(multiset& __x) 432 _GLIBCXX_NOEXCEPT_IF( noexcept(declval<_Base&>().swap(__x)) ) 433 { 434 _Safe::_M_swap(__x); 435 _Base::swap(__x); 436 } 437 438 void 439 clear() _GLIBCXX_NOEXCEPT 440 { 441 this->_M_invalidate_all(); 442 _Base::clear(); 443 } 444 445 // observers: 446 using _Base::key_comp; 447 using _Base::value_comp; 448 449 // multiset operations: 450 iterator 451 find(const key_type& __x) 452 { return iterator(_Base::find(__x), this); } 453 454 // _GLIBCXX_RESOLVE_LIB_DEFECTS 455 // 214. set::find() missing const overload 456 const_iterator 457 find(const key_type& __x) const 458 { return const_iterator(_Base::find(__x), this); } 459 460 #if __cplusplus > 201103L 461 template<typename _Kt, 462 typename _Req = 463 typename __has_is_transparent<_Compare, _Kt>::type> 464 iterator 465 find(const _Kt& __x) 466 { return { _Base::find(__x), this }; } 467 468 template<typename _Kt, 469 typename _Req = 470 typename __has_is_transparent<_Compare, _Kt>::type> 471 const_iterator 472 find(const _Kt& __x) const 473 { return { _Base::find(__x), this }; } 474 #endif 475 476 using _Base::count; 477 478 iterator 479 lower_bound(const key_type& __x) 480 { return iterator(_Base::lower_bound(__x), this); } 481 482 // _GLIBCXX_RESOLVE_LIB_DEFECTS 483 // 214. set::find() missing const overload 484 const_iterator 485 lower_bound(const key_type& __x) const 486 { return const_iterator(_Base::lower_bound(__x), this); } 487 488 #if __cplusplus > 201103L 489 template<typename _Kt, 490 typename _Req = 491 typename __has_is_transparent<_Compare, _Kt>::type> 492 iterator 493 lower_bound(const _Kt& __x) 494 { return { _Base::lower_bound(__x), this }; } 495 496 template<typename _Kt, 497 typename _Req = 498 typename __has_is_transparent<_Compare, _Kt>::type> 499 const_iterator 500 lower_bound(const _Kt& __x) const 501 { return { _Base::lower_bound(__x), this }; } 502 #endif 503 504 iterator 505 upper_bound(const key_type& __x) 506 { return iterator(_Base::upper_bound(__x), this); } 507 508 // _GLIBCXX_RESOLVE_LIB_DEFECTS 509 // 214. set::find() missing const overload 510 const_iterator 511 upper_bound(const key_type& __x) const 512 { return const_iterator(_Base::upper_bound(__x), this); } 513 514 #if __cplusplus > 201103L 515 template<typename _Kt, 516 typename _Req = 517 typename __has_is_transparent<_Compare, _Kt>::type> 518 iterator 519 upper_bound(const _Kt& __x) 520 { return { _Base::upper_bound(__x), this }; } 521 522 template<typename _Kt, 523 typename _Req = 524 typename __has_is_transparent<_Compare, _Kt>::type> 525 const_iterator 526 upper_bound(const _Kt& __x) const 527 { return { _Base::upper_bound(__x), this }; } 528 #endif 529 530 std::pair<iterator,iterator> 531 equal_range(const key_type& __x) 532 { 533 std::pair<_Base_iterator, _Base_iterator> __res = 534 _Base::equal_range(__x); 535 return std::make_pair(iterator(__res.first, this), 536 iterator(__res.second, this)); 537 } 538 539 // _GLIBCXX_RESOLVE_LIB_DEFECTS 540 // 214. set::find() missing const overload 541 std::pair<const_iterator,const_iterator> 542 equal_range(const key_type& __x) const 543 { 544 std::pair<_Base_const_iterator, _Base_const_iterator> __res = 545 _Base::equal_range(__x); 546 return std::make_pair(const_iterator(__res.first, this), 547 const_iterator(__res.second, this)); 548 } 549 550 #if __cplusplus > 201103L 551 template<typename _Kt, 552 typename _Req = 553 typename __has_is_transparent<_Compare, _Kt>::type> 554 std::pair<iterator, iterator> 555 equal_range(const _Kt& __x) 556 { 557 auto __res = _Base::equal_range(__x); 558 return { { __res.first, this }, { __res.second, this } }; 559 } 560 561 template<typename _Kt, 562 typename _Req = 563 typename __has_is_transparent<_Compare, _Kt>::type> 564 std::pair<const_iterator, const_iterator> 565 equal_range(const _Kt& __x) const 566 { 567 auto __res = _Base::equal_range(__x); 568 return { { __res.first, this }, { __res.second, this } }; 569 } 570 #endif 571 572 _Base& 573 _M_base() _GLIBCXX_NOEXCEPT { return *this; } 574 575 const _Base& 576 _M_base() const _GLIBCXX_NOEXCEPT { return *this; } 577 }; 578 579 #if __cpp_deduction_guides >= 201606 580 581 template<typename _InputIterator, 582 typename _Compare = 583 less<typename iterator_traits<_InputIterator>::value_type>, 584 typename _Allocator = 585 allocator<typename iterator_traits<_InputIterator>::value_type>, 586 typename = _RequireInputIter<_InputIterator>, 587 typename = _RequireNotAllocator<_Compare>, 588 typename = _RequireAllocator<_Allocator>> 589 multiset(_InputIterator, _InputIterator, 590 _Compare = _Compare(), _Allocator = _Allocator()) 591 -> multiset<typename iterator_traits<_InputIterator>::value_type, 592 _Compare, _Allocator>; 593 594 template<typename _Key, 595 typename _Compare = less<_Key>, 596 typename _Allocator = allocator<_Key>, 597 typename = _RequireNotAllocator<_Compare>, 598 typename = _RequireAllocator<_Allocator>> 599 multiset(initializer_list<_Key>, 600 _Compare = _Compare(), _Allocator = _Allocator()) 601 -> multiset<_Key, _Compare, _Allocator>; 602 603 template<typename _InputIterator, typename _Allocator, 604 typename = _RequireInputIter<_InputIterator>, 605 typename = _RequireAllocator<_Allocator>> 606 multiset(_InputIterator, _InputIterator, _Allocator) 607 -> multiset<typename iterator_traits<_InputIterator>::value_type, 608 less<typename iterator_traits<_InputIterator>::value_type>, 609 _Allocator>; 610 611 template<typename _Key, typename _Allocator, 612 typename = _RequireAllocator<_Allocator>> 613 multiset(initializer_list<_Key>, _Allocator) 614 -> multiset<_Key, less<_Key>, _Allocator>; 615 616 #if __glibcxx_containers_ranges // C++ >= 23 617 template<ranges::input_range _Rg, 618 __not_allocator_like _Compare = less<ranges::range_value_t<_Rg>>, 619 __allocator_like _Alloc = std::allocator<ranges::range_value_t<_Rg>>> 620 multiset(from_range_t, _Rg&&, _Compare = _Compare(), _Alloc = _Alloc()) 621 -> multiset<ranges::range_value_t<_Rg>, _Compare, _Alloc>; 622 623 template<ranges::input_range _Rg, __allocator_like _Alloc> 624 multiset(from_range_t, _Rg&&, _Alloc) 625 -> multiset<ranges::range_value_t<_Rg>, less<ranges::range_value_t<_Rg>>, _Alloc>; 626 #endif 627 #endif // deduction guides 628 629 template<typename _Key, typename _Compare, typename _Allocator> 630 inline bool 631 operator==(const multiset<_Key, _Compare, _Allocator>& __lhs, 632 const multiset<_Key, _Compare, _Allocator>& __rhs) 633 { return __lhs._M_base() == __rhs._M_base(); } 634 635 #if __cpp_lib_three_way_comparison 636 template<typename _Key, typename _Compare, typename _Alloc> 637 inline __detail::__synth3way_t<_Key> 638 operator<=>(const multiset<_Key, _Compare, _Alloc>& __lhs, 639 const multiset<_Key, _Compare, _Alloc>& __rhs) 640 { return __lhs._M_base() <=> __rhs._M_base(); } 641 #else 642 template<typename _Key, typename _Compare, typename _Allocator> 643 inline bool 644 operator!=(const multiset<_Key, _Compare, _Allocator>& __lhs, 645 const multiset<_Key, _Compare, _Allocator>& __rhs) 646 { return __lhs._M_base() != __rhs._M_base(); } 647 648 template<typename _Key, typename _Compare, typename _Allocator> 649 inline bool 650 operator<(const multiset<_Key, _Compare, _Allocator>& __lhs, 651 const multiset<_Key, _Compare, _Allocator>& __rhs) 652 { return __lhs._M_base() < __rhs._M_base(); } 653 654 template<typename _Key, typename _Compare, typename _Allocator> 655 inline bool 656 operator<=(const multiset<_Key, _Compare, _Allocator>& __lhs, 657 const multiset<_Key, _Compare, _Allocator>& __rhs) 658 { return __lhs._M_base() <= __rhs._M_base(); } 659 660 template<typename _Key, typename _Compare, typename _Allocator> 661 inline bool 662 operator>=(const multiset<_Key, _Compare, _Allocator>& __lhs, 663 const multiset<_Key, _Compare, _Allocator>& __rhs) 664 { return __lhs._M_base() >= __rhs._M_base(); } 665 666 template<typename _Key, typename _Compare, typename _Allocator> 667 inline bool 668 operator>(const multiset<_Key, _Compare, _Allocator>& __lhs, 669 const multiset<_Key, _Compare, _Allocator>& __rhs) 670 { return __lhs._M_base() > __rhs._M_base(); } 671 #endif // three-way comparison 672 673 template<typename _Key, typename _Compare, typename _Allocator> 674 void 675 swap(multiset<_Key, _Compare, _Allocator>& __x, 676 multiset<_Key, _Compare, _Allocator>& __y) 677 _GLIBCXX_NOEXCEPT_IF(noexcept(__x.swap(__y))) 678 { return __x.swap(__y); } 679 680 } // namespace __debug 681 } // namespace std 682 683 #endif
