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