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