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