1// -*- C++ -*-
2//===----------------------------------------------------------------------===//
3//
4// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
5// See https://llvm.org/LICENSE.txt for license information.
6// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
7//
8//===----------------------------------------------------------------------===//
9
10#ifndef _LIBCPP_FORWARD_LIST
11#define _LIBCPP_FORWARD_LIST
12
13/*
14    forward_list synopsis
15
16namespace std
17{
18
19template <class T, class Allocator = allocator<T>>
20class forward_list
21{
22public:
23    typedef T         value_type;
24    typedef Allocator allocator_type;
25
26    typedef value_type&                                                reference;
27    typedef const value_type&                                          const_reference;
28    typedef typename allocator_traits<allocator_type>::pointer         pointer;
29    typedef typename allocator_traits<allocator_type>::const_pointer   const_pointer;
30    typedef typename allocator_traits<allocator_type>::size_type       size_type;
31    typedef typename allocator_traits<allocator_type>::difference_type difference_type;
32
33    typedef <details> iterator;
34    typedef <details> const_iterator;
35
36    forward_list()
37        noexcept(is_nothrow_default_constructible<allocator_type>::value);
38    explicit forward_list(const allocator_type& a);
39    explicit forward_list(size_type n);
40    explicit forward_list(size_type n, const allocator_type& a); // C++14
41    forward_list(size_type n, const value_type& v);
42    forward_list(size_type n, const value_type& v, const allocator_type& a);
43    template <class InputIterator>
44        forward_list(InputIterator first, InputIterator last);
45    template <class InputIterator>
46        forward_list(InputIterator first, InputIterator last, const allocator_type& a);
47    forward_list(const forward_list& x);
48    forward_list(const forward_list& x, const allocator_type& a);
49    forward_list(forward_list&& x)
50        noexcept(is_nothrow_move_constructible<allocator_type>::value);
51    forward_list(forward_list&& x, const allocator_type& a);
52    forward_list(initializer_list<value_type> il);
53    forward_list(initializer_list<value_type> il, const allocator_type& a);
54
55    ~forward_list();
56
57    forward_list& operator=(const forward_list& x);
58    forward_list& operator=(forward_list&& x)
59        noexcept(
60             allocator_type::propagate_on_container_move_assignment::value &&
61             is_nothrow_move_assignable<allocator_type>::value);
62    forward_list& operator=(initializer_list<value_type> il);
63
64    template <class InputIterator>
65        void assign(InputIterator first, InputIterator last);
66    void assign(size_type n, const value_type& v);
67    void assign(initializer_list<value_type> il);
68
69    allocator_type get_allocator() const noexcept;
70
71    iterator       begin() noexcept;
72    const_iterator begin() const noexcept;
73    iterator       end() noexcept;
74    const_iterator end() const noexcept;
75
76    const_iterator cbegin() const noexcept;
77    const_iterator cend() const noexcept;
78
79    iterator       before_begin() noexcept;
80    const_iterator before_begin() const noexcept;
81    const_iterator cbefore_begin() const noexcept;
82
83    bool empty() const noexcept;
84    size_type max_size() const noexcept;
85
86    reference       front();
87    const_reference front() const;
88
89    template <class... Args> reference emplace_front(Args&&... args);  // reference in C++17
90    void push_front(const value_type& v);
91    void push_front(value_type&& v);
92
93    void pop_front();
94
95    template <class... Args>
96        iterator emplace_after(const_iterator p, Args&&... args);
97    iterator insert_after(const_iterator p, const value_type& v);
98    iterator insert_after(const_iterator p, value_type&& v);
99    iterator insert_after(const_iterator p, size_type n, const value_type& v);
100    template <class InputIterator>
101        iterator insert_after(const_iterator p,
102                              InputIterator first, InputIterator last);
103    iterator insert_after(const_iterator p, initializer_list<value_type> il);
104
105    iterator erase_after(const_iterator p);
106    iterator erase_after(const_iterator first, const_iterator last);
107
108    void swap(forward_list& x)
109        noexcept(allocator_traits<allocator_type>::is_always_equal::value);  // C++17
110
111    void resize(size_type n);
112    void resize(size_type n, const value_type& v);
113    void clear() noexcept;
114
115    void splice_after(const_iterator p, forward_list& x);
116    void splice_after(const_iterator p, forward_list&& x);
117    void splice_after(const_iterator p, forward_list& x, const_iterator i);
118    void splice_after(const_iterator p, forward_list&& x, const_iterator i);
119    void splice_after(const_iterator p, forward_list& x,
120                      const_iterator first, const_iterator last);
121    void splice_after(const_iterator p, forward_list&& x,
122                      const_iterator first, const_iterator last);
123    size_type remove(const value_type& v);           // void before C++20
124    template <class Predicate>
125      size_type remove_if(Predicate pred);           // void before C++20
126    size_type unique();                              // void before C++20
127    template <class BinaryPredicate>
128      size_type unique(BinaryPredicate binary_pred); // void before C++20
129    void merge(forward_list& x);
130    void merge(forward_list&& x);
131    template <class Compare> void merge(forward_list& x, Compare comp);
132    template <class Compare> void merge(forward_list&& x, Compare comp);
133    void sort();
134    template <class Compare> void sort(Compare comp);
135    void reverse() noexcept;
136};
137
138
139template <class InputIterator, class Allocator = allocator<typename iterator_traits<InputIterator>::value_type>>
140    forward_list(InputIterator, InputIterator, Allocator = Allocator())
141    -> forward_list<typename iterator_traits<InputIterator>::value_type, Allocator>;  // C++17
142
143template <class T, class Allocator>
144    bool operator==(const forward_list<T, Allocator>& x,
145                    const forward_list<T, Allocator>& y);
146
147template <class T, class Allocator>
148    bool operator< (const forward_list<T, Allocator>& x,
149                    const forward_list<T, Allocator>& y);
150
151template <class T, class Allocator>
152    bool operator!=(const forward_list<T, Allocator>& x,
153                    const forward_list<T, Allocator>& y);
154
155template <class T, class Allocator>
156    bool operator> (const forward_list<T, Allocator>& x,
157                    const forward_list<T, Allocator>& y);
158
159template <class T, class Allocator>
160    bool operator>=(const forward_list<T, Allocator>& x,
161                    const forward_list<T, Allocator>& y);
162
163template <class T, class Allocator>
164    bool operator<=(const forward_list<T, Allocator>& x,
165                    const forward_list<T, Allocator>& y);
166
167template <class T, class Allocator>
168    void swap(forward_list<T, Allocator>& x, forward_list<T, Allocator>& y)
169         noexcept(noexcept(x.swap(y)));
170
171template <class T, class Allocator, class U>
172    typename forward_list<T, Allocator>::size_type
173    erase(forward_list<T, Allocator>& c, const U& value);       // C++20
174template <class T, class Allocator, class Predicate>
175    typename forward_list<T, Allocator>::size_type
176    erase_if(forward_list<T, Allocator>& c, Predicate pred);    // C++20
177
178}  // std
179
180*/
181
182#include <__algorithm/comp.h>
183#include <__algorithm/lexicographical_compare.h>
184#include <__algorithm/min.h>
185#include <__assert> // all public C++ headers provide the assertion handler
186#include <__config>
187#include <__iterator/distance.h>
188#include <__iterator/iterator_traits.h>
189#include <__iterator/move_iterator.h>
190#include <__iterator/next.h>
191#include <__memory/addressof.h>
192#include <__memory/allocator.h>
193#include <__memory/allocator_destructor.h>
194#include <__memory/allocator_traits.h>
195#include <__memory/compressed_pair.h>
196#include <__memory/pointer_traits.h>
197#include <__memory/swap_allocator.h>
198#include <__memory/unique_ptr.h>
199#include <__memory_resource/polymorphic_allocator.h>
200#include <__type_traits/is_allocator.h>
201#include <__utility/forward.h>
202#include <__utility/move.h>
203#include <limits>
204#include <type_traits>
205#include <version>
206
207// standard-mandated includes
208
209// [iterator.range]
210#include <__iterator/access.h>
211#include <__iterator/data.h>
212#include <__iterator/empty.h>
213#include <__iterator/reverse_access.h>
214#include <__iterator/size.h>
215
216// [forward.list.syn]
217#include <compare>
218#include <initializer_list>
219
220#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
221#  pragma GCC system_header
222#endif
223
224_LIBCPP_PUSH_MACROS
225#include <__undef_macros>
226
227
228_LIBCPP_BEGIN_NAMESPACE_STD
229
230template <class _Tp, class _VoidPtr> struct __forward_list_node;
231template <class _NodePtr> struct __forward_begin_node;
232
233
234template <class>
235struct __forward_list_node_value_type;
236
237template <class _Tp, class _VoidPtr>
238struct __forward_list_node_value_type<__forward_list_node<_Tp, _VoidPtr> > {
239  typedef _Tp type;
240};
241
242template <class _NodePtr>
243struct __forward_node_traits {
244
245  typedef __remove_cv_t<
246        typename pointer_traits<_NodePtr>::element_type>        __node;
247  typedef typename __forward_list_node_value_type<__node>::type __node_value_type;
248  typedef _NodePtr                                              __node_pointer;
249  typedef __forward_begin_node<_NodePtr>                        __begin_node;
250  typedef __rebind_pointer_t<_NodePtr, __begin_node>            __begin_node_pointer;
251  typedef __rebind_pointer_t<_NodePtr, void>                    __void_pointer;
252
253#if defined(_LIBCPP_ABI_FORWARD_LIST_REMOVE_NODE_POINTER_UB)
254  typedef __begin_node_pointer __iter_node_pointer;
255#else
256  typedef __conditional_t<is_pointer<__void_pointer>::value, __begin_node_pointer, __node_pointer>
257      __iter_node_pointer;
258#endif
259
260  typedef __conditional_t<is_same<__iter_node_pointer, __node_pointer>::value, __begin_node_pointer, __node_pointer>
261      __non_iter_node_pointer;
262
263  _LIBCPP_INLINE_VISIBILITY
264  static __iter_node_pointer __as_iter_node(__iter_node_pointer __p) {
265      return __p;
266  }
267  _LIBCPP_INLINE_VISIBILITY
268  static __iter_node_pointer __as_iter_node(__non_iter_node_pointer __p) {
269      return static_cast<__iter_node_pointer>(static_cast<__void_pointer>(__p));
270  }
271};
272
273template <class _NodePtr>
274struct __forward_begin_node
275{
276    typedef _NodePtr pointer;
277    typedef __rebind_pointer_t<_NodePtr, __forward_begin_node> __begin_node_pointer;
278
279    pointer __next_;
280
281    _LIBCPP_INLINE_VISIBILITY __forward_begin_node() : __next_(nullptr) {}
282
283    _LIBCPP_INLINE_VISIBILITY
284    __begin_node_pointer __next_as_begin() const {
285        return static_cast<__begin_node_pointer>(__next_);
286    }
287};
288
289template <class _Tp, class _VoidPtr>
290using __begin_node_of = __forward_begin_node<__rebind_pointer_t<_VoidPtr, __forward_list_node<_Tp, _VoidPtr> > >;
291
292template <class _Tp, class _VoidPtr>
293struct _LIBCPP_STANDALONE_DEBUG __forward_list_node
294    : public __begin_node_of<_Tp, _VoidPtr>
295{
296    typedef _Tp value_type;
297
298    value_type __value_;
299};
300
301
302template <class _Tp, class _Alloc = allocator<_Tp> > class _LIBCPP_TEMPLATE_VIS forward_list;
303template<class _NodeConstPtr> class _LIBCPP_TEMPLATE_VIS __forward_list_const_iterator;
304
305template <class _NodePtr>
306class _LIBCPP_TEMPLATE_VIS __forward_list_iterator
307{
308    typedef __forward_node_traits<_NodePtr>         __traits;
309    typedef typename __traits::__node_pointer       __node_pointer;
310    typedef typename __traits::__begin_node_pointer __begin_node_pointer;
311    typedef typename __traits::__iter_node_pointer  __iter_node_pointer;
312    typedef typename __traits::__void_pointer       __void_pointer;
313
314    __iter_node_pointer __ptr_;
315
316    _LIBCPP_INLINE_VISIBILITY
317    __begin_node_pointer __get_begin() const {
318        return static_cast<__begin_node_pointer>(
319                static_cast<__void_pointer>(__ptr_));
320    }
321    _LIBCPP_INLINE_VISIBILITY
322    __node_pointer __get_unsafe_node_pointer() const {
323        return static_cast<__node_pointer>(
324                static_cast<__void_pointer>(__ptr_));
325    }
326
327    _LIBCPP_INLINE_VISIBILITY
328    explicit __forward_list_iterator(nullptr_t) _NOEXCEPT : __ptr_(nullptr) {}
329
330    _LIBCPP_INLINE_VISIBILITY
331    explicit __forward_list_iterator(__begin_node_pointer __p) _NOEXCEPT
332        : __ptr_(__traits::__as_iter_node(__p)) {}
333
334    _LIBCPP_INLINE_VISIBILITY
335    explicit __forward_list_iterator(__node_pointer __p) _NOEXCEPT
336        : __ptr_(__traits::__as_iter_node(__p)) {}
337
338    template<class, class> friend class _LIBCPP_TEMPLATE_VIS forward_list;
339    template<class> friend class _LIBCPP_TEMPLATE_VIS __forward_list_const_iterator;
340
341public:
342    typedef forward_iterator_tag                              iterator_category;
343    typedef typename __traits::__node_value_type              value_type;
344    typedef value_type&                                       reference;
345    typedef typename pointer_traits<__node_pointer>::difference_type
346                                                              difference_type;
347    typedef __rebind_pointer_t<__node_pointer, value_type> pointer;
348
349    _LIBCPP_INLINE_VISIBILITY
350    __forward_list_iterator() _NOEXCEPT : __ptr_(nullptr) {}
351
352    _LIBCPP_INLINE_VISIBILITY
353    reference operator*() const {return __get_unsafe_node_pointer()->__value_;}
354    _LIBCPP_INLINE_VISIBILITY
355    pointer operator->() const {
356        return pointer_traits<pointer>::pointer_to(__get_unsafe_node_pointer()->__value_);
357    }
358
359    _LIBCPP_INLINE_VISIBILITY
360    __forward_list_iterator& operator++()
361    {
362        __ptr_ = __traits::__as_iter_node(__ptr_->__next_);
363        return *this;
364    }
365    _LIBCPP_INLINE_VISIBILITY
366    __forward_list_iterator operator++(int)
367    {
368        __forward_list_iterator __t(*this);
369        ++(*this);
370        return __t;
371    }
372
373    friend _LIBCPP_INLINE_VISIBILITY
374    bool operator==(const __forward_list_iterator& __x,
375                    const __forward_list_iterator& __y)
376        {return __x.__ptr_ == __y.__ptr_;}
377    friend _LIBCPP_INLINE_VISIBILITY
378    bool operator!=(const __forward_list_iterator& __x,
379                    const __forward_list_iterator& __y)
380        {return !(__x == __y);}
381};
382
383template <class _NodeConstPtr>
384class _LIBCPP_TEMPLATE_VIS __forward_list_const_iterator
385{
386    static_assert((!is_const<typename pointer_traits<_NodeConstPtr>::element_type>::value), "");
387    typedef _NodeConstPtr _NodePtr;
388
389    typedef __forward_node_traits<_NodePtr>         __traits;
390    typedef typename __traits::__node               __node;
391    typedef typename __traits::__node_pointer       __node_pointer;
392    typedef typename __traits::__begin_node_pointer __begin_node_pointer;
393    typedef typename __traits::__iter_node_pointer  __iter_node_pointer;
394    typedef typename __traits::__void_pointer       __void_pointer;
395
396    __iter_node_pointer __ptr_;
397
398    __begin_node_pointer __get_begin() const {
399        return static_cast<__begin_node_pointer>(
400                static_cast<__void_pointer>(__ptr_));
401    }
402    __node_pointer __get_unsafe_node_pointer() const {
403        return static_cast<__node_pointer>(
404                static_cast<__void_pointer>(__ptr_));
405    }
406
407    _LIBCPP_INLINE_VISIBILITY
408    explicit __forward_list_const_iterator(nullptr_t) _NOEXCEPT
409        : __ptr_(nullptr) {}
410
411    _LIBCPP_INLINE_VISIBILITY
412    explicit __forward_list_const_iterator(__begin_node_pointer __p) _NOEXCEPT
413        : __ptr_(__traits::__as_iter_node(__p)) {}
414
415    _LIBCPP_INLINE_VISIBILITY
416    explicit __forward_list_const_iterator(__node_pointer __p) _NOEXCEPT
417        : __ptr_(__traits::__as_iter_node(__p)) {}
418
419
420    template<class, class> friend class forward_list;
421
422public:
423    typedef forward_iterator_tag                              iterator_category;
424    typedef typename __traits::__node_value_type              value_type;
425    typedef const value_type&                                 reference;
426    typedef typename pointer_traits<__node_pointer>::difference_type
427                                                              difference_type;
428    typedef __rebind_pointer_t<__node_pointer, const value_type>
429                                                              pointer;
430
431    _LIBCPP_INLINE_VISIBILITY
432    __forward_list_const_iterator() _NOEXCEPT : __ptr_(nullptr) {}
433    _LIBCPP_INLINE_VISIBILITY
434    __forward_list_const_iterator(__forward_list_iterator<__node_pointer> __p) _NOEXCEPT
435        : __ptr_(__p.__ptr_) {}
436
437    _LIBCPP_INLINE_VISIBILITY
438    reference operator*() const {return __get_unsafe_node_pointer()->__value_;}
439    _LIBCPP_INLINE_VISIBILITY
440    pointer operator->() const {return pointer_traits<pointer>::pointer_to(
441                __get_unsafe_node_pointer()->__value_);}
442
443    _LIBCPP_INLINE_VISIBILITY
444    __forward_list_const_iterator& operator++()
445    {
446        __ptr_ = __traits::__as_iter_node(__ptr_->__next_);
447        return *this;
448    }
449    _LIBCPP_INLINE_VISIBILITY
450    __forward_list_const_iterator operator++(int)
451    {
452        __forward_list_const_iterator __t(*this);
453        ++(*this);
454        return __t;
455    }
456
457    friend _LIBCPP_INLINE_VISIBILITY
458    bool operator==(const __forward_list_const_iterator& __x,
459                    const __forward_list_const_iterator& __y)
460        {return __x.__ptr_ == __y.__ptr_;}
461    friend _LIBCPP_INLINE_VISIBILITY
462    bool operator!=(const __forward_list_const_iterator& __x,
463                           const __forward_list_const_iterator& __y)
464        {return !(__x == __y);}
465};
466
467template <class _Tp, class _Alloc>
468class __forward_list_base
469{
470protected:
471    typedef _Tp    value_type;
472    typedef _Alloc allocator_type;
473
474    typedef typename allocator_traits<allocator_type>::void_pointer  void_pointer;
475    typedef __forward_list_node<value_type, void_pointer>            __node;
476    typedef __begin_node_of<value_type, void_pointer>                __begin_node;
477    typedef __rebind_alloc<allocator_traits<allocator_type>, __node> __node_allocator;
478    typedef allocator_traits<__node_allocator>        __node_traits;
479    typedef typename __node_traits::pointer           __node_pointer;
480
481    typedef __rebind_alloc<allocator_traits<allocator_type>, __begin_node> __begin_node_allocator;
482    typedef typename allocator_traits<__begin_node_allocator>::pointer
483                                                      __begin_node_pointer;
484
485    static_assert((!is_same<allocator_type, __node_allocator>::value),
486                  "internal allocator type must differ from user-specified "
487                  "type; otherwise overload resolution breaks");
488
489    static_assert(is_same<allocator_type, __rebind_alloc<__node_traits, value_type> >::value,
490                  "[allocator.requirements] states that rebinding an allocator to the same type should result in the "
491                  "original allocator");
492
493    __compressed_pair<__begin_node, __node_allocator> __before_begin_;
494
495    _LIBCPP_INLINE_VISIBILITY
496    __begin_node_pointer        __before_begin() _NOEXCEPT
497        {return pointer_traits<__begin_node_pointer>::pointer_to(__before_begin_.first());}
498    _LIBCPP_INLINE_VISIBILITY
499    __begin_node_pointer __before_begin() const _NOEXCEPT
500        {return pointer_traits<__begin_node_pointer>::pointer_to(const_cast<__begin_node&>(__before_begin_.first()));}
501
502    _LIBCPP_INLINE_VISIBILITY
503          __node_allocator& __alloc() _NOEXCEPT
504            {return __before_begin_.second();}
505    _LIBCPP_INLINE_VISIBILITY
506    const __node_allocator& __alloc() const _NOEXCEPT
507        {return __before_begin_.second();}
508
509    typedef __forward_list_iterator<__node_pointer>             iterator;
510    typedef __forward_list_const_iterator<__node_pointer>       const_iterator;
511
512    _LIBCPP_INLINE_VISIBILITY
513    __forward_list_base()
514        _NOEXCEPT_(is_nothrow_default_constructible<__node_allocator>::value)
515        : __before_begin_(__begin_node(), __default_init_tag()) {}
516    _LIBCPP_INLINE_VISIBILITY
517    explicit __forward_list_base(const allocator_type& __a)
518        : __before_begin_(__begin_node(), __node_allocator(__a)) {}
519    _LIBCPP_INLINE_VISIBILITY
520    explicit __forward_list_base(const __node_allocator& __a)
521        : __before_begin_(__begin_node(), __a) {}
522#ifndef _LIBCPP_CXX03_LANG
523public:
524    _LIBCPP_INLINE_VISIBILITY
525    __forward_list_base(__forward_list_base&& __x)
526        _NOEXCEPT_(is_nothrow_move_constructible<__node_allocator>::value);
527    _LIBCPP_INLINE_VISIBILITY
528    __forward_list_base(__forward_list_base&& __x, const allocator_type& __a);
529#endif // _LIBCPP_CXX03_LANG
530
531private:
532    __forward_list_base(const __forward_list_base&);
533    __forward_list_base& operator=(const __forward_list_base&);
534
535public:
536    ~__forward_list_base();
537
538protected:
539    _LIBCPP_INLINE_VISIBILITY
540    void __copy_assign_alloc(const __forward_list_base& __x)
541        {__copy_assign_alloc(__x, integral_constant<bool,
542              __node_traits::propagate_on_container_copy_assignment::value>());}
543
544    _LIBCPP_INLINE_VISIBILITY
545    void __move_assign_alloc(__forward_list_base& __x)
546        _NOEXCEPT_(!__node_traits::propagate_on_container_move_assignment::value ||
547                   is_nothrow_move_assignable<__node_allocator>::value)
548        {__move_assign_alloc(__x, integral_constant<bool,
549              __node_traits::propagate_on_container_move_assignment::value>());}
550
551public:
552    _LIBCPP_INLINE_VISIBILITY
553    void swap(__forward_list_base& __x)
554#if _LIBCPP_STD_VER >= 14
555        _NOEXCEPT;
556#else
557        _NOEXCEPT_(!__node_traits::propagate_on_container_swap::value ||
558                    __is_nothrow_swappable<__node_allocator>::value);
559#endif
560protected:
561    void clear() _NOEXCEPT;
562
563private:
564    _LIBCPP_INLINE_VISIBILITY
565    void __copy_assign_alloc(const __forward_list_base&, false_type) {}
566    _LIBCPP_INLINE_VISIBILITY
567    void __copy_assign_alloc(const __forward_list_base& __x, true_type)
568    {
569        if (__alloc() != __x.__alloc())
570            clear();
571        __alloc() = __x.__alloc();
572    }
573
574    _LIBCPP_INLINE_VISIBILITY
575    void __move_assign_alloc(__forward_list_base&, false_type) _NOEXCEPT
576        {}
577    _LIBCPP_INLINE_VISIBILITY
578    void __move_assign_alloc(__forward_list_base& __x, true_type)
579        _NOEXCEPT_(is_nothrow_move_assignable<__node_allocator>::value)
580        {__alloc() = _VSTD::move(__x.__alloc());}
581};
582
583#ifndef _LIBCPP_CXX03_LANG
584
585template <class _Tp, class _Alloc>
586inline
587__forward_list_base<_Tp, _Alloc>::__forward_list_base(__forward_list_base&& __x)
588        _NOEXCEPT_(is_nothrow_move_constructible<__node_allocator>::value)
589    : __before_begin_(_VSTD::move(__x.__before_begin_))
590{
591    __x.__before_begin()->__next_ = nullptr;
592}
593
594template <class _Tp, class _Alloc>
595inline
596__forward_list_base<_Tp, _Alloc>::__forward_list_base(__forward_list_base&& __x,
597                                                      const allocator_type& __a)
598    : __before_begin_(__begin_node(), __node_allocator(__a))
599{
600    if (__alloc() == __x.__alloc())
601    {
602        __before_begin()->__next_ = __x.__before_begin()->__next_;
603        __x.__before_begin()->__next_ = nullptr;
604    }
605}
606
607#endif // _LIBCPP_CXX03_LANG
608
609template <class _Tp, class _Alloc>
610__forward_list_base<_Tp, _Alloc>::~__forward_list_base()
611{
612    clear();
613}
614
615template <class _Tp, class _Alloc>
616inline
617void
618__forward_list_base<_Tp, _Alloc>::swap(__forward_list_base& __x)
619#if _LIBCPP_STD_VER >= 14
620        _NOEXCEPT
621#else
622        _NOEXCEPT_(!__node_traits::propagate_on_container_swap::value ||
623                    __is_nothrow_swappable<__node_allocator>::value)
624#endif
625{
626    _VSTD::__swap_allocator(__alloc(), __x.__alloc(),
627            integral_constant<bool, __node_traits::propagate_on_container_swap::value>());
628    using _VSTD::swap;
629    swap(__before_begin()->__next_, __x.__before_begin()->__next_);
630}
631
632template <class _Tp, class _Alloc>
633void
634__forward_list_base<_Tp, _Alloc>::clear() _NOEXCEPT
635{
636    __node_allocator& __a = __alloc();
637    for (__node_pointer __p = __before_begin()->__next_; __p != nullptr;)
638    {
639        __node_pointer __next = __p->__next_;
640        __node_traits::destroy(__a, _VSTD::addressof(__p->__value_));
641        __node_traits::deallocate(__a, __p, 1);
642        __p = __next;
643    }
644    __before_begin()->__next_ = nullptr;
645}
646
647template <class _Tp, class _Alloc /*= allocator<_Tp>*/>
648class _LIBCPP_TEMPLATE_VIS forward_list
649    : private __forward_list_base<_Tp, _Alloc>
650{
651    typedef __forward_list_base<_Tp, _Alloc> base;
652    typedef typename base::__node_allocator  __node_allocator;
653    typedef typename base::__node               __node;
654    typedef typename base::__node_traits        __node_traits;
655    typedef typename base::__node_pointer       __node_pointer;
656    typedef typename base::__begin_node_pointer __begin_node_pointer;
657
658public:
659    typedef _Tp    value_type;
660    typedef _Alloc allocator_type;
661
662    static_assert((is_same<typename allocator_type::value_type, value_type>::value),
663                  "Allocator::value_type must be same type as value_type");
664
665    typedef value_type&                                                 reference;
666    typedef const value_type&                                           const_reference;
667    typedef typename allocator_traits<allocator_type>::pointer          pointer;
668    typedef typename allocator_traits<allocator_type>::const_pointer    const_pointer;
669    typedef typename allocator_traits<allocator_type>::size_type        size_type;
670    typedef typename allocator_traits<allocator_type>::difference_type  difference_type;
671
672    typedef typename base::iterator       iterator;
673    typedef typename base::const_iterator const_iterator;
674#if _LIBCPP_STD_VER > 17
675    typedef size_type                                __remove_return_type;
676#else
677    typedef void                                     __remove_return_type;
678#endif
679
680    _LIBCPP_INLINE_VISIBILITY
681    forward_list()
682        _NOEXCEPT_(is_nothrow_default_constructible<__node_allocator>::value)
683        {} // = default;
684    _LIBCPP_INLINE_VISIBILITY
685    explicit forward_list(const allocator_type& __a);
686    explicit forward_list(size_type __n);
687#if _LIBCPP_STD_VER > 11
688    explicit forward_list(size_type __n, const allocator_type& __a);
689#endif
690    forward_list(size_type __n, const value_type& __v);
691
692    template <class = __enable_if_t<__is_allocator<_Alloc>::value> >
693    forward_list(size_type __n, const value_type& __v, const allocator_type& __a) : base(__a)
694    {
695        insert_after(cbefore_begin(), __n, __v);
696    }
697
698    template <class _InputIterator>
699        forward_list(_InputIterator __f, _InputIterator __l,
700                     __enable_if_t<__is_cpp17_input_iterator<_InputIterator>::value>* = nullptr);
701    template <class _InputIterator>
702        forward_list(_InputIterator __f, _InputIterator __l,
703                     const allocator_type& __a,
704                     __enable_if_t<__is_cpp17_input_iterator<_InputIterator>::value>* = nullptr);
705    forward_list(const forward_list& __x);
706    forward_list(const forward_list& __x, const __type_identity_t<allocator_type>& __a);
707
708    forward_list& operator=(const forward_list& __x);
709
710#ifndef _LIBCPP_CXX03_LANG
711    _LIBCPP_INLINE_VISIBILITY
712    forward_list(forward_list&& __x)
713        _NOEXCEPT_(is_nothrow_move_constructible<base>::value)
714        : base(_VSTD::move(__x)) {}
715    forward_list(forward_list&& __x, const __type_identity_t<allocator_type>& __a);
716
717    forward_list(initializer_list<value_type> __il);
718    forward_list(initializer_list<value_type> __il, const allocator_type& __a);
719
720    _LIBCPP_INLINE_VISIBILITY
721    forward_list& operator=(forward_list&& __x)
722        _NOEXCEPT_(
723             __node_traits::propagate_on_container_move_assignment::value &&
724             is_nothrow_move_assignable<allocator_type>::value);
725
726    _LIBCPP_INLINE_VISIBILITY
727    forward_list& operator=(initializer_list<value_type> __il);
728
729    _LIBCPP_INLINE_VISIBILITY
730    void assign(initializer_list<value_type> __il);
731#endif // _LIBCPP_CXX03_LANG
732
733    // ~forward_list() = default;
734
735    template <class _InputIterator>
736    __enable_if_t<__is_cpp17_input_iterator<_InputIterator>::value, void>
737        assign(_InputIterator __f, _InputIterator __l);
738    void assign(size_type __n, const value_type& __v);
739
740    _LIBCPP_INLINE_VISIBILITY
741    allocator_type get_allocator() const _NOEXCEPT
742        {return allocator_type(base::__alloc());}
743
744    _LIBCPP_INLINE_VISIBILITY
745    iterator       begin() _NOEXCEPT
746        {return       iterator(base::__before_begin()->__next_);}
747    _LIBCPP_INLINE_VISIBILITY
748    const_iterator begin() const _NOEXCEPT
749        {return const_iterator(base::__before_begin()->__next_);}
750    _LIBCPP_INLINE_VISIBILITY
751    iterator       end() _NOEXCEPT
752        {return       iterator(nullptr);}
753    _LIBCPP_INLINE_VISIBILITY
754    const_iterator end() const _NOEXCEPT
755        {return const_iterator(nullptr);}
756
757    _LIBCPP_INLINE_VISIBILITY
758    const_iterator cbegin() const _NOEXCEPT
759        {return const_iterator(base::__before_begin()->__next_);}
760    _LIBCPP_INLINE_VISIBILITY
761    const_iterator cend() const _NOEXCEPT
762        {return const_iterator(nullptr);}
763
764    _LIBCPP_INLINE_VISIBILITY
765    iterator       before_begin() _NOEXCEPT
766        {return       iterator(base::__before_begin());}
767    _LIBCPP_INLINE_VISIBILITY
768    const_iterator before_begin() const _NOEXCEPT
769        {return const_iterator(base::__before_begin());}
770    _LIBCPP_INLINE_VISIBILITY
771    const_iterator cbefore_begin() const _NOEXCEPT
772        {return const_iterator(base::__before_begin());}
773
774    _LIBCPP_NODISCARD_AFTER_CXX17 _LIBCPP_INLINE_VISIBILITY
775    bool empty() const _NOEXCEPT
776        {return base::__before_begin()->__next_ == nullptr;}
777    _LIBCPP_INLINE_VISIBILITY
778    size_type max_size() const _NOEXCEPT {
779        return _VSTD::min<size_type>(
780            __node_traits::max_size(base::__alloc()),
781            numeric_limits<difference_type>::max());
782    }
783
784    _LIBCPP_INLINE_VISIBILITY
785    reference       front()       {return base::__before_begin()->__next_->__value_;}
786    _LIBCPP_INLINE_VISIBILITY
787    const_reference front() const {return base::__before_begin()->__next_->__value_;}
788
789#ifndef _LIBCPP_CXX03_LANG
790#if _LIBCPP_STD_VER > 14
791    template <class... _Args> reference emplace_front(_Args&&... __args);
792#else
793    template <class... _Args> void      emplace_front(_Args&&... __args);
794#endif
795    void push_front(value_type&& __v);
796#endif // _LIBCPP_CXX03_LANG
797    void push_front(const value_type& __v);
798
799    void pop_front();
800
801#ifndef _LIBCPP_CXX03_LANG
802    template <class... _Args>
803        iterator emplace_after(const_iterator __p, _Args&&... __args);
804
805    iterator insert_after(const_iterator __p, value_type&& __v);
806    iterator insert_after(const_iterator __p, initializer_list<value_type> __il)
807        {return insert_after(__p, __il.begin(), __il.end());}
808#endif // _LIBCPP_CXX03_LANG
809    iterator insert_after(const_iterator __p, const value_type& __v);
810    iterator insert_after(const_iterator __p, size_type __n, const value_type& __v);
811    template <class _InputIterator>
812    _LIBCPP_INLINE_VISIBILITY
813    __enable_if_t<__is_cpp17_input_iterator<_InputIterator>::value, iterator>
814        insert_after(const_iterator __p, _InputIterator __f, _InputIterator __l);
815
816    iterator erase_after(const_iterator __p);
817    iterator erase_after(const_iterator __f, const_iterator __l);
818
819    _LIBCPP_INLINE_VISIBILITY
820    void swap(forward_list& __x)
821#if _LIBCPP_STD_VER >= 14
822        _NOEXCEPT
823#else
824        _NOEXCEPT_(!__node_traits::propagate_on_container_swap::value ||
825                   __is_nothrow_swappable<__node_allocator>::value)
826#endif
827        {base::swap(__x);}
828
829    void resize(size_type __n);
830    void resize(size_type __n, const value_type& __v);
831    _LIBCPP_INLINE_VISIBILITY
832    void clear() _NOEXCEPT {base::clear();}
833
834    _LIBCPP_INLINE_VISIBILITY
835    void splice_after(const_iterator __p, forward_list&& __x);
836    _LIBCPP_INLINE_VISIBILITY
837    void splice_after(const_iterator __p, forward_list&& __x, const_iterator __i);
838    _LIBCPP_INLINE_VISIBILITY
839    void splice_after(const_iterator __p, forward_list&& __x,
840                      const_iterator __f, const_iterator __l);
841    void splice_after(const_iterator __p, forward_list& __x);
842    void splice_after(const_iterator __p, forward_list& __x, const_iterator __i);
843    void splice_after(const_iterator __p, forward_list& __x,
844                      const_iterator __f, const_iterator __l);
845    __remove_return_type remove(const value_type& __v);
846    template <class _Predicate> __remove_return_type remove_if(_Predicate __pred);
847    _LIBCPP_INLINE_VISIBILITY
848    __remove_return_type unique() { return unique(__equal_to()); }
849    template <class _BinaryPredicate> __remove_return_type unique(_BinaryPredicate __binary_pred);
850#ifndef _LIBCPP_CXX03_LANG
851    _LIBCPP_INLINE_VISIBILITY
852    void merge(forward_list&& __x) {merge(__x, __less<value_type>());}
853    template <class _Compare>
854        _LIBCPP_INLINE_VISIBILITY
855        void merge(forward_list&& __x, _Compare __comp)
856        {merge(__x, _VSTD::move(__comp));}
857#endif // _LIBCPP_CXX03_LANG
858    _LIBCPP_INLINE_VISIBILITY
859    void merge(forward_list& __x) {merge(__x, __less<value_type>());}
860    template <class _Compare> void merge(forward_list& __x, _Compare __comp);
861    _LIBCPP_INLINE_VISIBILITY
862    void sort() {sort(__less<value_type>());}
863    template <class _Compare> _LIBCPP_INLINE_VISIBILITY void sort(_Compare __comp);
864    void reverse() _NOEXCEPT;
865
866private:
867
868#ifndef _LIBCPP_CXX03_LANG
869    void __move_assign(forward_list& __x, true_type)
870        _NOEXCEPT_(is_nothrow_move_assignable<allocator_type>::value);
871    void __move_assign(forward_list& __x, false_type);
872#endif // _LIBCPP_CXX03_LANG
873
874    template <class _Compare>
875        static
876        __node_pointer
877        __merge(__node_pointer __f1, __node_pointer __f2, _Compare& __comp);
878
879    template <class _Compare>
880        static
881        __node_pointer
882        __sort(__node_pointer __f, difference_type __sz, _Compare& __comp);
883};
884
885
886#if _LIBCPP_STD_VER >= 17
887template<class _InputIterator,
888         class _Alloc = allocator<__iter_value_type<_InputIterator>>,
889         class = enable_if_t<__is_cpp17_input_iterator<_InputIterator>::value>,
890         class = enable_if_t<__is_allocator<_Alloc>::value>
891         >
892forward_list(_InputIterator, _InputIterator)
893  -> forward_list<__iter_value_type<_InputIterator>, _Alloc>;
894
895template<class _InputIterator,
896         class _Alloc,
897         class = enable_if_t<__is_cpp17_input_iterator<_InputIterator>::value>,
898         class = enable_if_t<__is_allocator<_Alloc>::value>
899         >
900forward_list(_InputIterator, _InputIterator, _Alloc)
901  -> forward_list<__iter_value_type<_InputIterator>, _Alloc>;
902#endif
903
904template <class _Tp, class _Alloc>
905inline
906forward_list<_Tp, _Alloc>::forward_list(const allocator_type& __a)
907    : base(__a)
908{
909}
910
911template <class _Tp, class _Alloc>
912forward_list<_Tp, _Alloc>::forward_list(size_type __n)
913{
914    if (__n > 0)
915    {
916        __node_allocator& __a = base::__alloc();
917        typedef __allocator_destructor<__node_allocator> _Dp;
918        unique_ptr<__node, _Dp> __h(nullptr, _Dp(__a, 1));
919        for (__begin_node_pointer __p = base::__before_begin(); __n > 0; --__n,
920                                                             __p = __p->__next_as_begin())
921        {
922            __h.reset(__node_traits::allocate(__a, 1));
923            __node_traits::construct(__a, _VSTD::addressof(__h->__value_));
924            __h->__next_ = nullptr;
925            __p->__next_ = __h.release();
926        }
927    }
928}
929
930#if _LIBCPP_STD_VER > 11
931template <class _Tp, class _Alloc>
932forward_list<_Tp, _Alloc>::forward_list(size_type __n,
933                                        const allocator_type& __base_alloc)
934    : base ( __base_alloc )
935{
936    if (__n > 0)
937    {
938        __node_allocator& __a = base::__alloc();
939        typedef __allocator_destructor<__node_allocator> _Dp;
940        unique_ptr<__node, _Dp> __h(nullptr, _Dp(__a, 1));
941        for (__begin_node_pointer __p = base::__before_begin(); __n > 0; --__n,
942                                                             __p = __p->__next_as_begin())
943        {
944            __h.reset(__node_traits::allocate(__a, 1));
945            __node_traits::construct(__a, _VSTD::addressof(__h->__value_));
946            __h->__next_ = nullptr;
947            __p->__next_ = __h.release();
948        }
949    }
950}
951#endif
952
953template <class _Tp, class _Alloc>
954forward_list<_Tp, _Alloc>::forward_list(size_type __n, const value_type& __v)
955{
956    insert_after(cbefore_begin(), __n, __v);
957}
958
959template <class _Tp, class _Alloc>
960template <class _InputIterator>
961forward_list<_Tp, _Alloc>::forward_list(_InputIterator __f, _InputIterator __l,
962                                        __enable_if_t<__is_cpp17_input_iterator<_InputIterator>::value>*)
963{
964    insert_after(cbefore_begin(), __f, __l);
965}
966
967template <class _Tp, class _Alloc>
968template <class _InputIterator>
969forward_list<_Tp, _Alloc>::forward_list(_InputIterator __f, _InputIterator __l,
970                                        const allocator_type& __a,
971                                        __enable_if_t<__is_cpp17_input_iterator<_InputIterator>::value>*)
972    : base(__a)
973{
974    insert_after(cbefore_begin(), __f, __l);
975}
976
977template <class _Tp, class _Alloc>
978forward_list<_Tp, _Alloc>::forward_list(const forward_list& __x)
979    : base(
980          __node_traits::select_on_container_copy_construction(__x.__alloc())) {
981  insert_after(cbefore_begin(), __x.begin(), __x.end());
982}
983
984template <class _Tp, class _Alloc>
985forward_list<_Tp, _Alloc>::forward_list(const forward_list& __x,
986                                        const __type_identity_t<allocator_type>& __a)
987    : base(__a)
988{
989    insert_after(cbefore_begin(), __x.begin(), __x.end());
990}
991
992template <class _Tp, class _Alloc>
993forward_list<_Tp, _Alloc>&
994forward_list<_Tp, _Alloc>::operator=(const forward_list& __x)
995{
996    if (this != _VSTD::addressof(__x))
997    {
998        base::__copy_assign_alloc(__x);
999        assign(__x.begin(), __x.end());
1000    }
1001    return *this;
1002}
1003
1004#ifndef _LIBCPP_CXX03_LANG
1005template <class _Tp, class _Alloc>
1006forward_list<_Tp, _Alloc>::forward_list(forward_list&& __x,
1007                                        const __type_identity_t<allocator_type>& __a)
1008    : base(_VSTD::move(__x), __a)
1009{
1010    if (base::__alloc() != __x.__alloc())
1011    {
1012        typedef move_iterator<iterator> _Ip;
1013        insert_after(cbefore_begin(), _Ip(__x.begin()), _Ip(__x.end()));
1014    }
1015}
1016
1017template <class _Tp, class _Alloc>
1018forward_list<_Tp, _Alloc>::forward_list(initializer_list<value_type> __il)
1019{
1020    insert_after(cbefore_begin(), __il.begin(), __il.end());
1021}
1022
1023template <class _Tp, class _Alloc>
1024forward_list<_Tp, _Alloc>::forward_list(initializer_list<value_type> __il,
1025                                        const allocator_type& __a)
1026    : base(__a)
1027{
1028    insert_after(cbefore_begin(), __il.begin(), __il.end());
1029}
1030
1031template <class _Tp, class _Alloc>
1032void
1033forward_list<_Tp, _Alloc>::__move_assign(forward_list& __x, true_type)
1034    _NOEXCEPT_(is_nothrow_move_assignable<allocator_type>::value)
1035{
1036    clear();
1037    base::__move_assign_alloc(__x);
1038    base::__before_begin()->__next_ = __x.__before_begin()->__next_;
1039    __x.__before_begin()->__next_ = nullptr;
1040}
1041
1042template <class _Tp, class _Alloc>
1043void
1044forward_list<_Tp, _Alloc>::__move_assign(forward_list& __x, false_type)
1045{
1046    if (base::__alloc() == __x.__alloc())
1047        __move_assign(__x, true_type());
1048    else
1049    {
1050        typedef move_iterator<iterator> _Ip;
1051        assign(_Ip(__x.begin()), _Ip(__x.end()));
1052    }
1053}
1054
1055template <class _Tp, class _Alloc>
1056inline
1057forward_list<_Tp, _Alloc>&
1058forward_list<_Tp, _Alloc>::operator=(forward_list&& __x)
1059    _NOEXCEPT_(
1060             __node_traits::propagate_on_container_move_assignment::value &&
1061             is_nothrow_move_assignable<allocator_type>::value)
1062{
1063    __move_assign(__x, integral_constant<bool,
1064          __node_traits::propagate_on_container_move_assignment::value>());
1065    return *this;
1066}
1067
1068template <class _Tp, class _Alloc>
1069inline
1070forward_list<_Tp, _Alloc>&
1071forward_list<_Tp, _Alloc>::operator=(initializer_list<value_type> __il)
1072{
1073    assign(__il.begin(), __il.end());
1074    return *this;
1075}
1076
1077#endif // _LIBCPP_CXX03_LANG
1078
1079template <class _Tp, class _Alloc>
1080template <class _InputIterator>
1081__enable_if_t<__is_cpp17_input_iterator<_InputIterator>::value, void>
1082forward_list<_Tp, _Alloc>::assign(_InputIterator __f, _InputIterator __l)
1083{
1084    iterator __i = before_begin();
1085    iterator __j = _VSTD::next(__i);
1086    iterator __e = end();
1087    for (; __j != __e && __f != __l; ++__i, (void) ++__j, ++__f)
1088        *__j = *__f;
1089    if (__j == __e)
1090        insert_after(__i, __f, __l);
1091    else
1092        erase_after(__i, __e);
1093}
1094
1095template <class _Tp, class _Alloc>
1096void
1097forward_list<_Tp, _Alloc>::assign(size_type __n, const value_type& __v)
1098{
1099    iterator __i = before_begin();
1100    iterator __j = _VSTD::next(__i);
1101    iterator __e = end();
1102    for (; __j != __e && __n > 0; --__n, ++__i, ++__j)
1103        *__j = __v;
1104    if (__j == __e)
1105        insert_after(__i, __n, __v);
1106    else
1107        erase_after(__i, __e);
1108}
1109
1110#ifndef _LIBCPP_CXX03_LANG
1111
1112template <class _Tp, class _Alloc>
1113inline
1114void
1115forward_list<_Tp, _Alloc>::assign(initializer_list<value_type> __il)
1116{
1117    assign(__il.begin(), __il.end());
1118}
1119
1120template <class _Tp, class _Alloc>
1121template <class... _Args>
1122#if _LIBCPP_STD_VER > 14
1123typename forward_list<_Tp, _Alloc>::reference
1124#else
1125void
1126#endif
1127forward_list<_Tp, _Alloc>::emplace_front(_Args&&... __args)
1128{
1129    __node_allocator& __a = base::__alloc();
1130    typedef __allocator_destructor<__node_allocator> _Dp;
1131    unique_ptr<__node, _Dp> __h(__node_traits::allocate(__a, 1), _Dp(__a, 1));
1132    __node_traits::construct(__a, _VSTD::addressof(__h->__value_),
1133                                  _VSTD::forward<_Args>(__args)...);
1134    __h->__next_ = base::__before_begin()->__next_;
1135    base::__before_begin()->__next_ = __h.release();
1136#if _LIBCPP_STD_VER > 14
1137    return base::__before_begin()->__next_->__value_;
1138#endif
1139}
1140
1141template <class _Tp, class _Alloc>
1142void
1143forward_list<_Tp, _Alloc>::push_front(value_type&& __v)
1144{
1145    __node_allocator& __a = base::__alloc();
1146    typedef __allocator_destructor<__node_allocator> _Dp;
1147    unique_ptr<__node, _Dp> __h(__node_traits::allocate(__a, 1), _Dp(__a, 1));
1148    __node_traits::construct(__a, _VSTD::addressof(__h->__value_), _VSTD::move(__v));
1149    __h->__next_ = base::__before_begin()->__next_;
1150    base::__before_begin()->__next_ = __h.release();
1151}
1152
1153#endif // _LIBCPP_CXX03_LANG
1154
1155template <class _Tp, class _Alloc>
1156void
1157forward_list<_Tp, _Alloc>::push_front(const value_type& __v)
1158{
1159    __node_allocator& __a = base::__alloc();
1160    typedef __allocator_destructor<__node_allocator> _Dp;
1161    unique_ptr<__node, _Dp> __h(__node_traits::allocate(__a, 1), _Dp(__a, 1));
1162    __node_traits::construct(__a, _VSTD::addressof(__h->__value_), __v);
1163    __h->__next_ = base::__before_begin()->__next_;
1164    base::__before_begin()->__next_ = __h.release();
1165}
1166
1167template <class _Tp, class _Alloc>
1168void
1169forward_list<_Tp, _Alloc>::pop_front()
1170{
1171    __node_allocator& __a = base::__alloc();
1172    __node_pointer __p = base::__before_begin()->__next_;
1173    base::__before_begin()->__next_ = __p->__next_;
1174    __node_traits::destroy(__a, _VSTD::addressof(__p->__value_));
1175    __node_traits::deallocate(__a, __p, 1);
1176}
1177
1178#ifndef _LIBCPP_CXX03_LANG
1179
1180template <class _Tp, class _Alloc>
1181template <class... _Args>
1182typename forward_list<_Tp, _Alloc>::iterator
1183forward_list<_Tp, _Alloc>::emplace_after(const_iterator __p, _Args&&... __args)
1184{
1185    __begin_node_pointer const __r = __p.__get_begin();
1186    __node_allocator& __a = base::__alloc();
1187    typedef __allocator_destructor<__node_allocator> _Dp;
1188    unique_ptr<__node, _Dp> __h(__node_traits::allocate(__a, 1), _Dp(__a, 1));
1189    __node_traits::construct(__a, _VSTD::addressof(__h->__value_),
1190                                  _VSTD::forward<_Args>(__args)...);
1191    __h->__next_ = __r->__next_;
1192    __r->__next_ = __h.release();
1193    return iterator(__r->__next_);
1194}
1195
1196template <class _Tp, class _Alloc>
1197typename forward_list<_Tp, _Alloc>::iterator
1198forward_list<_Tp, _Alloc>::insert_after(const_iterator __p, value_type&& __v)
1199{
1200    __begin_node_pointer const __r = __p.__get_begin();
1201    __node_allocator& __a = base::__alloc();
1202    typedef __allocator_destructor<__node_allocator> _Dp;
1203    unique_ptr<__node, _Dp> __h(__node_traits::allocate(__a, 1), _Dp(__a, 1));
1204    __node_traits::construct(__a, _VSTD::addressof(__h->__value_), _VSTD::move(__v));
1205    __h->__next_ = __r->__next_;
1206    __r->__next_ = __h.release();
1207    return iterator(__r->__next_);
1208}
1209
1210#endif // _LIBCPP_CXX03_LANG
1211
1212template <class _Tp, class _Alloc>
1213typename forward_list<_Tp, _Alloc>::iterator
1214forward_list<_Tp, _Alloc>::insert_after(const_iterator __p, const value_type& __v)
1215{
1216    __begin_node_pointer const __r = __p.__get_begin();
1217    __node_allocator& __a = base::__alloc();
1218    typedef __allocator_destructor<__node_allocator> _Dp;
1219    unique_ptr<__node, _Dp> __h(__node_traits::allocate(__a, 1), _Dp(__a, 1));
1220    __node_traits::construct(__a, _VSTD::addressof(__h->__value_), __v);
1221    __h->__next_ = __r->__next_;
1222    __r->__next_ = __h.release();
1223    return iterator(__r->__next_);
1224}
1225
1226template <class _Tp, class _Alloc>
1227typename forward_list<_Tp, _Alloc>::iterator
1228forward_list<_Tp, _Alloc>::insert_after(const_iterator __p, size_type __n,
1229                                        const value_type& __v)
1230{
1231    __begin_node_pointer __r = __p.__get_begin();
1232    if (__n > 0)
1233    {
1234        __node_allocator& __a = base::__alloc();
1235        typedef __allocator_destructor<__node_allocator> _Dp;
1236        unique_ptr<__node, _Dp> __h(__node_traits::allocate(__a, 1), _Dp(__a, 1));
1237        __node_traits::construct(__a, _VSTD::addressof(__h->__value_), __v);
1238        __node_pointer __first = __h.release();
1239        __node_pointer __last = __first;
1240#ifndef _LIBCPP_NO_EXCEPTIONS
1241        try
1242        {
1243#endif // _LIBCPP_NO_EXCEPTIONS
1244            for (--__n; __n != 0; --__n, __last = __last->__next_)
1245            {
1246                __h.reset(__node_traits::allocate(__a, 1));
1247                __node_traits::construct(__a, _VSTD::addressof(__h->__value_), __v);
1248                __last->__next_ = __h.release();
1249            }
1250#ifndef _LIBCPP_NO_EXCEPTIONS
1251        }
1252        catch (...)
1253        {
1254            while (__first != nullptr)
1255            {
1256                __node_pointer __next = __first->__next_;
1257                __node_traits::destroy(__a, _VSTD::addressof(__first->__value_));
1258                __node_traits::deallocate(__a, __first, 1);
1259                __first = __next;
1260            }
1261            throw;
1262        }
1263#endif // _LIBCPP_NO_EXCEPTIONS
1264        __last->__next_ = __r->__next_;
1265        __r->__next_ = __first;
1266        __r = static_cast<__begin_node_pointer>(__last);
1267    }
1268    return iterator(__r);
1269}
1270
1271template <class _Tp, class _Alloc>
1272template <class _InputIterator>
1273__enable_if_t<__is_cpp17_input_iterator<_InputIterator>::value, typename forward_list<_Tp, _Alloc>::iterator>
1274forward_list<_Tp, _Alloc>::insert_after(const_iterator __p,
1275                                        _InputIterator __f, _InputIterator __l)
1276{
1277    __begin_node_pointer __r = __p.__get_begin();
1278    if (__f != __l)
1279    {
1280        __node_allocator& __a = base::__alloc();
1281        typedef __allocator_destructor<__node_allocator> _Dp;
1282        unique_ptr<__node, _Dp> __h(__node_traits::allocate(__a, 1), _Dp(__a, 1));
1283        __node_traits::construct(__a, _VSTD::addressof(__h->__value_), *__f);
1284        __node_pointer __first = __h.release();
1285        __node_pointer __last = __first;
1286#ifndef _LIBCPP_NO_EXCEPTIONS
1287        try
1288        {
1289#endif // _LIBCPP_NO_EXCEPTIONS
1290            for (++__f; __f != __l; ++__f, ((void)(__last = __last->__next_)))
1291            {
1292                __h.reset(__node_traits::allocate(__a, 1));
1293                __node_traits::construct(__a, _VSTD::addressof(__h->__value_), *__f);
1294                __last->__next_ = __h.release();
1295            }
1296#ifndef _LIBCPP_NO_EXCEPTIONS
1297        }
1298        catch (...)
1299        {
1300            while (__first != nullptr)
1301            {
1302                __node_pointer __next = __first->__next_;
1303                __node_traits::destroy(__a, _VSTD::addressof(__first->__value_));
1304                __node_traits::deallocate(__a, __first, 1);
1305                __first = __next;
1306            }
1307            throw;
1308        }
1309#endif // _LIBCPP_NO_EXCEPTIONS
1310        __last->__next_ = __r->__next_;
1311        __r->__next_ = __first;
1312        __r = static_cast<__begin_node_pointer>(__last);
1313    }
1314    return iterator(__r);
1315}
1316
1317template <class _Tp, class _Alloc>
1318typename forward_list<_Tp, _Alloc>::iterator
1319forward_list<_Tp, _Alloc>::erase_after(const_iterator __f)
1320{
1321    __begin_node_pointer __p = __f.__get_begin();
1322    __node_pointer __n = __p->__next_;
1323    __p->__next_ = __n->__next_;
1324    __node_allocator& __a = base::__alloc();
1325    __node_traits::destroy(__a, _VSTD::addressof(__n->__value_));
1326    __node_traits::deallocate(__a, __n, 1);
1327    return iterator(__p->__next_);
1328}
1329
1330template <class _Tp, class _Alloc>
1331typename forward_list<_Tp, _Alloc>::iterator
1332forward_list<_Tp, _Alloc>::erase_after(const_iterator __f, const_iterator __l)
1333{
1334    __node_pointer __e = __l.__get_unsafe_node_pointer();
1335    if (__f != __l)
1336    {
1337        __begin_node_pointer __bp = __f.__get_begin();
1338
1339        __node_pointer __n = __bp->__next_;
1340        if (__n != __e)
1341        {
1342            __bp->__next_ = __e;
1343            __node_allocator& __a = base::__alloc();
1344            do
1345            {
1346                __node_pointer __tmp = __n->__next_;
1347                __node_traits::destroy(__a, _VSTD::addressof(__n->__value_));
1348                __node_traits::deallocate(__a, __n, 1);
1349                __n = __tmp;
1350            } while (__n != __e);
1351        }
1352    }
1353    return iterator(__e);
1354}
1355
1356template <class _Tp, class _Alloc>
1357void
1358forward_list<_Tp, _Alloc>::resize(size_type __n)
1359{
1360    size_type __sz = 0;
1361    iterator __p = before_begin();
1362    iterator __i = begin();
1363    iterator __e = end();
1364    for (; __i != __e && __sz < __n; ++__p, ++__i, ++__sz)
1365        ;
1366    if (__i != __e)
1367        erase_after(__p, __e);
1368    else
1369    {
1370        __n -= __sz;
1371        if (__n > 0)
1372        {
1373            __node_allocator& __a = base::__alloc();
1374            typedef __allocator_destructor<__node_allocator> _Dp;
1375            unique_ptr<__node, _Dp> __h(nullptr, _Dp(__a, 1));
1376            for (__begin_node_pointer __ptr = __p.__get_begin(); __n > 0; --__n,
1377                                                         __ptr = __ptr->__next_as_begin())
1378            {
1379                __h.reset(__node_traits::allocate(__a, 1));
1380                __node_traits::construct(__a, _VSTD::addressof(__h->__value_));
1381                __h->__next_ = nullptr;
1382                __ptr->__next_ = __h.release();
1383            }
1384        }
1385    }
1386}
1387
1388template <class _Tp, class _Alloc>
1389void
1390forward_list<_Tp, _Alloc>::resize(size_type __n, const value_type& __v)
1391{
1392    size_type __sz = 0;
1393    iterator __p = before_begin();
1394    iterator __i = begin();
1395    iterator __e = end();
1396    for (; __i != __e && __sz < __n; ++__p, ++__i, ++__sz)
1397        ;
1398    if (__i != __e)
1399        erase_after(__p, __e);
1400    else
1401    {
1402        __n -= __sz;
1403        if (__n > 0)
1404        {
1405            __node_allocator& __a = base::__alloc();
1406            typedef __allocator_destructor<__node_allocator> _Dp;
1407            unique_ptr<__node, _Dp> __h(nullptr, _Dp(__a, 1));
1408            for (__begin_node_pointer __ptr = __p.__get_begin(); __n > 0; --__n,
1409                                                         __ptr = __ptr->__next_as_begin())
1410            {
1411                __h.reset(__node_traits::allocate(__a, 1));
1412                __node_traits::construct(__a, _VSTD::addressof(__h->__value_), __v);
1413                __h->__next_ = nullptr;
1414                __ptr->__next_ = __h.release();
1415            }
1416        }
1417    }
1418}
1419
1420template <class _Tp, class _Alloc>
1421void
1422forward_list<_Tp, _Alloc>::splice_after(const_iterator __p,
1423                                        forward_list& __x)
1424{
1425    if (!__x.empty())
1426    {
1427        if (__p.__get_begin()->__next_ != nullptr)
1428        {
1429            const_iterator __lm1 = __x.before_begin();
1430            while (__lm1.__get_begin()->__next_ != nullptr)
1431                ++__lm1;
1432            __lm1.__get_begin()->__next_ = __p.__get_begin()->__next_;
1433        }
1434        __p.__get_begin()->__next_ = __x.__before_begin()->__next_;
1435        __x.__before_begin()->__next_ = nullptr;
1436    }
1437}
1438
1439template <class _Tp, class _Alloc>
1440void
1441forward_list<_Tp, _Alloc>::splice_after(const_iterator __p,
1442                                        forward_list& /*__other*/,
1443                                        const_iterator __i)
1444{
1445    const_iterator __lm1 = _VSTD::next(__i);
1446    if (__p != __i && __p != __lm1)
1447    {
1448        __i.__get_begin()->__next_ = __lm1.__get_begin()->__next_;
1449        __lm1.__get_begin()->__next_ = __p.__get_begin()->__next_;
1450        __p.__get_begin()->__next_ = __lm1.__get_unsafe_node_pointer();
1451    }
1452}
1453
1454template <class _Tp, class _Alloc>
1455void
1456forward_list<_Tp, _Alloc>::splice_after(const_iterator __p,
1457                                        forward_list& /*__other*/,
1458                                        const_iterator __f, const_iterator __l)
1459{
1460    if (__f != __l && __p != __f)
1461    {
1462        const_iterator __lm1 = __f;
1463        while (__lm1.__get_begin()->__next_ != __l.__get_begin())
1464            ++__lm1;
1465        if (__f != __lm1)
1466        {
1467            __lm1.__get_begin()->__next_ = __p.__get_begin()->__next_;
1468            __p.__get_begin()->__next_ = __f.__get_begin()->__next_;
1469            __f.__get_begin()->__next_ = __l.__get_unsafe_node_pointer();
1470        }
1471    }
1472}
1473
1474template <class _Tp, class _Alloc>
1475inline _LIBCPP_INLINE_VISIBILITY
1476void
1477forward_list<_Tp, _Alloc>::splice_after(const_iterator __p,
1478                                        forward_list&& __x)
1479{
1480    splice_after(__p, __x);
1481}
1482
1483template <class _Tp, class _Alloc>
1484inline _LIBCPP_INLINE_VISIBILITY
1485void
1486forward_list<_Tp, _Alloc>::splice_after(const_iterator __p,
1487                                        forward_list&& __x,
1488                                        const_iterator __i)
1489{
1490    splice_after(__p, __x, __i);
1491}
1492
1493template <class _Tp, class _Alloc>
1494inline _LIBCPP_INLINE_VISIBILITY
1495void
1496forward_list<_Tp, _Alloc>::splice_after(const_iterator __p,
1497                                        forward_list&& __x,
1498                                        const_iterator __f, const_iterator __l)
1499{
1500    splice_after(__p, __x, __f, __l);
1501}
1502
1503template <class _Tp, class _Alloc>
1504typename forward_list<_Tp, _Alloc>::__remove_return_type
1505forward_list<_Tp, _Alloc>::remove(const value_type& __v)
1506{
1507    forward_list<_Tp, _Alloc> __deleted_nodes(get_allocator()); // collect the nodes we're removing
1508    typename forward_list<_Tp, _Alloc>::size_type __count_removed = 0;
1509    const iterator __e = end();
1510    for (iterator __i = before_begin(); __i.__get_begin()->__next_ != nullptr;)
1511    {
1512        if (__i.__get_begin()->__next_->__value_ == __v)
1513        {
1514            ++__count_removed;
1515            iterator __j = _VSTD::next(__i, 2);
1516            for (; __j != __e && *__j == __v; ++__j)
1517                ++__count_removed;
1518            __deleted_nodes.splice_after(__deleted_nodes.before_begin(), *this, __i, __j);
1519            if (__j == __e)
1520                break;
1521            __i = __j;
1522        }
1523        else
1524            ++__i;
1525    }
1526
1527    return (__remove_return_type) __count_removed;
1528}
1529
1530template <class _Tp, class _Alloc>
1531template <class _Predicate>
1532typename forward_list<_Tp, _Alloc>::__remove_return_type
1533forward_list<_Tp, _Alloc>::remove_if(_Predicate __pred)
1534{
1535    forward_list<_Tp, _Alloc> __deleted_nodes(get_allocator()); // collect the nodes we're removing
1536    typename forward_list<_Tp, _Alloc>::size_type __count_removed = 0;
1537    const iterator __e = end();
1538    for (iterator __i = before_begin(); __i.__get_begin()->__next_ != nullptr;)
1539    {
1540        if (__pred(__i.__get_begin()->__next_->__value_))
1541        {
1542            ++__count_removed;
1543            iterator __j = _VSTD::next(__i, 2);
1544            for (; __j != __e && __pred(*__j); ++__j)
1545                ++__count_removed;
1546            __deleted_nodes.splice_after(__deleted_nodes.before_begin(), *this, __i, __j);
1547            if (__j == __e)
1548                break;
1549            __i = __j;
1550        }
1551        else
1552            ++__i;
1553    }
1554
1555    return (__remove_return_type) __count_removed;
1556}
1557
1558template <class _Tp, class _Alloc>
1559template <class _BinaryPredicate>
1560typename forward_list<_Tp, _Alloc>::__remove_return_type
1561forward_list<_Tp, _Alloc>::unique(_BinaryPredicate __binary_pred)
1562{
1563    forward_list<_Tp, _Alloc> __deleted_nodes(get_allocator()); // collect the nodes we're removing
1564    typename forward_list<_Tp, _Alloc>::size_type __count_removed = 0;
1565    for (iterator __i = begin(), __e = end(); __i != __e;)
1566    {
1567        iterator __j = _VSTD::next(__i);
1568        for (; __j != __e && __binary_pred(*__i, *__j); ++__j)
1569            ++__count_removed;
1570        if (__i.__get_begin()->__next_ != __j.__get_unsafe_node_pointer())
1571            __deleted_nodes.splice_after(__deleted_nodes.before_begin(), *this, __i, __j);
1572        __i = __j;
1573    }
1574
1575    return (__remove_return_type) __count_removed;
1576}
1577
1578template <class _Tp, class _Alloc>
1579template <class _Compare>
1580void
1581forward_list<_Tp, _Alloc>::merge(forward_list& __x, _Compare __comp)
1582{
1583    if (this != _VSTD::addressof(__x))
1584    {
1585        base::__before_begin()->__next_ = __merge(base::__before_begin()->__next_,
1586                                                    __x.__before_begin()->__next_,
1587                                                    __comp);
1588        __x.__before_begin()->__next_ = nullptr;
1589    }
1590}
1591
1592template <class _Tp, class _Alloc>
1593template <class _Compare>
1594typename forward_list<_Tp, _Alloc>::__node_pointer
1595forward_list<_Tp, _Alloc>::__merge(__node_pointer __f1, __node_pointer __f2,
1596                                   _Compare& __comp)
1597{
1598    if (__f1 == nullptr)
1599        return __f2;
1600    if (__f2 == nullptr)
1601        return __f1;
1602    __node_pointer __r;
1603    if (__comp(__f2->__value_, __f1->__value_))
1604    {
1605        __node_pointer __t = __f2;
1606        while (__t->__next_ != nullptr &&
1607                             __comp(__t->__next_->__value_, __f1->__value_))
1608            __t = __t->__next_;
1609        __r = __f2;
1610        __f2 = __t->__next_;
1611        __t->__next_ = __f1;
1612    }
1613    else
1614        __r = __f1;
1615    __node_pointer __p = __f1;
1616    __f1 = __f1->__next_;
1617    while (__f1 != nullptr && __f2 != nullptr)
1618    {
1619        if (__comp(__f2->__value_, __f1->__value_))
1620        {
1621            __node_pointer __t = __f2;
1622            while (__t->__next_ != nullptr &&
1623                                 __comp(__t->__next_->__value_, __f1->__value_))
1624                __t = __t->__next_;
1625            __p->__next_ = __f2;
1626            __f2 = __t->__next_;
1627            __t->__next_ = __f1;
1628        }
1629        __p = __f1;
1630        __f1 = __f1->__next_;
1631    }
1632    if (__f2 != nullptr)
1633        __p->__next_ = __f2;
1634    return __r;
1635}
1636
1637template <class _Tp, class _Alloc>
1638template <class _Compare>
1639inline
1640void
1641forward_list<_Tp, _Alloc>::sort(_Compare __comp)
1642{
1643    base::__before_begin()->__next_ = __sort(base::__before_begin()->__next_,
1644                                       _VSTD::distance(begin(), end()), __comp);
1645}
1646
1647template <class _Tp, class _Alloc>
1648template <class _Compare>
1649typename forward_list<_Tp, _Alloc>::__node_pointer
1650forward_list<_Tp, _Alloc>::__sort(__node_pointer __f1, difference_type __sz,
1651                                  _Compare& __comp)
1652{
1653    switch (__sz)
1654    {
1655    case 0:
1656    case 1:
1657        return __f1;
1658    case 2:
1659        if (__comp(__f1->__next_->__value_, __f1->__value_))
1660        {
1661            __node_pointer __t = __f1->__next_;
1662            __t->__next_ = __f1;
1663            __f1->__next_ = nullptr;
1664            __f1 = __t;
1665        }
1666        return __f1;
1667    }
1668    difference_type __sz1 = __sz / 2;
1669    difference_type __sz2 = __sz - __sz1;
1670    __node_pointer __t = _VSTD::next(iterator(__f1), __sz1 - 1).__get_unsafe_node_pointer();
1671    __node_pointer __f2 = __t->__next_;
1672    __t->__next_ = nullptr;
1673    return __merge(__sort(__f1, __sz1, __comp),
1674                   __sort(__f2, __sz2, __comp), __comp);
1675}
1676
1677template <class _Tp, class _Alloc>
1678void
1679forward_list<_Tp, _Alloc>::reverse() _NOEXCEPT
1680{
1681    __node_pointer __p = base::__before_begin()->__next_;
1682    if (__p != nullptr)
1683    {
1684        __node_pointer __f = __p->__next_;
1685        __p->__next_ = nullptr;
1686        while (__f != nullptr)
1687        {
1688            __node_pointer __t = __f->__next_;
1689            __f->__next_ = __p;
1690            __p = __f;
1691            __f = __t;
1692        }
1693        base::__before_begin()->__next_ = __p;
1694    }
1695}
1696
1697template <class _Tp, class _Alloc>
1698_LIBCPP_HIDE_FROM_ABI
1699bool operator==(const forward_list<_Tp, _Alloc>& __x,
1700                const forward_list<_Tp, _Alloc>& __y)
1701{
1702    typedef forward_list<_Tp, _Alloc> _Cp;
1703    typedef typename _Cp::const_iterator _Ip;
1704    _Ip __ix = __x.begin();
1705    _Ip __ex = __x.end();
1706    _Ip __iy = __y.begin();
1707    _Ip __ey = __y.end();
1708    for (; __ix != __ex && __iy != __ey; ++__ix, ++__iy)
1709        if (!(*__ix == *__iy))
1710            return false;
1711    return (__ix == __ex) == (__iy == __ey);
1712}
1713
1714template <class _Tp, class _Alloc>
1715inline _LIBCPP_INLINE_VISIBILITY
1716bool operator!=(const forward_list<_Tp, _Alloc>& __x,
1717                const forward_list<_Tp, _Alloc>& __y)
1718{
1719    return !(__x == __y);
1720}
1721
1722template <class _Tp, class _Alloc>
1723inline _LIBCPP_INLINE_VISIBILITY
1724bool operator< (const forward_list<_Tp, _Alloc>& __x,
1725                const forward_list<_Tp, _Alloc>& __y)
1726{
1727    return _VSTD::lexicographical_compare(__x.begin(), __x.end(),
1728                                         __y.begin(), __y.end());
1729}
1730
1731template <class _Tp, class _Alloc>
1732inline _LIBCPP_INLINE_VISIBILITY
1733bool operator> (const forward_list<_Tp, _Alloc>& __x,
1734                const forward_list<_Tp, _Alloc>& __y)
1735{
1736    return __y < __x;
1737}
1738
1739template <class _Tp, class _Alloc>
1740inline _LIBCPP_INLINE_VISIBILITY
1741bool operator>=(const forward_list<_Tp, _Alloc>& __x,
1742                const forward_list<_Tp, _Alloc>& __y)
1743{
1744    return !(__x < __y);
1745}
1746
1747template <class _Tp, class _Alloc>
1748inline _LIBCPP_INLINE_VISIBILITY
1749bool operator<=(const forward_list<_Tp, _Alloc>& __x,
1750                const forward_list<_Tp, _Alloc>& __y)
1751{
1752    return !(__y < __x);
1753}
1754
1755template <class _Tp, class _Alloc>
1756inline _LIBCPP_INLINE_VISIBILITY
1757void
1758swap(forward_list<_Tp, _Alloc>& __x, forward_list<_Tp, _Alloc>& __y)
1759    _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y)))
1760{
1761    __x.swap(__y);
1762}
1763
1764#if _LIBCPP_STD_VER > 17
1765template <class _Tp, class _Allocator, class _Predicate>
1766inline _LIBCPP_INLINE_VISIBILITY
1767    typename forward_list<_Tp, _Allocator>::size_type
1768    erase_if(forward_list<_Tp, _Allocator>& __c, _Predicate __pred) {
1769  return __c.remove_if(__pred);
1770}
1771
1772template <class _Tp, class _Allocator, class _Up>
1773inline _LIBCPP_INLINE_VISIBILITY
1774    typename forward_list<_Tp, _Allocator>::size_type
1775    erase(forward_list<_Tp, _Allocator>& __c, const _Up& __v) {
1776  return _VSTD::erase_if(__c, [&](auto& __elem) { return __elem == __v; });
1777}
1778#endif
1779
1780_LIBCPP_END_NAMESPACE_STD
1781
1782#if _LIBCPP_STD_VER > 14
1783_LIBCPP_BEGIN_NAMESPACE_STD
1784namespace pmr {
1785template <class _ValueT>
1786using forward_list = std::forward_list<_ValueT, polymorphic_allocator<_ValueT>>;
1787} // namespace pmr
1788_LIBCPP_END_NAMESPACE_STD
1789#endif
1790
1791_LIBCPP_POP_MACROS
1792
1793#if !defined(_LIBCPP_REMOVE_TRANSITIVE_INCLUDES) && _LIBCPP_STD_VER <= 20
1794#  include <algorithm>
1795#  include <atomic>
1796#  include <concepts>
1797#  include <functional>
1798#  include <iosfwd>
1799#  include <iterator>
1800#  include <typeinfo>
1801#endif
1802
1803#endif // _LIBCPP_FORWARD_LIST
1804