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