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