contrib/libc++/include/forward_list

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