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