libcxx/include/__cxx03/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 <__cxx03/__algorithm/comp.h>
 201 #include <__cxx03/__algorithm/equal.h>
 202 #include <__cxx03/__algorithm/lexicographical_compare.h>
 203 #include <__cxx03/__algorithm/lexicographical_compare_three_way.h>
 204 #include <__cxx03/__algorithm/min.h>
 205 #include <__cxx03/__assert>
 206 #include <__cxx03/__config>
 207 #include <__cxx03/__format/enable_insertable.h>
 208 #include <__cxx03/__iterator/distance.h>
 209 #include <__cxx03/__iterator/iterator_traits.h>
 210 #include <__cxx03/__iterator/move_iterator.h>
 211 #include <__cxx03/__iterator/next.h>
 212 #include <__cxx03/__iterator/prev.h>
 213 #include <__cxx03/__iterator/reverse_iterator.h>
 214 #include <__cxx03/__memory/addressof.h>
 215 #include <__cxx03/__memory/allocation_guard.h>
 216 #include <__cxx03/__memory/allocator.h>
 217 #include <__cxx03/__memory/allocator_traits.h>
 218 #include <__cxx03/__memory/compressed_pair.h>
 219 #include <__cxx03/__memory/construct_at.h>
 220 #include <__cxx03/__memory/pointer_traits.h>
 221 #include <__cxx03/__memory/swap_allocator.h>
 222 #include <__cxx03/__memory_resource/polymorphic_allocator.h>
 223 #include <__cxx03/__ranges/access.h>
 224 #include <__cxx03/__ranges/concepts.h>
 225 #include <__cxx03/__ranges/container_compatible_range.h>
 226 #include <__cxx03/__ranges/from_range.h>
 227 #include <__cxx03/__type_traits/conditional.h>
 228 #include <__cxx03/__type_traits/is_allocator.h>
 229 #include <__cxx03/__type_traits/is_nothrow_assignable.h>
 230 #include <__cxx03/__type_traits/is_nothrow_constructible.h>
 231 #include <__cxx03/__type_traits/is_pointer.h>
 232 #include <__cxx03/__type_traits/is_same.h>
 233 #include <__cxx03/__type_traits/type_identity.h>
 234 #include <__cxx03/__utility/forward.h>
 235 #include <__cxx03/__utility/move.h>
 236 #include <__cxx03/__utility/swap.h>
 237 #include <__cxx03/cstring>
 238 #include <__cxx03/limits>
 239 #include <__cxx03/new> // __launder
 240 #include <__cxx03/version>
 241
 242 // standard-mandated includes
 243
 244 // [iterator.range]
 245 #include <__cxx03/__iterator/access.h>
 246 #include <__cxx03/__iterator/data.h>
 247 #include <__cxx03/__iterator/empty.h>
 248 #include <__cxx03/__iterator/reverse_access.h>
 249 #include <__cxx03/__iterator/size.h>
 250
 251 // [list.syn]
 252 #include <__cxx03/compare>
 253 #include <__cxx03/initializer_list>
 254
 255 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
 256 #  pragma GCC system_header
 257 #endif
 258
 259 _LIBCPP_PUSH_MACROS
 260 #include <__cxx03/__undef_macros>
 261
 262 _LIBCPP_BEGIN_NAMESPACE_STD
 263
 264 template <class _Tp, class _VoidPtr>
 265 struct __list_node;
 266 template <class _Tp, class _VoidPtr>
 267 struct __list_node_base;
 268
 269 template <class _Tp, class _VoidPtr>
 270 struct __list_node_pointer_traits {
 271   typedef __rebind_pointer_t<_VoidPtr, __list_node<_Tp, _VoidPtr> > __node_pointer;
 272   typedef __rebind_pointer_t<_VoidPtr, __list_node_base<_Tp, _VoidPtr> > __base_pointer;
 273
 274 #if defined(_LIBCPP_ABI_LIST_REMOVE_NODE_POINTER_UB)
 275   typedef __base_pointer __link_pointer;
 276 #else
 277   typedef __conditional_t<is_pointer<_VoidPtr>::value, __base_pointer, __node_pointer> __link_pointer;
 278 #endif
 279
 280   typedef __conditional_t<is_same<__link_pointer, __node_pointer>::value, __base_pointer, __node_pointer>
 281       __non_link_pointer;
 282
 283   static _LIBCPP_HIDE_FROM_ABI __link_pointer __unsafe_link_pointer_cast(__link_pointer __p) { return __p; }
 284
 285   static _LIBCPP_HIDE_FROM_ABI __link_pointer __unsafe_link_pointer_cast(__non_link_pointer __p) {
 286     return static_cast<__link_pointer>(static_cast<_VoidPtr>(__p));
 287   }
 288 };
 289
 290 template <class _Tp, class _VoidPtr>
 291 struct __list_node_base {
 292   typedef __list_node_pointer_traits<_Tp, _VoidPtr> _NodeTraits;
 293   typedef typename _NodeTraits::__node_pointer __node_pointer;
 294   typedef typename _NodeTraits::__base_pointer __base_pointer;
 295   typedef typename _NodeTraits::__link_pointer __link_pointer;
 296
 297   __link_pointer __prev_;
 298   __link_pointer __next_;
 299
 300   _LIBCPP_HIDE_FROM_ABI __list_node_base()
 301       : __prev_(_NodeTraits::__unsafe_link_pointer_cast(__self())),
 302         __next_(_NodeTraits::__unsafe_link_pointer_cast(__self())) {}
 303
 304   _LIBCPP_HIDE_FROM_ABI explicit __list_node_base(__link_pointer __prev, __link_pointer __next)
 305       : __prev_(__prev), __next_(__next) {}
 306
 307   _LIBCPP_HIDE_FROM_ABI __base_pointer __self() { return pointer_traits<__base_pointer>::pointer_to(*this); }
 308
 309   _LIBCPP_HIDE_FROM_ABI __node_pointer __as_node() { return static_cast<__node_pointer>(__self()); }
 310 };
 311
 312 template <class _Tp, class _VoidPtr>
 313 struct __list_node : public __list_node_base<_Tp, _VoidPtr> {
 314   // We allow starting the lifetime of nodes without initializing the value held by the node,
 315   // since that is handled by the list itself in order to be allocator-aware.
 316 #ifndef _LIBCPP_CXX03_LANG
 317
 318 private:
 319   union {
 320     _Tp __value_;
 321   };
 322
 323 public:
 324   _LIBCPP_HIDE_FROM_ABI _Tp& __get_value() { return __value_; }
 325 #else
 326
 327 private:
 328   _ALIGNAS_TYPE(_Tp) char __buffer_[sizeof(_Tp)];
 329
 330 public:
 331   _LIBCPP_HIDE_FROM_ABI _Tp& __get_value() { return *std::__launder(reinterpret_cast<_Tp*>(&__buffer_)); }
 332 #endif
 333
 334   typedef __list_node_base<_Tp, _VoidPtr> __base;
 335   typedef typename __base::__link_pointer __link_pointer;
 336
 337   _LIBCPP_HIDE_FROM_ABI explicit __list_node(__link_pointer __prev, __link_pointer __next) : __base(__prev, __next) {}
 338   _LIBCPP_HIDE_FROM_ABI ~__list_node() {}
 339
 340   _LIBCPP_HIDE_FROM_ABI __link_pointer __as_link() { return static_cast<__link_pointer>(__base::__self()); }
 341 };
 342
 343 template <class _Tp, class _Alloc = allocator<_Tp> >
 344 class _LIBCPP_TEMPLATE_VIS list;
 345 template <class _Tp, class _Alloc>
 346 class __list_imp;
 347 template <class _Tp, class _VoidPtr>
 348 class _LIBCPP_TEMPLATE_VIS __list_const_iterator;
 349
 350 template <class _Tp, class _VoidPtr>
 351 class _LIBCPP_TEMPLATE_VIS __list_iterator {
 352   typedef __list_node_pointer_traits<_Tp, _VoidPtr> _NodeTraits;
 353   typedef typename _NodeTraits::__link_pointer __link_pointer;
 354
 355   __link_pointer __ptr_;
 356
 357   _LIBCPP_HIDE_FROM_ABI explicit __list_iterator(__link_pointer __p) _NOEXCEPT : __ptr_(__p) {}
 358
 359   template <class, class>
 360   friend class list;
 361   template <class, class>
 362   friend class __list_imp;
 363   template <class, class>
 364   friend class __list_const_iterator;
 365
 366 public:
 367   typedef bidirectional_iterator_tag iterator_category;
 368   typedef _Tp value_type;
 369   typedef value_type& reference;
 370   typedef __rebind_pointer_t<_VoidPtr, value_type> pointer;
 371   typedef typename pointer_traits<pointer>::difference_type difference_type;
 372
 373   _LIBCPP_HIDE_FROM_ABI __list_iterator() _NOEXCEPT : __ptr_(nullptr) {}
 374
 375   _LIBCPP_HIDE_FROM_ABI reference operator*() const { return __ptr_->__as_node()->__get_value(); }
 376   _LIBCPP_HIDE_FROM_ABI pointer operator->() const {
 377     return pointer_traits<pointer>::pointer_to(__ptr_->__as_node()->__get_value());
 378   }
 379
 380   _LIBCPP_HIDE_FROM_ABI __list_iterator& operator++() {
 381     __ptr_ = __ptr_->__next_;
 382     return *this;
 383   }
 384   _LIBCPP_HIDE_FROM_ABI __list_iterator operator++(int) {
 385     __list_iterator __t(*this);
 386     ++(*this);
 387     return __t;
 388   }
 389
 390   _LIBCPP_HIDE_FROM_ABI __list_iterator& operator--() {
 391     __ptr_ = __ptr_->__prev_;
 392     return *this;
 393   }
 394   _LIBCPP_HIDE_FROM_ABI __list_iterator operator--(int) {
 395     __list_iterator __t(*this);
 396     --(*this);
 397     return __t;
 398   }
 399
 400   friend _LIBCPP_HIDE_FROM_ABI bool operator==(const __list_iterator& __x, const __list_iterator& __y) {
 401     return __x.__ptr_ == __y.__ptr_;
 402   }
 403   friend _LIBCPP_HIDE_FROM_ABI bool operator!=(const __list_iterator& __x, const __list_iterator& __y) {
 404     return !(__x == __y);
 405   }
 406 };
 407
 408 template <class _Tp, class _VoidPtr>
 409 class _LIBCPP_TEMPLATE_VIS __list_const_iterator {
 410   typedef __list_node_pointer_traits<_Tp, _VoidPtr> _NodeTraits;
 411   typedef typename _NodeTraits::__link_pointer __link_pointer;
 412
 413   __link_pointer __ptr_;
 414
 415   _LIBCPP_HIDE_FROM_ABI explicit __list_const_iterator(__link_pointer __p) _NOEXCEPT : __ptr_(__p) {}
 416
 417   template <class, class>
 418   friend class list;
 419   template <class, class>
 420   friend class __list_imp;
 421
 422 public:
 423   typedef bidirectional_iterator_tag iterator_category;
 424   typedef _Tp value_type;
 425   typedef const value_type& reference;
 426   typedef __rebind_pointer_t<_VoidPtr, const value_type> pointer;
 427   typedef typename pointer_traits<pointer>::difference_type difference_type;
 428
 429   _LIBCPP_HIDE_FROM_ABI __list_const_iterator() _NOEXCEPT : __ptr_(nullptr) {}
 430   _LIBCPP_HIDE_FROM_ABI __list_const_iterator(const __list_iterator<_Tp, _VoidPtr>& __p) _NOEXCEPT
 431       : __ptr_(__p.__ptr_) {}
 432
 433   _LIBCPP_HIDE_FROM_ABI reference operator*() const { return __ptr_->__as_node()->__get_value(); }
 434   _LIBCPP_HIDE_FROM_ABI pointer operator->() const {
 435     return pointer_traits<pointer>::pointer_to(__ptr_->__as_node()->__get_value());
 436   }
 437
 438   _LIBCPP_HIDE_FROM_ABI __list_const_iterator& operator++() {
 439     __ptr_ = __ptr_->__next_;
 440     return *this;
 441   }
 442   _LIBCPP_HIDE_FROM_ABI __list_const_iterator operator++(int) {
 443     __list_const_iterator __t(*this);
 444     ++(*this);
 445     return __t;
 446   }
 447
 448   _LIBCPP_HIDE_FROM_ABI __list_const_iterator& operator--() {
 449     __ptr_ = __ptr_->__prev_;
 450     return *this;
 451   }
 452   _LIBCPP_HIDE_FROM_ABI __list_const_iterator operator--(int) {
 453     __list_const_iterator __t(*this);
 454     --(*this);
 455     return __t;
 456   }
 457
 458   friend _LIBCPP_HIDE_FROM_ABI bool operator==(const __list_const_iterator& __x, const __list_const_iterator& __y) {
 459     return __x.__ptr_ == __y.__ptr_;
 460   }
 461   friend _LIBCPP_HIDE_FROM_ABI bool operator!=(const __list_const_iterator& __x, const __list_const_iterator& __y) {
 462     return !(__x == __y);
 463   }
 464 };
 465
 466 template <class _Tp, class _Alloc>
 467 class __list_imp {
 468 public:
 469   __list_imp(const __list_imp&)            = delete;
 470   __list_imp& operator=(const __list_imp&) = delete;
 471
 472   typedef _Alloc allocator_type;
 473   typedef allocator_traits<allocator_type> __alloc_traits;
 474   typedef typename __alloc_traits::size_type size_type;
 475
 476 protected:
 477   typedef _Tp value_type;
 478   typedef typename __alloc_traits::void_pointer __void_pointer;
 479   typedef __list_iterator<value_type, __void_pointer> iterator;
 480   typedef __list_const_iterator<value_type, __void_pointer> const_iterator;
 481   typedef __list_node_base<value_type, __void_pointer> __node_base;
 482   typedef __list_node<value_type, __void_pointer> __node_type;
 483   typedef __rebind_alloc<__alloc_traits, __node_type> __node_allocator;
 484   typedef allocator_traits<__node_allocator> __node_alloc_traits;
 485   typedef typename __node_alloc_traits::pointer __node_pointer;
 486   typedef typename __node_alloc_traits::pointer __node_const_pointer;
 487   typedef __list_node_pointer_traits<value_type, __void_pointer> __node_pointer_traits;
 488   typedef typename __node_pointer_traits::__link_pointer __link_pointer;
 489   typedef __link_pointer __link_const_pointer;
 490   typedef typename __alloc_traits::pointer pointer;
 491   typedef typename __alloc_traits::const_pointer const_pointer;
 492   typedef typename __alloc_traits::difference_type difference_type;
 493
 494   typedef __rebind_alloc<__alloc_traits, __node_base> __node_base_allocator;
 495   typedef typename allocator_traits<__node_base_allocator>::pointer __node_base_pointer;
 496   static_assert(!is_same<allocator_type, __node_allocator>::value,
 497                 "internal allocator type must differ from user-specified type; otherwise overload resolution breaks");
 498
 499   __node_base __end_;
 500   __compressed_pair<size_type, __node_allocator> __size_alloc_;
 501
 502   _LIBCPP_HIDE_FROM_ABI __link_pointer __end_as_link() const _NOEXCEPT {
 503     return __node_pointer_traits::__unsafe_link_pointer_cast(const_cast<__node_base&>(__end_).__self());
 504   }
 505
 506   _LIBCPP_HIDE_FROM_ABI size_type& __sz() _NOEXCEPT { return __size_alloc_.first(); }
 507   _LIBCPP_HIDE_FROM_ABI const size_type& __sz() const _NOEXCEPT { return __size_alloc_.first(); }
 508   _LIBCPP_HIDE_FROM_ABI __node_allocator& __node_alloc() _NOEXCEPT { return __size_alloc_.second(); }
 509   _LIBCPP_HIDE_FROM_ABI const __node_allocator& __node_alloc() const _NOEXCEPT { return __size_alloc_.second(); }
 510
 511   _LIBCPP_HIDE_FROM_ABI size_type __node_alloc_max_size() const _NOEXCEPT {
 512     return __node_alloc_traits::max_size(__node_alloc());
 513   }
 514   _LIBCPP_HIDE_FROM_ABI static void __unlink_nodes(__link_pointer __f, __link_pointer __l) _NOEXCEPT;
 515
 516   _LIBCPP_HIDE_FROM_ABI __list_imp() _NOEXCEPT_(is_nothrow_default_constructible<__node_allocator>::value);
 517   _LIBCPP_HIDE_FROM_ABI __list_imp(const allocator_type& __a);
 518   _LIBCPP_HIDE_FROM_ABI __list_imp(const __node_allocator& __a);
 519 #ifndef _LIBCPP_CXX03_LANG
 520   _LIBCPP_HIDE_FROM_ABI __list_imp(__node_allocator&& __a) _NOEXCEPT;
 521 #endif
 522   _LIBCPP_HIDE_FROM_ABI ~__list_imp();
 523   _LIBCPP_HIDE_FROM_ABI void clear() _NOEXCEPT;
 524   _LIBCPP_HIDE_FROM_ABI bool empty() const _NOEXCEPT { return __sz() == 0; }
 525
 526   _LIBCPP_HIDE_FROM_ABI iterator begin() _NOEXCEPT { return iterator(__end_.__next_); }
 527   _LIBCPP_HIDE_FROM_ABI const_iterator begin() const _NOEXCEPT { return const_iterator(__end_.__next_); }
 528   _LIBCPP_HIDE_FROM_ABI iterator end() _NOEXCEPT { return iterator(__end_as_link()); }
 529   _LIBCPP_HIDE_FROM_ABI const_iterator end() const _NOEXCEPT { return const_iterator(__end_as_link()); }
 530
 531   _LIBCPP_HIDE_FROM_ABI void swap(__list_imp& __c)
 532 #if _LIBCPP_STD_VER >= 14
 533       _NOEXCEPT;
 534 #else
 535       _NOEXCEPT_(!__alloc_traits::propagate_on_container_swap::value || __is_nothrow_swappable_v<allocator_type>);
 536 #endif
 537
 538   _LIBCPP_HIDE_FROM_ABI void __copy_assign_alloc(const __list_imp& __c) {
 539     __copy_assign_alloc(
 540         __c, integral_constant<bool, __node_alloc_traits::propagate_on_container_copy_assignment::value>());
 541   }
 542
 543   _LIBCPP_HIDE_FROM_ABI void __move_assign_alloc(__list_imp& __c)
 544       _NOEXCEPT_(!__node_alloc_traits::propagate_on_container_move_assignment::value ||
 545                  is_nothrow_move_assignable<__node_allocator>::value) {
 546     __move_assign_alloc(
 547         __c, integral_constant<bool, __node_alloc_traits::propagate_on_container_move_assignment::value>());
 548   }
 549
 550   template <class... _Args>
 551   _LIBCPP_HIDE_FROM_ABI __node_pointer __create_node(__link_pointer __prev, __link_pointer __next, _Args&&... __args) {
 552     __node_allocator& __alloc = __node_alloc();
 553     __allocation_guard<__node_allocator> __guard(__alloc, 1);
 554     // Begin the lifetime of the node itself. Note that this doesn't begin the lifetime of the value
 555     // held inside the node, since we need to use the allocator's construct() method for that.
 556     //
 557     // We don't use the allocator's construct() method to construct the node itself since the
 558     // Cpp17FooInsertable named requirements don't require the allocator's construct() method
 559     // to work on anything other than the value_type.
 560     std::__construct_at(std::addressof(*__guard.__get()), __prev, __next);
 561
 562     // Now construct the value_type using the allocator's construct() method.
 563     __node_alloc_traits::construct(
 564         __alloc, std::addressof(__guard.__get()->__get_value()), std::forward<_Args>(__args)...);
 565     return __guard.__release_ptr();
 566   }
 567
 568   _LIBCPP_HIDE_FROM_ABI void __delete_node(__node_pointer __node) {
 569     // For the same reason as above, we use the allocator's destroy() method for the value_type,
 570     // but not for the node itself.
 571     __node_allocator& __alloc = __node_alloc();
 572     __node_alloc_traits::destroy(__alloc, std::addressof(__node->__get_value()));
 573     std::__destroy_at(std::addressof(*__node));
 574     __node_alloc_traits::deallocate(__alloc, __node, 1);
 575   }
 576
 577 private:
 578   _LIBCPP_HIDE_FROM_ABI void __copy_assign_alloc(const __list_imp& __c, true_type) {
 579     if (__node_alloc() != __c.__node_alloc())
 580       clear();
 581     __node_alloc() = __c.__node_alloc();
 582   }
 583
 584   _LIBCPP_HIDE_FROM_ABI void __copy_assign_alloc(const __list_imp&, false_type) {}
 585
 586   _LIBCPP_HIDE_FROM_ABI void __move_assign_alloc(__list_imp& __c, true_type)
 587       _NOEXCEPT_(is_nothrow_move_assignable<__node_allocator>::value) {
 588     __node_alloc() = std::move(__c.__node_alloc());
 589   }
 590
 591   _LIBCPP_HIDE_FROM_ABI void __move_assign_alloc(__list_imp&, false_type) _NOEXCEPT {}
 592 };
 593
 594 // Unlink nodes [__f, __l]
 595 template <class _Tp, class _Alloc>
 596 inline void __list_imp<_Tp, _Alloc>::__unlink_nodes(__link_pointer __f, __link_pointer __l) _NOEXCEPT {
 597   __f->__prev_->__next_ = __l->__next_;
 598   __l->__next_->__prev_ = __f->__prev_;
 599 }
 600
 601 template <class _Tp, class _Alloc>
 602 inline __list_imp<_Tp, _Alloc>::__list_imp() _NOEXCEPT_(is_nothrow_default_constructible<__node_allocator>::value)
 603     : __size_alloc_(0, __default_init_tag()) {}
 604
 605 template <class _Tp, class _Alloc>
 606 inline __list_imp<_Tp, _Alloc>::__list_imp(const allocator_type& __a) : __size_alloc_(0, __node_allocator(__a)) {}
 607
 608 template <class _Tp, class _Alloc>
 609 inline __list_imp<_Tp, _Alloc>::__list_imp(const __node_allocator& __a) : __size_alloc_(0, __a) {}
 610
 611 #ifndef _LIBCPP_CXX03_LANG
 612 template <class _Tp, class _Alloc>
 613 inline __list_imp<_Tp, _Alloc>::__list_imp(__node_allocator&& __a) _NOEXCEPT : __size_alloc_(0, std::move(__a)) {}
 614 #endif
 615
 616 template <class _Tp, class _Alloc>
 617 __list_imp<_Tp, _Alloc>::~__list_imp() {
 618   clear();
 619 }
 620
 621 template <class _Tp, class _Alloc>
 622 void __list_imp<_Tp, _Alloc>::clear() _NOEXCEPT {
 623   if (!empty()) {
 624     __link_pointer __f = __end_.__next_;
 625     __link_pointer __l = __end_as_link();
 626     __unlink_nodes(__f, __l->__prev_);
 627     __sz() = 0;
 628     while (__f != __l) {
 629       __node_pointer __np = __f->__as_node();
 630       __f                 = __f->__next_;
 631       __delete_node(__np);
 632     }
 633   }
 634 }
 635
 636 template <class _Tp, class _Alloc>
 637 void __list_imp<_Tp, _Alloc>::swap(__list_imp& __c)
 638 #if _LIBCPP_STD_VER >= 14
 639     _NOEXCEPT
 640 #else
 641     _NOEXCEPT_(!__alloc_traits::propagate_on_container_swap::value || __is_nothrow_swappable_v<allocator_type>)
 642 #endif
 643 {
 644   _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR(
 645       __alloc_traits::propagate_on_container_swap::value || this->__node_alloc() == __c.__node_alloc(),
 646       "list::swap: Either propagate_on_container_swap must be true"
 647       " or the allocators must compare equal");
 648   using std::swap;
 649   std::__swap_allocator(__node_alloc(), __c.__node_alloc());
 650   swap(__sz(), __c.__sz());
 651   swap(__end_, __c.__end_);
 652   if (__sz() == 0)
 653     __end_.__next_ = __end_.__prev_ = __end_as_link();
 654   else
 655     __end_.__prev_->__next_ = __end_.__next_->__prev_ = __end_as_link();
 656   if (__c.__sz() == 0)
 657     __c.__end_.__next_ = __c.__end_.__prev_ = __c.__end_as_link();
 658   else
 659     __c.__end_.__prev_->__next_ = __c.__end_.__next_->__prev_ = __c.__end_as_link();
 660 }
 661
 662 template <class _Tp, class _Alloc /*= allocator<_Tp>*/>
 663 class _LIBCPP_TEMPLATE_VIS list : private __list_imp<_Tp, _Alloc> {
 664   typedef __list_imp<_Tp, _Alloc> base;
 665   typedef typename base::__node_type __node_type;
 666   typedef typename base::__node_allocator __node_allocator;
 667   typedef typename base::__node_pointer __node_pointer;
 668   typedef typename base::__node_alloc_traits __node_alloc_traits;
 669   typedef typename base::__node_base __node_base;
 670   typedef typename base::__node_base_pointer __node_base_pointer;
 671   typedef typename base::__link_pointer __link_pointer;
 672
 673 public:
 674   typedef _Tp value_type;
 675   typedef _Alloc allocator_type;
 676   static_assert(__check_valid_allocator<allocator_type>::value);
 677   static_assert(is_same<value_type, typename allocator_type::value_type>::value,
 678                 "Allocator::value_type must be same type as value_type");
 679   typedef value_type& reference;
 680   typedef const value_type& const_reference;
 681   typedef typename base::pointer pointer;
 682   typedef typename base::const_pointer const_pointer;
 683   typedef typename base::size_type size_type;
 684   typedef typename base::difference_type difference_type;
 685   typedef typename base::iterator iterator;
 686   typedef typename base::const_iterator const_iterator;
 687   typedef std::reverse_iterator<iterator> reverse_iterator;
 688   typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
 689 #if _LIBCPP_STD_VER >= 20
 690   typedef size_type __remove_return_type;
 691 #else
 692   typedef void __remove_return_type;
 693 #endif
 694
 695   _LIBCPP_HIDE_FROM_ABI list() _NOEXCEPT_(is_nothrow_default_constructible<__node_allocator>::value) {}
 696   _LIBCPP_HIDE_FROM_ABI explicit list(const allocator_type& __a) : base(__a) {}
 697   _LIBCPP_HIDE_FROM_ABI explicit list(size_type __n);
 698 #if _LIBCPP_STD_VER >= 14
 699   _LIBCPP_HIDE_FROM_ABI explicit list(size_type __n, const allocator_type& __a);
 700 #endif
 701   _LIBCPP_HIDE_FROM_ABI list(size_type __n, const value_type& __x);
 702   template <__enable_if_t<__is_allocator<_Alloc>::value, int> = 0>
 703   _LIBCPP_HIDE_FROM_ABI list(size_type __n, const value_type& __x, const allocator_type& __a) : base(__a) {
 704     for (; __n > 0; --__n)
 705       push_back(__x);
 706   }
 707
 708   template <class _InpIter, __enable_if_t<__has_input_iterator_category<_InpIter>::value, int> = 0>
 709   _LIBCPP_HIDE_FROM_ABI list(_InpIter __f, _InpIter __l);
 710
 711   template <class _InpIter, __enable_if_t<__has_input_iterator_category<_InpIter>::value, int> = 0>
 712   _LIBCPP_HIDE_FROM_ABI list(_InpIter __f, _InpIter __l, const allocator_type& __a);
 713
 714 #if _LIBCPP_STD_VER >= 23
 715   template <_ContainerCompatibleRange<_Tp> _Range>
 716   _LIBCPP_HIDE_FROM_ABI list(from_range_t, _Range&& __range, const allocator_type& __a = allocator_type()) : base(__a) {
 717     prepend_range(std::forward<_Range>(__range));
 718   }
 719 #endif
 720
 721   _LIBCPP_HIDE_FROM_ABI list(const list& __c);
 722   _LIBCPP_HIDE_FROM_ABI list(const list& __c, const __type_identity_t<allocator_type>& __a);
 723   _LIBCPP_HIDE_FROM_ABI list& operator=(const list& __c);
 724 #ifndef _LIBCPP_CXX03_LANG
 725   _LIBCPP_HIDE_FROM_ABI list(initializer_list<value_type> __il);
 726   _LIBCPP_HIDE_FROM_ABI list(initializer_list<value_type> __il, const allocator_type& __a);
 727
 728   _LIBCPP_HIDE_FROM_ABI list(list&& __c) _NOEXCEPT_(is_nothrow_move_constructible<__node_allocator>::value);
 729   _LIBCPP_HIDE_FROM_ABI list(list&& __c, const __type_identity_t<allocator_type>& __a);
 730   _LIBCPP_HIDE_FROM_ABI list& operator=(list&& __c)
 731       _NOEXCEPT_(__node_alloc_traits::propagate_on_container_move_assignment::value&&
 732                      is_nothrow_move_assignable<__node_allocator>::value);
 733
 734   _LIBCPP_HIDE_FROM_ABI list& operator=(initializer_list<value_type> __il) {
 735     assign(__il.begin(), __il.end());
 736     return *this;
 737   }
 738
 739   _LIBCPP_HIDE_FROM_ABI void assign(initializer_list<value_type> __il) { assign(__il.begin(), __il.end()); }
 740 #endif // _LIBCPP_CXX03_LANG
 741
 742   template <class _InpIter, __enable_if_t<__has_input_iterator_category<_InpIter>::value, int> = 0>
 743   _LIBCPP_HIDE_FROM_ABI void assign(_InpIter __f, _InpIter __l);
 744
 745 #if _LIBCPP_STD_VER >= 23
 746   template <_ContainerCompatibleRange<_Tp> _Range>
 747   _LIBCPP_HIDE_FROM_ABI void assign_range(_Range&& __range) {
 748     __assign_with_sentinel(ranges::begin(__range), ranges::end(__range));
 749   }
 750 #endif
 751
 752   _LIBCPP_HIDE_FROM_ABI void assign(size_type __n, const value_type& __x);
 753
 754   _LIBCPP_HIDE_FROM_ABI allocator_type get_allocator() const _NOEXCEPT;
 755
 756   _LIBCPP_HIDE_FROM_ABI size_type size() const _NOEXCEPT { return base::__sz(); }
 757   _LIBCPP_NODISCARD _LIBCPP_HIDE_FROM_ABI bool empty() const _NOEXCEPT { return base::empty(); }
 758   _LIBCPP_HIDE_FROM_ABI size_type max_size() const _NOEXCEPT {
 759     return std::min<size_type>(base::__node_alloc_max_size(), numeric_limits<difference_type >::max());
 760   }
 761
 762   _LIBCPP_HIDE_FROM_ABI iterator begin() _NOEXCEPT { return base::begin(); }
 763   _LIBCPP_HIDE_FROM_ABI const_iterator begin() const _NOEXCEPT { return base::begin(); }
 764   _LIBCPP_HIDE_FROM_ABI iterator end() _NOEXCEPT { return base::end(); }
 765   _LIBCPP_HIDE_FROM_ABI const_iterator end() const _NOEXCEPT { return base::end(); }
 766   _LIBCPP_HIDE_FROM_ABI const_iterator cbegin() const _NOEXCEPT { return base::begin(); }
 767   _LIBCPP_HIDE_FROM_ABI const_iterator cend() const _NOEXCEPT { return base::end(); }
 768
 769   _LIBCPP_HIDE_FROM_ABI reverse_iterator rbegin() _NOEXCEPT { return reverse_iterator(end()); }
 770   _LIBCPP_HIDE_FROM_ABI const_reverse_iterator rbegin() const _NOEXCEPT { return const_reverse_iterator(end()); }
 771   _LIBCPP_HIDE_FROM_ABI reverse_iterator rend() _NOEXCEPT { return reverse_iterator(begin()); }
 772   _LIBCPP_HIDE_FROM_ABI const_reverse_iterator rend() const _NOEXCEPT { return const_reverse_iterator(begin()); }
 773   _LIBCPP_HIDE_FROM_ABI const_reverse_iterator crbegin() const _NOEXCEPT { return const_reverse_iterator(end()); }
 774   _LIBCPP_HIDE_FROM_ABI const_reverse_iterator crend() const _NOEXCEPT { return const_reverse_iterator(begin()); }
 775
 776   _LIBCPP_HIDE_FROM_ABI reference front() {
 777     _LIBCPP_ASSERT_VALID_ELEMENT_ACCESS(!empty(), "list::front called on empty list");
 778     return base::__end_.__next_->__as_node()->__get_value();
 779   }
 780   _LIBCPP_HIDE_FROM_ABI const_reference front() const {
 781     _LIBCPP_ASSERT_VALID_ELEMENT_ACCESS(!empty(), "list::front called on empty list");
 782     return base::__end_.__next_->__as_node()->__get_value();
 783   }
 784   _LIBCPP_HIDE_FROM_ABI reference back() {
 785     _LIBCPP_ASSERT_VALID_ELEMENT_ACCESS(!empty(), "list::back called on empty list");
 786     return base::__end_.__prev_->__as_node()->__get_value();
 787   }
 788   _LIBCPP_HIDE_FROM_ABI const_reference back() const {
 789     _LIBCPP_ASSERT_VALID_ELEMENT_ACCESS(!empty(), "list::back called on empty list");
 790     return base::__end_.__prev_->__as_node()->__get_value();
 791   }
 792
 793 #ifndef _LIBCPP_CXX03_LANG
 794   _LIBCPP_HIDE_FROM_ABI void push_front(value_type&& __x);
 795   _LIBCPP_HIDE_FROM_ABI void push_back(value_type&& __x);
 796
 797 #  if _LIBCPP_STD_VER >= 23
 798   template <_ContainerCompatibleRange<_Tp> _Range>
 799   _LIBCPP_HIDE_FROM_ABI void prepend_range(_Range&& __range) {
 800     insert_range(begin(), std::forward<_Range>(__range));
 801   }
 802
 803   template <_ContainerCompatibleRange<_Tp> _Range>
 804   _LIBCPP_HIDE_FROM_ABI void append_range(_Range&& __range) {
 805     insert_range(end(), std::forward<_Range>(__range));
 806   }
 807 #  endif
 808
 809   template <class... _Args>
 810 #  if _LIBCPP_STD_VER >= 17
 811   _LIBCPP_HIDE_FROM_ABI reference emplace_front(_Args&&... __args);
 812 #  else
 813   _LIBCPP_HIDE_FROM_ABI void emplace_front(_Args&&... __args);
 814 #  endif
 815   template <class... _Args>
 816 #  if _LIBCPP_STD_VER >= 17
 817   _LIBCPP_HIDE_FROM_ABI reference emplace_back(_Args&&... __args);
 818 #  else
 819   _LIBCPP_HIDE_FROM_ABI void emplace_back(_Args&&... __args);
 820 #  endif
 821   template <class... _Args>
 822   _LIBCPP_HIDE_FROM_ABI iterator emplace(const_iterator __p, _Args&&... __args);
 823
 824   _LIBCPP_HIDE_FROM_ABI iterator insert(const_iterator __p, value_type&& __x);
 825
 826   _LIBCPP_HIDE_FROM_ABI iterator insert(const_iterator __p, initializer_list<value_type> __il) {
 827     return insert(__p, __il.begin(), __il.end());
 828   }
 829 #endif // _LIBCPP_CXX03_LANG
 830
 831   _LIBCPP_HIDE_FROM_ABI void push_front(const value_type& __x);
 832   _LIBCPP_HIDE_FROM_ABI void push_back(const value_type& __x);
 833
 834 #ifndef _LIBCPP_CXX03_LANG
 835   template <class _Arg>
 836   _LIBCPP_HIDE_FROM_ABI void __emplace_back(_Arg&& __arg) {
 837     emplace_back(std::forward<_Arg>(__arg));
 838   }
 839 #else
 840   _LIBCPP_HIDE_FROM_ABI void __emplace_back(value_type const& __arg) { push_back(__arg); }
 841 #endif
 842
 843   _LIBCPP_HIDE_FROM_ABI iterator insert(const_iterator __p, const value_type& __x);
 844   _LIBCPP_HIDE_FROM_ABI iterator insert(const_iterator __p, size_type __n, const value_type& __x);
 845
 846   template <class _InpIter, __enable_if_t<__has_input_iterator_category<_InpIter>::value, int> = 0>
 847   _LIBCPP_HIDE_FROM_ABI iterator insert(const_iterator __p, _InpIter __f, _InpIter __l);
 848
 849 #if _LIBCPP_STD_VER >= 23
 850   template <_ContainerCompatibleRange<_Tp> _Range>
 851   _LIBCPP_HIDE_FROM_ABI iterator insert_range(const_iterator __position, _Range&& __range) {
 852     return __insert_with_sentinel(__position, ranges::begin(__range), ranges::end(__range));
 853   }
 854 #endif
 855
 856   _LIBCPP_HIDE_FROM_ABI void swap(list& __c)
 857 #if _LIBCPP_STD_VER >= 14
 858       _NOEXCEPT
 859 #else
 860       _NOEXCEPT_(!__node_alloc_traits::propagate_on_container_swap::value || __is_nothrow_swappable_v<__node_allocator>)
 861 #endif
 862   {
 863     base::swap(__c);
 864   }
 865   _LIBCPP_HIDE_FROM_ABI void clear() _NOEXCEPT { base::clear(); }
 866
 867   _LIBCPP_HIDE_FROM_ABI void pop_front();
 868   _LIBCPP_HIDE_FROM_ABI void pop_back();
 869
 870   _LIBCPP_HIDE_FROM_ABI iterator erase(const_iterator __p);
 871   _LIBCPP_HIDE_FROM_ABI iterator erase(const_iterator __f, const_iterator __l);
 872
 873   _LIBCPP_HIDE_FROM_ABI void resize(size_type __n);
 874   _LIBCPP_HIDE_FROM_ABI void resize(size_type __n, const value_type& __x);
 875
 876   _LIBCPP_HIDE_FROM_ABI void splice(const_iterator __p, list& __c);
 877 #ifndef _LIBCPP_CXX03_LANG
 878   _LIBCPP_HIDE_FROM_ABI void splice(const_iterator __p, list&& __c) { splice(__p, __c); }
 879   _LIBCPP_HIDE_FROM_ABI void splice(const_iterator __p, list&& __c, const_iterator __i) { splice(__p, __c, __i); }
 880   _LIBCPP_HIDE_FROM_ABI void splice(const_iterator __p, list&& __c, const_iterator __f, const_iterator __l) {
 881     splice(__p, __c, __f, __l);
 882   }
 883 #endif
 884   _LIBCPP_HIDE_FROM_ABI void splice(const_iterator __p, list& __c, const_iterator __i);
 885   _LIBCPP_HIDE_FROM_ABI void splice(const_iterator __p, list& __c, const_iterator __f, const_iterator __l);
 886
 887   _LIBCPP_HIDE_FROM_ABI __remove_return_type remove(const value_type& __x);
 888   template <class _Pred>
 889   _LIBCPP_HIDE_FROM_ABI __remove_return_type remove_if(_Pred __pred);
 890   _LIBCPP_HIDE_FROM_ABI __remove_return_type unique() { return unique(__equal_to()); }
 891   template <class _BinaryPred>
 892   _LIBCPP_HIDE_FROM_ABI __remove_return_type unique(_BinaryPred __binary_pred);
 893   _LIBCPP_HIDE_FROM_ABI void merge(list& __c);
 894 #ifndef _LIBCPP_CXX03_LANG
 895   _LIBCPP_HIDE_FROM_ABI void merge(list&& __c) { merge(__c); }
 896
 897   template <class _Comp>
 898   _LIBCPP_HIDE_FROM_ABI void merge(list&& __c, _Comp __comp) {
 899     merge(__c, __comp);
 900   }
 901 #endif
 902   template <class _Comp>
 903   _LIBCPP_HIDE_FROM_ABI void merge(list& __c, _Comp __comp);
 904
 905   _LIBCPP_HIDE_FROM_ABI void sort();
 906   template <class _Comp>
 907   _LIBCPP_HIDE_FROM_ABI void sort(_Comp __comp);
 908
 909   _LIBCPP_HIDE_FROM_ABI void reverse() _NOEXCEPT;
 910
 911   _LIBCPP_HIDE_FROM_ABI bool __invariants() const;
 912
 913 private:
 914   template <class _Iterator, class _Sentinel>
 915   _LIBCPP_HIDE_FROM_ABI void __assign_with_sentinel(_Iterator __f, _Sentinel __l);
 916
 917   template <class _Iterator, class _Sentinel>
 918   _LIBCPP_HIDE_FROM_ABI iterator __insert_with_sentinel(const_iterator __p, _Iterator __f, _Sentinel __l);
 919
 920   _LIBCPP_HIDE_FROM_ABI static void __link_nodes(__link_pointer __p, __link_pointer __f, __link_pointer __l);
 921   _LIBCPP_HIDE_FROM_ABI void __link_nodes_at_front(__link_pointer __f, __link_pointer __l);
 922   _LIBCPP_HIDE_FROM_ABI void __link_nodes_at_back(__link_pointer __f, __link_pointer __l);
 923   _LIBCPP_HIDE_FROM_ABI iterator __iterator(size_type __n);
 924   // TODO: Make this _LIBCPP_HIDE_FROM_ABI
 925   template <class _Comp>
 926   _LIBCPP_HIDDEN static iterator __sort(iterator __f1, iterator __e2, size_type __n, _Comp& __comp);
 927
 928   _LIBCPP_HIDE_FROM_ABI void __move_assign(list& __c, true_type)
 929       _NOEXCEPT_(is_nothrow_move_assignable<__node_allocator>::value);
 930   _LIBCPP_HIDE_FROM_ABI void __move_assign(list& __c, false_type);
 931 };
 932
 933 #if _LIBCPP_STD_VER >= 17
 934 template <class _InputIterator,
 935           class _Alloc = allocator<__iter_value_type<_InputIterator>>,
 936           class        = enable_if_t<__has_input_iterator_category<_InputIterator>::value>,
 937           class        = enable_if_t<__is_allocator<_Alloc>::value> >
 938 list(_InputIterator, _InputIterator) -> list<__iter_value_type<_InputIterator>, _Alloc>;
 939
 940 template <class _InputIterator,
 941           class _Alloc,
 942           class = enable_if_t<__has_input_iterator_category<_InputIterator>::value>,
 943           class = enable_if_t<__is_allocator<_Alloc>::value> >
 944 list(_InputIterator, _InputIterator, _Alloc) -> list<__iter_value_type<_InputIterator>, _Alloc>;
 945 #endif
 946
 947 #if _LIBCPP_STD_VER >= 23
 948 template <ranges::input_range _Range,
 949           class _Alloc = allocator<ranges::range_value_t<_Range>>,
 950           class        = enable_if_t<__is_allocator<_Alloc>::value> >
 951 list(from_range_t, _Range&&, _Alloc = _Alloc()) -> list<ranges::range_value_t<_Range>, _Alloc>;
 952 #endif
 953
 954 // Link in nodes [__f, __l] just prior to __p
 955 template <class _Tp, class _Alloc>
 956 inline void list<_Tp, _Alloc>::__link_nodes(__link_pointer __p, __link_pointer __f, __link_pointer __l) {
 957   __p->__prev_->__next_ = __f;
 958   __f->__prev_          = __p->__prev_;
 959   __p->__prev_          = __l;
 960   __l->__next_          = __p;
 961 }
 962
 963 // Link in nodes [__f, __l] at the front of the list
 964 template <class _Tp, class _Alloc>
 965 inline void list<_Tp, _Alloc>::__link_nodes_at_front(__link_pointer __f, __link_pointer __l) {
 966   __f->__prev_          = base::__end_as_link();
 967   __l->__next_          = base::__end_.__next_;
 968   __l->__next_->__prev_ = __l;
 969   base::__end_.__next_  = __f;
 970 }
 971
 972 // Link in nodes [__f, __l] at the back of the list
 973 template <class _Tp, class _Alloc>
 974 inline void list<_Tp, _Alloc>::__link_nodes_at_back(__link_pointer __f, __link_pointer __l) {
 975   __l->__next_          = base::__end_as_link();
 976   __f->__prev_          = base::__end_.__prev_;
 977   __f->__prev_->__next_ = __f;
 978   base::__end_.__prev_  = __l;
 979 }
 980
 981 template <class _Tp, class _Alloc>
 982 inline typename list<_Tp, _Alloc>::iterator list<_Tp, _Alloc>::__iterator(size_type __n) {
 983   return __n <= base::__sz() / 2 ? std::next(begin(), __n) : std::prev(end(), base::__sz() - __n);
 984 }
 985
 986 template <class _Tp, class _Alloc>
 987 list<_Tp, _Alloc>::list(size_type __n) {
 988   for (; __n > 0; --__n)
 989 #ifndef _LIBCPP_CXX03_LANG
 990     emplace_back();
 991 #else
 992     push_back(value_type());
 993 #endif
 994 }
 995
 996 #if _LIBCPP_STD_VER >= 14
 997 template <class _Tp, class _Alloc>
 998 list<_Tp, _Alloc>::list(size_type __n, const allocator_type& __a) : base(__a) {
 999   for (; __n > 0; --__n)
1000     emplace_back();
1001 }
1002 #endif
1003
1004 template <class _Tp, class _Alloc>
1005 list<_Tp, _Alloc>::list(size_type __n, const value_type& __x) {
1006   for (; __n > 0; --__n)
1007     push_back(__x);
1008 }
1009
1010 template <class _Tp, class _Alloc>
1011 template <class _InpIter, __enable_if_t<__has_input_iterator_category<_InpIter>::value, int> >
1012 list<_Tp, _Alloc>::list(_InpIter __f, _InpIter __l) {
1013   for (; __f != __l; ++__f)
1014     __emplace_back(*__f);
1015 }
1016
1017 template <class _Tp, class _Alloc>
1018 template <class _InpIter, __enable_if_t<__has_input_iterator_category<_InpIter>::value, int> >
1019 list<_Tp, _Alloc>::list(_InpIter __f, _InpIter __l, const allocator_type& __a) : base(__a) {
1020   for (; __f != __l; ++__f)
1021     __emplace_back(*__f);
1022 }
1023
1024 template <class _Tp, class _Alloc>
1025 list<_Tp, _Alloc>::list(const list& __c)
1026     : base(__node_alloc_traits::select_on_container_copy_construction(__c.__node_alloc())) {
1027   for (const_iterator __i = __c.begin(), __e = __c.end(); __i != __e; ++__i)
1028     push_back(*__i);
1029 }
1030
1031 template <class _Tp, class _Alloc>
1032 list<_Tp, _Alloc>::list(const list& __c, const __type_identity_t<allocator_type>& __a) : base(__a) {
1033   for (const_iterator __i = __c.begin(), __e = __c.end(); __i != __e; ++__i)
1034     push_back(*__i);
1035 }
1036
1037 #ifndef _LIBCPP_CXX03_LANG
1038
1039 template <class _Tp, class _Alloc>
1040 list<_Tp, _Alloc>::list(initializer_list<value_type> __il, const allocator_type& __a) : base(__a) {
1041   for (typename initializer_list<value_type>::const_iterator __i = __il.begin(), __e = __il.end(); __i != __e; ++__i)
1042     push_back(*__i);
1043 }
1044
1045 template <class _Tp, class _Alloc>
1046 list<_Tp, _Alloc>::list(initializer_list<value_type> __il) {
1047   for (typename initializer_list<value_type>::const_iterator __i = __il.begin(), __e = __il.end(); __i != __e; ++__i)
1048     push_back(*__i);
1049 }
1050
1051 template <class _Tp, class _Alloc>
1052 inline list<_Tp, _Alloc>::list(list&& __c) noexcept(is_nothrow_move_constructible<__node_allocator>::value)
1053     : base(std::move(__c.__node_alloc())) {
1054   splice(end(), __c);
1055 }
1056
1057 template <class _Tp, class _Alloc>
1058 inline list<_Tp, _Alloc>::list(list&& __c, const __type_identity_t<allocator_type>& __a) : base(__a) {
1059   if (__a == __c.get_allocator())
1060     splice(end(), __c);
1061   else {
1062     typedef move_iterator<iterator> _Ip;
1063     assign(_Ip(__c.begin()), _Ip(__c.end()));
1064   }
1065 }
1066
1067 template <class _Tp, class _Alloc>
1068 inline list<_Tp, _Alloc>& list<_Tp, _Alloc>::operator=(list&& __c) noexcept(
1069     __node_alloc_traits::propagate_on_container_move_assignment::value &&
1070     is_nothrow_move_assignable<__node_allocator>::value) {
1071   __move_assign(__c, integral_constant<bool, __node_alloc_traits::propagate_on_container_move_assignment::value>());
1072   return *this;
1073 }
1074
1075 template <class _Tp, class _Alloc>
1076 void list<_Tp, _Alloc>::__move_assign(list& __c, false_type) {
1077   if (base::__node_alloc() != __c.__node_alloc()) {
1078     typedef move_iterator<iterator> _Ip;
1079     assign(_Ip(__c.begin()), _Ip(__c.end()));
1080   } else
1081     __move_assign(__c, true_type());
1082 }
1083
1084 template <class _Tp, class _Alloc>
1085 void list<_Tp, _Alloc>::__move_assign(list& __c,
1086                                       true_type) noexcept(is_nothrow_move_assignable<__node_allocator>::value) {
1087   clear();
1088   base::__move_assign_alloc(__c);
1089   splice(end(), __c);
1090 }
1091
1092 #endif // _LIBCPP_CXX03_LANG
1093
1094 template <class _Tp, class _Alloc>
1095 inline list<_Tp, _Alloc>& list<_Tp, _Alloc>::operator=(const list& __c) {
1096   if (this != std::addressof(__c)) {
1097     base::__copy_assign_alloc(__c);
1098     assign(__c.begin(), __c.end());
1099   }
1100   return *this;
1101 }
1102
1103 template <class _Tp, class _Alloc>
1104 template <class _InpIter, __enable_if_t<__has_input_iterator_category<_InpIter>::value, int> >
1105 void list<_Tp, _Alloc>::assign(_InpIter __f, _InpIter __l) {
1106   __assign_with_sentinel(__f, __l);
1107 }
1108
1109 template <class _Tp, class _Alloc>
1110 template <class _Iterator, class _Sentinel>
1111 _LIBCPP_HIDE_FROM_ABI void list<_Tp, _Alloc>::__assign_with_sentinel(_Iterator __f, _Sentinel __l) {
1112   iterator __i = begin();
1113   iterator __e = end();
1114   for (; __f != __l && __i != __e; ++__f, (void)++__i)
1115     *__i = *__f;
1116   if (__i == __e)
1117     __insert_with_sentinel(__e, std::move(__f), std::move(__l));
1118   else
1119     erase(__i, __e);
1120 }
1121
1122 template <class _Tp, class _Alloc>
1123 void list<_Tp, _Alloc>::assign(size_type __n, const value_type& __x) {
1124   iterator __i = begin();
1125   iterator __e = end();
1126   for (; __n > 0 && __i != __e; --__n, (void)++__i)
1127     *__i = __x;
1128   if (__i == __e)
1129     insert(__e, __n, __x);
1130   else
1131     erase(__i, __e);
1132 }
1133
1134 template <class _Tp, class _Alloc>
1135 inline _Alloc list<_Tp, _Alloc>::get_allocator() const _NOEXCEPT {
1136   return allocator_type(base::__node_alloc());
1137 }
1138
1139 template <class _Tp, class _Alloc>
1140 typename list<_Tp, _Alloc>::iterator list<_Tp, _Alloc>::insert(const_iterator __p, const value_type& __x) {
1141   __node_pointer __node = this->__create_node(/* prev = */ nullptr, /* next = */ nullptr, __x);
1142   __link_nodes(__p.__ptr_, __node->__as_link(), __node->__as_link());
1143   ++base::__sz();
1144   return iterator(__node->__as_link());
1145 }
1146
1147 template <class _Tp, class _Alloc>
1148 typename list<_Tp, _Alloc>::iterator
1149 list<_Tp, _Alloc>::insert(const_iterator __p, size_type __n, const value_type& __x) {
1150   iterator __r(__p.__ptr_);
1151   if (__n > 0) {
1152     size_type __ds        = 0;
1153     __node_pointer __node = this->__create_node(/* prev = */ nullptr, /* next = */ nullptr, __x);
1154     ++__ds;
1155     __r          = iterator(__node->__as_link());
1156     iterator __e = __r;
1157 #ifndef _LIBCPP_HAS_NO_EXCEPTIONS
1158     try {
1159 #endif // _LIBCPP_HAS_NO_EXCEPTIONS
1160       for (--__n; __n != 0; --__n, (void)++__e, ++__ds) {
1161         __e.__ptr_->__next_ = this->__create_node(/* prev = */ __e.__ptr_, /* next = */ nullptr, __x)->__as_link();
1162       }
1163 #ifndef _LIBCPP_HAS_NO_EXCEPTIONS
1164     } catch (...) {
1165       while (true) {
1166         __link_pointer __prev    = __e.__ptr_->__prev_;
1167         __node_pointer __current = __e.__ptr_->__as_node();
1168         this->__delete_node(__current);
1169         if (__prev == 0)
1170           break;
1171         __e = iterator(__prev);
1172       }
1173       throw;
1174     }
1175 #endif // _LIBCPP_HAS_NO_EXCEPTIONS
1176     __link_nodes(__p.__ptr_, __r.__ptr_, __e.__ptr_);
1177     base::__sz() += __ds;
1178   }
1179   return __r;
1180 }
1181
1182 template <class _Tp, class _Alloc>
1183 template <class _InpIter, __enable_if_t<__has_input_iterator_category<_InpIter>::value, int> >
1184 typename list<_Tp, _Alloc>::iterator list<_Tp, _Alloc>::insert(const_iterator __p, _InpIter __f, _InpIter __l) {
1185   return __insert_with_sentinel(__p, __f, __l);
1186 }
1187
1188 template <class _Tp, class _Alloc>
1189 template <class _Iterator, class _Sentinel>
1190 _LIBCPP_HIDE_FROM_ABI typename list<_Tp, _Alloc>::iterator
1191 list<_Tp, _Alloc>::__insert_with_sentinel(const_iterator __p, _Iterator __f, _Sentinel __l) {
1192   iterator __r(__p.__ptr_);
1193   if (__f != __l) {
1194     size_type __ds        = 0;
1195     __node_pointer __node = this->__create_node(/* prev = */ nullptr, /* next = */ nullptr, *__f);
1196     ++__ds;
1197     __r          = iterator(__node->__as_link());
1198     iterator __e = __r;
1199 #ifndef _LIBCPP_HAS_NO_EXCEPTIONS
1200     try {
1201 #endif // _LIBCPP_HAS_NO_EXCEPTIONS
1202       for (++__f; __f != __l; ++__f, (void)++__e, ++__ds) {
1203         __e.__ptr_->__next_ = this->__create_node(/* prev = */ __e.__ptr_, /* next = */ nullptr, *__f)->__as_link();
1204       }
1205 #ifndef _LIBCPP_HAS_NO_EXCEPTIONS
1206     } catch (...) {
1207       while (true) {
1208         __link_pointer __prev    = __e.__ptr_->__prev_;
1209         __node_pointer __current = __e.__ptr_->__as_node();
1210         this->__delete_node(__current);
1211         if (__prev == 0)
1212           break;
1213         __e = iterator(__prev);
1214       }
1215       throw;
1216     }
1217 #endif // _LIBCPP_HAS_NO_EXCEPTIONS
1218     __link_nodes(__p.__ptr_, __r.__ptr_, __e.__ptr_);
1219     base::__sz() += __ds;
1220   }
1221   return __r;
1222 }
1223
1224 template <class _Tp, class _Alloc>
1225 void list<_Tp, _Alloc>::push_front(const value_type& __x) {
1226   __node_pointer __node = this->__create_node(/* prev = */ nullptr, /* next = */ nullptr, __x);
1227   __link_pointer __nl   = __node->__as_link();
1228   __link_nodes_at_front(__nl, __nl);
1229   ++base::__sz();
1230 }
1231
1232 template <class _Tp, class _Alloc>
1233 void list<_Tp, _Alloc>::push_back(const value_type& __x) {
1234   __node_pointer __node = this->__create_node(/* prev = */ nullptr, /* next = */ nullptr, __x);
1235   __link_pointer __nl   = __node->__as_link();
1236   __link_nodes_at_back(__nl, __nl);
1237   ++base::__sz();
1238 }
1239
1240 #ifndef _LIBCPP_CXX03_LANG
1241
1242 template <class _Tp, class _Alloc>
1243 void list<_Tp, _Alloc>::push_front(value_type&& __x) {
1244   __node_pointer __node = this->__create_node(/* prev = */ nullptr, /* next = */ nullptr, std::move(__x));
1245   __link_pointer __nl   = __node->__as_link();
1246   __link_nodes_at_front(__nl, __nl);
1247   ++base::__sz();
1248 }
1249
1250 template <class _Tp, class _Alloc>
1251 void list<_Tp, _Alloc>::push_back(value_type&& __x) {
1252   __node_pointer __node = this->__create_node(/* prev = */ nullptr, /* next = */ nullptr, std::move(__x));
1253   __link_pointer __nl   = __node->__as_link();
1254   __link_nodes_at_back(__nl, __nl);
1255   ++base::__sz();
1256 }
1257
1258 template <class _Tp, class _Alloc>
1259 template <class... _Args>
1260 #  if _LIBCPP_STD_VER >= 17
1261 typename list<_Tp, _Alloc>::reference
1262 #  else
1263 void
1264 #  endif
1265 list<_Tp, _Alloc>::emplace_front(_Args&&... __args) {
1266   __node_pointer __node =
1267       this->__create_node(/* prev = */ nullptr, /* next = */ nullptr, std::forward<_Args>(__args)...);
1268   __link_pointer __nl = __node->__as_link();
1269   __link_nodes_at_front(__nl, __nl);
1270   ++base::__sz();
1271 #  if _LIBCPP_STD_VER >= 17
1272   return __node->__get_value();
1273 #  endif
1274 }
1275
1276 template <class _Tp, class _Alloc>
1277 template <class... _Args>
1278 #  if _LIBCPP_STD_VER >= 17
1279 typename list<_Tp, _Alloc>::reference
1280 #  else
1281 void
1282 #  endif
1283 list<_Tp, _Alloc>::emplace_back(_Args&&... __args) {
1284   __node_pointer __node =
1285       this->__create_node(/* prev = */ nullptr, /* next = */ nullptr, std::forward<_Args>(__args)...);
1286   __link_pointer __nl = __node->__as_link();
1287   __link_nodes_at_back(__nl, __nl);
1288   ++base::__sz();
1289 #  if _LIBCPP_STD_VER >= 17
1290   return __node->__get_value();
1291 #  endif
1292 }
1293
1294 template <class _Tp, class _Alloc>
1295 template <class... _Args>
1296 typename list<_Tp, _Alloc>::iterator list<_Tp, _Alloc>::emplace(const_iterator __p, _Args&&... __args) {
1297   __node_pointer __node =
1298       this->__create_node(/* prev = */ nullptr, /* next = */ nullptr, std::forward<_Args>(__args)...);
1299   __link_pointer __nl = __node->__as_link();
1300   __link_nodes(__p.__ptr_, __nl, __nl);
1301   ++base::__sz();
1302   return iterator(__nl);
1303 }
1304
1305 template <class _Tp, class _Alloc>
1306 typename list<_Tp, _Alloc>::iterator list<_Tp, _Alloc>::insert(const_iterator __p, value_type&& __x) {
1307   __node_pointer __node = this->__create_node(/* prev = */ nullptr, /* next = */ nullptr, std::move(__x));
1308   __link_pointer __nl   = __node->__as_link();
1309   __link_nodes(__p.__ptr_, __nl, __nl);
1310   ++base::__sz();
1311   return iterator(__nl);
1312 }
1313
1314 #endif // _LIBCPP_CXX03_LANG
1315
1316 template <class _Tp, class _Alloc>
1317 void list<_Tp, _Alloc>::pop_front() {
1318   _LIBCPP_ASSERT_VALID_ELEMENT_ACCESS(!empty(), "list::pop_front() called with empty list");
1319   __link_pointer __n = base::__end_.__next_;
1320   base::__unlink_nodes(__n, __n);
1321   --base::__sz();
1322   this->__delete_node(__n->__as_node());
1323 }
1324
1325 template <class _Tp, class _Alloc>
1326 void list<_Tp, _Alloc>::pop_back() {
1327   _LIBCPP_ASSERT_VALID_ELEMENT_ACCESS(!empty(), "list::pop_back() called on an empty list");
1328   __link_pointer __n = base::__end_.__prev_;
1329   base::__unlink_nodes(__n, __n);
1330   --base::__sz();
1331   this->__delete_node(__n->__as_node());
1332 }
1333
1334 template <class _Tp, class _Alloc>
1335 typename list<_Tp, _Alloc>::iterator list<_Tp, _Alloc>::erase(const_iterator __p) {
1336   _LIBCPP_ASSERT_VALID_ELEMENT_ACCESS(__p != end(), "list::erase(iterator) called with a non-dereferenceable iterator");
1337   __link_pointer __n = __p.__ptr_;
1338   __link_pointer __r = __n->__next_;
1339   base::__unlink_nodes(__n, __n);
1340   --base::__sz();
1341   this->__delete_node(__n->__as_node());
1342   return iterator(__r);
1343 }
1344
1345 template <class _Tp, class _Alloc>
1346 typename list<_Tp, _Alloc>::iterator list<_Tp, _Alloc>::erase(const_iterator __f, const_iterator __l) {
1347   if (__f != __l) {
1348     base::__unlink_nodes(__f.__ptr_, __l.__ptr_->__prev_);
1349     while (__f != __l) {
1350       __link_pointer __n = __f.__ptr_;
1351       ++__f;
1352       --base::__sz();
1353       this->__delete_node(__n->__as_node());
1354     }
1355   }
1356   return iterator(__l.__ptr_);
1357 }
1358
1359 template <class _Tp, class _Alloc>
1360 void list<_Tp, _Alloc>::resize(size_type __n) {
1361   if (__n < base::__sz())
1362     erase(__iterator(__n), end());
1363   else if (__n > base::__sz()) {
1364     __n -= base::__sz();
1365     size_type __ds        = 0;
1366     __node_pointer __node = this->__create_node(/* prev = */ nullptr, /* next = */ nullptr);
1367     ++__ds;
1368     iterator __r = iterator(__node->__as_link());
1369     iterator __e = __r;
1370 #ifndef _LIBCPP_HAS_NO_EXCEPTIONS
1371     try {
1372 #endif // _LIBCPP_HAS_NO_EXCEPTIONS
1373       for (--__n; __n != 0; --__n, (void)++__e, ++__ds) {
1374         __e.__ptr_->__next_ = this->__create_node(/* prev = */ __e.__ptr_, /* next = */ nullptr)->__as_link();
1375       }
1376 #ifndef _LIBCPP_HAS_NO_EXCEPTIONS
1377     } catch (...) {
1378       while (true) {
1379         __link_pointer __prev    = __e.__ptr_->__prev_;
1380         __node_pointer __current = __e.__ptr_->__as_node();
1381         this->__delete_node(__current);
1382         if (__prev == 0)
1383           break;
1384         __e = iterator(__prev);
1385       }
1386       throw;
1387     }
1388 #endif // _LIBCPP_HAS_NO_EXCEPTIONS
1389     __link_nodes_at_back(__r.__ptr_, __e.__ptr_);
1390     base::__sz() += __ds;
1391   }
1392 }
1393
1394 template <class _Tp, class _Alloc>
1395 void list<_Tp, _Alloc>::resize(size_type __n, const value_type& __x) {
1396   if (__n < base::__sz())
1397     erase(__iterator(__n), end());
1398   else if (__n > base::__sz()) {
1399     __n -= base::__sz();
1400     size_type __ds        = 0;
1401     __node_pointer __node = this->__create_node(/* prev = */ nullptr, /* next = */ nullptr, __x);
1402     ++__ds;
1403     __link_pointer __nl = __node->__as_link();
1404     iterator __r        = iterator(__nl);
1405     iterator __e        = __r;
1406 #ifndef _LIBCPP_HAS_NO_EXCEPTIONS
1407     try {
1408 #endif // _LIBCPP_HAS_NO_EXCEPTIONS
1409       for (--__n; __n != 0; --__n, (void)++__e, ++__ds) {
1410         __e.__ptr_->__next_ = this->__create_node(/* prev = */ __e.__ptr_, /* next = */ nullptr, __x)->__as_link();
1411       }
1412 #ifndef _LIBCPP_HAS_NO_EXCEPTIONS
1413     } catch (...) {
1414       while (true) {
1415         __link_pointer __prev    = __e.__ptr_->__prev_;
1416         __node_pointer __current = __e.__ptr_->__as_node();
1417         this->__delete_node(__current);
1418         if (__prev == 0)
1419           break;
1420         __e = iterator(__prev);
1421       }
1422       throw;
1423     }
1424 #endif // _LIBCPP_HAS_NO_EXCEPTIONS
1425     __link_nodes(base::__end_as_link(), __r.__ptr_, __e.__ptr_);
1426     base::__sz() += __ds;
1427   }
1428 }
1429
1430 template <class _Tp, class _Alloc>
1431 void list<_Tp, _Alloc>::splice(const_iterator __p, list& __c) {
1432   _LIBCPP_ASSERT_VALID_INPUT_RANGE(
1433       this != std::addressof(__c), "list::splice(iterator, list) called with this == &list");
1434   if (!__c.empty()) {
1435     __link_pointer __f = __c.__end_.__next_;
1436     __link_pointer __l = __c.__end_.__prev_;
1437     base::__unlink_nodes(__f, __l);
1438     __link_nodes(__p.__ptr_, __f, __l);
1439     base::__sz() += __c.__sz();
1440     __c.__sz() = 0;
1441   }
1442 }
1443
1444 template <class _Tp, class _Alloc>
1445 void list<_Tp, _Alloc>::splice(const_iterator __p, list& __c, const_iterator __i) {
1446   if (__p.__ptr_ != __i.__ptr_ && __p.__ptr_ != __i.__ptr_->__next_) {
1447     __link_pointer __f = __i.__ptr_;
1448     base::__unlink_nodes(__f, __f);
1449     __link_nodes(__p.__ptr_, __f, __f);
1450     --__c.__sz();
1451     ++base::__sz();
1452   }
1453 }
1454
1455 template <class _Tp, class _Alloc>
1456 void list<_Tp, _Alloc>::splice(const_iterator __p, list& __c, const_iterator __f, const_iterator __l) {
1457   if (__f != __l) {
1458     __link_pointer __first = __f.__ptr_;
1459     --__l;
1460     __link_pointer __last = __l.__ptr_;
1461     if (this != std::addressof(__c)) {
1462       size_type __s = std::distance(__f, __l) + 1;
1463       __c.__sz() -= __s;
1464       base::__sz() += __s;
1465     }
1466     base::__unlink_nodes(__first, __last);
1467     __link_nodes(__p.__ptr_, __first, __last);
1468   }
1469 }
1470
1471 template <class _Tp, class _Alloc>
1472 typename list<_Tp, _Alloc>::__remove_return_type list<_Tp, _Alloc>::remove(const value_type& __x) {
1473   list<_Tp, _Alloc> __deleted_nodes(get_allocator()); // collect the nodes we're removing
1474   for (const_iterator __i = begin(), __e = end(); __i != __e;) {
1475     if (*__i == __x) {
1476       const_iterator __j = std::next(__i);
1477       for (; __j != __e && *__j == __x; ++__j)
1478         ;
1479       __deleted_nodes.splice(__deleted_nodes.end(), *this, __i, __j);
1480       __i = __j;
1481       if (__i != __e)
1482         ++__i;
1483     } else
1484       ++__i;
1485   }
1486
1487   return (__remove_return_type)__deleted_nodes.size();
1488 }
1489
1490 template <class _Tp, class _Alloc>
1491 template <class _Pred>
1492 typename list<_Tp, _Alloc>::__remove_return_type list<_Tp, _Alloc>::remove_if(_Pred __pred) {
1493   list<_Tp, _Alloc> __deleted_nodes(get_allocator()); // collect the nodes we're removing
1494   for (iterator __i = begin(), __e = end(); __i != __e;) {
1495     if (__pred(*__i)) {
1496       iterator __j = std::next(__i);
1497       for (; __j != __e && __pred(*__j); ++__j)
1498         ;
1499       __deleted_nodes.splice(__deleted_nodes.end(), *this, __i, __j);
1500       __i = __j;
1501       if (__i != __e)
1502         ++__i;
1503     } else
1504       ++__i;
1505   }
1506
1507   return (__remove_return_type)__deleted_nodes.size();
1508 }
1509
1510 template <class _Tp, class _Alloc>
1511 template <class _BinaryPred>
1512 typename list<_Tp, _Alloc>::__remove_return_type list<_Tp, _Alloc>::unique(_BinaryPred __binary_pred) {
1513   list<_Tp, _Alloc> __deleted_nodes(get_allocator()); // collect the nodes we're removing
1514   for (iterator __i = begin(), __e = end(); __i != __e;) {
1515     iterator __j = std::next(__i);
1516     for (; __j != __e && __binary_pred(*__i, *__j); ++__j)
1517       ;
1518     if (++__i != __j) {
1519       __deleted_nodes.splice(__deleted_nodes.end(), *this, __i, __j);
1520       __i = __j;
1521     }
1522   }
1523
1524   return (__remove_return_type)__deleted_nodes.size();
1525 }
1526
1527 template <class _Tp, class _Alloc>
1528 inline void list<_Tp, _Alloc>::merge(list& __c) {
1529   merge(__c, __less<>());
1530 }
1531
1532 template <class _Tp, class _Alloc>
1533 template <class _Comp>
1534 void list<_Tp, _Alloc>::merge(list& __c, _Comp __comp) {
1535   if (this != std::addressof(__c)) {
1536     iterator __f1 = begin();
1537     iterator __e1 = end();
1538     iterator __f2 = __c.begin();
1539     iterator __e2 = __c.end();
1540     while (__f1 != __e1 && __f2 != __e2) {
1541       if (__comp(*__f2, *__f1)) {
1542         size_type __ds = 1;
1543         iterator __m2  = std::next(__f2);
1544         for (; __m2 != __e2 && __comp(*__m2, *__f1); ++__m2, (void)++__ds)
1545           ;
1546         base::__sz() += __ds;
1547         __c.__sz() -= __ds;
1548         __link_pointer __f = __f2.__ptr_;
1549         __link_pointer __l = __m2.__ptr_->__prev_;
1550         __f2               = __m2;
1551         base::__unlink_nodes(__f, __l);
1552         __m2 = std::next(__f1);
1553         __link_nodes(__f1.__ptr_, __f, __l);
1554         __f1 = __m2;
1555       } else
1556         ++__f1;
1557     }
1558     splice(__e1, __c);
1559   }
1560 }
1561
1562 template <class _Tp, class _Alloc>
1563 inline void list<_Tp, _Alloc>::sort() {
1564   sort(__less<>());
1565 }
1566
1567 template <class _Tp, class _Alloc>
1568 template <class _Comp>
1569 inline void list<_Tp, _Alloc>::sort(_Comp __comp) {
1570   __sort(begin(), end(), base::__sz(), __comp);
1571 }
1572
1573 template <class _Tp, class _Alloc>
1574 template <class _Comp>
1575 typename list<_Tp, _Alloc>::iterator
1576 list<_Tp, _Alloc>::__sort(iterator __f1, iterator __e2, size_type __n, _Comp& __comp) {
1577   switch (__n) {
1578   case 0:
1579   case 1:
1580     return __f1;
1581   case 2:
1582     if (__comp(*--__e2, *__f1)) {
1583       __link_pointer __f = __e2.__ptr_;
1584       base::__unlink_nodes(__f, __f);
1585       __link_nodes(__f1.__ptr_, __f, __f);
1586       return __e2;
1587     }
1588     return __f1;
1589   }
1590   size_type __n2 = __n / 2;
1591   iterator __e1  = std::next(__f1, __n2);
1592   iterator __r = __f1 = __sort(__f1, __e1, __n2, __comp);
1593   iterator __f2 = __e1 = __sort(__e1, __e2, __n - __n2, __comp);
1594   if (__comp(*__f2, *__f1)) {
1595     iterator __m2 = std::next(__f2);
1596     for (; __m2 != __e2 && __comp(*__m2, *__f1); ++__m2)
1597       ;
1598     __link_pointer __f = __f2.__ptr_;
1599     __link_pointer __l = __m2.__ptr_->__prev_;
1600     __r                = __f2;
1601     __e1 = __f2 = __m2;
1602     base::__unlink_nodes(__f, __l);
1603     __m2 = std::next(__f1);
1604     __link_nodes(__f1.__ptr_, __f, __l);
1605     __f1 = __m2;
1606   } else
1607     ++__f1;
1608   while (__f1 != __e1 && __f2 != __e2) {
1609     if (__comp(*__f2, *__f1)) {
1610       iterator __m2 = std::next(__f2);
1611       for (; __m2 != __e2 && __comp(*__m2, *__f1); ++__m2)
1612         ;
1613       __link_pointer __f = __f2.__ptr_;
1614       __link_pointer __l = __m2.__ptr_->__prev_;
1615       if (__e1 == __f2)
1616         __e1 = __m2;
1617       __f2 = __m2;
1618       base::__unlink_nodes(__f, __l);
1619       __m2 = std::next(__f1);
1620       __link_nodes(__f1.__ptr_, __f, __l);
1621       __f1 = __m2;
1622     } else
1623       ++__f1;
1624   }
1625   return __r;
1626 }
1627
1628 template <class _Tp, class _Alloc>
1629 void list<_Tp, _Alloc>::reverse() _NOEXCEPT {
1630   if (base::__sz() > 1) {
1631     iterator __e = end();
1632     for (iterator __i = begin(); __i.__ptr_ != __e.__ptr_;) {
1633       std::swap(__i.__ptr_->__prev_, __i.__ptr_->__next_);
1634       __i.__ptr_ = __i.__ptr_->__prev_;
1635     }
1636     std::swap(__e.__ptr_->__prev_, __e.__ptr_->__next_);
1637   }
1638 }
1639
1640 template <class _Tp, class _Alloc>
1641 bool list<_Tp, _Alloc>::__invariants() const {
1642   return size() == std::distance(begin(), end());
1643 }
1644
1645 template <class _Tp, class _Alloc>
1646 inline _LIBCPP_HIDE_FROM_ABI bool operator==(const list<_Tp, _Alloc>& __x, const list<_Tp, _Alloc>& __y) {
1647   return __x.size() == __y.size() && std::equal(__x.begin(), __x.end(), __y.begin());
1648 }
1649
1650 #if _LIBCPP_STD_VER <= 17
1651
1652 template <class _Tp, class _Alloc>
1653 inline _LIBCPP_HIDE_FROM_ABI bool operator<(const list<_Tp, _Alloc>& __x, const list<_Tp, _Alloc>& __y) {
1654   return std::lexicographical_compare(__x.begin(), __x.end(), __y.begin(), __y.end());
1655 }
1656
1657 template <class _Tp, class _Alloc>
1658 inline _LIBCPP_HIDE_FROM_ABI bool operator!=(const list<_Tp, _Alloc>& __x, const list<_Tp, _Alloc>& __y) {
1659   return !(__x == __y);
1660 }
1661
1662 template <class _Tp, class _Alloc>
1663 inline _LIBCPP_HIDE_FROM_ABI bool operator>(const list<_Tp, _Alloc>& __x, const list<_Tp, _Alloc>& __y) {
1664   return __y < __x;
1665 }
1666
1667 template <class _Tp, class _Alloc>
1668 inline _LIBCPP_HIDE_FROM_ABI bool operator>=(const list<_Tp, _Alloc>& __x, const list<_Tp, _Alloc>& __y) {
1669   return !(__x < __y);
1670 }
1671
1672 template <class _Tp, class _Alloc>
1673 inline _LIBCPP_HIDE_FROM_ABI bool operator<=(const list<_Tp, _Alloc>& __x, const list<_Tp, _Alloc>& __y) {
1674   return !(__y < __x);
1675 }
1676
1677 #else // _LIBCPP_STD_VER <= 17
1678
1679 template <class _Tp, class _Allocator>
1680 _LIBCPP_HIDE_FROM_ABI __synth_three_way_result<_Tp>
1681 operator<=>(const list<_Tp, _Allocator>& __x, const list<_Tp, _Allocator>& __y) {
1682   return std::lexicographical_compare_three_way(__x.begin(), __x.end(), __y.begin(), __y.end(), std::__synth_three_way);
1683 }
1684
1685 #endif // _LIBCPP_STD_VER <= 17
1686
1687 template <class _Tp, class _Alloc>
1688 inline _LIBCPP_HIDE_FROM_ABI void swap(list<_Tp, _Alloc>& __x, list<_Tp, _Alloc>& __y)
1689     _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y))) {
1690   __x.swap(__y);
1691 }
1692
1693 #if _LIBCPP_STD_VER >= 20
1694 template <class _Tp, class _Allocator, class _Predicate>
1695 inline _LIBCPP_HIDE_FROM_ABI typename list<_Tp, _Allocator>::size_type
1696 erase_if(list<_Tp, _Allocator>& __c, _Predicate __pred) {
1697   return __c.remove_if(__pred);
1698 }
1699
1700 template <class _Tp, class _Allocator, class _Up>
1701 inline _LIBCPP_HIDE_FROM_ABI typename list<_Tp, _Allocator>::size_type
1702 erase(list<_Tp, _Allocator>& __c, const _Up& __v) {
1703   return std::erase_if(__c, [&](auto& __elem) { return __elem == __v; });
1704 }
1705
1706 template <>
1707 inline constexpr bool __format::__enable_insertable<std::list<char>> = true;
1708 #  ifndef _LIBCPP_HAS_NO_WIDE_CHARACTERS
1709 template <>
1710 inline constexpr bool __format::__enable_insertable<std::list<wchar_t>> = true;
1711 #  endif
1712
1713 #endif // _LIBCPP_STD_VER >= 20
1714
1715 _LIBCPP_END_NAMESPACE_STD
1716
1717 #if _LIBCPP_STD_VER >= 17
1718 _LIBCPP_BEGIN_NAMESPACE_STD
1719 namespace pmr {
1720 template <class _ValueT>
1721 using list _LIBCPP_AVAILABILITY_PMR = std::list<_ValueT, polymorphic_allocator<_ValueT>>;
1722 } // namespace pmr
1723 _LIBCPP_END_NAMESPACE_STD
1724 #endif
1725
1726 _LIBCPP_POP_MACROS
1727
1728 #if !defined(_LIBCPP_REMOVE_TRANSITIVE_INCLUDES) && _LIBCPP_STD_VER <= 20
1729 #  include <__cxx03/algorithm>
1730 #  include <__cxx03/atomic>
1731 #  include <__cxx03/concepts>
1732 #  include <__cxx03/cstdint>
1733 #  include <__cxx03/cstdlib>
1734 #  include <__cxx03/functional>
1735 #  include <__cxx03/iosfwd>
1736 #  include <__cxx03/iterator>
1737 #  include <__cxx03/stdexcept>
1738 #  include <__cxx03/type_traits>
1739 #  include <__cxx03/typeinfo>
1740 #endif
1741
1742 #endif // _LIBCPP_LIST