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