contrib/libc++/include/list

   1 // -*- C++ -*-
   2 //===---------------------------- list ------------------------------------===//
   3 //
   4 //                     The LLVM Compiler Infrastructure
   5 //
   6 // This file is dual licensed under the MIT and the University of Illinois Open
   7 // Source Licenses. See LICENSE.TXT for details.
   8 //
   9 //===----------------------------------------------------------------------===//
  10
  11 #ifndef _LIBCPP_LIST
  12 #define _LIBCPP_LIST
  13
  14 /*
  15     list synopsis
  16
  17 namespace std
  18 {
  19
  20 template <class T, class Alloc = allocator<T> >
  21 class list
  22 {
  23 public:
  24
  25     // types:
  26     typedef T value_type;
  27     typedef Alloc allocator_type;
  28     typedef typename allocator_type::reference reference;
  29     typedef typename allocator_type::const_reference const_reference;
  30     typedef typename allocator_type::pointer pointer;
  31     typedef typename allocator_type::const_pointer const_pointer;
  32     typedef implementation-defined iterator;
  33     typedef implementation-defined const_iterator;
  34     typedef implementation-defined size_type;
  35     typedef implementation-defined difference_type;
  36     typedef reverse_iterator<iterator> reverse_iterator;
  37     typedef reverse_iterator<const_iterator> const_reverse_iterator;
  38
  39     list()
  40         noexcept(is_nothrow_default_constructible<allocator_type>::value);
  41     explicit list(const allocator_type& a);
  42     explicit list(size_type n);
  43     explicit list(size_type n, const allocator_type& a); // C++14
  44     list(size_type n, const value_type& value);
  45     list(size_type n, const value_type& value, const allocator_type& a);
  46     template <class Iter>
  47         list(Iter first, Iter last);
  48     template <class Iter>
  49         list(Iter first, Iter last, const allocator_type& a);
  50     list(const list& x);
  51     list(const list&, const allocator_type& a);
  52     list(list&& x)
  53         noexcept(is_nothrow_move_constructible<allocator_type>::value);
  54     list(list&&, const allocator_type& a);
  55     list(initializer_list<value_type>);
  56     list(initializer_list<value_type>, const allocator_type& a);
  57
  58     ~list();
  59
  60     list& operator=(const list& x);
  61     list& operator=(list&& x)
  62         noexcept(
  63              allocator_type::propagate_on_container_move_assignment::value &&
  64              is_nothrow_move_assignable<allocator_type>::value);
  65     list& operator=(initializer_list<value_type>);
  66     template <class Iter>
  67         void assign(Iter first, Iter last);
  68     void assign(size_type n, const value_type& t);
  69     void assign(initializer_list<value_type>);
  70
  71     allocator_type get_allocator() const noexcept;
  72
  73     iterator begin() noexcept;
  74     const_iterator begin() const noexcept;
  75     iterator end() noexcept;
  76     const_iterator end() const noexcept;
  77     reverse_iterator rbegin() noexcept;
  78     const_reverse_iterator rbegin() const noexcept;
  79     reverse_iterator rend() noexcept;
  80     const_reverse_iterator rend() const noexcept;
  81     const_iterator cbegin() const noexcept;
  82     const_iterator cend() const noexcept;
  83     const_reverse_iterator crbegin() const noexcept;
  84     const_reverse_iterator crend() const noexcept;
  85
  86     reference front();
  87     const_reference front() const;
  88     reference back();
  89     const_reference back() const;
  90
  91     bool empty() const noexcept;
  92     size_type size() const noexcept;
  93     size_type max_size() const noexcept;
  94
  95     template <class... Args>
  96         reference emplace_front(Args&&... args); // reference in C++17
  97     void pop_front();
  98     template <class... Args>
  99         reference emplace_back(Args&&... args);  // reference in C++17
 100     void pop_back();
 101     void push_front(const value_type& x);
 102     void push_front(value_type&& x);
 103     void push_back(const value_type& x);
 104     void push_back(value_type&& x);
 105     template <class... Args>
 106         iterator emplace(const_iterator position, Args&&... args);
 107     iterator insert(const_iterator position, const value_type& x);
 108     iterator insert(const_iterator position, value_type&& x);
 109     iterator insert(const_iterator position, size_type n, const value_type& x);
 110     template <class Iter>
 111         iterator insert(const_iterator position, Iter first, Iter last);
 112     iterator insert(const_iterator position, initializer_list<value_type> il);
 113
 114     iterator erase(const_iterator position);
 115     iterator erase(const_iterator position, const_iterator last);
 116
 117     void resize(size_type sz);
 118     void resize(size_type sz, const value_type& c);
 119
 120     void swap(list&)
 121         noexcept(allocator_traits<allocator_type>::is_always_equal::value);  // C++17
 122     void clear() noexcept;
 123
 124     void splice(const_iterator position, list& x);
 125     void splice(const_iterator position, list&& x);
 126     void splice(const_iterator position, list& x, const_iterator i);
 127     void splice(const_iterator position, list&& x, const_iterator i);
 128     void splice(const_iterator position, list& x, const_iterator first,
 129                                                   const_iterator last);
 130     void splice(const_iterator position, list&& x, const_iterator first,
 131                                                   const_iterator last);
 132
 133     void remove(const value_type& value);
 134     template <class Pred> void remove_if(Pred pred);
 135     void unique();
 136     template <class BinaryPredicate>
 137         void unique(BinaryPredicate binary_pred);
 138     void merge(list& x);
 139     void merge(list&& x);
 140     template <class Compare>
 141         void merge(list& x, Compare comp);
 142     template <class Compare>
 143         void merge(list&& x, Compare comp);
 144     void sort();
 145     template <class Compare>
 146         void sort(Compare comp);
 147     void reverse() noexcept;
 148 };
 149
 150 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_CXX03_LANG
 864     list(initializer_list<value_type> __il);
 865     list(initializer_list<value_type> __il, const allocator_type& __a);
 866
 867     _LIBCPP_INLINE_VISIBILITY
 868     list(list&& __c)
 869         _NOEXCEPT_(is_nothrow_move_constructible<__node_allocator>::value);
 870     _LIBCPP_INLINE_VISIBILITY
 871     list(list&& __c, const allocator_type& __a);
 872     _LIBCPP_INLINE_VISIBILITY
 873     list& operator=(list&& __c)
 874         _NOEXCEPT_(
 875             __node_alloc_traits::propagate_on_container_move_assignment::value &&
 876             is_nothrow_move_assignable<__node_allocator>::value);
 877
 878     _LIBCPP_INLINE_VISIBILITY
 879     list& operator=(initializer_list<value_type> __il)
 880         {assign(__il.begin(), __il.end()); return *this;}
 881
 882     _LIBCPP_INLINE_VISIBILITY
 883     void assign(initializer_list<value_type> __il)
 884         {assign(__il.begin(), __il.end());}
 885 #endif  // _LIBCPP_CXX03_LANG
 886
 887     template <class _InpIter>
 888         void assign(_InpIter __f, _InpIter __l,
 889              typename enable_if<__is_input_iterator<_InpIter>::value>::type* = 0);
 890     void assign(size_type __n, const value_type& __x);
 891
 892     _LIBCPP_INLINE_VISIBILITY
 893     allocator_type get_allocator() const _NOEXCEPT;
 894
 895     _LIBCPP_INLINE_VISIBILITY
 896     size_type size() const _NOEXCEPT     {return base::__sz();}
 897     _LIBCPP_INLINE_VISIBILITY
 898     bool empty() const _NOEXCEPT         {return base::empty();}
 899     _LIBCPP_INLINE_VISIBILITY
 900     size_type max_size() const _NOEXCEPT
 901         {
 902             return std::min<size_type>(
 903                 base::__node_alloc_max_size(),
 904                 numeric_limits<difference_type >::max());
 905         }
 906
 907     _LIBCPP_INLINE_VISIBILITY
 908           iterator begin() _NOEXCEPT        {return base::begin();}
 909     _LIBCPP_INLINE_VISIBILITY
 910     const_iterator begin()  const _NOEXCEPT {return base::begin();}
 911     _LIBCPP_INLINE_VISIBILITY
 912           iterator end() _NOEXCEPT          {return base::end();}
 913     _LIBCPP_INLINE_VISIBILITY
 914     const_iterator end()    const _NOEXCEPT {return base::end();}
 915     _LIBCPP_INLINE_VISIBILITY
 916     const_iterator cbegin() const _NOEXCEPT {return base::begin();}
 917     _LIBCPP_INLINE_VISIBILITY
 918     const_iterator cend()   const _NOEXCEPT {return base::end();}
 919
 920     _LIBCPP_INLINE_VISIBILITY
 921           reverse_iterator rbegin() _NOEXCEPT
 922             {return       reverse_iterator(end());}
 923     _LIBCPP_INLINE_VISIBILITY
 924     const_reverse_iterator rbegin()  const _NOEXCEPT
 925         {return const_reverse_iterator(end());}
 926     _LIBCPP_INLINE_VISIBILITY
 927           reverse_iterator rend() _NOEXCEPT
 928             {return       reverse_iterator(begin());}
 929     _LIBCPP_INLINE_VISIBILITY
 930     const_reverse_iterator rend()    const _NOEXCEPT
 931         {return const_reverse_iterator(begin());}
 932     _LIBCPP_INLINE_VISIBILITY
 933     const_reverse_iterator crbegin() const _NOEXCEPT
 934         {return const_reverse_iterator(end());}
 935     _LIBCPP_INLINE_VISIBILITY
 936     const_reverse_iterator crend()   const _NOEXCEPT
 937         {return const_reverse_iterator(begin());}
 938
 939     _LIBCPP_INLINE_VISIBILITY
 940     reference front()
 941     {
 942         _LIBCPP_ASSERT(!empty(), "list::front called on empty list");
 943         return base::__end_.__next_->__as_node()->__value_;
 944     }
 945     _LIBCPP_INLINE_VISIBILITY
 946     const_reference front() const
 947     {
 948         _LIBCPP_ASSERT(!empty(), "list::front called on empty list");
 949         return base::__end_.__next_->__as_node()->__value_;
 950     }
 951     _LIBCPP_INLINE_VISIBILITY
 952     reference back()
 953     {
 954         _LIBCPP_ASSERT(!empty(), "list::back called on empty list");
 955         return base::__end_.__prev_->__as_node()->__value_;
 956     }
 957     _LIBCPP_INLINE_VISIBILITY
 958     const_reference back() const
 959     {
 960         _LIBCPP_ASSERT(!empty(), "list::back called on empty list");
 961         return base::__end_.__prev_->__as_node()->__value_;
 962     }
 963
 964 #ifndef _LIBCPP_CXX03_LANG
 965     void push_front(value_type&& __x);
 966     void push_back(value_type&& __x);
 967
 968     template <class... _Args>
 969 #if _LIBCPP_STD_VER > 14
 970        reference emplace_front(_Args&&... __args);
 971 #else
 972        void      emplace_front(_Args&&... __args);
 973 #endif
 974     template <class... _Args>
 975 #if _LIBCPP_STD_VER > 14
 976         reference emplace_back(_Args&&... __args);
 977 #else
 978        void       emplace_back(_Args&&... __args);
 979 #endif
 980     template <class... _Args>
 981         iterator emplace(const_iterator __p, _Args&&... __args);
 982
 983     iterator insert(const_iterator __p, value_type&& __x);
 984
 985     _LIBCPP_INLINE_VISIBILITY
 986     iterator insert(const_iterator __p, initializer_list<value_type> __il)
 987         {return insert(__p, __il.begin(), __il.end());}
 988 #endif  // _LIBCPP_CXX03_LANG
 989
 990     void push_front(const value_type& __x);
 991     void push_back(const value_type& __x);
 992
 993     iterator insert(const_iterator __p, const value_type& __x);
 994     iterator insert(const_iterator __p, size_type __n, const value_type& __x);
 995     template <class _InpIter>
 996         iterator insert(const_iterator __p, _InpIter __f, _InpIter __l,
 997              typename enable_if<__is_input_iterator<_InpIter>::value>::type* = 0);
 998
 999     _LIBCPP_INLINE_VISIBILITY
1000     void swap(list& __c)
1001 #if _LIBCPP_STD_VER >= 14
1002         _NOEXCEPT_DEBUG
1003 #else
1004         _NOEXCEPT_DEBUG_(!__node_alloc_traits::propagate_on_container_swap::value ||
1005                    __is_nothrow_swappable<__node_allocator>::value)
1006 #endif
1007         {base::swap(__c);}
1008     _LIBCPP_INLINE_VISIBILITY
1009     void clear() _NOEXCEPT {base::clear();}
1010
1011     void pop_front();
1012     void pop_back();
1013
1014     iterator erase(const_iterator __p);
1015     iterator erase(const_iterator __f, const_iterator __l);
1016
1017     void resize(size_type __n);
1018     void resize(size_type __n, const value_type& __x);
1019
1020     void splice(const_iterator __p, list& __c);
1021 #ifndef _LIBCPP_CXX03_LANG
1022     _LIBCPP_INLINE_VISIBILITY
1023     void splice(const_iterator __p, list&& __c) {splice(__p, __c);}
1024     _LIBCPP_INLINE_VISIBILITY
1025     void splice(const_iterator __p, list&& __c, const_iterator __i)
1026         {splice(__p, __c, __i);}
1027     _LIBCPP_INLINE_VISIBILITY
1028     void splice(const_iterator __p, list&& __c, const_iterator __f, const_iterator __l)
1029         {splice(__p, __c, __f, __l);}
1030 #endif
1031     void splice(const_iterator __p, list& __c, const_iterator __i);
1032     void splice(const_iterator __p, list& __c, const_iterator __f, const_iterator __l);
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_CXX03_LANG
1043     _LIBCPP_INLINE_VISIBILITY
1044     void merge(list&& __c) {merge(__c);}
1045
1046     template <class _Comp>
1047     _LIBCPP_INLINE_VISIBILITY
1048         void merge(list&& __c, _Comp __comp) {merge(__c, __comp);}
1049 #endif
1050     template <class _Comp>
1051         void merge(list& __c, _Comp __comp);
1052
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_CXX03_LANG
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         emplace_back();
1157 }
1158 #endif
1159
1160 template <class _Tp, class _Alloc>
1161 list<_Tp, _Alloc>::list(size_type __n, const value_type& __x)
1162 {
1163 #if _LIBCPP_DEBUG_LEVEL >= 2
1164     __get_db()->__insert_c(this);
1165 #endif
1166     for (; __n > 0; --__n)
1167         push_back(__x);
1168 }
1169
1170 template <class _Tp, class _Alloc>
1171 list<_Tp, _Alloc>::list(size_type __n, const value_type& __x, const allocator_type& __a)
1172     : base(__a)
1173 {
1174 #if _LIBCPP_DEBUG_LEVEL >= 2
1175     __get_db()->__insert_c(this);
1176 #endif
1177     for (; __n > 0; --__n)
1178         push_back(__x);
1179 }
1180
1181 template <class _Tp, class _Alloc>
1182 template <class _InpIter>
1183 list<_Tp, _Alloc>::list(_InpIter __f, _InpIter __l,
1184                         typename enable_if<__is_input_iterator<_InpIter>::value>::type*)
1185 {
1186 #if _LIBCPP_DEBUG_LEVEL >= 2
1187     __get_db()->__insert_c(this);
1188 #endif
1189     for (; __f != __l; ++__f)
1190         push_back(*__f);
1191 }
1192
1193 template <class _Tp, class _Alloc>
1194 template <class _InpIter>
1195 list<_Tp, _Alloc>::list(_InpIter __f, _InpIter __l, const allocator_type& __a,
1196                         typename enable_if<__is_input_iterator<_InpIter>::value>::type*)
1197     : base(__a)
1198 {
1199 #if _LIBCPP_DEBUG_LEVEL >= 2
1200     __get_db()->__insert_c(this);
1201 #endif
1202     for (; __f != __l; ++__f)
1203         push_back(*__f);
1204 }
1205
1206 template <class _Tp, class _Alloc>
1207 list<_Tp, _Alloc>::list(const list& __c)
1208     : base(allocator_type(
1209            __node_alloc_traits::select_on_container_copy_construction(
1210                 __c.__node_alloc())))
1211 {
1212 #if _LIBCPP_DEBUG_LEVEL >= 2
1213     __get_db()->__insert_c(this);
1214 #endif
1215     for (const_iterator __i = __c.begin(), __e = __c.end(); __i != __e; ++__i)
1216         push_back(*__i);
1217 }
1218
1219 template <class _Tp, class _Alloc>
1220 list<_Tp, _Alloc>::list(const list& __c, const allocator_type& __a)
1221     : base(__a)
1222 {
1223 #if _LIBCPP_DEBUG_LEVEL >= 2
1224     __get_db()->__insert_c(this);
1225 #endif
1226     for (const_iterator __i = __c.begin(), __e = __c.end(); __i != __e; ++__i)
1227         push_back(*__i);
1228 }
1229
1230 #ifndef _LIBCPP_CXX03_LANG
1231
1232 template <class _Tp, class _Alloc>
1233 list<_Tp, _Alloc>::list(initializer_list<value_type> __il, const allocator_type& __a)
1234     : base(__a)
1235 {
1236 #if _LIBCPP_DEBUG_LEVEL >= 2
1237     __get_db()->__insert_c(this);
1238 #endif
1239     for (typename initializer_list<value_type>::const_iterator __i = __il.begin(),
1240             __e = __il.end(); __i != __e; ++__i)
1241         push_back(*__i);
1242 }
1243
1244 template <class _Tp, class _Alloc>
1245 list<_Tp, _Alloc>::list(initializer_list<value_type> __il)
1246 {
1247 #if _LIBCPP_DEBUG_LEVEL >= 2
1248     __get_db()->__insert_c(this);
1249 #endif
1250     for (typename initializer_list<value_type>::const_iterator __i = __il.begin(),
1251             __e = __il.end(); __i != __e; ++__i)
1252         push_back(*__i);
1253 }
1254
1255 template <class _Tp, class _Alloc>
1256 inline
1257 list<_Tp, _Alloc>::list(list&& __c)
1258     _NOEXCEPT_(is_nothrow_move_constructible<__node_allocator>::value)
1259     : base(allocator_type(_VSTD::move(__c.__node_alloc())))
1260 {
1261 #if _LIBCPP_DEBUG_LEVEL >= 2
1262     __get_db()->__insert_c(this);
1263 #endif
1264     splice(end(), __c);
1265 }
1266
1267 template <class _Tp, class _Alloc>
1268 inline
1269 list<_Tp, _Alloc>::list(list&& __c, const allocator_type& __a)
1270     : base(__a)
1271 {
1272 #if _LIBCPP_DEBUG_LEVEL >= 2
1273     __get_db()->__insert_c(this);
1274 #endif
1275     if (__a == __c.get_allocator())
1276         splice(end(), __c);
1277     else
1278     {
1279         typedef move_iterator<iterator> _Ip;
1280         assign(_Ip(__c.begin()), _Ip(__c.end()));
1281     }
1282 }
1283
1284 template <class _Tp, class _Alloc>
1285 inline
1286 list<_Tp, _Alloc>&
1287 list<_Tp, _Alloc>::operator=(list&& __c)
1288         _NOEXCEPT_(
1289             __node_alloc_traits::propagate_on_container_move_assignment::value &&
1290             is_nothrow_move_assignable<__node_allocator>::value)
1291 {
1292     __move_assign(__c, integral_constant<bool,
1293           __node_alloc_traits::propagate_on_container_move_assignment::value>());
1294     return *this;
1295 }
1296
1297 template <class _Tp, class _Alloc>
1298 void
1299 list<_Tp, _Alloc>::__move_assign(list& __c, false_type)
1300 {
1301     if (base::__node_alloc() != __c.__node_alloc())
1302     {
1303         typedef move_iterator<iterator> _Ip;
1304         assign(_Ip(__c.begin()), _Ip(__c.end()));
1305     }
1306     else
1307         __move_assign(__c, true_type());
1308 }
1309
1310 template <class _Tp, class _Alloc>
1311 void
1312 list<_Tp, _Alloc>::__move_assign(list& __c, true_type)
1313         _NOEXCEPT_(is_nothrow_move_assignable<__node_allocator>::value)
1314 {
1315     clear();
1316     base::__move_assign_alloc(__c);
1317     splice(end(), __c);
1318 }
1319
1320 #endif  // _LIBCPP_CXX03_LANG
1321
1322 template <class _Tp, class _Alloc>
1323 inline
1324 list<_Tp, _Alloc>&
1325 list<_Tp, _Alloc>::operator=(const list& __c)
1326 {
1327     if (this != &__c)
1328     {
1329         base::__copy_assign_alloc(__c);
1330         assign(__c.begin(), __c.end());
1331     }
1332     return *this;
1333 }
1334
1335 template <class _Tp, class _Alloc>
1336 template <class _InpIter>
1337 void
1338 list<_Tp, _Alloc>::assign(_InpIter __f, _InpIter __l,
1339                           typename enable_if<__is_input_iterator<_InpIter>::value>::type*)
1340 {
1341     iterator __i = begin();
1342     iterator __e = end();
1343     for (; __f != __l && __i != __e; ++__f, ++__i)
1344         *__i = *__f;
1345     if (__i == __e)
1346         insert(__e, __f, __l);
1347     else
1348         erase(__i, __e);
1349 #if _LIBCPP_DEBUG_LEVEL >= 2
1350       __get_db()->__invalidate_all(this);
1351 #endif
1352 }
1353
1354 template <class _Tp, class _Alloc>
1355 void
1356 list<_Tp, _Alloc>::assign(size_type __n, const value_type& __x)
1357 {
1358     iterator __i = begin();
1359     iterator __e = end();
1360     for (; __n > 0 && __i != __e; --__n, ++__i)
1361         *__i = __x;
1362     if (__i == __e)
1363         insert(__e, __n, __x);
1364     else
1365         erase(__i, __e);
1366 #if _LIBCPP_DEBUG_LEVEL >= 2
1367       __get_db()->__invalidate_all(this);
1368 #endif
1369 }
1370
1371 template <class _Tp, class _Alloc>
1372 inline
1373 _Alloc
1374 list<_Tp, _Alloc>::get_allocator() const _NOEXCEPT
1375 {
1376     return allocator_type(base::__node_alloc());
1377 }
1378
1379 template <class _Tp, class _Alloc>
1380 typename list<_Tp, _Alloc>::iterator
1381 list<_Tp, _Alloc>::insert(const_iterator __p, const value_type& __x)
1382 {
1383 #if _LIBCPP_DEBUG_LEVEL >= 2
1384     _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__p) == this,
1385         "list::insert(iterator, x) called with an iterator not"
1386         " referring to this list");
1387 #endif
1388     __node_allocator& __na = base::__node_alloc();
1389     typedef __allocator_destructor<__node_allocator> _Dp;
1390     unique_ptr<__node, _Dp> __hold(__node_alloc_traits::allocate(__na, 1), _Dp(__na, 1));
1391     __hold->__prev_ = 0;
1392     __node_alloc_traits::construct(__na, _VSTD::addressof(__hold->__value_), __x);
1393     __link_nodes(__p.__ptr_, __hold->__as_link(), __hold->__as_link());
1394     ++base::__sz();
1395 #if _LIBCPP_DEBUG_LEVEL >= 2
1396     return iterator(__hold.release()->__as_link(), this);
1397 #else
1398     return iterator(__hold.release()->__as_link());
1399 #endif
1400 }
1401
1402 template <class _Tp, class _Alloc>
1403 typename list<_Tp, _Alloc>::iterator
1404 list<_Tp, _Alloc>::insert(const_iterator __p, size_type __n, const value_type& __x)
1405 {
1406 #if _LIBCPP_DEBUG_LEVEL >= 2
1407     _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__p) == this,
1408         "list::insert(iterator, n, x) called with an iterator not"
1409         " referring to this list");
1410     iterator __r(__p.__ptr_, this);
1411 #else
1412     iterator __r(__p.__ptr_);
1413 #endif
1414     if (__n > 0)
1415     {
1416         size_type __ds = 0;
1417         __node_allocator& __na = base::__node_alloc();
1418         typedef __allocator_destructor<__node_allocator> _Dp;
1419         unique_ptr<__node, _Dp> __hold(__node_alloc_traits::allocate(__na, 1), _Dp(__na, 1));
1420         __hold->__prev_ = 0;
1421         __node_alloc_traits::construct(__na, _VSTD::addressof(__hold->__value_), __x);
1422         ++__ds;
1423 #if _LIBCPP_DEBUG_LEVEL >= 2
1424         __r = iterator(__hold->__as_link(), this);
1425 #else
1426         __r = iterator(__hold->__as_link());
1427 #endif
1428         __hold.release();
1429         iterator __e = __r;
1430 #ifndef _LIBCPP_NO_EXCEPTIONS
1431         try
1432         {
1433 #endif  // _LIBCPP_NO_EXCEPTIONS
1434             for (--__n; __n != 0; --__n, ++__e, ++__ds)
1435             {
1436                 __hold.reset(__node_alloc_traits::allocate(__na, 1));
1437                 __node_alloc_traits::construct(__na, _VSTD::addressof(__hold->__value_), __x);
1438                 __e.__ptr_->__next_ = __hold->__as_link();
1439                 __hold->__prev_ = __e.__ptr_;
1440                 __hold.release();
1441             }
1442 #ifndef _LIBCPP_NO_EXCEPTIONS
1443         }
1444         catch (...)
1445         {
1446             while (true)
1447             {
1448                 __node_alloc_traits::destroy(__na, _VSTD::addressof(*__e));
1449                 __link_pointer __prev = __e.__ptr_->__prev_;
1450                 __node_alloc_traits::deallocate(__na, __e.__ptr_->__as_node(), 1);
1451                 if (__prev == 0)
1452                     break;
1453 #if _LIBCPP_DEBUG_LEVEL >= 2
1454                 __e = iterator(__prev, this);
1455 #else
1456                 __e = iterator(__prev);
1457 #endif
1458             }
1459             throw;
1460         }
1461 #endif  // _LIBCPP_NO_EXCEPTIONS
1462         __link_nodes(__p.__ptr_, __r.__ptr_, __e.__ptr_);
1463         base::__sz() += __ds;
1464     }
1465     return __r;
1466 }
1467
1468 template <class _Tp, class _Alloc>
1469 template <class _InpIter>
1470 typename list<_Tp, _Alloc>::iterator
1471 list<_Tp, _Alloc>::insert(const_iterator __p, _InpIter __f, _InpIter __l,
1472              typename enable_if<__is_input_iterator<_InpIter>::value>::type*)
1473 {
1474 #if _LIBCPP_DEBUG_LEVEL >= 2
1475     _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__p) == this,
1476         "list::insert(iterator, range) called with an iterator not"
1477         " referring to this list");
1478     iterator __r(__p.__ptr_, this);
1479 #else
1480     iterator __r(__p.__ptr_);
1481 #endif
1482     if (__f != __l)
1483     {
1484         size_type __ds = 0;
1485         __node_allocator& __na = base::__node_alloc();
1486         typedef __allocator_destructor<__node_allocator> _Dp;
1487         unique_ptr<__node, _Dp> __hold(__node_alloc_traits::allocate(__na, 1), _Dp(__na, 1));
1488         __hold->__prev_ = 0;
1489         __node_alloc_traits::construct(__na, _VSTD::addressof(__hold->__value_), *__f);
1490         ++__ds;
1491 #if _LIBCPP_DEBUG_LEVEL >= 2
1492         __r = iterator(__hold.get()->__as_link(), this);
1493 #else
1494         __r = iterator(__hold.get()->__as_link());
1495 #endif
1496         __hold.release();
1497         iterator __e = __r;
1498 #ifndef _LIBCPP_NO_EXCEPTIONS
1499         try
1500         {
1501 #endif  // _LIBCPP_NO_EXCEPTIONS
1502             for (++__f; __f != __l; ++__f, (void) ++__e, (void) ++__ds)
1503             {
1504                 __hold.reset(__node_alloc_traits::allocate(__na, 1));
1505                 __node_alloc_traits::construct(__na, _VSTD::addressof(__hold->__value_), *__f);
1506                 __e.__ptr_->__next_ = __hold.get()->__as_link();
1507                 __hold->__prev_ = __e.__ptr_;
1508                 __hold.release();
1509             }
1510 #ifndef _LIBCPP_NO_EXCEPTIONS
1511         }
1512         catch (...)
1513         {
1514             while (true)
1515             {
1516                 __node_alloc_traits::destroy(__na, _VSTD::addressof(*__e));
1517                 __link_pointer __prev = __e.__ptr_->__prev_;
1518                 __node_alloc_traits::deallocate(__na, __e.__ptr_->__as_node(), 1);
1519                 if (__prev == 0)
1520                     break;
1521 #if _LIBCPP_DEBUG_LEVEL >= 2
1522                 __e = iterator(__prev, this);
1523 #else
1524                 __e = iterator(__prev);
1525 #endif
1526             }
1527             throw;
1528         }
1529 #endif  // _LIBCPP_NO_EXCEPTIONS
1530         __link_nodes(__p.__ptr_, __r.__ptr_, __e.__ptr_);
1531         base::__sz() += __ds;
1532     }
1533     return __r;
1534 }
1535
1536 template <class _Tp, class _Alloc>
1537 void
1538 list<_Tp, _Alloc>::push_front(const value_type& __x)
1539 {
1540     __node_allocator& __na = base::__node_alloc();
1541     typedef __allocator_destructor<__node_allocator> _Dp;
1542     unique_ptr<__node, _Dp> __hold(__node_alloc_traits::allocate(__na, 1), _Dp(__na, 1));
1543     __node_alloc_traits::construct(__na, _VSTD::addressof(__hold->__value_), __x);
1544     __link_pointer __nl = __hold->__as_link();
1545     __link_nodes_at_front(__nl, __nl);
1546     ++base::__sz();
1547     __hold.release();
1548 }
1549
1550 template <class _Tp, class _Alloc>
1551 void
1552 list<_Tp, _Alloc>::push_back(const value_type& __x)
1553 {
1554     __node_allocator& __na = base::__node_alloc();
1555     typedef __allocator_destructor<__node_allocator> _Dp;
1556     unique_ptr<__node, _Dp> __hold(__node_alloc_traits::allocate(__na, 1), _Dp(__na, 1));
1557     __node_alloc_traits::construct(__na, _VSTD::addressof(__hold->__value_), __x);
1558     __link_nodes_at_back(__hold.get()->__as_link(), __hold.get()->__as_link());
1559     ++base::__sz();
1560     __hold.release();
1561 }
1562
1563 #ifndef _LIBCPP_CXX03_LANG
1564
1565 template <class _Tp, class _Alloc>
1566 void
1567 list<_Tp, _Alloc>::push_front(value_type&& __x)
1568 {
1569     __node_allocator& __na = base::__node_alloc();
1570     typedef __allocator_destructor<__node_allocator> _Dp;
1571     unique_ptr<__node, _Dp> __hold(__node_alloc_traits::allocate(__na, 1), _Dp(__na, 1));
1572     __node_alloc_traits::construct(__na, _VSTD::addressof(__hold->__value_), _VSTD::move(__x));
1573     __link_nodes_at_front(__hold.get()->__as_link(), __hold.get()->__as_link());
1574     ++base::__sz();
1575     __hold.release();
1576 }
1577
1578 template <class _Tp, class _Alloc>
1579 void
1580 list<_Tp, _Alloc>::push_back(value_type&& __x)
1581 {
1582     __node_allocator& __na = base::__node_alloc();
1583     typedef __allocator_destructor<__node_allocator> _Dp;
1584     unique_ptr<__node, _Dp> __hold(__node_alloc_traits::allocate(__na, 1), _Dp(__na, 1));
1585     __node_alloc_traits::construct(__na, _VSTD::addressof(__hold->__value_), _VSTD::move(__x));
1586     __link_nodes_at_back(__hold.get()->__as_link(), __hold.get()->__as_link());
1587     ++base::__sz();
1588     __hold.release();
1589 }
1590
1591 template <class _Tp, class _Alloc>
1592 template <class... _Args>
1593 #if _LIBCPP_STD_VER > 14
1594 typename list<_Tp, _Alloc>::reference
1595 #else
1596 void
1597 #endif
1598 list<_Tp, _Alloc>::emplace_front(_Args&&... __args)
1599 {
1600     __node_allocator& __na = base::__node_alloc();
1601     typedef __allocator_destructor<__node_allocator> _Dp;
1602     unique_ptr<__node, _Dp> __hold(__node_alloc_traits::allocate(__na, 1), _Dp(__na, 1));
1603     __node_alloc_traits::construct(__na, _VSTD::addressof(__hold->__value_), _VSTD::forward<_Args>(__args)...);
1604     __link_nodes_at_front(__hold.get()->__as_link(), __hold.get()->__as_link());
1605     ++base::__sz();
1606 #if _LIBCPP_STD_VER > 14
1607     return __hold.release()->__value_;
1608 #else
1609     __hold.release();
1610 #endif
1611 }
1612
1613 template <class _Tp, class _Alloc>
1614 template <class... _Args>
1615 #if _LIBCPP_STD_VER > 14
1616 typename list<_Tp, _Alloc>::reference
1617 #else
1618 void
1619 #endif
1620 list<_Tp, _Alloc>::emplace_back(_Args&&... __args)
1621 {
1622     __node_allocator& __na = base::__node_alloc();
1623     typedef __allocator_destructor<__node_allocator> _Dp;
1624     unique_ptr<__node, _Dp> __hold(__node_alloc_traits::allocate(__na, 1), _Dp(__na, 1));
1625     __node_alloc_traits::construct(__na, _VSTD::addressof(__hold->__value_), _VSTD::forward<_Args>(__args)...);
1626     __link_pointer __nl = __hold->__as_link();
1627     __link_nodes_at_back(__nl, __nl);
1628     ++base::__sz();
1629 #if _LIBCPP_STD_VER > 14
1630     return __hold.release()->__value_;
1631 #else
1632     __hold.release();
1633 #endif
1634 }
1635
1636 template <class _Tp, class _Alloc>
1637 template <class... _Args>
1638 typename list<_Tp, _Alloc>::iterator
1639 list<_Tp, _Alloc>::emplace(const_iterator __p, _Args&&... __args)
1640 {
1641 #if _LIBCPP_DEBUG_LEVEL >= 2
1642     _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__p) == this,
1643         "list::emplace(iterator, args...) called with an iterator not"
1644         " referring to this list");
1645 #endif
1646     __node_allocator& __na = base::__node_alloc();
1647     typedef __allocator_destructor<__node_allocator> _Dp;
1648     unique_ptr<__node, _Dp> __hold(__node_alloc_traits::allocate(__na, 1), _Dp(__na, 1));
1649     __hold->__prev_ = 0;
1650     __node_alloc_traits::construct(__na, _VSTD::addressof(__hold->__value_), _VSTD::forward<_Args>(__args)...);
1651     __link_pointer __nl = __hold.get()->__as_link();
1652     __link_nodes(__p.__ptr_, __nl, __nl);
1653     ++base::__sz();
1654     __hold.release();
1655 #if _LIBCPP_DEBUG_LEVEL >= 2
1656     return iterator(__nl, this);
1657 #else
1658     return iterator(__nl);
1659 #endif
1660 }
1661
1662 template <class _Tp, class _Alloc>
1663 typename list<_Tp, _Alloc>::iterator
1664 list<_Tp, _Alloc>::insert(const_iterator __p, value_type&& __x)
1665 {
1666 #if _LIBCPP_DEBUG_LEVEL >= 2
1667     _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__p) == this,
1668         "list::insert(iterator, x) called with an iterator not"
1669         " referring to this list");
1670 #endif
1671     __node_allocator& __na = base::__node_alloc();
1672     typedef __allocator_destructor<__node_allocator> _Dp;
1673     unique_ptr<__node, _Dp> __hold(__node_alloc_traits::allocate(__na, 1), _Dp(__na, 1));
1674     __hold->__prev_ = 0;
1675     __node_alloc_traits::construct(__na, _VSTD::addressof(__hold->__value_), _VSTD::move(__x));
1676     __link_pointer __nl = __hold->__as_link();
1677     __link_nodes(__p.__ptr_, __nl, __nl);
1678     ++base::__sz();
1679     __hold.release();
1680 #if _LIBCPP_DEBUG_LEVEL >= 2
1681     return iterator(__nl, this);
1682 #else
1683     return iterator(__nl);
1684 #endif
1685 }
1686
1687 #endif  // _LIBCPP_CXX03_LANG
1688
1689 template <class _Tp, class _Alloc>
1690 void
1691 list<_Tp, _Alloc>::pop_front()
1692 {
1693     _LIBCPP_ASSERT(!empty(), "list::pop_front() called with empty list");
1694     __node_allocator& __na = base::__node_alloc();
1695     __link_pointer __n = base::__end_.__next_;
1696     base::__unlink_nodes(__n, __n);
1697     --base::__sz();
1698 #if _LIBCPP_DEBUG_LEVEL >= 2
1699     __c_node* __c = __get_db()->__find_c_and_lock(this);
1700     for (__i_node** __p = __c->end_; __p != __c->beg_; )
1701     {
1702         --__p;
1703         iterator* __i = static_cast<iterator*>((*__p)->__i_);
1704         if (__i->__ptr_ == __n)
1705         {
1706             (*__p)->__c_ = nullptr;
1707             if (--__c->end_ != __p)
1708                 memmove(__p, __p+1, (__c->end_ - __p)*sizeof(__i_node*));
1709         }
1710     }
1711     __get_db()->unlock();
1712 #endif
1713     __node_pointer __np = __n->__as_node();
1714     __node_alloc_traits::destroy(__na, _VSTD::addressof(__np->__value_));
1715     __node_alloc_traits::deallocate(__na, __np, 1);
1716 }
1717
1718 template <class _Tp, class _Alloc>
1719 void
1720 list<_Tp, _Alloc>::pop_back()
1721 {
1722     _LIBCPP_ASSERT(!empty(), "list::pop_back() called with empty list");
1723     __node_allocator& __na = base::__node_alloc();
1724     __link_pointer __n = base::__end_.__prev_;
1725     base::__unlink_nodes(__n, __n);
1726     --base::__sz();
1727 #if _LIBCPP_DEBUG_LEVEL >= 2
1728     __c_node* __c = __get_db()->__find_c_and_lock(this);
1729     for (__i_node** __p = __c->end_; __p != __c->beg_; )
1730     {
1731         --__p;
1732         iterator* __i = static_cast<iterator*>((*__p)->__i_);
1733         if (__i->__ptr_ == __n)
1734         {
1735             (*__p)->__c_ = nullptr;
1736             if (--__c->end_ != __p)
1737                 memmove(__p, __p+1, (__c->end_ - __p)*sizeof(__i_node*));
1738         }
1739     }
1740     __get_db()->unlock();
1741 #endif
1742     __node_pointer __np = __n->__as_node();
1743     __node_alloc_traits::destroy(__na, _VSTD::addressof(__np->__value_));
1744     __node_alloc_traits::deallocate(__na, __np, 1);
1745 }
1746
1747 template <class _Tp, class _Alloc>
1748 typename list<_Tp, _Alloc>::iterator
1749 list<_Tp, _Alloc>::erase(const_iterator __p)
1750 {
1751 #if _LIBCPP_DEBUG_LEVEL >= 2
1752     _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__p) == this,
1753         "list::erase(iterator) called with an iterator not"
1754         " referring to this list");
1755 #endif
1756     _LIBCPP_ASSERT(__p != end(),
1757         "list::erase(iterator) called with a non-dereferenceable iterator");
1758     __node_allocator& __na = base::__node_alloc();
1759     __link_pointer __n = __p.__ptr_;
1760     __link_pointer __r = __n->__next_;
1761     base::__unlink_nodes(__n, __n);
1762     --base::__sz();
1763 #if _LIBCPP_DEBUG_LEVEL >= 2
1764     __c_node* __c = __get_db()->__find_c_and_lock(this);
1765     for (__i_node** __ip = __c->end_; __ip != __c->beg_; )
1766     {
1767         --__ip;
1768         iterator* __i = static_cast<iterator*>((*__ip)->__i_);
1769         if (__i->__ptr_ == __n)
1770         {
1771             (*__ip)->__c_ = nullptr;
1772             if (--__c->end_ != __ip)
1773                 memmove(__ip, __ip+1, (__c->end_ - __ip)*sizeof(__i_node*));
1774         }
1775     }
1776     __get_db()->unlock();
1777 #endif
1778     __node_pointer __np = __n->__as_node();
1779     __node_alloc_traits::destroy(__na, _VSTD::addressof(__np->__value_));
1780     __node_alloc_traits::deallocate(__na, __np, 1);
1781 #if _LIBCPP_DEBUG_LEVEL >= 2
1782     return iterator(__r, this);
1783 #else
1784     return iterator(__r);
1785 #endif
1786 }
1787
1788 template <class _Tp, class _Alloc>
1789 typename list<_Tp, _Alloc>::iterator
1790 list<_Tp, _Alloc>::erase(const_iterator __f, const_iterator __l)
1791 {
1792 #if _LIBCPP_DEBUG_LEVEL >= 2
1793     _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__f) == this,
1794         "list::erase(iterator, iterator) called with an iterator not"
1795         " referring to this list");
1796    _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__l) == this,
1797         "list::erase(iterator, iterator) called with an iterator not"
1798         " referring to this list");
1799 #endif
1800     if (__f != __l)
1801     {
1802         __node_allocator& __na = base::__node_alloc();
1803         base::__unlink_nodes(__f.__ptr_, __l.__ptr_->__prev_);
1804         while (__f != __l)
1805         {
1806             __link_pointer __n = __f.__ptr_;
1807             ++__f;
1808             --base::__sz();
1809 #if _LIBCPP_DEBUG_LEVEL >= 2
1810             __c_node* __c = __get_db()->__find_c_and_lock(this);
1811             for (__i_node** __p = __c->end_; __p != __c->beg_; )
1812             {
1813                 --__p;
1814                 iterator* __i = static_cast<iterator*>((*__p)->__i_);
1815                 if (__i->__ptr_ == __n)
1816                 {
1817                     (*__p)->__c_ = nullptr;
1818                     if (--__c->end_ != __p)
1819                         memmove(__p, __p+1, (__c->end_ - __p)*sizeof(__i_node*));
1820                 }
1821             }
1822             __get_db()->unlock();
1823 #endif
1824             __node_pointer __np = __n->__as_node();
1825             __node_alloc_traits::destroy(__na, _VSTD::addressof(__np->__value_));
1826             __node_alloc_traits::deallocate(__na, __np, 1);
1827         }
1828     }
1829 #if _LIBCPP_DEBUG_LEVEL >= 2
1830     return iterator(__l.__ptr_, this);
1831 #else
1832     return iterator(__l.__ptr_);
1833 #endif
1834 }
1835
1836 template <class _Tp, class _Alloc>
1837 void
1838 list<_Tp, _Alloc>::resize(size_type __n)
1839 {
1840     if (__n < base::__sz())
1841         erase(__iterator(__n), end());
1842     else if (__n > base::__sz())
1843     {
1844         __n -= base::__sz();
1845         size_type __ds = 0;
1846         __node_allocator& __na = base::__node_alloc();
1847         typedef __allocator_destructor<__node_allocator> _Dp;
1848         unique_ptr<__node, _Dp> __hold(__node_alloc_traits::allocate(__na, 1), _Dp(__na, 1));
1849         __hold->__prev_ = 0;
1850         __node_alloc_traits::construct(__na, _VSTD::addressof(__hold->__value_));
1851         ++__ds;
1852 #if _LIBCPP_DEBUG_LEVEL >= 2
1853         iterator __r = iterator(__hold.release()->__as_link(), this);
1854 #else
1855         iterator __r = iterator(__hold.release()->__as_link());
1856 #endif
1857         iterator __e = __r;
1858 #ifndef _LIBCPP_NO_EXCEPTIONS
1859         try
1860         {
1861 #endif  // _LIBCPP_NO_EXCEPTIONS
1862             for (--__n; __n != 0; --__n, ++__e, ++__ds)
1863             {
1864                 __hold.reset(__node_alloc_traits::allocate(__na, 1));
1865                 __node_alloc_traits::construct(__na, _VSTD::addressof(__hold->__value_));
1866                 __e.__ptr_->__next_ = __hold.get()->__as_link();
1867                 __hold->__prev_ = __e.__ptr_;
1868                 __hold.release();
1869             }
1870 #ifndef _LIBCPP_NO_EXCEPTIONS
1871         }
1872         catch (...)
1873         {
1874             while (true)
1875             {
1876                 __node_alloc_traits::destroy(__na, _VSTD::addressof(*__e));
1877                 __link_pointer __prev = __e.__ptr_->__prev_;
1878                 __node_alloc_traits::deallocate(__na, __e.__ptr_->__as_node(), 1);
1879                 if (__prev == 0)
1880                     break;
1881 #if _LIBCPP_DEBUG_LEVEL >= 2
1882                 __e = iterator(__prev, this);
1883 #else
1884                 __e = iterator(__prev);
1885 #endif
1886             }
1887             throw;
1888         }
1889 #endif  // _LIBCPP_NO_EXCEPTIONS
1890         __link_nodes_at_back(__r.__ptr_, __e.__ptr_);
1891         base::__sz() += __ds;
1892     }
1893 }
1894
1895 template <class _Tp, class _Alloc>
1896 void
1897 list<_Tp, _Alloc>::resize(size_type __n, const value_type& __x)
1898 {
1899     if (__n < base::__sz())
1900         erase(__iterator(__n), end());
1901     else if (__n > base::__sz())
1902     {
1903         __n -= base::__sz();
1904         size_type __ds = 0;
1905         __node_allocator& __na = base::__node_alloc();
1906         typedef __allocator_destructor<__node_allocator> _Dp;
1907         unique_ptr<__node, _Dp> __hold(__node_alloc_traits::allocate(__na, 1), _Dp(__na, 1));
1908         __hold->__prev_ = 0;
1909         __node_alloc_traits::construct(__na, _VSTD::addressof(__hold->__value_), __x);
1910         ++__ds;
1911         __link_pointer __nl = __hold.release()->__as_link();
1912 #if _LIBCPP_DEBUG_LEVEL >= 2
1913         iterator __r = iterator(__nl, this);
1914 #else
1915         iterator __r = iterator(__nl);
1916 #endif
1917         iterator __e = __r;
1918 #ifndef _LIBCPP_NO_EXCEPTIONS
1919         try
1920         {
1921 #endif  // _LIBCPP_NO_EXCEPTIONS
1922             for (--__n; __n != 0; --__n, ++__e, ++__ds)
1923             {
1924                 __hold.reset(__node_alloc_traits::allocate(__na, 1));
1925                 __node_alloc_traits::construct(__na, _VSTD::addressof(__hold->__value_), __x);
1926                 __e.__ptr_->__next_ = __hold.get()->__as_link();
1927                 __hold->__prev_ = __e.__ptr_;
1928                 __hold.release();
1929             }
1930 #ifndef _LIBCPP_NO_EXCEPTIONS
1931         }
1932         catch (...)
1933         {
1934             while (true)
1935             {
1936                 __node_alloc_traits::destroy(__na, _VSTD::addressof(*__e));
1937                 __link_pointer __prev = __e.__ptr_->__prev_;
1938                 __node_alloc_traits::deallocate(__na, __e.__ptr_->__as_node(), 1);
1939                 if (__prev == 0)
1940                     break;
1941 #if _LIBCPP_DEBUG_LEVEL >= 2
1942                 __e = iterator(__prev, this);
1943 #else
1944                 __e = iterator(__prev);
1945 #endif
1946             }
1947             throw;
1948         }
1949 #endif  // _LIBCPP_NO_EXCEPTIONS
1950         __link_nodes(base::__end_as_link(), __r.__ptr_, __e.__ptr_);
1951         base::__sz() += __ds;
1952     }
1953 }
1954
1955 template <class _Tp, class _Alloc>
1956 void
1957 list<_Tp, _Alloc>::splice(const_iterator __p, list& __c)
1958 {
1959     _LIBCPP_ASSERT(this != &__c,
1960                    "list::splice(iterator, list) called with this == &list");
1961 #if _LIBCPP_DEBUG_LEVEL >= 2
1962     _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__p) == this,
1963         "list::splice(iterator, list) called with an iterator not"
1964         " referring to this list");
1965 #endif
1966     if (!__c.empty())
1967     {
1968         __link_pointer __f = __c.__end_.__next_;
1969         __link_pointer __l = __c.__end_.__prev_;
1970         base::__unlink_nodes(__f, __l);
1971         __link_nodes(__p.__ptr_, __f, __l);
1972         base::__sz() += __c.__sz();
1973         __c.__sz() = 0;
1974 #if _LIBCPP_DEBUG_LEVEL >= 2
1975         __libcpp_db* __db = __get_db();
1976         __c_node* __cn1 = __db->__find_c_and_lock(this);
1977         __c_node* __cn2 = __db->__find_c(&__c);
1978         for (__i_node** __ip = __cn2->end_; __ip != __cn2->beg_;)
1979         {
1980             --__ip;
1981             iterator* __i = static_cast<iterator*>((*__ip)->__i_);
1982             if (__i->__ptr_ != __c.__end_as_link())
1983             {
1984                 __cn1->__add(*__ip);
1985                 (*__ip)->__c_ = __cn1;
1986                 if (--__cn2->end_ != __ip)
1987                     memmove(__ip, __ip+1, (__cn2->end_ - __ip)*sizeof(__i_node*));
1988             }
1989         }
1990         __db->unlock();
1991 #endif
1992     }
1993 }
1994
1995 template <class _Tp, class _Alloc>
1996 void
1997 list<_Tp, _Alloc>::splice(const_iterator __p, list& __c, const_iterator __i)
1998 {
1999 #if _LIBCPP_DEBUG_LEVEL >= 2
2000     _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__p) == this,
2001         "list::splice(iterator, list, iterator) called with first iterator not"
2002         " referring to this list");
2003     _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__i) == &__c,
2004         "list::splice(iterator, list, iterator) called with second iterator not"
2005         " referring to list argument");
2006     _LIBCPP_ASSERT(__get_const_db()->__dereferenceable(&__i),
2007         "list::splice(iterator, list, iterator) called with second iterator not"
2008         " derefereceable");
2009 #endif
2010     if (__p.__ptr_ != __i.__ptr_ && __p.__ptr_ != __i.__ptr_->__next_)
2011     {
2012         __link_pointer __f = __i.__ptr_;
2013         base::__unlink_nodes(__f, __f);
2014         __link_nodes(__p.__ptr_, __f, __f);
2015         --__c.__sz();
2016         ++base::__sz();
2017 #if _LIBCPP_DEBUG_LEVEL >= 2
2018         __libcpp_db* __db = __get_db();
2019         __c_node* __cn1 = __db->__find_c_and_lock(this);
2020         __c_node* __cn2 = __db->__find_c(&__c);
2021         for (__i_node** __ip = __cn2->end_; __ip != __cn2->beg_;)
2022         {
2023             --__ip;
2024             iterator* __j = static_cast<iterator*>((*__ip)->__i_);
2025             if (__j->__ptr_ == __f)
2026             {
2027                 __cn1->__add(*__ip);
2028                 (*__ip)->__c_ = __cn1;
2029                 if (--__cn2->end_ != __ip)
2030                     memmove(__ip, __ip+1, (__cn2->end_ - __ip)*sizeof(__i_node*));
2031             }
2032         }
2033         __db->unlock();
2034 #endif
2035     }
2036 }
2037
2038 template <class _Tp, class _Alloc>
2039 void
2040 list<_Tp, _Alloc>::splice(const_iterator __p, list& __c, const_iterator __f, const_iterator __l)
2041 {
2042 #if _LIBCPP_DEBUG_LEVEL >= 2
2043     _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__p) == this,
2044         "list::splice(iterator, list, iterator, iterator) called with first iterator not"
2045         " referring to this list");
2046     _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__f) == &__c,
2047         "list::splice(iterator, list, iterator, iterator) called with second iterator not"
2048         " referring to list argument");
2049     if (this == &__c)
2050     {
2051         for (const_iterator __i = __f; __i != __l; ++__i)
2052             _LIBCPP_ASSERT(__i != __p,
2053                            "list::splice(iterator, list, iterator, iterator)"
2054                            " called with the first iterator within the range"
2055                            " of the second and third iterators");
2056     }
2057 #endif
2058     if (__f != __l)
2059     {
2060         if (this != &__c)
2061         {
2062             size_type __s = _VSTD::distance(__f, __l);
2063             __c.__sz() -= __s;
2064             base::__sz() += __s;
2065         }
2066         __link_pointer __first = __f.__ptr_;
2067         --__l;
2068         __link_pointer __last = __l.__ptr_;
2069         base::__unlink_nodes(__first, __last);
2070         __link_nodes(__p.__ptr_, __first, __last);
2071 #if _LIBCPP_DEBUG_LEVEL >= 2
2072         __libcpp_db* __db = __get_db();
2073         __c_node* __cn1 = __db->__find_c_and_lock(this);
2074         __c_node* __cn2 = __db->__find_c(&__c);
2075         for (__i_node** __ip = __cn2->end_; __ip != __cn2->beg_;)
2076         {
2077             --__ip;
2078             iterator* __j = static_cast<iterator*>((*__ip)->__i_);
2079             for (__link_pointer __k = __f.__ptr_;
2080                                           __k != __l.__ptr_; __k = __k->__next_)
2081             {
2082                 if (__j->__ptr_ == __k)
2083                 {
2084                     __cn1->__add(*__ip);
2085                     (*__ip)->__c_ = __cn1;
2086                     if (--__cn2->end_ != __ip)
2087                         memmove(__ip, __ip+1, (__cn2->end_ - __ip)*sizeof(__i_node*));
2088                 }
2089             }
2090         }
2091         __db->unlock();
2092 #endif
2093     }
2094 }
2095
2096 template <class _Tp, class _Alloc>
2097 void
2098 list<_Tp, _Alloc>::remove(const value_type& __x)
2099 {
2100     list<_Tp, _Alloc> __deleted_nodes(get_allocator()); // collect the nodes we're removing
2101     for (const_iterator __i = begin(), __e = end(); __i != __e;)
2102     {
2103         if (*__i == __x)
2104         {
2105             const_iterator __j = _VSTD::next(__i);
2106             for (; __j != __e && *__j == __x; ++__j)
2107                 ;
2108             __deleted_nodes.splice(__deleted_nodes.end(), *this, __i, __j);
2109             __i = __j;
2110             if (__i != __e)
2111                 ++__i;
2112         }
2113         else
2114             ++__i;
2115     }
2116 }
2117
2118 template <class _Tp, class _Alloc>
2119 template <class _Pred>
2120 void
2121 list<_Tp, _Alloc>::remove_if(_Pred __pred)
2122 {
2123     for (iterator __i = begin(), __e = end(); __i != __e;)
2124     {
2125         if (__pred(*__i))
2126         {
2127             iterator __j = _VSTD::next(__i);
2128             for (; __j != __e && __pred(*__j); ++__j)
2129                 ;
2130             __i = erase(__i, __j);
2131             if (__i != __e)
2132                 ++__i;
2133         }
2134         else
2135             ++__i;
2136     }
2137 }
2138
2139 template <class _Tp, class _Alloc>
2140 inline
2141 void
2142 list<_Tp, _Alloc>::unique()
2143 {
2144     unique(__equal_to<value_type>());
2145 }
2146
2147 template <class _Tp, class _Alloc>
2148 template <class _BinaryPred>
2149 void
2150 list<_Tp, _Alloc>::unique(_BinaryPred __binary_pred)
2151 {
2152     for (iterator __i = begin(), __e = end(); __i != __e;)
2153     {
2154         iterator __j = _VSTD::next(__i);
2155         for (; __j != __e && __binary_pred(*__i, *__j); ++__j)
2156             ;
2157         if (++__i != __j)
2158             __i = erase(__i, __j);
2159     }
2160 }
2161
2162 template <class _Tp, class _Alloc>
2163 inline
2164 void
2165 list<_Tp, _Alloc>::merge(list& __c)
2166 {
2167     merge(__c, __less<value_type>());
2168 }
2169
2170 template <class _Tp, class _Alloc>
2171 template <class _Comp>
2172 void
2173 list<_Tp, _Alloc>::merge(list& __c, _Comp __comp)
2174 {
2175     if (this != &__c)
2176     {
2177         iterator __f1 = begin();
2178         iterator __e1 = end();
2179         iterator __f2 = __c.begin();
2180         iterator __e2 = __c.end();
2181         while (__f1 != __e1 && __f2 != __e2)
2182         {
2183             if (__comp(*__f2, *__f1))
2184             {
2185                 size_type __ds = 1;
2186                 iterator __m2 = _VSTD::next(__f2);
2187                 for (; __m2 != __e2 && __comp(*__m2, *__f1); ++__m2, ++__ds)
2188                     ;
2189                 base::__sz() += __ds;
2190                 __c.__sz() -= __ds;
2191                 __link_pointer __f = __f2.__ptr_;
2192                 __link_pointer __l = __m2.__ptr_->__prev_;
2193                 __f2 = __m2;
2194                 base::__unlink_nodes(__f, __l);
2195                 __m2 = _VSTD::next(__f1);
2196                 __link_nodes(__f1.__ptr_, __f, __l);
2197                 __f1 = __m2;
2198             }
2199             else
2200                 ++__f1;
2201         }
2202         splice(__e1, __c);
2203 #if _LIBCPP_DEBUG_LEVEL >= 2
2204         __libcpp_db* __db = __get_db();
2205         __c_node* __cn1 = __db->__find_c_and_lock(this);
2206         __c_node* __cn2 = __db->__find_c(&__c);
2207         for (__i_node** __p = __cn2->end_; __p != __cn2->beg_;)
2208         {
2209             --__p;
2210             iterator* __i = static_cast<iterator*>((*__p)->__i_);
2211             if (__i->__ptr_ != __c.__end_as_link())
2212             {
2213                 __cn1->__add(*__p);
2214                 (*__p)->__c_ = __cn1;
2215                 if (--__cn2->end_ != __p)
2216                     memmove(__p, __p+1, (__cn2->end_ - __p)*sizeof(__i_node*));
2217             }
2218         }
2219         __db->unlock();
2220 #endif
2221     }
2222 }
2223
2224 template <class _Tp, class _Alloc>
2225 inline
2226 void
2227 list<_Tp, _Alloc>::sort()
2228 {
2229     sort(__less<value_type>());
2230 }
2231
2232 template <class _Tp, class _Alloc>
2233 template <class _Comp>
2234 inline
2235 void
2236 list<_Tp, _Alloc>::sort(_Comp __comp)
2237 {
2238     __sort(begin(), end(), base::__sz(), __comp);
2239 }
2240
2241 template <class _Tp, class _Alloc>
2242 template <class _Comp>
2243 typename list<_Tp, _Alloc>::iterator
2244 list<_Tp, _Alloc>::__sort(iterator __f1, iterator __e2, size_type __n, _Comp& __comp)
2245 {
2246     switch (__n)
2247     {
2248     case 0:
2249     case 1:
2250         return __f1;
2251     case 2:
2252         if (__comp(*--__e2, *__f1))
2253         {
2254             __link_pointer __f = __e2.__ptr_;
2255             base::__unlink_nodes(__f, __f);
2256             __link_nodes(__f1.__ptr_, __f, __f);
2257             return __e2;
2258         }
2259         return __f1;
2260     }
2261     size_type __n2 = __n / 2;
2262     iterator __e1 = _VSTD::next(__f1, __n2);
2263     iterator  __r = __f1 = __sort(__f1, __e1, __n2, __comp);
2264     iterator __f2 = __e1 = __sort(__e1, __e2, __n - __n2, __comp);
2265     if (__comp(*__f2, *__f1))
2266     {
2267         iterator __m2 = _VSTD::next(__f2);
2268         for (; __m2 != __e2 && __comp(*__m2, *__f1); ++__m2)
2269             ;
2270         __link_pointer __f = __f2.__ptr_;
2271         __link_pointer __l = __m2.__ptr_->__prev_;
2272         __r = __f2;
2273         __e1 = __f2 = __m2;
2274         base::__unlink_nodes(__f, __l);
2275         __m2 = _VSTD::next(__f1);
2276         __link_nodes(__f1.__ptr_, __f, __l);
2277         __f1 = __m2;
2278     }
2279     else
2280         ++__f1;
2281     while (__f1 != __e1 && __f2 != __e2)
2282     {
2283         if (__comp(*__f2, *__f1))
2284         {
2285             iterator __m2 = _VSTD::next(__f2);
2286             for (; __m2 != __e2 && __comp(*__m2, *__f1); ++__m2)
2287                 ;
2288             __link_pointer __f = __f2.__ptr_;
2289             __link_pointer __l = __m2.__ptr_->__prev_;
2290             if (__e1 == __f2)
2291                 __e1 = __m2;
2292             __f2 = __m2;
2293             base::__unlink_nodes(__f, __l);
2294             __m2 = _VSTD::next(__f1);
2295             __link_nodes(__f1.__ptr_, __f, __l);
2296             __f1 = __m2;
2297         }
2298         else
2299             ++__f1;
2300     }
2301     return __r;
2302 }
2303
2304 template <class _Tp, class _Alloc>
2305 void
2306 list<_Tp, _Alloc>::reverse() _NOEXCEPT
2307 {
2308     if (base::__sz() > 1)
2309     {
2310         iterator __e = end();
2311         for (iterator __i = begin(); __i.__ptr_ != __e.__ptr_;)
2312         {
2313             _VSTD::swap(__i.__ptr_->__prev_, __i.__ptr_->__next_);
2314             __i.__ptr_ = __i.__ptr_->__prev_;
2315         }
2316         _VSTD::swap(__e.__ptr_->__prev_, __e.__ptr_->__next_);
2317     }
2318 }
2319
2320 template <class _Tp, class _Alloc>
2321 bool
2322 list<_Tp, _Alloc>::__invariants() const
2323 {
2324     return size() == _VSTD::distance(begin(), end());
2325 }
2326
2327 #if _LIBCPP_DEBUG_LEVEL >= 2
2328
2329 template <class _Tp, class _Alloc>
2330 bool
2331 list<_Tp, _Alloc>::__dereferenceable(const const_iterator* __i) const
2332 {
2333     return __i->__ptr_ != this->__end_as_link();
2334 }
2335
2336 template <class _Tp, class _Alloc>
2337 bool
2338 list<_Tp, _Alloc>::__decrementable(const const_iterator* __i) const
2339 {
2340     return !empty() &&  __i->__ptr_ != base::__end_.__next_;
2341 }
2342
2343 template <class _Tp, class _Alloc>
2344 bool
2345 list<_Tp, _Alloc>::__addable(const const_iterator*, ptrdiff_t) const
2346 {
2347     return false;
2348 }
2349
2350 template <class _Tp, class _Alloc>
2351 bool
2352 list<_Tp, _Alloc>::__subscriptable(const const_iterator*, ptrdiff_t) const
2353 {
2354     return false;
2355 }
2356
2357 #endif  // _LIBCPP_DEBUG_LEVEL >= 2
2358
2359 template <class _Tp, class _Alloc>
2360 inline _LIBCPP_INLINE_VISIBILITY
2361 bool
2362 operator==(const list<_Tp, _Alloc>& __x, const list<_Tp, _Alloc>& __y)
2363 {
2364     return __x.size() == __y.size() && _VSTD::equal(__x.begin(), __x.end(), __y.begin());
2365 }
2366
2367 template <class _Tp, class _Alloc>
2368 inline _LIBCPP_INLINE_VISIBILITY
2369 bool
2370 operator< (const list<_Tp, _Alloc>& __x, const list<_Tp, _Alloc>& __y)
2371 {
2372     return _VSTD::lexicographical_compare(__x.begin(), __x.end(), __y.begin(), __y.end());
2373 }
2374
2375 template <class _Tp, class _Alloc>
2376 inline _LIBCPP_INLINE_VISIBILITY
2377 bool
2378 operator!=(const list<_Tp, _Alloc>& __x, const list<_Tp, _Alloc>& __y)
2379 {
2380     return !(__x == __y);
2381 }
2382
2383 template <class _Tp, class _Alloc>
2384 inline _LIBCPP_INLINE_VISIBILITY
2385 bool
2386 operator> (const list<_Tp, _Alloc>& __x, const list<_Tp, _Alloc>& __y)
2387 {
2388     return __y < __x;
2389 }
2390
2391 template <class _Tp, class _Alloc>
2392 inline _LIBCPP_INLINE_VISIBILITY
2393 bool
2394 operator>=(const list<_Tp, _Alloc>& __x, const list<_Tp, _Alloc>& __y)
2395 {
2396     return !(__x < __y);
2397 }
2398
2399 template <class _Tp, class _Alloc>
2400 inline _LIBCPP_INLINE_VISIBILITY
2401 bool
2402 operator<=(const list<_Tp, _Alloc>& __x, const list<_Tp, _Alloc>& __y)
2403 {
2404     return !(__y < __x);
2405 }
2406
2407 template <class _Tp, class _Alloc>
2408 inline _LIBCPP_INLINE_VISIBILITY
2409 void
2410 swap(list<_Tp, _Alloc>& __x, list<_Tp, _Alloc>& __y)
2411     _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y)))
2412 {
2413     __x.swap(__y);
2414 }
2415
2416 _LIBCPP_END_NAMESPACE_STD
2417
2418 #endif  // _LIBCPP_LIST