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