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