libstdc++
forward_list.h
Go to the documentation of this file.
1// <forward_list.h> -*- C++ -*-
2
3// Copyright (C) 2008-2024 Free Software Foundation, Inc.
4//
5// This file is part of the GNU ISO C++ Library. This library is free
6// software; you can redistribute it and/or modify it under the
7// terms of the GNU General Public License as published by the
8// Free Software Foundation; either version 3, or (at your option)
9// any later version.
10
11// This library is distributed in the hope that it will be useful,
12// but WITHOUT ANY WARRANTY; without even the implied warranty of
13// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14// GNU General Public License for more details.
15
16// Under Section 7 of GPL version 3, you are granted additional
17// permissions described in the GCC Runtime Library Exception, version
18// 3.1, as published by the Free Software Foundation.
19
20// You should have received a copy of the GNU General Public License and
21// a copy of the GCC Runtime Library Exception along with this program;
22// see the files COPYING3 and COPYING.RUNTIME respectively. If not, see
23// <http://www.gnu.org/licenses/>.
24
25/** @file bits/forward_list.h
26 * This is an internal header file, included by other library headers.
27 * Do not attempt to use it directly. @headername{forward_list}
28 */
29
30#ifndef _FORWARD_LIST_H
31#define _FORWARD_LIST_H 1
32
33#ifdef _GLIBCXX_SYSHDR
34#pragma GCC system_header
35#endif
36
37#include <initializer_list>
39#include <bits/stl_iterator.h>
40#include <bits/stl_algobase.h>
41#include <bits/stl_function.h>
42#include <bits/allocator.h>
43#include <bits/allocated_ptr.h>
44#include <bits/ptr_traits.h>
45#include <debug/assertions.h>
46#include <ext/alloc_traits.h>
47#include <ext/aligned_buffer.h>
48#include <debug/assertions.h>
49#if __glibcxx_ranges_to_container // C++ >= 23
50# include <bits/ranges_base.h> // ranges::begin, ranges::distance etc.
51# include <bits/ranges_util.h> // ranges::subrange
52#endif
53
54#if ! defined _GLIBCXX_USE_ALLOC_PTR_FOR_FWD_LIST
55# define _GLIBCXX_USE_ALLOC_PTR_FOR_FWD_LIST 1
56#endif
57
58namespace std _GLIBCXX_VISIBILITY(default)
59{
60_GLIBCXX_BEGIN_NAMESPACE_VERSION
61_GLIBCXX_BEGIN_NAMESPACE_CONTAINER
62
63 /**
64 * @brief A helper basic node class for %forward_list.
65 *
66 * This is just a linked list with nothing inside it.
67 * There are purely list shuffling utility methods here.
68 */
70 {
72
73 _Fwd_list_node_base() = default;
75 : _M_next(__x._M_next)
76 { __x._M_next = nullptr; }
77
79 _Fwd_list_node_base& operator=(const _Fwd_list_node_base&) = delete;
80
82 operator=(_Fwd_list_node_base&& __x) noexcept
83 {
84 _M_next = __x._M_next;
85 __x._M_next = nullptr;
86 return *this;
87 }
88
89 _Fwd_list_node_base* _M_next = nullptr;
90
92 _M_transfer_after(_Fwd_list_node_base* __begin,
93 _Fwd_list_node_base* __end) noexcept
94 {
95 _Fwd_list_node_base* __keep = __begin->_M_next;
96 if (__end)
97 {
98 __begin->_M_next = __end->_M_next;
99 __end->_M_next = _M_next;
100 }
101 else
102 __begin->_M_next = nullptr;
103 _M_next = __keep;
104 return __end;
105 }
106
107 void
108 _M_reverse_after() noexcept
109 {
110 _Fwd_list_node_base* __tail = _M_next;
111 if (!__tail)
112 return;
113 while (_Fwd_list_node_base* __temp = __tail->_M_next)
114 {
115 _Fwd_list_node_base* __keep = _M_next;
116 _M_next = __temp;
117 __tail->_M_next = __temp->_M_next;
118 _M_next->_M_next = __keep;
119 }
120 }
121
122 _Fwd_list_node_base* _M_base_ptr() { return this; }
123 const _Fwd_list_node_base* _M_base_ptr() const { return this; }
124 };
125
126 /**
127 * @brief A helper node class for %forward_list.
128 * This is just a linked list with uninitialized storage for a
129 * data value in each node.
130 * There is a sorting utility method.
131 */
132 template<typename _Tp>
134 : public _Fwd_list_node_base
135 {
136 using _Node_ptr = _Fwd_list_node*;
137
138 _Fwd_list_node() = default;
139
140 __gnu_cxx::__aligned_buffer<_Tp> _M_storage;
141
142 _Tp*
143 _M_valptr() noexcept
144 { return _M_storage._M_ptr(); }
145
146 const _Tp*
147 _M_valptr() const noexcept
148 { return _M_storage._M_ptr(); }
149
151 _M_node_ptr()
152 { return this; }
153 };
154
155 template<typename _Tp> struct _Fwd_list_const_iterator;
156
157 /**
158 * @brief A forward_list::iterator.
159 *
160 * All the functions are op overloads.
161 */
162 template<typename _Tp>
164 {
165 typedef _Fwd_list_iterator<_Tp> _Self;
166 typedef _Fwd_list_node<_Tp> _Node;
167
168 typedef _Tp value_type;
169 typedef _Tp* pointer;
170 typedef _Tp& reference;
171 typedef ptrdiff_t difference_type;
173
174 _Fwd_list_iterator() noexcept
175 : _M_node() { }
176
177 explicit
179 : _M_node(__n) { }
180
181 [[__nodiscard__]]
182 reference
183 operator*() const noexcept
184 { return *static_cast<_Node*>(this->_M_node)->_M_valptr(); }
185
186 [[__nodiscard__]]
187 pointer
188 operator->() const noexcept
189 { return static_cast<_Node*>(this->_M_node)->_M_valptr(); }
190
191 _Self&
192 operator++() noexcept
193 {
194 _M_node = _M_node->_M_next;
195 return *this;
196 }
197
198 _Self
199 operator++(int) noexcept
200 {
201 _Self __tmp(*this);
202 _M_node = _M_node->_M_next;
203 return __tmp;
204 }
205
206 /**
207 * @brief Forward list iterator equality comparison.
208 */
209 [[__nodiscard__]]
210 friend bool
211 operator==(const _Self& __x, const _Self& __y) noexcept
212 { return __x._M_node == __y._M_node; }
213
214#if __cpp_impl_three_way_comparison < 201907L
215 /**
216 * @brief Forward list iterator inequality comparison.
217 */
218 [[__nodiscard__]]
219 friend bool
220 operator!=(const _Self& __x, const _Self& __y) noexcept
221 { return __x._M_node != __y._M_node; }
222#endif
223
224 private:
225 template<typename, typename>
226 friend class forward_list;
227 template<typename, typename>
228 friend struct _Fwd_list_base;
229 friend struct _Fwd_list_const_iterator<_Tp>;
230
231 _Self
232 _M_next() const noexcept
233 {
234 if (_M_node)
235 return _Fwd_list_iterator(_M_node->_M_next);
236 else
237 return _Fwd_list_iterator(nullptr);
238 }
239
240 _Fwd_list_node_base* _M_node;
241 };
242
243 /**
244 * @brief A forward_list::const_iterator.
245 *
246 * All the functions are op overloads.
247 */
248 template<typename _Tp>
250 {
252 typedef const _Fwd_list_node<_Tp> _Node;
253 typedef _Fwd_list_iterator<_Tp> iterator;
254
255 typedef _Tp value_type;
256 typedef const _Tp* pointer;
257 typedef const _Tp& reference;
258 typedef ptrdiff_t difference_type;
260
261 _Fwd_list_const_iterator() noexcept
262 : _M_node() { }
263
264 explicit
266 : _M_node(__n) { }
267
268 _Fwd_list_const_iterator(const iterator& __iter) noexcept
269 : _M_node(__iter._M_node) { }
270
271 [[__nodiscard__]]
272 reference
273 operator*() const noexcept
274 { return *static_cast<_Node*>(this->_M_node)->_M_valptr(); }
275
276 [[__nodiscard__]]
277 pointer
278 operator->() const noexcept
279 { return static_cast<_Node*>(this->_M_node)->_M_valptr(); }
280
281 _Self&
282 operator++() noexcept
283 {
284 _M_node = _M_node->_M_next;
285 return *this;
286 }
287
288 _Self
289 operator++(int) noexcept
290 {
291 _Self __tmp(*this);
292 _M_node = _M_node->_M_next;
293 return __tmp;
294 }
295
296 /**
297 * @brief Forward list const_iterator equality comparison.
298 */
299 [[__nodiscard__]]
300 friend bool
301 operator==(const _Self& __x, const _Self& __y) noexcept
302 { return __x._M_node == __y._M_node; }
303
304#if __cpp_impl_three_way_comparison < 201907L
305 /**
306 * @brief Forward list const_iterator inequality comparison.
307 */
308 [[__nodiscard__]]
309 friend bool
310 operator!=(const _Self& __x, const _Self& __y) noexcept
311 { return __x._M_node != __y._M_node; }
312#endif
313
314 private:
315 template<typename, typename>
316 friend class forward_list;
317 template<typename, typename>
318 friend struct _Fwd_list_base;
319
320 _Self
321 _M_next() const noexcept
322 {
323 if (this->_M_node)
324 return _Fwd_list_const_iterator(_M_node->_M_next);
325 else
326 return _Fwd_list_const_iterator(nullptr);
327 }
328
329 _Fwd_list_iterator<_Tp>
330 _M_const_cast() const noexcept
331 {
332 return _Fwd_list_iterator<_Tp>(
333 const_cast<_Fwd_list_node_base*>(_M_node));
334 }
335
336 const _Fwd_list_node_base* _M_node;
337 };
338
339 template<typename _Tp, typename _Allocator> class forward_list;
340 template<typename _Tp, typename _Allocator> struct _Fwd_list_base;
341
342namespace __fwdlist
343{
344#if _GLIBCXX_USE_ALLOC_PTR_FOR_FWD_LIST
345 /// The node-base type for allocators that use fancy pointers.
346 template<typename _VoidPtr>
347 struct _Node_base
348 {
349 using _Base_ptr = __ptr_rebind<_VoidPtr, _Node_base>;
350
351 _Node_base() = default;
352
353 _Node_base(_Node_base&& __x) noexcept
354 : _M_next(__x._M_next)
355 { __x._M_next = nullptr; }
356
357 _Node_base(const _Node_base&) = delete;
358 _Node_base& operator=(const _Node_base&) = delete;
359
360 _Node_base&
361 operator=(_Node_base&& __x) noexcept
362 {
363 _M_next = __x._M_next;
364 __x._M_next = nullptr;
365 return *this;
366 }
367
368 _Base_ptr _M_next = nullptr;
369
370 // Splice (begin,end) before _M_next.
371 _Base_ptr
372 _M_transfer_after(_Base_ptr __begin, _Base_ptr __end) noexcept
373 {
374 _Base_ptr __keep = __begin->_M_next;
375 if (__end)
376 {
377 __begin->_M_next = __end->_M_next;
378 __end->_M_next = _M_next;
379 }
380 else
381 __begin->_M_next = nullptr;
382 _M_next = __keep;
383 return __end;
384 }
385
386 void
387 _M_reverse_after() noexcept
388 {
389 _Base_ptr __tail = _M_next;
390 if (!__tail)
391 return;
392 while (_Base_ptr __temp = __tail->_M_next)
393 {
394 _Base_ptr __keep = _M_next;
395 _M_next = __temp;
396 __tail->_M_next = __temp->_M_next;
397 _M_next->_M_next = __keep;
398 }
399 }
400
401 // This is not const-correct, but it's only used in a const access path
402 // by std::forward_list::empty(), where it doesn't escape, and by
403 // std::forward_list::before_begin() const, where the pointer is used
404 // to initialize a const_iterator and so constness is restored.
405 _Base_ptr
406 _M_base_ptr() const
407 {
408 return pointer_traits<_Base_ptr>::
409 pointer_to(const_cast<_Node_base&>(*this));
410 }
411 };
412
413 /**
414 * @brief A helper node class for %forward_list.
415 */
416 template<typename _ValPtr>
417 struct _Node
418 : public _Node_base<__ptr_rebind<_ValPtr, void>>
419 {
420 using value_type = typename pointer_traits<_ValPtr>::element_type;
421 using _Node_ptr = __ptr_rebind<_ValPtr, _Node>;
422
423 _Node() { }
424 ~_Node() { }
425 _Node(_Node&&) = delete;
426
427 union {
428#if ! _GLIBCXX_INLINE_VERSION
429 // For ABI compatibility we need to overalign this member.
430 alignas(__alignof__(value_type)) // XXX GLIBCXX_ABI Deprecated
431#endif
432 value_type _M_data;
433 };
434
435 value_type*
436 _M_valptr() noexcept
437 { return std::__addressof(_M_data); }
438
439 const value_type*
440 _M_valptr() const noexcept
441 { return std::__addressof(_M_data); }
442
443 _Node_ptr
444 _M_node_ptr()
445 { return pointer_traits<_Node_ptr>::pointer_to(*this); }
446 };
447
448 /// A forward_list iterator when the allocator uses fancy pointers.
449 template<bool _Const, typename _Ptr>
450 class _Iterator
451 {
452 using _Node = __fwdlist::_Node<_Ptr>;
453 using _Base_ptr
454 = typename __fwdlist::_Node_base<__ptr_rebind<_Ptr, void>>::_Base_ptr;
455
456 template<typename _Tp>
457 using __maybe_const = __conditional_t<_Const, const _Tp, _Tp>;
458
459 public:
460 using value_type = typename pointer_traits<_Ptr>::element_type;
461 using difference_type = ptrdiff_t;
462 using iterator_category = forward_iterator_tag;
463 using pointer = __maybe_const<value_type>*;
464 using reference = __maybe_const<value_type>&;
465
466 constexpr _Iterator() noexcept : _M_node() { }
467
468 _Iterator(const _Iterator&) = default;
469 _Iterator& operator=(const _Iterator&) = default;
470
471#ifdef __glibcxx_concepts
472 constexpr
473 _Iterator(const _Iterator<false, _Ptr>& __i) requires _Const
474#else
475 template<bool _OtherConst,
476 typename = __enable_if_t<_Const && !_OtherConst>>
477 constexpr
478 _Iterator(const _Iterator<_OtherConst, _Ptr>& __i)
479#endif
480 : _M_node(__i._M_node) { }
481
482 constexpr explicit
483 _Iterator(_Base_ptr __x) noexcept
484 : _M_node(__x) { }
485
486 [[__nodiscard__]]
487 constexpr reference
488 operator*() const noexcept
489 { return static_cast<_Node&>(*this->_M_node)._M_data; }
490
491 [[__nodiscard__]]
492 constexpr pointer
493 operator->() const noexcept
494 { return static_cast<_Node&>(*this->_M_node)._M_valptr(); }
495
496 _GLIBCXX14_CONSTEXPR _Iterator&
497 operator++() noexcept
498 {
499 _M_node = _M_node->_M_next;
500 return *this;
501 }
502
503 _GLIBCXX14_CONSTEXPR _Iterator
504 operator++(int) noexcept
505 {
506 _Iterator __tmp(*this);
507 _M_node = _M_node->_M_next;
508 return __tmp;
509 }
510
511 /**
512 * @brief Forward list iterator equality comparison.
513 */
514 [[__nodiscard__]]
515 friend constexpr bool
516 operator==(const _Iterator& __x, const _Iterator& __y) noexcept
517 { return __x._M_node == __y._M_node; }
518
519#if __cpp_impl_three_way_comparison < 201907L
520 /**
521 * @brief Forward list iterator inequality comparison.
522 */
523 [[__nodiscard__]]
524 friend constexpr bool
525 operator!=(const _Iterator& __x, const _Iterator& __y) noexcept
526 { return __x._M_node != __y._M_node; }
527#endif
528
529 private:
530 template<typename _Tp, typename _Allocator>
531 friend class _GLIBCXX_STD_C::forward_list;
532 template<typename _Tp, typename _Allocator>
533 friend struct _GLIBCXX_STD_C::_Fwd_list_base;
534
535 constexpr _Iterator<false, _Ptr>
536 _M_const_cast() const noexcept
537 { return _Iterator<false, _Ptr>(_M_node); }
538
539 friend _Iterator<!_Const, _Ptr>;
540
541 constexpr _Iterator
542 _M_next() const noexcept
543 { return _Iterator(_M_node ? _M_node->_M_next : nullptr); }
544
545 _Base_ptr _M_node;
546 };
547#endif // USE_ALLOC_PTR_FOR_FWD_LIST
548
549 // Determine the node and iterator types used by std::forward_list.
550 template<typename _Tp, typename _Ptr>
551 struct _Node_traits;
552
553#if _GLIBCXX_USE_ALLOC_PTR_FOR_LIST <= 9000
554 // Specialization for the simple case where the allocator's pointer type
555 // is the same type as value_type*.
556 // For ABI compatibility we can't change the types used for this case.
557 template<typename _Tp>
558 struct _Node_traits<_Tp, _Tp*>
559 {
560 using _Node_base = _Fwd_list_node_base;
561 using _Node = _Fwd_list_node<_Tp>;
562 using _Iterator = _Fwd_list_iterator<_Tp>;
563 using _Const_iterator = _Fwd_list_const_iterator<_Tp>;
564 };
565#endif
566
567#if ! _GLIBCXX_USE_ALLOC_PTR_FOR_FWD_LIST
568 // Always use the T* specialization.
569 template<typename _Tp, typename _Ptr>
570 struct _Node_traits
571 : _Node_traits<_Tp, _Tp*>
572 { };
573#else
574 // Primary template used when the allocator uses fancy pointers.
575 template<typename _Tp, typename _Ptr>
576 struct _Node_traits
577 {
578 private:
579 using _VoidPtr = __ptr_rebind<_Ptr, void>;
580 using _ValPtr = __ptr_rebind<_Ptr, _Tp>;
581
582 public:
583 using _Node_base = __fwdlist::_Node_base<_VoidPtr>;
584 using _Node = __fwdlist::_Node<_ValPtr>;
585 using _Iterator = __fwdlist::_Iterator<false, _ValPtr>;
586 using _Const_iterator = __fwdlist::_Iterator<true, _ValPtr>;
587 };
588#endif // USE_ALLOC_PTR_FOR_FWD_LIST
589} // namespace __fwdlist
590
591 /**
592 * @brief Base class for %forward_list.
593 */
594 template<typename _Tp, typename _Alloc>
596 {
597#if __cplusplus > 201703L || defined __STRICT_ANSI__
598 // The static_assert in forward_list ensures _Alloc::value_type is _Tp.
599 using pointer = typename allocator_traits<_Alloc>::pointer;
600#else
601 using _Tp_alloc_traits
602 = typename allocator_traits<_Alloc>::template rebind_traits<_Tp>;
603 using pointer = typename _Tp_alloc_traits::pointer;
604#endif
605
606 protected:
607 using _Node_traits = __fwdlist::_Node_traits<_Tp, pointer>;
608 using _Node = typename _Node_traits::_Node;
609 using _Node_alloc_type = __alloc_rebind<_Alloc, _Node>;
611 using _Node_ptr = typename _Node_alloc_traits::pointer;
612 using _Base_ptr = typename _Node_traits::_Node_base::_Base_ptr;
613
614 struct _Fwd_list_impl
615 : public _Node_alloc_type
616 {
617 typename _Node_traits::_Node_base _M_head;
618
619 _Fwd_list_impl()
621 : _Node_alloc_type(), _M_head()
622 { }
623
624 _Fwd_list_impl(_Fwd_list_impl&&) = default;
625
626 _Fwd_list_impl(_Fwd_list_impl&& __fl, _Node_alloc_type&& __a)
627 : _Node_alloc_type(std::move(__a)), _M_head(std::move(__fl._M_head))
628 { }
629
630 _Fwd_list_impl(_Node_alloc_type&& __a)
631 : _Node_alloc_type(std::move(__a)), _M_head()
632 { }
633 };
634
635 _Fwd_list_impl _M_impl;
636
637 public:
638 using iterator = typename _Node_traits::_Iterator;
639 using const_iterator = typename _Node_traits::_Const_iterator;
640
641 _Node_alloc_type&
642 _M_get_Node_allocator() noexcept
643 { return this->_M_impl; }
644
645 const _Node_alloc_type&
646 _M_get_Node_allocator() const noexcept
647 { return this->_M_impl; }
648
649 _Fwd_list_base() = default;
650
651 _Fwd_list_base(_Node_alloc_type&& __a)
652 : _M_impl(std::move(__a)) { }
653
654 // When allocators are always equal.
655 _Fwd_list_base(_Fwd_list_base&& __lst, _Node_alloc_type&& __a,
657 : _M_impl(std::move(__lst._M_impl), std::move(__a))
658 { }
659
660 // When allocators are not always equal.
661 _Fwd_list_base(_Fwd_list_base&& __lst, _Node_alloc_type&& __a);
662
663 _Fwd_list_base(_Fwd_list_base&&) = default;
664
666 { _M_erase_after(_M_impl._M_head._M_base_ptr(), nullptr); }
667
668 protected:
669#if ! _GLIBCXX_INLINE_VERSION
670 // XXX GLIBCXX_ABI Deprecated
671 _Node*
672 _M_get_node()
673 {
674 auto __ptr = _Node_alloc_traits::allocate(_M_get_Node_allocator(), 1);
675 return std::__to_address(__ptr);
676 }
677#endif
678
679 void
680 _M_put_node(_Node_ptr __p)
681 {
682#if _GLIBCXX_USE_ALLOC_PTR_FOR_FWD_LIST
683 _Node_alloc_traits::deallocate(_M_get_Node_allocator(), __p, 1);
684#else
685 typedef typename _Node_alloc_traits::pointer _Ptr;
686 auto __ptr = std::pointer_traits<_Ptr>::pointer_to(*__p);
687 _Node_alloc_traits::deallocate(_M_get_Node_allocator(), __ptr, 1);
688#endif
689 }
690
691 template<typename... _Args>
692 _Node_ptr
693 _M_create_node(_Args&&... __args)
694 {
695 auto& __alloc = _M_get_Node_allocator();
696 auto __guard = std::__allocate_guarded_obj(__alloc);
697 _Node_alloc_traits::construct(__alloc, __guard->_M_valptr(),
698 std::forward<_Args>(__args)...);
699 auto __p = __guard.release();
700#if _GLIBCXX_USE_ALLOC_PTR_FOR_FWD_LIST
701 return __p;
702#else
703 return std::__to_address(__p);
704#endif
705 }
706
707#pragma GCC diagnostic push
708#pragma GCC diagnostic ignored "-Wc++17-extensions" // if constexpr
709 void
710 _M_destroy_node(_Node_ptr __p)
711 {
712 auto& __alloc = _M_get_Node_allocator();
713 // Destroy the element
714 _Node_alloc_traits::destroy(__alloc, __p->_M_valptr());
715 // Only destroy the node if the pointers require it.
717 __p->~_Node();
718 _M_put_node(__p);
719 }
720#pragma GCC diagnostic pop
721
722 template<typename... _Args>
723 _Base_ptr
724 _M_insert_after(const_iterator __pos, _Args&&... __args);
725
726 _Base_ptr
727 _M_erase_after(_Base_ptr __pos);
728
729 _Base_ptr
730 _M_erase_after(_Base_ptr __pos, _Base_ptr __last);
731 };
732
733 /**
734 * @brief A standard container with linear time access to elements,
735 * and fixed time insertion/deletion at any point in the sequence.
736 *
737 * @ingroup sequences
738 * @headerfile forward_list
739 * @since C++11
740 *
741 * @tparam _Tp Type of element.
742 * @tparam _Alloc Allocator type, defaults to allocator<_Tp>.
743 *
744 * Meets the requirements of a <a href="tables.html#65">container</a>, a
745 * <a href="tables.html#67">sequence</a>, including the
746 * <a href="tables.html#68">optional sequence requirements</a> with the
747 * %exception of `at` and `operator[]`.
748 *
749 * This is a @e singly @e linked %list. Traversal up the
750 * %list requires linear time, but adding and removing elements (or
751 * @e nodes) is done in constant time, regardless of where the
752 * change takes place. Unlike std::vector and std::deque,
753 * random-access iterators are not provided, so subscripting (`[]`)
754 * access is not allowed. For algorithms which only need
755 * sequential access, this lack makes no difference.
756 *
757 * Also unlike the other standard containers, std::forward_list provides
758 * specialized algorithms %unique to linked lists, such as
759 * splicing, sorting, and in-place reversal.
760 */
761 template<typename _Tp, typename _Alloc = allocator<_Tp>>
762 class forward_list : private _Fwd_list_base<_Tp, _Alloc>
763 {
764 static_assert(is_same<typename remove_cv<_Tp>::type, _Tp>::value,
765 "std::forward_list must have a non-const, non-volatile value_type");
766#if __cplusplus > 201703L || defined __STRICT_ANSI__
768 "std::forward_list must have the same value_type as its allocator");
769#endif
770
771 private:
774 typedef typename _Base::_Node _Node;
775 typedef typename _Base::_Node_alloc_type _Node_alloc_type;
778
779 public:
780 // types:
781 typedef _Tp value_type;
782 typedef typename _Alloc_traits::pointer pointer;
783 typedef typename _Alloc_traits::const_pointer const_pointer;
784 typedef value_type& reference;
785 typedef const value_type& const_reference;
786
787 typedef typename _Base::iterator iterator;
788 typedef typename _Base::const_iterator const_iterator;
789 typedef std::size_t size_type;
790 typedef std::ptrdiff_t difference_type;
791 typedef _Alloc allocator_type;
792
793 // 23.3.4.2 construct/copy/destroy:
794
795 /**
796 * @brief Creates a %forward_list with no elements.
797 */
798 forward_list() = default;
799
800 /**
801 * @brief Creates a %forward_list with no elements.
802 * @param __al An allocator object.
803 */
804 explicit
805 forward_list(const _Alloc& __al) noexcept
806 : _Base(_Node_alloc_type(__al))
807 { }
808
809 /**
810 * @brief Copy constructor with allocator argument.
811 * @param __list Input list to copy.
812 * @param __al An allocator object.
813 */
815 const __type_identity_t<_Alloc>& __al)
816 : _Base(_Node_alloc_type(__al))
817 { _M_range_initialize(__list.begin(), __list.end()); }
818
819 private:
820 forward_list(forward_list&& __list, _Node_alloc_type&& __al,
822 : _Base(std::move(__list), std::move(__al))
823 {
824 // If __list is not empty it means its allocator is not equal to __a,
825 // so we need to move from each element individually.
827 std::__make_move_if_noexcept_iterator(__list.begin()),
828 std::__make_move_if_noexcept_iterator(__list.end()));
829 }
830
831 forward_list(forward_list&& __list, _Node_alloc_type&& __al,
832 true_type)
833 noexcept
834 : _Base(std::move(__list), _Node_alloc_type(__al), true_type{})
835 { }
836
837 public:
838 /**
839 * @brief Move constructor with allocator argument.
840 * @param __list Input list to move.
841 * @param __al An allocator object.
842 */
844 const __type_identity_t<_Alloc>& __al)
845 noexcept(_Node_alloc_traits::_S_always_equal())
846 : forward_list(std::move(__list), _Node_alloc_type(__al),
847 typename _Node_alloc_traits::is_always_equal{})
848 { }
849
850 /**
851 * @brief Creates a %forward_list with default constructed elements.
852 * @param __n The number of elements to initially create.
853 * @param __al An allocator object.
854 *
855 * This constructor creates the %forward_list with `__n` default
856 * constructed elements.
857 */
858 explicit
859 forward_list(size_type __n, const _Alloc& __al = _Alloc())
860 : _Base(_Node_alloc_type(__al))
861 { _M_default_initialize(__n); }
862
863 /**
864 * @brief Creates a %forward_list with copies of an exemplar element.
865 * @param __n The number of elements to initially create.
866 * @param __value An element to copy.
867 * @param __al An allocator object.
868 *
869 * This constructor fills the %forward_list with `__n` copies of
870 * `__value`.
871 */
872 forward_list(size_type __n, const _Tp& __value,
873 const _Alloc& __al = _Alloc())
874 : _Base(_Node_alloc_type(__al))
875 { _M_fill_initialize(__n, __value); }
876
877 /**
878 * @brief Builds a %forward_list from a range.
879 * @param __first An input iterator.
880 * @param __last An input iterator.
881 * @param __al An allocator object.
882 *
883 * Create a %forward_list consisting of copies of the elements from
884 * `[__first,__last)`. This is linear in N (where N is
885 * `distance(__first,__last)`).
886 */
887 template<typename _InputIterator,
888 typename = std::_RequireInputIter<_InputIterator>>
889 forward_list(_InputIterator __first, _InputIterator __last,
890 const _Alloc& __al = _Alloc())
891 : _Base(_Node_alloc_type(__al))
892 { _M_range_initialize(__first, __last); }
893
894#if __glibcxx_ranges_to_container // C++ >= 23
895 /**
896 * @brief Construct a forward_list from a range.
897 * @param __rg An input range with elements that are convertible to
898 * the forward_list's value_type.
899 * @param __a An allocator.
900 *
901 * @since C++23
902 */
903 template<__detail::__container_compatible_range<_Tp> _Rg>
904 forward_list(from_range_t, _Rg&& __rg, const _Alloc& __a = _Alloc())
905 : _Base(_Node_alloc_type(__a))
906 {
907 auto __to = this->_M_impl._M_head._M_base_ptr();
908 auto __first = ranges::begin(__rg);
909 const auto __last = ranges::end(__rg);
910 for (; __first != __last; ++__first)
911 {
912 __to->_M_next = this->_M_create_node(*__first)->_M_base_ptr();
913 __to = __to->_M_next;
914 }
915 }
916#endif // ranges_to_container
917
918 /**
919 * @brief The %forward_list copy constructor.
920 * @param __list A %forward_list of identical element and allocator
921 * types.
922 */
924 : _Base(_Node_alloc_traits::_S_select_on_copy(
925 __list._M_get_Node_allocator()))
926 { _M_range_initialize(__list.begin(), __list.end()); }
927
928 /**
929 * @brief The %forward_list move constructor.
930 * @param __list A %forward_list of identical element and allocator
931 * types.
932 *
933 * The newly-created %forward_list contains the exact contents of the
934 * moved instance. The contents of the moved instance are a valid, but
935 * unspecified %forward_list.
936 */
938
939 /**
940 * @brief Builds a %forward_list from an initializer_list
941 * @param __il An initializer_list of value_type.
942 * @param __al An allocator object.
943 *
944 * Create a %forward_list consisting of copies of the elements
945 * in the initializer_list `__il`. This is linear in `__il.size()`.
946 */
948 const _Alloc& __al = _Alloc())
949 : _Base(_Node_alloc_type(__al))
950 { _M_range_initialize(__il.begin(), __il.end()); }
951
952 /**
953 * @brief The forward_list dtor.
954 */
955 ~forward_list() noexcept
956 { }
957
958 /**
959 * @brief The %forward_list assignment operator.
960 * @param __list A %forward_list of identical element and allocator
961 * types.
962 *
963 * All the elements of `__list` are copied.
964 *
965 * Whether the allocator is copied depends on the allocator traits.
966 */
968 operator=(const forward_list& __list);
969
970#pragma GCC diagnostic push
971#pragma GCC diagnostic ignored "-Wc++17-extensions" // if constexpr
972 /**
973 * @brief The %forward_list move assignment operator.
974 * @param __list A %forward_list of identical element and allocator
975 * types.
976 *
977 * The contents of `__list` are moved into this %forward_list
978 * (without copying, if the allocators permit it).
979 *
980 * Afterwards @a __list is a valid, but unspecified %forward_list
981 *
982 * Whether the allocator is moved depends on the allocator traits.
983 */
986 noexcept(_Node_alloc_traits::_S_nothrow_move())
987 {
988 constexpr bool __move_storage =
989 _Node_alloc_traits::_S_propagate_on_move_assign()
990 || _Node_alloc_traits::_S_always_equal();
991 if constexpr (!__move_storage)
992 {
993 if (__list._M_get_Node_allocator() != this->_M_get_Node_allocator())
994 {
995 // The rvalue's allocator cannot be moved, or is not equal,
996 // so we need to individually move each element.
997 this->assign(std::make_move_iterator(__list.begin()),
998 std::make_move_iterator(__list.end()));
999 return *this;
1000 }
1001 }
1002
1003 clear();
1004 this->_M_impl._M_head._M_next = __list._M_impl._M_head._M_next;
1005 __list._M_impl._M_head._M_next = nullptr;
1006 if constexpr (_Node_alloc_traits::_S_propagate_on_move_assign())
1007 this->_M_get_Node_allocator()
1008 = std::move(__list._M_get_Node_allocator());
1009 return *this;
1010 }
1011
1012 /**
1013 * @brief The %forward_list initializer list assignment operator.
1014 * @param __il An initializer_list of value_type.
1015 *
1016 * Replace the contents of the %forward_list with copies of the
1017 * elements in the initializer_list `__il`. This is linear in
1018 * `__il.size()`.
1019 */
1022 {
1023 assign(__il);
1024 return *this;
1025 }
1026
1027 /**
1028 * @brief Assigns a range to a %forward_list.
1029 * @param __first An input iterator.
1030 * @param __last An input iterator.
1031 *
1032 * This function fills a %forward_list with copies of the elements
1033 * in the range `[ __first,__last)`.
1034 *
1035 * Note that the assignment completely changes the %forward_list and
1036 * that the number of elements of the resulting %forward_list is the
1037 * same as the number of elements assigned.
1038 */
1039 template<typename _InputIterator,
1040 typename = std::_RequireInputIter<_InputIterator>>
1041 void
1042 assign(_InputIterator __first, _InputIterator __last)
1043 {
1044 if constexpr (is_assignable<_Tp, decltype(*__first)>::value)
1045 {
1046 auto __prev = before_begin();
1047 auto __curr = begin();
1048 auto __end = end();
1049 while (__curr != __end && __first != __last)
1050 {
1051 *__curr = *__first;
1052 ++__prev;
1053 ++__curr;
1054 ++__first;
1055 }
1056 if (__first != __last)
1057 insert_after(__prev, __first, __last);
1058 else if (__curr != __end)
1059 erase_after(__prev, __end);
1060 }
1061 else
1062 {
1063 clear();
1064 insert_after(cbefore_begin(), __first, __last);
1065 }
1066 }
1067#pragma GCC diagnostic pop
1068
1069#if __glibcxx_ranges_to_container // C++ >= 23
1070 /**
1071 * @brief Assign a range to a forward_list.
1072 * @since C++23
1073 */
1074 template<__detail::__container_compatible_range<_Tp> _Rg>
1075 void
1076 assign_range(_Rg&& __rg)
1077 {
1078 static_assert(assignable_from<_Tp&, ranges::range_reference_t<_Rg>>);
1079
1080 auto __first = ranges::begin(__rg);
1081 const auto __last = ranges::end(__rg);
1082 iterator __prev = before_begin();
1083 iterator __curr = begin();
1084 const iterator __end = end();
1085
1086 while (__curr != __end && __first != __last)
1087 {
1088 *__curr = *__first;
1089 __prev = __curr;
1090 ++__first;
1091 ++__curr;
1092 }
1093
1094 if (__curr != __end)
1095 erase_after(__prev, __end);
1096 else
1097 insert_range_after(__prev,
1098 ranges::subrange(std::move(__first), __last));
1099 }
1100#endif // ranges_to_container
1101
1102#pragma GCC diagnostic push
1103#pragma GCC diagnostic ignored "-Wc++17-extensions" // if constexpr
1104 /**
1105 * @brief Assigns a given value to a %forward_list.
1106 * @param __n Number of elements to be assigned.
1107 * @param __val Value to be assigned.
1108 *
1109 * This function fills a %forward_list with `__n` copies of the
1110 * given value. Note that the assignment completely changes the
1111 * %forward_list, and that the resulting %forward_list has `__n`
1112 * elements.
1113 */
1114 void
1115 assign(size_type __n, const _Tp& __val)
1116 {
1117 if constexpr (is_copy_assignable<_Tp>::value)
1118 {
1119 auto __prev = before_begin();
1120 auto __curr = begin();
1121 auto __end = end();
1122 while (__curr != __end && __n > 0)
1123 {
1124 *__curr = __val;
1125 ++__prev;
1126 ++__curr;
1127 --__n;
1128 }
1129 if (__n > 0)
1130 insert_after(__prev, __n, __val);
1131 else if (__curr != __end)
1132 erase_after(__prev, __end);
1133 }
1134 else
1135 {
1136 clear();
1137 insert_after(cbefore_begin(), __n, __val);
1138 }
1139 }
1140#pragma GCC diagnostic pop
1141
1142 /**
1143 * @brief Assigns an initializer_list to a %forward_list.
1144 * @param __il An initializer_list of value_type.
1145 *
1146 * Replace the contents of the %forward_list with copies of the
1147 * elements in the initializer_list `__il`. This is linear in
1148 * `__il.size()`.
1149 */
1150 void
1152 { assign(__il.begin(), __il.end()); }
1153
1154 /// Get a copy of the memory allocation object.
1155 allocator_type
1156 get_allocator() const noexcept
1157 { return allocator_type(this->_M_get_Node_allocator()); }
1158
1159 // 23.3.4.3 iterators:
1160
1161 /**
1162 * Returns a read/write iterator that points before the first element
1163 * in the %forward_list. Iteration is done in ordinary element order.
1164 */
1165 [[__nodiscard__]]
1166 iterator
1167 before_begin() noexcept
1168 { return iterator(this->_M_impl._M_head._M_base_ptr()); }
1169
1170 /**
1171 * Returns a read-only (constant) iterator that points before the
1172 * first element in the %forward_list. Iteration is done in ordinary
1173 * element order.
1174 */
1175 [[__nodiscard__]]
1176 const_iterator
1177 before_begin() const noexcept
1178 { return const_iterator(this->_M_impl._M_head._M_base_ptr()); }
1179
1180 /**
1181 * Returns a read/write iterator that points to the first element
1182 * in the %forward_list. Iteration is done in ordinary element order.
1183 */
1184 [[__nodiscard__]]
1185 iterator
1186 begin() noexcept
1187 { return iterator(this->_M_impl._M_head._M_next); }
1188
1189 /**
1190 * Returns a read-only (constant) iterator that points to the first
1191 * element in the %forward_list. Iteration is done in ordinary
1192 * element order.
1193 */
1194 [[__nodiscard__]]
1195 const_iterator
1196 begin() const noexcept
1197 { return const_iterator(this->_M_impl._M_head._M_next); }
1198
1199 /**
1200 * Returns a read/write iterator that points one past the last
1201 * element in the %forward_list. Iteration is done in ordinary
1202 * element order.
1203 */
1204 [[__nodiscard__]]
1205 iterator
1206 end() noexcept
1207 { return iterator(nullptr); }
1208
1209 /**
1210 * Returns a read-only iterator that points one past the last
1211 * element in the %forward_list. Iteration is done in ordinary
1212 * element order.
1213 */
1214 [[__nodiscard__]]
1215 const_iterator
1216 end() const noexcept
1217 { return const_iterator(nullptr); }
1218
1219 /**
1220 * Returns a read-only (constant) iterator that points to the
1221 * first element in the %forward_list. Iteration is done in ordinary
1222 * element order.
1223 */
1224 [[__nodiscard__]]
1225 const_iterator
1226 cbegin() const noexcept
1227 { return const_iterator(this->_M_impl._M_head._M_next); }
1228
1229 /**
1230 * Returns a read-only (constant) iterator that points before the
1231 * first element in the %forward_list. Iteration is done in ordinary
1232 * element order.
1233 */
1234 [[__nodiscard__]]
1235 const_iterator
1236 cbefore_begin() const noexcept
1237 { return const_iterator(this->_M_impl._M_head._M_base_ptr()); }
1238
1239 /**
1240 * Returns a read-only (constant) iterator that points one past
1241 * the last element in the %forward_list. Iteration is done in
1242 * ordinary element order.
1243 */
1244 [[__nodiscard__]]
1245 const_iterator
1246 cend() const noexcept
1247 { return const_iterator(nullptr); }
1248
1249 /**
1250 * Returns true if the %forward_list is empty. (Thus begin() would
1251 * equal end().)
1252 */
1253 [[__nodiscard__]]
1254 bool
1255 empty() const noexcept
1256 { return this->_M_impl._M_head._M_next == nullptr; }
1257
1258 /**
1259 * Returns the largest possible number of elements of %forward_list.
1260 */
1261 [[__nodiscard__]]
1262 size_type
1263 max_size() const noexcept
1264 { return _Node_alloc_traits::max_size(this->_M_get_Node_allocator()); }
1265
1266 // 23.3.4.4 element access:
1267
1268 /**
1269 * Returns a read/write reference to the data at the first
1270 * element of the %forward_list.
1271 */
1272 [[__nodiscard__]]
1273 reference
1275 {
1276 __glibcxx_requires_nonempty();
1277 _Node& __front = static_cast<_Node&>(*this->_M_impl._M_head._M_next);
1278 return *__front._M_valptr();
1279 }
1280
1281 /**
1282 * Returns a read-only (constant) reference to the data at the first
1283 * element of the %forward_list.
1284 */
1285 [[__nodiscard__]]
1286 const_reference
1287 front() const
1288 {
1289 __glibcxx_requires_nonempty();
1290 _Node& __front = static_cast<_Node&>(*this->_M_impl._M_head._M_next);
1291 return *__front._M_valptr();
1292 }
1293
1294 // 23.3.4.5 modifiers:
1295
1296 /**
1297 * @brief Constructs object in %forward_list at the front of the
1298 * list.
1299 * @param __args Arguments.
1300 *
1301 * This function will insert an object of type `Tp` constructed
1302 * with `Tp(std::forward<Args>(args)...)` at the front of the list
1303 * Due to the nature of a %forward_list this operation can
1304 * be done in constant time, and does not invalidate iterators
1305 * and references.
1306 */
1307 template<typename... _Args>
1308#if __cplusplus > 201402L
1309 reference
1310#else
1311 void
1312#endif
1313 emplace_front(_Args&&... __args)
1314 {
1315 this->_M_insert_after(cbefore_begin(),
1316 std::forward<_Args>(__args)...);
1317#if __cplusplus > 201402L
1318 return front();
1319#endif
1320 }
1321
1322 /**
1323 * @brief Add data to the front of the %forward_list.
1324 * @param __val Data to be added.
1325 *
1326 * This is a typical stack operation. The function creates an
1327 * element at the front of the %forward_list and assigns the given
1328 * data to it. Due to the nature of a %forward_list this operation
1329 * can be done in constant time, and does not invalidate iterators
1330 * and references.
1331 */
1332 void
1333 push_front(const _Tp& __val)
1334 { this->_M_insert_after(cbefore_begin(), __val); }
1335
1336 /**
1337 *
1338 */
1339 void
1340 push_front(_Tp&& __val)
1341 { this->_M_insert_after(cbefore_begin(), std::move(__val)); }
1342
1343#if __glibcxx_ranges_to_container // C++ >= 23
1344 /**
1345 * @brief Insert a range at the beginning of a forward_list.
1346 * @param __rg An input range with elements that are convertible to
1347 * the forward_list's value_type.
1348 *
1349 * The inserted elements will be in the same order as in the range,
1350 * so they are not reversed as would happen with a simple loop calling
1351 * `emplace_front` for each element of the range.
1352 *
1353 * No iterators to existing elements are invalidated by this function.
1354 * If the insertion fails due to an exception, no elements will be added
1355 * and so the list will be unchanged.
1356 *
1357 * @since C++23
1358 */
1359 template<__detail::__container_compatible_range<_Tp> _Rg>
1360 void
1361 prepend_range(_Rg&& __rg)
1362 {
1363 forward_list __tmp(from_range, std::forward<_Rg>(__rg),
1364 get_allocator());
1365 if (!__tmp.empty())
1366 splice_after(before_begin(), __tmp);
1367 }
1368#endif // ranges_to_container
1369
1370 /**
1371 * @brief Removes first element.
1372 *
1373 * This is a typical stack operation. It shrinks the %forward_list
1374 * by one. Due to the nature of a %forward_list this operation can
1375 * be done in constant time, and only invalidates iterators/references
1376 * to the element being removed.
1377 *
1378 * Note that no data is returned, and if the first element's data
1379 * is needed, it should be retrieved before `pop_front()` is
1380 * called.
1381 */
1382 void
1384 {
1385 __glibcxx_requires_nonempty();
1386 this->_M_erase_after(this->_M_impl._M_head._M_base_ptr());
1387 }
1388
1389 /**
1390 * @brief Constructs object in %forward_list after the specified
1391 * iterator.
1392 * @param __pos A const_iterator into the %forward_list.
1393 * @param __args Arguments.
1394 * @return An iterator that points to the inserted data.
1395 *
1396 * This function will insert an object of type `T` constructed
1397 * with `T(std::forward<Args>(args)...)` after the specified
1398 * location. Due to the nature of a %forward_list this operation can
1399 * be done in constant time, and does not invalidate iterators
1400 * and references.
1401 */
1402 template<typename... _Args>
1403 iterator
1404 emplace_after(const_iterator __pos, _Args&&... __args)
1405 { return iterator(this->_M_insert_after(__pos,
1406 std::forward<_Args>(__args)...)); }
1407
1408 /**
1409 * @brief Inserts given value into %forward_list after specified
1410 * iterator.
1411 * @param __pos An iterator into the %forward_list.
1412 * @param __val Data to be inserted.
1413 * @return An iterator that points to the inserted data.
1414 *
1415 * This function will insert a copy of the given value after
1416 * the specified location. Due to the nature of a %forward_list this
1417 * operation can be done in constant time, and does not
1418 * invalidate iterators and references.
1419 */
1420 iterator
1421 insert_after(const_iterator __pos, const _Tp& __val)
1422 { return iterator(this->_M_insert_after(__pos, __val)); }
1423
1424 /**
1425 *
1426 */
1427 iterator
1428 insert_after(const_iterator __pos, _Tp&& __val)
1429 { return iterator(this->_M_insert_after(__pos, std::move(__val))); }
1430
1431 /**
1432 * @brief Inserts a number of copies of given data into the
1433 * %forward_list.
1434 * @param __pos An iterator into the %forward_list.
1435 * @param __n Number of elements to be inserted.
1436 * @param __val Data to be inserted.
1437 * @return An iterator pointing to the last inserted copy of
1438 * `val` or `pos` if `n == 0`.
1439 *
1440 * This function will insert a specified number of copies of the
1441 * given data after the location specified by `pos`.
1442 *
1443 * This operation is linear in the number of elements inserted and
1444 * does not invalidate iterators and references.
1445 */
1446 iterator
1447 insert_after(const_iterator __pos, size_type __n, const _Tp& __val);
1448
1449 /**
1450 * @brief Inserts a range into the %forward_list.
1451 * @param __pos An iterator into the %forward_list.
1452 * @param __first An input iterator.
1453 * @param __last An input iterator.
1454 * @return An iterator pointing to the last inserted element or
1455 * `__pos` if `__first == __last`.
1456 *
1457 * This function will insert copies of the data in the range
1458 * `[ __first, __last)` into the %forward_list after the
1459 * location specified by `__pos.
1460 *
1461 * This operation is linear in the number of elements inserted and
1462 * does not invalidate iterators and references.
1463 */
1464 template<typename _InputIterator,
1465 typename = std::_RequireInputIter<_InputIterator>>
1466 iterator
1467 insert_after(const_iterator __pos,
1468 _InputIterator __first, _InputIterator __last);
1469
1470 /**
1471 * @brief Inserts the contents of an initializer_list into
1472 * %forward_list after the specified iterator.
1473 * @param __pos An iterator into the %forward_list.
1474 * @param __il An initializer_list of value_type.
1475 * @return An iterator pointing to the last inserted element
1476 * or `__pos` if `__il` is empty.
1477 *
1478 * This function will insert copies of the data in the
1479 * initializer_list `__il` into the %forward_list before the location
1480 * specified by `__pos`.
1481 *
1482 * This operation is linear in the number of elements inserted and
1483 * does not invalidate iterators and references.
1484 */
1485 iterator
1486 insert_after(const_iterator __pos, std::initializer_list<_Tp> __il)
1487 { return insert_after(__pos, __il.begin(), __il.end()); }
1488
1489#if __glibcxx_ranges_to_container // C++ >= 23
1490 /**
1491 * @brief Insert a rangeinto a forward_list.
1492 * @param __position An iterator.
1493 * @param __rg An input range of elements that can be converted to
1494 * the forward_list's value type.
1495 * @return An iterator pointing to the last element inserted,
1496 * or `__position` if the range is empty.
1497 *
1498 * Inserts the elements of `__rg` after `__position`.
1499 * No iterators to existing elements are invalidated by this function.
1500 * If the insertion fails due to an exception, no elements will be added
1501 * and so the list will be unchanged.
1502 *
1503 * @since C++23
1504 */
1505 template<__detail::__container_compatible_range<_Tp> _Rg>
1506 iterator
1507 insert_range_after(const_iterator __position, _Rg&& __rg)
1508 {
1509 forward_list __tmp(from_range, std::forward<_Rg>(__rg),
1510 get_allocator());
1511 return _M_splice_after(__position, __tmp.before_begin(), __tmp.end());
1512 }
1513#endif // ranges_to_container
1514
1515 /**
1516 * @brief Removes the element pointed to by the iterator following
1517 * `pos`.
1518 * @param __pos Iterator pointing before element to be erased.
1519 * @return An iterator pointing to the element following the one
1520 * that was erased, or `end()` if no such element exists.
1521 *
1522 * This function will erase the element at the given position and
1523 * thus shorten the %forward_list by one.
1524 *
1525 * Due to the nature of a %forward_list this operation can be done
1526 * in constant time, and only invalidates iterators/references to
1527 * the element being removed. The user is also cautioned that
1528 * this function only erases the element, and that if the element
1529 * is itself a pointer, the pointed-to memory is not touched in
1530 * any way. Managing the pointer is the user's responsibility.
1531 */
1532 iterator
1533 erase_after(const_iterator __pos)
1534 { return iterator(this->_M_erase_after(__pos._M_const_cast()._M_node)); }
1535
1536 /**
1537 * @brief Remove a range of elements.
1538 * @param __pos Iterator pointing before the first element to be
1539 * erased.
1540 * @param __last Iterator pointing to one past the last element to be
1541 * erased.
1542 * @return `__last`
1543 *
1544 * This function will erase the elements in the range
1545 * `(__pos,__last)` and shorten the %forward_list accordingly.
1546 *
1547 * This operation is linear time in the size of the range and only
1548 * invalidates iterators/references to the element being removed.
1549 *
1550 * The user is also cautioned that this function only erases the
1551 * elements, and that if the elements themselves are pointers, the
1552 * pointed-to memory is not touched in any way. Managing the pointer
1553 * is the user's responsibility.
1554 */
1555 iterator
1556 erase_after(const_iterator __pos, const_iterator __last)
1557 {
1558 return iterator(this->_M_erase_after(__pos._M_const_cast()._M_node,
1559 __last._M_const_cast()._M_node));
1560 }
1561
1562 /**
1563 * @brief Swaps data with another %forward_list.
1564 * @param __list A %forward_list of the same element and allocator
1565 * types.
1566 *
1567 * This exchanges the elements between two lists in constant
1568 * time. Note that the global `std::swap()` function is
1569 * overloaded such that `std::swap(l1, l2)` will feed to this
1570 * function.
1571 *
1572 * Whether the allocators are swapped depends on the allocator traits.
1573 */
1574 void
1575 swap(forward_list& __list) noexcept
1576 {
1577 std::swap(this->_M_impl._M_head._M_next,
1578 __list._M_impl._M_head._M_next);
1579 _Node_alloc_traits::_S_on_swap(this->_M_get_Node_allocator(),
1580 __list._M_get_Node_allocator());
1581 }
1582
1583 /**
1584 * @brief Resizes the %forward_list to the specified number of
1585 * elements.
1586 * @param __sz Number of elements the %forward_list should contain.
1587 *
1588 * This function will %resize the %forward_list to the specified
1589 * number of elements. If the number is smaller than the
1590 * %forward_list's current number of elements the %forward_list
1591 * is truncated, otherwise the %forward_list is extended and the
1592 * new elements are default constructed.
1593 */
1594 void
1595 resize(size_type __sz);
1596
1597 /**
1598 * @brief Resizes the %forward_list to the specified number of
1599 * elements.
1600 * @param __sz Number of elements the %forward_list should contain.
1601 * @param __val Data with which new elements should be populated.
1602 *
1603 * This function will %resize the %forward_list to the specified
1604 * number of elements. If the number is smaller than the
1605 * %forward_list's current number of elements the %forward_list
1606 * is truncated, otherwise the %forward_list is extended and new
1607 * elements are populated with given data.
1608 */
1609 void
1610 resize(size_type __sz, const value_type& __val);
1611
1612 /**
1613 * @brief Erases all the elements.
1614 *
1615 * Note that this function only erases
1616 * the elements, and that if the elements themselves are
1617 * pointers, the pointed-to memory is not touched in any way.
1618 * Managing the pointer is the user's responsibility.
1619 */
1620 void
1621 clear() noexcept
1622 { this->_M_erase_after(this->_M_impl._M_head._M_base_ptr(), nullptr); }
1623
1624 // 23.3.4.6 forward_list operations:
1625
1626 /**
1627 * @brief Insert contents of another %forward_list.
1628 * @param __pos Iterator referencing the element to insert after.
1629 * @param __list Source list.
1630 *
1631 * The elements of `list` are inserted in constant time after
1632 * the element referenced by `pos`. `list` becomes an empty
1633 * list.
1634 *
1635 * Requires `this != &x`.
1636 */
1637 void
1638 splice_after(const_iterator __pos, forward_list&& __list) noexcept
1639 {
1640 if (!__list.empty())
1641 _M_splice_after(__pos, __list.before_begin(), __list.end());
1642 }
1643
1644 void
1645 splice_after(const_iterator __pos, forward_list& __list) noexcept
1646 { splice_after(__pos, std::move(__list)); }
1647
1648 /**
1649 * @brief Insert element from another %forward_list.
1650 * @param __pos Iterator referencing the element to insert after.
1651 * @param __list Source list.
1652 * @param __i Iterator referencing the element before the element
1653 * to move.
1654 *
1655 * Removes the element in list `__list` referenced by `__i` and
1656 * inserts it into the current list after `__pos`.
1657 */
1658 void
1659 splice_after(const_iterator __pos, forward_list&& __list,
1660 const_iterator __i) noexcept;
1661
1662 void
1663 splice_after(const_iterator __pos, forward_list& __list,
1664 const_iterator __i) noexcept
1665 { splice_after(__pos, std::move(__list), __i); }
1666
1667 /**
1668 * @brief Insert range from another %forward_list.
1669 * @param __pos Iterator referencing the element to insert after.
1670 * @param __list Source list.
1671 * @param __before Iterator referencing before the start of range
1672 * in `__list`.
1673 * @param __last Iterator referencing the end of range in `__list`.
1674 *
1675 * Removes elements in the range `(__before,__last)` and inserts them
1676 * after `__pos` in constant time.
1677 *
1678 * Undefined if `__pos` is in `(__before,__last)`.
1679 * @{
1680 */
1681 void
1682 splice_after(const_iterator __pos, forward_list&&,
1683 const_iterator __before, const_iterator __last) noexcept
1684 { _M_splice_after(__pos, __before, __last); }
1685
1686 void
1687 splice_after(const_iterator __pos, forward_list&,
1688 const_iterator __before, const_iterator __last) noexcept
1689 { _M_splice_after(__pos, __before, __last); }
1690 /// @}
1691
1692 private:
1693#ifdef __glibcxx_list_remove_return_type // C++20 && HOSTED
1694 using __remove_return_type = size_type;
1695# define _GLIBCXX_FWDLIST_REMOVE_RETURN_TYPE_TAG \
1696 __attribute__((__abi_tag__("__cxx20")))
1697#else
1698 using __remove_return_type = void;
1699# define _GLIBCXX_FWDLIST_REMOVE_RETURN_TYPE_TAG
1700#endif
1701 public:
1702
1703 /**
1704 * @brief Remove all elements equal to value.
1705 * @param __val The value to remove.
1706 *
1707 * Removes every element in the list equal to `__val`.
1708 * Remaining elements stay in list order. Note that this
1709 * function only erases the elements, and that if the elements
1710 * themselves are pointers, the pointed-to memory is not
1711 * touched in any way. Managing the pointer is the user's
1712 * responsibility.
1713 */
1714 _GLIBCXX_FWDLIST_REMOVE_RETURN_TYPE_TAG
1715 __remove_return_type
1716 remove(const _Tp& __val);
1717
1718 /**
1719 * @brief Remove all elements satisfying a predicate.
1720 * @param __pred Unary predicate function or object.
1721 *
1722 * Removes every element in the list for which the predicate
1723 * returns true. Remaining elements stay in list order. Note
1724 * that this function only erases the elements, and that if the
1725 * elements themselves are pointers, the pointed-to memory is
1726 * not touched in any way. Managing the pointer is the user's
1727 * responsibility.
1728 */
1729 template<typename _Pred>
1730 __remove_return_type
1731 remove_if(_Pred __pred);
1732
1733 /**
1734 * @brief Remove consecutive duplicate elements.
1735 *
1736 * For each consecutive set of elements with the same value,
1737 * remove all but the first one. Remaining elements stay in
1738 * list order. Note that this function only erases the
1739 * elements, and that if the elements themselves are pointers,
1740 * the pointed-to memory is not touched in any way. Managing
1741 * the pointer is the user's responsibility.
1742 */
1743 _GLIBCXX_FWDLIST_REMOVE_RETURN_TYPE_TAG
1744 __remove_return_type
1746 { return unique(std::equal_to<_Tp>()); }
1747
1748#undef _GLIBCXX_FWDLIST_REMOVE_RETURN_TYPE_TAG
1749
1750 /**
1751 * @brief Remove consecutive elements satisfying a predicate.
1752 * @param __binary_pred Binary predicate function or object.
1753 *
1754 * For each consecutive set of elements [first,last) that
1755 * satisfy predicate(first,i) where i is an iterator in
1756 * [first,last), remove all but the first one. Remaining
1757 * elements stay in list order. Note that this function only
1758 * erases the elements, and that if the elements themselves are
1759 * pointers, the pointed-to memory is not touched in any way.
1760 * Managing the pointer is the user's responsibility.
1761 */
1762 template<typename _BinPred>
1763 __remove_return_type
1764 unique(_BinPred __binary_pred);
1765
1766 /**
1767 * @brief Merge sorted lists.
1768 * @param __list Sorted list to merge.
1769 *
1770 * Assumes that both `__list` and this list are sorted according to
1771 * operator<(). Merges elements of `__list` into this list in
1772 * sorted order, leaving `__list` empty when complete. Elements in
1773 * this list precede elements in `__list` that are equal.
1774 */
1775 void
1777 { merge(std::move(__list), std::less<_Tp>()); }
1778
1779 void
1780 merge(forward_list& __list)
1781 { merge(std::move(__list)); }
1782
1783 /**
1784 * @brief Merge sorted lists according to comparison function.
1785 * @param __list Sorted list to merge.
1786 * @param __comp Comparison function defining sort order.
1787 *
1788 * Assumes that both `__list` and this list are sorted according to
1789 * comp. Merges elements of `__list` into this list
1790 * in sorted order, leaving `__list` empty when complete. Elements
1791 * in this list precede elements in `__list` that are equivalent
1792 * according to comp().
1793 */
1794 template<typename _Comp>
1795 void
1796 merge(forward_list&& __list, _Comp __comp);
1797
1798 template<typename _Comp>
1799 void
1800 merge(forward_list& __list, _Comp __comp)
1801 { merge(std::move(__list), __comp); }
1802
1803 /**
1804 * @brief Sort the elements of the list.
1805 *
1806 * Sorts the elements of this list in NlogN time. Equivalent
1807 * elements remain in list order.
1808 */
1809 void
1811 { sort(std::less<_Tp>()); }
1812
1813 /**
1814 * @brief Sort the forward_list using a comparison function.
1815 *
1816 * Sorts the elements of this list in NlogN time. Equivalent
1817 * elements remain in list order.
1818 */
1819 template<typename _Comp>
1820 void
1821 sort(_Comp __comp);
1822
1823 /**
1824 * @brief Reverse the elements in list.
1825 *
1826 * Reverse the order of elements in the list in linear time.
1827 */
1828 void
1829 reverse() noexcept
1830 { this->_M_impl._M_head._M_reverse_after(); }
1831
1832 private:
1833 // Called by the range constructor to implement [23.3.4.2]/9
1834 template<typename _InputIterator>
1835 void
1836 _M_range_initialize(_InputIterator __first, _InputIterator __last);
1837
1838 // Called by forward_list(n,v,a), and the range constructor when it
1839 // turns out to be the same thing.
1840 void
1841 _M_fill_initialize(size_type __n, const value_type& __value);
1842
1843 // Called by splice_after and insert_after.
1844 iterator
1845 _M_splice_after(const_iterator __pos, const_iterator __before,
1846 const_iterator __last);
1847
1848 // Called by forward_list(n).
1849 void
1850 _M_default_initialize(size_type __n);
1851
1852 // Called by resize(sz).
1853 void
1854 _M_default_insert_after(const_iterator __pos, size_type __n);
1855
1856#if ! _GLIBCXX_INLINE_VERSION
1857#pragma GCC diagnostic push
1858#pragma GCC diagnostic ignored "-Wc++17-extensions" // if constexpr
1859 // XXX GLIBCXX_ABI Deprecated
1860 // These members are unused by std::forward_list now, but we keep them
1861 // here so that an explicit instantiation will define them.
1862 // This ensures that explicit instantiations still define these symbols,
1863 // so that explicit instantiation declarations of std::forward_list that
1864 // were compiled with old versions of GCC can still find these symbols.
1865
1866 // Use 'if constexpr' so that the functions don't do anything for
1867 // specializations using _Node_traits<T, fancy-pointer>, because any
1868 // old code referencing these symbols wasn't using the fancy-pointer
1869 // specializations.
1870
1871 void
1872 _M_move_assign(forward_list&& __list, true_type) noexcept
1873 {
1874#if _GLIBCXX_USE_ALLOC_PTR_FOR_FWD_LIST
1876#endif
1877 {
1878 clear();
1879 this->_M_impl._M_head._M_next = __list._M_impl._M_head._M_next;
1880 __list._M_impl._M_head._M_next = nullptr;
1881 std::__alloc_on_move(this->_M_get_Node_allocator(),
1882 __list._M_get_Node_allocator());
1883 }
1884 }
1885
1886 void
1887 _M_move_assign(forward_list&& __list, false_type)
1888 {
1889#if _GLIBCXX_USE_ALLOC_PTR_FOR_FWD_LIST
1890 if constexpr (is_same<typename _Alloc_traits::pointer, _Tp*>::value)
1891#endif
1892 {
1893 if (__list._M_get_Node_allocator() == this->_M_get_Node_allocator())
1894 _M_move_assign(std::move(__list), true_type());
1895 else
1896 // The rvalue's allocator cannot be moved, or is not equal,
1897 // so we need to individually move each element.
1898 this->assign(std::make_move_iterator(__list.begin()),
1899 std::make_move_iterator(__list.end()));
1900 }
1901 }
1902
1903 void
1904 _M_assign_n(size_type __n, const _Tp& __val, true_type)
1905 {
1906#if _GLIBCXX_USE_ALLOC_PTR_FOR_FWD_LIST
1907 if constexpr (is_same<typename _Alloc_traits::pointer, _Tp*>::value)
1908#endif
1909 {
1910 auto __prev = before_begin();
1911 auto __curr = begin();
1912 auto __end = end();
1913 while (__curr != __end && __n > 0)
1914 {
1915 *__curr = __val;
1916 ++__prev;
1917 ++__curr;
1918 --__n;
1919 }
1920 if (__n > 0)
1921 insert_after(__prev, __n, __val);
1922 else if (__curr != __end)
1923 erase_after(__prev, __end);
1924 }
1925 }
1926
1927 void
1928 _M_assign_n(size_type __n, const _Tp& __val, false_type)
1929 {
1930#if _GLIBCXX_USE_ALLOC_PTR_FOR_FWD_LIST
1931 if constexpr (is_same<typename _Alloc_traits::pointer, _Tp*>::value)
1932#endif
1933 {
1934 clear();
1935 insert_after(cbefore_begin(), __n, __val);
1936 }
1937 }
1938#pragma GCC diagnostic pop
1939#endif // ! _GLIBCXX_INLINE_VERSION
1940 };
1941
1942#if __cpp_deduction_guides >= 201606
1943 template<typename _InputIterator, typename _ValT
1944 = typename iterator_traits<_InputIterator>::value_type,
1945 typename _Allocator = allocator<_ValT>,
1946 typename = _RequireInputIter<_InputIterator>,
1947 typename = _RequireAllocator<_Allocator>>
1948 forward_list(_InputIterator, _InputIterator, _Allocator = _Allocator())
1949 -> forward_list<_ValT, _Allocator>;
1950
1951#if __glibcxx_ranges_to_container // C++ >= 23
1952 template<ranges::input_range _Rg,
1953 typename _Allocator = allocator<ranges::range_value_t<_Rg>>>
1954 forward_list(from_range_t, _Rg&&, _Allocator = _Allocator())
1955 -> forward_list<ranges::range_value_t<_Rg>, _Allocator>;
1956#endif
1957#endif
1958
1959 /**
1960 * @brief Forward list equality comparison.
1961 * @param __lx A %forward_list
1962 * @param __ly A %forward_list of the same type as `__lx`.
1963 * @return True iff the elements of the forward lists are equal.
1964 *
1965 * This is an equivalence relation. It is linear in the number of
1966 * elements of the forward lists. Deques are considered equivalent
1967 * if corresponding elements compare equal.
1968 */
1969 template<typename _Tp, typename _Alloc>
1970 [[__nodiscard__]]
1971 bool
1972 operator==(const forward_list<_Tp, _Alloc>& __lx,
1973 const forward_list<_Tp, _Alloc>& __ly);
1974
1975#if __cpp_lib_three_way_comparison
1976 /**
1977 * @brief Forward list ordering relation.
1978 * @param __x A `forward_list`.
1979 * @param __y A `forward_list` of the same type as `__x`.
1980 * @return A value indicating whether `__x` is less than, equal to,
1981 * greater than, or incomparable with `__y`.
1982 *
1983 * See `std::lexicographical_compare_three_way()` for how the determination
1984 * is made. This operator is used to synthesize relational operators like
1985 * `<` and `>=` etc.
1986 */
1987 template<typename _Tp, typename _Alloc>
1988 [[nodiscard]]
1989 inline __detail::__synth3way_t<_Tp>
1990 operator<=>(const forward_list<_Tp, _Alloc>& __x,
1991 const forward_list<_Tp, _Alloc>& __y)
1992 {
1994 __y.begin(), __y.end(),
1995 __detail::__synth3way);
1996 }
1997#else
1998 /**
1999 * @brief Forward list ordering relation.
2000 * @param __lx A %forward_list.
2001 * @param __ly A %forward_list of the same type as `__lx`.
2002 * @return True iff `__lx` is lexicographically less than `__ly`.
2003 *
2004 * This is a total ordering relation. It is linear in the number of
2005 * elements of the forward lists. The elements must be comparable
2006 * with `<`.
2007 *
2008 * See std::lexicographical_compare() for how the determination is made.
2009 */
2010 template<typename _Tp, typename _Alloc>
2011 [[__nodiscard__]]
2012 inline bool
2013 operator<(const forward_list<_Tp, _Alloc>& __lx,
2014 const forward_list<_Tp, _Alloc>& __ly)
2015 { return std::lexicographical_compare(__lx.cbegin(), __lx.cend(),
2016 __ly.cbegin(), __ly.cend()); }
2017
2018 /// Based on operator==
2019 template<typename _Tp, typename _Alloc>
2020 [[__nodiscard__]]
2021 inline bool
2022 operator!=(const forward_list<_Tp, _Alloc>& __lx,
2023 const forward_list<_Tp, _Alloc>& __ly)
2024 { return !(__lx == __ly); }
2025
2026 /// Based on operator<
2027 template<typename _Tp, typename _Alloc>
2028 [[__nodiscard__]]
2029 inline bool
2030 operator>(const forward_list<_Tp, _Alloc>& __lx,
2031 const forward_list<_Tp, _Alloc>& __ly)
2032 { return (__ly < __lx); }
2033
2034 /// Based on operator<
2035 template<typename _Tp, typename _Alloc>
2036 [[__nodiscard__]]
2037 inline bool
2038 operator>=(const forward_list<_Tp, _Alloc>& __lx,
2039 const forward_list<_Tp, _Alloc>& __ly)
2040 { return !(__lx < __ly); }
2041
2042 /// Based on operator<
2043 template<typename _Tp, typename _Alloc>
2044 [[__nodiscard__]]
2045 inline bool
2046 operator<=(const forward_list<_Tp, _Alloc>& __lx,
2047 const forward_list<_Tp, _Alloc>& __ly)
2048 { return !(__ly < __lx); }
2049#endif // three-way comparison
2050
2051 /// See std::forward_list::swap().
2052 template<typename _Tp, typename _Alloc>
2053 inline void
2056 noexcept(noexcept(__lx.swap(__ly)))
2057 { __lx.swap(__ly); }
2058
2059_GLIBCXX_END_NAMESPACE_CONTAINER
2060_GLIBCXX_END_NAMESPACE_VERSION
2061} // namespace std
2062
2063#endif // _FORWARD_LIST_H
constexpr bool operator<=(const duration< _Rep1, _Period1 > &__lhs, const duration< _Rep2, _Period2 > &__rhs)
Definition chrono.h:859
constexpr bool operator>=(const duration< _Rep1, _Period1 > &__lhs, const duration< _Rep2, _Period2 > &__rhs)
Definition chrono.h:873
constexpr bool operator>(const duration< _Rep1, _Period1 > &__lhs, const duration< _Rep2, _Period2 > &__rhs)
Definition chrono.h:866
constexpr complex< _Tp > operator*(const complex< _Tp > &__x, const complex< _Tp > &__y)
Return new complex value x times y.
Definition complex:405
__bool_constant< true > true_type
The type used as a compile-time boolean with true value.
Definition type_traits:116
__bool_constant< false > false_type
The type used as a compile-time boolean with false value.
Definition type_traits:119
constexpr std::remove_reference< _Tp >::type && move(_Tp &&__t) noexcept
Convert a value to an rvalue.
Definition move.h:127
constexpr _Tp * __addressof(_Tp &__r) noexcept
Same as C++11 std::addressof.
Definition move.h:51
constexpr auto lexicographical_compare_three_way(_InputIter1 __first1, _InputIter1 __last1, _InputIter2 __first2, _InputIter2 __last2, _Comp __comp) -> decltype(__comp(*__first1, *__first2))
Performs dictionary comparison on ranges.
ISO C++ entities toplevel namespace is std.
initializer_list
is_nothrow_default_constructible
Definition type_traits:1245
is_assignable
Definition type_traits:1277
is_copy_assignable
Definition type_traits:1287
is_trivially_destructible
Definition type_traits:1459
Uniform interface to all allocator types.
__detected_or_t< value_type *, __pointer, _Alloc > pointer
The allocator's pointer type.
A helper basic node class for forward_list.
A helper node class for forward_list. This is just a linked list with uninitialized storage for a dat...
A forward_list::const_iterator.
friend bool operator==(const _Self &__x, const _Self &__y) noexcept
Forward list const_iterator equality comparison.
A forward_list::iterator.
friend bool operator==(const _Self &__x, const _Self &__y) noexcept
Forward list iterator equality comparison.
A standard container with linear time access to elements, and fixed time insertion/deletion at any po...
__remove_return_type unique(_BinPred __binary_pred)
Remove consecutive elements satisfying a predicate.
iterator begin() noexcept
const_iterator before_begin() const noexcept
void reverse() noexcept
Reverse the elements in list.
forward_list()=default
Creates a forward_list with no elements.
~forward_list() noexcept
The forward_list dtor.
iterator erase_after(const_iterator __pos)
Removes the element pointed to by the iterator following pos.
void swap(forward_list &__list) noexcept
Swaps data with another forward_list.
const_reference front() const
void merge(forward_list &&__list)
Merge sorted lists.
forward_list(const _Alloc &__al) noexcept
Creates a forward_list with no elements.
void sort()
Sort the elements of the list.
iterator before_begin() noexcept
forward_list(const forward_list &__list, const __type_identity_t< _Alloc > &__al)
Copy constructor with allocator argument.
iterator emplace_after(const_iterator __pos, _Args &&... __args)
Constructs object in forward_list after the specified iterator.
forward_list(const forward_list &__list)
The forward_list copy constructor.
iterator insert_after(const_iterator __pos, const _Tp &__val)
Inserts given value into forward_list after specified iterator.
forward_list & operator=(forward_list &&__list) noexcept(_Node_alloc_traits::_S_nothrow_move())
The forward_list move assignment operator.
void resize(size_type __sz)
Resizes the forward_list to the specified number of elements.
forward_list & operator=(const forward_list &__list)
The forward_list assignment operator.
__remove_return_type remove_if(_Pred __pred)
Remove all elements satisfying a predicate.
iterator end() noexcept
forward_list(size_type __n, const _Tp &__value, const _Alloc &__al=_Alloc())
Creates a forward_list with copies of an exemplar element.
void assign(size_type __n, const _Tp &__val)
Assigns a given value to a forward_list.
const_iterator begin() const noexcept
void splice_after(const_iterator __pos, forward_list &&__list) noexcept
Insert contents of another forward_list.
const_iterator cbefore_begin() const noexcept
forward_list & operator=(std::initializer_list< _Tp > __il)
The forward_list initializer list assignment operator.
forward_list(std::initializer_list< _Tp > __il, const _Alloc &__al=_Alloc())
Builds a forward_list from an initializer_list.
reference emplace_front(_Args &&... __args)
Constructs object in forward_list at the front of the list.
forward_list(size_type __n, const _Alloc &__al=_Alloc())
Creates a forward_list with default constructed elements.
iterator insert_after(const_iterator __pos, std::initializer_list< _Tp > __il)
Inserts the contents of an initializer_list into forward_list after the specified iterator.
const_iterator end() const noexcept
void splice_after(const_iterator __pos, forward_list &&, const_iterator __before, const_iterator __last) noexcept
Insert range from another forward_list.
forward_list(forward_list &&__list, const __type_identity_t< _Alloc > &__al) noexcept(_Node_alloc_traits::_S_always_equal())
Move constructor with allocator argument.
iterator erase_after(const_iterator __pos, const_iterator __last)
Remove a range of elements.
__remove_return_type unique()
Remove consecutive duplicate elements.
void clear() noexcept
Erases all the elements.
__remove_return_type remove(const _Tp &__val)
Remove all elements equal to value.
const_iterator cend() const noexcept
void assign(_InputIterator __first, _InputIterator __last)
Assigns a range to a forward_list.
bool empty() const noexcept
allocator_type get_allocator() const noexcept
Get a copy of the memory allocation object.
void push_front(const _Tp &__val)
Add data to the front of the forward_list.
forward_list(forward_list &&)=default
The forward_list move constructor.
forward_list(_InputIterator __first, _InputIterator __last, const _Alloc &__al=_Alloc())
Builds a forward_list from a range.
void splice_after(const_iterator __pos, forward_list &, const_iterator __before, const_iterator __last) noexcept
Insert range from another forward_list.
const_iterator cbegin() const noexcept
void pop_front()
Removes first element.
void assign(std::initializer_list< _Tp > __il)
Assigns an initializer_list to a forward_list.
size_type max_size() const noexcept
Base class for forward_list.
Uniform interface to all pointer-like types.
Definition ptr_traits.h:178
One of the comparison functors.
One of the comparison functors.
Forward iterators support a superset of input iterator operations.
Common iterator class.
Uniform interface to C++98 and C++11 allocators.
static constexpr pointer allocate(_Alloc &__a, size_type __n)
Allocate memory.
static constexpr void deallocate(_Alloc &__a, pointer __p, size_type __n)
Deallocate memory.
static constexpr size_type max_size(const _Alloc &__a) noexcept
The maximum supported allocation size.