Where Online Learning is simpler!
The C and C++ Include Header Files
cat -n /usr/include/c++/15/debug/list
1 // Debugging list 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/list 26 * This file is a GNU debug extension to the Standard C++ Library. 27 */ 28 29 #ifndef _GLIBCXX_DEBUG_LIST 30 #define _GLIBCXX_DEBUG_LIST 1 31 32 #ifdef _GLIBCXX_SYSHDR 33 #pragma GCC system_header 34 #endif 35 36 #include <bits/c++config.h> 37 namespace std _GLIBCXX_VISIBILITY(default) { namespace __debug { 38 template<typename _Tp, typename _Allocator> class list; 39 } } // namespace std::__debug 40 41 #include <list> 42 #include <debug/safe_sequence.h> 43 #include <debug/safe_container.h> 44 #include <debug/safe_iterator.h> 45 46 namespace std _GLIBCXX_VISIBILITY(default) 47 { 48 namespace __debug 49 { 50 /// Class std::list with safety/checking/debug instrumentation. 51 template<typename _Tp, typename _Allocator = std::allocator<_Tp> > 52 class list 53 : public __gnu_debug::_Safe_container< 54 list<_Tp, _Allocator>, _Allocator, 55 __gnu_debug::_Safe_node_sequence>, 56 public _GLIBCXX_STD_C::list<_Tp, _Allocator> 57 { 58 typedef _GLIBCXX_STD_C::list<_Tp, _Allocator> _Base; 59 typedef __gnu_debug::_Safe_container< 60 list, _Allocator, __gnu_debug::_Safe_node_sequence> _Safe; 61 62 typedef typename _Base::iterator _Base_iterator; 63 typedef typename _Base::const_iterator _Base_const_iterator; 64 typedef __gnu_debug::_Equal_to<_Base_const_iterator> _Equal; 65 typedef __gnu_debug::_Not_equal_to<_Base_const_iterator> _Not_equal; 66 67 template<typename _ItT, typename _SeqT, typename _CatT> 68 friend class ::__gnu_debug::_Safe_iterator; 69 70 // Reference wrapper for base class. Disambiguates list(const _Base&) 71 // from copy constructor by requiring a user-defined conversion. 72 // See PR libstdc++/90102. 73 struct _Base_ref 74 { 75 _Base_ref(const _Base& __r) : _M_ref(__r) { } 76 77 const _Base& _M_ref; 78 }; 79 80 public: 81 typedef typename _Base::reference reference; 82 typedef typename _Base::const_reference const_reference; 83 84 typedef __gnu_debug::_Safe_iterator<_Base_iterator, list> 85 iterator; 86 typedef __gnu_debug::_Safe_iterator<_Base_const_iterator, list> 87 const_iterator; 88 89 typedef typename _Base::size_type size_type; 90 typedef typename _Base::difference_type difference_type; 91 92 typedef _Tp value_type; 93 typedef _Allocator allocator_type; 94 typedef typename _Base::pointer pointer; 95 typedef typename _Base::const_pointer const_pointer; 96 typedef std::reverse_iterator<iterator> reverse_iterator; 97 typedef std::reverse_iterator<const_iterator> const_reverse_iterator; 98 99 // 23.2.2.1 construct/copy/destroy: 100 101 #if __cplusplus < 201103L 102 list() 103 : _Base() { } 104 105 list(const list& __x) 106 : _Base(__x) { } 107 108 ~list() { } 109 #else 110 list() = default; 111 list(const list&) = default; 112 list(list&&) = default; 113 114 list(initializer_list<value_type> __l, 115 const allocator_type& __a = allocator_type()) 116 : _Base(__l, __a) { } 117 118 ~list() = default; 119 120 list(const list& __x, const __type_identity_t<allocator_type>& __a) 121 : _Base(__x, __a) { } 122 123 list(list&& __x, const __type_identity_t<allocator_type>& __a) 124 noexcept( 125 std::is_nothrow_constructible<_Base, 126 _Base, const allocator_type&>::value ) 127 : _Safe(std::move(__x), __a), 128 _Base(std::move(__x), __a) { } 129 #endif 130 131 explicit 132 list(const _Allocator& __a) _GLIBCXX_NOEXCEPT 133 : _Base(__a) { } 134 135 #if __cplusplus >= 201103L 136 explicit 137 list(size_type __n, const allocator_type& __a = allocator_type()) 138 : _Base(__n, __a) { } 139 140 list(size_type __n, const __type_identity_t<_Tp>& __value, 141 const _Allocator& __a = _Allocator()) 142 : _Base(__n, __value, __a) { } 143 #else 144 explicit 145 list(size_type __n, const _Tp& __value = _Tp(), 146 const _Allocator& __a = _Allocator()) 147 : _Base(__n, __value, __a) { } 148 #endif 149 150 #if __cplusplus >= 201103L 151 template<class _InputIterator, 152 typename = std::_RequireInputIter<_InputIterator>> 153 #else 154 template<class _InputIterator> 155 #endif 156 list(_InputIterator __first, _InputIterator __last, 157 const _Allocator& __a = _Allocator()) 158 : _Base(__gnu_debug::__base( 159 __glibcxx_check_valid_constructor_range(__first, __last)), 160 __gnu_debug::__base(__last), __a) 161 { } 162 163 #if __glibcxx_containers_ranges // C++ >= 23 164 template<__detail::__container_compatible_range<_Tp> _Rg> 165 list(from_range_t, _Rg&& __rg, const _Allocator& __a = _Allocator()) 166 : _Base(std::from_range, std::forward<_Rg>(__rg), __a) 167 { } 168 #endif 169 170 list(_Base_ref __x) 171 : _Base(__x._M_ref) { } 172 173 #if __cplusplus >= 201103L 174 list& 175 operator=(const list&) = default; 176 177 list& 178 operator=(list&&) = default; 179 180 list& 181 operator=(initializer_list<value_type> __l) 182 { 183 this->_M_invalidate_all(); 184 _Base::operator=(__l); 185 return *this; 186 } 187 188 void 189 assign(initializer_list<value_type> __l) 190 { 191 _Base::assign(__l); 192 this->_M_invalidate_all(); 193 } 194 #endif 195 196 #if __cplusplus >= 201103L 197 template<class _InputIterator, 198 typename = std::_RequireInputIter<_InputIterator>> 199 #else 200 template<class _InputIterator> 201 #endif 202 void 203 assign(_InputIterator __first, _InputIterator __last) 204 { 205 typename __gnu_debug::_Distance_traits<_InputIterator>::__type __dist; 206 __glibcxx_check_valid_range2(__first, __last, __dist); 207 208 if (__dist.second >= __gnu_debug::__dp_sign) 209 _Base::assign(__gnu_debug::__unsafe(__first), 210 __gnu_debug::__unsafe(__last)); 211 else 212 _Base::assign(__first, __last); 213 214 this->_M_invalidate_all(); 215 } 216 217 #if __glibcxx_containers_ranges // C++ >= 23 218 template<__detail::__container_compatible_range<_Tp> _Rg> 219 void 220 assign_range(_Rg&& __rg) 221 { 222 // Have to reimplement this function, so that we use the debug 223 // version of erase, which invalidates the correct iterators. 224 225 static_assert(assignable_from<_Tp&, ranges::range_reference_t<_Rg>>); 226 227 auto __first1 = _Base::begin(); 228 const auto __last1 = _Base::end(); 229 auto __first2 = ranges::begin(__rg); 230 const auto __last2 = ranges::end(__rg); 231 for (; __first1 != __last1 && __first2 != __last2; 232 ++__first1, (void)++__first2) 233 *__first1 = *__first2; 234 if (__first2 == __last2) 235 erase(const_iterator(__first1, this), 236 const_iterator(__last1, this)); 237 else 238 _Base::insert_range(__last1, 239 ranges::subrange(std::move(__first2), __last2)); 240 } 241 #endif 242 243 void 244 assign(size_type __n, const _Tp& __t) 245 { 246 _Base::assign(__n, __t); 247 this->_M_invalidate_all(); 248 } 249 250 using _Base::get_allocator; 251 252 // iterators: 253 _GLIBCXX_NODISCARD 254 iterator 255 begin() _GLIBCXX_NOEXCEPT 256 { return iterator(_Base::begin(), this); } 257 258 _GLIBCXX_NODISCARD 259 const_iterator 260 begin() const _GLIBCXX_NOEXCEPT 261 { return const_iterator(_Base::begin(), this); } 262 263 _GLIBCXX_NODISCARD 264 iterator 265 end() _GLIBCXX_NOEXCEPT 266 { return iterator(_Base::end(), this); } 267 268 _GLIBCXX_NODISCARD 269 const_iterator 270 end() const _GLIBCXX_NOEXCEPT 271 { return const_iterator(_Base::end(), this); } 272 273 _GLIBCXX_NODISCARD 274 reverse_iterator 275 rbegin() _GLIBCXX_NOEXCEPT 276 { return reverse_iterator(end()); } 277 278 _GLIBCXX_NODISCARD 279 const_reverse_iterator 280 rbegin() const _GLIBCXX_NOEXCEPT 281 { return const_reverse_iterator(end()); } 282 283 _GLIBCXX_NODISCARD 284 reverse_iterator 285 rend() _GLIBCXX_NOEXCEPT 286 { return reverse_iterator(begin()); } 287 288 _GLIBCXX_NODISCARD 289 const_reverse_iterator 290 rend() const _GLIBCXX_NOEXCEPT 291 { return const_reverse_iterator(begin()); } 292 293 #if __cplusplus >= 201103L 294 [[__nodiscard__]] 295 const_iterator 296 cbegin() const noexcept 297 { return const_iterator(_Base::begin(), this); } 298 299 [[__nodiscard__]] 300 const_iterator 301 cend() const noexcept 302 { return const_iterator(_Base::end(), this); } 303 304 [[__nodiscard__]] 305 const_reverse_iterator 306 crbegin() const noexcept 307 { return const_reverse_iterator(end()); } 308 309 [[__nodiscard__]] 310 const_reverse_iterator 311 crend() const noexcept 312 { return const_reverse_iterator(begin()); } 313 #endif 314 315 // 23.2.2.2 capacity: 316 using _Base::empty; 317 using _Base::size; 318 using _Base::max_size; 319 320 #if __cplusplus >= 201103L 321 void 322 resize(size_type __sz) 323 { 324 this->_M_detach_singular(); 325 326 // if __sz < size(), invalidate all iterators in [begin + __sz, end()) 327 _Base_iterator __victim = _Base::begin(); 328 _Base_iterator __end = _Base::end(); 329 for (size_type __i = __sz; __victim != __end && __i > 0; --__i) 330 ++__victim; 331 332 for (; __victim != __end; ++__victim) 333 this->_M_invalidate_if(_Equal(__victim)); 334 335 __try 336 { 337 _Base::resize(__sz); 338 } 339 __catch(...) 340 { 341 this->_M_revalidate_singular(); 342 __throw_exception_again; 343 } 344 } 345 346 void 347 resize(size_type __sz, const _Tp& __c) 348 { 349 this->_M_detach_singular(); 350 351 // if __sz < size(), invalidate all iterators in [begin + __sz, end()) 352 _Base_iterator __victim = _Base::begin(); 353 _Base_iterator __end = _Base::end(); 354 for (size_type __i = __sz; __victim != __end && __i > 0; --__i) 355 ++__victim; 356 357 for (; __victim != __end; ++__victim) 358 this->_M_invalidate_if(_Equal(__victim)); 359 360 __try 361 { 362 _Base::resize(__sz, __c); 363 } 364 __catch(...) 365 { 366 this->_M_revalidate_singular(); 367 __throw_exception_again; 368 } 369 } 370 #else 371 void 372 resize(size_type __sz, _Tp __c = _Tp()) 373 { 374 this->_M_detach_singular(); 375 376 // if __sz < size(), invalidate all iterators in [begin + __sz, end()) 377 _Base_iterator __victim = _Base::begin(); 378 _Base_iterator __end = _Base::end(); 379 for (size_type __i = __sz; __victim != __end && __i > 0; --__i) 380 ++__victim; 381 382 for (; __victim != __end; ++__victim) 383 this->_M_invalidate_if(_Equal(__victim)); 384 385 __try 386 { 387 _Base::resize(__sz, __c); 388 } 389 __catch(...) 390 { 391 this->_M_revalidate_singular(); 392 __throw_exception_again; 393 } 394 } 395 #endif 396 397 // element access: 398 _GLIBCXX_NODISCARD 399 reference 400 front() _GLIBCXX_NOEXCEPT 401 { 402 __glibcxx_check_nonempty(); 403 return _Base::front(); 404 } 405 406 _GLIBCXX_NODISCARD 407 const_reference 408 front() const _GLIBCXX_NOEXCEPT 409 { 410 __glibcxx_check_nonempty(); 411 return _Base::front(); 412 } 413 414 _GLIBCXX_NODISCARD 415 reference 416 back() _GLIBCXX_NOEXCEPT 417 { 418 __glibcxx_check_nonempty(); 419 return _Base::back(); 420 } 421 422 _GLIBCXX_NODISCARD 423 const_reference 424 back() const _GLIBCXX_NOEXCEPT 425 { 426 __glibcxx_check_nonempty(); 427 return _Base::back(); 428 } 429 430 // 23.2.2.3 modifiers: 431 using _Base::push_front; 432 433 #if __cplusplus >= 201103L 434 using _Base::emplace_front; 435 #endif 436 437 #if __glibcxx_containers_ranges // C++ >= 23 438 using _Base::prepend_range; 439 using _Base::append_range; 440 #endif 441 442 void 443 pop_front() _GLIBCXX_NOEXCEPT 444 { 445 __glibcxx_check_nonempty(); 446 this->_M_invalidate_if(_Equal(_Base::begin())); 447 _Base::pop_front(); 448 } 449 450 using _Base::push_back; 451 452 #if __cplusplus >= 201103L 453 using _Base::emplace_back; 454 #endif 455 456 void 457 pop_back() _GLIBCXX_NOEXCEPT 458 { 459 __glibcxx_check_nonempty(); 460 this->_M_invalidate_if(_Equal(--_Base::end())); 461 _Base::pop_back(); 462 } 463 464 #if __cplusplus >= 201103L 465 template<typename... _Args> 466 iterator 467 emplace(const_iterator __position, _Args&&... __args) 468 { 469 __glibcxx_check_insert(__position); 470 return { _Base::emplace(__position.base(), 471 std::forward<_Args>(__args)...), this }; 472 } 473 #endif 474 475 iterator 476 #if __cplusplus >= 201103L 477 insert(const_iterator __position, const _Tp& __x) 478 #else 479 insert(iterator __position, const _Tp& __x) 480 #endif 481 { 482 __glibcxx_check_insert(__position); 483 return iterator(_Base::insert(__position.base(), __x), this); 484 } 485 486 #if __cplusplus >= 201103L 487 iterator 488 insert(const_iterator __position, _Tp&& __x) 489 { return emplace(__position, std::move(__x)); } 490 491 iterator 492 insert(const_iterator __p, initializer_list<value_type> __l) 493 { 494 __glibcxx_check_insert(__p); 495 return { _Base::insert(__p.base(), __l), this }; 496 } 497 #endif 498 499 #if __cplusplus >= 201103L 500 iterator 501 insert(const_iterator __position, size_type __n, const _Tp& __x) 502 { 503 __glibcxx_check_insert(__position); 504 return { _Base::insert(__position.base(), __n, __x), this }; 505 } 506 #else 507 void 508 insert(iterator __position, size_type __n, const _Tp& __x) 509 { 510 __glibcxx_check_insert(__position); 511 _Base::insert(__position.base(), __n, __x); 512 } 513 #endif 514 515 #if __cplusplus >= 201103L 516 template<class _InputIterator, 517 typename = std::_RequireInputIter<_InputIterator>> 518 iterator 519 insert(const_iterator __position, _InputIterator __first, 520 _InputIterator __last) 521 { 522 typename __gnu_debug::_Distance_traits<_InputIterator>::__type __dist; 523 __glibcxx_check_insert_range(__position, __first, __last, __dist); 524 if (__dist.second >= __gnu_debug::__dp_sign) 525 return 526 { 527 _Base::insert(__position.base(), 528 __gnu_debug::__unsafe(__first), 529 __gnu_debug::__unsafe(__last)), 530 this 531 }; 532 else 533 return { _Base::insert(__position.base(), __first, __last), this }; 534 } 535 #else 536 template<class _InputIterator> 537 void 538 insert(iterator __position, _InputIterator __first, 539 _InputIterator __last) 540 { 541 typename __gnu_debug::_Distance_traits<_InputIterator>::__type __dist; 542 __glibcxx_check_insert_range(__position, __first, __last, __dist); 543 544 if (__dist.second >= __gnu_debug::__dp_sign) 545 _Base::insert(__position.base(), __gnu_debug::__unsafe(__first), 546 __gnu_debug::__unsafe(__last)); 547 else 548 _Base::insert(__position.base(), __first, __last); 549 } 550 #endif 551 552 #if __glibcxx_containers_ranges // C++ >= 23 553 template<__detail::__container_compatible_range<_Tp> _Rg> 554 iterator 555 insert_range(const_iterator __position, _Rg&& __rg) 556 { 557 auto __ret = _Base::insert_range(__position.base(), 558 std::forward<_Rg>(__rg)); 559 return { __ret, this }; 560 } 561 #endif 562 563 private: 564 _Base_iterator 565 #if __cplusplus >= 201103L 566 _M_erase(_Base_const_iterator __position) noexcept 567 #else 568 _M_erase(_Base_iterator __position) 569 #endif 570 { 571 this->_M_invalidate_if(_Equal(__position)); 572 return _Base::erase(__position); 573 } 574 575 public: 576 iterator 577 #if __cplusplus >= 201103L 578 erase(const_iterator __position) noexcept 579 #else 580 erase(iterator __position) 581 #endif 582 { 583 __glibcxx_check_erase(__position); 584 return iterator(_M_erase(__position.base()), this); 585 } 586 587 iterator 588 #if __cplusplus >= 201103L 589 erase(const_iterator __first, const_iterator __last) noexcept 590 #else 591 erase(iterator __first, iterator __last) 592 #endif 593 { 594 // _GLIBCXX_RESOLVE_LIB_DEFECTS 595 // 151. can't currently clear() empty container 596 __glibcxx_check_erase_range(__first, __last); 597 for (_Base_const_iterator __victim = __first.base(); 598 __victim != __last.base(); ++__victim) 599 { 600 _GLIBCXX_DEBUG_VERIFY(__victim != _Base::end(), 601 _M_message(__gnu_debug::__msg_valid_range) 602 ._M_iterator(__first, "position") 603 ._M_iterator(__last, "last")); 604 this->_M_invalidate_if(_Equal(__victim)); 605 } 606 607 return iterator(_Base::erase(__first.base(), __last.base()), this); 608 } 609 610 void 611 swap(list& __x) 612 _GLIBCXX_NOEXCEPT_IF( noexcept(declval<_Base&>().swap(__x)) ) 613 { 614 _Safe::_M_swap(__x); 615 _Base::swap(__x); 616 } 617 618 void 619 clear() _GLIBCXX_NOEXCEPT 620 { 621 _Base::clear(); 622 this->_M_invalidate_all(); 623 } 624 625 // 23.2.2.4 list operations: 626 void 627 #if __cplusplus >= 201103L 628 splice(const_iterator __position, list&& __x) noexcept 629 #else 630 splice(iterator __position, list& __x) 631 #endif 632 { 633 _GLIBCXX_DEBUG_VERIFY(std::__addressof(__x) != this, 634 _M_message(__gnu_debug::__msg_self_splice) 635 ._M_sequence(*this, "this")); 636 this->_M_transfer_from_if(__x, _Not_equal(__x._M_base().end())); 637 _Base::splice(__position.base(), _GLIBCXX_MOVE(__x)); 638 } 639 640 #if __cplusplus >= 201103L 641 void 642 splice(const_iterator __position, list& __x) noexcept 643 { splice(__position, std::move(__x)); } 644 #endif 645 646 void 647 #if __cplusplus >= 201103L 648 splice(const_iterator __position, list&& __x, const_iterator __i) noexcept 649 #else 650 splice(iterator __position, list& __x, iterator __i) 651 #endif 652 { 653 __glibcxx_check_insert(__position); 654 655 // We used to perform the splice_alloc check: not anymore, redundant 656 // after implementing the relevant bits of N1599. 657 658 _GLIBCXX_DEBUG_VERIFY(__i._M_dereferenceable(), 659 _M_message(__gnu_debug::__msg_splice_bad) 660 ._M_iterator(__i, "__i")); 661 _GLIBCXX_DEBUG_VERIFY(__i._M_attached_to(std::__addressof(__x)), 662 _M_message(__gnu_debug::__msg_splice_other) 663 ._M_iterator(__i, "__i")._M_sequence(__x, "__x")); 664 665 // _GLIBCXX_RESOLVE_LIB_DEFECTS 666 // 250. splicing invalidates iterators 667 this->_M_transfer_from_if(__x, _Equal(__i.base())); 668 _Base::splice(__position.base(), _GLIBCXX_MOVE(__x), 669 __i.base()); 670 } 671 672 #if __cplusplus >= 201103L 673 void 674 splice(const_iterator __position, list& __x, const_iterator __i) noexcept 675 { splice(__position, std::move(__x), __i); } 676 #endif 677 678 void 679 #if __cplusplus >= 201103L 680 splice(const_iterator __position, list&& __x, const_iterator __first, 681 const_iterator __last) noexcept 682 #else 683 splice(iterator __position, list& __x, iterator __first, 684 iterator __last) 685 #endif 686 { 687 __glibcxx_check_insert(__position); 688 __glibcxx_check_valid_range(__first, __last); 689 _GLIBCXX_DEBUG_VERIFY(__first._M_attached_to(std::__addressof(__x)), 690 _M_message(__gnu_debug::__msg_splice_other) 691 ._M_sequence(__x, "x") 692 ._M_iterator(__first, "first")); 693 694 // We used to perform the splice_alloc check: not anymore, redundant 695 // after implementing the relevant bits of N1599. 696 697 for (_Base_const_iterator __tmp = __first.base(); 698 __tmp != __last.base(); ++__tmp) 699 { 700 _GLIBCXX_DEBUG_VERIFY(__tmp != _Base::end(), 701 _M_message(__gnu_debug::__msg_valid_range) 702 ._M_iterator(__first, "first") 703 ._M_iterator(__last, "last")); 704 _GLIBCXX_DEBUG_VERIFY(std::__addressof(__x) != this 705 || __tmp != __position.base(), 706 _M_message(__gnu_debug::__msg_splice_overlap) 707 ._M_iterator(__tmp, "position") 708 ._M_iterator(__first, "first") 709 ._M_iterator(__last, "last")); 710 711 // _GLIBCXX_RESOLVE_LIB_DEFECTS 712 // 250. splicing invalidates iterators 713 this->_M_transfer_from_if(__x, _Equal(__tmp)); 714 } 715 716 _Base::splice(__position.base(), _GLIBCXX_MOVE(__x), 717 __first.base(), __last.base()); 718 } 719 720 #if __cplusplus >= 201103L 721 void 722 splice(const_iterator __position, list& __x, 723 const_iterator __first, const_iterator __last) noexcept 724 { splice(__position, std::move(__x), __first, __last); } 725 #endif 726 727 private: 728 #if __cplusplus > 201703L 729 typedef size_type __remove_return_type; 730 # define _GLIBCXX_LIST_REMOVE_RETURN_TYPE_TAG \ 731 __attribute__((__abi_tag__("__cxx20"))) 732 # define _GLIBCXX20_ONLY(__expr) __expr 733 #else 734 typedef void __remove_return_type; 735 # define _GLIBCXX_LIST_REMOVE_RETURN_TYPE_TAG 736 # define _GLIBCXX20_ONLY(__expr) 737 #endif 738 739 public: 740 _GLIBCXX_LIST_REMOVE_RETURN_TYPE_TAG 741 __remove_return_type 742 remove(const _Tp& __value) 743 { 744 if (!this->_M_iterators && !this->_M_const_iterators) 745 return _Base::remove(__value); 746 747 #if !_GLIBCXX_USE_CXX11_ABI 748 size_type __removed __attribute__((__unused__)) = 0; 749 #endif 750 _Base __to_destroy(get_allocator()); 751 _Base_iterator __first = _Base::begin(); 752 _Base_iterator __last = _Base::end(); 753 while (__first != __last) 754 { 755 _Base_iterator __next = __first; 756 ++__next; 757 if (*__first == __value) 758 { 759 // _GLIBCXX_RESOLVE_LIB_DEFECTS 760 // 526. Is it undefined if a function in the standard changes 761 // in parameters? 762 this->_M_invalidate_if(_Equal(__first)); 763 __to_destroy.splice(__to_destroy.begin(), *this, __first); 764 #if !_GLIBCXX_USE_CXX11_ABI 765 _GLIBCXX20_ONLY( __removed++ ); 766 #endif 767 } 768 769 __first = __next; 770 } 771 772 #if !_GLIBCXX_USE_CXX11_ABI 773 return _GLIBCXX20_ONLY( __removed ); 774 #else 775 return _GLIBCXX20_ONLY( __to_destroy.size() ); 776 #endif 777 } 778 779 template<class _Predicate> 780 __remove_return_type 781 remove_if(_Predicate __pred) 782 { 783 if (!this->_M_iterators && !this->_M_const_iterators) 784 return _Base::remove_if(__pred); 785 786 #if !_GLIBCXX_USE_CXX11_ABI 787 size_type __removed __attribute__((__unused__)) = 0; 788 #endif 789 _Base __to_destroy(get_allocator()); 790 for (_Base_iterator __x = _Base::begin(); __x != _Base::end(); ) 791 { 792 _Base_iterator __next = __x; 793 ++__next; 794 if (__pred(*__x)) 795 { 796 this->_M_invalidate_if(_Equal(__x)); 797 __to_destroy.splice(__to_destroy.begin(), *this, __x); 798 #if !_GLIBCXX_USE_CXX11_ABI 799 _GLIBCXX20_ONLY( __removed++ ); 800 #endif 801 } 802 803 __x = __next; 804 } 805 806 #if !_GLIBCXX_USE_CXX11_ABI 807 return _GLIBCXX20_ONLY( __removed ); 808 #else 809 return _GLIBCXX20_ONLY( __to_destroy.size() ); 810 #endif 811 } 812 813 _GLIBCXX_LIST_REMOVE_RETURN_TYPE_TAG 814 __remove_return_type 815 unique() 816 { 817 if (!this->_M_iterators && !this->_M_const_iterators) 818 return _Base::unique(); 819 820 if (empty()) 821 return _GLIBCXX20_ONLY(0); 822 823 #if !_GLIBCXX_USE_CXX11_ABI 824 size_type __removed __attribute__((__unused__)) = 0; 825 #endif 826 _Base __to_destroy(get_allocator()); 827 _Base_iterator __first = _Base::begin(); 828 _Base_iterator __last = _Base::end(); 829 _Base_iterator __next = __first; 830 while (++__next != __last) 831 if (*__first == *__next) 832 { 833 this->_M_invalidate_if(_Equal(__next)); 834 __to_destroy.splice(__to_destroy.begin(), *this, __next); 835 __next = __first; 836 #if !_GLIBCXX_USE_CXX11_ABI 837 _GLIBCXX20_ONLY( __removed++ ); 838 #endif 839 } 840 else 841 __first = __next; 842 843 #if !_GLIBCXX_USE_CXX11_ABI 844 return _GLIBCXX20_ONLY( __removed ); 845 #else 846 return _GLIBCXX20_ONLY( __to_destroy.size() ); 847 #endif 848 } 849 850 template<class _BinaryPredicate> 851 __remove_return_type 852 unique(_BinaryPredicate __binary_pred) 853 { 854 if (!this->_M_iterators && !this->_M_const_iterators) 855 return _Base::unique(__binary_pred); 856 857 if (empty()) 858 return _GLIBCXX20_ONLY(0); 859 860 861 #if !_GLIBCXX_USE_CXX11_ABI 862 size_type __removed __attribute__((__unused__)) = 0; 863 #endif 864 _Base __to_destroy(get_allocator()); 865 _Base_iterator __first = _Base::begin(); 866 _Base_iterator __last = _Base::end(); 867 _Base_iterator __next = __first; 868 while (++__next != __last) 869 if (__binary_pred(*__first, *__next)) 870 { 871 this->_M_invalidate_if(_Equal(__next)); 872 __to_destroy.splice(__to_destroy.begin(), *this, __next); 873 __next = __first; 874 #if !_GLIBCXX_USE_CXX11_ABI 875 _GLIBCXX20_ONLY( __removed++ ); 876 #endif 877 } 878 else 879 __first = __next; 880 881 #if !_GLIBCXX_USE_CXX11_ABI 882 return _GLIBCXX20_ONLY( __removed ); 883 #else 884 return _GLIBCXX20_ONLY( __to_destroy.size() ); 885 #endif 886 } 887 888 #undef _GLIBCXX_LIST_REMOVE_RETURN_TYPE_TAG 889 #undef _GLIBCXX20_ONLY 890 891 void 892 #if __cplusplus >= 201103L 893 merge(list&& __x) 894 #else 895 merge(list& __x) 896 #endif 897 { 898 // _GLIBCXX_RESOLVE_LIB_DEFECTS 899 // 300. list::merge() specification incomplete 900 if (this != std::__addressof(__x)) 901 { 902 __glibcxx_check_sorted(_Base::begin(), _Base::end()); 903 __glibcxx_check_sorted(__x.begin().base(), __x.end().base()); 904 this->_M_transfer_from_if(__x, _Not_equal(__x._M_base().end())); 905 _Base::merge(_GLIBCXX_MOVE(__x)); 906 } 907 } 908 909 #if __cplusplus >= 201103L 910 void 911 merge(list& __x) 912 { merge(std::move(__x)); } 913 #endif 914 915 template<class _Compare> 916 void 917 #if __cplusplus >= 201103L 918 merge(list&& __x, _Compare __comp) 919 #else 920 merge(list& __x, _Compare __comp) 921 #endif 922 { 923 // _GLIBCXX_RESOLVE_LIB_DEFECTS 924 // 300. list::merge() specification incomplete 925 if (this != std::__addressof(__x)) 926 { 927 __glibcxx_check_sorted_pred(_Base::begin(), _Base::end(), 928 __comp); 929 __glibcxx_check_sorted_pred(__x.begin().base(), __x.end().base(), 930 __comp); 931 this->_M_transfer_from_if(__x, _Not_equal(__x._M_base().end())); 932 _Base::merge(_GLIBCXX_MOVE(__x), __comp); 933 } 934 } 935 936 #if __cplusplus >= 201103L 937 template<typename _Compare> 938 void 939 merge(list& __x, _Compare __comp) 940 { merge(std::move(__x), __comp); } 941 #endif 942 943 void 944 sort() { _Base::sort(); } 945 946 template<typename _StrictWeakOrdering> 947 void 948 sort(_StrictWeakOrdering __pred) { _Base::sort(__pred); } 949 950 using _Base::reverse; 951 952 _Base& 953 _M_base() _GLIBCXX_NOEXCEPT { return *this; } 954 955 const _Base& 956 _M_base() const _GLIBCXX_NOEXCEPT { return *this; } 957 }; 958 959 #if __cpp_deduction_guides >= 201606 960 template<typename _InputIterator, typename _ValT 961 = typename iterator_traits<_InputIterator>::value_type, 962 typename _Allocator = allocator<_ValT>, 963 typename = _RequireInputIter<_InputIterator>, 964 typename = _RequireAllocator<_Allocator>> 965 list(_InputIterator, _InputIterator, _Allocator = _Allocator()) 966 -> list<_ValT, _Allocator>; 967 968 template<typename _Tp, typename _Allocator = allocator<_Tp>, 969 typename = _RequireAllocator<_Allocator>> 970 list(size_t, _Tp, _Allocator = _Allocator()) 971 -> list<_Tp, _Allocator>; 972 973 #if __glibcxx_containers_ranges // C++ >= 23 974 template<ranges::input_range _Rg, 975 typename _Allocator = allocator<ranges::range_value_t<_Rg>>> 976 list(from_range_t, _Rg&&, _Allocator = _Allocator()) 977 -> list<ranges::range_value_t<_Rg>, _Allocator>; 978 #endif 979 #endif 980 981 template<typename _Tp, typename _Alloc> 982 inline bool 983 operator==(const list<_Tp, _Alloc>& __lhs, 984 const list<_Tp, _Alloc>& __rhs) 985 { return __lhs._M_base() == __rhs._M_base(); } 986 987 #if __cpp_lib_three_way_comparison 988 template<typename _Tp, typename _Alloc> 989 constexpr __detail::__synth3way_t<_Tp> 990 operator<=>(const list<_Tp, _Alloc>& __x, const list<_Tp, _Alloc>& __y) 991 { return __x._M_base() <=> __y._M_base(); } 992 #else 993 template<typename _Tp, typename _Alloc> 994 inline bool 995 operator!=(const list<_Tp, _Alloc>& __lhs, 996 const list<_Tp, _Alloc>& __rhs) 997 { return __lhs._M_base() != __rhs._M_base(); } 998 999 template<typename _Tp, typename _Alloc> 1000 inline bool 1001 operator<(const list<_Tp, _Alloc>& __lhs, 1002 const list<_Tp, _Alloc>& __rhs) 1003 { return __lhs._M_base() < __rhs._M_base(); } 1004 1005 template<typename _Tp, typename _Alloc> 1006 inline bool 1007 operator<=(const list<_Tp, _Alloc>& __lhs, 1008 const list<_Tp, _Alloc>& __rhs) 1009 { return __lhs._M_base() <= __rhs._M_base(); } 1010 1011 template<typename _Tp, typename _Alloc> 1012 inline bool 1013 operator>=(const list<_Tp, _Alloc>& __lhs, 1014 const list<_Tp, _Alloc>& __rhs) 1015 { return __lhs._M_base() >= __rhs._M_base(); } 1016 1017 template<typename _Tp, typename _Alloc> 1018 inline bool 1019 operator>(const list<_Tp, _Alloc>& __lhs, 1020 const list<_Tp, _Alloc>& __rhs) 1021 { return __lhs._M_base() > __rhs._M_base(); } 1022 #endif // three-way comparison 1023 1024 template<typename _Tp, typename _Alloc> 1025 inline void 1026 swap(list<_Tp, _Alloc>& __lhs, list<_Tp, _Alloc>& __rhs) 1027 _GLIBCXX_NOEXCEPT_IF(noexcept(__lhs.swap(__rhs))) 1028 { __lhs.swap(__rhs); } 1029 1030 } // namespace __debug 1031 } // namespace std 1032 1033 namespace __gnu_debug 1034 { 1035 #ifndef _GLIBCXX_USE_CXX11_ABI 1036 // If not using C++11 list::size() is not in O(1) so we do not use it. 1037 template<typename _Tp, typename _Alloc> 1038 struct _Sequence_traits<std::__debug::list<_Tp, _Alloc> > 1039 { 1040 typedef typename std::__debug::list<_Tp, _Alloc>::iterator _It; 1041 1042 static typename _Distance_traits<_It>::__type 1043 _S_size(const std::__debug::list<_Tp, _Alloc>& __seq) 1044 { 1045 return __seq.empty() 1046 ? std::make_pair(0, __dp_exact) : std::make_pair(1, __dp_sign); 1047 } 1048 }; 1049 #endif 1050 1051 #ifndef _GLIBCXX_DEBUG_PEDANTIC 1052 template<class _Tp, class _Alloc> 1053 struct _Insert_range_from_self_is_safe<std::__debug::list<_Tp, _Alloc> > 1054 { enum { __value = 1 }; }; 1055 #endif 1056 } 1057 1058 #endif
