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