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
58namespace 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
342namespace __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, before: __list.before_begin(), last: __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
2069