contrib/libc++/include/list

   1 // -*- C++ -*-
   2 //===---------------------------- 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_LIST
  12 #define _LIBCPP_LIST
  13
  14 /*
  15     list synopsis
  16
  17 namespace std
  18 {
  19
  20 template <class T, class Alloc = allocator<T> >
  21 class list
  22 {
  23 public:
  24
  25     // types:
  26     typedef T value_type;
  27     typedef Alloc allocator_type;
  28     typedef typename allocator_type::reference reference;
  29     typedef typename allocator_type::const_reference const_reference;
  30     typedef typename allocator_type::pointer pointer;
  31     typedef typename allocator_type::const_pointer const_pointer;
  32     typedef implementation-defined iterator;
  33     typedef implementation-defined const_iterator;
  34     typedef implementation-defined size_type;
  35     typedef implementation-defined difference_type;
  36     typedef reverse_iterator<iterator> reverse_iterator;
  37     typedef reverse_iterator<const_iterator> const_reverse_iterator;
  38
  39     list()
  40         noexcept(is_nothrow_default_constructible<allocator_type>::value);
  41     explicit list(const allocator_type& a);
  42     explicit list(size_type n);
  43     explicit list(size_type n, const allocator_type& a); // C++14
  44     list(size_type n, const value_type& value);
  45     list(size_type n, const value_type& value, const allocator_type& a);
  46     template <class Iter>
  47         list(Iter first, Iter last);
  48     template <class Iter>
  49         list(Iter first, Iter last, const allocator_type& a);
  50     list(const list& x);
  51     list(const list&, const allocator_type& a);
  52     list(list&& x)
  53         noexcept(is_nothrow_move_constructible<allocator_type>::value);
  54     list(list&&, const allocator_type& a);
  55     list(initializer_list<value_type>);
  56     list(initializer_list<value_type>, const allocator_type& a);
  57
  58     ~list();
  59
  60     list& operator=(const list& x);
  61     list& operator=(list&& x)
  62         noexcept(
  63              allocator_type::propagate_on_container_move_assignment::value &&
  64              is_nothrow_move_assignable<allocator_type>::value);
  65     list& operator=(initializer_list<value_type>);
  66     template <class Iter>
  67         void assign(Iter first, Iter last);
  68     void assign(size_type n, const value_type& t);
  69     void assign(initializer_list<value_type>);
  70
  71     allocator_type get_allocator() const noexcept;
  72
  73     iterator begin() noexcept;
  74     const_iterator begin() const noexcept;
  75     iterator end() noexcept;
  76     const_iterator end() const noexcept;
  77     reverse_iterator rbegin() noexcept;
  78     const_reverse_iterator rbegin() const noexcept;
  79     reverse_iterator rend() noexcept;
  80     const_reverse_iterator rend() const noexcept;
  81     const_iterator cbegin() const noexcept;
  82     const_iterator cend() const noexcept;
  83     const_reverse_iterator crbegin() const noexcept;
  84     const_reverse_iterator crend() const noexcept;
  85
  86     reference front();
  87     const_reference front() const;
  88     reference back();
  89     const_reference back() const;
  90
  91     bool empty() const noexcept;
  92     size_type size() const noexcept;
  93     size_type max_size() const noexcept;
  94
  95     template <class... Args>
  96         reference emplace_front(Args&&... args); // reference in C++17
  97     void pop_front();
  98     template <class... Args>
  99         reference emplace_back(Args&&... args);  // reference in C++17
 100     void pop_back();
 101     void push_front(const value_type& x);
 102     void push_front(value_type&& x);
 103     void push_back(const value_type& x);
 104     void push_back(value_type&& x);
 105     template <class... Args>
 106         iterator emplace(const_iterator position, Args&&... args);
 107     iterator insert(const_iterator position, const value_type& x);
 108     iterator insert(const_iterator position, value_type&& x);
 109     iterator insert(const_iterator position, size_type n, const value_type& x);
 110     template <class Iter>
 111         iterator insert(const_iterator position, Iter first, Iter last);
 112     iterator insert(const_iterator position, initializer_list<value_type> il);
 113
 114     iterator erase(const_iterator position);
 115     iterator erase(const_iterator position, const_iterator last);
 116
 117     void resize(size_type sz);
 118     void resize(size_type sz, const value_type& c);
 119
 120     void swap(list&)
 121         noexcept(allocator_traits<allocator_type>::is_always_equal::value);  // C++17
 122     void clear() noexcept;
 123
 124     void splice(const_iterator position, list& x);
 125     void splice(const_iterator position, list&& x);
 126     void splice(const_iterator position, list& x, const_iterator i);
 127     void splice(const_iterator position, list&& x, const_iterator i);
 128     void splice(const_iterator position, list& x, const_iterator first,
 129                                                   const_iterator last);
 130     void splice(const_iterator position, list&& x, const_iterator first,
 131                                                   const_iterator last);
 132
 133     void remove(const value_type& value);
 134     template <class Pred> void remove_if(Pred pred);
 135     void unique();
 136     template <class BinaryPredicate>
 137         void unique(BinaryPredicate binary_pred);
 138     void merge(list& x);
 139     void merge(list&& x);
 140     template <class Compare>
 141         void merge(list& x, Compare comp);
 142     template <class Compare>
 143         void merge(list&& x, Compare comp);
 144     void sort();
 145     template <class Compare>
 146         void sort(Compare comp);
 147     void reverse() noexcept;
 148 };
 149
 150
 151 template <class InputIterator, class Allocator = allocator<typename iterator_traits<InputIterator>::value_type>>
 152     list(InputIterator, InputIterator, Allocator = Allocator())
 153     -> list<typename iterator_traits<InputIterator>::value_type, Allocator>;  // C++17
 154
 155 template <class T, class Alloc>
 156     bool operator==(const list<T,Alloc>& x, const list<T,Alloc>& y);
 157 template <class T, class Alloc>
 158     bool operator< (const list<T,Alloc>& x, const list<T,Alloc>& y);
 159 template <class T, class Alloc>
 160     bool operator!=(const list<T,Alloc>& x, const list<T,Alloc>& y);
 161 template <class T, class Alloc>
 162     bool operator> (const list<T,Alloc>& x, const list<T,Alloc>& y);
 163 template <class T, class Alloc>
 164     bool operator>=(const list<T,Alloc>& x, const list<T,Alloc>& y);
 165 template <class T, class Alloc>
 166     bool operator<=(const list<T,Alloc>& x, const list<T,Alloc>& y);
 167
 168 template <class T, class Alloc>
 169     void swap(list<T,Alloc>& x, list<T,Alloc>& y)
 170          noexcept(noexcept(x.swap(y)));
 171
 172 template <class T, class Allocator, class U>
 173     void erase(list<T, Allocator>& c, const U& value);       // C++20
 174 template <class T, class Allocator, class Predicate>
 175     void erase_if(list<T, Allocator>& c, Predicate pred);    // C++20
 176
 177 }  // std
 178
 179 */
 180
 181 #include <__config>
 182
 183 #include <memory>
 184 #include <limits>
 185 #include <initializer_list>
 186 #include <iterator>
 187 #include <algorithm>
 188 #include <type_traits>
 189 #include <version>
 190
 191 #include <__debug>
 192
 193 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
 194 #pragma GCC system_header
 195 #endif
 196
 197 _LIBCPP_PUSH_MACROS
 198 #include <__undef_macros>
 199
 200
 201 _LIBCPP_BEGIN_NAMESPACE_STD
 202
 203 template <class _Tp, class _VoidPtr> struct __list_node;
 204 template <class _Tp, class _VoidPtr> struct __list_node_base;
 205
 206 template <class _Tp, class _VoidPtr>
 207 struct __list_node_pointer_traits {
 208   typedef typename __rebind_pointer<_VoidPtr, __list_node<_Tp, _VoidPtr> >::type
 209         __node_pointer;
 210   typedef typename __rebind_pointer<_VoidPtr, __list_node_base<_Tp, _VoidPtr> >::type
 211         __base_pointer;
 212
 213 #if defined(_LIBCPP_ABI_LIST_REMOVE_NODE_POINTER_UB)
 214   typedef __base_pointer __link_pointer;
 215 #else
 216   typedef typename conditional<
 217           is_pointer<_VoidPtr>::value,
 218           __base_pointer,
 219           __node_pointer
 220   >::type __link_pointer;
 221 #endif
 222
 223   typedef typename conditional<
 224           is_same<__link_pointer, __node_pointer>::value,
 225           __base_pointer,
 226           __node_pointer
 227   >::type __non_link_pointer;
 228
 229   static _LIBCPP_INLINE_VISIBILITY
 230   __link_pointer __unsafe_link_pointer_cast(__link_pointer __p) {
 231       return __p;
 232   }
 233
 234   static _LIBCPP_INLINE_VISIBILITY
 235   __link_pointer __unsafe_link_pointer_cast(__non_link_pointer __p) {
 236       return static_cast<__link_pointer>(static_cast<_VoidPtr>(__p));
 237   }
 238
 239 };
 240
 241 template <class _Tp, class _VoidPtr>
 242 struct __list_node_base
 243 {
 244     typedef __list_node_pointer_traits<_Tp, _VoidPtr> _NodeTraits;
 245     typedef typename _NodeTraits::__node_pointer __node_pointer;
 246     typedef typename _NodeTraits::__base_pointer __base_pointer;
 247     typedef typename _NodeTraits::__link_pointer __link_pointer;
 248
 249     __link_pointer __prev_;
 250     __link_pointer __next_;
 251
 252     _LIBCPP_INLINE_VISIBILITY
 253     __list_node_base() : __prev_(_NodeTraits::__unsafe_link_pointer_cast(__self())),
 254                          __next_(_NodeTraits::__unsafe_link_pointer_cast(__self())) {}
 255
 256     _LIBCPP_INLINE_VISIBILITY
 257     __base_pointer __self() {
 258         return pointer_traits<__base_pointer>::pointer_to(*this);
 259     }
 260
 261     _LIBCPP_INLINE_VISIBILITY
 262     __node_pointer __as_node() {
 263         return static_cast<__node_pointer>(__self());
 264     }
 265 };
 266
 267 template <class _Tp, class _VoidPtr>
 268 struct __list_node
 269     : public __list_node_base<_Tp, _VoidPtr>
 270 {
 271     _Tp __value_;
 272
 273     typedef __list_node_base<_Tp, _VoidPtr> __base;
 274     typedef typename __base::__link_pointer __link_pointer;
 275
 276     _LIBCPP_INLINE_VISIBILITY
 277     __link_pointer __as_link() {
 278         return static_cast<__link_pointer>(__base::__self());
 279     }
 280 };
 281
 282 template <class _Tp, class _Alloc = allocator<_Tp> > class _LIBCPP_TEMPLATE_VIS list;
 283 template <class _Tp, class _Alloc> class __list_imp;
 284 template <class _Tp, class _VoidPtr> class _LIBCPP_TEMPLATE_VIS __list_const_iterator;
 285
 286 template <class _Tp, class _VoidPtr>
 287 class _LIBCPP_TEMPLATE_VIS __list_iterator
 288 {
 289     typedef __list_node_pointer_traits<_Tp, _VoidPtr> _NodeTraits;
 290     typedef typename _NodeTraits::__link_pointer __link_pointer;
 291
 292     __link_pointer __ptr_;
 293
 294 #if _LIBCPP_DEBUG_LEVEL >= 2
 295     _LIBCPP_INLINE_VISIBILITY
 296     explicit __list_iterator(__link_pointer __p, const void* __c) _NOEXCEPT
 297         : __ptr_(__p)
 298     {
 299         __get_db()->__insert_ic(this, __c);
 300     }
 301 #else
 302     _LIBCPP_INLINE_VISIBILITY
 303     explicit __list_iterator(__link_pointer __p) _NOEXCEPT : __ptr_(__p) {}
 304 #endif
 305
 306
 307
 308     template<class, class> friend class list;
 309     template<class, class> friend class __list_imp;
 310     template<class, class> friend class __list_const_iterator;
 311 public:
 312     typedef bidirectional_iterator_tag       iterator_category;
 313     typedef _Tp                              value_type;
 314     typedef value_type&                      reference;
 315     typedef typename __rebind_pointer<_VoidPtr, value_type>::type pointer;
 316     typedef typename pointer_traits<pointer>::difference_type difference_type;
 317
 318     _LIBCPP_INLINE_VISIBILITY
 319     __list_iterator() _NOEXCEPT : __ptr_(nullptr)
 320     {
 321 #if _LIBCPP_DEBUG_LEVEL >= 2
 322         __get_db()->__insert_i(this);
 323 #endif
 324     }
 325
 326 #if _LIBCPP_DEBUG_LEVEL >= 2
 327
 328     _LIBCPP_INLINE_VISIBILITY
 329     __list_iterator(const __list_iterator& __p)
 330         : __ptr_(__p.__ptr_)
 331     {
 332         __get_db()->__iterator_copy(this, &__p);
 333     }
 334
 335     _LIBCPP_INLINE_VISIBILITY
 336     ~__list_iterator()
 337     {
 338         __get_db()->__erase_i(this);
 339     }
 340
 341     _LIBCPP_INLINE_VISIBILITY
 342     __list_iterator& operator=(const __list_iterator& __p)
 343     {
 344         if (this != &__p)
 345         {
 346             __get_db()->__iterator_copy(this, &__p);
 347             __ptr_ = __p.__ptr_;
 348         }
 349         return *this;
 350     }
 351
 352 #endif  // _LIBCPP_DEBUG_LEVEL >= 2
 353
 354     _LIBCPP_INLINE_VISIBILITY
 355     reference operator*() const
 356     {
 357 #if _LIBCPP_DEBUG_LEVEL >= 2
 358         _LIBCPP_ASSERT(__get_const_db()->__dereferenceable(this),
 359                        "Attempted to dereference a non-dereferenceable list::iterator");
 360 #endif
 361         return __ptr_->__as_node()->__value_;
 362     }
 363     _LIBCPP_INLINE_VISIBILITY
 364     pointer operator->() const
 365     {
 366 #if _LIBCPP_DEBUG_LEVEL >= 2
 367         _LIBCPP_ASSERT(__get_const_db()->__dereferenceable(this),
 368                        "Attempted to dereference a non-dereferenceable list::iterator");
 369 #endif
 370         return pointer_traits<pointer>::pointer_to(__ptr_->__as_node()->__value_);
 371     }
 372
 373     _LIBCPP_INLINE_VISIBILITY
 374     __list_iterator& operator++()
 375     {
 376 #if _LIBCPP_DEBUG_LEVEL >= 2
 377         _LIBCPP_ASSERT(__get_const_db()->__dereferenceable(this),
 378                        "Attempted to increment non-incrementable list::iterator");
 379 #endif
 380         __ptr_ = __ptr_->__next_;
 381         return *this;
 382     }
 383     _LIBCPP_INLINE_VISIBILITY
 384     __list_iterator operator++(int) {__list_iterator __t(*this); ++(*this); return __t;}
 385
 386     _LIBCPP_INLINE_VISIBILITY
 387     __list_iterator& operator--()
 388     {
 389 #if _LIBCPP_DEBUG_LEVEL >= 2
 390         _LIBCPP_ASSERT(__get_const_db()->__decrementable(this),
 391                        "Attempted to decrement non-decrementable list::iterator");
 392 #endif
 393         __ptr_ = __ptr_->__prev_;
 394         return *this;
 395     }
 396     _LIBCPP_INLINE_VISIBILITY
 397     __list_iterator operator--(int) {__list_iterator __t(*this); --(*this); return __t;}
 398
 399     friend _LIBCPP_INLINE_VISIBILITY
 400     bool operator==(const __list_iterator& __x, const __list_iterator& __y)
 401     {
 402         return __x.__ptr_ == __y.__ptr_;
 403     }
 404     friend _LIBCPP_INLINE_VISIBILITY
 405      bool operator!=(const __list_iterator& __x, const __list_iterator& __y)
 406         {return !(__x == __y);}
 407 };
 408
 409 template <class _Tp, class _VoidPtr>
 410 class _LIBCPP_TEMPLATE_VIS __list_const_iterator
 411 {
 412     typedef __list_node_pointer_traits<_Tp, _VoidPtr> _NodeTraits;
 413     typedef typename _NodeTraits::__link_pointer __link_pointer;
 414
 415     __link_pointer __ptr_;
 416
 417 #if _LIBCPP_DEBUG_LEVEL >= 2
 418     _LIBCPP_INLINE_VISIBILITY
 419     explicit __list_const_iterator(__link_pointer __p, const void* __c) _NOEXCEPT
 420         : __ptr_(__p)
 421     {
 422         __get_db()->__insert_ic(this, __c);
 423     }
 424 #else
 425     _LIBCPP_INLINE_VISIBILITY
 426     explicit __list_const_iterator(__link_pointer __p) _NOEXCEPT : __ptr_(__p) {}
 427 #endif
 428
 429     template<class, class> friend class list;
 430     template<class, class> friend class __list_imp;
 431 public:
 432     typedef bidirectional_iterator_tag       iterator_category;
 433     typedef _Tp                              value_type;
 434     typedef const value_type&                reference;
 435     typedef typename __rebind_pointer<_VoidPtr, const value_type>::type pointer;
 436     typedef typename pointer_traits<pointer>::difference_type difference_type;
 437
 438     _LIBCPP_INLINE_VISIBILITY
 439     __list_const_iterator() _NOEXCEPT : __ptr_(nullptr)
 440     {
 441 #if _LIBCPP_DEBUG_LEVEL >= 2
 442         __get_db()->__insert_i(this);
 443 #endif
 444     }
 445     _LIBCPP_INLINE_VISIBILITY
 446     __list_const_iterator(const __list_iterator<_Tp, _VoidPtr>& __p) _NOEXCEPT
 447         : __ptr_(__p.__ptr_)
 448     {
 449 #if _LIBCPP_DEBUG_LEVEL >= 2
 450         __get_db()->__iterator_copy(this, &__p);
 451 #endif
 452     }
 453
 454 #if _LIBCPP_DEBUG_LEVEL >= 2
 455
 456     _LIBCPP_INLINE_VISIBILITY
 457     __list_const_iterator(const __list_const_iterator& __p)
 458         : __ptr_(__p.__ptr_)
 459     {
 460         __get_db()->__iterator_copy(this, &__p);
 461     }
 462
 463     _LIBCPP_INLINE_VISIBILITY
 464     ~__list_const_iterator()
 465     {
 466         __get_db()->__erase_i(this);
 467     }
 468
 469     _LIBCPP_INLINE_VISIBILITY
 470     __list_const_iterator& operator=(const __list_const_iterator& __p)
 471     {
 472         if (this != &__p)
 473         {
 474             __get_db()->__iterator_copy(this, &__p);
 475             __ptr_ = __p.__ptr_;
 476         }
 477         return *this;
 478     }
 479
 480 #endif  // _LIBCPP_DEBUG_LEVEL >= 2
 481     _LIBCPP_INLINE_VISIBILITY
 482     reference operator*() const
 483     {
 484 #if _LIBCPP_DEBUG_LEVEL >= 2
 485         _LIBCPP_ASSERT(__get_const_db()->__dereferenceable(this),
 486                        "Attempted to dereference a non-dereferenceable list::const_iterator");
 487 #endif
 488         return __ptr_->__as_node()->__value_;
 489     }
 490     _LIBCPP_INLINE_VISIBILITY
 491     pointer operator->() const
 492     {
 493 #if _LIBCPP_DEBUG_LEVEL >= 2
 494         _LIBCPP_ASSERT(__get_const_db()->__dereferenceable(this),
 495                        "Attempted to dereference a non-dereferenceable list::const_iterator");
 496 #endif
 497         return pointer_traits<pointer>::pointer_to(__ptr_->__as_node()->__value_);
 498     }
 499
 500     _LIBCPP_INLINE_VISIBILITY
 501     __list_const_iterator& operator++()
 502     {
 503 #if _LIBCPP_DEBUG_LEVEL >= 2
 504         _LIBCPP_ASSERT(__get_const_db()->__dereferenceable(this),
 505                        "Attempted to increment non-incrementable list::const_iterator");
 506 #endif
 507         __ptr_ = __ptr_->__next_;
 508         return *this;
 509     }
 510     _LIBCPP_INLINE_VISIBILITY
 511     __list_const_iterator operator++(int) {__list_const_iterator __t(*this); ++(*this); return __t;}
 512
 513     _LIBCPP_INLINE_VISIBILITY
 514     __list_const_iterator& operator--()
 515     {
 516 #if _LIBCPP_DEBUG_LEVEL >= 2
 517         _LIBCPP_ASSERT(__get_const_db()->__decrementable(this),
 518                        "Attempted to decrement non-decrementable list::const_iterator");
 519 #endif
 520         __ptr_ = __ptr_->__prev_;
 521         return *this;
 522     }
 523     _LIBCPP_INLINE_VISIBILITY
 524     __list_const_iterator operator--(int) {__list_const_iterator __t(*this); --(*this); return __t;}
 525
 526     friend _LIBCPP_INLINE_VISIBILITY
 527     bool operator==(const __list_const_iterator& __x, const __list_const_iterator& __y)
 528     {
 529         return __x.__ptr_ == __y.__ptr_;
 530     }
 531     friend _LIBCPP_INLINE_VISIBILITY
 532     bool operator!=(const __list_const_iterator& __x, const __list_const_iterator& __y)
 533         {return !(__x == __y);}
 534 };
 535
 536 template <class _Tp, class _Alloc>
 537 class __list_imp
 538 {
 539     __list_imp(const __list_imp&);
 540     __list_imp& operator=(const __list_imp&);
 541 public:
 542     typedef _Alloc                                                  allocator_type;
 543     typedef allocator_traits<allocator_type>                        __alloc_traits;
 544     typedef typename __alloc_traits::size_type                      size_type;
 545 protected:
 546     typedef _Tp                                                     value_type;
 547     typedef typename __alloc_traits::void_pointer                   __void_pointer;
 548     typedef __list_iterator<value_type, __void_pointer>             iterator;
 549     typedef __list_const_iterator<value_type, __void_pointer>       const_iterator;
 550     typedef __list_node_base<value_type, __void_pointer>            __node_base;
 551     typedef __list_node<value_type, __void_pointer>                 __node;
 552     typedef typename __rebind_alloc_helper<__alloc_traits, __node>::type __node_allocator;
 553     typedef allocator_traits<__node_allocator>                       __node_alloc_traits;
 554     typedef typename __node_alloc_traits::pointer                    __node_pointer;
 555     typedef typename __node_alloc_traits::pointer                    __node_const_pointer;
 556     typedef __list_node_pointer_traits<value_type, __void_pointer> __node_pointer_traits;
 557     typedef typename __node_pointer_traits::__link_pointer __link_pointer;
 558     typedef __link_pointer __link_const_pointer;
 559     typedef typename __alloc_traits::pointer                         pointer;
 560     typedef typename __alloc_traits::const_pointer                   const_pointer;
 561     typedef typename __alloc_traits::difference_type                 difference_type;
 562
 563     typedef typename __rebind_alloc_helper<__alloc_traits, __node_base>::type __node_base_allocator;
 564     typedef typename allocator_traits<__node_base_allocator>::pointer __node_base_pointer;
 565     static_assert((!is_same<allocator_type, __node_allocator>::value),
 566                   "internal allocator type must differ from user-specified "
 567                   "type; otherwise overload resolution breaks");
 568
 569     __node_base __end_;
 570     __compressed_pair<size_type, __node_allocator> __size_alloc_;
 571
 572     _LIBCPP_INLINE_VISIBILITY
 573     __link_pointer __end_as_link() const _NOEXCEPT {
 574         return __node_pointer_traits::__unsafe_link_pointer_cast(
 575                 const_cast<__node_base&>(__end_).__self());
 576     }
 577
 578     _LIBCPP_INLINE_VISIBILITY
 579           size_type& __sz() _NOEXCEPT {return __size_alloc_.first();}
 580     _LIBCPP_INLINE_VISIBILITY
 581     const size_type& __sz() const _NOEXCEPT
 582         {return __size_alloc_.first();}
 583     _LIBCPP_INLINE_VISIBILITY
 584           __node_allocator& __node_alloc() _NOEXCEPT
 585           {return __size_alloc_.second();}
 586     _LIBCPP_INLINE_VISIBILITY
 587     const __node_allocator& __node_alloc() const _NOEXCEPT
 588         {return __size_alloc_.second();}
 589
 590     _LIBCPP_INLINE_VISIBILITY
 591     size_type __node_alloc_max_size() const _NOEXCEPT {
 592         return __node_alloc_traits::max_size(__node_alloc());
 593     }
 594     _LIBCPP_INLINE_VISIBILITY
 595     static void __unlink_nodes(__link_pointer __f, __link_pointer __l) _NOEXCEPT;
 596
 597     _LIBCPP_INLINE_VISIBILITY
 598     __list_imp()
 599         _NOEXCEPT_(is_nothrow_default_constructible<__node_allocator>::value);
 600     _LIBCPP_INLINE_VISIBILITY
 601     __list_imp(const allocator_type& __a);
 602     _LIBCPP_INLINE_VISIBILITY
 603     __list_imp(const __node_allocator& __a);
 604 #ifndef _LIBCPP_CXX03_LANG
 605     __list_imp(__node_allocator&& __a) _NOEXCEPT;
 606 #endif
 607     ~__list_imp();
 608     void clear() _NOEXCEPT;
 609     _LIBCPP_INLINE_VISIBILITY
 610     bool empty() const _NOEXCEPT {return __sz() == 0;}
 611
 612     _LIBCPP_INLINE_VISIBILITY
 613     iterator begin() _NOEXCEPT
 614     {
 615 #if _LIBCPP_DEBUG_LEVEL >= 2
 616         return iterator(__end_.__next_, this);
 617 #else
 618         return iterator(__end_.__next_);
 619 #endif
 620     }
 621     _LIBCPP_INLINE_VISIBILITY
 622     const_iterator begin() const  _NOEXCEPT
 623     {
 624 #if _LIBCPP_DEBUG_LEVEL >= 2
 625         return const_iterator(__end_.__next_, this);
 626 #else
 627         return const_iterator(__end_.__next_);
 628 #endif
 629     }
 630     _LIBCPP_INLINE_VISIBILITY
 631     iterator end() _NOEXCEPT
 632     {
 633 #if _LIBCPP_DEBUG_LEVEL >= 2
 634         return iterator(__end_as_link(), this);
 635 #else
 636         return iterator(__end_as_link());
 637 #endif
 638     }
 639     _LIBCPP_INLINE_VISIBILITY
 640     const_iterator end() const _NOEXCEPT
 641     {
 642 #if _LIBCPP_DEBUG_LEVEL >= 2
 643         return const_iterator(__end_as_link(), this);
 644 #else
 645         return const_iterator(__end_as_link());
 646 #endif
 647     }
 648
 649     void swap(__list_imp& __c)
 650 #if _LIBCPP_STD_VER >= 14
 651         _NOEXCEPT_DEBUG;
 652 #else
 653         _NOEXCEPT_DEBUG_(!__alloc_traits::propagate_on_container_swap::value ||
 654                     __is_nothrow_swappable<allocator_type>::value);
 655 #endif
 656
 657     _LIBCPP_INLINE_VISIBILITY
 658     void __copy_assign_alloc(const __list_imp& __c)
 659         {__copy_assign_alloc(__c, integral_constant<bool,
 660                       __node_alloc_traits::propagate_on_container_copy_assignment::value>());}
 661
 662     _LIBCPP_INLINE_VISIBILITY
 663     void __move_assign_alloc(__list_imp& __c)
 664         _NOEXCEPT_(
 665             !__node_alloc_traits::propagate_on_container_move_assignment::value ||
 666             is_nothrow_move_assignable<__node_allocator>::value)
 667         {__move_assign_alloc(__c, integral_constant<bool,
 668                       __node_alloc_traits::propagate_on_container_move_assignment::value>());}
 669
 670 private:
 671     _LIBCPP_INLINE_VISIBILITY
 672     void __copy_assign_alloc(const __list_imp& __c, true_type)
 673         {
 674             if (__node_alloc() != __c.__node_alloc())
 675                 clear();
 676             __node_alloc() = __c.__node_alloc();
 677         }
 678
 679     _LIBCPP_INLINE_VISIBILITY
 680     void __copy_assign_alloc(const __list_imp&, false_type)
 681         {}
 682
 683     _LIBCPP_INLINE_VISIBILITY
 684     void __move_assign_alloc(__list_imp& __c, true_type)
 685         _NOEXCEPT_(is_nothrow_move_assignable<__node_allocator>::value)
 686         {
 687             __node_alloc() = _VSTD::move(__c.__node_alloc());
 688         }
 689
 690     _LIBCPP_INLINE_VISIBILITY
 691     void __move_assign_alloc(__list_imp&, false_type)
 692         _NOEXCEPT
 693         {}
 694
 695     _LIBCPP_INLINE_VISIBILITY
 696     void __invalidate_all_iterators() {
 697 #if _LIBCPP_DEBUG_LEVEL >= 2
 698       __get_db()->__invalidate_all(this);
 699 #endif
 700     }
 701 };
 702
 703 // Unlink nodes [__f, __l]
 704 template <class _Tp, class _Alloc>
 705 inline
 706 void
 707 __list_imp<_Tp, _Alloc>::__unlink_nodes(__link_pointer __f, __link_pointer __l)
 708     _NOEXCEPT
 709 {
 710     __f->__prev_->__next_ = __l->__next_;
 711     __l->__next_->__prev_ = __f->__prev_;
 712 }
 713
 714 template <class _Tp, class _Alloc>
 715 inline
 716 __list_imp<_Tp, _Alloc>::__list_imp()
 717         _NOEXCEPT_(is_nothrow_default_constructible<__node_allocator>::value)
 718     : __size_alloc_(0)
 719 {
 720 }
 721
 722 template <class _Tp, class _Alloc>
 723 inline
 724 __list_imp<_Tp, _Alloc>::__list_imp(const allocator_type& __a)
 725     : __size_alloc_(0, __node_allocator(__a))
 726 {
 727 }
 728
 729 template <class _Tp, class _Alloc>
 730 inline __list_imp<_Tp, _Alloc>::__list_imp(const __node_allocator& __a)
 731     : __size_alloc_(0, __a) {}
 732
 733 #ifndef _LIBCPP_CXX03_LANG
 734 template <class _Tp, class _Alloc>
 735 inline __list_imp<_Tp, _Alloc>::__list_imp(__node_allocator&& __a) _NOEXCEPT
 736     : __size_alloc_(0, std::move(__a)) {}
 737 #endif
 738
 739 template <class _Tp, class _Alloc>
 740 __list_imp<_Tp, _Alloc>::~__list_imp() {
 741   clear();
 742 #if _LIBCPP_DEBUG_LEVEL >= 2
 743     __get_db()->__erase_c(this);
 744 #endif
 745 }
 746
 747 template <class _Tp, class _Alloc>
 748 void
 749 __list_imp<_Tp, _Alloc>::clear() _NOEXCEPT
 750 {
 751     if (!empty())
 752     {
 753         __node_allocator& __na = __node_alloc();
 754         __link_pointer __f = __end_.__next_;
 755         __link_pointer __l = __end_as_link();
 756         __unlink_nodes(__f, __l->__prev_);
 757         __sz() = 0;
 758         while (__f != __l)
 759         {
 760             __node_pointer __np = __f->__as_node();
 761             __f = __f->__next_;
 762             __node_alloc_traits::destroy(__na, _VSTD::addressof(__np->__value_));
 763             __node_alloc_traits::deallocate(__na, __np, 1);
 764         }
 765         __invalidate_all_iterators();
 766     }
 767 }
 768
 769 template <class _Tp, class _Alloc>
 770 void
 771 __list_imp<_Tp, _Alloc>::swap(__list_imp& __c)
 772 #if _LIBCPP_STD_VER >= 14
 773         _NOEXCEPT_DEBUG
 774 #else
 775         _NOEXCEPT_DEBUG_(!__alloc_traits::propagate_on_container_swap::value ||
 776                     __is_nothrow_swappable<allocator_type>::value)
 777 #endif
 778 {
 779     _LIBCPP_ASSERT(__alloc_traits::propagate_on_container_swap::value ||
 780                    this->__node_alloc() == __c.__node_alloc(),
 781                    "list::swap: Either propagate_on_container_swap must be true"
 782                    " or the allocators must compare equal");
 783     using _VSTD::swap;
 784     __swap_allocator(__node_alloc(), __c.__node_alloc());
 785     swap(__sz(), __c.__sz());
 786     swap(__end_, __c.__end_);
 787     if (__sz() == 0)
 788         __end_.__next_ = __end_.__prev_ = __end_as_link();
 789     else
 790         __end_.__prev_->__next_ = __end_.__next_->__prev_ = __end_as_link();
 791     if (__c.__sz() == 0)
 792         __c.__end_.__next_ = __c.__end_.__prev_ = __c.__end_as_link();
 793     else
 794         __c.__end_.__prev_->__next_ = __c.__end_.__next_->__prev_ = __c.__end_as_link();
 795
 796 #if _LIBCPP_DEBUG_LEVEL >= 2
 797     __libcpp_db* __db = __get_db();
 798     __c_node* __cn1 = __db->__find_c_and_lock(this);
 799     __c_node* __cn2 = __db->__find_c(&__c);
 800     std::swap(__cn1->beg_, __cn2->beg_);
 801     std::swap(__cn1->end_, __cn2->end_);
 802     std::swap(__cn1->cap_, __cn2->cap_);
 803     for (__i_node** __p = __cn1->end_; __p != __cn1->beg_;)
 804     {
 805         --__p;
 806         const_iterator* __i = static_cast<const_iterator*>((*__p)->__i_);
 807         if (__i->__ptr_ == __c.__end_as_link())
 808         {
 809             __cn2->__add(*__p);
 810             if (--__cn1->end_ != __p)
 811                 memmove(__p, __p+1, (__cn1->end_ - __p)*sizeof(__i_node*));
 812         }
 813         else
 814             (*__p)->__c_ = __cn1;
 815     }
 816     for (__i_node** __p = __cn2->end_; __p != __cn2->beg_;)
 817     {
 818         --__p;
 819         const_iterator* __i = static_cast<const_iterator*>((*__p)->__i_);
 820         if (__i->__ptr_ == __end_as_link())
 821         {
 822             __cn1->__add(*__p);
 823             if (--__cn2->end_ != __p)
 824                 memmove(__p, __p+1, (__cn2->end_ - __p)*sizeof(__i_node*));
 825         }
 826         else
 827             (*__p)->__c_ = __cn2;
 828     }
 829     __db->unlock();
 830 #endif
 831 }
 832
 833 template <class _Tp, class _Alloc /*= allocator<_Tp>*/>
 834 class _LIBCPP_TEMPLATE_VIS list
 835     : private __list_imp<_Tp, _Alloc>
 836 {
 837     typedef __list_imp<_Tp, _Alloc> base;
 838     typedef typename base::__node              __node;
 839     typedef typename base::__node_allocator    __node_allocator;
 840     typedef typename base::__node_pointer      __node_pointer;
 841     typedef typename base::__node_alloc_traits __node_alloc_traits;
 842     typedef typename base::__node_base         __node_base;
 843     typedef typename base::__node_base_pointer __node_base_pointer;
 844     typedef typename base::__link_pointer __link_pointer;
 845
 846 public:
 847     typedef _Tp                                      value_type;
 848     typedef _Alloc                                   allocator_type;
 849     static_assert((is_same<value_type, typename allocator_type::value_type>::value),
 850                   "Invalid allocator::value_type");
 851     typedef value_type&                              reference;
 852     typedef const value_type&                        const_reference;
 853     typedef typename base::pointer                   pointer;
 854     typedef typename base::const_pointer             const_pointer;
 855     typedef typename base::size_type                 size_type;
 856     typedef typename base::difference_type           difference_type;
 857     typedef typename base::iterator                  iterator;
 858     typedef typename base::const_iterator            const_iterator;
 859     typedef _VSTD::reverse_iterator<iterator>         reverse_iterator;
 860     typedef _VSTD::reverse_iterator<const_iterator>   const_reverse_iterator;
 861
 862     _LIBCPP_INLINE_VISIBILITY
 863     list()
 864         _NOEXCEPT_(is_nothrow_default_constructible<__node_allocator>::value)
 865     {
 866 #if _LIBCPP_DEBUG_LEVEL >= 2
 867         __get_db()->__insert_c(this);
 868 #endif
 869     }
 870     _LIBCPP_INLINE_VISIBILITY
 871     explicit list(const allocator_type& __a) : base(__a)
 872     {
 873 #if _LIBCPP_DEBUG_LEVEL >= 2
 874         __get_db()->__insert_c(this);
 875 #endif
 876     }
 877     explicit list(size_type __n);
 878 #if _LIBCPP_STD_VER > 11
 879     explicit list(size_type __n, const allocator_type& __a);
 880 #endif
 881     list(size_type __n, const value_type& __x);
 882     list(size_type __n, const value_type& __x, const allocator_type& __a);
 883     template <class _InpIter>
 884         list(_InpIter __f, _InpIter __l,
 885              typename enable_if<__is_input_iterator<_InpIter>::value>::type* = 0);
 886     template <class _InpIter>
 887         list(_InpIter __f, _InpIter __l, const allocator_type& __a,
 888              typename enable_if<__is_input_iterator<_InpIter>::value>::type* = 0);
 889
 890     list(const list& __c);
 891     list(const list& __c, const allocator_type& __a);
 892     _LIBCPP_INLINE_VISIBILITY
 893     list& operator=(const list& __c);
 894 #ifndef _LIBCPP_CXX03_LANG
 895     list(initializer_list<value_type> __il);
 896     list(initializer_list<value_type> __il, const allocator_type& __a);
 897
 898     _LIBCPP_INLINE_VISIBILITY
 899     list(list&& __c)
 900         _NOEXCEPT_(is_nothrow_move_constructible<__node_allocator>::value);
 901     _LIBCPP_INLINE_VISIBILITY
 902     list(list&& __c, const allocator_type& __a);
 903     _LIBCPP_INLINE_VISIBILITY
 904     list& operator=(list&& __c)
 905         _NOEXCEPT_(
 906             __node_alloc_traits::propagate_on_container_move_assignment::value &&
 907             is_nothrow_move_assignable<__node_allocator>::value);
 908
 909     _LIBCPP_INLINE_VISIBILITY
 910     list& operator=(initializer_list<value_type> __il)
 911         {assign(__il.begin(), __il.end()); return *this;}
 912
 913     _LIBCPP_INLINE_VISIBILITY
 914     void assign(initializer_list<value_type> __il)
 915         {assign(__il.begin(), __il.end());}
 916 #endif  // _LIBCPP_CXX03_LANG
 917
 918     template <class _InpIter>
 919         void assign(_InpIter __f, _InpIter __l,
 920              typename enable_if<__is_input_iterator<_InpIter>::value>::type* = 0);
 921     void assign(size_type __n, const value_type& __x);
 922
 923     _LIBCPP_INLINE_VISIBILITY
 924     allocator_type get_allocator() const _NOEXCEPT;
 925
 926     _LIBCPP_INLINE_VISIBILITY
 927     size_type size() const _NOEXCEPT     {return base::__sz();}
 928     _LIBCPP_NODISCARD_AFTER_CXX17 _LIBCPP_INLINE_VISIBILITY
 929     bool empty() const _NOEXCEPT         {return base::empty();}
 930     _LIBCPP_INLINE_VISIBILITY
 931     size_type max_size() const _NOEXCEPT
 932         {
 933             return std::min<size_type>(
 934                 base::__node_alloc_max_size(),
 935                 numeric_limits<difference_type >::max());
 936         }
 937
 938     _LIBCPP_INLINE_VISIBILITY
 939           iterator begin() _NOEXCEPT        {return base::begin();}
 940     _LIBCPP_INLINE_VISIBILITY
 941     const_iterator begin()  const _NOEXCEPT {return base::begin();}
 942     _LIBCPP_INLINE_VISIBILITY
 943           iterator end() _NOEXCEPT          {return base::end();}
 944     _LIBCPP_INLINE_VISIBILITY
 945     const_iterator end()    const _NOEXCEPT {return base::end();}
 946     _LIBCPP_INLINE_VISIBILITY
 947     const_iterator cbegin() const _NOEXCEPT {return base::begin();}
 948     _LIBCPP_INLINE_VISIBILITY
 949     const_iterator cend()   const _NOEXCEPT {return base::end();}
 950
 951     _LIBCPP_INLINE_VISIBILITY
 952           reverse_iterator rbegin() _NOEXCEPT
 953             {return       reverse_iterator(end());}
 954     _LIBCPP_INLINE_VISIBILITY
 955     const_reverse_iterator rbegin()  const _NOEXCEPT
 956         {return const_reverse_iterator(end());}
 957     _LIBCPP_INLINE_VISIBILITY
 958           reverse_iterator rend() _NOEXCEPT
 959             {return       reverse_iterator(begin());}
 960     _LIBCPP_INLINE_VISIBILITY
 961     const_reverse_iterator rend()    const _NOEXCEPT
 962         {return const_reverse_iterator(begin());}
 963     _LIBCPP_INLINE_VISIBILITY
 964     const_reverse_iterator crbegin() const _NOEXCEPT
 965         {return const_reverse_iterator(end());}
 966     _LIBCPP_INLINE_VISIBILITY
 967     const_reverse_iterator crend()   const _NOEXCEPT
 968         {return const_reverse_iterator(begin());}
 969
 970     _LIBCPP_INLINE_VISIBILITY
 971     reference front()
 972     {
 973         _LIBCPP_ASSERT(!empty(), "list::front called on empty list");
 974         return base::__end_.__next_->__as_node()->__value_;
 975     }
 976     _LIBCPP_INLINE_VISIBILITY
 977     const_reference front() const
 978     {
 979         _LIBCPP_ASSERT(!empty(), "list::front called on empty list");
 980         return base::__end_.__next_->__as_node()->__value_;
 981     }
 982     _LIBCPP_INLINE_VISIBILITY
 983     reference back()
 984     {
 985         _LIBCPP_ASSERT(!empty(), "list::back called on empty list");
 986         return base::__end_.__prev_->__as_node()->__value_;
 987     }
 988     _LIBCPP_INLINE_VISIBILITY
 989     const_reference back() const
 990     {
 991         _LIBCPP_ASSERT(!empty(), "list::back called on empty list");
 992         return base::__end_.__prev_->__as_node()->__value_;
 993     }
 994
 995 #ifndef _LIBCPP_CXX03_LANG
 996     void push_front(value_type&& __x);
 997     void push_back(value_type&& __x);
 998
 999     template <class... _Args>
1000 #if _LIBCPP_STD_VER > 14
1001        reference emplace_front(_Args&&... __args);
1002 #else
1003        void      emplace_front(_Args&&... __args);
1004 #endif
1005     template <class... _Args>
1006 #if _LIBCPP_STD_VER > 14
1007         reference emplace_back(_Args&&... __args);
1008 #else
1009        void       emplace_back(_Args&&... __args);
1010 #endif
1011     template <class... _Args>
1012         iterator emplace(const_iterator __p, _Args&&... __args);
1013
1014     iterator insert(const_iterator __p, value_type&& __x);
1015
1016     _LIBCPP_INLINE_VISIBILITY
1017     iterator insert(const_iterator __p, initializer_list<value_type> __il)
1018         {return insert(__p, __il.begin(), __il.end());}
1019 #endif  // _LIBCPP_CXX03_LANG
1020
1021     void push_front(const value_type& __x);
1022     void push_back(const value_type& __x);
1023
1024 #ifndef _LIBCPP_CXX03_LANG
1025     template <class _Arg>
1026     _LIBCPP_INLINE_VISIBILITY
1027     void __emplace_back(_Arg&& __arg) { emplace_back(_VSTD::forward<_Arg>(__arg)); }
1028 #else
1029     _LIBCPP_INLINE_VISIBILITY
1030     void __emplace_back(value_type const& __arg) { push_back(__arg); }
1031 #endif
1032
1033     iterator insert(const_iterator __p, const value_type& __x);
1034     iterator insert(const_iterator __p, size_type __n, const value_type& __x);
1035     template <class _InpIter>
1036         iterator insert(const_iterator __p, _InpIter __f, _InpIter __l,
1037              typename enable_if<__is_input_iterator<_InpIter>::value>::type* = 0);
1038
1039     _LIBCPP_INLINE_VISIBILITY
1040     void swap(list& __c)
1041 #if _LIBCPP_STD_VER >= 14
1042         _NOEXCEPT_DEBUG
1043 #else
1044         _NOEXCEPT_DEBUG_(!__node_alloc_traits::propagate_on_container_swap::value ||
1045                    __is_nothrow_swappable<__node_allocator>::value)
1046 #endif
1047         {base::swap(__c);}
1048     _LIBCPP_INLINE_VISIBILITY
1049     void clear() _NOEXCEPT {base::clear();}
1050
1051     void pop_front();
1052     void pop_back();
1053
1054     iterator erase(const_iterator __p);
1055     iterator erase(const_iterator __f, const_iterator __l);
1056
1057     void resize(size_type __n);
1058     void resize(size_type __n, const value_type& __x);
1059
1060     void splice(const_iterator __p, list& __c);
1061 #ifndef _LIBCPP_CXX03_LANG
1062     _LIBCPP_INLINE_VISIBILITY
1063     void splice(const_iterator __p, list&& __c) {splice(__p, __c);}
1064     _LIBCPP_INLINE_VISIBILITY
1065     void splice(const_iterator __p, list&& __c, const_iterator __i)
1066         {splice(__p, __c, __i);}
1067     _LIBCPP_INLINE_VISIBILITY
1068     void splice(const_iterator __p, list&& __c, const_iterator __f, const_iterator __l)
1069         {splice(__p, __c, __f, __l);}
1070 #endif
1071     void splice(const_iterator __p, list& __c, const_iterator __i);
1072     void splice(const_iterator __p, list& __c, const_iterator __f, const_iterator __l);
1073
1074     void remove(const value_type& __x);
1075     template <class _Pred> void remove_if(_Pred __pred);
1076     _LIBCPP_INLINE_VISIBILITY
1077     void unique();
1078     template <class _BinaryPred>
1079         void unique(_BinaryPred __binary_pred);
1080     _LIBCPP_INLINE_VISIBILITY
1081     void merge(list& __c);
1082 #ifndef _LIBCPP_CXX03_LANG
1083     _LIBCPP_INLINE_VISIBILITY
1084     void merge(list&& __c) {merge(__c);}
1085
1086     template <class _Comp>
1087     _LIBCPP_INLINE_VISIBILITY
1088         void merge(list&& __c, _Comp __comp) {merge(__c, __comp);}
1089 #endif
1090     template <class _Comp>
1091         void merge(list& __c, _Comp __comp);
1092
1093     _LIBCPP_INLINE_VISIBILITY
1094     void sort();
1095     template <class _Comp>
1096         _LIBCPP_INLINE_VISIBILITY
1097         void sort(_Comp __comp);
1098
1099     void reverse() _NOEXCEPT;
1100
1101     bool __invariants() const;
1102
1103     typedef __allocator_destructor<__node_allocator> __node_destructor;
1104     typedef unique_ptr<__node, __node_destructor> __hold_pointer;
1105
1106     _LIBCPP_INLINE_VISIBILITY
1107     __hold_pointer __allocate_node(__node_allocator& __na) {
1108       __node_pointer __p = __node_alloc_traits::allocate(__na, 1);
1109       __p->__prev_ = nullptr;
1110       return __hold_pointer(__p, __node_destructor(__na, 1));
1111     }
1112
1113 #if _LIBCPP_DEBUG_LEVEL >= 2
1114
1115     bool __dereferenceable(const const_iterator* __i) const;
1116     bool __decrementable(const const_iterator* __i) const;
1117     bool __addable(const const_iterator* __i, ptrdiff_t __n) const;
1118     bool __subscriptable(const const_iterator* __i, ptrdiff_t __n) const;
1119
1120 #endif  // _LIBCPP_DEBUG_LEVEL >= 2
1121
1122 private:
1123     _LIBCPP_INLINE_VISIBILITY
1124     static void __link_nodes  (__link_pointer __p, __link_pointer __f, __link_pointer __l);
1125     _LIBCPP_INLINE_VISIBILITY
1126     void __link_nodes_at_front(__link_pointer __f, __link_pointer __l);
1127     _LIBCPP_INLINE_VISIBILITY
1128     void __link_nodes_at_back (__link_pointer __f, __link_pointer __l);
1129     iterator __iterator(size_type __n);
1130     template <class _Comp>
1131         static iterator __sort(iterator __f1, iterator __e2, size_type __n, _Comp& __comp);
1132
1133     void __move_assign(list& __c, true_type)
1134         _NOEXCEPT_(is_nothrow_move_assignable<__node_allocator>::value);
1135     void __move_assign(list& __c, false_type);
1136 };
1137
1138 #ifndef _LIBCPP_HAS_NO_DEDUCTION_GUIDES
1139 template<class _InputIterator,
1140          class _Alloc = typename std::allocator<typename iterator_traits<_InputIterator>::value_type>,
1141          class = typename enable_if<__is_allocator<_Alloc>::value, void>::type
1142          >
1143 list(_InputIterator, _InputIterator)
1144   -> list<typename iterator_traits<_InputIterator>::value_type, _Alloc>;
1145
1146 template<class _InputIterator,
1147          class _Alloc,
1148          class = typename enable_if<__is_allocator<_Alloc>::value, void>::type
1149          >
1150 list(_InputIterator, _InputIterator, _Alloc)
1151   -> list<typename iterator_traits<_InputIterator>::value_type, _Alloc>;
1152 #endif
1153
1154 // Link in nodes [__f, __l] just prior to __p
1155 template <class _Tp, class _Alloc>
1156 inline
1157 void
1158 list<_Tp, _Alloc>::__link_nodes(__link_pointer __p, __link_pointer __f, __link_pointer __l)
1159 {
1160     __p->__prev_->__next_ = __f;
1161     __f->__prev_ = __p->__prev_;
1162     __p->__prev_ = __l;
1163     __l->__next_ = __p;
1164 }
1165
1166 // Link in nodes [__f, __l] at the front of the list
1167 template <class _Tp, class _Alloc>
1168 inline
1169 void
1170 list<_Tp, _Alloc>::__link_nodes_at_front(__link_pointer __f, __link_pointer __l)
1171 {
1172     __f->__prev_ = base::__end_as_link();
1173     __l->__next_ = base::__end_.__next_;
1174     __l->__next_->__prev_ = __l;
1175     base::__end_.__next_ = __f;
1176 }
1177
1178 // Link in nodes [__f, __l] at the back of the list
1179 template <class _Tp, class _Alloc>
1180 inline
1181 void
1182 list<_Tp, _Alloc>::__link_nodes_at_back(__link_pointer __f, __link_pointer __l)
1183 {
1184     __l->__next_ = base::__end_as_link();
1185     __f->__prev_ = base::__end_.__prev_;
1186     __f->__prev_->__next_ = __f;
1187     base::__end_.__prev_ = __l;
1188 }
1189
1190
1191 template <class _Tp, class _Alloc>
1192 inline
1193 typename list<_Tp, _Alloc>::iterator
1194 list<_Tp, _Alloc>::__iterator(size_type __n)
1195 {
1196     return __n <= base::__sz() / 2 ? _VSTD::next(begin(), __n)
1197                                    : _VSTD::prev(end(), base::__sz() - __n);
1198 }
1199
1200 template <class _Tp, class _Alloc>
1201 list<_Tp, _Alloc>::list(size_type __n)
1202 {
1203 #if _LIBCPP_DEBUG_LEVEL >= 2
1204     __get_db()->__insert_c(this);
1205 #endif
1206     for (; __n > 0; --__n)
1207 #ifndef _LIBCPP_CXX03_LANG
1208         emplace_back();
1209 #else
1210         push_back(value_type());
1211 #endif
1212 }
1213
1214 #if _LIBCPP_STD_VER > 11
1215 template <class _Tp, class _Alloc>
1216 list<_Tp, _Alloc>::list(size_type __n, const allocator_type& __a) : base(__a)
1217 {
1218 #if _LIBCPP_DEBUG_LEVEL >= 2
1219     __get_db()->__insert_c(this);
1220 #endif
1221     for (; __n > 0; --__n)
1222         emplace_back();
1223 }
1224 #endif
1225
1226 template <class _Tp, class _Alloc>
1227 list<_Tp, _Alloc>::list(size_type __n, const value_type& __x)
1228 {
1229 #if _LIBCPP_DEBUG_LEVEL >= 2
1230     __get_db()->__insert_c(this);
1231 #endif
1232     for (; __n > 0; --__n)
1233         push_back(__x);
1234 }
1235
1236 template <class _Tp, class _Alloc>
1237 list<_Tp, _Alloc>::list(size_type __n, const value_type& __x, const allocator_type& __a)
1238     : base(__a)
1239 {
1240 #if _LIBCPP_DEBUG_LEVEL >= 2
1241     __get_db()->__insert_c(this);
1242 #endif
1243     for (; __n > 0; --__n)
1244         push_back(__x);
1245 }
1246
1247 template <class _Tp, class _Alloc>
1248 template <class _InpIter>
1249 list<_Tp, _Alloc>::list(_InpIter __f, _InpIter __l,
1250                         typename enable_if<__is_input_iterator<_InpIter>::value>::type*)
1251 {
1252 #if _LIBCPP_DEBUG_LEVEL >= 2
1253     __get_db()->__insert_c(this);
1254 #endif
1255     for (; __f != __l; ++__f)
1256         __emplace_back(*__f);
1257 }
1258
1259 template <class _Tp, class _Alloc>
1260 template <class _InpIter>
1261 list<_Tp, _Alloc>::list(_InpIter __f, _InpIter __l, const allocator_type& __a,
1262                         typename enable_if<__is_input_iterator<_InpIter>::value>::type*)
1263     : base(__a)
1264 {
1265 #if _LIBCPP_DEBUG_LEVEL >= 2
1266     __get_db()->__insert_c(this);
1267 #endif
1268     for (; __f != __l; ++__f)
1269         __emplace_back(*__f);
1270 }
1271
1272 template <class _Tp, class _Alloc>
1273 list<_Tp, _Alloc>::list(const list& __c)
1274     : base(__node_alloc_traits::select_on_container_copy_construction(
1275           __c.__node_alloc())) {
1276 #if _LIBCPP_DEBUG_LEVEL >= 2
1277     __get_db()->__insert_c(this);
1278 #endif
1279     for (const_iterator __i = __c.begin(), __e = __c.end(); __i != __e; ++__i)
1280         push_back(*__i);
1281 }
1282
1283 template <class _Tp, class _Alloc>
1284 list<_Tp, _Alloc>::list(const list& __c, const allocator_type& __a)
1285     : base(__a)
1286 {
1287 #if _LIBCPP_DEBUG_LEVEL >= 2
1288     __get_db()->__insert_c(this);
1289 #endif
1290     for (const_iterator __i = __c.begin(), __e = __c.end(); __i != __e; ++__i)
1291         push_back(*__i);
1292 }
1293
1294 #ifndef _LIBCPP_CXX03_LANG
1295
1296 template <class _Tp, class _Alloc>
1297 list<_Tp, _Alloc>::list(initializer_list<value_type> __il, const allocator_type& __a)
1298     : base(__a)
1299 {
1300 #if _LIBCPP_DEBUG_LEVEL >= 2
1301     __get_db()->__insert_c(this);
1302 #endif
1303     for (typename initializer_list<value_type>::const_iterator __i = __il.begin(),
1304             __e = __il.end(); __i != __e; ++__i)
1305         push_back(*__i);
1306 }
1307
1308 template <class _Tp, class _Alloc>
1309 list<_Tp, _Alloc>::list(initializer_list<value_type> __il)
1310 {
1311 #if _LIBCPP_DEBUG_LEVEL >= 2
1312     __get_db()->__insert_c(this);
1313 #endif
1314     for (typename initializer_list<value_type>::const_iterator __i = __il.begin(),
1315             __e = __il.end(); __i != __e; ++__i)
1316         push_back(*__i);
1317 }
1318
1319 template <class _Tp, class _Alloc>
1320 inline list<_Tp, _Alloc>::list(list&& __c)
1321     _NOEXCEPT_(is_nothrow_move_constructible<__node_allocator>::value)
1322     : base(_VSTD::move(__c.__node_alloc())) {
1323 #if _LIBCPP_DEBUG_LEVEL >= 2
1324     __get_db()->__insert_c(this);
1325 #endif
1326     splice(end(), __c);
1327 }
1328
1329 template <class _Tp, class _Alloc>
1330 inline
1331 list<_Tp, _Alloc>::list(list&& __c, const allocator_type& __a)
1332     : base(__a)
1333 {
1334 #if _LIBCPP_DEBUG_LEVEL >= 2
1335     __get_db()->__insert_c(this);
1336 #endif
1337     if (__a == __c.get_allocator())
1338         splice(end(), __c);
1339     else
1340     {
1341         typedef move_iterator<iterator> _Ip;
1342         assign(_Ip(__c.begin()), _Ip(__c.end()));
1343     }
1344 }
1345
1346 template <class _Tp, class _Alloc>
1347 inline
1348 list<_Tp, _Alloc>&
1349 list<_Tp, _Alloc>::operator=(list&& __c)
1350         _NOEXCEPT_(
1351             __node_alloc_traits::propagate_on_container_move_assignment::value &&
1352             is_nothrow_move_assignable<__node_allocator>::value)
1353 {
1354     __move_assign(__c, integral_constant<bool,
1355           __node_alloc_traits::propagate_on_container_move_assignment::value>());
1356     return *this;
1357 }
1358
1359 template <class _Tp, class _Alloc>
1360 void
1361 list<_Tp, _Alloc>::__move_assign(list& __c, false_type)
1362 {
1363     if (base::__node_alloc() != __c.__node_alloc())
1364     {
1365         typedef move_iterator<iterator> _Ip;
1366         assign(_Ip(__c.begin()), _Ip(__c.end()));
1367     }
1368     else
1369         __move_assign(__c, true_type());
1370 }
1371
1372 template <class _Tp, class _Alloc>
1373 void
1374 list<_Tp, _Alloc>::__move_assign(list& __c, true_type)
1375         _NOEXCEPT_(is_nothrow_move_assignable<__node_allocator>::value)
1376 {
1377     clear();
1378     base::__move_assign_alloc(__c);
1379     splice(end(), __c);
1380 }
1381
1382 #endif  // _LIBCPP_CXX03_LANG
1383
1384 template <class _Tp, class _Alloc>
1385 inline
1386 list<_Tp, _Alloc>&
1387 list<_Tp, _Alloc>::operator=(const list& __c)
1388 {
1389     if (this != &__c)
1390     {
1391         base::__copy_assign_alloc(__c);
1392         assign(__c.begin(), __c.end());
1393     }
1394     return *this;
1395 }
1396
1397 template <class _Tp, class _Alloc>
1398 template <class _InpIter>
1399 void
1400 list<_Tp, _Alloc>::assign(_InpIter __f, _InpIter __l,
1401                           typename enable_if<__is_input_iterator<_InpIter>::value>::type*)
1402 {
1403     iterator __i = begin();
1404     iterator __e = end();
1405     for (; __f != __l && __i != __e; ++__f, ++__i)
1406         *__i = *__f;
1407     if (__i == __e)
1408         insert(__e, __f, __l);
1409     else
1410         erase(__i, __e);
1411 #if _LIBCPP_DEBUG_LEVEL >= 2
1412       __get_db()->__invalidate_all(this);
1413 #endif
1414 }
1415
1416 template <class _Tp, class _Alloc>
1417 void
1418 list<_Tp, _Alloc>::assign(size_type __n, const value_type& __x)
1419 {
1420     iterator __i = begin();
1421     iterator __e = end();
1422     for (; __n > 0 && __i != __e; --__n, ++__i)
1423         *__i = __x;
1424     if (__i == __e)
1425         insert(__e, __n, __x);
1426     else
1427         erase(__i, __e);
1428 #if _LIBCPP_DEBUG_LEVEL >= 2
1429       __get_db()->__invalidate_all(this);
1430 #endif
1431 }
1432
1433 template <class _Tp, class _Alloc>
1434 inline
1435 _Alloc
1436 list<_Tp, _Alloc>::get_allocator() const _NOEXCEPT
1437 {
1438     return allocator_type(base::__node_alloc());
1439 }
1440
1441 template <class _Tp, class _Alloc>
1442 typename list<_Tp, _Alloc>::iterator
1443 list<_Tp, _Alloc>::insert(const_iterator __p, const value_type& __x)
1444 {
1445 #if _LIBCPP_DEBUG_LEVEL >= 2
1446     _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__p) == this,
1447         "list::insert(iterator, x) called with an iterator not"
1448         " referring to this list");
1449 #endif
1450     __node_allocator& __na = base::__node_alloc();
1451     __hold_pointer __hold = __allocate_node(__na);
1452     __node_alloc_traits::construct(__na, _VSTD::addressof(__hold->__value_), __x);
1453     __link_nodes(__p.__ptr_, __hold->__as_link(), __hold->__as_link());
1454     ++base::__sz();
1455 #if _LIBCPP_DEBUG_LEVEL >= 2
1456     return iterator(__hold.release()->__as_link(), this);
1457 #else
1458     return iterator(__hold.release()->__as_link());
1459 #endif
1460 }
1461
1462 template <class _Tp, class _Alloc>
1463 typename list<_Tp, _Alloc>::iterator
1464 list<_Tp, _Alloc>::insert(const_iterator __p, size_type __n, const value_type& __x)
1465 {
1466 #if _LIBCPP_DEBUG_LEVEL >= 2
1467     _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__p) == this,
1468         "list::insert(iterator, n, x) called with an iterator not"
1469         " referring to this list");
1470     iterator __r(__p.__ptr_, this);
1471 #else
1472     iterator __r(__p.__ptr_);
1473 #endif
1474     if (__n > 0)
1475     {
1476         size_type __ds = 0;
1477         __node_allocator& __na = base::__node_alloc();
1478         __hold_pointer __hold = __allocate_node(__na);
1479         __node_alloc_traits::construct(__na, _VSTD::addressof(__hold->__value_), __x);
1480         ++__ds;
1481 #if _LIBCPP_DEBUG_LEVEL >= 2
1482         __r = iterator(__hold->__as_link(), this);
1483 #else
1484         __r = iterator(__hold->__as_link());
1485 #endif
1486         __hold.release();
1487         iterator __e = __r;
1488 #ifndef _LIBCPP_NO_EXCEPTIONS
1489         try
1490         {
1491 #endif  // _LIBCPP_NO_EXCEPTIONS
1492             for (--__n; __n != 0; --__n, ++__e, ++__ds)
1493             {
1494                 __hold.reset(__node_alloc_traits::allocate(__na, 1));
1495                 __node_alloc_traits::construct(__na, _VSTD::addressof(__hold->__value_), __x);
1496                 __e.__ptr_->__next_ = __hold->__as_link();
1497                 __hold->__prev_ = __e.__ptr_;
1498                 __hold.release();
1499             }
1500 #ifndef _LIBCPP_NO_EXCEPTIONS
1501         }
1502         catch (...)
1503         {
1504             while (true)
1505             {
1506                 __node_alloc_traits::destroy(__na, _VSTD::addressof(*__e));
1507                 __link_pointer __prev = __e.__ptr_->__prev_;
1508                 __node_alloc_traits::deallocate(__na, __e.__ptr_->__as_node(), 1);
1509                 if (__prev == 0)
1510                     break;
1511 #if _LIBCPP_DEBUG_LEVEL >= 2
1512                 __e = iterator(__prev, this);
1513 #else
1514                 __e = iterator(__prev);
1515 #endif
1516             }
1517             throw;
1518         }
1519 #endif  // _LIBCPP_NO_EXCEPTIONS
1520         __link_nodes(__p.__ptr_, __r.__ptr_, __e.__ptr_);
1521         base::__sz() += __ds;
1522     }
1523     return __r;
1524 }
1525
1526 template <class _Tp, class _Alloc>
1527 template <class _InpIter>
1528 typename list<_Tp, _Alloc>::iterator
1529 list<_Tp, _Alloc>::insert(const_iterator __p, _InpIter __f, _InpIter __l,
1530              typename enable_if<__is_input_iterator<_InpIter>::value>::type*)
1531 {
1532 #if _LIBCPP_DEBUG_LEVEL >= 2
1533     _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__p) == this,
1534         "list::insert(iterator, range) called with an iterator not"
1535         " referring to this list");
1536     iterator __r(__p.__ptr_, this);
1537 #else
1538     iterator __r(__p.__ptr_);
1539 #endif
1540     if (__f != __l)
1541     {
1542         size_type __ds = 0;
1543         __node_allocator& __na = base::__node_alloc();
1544         __hold_pointer __hold = __allocate_node(__na);
1545         __node_alloc_traits::construct(__na, _VSTD::addressof(__hold->__value_), *__f);
1546         ++__ds;
1547 #if _LIBCPP_DEBUG_LEVEL >= 2
1548         __r = iterator(__hold.get()->__as_link(), this);
1549 #else
1550         __r = iterator(__hold.get()->__as_link());
1551 #endif
1552         __hold.release();
1553         iterator __e = __r;
1554 #ifndef _LIBCPP_NO_EXCEPTIONS
1555         try
1556         {
1557 #endif  // _LIBCPP_NO_EXCEPTIONS
1558             for (++__f; __f != __l; ++__f, (void) ++__e, (void) ++__ds)
1559             {
1560                 __hold.reset(__node_alloc_traits::allocate(__na, 1));
1561                 __node_alloc_traits::construct(__na, _VSTD::addressof(__hold->__value_), *__f);
1562                 __e.__ptr_->__next_ = __hold.get()->__as_link();
1563                 __hold->__prev_ = __e.__ptr_;
1564                 __hold.release();
1565             }
1566 #ifndef _LIBCPP_NO_EXCEPTIONS
1567         }
1568         catch (...)
1569         {
1570             while (true)
1571             {
1572                 __node_alloc_traits::destroy(__na, _VSTD::addressof(*__e));
1573                 __link_pointer __prev = __e.__ptr_->__prev_;
1574                 __node_alloc_traits::deallocate(__na, __e.__ptr_->__as_node(), 1);
1575                 if (__prev == 0)
1576                     break;
1577 #if _LIBCPP_DEBUG_LEVEL >= 2
1578                 __e = iterator(__prev, this);
1579 #else
1580                 __e = iterator(__prev);
1581 #endif
1582             }
1583             throw;
1584         }
1585 #endif  // _LIBCPP_NO_EXCEPTIONS
1586         __link_nodes(__p.__ptr_, __r.__ptr_, __e.__ptr_);
1587         base::__sz() += __ds;
1588     }
1589     return __r;
1590 }
1591
1592 template <class _Tp, class _Alloc>
1593 void
1594 list<_Tp, _Alloc>::push_front(const value_type& __x)
1595 {
1596     __node_allocator& __na = base::__node_alloc();
1597     __hold_pointer __hold = __allocate_node(__na);
1598     __node_alloc_traits::construct(__na, _VSTD::addressof(__hold->__value_), __x);
1599     __link_pointer __nl = __hold->__as_link();
1600     __link_nodes_at_front(__nl, __nl);
1601     ++base::__sz();
1602     __hold.release();
1603 }
1604
1605 template <class _Tp, class _Alloc>
1606 void
1607 list<_Tp, _Alloc>::push_back(const value_type& __x)
1608 {
1609     __node_allocator& __na = base::__node_alloc();
1610     __hold_pointer __hold = __allocate_node(__na);
1611     __node_alloc_traits::construct(__na, _VSTD::addressof(__hold->__value_), __x);
1612     __link_nodes_at_back(__hold.get()->__as_link(), __hold.get()->__as_link());
1613     ++base::__sz();
1614     __hold.release();
1615 }
1616
1617 #ifndef _LIBCPP_CXX03_LANG
1618
1619 template <class _Tp, class _Alloc>
1620 void
1621 list<_Tp, _Alloc>::push_front(value_type&& __x)
1622 {
1623     __node_allocator& __na = base::__node_alloc();
1624     __hold_pointer __hold = __allocate_node(__na);
1625     __node_alloc_traits::construct(__na, _VSTD::addressof(__hold->__value_), _VSTD::move(__x));
1626     __link_nodes_at_front(__hold.get()->__as_link(), __hold.get()->__as_link());
1627     ++base::__sz();
1628     __hold.release();
1629 }
1630
1631 template <class _Tp, class _Alloc>
1632 void
1633 list<_Tp, _Alloc>::push_back(value_type&& __x)
1634 {
1635     __node_allocator& __na = base::__node_alloc();
1636     __hold_pointer __hold = __allocate_node(__na);
1637     __node_alloc_traits::construct(__na, _VSTD::addressof(__hold->__value_), _VSTD::move(__x));
1638     __link_nodes_at_back(__hold.get()->__as_link(), __hold.get()->__as_link());
1639     ++base::__sz();
1640     __hold.release();
1641 }
1642
1643 template <class _Tp, class _Alloc>
1644 template <class... _Args>
1645 #if _LIBCPP_STD_VER > 14
1646 typename list<_Tp, _Alloc>::reference
1647 #else
1648 void
1649 #endif
1650 list<_Tp, _Alloc>::emplace_front(_Args&&... __args)
1651 {
1652     __node_allocator& __na = base::__node_alloc();
1653     __hold_pointer __hold = __allocate_node(__na);
1654     __node_alloc_traits::construct(__na, _VSTD::addressof(__hold->__value_), _VSTD::forward<_Args>(__args)...);
1655     __link_nodes_at_front(__hold.get()->__as_link(), __hold.get()->__as_link());
1656     ++base::__sz();
1657 #if _LIBCPP_STD_VER > 14
1658     return __hold.release()->__value_;
1659 #else
1660     __hold.release();
1661 #endif
1662 }
1663
1664 template <class _Tp, class _Alloc>
1665 template <class... _Args>
1666 #if _LIBCPP_STD_VER > 14
1667 typename list<_Tp, _Alloc>::reference
1668 #else
1669 void
1670 #endif
1671 list<_Tp, _Alloc>::emplace_back(_Args&&... __args)
1672 {
1673     __node_allocator& __na = base::__node_alloc();
1674     __hold_pointer __hold = __allocate_node(__na);
1675     __node_alloc_traits::construct(__na, _VSTD::addressof(__hold->__value_), _VSTD::forward<_Args>(__args)...);
1676     __link_pointer __nl = __hold->__as_link();
1677     __link_nodes_at_back(__nl, __nl);
1678     ++base::__sz();
1679 #if _LIBCPP_STD_VER > 14
1680     return __hold.release()->__value_;
1681 #else
1682     __hold.release();
1683 #endif
1684 }
1685
1686 template <class _Tp, class _Alloc>
1687 template <class... _Args>
1688 typename list<_Tp, _Alloc>::iterator
1689 list<_Tp, _Alloc>::emplace(const_iterator __p, _Args&&... __args)
1690 {
1691 #if _LIBCPP_DEBUG_LEVEL >= 2
1692     _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__p) == this,
1693         "list::emplace(iterator, args...) called with an iterator not"
1694         " referring to this list");
1695 #endif
1696     __node_allocator& __na = base::__node_alloc();
1697     __hold_pointer __hold = __allocate_node(__na);
1698     __node_alloc_traits::construct(__na, _VSTD::addressof(__hold->__value_), _VSTD::forward<_Args>(__args)...);
1699     __link_pointer __nl = __hold.get()->__as_link();
1700     __link_nodes(__p.__ptr_, __nl, __nl);
1701     ++base::__sz();
1702     __hold.release();
1703 #if _LIBCPP_DEBUG_LEVEL >= 2
1704     return iterator(__nl, this);
1705 #else
1706     return iterator(__nl);
1707 #endif
1708 }
1709
1710 template <class _Tp, class _Alloc>
1711 typename list<_Tp, _Alloc>::iterator
1712 list<_Tp, _Alloc>::insert(const_iterator __p, value_type&& __x)
1713 {
1714 #if _LIBCPP_DEBUG_LEVEL >= 2
1715     _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__p) == this,
1716         "list::insert(iterator, x) called with an iterator not"
1717         " referring to this list");
1718 #endif
1719     __node_allocator& __na = base::__node_alloc();
1720     __hold_pointer __hold = __allocate_node(__na);
1721     __node_alloc_traits::construct(__na, _VSTD::addressof(__hold->__value_), _VSTD::move(__x));
1722     __link_pointer __nl = __hold->__as_link();
1723     __link_nodes(__p.__ptr_, __nl, __nl);
1724     ++base::__sz();
1725     __hold.release();
1726 #if _LIBCPP_DEBUG_LEVEL >= 2
1727     return iterator(__nl, this);
1728 #else
1729     return iterator(__nl);
1730 #endif
1731 }
1732
1733 #endif  // _LIBCPP_CXX03_LANG
1734
1735 template <class _Tp, class _Alloc>
1736 void
1737 list<_Tp, _Alloc>::pop_front()
1738 {
1739     _LIBCPP_ASSERT(!empty(), "list::pop_front() called with empty list");
1740     __node_allocator& __na = base::__node_alloc();
1741     __link_pointer __n = base::__end_.__next_;
1742     base::__unlink_nodes(__n, __n);
1743     --base::__sz();
1744 #if _LIBCPP_DEBUG_LEVEL >= 2
1745     __c_node* __c = __get_db()->__find_c_and_lock(this);
1746     for (__i_node** __p = __c->end_; __p != __c->beg_; )
1747     {
1748         --__p;
1749         iterator* __i = static_cast<iterator*>((*__p)->__i_);
1750         if (__i->__ptr_ == __n)
1751         {
1752             (*__p)->__c_ = nullptr;
1753             if (--__c->end_ != __p)
1754                 memmove(__p, __p+1, (__c->end_ - __p)*sizeof(__i_node*));
1755         }
1756     }
1757     __get_db()->unlock();
1758 #endif
1759     __node_pointer __np = __n->__as_node();
1760     __node_alloc_traits::destroy(__na, _VSTD::addressof(__np->__value_));
1761     __node_alloc_traits::deallocate(__na, __np, 1);
1762 }
1763
1764 template <class _Tp, class _Alloc>
1765 void
1766 list<_Tp, _Alloc>::pop_back()
1767 {
1768     _LIBCPP_ASSERT(!empty(), "list::pop_back() called with empty list");
1769     __node_allocator& __na = base::__node_alloc();
1770     __link_pointer __n = base::__end_.__prev_;
1771     base::__unlink_nodes(__n, __n);
1772     --base::__sz();
1773 #if _LIBCPP_DEBUG_LEVEL >= 2
1774     __c_node* __c = __get_db()->__find_c_and_lock(this);
1775     for (__i_node** __p = __c->end_; __p != __c->beg_; )
1776     {
1777         --__p;
1778         iterator* __i = static_cast<iterator*>((*__p)->__i_);
1779         if (__i->__ptr_ == __n)
1780         {
1781             (*__p)->__c_ = nullptr;
1782             if (--__c->end_ != __p)
1783                 memmove(__p, __p+1, (__c->end_ - __p)*sizeof(__i_node*));
1784         }
1785     }
1786     __get_db()->unlock();
1787 #endif
1788     __node_pointer __np = __n->__as_node();
1789     __node_alloc_traits::destroy(__na, _VSTD::addressof(__np->__value_));
1790     __node_alloc_traits::deallocate(__na, __np, 1);
1791 }
1792
1793 template <class _Tp, class _Alloc>
1794 typename list<_Tp, _Alloc>::iterator
1795 list<_Tp, _Alloc>::erase(const_iterator __p)
1796 {
1797 #if _LIBCPP_DEBUG_LEVEL >= 2
1798     _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__p) == this,
1799         "list::erase(iterator) called with an iterator not"
1800         " referring to this list");
1801 #endif
1802     _LIBCPP_ASSERT(__p != end(),
1803         "list::erase(iterator) called with a non-dereferenceable iterator");
1804     __node_allocator& __na = base::__node_alloc();
1805     __link_pointer __n = __p.__ptr_;
1806     __link_pointer __r = __n->__next_;
1807     base::__unlink_nodes(__n, __n);
1808     --base::__sz();
1809 #if _LIBCPP_DEBUG_LEVEL >= 2
1810     __c_node* __c = __get_db()->__find_c_and_lock(this);
1811     for (__i_node** __ip = __c->end_; __ip != __c->beg_; )
1812     {
1813         --__ip;
1814         iterator* __i = static_cast<iterator*>((*__ip)->__i_);
1815         if (__i->__ptr_ == __n)
1816         {
1817             (*__ip)->__c_ = nullptr;
1818             if (--__c->end_ != __ip)
1819                 memmove(__ip, __ip+1, (__c->end_ - __ip)*sizeof(__i_node*));
1820         }
1821     }
1822     __get_db()->unlock();
1823 #endif
1824     __node_pointer __np = __n->__as_node();
1825     __node_alloc_traits::destroy(__na, _VSTD::addressof(__np->__value_));
1826     __node_alloc_traits::deallocate(__na, __np, 1);
1827 #if _LIBCPP_DEBUG_LEVEL >= 2
1828     return iterator(__r, this);
1829 #else
1830     return iterator(__r);
1831 #endif
1832 }
1833
1834 template <class _Tp, class _Alloc>
1835 typename list<_Tp, _Alloc>::iterator
1836 list<_Tp, _Alloc>::erase(const_iterator __f, const_iterator __l)
1837 {
1838 #if _LIBCPP_DEBUG_LEVEL >= 2
1839     _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__f) == this,
1840         "list::erase(iterator, iterator) called with an iterator not"
1841         " referring to this list");
1842    _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__l) == this,
1843         "list::erase(iterator, iterator) called with an iterator not"
1844         " referring to this list");
1845 #endif
1846     if (__f != __l)
1847     {
1848         __node_allocator& __na = base::__node_alloc();
1849         base::__unlink_nodes(__f.__ptr_, __l.__ptr_->__prev_);
1850         while (__f != __l)
1851         {
1852             __link_pointer __n = __f.__ptr_;
1853             ++__f;
1854             --base::__sz();
1855 #if _LIBCPP_DEBUG_LEVEL >= 2
1856             __c_node* __c = __get_db()->__find_c_and_lock(this);
1857             for (__i_node** __p = __c->end_; __p != __c->beg_; )
1858             {
1859                 --__p;
1860                 iterator* __i = static_cast<iterator*>((*__p)->__i_);
1861                 if (__i->__ptr_ == __n)
1862                 {
1863                     (*__p)->__c_ = nullptr;
1864                     if (--__c->end_ != __p)
1865                         memmove(__p, __p+1, (__c->end_ - __p)*sizeof(__i_node*));
1866                 }
1867             }
1868             __get_db()->unlock();
1869 #endif
1870             __node_pointer __np = __n->__as_node();
1871             __node_alloc_traits::destroy(__na, _VSTD::addressof(__np->__value_));
1872             __node_alloc_traits::deallocate(__na, __np, 1);
1873         }
1874     }
1875 #if _LIBCPP_DEBUG_LEVEL >= 2
1876     return iterator(__l.__ptr_, this);
1877 #else
1878     return iterator(__l.__ptr_);
1879 #endif
1880 }
1881
1882 template <class _Tp, class _Alloc>
1883 void
1884 list<_Tp, _Alloc>::resize(size_type __n)
1885 {
1886     if (__n < base::__sz())
1887         erase(__iterator(__n), end());
1888     else if (__n > base::__sz())
1889     {
1890         __n -= base::__sz();
1891         size_type __ds = 0;
1892         __node_allocator& __na = base::__node_alloc();
1893         __hold_pointer __hold = __allocate_node(__na);
1894         __node_alloc_traits::construct(__na, _VSTD::addressof(__hold->__value_));
1895         ++__ds;
1896 #if _LIBCPP_DEBUG_LEVEL >= 2
1897         iterator __r = iterator(__hold.release()->__as_link(), this);
1898 #else
1899         iterator __r = iterator(__hold.release()->__as_link());
1900 #endif
1901         iterator __e = __r;
1902 #ifndef _LIBCPP_NO_EXCEPTIONS
1903         try
1904         {
1905 #endif  // _LIBCPP_NO_EXCEPTIONS
1906             for (--__n; __n != 0; --__n, ++__e, ++__ds)
1907             {
1908                 __hold.reset(__node_alloc_traits::allocate(__na, 1));
1909                 __node_alloc_traits::construct(__na, _VSTD::addressof(__hold->__value_));
1910                 __e.__ptr_->__next_ = __hold.get()->__as_link();
1911                 __hold->__prev_ = __e.__ptr_;
1912                 __hold.release();
1913             }
1914 #ifndef _LIBCPP_NO_EXCEPTIONS
1915         }
1916         catch (...)
1917         {
1918             while (true)
1919             {
1920                 __node_alloc_traits::destroy(__na, _VSTD::addressof(*__e));
1921                 __link_pointer __prev = __e.__ptr_->__prev_;
1922                 __node_alloc_traits::deallocate(__na, __e.__ptr_->__as_node(), 1);
1923                 if (__prev == 0)
1924                     break;
1925 #if _LIBCPP_DEBUG_LEVEL >= 2
1926                 __e = iterator(__prev, this);
1927 #else
1928                 __e = iterator(__prev);
1929 #endif
1930             }
1931             throw;
1932         }
1933 #endif  // _LIBCPP_NO_EXCEPTIONS
1934         __link_nodes_at_back(__r.__ptr_, __e.__ptr_);
1935         base::__sz() += __ds;
1936     }
1937 }
1938
1939 template <class _Tp, class _Alloc>
1940 void
1941 list<_Tp, _Alloc>::resize(size_type __n, const value_type& __x)
1942 {
1943     if (__n < base::__sz())
1944         erase(__iterator(__n), end());
1945     else if (__n > base::__sz())
1946     {
1947         __n -= base::__sz();
1948         size_type __ds = 0;
1949         __node_allocator& __na = base::__node_alloc();
1950         __hold_pointer __hold = __allocate_node(__na);
1951         __node_alloc_traits::construct(__na, _VSTD::addressof(__hold->__value_), __x);
1952         ++__ds;
1953         __link_pointer __nl = __hold.release()->__as_link();
1954 #if _LIBCPP_DEBUG_LEVEL >= 2
1955         iterator __r = iterator(__nl, this);
1956 #else
1957         iterator __r = iterator(__nl);
1958 #endif
1959         iterator __e = __r;
1960 #ifndef _LIBCPP_NO_EXCEPTIONS
1961         try
1962         {
1963 #endif  // _LIBCPP_NO_EXCEPTIONS
1964             for (--__n; __n != 0; --__n, ++__e, ++__ds)
1965             {
1966                 __hold.reset(__node_alloc_traits::allocate(__na, 1));
1967                 __node_alloc_traits::construct(__na, _VSTD::addressof(__hold->__value_), __x);
1968                 __e.__ptr_->__next_ = __hold.get()->__as_link();
1969                 __hold->__prev_ = __e.__ptr_;
1970                 __hold.release();
1971             }
1972 #ifndef _LIBCPP_NO_EXCEPTIONS
1973         }
1974         catch (...)
1975         {
1976             while (true)
1977             {
1978                 __node_alloc_traits::destroy(__na, _VSTD::addressof(*__e));
1979                 __link_pointer __prev = __e.__ptr_->__prev_;
1980                 __node_alloc_traits::deallocate(__na, __e.__ptr_->__as_node(), 1);
1981                 if (__prev == 0)
1982                     break;
1983 #if _LIBCPP_DEBUG_LEVEL >= 2
1984                 __e = iterator(__prev, this);
1985 #else
1986                 __e = iterator(__prev);
1987 #endif
1988             }
1989             throw;
1990         }
1991 #endif  // _LIBCPP_NO_EXCEPTIONS
1992         __link_nodes(base::__end_as_link(), __r.__ptr_, __e.__ptr_);
1993         base::__sz() += __ds;
1994     }
1995 }
1996
1997 template <class _Tp, class _Alloc>
1998 void
1999 list<_Tp, _Alloc>::splice(const_iterator __p, list& __c)
2000 {
2001     _LIBCPP_ASSERT(this != &__c,
2002                    "list::splice(iterator, list) called with this == &list");
2003 #if _LIBCPP_DEBUG_LEVEL >= 2
2004     _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__p) == this,
2005         "list::splice(iterator, list) called with an iterator not"
2006         " referring to this list");
2007 #endif
2008     if (!__c.empty())
2009     {
2010         __link_pointer __f = __c.__end_.__next_;
2011         __link_pointer __l = __c.__end_.__prev_;
2012         base::__unlink_nodes(__f, __l);
2013         __link_nodes(__p.__ptr_, __f, __l);
2014         base::__sz() += __c.__sz();
2015         __c.__sz() = 0;
2016 #if _LIBCPP_DEBUG_LEVEL >= 2
2017         __libcpp_db* __db = __get_db();
2018         __c_node* __cn1 = __db->__find_c_and_lock(this);
2019         __c_node* __cn2 = __db->__find_c(&__c);
2020         for (__i_node** __ip = __cn2->end_; __ip != __cn2->beg_;)
2021         {
2022             --__ip;
2023             iterator* __i = static_cast<iterator*>((*__ip)->__i_);
2024             if (__i->__ptr_ != __c.__end_as_link())
2025             {
2026                 __cn1->__add(*__ip);
2027                 (*__ip)->__c_ = __cn1;
2028                 if (--__cn2->end_ != __ip)
2029                     memmove(__ip, __ip+1, (__cn2->end_ - __ip)*sizeof(__i_node*));
2030             }
2031         }
2032         __db->unlock();
2033 #endif
2034     }
2035 }
2036
2037 template <class _Tp, class _Alloc>
2038 void
2039 list<_Tp, _Alloc>::splice(const_iterator __p, list& __c, const_iterator __i)
2040 {
2041 #if _LIBCPP_DEBUG_LEVEL >= 2
2042     _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__p) == this,
2043         "list::splice(iterator, list, iterator) called with first iterator not"
2044         " referring to this list");
2045     _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__i) == &__c,
2046         "list::splice(iterator, list, iterator) called with second iterator not"
2047         " referring to list argument");
2048     _LIBCPP_ASSERT(__get_const_db()->__dereferenceable(&__i),
2049         "list::splice(iterator, list, iterator) called with second iterator not"
2050         " derefereceable");
2051 #endif
2052     if (__p.__ptr_ != __i.__ptr_ && __p.__ptr_ != __i.__ptr_->__next_)
2053     {
2054         __link_pointer __f = __i.__ptr_;
2055         base::__unlink_nodes(__f, __f);
2056         __link_nodes(__p.__ptr_, __f, __f);
2057         --__c.__sz();
2058         ++base::__sz();
2059 #if _LIBCPP_DEBUG_LEVEL >= 2
2060         __libcpp_db* __db = __get_db();
2061         __c_node* __cn1 = __db->__find_c_and_lock(this);
2062         __c_node* __cn2 = __db->__find_c(&__c);
2063         for (__i_node** __ip = __cn2->end_; __ip != __cn2->beg_;)
2064         {
2065             --__ip;
2066             iterator* __j = static_cast<iterator*>((*__ip)->__i_);
2067             if (__j->__ptr_ == __f)
2068             {
2069                 __cn1->__add(*__ip);
2070                 (*__ip)->__c_ = __cn1;
2071                 if (--__cn2->end_ != __ip)
2072                     memmove(__ip, __ip+1, (__cn2->end_ - __ip)*sizeof(__i_node*));
2073             }
2074         }
2075         __db->unlock();
2076 #endif
2077     }
2078 }
2079
2080 template <class _Tp, class _Alloc>
2081 void
2082 list<_Tp, _Alloc>::splice(const_iterator __p, list& __c, const_iterator __f, const_iterator __l)
2083 {
2084 #if _LIBCPP_DEBUG_LEVEL >= 2
2085     _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__p) == this,
2086         "list::splice(iterator, list, iterator, iterator) called with first iterator not"
2087         " referring to this list");
2088     _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__f) == &__c,
2089         "list::splice(iterator, list, iterator, iterator) called with second iterator not"
2090         " referring to list argument");
2091     if (this == &__c)
2092     {
2093         for (const_iterator __i = __f; __i != __l; ++__i)
2094             _LIBCPP_ASSERT(__i != __p,
2095                            "list::splice(iterator, list, iterator, iterator)"
2096                            " called with the first iterator within the range"
2097                            " of the second and third iterators");
2098     }
2099 #endif
2100     if (__f != __l)
2101     {
2102         __link_pointer __first = __f.__ptr_;
2103         --__l;
2104         __link_pointer __last = __l.__ptr_;
2105         if (this != &__c)
2106         {
2107             size_type __s = _VSTD::distance(__f, __l) + 1;
2108             __c.__sz() -= __s;
2109             base::__sz() += __s;
2110         }
2111         base::__unlink_nodes(__first, __last);
2112         __link_nodes(__p.__ptr_, __first, __last);
2113 #if _LIBCPP_DEBUG_LEVEL >= 2
2114         __libcpp_db* __db = __get_db();
2115         __c_node* __cn1 = __db->__find_c_and_lock(this);
2116         __c_node* __cn2 = __db->__find_c(&__c);
2117         for (__i_node** __ip = __cn2->end_; __ip != __cn2->beg_;)
2118         {
2119             --__ip;
2120             iterator* __j = static_cast<iterator*>((*__ip)->__i_);
2121             for (__link_pointer __k = __f.__ptr_;
2122                                           __k != __l.__ptr_; __k = __k->__next_)
2123             {
2124                 if (__j->__ptr_ == __k)
2125                 {
2126                     __cn1->__add(*__ip);
2127                     (*__ip)->__c_ = __cn1;
2128                     if (--__cn2->end_ != __ip)
2129                         memmove(__ip, __ip+1, (__cn2->end_ - __ip)*sizeof(__i_node*));
2130                 }
2131             }
2132         }
2133         __db->unlock();
2134 #endif
2135     }
2136 }
2137
2138 template <class _Tp, class _Alloc>
2139 void
2140 list<_Tp, _Alloc>::remove(const value_type& __x)
2141 {
2142     list<_Tp, _Alloc> __deleted_nodes(get_allocator()); // collect the nodes we're removing
2143     for (const_iterator __i = begin(), __e = end(); __i != __e;)
2144     {
2145         if (*__i == __x)
2146         {
2147             const_iterator __j = _VSTD::next(__i);
2148             for (; __j != __e && *__j == __x; ++__j)
2149                 ;
2150             __deleted_nodes.splice(__deleted_nodes.end(), *this, __i, __j);
2151             __i = __j;
2152             if (__i != __e)
2153                 ++__i;
2154         }
2155         else
2156             ++__i;
2157     }
2158 }
2159
2160 template <class _Tp, class _Alloc>
2161 template <class _Pred>
2162 void
2163 list<_Tp, _Alloc>::remove_if(_Pred __pred)
2164 {
2165     for (iterator __i = begin(), __e = end(); __i != __e;)
2166     {
2167         if (__pred(*__i))
2168         {
2169             iterator __j = _VSTD::next(__i);
2170             for (; __j != __e && __pred(*__j); ++__j)
2171                 ;
2172             __i = erase(__i, __j);
2173             if (__i != __e)
2174                 ++__i;
2175         }
2176         else
2177             ++__i;
2178     }
2179 }
2180
2181 template <class _Tp, class _Alloc>
2182 inline
2183 void
2184 list<_Tp, _Alloc>::unique()
2185 {
2186     unique(__equal_to<value_type>());
2187 }
2188
2189 template <class _Tp, class _Alloc>
2190 template <class _BinaryPred>
2191 void
2192 list<_Tp, _Alloc>::unique(_BinaryPred __binary_pred)
2193 {
2194     for (iterator __i = begin(), __e = end(); __i != __e;)
2195     {
2196         iterator __j = _VSTD::next(__i);
2197         for (; __j != __e && __binary_pred(*__i, *__j); ++__j)
2198             ;
2199         if (++__i != __j)
2200             __i = erase(__i, __j);
2201     }
2202 }
2203
2204 template <class _Tp, class _Alloc>
2205 inline
2206 void
2207 list<_Tp, _Alloc>::merge(list& __c)
2208 {
2209     merge(__c, __less<value_type>());
2210 }
2211
2212 template <class _Tp, class _Alloc>
2213 template <class _Comp>
2214 void
2215 list<_Tp, _Alloc>::merge(list& __c, _Comp __comp)
2216 {
2217     if (this != _VSTD::addressof(__c))
2218     {
2219         iterator __f1 = begin();
2220         iterator __e1 = end();
2221         iterator __f2 = __c.begin();
2222         iterator __e2 = __c.end();
2223         while (__f1 != __e1 && __f2 != __e2)
2224         {
2225             if (__comp(*__f2, *__f1))
2226             {
2227                 size_type __ds = 1;
2228                 iterator __m2 = _VSTD::next(__f2);
2229                 for (; __m2 != __e2 && __comp(*__m2, *__f1); ++__m2, ++__ds)
2230                     ;
2231                 base::__sz() += __ds;
2232                 __c.__sz() -= __ds;
2233                 __link_pointer __f = __f2.__ptr_;
2234                 __link_pointer __l = __m2.__ptr_->__prev_;
2235                 __f2 = __m2;
2236                 base::__unlink_nodes(__f, __l);
2237                 __m2 = _VSTD::next(__f1);
2238                 __link_nodes(__f1.__ptr_, __f, __l);
2239                 __f1 = __m2;
2240             }
2241             else
2242                 ++__f1;
2243         }
2244         splice(__e1, __c);
2245 #if _LIBCPP_DEBUG_LEVEL >= 2
2246         __libcpp_db* __db = __get_db();
2247         __c_node* __cn1 = __db->__find_c_and_lock(this);
2248         __c_node* __cn2 = __db->__find_c(&__c);
2249         for (__i_node** __p = __cn2->end_; __p != __cn2->beg_;)
2250         {
2251             --__p;
2252             iterator* __i = static_cast<iterator*>((*__p)->__i_);
2253             if (__i->__ptr_ != __c.__end_as_link())
2254             {
2255                 __cn1->__add(*__p);
2256                 (*__p)->__c_ = __cn1;
2257                 if (--__cn2->end_ != __p)
2258                     memmove(__p, __p+1, (__cn2->end_ - __p)*sizeof(__i_node*));
2259             }
2260         }
2261         __db->unlock();
2262 #endif
2263     }
2264 }
2265
2266 template <class _Tp, class _Alloc>
2267 inline
2268 void
2269 list<_Tp, _Alloc>::sort()
2270 {
2271     sort(__less<value_type>());
2272 }
2273
2274 template <class _Tp, class _Alloc>
2275 template <class _Comp>
2276 inline
2277 void
2278 list<_Tp, _Alloc>::sort(_Comp __comp)
2279 {
2280     __sort(begin(), end(), base::__sz(), __comp);
2281 }
2282
2283 template <class _Tp, class _Alloc>
2284 template <class _Comp>
2285 typename list<_Tp, _Alloc>::iterator
2286 list<_Tp, _Alloc>::__sort(iterator __f1, iterator __e2, size_type __n, _Comp& __comp)
2287 {
2288     switch (__n)
2289     {
2290     case 0:
2291     case 1:
2292         return __f1;
2293     case 2:
2294         if (__comp(*--__e2, *__f1))
2295         {
2296             __link_pointer __f = __e2.__ptr_;
2297             base::__unlink_nodes(__f, __f);
2298             __link_nodes(__f1.__ptr_, __f, __f);
2299             return __e2;
2300         }
2301         return __f1;
2302     }
2303     size_type __n2 = __n / 2;
2304     iterator __e1 = _VSTD::next(__f1, __n2);
2305     iterator  __r = __f1 = __sort(__f1, __e1, __n2, __comp);
2306     iterator __f2 = __e1 = __sort(__e1, __e2, __n - __n2, __comp);
2307     if (__comp(*__f2, *__f1))
2308     {
2309         iterator __m2 = _VSTD::next(__f2);
2310         for (; __m2 != __e2 && __comp(*__m2, *__f1); ++__m2)
2311             ;
2312         __link_pointer __f = __f2.__ptr_;
2313         __link_pointer __l = __m2.__ptr_->__prev_;
2314         __r = __f2;
2315         __e1 = __f2 = __m2;
2316         base::__unlink_nodes(__f, __l);
2317         __m2 = _VSTD::next(__f1);
2318         __link_nodes(__f1.__ptr_, __f, __l);
2319         __f1 = __m2;
2320     }
2321     else
2322         ++__f1;
2323     while (__f1 != __e1 && __f2 != __e2)
2324     {
2325         if (__comp(*__f2, *__f1))
2326         {
2327             iterator __m2 = _VSTD::next(__f2);
2328             for (; __m2 != __e2 && __comp(*__m2, *__f1); ++__m2)
2329                 ;
2330             __link_pointer __f = __f2.__ptr_;
2331             __link_pointer __l = __m2.__ptr_->__prev_;
2332             if (__e1 == __f2)
2333                 __e1 = __m2;
2334             __f2 = __m2;
2335             base::__unlink_nodes(__f, __l);
2336             __m2 = _VSTD::next(__f1);
2337             __link_nodes(__f1.__ptr_, __f, __l);
2338             __f1 = __m2;
2339         }
2340         else
2341             ++__f1;
2342     }
2343     return __r;
2344 }
2345
2346 template <class _Tp, class _Alloc>
2347 void
2348 list<_Tp, _Alloc>::reverse() _NOEXCEPT
2349 {
2350     if (base::__sz() > 1)
2351     {
2352         iterator __e = end();
2353         for (iterator __i = begin(); __i.__ptr_ != __e.__ptr_;)
2354         {
2355             _VSTD::swap(__i.__ptr_->__prev_, __i.__ptr_->__next_);
2356             __i.__ptr_ = __i.__ptr_->__prev_;
2357         }
2358         _VSTD::swap(__e.__ptr_->__prev_, __e.__ptr_->__next_);
2359     }
2360 }
2361
2362 template <class _Tp, class _Alloc>
2363 bool
2364 list<_Tp, _Alloc>::__invariants() const
2365 {
2366     return size() == _VSTD::distance(begin(), end());
2367 }
2368
2369 #if _LIBCPP_DEBUG_LEVEL >= 2
2370
2371 template <class _Tp, class _Alloc>
2372 bool
2373 list<_Tp, _Alloc>::__dereferenceable(const const_iterator* __i) const
2374 {
2375     return __i->__ptr_ != this->__end_as_link();
2376 }
2377
2378 template <class _Tp, class _Alloc>
2379 bool
2380 list<_Tp, _Alloc>::__decrementable(const const_iterator* __i) const
2381 {
2382     return !empty() &&  __i->__ptr_ != base::__end_.__next_;
2383 }
2384
2385 template <class _Tp, class _Alloc>
2386 bool
2387 list<_Tp, _Alloc>::__addable(const const_iterator*, ptrdiff_t) const
2388 {
2389     return false;
2390 }
2391
2392 template <class _Tp, class _Alloc>
2393 bool
2394 list<_Tp, _Alloc>::__subscriptable(const const_iterator*, ptrdiff_t) const
2395 {
2396     return false;
2397 }
2398
2399 #endif  // _LIBCPP_DEBUG_LEVEL >= 2
2400
2401 template <class _Tp, class _Alloc>
2402 inline _LIBCPP_INLINE_VISIBILITY
2403 bool
2404 operator==(const list<_Tp, _Alloc>& __x, const list<_Tp, _Alloc>& __y)
2405 {
2406     return __x.size() == __y.size() && _VSTD::equal(__x.begin(), __x.end(), __y.begin());
2407 }
2408
2409 template <class _Tp, class _Alloc>
2410 inline _LIBCPP_INLINE_VISIBILITY
2411 bool
2412 operator< (const list<_Tp, _Alloc>& __x, const list<_Tp, _Alloc>& __y)
2413 {
2414     return _VSTD::lexicographical_compare(__x.begin(), __x.end(), __y.begin(), __y.end());
2415 }
2416
2417 template <class _Tp, class _Alloc>
2418 inline _LIBCPP_INLINE_VISIBILITY
2419 bool
2420 operator!=(const list<_Tp, _Alloc>& __x, const list<_Tp, _Alloc>& __y)
2421 {
2422     return !(__x == __y);
2423 }
2424
2425 template <class _Tp, class _Alloc>
2426 inline _LIBCPP_INLINE_VISIBILITY
2427 bool
2428 operator> (const list<_Tp, _Alloc>& __x, const list<_Tp, _Alloc>& __y)
2429 {
2430     return __y < __x;
2431 }
2432
2433 template <class _Tp, class _Alloc>
2434 inline _LIBCPP_INLINE_VISIBILITY
2435 bool
2436 operator>=(const list<_Tp, _Alloc>& __x, const list<_Tp, _Alloc>& __y)
2437 {
2438     return !(__x < __y);
2439 }
2440
2441 template <class _Tp, class _Alloc>
2442 inline _LIBCPP_INLINE_VISIBILITY
2443 bool
2444 operator<=(const list<_Tp, _Alloc>& __x, const list<_Tp, _Alloc>& __y)
2445 {
2446     return !(__y < __x);
2447 }
2448
2449 template <class _Tp, class _Alloc>
2450 inline _LIBCPP_INLINE_VISIBILITY
2451 void
2452 swap(list<_Tp, _Alloc>& __x, list<_Tp, _Alloc>& __y)
2453     _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y)))
2454 {
2455     __x.swap(__y);
2456 }
2457
2458 #if _LIBCPP_STD_VER > 17
2459 template <class _Tp, class _Allocator, class _Predicate>
2460 inline _LIBCPP_INLINE_VISIBILITY
2461 void erase_if(list<_Tp, _Allocator>& __c, _Predicate __pred)
2462 { __c.remove_if(__pred); }
2463
2464 template <class _Tp, class _Allocator, class _Up>
2465 inline _LIBCPP_INLINE_VISIBILITY
2466 void erase(list<_Tp, _Allocator>& __c, const _Up& __v)
2467 { _VSTD::erase_if(__c, [&](auto& __elem) { return __elem == __v; }); }
2468 #endif
2469
2470 _LIBCPP_END_NAMESPACE_STD
2471
2472 _LIBCPP_POP_MACROS
2473
2474 #endif  // _LIBCPP_LIST