contrib/libc++/include/list

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