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