Where Online Learning is simpler!
The C and C++ Include Header Files
cat -n /usr/include/c++/15/bits/stl_list.h
1 // List implementation -*- C++ -*- 2 3 // Copyright (C) 2001-2025 Free Software Foundation, Inc. 4 // Copyright The GNU Toolchain Authors. 5 // 6 // This file is part of the GNU ISO C++ Library. This library is free 7 // software; you can redistribute it and/or modify it under the 8 // terms of the GNU General Public License as published by the 9 // Free Software Foundation; either version 3, or (at your option) 10 // any later version. 11 12 // This library is distributed in the hope that it will be useful, 13 // but WITHOUT ANY WARRANTY; without even the implied warranty of 14 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 15 // GNU General Public License for more details. 16 17 // Under Section 7 of GPL version 3, you are granted additional 18 // permissions described in the GCC Runtime Library Exception, version 19 // 3.1, as published by the Free Software Foundation. 20 21 // You should have received a copy of the GNU General Public License and 22 // a copy of the GCC Runtime Library Exception along with this program; 23 // see the files COPYING3 and COPYING.RUNTIME respectively. If not, see 24 // <http://www.gnu.org/licenses/>. 25 26 /* 27 * 28 * Copyright (c) 1994 29 * Hewlett-Packard Company 30 * 31 * Permission to use, copy, modify, distribute and sell this software 32 * and its documentation for any purpose is hereby granted without fee, 33 * provided that the above copyright notice appear in all copies and 34 * that both that copyright notice and this permission notice appear 35 * in supporting documentation. Hewlett-Packard Company makes no 36 * representations about the suitability of this software for any 37 * purpose. It is provided "as is" without express or implied warranty. 38 * 39 * 40 * Copyright (c) 1996,1997 41 * Silicon Graphics Computer Systems, Inc. 42 * 43 * Permission to use, copy, modify, distribute and sell this software 44 * and its documentation for any purpose is hereby granted without fee, 45 * provided that the above copyright notice appear in all copies and 46 * that both that copyright notice and this permission notice appear 47 * in supporting documentation. Silicon Graphics makes no 48 * representations about the suitability of this software for any 49 * purpose. It is provided "as is" without express or implied warranty. 50 */ 51 52 /** @file bits/stl_list.h 53 * This is an internal header file, included by other library headers. 54 * Do not attempt to use it directly. @headername{list} 55 */ 56 57 #ifndef _STL_LIST_H 58 #define _STL_LIST_H 1 59 60 #include <bits/concept_check.h> 61 #include <ext/alloc_traits.h> 62 #include <debug/assertions.h> 63 #if __cplusplus >= 201103L 64 #include <initializer_list> 65 #include <bits/allocated_ptr.h> 66 #include <bits/ptr_traits.h> 67 #include <ext/aligned_buffer.h> 68 #endif 69 #if __glibcxx_containers_ranges // C++ >= 23 70 # include <bits/ranges_base.h> // ranges::begin, ranges::distance etc. 71 # include <bits/ranges_util.h> // ranges::subrange 72 #endif 73 74 #if __cplusplus < 201103L 75 # undef _GLIBCXX_USE_ALLOC_PTR_FOR_LIST 76 # define _GLIBCXX_USE_ALLOC_PTR_FOR_LIST 0 77 #elif ! defined _GLIBCXX_USE_ALLOC_PTR_FOR_LIST 78 # define _GLIBCXX_USE_ALLOC_PTR_FOR_LIST 1 79 #endif 80 81 namespace std _GLIBCXX_VISIBILITY(default) 82 { 83 _GLIBCXX_BEGIN_NAMESPACE_VERSION 84 85 namespace __detail 86 { 87 // Supporting structures are split into common and templated 88 // types; the latter publicly inherits from the former in an 89 // effort to reduce code duplication. This results in some 90 // "needless" static_cast'ing later on, but it's all safe 91 // downcasting. 92 93 /// Common part of a node in the %list. 94 struct _List_node_base 95 { 96 typedef _List_node_base* _Base_ptr; 97 98 _List_node_base* _M_next; 99 _List_node_base* _M_prev; 100 101 static void 102 swap(_List_node_base& __x, _List_node_base& __y) _GLIBCXX_USE_NOEXCEPT; 103 104 void 105 _M_transfer(_List_node_base* const __first, 106 _List_node_base* const __last) _GLIBCXX_USE_NOEXCEPT; 107 108 void 109 _M_reverse() _GLIBCXX_USE_NOEXCEPT; 110 111 void 112 _M_hook(_List_node_base* const __position) _GLIBCXX_USE_NOEXCEPT; 113 114 void 115 _M_unhook() _GLIBCXX_USE_NOEXCEPT; 116 117 _List_node_base* _M_base() { return this; } 118 const _List_node_base* _M_base() const { return this; } 119 }; 120 121 struct _List_size 122 { 123 #if _GLIBCXX_USE_CXX11_ABI 124 // Store the size here so that std::list::size() is fast. 125 size_t _M_size; 126 #endif 127 }; 128 129 /// The %list node header. 130 struct _List_node_header : public _List_node_base, _List_size 131 { 132 _List_node_header() _GLIBCXX_NOEXCEPT 133 { _M_init(); } 134 135 #if __cplusplus >= 201103L 136 _List_node_header(_List_node_header&& __x) noexcept 137 : _List_node_base(__x), _List_size(__x) 138 { 139 if (__x._M_base()->_M_next == __x._M_base()) 140 this->_M_next = this->_M_prev = this; 141 else 142 { 143 this->_M_next->_M_prev = this->_M_prev->_M_next = this->_M_base(); 144 __x._M_init(); 145 } 146 } 147 148 void 149 _M_move_nodes(_List_node_header&& __x) 150 { 151 _List_node_base* const __xnode = __x._M_base(); 152 if (__xnode->_M_next == __xnode) 153 _M_init(); 154 else 155 { 156 _List_node_base* const __node = this->_M_base(); 157 __node->_M_next = __xnode->_M_next; 158 __node->_M_prev = __xnode->_M_prev; 159 __node->_M_next->_M_prev = __node->_M_prev->_M_next = __node; 160 _List_size::operator=(__x); 161 __x._M_init(); 162 } 163 } 164 #endif 165 166 void 167 _M_init() _GLIBCXX_NOEXCEPT 168 { 169 this->_M_next = this->_M_prev = this; 170 _List_size::operator=(_List_size()); 171 } 172 173 using _List_node_base::_M_base; 174 #if ! _GLIBCXX_INLINE_VERSION 175 _List_node_base* _M_base() { return this; } // XXX GLIBCXX_ABI Deprecated 176 #endif 177 }; 178 179 } // namespace detail 180 181 #if _GLIBCXX_USE_ALLOC_PTR_FOR_LIST 182 _GLIBCXX_BEGIN_NAMESPACE_CONTAINER 183 _GLIBCXX_BEGIN_NAMESPACE_CXX11 184 template<typename _Tp, typename _Allocator> class list; 185 _GLIBCXX_END_NAMESPACE_CXX11 186 _GLIBCXX_END_NAMESPACE_CONTAINER 187 188 namespace __list 189 { 190 // The base class for a list node. Contains the pointers connecting nodes. 191 template<typename _VoidPtr> 192 struct _Node_base 193 { 194 using _Base_ptr = __ptr_rebind<_VoidPtr, _Node_base>; 195 _Base_ptr _M_next; 196 _Base_ptr _M_prev; 197 198 static void 199 swap(_Node_base& __x, _Node_base& __y) noexcept; 200 201 void 202 _M_transfer(_Base_ptr const __first, _Base_ptr const __last) noexcept; 203 204 void 205 _M_hook(_Base_ptr const __position) noexcept 206 { 207 auto __self = this->_M_base(); 208 this->_M_next = __position; 209 this->_M_prev = __position->_M_prev; 210 __position->_M_prev->_M_next = __self; 211 __position->_M_prev = __self; 212 } 213 214 void 215 _M_unhook() noexcept 216 { 217 auto const __next_node = this->_M_next; 218 auto const __prev_node = this->_M_prev; 219 __prev_node->_M_next = __next_node; 220 __next_node->_M_prev = __prev_node; 221 } 222 223 // This is not const-correct, but it's only used in a const access path 224 // by std::list::empty(), where it doesn't escape, and by 225 // std::list::end() const, where the pointer is used to initialize a 226 // const_iterator and so constness is restored. 227 // The standard allows pointer_to to be potentially-throwing, 228 // but we have to assume it doesn't throw to implement std::list. 229 _Base_ptr 230 _M_base() const noexcept 231 { 232 return pointer_traits<_Base_ptr>:: 233 pointer_to(const_cast<_Node_base&>(*this)); 234 } 235 }; 236 237 using ::std::__detail::_List_size; 238 239 // The special sentinel node contained by a std::list. 240 // begin()->_M_node->_M_prev and end()->_M_node point to this header. 241 // This is not a complete node, as it doesn't contain a value. 242 template<typename _VoidPtr> 243 struct _Node_header 244 : public _Node_base<_VoidPtr>, _List_size 245 { 246 _Node_header() noexcept 247 { _M_init(); } 248 249 _Node_header(_Node_header&& __x) noexcept 250 : _Node_base<_VoidPtr>(__x), _List_size(__x) 251 { 252 if (__x._M_base()->_M_next == __x._M_base()) 253 this->_M_next = this->_M_prev = this->_M_base(); 254 else 255 { 256 this->_M_next->_M_prev = this->_M_prev->_M_next = this->_M_base(); 257 __x._M_init(); 258 } 259 } 260 261 void 262 _M_move_nodes(_Node_header&& __x) noexcept 263 { 264 auto const __xnode = __x._M_base(); 265 if (__xnode->_M_next == __xnode) 266 _M_init(); 267 else 268 { 269 auto const __node = this->_M_base(); 270 __node->_M_next = __xnode->_M_next; 271 __node->_M_prev = __xnode->_M_prev; 272 __node->_M_next->_M_prev = __node->_M_prev->_M_next = __node; 273 _List_size::operator=(__x); 274 __x._M_init(); 275 } 276 } 277 278 void 279 _M_init() noexcept 280 { 281 this->_M_next = this->_M_prev = this->_M_base(); 282 _List_size::operator=(_List_size()); 283 } 284 285 void _M_reverse() noexcept; 286 }; 287 288 // The node type used for allocators with fancy pointers. 289 template<typename _ValPtr> 290 struct _Node : public __list::_Node_base<__ptr_rebind<_ValPtr, void>> 291 { 292 using value_type = typename pointer_traits<_ValPtr>::element_type; 293 using _Node_ptr = __ptr_rebind<_ValPtr, _Node>; 294 295 _Node() noexcept { } 296 ~_Node() { } 297 _Node(_Node&&) = delete; 298 299 union _Uninit_storage 300 { 301 _Uninit_storage() noexcept { } 302 ~_Uninit_storage() { } 303 304 value_type _M_data; 305 }; 306 _Uninit_storage _M_u; 307 308 value_type* 309 _M_valptr() noexcept { return std::__addressof(_M_u._M_data); } 310 311 value_type const* 312 _M_valptr() const noexcept { return std::__addressof(_M_u._M_data); } 313 314 _Node_ptr 315 _M_node_ptr() 316 { return pointer_traits<_Node_ptr>::pointer_to(*this); } 317 }; 318 319 template<bool _Const, typename _Ptr> class _Iterator; 320 321 template<bool _Const, typename _Ptr> 322 class _Iterator 323 { 324 using _Node = __list::_Node<_Ptr>; 325 using _Base_ptr 326 = typename __list::_Node_base<__ptr_rebind<_Ptr, void>>::_Base_ptr; 327 328 template<typename _Tp> 329 using __maybe_const = __conditional_t<_Const, const _Tp, _Tp>; 330 331 public: 332 using value_type = typename pointer_traits<_Ptr>::element_type; 333 using difference_type = ptrdiff_t; 334 using iterator_category = bidirectional_iterator_tag; 335 using pointer = __maybe_const<value_type>*; 336 using reference = __maybe_const<value_type>&; 337 338 constexpr _Iterator() noexcept : _M_node() { } 339 340 _Iterator(const _Iterator&) = default; 341 _Iterator& operator=(const _Iterator&) = default; 342 343 #ifdef __glibcxx_concepts 344 constexpr 345 _Iterator(const _Iterator<false, _Ptr>& __i) requires _Const 346 #else 347 template<bool _OtherConst, 348 typename = __enable_if_t<_Const && !_OtherConst>> 349 constexpr 350 _Iterator(const _Iterator<_OtherConst, _Ptr>& __i) 351 #endif 352 : _M_node(__i._M_node) { } 353 354 constexpr explicit 355 _Iterator(_Base_ptr __x) noexcept 356 : _M_node(__x) { } 357 358 // Must downcast from _Node_base to _Node to get to value. 359 [[__nodiscard__]] 360 constexpr reference 361 operator*() const noexcept 362 { return static_cast<_Node&>(*_M_node)._M_u._M_data; } 363 364 [[__nodiscard__]] 365 constexpr pointer 366 operator->() const noexcept 367 { return std::__addressof(operator*()); } 368 369 _GLIBCXX14_CONSTEXPR _Iterator& 370 operator++() noexcept 371 { 372 _M_node = _M_node->_M_next; 373 return *this; 374 } 375 376 _GLIBCXX14_CONSTEXPR _Iterator 377 operator++(int) noexcept 378 { 379 auto __tmp = *this; 380 _M_node = _M_node->_M_next; 381 return __tmp; 382 } 383 384 _GLIBCXX14_CONSTEXPR _Iterator& 385 operator--() noexcept 386 { 387 _M_node = _M_node->_M_prev; 388 return *this; 389 } 390 391 _GLIBCXX14_CONSTEXPR _Iterator 392 operator--(int) noexcept 393 { 394 auto __tmp = *this; 395 _M_node = _M_node->_M_prev; 396 return __tmp; 397 } 398 399 [[__nodiscard__]] 400 friend constexpr bool 401 operator==(const _Iterator& __x, const _Iterator& __y) noexcept 402 { return __x._M_node == __y._M_node; } 403 404 #if __cpp_impl_three_way_comparison < 201907L 405 [[__nodiscard__]] 406 friend constexpr bool 407 operator!=(const _Iterator& __x, const _Iterator& __y) noexcept 408 { return __x._M_node != __y._M_node; } 409 #endif 410 411 private: 412 template<typename _Tp, typename _Allocator> 413 friend class _GLIBCXX_STD_C::list; 414 415 friend _Iterator<!_Const, _Ptr>; 416 417 constexpr _Iterator<false, _Ptr> 418 _M_const_cast() const noexcept 419 { return _Iterator<false, _Ptr>(_M_node); } 420 421 _Base_ptr _M_node; 422 }; 423 } // namespace __list 424 #endif // USE_ALLOC_PTR_FOR_LIST 425 426 _GLIBCXX_BEGIN_NAMESPACE_CONTAINER 427 template<typename _Tp> struct _List_node; 428 template<typename _Tp> struct _List_iterator; 429 template<typename _Tp> struct _List_const_iterator; 430 _GLIBCXX_END_NAMESPACE_CONTAINER 431 432 namespace __list 433 { 434 // Determine the node and iterator types used by std::list. 435 template<typename _Tp, typename _Ptr> 436 struct _Node_traits; 437 438 #if _GLIBCXX_USE_ALLOC_PTR_FOR_LIST <= 9000 439 // Specialization for the simple case where the allocator's pointer type 440 // is the same type as value_type*. 441 // For ABI compatibility we can't change the types used for this case. 442 template<typename _Tp> 443 struct _Node_traits<_Tp, _Tp*> 444 { 445 typedef __detail::_List_node_base _Node_base; 446 typedef __detail::_List_node_header _Node_header; 447 typedef _GLIBCXX_STD_C::_List_node<_Tp> _Node; 448 typedef _GLIBCXX_STD_C::_List_iterator<_Tp> _Iterator; 449 typedef _GLIBCXX_STD_C::_List_const_iterator<_Tp> _Const_iterator; 450 }; 451 #endif 452 453 #if ! _GLIBCXX_USE_ALLOC_PTR_FOR_LIST 454 // Always use the T* specialization. 455 template<typename _Tp, typename _Ptr> 456 struct _Node_traits 457 : _Node_traits<_Tp, _Tp*> 458 { }; 459 #else 460 // Primary template used when the allocator uses fancy pointers. 461 template<typename _Tp, typename _Ptr> 462 struct _Node_traits 463 { 464 private: 465 using _VoidPtr = __ptr_rebind<_Ptr, void>; 466 using _ValPtr = __ptr_rebind<_Ptr, _Tp>; 467 468 public: 469 using _Node_base = __list::_Node_base<_VoidPtr>; 470 using _Node_header = __list::_Node_header<_VoidPtr>; 471 using _Node = __list::_Node<_ValPtr>; 472 using _Iterator = __list::_Iterator<false, _ValPtr>; 473 using _Const_iterator = __list::_Iterator<true, _ValPtr>; 474 }; 475 #endif // USE_ALLOC_PTR_FOR_LIST 476 477 // Used by std::list::sort to hold nodes being sorted. 478 template<typename _NodeBaseT> 479 struct _Scratch_list 480 : _NodeBaseT 481 { 482 typedef _NodeBaseT _Base; 483 typedef typename _Base::_Base_ptr _Base_ptr; 484 485 _Scratch_list() { this->_M_next = this->_M_prev = this->_M_base(); } 486 487 bool empty() const { return this->_M_next == this->_M_base(); } 488 489 void swap(_Base& __l) { _Base::swap(*this, __l); } 490 491 template<typename _Iter, typename _Cmp> 492 struct _Ptr_cmp 493 { 494 _Cmp _M_cmp; 495 496 bool 497 operator()(_Base_ptr __lhs, _Base_ptr __rhs) /* not const */ 498 { return _M_cmp(*_Iter(__lhs), *_Iter(__rhs)); } 499 }; 500 501 template<typename _Iter> 502 struct _Ptr_cmp<_Iter, void> 503 { 504 bool 505 operator()(_Base_ptr __lhs, _Base_ptr __rhs) const 506 { return *_Iter(__lhs) < *_Iter(__rhs); } 507 }; 508 509 // Merge nodes from __x into *this. Both lists must be sorted wrt _Cmp. 510 template<typename _Cmp> 511 void 512 merge(_Base& __x, _Cmp __comp) 513 { 514 _Base_ptr __first1 = this->_M_next; 515 _Base_ptr const __last1 = this->_M_base(); 516 _Base_ptr __first2 = __x._M_next; 517 _Base_ptr const __last2 = __x._M_base(); 518 519 while (__first1 != __last1 && __first2 != __last2) 520 { 521 if (__comp(__first2, __first1)) 522 { 523 _Base_ptr __next = __first2->_M_next; 524 __first1->_M_transfer(__first2, __next); 525 __first2 = __next; 526 } 527 else 528 __first1 = __first1->_M_next; 529 } 530 if (__first2 != __last2) 531 this->_M_transfer(__first2, __last2); 532 } 533 534 // Splice the node at __i into *this. 535 void _M_take_one(_Base_ptr __i) 536 { this->_M_transfer(__i, __i->_M_next); } 537 538 // Splice all nodes from *this after __i. 539 void _M_put_all(_Base_ptr __i) 540 { 541 if (!empty()) 542 __i->_M_transfer(this->_M_next, this->_M_base()); 543 } 544 }; 545 } // namespace __list 546 547 _GLIBCXX_BEGIN_NAMESPACE_CONTAINER 548 549 /// An actual node in the %list. 550 template<typename _Tp> 551 struct _List_node : public __detail::_List_node_base 552 { 553 typedef _List_node* _Node_ptr; 554 555 #if __cplusplus >= 201103L 556 __gnu_cxx::__aligned_membuf<_Tp> _M_storage; 557 _Tp* _M_valptr() { return _M_storage._M_ptr(); } 558 _Tp const* _M_valptr() const { return _M_storage._M_ptr(); } 559 #else 560 _Tp _M_data; 561 _Tp* _M_valptr() { return std::__addressof(_M_data); } 562 _Tp const* _M_valptr() const { return std::__addressof(_M_data); } 563 #endif 564 565 _Node_ptr _M_node_ptr() { return this; } 566 }; 567 568 /** 569 * @brief A list::iterator. 570 * 571 * All the functions are op overloads. 572 */ 573 template<typename _Tp> 574 struct _List_iterator 575 { 576 typedef _List_node<_Tp> _Node; 577 578 typedef ptrdiff_t difference_type; 579 typedef std::bidirectional_iterator_tag iterator_category; 580 typedef _Tp value_type; 581 typedef _Tp* pointer; 582 typedef _Tp& reference; 583 584 _List_iterator() _GLIBCXX_NOEXCEPT 585 : _M_node() { } 586 587 explicit 588 _List_iterator(__detail::_List_node_base* __x) _GLIBCXX_NOEXCEPT 589 : _M_node(__x) { } 590 591 _List_iterator 592 _M_const_cast() const _GLIBCXX_NOEXCEPT 593 { return *this; } 594 595 // Must downcast from _List_node_base to _List_node to get to value. 596 _GLIBCXX_NODISCARD 597 reference 598 operator*() const _GLIBCXX_NOEXCEPT 599 { return *static_cast<_Node*>(_M_node)->_M_valptr(); } 600 601 _GLIBCXX_NODISCARD 602 pointer 603 operator->() const _GLIBCXX_NOEXCEPT 604 { return static_cast<_Node*>(_M_node)->_M_valptr(); } 605 606 _List_iterator& 607 operator++() _GLIBCXX_NOEXCEPT 608 { 609 _M_node = _M_node->_M_next; 610 return *this; 611 } 612 613 _List_iterator 614 operator++(int) _GLIBCXX_NOEXCEPT 615 { 616 _List_iterator __tmp = *this; 617 _M_node = _M_node->_M_next; 618 return __tmp; 619 } 620 621 _List_iterator& 622 operator--() _GLIBCXX_NOEXCEPT 623 { 624 _M_node = _M_node->_M_prev; 625 return *this; 626 } 627 628 _List_iterator 629 operator--(int) _GLIBCXX_NOEXCEPT 630 { 631 _List_iterator __tmp = *this; 632 _M_node = _M_node->_M_prev; 633 return __tmp; 634 } 635 636 _GLIBCXX_NODISCARD 637 friend bool 638 operator==(const _List_iterator& __x, 639 const _List_iterator& __y) _GLIBCXX_NOEXCEPT 640 { return __x._M_node == __y._M_node; } 641 642 #if __cpp_impl_three_way_comparison < 201907L 643 _GLIBCXX_NODISCARD 644 friend bool 645 operator!=(const _List_iterator& __x, 646 const _List_iterator& __y) _GLIBCXX_NOEXCEPT 647 { return __x._M_node != __y._M_node; } 648 #endif 649 650 // The only member points to the %list element. 651 __detail::_List_node_base* _M_node; 652 }; 653 654 /** 655 * @brief A list::const_iterator. 656 * 657 * All the functions are op overloads. 658 */ 659 template<typename _Tp> 660 struct _List_const_iterator 661 { 662 typedef const _List_node<_Tp> _Node; 663 typedef _List_iterator<_Tp> iterator; 664 665 typedef ptrdiff_t difference_type; 666 typedef std::bidirectional_iterator_tag iterator_category; 667 typedef _Tp value_type; 668 typedef const _Tp* pointer; 669 typedef const _Tp& reference; 670 671 _List_const_iterator() _GLIBCXX_NOEXCEPT 672 : _M_node() { } 673 674 explicit 675 _List_const_iterator(const __detail::_List_node_base* __x) 676 _GLIBCXX_NOEXCEPT 677 : _M_node(__x) { } 678 679 _List_const_iterator(const iterator& __x) _GLIBCXX_NOEXCEPT 680 : _M_node(__x._M_node) { } 681 682 iterator 683 _M_const_cast() const _GLIBCXX_NOEXCEPT 684 { return iterator(const_cast<__detail::_List_node_base*>(_M_node)); } 685 686 // Must downcast from List_node_base to _List_node to get to value. 687 _GLIBCXX_NODISCARD 688 reference 689 operator*() const _GLIBCXX_NOEXCEPT 690 { return *static_cast<_Node*>(_M_node)->_M_valptr(); } 691 692 _GLIBCXX_NODISCARD 693 pointer 694 operator->() const _GLIBCXX_NOEXCEPT 695 { return static_cast<_Node*>(_M_node)->_M_valptr(); } 696 697 _List_const_iterator& 698 operator++() _GLIBCXX_NOEXCEPT 699 { 700 _M_node = _M_node->_M_next; 701 return *this; 702 } 703 704 _List_const_iterator 705 operator++(int) _GLIBCXX_NOEXCEPT 706 { 707 _List_const_iterator __tmp = *this; 708 _M_node = _M_node->_M_next; 709 return __tmp; 710 } 711 712 _List_const_iterator& 713 operator--() _GLIBCXX_NOEXCEPT 714 { 715 _M_node = _M_node->_M_prev; 716 return *this; 717 } 718 719 _List_const_iterator 720 operator--(int) _GLIBCXX_NOEXCEPT 721 { 722 _List_const_iterator __tmp = *this; 723 _M_node = _M_node->_M_prev; 724 return __tmp; 725 } 726 727 _GLIBCXX_NODISCARD 728 friend bool 729 operator==(const _List_const_iterator& __x, 730 const _List_const_iterator& __y) _GLIBCXX_NOEXCEPT 731 { return __x._M_node == __y._M_node; } 732 733 #if __cpp_impl_three_way_comparison < 201907L 734 _GLIBCXX_NODISCARD 735 friend bool 736 operator!=(const _List_const_iterator& __x, 737 const _List_const_iterator& __y) _GLIBCXX_NOEXCEPT 738 { return __x._M_node != __y._M_node; } 739 #endif 740 741 // The only member points to the %list element. 742 const __detail::_List_node_base* _M_node; 743 }; 744 745 _GLIBCXX_BEGIN_NAMESPACE_CXX11 746 /// See bits/stl_deque.h's _Deque_base for an explanation. 747 template<typename _Tp, typename _Alloc> 748 class _List_base 749 { 750 protected: 751 typedef typename __gnu_cxx::__alloc_traits<_Alloc>::template 752 rebind<_Tp>::other _Tp_alloc_type; 753 typedef __gnu_cxx::__alloc_traits<_Tp_alloc_type> _Tp_alloc_traits; 754 755 typedef __list::_Node_traits<_Tp, typename _Tp_alloc_traits::pointer> 756 _Node_traits; 757 typedef typename _Tp_alloc_traits::template 758 rebind<typename _Node_traits::_Node>::other _Node_alloc_type; 759 typedef __gnu_cxx::__alloc_traits<_Node_alloc_type> _Node_alloc_traits; 760 761 #if __cplusplus < 201103L || ! _GLIBCXX_USE_ALLOC_PTR_FOR_LIST 762 typedef _List_node<_Tp>* _Node_ptr; 763 #else 764 using _Node_ptr = typename _Node_alloc_traits::pointer; 765 #endif 766 767 struct _List_impl 768 : public _Node_alloc_type 769 { 770 typename _Node_traits::_Node_header _M_node; 771 772 _List_impl() _GLIBCXX_NOEXCEPT_IF( 773 is_nothrow_default_constructible<_Node_alloc_type>::value) 774 : _Node_alloc_type() 775 { } 776 777 _List_impl(const _Node_alloc_type& __a) _GLIBCXX_NOEXCEPT 778 : _Node_alloc_type(__a) 779 { } 780 781 #if __cplusplus >= 201103L 782 _List_impl(_List_impl&&) = default; 783 784 _List_impl(_Node_alloc_type&& __a, _List_impl&& __x) 785 : _Node_alloc_type(std::move(__a)), _M_node(std::move(__x._M_node)) 786 { } 787 788 _List_impl(_Node_alloc_type&& __a) noexcept 789 : _Node_alloc_type(std::move(__a)) 790 { } 791 #endif 792 }; 793 794 _List_impl _M_impl; 795 796 #if _GLIBCXX_USE_CXX11_ABI 797 size_t _M_get_size() const { return _M_impl._M_node._M_size; } 798 799 void _M_set_size(size_t __n) { _M_impl._M_node._M_size = __n; } 800 801 void _M_inc_size(size_t __n) { _M_impl._M_node._M_size += __n; } 802 803 void _M_dec_size(size_t __n) { _M_impl._M_node._M_size -= __n; } 804 #else 805 // dummy implementations used when the size is not stored 806 size_t _M_get_size() const { return 0; } 807 void _M_set_size(size_t) { } 808 void _M_inc_size(size_t) { } 809 void _M_dec_size(size_t) { } 810 #endif 811 812 typename _Node_alloc_traits::pointer 813 _M_get_node() 814 { return _Node_alloc_traits::allocate(_M_impl, 1); } 815 816 void 817 _M_put_node(_Node_ptr __p) _GLIBCXX_NOEXCEPT 818 { 819 #if __cplusplus < 201103L || _GLIBCXX_USE_ALLOC_PTR_FOR_LIST 820 _Node_alloc_traits::deallocate(_M_impl, __p, 1); 821 #else 822 #pragma GCC diagnostic push 823 #pragma GCC diagnostic ignored "-Wc++17-extensions" // if constexpr 824 using __alloc_pointer = typename _Node_alloc_traits::pointer; 825 if constexpr (is_same<_Node_ptr, __alloc_pointer>::value) 826 _Node_alloc_traits::deallocate(_M_impl, __p, 1); 827 else 828 { 829 // When not using the allocator's pointer type internally we must 830 // convert __p to __alloc_pointer so it can be deallocated. 831 auto __ap = pointer_traits<__alloc_pointer>::pointer_to(*__p); 832 _Node_alloc_traits::deallocate(_M_impl, __ap, 1); 833 } 834 #pragma GCC diagnostic pop 835 #endif 836 } 837 838 void 839 _M_destroy_node(_Node_ptr __p) 840 { 841 // Destroy the element 842 #if __cplusplus < 201103L 843 _Tp_alloc_type(_M_impl).destroy(__p->_M_valptr()); 844 #else 845 _Node_alloc_traits::destroy(_M_impl, __p->_M_valptr()); 846 // Only destroy the node if the pointers require it. 847 using _Node = typename _Node_traits::_Node; 848 using _Base_ptr = typename _Node_traits::_Node_base::_Base_ptr; 849 #pragma GCC diagnostic push 850 #pragma GCC diagnostic ignored "-Wc++17-extensions" // if constexpr 851 if constexpr (!is_trivially_destructible<_Base_ptr>::value) 852 __p->~_Node(); 853 #pragma GCC diagnostic pop 854 #endif 855 this->_M_put_node(__p); 856 } 857 858 public: 859 typedef _Alloc allocator_type; 860 861 _Node_alloc_type& 862 _M_get_Node_allocator() _GLIBCXX_NOEXCEPT 863 { return _M_impl; } 864 865 const _Node_alloc_type& 866 _M_get_Node_allocator() const _GLIBCXX_NOEXCEPT 867 { return _M_impl; } 868 869 #if __cplusplus >= 201103L 870 _List_base() = default; 871 #else 872 _List_base() { } 873 #endif 874 875 _List_base(const _Node_alloc_type& __a) _GLIBCXX_NOEXCEPT 876 : _M_impl(__a) 877 { } 878 879 #if __cplusplus >= 201103L 880 _List_base(_List_base&&) = default; 881 882 // Used when allocator is_always_equal. 883 _List_base(_Node_alloc_type&& __a, _List_base&& __x) 884 : _M_impl(std::move(__a), std::move(__x._M_impl)) 885 { } 886 887 // Used when allocator !is_always_equal. 888 _List_base(_Node_alloc_type&& __a) 889 : _M_impl(std::move(__a)) 890 { } 891 892 void 893 _M_move_nodes(_List_base&& __x) 894 { _M_impl._M_node._M_move_nodes(std::move(__x._M_impl._M_node)); } 895 #endif 896 897 // This is what actually destroys the list. 898 ~_List_base() _GLIBCXX_NOEXCEPT 899 { _M_clear(); } 900 901 void 902 _M_clear() _GLIBCXX_NOEXCEPT; 903 904 void 905 _M_init() _GLIBCXX_NOEXCEPT 906 { this->_M_impl._M_node._M_init(); } 907 908 #if !_GLIBCXX_INLINE_VERSION 909 // XXX GLIBCXX_ABI Deprecated 910 // These members are unused by std::list now, but we keep them here 911 // so that an explicit instantiation of std::list will define them. 912 // This ensures that explicit instantiations still define these symbols, 913 // so that explicit instantiation declarations of std::list that were 914 // compiled with old versions of GCC can still find these old symbols. 915 916 // Use 'if constexpr' so that the functions don't do anything for 917 // specializations using _Node_traits<T, fancy-pointer>, because any 918 // old code referencing these symbols wasn't using the fancy-pointer 919 // specializations. 920 921 #pragma GCC diagnostic push 922 #pragma GCC diagnostic ignored "-Wc++17-extensions" // if constexpr 923 924 # if __cplusplus >= 201103L 925 _List_base(_List_base&& __x, _Node_alloc_type&& __a) 926 : _M_impl(std::move(__a)) 927 { 928 #if _GLIBCXX_USE_ALLOC_PTR_FOR_LIST 929 if constexpr (is_same<typename _Tp_alloc_traits::pointer, _Tp*>::value) 930 #endif 931 if (__x._M_get_Node_allocator() == _M_get_Node_allocator()) 932 _M_move_nodes(std::move(__x)); 933 // else caller must move individual elements. 934 } 935 # endif 936 937 static size_t 938 _S_distance(const __detail::_List_node_base* __first, 939 const __detail::_List_node_base* __last) 940 { 941 #if _GLIBCXX_USE_ALLOC_PTR_FOR_LIST 942 if constexpr (!is_same<typename _Tp_alloc_traits::pointer, _Tp*>::value) 943 return 0; 944 else 945 #endif 946 { 947 size_t __n = 0; 948 while (__first != __last) 949 { 950 __first = __first->_M_next; 951 ++__n; 952 } 953 return __n; 954 } 955 } 956 957 #if _GLIBCXX_USE_CXX11_ABI 958 size_t 959 _M_distance(const __detail::_List_node_base* __first, 960 const __detail::_List_node_base* __last) const 961 { return _S_distance(__first, __last); } 962 963 // return the stored size 964 size_t _M_node_count() const { return _M_get_size(); } 965 #else 966 size_t _M_distance(const void*, const void*) const { return 0; } 967 968 // count the number of nodes 969 size_t _M_node_count() const 970 { 971 return _S_distance(_M_impl._M_node._M_next, _M_impl._M_node._M_base()); 972 } 973 #endif 974 #pragma GCC diagnostic pop 975 #endif // ! INLINE_VERSION 976 }; 977 978 /** 979 * @brief A standard container with linear time access to elements, 980 * and fixed time insertion/deletion at any point in the sequence. 981 * 982 * @ingroup sequences 983 * 984 * @tparam _Tp Type of element. 985 * @tparam _Alloc Allocator type, defaults to allocator<_Tp>. 986 * 987 * Meets the requirements of a <a href="tables.html#65">container</a>, a 988 * <a href="tables.html#66">reversible container</a>, and a 989 * <a href="tables.html#67">sequence</a>, including the 990 * <a href="tables.html#68">optional sequence requirements</a> with the 991 * %exception of @c at and @c operator[]. 992 * 993 * This is a @e doubly @e linked %list. Traversal up and down the 994 * %list requires linear time, but adding and removing elements (or 995 * @e nodes) is done in constant time, regardless of where the 996 * change takes place. Unlike std::vector and std::deque, 997 * random-access iterators are not provided, so subscripting ( @c 998 * [] ) access is not allowed. For algorithms which only need 999 * sequential access, this lack makes no difference. 1000 * 1001 * Also unlike the other standard containers, std::list provides 1002 * specialized algorithms %unique to linked lists, such as 1003 * splicing, sorting, and in-place reversal. 1004 * 1005 * A couple points on memory allocation for list<Tp>: 1006 * 1007 * First, we never actually allocate a Tp, we allocate 1008 * List_node<Tp>'s and trust [20.1.5]/4 to DTRT. This is to ensure 1009 * that after elements from %list<X,Alloc1> are spliced into 1010 * %list<X,Alloc2>, destroying the memory of the second %list is a 1011 * valid operation, i.e., Alloc1 giveth and Alloc2 taketh away. 1012 * 1013 * Second, a %list conceptually represented as 1014 * @code 1015 * A <---> B <---> C <---> D 1016 * @endcode 1017 * is actually circular; a link exists between A and D. The %list 1018 * class holds (as its only data member) a private list::iterator 1019 * pointing to @e D, not to @e A! To get to the head of the %list, 1020 * we start at the tail and move forward by one. When this member 1021 * iterator's next/previous pointers refer to itself, the %list is 1022 * %empty. 1023 */ 1024 template<typename _Tp, typename _Alloc = std::allocator<_Tp> > 1025 class list : protected _List_base<_Tp, _Alloc> 1026 { 1027 #ifdef _GLIBCXX_CONCEPT_CHECKS 1028 // concept requirements 1029 typedef typename _Alloc::value_type _Alloc_value_type; 1030 # if __cplusplus < 201103L 1031 __glibcxx_class_requires(_Tp, _SGIAssignableConcept) 1032 # endif 1033 __glibcxx_class_requires2(_Tp, _Alloc_value_type, _SameTypeConcept) 1034 #endif 1035 1036 #if __cplusplus >= 201103L 1037 static_assert(is_same<typename remove_cv<_Tp>::type, _Tp>::value, 1038 "std::list must have a non-const, non-volatile value_type"); 1039 # if __cplusplus > 201703L || defined __STRICT_ANSI__ 1040 static_assert(is_same<typename _Alloc::value_type, _Tp>::value, 1041 "std::list must have the same value_type as its allocator"); 1042 # endif 1043 #endif 1044 1045 typedef _List_base<_Tp, _Alloc> _Base; 1046 typedef typename _Base::_Tp_alloc_type _Tp_alloc_type; 1047 typedef typename _Base::_Tp_alloc_traits _Tp_alloc_traits; 1048 typedef typename _Base::_Node_alloc_type _Node_alloc_type; 1049 typedef typename _Base::_Node_alloc_traits _Node_alloc_traits; 1050 typedef typename _Base::_Node_traits _Node_traits; 1051 1052 public: 1053 typedef _Tp value_type; 1054 typedef typename _Tp_alloc_traits::pointer pointer; 1055 typedef typename _Tp_alloc_traits::const_pointer const_pointer; 1056 typedef typename _Tp_alloc_traits::reference reference; 1057 typedef typename _Tp_alloc_traits::const_reference const_reference; 1058 typedef typename _Node_traits::_Iterator iterator; 1059 typedef typename _Node_traits::_Const_iterator const_iterator; 1060 typedef std::reverse_iterator<const_iterator> const_reverse_iterator; 1061 typedef std::reverse_iterator<iterator> reverse_iterator; 1062 typedef size_t size_type; 1063 typedef ptrdiff_t difference_type; 1064 typedef _Alloc allocator_type; 1065 1066 protected: 1067 // Note that pointers-to-_Node's can be ctor-converted to 1068 // iterator types. 1069 typedef typename _Node_alloc_traits::pointer _Node_ptr; 1070 1071 using _Base::_M_impl; 1072 using _Base::_M_put_node; 1073 using _Base::_M_get_node; 1074 using _Base::_M_get_Node_allocator; 1075 1076 /** 1077 * @param __args An instance of user data. 1078 * 1079 * Allocates space for a new node and constructs a copy of 1080 * @a __args in it. 1081 */ 1082 #if __cplusplus < 201103L 1083 _Node_ptr 1084 _M_create_node(const value_type& __x) 1085 { 1086 _Node_ptr __p = this->_M_get_node(); 1087 __try 1088 { 1089 _Tp_alloc_type __alloc(_M_get_Node_allocator()); 1090 __alloc.construct(__p->_M_valptr(), __x); 1091 } 1092 __catch(...) 1093 { 1094 _M_put_node(__p); 1095 __throw_exception_again; 1096 } 1097 return __p; 1098 } 1099 #else 1100 template<typename... _Args> 1101 _Node_ptr 1102 _M_create_node(_Args&&... __args) 1103 { 1104 auto& __alloc = _M_get_Node_allocator(); 1105 auto __guard = std::__allocate_guarded_obj(__alloc); 1106 _Node_alloc_traits::construct(__alloc, __guard->_M_valptr(), 1107 std::forward<_Args>(__args)...); 1108 return __guard.release(); 1109 } 1110 #endif 1111 1112 public: 1113 // [23.2.2.1] construct/copy/destroy 1114 // (assign() and get_allocator() are also listed in this section) 1115 1116 /** 1117 * @brief Creates a %list with no elements. 1118 */ 1119 #if __cplusplus >= 201103L 1120 list() = default; 1121 #else 1122 list() { } 1123 #endif 1124 1125 /** 1126 * @brief Creates a %list with no elements. 1127 * @param __a An allocator object. 1128 */ 1129 explicit 1130 list(const allocator_type& __a) _GLIBCXX_NOEXCEPT 1131 : _Base(_Node_alloc_type(__a)) { } 1132 1133 #if __cplusplus >= 201103L 1134 /** 1135 * @brief Creates a %list with default constructed elements. 1136 * @param __n The number of elements to initially create. 1137 * @param __a An allocator object. 1138 * 1139 * This constructor fills the %list with @a __n default 1140 * constructed elements. 1141 */ 1142 explicit 1143 list(size_type __n, const allocator_type& __a = allocator_type()) 1144 : _Base(_Node_alloc_type(__a)) 1145 { _M_default_initialize(__n); } 1146 1147 /** 1148 * @brief Creates a %list with copies of an exemplar element. 1149 * @param __n The number of elements to initially create. 1150 * @param __value An element to copy. 1151 * @param __a An allocator object. 1152 * 1153 * This constructor fills the %list with @a __n copies of @a __value. 1154 */ 1155 list(size_type __n, const value_type& __value, 1156 const allocator_type& __a = allocator_type()) 1157 : _Base(_Node_alloc_type(__a)) 1158 { _M_fill_initialize(__n, __value); } 1159 #else 1160 /** 1161 * @brief Creates a %list with copies of an exemplar element. 1162 * @param __n The number of elements to initially create. 1163 * @param __value An element to copy. 1164 * @param __a An allocator object. 1165 * 1166 * This constructor fills the %list with @a __n copies of @a __value. 1167 */ 1168 explicit 1169 list(size_type __n, const value_type& __value = value_type(), 1170 const allocator_type& __a = allocator_type()) 1171 : _Base(_Node_alloc_type(__a)) 1172 { _M_fill_initialize(__n, __value); } 1173 #endif 1174 1175 /** 1176 * @brief %List copy constructor. 1177 * @param __x A %list of identical element and allocator types. 1178 * 1179 * The newly-created %list uses a copy of the allocation object used 1180 * by @a __x (unless the allocator traits dictate a different object). 1181 */ 1182 list(const list& __x) 1183 : _Base(_Node_alloc_traits:: 1184 _S_select_on_copy(__x._M_get_Node_allocator())) 1185 { _M_initialize_dispatch(__x.begin(), __x.end(), __false_type()); } 1186 1187 #if __cplusplus >= 201103L 1188 /** 1189 * @brief %List move constructor. 1190 * 1191 * The newly-created %list contains the exact contents of the moved 1192 * instance. The contents of the moved instance are a valid, but 1193 * unspecified %list. 1194 */ 1195 list(list&&) = default; 1196 1197 /** 1198 * @brief Builds a %list from an initializer_list 1199 * @param __l An initializer_list of value_type. 1200 * @param __a An allocator object. 1201 * 1202 * Create a %list consisting of copies of the elements in the 1203 * initializer_list @a __l. This is linear in __l.size(). 1204 */ 1205 list(initializer_list<value_type> __l, 1206 const allocator_type& __a = allocator_type()) 1207 : _Base(_Node_alloc_type(__a)) 1208 { _M_initialize_dispatch(__l.begin(), __l.end(), __false_type()); } 1209 1210 list(const list& __x, const __type_identity_t<allocator_type>& __a) 1211 : _Base(_Node_alloc_type(__a)) 1212 { _M_initialize_dispatch(__x.begin(), __x.end(), __false_type()); } 1213 1214 private: 1215 list(list&& __x, const allocator_type& __a, true_type) noexcept 1216 : _Base(_Node_alloc_type(__a), std::move(__x)) 1217 { } 1218 1219 list(list&& __x, const allocator_type& __a, false_type) 1220 : _Base(_Node_alloc_type(__a)) 1221 { 1222 if (__x._M_get_Node_allocator() == this->_M_get_Node_allocator()) 1223 this->_M_move_nodes(std::move(__x)); 1224 else 1225 insert(begin(), std::__make_move_if_noexcept_iterator(__x.begin()), 1226 std::__make_move_if_noexcept_iterator(__x.end())); 1227 } 1228 1229 public: 1230 list(list&& __x, const __type_identity_t<allocator_type>& __a) 1231 noexcept(_Node_alloc_traits::_S_always_equal()) 1232 : list(std::move(__x), __a, 1233 typename _Node_alloc_traits::is_always_equal{}) 1234 { } 1235 #endif 1236 1237 /** 1238 * @brief Builds a %list from a range. 1239 * @param __first An input iterator. 1240 * @param __last An input iterator. 1241 * @param __a An allocator object. 1242 * 1243 * Create a %list consisting of copies of the elements from 1244 * [@a __first,@a __last). This is linear in N (where N is 1245 * distance(@a __first,@a __last)). 1246 */ 1247 #if __cplusplus >= 201103L 1248 template<typename _InputIterator, 1249 typename = std::_RequireInputIter<_InputIterator>> 1250 list(_InputIterator __first, _InputIterator __last, 1251 const allocator_type& __a = allocator_type()) 1252 : _Base(_Node_alloc_type(__a)) 1253 { _M_initialize_dispatch(__first, __last, __false_type()); } 1254 #else 1255 template<typename _InputIterator> 1256 list(_InputIterator __first, _InputIterator __last, 1257 const allocator_type& __a = allocator_type()) 1258 : _Base(_Node_alloc_type(__a)) 1259 { 1260 // Check whether it's an integral type. If so, it's not an iterator. 1261 typedef typename std::__is_integer<_InputIterator>::__type _Integral; 1262 _M_initialize_dispatch(__first, __last, _Integral()); 1263 } 1264 #endif 1265 1266 #if __glibcxx_containers_ranges // C++ >= 23 1267 /** 1268 * @brief Construct a list from a range. 1269 * @since C++23 1270 */ 1271 template<__detail::__container_compatible_range<_Tp> _Rg> 1272 list(from_range_t, _Rg&& __rg, const _Alloc& __a = _Alloc()) 1273 : _Base(_Node_alloc_type(__a)) 1274 { 1275 auto __first = ranges::begin(__rg); 1276 const auto __last = ranges::end(__rg); 1277 for (; __first != __last; ++__first) 1278 emplace_back(*__first); 1279 } 1280 #endif 1281 1282 #if __cplusplus >= 201103L 1283 /** 1284 * No explicit dtor needed as the _Base dtor takes care of 1285 * things. The _Base dtor only erases the elements, and note 1286 * that if the elements themselves are pointers, the pointed-to 1287 * memory is not touched in any way. Managing the pointer is 1288 * the user's responsibility. 1289 */ 1290 ~list() = default; 1291 #endif 1292 1293 /** 1294 * @brief %List assignment operator. 1295 * @param __x A %list of identical element and allocator types. 1296 * 1297 * All the elements of @a __x are copied. 1298 * 1299 * Whether the allocator is copied depends on the allocator traits. 1300 */ 1301 list& 1302 operator=(const list& __x); 1303 1304 #if __cplusplus >= 201103L 1305 #pragma GCC diagnostic push 1306 #pragma GCC diagnostic ignored "-Wc++17-extensions" // if constexpr 1307 /** 1308 * @brief %List move assignment operator. 1309 * @param __x A %list of identical element and allocator types. 1310 * 1311 * The contents of @a __x are moved into this %list (without copying). 1312 * 1313 * Afterwards @a __x is a valid, but unspecified %list 1314 * 1315 * Whether the allocator is moved depends on the allocator traits. 1316 */ 1317 list& 1318 operator=(list&& __x) 1319 noexcept(_Node_alloc_traits::_S_nothrow_move()) 1320 { 1321 constexpr bool __move_storage = 1322 _Node_alloc_traits::_S_propagate_on_move_assign() 1323 || _Node_alloc_traits::_S_always_equal(); 1324 if constexpr (!__move_storage) 1325 { 1326 if (__x._M_get_Node_allocator() != this->_M_get_Node_allocator()) 1327 { 1328 // The rvalue's allocator cannot be moved, or is not equal, 1329 // so we need to individually move each element. 1330 _M_assign_dispatch(std::make_move_iterator(__x.begin()), 1331 std::make_move_iterator(__x.end()), 1332 __false_type{}); 1333 return *this; 1334 } 1335 } 1336 1337 this->clear(); 1338 this->_M_move_nodes(std::move(__x)); 1339 1340 if constexpr (_Node_alloc_traits::_S_propagate_on_move_assign()) 1341 this->_M_get_Node_allocator() 1342 = std::move(__x._M_get_Node_allocator()); 1343 1344 return *this; 1345 } 1346 #pragma GCC diagnostic pop 1347 1348 /** 1349 * @brief %List initializer list assignment operator. 1350 * @param __l An initializer_list of value_type. 1351 * 1352 * Replace the contents of the %list with copies of the elements 1353 * in the initializer_list @a __l. This is linear in l.size(). 1354 */ 1355 list& 1356 operator=(initializer_list<value_type> __l) 1357 { 1358 this->assign(__l.begin(), __l.end()); 1359 return *this; 1360 } 1361 #endif 1362 1363 #if __glibcxx_containers_ranges // C++ >= 23 1364 /** 1365 * @brief Assign a range to a list. 1366 * @since C++23 1367 */ 1368 template<__detail::__container_compatible_range<_Tp> _Rg> 1369 void 1370 assign_range(_Rg&& __rg) 1371 { 1372 static_assert(assignable_from<_Tp&, ranges::range_reference_t<_Rg>>); 1373 1374 iterator __first1 = begin(); 1375 const iterator __last1 = end(); 1376 auto __first2 = ranges::begin(__rg); 1377 const auto __last2 = ranges::end(__rg); 1378 for (; __first1 != __last1 && __first2 != __last2; 1379 ++__first1, (void)++__first2) 1380 *__first1 = *__first2; 1381 if (__first2 == __last2) 1382 erase(__first1, __last1); 1383 else 1384 insert_range(__last1, 1385 ranges::subrange(std::move(__first2), __last2)); 1386 } 1387 #endif 1388 1389 /** 1390 * @brief Assigns a given value to a %list. 1391 * @param __n Number of elements to be assigned. 1392 * @param __val Value to be assigned. 1393 * 1394 * This function fills a %list with @a __n copies of the given 1395 * value. Note that the assignment completely changes the %list 1396 * and that the resulting %list's size is the same as the number 1397 * of elements assigned. 1398 */ 1399 void 1400 assign(size_type __n, const value_type& __val) 1401 { _M_fill_assign(__n, __val); } 1402 1403 /** 1404 * @brief Assigns a range to a %list. 1405 * @param __first An input iterator. 1406 * @param __last An input iterator. 1407 * 1408 * This function fills a %list with copies of the elements in the 1409 * range [@a __first,@a __last). 1410 * 1411 * Note that the assignment completely changes the %list and 1412 * that the resulting %list's size is the same as the number of 1413 * elements assigned. 1414 */ 1415 #if __cplusplus >= 201103L 1416 template<typename _InputIterator, 1417 typename = std::_RequireInputIter<_InputIterator>> 1418 void 1419 assign(_InputIterator __first, _InputIterator __last) 1420 { _M_assign_dispatch(__first, __last, __false_type()); } 1421 #else 1422 template<typename _InputIterator> 1423 void 1424 assign(_InputIterator __first, _InputIterator __last) 1425 { 1426 // Check whether it's an integral type. If so, it's not an iterator. 1427 typedef typename std::__is_integer<_InputIterator>::__type _Integral; 1428 _M_assign_dispatch(__first, __last, _Integral()); 1429 } 1430 #endif 1431 1432 #if __cplusplus >= 201103L 1433 /** 1434 * @brief Assigns an initializer_list to a %list. 1435 * @param __l An initializer_list of value_type. 1436 * 1437 * Replace the contents of the %list with copies of the elements 1438 * in the initializer_list @a __l. This is linear in __l.size(). 1439 */ 1440 void 1441 assign(initializer_list<value_type> __l) 1442 { this->_M_assign_dispatch(__l.begin(), __l.end(), __false_type()); } 1443 #endif 1444 1445 /// Get a copy of the memory allocation object. 1446 allocator_type 1447 get_allocator() const _GLIBCXX_NOEXCEPT 1448 { return allocator_type(_Base::_M_get_Node_allocator()); } 1449 1450 // iterators 1451 /** 1452 * Returns a read/write iterator that points to the first element in the 1453 * %list. Iteration is done in ordinary element order. 1454 */ 1455 _GLIBCXX_NODISCARD 1456 iterator 1457 begin() _GLIBCXX_NOEXCEPT 1458 { return iterator(this->_M_impl._M_node._M_next); } 1459 1460 /** 1461 * Returns a read-only (constant) iterator that points to the 1462 * first element in the %list. Iteration is done in ordinary 1463 * element order. 1464 */ 1465 _GLIBCXX_NODISCARD 1466 const_iterator 1467 begin() const _GLIBCXX_NOEXCEPT 1468 { return const_iterator(this->_M_impl._M_node._M_next); } 1469 1470 /** 1471 * Returns a read/write iterator that points one past the last 1472 * element in the %list. Iteration is done in ordinary element 1473 * order. 1474 */ 1475 _GLIBCXX_NODISCARD 1476 iterator 1477 end() _GLIBCXX_NOEXCEPT 1478 { return iterator(this->_M_impl._M_node._M_base()); } 1479 1480 /** 1481 * Returns a read-only (constant) iterator that points one past 1482 * the last element in the %list. Iteration is done in ordinary 1483 * element order. 1484 */ 1485 _GLIBCXX_NODISCARD 1486 const_iterator 1487 end() const _GLIBCXX_NOEXCEPT 1488 { return const_iterator(this->_M_impl._M_node._M_base()); } 1489 1490 /** 1491 * Returns a read/write reverse iterator that points to the last 1492 * element in the %list. Iteration is done in reverse element 1493 * order. 1494 */ 1495 _GLIBCXX_NODISCARD 1496 reverse_iterator 1497 rbegin() _GLIBCXX_NOEXCEPT 1498 { return reverse_iterator(end()); } 1499 1500 /** 1501 * Returns a read-only (constant) reverse iterator that points to 1502 * the last element in the %list. Iteration is done in reverse 1503 * element order. 1504 */ 1505 _GLIBCXX_NODISCARD 1506 const_reverse_iterator 1507 rbegin() const _GLIBCXX_NOEXCEPT 1508 { return const_reverse_iterator(end()); } 1509 1510 /** 1511 * Returns a read/write reverse iterator that points to one 1512 * before the first element in the %list. Iteration is done in 1513 * reverse element order. 1514 */ 1515 _GLIBCXX_NODISCARD 1516 reverse_iterator 1517 rend() _GLIBCXX_NOEXCEPT 1518 { return reverse_iterator(begin()); } 1519 1520 /** 1521 * Returns a read-only (constant) reverse iterator that points to one 1522 * before the first element in the %list. Iteration is done in reverse 1523 * element order. 1524 */ 1525 _GLIBCXX_NODISCARD 1526 const_reverse_iterator 1527 rend() const _GLIBCXX_NOEXCEPT 1528 { return const_reverse_iterator(begin()); } 1529 1530 #if __cplusplus >= 201103L 1531 /** 1532 * Returns a read-only (constant) iterator that points to the 1533 * first element in the %list. Iteration is done in ordinary 1534 * element order. 1535 */ 1536 [[__nodiscard__]] 1537 const_iterator 1538 cbegin() const noexcept 1539 { return const_iterator(this->_M_impl._M_node._M_next); } 1540 1541 /** 1542 * Returns a read-only (constant) iterator that points one past 1543 * the last element in the %list. Iteration is done in ordinary 1544 * element order. 1545 */ 1546 [[__nodiscard__]] 1547 const_iterator 1548 cend() const noexcept 1549 { return const_iterator(this->_M_impl._M_node._M_base()); } 1550 1551 /** 1552 * Returns a read-only (constant) reverse iterator that points to 1553 * the last element in the %list. Iteration is done in reverse 1554 * element order. 1555 */ 1556 [[__nodiscard__]] 1557 const_reverse_iterator 1558 crbegin() const noexcept 1559 { return const_reverse_iterator(end()); } 1560 1561 /** 1562 * Returns a read-only (constant) reverse iterator that points to one 1563 * before the first element in the %list. Iteration is done in reverse 1564 * element order. 1565 */ 1566 [[__nodiscard__]] 1567 const_reverse_iterator 1568 crend() const noexcept 1569 { return const_reverse_iterator(begin()); } 1570 #endif 1571 1572 // [23.2.2.2] capacity 1573 /** 1574 * Returns true if the %list is empty. (Thus begin() would equal 1575 * end().) 1576 */ 1577 _GLIBCXX_NODISCARD bool 1578 empty() const _GLIBCXX_NOEXCEPT 1579 { 1580 return this->_M_impl._M_node._M_next == this->_M_impl._M_node._M_base(); 1581 } 1582 1583 /** Returns the number of elements in the %list. */ 1584 _GLIBCXX_NODISCARD 1585 size_type 1586 size() const _GLIBCXX_NOEXCEPT 1587 { 1588 #if _GLIBCXX_USE_CXX11_ABI 1589 return this->_M_get_size(); // return the stored size 1590 #else 1591 return std::distance(begin(), end()); // count the number of nodes 1592 #endif 1593 } 1594 1595 /** Returns the size() of the largest possible %list. */ 1596 _GLIBCXX_NODISCARD 1597 size_type 1598 max_size() const _GLIBCXX_NOEXCEPT 1599 { return _Node_alloc_traits::max_size(_M_get_Node_allocator()); } 1600 1601 #if __cplusplus >= 201103L 1602 /** 1603 * @brief Resizes the %list to the specified number of elements. 1604 * @param __new_size Number of elements the %list should contain. 1605 * 1606 * This function will %resize the %list to the specified number 1607 * of elements. If the number is smaller than the %list's 1608 * current size the %list is truncated, otherwise default 1609 * constructed elements are appended. 1610 */ 1611 void 1612 resize(size_type __new_size); 1613 1614 /** 1615 * @brief Resizes the %list to the specified number of elements. 1616 * @param __new_size Number of elements the %list should contain. 1617 * @param __x Data with which new elements should be populated. 1618 * 1619 * This function will %resize the %list to the specified number 1620 * of elements. If the number is smaller than the %list's 1621 * current size the %list is truncated, otherwise the %list is 1622 * extended and new elements are populated with given data. 1623 */ 1624 void 1625 resize(size_type __new_size, const value_type& __x); 1626 #else 1627 /** 1628 * @brief Resizes the %list to the specified number of elements. 1629 * @param __new_size Number of elements the %list should contain. 1630 * @param __x Data with which new elements should be populated. 1631 * 1632 * This function will %resize the %list to the specified number 1633 * of elements. If the number is smaller than the %list's 1634 * current size the %list is truncated, otherwise the %list is 1635 * extended and new elements are populated with given data. 1636 */ 1637 void 1638 resize(size_type __new_size, value_type __x = value_type()); 1639 #endif 1640 1641 // element access 1642 /** 1643 * Returns a read/write reference to the data at the first 1644 * element of the %list. 1645 */ 1646 _GLIBCXX_NODISCARD 1647 reference 1648 front() _GLIBCXX_NOEXCEPT 1649 { 1650 __glibcxx_requires_nonempty(); 1651 return *begin(); 1652 } 1653 1654 /** 1655 * Returns a read-only (constant) reference to the data at the first 1656 * element of the %list. 1657 */ 1658 _GLIBCXX_NODISCARD 1659 const_reference 1660 front() const _GLIBCXX_NOEXCEPT 1661 { 1662 __glibcxx_requires_nonempty(); 1663 return *begin(); 1664 } 1665 1666 /** 1667 * Returns a read/write reference to the data at the last element 1668 * of the %list. 1669 */ 1670 _GLIBCXX_NODISCARD 1671 reference 1672 back() _GLIBCXX_NOEXCEPT 1673 { 1674 __glibcxx_requires_nonempty(); 1675 iterator __tmp = end(); 1676 --__tmp; 1677 return *__tmp; 1678 } 1679 1680 /** 1681 * Returns a read-only (constant) reference to the data at the last 1682 * element of the %list. 1683 */ 1684 _GLIBCXX_NODISCARD 1685 const_reference 1686 back() const _GLIBCXX_NOEXCEPT 1687 { 1688 __glibcxx_requires_nonempty(); 1689 const_iterator __tmp = end(); 1690 --__tmp; 1691 return *__tmp; 1692 } 1693 1694 // [23.2.2.3] modifiers 1695 /** 1696 * @brief Add data to the front of the %list. 1697 * @param __x Data to be added. 1698 * 1699 * This is a typical stack operation. The function creates an 1700 * element at the front of the %list and assigns the given data 1701 * to it. Due to the nature of a %list this operation can be 1702 * done in constant time, and does not invalidate iterators and 1703 * references. 1704 */ 1705 void 1706 push_front(const value_type& __x) 1707 { this->_M_insert(begin(), __x); } 1708 1709 #if __cplusplus >= 201103L 1710 void 1711 push_front(value_type&& __x) 1712 { this->_M_insert(begin(), std::move(__x)); } 1713 1714 template<typename... _Args> 1715 #if __cplusplus > 201402L 1716 reference 1717 #else 1718 void 1719 #endif 1720 emplace_front(_Args&&... __args) 1721 { 1722 this->_M_insert(begin(), std::forward<_Args>(__args)...); 1723 #if __cplusplus > 201402L 1724 return front(); 1725 #endif 1726 } 1727 #endif 1728 1729 #if __glibcxx_containers_ranges // C++ >= 23 1730 /** 1731 * @brief Insert a range at the beginning of a list. 1732 * @param __rg An input range of elements that can be converted to 1733 * the list's value type. 1734 * 1735 * Inserts the elements of `__rg` at the beginning of the list. 1736 * No iterators to existing elements are invalidated by this function. 1737 * If the insertion fails due to an exception, no elements will be added 1738 * and so the list will be unchanged. 1739 * 1740 * @since C++23 1741 */ 1742 template<__detail::__container_compatible_range<_Tp> _Rg> 1743 void 1744 prepend_range(_Rg&& __rg) 1745 { 1746 list __tmp(from_range, std::forward<_Rg>(__rg), get_allocator()); 1747 if (!__tmp.empty()) 1748 splice(begin(), __tmp); 1749 } 1750 1751 /** 1752 * @brief Insert a range at the end of a list. 1753 * @param __rg An input range of elements that can be converted to 1754 * the list's value type. 1755 * 1756 * Inserts the elements of `__rg` at the end of the list. 1757 * No iterators to existing elements are invalidated by this function. 1758 * If the insertion fails due to an exception, no elements will be added 1759 * and so the list will be unchanged. 1760 * 1761 * @since C++23 1762 */ 1763 template<__detail::__container_compatible_range<_Tp> _Rg> 1764 void 1765 append_range(_Rg&& __rg) 1766 { 1767 list __tmp(from_range, std::forward<_Rg>(__rg), get_allocator()); 1768 if (!__tmp.empty()) 1769 splice(end(), __tmp); 1770 } 1771 #endif 1772 1773 /** 1774 * @brief Removes first element. 1775 * 1776 * This is a typical stack operation. It shrinks the %list by 1777 * one. Due to the nature of a %list this operation can be done 1778 * in constant time, and only invalidates iterators/references to 1779 * the element being removed. 1780 * 1781 * Note that no data is returned, and if the first element's data 1782 * is needed, it should be retrieved before pop_front() is 1783 * called. 1784 */ 1785 void 1786 pop_front() _GLIBCXX_NOEXCEPT 1787 { 1788 __glibcxx_requires_nonempty(); 1789 this->_M_erase(begin()); 1790 } 1791 1792 /** 1793 * @brief Add data to the end of the %list. 1794 * @param __x Data to be added. 1795 * 1796 * This is a typical stack operation. The function creates an 1797 * element at the end of the %list and assigns the given data to 1798 * it. Due to the nature of a %list this operation can be done 1799 * in constant time, and does not invalidate iterators and 1800 * references. 1801 */ 1802 void 1803 push_back(const value_type& __x) 1804 { this->_M_insert(end(), __x); } 1805 1806 #if __cplusplus >= 201103L 1807 void 1808 push_back(value_type&& __x) 1809 { this->_M_insert(end(), std::move(__x)); } 1810 1811 template<typename... _Args> 1812 #if __cplusplus > 201402L 1813 reference 1814 #else 1815 void 1816 #endif 1817 emplace_back(_Args&&... __args) 1818 { 1819 this->_M_insert(end(), std::forward<_Args>(__args)...); 1820 #if __cplusplus > 201402L 1821 return back(); 1822 #endif 1823 } 1824 #endif 1825 1826 /** 1827 * @brief Removes last element. 1828 * 1829 * This is a typical stack operation. It shrinks the %list by 1830 * one. Due to the nature of a %list this operation can be done 1831 * in constant time, and only invalidates iterators/references to 1832 * the element being removed. 1833 * 1834 * Note that no data is returned, and if the last element's data 1835 * is needed, it should be retrieved before pop_back() is called. 1836 */ 1837 void 1838 pop_back() _GLIBCXX_NOEXCEPT 1839 { 1840 __glibcxx_requires_nonempty(); 1841 this->_M_erase(iterator(this->_M_impl._M_node._M_prev)); 1842 } 1843 1844 #if __cplusplus >= 201103L 1845 /** 1846 * @brief Constructs object in %list before specified iterator. 1847 * @param __position A const_iterator into the %list. 1848 * @param __args Arguments. 1849 * @return An iterator that points to the inserted data. 1850 * 1851 * This function will insert an object of type T constructed 1852 * with T(std::forward<Args>(args)...) before the specified 1853 * location. Due to the nature of a %list this operation can 1854 * be done in constant time, and does not invalidate iterators 1855 * and references. 1856 */ 1857 template<typename... _Args> 1858 iterator 1859 emplace(const_iterator __position, _Args&&... __args); 1860 #endif 1861 1862 /** 1863 * @brief Inserts given value into %list before specified iterator. 1864 * @param __position An iterator into the %list. 1865 * @param __x Data to be inserted. 1866 * @return An iterator that points to the inserted data. 1867 * 1868 * This function will insert a copy of the given value before 1869 * the specified location. Due to the nature of a %list this 1870 * operation can be done in constant time, and does not 1871 * invalidate iterators and references. 1872 * 1873 * @{ 1874 */ 1875 #if __cplusplus >= 201103L 1876 iterator 1877 insert(const_iterator __position, const value_type& __x); 1878 1879 iterator 1880 insert(const_iterator __position, value_type&& __x) 1881 { return emplace(__position, std::move(__x)); } 1882 #else 1883 iterator 1884 insert(iterator __position, const value_type& __x); 1885 #endif 1886 /// @} 1887 1888 #if __cplusplus >= 201103L 1889 /** 1890 * @brief Inserts the contents of an initializer_list into %list 1891 * before specified const_iterator. 1892 * @param __p A const_iterator into the %list. 1893 * @param __l An initializer_list of value_type. 1894 * @return An iterator pointing to the first element inserted 1895 * (or `__p`). 1896 * 1897 * This function will insert copies of the data in the 1898 * initializer_list `__l` into the %list before the location 1899 * specified by `__p`. 1900 * 1901 * This operation is linear in the number of elements inserted and 1902 * does not invalidate iterators and references. 1903 */ 1904 iterator 1905 insert(const_iterator __p, initializer_list<value_type> __l) 1906 { return this->insert(__p, __l.begin(), __l.end()); } 1907 #endif 1908 1909 /** 1910 * @brief Inserts a number of copies of given data into the %list. 1911 * @param __position An iterator into the %list. 1912 * @param __n Number of elements to be inserted. 1913 * @param __x Data to be inserted. 1914 * @return Since C++11, an iterator pointing to the first element 1915 * inserted (or `__position`). In C++98 this returns void. 1916 * 1917 * This function will insert a specified number of copies of the 1918 * given data before the location specified by `__position`. 1919 * 1920 * This operation is linear in the number of elements inserted and 1921 * does not invalidate iterators and references. 1922 */ 1923 #if __cplusplus >= 201103L 1924 iterator 1925 insert(const_iterator __position, size_type __n, const value_type& __x); 1926 #else 1927 void 1928 insert(iterator __position, size_type __n, const value_type& __x) 1929 { 1930 list __tmp(__n, __x, get_allocator()); 1931 splice(__position, __tmp); 1932 } 1933 #endif 1934 1935 /** 1936 * @brief Inserts a range into the %list. 1937 * @param __position An iterator into the %list. 1938 * @param __first An input iterator. 1939 * @param __last An input iterator. 1940 * @return Since C++11, an iterator pointing to the first element 1941 * inserted (or `__position`). In C++98 this returns void. 1942 * 1943 * This function will insert copies of the data in the range 1944 * `[__first,__last)` into the %list before the location specified by 1945 * `__position`. 1946 * 1947 * This operation is linear in the number of elements inserted and 1948 * does not invalidate iterators and references. 1949 */ 1950 #if __cplusplus >= 201103L 1951 template<typename _InputIterator, 1952 typename = std::_RequireInputIter<_InputIterator>> 1953 iterator 1954 insert(const_iterator __position, _InputIterator __first, 1955 _InputIterator __last); 1956 #else 1957 template<typename _InputIterator> 1958 void 1959 insert(iterator __position, _InputIterator __first, 1960 _InputIterator __last) 1961 { 1962 list __tmp(__first, __last, get_allocator()); 1963 splice(__position, __tmp); 1964 } 1965 #endif 1966 1967 #if __glibcxx_containers_ranges // C++ >= 23 1968 /** 1969 * @brief Insert a range into a list. 1970 * @param __position An iterator. 1971 * @param __rg An input range of elements that can be converted to 1972 * the list's value type. 1973 * @return An iterator pointing to the first element inserted, 1974 * or `__position` if the range is empty. 1975 * 1976 * Inserts the elements of `__rg` before `__position`. 1977 * No iterators to existing elements are invalidated by this function. 1978 * If the insertion fails due to an exception, no elements will be added 1979 * and so the list will be unchanged. 1980 * 1981 * @since C++23 1982 */ 1983 template<__detail::__container_compatible_range<_Tp> _Rg> 1984 iterator 1985 insert_range(const_iterator __position, _Rg&& __rg) 1986 { 1987 list __tmp(from_range, std::forward<_Rg>(__rg), get_allocator()); 1988 if (!__tmp.empty()) 1989 { 1990 auto __it = __tmp.begin(); 1991 splice(__position, __tmp); 1992 return __it; 1993 } 1994 return __position._M_const_cast(); 1995 } 1996 #endif 1997 1998 /** 1999 * @brief Remove element at given position. 2000 * @param __position Iterator pointing to element to be erased. 2001 * @return An iterator pointing to the next element (or end()). 2002 * 2003 * This function will erase the element at the given position and thus 2004 * shorten the %list by one. 2005 * 2006 * Due to the nature of a %list this operation can be done in 2007 * constant time, and only invalidates iterators/references to 2008 * the element being removed. The user is also cautioned that 2009 * this function only erases the element, and that if the element 2010 * is itself a pointer, the pointed-to memory is not touched in 2011 * any way. Managing the pointer is the user's responsibility. 2012 */ 2013 iterator 2014 #if __cplusplus >= 201103L 2015 erase(const_iterator __position) noexcept; 2016 #else 2017 erase(iterator __position); 2018 #endif 2019 2020 /** 2021 * @brief Remove a range of elements. 2022 * @param __first Iterator pointing to the first element to be erased. 2023 * @param __last Iterator pointing to one past the last element to be 2024 * erased. 2025 * @return An iterator pointing to the element pointed to by @a last 2026 * prior to erasing (or end()). 2027 * 2028 * This function will erase the elements in the range @a 2029 * [first,last) and shorten the %list accordingly. 2030 * 2031 * This operation is linear time in the size of the range and only 2032 * invalidates iterators/references to the element being removed. 2033 * The user is also cautioned that this function only erases the 2034 * elements, and that if the elements themselves are pointers, the 2035 * pointed-to memory is not touched in any way. Managing the pointer 2036 * is the user's responsibility. 2037 */ 2038 iterator 2039 #if __cplusplus >= 201103L 2040 erase(const_iterator __first, const_iterator __last) noexcept 2041 #else 2042 erase(iterator __first, iterator __last) 2043 #endif 2044 { 2045 while (__first != __last) 2046 __first = erase(__first); 2047 return __last._M_const_cast(); 2048 } 2049 2050 /** 2051 * @brief Swaps data with another %list. 2052 * @param __x A %list of the same element and allocator types. 2053 * 2054 * This exchanges the elements between two lists in constant 2055 * time. Note that the global std::swap() function is 2056 * specialized such that std::swap(l1,l2) will feed to this 2057 * function. 2058 * 2059 * Whether the allocators are swapped depends on the allocator traits. 2060 */ 2061 void 2062 swap(list& __x) _GLIBCXX_NOEXCEPT 2063 { 2064 _Node_traits::_Node_base::swap(this->_M_impl._M_node, 2065 __x._M_impl._M_node); 2066 2067 size_t __xsize = __x._M_get_size(); 2068 __x._M_set_size(this->_M_get_size()); 2069 this->_M_set_size(__xsize); 2070 2071 _Node_alloc_traits::_S_on_swap(this->_M_get_Node_allocator(), 2072 __x._M_get_Node_allocator()); 2073 } 2074 2075 /** 2076 * Erases all the elements. Note that this function only erases 2077 * the elements, and that if the elements themselves are 2078 * pointers, the pointed-to memory is not touched in any way. 2079 * Managing the pointer is the user's responsibility. 2080 */ 2081 void 2082 clear() _GLIBCXX_NOEXCEPT 2083 { 2084 _Base::_M_clear(); 2085 _Base::_M_init(); 2086 } 2087 2088 // [23.2.2.4] list operations 2089 /** 2090 * @brief Insert contents of another %list. 2091 * @param __position Iterator referencing the element to insert before. 2092 * @param __x Source list. 2093 * 2094 * The elements of @a __x are inserted in constant time in front of 2095 * the element referenced by @a __position. @a __x becomes an empty 2096 * list. 2097 * 2098 * Requires this != @a __x. 2099 */ 2100 void 2101 #if __cplusplus >= 201103L 2102 splice(const_iterator __position, list&& __x) noexcept 2103 #else 2104 splice(iterator __position, list& __x) 2105 #endif 2106 { 2107 if (!__x.empty()) 2108 { 2109 _M_check_equal_allocators(__x); 2110 2111 this->_M_transfer(__position._M_const_cast(), 2112 __x.begin(), __x.end()); 2113 2114 this->_M_inc_size(__x._M_get_size()); 2115 __x._M_set_size(0); 2116 } 2117 } 2118 2119 #if __cplusplus >= 201103L 2120 void 2121 splice(const_iterator __position, list& __x) noexcept 2122 { splice(__position, std::move(__x)); } 2123 #endif 2124 2125 /** 2126 * @brief Insert element from another %list. 2127 * @param __position Iterator referencing the element to insert before. 2128 * @param __x Source list. 2129 * @param __i Iterator referencing the element to move. 2130 * 2131 * Removes the element in list @a __x referenced by @a __i and 2132 * inserts it into the current list before @a __position. 2133 * 2134 * @{ 2135 */ 2136 #if __cplusplus >= 201103L 2137 void 2138 splice(const_iterator __position, list&& __x, const_iterator __i) noexcept 2139 #else 2140 void 2141 splice(iterator __position, list& __x, iterator __i) 2142 #endif 2143 { 2144 iterator __j = __i._M_const_cast(); 2145 ++__j; 2146 if (__position == __i || __position == __j) 2147 return; 2148 2149 if (this != std::__addressof(__x)) 2150 _M_check_equal_allocators(__x); 2151 2152 this->_M_transfer(__position._M_const_cast(), 2153 __i._M_const_cast(), __j); 2154 2155 this->_M_inc_size(1); 2156 __x._M_dec_size(1); 2157 } 2158 2159 #if __cplusplus >= 201103L 2160 void 2161 splice(const_iterator __position, list& __x, const_iterator __i) noexcept 2162 { splice(__position, std::move(__x), __i); } 2163 #endif 2164 /// @} 2165 2166 /** 2167 * @brief Insert range from another %list. 2168 * @param __position Iterator referencing the element to insert before. 2169 * @param __x Source list. 2170 * @param __first Iterator referencing the start of range in x. 2171 * @param __last Iterator referencing the end of range in x. 2172 * 2173 * Removes elements in the range [__first,__last) and inserts them 2174 * before @a __position in constant time. 2175 * 2176 * Undefined if @a __position is in [__first,__last). 2177 */ 2178 #if __cplusplus >= 201103L 2179 void 2180 splice(const_iterator __position, list&& __x, const_iterator __first, 2181 const_iterator __last) noexcept 2182 #else 2183 void 2184 splice(iterator __position, list& __x, iterator __first, 2185 iterator __last) 2186 #endif 2187 { 2188 if (__first != __last) 2189 { 2190 if (this != std::__addressof(__x)) 2191 _M_check_equal_allocators(__x); 2192 2193 #if _GLIBCXX_USE_CXX11_ABI 2194 size_t __n = std::distance(__first, __last); 2195 this->_M_inc_size(__n); 2196 __x._M_dec_size(__n); 2197 #endif 2198 2199 this->_M_transfer(__position._M_const_cast(), 2200 __first._M_const_cast(), 2201 __last._M_const_cast()); 2202 } 2203 } 2204 2205 #if __cplusplus >= 201103L 2206 /** 2207 * @brief Insert range from another %list. 2208 * @param __position Const_iterator referencing the element to 2209 * insert before. 2210 * @param __x Source list. 2211 * @param __first Const_iterator referencing the start of range in x. 2212 * @param __last Const_iterator referencing the end of range in x. 2213 * 2214 * Removes elements in the range [__first,__last) and inserts them 2215 * before @a __position in constant time. 2216 * 2217 * Undefined if @a __position is in [__first,__last). 2218 */ 2219 void 2220 splice(const_iterator __position, list& __x, const_iterator __first, 2221 const_iterator __last) noexcept 2222 { splice(__position, std::move(__x), __first, __last); } 2223 #endif 2224 2225 private: 2226 #ifdef __glibcxx_list_remove_return_type // C++ >= 20 && HOSTED 2227 typedef size_type __remove_return_type; 2228 # define _GLIBCXX_LIST_REMOVE_RETURN_TYPE_TAG \ 2229 __attribute__((__abi_tag__("__cxx20"))) 2230 #else 2231 typedef void __remove_return_type; 2232 # define _GLIBCXX_LIST_REMOVE_RETURN_TYPE_TAG 2233 #endif 2234 public: 2235 2236 /** 2237 * @brief Remove all elements equal to value. 2238 * @param __value The value to remove. 2239 * 2240 * Removes every element in the list equal to @a value. 2241 * Remaining elements stay in list order. Note that this 2242 * function only erases the elements, and that if the elements 2243 * themselves are pointers, the pointed-to memory is not 2244 * touched in any way. Managing the pointer is the user's 2245 * responsibility. 2246 */ 2247 _GLIBCXX_LIST_REMOVE_RETURN_TYPE_TAG 2248 __remove_return_type 2249 remove(const _Tp& __value); 2250 2251 /** 2252 * @brief Remove all elements satisfying a predicate. 2253 * @tparam _Predicate Unary predicate function or object. 2254 * 2255 * Removes every element in the list for which the predicate 2256 * returns true. Remaining elements stay in list order. Note 2257 * that this function only erases the elements, and that if the 2258 * elements themselves are pointers, the pointed-to memory is 2259 * not touched in any way. Managing the pointer is the user's 2260 * responsibility. 2261 */ 2262 template<typename _Predicate> 2263 __remove_return_type 2264 remove_if(_Predicate); 2265 2266 /** 2267 * @brief Remove consecutive duplicate elements. 2268 * 2269 * For each consecutive set of elements with the same value, 2270 * remove all but the first one. Remaining elements stay in 2271 * list order. Note that this function only erases the 2272 * elements, and that if the elements themselves are pointers, 2273 * the pointed-to memory is not touched in any way. Managing 2274 * the pointer is the user's responsibility. 2275 */ 2276 _GLIBCXX_LIST_REMOVE_RETURN_TYPE_TAG 2277 __remove_return_type 2278 unique(); 2279 2280 /** 2281 * @brief Remove consecutive elements satisfying a predicate. 2282 * @tparam _BinaryPredicate Binary predicate function or object. 2283 * 2284 * For each consecutive set of elements [first,last) that 2285 * satisfy predicate(first,i) where i is an iterator in 2286 * [first,last), remove all but the first one. Remaining 2287 * elements stay in list order. Note that this function only 2288 * erases the elements, and that if the elements themselves are 2289 * pointers, the pointed-to memory is not touched in any way. 2290 * Managing the pointer is the user's responsibility. 2291 */ 2292 template<typename _BinaryPredicate> 2293 __remove_return_type 2294 unique(_BinaryPredicate); 2295 2296 #undef _GLIBCXX_LIST_REMOVE_RETURN_TYPE_TAG 2297 2298 /** 2299 * @brief Merge sorted lists. 2300 * @param __x Sorted list to merge. 2301 * 2302 * Assumes that both @a __x and this list are sorted according to 2303 * operator<(). Merges elements of @a __x into this list in 2304 * sorted order, leaving @a __x empty when complete. Elements in 2305 * this list precede elements in @a __x that are equal. 2306 */ 2307 #if __cplusplus >= 201103L 2308 void 2309 merge(list&& __x); 2310 2311 void 2312 merge(list& __x) 2313 { merge(std::move(__x)); } 2314 #else 2315 void 2316 merge(list& __x); 2317 #endif 2318 2319 /** 2320 * @brief Merge sorted lists according to comparison function. 2321 * @tparam _StrictWeakOrdering Comparison function defining 2322 * sort order. 2323 * @param __x Sorted list to merge. 2324 * @param __comp Comparison functor. 2325 * 2326 * Assumes that both @a __x and this list are sorted according to 2327 * StrictWeakOrdering. Merges elements of @a __x into this list 2328 * in sorted order, leaving @a __x empty when complete. Elements 2329 * in this list precede elements in @a __x that are equivalent 2330 * according to StrictWeakOrdering(). 2331 */ 2332 #if __cplusplus >= 201103L 2333 template<typename _StrictWeakOrdering> 2334 void 2335 merge(list&& __x, _StrictWeakOrdering __comp); 2336 2337 template<typename _StrictWeakOrdering> 2338 void 2339 merge(list& __x, _StrictWeakOrdering __comp) 2340 { merge(std::move(__x), __comp); } 2341 #else 2342 template<typename _StrictWeakOrdering> 2343 void 2344 merge(list& __x, _StrictWeakOrdering __comp); 2345 #endif 2346 2347 /** 2348 * @brief Reverse the elements in list. 2349 * 2350 * Reverse the order of elements in the list in linear time. 2351 */ 2352 void 2353 reverse() _GLIBCXX_NOEXCEPT 2354 { this->_M_impl._M_node._M_reverse(); } 2355 2356 /** 2357 * @brief Sort the elements. 2358 * 2359 * Sorts the elements of this list in NlogN time. Equivalent 2360 * elements remain in list order. 2361 */ 2362 void 2363 sort(); 2364 2365 /** 2366 * @brief Sort the elements according to comparison function. 2367 * 2368 * Sorts the elements of this list in NlogN time. Equivalent 2369 * elements remain in list order. 2370 */ 2371 template<typename _StrictWeakOrdering> 2372 void 2373 sort(_StrictWeakOrdering); 2374 2375 protected: 2376 // Internal constructor functions follow. 2377 2378 // Called by the range constructor to implement [23.1.1]/9 2379 2380 // _GLIBCXX_RESOLVE_LIB_DEFECTS 2381 // 438. Ambiguity in the "do the right thing" clause 2382 template<typename _Integer> 2383 void 2384 _M_initialize_dispatch(_Integer __n, _Integer __x, __true_type) 2385 { _M_fill_initialize(static_cast<size_type>(__n), __x); } 2386 2387 // Called by the range constructor to implement [23.1.1]/9 2388 template<typename _InputIterator> 2389 void 2390 _M_initialize_dispatch(_InputIterator __first, _InputIterator __last, 2391 __false_type) 2392 { 2393 bool __notempty = __first != __last; 2394 for (; __first != __last; ++__first) 2395 #if __cplusplus >= 201103L 2396 emplace_back(*__first); 2397 #else 2398 push_back(*__first); 2399 #endif 2400 if (__notempty) 2401 { 2402 if (begin() == end()) 2403 __builtin_unreachable(); 2404 } 2405 } 2406 2407 // Called by list(n,v,a), and the range constructor when it turns out 2408 // to be the same thing. 2409 void 2410 _M_fill_initialize(size_type __n, const value_type& __x) 2411 { 2412 for (; __n; --__n) 2413 push_back(__x); 2414 } 2415 2416 #if __cplusplus >= 201103L 2417 // Called by list(n). 2418 void 2419 _M_default_initialize(size_type __n) 2420 { 2421 for (; __n; --__n) 2422 emplace_back(); 2423 } 2424 2425 // Called by resize(sz). 2426 void 2427 _M_default_append(size_type __n); 2428 #endif 2429 2430 // Internal assign functions follow. 2431 2432 // Called by the range assign to implement [23.1.1]/9 2433 2434 // _GLIBCXX_RESOLVE_LIB_DEFECTS 2435 // 438. Ambiguity in the "do the right thing" clause 2436 template<typename _Integer> 2437 void 2438 _M_assign_dispatch(_Integer __n, _Integer __val, __true_type) 2439 { _M_fill_assign(__n, __val); } 2440 2441 // Called by the range assign to implement [23.1.1]/9 2442 template<typename _InputIterator> 2443 void 2444 _M_assign_dispatch(_InputIterator __first, _InputIterator __last, 2445 __false_type); 2446 2447 // Called by assign(n,t), and the range assign when it turns out 2448 // to be the same thing. 2449 void 2450 _M_fill_assign(size_type __n, const value_type& __val); 2451 2452 2453 // Moves the elements from [first,last) before position. 2454 void 2455 _M_transfer(iterator __position, iterator __first, iterator __last) 2456 { __position._M_node->_M_transfer(__first._M_node, __last._M_node); } 2457 2458 // Inserts new element at position given and with value given. 2459 #if __cplusplus < 201103L 2460 void 2461 _M_insert(iterator __position, const value_type& __x) 2462 { 2463 _Node_ptr __tmp = _M_create_node(__x); 2464 __tmp->_M_hook(__position._M_node); 2465 this->_M_inc_size(1); 2466 } 2467 #else 2468 template<typename... _Args> 2469 void 2470 _M_insert(iterator __position, _Args&&... __args) 2471 { 2472 _Node_ptr __tmp = _M_create_node(std::forward<_Args>(__args)...); 2473 __tmp->_M_hook(__position._M_node); 2474 this->_M_inc_size(1); 2475 } 2476 #endif 2477 2478 // Erases element at position given. 2479 void 2480 _M_erase(iterator __position) _GLIBCXX_NOEXCEPT 2481 { 2482 typedef typename _Node_traits::_Node _Node; 2483 this->_M_dec_size(1); 2484 __position._M_node->_M_unhook(); 2485 _Node& __n = static_cast<_Node&>(*__position._M_node); 2486 this->_M_destroy_node(__n._M_node_ptr()); 2487 } 2488 2489 // To implement the splice (and merge) bits of N1599. 2490 void 2491 _M_check_equal_allocators(const list& __x) _GLIBCXX_NOEXCEPT 2492 { 2493 if (_M_get_Node_allocator() != __x._M_get_Node_allocator()) 2494 __builtin_abort(); 2495 } 2496 2497 // Used to implement resize. 2498 const_iterator 2499 _M_resize_pos(size_type& __new_size) const; 2500 2501 #if __cplusplus >= 201103L && ! _GLIBCXX_INLINE_VERSION 2502 // XXX GLIBCXX_ABI Deprecated 2503 // These are unused and only kept so that explicit instantiations will 2504 // continue to define the symbols. 2505 void 2506 _M_move_assign(list&& __x, true_type) noexcept 2507 { 2508 this->clear(); 2509 this->_M_move_nodes(std::move(__x)); 2510 std::__alloc_on_move(this->_M_get_Node_allocator(), 2511 __x._M_get_Node_allocator()); 2512 } 2513 2514 void 2515 _M_move_assign(list&& __x, false_type) 2516 { 2517 if (__x._M_get_Node_allocator() == this->_M_get_Node_allocator()) 2518 _M_move_assign(std::move(__x), true_type{}); 2519 else 2520 // The rvalue's allocator cannot be moved, or is not equal, 2521 // so we need to individually move each element. 2522 _M_assign_dispatch(std::make_move_iterator(__x.begin()), 2523 std::make_move_iterator(__x.end()), 2524 __false_type{}); 2525 } 2526 #endif 2527 2528 #if _GLIBCXX_USE_CXX11_ABI 2529 // Update _M_size members after merging (some of) __src into __dest. 2530 struct _Finalize_merge 2531 { 2532 explicit 2533 _Finalize_merge(list& __dest, list& __src, const iterator& __src_next) 2534 : _M_dest(__dest), _M_src(__src), _M_next(__src_next) 2535 { } 2536 2537 ~_Finalize_merge() 2538 { 2539 // For the common case, _M_next == _M_sec.end() and the std::distance 2540 // call is fast. But if any *iter1 < *iter2 comparison throws then we 2541 // have to count how many elements remain in _M_src. 2542 const size_t __num_unmerged = std::distance(_M_next, _M_src.end()); 2543 const size_t __orig_size = _M_src._M_get_size(); 2544 _M_dest._M_inc_size(__orig_size - __num_unmerged); 2545 _M_src._M_set_size(__num_unmerged); 2546 } 2547 2548 list& _M_dest; 2549 list& _M_src; 2550 const iterator& _M_next; 2551 2552 #if __cplusplus >= 201103L 2553 _Finalize_merge(const _Finalize_merge&) = delete; 2554 #endif 2555 }; 2556 #else 2557 struct _Finalize_merge 2558 { explicit _Finalize_merge(list&, list&, const iterator&) { } }; 2559 #endif 2560 2561 #if !_GLIBCXX_INLINE_VERSION 2562 // XXX GLIBCXX_ABI Deprecated 2563 // These members are unused by std::list now, but we keep them here 2564 // so that an explicit instantiation of std::list will define them. 2565 // This ensures that any objects or libraries compiled against old 2566 // versions of GCC will still be able to use the symbols. 2567 2568 #if _GLIBCXX_USE_CXX11_ABI 2569 static size_t 2570 _S_distance(const_iterator __first, const_iterator __last) 2571 { return std::distance(__first, __last); } 2572 2573 size_t 2574 _M_node_count() const 2575 { return this->_M_get_size(); } 2576 #else 2577 static size_t 2578 _S_distance(const_iterator, const_iterator) 2579 { return 0; } 2580 2581 size_t 2582 _M_node_count() const 2583 { return std::distance(begin(), end()); } 2584 #endif 2585 #endif // ! INLINE_VERSION 2586 }; 2587 2588 #if __cpp_deduction_guides >= 201606 2589 template<typename _InputIterator, typename _ValT 2590 = typename iterator_traits<_InputIterator>::value_type, 2591 typename _Allocator = allocator<_ValT>, 2592 typename = _RequireInputIter<_InputIterator>, 2593 typename = _RequireAllocator<_Allocator>> 2594 list(_InputIterator, _InputIterator, _Allocator = _Allocator()) 2595 -> list<_ValT, _Allocator>; 2596 2597 #if __glibcxx_containers_ranges // C++ >= 23 2598 template<ranges::input_range _Rg, 2599 typename _Allocator = allocator<ranges::range_value_t<_Rg>>> 2600 list(from_range_t, _Rg&&, _Allocator = _Allocator()) 2601 -> list<ranges::range_value_t<_Rg>, _Allocator>; 2602 #endif 2603 #endif 2604 2605 _GLIBCXX_END_NAMESPACE_CXX11 2606 2607 /** 2608 * @brief List equality comparison. 2609 * @param __x A %list. 2610 * @param __y A %list of the same type as @a __x. 2611 * @return True iff the size and elements of the lists are equal. 2612 * 2613 * This is an equivalence relation. It is linear in the size of 2614 * the lists. Lists are considered equivalent if their sizes are 2615 * equal, and if corresponding elements compare equal. 2616 */ 2617 template<typename _Tp, typename _Alloc> 2618 _GLIBCXX_NODISCARD 2619 inline bool 2620 operator==(const list<_Tp, _Alloc>& __x, const list<_Tp, _Alloc>& __y) 2621 { 2622 #if _GLIBCXX_USE_CXX11_ABI 2623 if (__x.size() != __y.size()) 2624 return false; 2625 #endif 2626 2627 typedef typename list<_Tp, _Alloc>::const_iterator const_iterator; 2628 const_iterator __end1 = __x.end(); 2629 const_iterator __end2 = __y.end(); 2630 2631 const_iterator __i1 = __x.begin(); 2632 const_iterator __i2 = __y.begin(); 2633 while (__i1 != __end1 && __i2 != __end2 && *__i1 == *__i2) 2634 { 2635 ++__i1; 2636 ++__i2; 2637 } 2638 return __i1 == __end1 && __i2 == __end2; 2639 } 2640 2641 #if __cpp_lib_three_way_comparison 2642 /** 2643 * @brief List ordering relation. 2644 * @param __x A `list`. 2645 * @param __y A `list` of the same type as `__x`. 2646 * @return A value indicating whether `__x` is less than, equal to, 2647 * greater than, or incomparable with `__y`. 2648 * 2649 * See `std::lexicographical_compare_three_way()` for how the determination 2650 * is made. This operator is used to synthesize relational operators like 2651 * `<` and `>=` etc. 2652 */ 2653 template<typename _Tp, typename _Alloc> 2654 [[nodiscard]] 2655 inline __detail::__synth3way_t<_Tp> 2656 operator<=>(const list<_Tp, _Alloc>& __x, const list<_Tp, _Alloc>& __y) 2657 { 2658 return std::lexicographical_compare_three_way(__x.begin(), __x.end(), 2659 __y.begin(), __y.end(), 2660 __detail::__synth3way); 2661 } 2662 #else 2663 /** 2664 * @brief List ordering relation. 2665 * @param __x A %list. 2666 * @param __y A %list of the same type as @a __x. 2667 * @return True iff @a __x is lexicographically less than @a __y. 2668 * 2669 * This is a total ordering relation. It is linear in the size of the 2670 * lists. The elements must be comparable with @c <. 2671 * 2672 * See std::lexicographical_compare() for how the determination is made. 2673 */ 2674 template<typename _Tp, typename _Alloc> 2675 _GLIBCXX_NODISCARD 2676 inline bool 2677 operator<(const list<_Tp, _Alloc>& __x, const list<_Tp, _Alloc>& __y) 2678 { return std::lexicographical_compare(__x.begin(), __x.end(), 2679 __y.begin(), __y.end()); } 2680 2681 /// Based on operator== 2682 template<typename _Tp, typename _Alloc> 2683 _GLIBCXX_NODISCARD 2684 inline bool 2685 operator!=(const list<_Tp, _Alloc>& __x, const list<_Tp, _Alloc>& __y) 2686 { return !(__x == __y); } 2687 2688 /// Based on operator< 2689 template<typename _Tp, typename _Alloc> 2690 _GLIBCXX_NODISCARD 2691 inline bool 2692 operator>(const list<_Tp, _Alloc>& __x, const list<_Tp, _Alloc>& __y) 2693 { return __y < __x; } 2694 2695 /// Based on operator< 2696 template<typename _Tp, typename _Alloc> 2697 _GLIBCXX_NODISCARD 2698 inline bool 2699 operator<=(const list<_Tp, _Alloc>& __x, const list<_Tp, _Alloc>& __y) 2700 { return !(__y < __x); } 2701 2702 /// Based on operator< 2703 template<typename _Tp, typename _Alloc> 2704 _GLIBCXX_NODISCARD 2705 inline bool 2706 operator>=(const list<_Tp, _Alloc>& __x, const list<_Tp, _Alloc>& __y) 2707 { return !(__x < __y); } 2708 #endif // three-way comparison 2709 2710 /// See std::list::swap(). 2711 template<typename _Tp, typename _Alloc> 2712 inline void 2713 swap(list<_Tp, _Alloc>& __x, list<_Tp, _Alloc>& __y) 2714 _GLIBCXX_NOEXCEPT_IF(noexcept(__x.swap(__y))) 2715 { __x.swap(__y); } 2716 2717 _GLIBCXX_END_NAMESPACE_CONTAINER 2718 2719 #if _GLIBCXX_USE_CXX11_ABI 2720 2721 // Detect when distance is used to compute the size of the whole list. 2722 template<typename _Tp> 2723 inline ptrdiff_t 2724 __distance(_GLIBCXX_STD_C::_List_iterator<_Tp> __first, 2725 _GLIBCXX_STD_C::_List_iterator<_Tp> __last, 2726 input_iterator_tag __tag) 2727 { 2728 typedef _GLIBCXX_STD_C::_List_const_iterator<_Tp> _CIter; 2729 return std::__distance(_CIter(__first), _CIter(__last), __tag); 2730 } 2731 2732 template<typename _Tp> 2733 inline ptrdiff_t 2734 __distance(_GLIBCXX_STD_C::_List_const_iterator<_Tp> __first, 2735 _GLIBCXX_STD_C::_List_const_iterator<_Tp> __last, 2736 input_iterator_tag) 2737 { 2738 typedef __detail::_List_node_header _Sentinel; 2739 _GLIBCXX_STD_C::_List_const_iterator<_Tp> __beyond = __last; 2740 ++__beyond; 2741 const bool __whole = __first == __beyond; 2742 if (__builtin_constant_p (__whole) && __whole) 2743 return static_cast<const _Sentinel*>(__last._M_node)->_M_size; 2744 2745 ptrdiff_t __n = 0; 2746 while (__first != __last) 2747 { 2748 ++__first; 2749 ++__n; 2750 } 2751 return __n; 2752 } 2753 2754 #if _GLIBCXX_USE_ALLOC_PTR_FOR_LIST 2755 template<bool _Const, typename _Ptr> 2756 inline ptrdiff_t 2757 __distance(__list::_Iterator<_Const, _Ptr> __first, 2758 __list::_Iterator<_Const, _Ptr> __last, 2759 input_iterator_tag __tag) 2760 { 2761 using _Tp = typename __list::_Iterator<_Const, _Ptr>::value_type; 2762 using _Sentinel = typename __list::_Node_traits<_Tp, _Ptr>::_Node_header; 2763 auto __beyond = __last; 2764 ++__beyond; 2765 const bool __whole = __first == __beyond; 2766 if (__builtin_constant_p (__whole) && __whole) 2767 return static_cast<const _Sentinel&>(*__last._M_node)._M_size; 2768 2769 ptrdiff_t __n = 0; 2770 while (__first != __last) 2771 { 2772 ++__first; 2773 ++__n; 2774 } 2775 return __n; 2776 } 2777 #endif 2778 #endif 2779 2780 #if _GLIBCXX_USE_ALLOC_PTR_FOR_LIST 2781 namespace __list 2782 { 2783 template<typename _VoidPtr> 2784 void 2785 _Node_base<_VoidPtr>::swap(_Node_base& __x, _Node_base& __y) noexcept 2786 { 2787 auto __px = __x._M_base(); 2788 auto __py = __x._M_base(); 2789 2790 if (__x._M_next != __px) 2791 { 2792 if (__y._M_next != __py) 2793 { 2794 using std::swap; 2795 // Both __x and __y are not empty. 2796 swap(__x._M_next,__y._M_next); 2797 swap(__x._M_prev,__y._M_prev); 2798 __x._M_next->_M_prev = __x._M_prev->_M_next = __px; 2799 __y._M_next->_M_prev = __y._M_prev->_M_next = __py; 2800 } 2801 else 2802 { 2803 // __x is not empty, __y is empty. 2804 __y._M_next = __x._M_next; 2805 __y._M_prev = __x._M_prev; 2806 __y._M_next->_M_prev = __y._M_prev->_M_next = __py; 2807 __x._M_next = __x._M_prev = __px; 2808 } 2809 } 2810 else if (__y._M_next != __py) 2811 { 2812 // __x is empty, __y is not empty. 2813 __x._M_next = __y._M_next; 2814 __x._M_prev = __y._M_prev; 2815 __x._M_next->_M_prev = __x._M_prev->_M_next = __px; 2816 __y._M_next = __y._M_prev = __py; 2817 } 2818 } 2819 2820 template<typename _VoidPtr> 2821 void 2822 _Node_base<_VoidPtr>::_M_transfer(_Base_ptr const __first, 2823 _Base_ptr const __last) noexcept 2824 { 2825 __glibcxx_assert(__first != __last); 2826 2827 auto __self = _M_base(); 2828 if (__self != __last) 2829 { 2830 // Remove [first, last) from its old position. 2831 __last->_M_prev->_M_next = __self; 2832 __first->_M_prev->_M_next = __last; 2833 this->_M_prev->_M_next = __first; 2834 2835 // Splice [first, last) into its new position. 2836 auto const __tmp = this->_M_prev; 2837 this->_M_prev = __last->_M_prev; 2838 __last->_M_prev = __first->_M_prev; 2839 __first->_M_prev = __tmp; 2840 } 2841 } 2842 2843 template<typename _VoidPtr> 2844 void 2845 _Node_header<_VoidPtr>::_M_reverse() noexcept 2846 { 2847 const auto __self = this->_M_base(); 2848 auto __tmp = __self; 2849 do 2850 { 2851 using std::swap; 2852 swap(__tmp->_M_next, __tmp->_M_prev); 2853 2854 // Old next node is now prev. 2855 __tmp = __tmp->_M_prev; 2856 } 2857 while (__tmp != __self); 2858 } 2859 } // namespace __list 2860 #endif 2861 2862 _GLIBCXX_END_NAMESPACE_VERSION 2863 } // namespace std 2864 2865 #endif /* _STL_LIST_H */
