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