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