1369 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___CXX03_LIST11#define _LIBCPP___CXX03_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(64 allocator_type::propagate_on_container_move_assignment::value &&65 is_nothrow_move_assignable<allocator_type>::value);66 list& operator=(initializer_list<value_type>);67 template <class Iter>68 void assign(Iter first, Iter last);69 template<container-compatible-range<T> R>70 void assign_range(R&& rg); // C++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#include <__cxx03/__algorithm/comp.h>201#include <__cxx03/__algorithm/equal.h>202#include <__cxx03/__algorithm/lexicographical_compare.h>203#include <__cxx03/__algorithm/min.h>204#include <__cxx03/__assert>205#include <__cxx03/__config>206#include <__cxx03/__iterator/distance.h>207#include <__cxx03/__iterator/iterator_traits.h>208#include <__cxx03/__iterator/move_iterator.h>209#include <__cxx03/__iterator/next.h>210#include <__cxx03/__iterator/prev.h>211#include <__cxx03/__iterator/reverse_iterator.h>212#include <__cxx03/__memory/addressof.h>213#include <__cxx03/__memory/allocation_guard.h>214#include <__cxx03/__memory/allocator.h>215#include <__cxx03/__memory/allocator_traits.h>216#include <__cxx03/__memory/compressed_pair.h>217#include <__cxx03/__memory/construct_at.h>218#include <__cxx03/__memory/pointer_traits.h>219#include <__cxx03/__memory/swap_allocator.h>220#include <__cxx03/__type_traits/conditional.h>221#include <__cxx03/__type_traits/is_allocator.h>222#include <__cxx03/__type_traits/is_nothrow_assignable.h>223#include <__cxx03/__type_traits/is_nothrow_constructible.h>224#include <__cxx03/__type_traits/is_pointer.h>225#include <__cxx03/__type_traits/is_same.h>226#include <__cxx03/__type_traits/type_identity.h>227#include <__cxx03/__utility/forward.h>228#include <__cxx03/__utility/move.h>229#include <__cxx03/__utility/swap.h>230#include <__cxx03/cstring>231#include <__cxx03/limits>232#include <__cxx03/new> // __launder233#include <__cxx03/version>234 235// standard-mandated includes236 237// [iterator.range]238#include <__cxx03/__iterator/access.h>239 240#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)241# pragma GCC system_header242#endif243 244_LIBCPP_PUSH_MACROS245#include <__cxx03/__undef_macros>246 247_LIBCPP_BEGIN_NAMESPACE_STD248 249template <class _Tp, class _VoidPtr>250struct __list_node;251template <class _Tp, class _VoidPtr>252struct __list_node_base;253 254template <class _Tp, class _VoidPtr>255struct __list_node_pointer_traits {256 typedef __rebind_pointer_t<_VoidPtr, __list_node<_Tp, _VoidPtr> > __node_pointer;257 typedef __rebind_pointer_t<_VoidPtr, __list_node_base<_Tp, _VoidPtr> > __base_pointer;258 259#if defined(_LIBCPP_ABI_LIST_REMOVE_NODE_POINTER_UB)260 typedef __base_pointer __link_pointer;261#else262 typedef __conditional_t<is_pointer<_VoidPtr>::value, __base_pointer, __node_pointer> __link_pointer;263#endif264 265 typedef __conditional_t<is_same<__link_pointer, __node_pointer>::value, __base_pointer, __node_pointer>266 __non_link_pointer;267 268 static _LIBCPP_HIDE_FROM_ABI __link_pointer __unsafe_link_pointer_cast(__link_pointer __p) { return __p; }269 270 static _LIBCPP_HIDE_FROM_ABI __link_pointer __unsafe_link_pointer_cast(__non_link_pointer __p) {271 return static_cast<__link_pointer>(static_cast<_VoidPtr>(__p));272 }273};274 275template <class _Tp, class _VoidPtr>276struct __list_node_base {277 typedef __list_node_pointer_traits<_Tp, _VoidPtr> _NodeTraits;278 typedef typename _NodeTraits::__node_pointer __node_pointer;279 typedef typename _NodeTraits::__base_pointer __base_pointer;280 typedef typename _NodeTraits::__link_pointer __link_pointer;281 282 __link_pointer __prev_;283 __link_pointer __next_;284 285 _LIBCPP_HIDE_FROM_ABI __list_node_base()286 : __prev_(_NodeTraits::__unsafe_link_pointer_cast(__self())),287 __next_(_NodeTraits::__unsafe_link_pointer_cast(__self())) {}288 289 _LIBCPP_HIDE_FROM_ABI explicit __list_node_base(__link_pointer __prev, __link_pointer __next)290 : __prev_(__prev), __next_(__next) {}291 292 _LIBCPP_HIDE_FROM_ABI __base_pointer __self() { return pointer_traits<__base_pointer>::pointer_to(*this); }293 294 _LIBCPP_HIDE_FROM_ABI __node_pointer __as_node() { return static_cast<__node_pointer>(__self()); }295};296 297template <class _Tp, class _VoidPtr>298struct __list_node : public __list_node_base<_Tp, _VoidPtr> {299 // We allow starting the lifetime of nodes without initializing the value held by the node,300 // since that is handled by the list itself in order to be allocator-aware.301 302private:303 _ALIGNAS_TYPE(_Tp) char __buffer_[sizeof(_Tp)];304 305public:306 _LIBCPP_HIDE_FROM_ABI _Tp& __get_value() { return *std::__launder(reinterpret_cast<_Tp*>(&__buffer_)); }307 308 typedef __list_node_base<_Tp, _VoidPtr> __base;309 typedef typename __base::__link_pointer __link_pointer;310 311 _LIBCPP_HIDE_FROM_ABI explicit __list_node(__link_pointer __prev, __link_pointer __next) : __base(__prev, __next) {}312 _LIBCPP_HIDE_FROM_ABI ~__list_node() {}313 314 _LIBCPP_HIDE_FROM_ABI __link_pointer __as_link() { return static_cast<__link_pointer>(__base::__self()); }315};316 317template <class _Tp, class _Alloc = allocator<_Tp> >318class _LIBCPP_TEMPLATE_VIS list;319template <class _Tp, class _Alloc>320class __list_imp;321template <class _Tp, class _VoidPtr>322class _LIBCPP_TEMPLATE_VIS __list_const_iterator;323 324template <class _Tp, class _VoidPtr>325class _LIBCPP_TEMPLATE_VIS __list_iterator {326 typedef __list_node_pointer_traits<_Tp, _VoidPtr> _NodeTraits;327 typedef typename _NodeTraits::__link_pointer __link_pointer;328 329 __link_pointer __ptr_;330 331 _LIBCPP_HIDE_FROM_ABI explicit __list_iterator(__link_pointer __p) _NOEXCEPT : __ptr_(__p) {}332 333 template <class, class>334 friend class list;335 template <class, class>336 friend class __list_imp;337 template <class, class>338 friend class __list_const_iterator;339 340public:341 typedef bidirectional_iterator_tag iterator_category;342 typedef _Tp value_type;343 typedef value_type& reference;344 typedef __rebind_pointer_t<_VoidPtr, value_type> pointer;345 typedef typename pointer_traits<pointer>::difference_type difference_type;346 347 _LIBCPP_HIDE_FROM_ABI __list_iterator() _NOEXCEPT : __ptr_(nullptr) {}348 349 _LIBCPP_HIDE_FROM_ABI reference operator*() const { return __ptr_->__as_node()->__get_value(); }350 _LIBCPP_HIDE_FROM_ABI pointer operator->() const {351 return pointer_traits<pointer>::pointer_to(__ptr_->__as_node()->__get_value());352 }353 354 _LIBCPP_HIDE_FROM_ABI __list_iterator& operator++() {355 __ptr_ = __ptr_->__next_;356 return *this;357 }358 _LIBCPP_HIDE_FROM_ABI __list_iterator operator++(int) {359 __list_iterator __t(*this);360 ++(*this);361 return __t;362 }363 364 _LIBCPP_HIDE_FROM_ABI __list_iterator& operator--() {365 __ptr_ = __ptr_->__prev_;366 return *this;367 }368 _LIBCPP_HIDE_FROM_ABI __list_iterator operator--(int) {369 __list_iterator __t(*this);370 --(*this);371 return __t;372 }373 374 friend _LIBCPP_HIDE_FROM_ABI bool operator==(const __list_iterator& __x, const __list_iterator& __y) {375 return __x.__ptr_ == __y.__ptr_;376 }377 friend _LIBCPP_HIDE_FROM_ABI bool operator!=(const __list_iterator& __x, const __list_iterator& __y) {378 return !(__x == __y);379 }380};381 382template <class _Tp, class _VoidPtr>383class _LIBCPP_TEMPLATE_VIS __list_const_iterator {384 typedef __list_node_pointer_traits<_Tp, _VoidPtr> _NodeTraits;385 typedef typename _NodeTraits::__link_pointer __link_pointer;386 387 __link_pointer __ptr_;388 389 _LIBCPP_HIDE_FROM_ABI explicit __list_const_iterator(__link_pointer __p) _NOEXCEPT : __ptr_(__p) {}390 391 template <class, class>392 friend class list;393 template <class, class>394 friend class __list_imp;395 396public:397 typedef bidirectional_iterator_tag iterator_category;398 typedef _Tp value_type;399 typedef const value_type& reference;400 typedef __rebind_pointer_t<_VoidPtr, const value_type> pointer;401 typedef typename pointer_traits<pointer>::difference_type difference_type;402 403 _LIBCPP_HIDE_FROM_ABI __list_const_iterator() _NOEXCEPT : __ptr_(nullptr) {}404 _LIBCPP_HIDE_FROM_ABI __list_const_iterator(const __list_iterator<_Tp, _VoidPtr>& __p) _NOEXCEPT405 : __ptr_(__p.__ptr_) {}406 407 _LIBCPP_HIDE_FROM_ABI reference operator*() const { return __ptr_->__as_node()->__get_value(); }408 _LIBCPP_HIDE_FROM_ABI pointer operator->() const {409 return pointer_traits<pointer>::pointer_to(__ptr_->__as_node()->__get_value());410 }411 412 _LIBCPP_HIDE_FROM_ABI __list_const_iterator& operator++() {413 __ptr_ = __ptr_->__next_;414 return *this;415 }416 _LIBCPP_HIDE_FROM_ABI __list_const_iterator operator++(int) {417 __list_const_iterator __t(*this);418 ++(*this);419 return __t;420 }421 422 _LIBCPP_HIDE_FROM_ABI __list_const_iterator& operator--() {423 __ptr_ = __ptr_->__prev_;424 return *this;425 }426 _LIBCPP_HIDE_FROM_ABI __list_const_iterator operator--(int) {427 __list_const_iterator __t(*this);428 --(*this);429 return __t;430 }431 432 friend _LIBCPP_HIDE_FROM_ABI bool operator==(const __list_const_iterator& __x, const __list_const_iterator& __y) {433 return __x.__ptr_ == __y.__ptr_;434 }435 friend _LIBCPP_HIDE_FROM_ABI bool operator!=(const __list_const_iterator& __x, const __list_const_iterator& __y) {436 return !(__x == __y);437 }438};439 440template <class _Tp, class _Alloc>441class __list_imp {442public:443 __list_imp(const __list_imp&) = delete;444 __list_imp& operator=(const __list_imp&) = delete;445 446 typedef _Alloc allocator_type;447 typedef allocator_traits<allocator_type> __alloc_traits;448 typedef typename __alloc_traits::size_type size_type;449 450protected:451 typedef _Tp value_type;452 typedef typename __alloc_traits::void_pointer __void_pointer;453 typedef __list_iterator<value_type, __void_pointer> iterator;454 typedef __list_const_iterator<value_type, __void_pointer> const_iterator;455 typedef __list_node_base<value_type, __void_pointer> __node_base;456 typedef __list_node<value_type, __void_pointer> __node_type;457 typedef __rebind_alloc<__alloc_traits, __node_type> __node_allocator;458 typedef allocator_traits<__node_allocator> __node_alloc_traits;459 typedef typename __node_alloc_traits::pointer __node_pointer;460 typedef typename __node_alloc_traits::pointer __node_const_pointer;461 typedef __list_node_pointer_traits<value_type, __void_pointer> __node_pointer_traits;462 typedef typename __node_pointer_traits::__link_pointer __link_pointer;463 typedef __link_pointer __link_const_pointer;464 typedef typename __alloc_traits::pointer pointer;465 typedef typename __alloc_traits::const_pointer const_pointer;466 typedef typename __alloc_traits::difference_type difference_type;467 468 typedef __rebind_alloc<__alloc_traits, __node_base> __node_base_allocator;469 typedef typename allocator_traits<__node_base_allocator>::pointer __node_base_pointer;470 static_assert(!is_same<allocator_type, __node_allocator>::value,471 "internal allocator type must differ from user-specified type; otherwise overload resolution breaks");472 473 __node_base __end_;474 __compressed_pair<size_type, __node_allocator> __size_alloc_;475 476 _LIBCPP_HIDE_FROM_ABI __link_pointer __end_as_link() const _NOEXCEPT {477 return __node_pointer_traits::__unsafe_link_pointer_cast(const_cast<__node_base&>(__end_).__self());478 }479 480 _LIBCPP_HIDE_FROM_ABI size_type& __sz() _NOEXCEPT { return __size_alloc_.first(); }481 _LIBCPP_HIDE_FROM_ABI const size_type& __sz() const _NOEXCEPT { return __size_alloc_.first(); }482 _LIBCPP_HIDE_FROM_ABI __node_allocator& __node_alloc() _NOEXCEPT { return __size_alloc_.second(); }483 _LIBCPP_HIDE_FROM_ABI const __node_allocator& __node_alloc() const _NOEXCEPT { return __size_alloc_.second(); }484 485 _LIBCPP_HIDE_FROM_ABI size_type __node_alloc_max_size() const _NOEXCEPT {486 return __node_alloc_traits::max_size(__node_alloc());487 }488 _LIBCPP_HIDE_FROM_ABI static void __unlink_nodes(__link_pointer __f, __link_pointer __l) _NOEXCEPT;489 490 _LIBCPP_HIDE_FROM_ABI __list_imp();491 _LIBCPP_HIDE_FROM_ABI __list_imp(const allocator_type& __a);492 _LIBCPP_HIDE_FROM_ABI __list_imp(const __node_allocator& __a);493 _LIBCPP_HIDE_FROM_ABI ~__list_imp();494 _LIBCPP_HIDE_FROM_ABI void clear() _NOEXCEPT;495 _LIBCPP_HIDE_FROM_ABI bool empty() const _NOEXCEPT { return __sz() == 0; }496 497 _LIBCPP_HIDE_FROM_ABI iterator begin() _NOEXCEPT { return iterator(__end_.__next_); }498 _LIBCPP_HIDE_FROM_ABI const_iterator begin() const _NOEXCEPT { return const_iterator(__end_.__next_); }499 _LIBCPP_HIDE_FROM_ABI iterator end() _NOEXCEPT { return iterator(__end_as_link()); }500 _LIBCPP_HIDE_FROM_ABI const_iterator end() const _NOEXCEPT { return const_iterator(__end_as_link()); }501 502 _LIBCPP_HIDE_FROM_ABI void swap(__list_imp& __c);503 504 _LIBCPP_HIDE_FROM_ABI void __copy_assign_alloc(const __list_imp& __c) {505 __copy_assign_alloc(506 __c, integral_constant<bool, __node_alloc_traits::propagate_on_container_copy_assignment::value>());507 }508 509 _LIBCPP_HIDE_FROM_ABI void __move_assign_alloc(__list_imp& __c) {510 __move_assign_alloc(511 __c, integral_constant<bool, __node_alloc_traits::propagate_on_container_move_assignment::value>());512 }513 514 template <class... _Args>515 _LIBCPP_HIDE_FROM_ABI __node_pointer __create_node(__link_pointer __prev, __link_pointer __next, _Args&&... __args) {516 __node_allocator& __alloc = __node_alloc();517 __allocation_guard<__node_allocator> __guard(__alloc, 1);518 // Begin the lifetime of the node itself. Note that this doesn't begin the lifetime of the value519 // held inside the node, since we need to use the allocator's construct() method for that.520 //521 // We don't use the allocator's construct() method to construct the node itself since the522 // Cpp17FooInsertable named requirements don't require the allocator's construct() method523 // to work on anything other than the value_type.524 std::__construct_at(std::addressof(*__guard.__get()), __prev, __next);525 526 // Now construct the value_type using the allocator's construct() method.527 __node_alloc_traits::construct(528 __alloc, std::addressof(__guard.__get()->__get_value()), std::forward<_Args>(__args)...);529 return __guard.__release_ptr();530 }531 532 _LIBCPP_HIDE_FROM_ABI void __delete_node(__node_pointer __node) {533 // For the same reason as above, we use the allocator's destroy() method for the value_type,534 // but not for the node itself.535 __node_allocator& __alloc = __node_alloc();536 __node_alloc_traits::destroy(__alloc, std::addressof(__node->__get_value()));537 std::__destroy_at(std::addressof(*__node));538 __node_alloc_traits::deallocate(__alloc, __node, 1);539 }540 541private:542 _LIBCPP_HIDE_FROM_ABI void __copy_assign_alloc(const __list_imp& __c, true_type) {543 if (__node_alloc() != __c.__node_alloc())544 clear();545 __node_alloc() = __c.__node_alloc();546 }547 548 _LIBCPP_HIDE_FROM_ABI void __copy_assign_alloc(const __list_imp&, false_type) {}549 550 _LIBCPP_HIDE_FROM_ABI void __move_assign_alloc(__list_imp& __c, true_type) {551 __node_alloc() = std::move(__c.__node_alloc());552 }553 554 _LIBCPP_HIDE_FROM_ABI void __move_assign_alloc(__list_imp&, false_type) _NOEXCEPT {}555};556 557// Unlink nodes [__f, __l]558template <class _Tp, class _Alloc>559inline void __list_imp<_Tp, _Alloc>::__unlink_nodes(__link_pointer __f, __link_pointer __l) _NOEXCEPT {560 __f->__prev_->__next_ = __l->__next_;561 __l->__next_->__prev_ = __f->__prev_;562}563 564template <class _Tp, class _Alloc>565inline __list_imp<_Tp, _Alloc>::__list_imp() : __size_alloc_(0, __default_init_tag()) {}566 567template <class _Tp, class _Alloc>568inline __list_imp<_Tp, _Alloc>::__list_imp(const allocator_type& __a) : __size_alloc_(0, __node_allocator(__a)) {}569 570template <class _Tp, class _Alloc>571inline __list_imp<_Tp, _Alloc>::__list_imp(const __node_allocator& __a) : __size_alloc_(0, __a) {}572 573template <class _Tp, class _Alloc>574__list_imp<_Tp, _Alloc>::~__list_imp() {575 clear();576}577 578template <class _Tp, class _Alloc>579void __list_imp<_Tp, _Alloc>::clear() _NOEXCEPT {580 if (!empty()) {581 __link_pointer __f = __end_.__next_;582 __link_pointer __l = __end_as_link();583 __unlink_nodes(__f, __l->__prev_);584 __sz() = 0;585 while (__f != __l) {586 __node_pointer __np = __f->__as_node();587 __f = __f->__next_;588 __delete_node(__np);589 }590 }591}592 593template <class _Tp, class _Alloc>594void __list_imp<_Tp, _Alloc>::swap(__list_imp& __c) {595 _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR(596 __alloc_traits::propagate_on_container_swap::value || this->__node_alloc() == __c.__node_alloc(),597 "list::swap: Either propagate_on_container_swap must be true"598 " or the allocators must compare equal");599 using std::swap;600 std::__swap_allocator(__node_alloc(), __c.__node_alloc());601 swap(__sz(), __c.__sz());602 swap(__end_, __c.__end_);603 if (__sz() == 0)604 __end_.__next_ = __end_.__prev_ = __end_as_link();605 else606 __end_.__prev_->__next_ = __end_.__next_->__prev_ = __end_as_link();607 if (__c.__sz() == 0)608 __c.__end_.__next_ = __c.__end_.__prev_ = __c.__end_as_link();609 else610 __c.__end_.__prev_->__next_ = __c.__end_.__next_->__prev_ = __c.__end_as_link();611}612 613template <class _Tp, class _Alloc /*= allocator<_Tp>*/>614class _LIBCPP_TEMPLATE_VIS list : private __list_imp<_Tp, _Alloc> {615 typedef __list_imp<_Tp, _Alloc> __base;616 typedef typename __base::__node_type __node_type;617 typedef typename __base::__node_allocator __node_allocator;618 typedef typename __base::__node_pointer __node_pointer;619 typedef typename __base::__node_alloc_traits __node_alloc_traits;620 typedef typename __base::__node_base __node_base;621 typedef typename __base::__node_base_pointer __node_base_pointer;622 typedef typename __base::__link_pointer __link_pointer;623 624public:625 typedef _Tp value_type;626 typedef _Alloc allocator_type;627 static_assert(__check_valid_allocator<allocator_type>::value);628 static_assert(is_same<value_type, typename allocator_type::value_type>::value,629 "Allocator::value_type must be same type as value_type");630 typedef value_type& reference;631 typedef const value_type& const_reference;632 typedef typename __base::pointer pointer;633 typedef typename __base::const_pointer const_pointer;634 typedef typename __base::size_type size_type;635 typedef typename __base::difference_type difference_type;636 typedef typename __base::iterator iterator;637 typedef typename __base::const_iterator const_iterator;638 typedef std::reverse_iterator<iterator> reverse_iterator;639 typedef std::reverse_iterator<const_iterator> const_reverse_iterator;640 typedef void __remove_return_type;641 642 _LIBCPP_HIDE_FROM_ABI list() {}643 _LIBCPP_HIDE_FROM_ABI explicit list(const allocator_type& __a) : __base(__a) {}644 _LIBCPP_HIDE_FROM_ABI explicit list(size_type __n);645 _LIBCPP_HIDE_FROM_ABI list(size_type __n, const value_type& __x);646 template <__enable_if_t<__is_allocator<_Alloc>::value, int> = 0>647 _LIBCPP_HIDE_FROM_ABI list(size_type __n, const value_type& __x, const allocator_type& __a) : __base(__a) {648 for (; __n > 0; --__n)649 push_back(__x);650 }651 652 template <class _InpIter, __enable_if_t<__has_input_iterator_category<_InpIter>::value, int> = 0>653 _LIBCPP_HIDE_FROM_ABI list(_InpIter __f, _InpIter __l);654 655 template <class _InpIter, __enable_if_t<__has_input_iterator_category<_InpIter>::value, int> = 0>656 _LIBCPP_HIDE_FROM_ABI list(_InpIter __f, _InpIter __l, const allocator_type& __a);657 658 _LIBCPP_HIDE_FROM_ABI list(const list& __c);659 _LIBCPP_HIDE_FROM_ABI list(const list& __c, const __type_identity_t<allocator_type>& __a);660 _LIBCPP_HIDE_FROM_ABI list& operator=(const list& __c);661 662 template <class _InpIter, __enable_if_t<__has_input_iterator_category<_InpIter>::value, int> = 0>663 _LIBCPP_HIDE_FROM_ABI void assign(_InpIter __f, _InpIter __l);664 665 _LIBCPP_HIDE_FROM_ABI void assign(size_type __n, const value_type& __x);666 667 _LIBCPP_HIDE_FROM_ABI allocator_type get_allocator() const _NOEXCEPT;668 669 _LIBCPP_HIDE_FROM_ABI size_type size() const _NOEXCEPT { return __base::__sz(); }670 _LIBCPP_NODISCARD _LIBCPP_HIDE_FROM_ABI bool empty() const _NOEXCEPT { return __base::empty(); }671 _LIBCPP_HIDE_FROM_ABI size_type max_size() const _NOEXCEPT {672 return std::min<size_type>(__base::__node_alloc_max_size(), numeric_limits<difference_type >::max());673 }674 675 _LIBCPP_HIDE_FROM_ABI iterator begin() _NOEXCEPT { return __base::begin(); }676 _LIBCPP_HIDE_FROM_ABI const_iterator begin() const _NOEXCEPT { return __base::begin(); }677 _LIBCPP_HIDE_FROM_ABI iterator end() _NOEXCEPT { return __base::end(); }678 _LIBCPP_HIDE_FROM_ABI const_iterator end() const _NOEXCEPT { return __base::end(); }679 _LIBCPP_HIDE_FROM_ABI const_iterator cbegin() const _NOEXCEPT { return __base::begin(); }680 _LIBCPP_HIDE_FROM_ABI const_iterator cend() const _NOEXCEPT { return __base::end(); }681 682 _LIBCPP_HIDE_FROM_ABI reverse_iterator rbegin() _NOEXCEPT { return reverse_iterator(end()); }683 _LIBCPP_HIDE_FROM_ABI const_reverse_iterator rbegin() const _NOEXCEPT { return const_reverse_iterator(end()); }684 _LIBCPP_HIDE_FROM_ABI reverse_iterator rend() _NOEXCEPT { return reverse_iterator(begin()); }685 _LIBCPP_HIDE_FROM_ABI const_reverse_iterator rend() const _NOEXCEPT { return const_reverse_iterator(begin()); }686 _LIBCPP_HIDE_FROM_ABI const_reverse_iterator crbegin() const _NOEXCEPT { return const_reverse_iterator(end()); }687 _LIBCPP_HIDE_FROM_ABI const_reverse_iterator crend() const _NOEXCEPT { return const_reverse_iterator(begin()); }688 689 _LIBCPP_HIDE_FROM_ABI reference front() {690 _LIBCPP_ASSERT_VALID_ELEMENT_ACCESS(!empty(), "list::front called on empty list");691 return __base::__end_.__next_->__as_node()->__get_value();692 }693 _LIBCPP_HIDE_FROM_ABI const_reference front() const {694 _LIBCPP_ASSERT_VALID_ELEMENT_ACCESS(!empty(), "list::front called on empty list");695 return __base::__end_.__next_->__as_node()->__get_value();696 }697 _LIBCPP_HIDE_FROM_ABI reference back() {698 _LIBCPP_ASSERT_VALID_ELEMENT_ACCESS(!empty(), "list::back called on empty list");699 return __base::__end_.__prev_->__as_node()->__get_value();700 }701 _LIBCPP_HIDE_FROM_ABI const_reference back() const {702 _LIBCPP_ASSERT_VALID_ELEMENT_ACCESS(!empty(), "list::back called on empty list");703 return __base::__end_.__prev_->__as_node()->__get_value();704 }705 706 _LIBCPP_HIDE_FROM_ABI void push_front(const value_type& __x);707 _LIBCPP_HIDE_FROM_ABI void push_back(const value_type& __x);708 709 _LIBCPP_HIDE_FROM_ABI void __emplace_back(value_type const& __arg) { push_back(__arg); }710 711 _LIBCPP_HIDE_FROM_ABI iterator insert(const_iterator __p, const value_type& __x);712 _LIBCPP_HIDE_FROM_ABI iterator insert(const_iterator __p, size_type __n, const value_type& __x);713 714 template <class _InpIter, __enable_if_t<__has_input_iterator_category<_InpIter>::value, int> = 0>715 _LIBCPP_HIDE_FROM_ABI iterator insert(const_iterator __p, _InpIter __f, _InpIter __l);716 717 _LIBCPP_HIDE_FROM_ABI void swap(list& __c) { __base::swap(__c); }718 _LIBCPP_HIDE_FROM_ABI void clear() _NOEXCEPT { __base::clear(); }719 720 _LIBCPP_HIDE_FROM_ABI void pop_front();721 _LIBCPP_HIDE_FROM_ABI void pop_back();722 723 _LIBCPP_HIDE_FROM_ABI iterator erase(const_iterator __p);724 _LIBCPP_HIDE_FROM_ABI iterator erase(const_iterator __f, const_iterator __l);725 726 _LIBCPP_HIDE_FROM_ABI void resize(size_type __n);727 _LIBCPP_HIDE_FROM_ABI void resize(size_type __n, const value_type& __x);728 729 _LIBCPP_HIDE_FROM_ABI void splice(const_iterator __p, list& __c);730 _LIBCPP_HIDE_FROM_ABI void splice(const_iterator __p, list& __c, const_iterator __i);731 _LIBCPP_HIDE_FROM_ABI void splice(const_iterator __p, list& __c, const_iterator __f, const_iterator __l);732 733 _LIBCPP_HIDE_FROM_ABI __remove_return_type remove(const value_type& __x);734 template <class _Pred>735 _LIBCPP_HIDE_FROM_ABI __remove_return_type remove_if(_Pred __pred);736 _LIBCPP_HIDE_FROM_ABI __remove_return_type unique() { return unique(__equal_to()); }737 template <class _BinaryPred>738 _LIBCPP_HIDE_FROM_ABI __remove_return_type unique(_BinaryPred __binary_pred);739 _LIBCPP_HIDE_FROM_ABI void merge(list& __c);740 template <class _Comp>741 _LIBCPP_HIDE_FROM_ABI void merge(list& __c, _Comp __comp);742 743 _LIBCPP_HIDE_FROM_ABI void sort();744 template <class _Comp>745 _LIBCPP_HIDE_FROM_ABI void sort(_Comp __comp);746 747 _LIBCPP_HIDE_FROM_ABI void reverse() _NOEXCEPT;748 749 _LIBCPP_HIDE_FROM_ABI bool __invariants() const;750 751private:752 template <class _Iterator, class _Sentinel>753 _LIBCPP_HIDE_FROM_ABI void __assign_with_sentinel(_Iterator __f, _Sentinel __l);754 755 template <class _Iterator, class _Sentinel>756 _LIBCPP_HIDE_FROM_ABI iterator __insert_with_sentinel(const_iterator __p, _Iterator __f, _Sentinel __l);757 758 _LIBCPP_HIDE_FROM_ABI static void __link_nodes(__link_pointer __p, __link_pointer __f, __link_pointer __l);759 _LIBCPP_HIDE_FROM_ABI void __link_nodes_at_front(__link_pointer __f, __link_pointer __l);760 _LIBCPP_HIDE_FROM_ABI void __link_nodes_at_back(__link_pointer __f, __link_pointer __l);761 _LIBCPP_HIDE_FROM_ABI iterator __iterator(size_type __n);762 // TODO: Make this _LIBCPP_HIDE_FROM_ABI763 template <class _Comp>764 _LIBCPP_HIDDEN static iterator __sort(iterator __f1, iterator __e2, size_type __n, _Comp& __comp);765 766 _LIBCPP_HIDE_FROM_ABI void __move_assign(list& __c, true_type);767 _LIBCPP_HIDE_FROM_ABI void __move_assign(list& __c, false_type);768};769 770// Link in nodes [__f, __l] just prior to __p771template <class _Tp, class _Alloc>772inline void list<_Tp, _Alloc>::__link_nodes(__link_pointer __p, __link_pointer __f, __link_pointer __l) {773 __p->__prev_->__next_ = __f;774 __f->__prev_ = __p->__prev_;775 __p->__prev_ = __l;776 __l->__next_ = __p;777}778 779// Link in nodes [__f, __l] at the front of the list780template <class _Tp, class _Alloc>781inline void list<_Tp, _Alloc>::__link_nodes_at_front(__link_pointer __f, __link_pointer __l) {782 __f->__prev_ = __base::__end_as_link();783 __l->__next_ = __base::__end_.__next_;784 __l->__next_->__prev_ = __l;785 __base::__end_.__next_ = __f;786}787 788// Link in nodes [__f, __l] at the back of the list789template <class _Tp, class _Alloc>790inline void list<_Tp, _Alloc>::__link_nodes_at_back(__link_pointer __f, __link_pointer __l) {791 __l->__next_ = __base::__end_as_link();792 __f->__prev_ = __base::__end_.__prev_;793 __f->__prev_->__next_ = __f;794 __base::__end_.__prev_ = __l;795}796 797template <class _Tp, class _Alloc>798inline typename list<_Tp, _Alloc>::iterator list<_Tp, _Alloc>::__iterator(size_type __n) {799 return __n <= __base::__sz() / 2 ? std::next(begin(), __n) : std::prev(end(), __base::__sz() - __n);800}801 802template <class _Tp, class _Alloc>803list<_Tp, _Alloc>::list(size_type __n) {804 for (; __n > 0; --__n)805 push_back(value_type());806}807 808template <class _Tp, class _Alloc>809list<_Tp, _Alloc>::list(size_type __n, const value_type& __x) {810 for (; __n > 0; --__n)811 push_back(__x);812}813 814template <class _Tp, class _Alloc>815template <class _InpIter, __enable_if_t<__has_input_iterator_category<_InpIter>::value, int> >816list<_Tp, _Alloc>::list(_InpIter __f, _InpIter __l) {817 for (; __f != __l; ++__f)818 __emplace_back(*__f);819}820 821template <class _Tp, class _Alloc>822template <class _InpIter, __enable_if_t<__has_input_iterator_category<_InpIter>::value, int> >823list<_Tp, _Alloc>::list(_InpIter __f, _InpIter __l, const allocator_type& __a) : __base(__a) {824 for (; __f != __l; ++__f)825 __emplace_back(*__f);826}827 828template <class _Tp, class _Alloc>829list<_Tp, _Alloc>::list(const list& __c)830 : __base(__node_alloc_traits::select_on_container_copy_construction(__c.__node_alloc())) {831 for (const_iterator __i = __c.begin(), __e = __c.end(); __i != __e; ++__i)832 push_back(*__i);833}834 835template <class _Tp, class _Alloc>836list<_Tp, _Alloc>::list(const list& __c, const __type_identity_t<allocator_type>& __a) : __base(__a) {837 for (const_iterator __i = __c.begin(), __e = __c.end(); __i != __e; ++__i)838 push_back(*__i);839}840 841template <class _Tp, class _Alloc>842inline list<_Tp, _Alloc>& list<_Tp, _Alloc>::operator=(const list& __c) {843 if (this != std::addressof(__c)) {844 __base::__copy_assign_alloc(__c);845 assign(__c.begin(), __c.end());846 }847 return *this;848}849 850template <class _Tp, class _Alloc>851template <class _InpIter, __enable_if_t<__has_input_iterator_category<_InpIter>::value, int> >852void list<_Tp, _Alloc>::assign(_InpIter __f, _InpIter __l) {853 __assign_with_sentinel(__f, __l);854}855 856template <class _Tp, class _Alloc>857template <class _Iterator, class _Sentinel>858_LIBCPP_HIDE_FROM_ABI void list<_Tp, _Alloc>::__assign_with_sentinel(_Iterator __f, _Sentinel __l) {859 iterator __i = begin();860 iterator __e = end();861 for (; __f != __l && __i != __e; ++__f, (void)++__i)862 *__i = *__f;863 if (__i == __e)864 __insert_with_sentinel(__e, std::move(__f), std::move(__l));865 else866 erase(__i, __e);867}868 869template <class _Tp, class _Alloc>870void list<_Tp, _Alloc>::assign(size_type __n, const value_type& __x) {871 iterator __i = begin();872 iterator __e = end();873 for (; __n > 0 && __i != __e; --__n, (void)++__i)874 *__i = __x;875 if (__i == __e)876 insert(__e, __n, __x);877 else878 erase(__i, __e);879}880 881template <class _Tp, class _Alloc>882inline _Alloc list<_Tp, _Alloc>::get_allocator() const _NOEXCEPT {883 return allocator_type(__base::__node_alloc());884}885 886template <class _Tp, class _Alloc>887typename list<_Tp, _Alloc>::iterator list<_Tp, _Alloc>::insert(const_iterator __p, const value_type& __x) {888 __node_pointer __node = this->__create_node(/* prev = */ nullptr, /* next = */ nullptr, __x);889 __link_nodes(__p.__ptr_, __node->__as_link(), __node->__as_link());890 ++__base::__sz();891 return iterator(__node->__as_link());892}893 894template <class _Tp, class _Alloc>895typename list<_Tp, _Alloc>::iterator896list<_Tp, _Alloc>::insert(const_iterator __p, size_type __n, const value_type& __x) {897 iterator __r(__p.__ptr_);898 if (__n > 0) {899 size_type __ds = 0;900 __node_pointer __node = this->__create_node(/* prev = */ nullptr, /* next = */ nullptr, __x);901 ++__ds;902 __r = iterator(__node->__as_link());903 iterator __e = __r;904#ifndef _LIBCPP_HAS_NO_EXCEPTIONS905 try {906#endif // _LIBCPP_HAS_NO_EXCEPTIONS907 for (--__n; __n != 0; --__n, (void)++__e, ++__ds) {908 __e.__ptr_->__next_ = this->__create_node(/* prev = */ __e.__ptr_, /* next = */ nullptr, __x)->__as_link();909 }910#ifndef _LIBCPP_HAS_NO_EXCEPTIONS911 } catch (...) {912 while (true) {913 __link_pointer __prev = __e.__ptr_->__prev_;914 __node_pointer __current = __e.__ptr_->__as_node();915 this->__delete_node(__current);916 if (__prev == 0)917 break;918 __e = iterator(__prev);919 }920 throw;921 }922#endif // _LIBCPP_HAS_NO_EXCEPTIONS923 __link_nodes(__p.__ptr_, __r.__ptr_, __e.__ptr_);924 __base::__sz() += __ds;925 }926 return __r;927}928 929template <class _Tp, class _Alloc>930template <class _InpIter, __enable_if_t<__has_input_iterator_category<_InpIter>::value, int> >931typename list<_Tp, _Alloc>::iterator list<_Tp, _Alloc>::insert(const_iterator __p, _InpIter __f, _InpIter __l) {932 return __insert_with_sentinel(__p, __f, __l);933}934 935template <class _Tp, class _Alloc>936template <class _Iterator, class _Sentinel>937_LIBCPP_HIDE_FROM_ABI typename list<_Tp, _Alloc>::iterator938list<_Tp, _Alloc>::__insert_with_sentinel(const_iterator __p, _Iterator __f, _Sentinel __l) {939 iterator __r(__p.__ptr_);940 if (__f != __l) {941 size_type __ds = 0;942 __node_pointer __node = this->__create_node(/* prev = */ nullptr, /* next = */ nullptr, *__f);943 ++__ds;944 __r = iterator(__node->__as_link());945 iterator __e = __r;946#ifndef _LIBCPP_HAS_NO_EXCEPTIONS947 try {948#endif // _LIBCPP_HAS_NO_EXCEPTIONS949 for (++__f; __f != __l; ++__f, (void)++__e, ++__ds) {950 __e.__ptr_->__next_ = this->__create_node(/* prev = */ __e.__ptr_, /* next = */ nullptr, *__f)->__as_link();951 }952#ifndef _LIBCPP_HAS_NO_EXCEPTIONS953 } catch (...) {954 while (true) {955 __link_pointer __prev = __e.__ptr_->__prev_;956 __node_pointer __current = __e.__ptr_->__as_node();957 this->__delete_node(__current);958 if (__prev == 0)959 break;960 __e = iterator(__prev);961 }962 throw;963 }964#endif // _LIBCPP_HAS_NO_EXCEPTIONS965 __link_nodes(__p.__ptr_, __r.__ptr_, __e.__ptr_);966 __base::__sz() += __ds;967 }968 return __r;969}970 971template <class _Tp, class _Alloc>972void list<_Tp, _Alloc>::push_front(const value_type& __x) {973 __node_pointer __node = this->__create_node(/* prev = */ nullptr, /* next = */ nullptr, __x);974 __link_pointer __nl = __node->__as_link();975 __link_nodes_at_front(__nl, __nl);976 ++__base::__sz();977}978 979template <class _Tp, class _Alloc>980void list<_Tp, _Alloc>::push_back(const value_type& __x) {981 __node_pointer __node = this->__create_node(/* prev = */ nullptr, /* next = */ nullptr, __x);982 __link_pointer __nl = __node->__as_link();983 __link_nodes_at_back(__nl, __nl);984 ++__base::__sz();985}986 987template <class _Tp, class _Alloc>988void list<_Tp, _Alloc>::pop_front() {989 _LIBCPP_ASSERT_VALID_ELEMENT_ACCESS(!empty(), "list::pop_front() called with empty list");990 __link_pointer __n = __base::__end_.__next_;991 __base::__unlink_nodes(__n, __n);992 --__base::__sz();993 this->__delete_node(__n->__as_node());994}995 996template <class _Tp, class _Alloc>997void list<_Tp, _Alloc>::pop_back() {998 _LIBCPP_ASSERT_VALID_ELEMENT_ACCESS(!empty(), "list::pop_back() called on an empty list");999 __link_pointer __n = __base::__end_.__prev_;1000 __base::__unlink_nodes(__n, __n);1001 --__base::__sz();1002 this->__delete_node(__n->__as_node());1003}1004 1005template <class _Tp, class _Alloc>1006typename list<_Tp, _Alloc>::iterator list<_Tp, _Alloc>::erase(const_iterator __p) {1007 _LIBCPP_ASSERT_VALID_ELEMENT_ACCESS(__p != end(), "list::erase(iterator) called with a non-dereferenceable iterator");1008 __link_pointer __n = __p.__ptr_;1009 __link_pointer __r = __n->__next_;1010 __base::__unlink_nodes(__n, __n);1011 --__base::__sz();1012 this->__delete_node(__n->__as_node());1013 return iterator(__r);1014}1015 1016template <class _Tp, class _Alloc>1017typename list<_Tp, _Alloc>::iterator list<_Tp, _Alloc>::erase(const_iterator __f, const_iterator __l) {1018 if (__f != __l) {1019 __base::__unlink_nodes(__f.__ptr_, __l.__ptr_->__prev_);1020 while (__f != __l) {1021 __link_pointer __n = __f.__ptr_;1022 ++__f;1023 --__base::__sz();1024 this->__delete_node(__n->__as_node());1025 }1026 }1027 return iterator(__l.__ptr_);1028}1029 1030template <class _Tp, class _Alloc>1031void list<_Tp, _Alloc>::resize(size_type __n) {1032 if (__n < __base::__sz())1033 erase(__iterator(__n), end());1034 else if (__n > __base::__sz()) {1035 __n -= __base::__sz();1036 size_type __ds = 0;1037 __node_pointer __node = this->__create_node(/* prev = */ nullptr, /* next = */ nullptr);1038 ++__ds;1039 iterator __r = iterator(__node->__as_link());1040 iterator __e = __r;1041#ifndef _LIBCPP_HAS_NO_EXCEPTIONS1042 try {1043#endif // _LIBCPP_HAS_NO_EXCEPTIONS1044 for (--__n; __n != 0; --__n, (void)++__e, ++__ds) {1045 __e.__ptr_->__next_ = this->__create_node(/* prev = */ __e.__ptr_, /* next = */ nullptr)->__as_link();1046 }1047#ifndef _LIBCPP_HAS_NO_EXCEPTIONS1048 } catch (...) {1049 while (true) {1050 __link_pointer __prev = __e.__ptr_->__prev_;1051 __node_pointer __current = __e.__ptr_->__as_node();1052 this->__delete_node(__current);1053 if (__prev == 0)1054 break;1055 __e = iterator(__prev);1056 }1057 throw;1058 }1059#endif // _LIBCPP_HAS_NO_EXCEPTIONS1060 __link_nodes_at_back(__r.__ptr_, __e.__ptr_);1061 __base::__sz() += __ds;1062 }1063}1064 1065template <class _Tp, class _Alloc>1066void list<_Tp, _Alloc>::resize(size_type __n, const value_type& __x) {1067 if (__n < __base::__sz())1068 erase(__iterator(__n), end());1069 else if (__n > __base::__sz()) {1070 __n -= __base::__sz();1071 size_type __ds = 0;1072 __node_pointer __node = this->__create_node(/* prev = */ nullptr, /* next = */ nullptr, __x);1073 ++__ds;1074 __link_pointer __nl = __node->__as_link();1075 iterator __r = iterator(__nl);1076 iterator __e = __r;1077#ifndef _LIBCPP_HAS_NO_EXCEPTIONS1078 try {1079#endif // _LIBCPP_HAS_NO_EXCEPTIONS1080 for (--__n; __n != 0; --__n, (void)++__e, ++__ds) {1081 __e.__ptr_->__next_ = this->__create_node(/* prev = */ __e.__ptr_, /* next = */ nullptr, __x)->__as_link();1082 }1083#ifndef _LIBCPP_HAS_NO_EXCEPTIONS1084 } catch (...) {1085 while (true) {1086 __link_pointer __prev = __e.__ptr_->__prev_;1087 __node_pointer __current = __e.__ptr_->__as_node();1088 this->__delete_node(__current);1089 if (__prev == 0)1090 break;1091 __e = iterator(__prev);1092 }1093 throw;1094 }1095#endif // _LIBCPP_HAS_NO_EXCEPTIONS1096 __link_nodes(__base::__end_as_link(), __r.__ptr_, __e.__ptr_);1097 __base::__sz() += __ds;1098 }1099}1100 1101template <class _Tp, class _Alloc>1102void list<_Tp, _Alloc>::splice(const_iterator __p, list& __c) {1103 _LIBCPP_ASSERT_VALID_INPUT_RANGE(1104 this != std::addressof(__c), "list::splice(iterator, list) called with this == &list");1105 if (!__c.empty()) {1106 __link_pointer __f = __c.__end_.__next_;1107 __link_pointer __l = __c.__end_.__prev_;1108 __base::__unlink_nodes(__f, __l);1109 __link_nodes(__p.__ptr_, __f, __l);1110 __base::__sz() += __c.__sz();1111 __c.__sz() = 0;1112 }1113}1114 1115template <class _Tp, class _Alloc>1116void list<_Tp, _Alloc>::splice(const_iterator __p, list& __c, const_iterator __i) {1117 if (__p.__ptr_ != __i.__ptr_ && __p.__ptr_ != __i.__ptr_->__next_) {1118 __link_pointer __f = __i.__ptr_;1119 __base::__unlink_nodes(__f, __f);1120 __link_nodes(__p.__ptr_, __f, __f);1121 --__c.__sz();1122 ++__base::__sz();1123 }1124}1125 1126template <class _Tp, class _Alloc>1127void list<_Tp, _Alloc>::splice(const_iterator __p, list& __c, const_iterator __f, const_iterator __l) {1128 if (__f != __l) {1129 __link_pointer __first = __f.__ptr_;1130 --__l;1131 __link_pointer __last = __l.__ptr_;1132 if (this != std::addressof(__c)) {1133 size_type __s = std::distance(__f, __l) + 1;1134 __c.__sz() -= __s;1135 __base::__sz() += __s;1136 }1137 __base::__unlink_nodes(__first, __last);1138 __link_nodes(__p.__ptr_, __first, __last);1139 }1140}1141 1142template <class _Tp, class _Alloc>1143typename list<_Tp, _Alloc>::__remove_return_type list<_Tp, _Alloc>::remove(const value_type& __x) {1144 list<_Tp, _Alloc> __deleted_nodes(get_allocator()); // collect the nodes we're removing1145 for (const_iterator __i = begin(), __e = end(); __i != __e;) {1146 if (*__i == __x) {1147 const_iterator __j = std::next(__i);1148 for (; __j != __e && *__j == __x; ++__j)1149 ;1150 __deleted_nodes.splice(__deleted_nodes.end(), *this, __i, __j);1151 __i = __j;1152 if (__i != __e)1153 ++__i;1154 } else1155 ++__i;1156 }1157 1158 return (__remove_return_type)__deleted_nodes.size();1159}1160 1161template <class _Tp, class _Alloc>1162template <class _Pred>1163typename list<_Tp, _Alloc>::__remove_return_type list<_Tp, _Alloc>::remove_if(_Pred __pred) {1164 list<_Tp, _Alloc> __deleted_nodes(get_allocator()); // collect the nodes we're removing1165 for (iterator __i = begin(), __e = end(); __i != __e;) {1166 if (__pred(*__i)) {1167 iterator __j = std::next(__i);1168 for (; __j != __e && __pred(*__j); ++__j)1169 ;1170 __deleted_nodes.splice(__deleted_nodes.end(), *this, __i, __j);1171 __i = __j;1172 if (__i != __e)1173 ++__i;1174 } else1175 ++__i;1176 }1177 1178 return (__remove_return_type)__deleted_nodes.size();1179}1180 1181template <class _Tp, class _Alloc>1182template <class _BinaryPred>1183typename list<_Tp, _Alloc>::__remove_return_type list<_Tp, _Alloc>::unique(_BinaryPred __binary_pred) {1184 list<_Tp, _Alloc> __deleted_nodes(get_allocator()); // collect the nodes we're removing1185 for (iterator __i = begin(), __e = end(); __i != __e;) {1186 iterator __j = std::next(__i);1187 for (; __j != __e && __binary_pred(*__i, *__j); ++__j)1188 ;1189 if (++__i != __j) {1190 __deleted_nodes.splice(__deleted_nodes.end(), *this, __i, __j);1191 __i = __j;1192 }1193 }1194 1195 return (__remove_return_type)__deleted_nodes.size();1196}1197 1198template <class _Tp, class _Alloc>1199inline void list<_Tp, _Alloc>::merge(list& __c) {1200 merge(__c, __less<>());1201}1202 1203template <class _Tp, class _Alloc>1204template <class _Comp>1205void list<_Tp, _Alloc>::merge(list& __c, _Comp __comp) {1206 if (this != std::addressof(__c)) {1207 iterator __f1 = begin();1208 iterator __e1 = end();1209 iterator __f2 = __c.begin();1210 iterator __e2 = __c.end();1211 while (__f1 != __e1 && __f2 != __e2) {1212 if (__comp(*__f2, *__f1)) {1213 size_type __ds = 1;1214 iterator __m2 = std::next(__f2);1215 for (; __m2 != __e2 && __comp(*__m2, *__f1); ++__m2, (void)++__ds)1216 ;1217 __base::__sz() += __ds;1218 __c.__sz() -= __ds;1219 __link_pointer __f = __f2.__ptr_;1220 __link_pointer __l = __m2.__ptr_->__prev_;1221 __f2 = __m2;1222 __base::__unlink_nodes(__f, __l);1223 __m2 = std::next(__f1);1224 __link_nodes(__f1.__ptr_, __f, __l);1225 __f1 = __m2;1226 } else1227 ++__f1;1228 }1229 splice(__e1, __c);1230 }1231}1232 1233template <class _Tp, class _Alloc>1234inline void list<_Tp, _Alloc>::sort() {1235 sort(__less<>());1236}1237 1238template <class _Tp, class _Alloc>1239template <class _Comp>1240inline void list<_Tp, _Alloc>::sort(_Comp __comp) {1241 __sort(begin(), end(), __base::__sz(), __comp);1242}1243 1244template <class _Tp, class _Alloc>1245template <class _Comp>1246typename list<_Tp, _Alloc>::iterator1247list<_Tp, _Alloc>::__sort(iterator __f1, iterator __e2, size_type __n, _Comp& __comp) {1248 switch (__n) {1249 case 0:1250 case 1:1251 return __f1;1252 case 2:1253 if (__comp(*--__e2, *__f1)) {1254 __link_pointer __f = __e2.__ptr_;1255 __base::__unlink_nodes(__f, __f);1256 __link_nodes(__f1.__ptr_, __f, __f);1257 return __e2;1258 }1259 return __f1;1260 }1261 size_type __n2 = __n / 2;1262 iterator __e1 = std::next(__f1, __n2);1263 iterator __r = __f1 = __sort(__f1, __e1, __n2, __comp);1264 iterator __f2 = __e1 = __sort(__e1, __e2, __n - __n2, __comp);1265 if (__comp(*__f2, *__f1)) {1266 iterator __m2 = std::next(__f2);1267 for (; __m2 != __e2 && __comp(*__m2, *__f1); ++__m2)1268 ;1269 __link_pointer __f = __f2.__ptr_;1270 __link_pointer __l = __m2.__ptr_->__prev_;1271 __r = __f2;1272 __e1 = __f2 = __m2;1273 __base::__unlink_nodes(__f, __l);1274 __m2 = std::next(__f1);1275 __link_nodes(__f1.__ptr_, __f, __l);1276 __f1 = __m2;1277 } else1278 ++__f1;1279 while (__f1 != __e1 && __f2 != __e2) {1280 if (__comp(*__f2, *__f1)) {1281 iterator __m2 = std::next(__f2);1282 for (; __m2 != __e2 && __comp(*__m2, *__f1); ++__m2)1283 ;1284 __link_pointer __f = __f2.__ptr_;1285 __link_pointer __l = __m2.__ptr_->__prev_;1286 if (__e1 == __f2)1287 __e1 = __m2;1288 __f2 = __m2;1289 __base::__unlink_nodes(__f, __l);1290 __m2 = std::next(__f1);1291 __link_nodes(__f1.__ptr_, __f, __l);1292 __f1 = __m2;1293 } else1294 ++__f1;1295 }1296 return __r;1297}1298 1299template <class _Tp, class _Alloc>1300void list<_Tp, _Alloc>::reverse() _NOEXCEPT {1301 if (__base::__sz() > 1) {1302 iterator __e = end();1303 for (iterator __i = begin(); __i.__ptr_ != __e.__ptr_;) {1304 std::swap(__i.__ptr_->__prev_, __i.__ptr_->__next_);1305 __i.__ptr_ = __i.__ptr_->__prev_;1306 }1307 std::swap(__e.__ptr_->__prev_, __e.__ptr_->__next_);1308 }1309}1310 1311template <class _Tp, class _Alloc>1312bool list<_Tp, _Alloc>::__invariants() const {1313 return size() == std::distance(begin(), end());1314}1315 1316template <class _Tp, class _Alloc>1317inline _LIBCPP_HIDE_FROM_ABI bool operator==(const list<_Tp, _Alloc>& __x, const list<_Tp, _Alloc>& __y) {1318 return __x.size() == __y.size() && std::equal(__x.begin(), __x.end(), __y.begin());1319}1320 1321template <class _Tp, class _Alloc>1322inline _LIBCPP_HIDE_FROM_ABI bool operator<(const list<_Tp, _Alloc>& __x, const list<_Tp, _Alloc>& __y) {1323 return std::lexicographical_compare(__x.begin(), __x.end(), __y.begin(), __y.end());1324}1325 1326template <class _Tp, class _Alloc>1327inline _LIBCPP_HIDE_FROM_ABI bool operator!=(const list<_Tp, _Alloc>& __x, const list<_Tp, _Alloc>& __y) {1328 return !(__x == __y);1329}1330 1331template <class _Tp, class _Alloc>1332inline _LIBCPP_HIDE_FROM_ABI bool operator>(const list<_Tp, _Alloc>& __x, const list<_Tp, _Alloc>& __y) {1333 return __y < __x;1334}1335 1336template <class _Tp, class _Alloc>1337inline _LIBCPP_HIDE_FROM_ABI bool operator>=(const list<_Tp, _Alloc>& __x, const list<_Tp, _Alloc>& __y) {1338 return !(__x < __y);1339}1340 1341template <class _Tp, class _Alloc>1342inline _LIBCPP_HIDE_FROM_ABI bool operator<=(const list<_Tp, _Alloc>& __x, const list<_Tp, _Alloc>& __y) {1343 return !(__y < __x);1344}1345 1346template <class _Tp, class _Alloc>1347inline _LIBCPP_HIDE_FROM_ABI void swap(list<_Tp, _Alloc>& __x, list<_Tp, _Alloc>& __y) {1348 __x.swap(__y);1349}1350 1351_LIBCPP_END_NAMESPACE_STD1352 1353_LIBCPP_POP_MACROS1354 1355#if !defined(_LIBCPP_REMOVE_TRANSITIVE_INCLUDES)1356# include <__cxx03/algorithm>1357# include <__cxx03/atomic>1358# include <__cxx03/cstdint>1359# include <__cxx03/cstdlib>1360# include <__cxx03/functional>1361# include <__cxx03/iosfwd>1362# include <__cxx03/iterator>1363# include <__cxx03/stdexcept>1364# include <__cxx03/type_traits>1365# include <__cxx03/typeinfo>1366#endif1367 1368#endif // _LIBCPP___CXX03_LIST1369