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