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