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