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