1834 lines · plain
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-exception7//8//===----------------------------------------------------------------------===//9 10#ifndef _LIBCPP_LIST11#define _LIBCPP_LIST12 13/*14 list synopsis15 16namespace std17{18 19template <class T, class Alloc = allocator<T> >20class list21{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++1443 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++2351 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++2371 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++17100 void pop_front();101 template <class... Args>102 reference emplace_back(Args&&... args); // reference in C++17103 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++23108 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++23112 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++23121 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++17131 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++20143 template <class Pred>144 size_type remove_if(Pred pred); // void before C++20145 size_type unique(); // void before C++20146 template <class BinaryPredicate>147 size_type unique(BinaryPredicate binary_pred); // void before C++20148 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++17164 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++23168 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++20173template <class T, class Alloc>174 bool operator!=(const list<T,Alloc>& x, const list<T,Alloc>& y); // removed in C++20175template <class T, class Alloc>176 bool operator> (const list<T,Alloc>& x, const list<T,Alloc>& y); // removed in C++20177template <class T, class Alloc>178 bool operator>=(const list<T,Alloc>& x, const list<T,Alloc>& y); // removed in C++20179template <class T, class Alloc>180 bool operator<=(const list<T,Alloc>& x, const list<T,Alloc>& y); // removed in C++20181template<class T, class Allocator>182 synth-three-way-result<T> operator<=>(const list<T, Allocator>& x,183 const list<T, Allocator>& y); // since C++20184 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_type191 erase(list<T, Allocator>& c, const U& value); // since C++20192template <class T, class Allocator, class Predicate>193 typename list<T, Allocator>::size_type194 erase_if(list<T, Allocator>& c, Predicate pred); // since C++20195 196} // std197 198*/199 200#if __cplusplus < 201103L && defined(_LIBCPP_USE_FROZEN_CXX03_HEADERS)201# include <__cxx03/list>202#else203# 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 includes247 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_header261# endif262 263_LIBCPP_PUSH_MACROS264# include <__undef_macros>265 266_LIBCPP_BEGIN_NAMESPACE_STD267 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_CXX26291 _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_LANG309 310private:311 union {312 _Tp __value_;313 };314 315public:316 _LIBCPP_CONSTEXPR_SINCE_CXX26 _LIBCPP_HIDE_FROM_ABI _Tp& __get_value() { return __value_; }317# else318 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# endif325 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) _NOEXCEPT354 : __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 bool400 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 bool404 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) _NOEXCEPT417 : __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_ABI433 __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 bool463 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 bool467 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 void516 __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_LANG523 _LIBCPP_CONSTEXPR_SINCE_CXX26 _LIBCPP_HIDE_FROM_ABI __list_imp(__node_allocator&& __a) _NOEXCEPT;524# endif525 _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 >= 14540 _NOEXCEPT;541# else542 _NOEXCEPT_(!__alloc_traits::propagate_on_container_swap::value || __is_nothrow_swappable_v<allocator_type>);543# endif544 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_pointer559 __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 value562 // 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 the565 // Cpp17FooInsertable named requirements don't require the allocator's construct() method566 // 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 void603__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_LANG622template <class _Tp, class _Alloc>623_LIBCPP_CONSTEXPR_SINCE_CXX26 inline __list_imp<_Tp, _Alloc>::__list_imp(__node_allocator&& __a) _NOEXCEPT624 : __size_(0),625 __node_alloc_(std::move(__a)) {}626# endif627 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 >= 14651 _NOEXCEPT652# else653 _NOEXCEPT_(!__alloc_traits::propagate_on_container_swap::value || __is_nothrow_swappable_v<allocator_type>)654# endif655{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 else667 __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 else671 __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 >= 20702 typedef size_type __remove_return_type;703# else704 typedef void __remove_return_type;705# endif706 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 >= 14712 _LIBCPP_CONSTEXPR_SINCE_CXX26 _LIBCPP_HIDE_FROM_ABI explicit list(size_type __n, const allocator_type& __a);713# endif714 _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_ABI717 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 >= 23730 template <_ContainerCompatibleRange<_Tp> _Range>731 _LIBCPP_CONSTEXPR_SINCE_CXX26 _LIBCPP_HIDE_FROM_ABI732 list(from_range_t, _Range&& __range, const allocator_type& __a = allocator_type())733 : __base(__a) {734 prepend_range(std::forward<_Range>(__range));735 }736# endif737 738 _LIBCPP_CONSTEXPR_SINCE_CXX26 _LIBCPP_HIDE_FROM_ABI list(const list& __c);739 _LIBCPP_CONSTEXPR_SINCE_CXX26 _LIBCPP_HIDE_FROM_ABI740 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_LANG743 _LIBCPP_CONSTEXPR_SINCE_CXX26 _LIBCPP_HIDE_FROM_ABI list(initializer_list<value_type> __il);744 _LIBCPP_CONSTEXPR_SINCE_CXX26 _LIBCPP_HIDE_FROM_ABI745 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_LANG764 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 >= 23769 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# endif774 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_iterator812 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_iterator822 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_LANG847 _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 >= 23851 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# endif861 862 template <class... _Args>863 _LIBCPP_CONSTEXPR_SINCE_CXX26864# if _LIBCPP_STD_VER >= 17865 _LIBCPP_HIDE_FROM_ABI reference866 emplace_front(_Args&&... __args);867# else868 _LIBCPP_HIDE_FROM_ABI void869 emplace_front(_Args&&... __args);870# endif871 template <class... _Args>872 _LIBCPP_CONSTEXPR_SINCE_CXX26873# if _LIBCPP_STD_VER >= 17874 _LIBCPP_HIDE_FROM_ABI reference875 emplace_back(_Args&&... __args);876# else877 _LIBCPP_HIDE_FROM_ABI void878 emplace_back(_Args&&... __args);879# endif880 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 iterator886 insert(const_iterator __p, initializer_list<value_type> __il) {887 return insert(__p, __il.begin(), __il.end());888 }889# endif // _LIBCPP_CXX03_LANG890 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_LANG895 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# else900 _LIBCPP_HIDE_FROM_ABI void __emplace_back(value_type const& __arg) { push_back(__arg); }901# endif902 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 iterator905 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 >= 23911 template <_ContainerCompatibleRange<_Tp> _Range>912 _LIBCPP_CONSTEXPR_SINCE_CXX26 _LIBCPP_HIDE_FROM_ABI iterator913 insert_range(const_iterator __position, _Range&& __range) {914 return __insert_with_sentinel(__position, ranges::begin(__range), ranges::end(__range));915 }916# endif917 918 _LIBCPP_CONSTEXPR_SINCE_CXX26 _LIBCPP_HIDE_FROM_ABI void swap(list& __c)919# if _LIBCPP_STD_VER >= 14920 _NOEXCEPT921# else922 _NOEXCEPT_(!__node_alloc_traits::propagate_on_container_swap::value || __is_nothrow_swappable_v<__node_allocator>)923# endif924 {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_LANG940 _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 void945 splice(const_iterator __p, list&& __c, const_iterator __f, const_iterator __l) {946 splice(__p, __c, __f, __l);947 }948# endif949 _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 void951 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_LANG961 _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# endif968 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 iterator985 __insert_with_sentinel(const_iterator __p, _Iterator __f, _Sentinel __l);986 987 _LIBCPP_CONSTEXPR_SINCE_CXX26 _LIBCPP_HIDE_FROM_ABI static void988 __link_nodes(__base_pointer __p, __base_pointer __f, __base_pointer __l);989 _LIBCPP_CONSTEXPR_SINCE_CXX26 _LIBCPP_HIDE_FROM_ABI void990 __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_ABI994 template <class _Comp>995 _LIBCPP_CONSTEXPR_SINCE_CXX26 _LIBCPP_HIDDEN static iterator996 __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 >= 171004template <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# endif1016 1017# if _LIBCPP_STD_VER >= 231018template <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# endif1023 1024// Link in nodes [__f, __l] just prior to __p1025template <class _Tp, class _Alloc>1026_LIBCPP_CONSTEXPR_SINCE_CXX26 inline void1027list<_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 list1035template <class _Tp, class _Alloc>1036_LIBCPP_CONSTEXPR_SINCE_CXX26 inline void1037list<_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 list1045template <class _Tp, class _Alloc>1046_LIBCPP_CONSTEXPR_SINCE_CXX26 inline void1047list<_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_LANG1063 emplace_back();1064# else1065 push_back(value_type());1066# endif1067}1068 1069# if _LIBCPP_STD_VER >= 141070template <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# endif1076 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_LANG1113 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 } else1160 __move_assign(__c, true_type());1161}1162 1163template <class _Tp, class _Alloc>1164_LIBCPP_CONSTEXPR_SINCE_CXX26 void1165list<_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_LANG1172 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 void1191list<_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 else1199 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 else1211 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>::iterator1221list<_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>::iterator1230list<_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>::iterator1261list<_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>::iterator1268list<_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_LANG1313 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_CXX261333# if _LIBCPP_STD_VER >= 171334 typename list<_Tp, _Alloc>::reference1335# else1336 void1337# endif1338 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 >= 171345 return __node->__get_value();1346# endif1347}1348 1349template <class _Tp, class _Alloc>1350template <class... _Args>1351_LIBCPP_CONSTEXPR_SINCE_CXX261352# if _LIBCPP_STD_VER >= 171353 typename list<_Tp, _Alloc>::reference1354# else1355 void1356# endif1357 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 >= 171364 return __node->__get_value();1365# endif1366}1367 1368template <class _Tp, class _Alloc>1369template <class... _Args>1370_LIBCPP_CONSTEXPR_SINCE_CXX26 typename list<_Tp, _Alloc>::iterator1371list<_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>::iterator1382list<_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_LANG1391 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>::iterator1423list<_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 void1524list<_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_type1541list<_Tp, _Alloc>::remove(const value_type& __x) {1542 list<_Tp, _Alloc> __deleted_nodes(get_allocator()); // collect the nodes we're removing1543 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 } else1553 ++__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_type1562list<_Tp, _Alloc>::remove_if(_Pred __pred) {1563 list<_Tp, _Alloc> __deleted_nodes(get_allocator()); // collect the nodes we're removing1564 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 } else1574 ++__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_type1583list<_Tp, _Alloc>::unique(_BinaryPred __binary_pred) {1584 list<_Tp, _Alloc> __deleted_nodes(get_allocator()); // collect the nodes we're removing1585 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 } else1627 ++__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>::iterator1647list<_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 } else1678 ++__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 } else1694 ++__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 bool1718operator==(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 <= 171723 1724template <class _Tp, class _Alloc>1725_LIBCPP_CONSTEXPR_SINCE_CXX26 inline _LIBCPP_HIDE_FROM_ABI bool1726operator<(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 bool1732operator!=(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 bool1738operator>(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 bool1744operator>=(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 bool1750operator<=(const list<_Tp, _Alloc>& __x, const list<_Tp, _Alloc>& __y) {1751 return !(__y < __x);1752}1753 1754# else // _LIBCPP_STD_VER <= 171755 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 <= 171763 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 >= 201771template <class _Tp, class _Allocator, class _Predicate>1772_LIBCPP_CONSTEXPR_SINCE_CXX26 inline _LIBCPP_HIDE_FROM_ABI typename list<_Tp, _Allocator>::size_type1773erase_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_type1779erase(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_CHARACTERS1786template <>1787inline constexpr bool __format::__enable_insertable<std::list<wchar_t>> = true;1788# endif1789 1790# endif // _LIBCPP_STD_VER >= 201791 1792template <class _Tp, class _Allocator>1793struct __container_traits<list<_Tp, _Allocator> > {1794 // http://eel.is/c++draft/container.reqmts1795 // 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 following1797 // additional requirements:1798 // - If an exception is thrown by an insert() or emplace() function while inserting a single element, that1799 // 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_STD1806 1807# if _LIBCPP_STD_VER >= 171808_LIBCPP_BEGIN_NAMESPACE_STD1809namespace pmr {1810template <class _ValueT>1811using list _LIBCPP_AVAILABILITY_PMR = std::list<_ValueT, polymorphic_allocator<_ValueT>>;1812} // namespace pmr1813_LIBCPP_END_NAMESPACE_STD1814# endif1815 1816_LIBCPP_POP_MACROS1817 1818# if !defined(_LIBCPP_REMOVE_TRANSITIVE_INCLUDES) && _LIBCPP_STD_VER <= 201819# 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# endif1831#endif // __cplusplus < 201103L && defined(_LIBCPP_USE_FROZEN_CXX03_HEADERS)1832 1833#endif // _LIBCPP_LIST1834