libcxx/include/list

   1 // -*- C++ -*-
   2 //===----------------------------------------------------------------------===//
   3 //
   4 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
   5 // See https://llvm.org/LICENSE.txt for license information.
   6 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
   7 //
   8 //===----------------------------------------------------------------------===//
   9
  10 #ifndef _LIBCPP_LIST
  11 #define _LIBCPP_LIST
  12
  13 /*
  14     list synopsis
  15
  16 namespace std
  17 {
  18
  19 template <class T, class Alloc = allocator<T> >
  20 class list
  21 {
  22 public:
  23
  24     // types:
  25     typedef T value_type;
  26     typedef Alloc allocator_type;
  27     typedef typename allocator_type::reference reference;
  28     typedef typename allocator_type::const_reference const_reference;
  29     typedef typename allocator_type::pointer pointer;
  30     typedef typename allocator_type::const_pointer const_pointer;
  31     typedef implementation-defined iterator;
  32     typedef implementation-defined const_iterator;
  33     typedef implementation-defined size_type;
  34     typedef implementation-defined difference_type;
  35     typedef reverse_iterator<iterator> reverse_iterator;
  36     typedef reverse_iterator<const_iterator> const_reverse_iterator;
  37
  38     list()
  39         noexcept(is_nothrow_default_constructible<allocator_type>::value);
  40     explicit list(const allocator_type& a);
  41     explicit list(size_type n);
  42     explicit list(size_type n, const allocator_type& a); // C++14
  43     list(size_type n, const value_type& value);
  44     list(size_type n, const value_type& value, const allocator_type& a);
  45     template <class Iter>
  46         list(Iter first, Iter last);
  47     template <class Iter>
  48         list(Iter first, Iter last, const allocator_type& a);
  49     template<container-compatible-range<T> R>
  50       list(from_range_t, R&& rg, const Allocator& = Allocator()); // C++23
  51     list(const list& x);
  52     list(const list&, const allocator_type& a);
  53     list(list&& x)
  54         noexcept(is_nothrow_move_constructible<allocator_type>::value);
  55     list(list&&, const allocator_type& a);
  56     list(initializer_list<value_type>);
  57     list(initializer_list<value_type>, const allocator_type& a);
  58
  59     ~list();
  60
  61     list& operator=(const list& x);
  62     list& operator=(list&& x)
  63         noexcept(
  64              allocator_type::propagate_on_container_move_assignment::value &&
  65              is_nothrow_move_assignable<allocator_type>::value);
  66     list& operator=(initializer_list<value_type>);
  67     template <class Iter>
  68         void assign(Iter first, Iter last);
  69     template<container-compatible-range<T> R>
  70       void assign_range(R&& rg); // C++23
  71     void assign(size_type n, const value_type& t);
  72     void assign(initializer_list<value_type>);
  73
  74     allocator_type get_allocator() const noexcept;
  75
  76     iterator begin() noexcept;
  77     const_iterator begin() const noexcept;
  78     iterator end() noexcept;
  79     const_iterator end() const noexcept;
  80     reverse_iterator rbegin() noexcept;
  81     const_reverse_iterator rbegin() const noexcept;
  82     reverse_iterator rend() noexcept;
  83     const_reverse_iterator rend() const noexcept;
  84     const_iterator cbegin() const noexcept;
  85     const_iterator cend() const noexcept;
  86     const_reverse_iterator crbegin() const noexcept;
  87     const_reverse_iterator crend() const noexcept;
  88
  89     reference front();
  90     const_reference front() const;
  91     reference back();
  92     const_reference back() const;
  93
  94     bool empty() const noexcept;
  95     size_type size() const noexcept;
  96     size_type max_size() const noexcept;
  97
  98     template <class... Args>
  99         reference emplace_front(Args&&... args); // reference in C++17
 100     void pop_front();
 101     template <class... Args>
 102         reference emplace_back(Args&&... args);  // reference in C++17
 103     void pop_back();
 104     void push_front(const value_type& x);
 105     void push_front(value_type&& x);
 106     template<container-compatible-range<T> R>
 107       void prepend_range(R&& rg); // C++23
 108     void push_back(const value_type& x);
 109     void push_back(value_type&& x);
 110     template<container-compatible-range<T> R>
 111       void append_range(R&& rg); // C++23
 112     template <class... Args>
 113         iterator emplace(const_iterator position, Args&&... args);
 114     iterator insert(const_iterator position, const value_type& x);
 115     iterator insert(const_iterator position, value_type&& x);
 116     iterator insert(const_iterator position, size_type n, const value_type& x);
 117     template <class Iter>
 118         iterator insert(const_iterator position, Iter first, Iter last);
 119     template<container-compatible-range<T> R>
 120       iterator insert_range(const_iterator position, R&& rg); // C++23
 121     iterator insert(const_iterator position, initializer_list<value_type> il);
 122
 123     iterator erase(const_iterator position);
 124     iterator erase(const_iterator position, const_iterator last);
 125
 126     void resize(size_type sz);
 127     void resize(size_type sz, const value_type& c);
 128
 129     void swap(list&)
 130         noexcept(allocator_traits<allocator_type>::is_always_equal::value);  // C++17
 131     void clear() noexcept;
 132
 133     void splice(const_iterator position, list& x);
 134     void splice(const_iterator position, list&& x);
 135     void splice(const_iterator position, list& x, const_iterator i);
 136     void splice(const_iterator position, list&& x, const_iterator i);
 137     void splice(const_iterator position, list& x, const_iterator first,
 138                                                   const_iterator last);
 139     void splice(const_iterator position, list&& x, const_iterator first,
 140                                                   const_iterator last);
 141
 142     size_type remove(const value_type& value);       // void before C++20
 143     template <class Pred>
 144       size_type remove_if(Pred pred);                // void before C++20
 145     size_type unique();                              // void before C++20
 146     template <class BinaryPredicate>
 147       size_type unique(BinaryPredicate binary_pred); // void before C++20
 148     void merge(list& x);
 149     void merge(list&& x);
 150     template <class Compare>
 151         void merge(list& x, Compare comp);
 152     template <class Compare>
 153         void merge(list&& x, Compare comp);
 154     void sort();
 155     template <class Compare>
 156         void sort(Compare comp);
 157     void reverse() noexcept;
 158 };
 159
 160
 161 template <class InputIterator, class Allocator = allocator<typename iterator_traits<InputIterator>::value_type>>
 162     list(InputIterator, InputIterator, Allocator = Allocator())
 163     -> list<typename iterator_traits<InputIterator>::value_type, Allocator>;  // C++17
 164
 165 template<ranges::input_range R, class Allocator = allocator<ranges::range_value_t<R>>>
 166   list(from_range_t, R&&, Allocator = Allocator())
 167     -> list<ranges::range_value_t<R>, Allocator>; // C++23
 168
 169 template <class T, class Alloc>
 170     bool operator==(const list<T,Alloc>& x, const list<T,Alloc>& y);
 171 template <class T, class Alloc>
 172     bool operator< (const list<T,Alloc>& x, const list<T,Alloc>& y);     // removed in C++20
 173 template <class T, class Alloc>
 174     bool operator!=(const list<T,Alloc>& x, const list<T,Alloc>& y);     // removed in C++20
 175 template <class T, class Alloc>
 176     bool operator> (const list<T,Alloc>& x, const list<T,Alloc>& y);     // removed in C++20
 177 template <class T, class Alloc>
 178     bool operator>=(const list<T,Alloc>& x, const list<T,Alloc>& y);     // removed in C++20
 179 template <class T, class Alloc>
 180     bool operator<=(const list<T,Alloc>& x, const list<T,Alloc>& y);     // removed in C++20
 181 template<class T, class Allocator>
 182   synth-three-way-result<T> operator<=>(const list<T, Allocator>& x,
 183                                         const list<T, Allocator>& y);    // since C++20
 184
 185 template <class T, class Alloc>
 186     void swap(list<T,Alloc>& x, list<T,Alloc>& y)
 187          noexcept(noexcept(x.swap(y)));
 188
 189 template <class T, class Allocator, class U>
 190     typename list<T, Allocator>::size_type
 191     erase(list<T, Allocator>& c, const U& value);       // since C++20
 192 template <class T, class Allocator, class Predicate>
 193     typename list<T, Allocator>::size_type
 194     erase_if(list<T, Allocator>& c, Predicate pred);    // since C++20
 195
 196 }  // std
 197
 198 */
 199
 200 #include <__algorithm/comp.h>
 201 #include <__algorithm/equal.h>
 202 #include <__algorithm/lexicographical_compare.h>
 203 #include <__algorithm/lexicographical_compare_three_way.h>
 204 #include <__algorithm/min.h>
 205 #include <__assert> // all public C++ headers provide the assertion handler
 206 #include <__availability>
 207 #include <__config>
 208 #include <__format/enable_insertable.h>
 209 #include <__iterator/distance.h>
 210 #include <__iterator/iterator_traits.h>
 211 #include <__iterator/move_iterator.h>
 212 #include <__iterator/next.h>
 213 #include <__iterator/prev.h>
 214 #include <__iterator/reverse_iterator.h>
 215 #include <__memory/addressof.h>
 216 #include <__memory/allocation_guard.h>
 217 #include <__memory/allocator.h>
 218 #include <__memory/allocator_traits.h>
 219 #include <__memory/compressed_pair.h>
 220 #include <__memory/construct_at.h>
 221 #include <__memory/pointer_traits.h>
 222 #include <__memory/swap_allocator.h>
 223 #include <__memory_resource/polymorphic_allocator.h>
 224 #include <__ranges/access.h>
 225 #include <__ranges/concepts.h>
 226 #include <__ranges/container_compatible_range.h>
 227 #include <__ranges/from_range.h>
 228 #include <__type_traits/conditional.h>
 229 #include <__type_traits/is_allocator.h>
 230 #include <__type_traits/is_nothrow_default_constructible.h>
 231 #include <__type_traits/is_nothrow_move_assignable.h>
 232 #include <__type_traits/is_nothrow_move_constructible.h>
 233 #include <__type_traits/is_pointer.h>
 234 #include <__type_traits/is_same.h>
 235 #include <__type_traits/type_identity.h>
 236 #include <__utility/forward.h>
 237 #include <__utility/move.h>
 238 #include <__utility/swap.h>
 239 #include <cstring>
 240 #include <limits>
 241 #include <new> // __launder
 242 #include <version>
 243
 244 // standard-mandated includes
 245
 246 // [iterator.range]
 247 #include <__iterator/access.h>
 248 #include <__iterator/data.h>
 249 #include <__iterator/empty.h>
 250 #include <__iterator/reverse_access.h>
 251 #include <__iterator/size.h>
 252
 253 // [list.syn]
 254 #include <compare>
 255 #include <initializer_list>
 256
 257 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
 258 #  pragma GCC system_header
 259 #endif
 260
 261 _LIBCPP_PUSH_MACROS
 262 #include <__undef_macros>
 263
 264
 265 _LIBCPP_BEGIN_NAMESPACE_STD
 266
 267 template <class _Tp, class _VoidPtr> struct __list_node;
 268 template <class _Tp, class _VoidPtr> struct __list_node_base;
 269
 270 template <class _Tp, class _VoidPtr>
 271 struct __list_node_pointer_traits {
 272   typedef __rebind_pointer_t<_VoidPtr, __list_node<_Tp, _VoidPtr> >
 273         __node_pointer;
 274   typedef __rebind_pointer_t<_VoidPtr, __list_node_base<_Tp, _VoidPtr> >
 275         __base_pointer;
 276
 277 #if defined(_LIBCPP_ABI_LIST_REMOVE_NODE_POINTER_UB)
 278   typedef __base_pointer __link_pointer;
 279 #else
 280   typedef __conditional_t<is_pointer<_VoidPtr>::value, __base_pointer, __node_pointer> __link_pointer;
 281 #endif
 282
 283   typedef __conditional_t<is_same<__link_pointer, __node_pointer>::value, __base_pointer, __node_pointer>
 284       __non_link_pointer;
 285
 286   static _LIBCPP_INLINE_VISIBILITY
 287   __link_pointer __unsafe_link_pointer_cast(__link_pointer __p) {
 288       return __p;
 289   }
 290
 291   static _LIBCPP_INLINE_VISIBILITY
 292   __link_pointer __unsafe_link_pointer_cast(__non_link_pointer __p) {
 293       return static_cast<__link_pointer>(static_cast<_VoidPtr>(__p));
 294   }
 295
 296 };
 297
 298 template <class _Tp, class _VoidPtr>
 299 struct __list_node_base
 300 {
 301     typedef __list_node_pointer_traits<_Tp, _VoidPtr> _NodeTraits;
 302     typedef typename _NodeTraits::__node_pointer __node_pointer;
 303     typedef typename _NodeTraits::__base_pointer __base_pointer;
 304     typedef typename _NodeTraits::__link_pointer __link_pointer;
 305
 306     __link_pointer __prev_;
 307     __link_pointer __next_;
 308
 309     _LIBCPP_INLINE_VISIBILITY
 310     __list_node_base() : __prev_(_NodeTraits::__unsafe_link_pointer_cast(__self())),
 311                          __next_(_NodeTraits::__unsafe_link_pointer_cast(__self())) {}
 312
 313     _LIBCPP_HIDE_FROM_ABI explicit __list_node_base(__link_pointer __prev, __link_pointer __next)
 314         : __prev_(__prev), __next_(__next) {}
 315
 316     _LIBCPP_INLINE_VISIBILITY
 317     __base_pointer __self() {
 318         return pointer_traits<__base_pointer>::pointer_to(*this);
 319     }
 320
 321     _LIBCPP_INLINE_VISIBILITY
 322     __node_pointer __as_node() {
 323         return static_cast<__node_pointer>(__self());
 324     }
 325 };
 326
 327 template <class _Tp, class _VoidPtr>
 328 struct __list_node
 329     : public __list_node_base<_Tp, _VoidPtr>
 330 {
 331     // We allow starting the lifetime of nodes without initializing the value held by the node,
 332     // since that is handled by the list itself in order to be allocator-aware.
 333 #ifndef _LIBCPP_CXX03_LANG
 334 private:
 335     union {
 336         _Tp __value_;
 337     };
 338
 339 public:
 340     _LIBCPP_HIDE_FROM_ABI _Tp& __get_value() { return __value_; }
 341 #else
 342 private:
 343     _ALIGNAS_TYPE(_Tp) char __buffer_[sizeof(_Tp)];
 344
 345 public:
 346     _LIBCPP_HIDE_FROM_ABI _Tp& __get_value() {
 347         return *std::__launder(reinterpret_cast<_Tp*>(&__buffer_));
 348     }
 349 #endif
 350
 351     typedef __list_node_base<_Tp, _VoidPtr> __base;
 352     typedef typename __base::__link_pointer __link_pointer;
 353
 354     _LIBCPP_HIDE_FROM_ABI explicit __list_node(__link_pointer __prev, __link_pointer __next) : __base(__prev, __next) {}
 355     _LIBCPP_HIDE_FROM_ABI ~__list_node() {}
 356
 357     _LIBCPP_INLINE_VISIBILITY
 358     __link_pointer __as_link() {
 359         return static_cast<__link_pointer>(__base::__self());
 360     }
 361 };
 362
 363 template <class _Tp, class _Alloc = allocator<_Tp> > class _LIBCPP_TEMPLATE_VIS list;
 364 template <class _Tp, class _Alloc> class __list_imp;
 365 template <class _Tp, class _VoidPtr> class _LIBCPP_TEMPLATE_VIS __list_const_iterator;
 366
 367 template <class _Tp, class _VoidPtr>
 368 class _LIBCPP_TEMPLATE_VIS __list_iterator
 369 {
 370     typedef __list_node_pointer_traits<_Tp, _VoidPtr> _NodeTraits;
 371     typedef typename _NodeTraits::__link_pointer __link_pointer;
 372
 373     __link_pointer __ptr_;
 374
 375     _LIBCPP_INLINE_VISIBILITY
 376     explicit __list_iterator(__link_pointer __p) _NOEXCEPT
 377         : __ptr_(__p)
 378     {
 379     }
 380
 381     template<class, class> friend class list;
 382     template<class, class> friend class __list_imp;
 383     template<class, class> friend class __list_const_iterator;
 384 public:
 385     typedef bidirectional_iterator_tag       iterator_category;
 386     typedef _Tp                              value_type;
 387     typedef value_type&                      reference;
 388     typedef __rebind_pointer_t<_VoidPtr, value_type> pointer;
 389     typedef typename pointer_traits<pointer>::difference_type difference_type;
 390
 391     _LIBCPP_INLINE_VISIBILITY
 392     __list_iterator() _NOEXCEPT : __ptr_(nullptr)
 393     {
 394     }
 395
 396     _LIBCPP_INLINE_VISIBILITY
 397     reference operator*() const
 398     {
 399         return __ptr_->__as_node()->__get_value();
 400     }
 401     _LIBCPP_INLINE_VISIBILITY
 402     pointer operator->() const
 403     {
 404         return pointer_traits<pointer>::pointer_to(__ptr_->__as_node()->__get_value());
 405     }
 406
 407     _LIBCPP_INLINE_VISIBILITY
 408     __list_iterator& operator++()
 409     {
 410         __ptr_ = __ptr_->__next_;
 411         return *this;
 412     }
 413     _LIBCPP_INLINE_VISIBILITY
 414     __list_iterator operator++(int) {__list_iterator __t(*this); ++(*this); return __t;}
 415
 416     _LIBCPP_INLINE_VISIBILITY
 417     __list_iterator& operator--()
 418     {
 419         __ptr_ = __ptr_->__prev_;
 420         return *this;
 421     }
 422     _LIBCPP_INLINE_VISIBILITY
 423     __list_iterator operator--(int) {__list_iterator __t(*this); --(*this); return __t;}
 424
 425     friend _LIBCPP_INLINE_VISIBILITY
 426     bool operator==(const __list_iterator& __x, const __list_iterator& __y)
 427     {
 428         return __x.__ptr_ == __y.__ptr_;
 429     }
 430     friend _LIBCPP_INLINE_VISIBILITY
 431      bool operator!=(const __list_iterator& __x, const __list_iterator& __y)
 432         {return !(__x == __y);}
 433 };
 434
 435 template <class _Tp, class _VoidPtr>
 436 class _LIBCPP_TEMPLATE_VIS __list_const_iterator
 437 {
 438     typedef __list_node_pointer_traits<_Tp, _VoidPtr> _NodeTraits;
 439     typedef typename _NodeTraits::__link_pointer __link_pointer;
 440
 441     __link_pointer __ptr_;
 442
 443     _LIBCPP_INLINE_VISIBILITY
 444     explicit __list_const_iterator(__link_pointer __p) _NOEXCEPT
 445         : __ptr_(__p)
 446     {
 447     }
 448
 449     template<class, class> friend class list;
 450     template<class, class> friend class __list_imp;
 451 public:
 452     typedef bidirectional_iterator_tag       iterator_category;
 453     typedef _Tp                              value_type;
 454     typedef const value_type&                reference;
 455     typedef __rebind_pointer_t<_VoidPtr, const value_type> pointer;
 456     typedef typename pointer_traits<pointer>::difference_type difference_type;
 457
 458     _LIBCPP_INLINE_VISIBILITY
 459     __list_const_iterator() _NOEXCEPT : __ptr_(nullptr)
 460     {
 461     }
 462     _LIBCPP_INLINE_VISIBILITY
 463     __list_const_iterator(const __list_iterator<_Tp, _VoidPtr>& __p) _NOEXCEPT
 464         : __ptr_(__p.__ptr_)
 465     {
 466     }
 467
 468     _LIBCPP_INLINE_VISIBILITY
 469     reference operator*() const
 470     {
 471         return __ptr_->__as_node()->__get_value();
 472     }
 473     _LIBCPP_INLINE_VISIBILITY
 474     pointer operator->() const
 475     {
 476         return pointer_traits<pointer>::pointer_to(__ptr_->__as_node()->__get_value());
 477     }
 478
 479     _LIBCPP_INLINE_VISIBILITY
 480     __list_const_iterator& operator++()
 481     {
 482         __ptr_ = __ptr_->__next_;
 483         return *this;
 484     }
 485     _LIBCPP_INLINE_VISIBILITY
 486     __list_const_iterator operator++(int) {__list_const_iterator __t(*this); ++(*this); return __t;}
 487
 488     _LIBCPP_INLINE_VISIBILITY
 489     __list_const_iterator& operator--()
 490     {
 491         __ptr_ = __ptr_->__prev_;
 492         return *this;
 493     }
 494     _LIBCPP_INLINE_VISIBILITY
 495     __list_const_iterator operator--(int) {__list_const_iterator __t(*this); --(*this); return __t;}
 496
 497     friend _LIBCPP_INLINE_VISIBILITY
 498     bool operator==(const __list_const_iterator& __x, const __list_const_iterator& __y)
 499     {
 500         return __x.__ptr_ == __y.__ptr_;
 501     }
 502     friend _LIBCPP_INLINE_VISIBILITY
 503     bool operator!=(const __list_const_iterator& __x, const __list_const_iterator& __y)
 504         {return !(__x == __y);}
 505 };
 506
 507 template <class _Tp, class _Alloc>
 508 class __list_imp
 509 {
 510     __list_imp(const __list_imp&);
 511     __list_imp& operator=(const __list_imp&);
 512 public:
 513     typedef _Alloc                                                  allocator_type;
 514     typedef allocator_traits<allocator_type>                        __alloc_traits;
 515     typedef typename __alloc_traits::size_type                      size_type;
 516 protected:
 517     typedef _Tp                                                     value_type;
 518     typedef typename __alloc_traits::void_pointer                   __void_pointer;
 519     typedef __list_iterator<value_type, __void_pointer>             iterator;
 520     typedef __list_const_iterator<value_type, __void_pointer>       const_iterator;
 521     typedef __list_node_base<value_type, __void_pointer>            __node_base;
 522     typedef __list_node<value_type, __void_pointer>                 __node_type;
 523     typedef __rebind_alloc<__alloc_traits, __node_type>             __node_allocator;
 524     typedef allocator_traits<__node_allocator>                       __node_alloc_traits;
 525     typedef typename __node_alloc_traits::pointer                    __node_pointer;
 526     typedef typename __node_alloc_traits::pointer                    __node_const_pointer;
 527     typedef __list_node_pointer_traits<value_type, __void_pointer> __node_pointer_traits;
 528     typedef typename __node_pointer_traits::__link_pointer __link_pointer;
 529     typedef __link_pointer __link_const_pointer;
 530     typedef typename __alloc_traits::pointer                         pointer;
 531     typedef typename __alloc_traits::const_pointer                   const_pointer;
 532     typedef typename __alloc_traits::difference_type                 difference_type;
 533
 534     typedef __rebind_alloc<__alloc_traits, __node_base>               __node_base_allocator;
 535     typedef typename allocator_traits<__node_base_allocator>::pointer __node_base_pointer;
 536     static_assert((!is_same<allocator_type, __node_allocator>::value),
 537                   "internal allocator type must differ from user-specified "
 538                   "type; otherwise overload resolution breaks");
 539
 540     __node_base __end_;
 541     __compressed_pair<size_type, __node_allocator> __size_alloc_;
 542
 543     _LIBCPP_INLINE_VISIBILITY
 544     __link_pointer __end_as_link() const _NOEXCEPT {
 545         return __node_pointer_traits::__unsafe_link_pointer_cast(
 546                 const_cast<__node_base&>(__end_).__self());
 547     }
 548
 549     _LIBCPP_INLINE_VISIBILITY
 550           size_type& __sz() _NOEXCEPT {return __size_alloc_.first();}
 551     _LIBCPP_INLINE_VISIBILITY
 552     const size_type& __sz() const _NOEXCEPT
 553         {return __size_alloc_.first();}
 554     _LIBCPP_INLINE_VISIBILITY
 555           __node_allocator& __node_alloc() _NOEXCEPT
 556           {return __size_alloc_.second();}
 557     _LIBCPP_INLINE_VISIBILITY
 558     const __node_allocator& __node_alloc() const _NOEXCEPT
 559         {return __size_alloc_.second();}
 560
 561     _LIBCPP_INLINE_VISIBILITY
 562     size_type __node_alloc_max_size() const _NOEXCEPT {
 563         return __node_alloc_traits::max_size(__node_alloc());
 564     }
 565     _LIBCPP_INLINE_VISIBILITY
 566     static void __unlink_nodes(__link_pointer __f, __link_pointer __l) _NOEXCEPT;
 567
 568     _LIBCPP_INLINE_VISIBILITY
 569     __list_imp()
 570         _NOEXCEPT_(is_nothrow_default_constructible<__node_allocator>::value);
 571     _LIBCPP_INLINE_VISIBILITY
 572     __list_imp(const allocator_type& __a);
 573     _LIBCPP_INLINE_VISIBILITY
 574     __list_imp(const __node_allocator& __a);
 575 #ifndef _LIBCPP_CXX03_LANG
 576     _LIBCPP_HIDE_FROM_ABI __list_imp(__node_allocator&& __a) _NOEXCEPT;
 577 #endif
 578     _LIBCPP_HIDE_FROM_ABI ~__list_imp();
 579     _LIBCPP_HIDE_FROM_ABI void clear() _NOEXCEPT;
 580     _LIBCPP_INLINE_VISIBILITY
 581     bool empty() const _NOEXCEPT {return __sz() == 0;}
 582
 583     _LIBCPP_INLINE_VISIBILITY
 584     iterator begin() _NOEXCEPT
 585     {
 586         return iterator(__end_.__next_);
 587     }
 588     _LIBCPP_INLINE_VISIBILITY
 589     const_iterator begin() const  _NOEXCEPT
 590     {
 591         return const_iterator(__end_.__next_);
 592     }
 593     _LIBCPP_INLINE_VISIBILITY
 594     iterator end() _NOEXCEPT
 595     {
 596         return iterator(__end_as_link());
 597     }
 598     _LIBCPP_INLINE_VISIBILITY
 599     const_iterator end() const _NOEXCEPT
 600     {
 601         return const_iterator(__end_as_link());
 602     }
 603
 604     _LIBCPP_HIDE_FROM_ABI void swap(__list_imp& __c)
 605 #if _LIBCPP_STD_VER >= 14
 606         _NOEXCEPT;
 607 #else
 608         _NOEXCEPT_(!__alloc_traits::propagate_on_container_swap::value ||
 609                     __is_nothrow_swappable<allocator_type>::value);
 610 #endif
 611
 612     _LIBCPP_INLINE_VISIBILITY
 613     void __copy_assign_alloc(const __list_imp& __c)
 614         {__copy_assign_alloc(__c, integral_constant<bool,
 615                       __node_alloc_traits::propagate_on_container_copy_assignment::value>());}
 616
 617     _LIBCPP_INLINE_VISIBILITY
 618     void __move_assign_alloc(__list_imp& __c)
 619         _NOEXCEPT_(
 620             !__node_alloc_traits::propagate_on_container_move_assignment::value ||
 621             is_nothrow_move_assignable<__node_allocator>::value)
 622         {__move_assign_alloc(__c, integral_constant<bool,
 623                       __node_alloc_traits::propagate_on_container_move_assignment::value>());}
 624
 625     template <class ..._Args>
 626     _LIBCPP_HIDE_FROM_ABI __node_pointer __create_node(__link_pointer __prev, __link_pointer __next, _Args&& ...__args) {
 627         __node_allocator& __alloc = __node_alloc();
 628         __allocation_guard<__node_allocator> __guard(__alloc, 1);
 629         // Begin the lifetime of the node itself. Note that this doesn't begin the lifetime of the value
 630         // held inside the node, since we need to use the allocator's construct() method for that.
 631         //
 632         // We don't use the allocator's construct() method to construct the node itself since the
 633         // Cpp17FooInsertable named requirements don't require the allocator's construct() method
 634         // to work on anything other than the value_type.
 635         std::__construct_at(std::addressof(*__guard.__get()), __prev, __next);
 636
 637         // Now construct the value_type using the allocator's construct() method.
 638         __node_alloc_traits::construct(__alloc, std::addressof(__guard.__get()->__get_value()), std::forward<_Args>(__args)...);
 639         return __guard.__release_ptr();
 640     }
 641
 642     template <class ..._Args>
 643     _LIBCPP_HIDE_FROM_ABI void __delete_node(__node_pointer __node) {
 644         // For the same reason as above, we use the allocator's destroy() method for the value_type,
 645         // but not for the node itself.
 646         __node_allocator& __alloc = __node_alloc();
 647         __node_alloc_traits::destroy(__alloc, std::addressof(__node->__get_value()));
 648         std::__destroy_at(std::addressof(*__node));
 649         __node_alloc_traits::deallocate(__alloc, __node, 1);
 650     }
 651
 652 private:
 653     _LIBCPP_INLINE_VISIBILITY
 654     void __copy_assign_alloc(const __list_imp& __c, true_type)
 655         {
 656             if (__node_alloc() != __c.__node_alloc())
 657                 clear();
 658             __node_alloc() = __c.__node_alloc();
 659         }
 660
 661     _LIBCPP_INLINE_VISIBILITY
 662     void __copy_assign_alloc(const __list_imp&, false_type)
 663         {}
 664
 665     _LIBCPP_INLINE_VISIBILITY
 666     void __move_assign_alloc(__list_imp& __c, true_type)
 667         _NOEXCEPT_(is_nothrow_move_assignable<__node_allocator>::value)
 668         {
 669             __node_alloc() = _VSTD::move(__c.__node_alloc());
 670         }
 671
 672     _LIBCPP_INLINE_VISIBILITY
 673     void __move_assign_alloc(__list_imp&, false_type)
 674         _NOEXCEPT
 675         {}
 676 };
 677
 678 // Unlink nodes [__f, __l]
 679 template <class _Tp, class _Alloc>
 680 inline
 681 void
 682 __list_imp<_Tp, _Alloc>::__unlink_nodes(__link_pointer __f, __link_pointer __l)
 683     _NOEXCEPT
 684 {
 685     __f->__prev_->__next_ = __l->__next_;
 686     __l->__next_->__prev_ = __f->__prev_;
 687 }
 688
 689 template <class _Tp, class _Alloc>
 690 inline
 691 __list_imp<_Tp, _Alloc>::__list_imp()
 692         _NOEXCEPT_(is_nothrow_default_constructible<__node_allocator>::value)
 693     : __size_alloc_(0, __default_init_tag())
 694 {
 695 }
 696
 697 template <class _Tp, class _Alloc>
 698 inline
 699 __list_imp<_Tp, _Alloc>::__list_imp(const allocator_type& __a)
 700     : __size_alloc_(0, __node_allocator(__a))
 701 {
 702 }
 703
 704 template <class _Tp, class _Alloc>
 705 inline __list_imp<_Tp, _Alloc>::__list_imp(const __node_allocator& __a)
 706     : __size_alloc_(0, __a) {}
 707
 708 #ifndef _LIBCPP_CXX03_LANG
 709 template <class _Tp, class _Alloc>
 710 inline __list_imp<_Tp, _Alloc>::__list_imp(__node_allocator&& __a) _NOEXCEPT
 711     : __size_alloc_(0, _VSTD::move(__a)) {}
 712 #endif
 713
 714 template <class _Tp, class _Alloc>
 715 __list_imp<_Tp, _Alloc>::~__list_imp() {
 716   clear();
 717 }
 718
 719 template <class _Tp, class _Alloc>
 720 void
 721 __list_imp<_Tp, _Alloc>::clear() _NOEXCEPT
 722 {
 723     if (!empty())
 724     {
 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             __delete_node(__np);
 734         }
 735     }
 736 }
 737
 738 template <class _Tp, class _Alloc>
 739 void
 740 __list_imp<_Tp, _Alloc>::swap(__list_imp& __c)
 741 #if _LIBCPP_STD_VER >= 14
 742         _NOEXCEPT
 743 #else
 744         _NOEXCEPT_(!__alloc_traits::propagate_on_container_swap::value ||
 745                     __is_nothrow_swappable<allocator_type>::value)
 746 #endif
 747 {
 748     _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR(__alloc_traits::propagate_on_container_swap::value ||
 749                                         this->__node_alloc() == __c.__node_alloc(),
 750                                         "list::swap: Either propagate_on_container_swap must be true"
 751                                         " or the allocators must compare equal");
 752     using _VSTD::swap;
 753     _VSTD::__swap_allocator(__node_alloc(), __c.__node_alloc());
 754     swap(__sz(), __c.__sz());
 755     swap(__end_, __c.__end_);
 756     if (__sz() == 0)
 757         __end_.__next_ = __end_.__prev_ = __end_as_link();
 758     else
 759         __end_.__prev_->__next_ = __end_.__next_->__prev_ = __end_as_link();
 760     if (__c.__sz() == 0)
 761         __c.__end_.__next_ = __c.__end_.__prev_ = __c.__end_as_link();
 762     else
 763         __c.__end_.__prev_->__next_ = __c.__end_.__next_->__prev_ = __c.__end_as_link();
 764 }
 765
 766 template <class _Tp, class _Alloc /*= allocator<_Tp>*/>
 767 class _LIBCPP_TEMPLATE_VIS list
 768     : private __list_imp<_Tp, _Alloc>
 769 {
 770     typedef __list_imp<_Tp, _Alloc> base;
 771     typedef typename base::__node_type         __node_type;
 772     typedef typename base::__node_allocator    __node_allocator;
 773     typedef typename base::__node_pointer      __node_pointer;
 774     typedef typename base::__node_alloc_traits __node_alloc_traits;
 775     typedef typename base::__node_base         __node_base;
 776     typedef typename base::__node_base_pointer __node_base_pointer;
 777     typedef typename base::__link_pointer __link_pointer;
 778
 779 public:
 780     typedef _Tp                                            value_type;
 781     typedef _Alloc                                         allocator_type;
 782     static_assert((is_same<value_type, typename allocator_type::value_type>::value),
 783                   "Allocator::value_type must be same type as value_type");
 784     typedef value_type&                                    reference;
 785     typedef const value_type&                              const_reference;
 786     typedef typename base::pointer                         pointer;
 787     typedef typename base::const_pointer                   const_pointer;
 788     typedef typename base::size_type                       size_type;
 789     typedef typename base::difference_type                 difference_type;
 790     typedef typename base::iterator                        iterator;
 791     typedef typename base::const_iterator                  const_iterator;
 792     typedef _VSTD::reverse_iterator<iterator>              reverse_iterator;
 793     typedef _VSTD::reverse_iterator<const_iterator>        const_reverse_iterator;
 794 #if _LIBCPP_STD_VER >= 20
 795     typedef size_type                                      __remove_return_type;
 796 #else
 797     typedef void                                           __remove_return_type;
 798 #endif
 799
 800     static_assert(is_same<allocator_type, __rebind_alloc<allocator_traits<allocator_type>, value_type> >::value,
 801                   "[allocator.requirements] states that rebinding an allocator to the same type should result in the "
 802                   "original allocator");
 803
 804     _LIBCPP_INLINE_VISIBILITY
 805     list()
 806         _NOEXCEPT_(is_nothrow_default_constructible<__node_allocator>::value)
 807     {
 808     }
 809     _LIBCPP_INLINE_VISIBILITY
 810     explicit list(const allocator_type& __a) : base(__a)
 811     {
 812     }
 813     _LIBCPP_HIDE_FROM_ABI explicit list(size_type __n);
 814 #if _LIBCPP_STD_VER >= 14
 815     _LIBCPP_HIDE_FROM_ABI explicit list(size_type __n, const allocator_type& __a);
 816 #endif
 817     _LIBCPP_HIDE_FROM_ABI list(size_type __n, const value_type& __x);
 818     template <class = __enable_if_t<__is_allocator<_Alloc>::value> >
 819     _LIBCPP_HIDE_FROM_ABI list(size_type __n, const value_type& __x, const allocator_type& __a) : base(__a)
 820     {
 821         for (; __n > 0; --__n)
 822             push_back(__x);
 823     }
 824
 825     template <class _InpIter>
 826     _LIBCPP_HIDE_FROM_ABI list(_InpIter __f, _InpIter __l,
 827              __enable_if_t<__has_input_iterator_category<_InpIter>::value>* = 0);
 828     template <class _InpIter>
 829     _LIBCPP_HIDE_FROM_ABI list(_InpIter __f, _InpIter __l, const allocator_type& __a,
 830              __enable_if_t<__has_input_iterator_category<_InpIter>::value>* = 0);
 831
 832 #if _LIBCPP_STD_VER >= 23
 833     template <_ContainerCompatibleRange<_Tp> _Range>
 834     _LIBCPP_HIDE_FROM_ABI list(from_range_t, _Range&& __range,
 835         const allocator_type& __a = allocator_type()) : base(__a) {
 836       prepend_range(std::forward<_Range>(__range));
 837     }
 838 #endif
 839
 840     _LIBCPP_HIDE_FROM_ABI list(const list& __c);
 841     _LIBCPP_HIDE_FROM_ABI list(const list& __c, const __type_identity_t<allocator_type>& __a);
 842     _LIBCPP_INLINE_VISIBILITY
 843     list& operator=(const list& __c);
 844 #ifndef _LIBCPP_CXX03_LANG
 845     _LIBCPP_HIDE_FROM_ABI list(initializer_list<value_type> __il);
 846     _LIBCPP_HIDE_FROM_ABI list(initializer_list<value_type> __il, const allocator_type& __a);
 847
 848     _LIBCPP_INLINE_VISIBILITY
 849     list(list&& __c)
 850         _NOEXCEPT_(is_nothrow_move_constructible<__node_allocator>::value);
 851     _LIBCPP_INLINE_VISIBILITY
 852     list(list&& __c, const __type_identity_t<allocator_type>& __a);
 853     _LIBCPP_INLINE_VISIBILITY
 854     list& operator=(list&& __c)
 855         _NOEXCEPT_(
 856             __node_alloc_traits::propagate_on_container_move_assignment::value &&
 857             is_nothrow_move_assignable<__node_allocator>::value);
 858
 859     _LIBCPP_INLINE_VISIBILITY
 860     list& operator=(initializer_list<value_type> __il)
 861         {assign(__il.begin(), __il.end()); return *this;}
 862
 863     _LIBCPP_INLINE_VISIBILITY
 864     void assign(initializer_list<value_type> __il)
 865         {assign(__il.begin(), __il.end());}
 866 #endif // _LIBCPP_CXX03_LANG
 867
 868     template <class _InpIter>
 869     _LIBCPP_HIDE_FROM_ABI void assign(_InpIter __f, _InpIter __l,
 870                     __enable_if_t<__has_input_iterator_category<_InpIter>::value>* = 0);
 871
 872 #if _LIBCPP_STD_VER >= 23
 873     template <_ContainerCompatibleRange<_Tp> _Range>
 874     _LIBCPP_HIDE_FROM_ABI
 875     void assign_range(_Range&& __range) {
 876       __assign_with_sentinel(ranges::begin(__range), ranges::end(__range));
 877     }
 878 #endif
 879
 880     _LIBCPP_HIDE_FROM_ABI void assign(size_type __n, const value_type& __x);
 881
 882     _LIBCPP_INLINE_VISIBILITY
 883     allocator_type get_allocator() const _NOEXCEPT;
 884
 885     _LIBCPP_INLINE_VISIBILITY
 886     size_type size() const _NOEXCEPT     {return base::__sz();}
 887     _LIBCPP_NODISCARD_AFTER_CXX17 _LIBCPP_INLINE_VISIBILITY
 888     bool empty() const _NOEXCEPT         {return base::empty();}
 889     _LIBCPP_INLINE_VISIBILITY
 890     size_type max_size() const _NOEXCEPT
 891         {
 892             return _VSTD::min<size_type>(
 893                 base::__node_alloc_max_size(),
 894                 numeric_limits<difference_type >::max());
 895         }
 896
 897     _LIBCPP_INLINE_VISIBILITY
 898           iterator begin() _NOEXCEPT        {return base::begin();}
 899     _LIBCPP_INLINE_VISIBILITY
 900     const_iterator begin()  const _NOEXCEPT {return base::begin();}
 901     _LIBCPP_INLINE_VISIBILITY
 902           iterator end() _NOEXCEPT          {return base::end();}
 903     _LIBCPP_INLINE_VISIBILITY
 904     const_iterator end()    const _NOEXCEPT {return base::end();}
 905     _LIBCPP_INLINE_VISIBILITY
 906     const_iterator cbegin() const _NOEXCEPT {return base::begin();}
 907     _LIBCPP_INLINE_VISIBILITY
 908     const_iterator cend()   const _NOEXCEPT {return base::end();}
 909
 910     _LIBCPP_INLINE_VISIBILITY
 911           reverse_iterator rbegin() _NOEXCEPT
 912             {return       reverse_iterator(end());}
 913     _LIBCPP_INLINE_VISIBILITY
 914     const_reverse_iterator rbegin()  const _NOEXCEPT
 915         {return const_reverse_iterator(end());}
 916     _LIBCPP_INLINE_VISIBILITY
 917           reverse_iterator rend() _NOEXCEPT
 918             {return       reverse_iterator(begin());}
 919     _LIBCPP_INLINE_VISIBILITY
 920     const_reverse_iterator rend()    const _NOEXCEPT
 921         {return const_reverse_iterator(begin());}
 922     _LIBCPP_INLINE_VISIBILITY
 923     const_reverse_iterator crbegin() const _NOEXCEPT
 924         {return const_reverse_iterator(end());}
 925     _LIBCPP_INLINE_VISIBILITY
 926     const_reverse_iterator crend()   const _NOEXCEPT
 927         {return const_reverse_iterator(begin());}
 928
 929     _LIBCPP_INLINE_VISIBILITY
 930     reference front()
 931     {
 932         _LIBCPP_ASSERT_VALID_ELEMENT_ACCESS(!empty(), "list::front called on empty list");
 933         return base::__end_.__next_->__as_node()->__get_value();
 934     }
 935     _LIBCPP_INLINE_VISIBILITY
 936     const_reference front() const
 937     {
 938         _LIBCPP_ASSERT_VALID_ELEMENT_ACCESS(!empty(), "list::front called on empty list");
 939         return base::__end_.__next_->__as_node()->__get_value();
 940     }
 941     _LIBCPP_INLINE_VISIBILITY
 942     reference back()
 943     {
 944         _LIBCPP_ASSERT_VALID_ELEMENT_ACCESS(!empty(), "list::back called on empty list");
 945         return base::__end_.__prev_->__as_node()->__get_value();
 946     }
 947     _LIBCPP_INLINE_VISIBILITY
 948     const_reference back() const
 949     {
 950         _LIBCPP_ASSERT_VALID_ELEMENT_ACCESS(!empty(), "list::back called on empty list");
 951         return base::__end_.__prev_->__as_node()->__get_value();
 952     }
 953
 954 #ifndef _LIBCPP_CXX03_LANG
 955     _LIBCPP_HIDE_FROM_ABI void push_front(value_type&& __x);
 956     _LIBCPP_HIDE_FROM_ABI void push_back(value_type&& __x);
 957
 958 #if _LIBCPP_STD_VER >= 23
 959     template <_ContainerCompatibleRange<_Tp> _Range>
 960     _LIBCPP_HIDE_FROM_ABI
 961     void prepend_range(_Range&& __range) {
 962       insert_range(begin(), std::forward<_Range>(__range));
 963     }
 964
 965     template <_ContainerCompatibleRange<_Tp> _Range>
 966     _LIBCPP_HIDE_FROM_ABI
 967     void append_range(_Range&& __range) {
 968       insert_range(end(), std::forward<_Range>(__range));
 969     }
 970 #endif
 971
 972     template <class... _Args>
 973 #if _LIBCPP_STD_VER >= 17
 974     _LIBCPP_HIDE_FROM_ABI reference emplace_front(_Args&&... __args);
 975 #else
 976     _LIBCPP_HIDE_FROM_ABI void      emplace_front(_Args&&... __args);
 977 #endif
 978     template <class... _Args>
 979 #if _LIBCPP_STD_VER >= 17
 980     _LIBCPP_HIDE_FROM_ABI reference emplace_back(_Args&&... __args);
 981 #else
 982     _LIBCPP_HIDE_FROM_ABI void       emplace_back(_Args&&... __args);
 983 #endif
 984     template <class... _Args>
 985     _LIBCPP_HIDE_FROM_ABI iterator emplace(const_iterator __p, _Args&&... __args);
 986
 987     _LIBCPP_HIDE_FROM_ABI iterator insert(const_iterator __p, value_type&& __x);
 988
 989     _LIBCPP_INLINE_VISIBILITY
 990     iterator insert(const_iterator __p, initializer_list<value_type> __il)
 991         {return insert(__p, __il.begin(), __il.end());}
 992 #endif // _LIBCPP_CXX03_LANG
 993
 994     _LIBCPP_HIDE_FROM_ABI void push_front(const value_type& __x);
 995     _LIBCPP_HIDE_FROM_ABI void push_back(const value_type& __x);
 996
 997 #ifndef _LIBCPP_CXX03_LANG
 998     template <class _Arg>
 999     _LIBCPP_INLINE_VISIBILITY
1000     void __emplace_back(_Arg&& __arg) { emplace_back(_VSTD::forward<_Arg>(__arg)); }
1001 #else
1002     _LIBCPP_INLINE_VISIBILITY
1003     void __emplace_back(value_type const& __arg) { push_back(__arg); }
1004 #endif
1005
1006     _LIBCPP_HIDE_FROM_ABI iterator insert(const_iterator __p, const value_type& __x);
1007     _LIBCPP_HIDE_FROM_ABI iterator insert(const_iterator __p, size_type __n, const value_type& __x);
1008     template <class _InpIter>
1009     _LIBCPP_HIDE_FROM_ABI iterator insert(const_iterator __p, _InpIter __f, _InpIter __l,
1010                         __enable_if_t<__has_input_iterator_category<_InpIter>::value>* = 0);
1011
1012 #if _LIBCPP_STD_VER >= 23
1013     template <_ContainerCompatibleRange<_Tp> _Range>
1014     _LIBCPP_HIDE_FROM_ABI
1015     iterator insert_range(const_iterator __position, _Range&& __range) {
1016       return __insert_with_sentinel(__position, ranges::begin(__range), ranges::end(__range));
1017     }
1018 #endif
1019
1020     _LIBCPP_INLINE_VISIBILITY
1021     void swap(list& __c)
1022 #if _LIBCPP_STD_VER >= 14
1023         _NOEXCEPT
1024 #else
1025         _NOEXCEPT_(!__node_alloc_traits::propagate_on_container_swap::value ||
1026                    __is_nothrow_swappable<__node_allocator>::value)
1027 #endif
1028         {base::swap(__c);}
1029     _LIBCPP_INLINE_VISIBILITY
1030     void clear() _NOEXCEPT {base::clear();}
1031
1032     _LIBCPP_HIDE_FROM_ABI void pop_front();
1033     _LIBCPP_HIDE_FROM_ABI void pop_back();
1034
1035     _LIBCPP_HIDE_FROM_ABI iterator erase(const_iterator __p);
1036     _LIBCPP_HIDE_FROM_ABI iterator erase(const_iterator __f, const_iterator __l);
1037
1038     _LIBCPP_HIDE_FROM_ABI void resize(size_type __n);
1039     _LIBCPP_HIDE_FROM_ABI void resize(size_type __n, const value_type& __x);
1040
1041     _LIBCPP_HIDE_FROM_ABI void splice(const_iterator __p, list& __c);
1042 #ifndef _LIBCPP_CXX03_LANG
1043     _LIBCPP_INLINE_VISIBILITY
1044     void splice(const_iterator __p, list&& __c) {splice(__p, __c);}
1045     _LIBCPP_INLINE_VISIBILITY
1046     void splice(const_iterator __p, list&& __c, const_iterator __i)
1047         {splice(__p, __c, __i);}
1048     _LIBCPP_INLINE_VISIBILITY
1049     void splice(const_iterator __p, list&& __c, const_iterator __f, const_iterator __l)
1050         {splice(__p, __c, __f, __l);}
1051 #endif
1052     _LIBCPP_HIDE_FROM_ABI void splice(const_iterator __p, list& __c, const_iterator __i);
1053     _LIBCPP_HIDE_FROM_ABI void splice(const_iterator __p, list& __c, const_iterator __f, const_iterator __l);
1054
1055     _LIBCPP_HIDE_FROM_ABI __remove_return_type remove(const value_type& __x);
1056     template <class _Pred>
1057     _LIBCPP_HIDE_FROM_ABI __remove_return_type remove_if(_Pred __pred);
1058     _LIBCPP_INLINE_VISIBILITY
1059     __remove_return_type unique() { return unique(__equal_to()); }
1060     template <class _BinaryPred>
1061     _LIBCPP_HIDE_FROM_ABI __remove_return_type unique(_BinaryPred __binary_pred);
1062     _LIBCPP_INLINE_VISIBILITY
1063     void merge(list& __c);
1064 #ifndef _LIBCPP_CXX03_LANG
1065     _LIBCPP_INLINE_VISIBILITY
1066     void merge(list&& __c) {merge(__c);}
1067
1068     template <class _Comp>
1069     _LIBCPP_INLINE_VISIBILITY
1070         void merge(list&& __c, _Comp __comp) {merge(__c, __comp);}
1071 #endif
1072     template <class _Comp>
1073     _LIBCPP_HIDE_FROM_ABI void merge(list& __c, _Comp __comp);
1074
1075     _LIBCPP_INLINE_VISIBILITY
1076     void sort();
1077     template <class _Comp>
1078         _LIBCPP_INLINE_VISIBILITY
1079         void sort(_Comp __comp);
1080
1081     _LIBCPP_HIDE_FROM_ABI void reverse() _NOEXCEPT;
1082
1083     _LIBCPP_HIDE_FROM_ABI bool __invariants() const;
1084
1085 private:
1086     template <class _Iterator, class _Sentinel>
1087     _LIBCPP_HIDE_FROM_ABI
1088     void __assign_with_sentinel(_Iterator __f, _Sentinel __l);
1089
1090     template <class _Iterator, class _Sentinel>
1091     _LIBCPP_HIDE_FROM_ABI
1092     iterator __insert_with_sentinel(const_iterator __p, _Iterator __f, _Sentinel __l);
1093
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     _LIBCPP_HIDE_FROM_ABI iterator __iterator(size_type __n);
1101     // TODO: Make this _LIBCPP_HIDE_FROM_ABI
1102     template <class _Comp>
1103     _LIBCPP_HIDDEN static iterator __sort(iterator __f1, iterator __e2, size_type __n, _Comp& __comp);
1104
1105     _LIBCPP_HIDE_FROM_ABI void __move_assign(list& __c, true_type)
1106         _NOEXCEPT_(is_nothrow_move_assignable<__node_allocator>::value);
1107     _LIBCPP_HIDE_FROM_ABI void __move_assign(list& __c, false_type);
1108 };
1109
1110 #if _LIBCPP_STD_VER >= 17
1111 template<class _InputIterator,
1112          class _Alloc = allocator<__iter_value_type<_InputIterator>>,
1113          class = enable_if_t<__has_input_iterator_category<_InputIterator>::value>,
1114          class = enable_if_t<__is_allocator<_Alloc>::value>
1115          >
1116 list(_InputIterator, _InputIterator)
1117   -> list<__iter_value_type<_InputIterator>, _Alloc>;
1118
1119 template<class _InputIterator,
1120          class _Alloc,
1121          class = enable_if_t<__has_input_iterator_category<_InputIterator>::value>,
1122          class = enable_if_t<__is_allocator<_Alloc>::value>
1123          >
1124 list(_InputIterator, _InputIterator, _Alloc)
1125   -> list<__iter_value_type<_InputIterator>, _Alloc>;
1126 #endif
1127
1128 #if _LIBCPP_STD_VER >= 23
1129 template <ranges::input_range _Range,
1130           class _Alloc = allocator<ranges::range_value_t<_Range>>,
1131           class = enable_if_t<__is_allocator<_Alloc>::value>
1132           >
1133 list(from_range_t, _Range&&, _Alloc = _Alloc())
1134   -> list<ranges::range_value_t<_Range>, _Alloc>;
1135 #endif
1136
1137 // Link in nodes [__f, __l] just prior to __p
1138 template <class _Tp, class _Alloc>
1139 inline
1140 void
1141 list<_Tp, _Alloc>::__link_nodes(__link_pointer __p, __link_pointer __f, __link_pointer __l)
1142 {
1143     __p->__prev_->__next_ = __f;
1144     __f->__prev_ = __p->__prev_;
1145     __p->__prev_ = __l;
1146     __l->__next_ = __p;
1147 }
1148
1149 // Link in nodes [__f, __l] at the front of the list
1150 template <class _Tp, class _Alloc>
1151 inline
1152 void
1153 list<_Tp, _Alloc>::__link_nodes_at_front(__link_pointer __f, __link_pointer __l)
1154 {
1155     __f->__prev_ = base::__end_as_link();
1156     __l->__next_ = base::__end_.__next_;
1157     __l->__next_->__prev_ = __l;
1158     base::__end_.__next_ = __f;
1159 }
1160
1161 // Link in nodes [__f, __l] at the back of the list
1162 template <class _Tp, class _Alloc>
1163 inline
1164 void
1165 list<_Tp, _Alloc>::__link_nodes_at_back(__link_pointer __f, __link_pointer __l)
1166 {
1167     __l->__next_ = base::__end_as_link();
1168     __f->__prev_ = base::__end_.__prev_;
1169     __f->__prev_->__next_ = __f;
1170     base::__end_.__prev_ = __l;
1171 }
1172
1173
1174 template <class _Tp, class _Alloc>
1175 inline
1176 typename list<_Tp, _Alloc>::iterator
1177 list<_Tp, _Alloc>::__iterator(size_type __n)
1178 {
1179     return __n <= base::__sz() / 2 ? _VSTD::next(begin(), __n)
1180                                    : _VSTD::prev(end(), base::__sz() - __n);
1181 }
1182
1183 template <class _Tp, class _Alloc>
1184 list<_Tp, _Alloc>::list(size_type __n)
1185 {
1186     for (; __n > 0; --__n)
1187 #ifndef _LIBCPP_CXX03_LANG
1188         emplace_back();
1189 #else
1190         push_back(value_type());
1191 #endif
1192 }
1193
1194 #if _LIBCPP_STD_VER >= 14
1195 template <class _Tp, class _Alloc>
1196 list<_Tp, _Alloc>::list(size_type __n, const allocator_type& __a) : base(__a)
1197 {
1198     for (; __n > 0; --__n)
1199         emplace_back();
1200 }
1201 #endif
1202
1203 template <class _Tp, class _Alloc>
1204 list<_Tp, _Alloc>::list(size_type __n, const value_type& __x)
1205 {
1206     for (; __n > 0; --__n)
1207         push_back(__x);
1208 }
1209
1210 template <class _Tp, class _Alloc>
1211 template <class _InpIter>
1212 list<_Tp, _Alloc>::list(_InpIter __f, _InpIter __l,
1213                         __enable_if_t<__has_input_iterator_category<_InpIter>::value>*)
1214 {
1215     for (; __f != __l; ++__f)
1216         __emplace_back(*__f);
1217 }
1218
1219 template <class _Tp, class _Alloc>
1220 template <class _InpIter>
1221 list<_Tp, _Alloc>::list(_InpIter __f, _InpIter __l, const allocator_type& __a,
1222                         __enable_if_t<__has_input_iterator_category<_InpIter>::value>*)
1223     : base(__a)
1224 {
1225     for (; __f != __l; ++__f)
1226         __emplace_back(*__f);
1227 }
1228
1229 template <class _Tp, class _Alloc>
1230 list<_Tp, _Alloc>::list(const list& __c)
1231     : base(__node_alloc_traits::select_on_container_copy_construction(
1232           __c.__node_alloc())) {
1233     for (const_iterator __i = __c.begin(), __e = __c.end(); __i != __e; ++__i)
1234         push_back(*__i);
1235 }
1236
1237 template <class _Tp, class _Alloc>
1238 list<_Tp, _Alloc>::list(const list& __c, const __type_identity_t<allocator_type>& __a)
1239     : base(__a)
1240 {
1241     for (const_iterator __i = __c.begin(), __e = __c.end(); __i != __e; ++__i)
1242         push_back(*__i);
1243 }
1244
1245 #ifndef _LIBCPP_CXX03_LANG
1246
1247 template <class _Tp, class _Alloc>
1248 list<_Tp, _Alloc>::list(initializer_list<value_type> __il, const allocator_type& __a)
1249     : base(__a)
1250 {
1251     for (typename initializer_list<value_type>::const_iterator __i = __il.begin(),
1252             __e = __il.end(); __i != __e; ++__i)
1253         push_back(*__i);
1254 }
1255
1256 template <class _Tp, class _Alloc>
1257 list<_Tp, _Alloc>::list(initializer_list<value_type> __il)
1258 {
1259     for (typename initializer_list<value_type>::const_iterator __i = __il.begin(),
1260             __e = __il.end(); __i != __e; ++__i)
1261         push_back(*__i);
1262 }
1263
1264 template <class _Tp, class _Alloc>
1265 inline list<_Tp, _Alloc>::list(list&& __c)
1266         _NOEXCEPT_(is_nothrow_move_constructible<__node_allocator>::value)
1267         : base(_VSTD::move(__c.__node_alloc())) {
1268     splice(end(), __c);
1269 }
1270
1271 template <class _Tp, class _Alloc>
1272 inline
1273 list<_Tp, _Alloc>::list(list&& __c, const __type_identity_t<allocator_type>& __a)
1274     : base(__a)
1275 {
1276     if (__a == __c.get_allocator())
1277         splice(end(), __c);
1278     else
1279     {
1280         typedef move_iterator<iterator> _Ip;
1281         assign(_Ip(__c.begin()), _Ip(__c.end()));
1282     }
1283 }
1284
1285 template <class _Tp, class _Alloc>
1286 inline
1287 list<_Tp, _Alloc>&
1288 list<_Tp, _Alloc>::operator=(list&& __c)
1289         _NOEXCEPT_(
1290             __node_alloc_traits::propagate_on_container_move_assignment::value &&
1291             is_nothrow_move_assignable<__node_allocator>::value)
1292 {
1293     __move_assign(__c, integral_constant<bool,
1294           __node_alloc_traits::propagate_on_container_move_assignment::value>());
1295     return *this;
1296 }
1297
1298 template <class _Tp, class _Alloc>
1299 void
1300 list<_Tp, _Alloc>::__move_assign(list& __c, false_type)
1301 {
1302     if (base::__node_alloc() != __c.__node_alloc())
1303     {
1304         typedef move_iterator<iterator> _Ip;
1305         assign(_Ip(__c.begin()), _Ip(__c.end()));
1306     }
1307     else
1308         __move_assign(__c, true_type());
1309 }
1310
1311 template <class _Tp, class _Alloc>
1312 void
1313 list<_Tp, _Alloc>::__move_assign(list& __c, true_type)
1314         _NOEXCEPT_(is_nothrow_move_assignable<__node_allocator>::value)
1315 {
1316     clear();
1317     base::__move_assign_alloc(__c);
1318     splice(end(), __c);
1319 }
1320
1321 #endif // _LIBCPP_CXX03_LANG
1322
1323 template <class _Tp, class _Alloc>
1324 inline
1325 list<_Tp, _Alloc>&
1326 list<_Tp, _Alloc>::operator=(const list& __c)
1327 {
1328     if (this != _VSTD::addressof(__c))
1329     {
1330         base::__copy_assign_alloc(__c);
1331         assign(__c.begin(), __c.end());
1332     }
1333     return *this;
1334 }
1335
1336 template <class _Tp, class _Alloc>
1337 template <class _InpIter>
1338 void
1339 list<_Tp, _Alloc>::assign(_InpIter __f, _InpIter __l,
1340                           __enable_if_t<__has_input_iterator_category<_InpIter>::value>*)
1341 {
1342   __assign_with_sentinel(__f, __l);
1343 }
1344
1345 template <class _Tp, class _Alloc>
1346 template <class _Iterator, class _Sentinel>
1347 _LIBCPP_HIDE_FROM_ABI
1348 void list<_Tp, _Alloc>::__assign_with_sentinel(_Iterator __f, _Sentinel __l) {
1349     iterator __i = begin();
1350     iterator __e = end();
1351     for (; __f != __l && __i != __e; ++__f, (void) ++__i)
1352         *__i = *__f;
1353     if (__i == __e)
1354         __insert_with_sentinel(__e, std::move(__f), std::move(__l));
1355     else
1356         erase(__i, __e);
1357 }
1358
1359 template <class _Tp, class _Alloc>
1360 void
1361 list<_Tp, _Alloc>::assign(size_type __n, const value_type& __x)
1362 {
1363     iterator __i = begin();
1364     iterator __e = end();
1365     for (; __n > 0 && __i != __e; --__n, (void) ++__i)
1366         *__i = __x;
1367     if (__i == __e)
1368         insert(__e, __n, __x);
1369     else
1370         erase(__i, __e);
1371 }
1372
1373 template <class _Tp, class _Alloc>
1374 inline
1375 _Alloc
1376 list<_Tp, _Alloc>::get_allocator() const _NOEXCEPT
1377 {
1378     return allocator_type(base::__node_alloc());
1379 }
1380
1381 template <class _Tp, class _Alloc>
1382 typename list<_Tp, _Alloc>::iterator
1383 list<_Tp, _Alloc>::insert(const_iterator __p, const value_type& __x)
1384 {
1385     __node_pointer __node = this->__create_node(/* prev = */nullptr, /* next = */nullptr, __x);
1386     __link_nodes(__p.__ptr_, __node->__as_link(), __node->__as_link());
1387     ++base::__sz();
1388     return iterator(__node->__as_link());
1389 }
1390
1391 template <class _Tp, class _Alloc>
1392 typename list<_Tp, _Alloc>::iterator
1393 list<_Tp, _Alloc>::insert(const_iterator __p, size_type __n, const value_type& __x)
1394 {
1395     iterator __r(__p.__ptr_);
1396     if (__n > 0)
1397     {
1398         size_type __ds = 0;
1399         __node_pointer __node = this->__create_node(/* prev = */nullptr, /* next = */nullptr, __x);
1400         ++__ds;
1401         __r = iterator(__node->__as_link());
1402         iterator __e = __r;
1403 #ifndef _LIBCPP_HAS_NO_EXCEPTIONS
1404         try
1405         {
1406 #endif // _LIBCPP_HAS_NO_EXCEPTIONS
1407             for (--__n; __n != 0; --__n, (void) ++__e, ++__ds)
1408             {
1409                 __e.__ptr_->__next_ = this->__create_node(/* prev = */__e.__ptr_, /* next = */nullptr, __x)->__as_link();
1410             }
1411 #ifndef _LIBCPP_HAS_NO_EXCEPTIONS
1412         }
1413         catch (...)
1414         {
1415             while (true)
1416             {
1417                 __link_pointer __prev = __e.__ptr_->__prev_;
1418                 __node_pointer __current = __e.__ptr_->__as_node();
1419                 this->__delete_node(__current);
1420                 if (__prev == 0)
1421                     break;
1422                 __e = iterator(__prev);
1423             }
1424             throw;
1425         }
1426 #endif // _LIBCPP_HAS_NO_EXCEPTIONS
1427         __link_nodes(__p.__ptr_, __r.__ptr_, __e.__ptr_);
1428         base::__sz() += __ds;
1429     }
1430     return __r;
1431 }
1432
1433 template <class _Tp, class _Alloc>
1434 template <class _InpIter>
1435 typename list<_Tp, _Alloc>::iterator
1436 list<_Tp, _Alloc>::insert(const_iterator __p, _InpIter __f, _InpIter __l,
1437                           __enable_if_t<__has_input_iterator_category<_InpIter>::value>*)
1438 {
1439     return __insert_with_sentinel(__p, __f, __l);
1440 }
1441
1442 template <class _Tp, class _Alloc>
1443 template <class _Iterator, class _Sentinel>
1444 _LIBCPP_HIDE_FROM_ABI
1445 typename list<_Tp, _Alloc>::iterator
1446 list<_Tp, _Alloc>::__insert_with_sentinel(const_iterator __p, _Iterator __f, _Sentinel __l) {
1447     iterator __r(__p.__ptr_);
1448     if (__f != __l)
1449     {
1450         size_type __ds = 0;
1451         __node_pointer __node = this->__create_node(/* prev = */nullptr, /* next = */nullptr, *__f);
1452         ++__ds;
1453         __r = iterator(__node->__as_link());
1454         iterator __e = __r;
1455 #ifndef _LIBCPP_HAS_NO_EXCEPTIONS
1456         try
1457         {
1458 #endif // _LIBCPP_HAS_NO_EXCEPTIONS
1459             for (++__f; __f != __l; ++__f, (void) ++__e, ++__ds)
1460             {
1461                 __e.__ptr_->__next_ = this->__create_node(/* prev = */__e.__ptr_, /* next = */nullptr, *__f)->__as_link();
1462             }
1463 #ifndef _LIBCPP_HAS_NO_EXCEPTIONS
1464         }
1465         catch (...)
1466         {
1467             while (true)
1468             {
1469                 __link_pointer __prev = __e.__ptr_->__prev_;
1470                 __node_pointer __current = __e.__ptr_->__as_node();
1471                 this->__delete_node(__current);
1472                 if (__prev == 0)
1473                     break;
1474                 __e = iterator(__prev);
1475             }
1476             throw;
1477         }
1478 #endif // _LIBCPP_HAS_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 void
1487 list<_Tp, _Alloc>::push_front(const value_type& __x)
1488 {
1489     __node_pointer __node = this->__create_node(/* prev = */nullptr, /* next = */nullptr, __x);
1490     __link_pointer __nl = __node->__as_link();
1491     __link_nodes_at_front(__nl, __nl);
1492     ++base::__sz();
1493 }
1494
1495 template <class _Tp, class _Alloc>
1496 void
1497 list<_Tp, _Alloc>::push_back(const value_type& __x)
1498 {
1499     __node_pointer __node = this->__create_node(/* prev = */nullptr, /* next = */nullptr, __x);
1500     __link_pointer __nl = __node->__as_link();
1501     __link_nodes_at_back(__nl, __nl);
1502     ++base::__sz();
1503 }
1504
1505 #ifndef _LIBCPP_CXX03_LANG
1506
1507 template <class _Tp, class _Alloc>
1508 void
1509 list<_Tp, _Alloc>::push_front(value_type&& __x)
1510 {
1511     __node_pointer __node = this->__create_node(/* prev = */nullptr, /* next = */nullptr, std::move(__x));
1512     __link_pointer __nl = __node->__as_link();
1513     __link_nodes_at_front(__nl, __nl);
1514     ++base::__sz();
1515 }
1516
1517 template <class _Tp, class _Alloc>
1518 void
1519 list<_Tp, _Alloc>::push_back(value_type&& __x)
1520 {
1521     __node_pointer __node = this->__create_node(/* prev = */nullptr, /* next = */nullptr, std::move(__x));
1522     __link_pointer __nl = __node->__as_link();
1523     __link_nodes_at_back(__nl, __nl);
1524     ++base::__sz();
1525 }
1526
1527 template <class _Tp, class _Alloc>
1528 template <class... _Args>
1529 #if _LIBCPP_STD_VER >= 17
1530 typename list<_Tp, _Alloc>::reference
1531 #else
1532 void
1533 #endif
1534 list<_Tp, _Alloc>::emplace_front(_Args&&... __args)
1535 {
1536     __node_pointer __node = this->__create_node(/* prev = */nullptr, /* next = */nullptr, std::forward<_Args>(__args)...);
1537     __link_pointer __nl = __node->__as_link();
1538     __link_nodes_at_front(__nl, __nl);
1539     ++base::__sz();
1540 #if _LIBCPP_STD_VER >= 17
1541     return __node->__get_value();
1542 #endif
1543 }
1544
1545 template <class _Tp, class _Alloc>
1546 template <class... _Args>
1547 #if _LIBCPP_STD_VER >= 17
1548 typename list<_Tp, _Alloc>::reference
1549 #else
1550 void
1551 #endif
1552 list<_Tp, _Alloc>::emplace_back(_Args&&... __args)
1553 {
1554     __node_pointer __node = this->__create_node(/* prev = */nullptr, /* next = */nullptr, std::forward<_Args>(__args)...);
1555     __link_pointer __nl = __node->__as_link();
1556     __link_nodes_at_back(__nl, __nl);
1557     ++base::__sz();
1558 #if _LIBCPP_STD_VER >= 17
1559     return __node->__get_value();
1560 #endif
1561 }
1562
1563 template <class _Tp, class _Alloc>
1564 template <class... _Args>
1565 typename list<_Tp, _Alloc>::iterator
1566 list<_Tp, _Alloc>::emplace(const_iterator __p, _Args&&... __args)
1567 {
1568     __node_pointer __node = this->__create_node(/* prev = */nullptr, /* next = */nullptr, std::forward<_Args>(__args)...);
1569     __link_pointer __nl = __node->__as_link();
1570     __link_nodes(__p.__ptr_, __nl, __nl);
1571     ++base::__sz();
1572     return iterator(__nl);
1573 }
1574
1575 template <class _Tp, class _Alloc>
1576 typename list<_Tp, _Alloc>::iterator
1577 list<_Tp, _Alloc>::insert(const_iterator __p, value_type&& __x)
1578 {
1579     __node_pointer __node = this->__create_node(/* prev = */nullptr, /* next = */nullptr, std::move(__x));
1580     __link_pointer __nl = __node->__as_link();
1581     __link_nodes(__p.__ptr_, __nl, __nl);
1582     ++base::__sz();
1583     return iterator(__nl);
1584 }
1585
1586 #endif // _LIBCPP_CXX03_LANG
1587
1588 template <class _Tp, class _Alloc>
1589 void
1590 list<_Tp, _Alloc>::pop_front()
1591 {
1592     _LIBCPP_ASSERT_VALID_ELEMENT_ACCESS(!empty(), "list::pop_front() called with empty list");
1593     __link_pointer __n = base::__end_.__next_;
1594     base::__unlink_nodes(__n, __n);
1595     --base::__sz();
1596     this->__delete_node(__n->__as_node());
1597 }
1598
1599 template <class _Tp, class _Alloc>
1600 void
1601 list<_Tp, _Alloc>::pop_back()
1602 {
1603     _LIBCPP_ASSERT_VALID_ELEMENT_ACCESS(!empty(), "list::pop_back() called on an empty list");
1604     __link_pointer __n = base::__end_.__prev_;
1605     base::__unlink_nodes(__n, __n);
1606     --base::__sz();
1607     this->__delete_node(__n->__as_node());
1608 }
1609
1610 template <class _Tp, class _Alloc>
1611 typename list<_Tp, _Alloc>::iterator
1612 list<_Tp, _Alloc>::erase(const_iterator __p)
1613 {
1614     _LIBCPP_ASSERT_VALID_ELEMENT_ACCESS(__p != end(),
1615         "list::erase(iterator) called with a non-dereferenceable iterator");
1616     __link_pointer __n = __p.__ptr_;
1617     __link_pointer __r = __n->__next_;
1618     base::__unlink_nodes(__n, __n);
1619     --base::__sz();
1620     this->__delete_node(__n->__as_node());
1621     return iterator(__r);
1622 }
1623
1624 template <class _Tp, class _Alloc>
1625 typename list<_Tp, _Alloc>::iterator
1626 list<_Tp, _Alloc>::erase(const_iterator __f, const_iterator __l)
1627 {
1628     if (__f != __l)
1629     {
1630         base::__unlink_nodes(__f.__ptr_, __l.__ptr_->__prev_);
1631         while (__f != __l)
1632         {
1633             __link_pointer __n = __f.__ptr_;
1634             ++__f;
1635             --base::__sz();
1636             this->__delete_node(__n->__as_node());
1637         }
1638     }
1639     return iterator(__l.__ptr_);
1640 }
1641
1642 template <class _Tp, class _Alloc>
1643 void
1644 list<_Tp, _Alloc>::resize(size_type __n)
1645 {
1646     if (__n < base::__sz())
1647         erase(__iterator(__n), end());
1648     else if (__n > base::__sz())
1649     {
1650         __n -= base::__sz();
1651         size_type __ds = 0;
1652         __node_pointer __node = this->__create_node(/* prev = */nullptr, /* next = */nullptr);
1653         ++__ds;
1654         iterator __r = iterator(__node->__as_link());
1655         iterator __e = __r;
1656 #ifndef _LIBCPP_HAS_NO_EXCEPTIONS
1657         try
1658         {
1659 #endif // _LIBCPP_HAS_NO_EXCEPTIONS
1660             for (--__n; __n != 0; --__n, (void) ++__e, ++__ds)
1661             {
1662                 __e.__ptr_->__next_ = this->__create_node(/* prev = */__e.__ptr_, /* next = */nullptr)->__as_link();
1663             }
1664 #ifndef _LIBCPP_HAS_NO_EXCEPTIONS
1665         }
1666         catch (...)
1667         {
1668             while (true)
1669             {
1670                 __link_pointer __prev = __e.__ptr_->__prev_;
1671                 __node_pointer __current = __e.__ptr_->__as_node();
1672                 this->__delete_node(__current);
1673                 if (__prev == 0)
1674                     break;
1675                 __e = iterator(__prev);
1676             }
1677             throw;
1678         }
1679 #endif // _LIBCPP_HAS_NO_EXCEPTIONS
1680         __link_nodes_at_back(__r.__ptr_, __e.__ptr_);
1681         base::__sz() += __ds;
1682     }
1683 }
1684
1685 template <class _Tp, class _Alloc>
1686 void
1687 list<_Tp, _Alloc>::resize(size_type __n, const value_type& __x)
1688 {
1689     if (__n < base::__sz())
1690         erase(__iterator(__n), end());
1691     else if (__n > base::__sz())
1692     {
1693         __n -= base::__sz();
1694         size_type __ds = 0;
1695         __node_pointer __node = this->__create_node(/* prev = */nullptr, /* next = */nullptr, __x);
1696         ++__ds;
1697         __link_pointer __nl = __node->__as_link();
1698         iterator __r = iterator(__nl);
1699         iterator __e = __r;
1700 #ifndef _LIBCPP_HAS_NO_EXCEPTIONS
1701         try
1702         {
1703 #endif // _LIBCPP_HAS_NO_EXCEPTIONS
1704             for (--__n; __n != 0; --__n, (void) ++__e, ++__ds)
1705             {
1706                 __e.__ptr_->__next_ = this->__create_node(/* prev = */__e.__ptr_, /* next = */nullptr, __x)->__as_link();
1707             }
1708 #ifndef _LIBCPP_HAS_NO_EXCEPTIONS
1709         }
1710         catch (...)
1711         {
1712             while (true)
1713             {
1714                 __link_pointer __prev = __e.__ptr_->__prev_;
1715                 __node_pointer __current = __e.__ptr_->__as_node();
1716                 this->__delete_node(__current);
1717                 if (__prev == 0)
1718                     break;
1719                 __e = iterator(__prev);
1720             }
1721             throw;
1722         }
1723 #endif // _LIBCPP_HAS_NO_EXCEPTIONS
1724         __link_nodes(base::__end_as_link(), __r.__ptr_, __e.__ptr_);
1725         base::__sz() += __ds;
1726     }
1727 }
1728
1729 template <class _Tp, class _Alloc>
1730 void
1731 list<_Tp, _Alloc>::splice(const_iterator __p, list& __c)
1732 {
1733     _LIBCPP_ASSERT_VALID_INPUT_RANGE(this != _VSTD::addressof(__c),
1734                                      "list::splice(iterator, list) called with this == &list");
1735     if (!__c.empty())
1736     {
1737         __link_pointer __f = __c.__end_.__next_;
1738         __link_pointer __l = __c.__end_.__prev_;
1739         base::__unlink_nodes(__f, __l);
1740         __link_nodes(__p.__ptr_, __f, __l);
1741         base::__sz() += __c.__sz();
1742         __c.__sz() = 0;
1743     }
1744 }
1745
1746 template <class _Tp, class _Alloc>
1747 void
1748 list<_Tp, _Alloc>::splice(const_iterator __p, list& __c, const_iterator __i)
1749 {
1750     if (__p.__ptr_ != __i.__ptr_ && __p.__ptr_ != __i.__ptr_->__next_)
1751     {
1752         __link_pointer __f = __i.__ptr_;
1753         base::__unlink_nodes(__f, __f);
1754         __link_nodes(__p.__ptr_, __f, __f);
1755         --__c.__sz();
1756         ++base::__sz();
1757     }
1758 }
1759
1760 template <class _Tp, class _Alloc>
1761 void
1762 list<_Tp, _Alloc>::splice(const_iterator __p, list& __c, const_iterator __f, const_iterator __l)
1763 {
1764     if (__f != __l)
1765     {
1766         __link_pointer __first = __f.__ptr_;
1767         --__l;
1768         __link_pointer __last = __l.__ptr_;
1769         if (this != _VSTD::addressof(__c))
1770         {
1771             size_type __s = _VSTD::distance(__f, __l) + 1;
1772             __c.__sz() -= __s;
1773             base::__sz() += __s;
1774         }
1775         base::__unlink_nodes(__first, __last);
1776         __link_nodes(__p.__ptr_, __first, __last);
1777     }
1778 }
1779
1780 template <class _Tp, class _Alloc>
1781 typename list<_Tp, _Alloc>::__remove_return_type
1782 list<_Tp, _Alloc>::remove(const value_type& __x)
1783 {
1784     list<_Tp, _Alloc> __deleted_nodes(get_allocator()); // collect the nodes we're removing
1785     for (const_iterator __i = begin(), __e = end(); __i != __e;)
1786     {
1787         if (*__i == __x)
1788         {
1789             const_iterator __j = _VSTD::next(__i);
1790             for (; __j != __e && *__j == __x; ++__j)
1791                 ;
1792             __deleted_nodes.splice(__deleted_nodes.end(), *this, __i, __j);
1793             __i = __j;
1794             if (__i != __e)
1795                 ++__i;
1796         }
1797         else
1798             ++__i;
1799     }
1800
1801     return (__remove_return_type) __deleted_nodes.size();
1802 }
1803
1804 template <class _Tp, class _Alloc>
1805 template <class _Pred>
1806 typename list<_Tp, _Alloc>::__remove_return_type
1807 list<_Tp, _Alloc>::remove_if(_Pred __pred)
1808 {
1809     list<_Tp, _Alloc> __deleted_nodes(get_allocator()); // collect the nodes we're removing
1810     for (iterator __i = begin(), __e = end(); __i != __e;)
1811     {
1812         if (__pred(*__i))
1813         {
1814             iterator __j = _VSTD::next(__i);
1815             for (; __j != __e && __pred(*__j); ++__j)
1816                 ;
1817             __deleted_nodes.splice(__deleted_nodes.end(), *this, __i, __j);
1818             __i = __j;
1819             if (__i != __e)
1820                 ++__i;
1821         }
1822         else
1823             ++__i;
1824     }
1825
1826     return (__remove_return_type) __deleted_nodes.size();
1827 }
1828
1829 template <class _Tp, class _Alloc>
1830 template <class _BinaryPred>
1831 typename list<_Tp, _Alloc>::__remove_return_type
1832 list<_Tp, _Alloc>::unique(_BinaryPred __binary_pred)
1833 {
1834     list<_Tp, _Alloc> __deleted_nodes(get_allocator()); // collect the nodes we're removing
1835     for (iterator __i = begin(), __e = end(); __i != __e;)
1836     {
1837         iterator __j = _VSTD::next(__i);
1838         for (; __j != __e && __binary_pred(*__i, *__j); ++__j)
1839             ;
1840         if (++__i != __j) {
1841             __deleted_nodes.splice(__deleted_nodes.end(), *this, __i, __j);
1842             __i = __j;
1843             }
1844     }
1845
1846     return (__remove_return_type) __deleted_nodes.size();
1847 }
1848
1849 template <class _Tp, class _Alloc>
1850 inline
1851 void
1852 list<_Tp, _Alloc>::merge(list& __c)
1853 {
1854     merge(__c, __less<>());
1855 }
1856
1857 template <class _Tp, class _Alloc>
1858 template <class _Comp>
1859 void
1860 list<_Tp, _Alloc>::merge(list& __c, _Comp __comp)
1861 {
1862     if (this != _VSTD::addressof(__c))
1863     {
1864         iterator __f1 = begin();
1865         iterator __e1 = end();
1866         iterator __f2 = __c.begin();
1867         iterator __e2 = __c.end();
1868         while (__f1 != __e1 && __f2 != __e2)
1869         {
1870             if (__comp(*__f2, *__f1))
1871             {
1872                 size_type __ds = 1;
1873                 iterator __m2 = _VSTD::next(__f2);
1874                 for (; __m2 != __e2 && __comp(*__m2, *__f1); ++__m2, (void) ++__ds)
1875                     ;
1876                 base::__sz() += __ds;
1877                 __c.__sz() -= __ds;
1878                 __link_pointer __f = __f2.__ptr_;
1879                 __link_pointer __l = __m2.__ptr_->__prev_;
1880                 __f2 = __m2;
1881                 base::__unlink_nodes(__f, __l);
1882                 __m2 = _VSTD::next(__f1);
1883                 __link_nodes(__f1.__ptr_, __f, __l);
1884                 __f1 = __m2;
1885             }
1886             else
1887                 ++__f1;
1888         }
1889         splice(__e1, __c);
1890     }
1891 }
1892
1893 template <class _Tp, class _Alloc>
1894 inline
1895 void
1896 list<_Tp, _Alloc>::sort()
1897 {
1898     sort(__less<>());
1899 }
1900
1901 template <class _Tp, class _Alloc>
1902 template <class _Comp>
1903 inline
1904 void
1905 list<_Tp, _Alloc>::sort(_Comp __comp)
1906 {
1907     __sort(begin(), end(), base::__sz(), __comp);
1908 }
1909
1910 template <class _Tp, class _Alloc>
1911 template <class _Comp>
1912 typename list<_Tp, _Alloc>::iterator
1913 list<_Tp, _Alloc>::__sort(iterator __f1, iterator __e2, size_type __n, _Comp& __comp)
1914 {
1915     switch (__n)
1916     {
1917     case 0:
1918     case 1:
1919         return __f1;
1920     case 2:
1921         if (__comp(*--__e2, *__f1))
1922         {
1923             __link_pointer __f = __e2.__ptr_;
1924             base::__unlink_nodes(__f, __f);
1925             __link_nodes(__f1.__ptr_, __f, __f);
1926             return __e2;
1927         }
1928         return __f1;
1929     }
1930     size_type __n2 = __n / 2;
1931     iterator __e1 = _VSTD::next(__f1, __n2);
1932     iterator  __r = __f1 = __sort(__f1, __e1, __n2, __comp);
1933     iterator __f2 = __e1 = __sort(__e1, __e2, __n - __n2, __comp);
1934     if (__comp(*__f2, *__f1))
1935     {
1936         iterator __m2 = _VSTD::next(__f2);
1937         for (; __m2 != __e2 && __comp(*__m2, *__f1); ++__m2)
1938             ;
1939         __link_pointer __f = __f2.__ptr_;
1940         __link_pointer __l = __m2.__ptr_->__prev_;
1941         __r = __f2;
1942         __e1 = __f2 = __m2;
1943         base::__unlink_nodes(__f, __l);
1944         __m2 = _VSTD::next(__f1);
1945         __link_nodes(__f1.__ptr_, __f, __l);
1946         __f1 = __m2;
1947     }
1948     else
1949         ++__f1;
1950     while (__f1 != __e1 && __f2 != __e2)
1951     {
1952         if (__comp(*__f2, *__f1))
1953         {
1954             iterator __m2 = _VSTD::next(__f2);
1955             for (; __m2 != __e2 && __comp(*__m2, *__f1); ++__m2)
1956                 ;
1957             __link_pointer __f = __f2.__ptr_;
1958             __link_pointer __l = __m2.__ptr_->__prev_;
1959             if (__e1 == __f2)
1960                 __e1 = __m2;
1961             __f2 = __m2;
1962             base::__unlink_nodes(__f, __l);
1963             __m2 = _VSTD::next(__f1);
1964             __link_nodes(__f1.__ptr_, __f, __l);
1965             __f1 = __m2;
1966         }
1967         else
1968             ++__f1;
1969     }
1970     return __r;
1971 }
1972
1973 template <class _Tp, class _Alloc>
1974 void
1975 list<_Tp, _Alloc>::reverse() _NOEXCEPT
1976 {
1977     if (base::__sz() > 1)
1978     {
1979         iterator __e = end();
1980         for (iterator __i = begin(); __i.__ptr_ != __e.__ptr_;)
1981         {
1982             _VSTD::swap(__i.__ptr_->__prev_, __i.__ptr_->__next_);
1983             __i.__ptr_ = __i.__ptr_->__prev_;
1984         }
1985         _VSTD::swap(__e.__ptr_->__prev_, __e.__ptr_->__next_);
1986     }
1987 }
1988
1989 template <class _Tp, class _Alloc>
1990 bool
1991 list<_Tp, _Alloc>::__invariants() const
1992 {
1993     return size() == _VSTD::distance(begin(), end());
1994 }
1995
1996 template <class _Tp, class _Alloc>
1997 inline _LIBCPP_INLINE_VISIBILITY
1998 bool
1999 operator==(const list<_Tp, _Alloc>& __x, const list<_Tp, _Alloc>& __y)
2000 {
2001     return __x.size() == __y.size() && _VSTD::equal(__x.begin(), __x.end(), __y.begin());
2002 }
2003
2004 #if _LIBCPP_STD_VER <= 17
2005
2006 template <class _Tp, class _Alloc>
2007 inline _LIBCPP_INLINE_VISIBILITY
2008 bool
2009 operator< (const list<_Tp, _Alloc>& __x, const list<_Tp, _Alloc>& __y)
2010 {
2011     return _VSTD::lexicographical_compare(__x.begin(), __x.end(), __y.begin(), __y.end());
2012 }
2013
2014 template <class _Tp, class _Alloc>
2015 inline _LIBCPP_INLINE_VISIBILITY
2016 bool
2017 operator!=(const list<_Tp, _Alloc>& __x, const list<_Tp, _Alloc>& __y)
2018 {
2019     return !(__x == __y);
2020 }
2021
2022 template <class _Tp, class _Alloc>
2023 inline _LIBCPP_INLINE_VISIBILITY
2024 bool
2025 operator> (const list<_Tp, _Alloc>& __x, const list<_Tp, _Alloc>& __y)
2026 {
2027     return __y < __x;
2028 }
2029
2030 template <class _Tp, class _Alloc>
2031 inline _LIBCPP_INLINE_VISIBILITY
2032 bool
2033 operator>=(const list<_Tp, _Alloc>& __x, const list<_Tp, _Alloc>& __y)
2034 {
2035     return !(__x < __y);
2036 }
2037
2038 template <class _Tp, class _Alloc>
2039 inline _LIBCPP_INLINE_VISIBILITY
2040 bool
2041 operator<=(const list<_Tp, _Alloc>& __x, const list<_Tp, _Alloc>& __y)
2042 {
2043     return !(__y < __x);
2044 }
2045
2046 #else // _LIBCPP_STD_VER <= 17
2047
2048 template <class _Tp, class _Allocator>
2049 _LIBCPP_HIDE_FROM_ABI __synth_three_way_result<_Tp>
2050 operator<=>(const list<_Tp, _Allocator>& __x, const list<_Tp, _Allocator>& __y) {
2051     return std::lexicographical_compare_three_way(
2052         __x.begin(), __x.end(), __y.begin(), __y.end(), std::__synth_three_way<_Tp, _Tp>);
2053 }
2054
2055 #endif // _LIBCPP_STD_VER <= 17
2056
2057 template <class _Tp, class _Alloc>
2058 inline _LIBCPP_INLINE_VISIBILITY
2059 void
2060 swap(list<_Tp, _Alloc>& __x, list<_Tp, _Alloc>& __y)
2061     _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y)))
2062 {
2063     __x.swap(__y);
2064 }
2065
2066 #if _LIBCPP_STD_VER >= 20
2067 template <class _Tp, class _Allocator, class _Predicate>
2068 inline _LIBCPP_INLINE_VISIBILITY typename list<_Tp, _Allocator>::size_type
2069 erase_if(list<_Tp, _Allocator>& __c, _Predicate __pred) {
2070   return __c.remove_if(__pred);
2071 }
2072
2073 template <class _Tp, class _Allocator, class _Up>
2074 inline _LIBCPP_INLINE_VISIBILITY typename list<_Tp, _Allocator>::size_type
2075 erase(list<_Tp, _Allocator>& __c, const _Up& __v) {
2076   return _VSTD::erase_if(__c, [&](auto& __elem) { return __elem == __v; });
2077 }
2078
2079 template <>
2080 inline constexpr bool __format::__enable_insertable<std::list<char>> = true;
2081 #ifndef _LIBCPP_HAS_NO_WIDE_CHARACTERS
2082 template <>
2083 inline constexpr bool __format::__enable_insertable<std::list<wchar_t>> = true;
2084 #endif
2085
2086 #endif // _LIBCPP_STD_VER >= 20
2087
2088 _LIBCPP_END_NAMESPACE_STD
2089
2090 #if _LIBCPP_STD_VER >= 17
2091 _LIBCPP_BEGIN_NAMESPACE_STD
2092 namespace pmr {
2093 template <class _ValueT>
2094 using list _LIBCPP_AVAILABILITY_PMR = std::list<_ValueT, polymorphic_allocator<_ValueT>>;
2095 } // namespace pmr
2096 _LIBCPP_END_NAMESPACE_STD
2097 #endif
2098
2099 _LIBCPP_POP_MACROS
2100
2101 #if !defined(_LIBCPP_REMOVE_TRANSITIVE_INCLUDES) && _LIBCPP_STD_VER <= 20
2102 #  include <algorithm>
2103 #  include <atomic>
2104 #  include <concepts>
2105 #  include <cstdint>
2106 #  include <cstdlib>
2107 #  include <functional>
2108 #  include <iosfwd>
2109 #  include <iterator>
2110 #  include <stdexcept>
2111 #  include <type_traits>
2112 #  include <typeinfo>
2113 #endif
2114
2115 #endif // _LIBCPP_LIST