contrib/libc++/include/forward_list

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