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