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