EIC code displayed by LXR

0001 // -*- C++ -*-
0002 //===----------------------------------------------------------------------===//
0003 //
0004 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
0005 // See https://llvm.org/LICENSE.txt for license information.
0006 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
0007 //
0008 //===----------------------------------------------------------------------===//
0009
0010 #ifndef _LIBCPP___CXX03_LIST
0011 #define _LIBCPP___CXX03_LIST
0012
0013 /*
0014     list synopsis
0015
0016 namespace std
0017 {
0018
0019 template <class T, class Alloc = allocator<T> >
0020 class list
0021 {
0022 public:
0023
0024     // types:
0025     typedef T value_type;
0026     typedef Alloc allocator_type;
0027     typedef typename allocator_type::reference reference;
0028     typedef typename allocator_type::const_reference const_reference;
0029     typedef typename allocator_type::pointer pointer;
0030     typedef typename allocator_type::const_pointer const_pointer;
0031     typedef implementation-defined iterator;
0032     typedef implementation-defined const_iterator;
0033     typedef implementation-defined size_type;
0034     typedef implementation-defined difference_type;
0035     typedef reverse_iterator<iterator> reverse_iterator;
0036     typedef reverse_iterator<const_iterator> const_reverse_iterator;
0037
0038     list()
0039         noexcept(is_nothrow_default_constructible<allocator_type>::value);
0040     explicit list(const allocator_type& a);
0041     explicit list(size_type n);
0042     explicit list(size_type n, const allocator_type& a); // C++14
0043     list(size_type n, const value_type& value);
0044     list(size_type n, const value_type& value, const allocator_type& a);
0045     template <class Iter>
0046         list(Iter first, Iter last);
0047     template <class Iter>
0048         list(Iter first, Iter last, const allocator_type& a);
0049     template<container-compatible-range<T> R>
0050       list(from_range_t, R&& rg, const Allocator& = Allocator()); // C++23
0051     list(const list& x);
0052     list(const list&, const allocator_type& a);
0053     list(list&& x)
0054         noexcept(is_nothrow_move_constructible<allocator_type>::value);
0055     list(list&&, const allocator_type& a);
0056     list(initializer_list<value_type>);
0057     list(initializer_list<value_type>, const allocator_type& a);
0058
0059     ~list();
0060
0061     list& operator=(const list& x);
0062     list& operator=(list&& x)
0063         noexcept(
0064              allocator_type::propagate_on_container_move_assignment::value &&
0065              is_nothrow_move_assignable<allocator_type>::value);
0066     list& operator=(initializer_list<value_type>);
0067     template <class Iter>
0068         void assign(Iter first, Iter last);
0069     template<container-compatible-range<T> R>
0070       void assign_range(R&& rg); // C++23
0071     void assign(size_type n, const value_type& t);
0072     void assign(initializer_list<value_type>);
0073
0074     allocator_type get_allocator() const noexcept;
0075
0076     iterator begin() noexcept;
0077     const_iterator begin() const noexcept;
0078     iterator end() noexcept;
0079     const_iterator end() const noexcept;
0080     reverse_iterator rbegin() noexcept;
0081     const_reverse_iterator rbegin() const noexcept;
0082     reverse_iterator rend() noexcept;
0083     const_reverse_iterator rend() const noexcept;
0084     const_iterator cbegin() const noexcept;
0085     const_iterator cend() const noexcept;
0086     const_reverse_iterator crbegin() const noexcept;
0087     const_reverse_iterator crend() const noexcept;
0088
0089     reference front();
0090     const_reference front() const;
0091     reference back();
0092     const_reference back() const;
0093
0094     bool empty() const noexcept;
0095     size_type size() const noexcept;
0096     size_type max_size() const noexcept;
0097
0098     template <class... Args>
0099         reference emplace_front(Args&&... args); // reference in C++17
0100     void pop_front();
0101     template <class... Args>
0102         reference emplace_back(Args&&... args);  // reference in C++17
0103     void pop_back();
0104     void push_front(const value_type& x);
0105     void push_front(value_type&& x);
0106     template<container-compatible-range<T> R>
0107       void prepend_range(R&& rg); // C++23
0108     void push_back(const value_type& x);
0109     void push_back(value_type&& x);
0110     template<container-compatible-range<T> R>
0111       void append_range(R&& rg); // C++23
0112     template <class... Args>
0113         iterator emplace(const_iterator position, Args&&... args);
0114     iterator insert(const_iterator position, const value_type& x);
0115     iterator insert(const_iterator position, value_type&& x);
0116     iterator insert(const_iterator position, size_type n, const value_type& x);
0117     template <class Iter>
0118         iterator insert(const_iterator position, Iter first, Iter last);
0119     template<container-compatible-range<T> R>
0120       iterator insert_range(const_iterator position, R&& rg); // C++23
0121     iterator insert(const_iterator position, initializer_list<value_type> il);
0122
0123     iterator erase(const_iterator position);
0124     iterator erase(const_iterator position, const_iterator last);
0125
0126     void resize(size_type sz);
0127     void resize(size_type sz, const value_type& c);
0128
0129     void swap(list&)
0130         noexcept(allocator_traits<allocator_type>::is_always_equal::value);  // C++17
0131     void clear() noexcept;
0132
0133     void splice(const_iterator position, list& x);
0134     void splice(const_iterator position, list&& x);
0135     void splice(const_iterator position, list& x, const_iterator i);
0136     void splice(const_iterator position, list&& x, const_iterator i);
0137     void splice(const_iterator position, list& x, const_iterator first,
0138                                                   const_iterator last);
0139     void splice(const_iterator position, list&& x, const_iterator first,
0140                                                   const_iterator last);
0141
0142     size_type remove(const value_type& value);       // void before C++20
0143     template <class Pred>
0144       size_type remove_if(Pred pred);                // void before C++20
0145     size_type unique();                              // void before C++20
0146     template <class BinaryPredicate>
0147       size_type unique(BinaryPredicate binary_pred); // void before C++20
0148     void merge(list& x);
0149     void merge(list&& x);
0150     template <class Compare>
0151         void merge(list& x, Compare comp);
0152     template <class Compare>
0153         void merge(list&& x, Compare comp);
0154     void sort();
0155     template <class Compare>
0156         void sort(Compare comp);
0157     void reverse() noexcept;
0158 };
0159
0160
0161 template <class InputIterator, class Allocator = allocator<typename iterator_traits<InputIterator>::value_type>>
0162     list(InputIterator, InputIterator, Allocator = Allocator())
0163     -> list<typename iterator_traits<InputIterator>::value_type, Allocator>;  // C++17
0164
0165 template<ranges::input_range R, class Allocator = allocator<ranges::range_value_t<R>>>
0166   list(from_range_t, R&&, Allocator = Allocator())
0167     -> list<ranges::range_value_t<R>, Allocator>; // C++23
0168
0169 template <class T, class Alloc>
0170     bool operator==(const list<T,Alloc>& x, const list<T,Alloc>& y);
0171 template <class T, class Alloc>
0172     bool operator< (const list<T,Alloc>& x, const list<T,Alloc>& y);     // removed in C++20
0173 template <class T, class Alloc>
0174     bool operator!=(const list<T,Alloc>& x, const list<T,Alloc>& y);     // removed in C++20
0175 template <class T, class Alloc>
0176     bool operator> (const list<T,Alloc>& x, const list<T,Alloc>& y);     // removed in C++20
0177 template <class T, class Alloc>
0178     bool operator>=(const list<T,Alloc>& x, const list<T,Alloc>& y);     // removed in C++20
0179 template <class T, class Alloc>
0180     bool operator<=(const list<T,Alloc>& x, const list<T,Alloc>& y);     // removed in C++20
0181 template<class T, class Allocator>
0182   synth-three-way-result<T> operator<=>(const list<T, Allocator>& x,
0183                                         const list<T, Allocator>& y);    // since C++20
0184
0185 template <class T, class Alloc>
0186     void swap(list<T,Alloc>& x, list<T,Alloc>& y)
0187          noexcept(noexcept(x.swap(y)));
0188
0189 template <class T, class Allocator, class U>
0190     typename list<T, Allocator>::size_type
0191     erase(list<T, Allocator>& c, const U& value);       // since C++20
0192 template <class T, class Allocator, class Predicate>
0193     typename list<T, Allocator>::size_type
0194     erase_if(list<T, Allocator>& c, Predicate pred);    // since C++20
0195
0196 }  // std
0197
0198 */
0199
0200 #include <__cxx03/__algorithm/comp.h>
0201 #include <__cxx03/__algorithm/equal.h>
0202 #include <__cxx03/__algorithm/lexicographical_compare.h>
0203 #include <__cxx03/__algorithm/lexicographical_compare_three_way.h>
0204 #include <__cxx03/__algorithm/min.h>
0205 #include <__cxx03/__assert>
0206 #include <__cxx03/__config>
0207 #include <__cxx03/__format/enable_insertable.h>
0208 #include <__cxx03/__iterator/distance.h>
0209 #include <__cxx03/__iterator/iterator_traits.h>
0210 #include <__cxx03/__iterator/move_iterator.h>
0211 #include <__cxx03/__iterator/next.h>
0212 #include <__cxx03/__iterator/prev.h>
0213 #include <__cxx03/__iterator/reverse_iterator.h>
0214 #include <__cxx03/__memory/addressof.h>
0215 #include <__cxx03/__memory/allocation_guard.h>
0216 #include <__cxx03/__memory/allocator.h>
0217 #include <__cxx03/__memory/allocator_traits.h>
0218 #include <__cxx03/__memory/compressed_pair.h>
0219 #include <__cxx03/__memory/construct_at.h>
0220 #include <__cxx03/__memory/pointer_traits.h>
0221 #include <__cxx03/__memory/swap_allocator.h>
0222 #include <__cxx03/__memory_resource/polymorphic_allocator.h>
0223 #include <__cxx03/__ranges/access.h>
0224 #include <__cxx03/__ranges/concepts.h>
0225 #include <__cxx03/__ranges/container_compatible_range.h>
0226 #include <__cxx03/__ranges/from_range.h>
0227 #include <__cxx03/__type_traits/conditional.h>
0228 #include <__cxx03/__type_traits/is_allocator.h>
0229 #include <__cxx03/__type_traits/is_nothrow_assignable.h>
0230 #include <__cxx03/__type_traits/is_nothrow_constructible.h>
0231 #include <__cxx03/__type_traits/is_pointer.h>
0232 #include <__cxx03/__type_traits/is_same.h>
0233 #include <__cxx03/__type_traits/type_identity.h>
0234 #include <__cxx03/__utility/forward.h>
0235 #include <__cxx03/__utility/move.h>
0236 #include <__cxx03/__utility/swap.h>
0237 #include <__cxx03/cstring>
0238 #include <__cxx03/limits>
0239 #include <__cxx03/new> // __launder
0240 #include <__cxx03/version>
0241
0242 // standard-mandated includes
0243
0244 // [iterator.range]
0245 #include <__cxx03/__iterator/access.h>
0246 #include <__cxx03/__iterator/data.h>
0247 #include <__cxx03/__iterator/empty.h>
0248 #include <__cxx03/__iterator/reverse_access.h>
0249 #include <__cxx03/__iterator/size.h>
0250
0251 // [list.syn]
0252 #include <__cxx03/compare>
0253 #include <__cxx03/initializer_list>
0254
0255 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
0256 #  pragma GCC system_header
0257 #endif
0258
0259 _LIBCPP_PUSH_MACROS
0260 #include <__cxx03/__undef_macros>
0261
0262 _LIBCPP_BEGIN_NAMESPACE_STD
0263
0264 template <class _Tp, class _VoidPtr>
0265 struct __list_node;
0266 template <class _Tp, class _VoidPtr>
0267 struct __list_node_base;
0268
0269 template <class _Tp, class _VoidPtr>
0270 struct __list_node_pointer_traits {
0271   typedef __rebind_pointer_t<_VoidPtr, __list_node<_Tp, _VoidPtr> > __node_pointer;
0272   typedef __rebind_pointer_t<_VoidPtr, __list_node_base<_Tp, _VoidPtr> > __base_pointer;
0273
0274 #if defined(_LIBCPP_ABI_LIST_REMOVE_NODE_POINTER_UB)
0275   typedef __base_pointer __link_pointer;
0276 #else
0277   typedef __conditional_t<is_pointer<_VoidPtr>::value, __base_pointer, __node_pointer> __link_pointer;
0278 #endif
0279
0280   typedef __conditional_t<is_same<__link_pointer, __node_pointer>::value, __base_pointer, __node_pointer>
0281       __non_link_pointer;
0282
0283   static _LIBCPP_HIDE_FROM_ABI __link_pointer __unsafe_link_pointer_cast(__link_pointer __p) { return __p; }
0284
0285   static _LIBCPP_HIDE_FROM_ABI __link_pointer __unsafe_link_pointer_cast(__non_link_pointer __p) {
0286     return static_cast<__link_pointer>(static_cast<_VoidPtr>(__p));
0287   }
0288 };
0289
0290 template <class _Tp, class _VoidPtr>
0291 struct __list_node_base {
0292   typedef __list_node_pointer_traits<_Tp, _VoidPtr> _NodeTraits;
0293   typedef typename _NodeTraits::__node_pointer __node_pointer;
0294   typedef typename _NodeTraits::__base_pointer __base_pointer;
0295   typedef typename _NodeTraits::__link_pointer __link_pointer;
0296
0297   __link_pointer __prev_;
0298   __link_pointer __next_;
0299
0300   _LIBCPP_HIDE_FROM_ABI __list_node_base()
0301       : __prev_(_NodeTraits::__unsafe_link_pointer_cast(__self())),
0302         __next_(_NodeTraits::__unsafe_link_pointer_cast(__self())) {}
0303
0304   _LIBCPP_HIDE_FROM_ABI explicit __list_node_base(__link_pointer __prev, __link_pointer __next)
0305       : __prev_(__prev), __next_(__next) {}
0306
0307   _LIBCPP_HIDE_FROM_ABI __base_pointer __self() { return pointer_traits<__base_pointer>::pointer_to(*this); }
0308
0309   _LIBCPP_HIDE_FROM_ABI __node_pointer __as_node() { return static_cast<__node_pointer>(__self()); }
0310 };
0311
0312 template <class _Tp, class _VoidPtr>
0313 struct __list_node : public __list_node_base<_Tp, _VoidPtr> {
0314   // We allow starting the lifetime of nodes without initializing the value held by the node,
0315   // since that is handled by the list itself in order to be allocator-aware.
0316 #ifndef _LIBCPP_CXX03_LANG
0317
0318 private:
0319   union {
0320     _Tp __value_;
0321   };
0322
0323 public:
0324   _LIBCPP_HIDE_FROM_ABI _Tp& __get_value() { return __value_; }
0325 #else
0326
0327 private:
0328   _ALIGNAS_TYPE(_Tp) char __buffer_[sizeof(_Tp)];
0329
0330 public:
0331   _LIBCPP_HIDE_FROM_ABI _Tp& __get_value() { return *std::__launder(reinterpret_cast<_Tp*>(&__buffer_)); }
0332 #endif
0333
0334   typedef __list_node_base<_Tp, _VoidPtr> __base;
0335   typedef typename __base::__link_pointer __link_pointer;
0336
0337   _LIBCPP_HIDE_FROM_ABI explicit __list_node(__link_pointer __prev, __link_pointer __next) : __base(__prev, __next) {}
0338   _LIBCPP_HIDE_FROM_ABI ~__list_node() {}
0339
0340   _LIBCPP_HIDE_FROM_ABI __link_pointer __as_link() { return static_cast<__link_pointer>(__base::__self()); }
0341 };
0342
0343 template <class _Tp, class _Alloc = allocator<_Tp> >
0344 class _LIBCPP_TEMPLATE_VIS list;
0345 template <class _Tp, class _Alloc>
0346 class __list_imp;
0347 template <class _Tp, class _VoidPtr>
0348 class _LIBCPP_TEMPLATE_VIS __list_const_iterator;
0349
0350 template <class _Tp, class _VoidPtr>
0351 class _LIBCPP_TEMPLATE_VIS __list_iterator {
0352   typedef __list_node_pointer_traits<_Tp, _VoidPtr> _NodeTraits;
0353   typedef typename _NodeTraits::__link_pointer __link_pointer;
0354
0355   __link_pointer __ptr_;
0356
0357   _LIBCPP_HIDE_FROM_ABI explicit __list_iterator(__link_pointer __p) _NOEXCEPT : __ptr_(__p) {}
0358
0359   template <class, class>
0360   friend class list;
0361   template <class, class>
0362   friend class __list_imp;
0363   template <class, class>
0364   friend class __list_const_iterator;
0365
0366 public:
0367   typedef bidirectional_iterator_tag iterator_category;
0368   typedef _Tp value_type;
0369   typedef value_type& reference;
0370   typedef __rebind_pointer_t<_VoidPtr, value_type> pointer;
0371   typedef typename pointer_traits<pointer>::difference_type difference_type;
0372
0373   _LIBCPP_HIDE_FROM_ABI __list_iterator() _NOEXCEPT : __ptr_(nullptr) {}
0374
0375   _LIBCPP_HIDE_FROM_ABI reference operator*() const { return __ptr_->__as_node()->__get_value(); }
0376   _LIBCPP_HIDE_FROM_ABI pointer operator->() const {
0377     return pointer_traits<pointer>::pointer_to(__ptr_->__as_node()->__get_value());
0378   }
0379
0380   _LIBCPP_HIDE_FROM_ABI __list_iterator& operator++() {
0381     __ptr_ = __ptr_->__next_;
0382     return *this;
0383   }
0384   _LIBCPP_HIDE_FROM_ABI __list_iterator operator++(int) {
0385     __list_iterator __t(*this);
0386     ++(*this);
0387     return __t;
0388   }
0389
0390   _LIBCPP_HIDE_FROM_ABI __list_iterator& operator--() {
0391     __ptr_ = __ptr_->__prev_;
0392     return *this;
0393   }
0394   _LIBCPP_HIDE_FROM_ABI __list_iterator operator--(int) {
0395     __list_iterator __t(*this);
0396     --(*this);
0397     return __t;
0398   }
0399
0400   friend _LIBCPP_HIDE_FROM_ABI bool operator==(const __list_iterator& __x, const __list_iterator& __y) {
0401     return __x.__ptr_ == __y.__ptr_;
0402   }
0403   friend _LIBCPP_HIDE_FROM_ABI bool operator!=(const __list_iterator& __x, const __list_iterator& __y) {
0404     return !(__x == __y);
0405   }
0406 };
0407
0408 template <class _Tp, class _VoidPtr>
0409 class _LIBCPP_TEMPLATE_VIS __list_const_iterator {
0410   typedef __list_node_pointer_traits<_Tp, _VoidPtr> _NodeTraits;
0411   typedef typename _NodeTraits::__link_pointer __link_pointer;
0412
0413   __link_pointer __ptr_;
0414
0415   _LIBCPP_HIDE_FROM_ABI explicit __list_const_iterator(__link_pointer __p) _NOEXCEPT : __ptr_(__p) {}
0416
0417   template <class, class>
0418   friend class list;
0419   template <class, class>
0420   friend class __list_imp;
0421
0422 public:
0423   typedef bidirectional_iterator_tag iterator_category;
0424   typedef _Tp value_type;
0425   typedef const value_type& reference;
0426   typedef __rebind_pointer_t<_VoidPtr, const value_type> pointer;
0427   typedef typename pointer_traits<pointer>::difference_type difference_type;
0428
0429   _LIBCPP_HIDE_FROM_ABI __list_const_iterator() _NOEXCEPT : __ptr_(nullptr) {}
0430   _LIBCPP_HIDE_FROM_ABI __list_const_iterator(const __list_iterator<_Tp, _VoidPtr>& __p) _NOEXCEPT
0431       : __ptr_(__p.__ptr_) {}
0432
0433   _LIBCPP_HIDE_FROM_ABI reference operator*() const { return __ptr_->__as_node()->__get_value(); }
0434   _LIBCPP_HIDE_FROM_ABI pointer operator->() const {
0435     return pointer_traits<pointer>::pointer_to(__ptr_->__as_node()->__get_value());
0436   }
0437
0438   _LIBCPP_HIDE_FROM_ABI __list_const_iterator& operator++() {
0439     __ptr_ = __ptr_->__next_;
0440     return *this;
0441   }
0442   _LIBCPP_HIDE_FROM_ABI __list_const_iterator operator++(int) {
0443     __list_const_iterator __t(*this);
0444     ++(*this);
0445     return __t;
0446   }
0447
0448   _LIBCPP_HIDE_FROM_ABI __list_const_iterator& operator--() {
0449     __ptr_ = __ptr_->__prev_;
0450     return *this;
0451   }
0452   _LIBCPP_HIDE_FROM_ABI __list_const_iterator operator--(int) {
0453     __list_const_iterator __t(*this);
0454     --(*this);
0455     return __t;
0456   }
0457
0458   friend _LIBCPP_HIDE_FROM_ABI bool operator==(const __list_const_iterator& __x, const __list_const_iterator& __y) {
0459     return __x.__ptr_ == __y.__ptr_;
0460   }
0461   friend _LIBCPP_HIDE_FROM_ABI bool operator!=(const __list_const_iterator& __x, const __list_const_iterator& __y) {
0462     return !(__x == __y);
0463   }
0464 };
0465
0466 template <class _Tp, class _Alloc>
0467 class __list_imp {
0468 public:
0469   __list_imp(const __list_imp&)            = delete;
0470   __list_imp& operator=(const __list_imp&) = delete;
0471
0472   typedef _Alloc allocator_type;
0473   typedef allocator_traits<allocator_type> __alloc_traits;
0474   typedef typename __alloc_traits::size_type size_type;
0475
0476 protected:
0477   typedef _Tp value_type;
0478   typedef typename __alloc_traits::void_pointer __void_pointer;
0479   typedef __list_iterator<value_type, __void_pointer> iterator;
0480   typedef __list_const_iterator<value_type, __void_pointer> const_iterator;
0481   typedef __list_node_base<value_type, __void_pointer> __node_base;
0482   typedef __list_node<value_type, __void_pointer> __node_type;
0483   typedef __rebind_alloc<__alloc_traits, __node_type> __node_allocator;
0484   typedef allocator_traits<__node_allocator> __node_alloc_traits;
0485   typedef typename __node_alloc_traits::pointer __node_pointer;
0486   typedef typename __node_alloc_traits::pointer __node_const_pointer;
0487   typedef __list_node_pointer_traits<value_type, __void_pointer> __node_pointer_traits;
0488   typedef typename __node_pointer_traits::__link_pointer __link_pointer;
0489   typedef __link_pointer __link_const_pointer;
0490   typedef typename __alloc_traits::pointer pointer;
0491   typedef typename __alloc_traits::const_pointer const_pointer;
0492   typedef typename __alloc_traits::difference_type difference_type;
0493
0494   typedef __rebind_alloc<__alloc_traits, __node_base> __node_base_allocator;
0495   typedef typename allocator_traits<__node_base_allocator>::pointer __node_base_pointer;
0496   static_assert(!is_same<allocator_type, __node_allocator>::value,
0497                 "internal allocator type must differ from user-specified type; otherwise overload resolution breaks");
0498
0499   __node_base __end_;
0500   __compressed_pair<size_type, __node_allocator> __size_alloc_;
0501
0502   _LIBCPP_HIDE_FROM_ABI __link_pointer __end_as_link() const _NOEXCEPT {
0503     return __node_pointer_traits::__unsafe_link_pointer_cast(const_cast<__node_base&>(__end_).__self());
0504   }
0505
0506   _LIBCPP_HIDE_FROM_ABI size_type& __sz() _NOEXCEPT { return __size_alloc_.first(); }
0507   _LIBCPP_HIDE_FROM_ABI const size_type& __sz() const _NOEXCEPT { return __size_alloc_.first(); }
0508   _LIBCPP_HIDE_FROM_ABI __node_allocator& __node_alloc() _NOEXCEPT { return __size_alloc_.second(); }
0509   _LIBCPP_HIDE_FROM_ABI const __node_allocator& __node_alloc() const _NOEXCEPT { return __size_alloc_.second(); }
0510
0511   _LIBCPP_HIDE_FROM_ABI size_type __node_alloc_max_size() const _NOEXCEPT {
0512     return __node_alloc_traits::max_size(__node_alloc());
0513   }
0514   _LIBCPP_HIDE_FROM_ABI static void __unlink_nodes(__link_pointer __f, __link_pointer __l) _NOEXCEPT;
0515
0516   _LIBCPP_HIDE_FROM_ABI __list_imp() _NOEXCEPT_(is_nothrow_default_constructible<__node_allocator>::value);
0517   _LIBCPP_HIDE_FROM_ABI __list_imp(const allocator_type& __a);
0518   _LIBCPP_HIDE_FROM_ABI __list_imp(const __node_allocator& __a);
0519 #ifndef _LIBCPP_CXX03_LANG
0520   _LIBCPP_HIDE_FROM_ABI __list_imp(__node_allocator&& __a) _NOEXCEPT;
0521 #endif
0522   _LIBCPP_HIDE_FROM_ABI ~__list_imp();
0523   _LIBCPP_HIDE_FROM_ABI void clear() _NOEXCEPT;
0524   _LIBCPP_HIDE_FROM_ABI bool empty() const _NOEXCEPT { return __sz() == 0; }
0525
0526   _LIBCPP_HIDE_FROM_ABI iterator begin() _NOEXCEPT { return iterator(__end_.__next_); }
0527   _LIBCPP_HIDE_FROM_ABI const_iterator begin() const _NOEXCEPT { return const_iterator(__end_.__next_); }
0528   _LIBCPP_HIDE_FROM_ABI iterator end() _NOEXCEPT { return iterator(__end_as_link()); }
0529   _LIBCPP_HIDE_FROM_ABI const_iterator end() const _NOEXCEPT { return const_iterator(__end_as_link()); }
0530
0531   _LIBCPP_HIDE_FROM_ABI void swap(__list_imp& __c)
0532 #if _LIBCPP_STD_VER >= 14
0533       _NOEXCEPT;
0534 #else
0535       _NOEXCEPT_(!__alloc_traits::propagate_on_container_swap::value || __is_nothrow_swappable_v<allocator_type>);
0536 #endif
0537
0538   _LIBCPP_HIDE_FROM_ABI void __copy_assign_alloc(const __list_imp& __c) {
0539     __copy_assign_alloc(
0540         __c, integral_constant<bool, __node_alloc_traits::propagate_on_container_copy_assignment::value>());
0541   }
0542
0543   _LIBCPP_HIDE_FROM_ABI void __move_assign_alloc(__list_imp& __c)
0544       _NOEXCEPT_(!__node_alloc_traits::propagate_on_container_move_assignment::value ||
0545                  is_nothrow_move_assignable<__node_allocator>::value) {
0546     __move_assign_alloc(
0547         __c, integral_constant<bool, __node_alloc_traits::propagate_on_container_move_assignment::value>());
0548   }
0549
0550   template <class... _Args>
0551   _LIBCPP_HIDE_FROM_ABI __node_pointer __create_node(__link_pointer __prev, __link_pointer __next, _Args&&... __args) {
0552     __node_allocator& __alloc = __node_alloc();
0553     __allocation_guard<__node_allocator> __guard(__alloc, 1);
0554     // Begin the lifetime of the node itself. Note that this doesn't begin the lifetime of the value
0555     // held inside the node, since we need to use the allocator's construct() method for that.
0556     //
0557     // We don't use the allocator's construct() method to construct the node itself since the
0558     // Cpp17FooInsertable named requirements don't require the allocator's construct() method
0559     // to work on anything other than the value_type.
0560     std::__construct_at(std::addressof(*__guard.__get()), __prev, __next);
0561
0562     // Now construct the value_type using the allocator's construct() method.
0563     __node_alloc_traits::construct(
0564         __alloc, std::addressof(__guard.__get()->__get_value()), std::forward<_Args>(__args)...);
0565     return __guard.__release_ptr();
0566   }
0567
0568   _LIBCPP_HIDE_FROM_ABI void __delete_node(__node_pointer __node) {
0569     // For the same reason as above, we use the allocator's destroy() method for the value_type,
0570     // but not for the node itself.
0571     __node_allocator& __alloc = __node_alloc();
0572     __node_alloc_traits::destroy(__alloc, std::addressof(__node->__get_value()));
0573     std::__destroy_at(std::addressof(*__node));
0574     __node_alloc_traits::deallocate(__alloc, __node, 1);
0575   }
0576
0577 private:
0578   _LIBCPP_HIDE_FROM_ABI void __copy_assign_alloc(const __list_imp& __c, true_type) {
0579     if (__node_alloc() != __c.__node_alloc())
0580       clear();
0581     __node_alloc() = __c.__node_alloc();
0582   }
0583
0584   _LIBCPP_HIDE_FROM_ABI void __copy_assign_alloc(const __list_imp&, false_type) {}
0585
0586   _LIBCPP_HIDE_FROM_ABI void __move_assign_alloc(__list_imp& __c, true_type)
0587       _NOEXCEPT_(is_nothrow_move_assignable<__node_allocator>::value) {
0588     __node_alloc() = std::move(__c.__node_alloc());
0589   }
0590
0591   _LIBCPP_HIDE_FROM_ABI void __move_assign_alloc(__list_imp&, false_type) _NOEXCEPT {}
0592 };
0593
0594 // Unlink nodes [__f, __l]
0595 template <class _Tp, class _Alloc>
0596 inline void __list_imp<_Tp, _Alloc>::__unlink_nodes(__link_pointer __f, __link_pointer __l) _NOEXCEPT {
0597   __f->__prev_->__next_ = __l->__next_;
0598   __l->__next_->__prev_ = __f->__prev_;
0599 }
0600
0601 template <class _Tp, class _Alloc>
0602 inline __list_imp<_Tp, _Alloc>::__list_imp() _NOEXCEPT_(is_nothrow_default_constructible<__node_allocator>::value)
0603     : __size_alloc_(0, __default_init_tag()) {}
0604
0605 template <class _Tp, class _Alloc>
0606 inline __list_imp<_Tp, _Alloc>::__list_imp(const allocator_type& __a) : __size_alloc_(0, __node_allocator(__a)) {}
0607
0608 template <class _Tp, class _Alloc>
0609 inline __list_imp<_Tp, _Alloc>::__list_imp(const __node_allocator& __a) : __size_alloc_(0, __a) {}
0610
0611 #ifndef _LIBCPP_CXX03_LANG
0612 template <class _Tp, class _Alloc>
0613 inline __list_imp<_Tp, _Alloc>::__list_imp(__node_allocator&& __a) _NOEXCEPT : __size_alloc_(0, std::move(__a)) {}
0614 #endif
0615
0616 template <class _Tp, class _Alloc>
0617 __list_imp<_Tp, _Alloc>::~__list_imp() {
0618   clear();
0619 }
0620
0621 template <class _Tp, class _Alloc>
0622 void __list_imp<_Tp, _Alloc>::clear() _NOEXCEPT {
0623   if (!empty()) {
0624     __link_pointer __f = __end_.__next_;
0625     __link_pointer __l = __end_as_link();
0626     __unlink_nodes(__f, __l->__prev_);
0627     __sz() = 0;
0628     while (__f != __l) {
0629       __node_pointer __np = __f->__as_node();
0630       __f                 = __f->__next_;
0631       __delete_node(__np);
0632     }
0633   }
0634 }
0635
0636 template <class _Tp, class _Alloc>
0637 void __list_imp<_Tp, _Alloc>::swap(__list_imp& __c)
0638 #if _LIBCPP_STD_VER >= 14
0639     _NOEXCEPT
0640 #else
0641     _NOEXCEPT_(!__alloc_traits::propagate_on_container_swap::value || __is_nothrow_swappable_v<allocator_type>)
0642 #endif
0643 {
0644   _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR(
0645       __alloc_traits::propagate_on_container_swap::value || this->__node_alloc() == __c.__node_alloc(),
0646       "list::swap: Either propagate_on_container_swap must be true"
0647       " or the allocators must compare equal");
0648   using std::swap;
0649   std::__swap_allocator(__node_alloc(), __c.__node_alloc());
0650   swap(__sz(), __c.__sz());
0651   swap(__end_, __c.__end_);
0652   if (__sz() == 0)
0653     __end_.__next_ = __end_.__prev_ = __end_as_link();
0654   else
0655     __end_.__prev_->__next_ = __end_.__next_->__prev_ = __end_as_link();
0656   if (__c.__sz() == 0)
0657     __c.__end_.__next_ = __c.__end_.__prev_ = __c.__end_as_link();
0658   else
0659     __c.__end_.__prev_->__next_ = __c.__end_.__next_->__prev_ = __c.__end_as_link();
0660 }
0661
0662 template <class _Tp, class _Alloc /*= allocator<_Tp>*/>
0663 class _LIBCPP_TEMPLATE_VIS list : private __list_imp<_Tp, _Alloc> {
0664   typedef __list_imp<_Tp, _Alloc> base;
0665   typedef typename base::__node_type __node_type;
0666   typedef typename base::__node_allocator __node_allocator;
0667   typedef typename base::__node_pointer __node_pointer;
0668   typedef typename base::__node_alloc_traits __node_alloc_traits;
0669   typedef typename base::__node_base __node_base;
0670   typedef typename base::__node_base_pointer __node_base_pointer;
0671   typedef typename base::__link_pointer __link_pointer;
0672
0673 public:
0674   typedef _Tp value_type;
0675   typedef _Alloc allocator_type;
0676   static_assert(__check_valid_allocator<allocator_type>::value);
0677   static_assert(is_same<value_type, typename allocator_type::value_type>::value,
0678                 "Allocator::value_type must be same type as value_type");
0679   typedef value_type& reference;
0680   typedef const value_type& const_reference;
0681   typedef typename base::pointer pointer;
0682   typedef typename base::const_pointer const_pointer;
0683   typedef typename base::size_type size_type;
0684   typedef typename base::difference_type difference_type;
0685   typedef typename base::iterator iterator;
0686   typedef typename base::const_iterator const_iterator;
0687   typedef std::reverse_iterator<iterator> reverse_iterator;
0688   typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
0689 #if _LIBCPP_STD_VER >= 20
0690   typedef size_type __remove_return_type;
0691 #else
0692   typedef void __remove_return_type;
0693 #endif
0694
0695   _LIBCPP_HIDE_FROM_ABI list() _NOEXCEPT_(is_nothrow_default_constructible<__node_allocator>::value) {}
0696   _LIBCPP_HIDE_FROM_ABI explicit list(const allocator_type& __a) : base(__a) {}
0697   _LIBCPP_HIDE_FROM_ABI explicit list(size_type __n);
0698 #if _LIBCPP_STD_VER >= 14
0699   _LIBCPP_HIDE_FROM_ABI explicit list(size_type __n, const allocator_type& __a);
0700 #endif
0701   _LIBCPP_HIDE_FROM_ABI list(size_type __n, const value_type& __x);
0702   template <__enable_if_t<__is_allocator<_Alloc>::value, int> = 0>
0703   _LIBCPP_HIDE_FROM_ABI list(size_type __n, const value_type& __x, const allocator_type& __a) : base(__a) {
0704     for (; __n > 0; --__n)
0705       push_back(__x);
0706   }
0707
0708   template <class _InpIter, __enable_if_t<__has_input_iterator_category<_InpIter>::value, int> = 0>
0709   _LIBCPP_HIDE_FROM_ABI list(_InpIter __f, _InpIter __l);
0710
0711   template <class _InpIter, __enable_if_t<__has_input_iterator_category<_InpIter>::value, int> = 0>
0712   _LIBCPP_HIDE_FROM_ABI list(_InpIter __f, _InpIter __l, const allocator_type& __a);
0713
0714 #if _LIBCPP_STD_VER >= 23
0715   template <_ContainerCompatibleRange<_Tp> _Range>
0716   _LIBCPP_HIDE_FROM_ABI list(from_range_t, _Range&& __range, const allocator_type& __a = allocator_type()) : base(__a) {
0717     prepend_range(std::forward<_Range>(__range));
0718   }
0719 #endif
0720
0721   _LIBCPP_HIDE_FROM_ABI list(const list& __c);
0722   _LIBCPP_HIDE_FROM_ABI list(const list& __c, const __type_identity_t<allocator_type>& __a);
0723   _LIBCPP_HIDE_FROM_ABI list& operator=(const list& __c);
0724 #ifndef _LIBCPP_CXX03_LANG
0725   _LIBCPP_HIDE_FROM_ABI list(initializer_list<value_type> __il);
0726   _LIBCPP_HIDE_FROM_ABI list(initializer_list<value_type> __il, const allocator_type& __a);
0727
0728   _LIBCPP_HIDE_FROM_ABI list(list&& __c) _NOEXCEPT_(is_nothrow_move_constructible<__node_allocator>::value);
0729   _LIBCPP_HIDE_FROM_ABI list(list&& __c, const __type_identity_t<allocator_type>& __a);
0730   _LIBCPP_HIDE_FROM_ABI list& operator=(list&& __c)
0731       _NOEXCEPT_(__node_alloc_traits::propagate_on_container_move_assignment::value&&
0732                      is_nothrow_move_assignable<__node_allocator>::value);
0733
0734   _LIBCPP_HIDE_FROM_ABI list& operator=(initializer_list<value_type> __il) {
0735     assign(__il.begin(), __il.end());
0736     return *this;
0737   }
0738
0739   _LIBCPP_HIDE_FROM_ABI void assign(initializer_list<value_type> __il) { assign(__il.begin(), __il.end()); }
0740 #endif // _LIBCPP_CXX03_LANG
0741
0742   template <class _InpIter, __enable_if_t<__has_input_iterator_category<_InpIter>::value, int> = 0>
0743   _LIBCPP_HIDE_FROM_ABI void assign(_InpIter __f, _InpIter __l);
0744
0745 #if _LIBCPP_STD_VER >= 23
0746   template <_ContainerCompatibleRange<_Tp> _Range>
0747   _LIBCPP_HIDE_FROM_ABI void assign_range(_Range&& __range) {
0748     __assign_with_sentinel(ranges::begin(__range), ranges::end(__range));
0749   }
0750 #endif
0751
0752   _LIBCPP_HIDE_FROM_ABI void assign(size_type __n, const value_type& __x);
0753
0754   _LIBCPP_HIDE_FROM_ABI allocator_type get_allocator() const _NOEXCEPT;
0755
0756   _LIBCPP_HIDE_FROM_ABI size_type size() const _NOEXCEPT { return base::__sz(); }
0757   _LIBCPP_NODISCARD _LIBCPP_HIDE_FROM_ABI bool empty() const _NOEXCEPT { return base::empty(); }
0758   _LIBCPP_HIDE_FROM_ABI size_type max_size() const _NOEXCEPT {
0759     return std::min<size_type>(base::__node_alloc_max_size(), numeric_limits<difference_type >::max());
0760   }
0761
0762   _LIBCPP_HIDE_FROM_ABI iterator begin() _NOEXCEPT { return base::begin(); }
0763   _LIBCPP_HIDE_FROM_ABI const_iterator begin() const _NOEXCEPT { return base::begin(); }
0764   _LIBCPP_HIDE_FROM_ABI iterator end() _NOEXCEPT { return base::end(); }
0765   _LIBCPP_HIDE_FROM_ABI const_iterator end() const _NOEXCEPT { return base::end(); }
0766   _LIBCPP_HIDE_FROM_ABI const_iterator cbegin() const _NOEXCEPT { return base::begin(); }
0767   _LIBCPP_HIDE_FROM_ABI const_iterator cend() const _NOEXCEPT { return base::end(); }
0768
0769   _LIBCPP_HIDE_FROM_ABI reverse_iterator rbegin() _NOEXCEPT { return reverse_iterator(end()); }
0770   _LIBCPP_HIDE_FROM_ABI const_reverse_iterator rbegin() const _NOEXCEPT { return const_reverse_iterator(end()); }
0771   _LIBCPP_HIDE_FROM_ABI reverse_iterator rend() _NOEXCEPT { return reverse_iterator(begin()); }
0772   _LIBCPP_HIDE_FROM_ABI const_reverse_iterator rend() const _NOEXCEPT { return const_reverse_iterator(begin()); }
0773   _LIBCPP_HIDE_FROM_ABI const_reverse_iterator crbegin() const _NOEXCEPT { return const_reverse_iterator(end()); }
0774   _LIBCPP_HIDE_FROM_ABI const_reverse_iterator crend() const _NOEXCEPT { return const_reverse_iterator(begin()); }
0775
0776   _LIBCPP_HIDE_FROM_ABI reference front() {
0777     _LIBCPP_ASSERT_VALID_ELEMENT_ACCESS(!empty(), "list::front called on empty list");
0778     return base::__end_.__next_->__as_node()->__get_value();
0779   }
0780   _LIBCPP_HIDE_FROM_ABI const_reference front() const {
0781     _LIBCPP_ASSERT_VALID_ELEMENT_ACCESS(!empty(), "list::front called on empty list");
0782     return base::__end_.__next_->__as_node()->__get_value();
0783   }
0784   _LIBCPP_HIDE_FROM_ABI reference back() {
0785     _LIBCPP_ASSERT_VALID_ELEMENT_ACCESS(!empty(), "list::back called on empty list");
0786     return base::__end_.__prev_->__as_node()->__get_value();
0787   }
0788   _LIBCPP_HIDE_FROM_ABI const_reference back() const {
0789     _LIBCPP_ASSERT_VALID_ELEMENT_ACCESS(!empty(), "list::back called on empty list");
0790     return base::__end_.__prev_->__as_node()->__get_value();
0791   }
0792
0793 #ifndef _LIBCPP_CXX03_LANG
0794   _LIBCPP_HIDE_FROM_ABI void push_front(value_type&& __x);
0795   _LIBCPP_HIDE_FROM_ABI void push_back(value_type&& __x);
0796
0797 #  if _LIBCPP_STD_VER >= 23
0798   template <_ContainerCompatibleRange<_Tp> _Range>
0799   _LIBCPP_HIDE_FROM_ABI void prepend_range(_Range&& __range) {
0800     insert_range(begin(), std::forward<_Range>(__range));
0801   }
0802
0803   template <_ContainerCompatibleRange<_Tp> _Range>
0804   _LIBCPP_HIDE_FROM_ABI void append_range(_Range&& __range) {
0805     insert_range(end(), std::forward<_Range>(__range));
0806   }
0807 #  endif
0808
0809   template <class... _Args>
0810 #  if _LIBCPP_STD_VER >= 17
0811   _LIBCPP_HIDE_FROM_ABI reference emplace_front(_Args&&... __args);
0812 #  else
0813   _LIBCPP_HIDE_FROM_ABI void emplace_front(_Args&&... __args);
0814 #  endif
0815   template <class... _Args>
0816 #  if _LIBCPP_STD_VER >= 17
0817   _LIBCPP_HIDE_FROM_ABI reference emplace_back(_Args&&... __args);
0818 #  else
0819   _LIBCPP_HIDE_FROM_ABI void emplace_back(_Args&&... __args);
0820 #  endif
0821   template <class... _Args>
0822   _LIBCPP_HIDE_FROM_ABI iterator emplace(const_iterator __p, _Args&&... __args);
0823
0824   _LIBCPP_HIDE_FROM_ABI iterator insert(const_iterator __p, value_type&& __x);
0825
0826   _LIBCPP_HIDE_FROM_ABI iterator insert(const_iterator __p, initializer_list<value_type> __il) {
0827     return insert(__p, __il.begin(), __il.end());
0828   }
0829 #endif // _LIBCPP_CXX03_LANG
0830
0831   _LIBCPP_HIDE_FROM_ABI void push_front(const value_type& __x);
0832   _LIBCPP_HIDE_FROM_ABI void push_back(const value_type& __x);
0833
0834 #ifndef _LIBCPP_CXX03_LANG
0835   template <class _Arg>
0836   _LIBCPP_HIDE_FROM_ABI void __emplace_back(_Arg&& __arg) {
0837     emplace_back(std::forward<_Arg>(__arg));
0838   }
0839 #else
0840   _LIBCPP_HIDE_FROM_ABI void __emplace_back(value_type const& __arg) { push_back(__arg); }
0841 #endif
0842
0843   _LIBCPP_HIDE_FROM_ABI iterator insert(const_iterator __p, const value_type& __x);
0844   _LIBCPP_HIDE_FROM_ABI iterator insert(const_iterator __p, size_type __n, const value_type& __x);
0845
0846   template <class _InpIter, __enable_if_t<__has_input_iterator_category<_InpIter>::value, int> = 0>
0847   _LIBCPP_HIDE_FROM_ABI iterator insert(const_iterator __p, _InpIter __f, _InpIter __l);
0848
0849 #if _LIBCPP_STD_VER >= 23
0850   template <_ContainerCompatibleRange<_Tp> _Range>
0851   _LIBCPP_HIDE_FROM_ABI iterator insert_range(const_iterator __position, _Range&& __range) {
0852     return __insert_with_sentinel(__position, ranges::begin(__range), ranges::end(__range));
0853   }
0854 #endif
0855
0856   _LIBCPP_HIDE_FROM_ABI void swap(list& __c)
0857 #if _LIBCPP_STD_VER >= 14
0858       _NOEXCEPT
0859 #else
0860       _NOEXCEPT_(!__node_alloc_traits::propagate_on_container_swap::value || __is_nothrow_swappable_v<__node_allocator>)
0861 #endif
0862   {
0863     base::swap(__c);
0864   }
0865   _LIBCPP_HIDE_FROM_ABI void clear() _NOEXCEPT { base::clear(); }
0866
0867   _LIBCPP_HIDE_FROM_ABI void pop_front();
0868   _LIBCPP_HIDE_FROM_ABI void pop_back();
0869
0870   _LIBCPP_HIDE_FROM_ABI iterator erase(const_iterator __p);
0871   _LIBCPP_HIDE_FROM_ABI iterator erase(const_iterator __f, const_iterator __l);
0872
0873   _LIBCPP_HIDE_FROM_ABI void resize(size_type __n);
0874   _LIBCPP_HIDE_FROM_ABI void resize(size_type __n, const value_type& __x);
0875
0876   _LIBCPP_HIDE_FROM_ABI void splice(const_iterator __p, list& __c);
0877 #ifndef _LIBCPP_CXX03_LANG
0878   _LIBCPP_HIDE_FROM_ABI void splice(const_iterator __p, list&& __c) { splice(__p, __c); }
0879   _LIBCPP_HIDE_FROM_ABI void splice(const_iterator __p, list&& __c, const_iterator __i) { splice(__p, __c, __i); }
0880   _LIBCPP_HIDE_FROM_ABI void splice(const_iterator __p, list&& __c, const_iterator __f, const_iterator __l) {
0881     splice(__p, __c, __f, __l);
0882   }
0883 #endif
0884   _LIBCPP_HIDE_FROM_ABI void splice(const_iterator __p, list& __c, const_iterator __i);
0885   _LIBCPP_HIDE_FROM_ABI void splice(const_iterator __p, list& __c, const_iterator __f, const_iterator __l);
0886
0887   _LIBCPP_HIDE_FROM_ABI __remove_return_type remove(const value_type& __x);
0888   template <class _Pred>
0889   _LIBCPP_HIDE_FROM_ABI __remove_return_type remove_if(_Pred __pred);
0890   _LIBCPP_HIDE_FROM_ABI __remove_return_type unique() { return unique(__equal_to()); }
0891   template <class _BinaryPred>
0892   _LIBCPP_HIDE_FROM_ABI __remove_return_type unique(_BinaryPred __binary_pred);
0893   _LIBCPP_HIDE_FROM_ABI void merge(list& __c);
0894 #ifndef _LIBCPP_CXX03_LANG
0895   _LIBCPP_HIDE_FROM_ABI void merge(list&& __c) { merge(__c); }
0896
0897   template <class _Comp>
0898   _LIBCPP_HIDE_FROM_ABI void merge(list&& __c, _Comp __comp) {
0899     merge(__c, __comp);
0900   }
0901 #endif
0902   template <class _Comp>
0903   _LIBCPP_HIDE_FROM_ABI void merge(list& __c, _Comp __comp);
0904
0905   _LIBCPP_HIDE_FROM_ABI void sort();
0906   template <class _Comp>
0907   _LIBCPP_HIDE_FROM_ABI void sort(_Comp __comp);
0908
0909   _LIBCPP_HIDE_FROM_ABI void reverse() _NOEXCEPT;
0910
0911   _LIBCPP_HIDE_FROM_ABI bool __invariants() const;
0912
0913 private:
0914   template <class _Iterator, class _Sentinel>
0915   _LIBCPP_HIDE_FROM_ABI void __assign_with_sentinel(_Iterator __f, _Sentinel __l);
0916
0917   template <class _Iterator, class _Sentinel>
0918   _LIBCPP_HIDE_FROM_ABI iterator __insert_with_sentinel(const_iterator __p, _Iterator __f, _Sentinel __l);
0919
0920   _LIBCPP_HIDE_FROM_ABI static void __link_nodes(__link_pointer __p, __link_pointer __f, __link_pointer __l);
0921   _LIBCPP_HIDE_FROM_ABI void __link_nodes_at_front(__link_pointer __f, __link_pointer __l);
0922   _LIBCPP_HIDE_FROM_ABI void __link_nodes_at_back(__link_pointer __f, __link_pointer __l);
0923   _LIBCPP_HIDE_FROM_ABI iterator __iterator(size_type __n);
0924   // TODO: Make this _LIBCPP_HIDE_FROM_ABI
0925   template <class _Comp>
0926   _LIBCPP_HIDDEN static iterator __sort(iterator __f1, iterator __e2, size_type __n, _Comp& __comp);
0927
0928   _LIBCPP_HIDE_FROM_ABI void __move_assign(list& __c, true_type)
0929       _NOEXCEPT_(is_nothrow_move_assignable<__node_allocator>::value);
0930   _LIBCPP_HIDE_FROM_ABI void __move_assign(list& __c, false_type);
0931 };
0932
0933 #if _LIBCPP_STD_VER >= 17
0934 template <class _InputIterator,
0935           class _Alloc = allocator<__iter_value_type<_InputIterator>>,
0936           class        = enable_if_t<__has_input_iterator_category<_InputIterator>::value>,
0937           class        = enable_if_t<__is_allocator<_Alloc>::value> >
0938 list(_InputIterator, _InputIterator) -> list<__iter_value_type<_InputIterator>, _Alloc>;
0939
0940 template <class _InputIterator,
0941           class _Alloc,
0942           class = enable_if_t<__has_input_iterator_category<_InputIterator>::value>,
0943           class = enable_if_t<__is_allocator<_Alloc>::value> >
0944 list(_InputIterator, _InputIterator, _Alloc) -> list<__iter_value_type<_InputIterator>, _Alloc>;
0945 #endif
0946
0947 #if _LIBCPP_STD_VER >= 23
0948 template <ranges::input_range _Range,
0949           class _Alloc = allocator<ranges::range_value_t<_Range>>,
0950           class        = enable_if_t<__is_allocator<_Alloc>::value> >
0951 list(from_range_t, _Range&&, _Alloc = _Alloc()) -> list<ranges::range_value_t<_Range>, _Alloc>;
0952 #endif
0953
0954 // Link in nodes [__f, __l] just prior to __p
0955 template <class _Tp, class _Alloc>
0956 inline void list<_Tp, _Alloc>::__link_nodes(__link_pointer __p, __link_pointer __f, __link_pointer __l) {
0957   __p->__prev_->__next_ = __f;
0958   __f->__prev_          = __p->__prev_;
0959   __p->__prev_          = __l;
0960   __l->__next_          = __p;
0961 }
0962
0963 // Link in nodes [__f, __l] at the front of the list
0964 template <class _Tp, class _Alloc>
0965 inline void list<_Tp, _Alloc>::__link_nodes_at_front(__link_pointer __f, __link_pointer __l) {
0966   __f->__prev_          = base::__end_as_link();
0967   __l->__next_          = base::__end_.__next_;
0968   __l->__next_->__prev_ = __l;
0969   base::__end_.__next_  = __f;
0970 }
0971
0972 // Link in nodes [__f, __l] at the back of the list
0973 template <class _Tp, class _Alloc>
0974 inline void list<_Tp, _Alloc>::__link_nodes_at_back(__link_pointer __f, __link_pointer __l) {
0975   __l->__next_          = base::__end_as_link();
0976   __f->__prev_          = base::__end_.__prev_;
0977   __f->__prev_->__next_ = __f;
0978   base::__end_.__prev_  = __l;
0979 }
0980
0981 template <class _Tp, class _Alloc>
0982 inline typename list<_Tp, _Alloc>::iterator list<_Tp, _Alloc>::__iterator(size_type __n) {
0983   return __n <= base::__sz() / 2 ? std::next(begin(), __n) : std::prev(end(), base::__sz() - __n);
0984 }
0985
0986 template <class _Tp, class _Alloc>
0987 list<_Tp, _Alloc>::list(size_type __n) {
0988   for (; __n > 0; --__n)
0989 #ifndef _LIBCPP_CXX03_LANG
0990     emplace_back();
0991 #else
0992     push_back(value_type());
0993 #endif
0994 }
0995
0996 #if _LIBCPP_STD_VER >= 14
0997 template <class _Tp, class _Alloc>
0998 list<_Tp, _Alloc>::list(size_type __n, const allocator_type& __a) : base(__a) {
0999   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___CXX03_LIST