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