include/list

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