headers/libs/libc++/list

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