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