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