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