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