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