Where Online Learning is simpler!
The C and C++ Include Header Files
cat -n /usr/include/c++/15/bits/forward_list.h
1 // <forward_list.h> -*- C++ -*- 2 3 // Copyright (C) 2008-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 bits/forward_list.h 26 * This is an internal header file, included by other library headers. 27 * Do not attempt to use it directly. @headername{forward_list} 28 */ 29 30 #ifndef _FORWARD_LIST_H 31 #define _FORWARD_LIST_H 1 32 33 #ifdef _GLIBCXX_SYSHDR 34 #pragma GCC system_header 35 #endif 36 37 #include <initializer_list> 38 #include <bits/stl_iterator_base_types.h> 39 #include <bits/stl_iterator.h> 40 #include <bits/stl_algobase.h> 41 #include <bits/stl_function.h> 42 #include <bits/allocator.h> 43 #include <bits/allocated_ptr.h> 44 #include <bits/ptr_traits.h> 45 #include <debug/assertions.h> 46 #include <ext/alloc_traits.h> 47 #include <ext/aligned_buffer.h> 48 #include <debug/assertions.h> 49 #if __glibcxx_containers_ranges // C++ >= 23 50 # include <bits/ranges_base.h> // ranges::begin, ranges::distance etc. 51 # include <bits/ranges_util.h> // ranges::subrange 52 #endif 53 54 #if ! defined _GLIBCXX_USE_ALLOC_PTR_FOR_FWD_LIST 55 # define _GLIBCXX_USE_ALLOC_PTR_FOR_FWD_LIST 1 56 #endif 57 58 namespace std _GLIBCXX_VISIBILITY(default) 59 { 60 _GLIBCXX_BEGIN_NAMESPACE_VERSION 61 _GLIBCXX_BEGIN_NAMESPACE_CONTAINER 62 63 /** 64 * @brief A helper basic node class for %forward_list. 65 * 66 * This is just a linked list with nothing inside it. 67 * There are purely list shuffling utility methods here. 68 */ 69 struct _Fwd_list_node_base 70 { 71 using _Base_ptr = _Fwd_list_node_base*; 72 73 _Fwd_list_node_base() = default; 74 _Fwd_list_node_base(_Fwd_list_node_base&& __x) noexcept 75 : _M_next(__x._M_next) 76 { __x._M_next = nullptr; } 77 78 _Fwd_list_node_base(const _Fwd_list_node_base&) = delete; 79 _Fwd_list_node_base& operator=(const _Fwd_list_node_base&) = delete; 80 81 _Fwd_list_node_base& 82 operator=(_Fwd_list_node_base&& __x) noexcept 83 { 84 _M_next = __x._M_next; 85 __x._M_next = nullptr; 86 return *this; 87 } 88 89 _Fwd_list_node_base* _M_next = nullptr; 90 91 _Fwd_list_node_base* 92 _M_transfer_after(_Fwd_list_node_base* __begin, 93 _Fwd_list_node_base* __end) noexcept 94 { 95 _Fwd_list_node_base* __keep = __begin->_M_next; 96 if (__end) 97 { 98 __begin->_M_next = __end->_M_next; 99 __end->_M_next = _M_next; 100 } 101 else 102 __begin->_M_next = nullptr; 103 _M_next = __keep; 104 return __end; 105 } 106 107 void 108 _M_reverse_after() noexcept 109 { 110 _Fwd_list_node_base* __tail = _M_next; 111 if (!__tail) 112 return; 113 while (_Fwd_list_node_base* __temp = __tail->_M_next) 114 { 115 _Fwd_list_node_base* __keep = _M_next; 116 _M_next = __temp; 117 __tail->_M_next = __temp->_M_next; 118 _M_next->_M_next = __keep; 119 } 120 } 121 122 _Fwd_list_node_base* _M_base_ptr() { return this; } 123 const _Fwd_list_node_base* _M_base_ptr() const { return this; } 124 }; 125 126 /** 127 * @brief A helper node class for %forward_list. 128 * This is just a linked list with uninitialized storage for a 129 * data value in each node. 130 * There is a sorting utility method. 131 */ 132 template<typename _Tp> 133 struct _Fwd_list_node 134 : public _Fwd_list_node_base 135 { 136 using _Node_ptr = _Fwd_list_node*; 137 138 _Fwd_list_node() = default; 139 140 __gnu_cxx::__aligned_buffer<_Tp> _M_storage; 141 142 _Tp* 143 _M_valptr() noexcept 144 { return _M_storage._M_ptr(); } 145 146 const _Tp* 147 _M_valptr() const noexcept 148 { return _M_storage._M_ptr(); } 149 150 _Node_ptr 151 _M_node_ptr() 152 { return this; } 153 }; 154 155 template<typename _Tp> struct _Fwd_list_const_iterator; 156 157 /** 158 * @brief A forward_list::iterator. 159 * 160 * All the functions are op overloads. 161 */ 162 template<typename _Tp> 163 struct _Fwd_list_iterator 164 { 165 typedef _Fwd_list_iterator<_Tp> _Self; 166 typedef _Fwd_list_node<_Tp> _Node; 167 168 typedef _Tp value_type; 169 typedef _Tp* pointer; 170 typedef _Tp& reference; 171 typedef ptrdiff_t difference_type; 172 typedef std::forward_iterator_tag iterator_category; 173 174 _Fwd_list_iterator() noexcept 175 : _M_node() { } 176 177 explicit 178 _Fwd_list_iterator(_Fwd_list_node_base* __n) noexcept 179 : _M_node(__n) { } 180 181 [[__nodiscard__]] 182 reference 183 operator*() const noexcept 184 { return *static_cast<_Node*>(this->_M_node)->_M_valptr(); } 185 186 [[__nodiscard__]] 187 pointer 188 operator->() const noexcept 189 { return static_cast<_Node*>(this->_M_node)->_M_valptr(); } 190 191 _Self& 192 operator++() noexcept 193 { 194 _M_node = _M_node->_M_next; 195 return *this; 196 } 197 198 _Self 199 operator++(int) noexcept 200 { 201 _Self __tmp(*this); 202 _M_node = _M_node->_M_next; 203 return __tmp; 204 } 205 206 /** 207 * @brief Forward list iterator equality comparison. 208 */ 209 [[__nodiscard__]] 210 friend bool 211 operator==(const _Self& __x, const _Self& __y) noexcept 212 { return __x._M_node == __y._M_node; } 213 214 #if __cpp_impl_three_way_comparison < 201907L 215 /** 216 * @brief Forward list iterator inequality comparison. 217 */ 218 [[__nodiscard__]] 219 friend bool 220 operator!=(const _Self& __x, const _Self& __y) noexcept 221 { return __x._M_node != __y._M_node; } 222 #endif 223 224 private: 225 template<typename, typename> 226 friend class forward_list; 227 template<typename, typename> 228 friend struct _Fwd_list_base; 229 friend struct _Fwd_list_const_iterator<_Tp>; 230 231 _Self 232 _M_next() const noexcept 233 { 234 if (_M_node) 235 return _Fwd_list_iterator(_M_node->_M_next); 236 else 237 return _Fwd_list_iterator(nullptr); 238 } 239 240 _Fwd_list_node_base* _M_node; 241 }; 242 243 /** 244 * @brief A forward_list::const_iterator. 245 * 246 * All the functions are op overloads. 247 */ 248 template<typename _Tp> 249 struct _Fwd_list_const_iterator 250 { 251 typedef _Fwd_list_const_iterator<_Tp> _Self; 252 typedef const _Fwd_list_node<_Tp> _Node; 253 typedef _Fwd_list_iterator<_Tp> iterator; 254 255 typedef _Tp value_type; 256 typedef const _Tp* pointer; 257 typedef const _Tp& reference; 258 typedef ptrdiff_t difference_type; 259 typedef std::forward_iterator_tag iterator_category; 260 261 _Fwd_list_const_iterator() noexcept 262 : _M_node() { } 263 264 explicit 265 _Fwd_list_const_iterator(const _Fwd_list_node_base* __n) noexcept 266 : _M_node(__n) { } 267 268 _Fwd_list_const_iterator(const iterator& __iter) noexcept 269 : _M_node(__iter._M_node) { } 270 271 [[__nodiscard__]] 272 reference 273 operator*() const noexcept 274 { return *static_cast<_Node*>(this->_M_node)->_M_valptr(); } 275 276 [[__nodiscard__]] 277 pointer 278 operator->() const noexcept 279 { return static_cast<_Node*>(this->_M_node)->_M_valptr(); } 280 281 _Self& 282 operator++() noexcept 283 { 284 _M_node = _M_node->_M_next; 285 return *this; 286 } 287 288 _Self 289 operator++(int) noexcept 290 { 291 _Self __tmp(*this); 292 _M_node = _M_node->_M_next; 293 return __tmp; 294 } 295 296 /** 297 * @brief Forward list const_iterator equality comparison. 298 */ 299 [[__nodiscard__]] 300 friend bool 301 operator==(const _Self& __x, const _Self& __y) noexcept 302 { return __x._M_node == __y._M_node; } 303 304 #if __cpp_impl_three_way_comparison < 201907L 305 /** 306 * @brief Forward list const_iterator inequality comparison. 307 */ 308 [[__nodiscard__]] 309 friend bool 310 operator!=(const _Self& __x, const _Self& __y) noexcept 311 { return __x._M_node != __y._M_node; } 312 #endif 313 314 private: 315 template<typename, typename> 316 friend class forward_list; 317 template<typename, typename> 318 friend struct _Fwd_list_base; 319 320 _Self 321 _M_next() const noexcept 322 { 323 if (this->_M_node) 324 return _Fwd_list_const_iterator(_M_node->_M_next); 325 else 326 return _Fwd_list_const_iterator(nullptr); 327 } 328 329 _Fwd_list_iterator<_Tp> 330 _M_const_cast() const noexcept 331 { 332 return _Fwd_list_iterator<_Tp>( 333 const_cast<_Fwd_list_node_base*>(_M_node)); 334 } 335 336 const _Fwd_list_node_base* _M_node; 337 }; 338 339 template<typename _Tp, typename _Allocator> class forward_list; 340 template<typename _Tp, typename _Allocator> struct _Fwd_list_base; 341 342 namespace __fwdlist 343 { 344 #if _GLIBCXX_USE_ALLOC_PTR_FOR_FWD_LIST 345 /// The node-base type for allocators that use fancy pointers. 346 template<typename _VoidPtr> 347 struct _Node_base 348 { 349 using _Base_ptr = __ptr_rebind<_VoidPtr, _Node_base>; 350 351 _Node_base() = default; 352 353 _Node_base(_Node_base&& __x) noexcept 354 : _M_next(__x._M_next) 355 { __x._M_next = nullptr; } 356 357 _Node_base(const _Node_base&) = delete; 358 _Node_base& operator=(const _Node_base&) = delete; 359 360 _Node_base& 361 operator=(_Node_base&& __x) noexcept 362 { 363 _M_next = __x._M_next; 364 __x._M_next = nullptr; 365 return *this; 366 } 367 368 _Base_ptr _M_next = nullptr; 369 370 // Splice (begin,end) before _M_next. 371 _Base_ptr 372 _M_transfer_after(_Base_ptr __begin, _Base_ptr __end) noexcept 373 { 374 _Base_ptr __keep = __begin->_M_next; 375 if (__end) 376 { 377 __begin->_M_next = __end->_M_next; 378 __end->_M_next = _M_next; 379 } 380 else 381 __begin->_M_next = nullptr; 382 _M_next = __keep; 383 return __end; 384 } 385 386 void 387 _M_reverse_after() noexcept 388 { 389 _Base_ptr __tail = _M_next; 390 if (!__tail) 391 return; 392 while (_Base_ptr __temp = __tail->_M_next) 393 { 394 _Base_ptr __keep = _M_next; 395 _M_next = __temp; 396 __tail->_M_next = __temp->_M_next; 397 _M_next->_M_next = __keep; 398 } 399 } 400 401 // This is not const-correct, but it's only used in a const access path 402 // by std::forward_list::empty(), where it doesn't escape, and by 403 // std::forward_list::before_begin() const, where the pointer is used 404 // to initialize a const_iterator and so constness is restored. 405 _Base_ptr 406 _M_base_ptr() const 407 { 408 return pointer_traits<_Base_ptr>:: 409 pointer_to(const_cast<_Node_base&>(*this)); 410 } 411 }; 412 413 /** 414 * @brief A helper node class for %forward_list. 415 */ 416 template<typename _ValPtr> 417 struct _Node 418 : public _Node_base<__ptr_rebind<_ValPtr, void>> 419 { 420 using value_type = typename pointer_traits<_ValPtr>::element_type; 421 using _Node_ptr = __ptr_rebind<_ValPtr, _Node>; 422 423 _Node() noexcept { } 424 ~_Node() { } 425 _Node(_Node&&) = delete; 426 427 union _Uninit_storage 428 { 429 _Uninit_storage() noexcept { } 430 ~_Uninit_storage() { } 431 432 #if ! _GLIBCXX_INLINE_VERSION 433 // For ABI compatibility we need to overalign this member. 434 alignas(__alignof__(value_type)) // XXX GLIBCXX_ABI Deprecated 435 #endif 436 value_type _M_data; 437 }; 438 _Uninit_storage _M_u; 439 440 value_type* 441 _M_valptr() noexcept 442 { return std::__addressof(_M_u._M_data); } 443 444 const value_type* 445 _M_valptr() const noexcept 446 { return std::__addressof(_M_u._M_data); } 447 448 _Node_ptr 449 _M_node_ptr() 450 { return pointer_traits<_Node_ptr>::pointer_to(*this); } 451 }; 452 453 /// A forward_list iterator when the allocator uses fancy pointers. 454 template<bool _Const, typename _Ptr> 455 class _Iterator 456 { 457 using _Node = __fwdlist::_Node<_Ptr>; 458 using _Base_ptr 459 = typename __fwdlist::_Node_base<__ptr_rebind<_Ptr, void>>::_Base_ptr; 460 461 template<typename _Tp> 462 using __maybe_const = __conditional_t<_Const, const _Tp, _Tp>; 463 464 public: 465 using value_type = typename pointer_traits<_Ptr>::element_type; 466 using difference_type = ptrdiff_t; 467 using iterator_category = forward_iterator_tag; 468 using pointer = __maybe_const<value_type>*; 469 using reference = __maybe_const<value_type>&; 470 471 constexpr _Iterator() noexcept : _M_node() { } 472 473 _Iterator(const _Iterator&) = default; 474 _Iterator& operator=(const _Iterator&) = default; 475 476 #ifdef __glibcxx_concepts 477 constexpr 478 _Iterator(const _Iterator<false, _Ptr>& __i) requires _Const 479 #else 480 template<bool _OtherConst, 481 typename = __enable_if_t<_Const && !_OtherConst>> 482 constexpr 483 _Iterator(const _Iterator<_OtherConst, _Ptr>& __i) 484 #endif 485 : _M_node(__i._M_node) { } 486 487 constexpr explicit 488 _Iterator(_Base_ptr __x) noexcept 489 : _M_node(__x) { } 490 491 [[__nodiscard__]] 492 constexpr reference 493 operator*() const noexcept 494 { return static_cast<_Node&>(*this->_M_node)._M_u._M_data; } 495 496 [[__nodiscard__]] 497 constexpr pointer 498 operator->() const noexcept 499 { return static_cast<_Node&>(*this->_M_node)._M_valptr(); } 500 501 _GLIBCXX14_CONSTEXPR _Iterator& 502 operator++() noexcept 503 { 504 _M_node = _M_node->_M_next; 505 return *this; 506 } 507 508 _GLIBCXX14_CONSTEXPR _Iterator 509 operator++(int) noexcept 510 { 511 _Iterator __tmp(*this); 512 _M_node = _M_node->_M_next; 513 return __tmp; 514 } 515 516 /** 517 * @brief Forward list iterator equality comparison. 518 */ 519 [[__nodiscard__]] 520 friend constexpr bool 521 operator==(const _Iterator& __x, const _Iterator& __y) noexcept 522 { return __x._M_node == __y._M_node; } 523 524 #if __cpp_impl_three_way_comparison < 201907L 525 /** 526 * @brief Forward list iterator inequality comparison. 527 */ 528 [[__nodiscard__]] 529 friend constexpr bool 530 operator!=(const _Iterator& __x, const _Iterator& __y) noexcept 531 { return __x._M_node != __y._M_node; } 532 #endif 533 534 private: 535 template<typename _Tp, typename _Allocator> 536 friend class _GLIBCXX_STD_C::forward_list; 537 template<typename _Tp, typename _Allocator> 538 friend struct _GLIBCXX_STD_C::_Fwd_list_base; 539 540 constexpr _Iterator<false, _Ptr> 541 _M_const_cast() const noexcept 542 { return _Iterator<false, _Ptr>(_M_node); } 543 544 friend _Iterator<!_Const, _Ptr>; 545 546 constexpr _Iterator 547 _M_next() const noexcept 548 { return _Iterator(_M_node ? _M_node->_M_next : nullptr); } 549 550 _Base_ptr _M_node; 551 }; 552 #endif // USE_ALLOC_PTR_FOR_FWD_LIST 553 554 // Determine the node and iterator types used by std::forward_list. 555 template<typename _Tp, typename _Ptr> 556 struct _Node_traits; 557 558 #if _GLIBCXX_USE_ALLOC_PTR_FOR_LIST <= 9000 559 // Specialization for the simple case where the allocator's pointer type 560 // is the same type as value_type*. 561 // For ABI compatibility we can't change the types used for this case. 562 template<typename _Tp> 563 struct _Node_traits<_Tp, _Tp*> 564 { 565 using _Node_base = _Fwd_list_node_base; 566 using _Node = _Fwd_list_node<_Tp>; 567 using _Iterator = _Fwd_list_iterator<_Tp>; 568 using _Const_iterator = _Fwd_list_const_iterator<_Tp>; 569 }; 570 #endif 571 572 #if ! _GLIBCXX_USE_ALLOC_PTR_FOR_FWD_LIST 573 // Always use the T* specialization. 574 template<typename _Tp, typename _Ptr> 575 struct _Node_traits 576 : _Node_traits<_Tp, _Tp*> 577 { }; 578 #else 579 // Primary template used when the allocator uses fancy pointers. 580 template<typename _Tp, typename _Ptr> 581 struct _Node_traits 582 { 583 private: 584 using _VoidPtr = __ptr_rebind<_Ptr, void>; 585 using _ValPtr = __ptr_rebind<_Ptr, _Tp>; 586 587 public: 588 using _Node_base = __fwdlist::_Node_base<_VoidPtr>; 589 using _Node = __fwdlist::_Node<_ValPtr>; 590 using _Iterator = __fwdlist::_Iterator<false, _ValPtr>; 591 using _Const_iterator = __fwdlist::_Iterator<true, _ValPtr>; 592 }; 593 #endif // USE_ALLOC_PTR_FOR_FWD_LIST 594 } // namespace __fwdlist 595 596 /** 597 * @brief Base class for %forward_list. 598 */ 599 template<typename _Tp, typename _Alloc> 600 struct _Fwd_list_base 601 { 602 #if __cplusplus > 201703L || defined __STRICT_ANSI__ 603 // The static_assert in forward_list ensures _Alloc::value_type is _Tp. 604 using pointer = typename allocator_traits<_Alloc>::pointer; 605 #else 606 using _Tp_alloc_traits 607 = typename allocator_traits<_Alloc>::template rebind_traits<_Tp>; 608 using pointer = typename _Tp_alloc_traits::pointer; 609 #endif 610 611 protected: 612 using _Node_traits = __fwdlist::_Node_traits<_Tp, pointer>; 613 using _Node = typename _Node_traits::_Node; 614 using _Node_alloc_type = __alloc_rebind<_Alloc, _Node>; 615 using _Node_alloc_traits = __gnu_cxx::__alloc_traits<_Node_alloc_type>; 616 using _Node_ptr = typename _Node_alloc_traits::pointer; 617 using _Base_ptr = typename _Node_traits::_Node_base::_Base_ptr; 618 619 struct _Fwd_list_impl 620 : public _Node_alloc_type 621 { 622 typename _Node_traits::_Node_base _M_head; 623 624 _Fwd_list_impl() 625 noexcept(is_nothrow_default_constructible<_Node_alloc_type>::value) 626 : _Node_alloc_type(), _M_head() 627 { } 628 629 _Fwd_list_impl(_Fwd_list_impl&&) = default; 630 631 _Fwd_list_impl(_Fwd_list_impl&& __fl, _Node_alloc_type&& __a) 632 : _Node_alloc_type(std::move(__a)), _M_head(std::move(__fl._M_head)) 633 { } 634 635 _Fwd_list_impl(_Node_alloc_type&& __a) 636 : _Node_alloc_type(std::move(__a)), _M_head() 637 { } 638 }; 639 640 _Fwd_list_impl _M_impl; 641 642 public: 643 using iterator = typename _Node_traits::_Iterator; 644 using const_iterator = typename _Node_traits::_Const_iterator; 645 646 _Node_alloc_type& 647 _M_get_Node_allocator() noexcept 648 { return this->_M_impl; } 649 650 const _Node_alloc_type& 651 _M_get_Node_allocator() const noexcept 652 { return this->_M_impl; } 653 654 _Fwd_list_base() = default; 655 656 _Fwd_list_base(_Node_alloc_type&& __a) 657 : _M_impl(std::move(__a)) { } 658 659 // When allocators are always equal. 660 _Fwd_list_base(_Fwd_list_base&& __lst, _Node_alloc_type&& __a, 661 std::true_type) 662 : _M_impl(std::move(__lst._M_impl), std::move(__a)) 663 { } 664 665 // When allocators are not always equal. 666 _Fwd_list_base(_Fwd_list_base&& __lst, _Node_alloc_type&& __a); 667 668 _Fwd_list_base(_Fwd_list_base&&) = default; 669 670 ~_Fwd_list_base() 671 { _M_erase_after(_M_impl._M_head._M_base_ptr(), nullptr); } 672 673 protected: 674 #if ! _GLIBCXX_INLINE_VERSION 675 // XXX GLIBCXX_ABI Deprecated 676 _Node* 677 _M_get_node() 678 { 679 auto __ptr = _Node_alloc_traits::allocate(_M_get_Node_allocator(), 1); 680 return std::__to_address(__ptr); 681 } 682 #endif 683 684 void 685 _M_put_node(_Node_ptr __p) 686 { 687 #if _GLIBCXX_USE_ALLOC_PTR_FOR_FWD_LIST 688 _Node_alloc_traits::deallocate(_M_get_Node_allocator(), __p, 1); 689 #else 690 typedef typename _Node_alloc_traits::pointer _Ptr; 691 auto __ptr = std::pointer_traits<_Ptr>::pointer_to(*__p); 692 _Node_alloc_traits::deallocate(_M_get_Node_allocator(), __ptr, 1); 693 #endif 694 } 695 696 template<typename... _Args> 697 _Node_ptr 698 _M_create_node(_Args&&... __args) 699 { 700 auto& __alloc = _M_get_Node_allocator(); 701 auto __guard = std::__allocate_guarded_obj(__alloc); 702 _Node_alloc_traits::construct(__alloc, __guard->_M_valptr(), 703 std::forward<_Args>(__args)...); 704 auto __p = __guard.release(); 705 #if _GLIBCXX_USE_ALLOC_PTR_FOR_FWD_LIST 706 return __p; 707 #else 708 return std::__to_address(__p); 709 #endif 710 } 711 712 #pragma GCC diagnostic push 713 #pragma GCC diagnostic ignored "-Wc++17-extensions" // if constexpr 714 void 715 _M_destroy_node(_Node_ptr __p) 716 { 717 auto& __alloc = _M_get_Node_allocator(); 718 // Destroy the element 719 _Node_alloc_traits::destroy(__alloc, __p->_M_valptr()); 720 // Only destroy the node if the pointers require it. 721 if constexpr (!is_trivially_destructible<_Base_ptr>::value) 722 __p->~_Node(); 723 _M_put_node(__p); 724 } 725 #pragma GCC diagnostic pop 726 727 template<typename... _Args> 728 _Base_ptr 729 _M_insert_after(const_iterator __pos, _Args&&... __args); 730 731 _Base_ptr 732 _M_erase_after(_Base_ptr __pos); 733 734 _Base_ptr 735 _M_erase_after(_Base_ptr __pos, _Base_ptr __last); 736 }; 737 738 /** 739 * @brief A standard container with linear time access to elements, 740 * and fixed time insertion/deletion at any point in the sequence. 741 * 742 * @ingroup sequences 743 * @headerfile forward_list 744 * @since C++11 745 * 746 * @tparam _Tp Type of element. 747 * @tparam _Alloc Allocator type, defaults to allocator<_Tp>. 748 * 749 * Meets the requirements of a <a href="tables.html#65">container</a>, a 750 * <a href="tables.html#67">sequence</a>, including the 751 * <a href="tables.html#68">optional sequence requirements</a> with the 752 * %exception of `at` and `operator[]`. 753 * 754 * This is a @e singly @e linked %list. Traversal up the 755 * %list requires linear time, but adding and removing elements (or 756 * @e nodes) is done in constant time, regardless of where the 757 * change takes place. Unlike std::vector and std::deque, 758 * random-access iterators are not provided, so subscripting (`[]`) 759 * access is not allowed. For algorithms which only need 760 * sequential access, this lack makes no difference. 761 * 762 * Also unlike the other standard containers, std::forward_list provides 763 * specialized algorithms %unique to linked lists, such as 764 * splicing, sorting, and in-place reversal. 765 */ 766 template<typename _Tp, typename _Alloc = allocator<_Tp>> 767 class forward_list : private _Fwd_list_base<_Tp, _Alloc> 768 { 769 static_assert(is_same<typename remove_cv<_Tp>::type, _Tp>::value, 770 "std::forward_list must have a non-const, non-volatile value_type"); 771 #if __cplusplus > 201703L || defined __STRICT_ANSI__ 772 static_assert(is_same<typename _Alloc::value_type, _Tp>::value, 773 "std::forward_list must have the same value_type as its allocator"); 774 #endif 775 776 private: 777 typedef _Fwd_list_base<_Tp, _Alloc> _Base; 778 typedef _Fwd_list_node_base _Node_base; 779 typedef typename _Base::_Node _Node; 780 typedef typename _Base::_Node_alloc_type _Node_alloc_type; 781 typedef typename _Base::_Node_alloc_traits _Node_alloc_traits; 782 typedef allocator_traits<__alloc_rebind<_Alloc, _Tp>> _Alloc_traits; 783 784 public: 785 // types: 786 typedef _Tp value_type; 787 typedef typename _Alloc_traits::pointer pointer; 788 typedef typename _Alloc_traits::const_pointer const_pointer; 789 typedef value_type& reference; 790 typedef const value_type& const_reference; 791 792 typedef typename _Base::iterator iterator; 793 typedef typename _Base::const_iterator const_iterator; 794 typedef std::size_t size_type; 795 typedef std::ptrdiff_t difference_type; 796 typedef _Alloc allocator_type; 797 798 // 23.3.4.2 construct/copy/destroy: 799 800 /** 801 * @brief Creates a %forward_list with no elements. 802 */ 803 forward_list() = default; 804 805 /** 806 * @brief Creates a %forward_list with no elements. 807 * @param __al An allocator object. 808 */ 809 explicit 810 forward_list(const _Alloc& __al) noexcept 811 : _Base(_Node_alloc_type(__al)) 812 { } 813 814 /** 815 * @brief Copy constructor with allocator argument. 816 * @param __list Input list to copy. 817 * @param __al An allocator object. 818 */ 819 forward_list(const forward_list& __list, 820 const __type_identity_t<_Alloc>& __al) 821 : _Base(_Node_alloc_type(__al)) 822 { _M_range_initialize(__list.begin(), __list.end()); } 823 824 private: 825 forward_list(forward_list&& __list, _Node_alloc_type&& __al, 826 false_type) 827 : _Base(std::move(__list), std::move(__al)) 828 { 829 // If __list is not empty it means its allocator is not equal to __a, 830 // so we need to move from each element individually. 831 insert_after(cbefore_begin(), 832 std::__make_move_if_noexcept_iterator(__list.begin()), 833 std::__make_move_if_noexcept_iterator(__list.end())); 834 } 835 836 forward_list(forward_list&& __list, _Node_alloc_type&& __al, 837 true_type) 838 noexcept 839 : _Base(std::move(__list), _Node_alloc_type(__al), true_type{}) 840 { } 841 842 public: 843 /** 844 * @brief Move constructor with allocator argument. 845 * @param __list Input list to move. 846 * @param __al An allocator object. 847 */ 848 forward_list(forward_list&& __list, 849 const __type_identity_t<_Alloc>& __al) 850 noexcept(_Node_alloc_traits::_S_always_equal()) 851 : forward_list(std::move(__list), _Node_alloc_type(__al), 852 typename _Node_alloc_traits::is_always_equal{}) 853 { } 854 855 /** 856 * @brief Creates a %forward_list with default constructed elements. 857 * @param __n The number of elements to initially create. 858 * @param __al An allocator object. 859 * 860 * This constructor creates the %forward_list with `__n` default 861 * constructed elements. 862 */ 863 explicit 864 forward_list(size_type __n, const _Alloc& __al = _Alloc()) 865 : _Base(_Node_alloc_type(__al)) 866 { _M_default_initialize(__n); } 867 868 /** 869 * @brief Creates a %forward_list with copies of an exemplar element. 870 * @param __n The number of elements to initially create. 871 * @param __value An element to copy. 872 * @param __al An allocator object. 873 * 874 * This constructor fills the %forward_list with `__n` copies of 875 * `__value`. 876 */ 877 forward_list(size_type __n, const _Tp& __value, 878 const _Alloc& __al = _Alloc()) 879 : _Base(_Node_alloc_type(__al)) 880 { _M_fill_initialize(__n, __value); } 881 882 /** 883 * @brief Builds a %forward_list from a range. 884 * @param __first An input iterator. 885 * @param __last An input iterator. 886 * @param __al An allocator object. 887 * 888 * Create a %forward_list consisting of copies of the elements from 889 * `[__first,__last)`. This is linear in N (where N is 890 * `distance(__first,__last)`). 891 */ 892 template<typename _InputIterator, 893 typename = std::_RequireInputIter<_InputIterator>> 894 forward_list(_InputIterator __first, _InputIterator __last, 895 const _Alloc& __al = _Alloc()) 896 : _Base(_Node_alloc_type(__al)) 897 { _M_range_initialize(__first, __last); } 898 899 #if __glibcxx_containers_ranges // C++ >= 23 900 /** 901 * @brief Construct a forward_list from a range. 902 * @param __rg An input range with elements that are convertible to 903 * the forward_list's value_type. 904 * @param __a An allocator. 905 * 906 * @since C++23 907 */ 908 template<__detail::__container_compatible_range<_Tp> _Rg> 909 forward_list(from_range_t, _Rg&& __rg, const _Alloc& __a = _Alloc()) 910 : _Base(_Node_alloc_type(__a)) 911 { 912 auto __to = this->_M_impl._M_head._M_base_ptr(); 913 auto __first = ranges::begin(__rg); 914 const auto __last = ranges::end(__rg); 915 for (; __first != __last; ++__first) 916 { 917 __to->_M_next = this->_M_create_node(*__first)->_M_base_ptr(); 918 __to = __to->_M_next; 919 } 920 } 921 #endif // containers_ranges 922 923 /** 924 * @brief The %forward_list copy constructor. 925 * @param __list A %forward_list of identical element and allocator 926 * types. 927 */ 928 forward_list(const forward_list& __list) 929 : _Base(_Node_alloc_traits::_S_select_on_copy( 930 __list._M_get_Node_allocator())) 931 { _M_range_initialize(__list.begin(), __list.end()); } 932 933 /** 934 * @brief The %forward_list move constructor. 935 * @param __list A %forward_list of identical element and allocator 936 * types. 937 * 938 * The newly-created %forward_list contains the exact contents of the 939 * moved instance. The contents of the moved instance are a valid, but 940 * unspecified %forward_list. 941 */ 942 forward_list(forward_list&&) = default; 943 944 /** 945 * @brief Builds a %forward_list from an initializer_list 946 * @param __il An initializer_list of value_type. 947 * @param __al An allocator object. 948 * 949 * Create a %forward_list consisting of copies of the elements 950 * in the initializer_list `__il`. This is linear in `__il.size()`. 951 */ 952 forward_list(std::initializer_list<_Tp> __il, 953 const _Alloc& __al = _Alloc()) 954 : _Base(_Node_alloc_type(__al)) 955 { _M_range_initialize(__il.begin(), __il.end()); } 956 957 /** 958 * @brief The forward_list dtor. 959 */ 960 ~forward_list() noexcept 961 { } 962 963 /** 964 * @brief The %forward_list assignment operator. 965 * @param __list A %forward_list of identical element and allocator 966 * types. 967 * 968 * All the elements of `__list` are copied. 969 * 970 * Whether the allocator is copied depends on the allocator traits. 971 */ 972 forward_list& 973 operator=(const forward_list& __list); 974 975 #pragma GCC diagnostic push 976 #pragma GCC diagnostic ignored "-Wc++17-extensions" // if constexpr 977 /** 978 * @brief The %forward_list move assignment operator. 979 * @param __list A %forward_list of identical element and allocator 980 * types. 981 * 982 * The contents of `__list` are moved into this %forward_list 983 * (without copying, if the allocators permit it). 984 * 985 * Afterwards @a __list is a valid, but unspecified %forward_list 986 * 987 * Whether the allocator is moved depends on the allocator traits. 988 */ 989 forward_list& 990 operator=(forward_list&& __list) 991 noexcept(_Node_alloc_traits::_S_nothrow_move()) 992 { 993 constexpr bool __move_storage = 994 _Node_alloc_traits::_S_propagate_on_move_assign() 995 || _Node_alloc_traits::_S_always_equal(); 996 if constexpr (!__move_storage) 997 { 998 if (__list._M_get_Node_allocator() != this->_M_get_Node_allocator()) 999 { 1000 // The rvalue's allocator cannot be moved, or is not equal, 1001 // so we need to individually move each element. 1002 this->assign(std::make_move_iterator(__list.begin()), 1003 std::make_move_iterator(__list.end())); 1004 return *this; 1005 } 1006 } 1007 1008 clear(); 1009 this->_M_impl._M_head._M_next = __list._M_impl._M_head._M_next; 1010 __list._M_impl._M_head._M_next = nullptr; 1011 if constexpr (_Node_alloc_traits::_S_propagate_on_move_assign()) 1012 this->_M_get_Node_allocator() 1013 = std::move(__list._M_get_Node_allocator()); 1014 return *this; 1015 } 1016 1017 /** 1018 * @brief The %forward_list initializer list assignment operator. 1019 * @param __il An initializer_list of value_type. 1020 * 1021 * Replace the contents of the %forward_list with copies of the 1022 * elements in the initializer_list `__il`. This is linear in 1023 * `__il.size()`. 1024 */ 1025 forward_list& 1026 operator=(std::initializer_list<_Tp> __il) 1027 { 1028 assign(__il); 1029 return *this; 1030 } 1031 1032 /** 1033 * @brief Assigns a range to a %forward_list. 1034 * @param __first An input iterator. 1035 * @param __last An input iterator. 1036 * 1037 * This function fills a %forward_list with copies of the elements 1038 * in the range `[ __first,__last)`. 1039 * 1040 * Note that the assignment completely changes the %forward_list and 1041 * that the number of elements of the resulting %forward_list is the 1042 * same as the number of elements assigned. 1043 */ 1044 template<typename _InputIterator, 1045 typename = std::_RequireInputIter<_InputIterator>> 1046 void 1047 assign(_InputIterator __first, _InputIterator __last) 1048 { 1049 if constexpr (is_assignable<_Tp&, decltype(*__first)>::value) 1050 { 1051 auto __prev = before_begin(); 1052 auto __curr = begin(); 1053 auto __end = end(); 1054 while (__curr != __end && __first != __last) 1055 { 1056 *__curr = *__first; 1057 ++__prev; 1058 ++__curr; 1059 ++__first; 1060 } 1061 if (__first != __last) 1062 insert_after(__prev, __first, __last); 1063 else if (__curr != __end) 1064 erase_after(__prev, __end); 1065 } 1066 else 1067 { 1068 clear(); 1069 insert_after(cbefore_begin(), __first, __last); 1070 } 1071 } 1072 #pragma GCC diagnostic pop 1073 1074 #if __glibcxx_containers_ranges // C++ >= 23 1075 /** 1076 * @brief Assign a range to a forward_list. 1077 * @since C++23 1078 */ 1079 template<__detail::__container_compatible_range<_Tp> _Rg> 1080 void 1081 assign_range(_Rg&& __rg) 1082 { 1083 static_assert(assignable_from<_Tp&, ranges::range_reference_t<_Rg>>); 1084 1085 auto __first = ranges::begin(__rg); 1086 const auto __last = ranges::end(__rg); 1087 iterator __prev = before_begin(); 1088 iterator __curr = begin(); 1089 const iterator __end = end(); 1090 1091 while (__curr != __end && __first != __last) 1092 { 1093 *__curr = *__first; 1094 __prev = __curr; 1095 ++__first; 1096 ++__curr; 1097 } 1098 1099 if (__curr != __end) 1100 erase_after(__prev, __end); 1101 else 1102 insert_range_after(__prev, 1103 ranges::subrange(std::move(__first), __last)); 1104 } 1105 #endif // containers_ranges 1106 1107 #pragma GCC diagnostic push 1108 #pragma GCC diagnostic ignored "-Wc++17-extensions" // if constexpr 1109 /** 1110 * @brief Assigns a given value to a %forward_list. 1111 * @param __n Number of elements to be assigned. 1112 * @param __val Value to be assigned. 1113 * 1114 * This function fills a %forward_list with `__n` copies of the 1115 * given value. Note that the assignment completely changes the 1116 * %forward_list, and that the resulting %forward_list has `__n` 1117 * elements. 1118 */ 1119 void 1120 assign(size_type __n, const _Tp& __val) 1121 { 1122 if constexpr (is_copy_assignable<_Tp>::value) 1123 { 1124 auto __prev = before_begin(); 1125 auto __curr = begin(); 1126 auto __end = end(); 1127 while (__curr != __end && __n > 0) 1128 { 1129 *__curr = __val; 1130 ++__prev; 1131 ++__curr; 1132 --__n; 1133 } 1134 if (__n > 0) 1135 insert_after(__prev, __n, __val); 1136 else if (__curr != __end) 1137 erase_after(__prev, __end); 1138 } 1139 else 1140 { 1141 clear(); 1142 insert_after(cbefore_begin(), __n, __val); 1143 } 1144 } 1145 #pragma GCC diagnostic pop 1146 1147 /** 1148 * @brief Assigns an initializer_list to a %forward_list. 1149 * @param __il An initializer_list of value_type. 1150 * 1151 * Replace the contents of the %forward_list with copies of the 1152 * elements in the initializer_list `__il`. This is linear in 1153 * `__il.size()`. 1154 */ 1155 void 1156 assign(std::initializer_list<_Tp> __il) 1157 { assign(__il.begin(), __il.end()); } 1158 1159 /// Get a copy of the memory allocation object. 1160 allocator_type 1161 get_allocator() const noexcept 1162 { return allocator_type(this->_M_get_Node_allocator()); } 1163 1164 // 23.3.4.3 iterators: 1165 1166 /** 1167 * Returns a read/write iterator that points before the first element 1168 * in the %forward_list. Iteration is done in ordinary element order. 1169 */ 1170 [[__nodiscard__]] 1171 iterator 1172 before_begin() noexcept 1173 { return iterator(this->_M_impl._M_head._M_base_ptr()); } 1174 1175 /** 1176 * Returns a read-only (constant) iterator that points before the 1177 * first element in the %forward_list. Iteration is done in ordinary 1178 * element order. 1179 */ 1180 [[__nodiscard__]] 1181 const_iterator 1182 before_begin() const noexcept 1183 { return const_iterator(this->_M_impl._M_head._M_base_ptr()); } 1184 1185 /** 1186 * Returns a read/write iterator that points to the first element 1187 * in the %forward_list. Iteration is done in ordinary element order. 1188 */ 1189 [[__nodiscard__]] 1190 iterator 1191 begin() noexcept 1192 { return iterator(this->_M_impl._M_head._M_next); } 1193 1194 /** 1195 * Returns a read-only (constant) iterator that points to the first 1196 * element in the %forward_list. Iteration is done in ordinary 1197 * element order. 1198 */ 1199 [[__nodiscard__]] 1200 const_iterator 1201 begin() const noexcept 1202 { return const_iterator(this->_M_impl._M_head._M_next); } 1203 1204 /** 1205 * Returns a read/write iterator that points one past the last 1206 * element in the %forward_list. Iteration is done in ordinary 1207 * element order. 1208 */ 1209 [[__nodiscard__]] 1210 iterator 1211 end() noexcept 1212 { return iterator(nullptr); } 1213 1214 /** 1215 * Returns a read-only iterator that points one past the last 1216 * element in the %forward_list. Iteration is done in ordinary 1217 * element order. 1218 */ 1219 [[__nodiscard__]] 1220 const_iterator 1221 end() const noexcept 1222 { return const_iterator(nullptr); } 1223 1224 /** 1225 * Returns a read-only (constant) iterator that points to the 1226 * first element in the %forward_list. Iteration is done in ordinary 1227 * element order. 1228 */ 1229 [[__nodiscard__]] 1230 const_iterator 1231 cbegin() const noexcept 1232 { return const_iterator(this->_M_impl._M_head._M_next); } 1233 1234 /** 1235 * Returns a read-only (constant) iterator that points before the 1236 * first element in the %forward_list. Iteration is done in ordinary 1237 * element order. 1238 */ 1239 [[__nodiscard__]] 1240 const_iterator 1241 cbefore_begin() const noexcept 1242 { return const_iterator(this->_M_impl._M_head._M_base_ptr()); } 1243 1244 /** 1245 * Returns a read-only (constant) iterator that points one past 1246 * the last element in the %forward_list. Iteration is done in 1247 * ordinary element order. 1248 */ 1249 [[__nodiscard__]] 1250 const_iterator 1251 cend() const noexcept 1252 { return const_iterator(nullptr); } 1253 1254 /** 1255 * Returns true if the %forward_list is empty. (Thus begin() would 1256 * equal end().) 1257 */ 1258 [[__nodiscard__]] 1259 bool 1260 empty() const noexcept 1261 { return this->_M_impl._M_head._M_next == nullptr; } 1262 1263 /** 1264 * Returns the largest possible number of elements of %forward_list. 1265 */ 1266 [[__nodiscard__]] 1267 size_type 1268 max_size() const noexcept 1269 { return _Node_alloc_traits::max_size(this->_M_get_Node_allocator()); } 1270 1271 // 23.3.4.4 element access: 1272 1273 /** 1274 * Returns a read/write reference to the data at the first 1275 * element of the %forward_list. 1276 */ 1277 [[__nodiscard__]] 1278 reference 1279 front() 1280 { 1281 __glibcxx_requires_nonempty(); 1282 _Node& __front = static_cast<_Node&>(*this->_M_impl._M_head._M_next); 1283 return *__front._M_valptr(); 1284 } 1285 1286 /** 1287 * Returns a read-only (constant) reference to the data at the first 1288 * element of the %forward_list. 1289 */ 1290 [[__nodiscard__]] 1291 const_reference 1292 front() const 1293 { 1294 __glibcxx_requires_nonempty(); 1295 _Node& __front = static_cast<_Node&>(*this->_M_impl._M_head._M_next); 1296 return *__front._M_valptr(); 1297 } 1298 1299 // 23.3.4.5 modifiers: 1300 1301 /** 1302 * @brief Constructs object in %forward_list at the front of the 1303 * list. 1304 * @param __args Arguments. 1305 * 1306 * This function will insert an object of type `Tp` constructed 1307 * with `Tp(std::forward<Args>(args)...)` at the front of the list 1308 * Due to the nature of a %forward_list this operation can 1309 * be done in constant time, and does not invalidate iterators 1310 * and references. 1311 */ 1312 template<typename... _Args> 1313 #if __cplusplus > 201402L 1314 reference 1315 #else 1316 void 1317 #endif 1318 emplace_front(_Args&&... __args) 1319 { 1320 this->_M_insert_after(cbefore_begin(), 1321 std::forward<_Args>(__args)...); 1322 #if __cplusplus > 201402L 1323 return front(); 1324 #endif 1325 } 1326 1327 /** 1328 * @brief Add data to the front of the %forward_list. 1329 * @param __val Data to be added. 1330 * 1331 * This is a typical stack operation. The function creates an 1332 * element at the front of the %forward_list and assigns the given 1333 * data to it. Due to the nature of a %forward_list this operation 1334 * can be done in constant time, and does not invalidate iterators 1335 * and references. 1336 */ 1337 void 1338 push_front(const _Tp& __val) 1339 { this->_M_insert_after(cbefore_begin(), __val); } 1340 1341 /** 1342 * 1343 */ 1344 void 1345 push_front(_Tp&& __val) 1346 { this->_M_insert_after(cbefore_begin(), std::move(__val)); } 1347 1348 #if __glibcxx_containers_ranges // C++ >= 23 1349 /** 1350 * @brief Insert a range at the beginning of a forward_list. 1351 * @param __rg An input range with elements that are convertible to 1352 * the forward_list's value_type. 1353 * 1354 * The inserted elements will be in the same order as in the range, 1355 * so they are not reversed as would happen with a simple loop calling 1356 * `emplace_front` for each element of the range. 1357 * 1358 * No iterators to existing elements are invalidated by this function. 1359 * If the insertion fails due to an exception, no elements will be added 1360 * and so the list will be unchanged. 1361 * 1362 * @since C++23 1363 */ 1364 template<__detail::__container_compatible_range<_Tp> _Rg> 1365 void 1366 prepend_range(_Rg&& __rg) 1367 { 1368 forward_list __tmp(from_range, std::forward<_Rg>(__rg), 1369 get_allocator()); 1370 if (!__tmp.empty()) 1371 splice_after(before_begin(), __tmp); 1372 } 1373 #endif // containers_ranges 1374 1375 /** 1376 * @brief Removes first element. 1377 * 1378 * This is a typical stack operation. It shrinks the %forward_list 1379 * by one. Due to the nature of a %forward_list this operation can 1380 * be done in constant time, and only invalidates iterators/references 1381 * to the element being removed. 1382 * 1383 * Note that no data is returned, and if the first element's data 1384 * is needed, it should be retrieved before `pop_front()` is 1385 * called. 1386 */ 1387 void 1388 pop_front() 1389 { 1390 __glibcxx_requires_nonempty(); 1391 this->_M_erase_after(this->_M_impl._M_head._M_base_ptr()); 1392 } 1393 1394 /** 1395 * @brief Constructs object in %forward_list after the specified 1396 * iterator. 1397 * @param __pos A const_iterator into the %forward_list. 1398 * @param __args Arguments. 1399 * @return An iterator that points to the inserted data. 1400 * 1401 * This function will insert an object of type `T` constructed 1402 * with `T(std::forward<Args>(args)...)` after the specified 1403 * location. Due to the nature of a %forward_list this operation can 1404 * be done in constant time, and does not invalidate iterators 1405 * and references. 1406 */ 1407 template<typename... _Args> 1408 iterator 1409 emplace_after(const_iterator __pos, _Args&&... __args) 1410 { return iterator(this->_M_insert_after(__pos, 1411 std::forward<_Args>(__args)...)); } 1412 1413 /** 1414 * @brief Inserts given value into %forward_list after specified 1415 * iterator. 1416 * @param __pos An iterator into the %forward_list. 1417 * @param __val Data to be inserted. 1418 * @return An iterator that points to the inserted data. 1419 * 1420 * This function will insert a copy of the given value after 1421 * the specified location. Due to the nature of a %forward_list this 1422 * operation can be done in constant time, and does not 1423 * invalidate iterators and references. 1424 */ 1425 iterator 1426 insert_after(const_iterator __pos, const _Tp& __val) 1427 { return iterator(this->_M_insert_after(__pos, __val)); } 1428 1429 /** 1430 * 1431 */ 1432 iterator 1433 insert_after(const_iterator __pos, _Tp&& __val) 1434 { return iterator(this->_M_insert_after(__pos, std::move(__val))); } 1435 1436 /** 1437 * @brief Inserts a number of copies of given data into the 1438 * %forward_list. 1439 * @param __pos An iterator into the %forward_list. 1440 * @param __n Number of elements to be inserted. 1441 * @param __val Data to be inserted. 1442 * @return An iterator pointing to the last inserted copy of 1443 * `val` or `pos` if `n == 0`. 1444 * 1445 * This function will insert a specified number of copies of the 1446 * given data after the location specified by `pos`. 1447 * 1448 * This operation is linear in the number of elements inserted and 1449 * does not invalidate iterators and references. 1450 */ 1451 iterator 1452 insert_after(const_iterator __pos, size_type __n, const _Tp& __val); 1453 1454 /** 1455 * @brief Inserts a range into the %forward_list. 1456 * @param __pos An iterator into the %forward_list. 1457 * @param __first An input iterator. 1458 * @param __last An input iterator. 1459 * @return An iterator pointing to the last inserted element or 1460 * `__pos` if `__first == __last`. 1461 * 1462 * This function will insert copies of the data in the range 1463 * `[ __first, __last)` into the %forward_list after the 1464 * location specified by `__pos. 1465 * 1466 * This operation is linear in the number of elements inserted and 1467 * does not invalidate iterators and references. 1468 */ 1469 template<typename _InputIterator, 1470 typename = std::_RequireInputIter<_InputIterator>> 1471 iterator 1472 insert_after(const_iterator __pos, 1473 _InputIterator __first, _InputIterator __last); 1474 1475 /** 1476 * @brief Inserts the contents of an initializer_list into 1477 * %forward_list after the specified iterator. 1478 * @param __pos An iterator into the %forward_list. 1479 * @param __il An initializer_list of value_type. 1480 * @return An iterator pointing to the last inserted element 1481 * or `__pos` if `__il` is empty. 1482 * 1483 * This function will insert copies of the data in the 1484 * initializer_list `__il` into the %forward_list before the location 1485 * specified by `__pos`. 1486 * 1487 * This operation is linear in the number of elements inserted and 1488 * does not invalidate iterators and references. 1489 */ 1490 iterator 1491 insert_after(const_iterator __pos, std::initializer_list<_Tp> __il) 1492 { return insert_after(__pos, __il.begin(), __il.end()); } 1493 1494 #if __glibcxx_containers_ranges // C++ >= 23 1495 /** 1496 * @brief Insert a rangeinto a forward_list. 1497 * @param __position An iterator. 1498 * @param __rg An input range of elements that can be converted to 1499 * the forward_list's value type. 1500 * @return An iterator pointing to the last element inserted, 1501 * or `__position` if the range is empty. 1502 * 1503 * Inserts the elements of `__rg` after `__position`. 1504 * No iterators to existing elements are invalidated by this function. 1505 * If the insertion fails due to an exception, no elements will be added 1506 * and so the list will be unchanged. 1507 * 1508 * @since C++23 1509 */ 1510 template<__detail::__container_compatible_range<_Tp> _Rg> 1511 iterator 1512 insert_range_after(const_iterator __position, _Rg&& __rg) 1513 { 1514 forward_list __tmp(from_range, std::forward<_Rg>(__rg), 1515 get_allocator()); 1516 return _M_splice_after(__position, __tmp.before_begin(), __tmp.end()); 1517 } 1518 #endif // containers_ranges 1519 1520 /** 1521 * @brief Removes the element pointed to by the iterator following 1522 * `pos`. 1523 * @param __pos Iterator pointing before element to be erased. 1524 * @return An iterator pointing to the element following the one 1525 * that was erased, or `end()` if no such element exists. 1526 * 1527 * This function will erase the element at the given position and 1528 * thus shorten the %forward_list by one. 1529 * 1530 * Due to the nature of a %forward_list this operation can be done 1531 * in constant time, and only invalidates iterators/references to 1532 * the element being removed. The user is also cautioned that 1533 * this function only erases the element, and that if the element 1534 * is itself a pointer, the pointed-to memory is not touched in 1535 * any way. Managing the pointer is the user's responsibility. 1536 */ 1537 iterator 1538 erase_after(const_iterator __pos) 1539 { return iterator(this->_M_erase_after(__pos._M_const_cast()._M_node)); } 1540 1541 /** 1542 * @brief Remove a range of elements. 1543 * @param __pos Iterator pointing before the first element to be 1544 * erased. 1545 * @param __last Iterator pointing to one past the last element to be 1546 * erased. 1547 * @return `__last` 1548 * 1549 * This function will erase the elements in the range 1550 * `(__pos,__last)` and shorten the %forward_list accordingly. 1551 * 1552 * This operation is linear time in the size of the range and only 1553 * invalidates iterators/references to the element being removed. 1554 * 1555 * The user is also cautioned that this function only erases the 1556 * elements, and that if the elements themselves are pointers, the 1557 * pointed-to memory is not touched in any way. Managing the pointer 1558 * is the user's responsibility. 1559 */ 1560 iterator 1561 erase_after(const_iterator __pos, const_iterator __last) 1562 { 1563 return iterator(this->_M_erase_after(__pos._M_const_cast()._M_node, 1564 __last._M_const_cast()._M_node)); 1565 } 1566 1567 /** 1568 * @brief Swaps data with another %forward_list. 1569 * @param __list A %forward_list of the same element and allocator 1570 * types. 1571 * 1572 * This exchanges the elements between two lists in constant 1573 * time. Note that the global `std::swap()` function is 1574 * overloaded such that `std::swap(l1, l2)` will feed to this 1575 * function. 1576 * 1577 * Whether the allocators are swapped depends on the allocator traits. 1578 */ 1579 void 1580 swap(forward_list& __list) noexcept 1581 { 1582 std::swap(this->_M_impl._M_head._M_next, 1583 __list._M_impl._M_head._M_next); 1584 _Node_alloc_traits::_S_on_swap(this->_M_get_Node_allocator(), 1585 __list._M_get_Node_allocator()); 1586 } 1587 1588 /** 1589 * @brief Resizes the %forward_list to the specified number of 1590 * elements. 1591 * @param __sz Number of elements the %forward_list should contain. 1592 * 1593 * This function will %resize the %forward_list to the specified 1594 * number of elements. If the number is smaller than the 1595 * %forward_list's current number of elements the %forward_list 1596 * is truncated, otherwise the %forward_list is extended and the 1597 * new elements are default constructed. 1598 */ 1599 void 1600 resize(size_type __sz); 1601 1602 /** 1603 * @brief Resizes the %forward_list to the specified number of 1604 * elements. 1605 * @param __sz Number of elements the %forward_list should contain. 1606 * @param __val Data with which new elements should be populated. 1607 * 1608 * This function will %resize the %forward_list to the specified 1609 * number of elements. If the number is smaller than the 1610 * %forward_list's current number of elements the %forward_list 1611 * is truncated, otherwise the %forward_list is extended and new 1612 * elements are populated with given data. 1613 */ 1614 void 1615 resize(size_type __sz, const value_type& __val); 1616 1617 /** 1618 * @brief Erases all the elements. 1619 * 1620 * Note that this function only erases 1621 * the elements, and that if the elements themselves are 1622 * pointers, the pointed-to memory is not touched in any way. 1623 * Managing the pointer is the user's responsibility. 1624 */ 1625 void 1626 clear() noexcept 1627 { this->_M_erase_after(this->_M_impl._M_head._M_base_ptr(), nullptr); } 1628 1629 // 23.3.4.6 forward_list operations: 1630 1631 /** 1632 * @brief Insert contents of another %forward_list. 1633 * @param __pos Iterator referencing the element to insert after. 1634 * @param __list Source list. 1635 * 1636 * The elements of `list` are inserted in constant time after 1637 * the element referenced by `pos`. `list` becomes an empty 1638 * list. 1639 * 1640 * Requires `this != &x`. 1641 */ 1642 void 1643 splice_after(const_iterator __pos, forward_list&& __list) noexcept 1644 { 1645 if (!__list.empty()) 1646 _M_splice_after(__pos, __list.before_begin(), __list.end()); 1647 } 1648 1649 void 1650 splice_after(const_iterator __pos, forward_list& __list) noexcept 1651 { splice_after(__pos, std::move(__list)); } 1652 1653 /** 1654 * @brief Insert element from another %forward_list. 1655 * @param __pos Iterator referencing the element to insert after. 1656 * @param __list Source list. 1657 * @param __i Iterator referencing the element before the element 1658 * to move. 1659 * 1660 * Removes the element in list `__list` referenced by `__i` and 1661 * inserts it into the current list after `__pos`. 1662 */ 1663 void 1664 splice_after(const_iterator __pos, forward_list&& __list, 1665 const_iterator __i) noexcept; 1666 1667 void 1668 splice_after(const_iterator __pos, forward_list& __list, 1669 const_iterator __i) noexcept 1670 { splice_after(__pos, std::move(__list), __i); } 1671 1672 /** 1673 * @brief Insert range from another %forward_list. 1674 * @param __pos Iterator referencing the element to insert after. 1675 * @param __list Source list. 1676 * @param __before Iterator referencing before the start of range 1677 * in `__list`. 1678 * @param __last Iterator referencing the end of range in `__list`. 1679 * 1680 * Removes elements in the range `(__before,__last)` and inserts them 1681 * after `__pos` in constant time. 1682 * 1683 * Undefined if `__pos` is in `(__before,__last)`. 1684 * @{ 1685 */ 1686 void 1687 splice_after(const_iterator __pos, forward_list&&, 1688 const_iterator __before, const_iterator __last) noexcept 1689 { _M_splice_after(__pos, __before, __last); } 1690 1691 void 1692 splice_after(const_iterator __pos, forward_list&, 1693 const_iterator __before, const_iterator __last) noexcept 1694 { _M_splice_after(__pos, __before, __last); } 1695 /// @} 1696 1697 private: 1698 #ifdef __glibcxx_list_remove_return_type // C++20 && HOSTED 1699 using __remove_return_type = size_type; 1700 # define _GLIBCXX_FWDLIST_REMOVE_RETURN_TYPE_TAG \ 1701 __attribute__((__abi_tag__("__cxx20"))) 1702 #else 1703 using __remove_return_type = void; 1704 # define _GLIBCXX_FWDLIST_REMOVE_RETURN_TYPE_TAG 1705 #endif 1706 public: 1707 1708 /** 1709 * @brief Remove all elements equal to value. 1710 * @param __val The value to remove. 1711 * 1712 * Removes every element in the list equal to `__val`. 1713 * Remaining elements stay in list order. Note that this 1714 * function only erases the elements, and that if the elements 1715 * themselves are pointers, the pointed-to memory is not 1716 * touched in any way. Managing the pointer is the user's 1717 * responsibility. 1718 */ 1719 _GLIBCXX_FWDLIST_REMOVE_RETURN_TYPE_TAG 1720 __remove_return_type 1721 remove(const _Tp& __val); 1722 1723 /** 1724 * @brief Remove all elements satisfying a predicate. 1725 * @param __pred Unary predicate function or object. 1726 * 1727 * Removes every element in the list for which the predicate 1728 * returns true. Remaining elements stay in list order. Note 1729 * that this function only erases the elements, and that if the 1730 * elements themselves are pointers, the pointed-to memory is 1731 * not touched in any way. Managing the pointer is the user's 1732 * responsibility. 1733 */ 1734 template<typename _Pred> 1735 __remove_return_type 1736 remove_if(_Pred __pred); 1737 1738 /** 1739 * @brief Remove consecutive duplicate elements. 1740 * 1741 * For each consecutive set of elements with the same value, 1742 * remove all but the first one. Remaining elements stay in 1743 * list order. Note that this function only erases the 1744 * elements, and that if the elements themselves are pointers, 1745 * the pointed-to memory is not touched in any way. Managing 1746 * the pointer is the user's responsibility. 1747 */ 1748 _GLIBCXX_FWDLIST_REMOVE_RETURN_TYPE_TAG 1749 __remove_return_type 1750 unique() 1751 { return unique(std::equal_to<_Tp>()); } 1752 1753 #undef _GLIBCXX_FWDLIST_REMOVE_RETURN_TYPE_TAG 1754 1755 /** 1756 * @brief Remove consecutive elements satisfying a predicate. 1757 * @param __binary_pred Binary predicate function or object. 1758 * 1759 * For each consecutive set of elements [first,last) that 1760 * satisfy predicate(first,i) where i is an iterator in 1761 * [first,last), remove all but the first one. Remaining 1762 * elements stay in list order. Note that this function only 1763 * erases the elements, and that if the elements themselves are 1764 * pointers, the pointed-to memory is not touched in any way. 1765 * Managing the pointer is the user's responsibility. 1766 */ 1767 template<typename _BinPred> 1768 __remove_return_type 1769 unique(_BinPred __binary_pred); 1770 1771 /** 1772 * @brief Merge sorted lists. 1773 * @param __list Sorted list to merge. 1774 * 1775 * Assumes that both `__list` and this list are sorted according to 1776 * operator<(). Merges elements of `__list` into this list in 1777 * sorted order, leaving `__list` empty when complete. Elements in 1778 * this list precede elements in `__list` that are equal. 1779 */ 1780 void 1781 merge(forward_list&& __list) 1782 { merge(std::move(__list), std::less<_Tp>()); } 1783 1784 void 1785 merge(forward_list& __list) 1786 { merge(std::move(__list)); } 1787 1788 /** 1789 * @brief Merge sorted lists according to comparison function. 1790 * @param __list Sorted list to merge. 1791 * @param __comp Comparison function defining sort order. 1792 * 1793 * Assumes that both `__list` and this list are sorted according to 1794 * comp. Merges elements of `__list` into this list 1795 * in sorted order, leaving `__list` empty when complete. Elements 1796 * in this list precede elements in `__list` that are equivalent 1797 * according to comp(). 1798 */ 1799 template<typename _Comp> 1800 void 1801 merge(forward_list&& __list, _Comp __comp); 1802 1803 template<typename _Comp> 1804 void 1805 merge(forward_list& __list, _Comp __comp) 1806 { merge(std::move(__list), __comp); } 1807 1808 /** 1809 * @brief Sort the elements of the list. 1810 * 1811 * Sorts the elements of this list in NlogN time. Equivalent 1812 * elements remain in list order. 1813 */ 1814 void 1815 sort() 1816 { sort(std::less<_Tp>()); } 1817 1818 /** 1819 * @brief Sort the forward_list using a comparison function. 1820 * 1821 * Sorts the elements of this list in NlogN time. Equivalent 1822 * elements remain in list order. 1823 */ 1824 template<typename _Comp> 1825 void 1826 sort(_Comp __comp); 1827 1828 /** 1829 * @brief Reverse the elements in list. 1830 * 1831 * Reverse the order of elements in the list in linear time. 1832 */ 1833 void 1834 reverse() noexcept 1835 { this->_M_impl._M_head._M_reverse_after(); } 1836 1837 private: 1838 // Called by the range constructor to implement [23.3.4.2]/9 1839 template<typename _InputIterator> 1840 void 1841 _M_range_initialize(_InputIterator __first, _InputIterator __last); 1842 1843 // Called by forward_list(n,v,a), and the range constructor when it 1844 // turns out to be the same thing. 1845 void 1846 _M_fill_initialize(size_type __n, const value_type& __value); 1847 1848 // Called by splice_after and insert_after. 1849 iterator 1850 _M_splice_after(const_iterator __pos, const_iterator __before, 1851 const_iterator __last); 1852 1853 // Called by forward_list(n). 1854 void 1855 _M_default_initialize(size_type __n); 1856 1857 // Called by resize(sz). 1858 void 1859 _M_default_insert_after(const_iterator __pos, size_type __n); 1860 1861 #if ! _GLIBCXX_INLINE_VERSION 1862 #pragma GCC diagnostic push 1863 #pragma GCC diagnostic ignored "-Wc++17-extensions" // if constexpr 1864 // XXX GLIBCXX_ABI Deprecated 1865 // These members are unused by std::forward_list now, but we keep them 1866 // here so that an explicit instantiation will define them. 1867 // This ensures that explicit instantiations still define these symbols, 1868 // so that explicit instantiation declarations of std::forward_list that 1869 // were compiled with old versions of GCC can still find these symbols. 1870 1871 // Use 'if constexpr' so that the functions don't do anything for 1872 // specializations using _Node_traits<T, fancy-pointer>, because any 1873 // old code referencing these symbols wasn't using the fancy-pointer 1874 // specializations. 1875 1876 void 1877 _M_move_assign(forward_list&& __list, true_type) noexcept 1878 { 1879 #if _GLIBCXX_USE_ALLOC_PTR_FOR_FWD_LIST 1880 if constexpr (is_same<typename _Alloc_traits::pointer, _Tp*>::value) 1881 #endif 1882 { 1883 clear(); 1884 this->_M_impl._M_head._M_next = __list._M_impl._M_head._M_next; 1885 __list._M_impl._M_head._M_next = nullptr; 1886 std::__alloc_on_move(this->_M_get_Node_allocator(), 1887 __list._M_get_Node_allocator()); 1888 } 1889 } 1890 1891 void 1892 _M_move_assign(forward_list&& __list, false_type) 1893 { 1894 #if _GLIBCXX_USE_ALLOC_PTR_FOR_FWD_LIST 1895 if constexpr (is_same<typename _Alloc_traits::pointer, _Tp*>::value) 1896 #endif 1897 { 1898 if (__list._M_get_Node_allocator() == this->_M_get_Node_allocator()) 1899 _M_move_assign(std::move(__list), true_type()); 1900 else 1901 // The rvalue's allocator cannot be moved, or is not equal, 1902 // so we need to individually move each element. 1903 this->assign(std::make_move_iterator(__list.begin()), 1904 std::make_move_iterator(__list.end())); 1905 } 1906 } 1907 1908 void 1909 _M_assign_n(size_type __n, const _Tp& __val, true_type) 1910 { 1911 #if _GLIBCXX_USE_ALLOC_PTR_FOR_FWD_LIST 1912 if constexpr (is_same<typename _Alloc_traits::pointer, _Tp*>::value) 1913 #endif 1914 { 1915 auto __prev = before_begin(); 1916 auto __curr = begin(); 1917 auto __end = end(); 1918 while (__curr != __end && __n > 0) 1919 { 1920 *__curr = __val; 1921 ++__prev; 1922 ++__curr; 1923 --__n; 1924 } 1925 if (__n > 0) 1926 insert_after(__prev, __n, __val); 1927 else if (__curr != __end) 1928 erase_after(__prev, __end); 1929 } 1930 } 1931 1932 void 1933 _M_assign_n(size_type __n, const _Tp& __val, false_type) 1934 { 1935 #if _GLIBCXX_USE_ALLOC_PTR_FOR_FWD_LIST 1936 if constexpr (is_same<typename _Alloc_traits::pointer, _Tp*>::value) 1937 #endif 1938 { 1939 clear(); 1940 insert_after(cbefore_begin(), __n, __val); 1941 } 1942 } 1943 #pragma GCC diagnostic pop 1944 #endif // ! _GLIBCXX_INLINE_VERSION 1945 }; 1946 1947 #if __cpp_deduction_guides >= 201606 1948 template<typename _InputIterator, typename _ValT 1949 = typename iterator_traits<_InputIterator>::value_type, 1950 typename _Allocator = allocator<_ValT>, 1951 typename = _RequireInputIter<_InputIterator>, 1952 typename = _RequireAllocator<_Allocator>> 1953 forward_list(_InputIterator, _InputIterator, _Allocator = _Allocator()) 1954 -> forward_list<_ValT, _Allocator>; 1955 1956 #if __glibcxx_containers_ranges // C++ >= 23 1957 template<ranges::input_range _Rg, 1958 typename _Allocator = allocator<ranges::range_value_t<_Rg>>> 1959 forward_list(from_range_t, _Rg&&, _Allocator = _Allocator()) 1960 -> forward_list<ranges::range_value_t<_Rg>, _Allocator>; 1961 #endif 1962 #endif 1963 1964 /** 1965 * @brief Forward list equality comparison. 1966 * @param __lx A %forward_list 1967 * @param __ly A %forward_list of the same type as `__lx`. 1968 * @return True iff the elements of the forward lists are equal. 1969 * 1970 * This is an equivalence relation. It is linear in the number of 1971 * elements of the forward lists. Deques are considered equivalent 1972 * if corresponding elements compare equal. 1973 */ 1974 template<typename _Tp, typename _Alloc> 1975 [[__nodiscard__]] 1976 bool 1977 operator==(const forward_list<_Tp, _Alloc>& __lx, 1978 const forward_list<_Tp, _Alloc>& __ly); 1979 1980 #if __cpp_lib_three_way_comparison 1981 /** 1982 * @brief Forward list ordering relation. 1983 * @param __x A `forward_list`. 1984 * @param __y A `forward_list` of the same type as `__x`. 1985 * @return A value indicating whether `__x` is less than, equal to, 1986 * greater than, or incomparable with `__y`. 1987 * 1988 * See `std::lexicographical_compare_three_way()` for how the determination 1989 * is made. This operator is used to synthesize relational operators like 1990 * `<` and `>=` etc. 1991 */ 1992 template<typename _Tp, typename _Alloc> 1993 [[nodiscard]] 1994 inline __detail::__synth3way_t<_Tp> 1995 operator<=>(const forward_list<_Tp, _Alloc>& __x, 1996 const forward_list<_Tp, _Alloc>& __y) 1997 { 1998 return std::lexicographical_compare_three_way(__x.begin(), __x.end(), 1999 __y.begin(), __y.end(), 2000 __detail::__synth3way); 2001 } 2002 #else 2003 /** 2004 * @brief Forward list ordering relation. 2005 * @param __lx A %forward_list. 2006 * @param __ly A %forward_list of the same type as `__lx`. 2007 * @return True iff `__lx` is lexicographically less than `__ly`. 2008 * 2009 * This is a total ordering relation. It is linear in the number of 2010 * elements of the forward lists. The elements must be comparable 2011 * with `<`. 2012 * 2013 * See std::lexicographical_compare() for how the determination is made. 2014 */ 2015 template<typename _Tp, typename _Alloc> 2016 [[__nodiscard__]] 2017 inline bool 2018 operator<(const forward_list<_Tp, _Alloc>& __lx, 2019 const forward_list<_Tp, _Alloc>& __ly) 2020 { return std::lexicographical_compare(__lx.cbegin(), __lx.cend(), 2021 __ly.cbegin(), __ly.cend()); } 2022 2023 /// Based on operator== 2024 template<typename _Tp, typename _Alloc> 2025 [[__nodiscard__]] 2026 inline bool 2027 operator!=(const forward_list<_Tp, _Alloc>& __lx, 2028 const forward_list<_Tp, _Alloc>& __ly) 2029 { return !(__lx == __ly); } 2030 2031 /// Based on operator< 2032 template<typename _Tp, typename _Alloc> 2033 [[__nodiscard__]] 2034 inline bool 2035 operator>(const forward_list<_Tp, _Alloc>& __lx, 2036 const forward_list<_Tp, _Alloc>& __ly) 2037 { return (__ly < __lx); } 2038 2039 /// Based on operator< 2040 template<typename _Tp, typename _Alloc> 2041 [[__nodiscard__]] 2042 inline bool 2043 operator>=(const forward_list<_Tp, _Alloc>& __lx, 2044 const forward_list<_Tp, _Alloc>& __ly) 2045 { return !(__lx < __ly); } 2046 2047 /// Based on operator< 2048 template<typename _Tp, typename _Alloc> 2049 [[__nodiscard__]] 2050 inline bool 2051 operator<=(const forward_list<_Tp, _Alloc>& __lx, 2052 const forward_list<_Tp, _Alloc>& __ly) 2053 { return !(__ly < __lx); } 2054 #endif // three-way comparison 2055 2056 /// See std::forward_list::swap(). 2057 template<typename _Tp, typename _Alloc> 2058 inline void 2059 swap(forward_list<_Tp, _Alloc>& __lx, 2060 forward_list<_Tp, _Alloc>& __ly) 2061 noexcept(noexcept(__lx.swap(__ly))) 2062 { __lx.swap(__ly); } 2063 2064 _GLIBCXX_END_NAMESPACE_CONTAINER 2065 _GLIBCXX_END_NAMESPACE_VERSION 2066 } // namespace std 2067 2068 #endif // _FORWARD_LIST_H
