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