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