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