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