libstdc++
forward_list.h
Go to the documentation of this file.
1// <forward_list.h> -*- C++ -*-
2
3// Copyright (C) 2008-2024 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>
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 <ext/alloc_traits.h>
44#include <ext/aligned_buffer.h>
45#if __glibcxx_ranges_to_container // C++ >= 23
46# include <bits/ranges_base.h> // ranges::begin, ranges::distance etc.
47# include <bits/ranges_util.h> // ranges::subrange
48#endif
49
50namespace std _GLIBCXX_VISIBILITY(default)
51{
52_GLIBCXX_BEGIN_NAMESPACE_VERSION
53_GLIBCXX_BEGIN_NAMESPACE_CONTAINER
54
55 /**
56 * @brief A helper basic node class for %forward_list.
57 * This is just a linked list with nothing inside it.
58 * There are purely list shuffling utility methods here.
59 */
61 {
62 _Fwd_list_node_base() = default;
64 : _M_next(__x._M_next)
65 { __x._M_next = nullptr; }
66
68 _Fwd_list_node_base& operator=(const _Fwd_list_node_base&) = delete;
69
71 operator=(_Fwd_list_node_base&& __x) noexcept
72 {
73 _M_next = __x._M_next;
74 __x._M_next = nullptr;
75 return *this;
76 }
77
78 _Fwd_list_node_base* _M_next = nullptr;
79
81 _M_transfer_after(_Fwd_list_node_base* __begin,
82 _Fwd_list_node_base* __end) noexcept
83 {
84 _Fwd_list_node_base* __keep = __begin->_M_next;
85 if (__end)
86 {
87 __begin->_M_next = __end->_M_next;
88 __end->_M_next = _M_next;
89 }
90 else
91 __begin->_M_next = nullptr;
92 _M_next = __keep;
93 return __end;
94 }
95
96 void
97 _M_reverse_after() noexcept
98 {
99 _Fwd_list_node_base* __tail = _M_next;
100 if (!__tail)
101 return;
102 while (_Fwd_list_node_base* __temp = __tail->_M_next)
103 {
104 _Fwd_list_node_base* __keep = _M_next;
105 _M_next = __temp;
106 __tail->_M_next = __temp->_M_next;
107 _M_next->_M_next = __keep;
108 }
109 }
110 };
111
112 /**
113 * @brief A helper node class for %forward_list.
114 * This is just a linked list with uninitialized storage for a
115 * data value in each node.
116 * There is a sorting utility method.
117 */
118 template<typename _Tp>
120 : public _Fwd_list_node_base
121 {
122 _Fwd_list_node() = default;
123
124 __gnu_cxx::__aligned_buffer<_Tp> _M_storage;
125
126 _Tp*
127 _M_valptr() noexcept
128 { return _M_storage._M_ptr(); }
129
130 const _Tp*
131 _M_valptr() const noexcept
132 { return _M_storage._M_ptr(); }
133 };
134
135 /**
136 * @brief A forward_list::iterator.
137 *
138 * All the functions are op overloads.
139 */
140 template<typename _Tp>
142 {
143 typedef _Fwd_list_iterator<_Tp> _Self;
144 typedef _Fwd_list_node<_Tp> _Node;
145
146 typedef _Tp value_type;
147 typedef _Tp* pointer;
148 typedef _Tp& reference;
149 typedef ptrdiff_t difference_type;
151
152 _Fwd_list_iterator() noexcept
153 : _M_node() { }
154
155 explicit
157 : _M_node(__n) { }
158
159 [[__nodiscard__]]
160 reference
161 operator*() const noexcept
162 { return *static_cast<_Node*>(this->_M_node)->_M_valptr(); }
163
164 [[__nodiscard__]]
165 pointer
166 operator->() const noexcept
167 { return static_cast<_Node*>(this->_M_node)->_M_valptr(); }
168
169 _Self&
170 operator++() noexcept
171 {
172 _M_node = _M_node->_M_next;
173 return *this;
174 }
175
176 _Self
177 operator++(int) noexcept
178 {
179 _Self __tmp(*this);
180 _M_node = _M_node->_M_next;
181 return __tmp;
182 }
183
184 /**
185 * @brief Forward list iterator equality comparison.
186 */
187 [[__nodiscard__]]
188 friend bool
189 operator==(const _Self& __x, const _Self& __y) noexcept
190 { return __x._M_node == __y._M_node; }
191
192#if __cpp_impl_three_way_comparison < 201907L
193 /**
194 * @brief Forward list iterator inequality comparison.
195 */
196 [[__nodiscard__]]
197 friend bool
198 operator!=(const _Self& __x, const _Self& __y) noexcept
199 { return __x._M_node != __y._M_node; }
200#endif
201
202 _Self
203 _M_next() const noexcept
204 {
205 if (_M_node)
206 return _Fwd_list_iterator(_M_node->_M_next);
207 else
208 return _Fwd_list_iterator(nullptr);
209 }
210
211 _Fwd_list_node_base* _M_node;
212 };
213
214 /**
215 * @brief A forward_list::const_iterator.
216 *
217 * All the functions are op overloads.
218 */
219 template<typename _Tp>
221 {
222 typedef _Fwd_list_const_iterator<_Tp> _Self;
223 typedef const _Fwd_list_node<_Tp> _Node;
224 typedef _Fwd_list_iterator<_Tp> iterator;
225
226 typedef _Tp value_type;
227 typedef const _Tp* pointer;
228 typedef const _Tp& reference;
229 typedef ptrdiff_t difference_type;
231
232 _Fwd_list_const_iterator() noexcept
233 : _M_node() { }
234
235 explicit
237 : _M_node(__n) { }
238
239 _Fwd_list_const_iterator(const iterator& __iter) noexcept
240 : _M_node(__iter._M_node) { }
241
242 [[__nodiscard__]]
243 reference
244 operator*() const noexcept
245 { return *static_cast<_Node*>(this->_M_node)->_M_valptr(); }
246
247 [[__nodiscard__]]
248 pointer
249 operator->() const noexcept
250 { return static_cast<_Node*>(this->_M_node)->_M_valptr(); }
251
252 _Self&
253 operator++() noexcept
254 {
255 _M_node = _M_node->_M_next;
256 return *this;
257 }
258
259 _Self
260 operator++(int) noexcept
261 {
262 _Self __tmp(*this);
263 _M_node = _M_node->_M_next;
264 return __tmp;
265 }
266
267 /**
268 * @brief Forward list const_iterator equality comparison.
269 */
270 [[__nodiscard__]]
271 friend bool
272 operator==(const _Self& __x, const _Self& __y) noexcept
273 { return __x._M_node == __y._M_node; }
274
275#if __cpp_impl_three_way_comparison < 201907L
276 /**
277 * @brief Forward list const_iterator inequality comparison.
278 */
279 [[__nodiscard__]]
280 friend bool
281 operator!=(const _Self& __x, const _Self& __y) noexcept
282 { return __x._M_node != __y._M_node; }
283#endif
284
285 _Self
286 _M_next() const noexcept
287 {
288 if (this->_M_node)
289 return _Fwd_list_const_iterator(_M_node->_M_next);
290 else
291 return _Fwd_list_const_iterator(nullptr);
292 }
293
294 const _Fwd_list_node_base* _M_node;
295 };
296
297 /**
298 * @brief Base class for %forward_list.
299 */
300 template<typename _Tp, typename _Alloc>
302 {
303 protected:
304 typedef __alloc_rebind<_Alloc, _Fwd_list_node<_Tp>> _Node_alloc_type;
306
307 struct _Fwd_list_impl
308 : public _Node_alloc_type
309 {
310 _Fwd_list_node_base _M_head;
311
312 _Fwd_list_impl()
314 : _Node_alloc_type(), _M_head()
315 { }
316
317 _Fwd_list_impl(_Fwd_list_impl&&) = default;
318
319 _Fwd_list_impl(_Fwd_list_impl&& __fl, _Node_alloc_type&& __a)
320 : _Node_alloc_type(std::move(__a)), _M_head(std::move(__fl._M_head))
321 { }
322
323 _Fwd_list_impl(_Node_alloc_type&& __a)
324 : _Node_alloc_type(std::move(__a)), _M_head()
325 { }
326 };
327
328 _Fwd_list_impl _M_impl;
329
330 public:
331 typedef _Fwd_list_iterator<_Tp> iterator;
333 typedef _Fwd_list_node<_Tp> _Node;
334
335 _Node_alloc_type&
336 _M_get_Node_allocator() noexcept
337 { return this->_M_impl; }
338
339 const _Node_alloc_type&
340 _M_get_Node_allocator() const noexcept
341 { return this->_M_impl; }
342
343 _Fwd_list_base() = default;
344
345 _Fwd_list_base(_Node_alloc_type&& __a)
346 : _M_impl(std::move(__a)) { }
347
348 // When allocators are always equal.
349 _Fwd_list_base(_Fwd_list_base&& __lst, _Node_alloc_type&& __a,
351 : _M_impl(std::move(__lst._M_impl), std::move(__a))
352 { }
353
354 // When allocators are not always equal.
355 _Fwd_list_base(_Fwd_list_base&& __lst, _Node_alloc_type&& __a);
356
357 _Fwd_list_base(_Fwd_list_base&&) = default;
358
360 { _M_erase_after(&_M_impl._M_head, nullptr); }
361
362 protected:
363 _Node*
364 _M_get_node()
365 {
366 auto __ptr = _Node_alloc_traits::allocate(_M_get_Node_allocator(), 1);
367 return std::__to_address(__ptr);
368 }
369
370 template<typename... _Args>
371 _Node*
372 _M_create_node(_Args&&... __args)
373 {
374 _Node* __node = this->_M_get_node();
375 __try
376 {
377 ::new ((void*)__node) _Node;
378 _Node_alloc_traits::construct(_M_get_Node_allocator(),
379 __node->_M_valptr(),
380 std::forward<_Args>(__args)...);
381 }
382 __catch(...)
383 {
384 this->_M_put_node(__node);
385 __throw_exception_again;
386 }
387 return __node;
388 }
389
390 template<typename... _Args>
392 _M_insert_after(const_iterator __pos, _Args&&... __args);
393
394 void
395 _M_put_node(_Node* __p)
396 {
397 typedef typename _Node_alloc_traits::pointer _Ptr;
398 auto __ptr = std::pointer_traits<_Ptr>::pointer_to(*__p);
399 _Node_alloc_traits::deallocate(_M_get_Node_allocator(), __ptr, 1);
400 }
401
403 _M_erase_after(_Fwd_list_node_base* __pos);
404
406 _M_erase_after(_Fwd_list_node_base* __pos,
407 _Fwd_list_node_base* __last);
408 };
409
410 /**
411 * @brief A standard container with linear time access to elements,
412 * and fixed time insertion/deletion at any point in the sequence.
413 *
414 * @ingroup sequences
415 * @headerfile forward_list
416 * @since C++11
417 *
418 * @tparam _Tp Type of element.
419 * @tparam _Alloc Allocator type, defaults to allocator<_Tp>.
420 *
421 * Meets the requirements of a <a href="tables.html#65">container</a>, a
422 * <a href="tables.html#67">sequence</a>, including the
423 * <a href="tables.html#68">optional sequence requirements</a> with the
424 * %exception of @c at and @c operator[].
425 *
426 * This is a @e singly @e linked %list. Traversal up the
427 * %list requires linear time, but adding and removing elements (or
428 * @e nodes) is done in constant time, regardless of where the
429 * change takes place. Unlike std::vector and std::deque,
430 * random-access iterators are not provided, so subscripting ( @c
431 * [] ) access is not allowed. For algorithms which only need
432 * sequential access, this lack makes no difference.
433 *
434 * Also unlike the other standard containers, std::forward_list provides
435 * specialized algorithms %unique to linked lists, such as
436 * splicing, sorting, and in-place reversal.
437 */
438 template<typename _Tp, typename _Alloc = allocator<_Tp>>
439 class forward_list : private _Fwd_list_base<_Tp, _Alloc>
440 {
441 static_assert(is_same<typename remove_cv<_Tp>::type, _Tp>::value,
442 "std::forward_list must have a non-const, non-volatile value_type");
443#if __cplusplus > 201703L || defined __STRICT_ANSI__
445 "std::forward_list must have the same value_type as its allocator");
446#endif
447
448 private:
451 typedef typename _Base::_Node _Node;
452 typedef typename _Base::_Node_alloc_type _Node_alloc_type;
455
456 public:
457 // types:
458 typedef _Tp value_type;
459 typedef typename _Alloc_traits::pointer pointer;
460 typedef typename _Alloc_traits::const_pointer const_pointer;
461 typedef value_type& reference;
462 typedef const value_type& const_reference;
463
464 typedef typename _Base::iterator iterator;
465 typedef typename _Base::const_iterator const_iterator;
466 typedef std::size_t size_type;
467 typedef std::ptrdiff_t difference_type;
468 typedef _Alloc allocator_type;
469
470 // 23.3.4.2 construct/copy/destroy:
471
472 /**
473 * @brief Creates a %forward_list with no elements.
474 */
475 forward_list() = default;
476
477 /**
478 * @brief Creates a %forward_list with no elements.
479 * @param __al An allocator object.
480 */
481 explicit
482 forward_list(const _Alloc& __al) noexcept
483 : _Base(_Node_alloc_type(__al))
484 { }
485
486 /**
487 * @brief Copy constructor with allocator argument.
488 * @param __list Input list to copy.
489 * @param __al An allocator object.
490 */
492 const __type_identity_t<_Alloc>& __al)
493 : _Base(_Node_alloc_type(__al))
494 { _M_range_initialize(__list.begin(), __list.end()); }
495
496 private:
497 forward_list(forward_list&& __list, _Node_alloc_type&& __al,
499 : _Base(std::move(__list), std::move(__al))
500 {
501 // If __list is not empty it means its allocator is not equal to __a,
502 // so we need to move from each element individually.
504 std::__make_move_if_noexcept_iterator(__list.begin()),
505 std::__make_move_if_noexcept_iterator(__list.end()));
506 }
507
508 forward_list(forward_list&& __list, _Node_alloc_type&& __al,
509 true_type)
510 noexcept
511 : _Base(std::move(__list), _Node_alloc_type(__al), true_type{})
512 { }
513
514 public:
515 /**
516 * @brief Move constructor with allocator argument.
517 * @param __list Input list to move.
518 * @param __al An allocator object.
519 */
521 const __type_identity_t<_Alloc>& __al)
522 noexcept(_Node_alloc_traits::_S_always_equal())
523 : forward_list(std::move(__list), _Node_alloc_type(__al),
524 typename _Node_alloc_traits::is_always_equal{})
525 { }
526
527 /**
528 * @brief Creates a %forward_list with default constructed elements.
529 * @param __n The number of elements to initially create.
530 * @param __al An allocator object.
531 *
532 * This constructor creates the %forward_list with @a __n default
533 * constructed elements.
534 */
535 explicit
536 forward_list(size_type __n, const _Alloc& __al = _Alloc())
537 : _Base(_Node_alloc_type(__al))
538 { _M_default_initialize(__n); }
539
540 /**
541 * @brief Creates a %forward_list with copies of an exemplar element.
542 * @param __n The number of elements to initially create.
543 * @param __value An element to copy.
544 * @param __al An allocator object.
545 *
546 * This constructor fills the %forward_list with @a __n copies of
547 * @a __value.
548 */
549 forward_list(size_type __n, const _Tp& __value,
550 const _Alloc& __al = _Alloc())
551 : _Base(_Node_alloc_type(__al))
552 { _M_fill_initialize(__n, __value); }
553
554 /**
555 * @brief Builds a %forward_list from a range.
556 * @param __first An input iterator.
557 * @param __last An input iterator.
558 * @param __al An allocator object.
559 *
560 * Create a %forward_list consisting of copies of the elements from
561 * [@a __first,@a __last). This is linear in N (where N is
562 * distance(@a __first,@a __last)).
563 */
564 template<typename _InputIterator,
565 typename = std::_RequireInputIter<_InputIterator>>
566 forward_list(_InputIterator __first, _InputIterator __last,
567 const _Alloc& __al = _Alloc())
568 : _Base(_Node_alloc_type(__al))
569 { _M_range_initialize(__first, __last); }
570
571#if __glibcxx_ranges_to_container // C++ >= 23
572 /**
573 * @brief Construct a forward_list from a range.
574 * @param __rg An input range with elements that are convertible to
575 * the forward_list's value_type.
576 * @param __a An allocator.
577 *
578 * @since C++23
579 */
580 template<__detail::__container_compatible_range<_Tp> _Rg>
581 forward_list(from_range_t, _Rg&& __rg, const _Alloc& __a = _Alloc())
582 : _Base(_Node_alloc_type(__a))
583 {
584 _Node_base* __to = &this->_M_impl._M_head;
585 auto __first = ranges::begin(__rg);
586 const auto __last = ranges::end(__rg);
587 for (; __first != __last; ++__first)
588 {
589 __to->_M_next = this->_M_create_node(*__first);
590 __to = __to->_M_next;
591 }
592 }
593#endif // ranges_to_container
594
595 /**
596 * @brief The %forward_list copy constructor.
597 * @param __list A %forward_list of identical element and allocator
598 * types.
599 */
601 : _Base(_Node_alloc_traits::_S_select_on_copy(
602 __list._M_get_Node_allocator()))
603 { _M_range_initialize(__list.begin(), __list.end()); }
604
605 /**
606 * @brief The %forward_list move constructor.
607 * @param __list A %forward_list of identical element and allocator
608 * types.
609 *
610 * The newly-created %forward_list contains the exact contents of the
611 * moved instance. The contents of the moved instance are a valid, but
612 * unspecified %forward_list.
613 */
615
616 /**
617 * @brief Builds a %forward_list from an initializer_list
618 * @param __il An initializer_list of value_type.
619 * @param __al An allocator object.
620 *
621 * Create a %forward_list consisting of copies of the elements
622 * in the initializer_list @a __il. This is linear in __il.size().
623 */
625 const _Alloc& __al = _Alloc())
626 : _Base(_Node_alloc_type(__al))
627 { _M_range_initialize(__il.begin(), __il.end()); }
628
629 /**
630 * @brief The forward_list dtor.
631 */
632 ~forward_list() noexcept
633 { }
634
635 /**
636 * @brief The %forward_list assignment operator.
637 * @param __list A %forward_list of identical element and allocator
638 * types.
639 *
640 * All the elements of @a __list are copied.
641 *
642 * Whether the allocator is copied depends on the allocator traits.
643 */
645 operator=(const forward_list& __list);
646
647 /**
648 * @brief The %forward_list move assignment operator.
649 * @param __list A %forward_list of identical element and allocator
650 * types.
651 *
652 * The contents of @a __list are moved into this %forward_list
653 * (without copying, if the allocators permit it).
654 *
655 * Afterwards @a __list is a valid, but unspecified %forward_list
656 *
657 * Whether the allocator is moved depends on the allocator traits.
658 */
661 noexcept(_Node_alloc_traits::_S_nothrow_move())
662 {
663 constexpr bool __move_storage =
664 _Node_alloc_traits::_S_propagate_on_move_assign()
665 || _Node_alloc_traits::_S_always_equal();
666 _M_move_assign(std::move(__list), __bool_constant<__move_storage>());
667 return *this;
668 }
669
670 /**
671 * @brief The %forward_list initializer list assignment operator.
672 * @param __il An initializer_list of value_type.
673 *
674 * Replace the contents of the %forward_list with copies of the
675 * elements in the initializer_list @a __il. This is linear in
676 * __il.size().
677 */
680 {
681 assign(__il);
682 return *this;
683 }
684
685 /**
686 * @brief Assigns a range to a %forward_list.
687 * @param __first An input iterator.
688 * @param __last An input iterator.
689 *
690 * This function fills a %forward_list with copies of the elements
691 * in the range [@a __first,@a __last).
692 *
693 * Note that the assignment completely changes the %forward_list and
694 * that the number of elements of the resulting %forward_list is the
695 * same as the number of elements assigned.
696 */
697 template<typename _InputIterator,
698 typename = std::_RequireInputIter<_InputIterator>>
699 void
700 assign(_InputIterator __first, _InputIterator __last)
701 {
702 typedef is_assignable<_Tp, decltype(*__first)> __assignable;
703 _M_assign(__first, __last, __assignable());
704 }
705
706#if __glibcxx_ranges_to_container // C++ >= 23
707 /**
708 * @brief Assign a range to a forward_list.
709 * @since C++23
710 */
711 template<__detail::__container_compatible_range<_Tp> _Rg>
712 void
713 assign_range(_Rg&& __rg)
714 {
715 static_assert(assignable_from<_Tp&, ranges::range_reference_t<_Rg>>);
716
717 auto __first = ranges::begin(__rg);
718 const auto __last = ranges::end(__rg);
719 iterator __prev = before_begin();
720 iterator __curr = begin();
721 const iterator __end = end();
722
723 while (__curr != __end && __first != __last)
724 {
725 *__curr = *__first;
726 __prev = __curr;
727 ++__first;
728 ++__curr;
729 }
730
731 if (__curr != __end)
732 erase_after(__prev, __end);
733 else
734 insert_range_after(__prev,
735 ranges::subrange(std::move(__first), __last));
736 }
737#endif // ranges_to_container
738
739 /**
740 * @brief Assigns a given value to a %forward_list.
741 * @param __n Number of elements to be assigned.
742 * @param __val Value to be assigned.
743 *
744 * This function fills a %forward_list with @a __n copies of the
745 * given value. Note that the assignment completely changes the
746 * %forward_list, and that the resulting %forward_list has __n
747 * elements.
748 */
749 void
750 assign(size_type __n, const _Tp& __val)
751 { _M_assign_n(__n, __val, is_copy_assignable<_Tp>()); }
752
753 /**
754 * @brief Assigns an initializer_list to a %forward_list.
755 * @param __il An initializer_list of value_type.
756 *
757 * Replace the contents of the %forward_list with copies of the
758 * elements in the initializer_list @a __il. This is linear in
759 * il.size().
760 */
761 void
763 { assign(__il.begin(), __il.end()); }
764
765 /// Get a copy of the memory allocation object.
766 allocator_type
767 get_allocator() const noexcept
768 { return allocator_type(this->_M_get_Node_allocator()); }
769
770 // 23.3.4.3 iterators:
771
772 /**
773 * Returns a read/write iterator that points before the first element
774 * in the %forward_list. Iteration is done in ordinary element order.
775 */
776 [[__nodiscard__]]
778 before_begin() noexcept
779 { return iterator(&this->_M_impl._M_head); }
780
781 /**
782 * Returns a read-only (constant) iterator that points before the
783 * first element in the %forward_list. Iteration is done in ordinary
784 * element order.
785 */
786 [[__nodiscard__]]
787 const_iterator
788 before_begin() const noexcept
789 { return const_iterator(&this->_M_impl._M_head); }
790
791 /**
792 * Returns a read/write iterator that points to the first element
793 * in the %forward_list. Iteration is done in ordinary element order.
794 */
795 [[__nodiscard__]]
797 begin() noexcept
798 { return iterator(this->_M_impl._M_head._M_next); }
799
800 /**
801 * Returns a read-only (constant) iterator that points to the first
802 * element in the %forward_list. Iteration is done in ordinary
803 * element order.
804 */
805 [[__nodiscard__]]
806 const_iterator
807 begin() const noexcept
808 { return const_iterator(this->_M_impl._M_head._M_next); }
809
810 /**
811 * Returns a read/write iterator that points one past the last
812 * element in the %forward_list. Iteration is done in ordinary
813 * element order.
814 */
815 [[__nodiscard__]]
817 end() noexcept
818 { return iterator(nullptr); }
819
820 /**
821 * Returns a read-only iterator that points one past the last
822 * element in the %forward_list. Iteration is done in ordinary
823 * element order.
824 */
825 [[__nodiscard__]]
826 const_iterator
827 end() const noexcept
828 { return const_iterator(nullptr); }
829
830 /**
831 * Returns a read-only (constant) iterator that points to the
832 * first element in the %forward_list. Iteration is done in ordinary
833 * element order.
834 */
835 [[__nodiscard__]]
836 const_iterator
837 cbegin() const noexcept
838 { return const_iterator(this->_M_impl._M_head._M_next); }
839
840 /**
841 * Returns a read-only (constant) iterator that points before the
842 * first element in the %forward_list. Iteration is done in ordinary
843 * element order.
844 */
845 [[__nodiscard__]]
846 const_iterator
847 cbefore_begin() const noexcept
848 { return const_iterator(&this->_M_impl._M_head); }
849
850 /**
851 * Returns a read-only (constant) iterator that points one past
852 * the last element in the %forward_list. Iteration is done in
853 * ordinary element order.
854 */
855 [[__nodiscard__]]
856 const_iterator
857 cend() const noexcept
858 { return const_iterator(nullptr); }
859
860 /**
861 * Returns true if the %forward_list is empty. (Thus begin() would
862 * equal end().)
863 */
864 [[__nodiscard__]]
865 bool
866 empty() const noexcept
867 { return this->_M_impl._M_head._M_next == nullptr; }
868
869 /**
870 * Returns the largest possible number of elements of %forward_list.
871 */
872 [[__nodiscard__]]
873 size_type
874 max_size() const noexcept
875 { return _Node_alloc_traits::max_size(this->_M_get_Node_allocator()); }
876
877 // 23.3.4.4 element access:
878
879 /**
880 * Returns a read/write reference to the data at the first
881 * element of the %forward_list.
882 */
883 [[__nodiscard__]]
884 reference
886 {
887 _Node* __front = static_cast<_Node*>(this->_M_impl._M_head._M_next);
888 return *__front->_M_valptr();
889 }
890
891 /**
892 * Returns a read-only (constant) reference to the data at the first
893 * element of the %forward_list.
894 */
895 [[__nodiscard__]]
896 const_reference
897 front() const
898 {
899 _Node* __front = static_cast<_Node*>(this->_M_impl._M_head._M_next);
900 return *__front->_M_valptr();
901 }
902
903 // 23.3.4.5 modifiers:
904
905 /**
906 * @brief Constructs object in %forward_list at the front of the
907 * list.
908 * @param __args Arguments.
909 *
910 * This function will insert an object of type Tp constructed
911 * with Tp(std::forward<Args>(args)...) at the front of the list
912 * Due to the nature of a %forward_list this operation can
913 * be done in constant time, and does not invalidate iterators
914 * and references.
915 */
916 template<typename... _Args>
917#if __cplusplus > 201402L
918 reference
919#else
920 void
921#endif
922 emplace_front(_Args&&... __args)
923 {
924 this->_M_insert_after(cbefore_begin(),
925 std::forward<_Args>(__args)...);
926#if __cplusplus > 201402L
927 return front();
928#endif
929 }
930
931 /**
932 * @brief Add data to the front of the %forward_list.
933 * @param __val Data to be added.
934 *
935 * This is a typical stack operation. The function creates an
936 * element at the front of the %forward_list and assigns the given
937 * data to it. Due to the nature of a %forward_list this operation
938 * can be done in constant time, and does not invalidate iterators
939 * and references.
940 */
941 void
942 push_front(const _Tp& __val)
943 { this->_M_insert_after(cbefore_begin(), __val); }
944
945 /**
946 *
947 */
948 void
949 push_front(_Tp&& __val)
950 { this->_M_insert_after(cbefore_begin(), std::move(__val)); }
951
952#if __glibcxx_ranges_to_container // C++ >= 23
953 /**
954 * @brief Insert a range at the beginning of a forward_list.
955 * @param __rg An input range with elements that are convertible to
956 * the forward_list's value_type.
957 *
958 * The inserted elements will be in the same order as in the range,
959 * so they are not reversed as would happen with a simple loop calling
960 * emplace_front for each element of the range.
961 *
962 * No iterators to existing elements are invalidated by this function.
963 * If the insertion fails due to an exception, no elements will be added
964 * and so the list will be unchanged.
965 *
966 * @since C++23
967 */
968 template<__detail::__container_compatible_range<_Tp> _Rg>
969 void
970 prepend_range(_Rg&& __rg)
971 {
972 forward_list __tmp(from_range, std::forward<_Rg>(__rg),
973 get_allocator());
974 if (!__tmp.empty())
975 splice_after(before_begin(), __tmp);
976 }
977#endif // ranges_to_container
978
979 /**
980 * @brief Removes first element.
981 *
982 * This is a typical stack operation. It shrinks the %forward_list
983 * by one. Due to the nature of a %forward_list this operation can
984 * be done in constant time, and only invalidates iterators/references
985 * to the element being removed.
986 *
987 * Note that no data is returned, and if the first element's data
988 * is needed, it should be retrieved before pop_front() is
989 * called.
990 */
991 void
993 { this->_M_erase_after(&this->_M_impl._M_head); }
994
995 /**
996 * @brief Constructs object in %forward_list after the specified
997 * iterator.
998 * @param __pos A const_iterator into the %forward_list.
999 * @param __args Arguments.
1000 * @return An iterator that points to the inserted data.
1001 *
1002 * This function will insert an object of type T constructed
1003 * with T(std::forward<Args>(args)...) after the specified
1004 * location. Due to the nature of a %forward_list this operation can
1005 * be done in constant time, and does not invalidate iterators
1006 * and references.
1007 */
1008 template<typename... _Args>
1009 iterator
1010 emplace_after(const_iterator __pos, _Args&&... __args)
1011 { return iterator(this->_M_insert_after(__pos,
1012 std::forward<_Args>(__args)...)); }
1013
1014 /**
1015 * @brief Inserts given value into %forward_list after specified
1016 * iterator.
1017 * @param __pos An iterator into the %forward_list.
1018 * @param __val Data to be inserted.
1019 * @return An iterator that points to the inserted data.
1020 *
1021 * This function will insert a copy of the given value after
1022 * the specified location. Due to the nature of a %forward_list this
1023 * operation can be done in constant time, and does not
1024 * invalidate iterators and references.
1025 */
1026 iterator
1027 insert_after(const_iterator __pos, const _Tp& __val)
1028 { return iterator(this->_M_insert_after(__pos, __val)); }
1029
1030 /**
1031 *
1032 */
1033 iterator
1034 insert_after(const_iterator __pos, _Tp&& __val)
1035 { return iterator(this->_M_insert_after(__pos, std::move(__val))); }
1036
1037 /**
1038 * @brief Inserts a number of copies of given data into the
1039 * %forward_list.
1040 * @param __pos An iterator into the %forward_list.
1041 * @param __n Number of elements to be inserted.
1042 * @param __val Data to be inserted.
1043 * @return An iterator pointing to the last inserted copy of
1044 * @a val or @a pos if @a n == 0.
1045 *
1046 * This function will insert a specified number of copies of the
1047 * given data after the location specified by @a pos.
1048 *
1049 * This operation is linear in the number of elements inserted and
1050 * does not invalidate iterators and references.
1051 */
1052 iterator
1053 insert_after(const_iterator __pos, size_type __n, const _Tp& __val);
1054
1055 /**
1056 * @brief Inserts a range into the %forward_list.
1057 * @param __pos An iterator into the %forward_list.
1058 * @param __first An input iterator.
1059 * @param __last An input iterator.
1060 * @return An iterator pointing to the last inserted element or
1061 * @a __pos if @a __first == @a __last.
1062 *
1063 * This function will insert copies of the data in the range
1064 * [@a __first,@a __last) into the %forward_list after the
1065 * location specified by @a __pos.
1066 *
1067 * This operation is linear in the number of elements inserted and
1068 * does not invalidate iterators and references.
1069 */
1070 template<typename _InputIterator,
1071 typename = std::_RequireInputIter<_InputIterator>>
1072 iterator
1073 insert_after(const_iterator __pos,
1074 _InputIterator __first, _InputIterator __last);
1075
1076 /**
1077 * @brief Inserts the contents of an initializer_list into
1078 * %forward_list after the specified iterator.
1079 * @param __pos An iterator into the %forward_list.
1080 * @param __il An initializer_list of value_type.
1081 * @return An iterator pointing to the last inserted element
1082 * or @a __pos if @a __il is empty.
1083 *
1084 * This function will insert copies of the data in the
1085 * initializer_list @a __il into the %forward_list before the location
1086 * specified by @a __pos.
1087 *
1088 * This operation is linear in the number of elements inserted and
1089 * does not invalidate iterators and references.
1090 */
1091 iterator
1093 { return insert_after(__pos, __il.begin(), __il.end()); }
1094
1095#if __glibcxx_ranges_to_container // C++ >= 23
1096 /**
1097 * @brief Insert a rangeinto a forward_list.
1098 * @param __position An iterator.
1099 * @param __rg An input range of elements that can be converted to
1100 * the forward_list's value type.
1101 * @return An iterator pointing to the last element inserted,
1102 * or `__position` if the range is empty.
1103 *
1104 * Inserts the elements of `__rg` after `__position`.
1105 * No iterators to existing elements are invalidated by this function.
1106 * If the insertion fails due to an exception, no elements will be added
1107 * and so the list will be unchanged.
1108 *
1109 * @since C++23
1110 */
1111 template<__detail::__container_compatible_range<_Tp> _Rg>
1112 iterator
1113 insert_range_after(const_iterator __position, _Rg&& __rg)
1114 {
1115 forward_list __tmp(from_range, std::forward<_Rg>(__rg),
1116 get_allocator());
1117 return _M_splice_after(__position, __tmp.before_begin(), __tmp.end());
1118 }
1119#endif // ranges_to_container
1120
1121 /**
1122 * @brief Removes the element pointed to by the iterator following
1123 * @c pos.
1124 * @param __pos Iterator pointing before element to be erased.
1125 * @return An iterator pointing to the element following the one
1126 * that was erased, or end() if no such element exists.
1127 *
1128 * This function will erase the element at the given position and
1129 * thus shorten the %forward_list by one.
1130 *
1131 * Due to the nature of a %forward_list this operation can be done
1132 * in constant time, and only invalidates iterators/references to
1133 * the element being removed. The user is also cautioned that
1134 * this function only erases the element, and that if the element
1135 * is itself a pointer, the pointed-to memory is not touched in
1136 * any way. Managing the pointer is the user's responsibility.
1137 */
1138 iterator
1140 { return iterator(this->_M_erase_after(const_cast<_Node_base*>
1141 (__pos._M_node))); }
1142
1143 /**
1144 * @brief Remove a range of elements.
1145 * @param __pos Iterator pointing before the first element to be
1146 * erased.
1147 * @param __last Iterator pointing to one past the last element to be
1148 * erased.
1149 * @return @ __last.
1150 *
1151 * This function will erase the elements in the range
1152 * @a (__pos,__last) and shorten the %forward_list accordingly.
1153 *
1154 * This operation is linear time in the size of the range and only
1155 * invalidates iterators/references to the element being removed.
1156 * The user is also cautioned that this function only erases the
1157 * elements, and that if the elements themselves are pointers, the
1158 * pointed-to memory is not touched in any way. Managing the pointer
1159 * is the user's responsibility.
1160 */
1161 iterator
1163 { return iterator(this->_M_erase_after(const_cast<_Node_base*>
1164 (__pos._M_node),
1165 const_cast<_Node_base*>
1166 (__last._M_node))); }
1167
1168 /**
1169 * @brief Swaps data with another %forward_list.
1170 * @param __list A %forward_list of the same element and allocator
1171 * types.
1172 *
1173 * This exchanges the elements between two lists in constant
1174 * time. Note that the global std::swap() function is
1175 * specialized such that std::swap(l1,l2) will feed to this
1176 * function.
1177 *
1178 * Whether the allocators are swapped depends on the allocator traits.
1179 */
1180 void
1181 swap(forward_list& __list) noexcept
1182 {
1183 std::swap(this->_M_impl._M_head._M_next,
1184 __list._M_impl._M_head._M_next);
1185 _Node_alloc_traits::_S_on_swap(this->_M_get_Node_allocator(),
1186 __list._M_get_Node_allocator());
1187 }
1188
1189 /**
1190 * @brief Resizes the %forward_list to the specified number of
1191 * elements.
1192 * @param __sz Number of elements the %forward_list should contain.
1193 *
1194 * This function will %resize the %forward_list to the specified
1195 * number of elements. If the number is smaller than the
1196 * %forward_list's current number of elements the %forward_list
1197 * is truncated, otherwise the %forward_list is extended and the
1198 * new elements are default constructed.
1199 */
1200 void
1201 resize(size_type __sz);
1202
1203 /**
1204 * @brief Resizes the %forward_list to the specified number of
1205 * elements.
1206 * @param __sz Number of elements the %forward_list should contain.
1207 * @param __val Data with which new elements should be populated.
1208 *
1209 * This function will %resize the %forward_list to the specified
1210 * number of elements. If the number is smaller than the
1211 * %forward_list's current number of elements the %forward_list
1212 * is truncated, otherwise the %forward_list is extended and new
1213 * elements are populated with given data.
1214 */
1215 void
1216 resize(size_type __sz, const value_type& __val);
1217
1218 /**
1219 * @brief Erases all the elements.
1220 *
1221 * Note that this function only erases
1222 * the elements, and that if the elements themselves are
1223 * pointers, the pointed-to memory is not touched in any way.
1224 * Managing the pointer is the user's responsibility.
1225 */
1226 void
1227 clear() noexcept
1228 { this->_M_erase_after(&this->_M_impl._M_head, nullptr); }
1229
1230 // 23.3.4.6 forward_list operations:
1231
1232 /**
1233 * @brief Insert contents of another %forward_list.
1234 * @param __pos Iterator referencing the element to insert after.
1235 * @param __list Source list.
1236 *
1237 * The elements of @a list are inserted in constant time after
1238 * the element referenced by @a pos. @a list becomes an empty
1239 * list.
1240 *
1241 * Requires this != @a x.
1242 */
1243 void
1244 splice_after(const_iterator __pos, forward_list&& __list) noexcept
1245 {
1246 if (!__list.empty())
1247 _M_splice_after(__pos, __list.before_begin(), __list.end());
1248 }
1249
1250 void
1251 splice_after(const_iterator __pos, forward_list& __list) noexcept
1252 { splice_after(__pos, std::move(__list)); }
1253
1254 /**
1255 * @brief Insert element from another %forward_list.
1256 * @param __pos Iterator referencing the element to insert after.
1257 * @param __list Source list.
1258 * @param __i Iterator referencing the element before the element
1259 * to move.
1260 *
1261 * Removes the element in list @a list referenced by @a i and
1262 * inserts it into the current list after @a pos.
1263 */
1264 void
1265 splice_after(const_iterator __pos, forward_list&& __list,
1266 const_iterator __i) noexcept;
1267
1268 void
1269 splice_after(const_iterator __pos, forward_list& __list,
1270 const_iterator __i) noexcept
1271 { splice_after(__pos, std::move(__list), __i); }
1272
1273 /**
1274 * @brief Insert range from another %forward_list.
1275 * @param __pos Iterator referencing the element to insert after.
1276 * @param __list Source list.
1277 * @param __before Iterator referencing before the start of range
1278 * in list.
1279 * @param __last Iterator referencing the end of range in list.
1280 *
1281 * Removes elements in the range (__before,__last) and inserts them
1282 * after @a __pos in constant time.
1283 *
1284 * Undefined if @a __pos is in (__before,__last).
1285 * @{
1286 */
1287 void
1289 const_iterator __before, const_iterator __last) noexcept
1290 { _M_splice_after(__pos, __before, __last); }
1291
1292 void
1294 const_iterator __before, const_iterator __last) noexcept
1295 { _M_splice_after(__pos, __before, __last); }
1296 /// @}
1297
1298 private:
1299#ifdef __glibcxx_list_remove_return_type // C++20 && HOSTED
1300 using __remove_return_type = size_type;
1301# define _GLIBCXX_FWDLIST_REMOVE_RETURN_TYPE_TAG \
1302 __attribute__((__abi_tag__("__cxx20")))
1303#else
1304 using __remove_return_type = void;
1305# define _GLIBCXX_FWDLIST_REMOVE_RETURN_TYPE_TAG
1306#endif
1307 public:
1308
1309 /**
1310 * @brief Remove all elements equal to value.
1311 * @param __val The value to remove.
1312 *
1313 * Removes every element in the list equal to @a __val.
1314 * Remaining elements stay in list order. Note that this
1315 * function only erases the elements, and that if the elements
1316 * themselves are pointers, the pointed-to memory is not
1317 * touched in any way. Managing the pointer is the user's
1318 * responsibility.
1319 */
1320 _GLIBCXX_FWDLIST_REMOVE_RETURN_TYPE_TAG
1321 __remove_return_type
1322 remove(const _Tp& __val);
1323
1324 /**
1325 * @brief Remove all elements satisfying a predicate.
1326 * @param __pred Unary predicate function or object.
1327 *
1328 * Removes every element in the list for which the predicate
1329 * returns true. Remaining elements stay in list order. Note
1330 * that this function only erases the elements, and that if the
1331 * elements themselves are pointers, the pointed-to memory is
1332 * not touched in any way. Managing the pointer is the user's
1333 * responsibility.
1334 */
1335 template<typename _Pred>
1336 __remove_return_type
1337 remove_if(_Pred __pred);
1338
1339 /**
1340 * @brief Remove consecutive duplicate elements.
1341 *
1342 * For each consecutive set of elements with the same value,
1343 * remove all but the first one. Remaining elements stay in
1344 * list order. Note that this function only erases the
1345 * elements, and that if the elements themselves are pointers,
1346 * the pointed-to memory is not touched in any way. Managing
1347 * the pointer is the user's responsibility.
1348 */
1349 _GLIBCXX_FWDLIST_REMOVE_RETURN_TYPE_TAG
1350 __remove_return_type
1352 { return unique(std::equal_to<_Tp>()); }
1353
1354#undef _GLIBCXX_FWDLIST_REMOVE_RETURN_TYPE_TAG
1355
1356 /**
1357 * @brief Remove consecutive elements satisfying a predicate.
1358 * @param __binary_pred Binary predicate function or object.
1359 *
1360 * For each consecutive set of elements [first,last) that
1361 * satisfy predicate(first,i) where i is an iterator in
1362 * [first,last), remove all but the first one. Remaining
1363 * elements stay in list order. Note that this function only
1364 * erases the elements, and that if the elements themselves are
1365 * pointers, the pointed-to memory is not touched in any way.
1366 * Managing the pointer is the user's responsibility.
1367 */
1368 template<typename _BinPred>
1369 __remove_return_type
1370 unique(_BinPred __binary_pred);
1371
1372 /**
1373 * @brief Merge sorted lists.
1374 * @param __list Sorted list to merge.
1375 *
1376 * Assumes that both @a list and this list are sorted according to
1377 * operator<(). Merges elements of @a __list into this list in
1378 * sorted order, leaving @a __list empty when complete. Elements in
1379 * this list precede elements in @a __list that are equal.
1380 */
1381 void
1383 { merge(std::move(__list), std::less<_Tp>()); }
1384
1385 void
1386 merge(forward_list& __list)
1387 { merge(std::move(__list)); }
1388
1389 /**
1390 * @brief Merge sorted lists according to comparison function.
1391 * @param __list Sorted list to merge.
1392 * @param __comp Comparison function defining sort order.
1393 *
1394 * Assumes that both @a __list and this list are sorted according to
1395 * comp. Merges elements of @a __list into this list
1396 * in sorted order, leaving @a __list empty when complete. Elements
1397 * in this list precede elements in @a __list that are equivalent
1398 * according to comp().
1399 */
1400 template<typename _Comp>
1401 void
1402 merge(forward_list&& __list, _Comp __comp);
1403
1404 template<typename _Comp>
1405 void
1406 merge(forward_list& __list, _Comp __comp)
1407 { merge(std::move(__list), __comp); }
1408
1409 /**
1410 * @brief Sort the elements of the list.
1411 *
1412 * Sorts the elements of this list in NlogN time. Equivalent
1413 * elements remain in list order.
1414 */
1415 void
1417 { sort(std::less<_Tp>()); }
1418
1419 /**
1420 * @brief Sort the forward_list using a comparison function.
1421 *
1422 * Sorts the elements of this list in NlogN time. Equivalent
1423 * elements remain in list order.
1424 */
1425 template<typename _Comp>
1426 void
1427 sort(_Comp __comp);
1428
1429 /**
1430 * @brief Reverse the elements in list.
1431 *
1432 * Reverse the order of elements in the list in linear time.
1433 */
1434 void
1435 reverse() noexcept
1436 { this->_M_impl._M_head._M_reverse_after(); }
1437
1438 private:
1439 // Called by the range constructor to implement [23.3.4.2]/9
1440 template<typename _InputIterator>
1441 void
1442 _M_range_initialize(_InputIterator __first, _InputIterator __last);
1443
1444 // Called by forward_list(n,v,a), and the range constructor when it
1445 // turns out to be the same thing.
1446 void
1447 _M_fill_initialize(size_type __n, const value_type& __value);
1448
1449 // Called by splice_after and insert_after.
1450 iterator
1451 _M_splice_after(const_iterator __pos, const_iterator __before,
1452 const_iterator __last);
1453
1454 // Called by forward_list(n).
1455 void
1456 _M_default_initialize(size_type __n);
1457
1458 // Called by resize(sz).
1459 void
1460 _M_default_insert_after(const_iterator __pos, size_type __n);
1461
1462 // Called by operator=(forward_list&&)
1463 void
1464 _M_move_assign(forward_list&& __list, true_type) noexcept
1465 {
1466 clear();
1467 this->_M_impl._M_head._M_next = __list._M_impl._M_head._M_next;
1468 __list._M_impl._M_head._M_next = nullptr;
1469 std::__alloc_on_move(this->_M_get_Node_allocator(),
1470 __list._M_get_Node_allocator());
1471 }
1472
1473 // Called by operator=(forward_list&&)
1474 void
1475 _M_move_assign(forward_list&& __list, false_type)
1476 {
1477 if (__list._M_get_Node_allocator() == this->_M_get_Node_allocator())
1478 _M_move_assign(std::move(__list), true_type());
1479 else
1480 // The rvalue's allocator cannot be moved, or is not equal,
1481 // so we need to individually move each element.
1482 this->assign(std::make_move_iterator(__list.begin()),
1483 std::make_move_iterator(__list.end()));
1484 }
1485
1486 // Called by assign(_InputIterator, _InputIterator) if _Tp is
1487 // CopyAssignable.
1488 template<typename _InputIterator>
1489 void
1490 _M_assign(_InputIterator __first, _InputIterator __last, true_type)
1491 {
1492 auto __prev = before_begin();
1493 auto __curr = begin();
1494 auto __end = end();
1495 while (__curr != __end && __first != __last)
1496 {
1497 *__curr = *__first;
1498 ++__prev;
1499 ++__curr;
1500 ++__first;
1501 }
1502 if (__first != __last)
1503 insert_after(__prev, __first, __last);
1504 else if (__curr != __end)
1505 erase_after(__prev, __end);
1506 }
1507
1508 // Called by assign(_InputIterator, _InputIterator) if _Tp is not
1509 // CopyAssignable.
1510 template<typename _InputIterator>
1511 void
1512 _M_assign(_InputIterator __first, _InputIterator __last, false_type)
1513 {
1514 clear();
1515 insert_after(cbefore_begin(), __first, __last);
1516 }
1517
1518 // Called by assign(size_type, const _Tp&) if Tp is CopyAssignable
1519 void
1520 _M_assign_n(size_type __n, const _Tp& __val, true_type)
1521 {
1522 auto __prev = before_begin();
1523 auto __curr = begin();
1524 auto __end = end();
1525 while (__curr != __end && __n > 0)
1526 {
1527 *__curr = __val;
1528 ++__prev;
1529 ++__curr;
1530 --__n;
1531 }
1532 if (__n > 0)
1533 insert_after(__prev, __n, __val);
1534 else if (__curr != __end)
1535 erase_after(__prev, __end);
1536 }
1537
1538 // Called by assign(size_type, const _Tp&) if Tp is non-CopyAssignable
1539 void
1540 _M_assign_n(size_type __n, const _Tp& __val, false_type)
1541 {
1542 clear();
1543 insert_after(cbefore_begin(), __n, __val);
1544 }
1545 };
1546
1547#if __cpp_deduction_guides >= 201606
1548 template<typename _InputIterator, typename _ValT
1549 = typename iterator_traits<_InputIterator>::value_type,
1550 typename _Allocator = allocator<_ValT>,
1551 typename = _RequireInputIter<_InputIterator>,
1552 typename = _RequireAllocator<_Allocator>>
1553 forward_list(_InputIterator, _InputIterator, _Allocator = _Allocator())
1554 -> forward_list<_ValT, _Allocator>;
1555
1556#if __glibcxx_ranges_to_container // C++ >= 23
1557 template<ranges::input_range _Rg,
1558 typename _Allocator = allocator<ranges::range_value_t<_Rg>>>
1559 forward_list(from_range_t, _Rg&&, _Allocator = _Allocator())
1560 -> forward_list<ranges::range_value_t<_Rg>, _Allocator>;
1561#endif
1562#endif
1563
1564 /**
1565 * @brief Forward list equality comparison.
1566 * @param __lx A %forward_list
1567 * @param __ly A %forward_list of the same type as @a __lx.
1568 * @return True iff the elements of the forward lists are equal.
1569 *
1570 * This is an equivalence relation. It is linear in the number of
1571 * elements of the forward lists. Deques are considered equivalent
1572 * if corresponding elements compare equal.
1573 */
1574 template<typename _Tp, typename _Alloc>
1575 [[__nodiscard__]]
1576 bool
1577 operator==(const forward_list<_Tp, _Alloc>& __lx,
1578 const forward_list<_Tp, _Alloc>& __ly);
1579
1580#if __cpp_lib_three_way_comparison
1581 /**
1582 * @brief Forward list ordering relation.
1583 * @param __x A `forward_list`.
1584 * @param __y A `forward_list` of the same type as `__x`.
1585 * @return A value indicating whether `__x` is less than, equal to,
1586 * greater than, or incomparable with `__y`.
1587 *
1588 * See `std::lexicographical_compare_three_way()` for how the determination
1589 * is made. This operator is used to synthesize relational operators like
1590 * `<` and `>=` etc.
1591 */
1592 template<typename _Tp, typename _Alloc>
1593 [[nodiscard]]
1594 inline __detail::__synth3way_t<_Tp>
1595 operator<=>(const forward_list<_Tp, _Alloc>& __x,
1596 const forward_list<_Tp, _Alloc>& __y)
1597 {
1599 __y.begin(), __y.end(),
1600 __detail::__synth3way);
1601 }
1602#else
1603 /**
1604 * @brief Forward list ordering relation.
1605 * @param __lx A %forward_list.
1606 * @param __ly A %forward_list of the same type as @a __lx.
1607 * @return True iff @a __lx is lexicographically less than @a __ly.
1608 *
1609 * This is a total ordering relation. It is linear in the number of
1610 * elements of the forward lists. The elements must be comparable
1611 * with @c <.
1612 *
1613 * See std::lexicographical_compare() for how the determination is made.
1614 */
1615 template<typename _Tp, typename _Alloc>
1616 [[__nodiscard__]]
1617 inline bool
1618 operator<(const forward_list<_Tp, _Alloc>& __lx,
1619 const forward_list<_Tp, _Alloc>& __ly)
1620 { return std::lexicographical_compare(__lx.cbegin(), __lx.cend(),
1621 __ly.cbegin(), __ly.cend()); }
1622
1623 /// Based on operator==
1624 template<typename _Tp, typename _Alloc>
1625 [[__nodiscard__]]
1626 inline bool
1627 operator!=(const forward_list<_Tp, _Alloc>& __lx,
1628 const forward_list<_Tp, _Alloc>& __ly)
1629 { return !(__lx == __ly); }
1630
1631 /// Based on operator<
1632 template<typename _Tp, typename _Alloc>
1633 [[__nodiscard__]]
1634 inline bool
1635 operator>(const forward_list<_Tp, _Alloc>& __lx,
1636 const forward_list<_Tp, _Alloc>& __ly)
1637 { return (__ly < __lx); }
1638
1639 /// Based on operator<
1640 template<typename _Tp, typename _Alloc>
1641 [[__nodiscard__]]
1642 inline bool
1643 operator>=(const forward_list<_Tp, _Alloc>& __lx,
1644 const forward_list<_Tp, _Alloc>& __ly)
1645 { return !(__lx < __ly); }
1646
1647 /// Based on operator<
1648 template<typename _Tp, typename _Alloc>
1649 [[__nodiscard__]]
1650 inline bool
1651 operator<=(const forward_list<_Tp, _Alloc>& __lx,
1652 const forward_list<_Tp, _Alloc>& __ly)
1653 { return !(__ly < __lx); }
1654#endif // three-way comparison
1655
1656 /// See std::forward_list::swap().
1657 template<typename _Tp, typename _Alloc>
1658 inline void
1661 noexcept(noexcept(__lx.swap(__ly)))
1662 { __lx.swap(__ly); }
1663
1664_GLIBCXX_END_NAMESPACE_CONTAINER
1665_GLIBCXX_END_NAMESPACE_VERSION
1666} // namespace std
1667
1668#endif // _FORWARD_LIST_H
constexpr bool operator<=(const duration< _Rep1, _Period1 > &__lhs, const duration< _Rep2, _Period2 > &__rhs)
Definition chrono.h:859
constexpr bool operator>=(const duration< _Rep1, _Period1 > &__lhs, const duration< _Rep2, _Period2 > &__rhs)
Definition chrono.h:873
constexpr bool operator>(const duration< _Rep1, _Period1 > &__lhs, const duration< _Rep2, _Period2 > &__rhs)
Definition chrono.h:866
__bool_constant< true > true_type
The type used as a compile-time boolean with true value.
Definition type_traits:116
__bool_constant< false > false_type
The type used as a compile-time boolean with false value.
Definition type_traits:119
constexpr std::remove_reference< _Tp >::type && move(_Tp &&__t) noexcept
Convert a value to an rvalue.
Definition move.h:127
constexpr auto lexicographical_compare_three_way(_InputIter1 __first1, _InputIter1 __last1, _InputIter2 __first2, _InputIter2 __last2, _Comp __comp) -> decltype(__comp(*__first1, *__first2))
Performs dictionary comparison on ranges.
ISO C++ entities toplevel namespace is std.
initializer_list
is_nothrow_default_constructible
Definition type_traits:1237
is_assignable
Definition type_traits:1269
is_copy_assignable
Definition type_traits:1279
Uniform interface to all allocator types.
A helper basic node class for forward_list. This is just a linked list with nothing inside it....
A helper node class for forward_list. This is just a linked list with uninitialized storage for a dat...
A forward_list::iterator.
friend bool operator==(const _Self &__x, const _Self &__y) noexcept
Forward list iterator equality comparison.
A forward_list::const_iterator.
friend bool operator==(const _Self &__x, const _Self &__y) noexcept
Forward list const_iterator equality comparison.
Base class for forward_list.
A standard container with linear time access to elements, and fixed time insertion/deletion at any po...
__remove_return_type unique(_BinPred __binary_pred)
Remove consecutive elements satisfying a predicate.
iterator begin() noexcept
const_iterator before_begin() const noexcept
void reverse() noexcept
Reverse the elements in list.
forward_list()=default
Creates a forward_list with no elements.
~forward_list() noexcept
The forward_list dtor.
iterator erase_after(const_iterator __pos)
Removes the element pointed to by the iterator following pos.
void swap(forward_list &__list) noexcept
Swaps data with another forward_list.
const_reference front() const
void merge(forward_list &&__list)
Merge sorted lists.
forward_list(const _Alloc &__al) noexcept
Creates a forward_list with no elements.
void sort()
Sort the elements of the list.
iterator before_begin() noexcept
forward_list(const forward_list &__list, const __type_identity_t< _Alloc > &__al)
Copy constructor with allocator argument.
iterator emplace_after(const_iterator __pos, _Args &&... __args)
Constructs object in forward_list after the specified iterator.
forward_list(const forward_list &__list)
The forward_list copy constructor.
iterator insert_after(const_iterator __pos, const _Tp &__val)
Inserts given value into forward_list after specified iterator.
forward_list & operator=(forward_list &&__list) noexcept(_Node_alloc_traits::_S_nothrow_move())
The forward_list move assignment operator.
void resize(size_type __sz)
Resizes the forward_list to the specified number of elements.
forward_list & operator=(const forward_list &__list)
The forward_list assignment operator.
__remove_return_type remove_if(_Pred __pred)
Remove all elements satisfying a predicate.
iterator end() noexcept
forward_list(size_type __n, const _Tp &__value, const _Alloc &__al=_Alloc())
Creates a forward_list with copies of an exemplar element.
void assign(size_type __n, const _Tp &__val)
Assigns a given value to a forward_list.
const_iterator begin() const noexcept
void splice_after(const_iterator __pos, forward_list &&__list) noexcept
Insert contents of another forward_list.
const_iterator cbefore_begin() const noexcept
forward_list & operator=(std::initializer_list< _Tp > __il)
The forward_list initializer list assignment operator.
forward_list(std::initializer_list< _Tp > __il, const _Alloc &__al=_Alloc())
Builds a forward_list from an initializer_list.
reference emplace_front(_Args &&... __args)
Constructs object in forward_list at the front of the list.
forward_list(size_type __n, const _Alloc &__al=_Alloc())
Creates a forward_list with default constructed elements.
iterator insert_after(const_iterator __pos, std::initializer_list< _Tp > __il)
Inserts the contents of an initializer_list into forward_list after the specified iterator.
const_iterator end() const noexcept
void splice_after(const_iterator __pos, forward_list &&, const_iterator __before, const_iterator __last) noexcept
Insert range from another forward_list.
reference front()
forward_list(forward_list &&__list, const __type_identity_t< _Alloc > &__al) noexcept(_Node_alloc_traits::_S_always_equal())
Move constructor with allocator argument.
iterator erase_after(const_iterator __pos, const_iterator __last)
Remove a range of elements.
__remove_return_type unique()
Remove consecutive duplicate elements.
void clear() noexcept
Erases all the elements.
__remove_return_type remove(const _Tp &__val)
Remove all elements equal to value.
const_iterator cend() const noexcept
void assign(_InputIterator __first, _InputIterator __last)
Assigns a range to a forward_list.
bool empty() const noexcept
allocator_type get_allocator() const noexcept
Get a copy of the memory allocation object.
void push_front(const _Tp &__val)
Add data to the front of the forward_list.
forward_list(forward_list &&)=default
The forward_list move constructor.
forward_list(_InputIterator __first, _InputIterator __last, const _Alloc &__al=_Alloc())
Builds a forward_list from a range.
void splice_after(const_iterator __pos, forward_list &, const_iterator __before, const_iterator __last) noexcept
Insert range from another forward_list.
const_iterator cbegin() const noexcept
void pop_front()
Removes first element.
void assign(std::initializer_list< _Tp > __il)
Assigns an initializer_list to a forward_list.
size_type max_size() const noexcept
Uniform interface to all pointer-like types.
Definition ptr_traits.h:178
One of the comparison functors.
One of the comparison functors.
Forward iterators support a superset of input iterator operations.
Common iterator class.
Uniform interface to C++98 and C++11 allocators.
static constexpr pointer allocate(_Alloc &__a, size_type __n)
Allocate memory.
static constexpr void deallocate(_Alloc &__a, pointer __p, size_type __n)
Deallocate memory.
static constexpr size_type max_size(const _Alloc &__a) noexcept
The maximum supported allocation size.