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