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