contrib/libc++/include/forward_list

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