xref: /freebsd/contrib/llvm-project/libcxx/include/list (revision b1879975794772ee51f0b4865753364c7d7626c3)
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
16namespace std
17{
18
19template <class T, class Alloc = allocator<T> >
20class list
21{
22public:
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
161template <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
165template<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
169template <class T, class Alloc>
170    bool operator==(const list<T,Alloc>& x, const list<T,Alloc>& y);
171template <class T, class Alloc>
172    bool operator< (const list<T,Alloc>& x, const list<T,Alloc>& y);     // removed in C++20
173template <class T, class Alloc>
174    bool operator!=(const list<T,Alloc>& x, const list<T,Alloc>& y);     // removed in C++20
175template <class T, class Alloc>
176    bool operator> (const list<T,Alloc>& x, const list<T,Alloc>& y);     // removed in C++20
177template <class T, class Alloc>
178    bool operator>=(const list<T,Alloc>& x, const list<T,Alloc>& y);     // removed in C++20
179template <class T, class Alloc>
180    bool operator<=(const list<T,Alloc>& x, const list<T,Alloc>& y);     // removed in C++20
181template<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
185template <class T, class Alloc>
186    void swap(list<T,Alloc>& x, list<T,Alloc>& y)
187         noexcept(noexcept(x.swap(y)));
188
189template <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
192template <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>
206#include <__config>
207#include <__format/enable_insertable.h>
208#include <__iterator/distance.h>
209#include <__iterator/iterator_traits.h>
210#include <__iterator/move_iterator.h>
211#include <__iterator/next.h>
212#include <__iterator/prev.h>
213#include <__iterator/reverse_iterator.h>
214#include <__memory/addressof.h>
215#include <__memory/allocation_guard.h>
216#include <__memory/allocator.h>
217#include <__memory/allocator_traits.h>
218#include <__memory/compressed_pair.h>
219#include <__memory/construct_at.h>
220#include <__memory/pointer_traits.h>
221#include <__memory/swap_allocator.h>
222#include <__memory_resource/polymorphic_allocator.h>
223#include <__ranges/access.h>
224#include <__ranges/concepts.h>
225#include <__ranges/container_compatible_range.h>
226#include <__ranges/from_range.h>
227#include <__type_traits/conditional.h>
228#include <__type_traits/is_allocator.h>
229#include <__type_traits/is_nothrow_assignable.h>
230#include <__type_traits/is_nothrow_constructible.h>
231#include <__type_traits/is_pointer.h>
232#include <__type_traits/is_same.h>
233#include <__type_traits/type_identity.h>
234#include <__utility/forward.h>
235#include <__utility/move.h>
236#include <__utility/swap.h>
237#include <cstring>
238#include <limits>
239#include <new> // __launder
240#include <version>
241
242// standard-mandated includes
243
244// [iterator.range]
245#include <__iterator/access.h>
246#include <__iterator/data.h>
247#include <__iterator/empty.h>
248#include <__iterator/reverse_access.h>
249#include <__iterator/size.h>
250
251// [list.syn]
252#include <compare>
253#include <initializer_list>
254
255#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
256#  pragma GCC system_header
257#endif
258
259_LIBCPP_PUSH_MACROS
260#include <__undef_macros>
261
262_LIBCPP_BEGIN_NAMESPACE_STD
263
264template <class _Tp, class _VoidPtr>
265struct __list_node;
266template <class _Tp, class _VoidPtr>
267struct __list_node_base;
268
269template <class _Tp, class _VoidPtr>
270struct __list_node_pointer_traits {
271  typedef __rebind_pointer_t<_VoidPtr, __list_node<_Tp, _VoidPtr> > __node_pointer;
272  typedef __rebind_pointer_t<_VoidPtr, __list_node_base<_Tp, _VoidPtr> > __base_pointer;
273
274#if defined(_LIBCPP_ABI_LIST_REMOVE_NODE_POINTER_UB)
275  typedef __base_pointer __link_pointer;
276#else
277  typedef __conditional_t<is_pointer<_VoidPtr>::value, __base_pointer, __node_pointer> __link_pointer;
278#endif
279
280  typedef __conditional_t<is_same<__link_pointer, __node_pointer>::value, __base_pointer, __node_pointer>
281      __non_link_pointer;
282
283  static _LIBCPP_HIDE_FROM_ABI __link_pointer __unsafe_link_pointer_cast(__link_pointer __p) { return __p; }
284
285  static _LIBCPP_HIDE_FROM_ABI __link_pointer __unsafe_link_pointer_cast(__non_link_pointer __p) {
286    return static_cast<__link_pointer>(static_cast<_VoidPtr>(__p));
287  }
288};
289
290template <class _Tp, class _VoidPtr>
291struct __list_node_base {
292  typedef __list_node_pointer_traits<_Tp, _VoidPtr> _NodeTraits;
293  typedef typename _NodeTraits::__node_pointer __node_pointer;
294  typedef typename _NodeTraits::__base_pointer __base_pointer;
295  typedef typename _NodeTraits::__link_pointer __link_pointer;
296
297  __link_pointer __prev_;
298  __link_pointer __next_;
299
300  _LIBCPP_HIDE_FROM_ABI __list_node_base()
301      : __prev_(_NodeTraits::__unsafe_link_pointer_cast(__self())),
302        __next_(_NodeTraits::__unsafe_link_pointer_cast(__self())) {}
303
304  _LIBCPP_HIDE_FROM_ABI explicit __list_node_base(__link_pointer __prev, __link_pointer __next)
305      : __prev_(__prev), __next_(__next) {}
306
307  _LIBCPP_HIDE_FROM_ABI __base_pointer __self() { return pointer_traits<__base_pointer>::pointer_to(*this); }
308
309  _LIBCPP_HIDE_FROM_ABI __node_pointer __as_node() { return static_cast<__node_pointer>(__self()); }
310};
311
312template <class _Tp, class _VoidPtr>
313struct __list_node : public __list_node_base<_Tp, _VoidPtr> {
314  // We allow starting the lifetime of nodes without initializing the value held by the node,
315  // since that is handled by the list itself in order to be allocator-aware.
316#ifndef _LIBCPP_CXX03_LANG
317
318private:
319  union {
320    _Tp __value_;
321  };
322
323public:
324  _LIBCPP_HIDE_FROM_ABI _Tp& __get_value() { return __value_; }
325#else
326
327private:
328  _ALIGNAS_TYPE(_Tp) char __buffer_[sizeof(_Tp)];
329
330public:
331  _LIBCPP_HIDE_FROM_ABI _Tp& __get_value() { return *std::__launder(reinterpret_cast<_Tp*>(&__buffer_)); }
332#endif
333
334  typedef __list_node_base<_Tp, _VoidPtr> __base;
335  typedef typename __base::__link_pointer __link_pointer;
336
337  _LIBCPP_HIDE_FROM_ABI explicit __list_node(__link_pointer __prev, __link_pointer __next) : __base(__prev, __next) {}
338  _LIBCPP_HIDE_FROM_ABI ~__list_node() {}
339
340  _LIBCPP_HIDE_FROM_ABI __link_pointer __as_link() { return static_cast<__link_pointer>(__base::__self()); }
341};
342
343template <class _Tp, class _Alloc = allocator<_Tp> >
344class _LIBCPP_TEMPLATE_VIS list;
345template <class _Tp, class _Alloc>
346class __list_imp;
347template <class _Tp, class _VoidPtr>
348class _LIBCPP_TEMPLATE_VIS __list_const_iterator;
349
350template <class _Tp, class _VoidPtr>
351class _LIBCPP_TEMPLATE_VIS __list_iterator {
352  typedef __list_node_pointer_traits<_Tp, _VoidPtr> _NodeTraits;
353  typedef typename _NodeTraits::__link_pointer __link_pointer;
354
355  __link_pointer __ptr_;
356
357  _LIBCPP_HIDE_FROM_ABI explicit __list_iterator(__link_pointer __p) _NOEXCEPT : __ptr_(__p) {}
358
359  template <class, class>
360  friend class list;
361  template <class, class>
362  friend class __list_imp;
363  template <class, class>
364  friend class __list_const_iterator;
365
366public:
367  typedef bidirectional_iterator_tag iterator_category;
368  typedef _Tp value_type;
369  typedef value_type& reference;
370  typedef __rebind_pointer_t<_VoidPtr, value_type> pointer;
371  typedef typename pointer_traits<pointer>::difference_type difference_type;
372
373  _LIBCPP_HIDE_FROM_ABI __list_iterator() _NOEXCEPT : __ptr_(nullptr) {}
374
375  _LIBCPP_HIDE_FROM_ABI reference operator*() const { return __ptr_->__as_node()->__get_value(); }
376  _LIBCPP_HIDE_FROM_ABI pointer operator->() const {
377    return pointer_traits<pointer>::pointer_to(__ptr_->__as_node()->__get_value());
378  }
379
380  _LIBCPP_HIDE_FROM_ABI __list_iterator& operator++() {
381    __ptr_ = __ptr_->__next_;
382    return *this;
383  }
384  _LIBCPP_HIDE_FROM_ABI __list_iterator operator++(int) {
385    __list_iterator __t(*this);
386    ++(*this);
387    return __t;
388  }
389
390  _LIBCPP_HIDE_FROM_ABI __list_iterator& operator--() {
391    __ptr_ = __ptr_->__prev_;
392    return *this;
393  }
394  _LIBCPP_HIDE_FROM_ABI __list_iterator operator--(int) {
395    __list_iterator __t(*this);
396    --(*this);
397    return __t;
398  }
399
400  friend _LIBCPP_HIDE_FROM_ABI bool operator==(const __list_iterator& __x, const __list_iterator& __y) {
401    return __x.__ptr_ == __y.__ptr_;
402  }
403  friend _LIBCPP_HIDE_FROM_ABI bool operator!=(const __list_iterator& __x, const __list_iterator& __y) {
404    return !(__x == __y);
405  }
406};
407
408template <class _Tp, class _VoidPtr>
409class _LIBCPP_TEMPLATE_VIS __list_const_iterator {
410  typedef __list_node_pointer_traits<_Tp, _VoidPtr> _NodeTraits;
411  typedef typename _NodeTraits::__link_pointer __link_pointer;
412
413  __link_pointer __ptr_;
414
415  _LIBCPP_HIDE_FROM_ABI explicit __list_const_iterator(__link_pointer __p) _NOEXCEPT : __ptr_(__p) {}
416
417  template <class, class>
418  friend class list;
419  template <class, class>
420  friend class __list_imp;
421
422public:
423  typedef bidirectional_iterator_tag iterator_category;
424  typedef _Tp value_type;
425  typedef const value_type& reference;
426  typedef __rebind_pointer_t<_VoidPtr, const value_type> pointer;
427  typedef typename pointer_traits<pointer>::difference_type difference_type;
428
429  _LIBCPP_HIDE_FROM_ABI __list_const_iterator() _NOEXCEPT : __ptr_(nullptr) {}
430  _LIBCPP_HIDE_FROM_ABI __list_const_iterator(const __list_iterator<_Tp, _VoidPtr>& __p) _NOEXCEPT
431      : __ptr_(__p.__ptr_) {}
432
433  _LIBCPP_HIDE_FROM_ABI reference operator*() const { return __ptr_->__as_node()->__get_value(); }
434  _LIBCPP_HIDE_FROM_ABI pointer operator->() const {
435    return pointer_traits<pointer>::pointer_to(__ptr_->__as_node()->__get_value());
436  }
437
438  _LIBCPP_HIDE_FROM_ABI __list_const_iterator& operator++() {
439    __ptr_ = __ptr_->__next_;
440    return *this;
441  }
442  _LIBCPP_HIDE_FROM_ABI __list_const_iterator operator++(int) {
443    __list_const_iterator __t(*this);
444    ++(*this);
445    return __t;
446  }
447
448  _LIBCPP_HIDE_FROM_ABI __list_const_iterator& operator--() {
449    __ptr_ = __ptr_->__prev_;
450    return *this;
451  }
452  _LIBCPP_HIDE_FROM_ABI __list_const_iterator operator--(int) {
453    __list_const_iterator __t(*this);
454    --(*this);
455    return __t;
456  }
457
458  friend _LIBCPP_HIDE_FROM_ABI bool operator==(const __list_const_iterator& __x, const __list_const_iterator& __y) {
459    return __x.__ptr_ == __y.__ptr_;
460  }
461  friend _LIBCPP_HIDE_FROM_ABI bool operator!=(const __list_const_iterator& __x, const __list_const_iterator& __y) {
462    return !(__x == __y);
463  }
464};
465
466template <class _Tp, class _Alloc>
467class __list_imp {
468public:
469  __list_imp(const __list_imp&) = delete;
470  __list_imp& operator=(const __list_imp&) = delete;
471
472  typedef _Alloc allocator_type;
473  typedef allocator_traits<allocator_type> __alloc_traits;
474  typedef typename __alloc_traits::size_type size_type;
475
476protected:
477  typedef _Tp value_type;
478  typedef typename __alloc_traits::void_pointer __void_pointer;
479  typedef __list_iterator<value_type, __void_pointer> iterator;
480  typedef __list_const_iterator<value_type, __void_pointer> const_iterator;
481  typedef __list_node_base<value_type, __void_pointer> __node_base;
482  typedef __list_node<value_type, __void_pointer> __node_type;
483  typedef __rebind_alloc<__alloc_traits, __node_type> __node_allocator;
484  typedef allocator_traits<__node_allocator> __node_alloc_traits;
485  typedef typename __node_alloc_traits::pointer __node_pointer;
486  typedef typename __node_alloc_traits::pointer __node_const_pointer;
487  typedef __list_node_pointer_traits<value_type, __void_pointer> __node_pointer_traits;
488  typedef typename __node_pointer_traits::__link_pointer __link_pointer;
489  typedef __link_pointer __link_const_pointer;
490  typedef typename __alloc_traits::pointer pointer;
491  typedef typename __alloc_traits::const_pointer const_pointer;
492  typedef typename __alloc_traits::difference_type difference_type;
493
494  typedef __rebind_alloc<__alloc_traits, __node_base> __node_base_allocator;
495  typedef typename allocator_traits<__node_base_allocator>::pointer __node_base_pointer;
496  static_assert(!is_same<allocator_type, __node_allocator>::value,
497                "internal allocator type must differ from user-specified type; otherwise overload resolution breaks");
498
499  __node_base __end_;
500  __compressed_pair<size_type, __node_allocator> __size_alloc_;
501
502  _LIBCPP_HIDE_FROM_ABI __link_pointer __end_as_link() const _NOEXCEPT {
503    return __node_pointer_traits::__unsafe_link_pointer_cast(const_cast<__node_base&>(__end_).__self());
504  }
505
506  _LIBCPP_HIDE_FROM_ABI size_type& __sz() _NOEXCEPT { return __size_alloc_.first(); }
507  _LIBCPP_HIDE_FROM_ABI const size_type& __sz() const _NOEXCEPT { return __size_alloc_.first(); }
508  _LIBCPP_HIDE_FROM_ABI __node_allocator& __node_alloc() _NOEXCEPT { return __size_alloc_.second(); }
509  _LIBCPP_HIDE_FROM_ABI const __node_allocator& __node_alloc() const _NOEXCEPT { return __size_alloc_.second(); }
510
511  _LIBCPP_HIDE_FROM_ABI size_type __node_alloc_max_size() const _NOEXCEPT {
512    return __node_alloc_traits::max_size(__node_alloc());
513  }
514  _LIBCPP_HIDE_FROM_ABI static void __unlink_nodes(__link_pointer __f, __link_pointer __l) _NOEXCEPT;
515
516  _LIBCPP_HIDE_FROM_ABI __list_imp() _NOEXCEPT_(is_nothrow_default_constructible<__node_allocator>::value);
517  _LIBCPP_HIDE_FROM_ABI __list_imp(const allocator_type& __a);
518  _LIBCPP_HIDE_FROM_ABI __list_imp(const __node_allocator& __a);
519#ifndef _LIBCPP_CXX03_LANG
520  _LIBCPP_HIDE_FROM_ABI __list_imp(__node_allocator&& __a) _NOEXCEPT;
521#endif
522  _LIBCPP_HIDE_FROM_ABI ~__list_imp();
523  _LIBCPP_HIDE_FROM_ABI void clear() _NOEXCEPT;
524  _LIBCPP_HIDE_FROM_ABI bool empty() const _NOEXCEPT { return __sz() == 0; }
525
526  _LIBCPP_HIDE_FROM_ABI iterator begin() _NOEXCEPT { return iterator(__end_.__next_); }
527  _LIBCPP_HIDE_FROM_ABI const_iterator begin() const _NOEXCEPT { return const_iterator(__end_.__next_); }
528  _LIBCPP_HIDE_FROM_ABI iterator end() _NOEXCEPT { return iterator(__end_as_link()); }
529  _LIBCPP_HIDE_FROM_ABI const_iterator end() const _NOEXCEPT { return const_iterator(__end_as_link()); }
530
531  _LIBCPP_HIDE_FROM_ABI void swap(__list_imp& __c)
532#if _LIBCPP_STD_VER >= 14
533      _NOEXCEPT;
534#else
535      _NOEXCEPT_(!__alloc_traits::propagate_on_container_swap::value || __is_nothrow_swappable_v<allocator_type>);
536#endif
537
538  _LIBCPP_HIDE_FROM_ABI void __copy_assign_alloc(const __list_imp& __c) {
539    __copy_assign_alloc(
540        __c, integral_constant<bool, __node_alloc_traits::propagate_on_container_copy_assignment::value>());
541  }
542
543  _LIBCPP_HIDE_FROM_ABI void __move_assign_alloc(__list_imp& __c)
544      _NOEXCEPT_(!__node_alloc_traits::propagate_on_container_move_assignment::value ||
545                 is_nothrow_move_assignable<__node_allocator>::value) {
546    __move_assign_alloc(
547        __c, integral_constant<bool, __node_alloc_traits::propagate_on_container_move_assignment::value>());
548  }
549
550  template <class... _Args>
551  _LIBCPP_HIDE_FROM_ABI __node_pointer __create_node(__link_pointer __prev, __link_pointer __next, _Args&&... __args) {
552    __node_allocator& __alloc = __node_alloc();
553    __allocation_guard<__node_allocator> __guard(__alloc, 1);
554    // Begin the lifetime of the node itself. Note that this doesn't begin the lifetime of the value
555    // held inside the node, since we need to use the allocator's construct() method for that.
556    //
557    // We don't use the allocator's construct() method to construct the node itself since the
558    // Cpp17FooInsertable named requirements don't require the allocator's construct() method
559    // to work on anything other than the value_type.
560    std::__construct_at(std::addressof(*__guard.__get()), __prev, __next);
561
562    // Now construct the value_type using the allocator's construct() method.
563    __node_alloc_traits::construct(
564        __alloc, std::addressof(__guard.__get()->__get_value()), std::forward<_Args>(__args)...);
565    return __guard.__release_ptr();
566  }
567
568  _LIBCPP_HIDE_FROM_ABI void __delete_node(__node_pointer __node) {
569    // For the same reason as above, we use the allocator's destroy() method for the value_type,
570    // but not for the node itself.
571    __node_allocator& __alloc = __node_alloc();
572    __node_alloc_traits::destroy(__alloc, std::addressof(__node->__get_value()));
573    std::__destroy_at(std::addressof(*__node));
574    __node_alloc_traits::deallocate(__alloc, __node, 1);
575  }
576
577private:
578  _LIBCPP_HIDE_FROM_ABI void __copy_assign_alloc(const __list_imp& __c, true_type) {
579    if (__node_alloc() != __c.__node_alloc())
580      clear();
581    __node_alloc() = __c.__node_alloc();
582  }
583
584  _LIBCPP_HIDE_FROM_ABI void __copy_assign_alloc(const __list_imp&, false_type) {}
585
586  _LIBCPP_HIDE_FROM_ABI void __move_assign_alloc(__list_imp& __c, true_type)
587      _NOEXCEPT_(is_nothrow_move_assignable<__node_allocator>::value) {
588    __node_alloc() = std::move(__c.__node_alloc());
589  }
590
591  _LIBCPP_HIDE_FROM_ABI void __move_assign_alloc(__list_imp&, false_type) _NOEXCEPT {}
592};
593
594// Unlink nodes [__f, __l]
595template <class _Tp, class _Alloc>
596inline void __list_imp<_Tp, _Alloc>::__unlink_nodes(__link_pointer __f, __link_pointer __l) _NOEXCEPT {
597  __f->__prev_->__next_ = __l->__next_;
598  __l->__next_->__prev_ = __f->__prev_;
599}
600
601template <class _Tp, class _Alloc>
602inline __list_imp<_Tp, _Alloc>::__list_imp() _NOEXCEPT_(is_nothrow_default_constructible<__node_allocator>::value)
603    : __size_alloc_(0, __default_init_tag()) {}
604
605template <class _Tp, class _Alloc>
606inline __list_imp<_Tp, _Alloc>::__list_imp(const allocator_type& __a) : __size_alloc_(0, __node_allocator(__a)) {}
607
608template <class _Tp, class _Alloc>
609inline __list_imp<_Tp, _Alloc>::__list_imp(const __node_allocator& __a) : __size_alloc_(0, __a) {}
610
611#ifndef _LIBCPP_CXX03_LANG
612template <class _Tp, class _Alloc>
613inline __list_imp<_Tp, _Alloc>::__list_imp(__node_allocator&& __a) _NOEXCEPT : __size_alloc_(0, std::move(__a)) {}
614#endif
615
616template <class _Tp, class _Alloc>
617__list_imp<_Tp, _Alloc>::~__list_imp() {
618  clear();
619}
620
621template <class _Tp, class _Alloc>
622void __list_imp<_Tp, _Alloc>::clear() _NOEXCEPT {
623  if (!empty()) {
624    __link_pointer __f = __end_.__next_;
625    __link_pointer __l = __end_as_link();
626    __unlink_nodes(__f, __l->__prev_);
627    __sz() = 0;
628    while (__f != __l) {
629      __node_pointer __np = __f->__as_node();
630      __f                 = __f->__next_;
631      __delete_node(__np);
632    }
633  }
634}
635
636template <class _Tp, class _Alloc>
637void __list_imp<_Tp, _Alloc>::swap(__list_imp& __c)
638#if _LIBCPP_STD_VER >= 14
639    _NOEXCEPT
640#else
641    _NOEXCEPT_(!__alloc_traits::propagate_on_container_swap::value || __is_nothrow_swappable_v<allocator_type>)
642#endif
643{
644  _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR(
645      __alloc_traits::propagate_on_container_swap::value || this->__node_alloc() == __c.__node_alloc(),
646      "list::swap: Either propagate_on_container_swap must be true"
647      " or the allocators must compare equal");
648  using std::swap;
649  std::__swap_allocator(__node_alloc(), __c.__node_alloc());
650  swap(__sz(), __c.__sz());
651  swap(__end_, __c.__end_);
652  if (__sz() == 0)
653    __end_.__next_ = __end_.__prev_ = __end_as_link();
654  else
655    __end_.__prev_->__next_ = __end_.__next_->__prev_ = __end_as_link();
656  if (__c.__sz() == 0)
657    __c.__end_.__next_ = __c.__end_.__prev_ = __c.__end_as_link();
658  else
659    __c.__end_.__prev_->__next_ = __c.__end_.__next_->__prev_ = __c.__end_as_link();
660}
661
662template <class _Tp, class _Alloc /*= allocator<_Tp>*/>
663class _LIBCPP_TEMPLATE_VIS list : private __list_imp<_Tp, _Alloc> {
664  typedef __list_imp<_Tp, _Alloc> base;
665  typedef typename base::__node_type __node_type;
666  typedef typename base::__node_allocator __node_allocator;
667  typedef typename base::__node_pointer __node_pointer;
668  typedef typename base::__node_alloc_traits __node_alloc_traits;
669  typedef typename base::__node_base __node_base;
670  typedef typename base::__node_base_pointer __node_base_pointer;
671  typedef typename base::__link_pointer __link_pointer;
672
673public:
674  typedef _Tp value_type;
675  typedef _Alloc allocator_type;
676  static_assert(__check_valid_allocator<allocator_type>::value);
677  static_assert(is_same<value_type, typename allocator_type::value_type>::value,
678                "Allocator::value_type must be same type as value_type");
679  typedef value_type& reference;
680  typedef const value_type& const_reference;
681  typedef typename base::pointer pointer;
682  typedef typename base::const_pointer const_pointer;
683  typedef typename base::size_type size_type;
684  typedef typename base::difference_type difference_type;
685  typedef typename base::iterator iterator;
686  typedef typename base::const_iterator const_iterator;
687  typedef std::reverse_iterator<iterator> reverse_iterator;
688  typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
689#if _LIBCPP_STD_VER >= 20
690  typedef size_type __remove_return_type;
691#else
692  typedef void __remove_return_type;
693#endif
694
695  _LIBCPP_HIDE_FROM_ABI list() _NOEXCEPT_(is_nothrow_default_constructible<__node_allocator>::value) {}
696  _LIBCPP_HIDE_FROM_ABI explicit list(const allocator_type& __a) : base(__a) {}
697  _LIBCPP_HIDE_FROM_ABI explicit list(size_type __n);
698#if _LIBCPP_STD_VER >= 14
699  _LIBCPP_HIDE_FROM_ABI explicit list(size_type __n, const allocator_type& __a);
700#endif
701  _LIBCPP_HIDE_FROM_ABI list(size_type __n, const value_type& __x);
702  template <__enable_if_t<__is_allocator<_Alloc>::value, int> = 0>
703  _LIBCPP_HIDE_FROM_ABI list(size_type __n, const value_type& __x, const allocator_type& __a) : base(__a) {
704    for (; __n > 0; --__n)
705      push_back(__x);
706  }
707
708  template <class _InpIter, __enable_if_t<__has_input_iterator_category<_InpIter>::value, int> = 0>
709  _LIBCPP_HIDE_FROM_ABI list(_InpIter __f, _InpIter __l);
710
711  template <class _InpIter, __enable_if_t<__has_input_iterator_category<_InpIter>::value, int> = 0>
712  _LIBCPP_HIDE_FROM_ABI list(_InpIter __f, _InpIter __l, const allocator_type& __a);
713
714#if _LIBCPP_STD_VER >= 23
715  template <_ContainerCompatibleRange<_Tp> _Range>
716  _LIBCPP_HIDE_FROM_ABI list(from_range_t, _Range&& __range, const allocator_type& __a = allocator_type()) : base(__a) {
717    prepend_range(std::forward<_Range>(__range));
718  }
719#endif
720
721  _LIBCPP_HIDE_FROM_ABI list(const list& __c);
722  _LIBCPP_HIDE_FROM_ABI list(const list& __c, const __type_identity_t<allocator_type>& __a);
723  _LIBCPP_HIDE_FROM_ABI list& operator=(const list& __c);
724#ifndef _LIBCPP_CXX03_LANG
725  _LIBCPP_HIDE_FROM_ABI list(initializer_list<value_type> __il);
726  _LIBCPP_HIDE_FROM_ABI list(initializer_list<value_type> __il, const allocator_type& __a);
727
728  _LIBCPP_HIDE_FROM_ABI list(list&& __c) _NOEXCEPT_(is_nothrow_move_constructible<__node_allocator>::value);
729  _LIBCPP_HIDE_FROM_ABI list(list&& __c, const __type_identity_t<allocator_type>& __a);
730  _LIBCPP_HIDE_FROM_ABI list& operator=(list&& __c)
731      _NOEXCEPT_(__node_alloc_traits::propagate_on_container_move_assignment::value&&
732                     is_nothrow_move_assignable<__node_allocator>::value);
733
734  _LIBCPP_HIDE_FROM_ABI list& operator=(initializer_list<value_type> __il) {
735    assign(__il.begin(), __il.end());
736    return *this;
737  }
738
739  _LIBCPP_HIDE_FROM_ABI void assign(initializer_list<value_type> __il) { assign(__il.begin(), __il.end()); }
740#endif // _LIBCPP_CXX03_LANG
741
742  template <class _InpIter, __enable_if_t<__has_input_iterator_category<_InpIter>::value, int> = 0>
743  _LIBCPP_HIDE_FROM_ABI void assign(_InpIter __f, _InpIter __l);
744
745#if _LIBCPP_STD_VER >= 23
746  template <_ContainerCompatibleRange<_Tp> _Range>
747  _LIBCPP_HIDE_FROM_ABI void assign_range(_Range&& __range) {
748    __assign_with_sentinel(ranges::begin(__range), ranges::end(__range));
749  }
750#endif
751
752  _LIBCPP_HIDE_FROM_ABI void assign(size_type __n, const value_type& __x);
753
754  _LIBCPP_HIDE_FROM_ABI allocator_type get_allocator() const _NOEXCEPT;
755
756  _LIBCPP_HIDE_FROM_ABI size_type size() const _NOEXCEPT { return base::__sz(); }
757  _LIBCPP_NODISCARD _LIBCPP_HIDE_FROM_ABI bool empty() const _NOEXCEPT { return base::empty(); }
758  _LIBCPP_HIDE_FROM_ABI size_type max_size() const _NOEXCEPT {
759    return std::min<size_type>(base::__node_alloc_max_size(), numeric_limits<difference_type >::max());
760  }
761
762  _LIBCPP_HIDE_FROM_ABI iterator begin() _NOEXCEPT { return base::begin(); }
763  _LIBCPP_HIDE_FROM_ABI const_iterator begin() const _NOEXCEPT { return base::begin(); }
764  _LIBCPP_HIDE_FROM_ABI iterator end() _NOEXCEPT { return base::end(); }
765  _LIBCPP_HIDE_FROM_ABI const_iterator end() const _NOEXCEPT { return base::end(); }
766  _LIBCPP_HIDE_FROM_ABI const_iterator cbegin() const _NOEXCEPT { return base::begin(); }
767  _LIBCPP_HIDE_FROM_ABI const_iterator cend() const _NOEXCEPT { return base::end(); }
768
769  _LIBCPP_HIDE_FROM_ABI reverse_iterator rbegin() _NOEXCEPT { return reverse_iterator(end()); }
770  _LIBCPP_HIDE_FROM_ABI const_reverse_iterator rbegin() const _NOEXCEPT { return const_reverse_iterator(end()); }
771  _LIBCPP_HIDE_FROM_ABI reverse_iterator rend() _NOEXCEPT { return reverse_iterator(begin()); }
772  _LIBCPP_HIDE_FROM_ABI const_reverse_iterator rend() const _NOEXCEPT { return const_reverse_iterator(begin()); }
773  _LIBCPP_HIDE_FROM_ABI const_reverse_iterator crbegin() const _NOEXCEPT { return const_reverse_iterator(end()); }
774  _LIBCPP_HIDE_FROM_ABI const_reverse_iterator crend() const _NOEXCEPT { return const_reverse_iterator(begin()); }
775
776  _LIBCPP_HIDE_FROM_ABI reference front() {
777    _LIBCPP_ASSERT_VALID_ELEMENT_ACCESS(!empty(), "list::front called on empty list");
778    return base::__end_.__next_->__as_node()->__get_value();
779  }
780  _LIBCPP_HIDE_FROM_ABI const_reference front() const {
781    _LIBCPP_ASSERT_VALID_ELEMENT_ACCESS(!empty(), "list::front called on empty list");
782    return base::__end_.__next_->__as_node()->__get_value();
783  }
784  _LIBCPP_HIDE_FROM_ABI reference back() {
785    _LIBCPP_ASSERT_VALID_ELEMENT_ACCESS(!empty(), "list::back called on empty list");
786    return base::__end_.__prev_->__as_node()->__get_value();
787  }
788  _LIBCPP_HIDE_FROM_ABI const_reference back() const {
789    _LIBCPP_ASSERT_VALID_ELEMENT_ACCESS(!empty(), "list::back called on empty list");
790    return base::__end_.__prev_->__as_node()->__get_value();
791  }
792
793#ifndef _LIBCPP_CXX03_LANG
794  _LIBCPP_HIDE_FROM_ABI void push_front(value_type&& __x);
795  _LIBCPP_HIDE_FROM_ABI void push_back(value_type&& __x);
796
797#  if _LIBCPP_STD_VER >= 23
798  template <_ContainerCompatibleRange<_Tp> _Range>
799  _LIBCPP_HIDE_FROM_ABI void prepend_range(_Range&& __range) {
800    insert_range(begin(), std::forward<_Range>(__range));
801  }
802
803  template <_ContainerCompatibleRange<_Tp> _Range>
804  _LIBCPP_HIDE_FROM_ABI void append_range(_Range&& __range) {
805    insert_range(end(), std::forward<_Range>(__range));
806  }
807#  endif
808
809  template <class... _Args>
810#  if _LIBCPP_STD_VER >= 17
811  _LIBCPP_HIDE_FROM_ABI reference emplace_front(_Args&&... __args);
812#  else
813  _LIBCPP_HIDE_FROM_ABI void emplace_front(_Args&&... __args);
814#  endif
815  template <class... _Args>
816#  if _LIBCPP_STD_VER >= 17
817  _LIBCPP_HIDE_FROM_ABI reference emplace_back(_Args&&... __args);
818#  else
819  _LIBCPP_HIDE_FROM_ABI void emplace_back(_Args&&... __args);
820#  endif
821  template <class... _Args>
822  _LIBCPP_HIDE_FROM_ABI iterator emplace(const_iterator __p, _Args&&... __args);
823
824  _LIBCPP_HIDE_FROM_ABI iterator insert(const_iterator __p, value_type&& __x);
825
826  _LIBCPP_HIDE_FROM_ABI iterator insert(const_iterator __p, initializer_list<value_type> __il) {
827    return insert(__p, __il.begin(), __il.end());
828  }
829#endif // _LIBCPP_CXX03_LANG
830
831  _LIBCPP_HIDE_FROM_ABI void push_front(const value_type& __x);
832  _LIBCPP_HIDE_FROM_ABI void push_back(const value_type& __x);
833
834#ifndef _LIBCPP_CXX03_LANG
835  template <class _Arg>
836  _LIBCPP_HIDE_FROM_ABI void __emplace_back(_Arg&& __arg) {
837    emplace_back(std::forward<_Arg>(__arg));
838  }
839#else
840  _LIBCPP_HIDE_FROM_ABI void __emplace_back(value_type const& __arg) { push_back(__arg); }
841#endif
842
843  _LIBCPP_HIDE_FROM_ABI iterator insert(const_iterator __p, const value_type& __x);
844  _LIBCPP_HIDE_FROM_ABI iterator insert(const_iterator __p, size_type __n, const value_type& __x);
845
846  template <class _InpIter, __enable_if_t<__has_input_iterator_category<_InpIter>::value, int> = 0>
847  _LIBCPP_HIDE_FROM_ABI iterator insert(const_iterator __p, _InpIter __f, _InpIter __l);
848
849#if _LIBCPP_STD_VER >= 23
850  template <_ContainerCompatibleRange<_Tp> _Range>
851  _LIBCPP_HIDE_FROM_ABI iterator insert_range(const_iterator __position, _Range&& __range) {
852    return __insert_with_sentinel(__position, ranges::begin(__range), ranges::end(__range));
853  }
854#endif
855
856  _LIBCPP_HIDE_FROM_ABI void swap(list& __c)
857#if _LIBCPP_STD_VER >= 14
858      _NOEXCEPT
859#else
860      _NOEXCEPT_(!__node_alloc_traits::propagate_on_container_swap::value || __is_nothrow_swappable_v<__node_allocator>)
861#endif
862  {
863    base::swap(__c);
864  }
865  _LIBCPP_HIDE_FROM_ABI void clear() _NOEXCEPT { base::clear(); }
866
867  _LIBCPP_HIDE_FROM_ABI void pop_front();
868  _LIBCPP_HIDE_FROM_ABI void pop_back();
869
870  _LIBCPP_HIDE_FROM_ABI iterator erase(const_iterator __p);
871  _LIBCPP_HIDE_FROM_ABI iterator erase(const_iterator __f, const_iterator __l);
872
873  _LIBCPP_HIDE_FROM_ABI void resize(size_type __n);
874  _LIBCPP_HIDE_FROM_ABI void resize(size_type __n, const value_type& __x);
875
876  _LIBCPP_HIDE_FROM_ABI void splice(const_iterator __p, list& __c);
877#ifndef _LIBCPP_CXX03_LANG
878  _LIBCPP_HIDE_FROM_ABI void splice(const_iterator __p, list&& __c) { splice(__p, __c); }
879  _LIBCPP_HIDE_FROM_ABI void splice(const_iterator __p, list&& __c, const_iterator __i) { splice(__p, __c, __i); }
880  _LIBCPP_HIDE_FROM_ABI void splice(const_iterator __p, list&& __c, const_iterator __f, const_iterator __l) {
881    splice(__p, __c, __f, __l);
882  }
883#endif
884  _LIBCPP_HIDE_FROM_ABI void splice(const_iterator __p, list& __c, const_iterator __i);
885  _LIBCPP_HIDE_FROM_ABI void splice(const_iterator __p, list& __c, const_iterator __f, const_iterator __l);
886
887  _LIBCPP_HIDE_FROM_ABI __remove_return_type remove(const value_type& __x);
888  template <class _Pred>
889  _LIBCPP_HIDE_FROM_ABI __remove_return_type remove_if(_Pred __pred);
890  _LIBCPP_HIDE_FROM_ABI __remove_return_type unique() { return unique(__equal_to()); }
891  template <class _BinaryPred>
892  _LIBCPP_HIDE_FROM_ABI __remove_return_type unique(_BinaryPred __binary_pred);
893  _LIBCPP_HIDE_FROM_ABI void merge(list& __c);
894#ifndef _LIBCPP_CXX03_LANG
895  _LIBCPP_HIDE_FROM_ABI void merge(list&& __c) { merge(__c); }
896
897  template <class _Comp>
898  _LIBCPP_HIDE_FROM_ABI void merge(list&& __c, _Comp __comp) {
899    merge(__c, __comp);
900  }
901#endif
902  template <class _Comp>
903  _LIBCPP_HIDE_FROM_ABI void merge(list& __c, _Comp __comp);
904
905  _LIBCPP_HIDE_FROM_ABI void sort();
906  template <class _Comp>
907  _LIBCPP_HIDE_FROM_ABI void sort(_Comp __comp);
908
909  _LIBCPP_HIDE_FROM_ABI void reverse() _NOEXCEPT;
910
911  _LIBCPP_HIDE_FROM_ABI bool __invariants() const;
912
913private:
914  template <class _Iterator, class _Sentinel>
915  _LIBCPP_HIDE_FROM_ABI void __assign_with_sentinel(_Iterator __f, _Sentinel __l);
916
917  template <class _Iterator, class _Sentinel>
918  _LIBCPP_HIDE_FROM_ABI iterator __insert_with_sentinel(const_iterator __p, _Iterator __f, _Sentinel __l);
919
920  _LIBCPP_HIDE_FROM_ABI static void __link_nodes(__link_pointer __p, __link_pointer __f, __link_pointer __l);
921  _LIBCPP_HIDE_FROM_ABI void __link_nodes_at_front(__link_pointer __f, __link_pointer __l);
922  _LIBCPP_HIDE_FROM_ABI void __link_nodes_at_back(__link_pointer __f, __link_pointer __l);
923  _LIBCPP_HIDE_FROM_ABI iterator __iterator(size_type __n);
924  // TODO: Make this _LIBCPP_HIDE_FROM_ABI
925  template <class _Comp>
926  _LIBCPP_HIDDEN static iterator __sort(iterator __f1, iterator __e2, size_type __n, _Comp& __comp);
927
928  _LIBCPP_HIDE_FROM_ABI void __move_assign(list& __c, true_type)
929      _NOEXCEPT_(is_nothrow_move_assignable<__node_allocator>::value);
930  _LIBCPP_HIDE_FROM_ABI void __move_assign(list& __c, false_type);
931};
932
933#if _LIBCPP_STD_VER >= 17
934template <class _InputIterator,
935          class _Alloc = allocator<__iter_value_type<_InputIterator>>,
936          class        = enable_if_t<__has_input_iterator_category<_InputIterator>::value>,
937          class        = enable_if_t<__is_allocator<_Alloc>::value> >
938list(_InputIterator, _InputIterator) -> list<__iter_value_type<_InputIterator>, _Alloc>;
939
940template <class _InputIterator,
941          class _Alloc,
942          class = enable_if_t<__has_input_iterator_category<_InputIterator>::value>,
943          class = enable_if_t<__is_allocator<_Alloc>::value> >
944list(_InputIterator, _InputIterator, _Alloc) -> list<__iter_value_type<_InputIterator>, _Alloc>;
945#endif
946
947#if _LIBCPP_STD_VER >= 23
948template <ranges::input_range _Range,
949          class _Alloc = allocator<ranges::range_value_t<_Range>>,
950          class        = enable_if_t<__is_allocator<_Alloc>::value> >
951list(from_range_t, _Range&&, _Alloc = _Alloc()) -> list<ranges::range_value_t<_Range>, _Alloc>;
952#endif
953
954// Link in nodes [__f, __l] just prior to __p
955template <class _Tp, class _Alloc>
956inline void list<_Tp, _Alloc>::__link_nodes(__link_pointer __p, __link_pointer __f, __link_pointer __l) {
957  __p->__prev_->__next_ = __f;
958  __f->__prev_          = __p->__prev_;
959  __p->__prev_          = __l;
960  __l->__next_          = __p;
961}
962
963// Link in nodes [__f, __l] at the front of the list
964template <class _Tp, class _Alloc>
965inline void list<_Tp, _Alloc>::__link_nodes_at_front(__link_pointer __f, __link_pointer __l) {
966  __f->__prev_          = base::__end_as_link();
967  __l->__next_          = base::__end_.__next_;
968  __l->__next_->__prev_ = __l;
969  base::__end_.__next_  = __f;
970}
971
972// Link in nodes [__f, __l] at the back of the list
973template <class _Tp, class _Alloc>
974inline void list<_Tp, _Alloc>::__link_nodes_at_back(__link_pointer __f, __link_pointer __l) {
975  __l->__next_          = base::__end_as_link();
976  __f->__prev_          = base::__end_.__prev_;
977  __f->__prev_->__next_ = __f;
978  base::__end_.__prev_  = __l;
979}
980
981template <class _Tp, class _Alloc>
982inline typename list<_Tp, _Alloc>::iterator list<_Tp, _Alloc>::__iterator(size_type __n) {
983  return __n <= base::__sz() / 2 ? std::next(begin(), __n) : std::prev(end(), base::__sz() - __n);
984}
985
986template <class _Tp, class _Alloc>
987list<_Tp, _Alloc>::list(size_type __n) {
988  for (; __n > 0; --__n)
989#ifndef _LIBCPP_CXX03_LANG
990    emplace_back();
991#else
992    push_back(value_type());
993#endif
994}
995
996#if _LIBCPP_STD_VER >= 14
997template <class _Tp, class _Alloc>
998list<_Tp, _Alloc>::list(size_type __n, const allocator_type& __a) : base(__a) {
999  for (; __n > 0; --__n)
1000    emplace_back();
1001}
1002#endif
1003
1004template <class _Tp, class _Alloc>
1005list<_Tp, _Alloc>::list(size_type __n, const value_type& __x) {
1006  for (; __n > 0; --__n)
1007    push_back(__x);
1008}
1009
1010template <class _Tp, class _Alloc>
1011template <class _InpIter, __enable_if_t<__has_input_iterator_category<_InpIter>::value, int> >
1012list<_Tp, _Alloc>::list(_InpIter __f, _InpIter __l) {
1013  for (; __f != __l; ++__f)
1014    __emplace_back(*__f);
1015}
1016
1017template <class _Tp, class _Alloc>
1018template <class _InpIter, __enable_if_t<__has_input_iterator_category<_InpIter>::value, int> >
1019list<_Tp, _Alloc>::list(_InpIter __f, _InpIter __l, const allocator_type& __a) : base(__a) {
1020  for (; __f != __l; ++__f)
1021    __emplace_back(*__f);
1022}
1023
1024template <class _Tp, class _Alloc>
1025list<_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
1031template <class _Tp, class _Alloc>
1032list<_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
1039template <class _Tp, class _Alloc>
1040list<_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
1045template <class _Tp, class _Alloc>
1046list<_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
1051template <class _Tp, class _Alloc>
1052inline 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
1057template <class _Tp, class _Alloc>
1058inline 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
1067template <class _Tp, class _Alloc>
1068inline 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
1075template <class _Tp, class _Alloc>
1076void 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
1084template <class _Tp, class _Alloc>
1085void 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
1094template <class _Tp, class _Alloc>
1095inline 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
1103template <class _Tp, class _Alloc>
1104template <class _InpIter, __enable_if_t<__has_input_iterator_category<_InpIter>::value, int> >
1105void list<_Tp, _Alloc>::assign(_InpIter __f, _InpIter __l) {
1106  __assign_with_sentinel(__f, __l);
1107}
1108
1109template <class _Tp, class _Alloc>
1110template <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
1122template <class _Tp, class _Alloc>
1123void 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
1134template <class _Tp, class _Alloc>
1135inline _Alloc list<_Tp, _Alloc>::get_allocator() const _NOEXCEPT {
1136  return allocator_type(base::__node_alloc());
1137}
1138
1139template <class _Tp, class _Alloc>
1140typename 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
1147template <class _Tp, class _Alloc>
1148typename list<_Tp, _Alloc>::iterator
1149list<_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
1182template <class _Tp, class _Alloc>
1183template <class _InpIter, __enable_if_t<__has_input_iterator_category<_InpIter>::value, int> >
1184typename 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
1188template <class _Tp, class _Alloc>
1189template <class _Iterator, class _Sentinel>
1190_LIBCPP_HIDE_FROM_ABI typename list<_Tp, _Alloc>::iterator
1191list<_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
1224template <class _Tp, class _Alloc>
1225void 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
1232template <class _Tp, class _Alloc>
1233void 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
1242template <class _Tp, class _Alloc>
1243void 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
1250template <class _Tp, class _Alloc>
1251void 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
1258template <class _Tp, class _Alloc>
1259template <class... _Args>
1260#  if _LIBCPP_STD_VER >= 17
1261typename list<_Tp, _Alloc>::reference
1262#  else
1263void
1264#  endif
1265list<_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
1276template <class _Tp, class _Alloc>
1277template <class... _Args>
1278#  if _LIBCPP_STD_VER >= 17
1279typename list<_Tp, _Alloc>::reference
1280#  else
1281void
1282#  endif
1283list<_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
1294template <class _Tp, class _Alloc>
1295template <class... _Args>
1296typename 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
1305template <class _Tp, class _Alloc>
1306typename 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
1316template <class _Tp, class _Alloc>
1317void 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
1325template <class _Tp, class _Alloc>
1326void 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
1334template <class _Tp, class _Alloc>
1335typename 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
1345template <class _Tp, class _Alloc>
1346typename 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
1359template <class _Tp, class _Alloc>
1360void 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
1394template <class _Tp, class _Alloc>
1395void 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
1430template <class _Tp, class _Alloc>
1431void 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
1444template <class _Tp, class _Alloc>
1445void 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
1455template <class _Tp, class _Alloc>
1456void 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
1471template <class _Tp, class _Alloc>
1472typename 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
1490template <class _Tp, class _Alloc>
1491template <class _Pred>
1492typename 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
1510template <class _Tp, class _Alloc>
1511template <class _BinaryPred>
1512typename 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
1527template <class _Tp, class _Alloc>
1528inline void list<_Tp, _Alloc>::merge(list& __c) {
1529  merge(__c, __less<>());
1530}
1531
1532template <class _Tp, class _Alloc>
1533template <class _Comp>
1534void 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
1562template <class _Tp, class _Alloc>
1563inline void list<_Tp, _Alloc>::sort() {
1564  sort(__less<>());
1565}
1566
1567template <class _Tp, class _Alloc>
1568template <class _Comp>
1569inline void list<_Tp, _Alloc>::sort(_Comp __comp) {
1570  __sort(begin(), end(), base::__sz(), __comp);
1571}
1572
1573template <class _Tp, class _Alloc>
1574template <class _Comp>
1575typename list<_Tp, _Alloc>::iterator
1576list<_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
1628template <class _Tp, class _Alloc>
1629void 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
1640template <class _Tp, class _Alloc>
1641bool list<_Tp, _Alloc>::__invariants() const {
1642  return size() == std::distance(begin(), end());
1643}
1644
1645template <class _Tp, class _Alloc>
1646inline _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
1652template <class _Tp, class _Alloc>
1653inline _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
1657template <class _Tp, class _Alloc>
1658inline _LIBCPP_HIDE_FROM_ABI bool operator!=(const list<_Tp, _Alloc>& __x, const list<_Tp, _Alloc>& __y) {
1659  return !(__x == __y);
1660}
1661
1662template <class _Tp, class _Alloc>
1663inline _LIBCPP_HIDE_FROM_ABI bool operator>(const list<_Tp, _Alloc>& __x, const list<_Tp, _Alloc>& __y) {
1664  return __y < __x;
1665}
1666
1667template <class _Tp, class _Alloc>
1668inline _LIBCPP_HIDE_FROM_ABI bool operator>=(const list<_Tp, _Alloc>& __x, const list<_Tp, _Alloc>& __y) {
1669  return !(__x < __y);
1670}
1671
1672template <class _Tp, class _Alloc>
1673inline _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
1679template <class _Tp, class _Allocator>
1680_LIBCPP_HIDE_FROM_ABI __synth_three_way_result<_Tp>
1681operator<=>(const list<_Tp, _Allocator>& __x, const list<_Tp, _Allocator>& __y) {
1682  return std::lexicographical_compare_three_way(
1683      __x.begin(), __x.end(), __y.begin(), __y.end(), std::__synth_three_way);
1684}
1685
1686#endif // _LIBCPP_STD_VER <= 17
1687
1688template <class _Tp, class _Alloc>
1689inline _LIBCPP_HIDE_FROM_ABI void swap(list<_Tp, _Alloc>& __x, list<_Tp, _Alloc>& __y)
1690    _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y))) {
1691  __x.swap(__y);
1692}
1693
1694#if _LIBCPP_STD_VER >= 20
1695template <class _Tp, class _Allocator, class _Predicate>
1696inline _LIBCPP_HIDE_FROM_ABI typename list<_Tp, _Allocator>::size_type
1697erase_if(list<_Tp, _Allocator>& __c, _Predicate __pred) {
1698  return __c.remove_if(__pred);
1699}
1700
1701template <class _Tp, class _Allocator, class _Up>
1702inline _LIBCPP_HIDE_FROM_ABI typename list<_Tp, _Allocator>::size_type
1703erase(list<_Tp, _Allocator>& __c, const _Up& __v) {
1704  return std::erase_if(__c, [&](auto& __elem) { return __elem == __v; });
1705}
1706
1707template <>
1708inline constexpr bool __format::__enable_insertable<std::list<char>> = true;
1709#  ifndef _LIBCPP_HAS_NO_WIDE_CHARACTERS
1710template <>
1711inline constexpr bool __format::__enable_insertable<std::list<wchar_t>> = true;
1712#  endif
1713
1714#endif // _LIBCPP_STD_VER >= 20
1715
1716_LIBCPP_END_NAMESPACE_STD
1717
1718#if _LIBCPP_STD_VER >= 17
1719_LIBCPP_BEGIN_NAMESPACE_STD
1720namespace pmr {
1721template <class _ValueT>
1722using list _LIBCPP_AVAILABILITY_PMR = std::list<_ValueT, polymorphic_allocator<_ValueT>>;
1723} // namespace pmr
1724_LIBCPP_END_NAMESPACE_STD
1725#endif
1726
1727_LIBCPP_POP_MACROS
1728
1729#if !defined(_LIBCPP_REMOVE_TRANSITIVE_INCLUDES) && _LIBCPP_STD_VER <= 20
1730#  include <algorithm>
1731#  include <atomic>
1732#  include <concepts>
1733#  include <cstdint>
1734#  include <cstdlib>
1735#  include <functional>
1736#  include <iosfwd>
1737#  include <iterator>
1738#  include <stdexcept>
1739#  include <type_traits>
1740#  include <typeinfo>
1741#endif
1742
1743#endif // _LIBCPP_LIST
1744