1// -*- C++ -*- 2//===----------------------------------------------------------------------===// 3// 4// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 5// See https://llvm.org/LICENSE.txt for license information. 6// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 7// 8//===----------------------------------------------------------------------===// 9 10#ifndef _LIBCPP_LIST 11#define _LIBCPP_LIST 12 13/* 14 list synopsis 15 16namespace std 17{ 18 19template <class T, class Alloc = allocator<T> > 20class list 21{ 22public: 23 24 // types: 25 typedef T value_type; 26 typedef Alloc allocator_type; 27 typedef typename allocator_type::reference reference; 28 typedef typename allocator_type::const_reference const_reference; 29 typedef typename allocator_type::pointer pointer; 30 typedef typename allocator_type::const_pointer const_pointer; 31 typedef implementation-defined iterator; 32 typedef implementation-defined const_iterator; 33 typedef implementation-defined size_type; 34 typedef implementation-defined difference_type; 35 typedef reverse_iterator<iterator> reverse_iterator; 36 typedef reverse_iterator<const_iterator> const_reverse_iterator; 37 38 list() 39 noexcept(is_nothrow_default_constructible<allocator_type>::value); 40 explicit list(const allocator_type& a); 41 explicit list(size_type n); 42 explicit list(size_type n, const allocator_type& a); // C++14 43 list(size_type n, const value_type& value); 44 list(size_type n, const value_type& value, const allocator_type& a); 45 template <class Iter> 46 list(Iter first, Iter last); 47 template <class Iter> 48 list(Iter first, Iter last, const allocator_type& a); 49 list(const list& x); 50 list(const list&, const allocator_type& a); 51 list(list&& x) 52 noexcept(is_nothrow_move_constructible<allocator_type>::value); 53 list(list&&, const allocator_type& a); 54 list(initializer_list<value_type>); 55 list(initializer_list<value_type>, const allocator_type& a); 56 57 ~list(); 58 59 list& operator=(const list& x); 60 list& operator=(list&& x) 61 noexcept( 62 allocator_type::propagate_on_container_move_assignment::value && 63 is_nothrow_move_assignable<allocator_type>::value); 64 list& operator=(initializer_list<value_type>); 65 template <class Iter> 66 void assign(Iter first, Iter last); 67 void assign(size_type n, const value_type& t); 68 void assign(initializer_list<value_type>); 69 70 allocator_type get_allocator() const noexcept; 71 72 iterator begin() noexcept; 73 const_iterator begin() const noexcept; 74 iterator end() noexcept; 75 const_iterator end() const noexcept; 76 reverse_iterator rbegin() noexcept; 77 const_reverse_iterator rbegin() const noexcept; 78 reverse_iterator rend() noexcept; 79 const_reverse_iterator rend() const noexcept; 80 const_iterator cbegin() const noexcept; 81 const_iterator cend() const noexcept; 82 const_reverse_iterator crbegin() const noexcept; 83 const_reverse_iterator crend() const noexcept; 84 85 reference front(); 86 const_reference front() const; 87 reference back(); 88 const_reference back() const; 89 90 bool empty() const noexcept; 91 size_type size() const noexcept; 92 size_type max_size() const noexcept; 93 94 template <class... Args> 95 reference emplace_front(Args&&... args); // reference in C++17 96 void pop_front(); 97 template <class... Args> 98 reference emplace_back(Args&&... args); // reference in C++17 99 void pop_back(); 100 void push_front(const value_type& x); 101 void push_front(value_type&& x); 102 void push_back(const value_type& x); 103 void push_back(value_type&& x); 104 template <class... Args> 105 iterator emplace(const_iterator position, Args&&... args); 106 iterator insert(const_iterator position, const value_type& x); 107 iterator insert(const_iterator position, value_type&& x); 108 iterator insert(const_iterator position, size_type n, const value_type& x); 109 template <class Iter> 110 iterator insert(const_iterator position, Iter first, Iter last); 111 iterator insert(const_iterator position, initializer_list<value_type> il); 112 113 iterator erase(const_iterator position); 114 iterator erase(const_iterator position, const_iterator last); 115 116 void resize(size_type sz); 117 void resize(size_type sz, const value_type& c); 118 119 void swap(list&) 120 noexcept(allocator_traits<allocator_type>::is_always_equal::value); // C++17 121 void clear() noexcept; 122 123 void splice(const_iterator position, list& x); 124 void splice(const_iterator position, list&& x); 125 void splice(const_iterator position, list& x, const_iterator i); 126 void splice(const_iterator position, list&& x, const_iterator i); 127 void splice(const_iterator position, list& x, const_iterator first, 128 const_iterator last); 129 void splice(const_iterator position, list&& x, const_iterator first, 130 const_iterator last); 131 132 size_type remove(const value_type& value); // void before C++20 133 template <class Pred> 134 size_type remove_if(Pred pred); // void before C++20 135 size_type unique(); // void before C++20 136 template <class BinaryPredicate> 137 size_type unique(BinaryPredicate binary_pred); // void before C++20 138 void merge(list& x); 139 void merge(list&& x); 140 template <class Compare> 141 void merge(list& x, Compare comp); 142 template <class Compare> 143 void merge(list&& x, Compare comp); 144 void sort(); 145 template <class Compare> 146 void sort(Compare comp); 147 void reverse() noexcept; 148}; 149 150 151template <class InputIterator, class Allocator = allocator<typename iterator_traits<InputIterator>::value_type>> 152 list(InputIterator, InputIterator, Allocator = Allocator()) 153 -> list<typename iterator_traits<InputIterator>::value_type, Allocator>; // C++17 154 155template <class T, class Alloc> 156 bool operator==(const list<T,Alloc>& x, const list<T,Alloc>& y); 157template <class T, class Alloc> 158 bool operator< (const list<T,Alloc>& x, const list<T,Alloc>& y); // removed in C++20 159template <class T, class Alloc> 160 bool operator!=(const list<T,Alloc>& x, const list<T,Alloc>& y); // removed in C++20 161template <class T, class Alloc> 162 bool operator> (const list<T,Alloc>& x, const list<T,Alloc>& y); // removed in C++20 163template <class T, class Alloc> 164 bool operator>=(const list<T,Alloc>& x, const list<T,Alloc>& y); // removed in C++20 165template <class T, class Alloc> 166 bool operator<=(const list<T,Alloc>& x, const list<T,Alloc>& y); // removed in C++20 167template<class T, class Allocator> 168 synth-three-way-result<T> operator<=>(const list<T, Allocator>& x, 169 const list<T, Allocator>& y); // since C++20 170 171template <class T, class Alloc> 172 void swap(list<T,Alloc>& x, list<T,Alloc>& y) 173 noexcept(noexcept(x.swap(y))); 174 175template <class T, class Allocator, class U> 176 typename list<T, Allocator>::size_type 177 erase(list<T, Allocator>& c, const U& value); // since C++20 178template <class T, class Allocator, class Predicate> 179 typename list<T, Allocator>::size_type 180 erase_if(list<T, Allocator>& c, Predicate pred); // since C++20 181 182} // std 183 184*/ 185 186#include <__algorithm/comp.h> 187#include <__algorithm/equal.h> 188#include <__algorithm/lexicographical_compare.h> 189#include <__algorithm/lexicographical_compare_three_way.h> 190#include <__algorithm/min.h> 191#include <__assert> // all public C++ headers provide the assertion handler 192#include <__config> 193#include <__debug> 194#include <__format/enable_insertable.h> 195#include <__iterator/distance.h> 196#include <__iterator/iterator_traits.h> 197#include <__iterator/move_iterator.h> 198#include <__iterator/next.h> 199#include <__iterator/prev.h> 200#include <__iterator/reverse_iterator.h> 201#include <__memory/addressof.h> 202#include <__memory/allocator.h> 203#include <__memory/allocator_destructor.h> 204#include <__memory/allocator_traits.h> 205#include <__memory/compressed_pair.h> 206#include <__memory/pointer_traits.h> 207#include <__memory/swap_allocator.h> 208#include <__memory/unique_ptr.h> 209#include <__memory_resource/polymorphic_allocator.h> 210#include <__type_traits/conditional.h> 211#include <__type_traits/is_allocator.h> 212#include <__type_traits/is_nothrow_default_constructible.h> 213#include <__type_traits/is_nothrow_move_assignable.h> 214#include <__type_traits/is_nothrow_move_constructible.h> 215#include <__type_traits/is_pointer.h> 216#include <__type_traits/is_same.h> 217#include <__type_traits/type_identity.h> 218#include <__utility/forward.h> 219#include <__utility/move.h> 220#include <__utility/swap.h> 221#include <cstring> 222#include <limits> 223#include <version> 224 225// standard-mandated includes 226 227// [iterator.range] 228#include <__iterator/access.h> 229#include <__iterator/data.h> 230#include <__iterator/empty.h> 231#include <__iterator/reverse_access.h> 232#include <__iterator/size.h> 233 234// [list.syn] 235#include <compare> 236#include <initializer_list> 237 238#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) 239# pragma GCC system_header 240#endif 241 242_LIBCPP_PUSH_MACROS 243#include <__undef_macros> 244 245 246_LIBCPP_BEGIN_NAMESPACE_STD 247 248template <class _Tp, class _VoidPtr> struct __list_node; 249template <class _Tp, class _VoidPtr> struct __list_node_base; 250 251template <class _Tp, class _VoidPtr> 252struct __list_node_pointer_traits { 253 typedef __rebind_pointer_t<_VoidPtr, __list_node<_Tp, _VoidPtr> > 254 __node_pointer; 255 typedef __rebind_pointer_t<_VoidPtr, __list_node_base<_Tp, _VoidPtr> > 256 __base_pointer; 257 258#if defined(_LIBCPP_ABI_LIST_REMOVE_NODE_POINTER_UB) 259 typedef __base_pointer __link_pointer; 260#else 261 typedef __conditional_t<is_pointer<_VoidPtr>::value, __base_pointer, __node_pointer> __link_pointer; 262#endif 263 264 typedef __conditional_t<is_same<__link_pointer, __node_pointer>::value, __base_pointer, __node_pointer> 265 __non_link_pointer; 266 267 static _LIBCPP_INLINE_VISIBILITY 268 __link_pointer __unsafe_link_pointer_cast(__link_pointer __p) { 269 return __p; 270 } 271 272 static _LIBCPP_INLINE_VISIBILITY 273 __link_pointer __unsafe_link_pointer_cast(__non_link_pointer __p) { 274 return static_cast<__link_pointer>(static_cast<_VoidPtr>(__p)); 275 } 276 277}; 278 279template <class _Tp, class _VoidPtr> 280struct __list_node_base 281{ 282 typedef __list_node_pointer_traits<_Tp, _VoidPtr> _NodeTraits; 283 typedef typename _NodeTraits::__node_pointer __node_pointer; 284 typedef typename _NodeTraits::__base_pointer __base_pointer; 285 typedef typename _NodeTraits::__link_pointer __link_pointer; 286 287 __link_pointer __prev_; 288 __link_pointer __next_; 289 290 _LIBCPP_INLINE_VISIBILITY 291 __list_node_base() : __prev_(_NodeTraits::__unsafe_link_pointer_cast(__self())), 292 __next_(_NodeTraits::__unsafe_link_pointer_cast(__self())) {} 293 294 _LIBCPP_INLINE_VISIBILITY 295 __base_pointer __self() { 296 return pointer_traits<__base_pointer>::pointer_to(*this); 297 } 298 299 _LIBCPP_INLINE_VISIBILITY 300 __node_pointer __as_node() { 301 return static_cast<__node_pointer>(__self()); 302 } 303}; 304 305template <class _Tp, class _VoidPtr> 306struct _LIBCPP_STANDALONE_DEBUG __list_node 307 : public __list_node_base<_Tp, _VoidPtr> 308{ 309 _Tp __value_; 310 311 typedef __list_node_base<_Tp, _VoidPtr> __base; 312 typedef typename __base::__link_pointer __link_pointer; 313 314 _LIBCPP_INLINE_VISIBILITY 315 __link_pointer __as_link() { 316 return static_cast<__link_pointer>(__base::__self()); 317 } 318}; 319 320template <class _Tp, class _Alloc = allocator<_Tp> > class _LIBCPP_TEMPLATE_VIS list; 321template <class _Tp, class _Alloc> class __list_imp; 322template <class _Tp, class _VoidPtr> class _LIBCPP_TEMPLATE_VIS __list_const_iterator; 323 324template <class _Tp, class _VoidPtr> 325class _LIBCPP_TEMPLATE_VIS __list_iterator 326{ 327 typedef __list_node_pointer_traits<_Tp, _VoidPtr> _NodeTraits; 328 typedef typename _NodeTraits::__link_pointer __link_pointer; 329 330 __link_pointer __ptr_; 331 332 _LIBCPP_INLINE_VISIBILITY 333 explicit __list_iterator(__link_pointer __p, const void* __c) _NOEXCEPT 334 : __ptr_(__p) 335 { 336 (void)__c; 337#ifdef _LIBCPP_ENABLE_DEBUG_MODE 338 __get_db()->__insert_ic(this, __c); 339#endif 340 } 341 342 template<class, class> friend class list; 343 template<class, class> friend class __list_imp; 344 template<class, class> friend class __list_const_iterator; 345public: 346 typedef bidirectional_iterator_tag iterator_category; 347 typedef _Tp value_type; 348 typedef value_type& reference; 349 typedef __rebind_pointer_t<_VoidPtr, value_type> pointer; 350 typedef typename pointer_traits<pointer>::difference_type difference_type; 351 352 _LIBCPP_INLINE_VISIBILITY 353 __list_iterator() _NOEXCEPT : __ptr_(nullptr) 354 { 355 _VSTD::__debug_db_insert_i(this); 356 } 357 358#ifdef _LIBCPP_ENABLE_DEBUG_MODE 359 360 _LIBCPP_INLINE_VISIBILITY 361 __list_iterator(const __list_iterator& __p) 362 : __ptr_(__p.__ptr_) 363 { 364 __get_db()->__iterator_copy(this, _VSTD::addressof(__p)); 365 } 366 367 _LIBCPP_INLINE_VISIBILITY 368 ~__list_iterator() 369 { 370 __get_db()->__erase_i(this); 371 } 372 373 _LIBCPP_INLINE_VISIBILITY 374 __list_iterator& operator=(const __list_iterator& __p) 375 { 376 if (this != _VSTD::addressof(__p)) 377 { 378 __get_db()->__iterator_copy(this, _VSTD::addressof(__p)); 379 __ptr_ = __p.__ptr_; 380 } 381 return *this; 382 } 383 384#endif // _LIBCPP_ENABLE_DEBUG_MODE 385 386 _LIBCPP_INLINE_VISIBILITY 387 reference operator*() const 388 { 389 _LIBCPP_DEBUG_ASSERT(__get_const_db()->__dereferenceable(this), 390 "Attempted to dereference a non-dereferenceable list::iterator"); 391 return __ptr_->__as_node()->__value_; 392 } 393 _LIBCPP_INLINE_VISIBILITY 394 pointer operator->() const 395 { 396 _LIBCPP_DEBUG_ASSERT(__get_const_db()->__dereferenceable(this), 397 "Attempted to dereference a non-dereferenceable list::iterator"); 398 return pointer_traits<pointer>::pointer_to(__ptr_->__as_node()->__value_); 399 } 400 401 _LIBCPP_INLINE_VISIBILITY 402 __list_iterator& operator++() 403 { 404 _LIBCPP_DEBUG_ASSERT(__get_const_db()->__dereferenceable(this), 405 "Attempted to increment a non-incrementable list::iterator"); 406 __ptr_ = __ptr_->__next_; 407 return *this; 408 } 409 _LIBCPP_INLINE_VISIBILITY 410 __list_iterator operator++(int) {__list_iterator __t(*this); ++(*this); return __t;} 411 412 _LIBCPP_INLINE_VISIBILITY 413 __list_iterator& operator--() 414 { 415 _LIBCPP_DEBUG_ASSERT(__get_const_db()->__decrementable(this), 416 "Attempted to decrement a non-decrementable list::iterator"); 417 __ptr_ = __ptr_->__prev_; 418 return *this; 419 } 420 _LIBCPP_INLINE_VISIBILITY 421 __list_iterator operator--(int) {__list_iterator __t(*this); --(*this); return __t;} 422 423 friend _LIBCPP_INLINE_VISIBILITY 424 bool operator==(const __list_iterator& __x, const __list_iterator& __y) 425 { 426 return __x.__ptr_ == __y.__ptr_; 427 } 428 friend _LIBCPP_INLINE_VISIBILITY 429 bool operator!=(const __list_iterator& __x, const __list_iterator& __y) 430 {return !(__x == __y);} 431}; 432 433template <class _Tp, class _VoidPtr> 434class _LIBCPP_TEMPLATE_VIS __list_const_iterator 435{ 436 typedef __list_node_pointer_traits<_Tp, _VoidPtr> _NodeTraits; 437 typedef typename _NodeTraits::__link_pointer __link_pointer; 438 439 __link_pointer __ptr_; 440 441 _LIBCPP_INLINE_VISIBILITY 442 explicit __list_const_iterator(__link_pointer __p, const void* __c) _NOEXCEPT 443 : __ptr_(__p) 444 { 445 (void)__c; 446#ifdef _LIBCPP_ENABLE_DEBUG_MODE 447 __get_db()->__insert_ic(this, __c); 448#endif 449 } 450 451 template<class, class> friend class list; 452 template<class, class> friend class __list_imp; 453public: 454 typedef bidirectional_iterator_tag iterator_category; 455 typedef _Tp value_type; 456 typedef const value_type& reference; 457 typedef __rebind_pointer_t<_VoidPtr, const value_type> pointer; 458 typedef typename pointer_traits<pointer>::difference_type difference_type; 459 460 _LIBCPP_INLINE_VISIBILITY 461 __list_const_iterator() _NOEXCEPT : __ptr_(nullptr) 462 { 463 _VSTD::__debug_db_insert_i(this); 464 } 465 _LIBCPP_INLINE_VISIBILITY 466 __list_const_iterator(const __list_iterator<_Tp, _VoidPtr>& __p) _NOEXCEPT 467 : __ptr_(__p.__ptr_) 468 { 469#ifdef _LIBCPP_ENABLE_DEBUG_MODE 470 __get_db()->__iterator_copy(this, _VSTD::addressof(__p)); 471#endif 472 } 473 474#ifdef _LIBCPP_ENABLE_DEBUG_MODE 475 476 _LIBCPP_INLINE_VISIBILITY 477 __list_const_iterator(const __list_const_iterator& __p) 478 : __ptr_(__p.__ptr_) 479 { 480 __get_db()->__iterator_copy(this, _VSTD::addressof(__p)); 481 } 482 483 _LIBCPP_INLINE_VISIBILITY 484 ~__list_const_iterator() 485 { 486 __get_db()->__erase_i(this); 487 } 488 489 _LIBCPP_INLINE_VISIBILITY 490 __list_const_iterator& operator=(const __list_const_iterator& __p) 491 { 492 if (this != _VSTD::addressof(__p)) 493 { 494 __get_db()->__iterator_copy(this, _VSTD::addressof(__p)); 495 __ptr_ = __p.__ptr_; 496 } 497 return *this; 498 } 499 500#endif // _LIBCPP_ENABLE_DEBUG_MODE 501 _LIBCPP_INLINE_VISIBILITY 502 reference operator*() const 503 { 504 _LIBCPP_DEBUG_ASSERT(__get_const_db()->__dereferenceable(this), 505 "Attempted to dereference a non-dereferenceable list::const_iterator"); 506 return __ptr_->__as_node()->__value_; 507 } 508 _LIBCPP_INLINE_VISIBILITY 509 pointer operator->() const 510 { 511 _LIBCPP_DEBUG_ASSERT(__get_const_db()->__dereferenceable(this), 512 "Attempted to dereference a non-dereferenceable list::const_iterator"); 513 return pointer_traits<pointer>::pointer_to(__ptr_->__as_node()->__value_); 514 } 515 516 _LIBCPP_INLINE_VISIBILITY 517 __list_const_iterator& operator++() 518 { 519 _LIBCPP_DEBUG_ASSERT(__get_const_db()->__dereferenceable(this), 520 "Attempted to increment a non-incrementable list::const_iterator"); 521 __ptr_ = __ptr_->__next_; 522 return *this; 523 } 524 _LIBCPP_INLINE_VISIBILITY 525 __list_const_iterator operator++(int) {__list_const_iterator __t(*this); ++(*this); return __t;} 526 527 _LIBCPP_INLINE_VISIBILITY 528 __list_const_iterator& operator--() 529 { 530 _LIBCPP_DEBUG_ASSERT(__get_const_db()->__decrementable(this), 531 "Attempted to decrement a non-decrementable list::const_iterator"); 532 __ptr_ = __ptr_->__prev_; 533 return *this; 534 } 535 _LIBCPP_INLINE_VISIBILITY 536 __list_const_iterator operator--(int) {__list_const_iterator __t(*this); --(*this); return __t;} 537 538 friend _LIBCPP_INLINE_VISIBILITY 539 bool operator==(const __list_const_iterator& __x, const __list_const_iterator& __y) 540 { 541 return __x.__ptr_ == __y.__ptr_; 542 } 543 friend _LIBCPP_INLINE_VISIBILITY 544 bool operator!=(const __list_const_iterator& __x, const __list_const_iterator& __y) 545 {return !(__x == __y);} 546}; 547 548template <class _Tp, class _Alloc> 549class __list_imp 550{ 551 __list_imp(const __list_imp&); 552 __list_imp& operator=(const __list_imp&); 553public: 554 typedef _Alloc allocator_type; 555 typedef allocator_traits<allocator_type> __alloc_traits; 556 typedef typename __alloc_traits::size_type size_type; 557protected: 558 typedef _Tp value_type; 559 typedef typename __alloc_traits::void_pointer __void_pointer; 560 typedef __list_iterator<value_type, __void_pointer> iterator; 561 typedef __list_const_iterator<value_type, __void_pointer> const_iterator; 562 typedef __list_node_base<value_type, __void_pointer> __node_base; 563 typedef __list_node<value_type, __void_pointer> __node; 564 typedef __rebind_alloc<__alloc_traits, __node> __node_allocator; 565 typedef allocator_traits<__node_allocator> __node_alloc_traits; 566 typedef typename __node_alloc_traits::pointer __node_pointer; 567 typedef typename __node_alloc_traits::pointer __node_const_pointer; 568 typedef __list_node_pointer_traits<value_type, __void_pointer> __node_pointer_traits; 569 typedef typename __node_pointer_traits::__link_pointer __link_pointer; 570 typedef __link_pointer __link_const_pointer; 571 typedef typename __alloc_traits::pointer pointer; 572 typedef typename __alloc_traits::const_pointer const_pointer; 573 typedef typename __alloc_traits::difference_type difference_type; 574 575 typedef __rebind_alloc<__alloc_traits, __node_base> __node_base_allocator; 576 typedef typename allocator_traits<__node_base_allocator>::pointer __node_base_pointer; 577 static_assert((!is_same<allocator_type, __node_allocator>::value), 578 "internal allocator type must differ from user-specified " 579 "type; otherwise overload resolution breaks"); 580 581 __node_base __end_; 582 __compressed_pair<size_type, __node_allocator> __size_alloc_; 583 584 _LIBCPP_INLINE_VISIBILITY 585 __link_pointer __end_as_link() const _NOEXCEPT { 586 return __node_pointer_traits::__unsafe_link_pointer_cast( 587 const_cast<__node_base&>(__end_).__self()); 588 } 589 590 _LIBCPP_INLINE_VISIBILITY 591 size_type& __sz() _NOEXCEPT {return __size_alloc_.first();} 592 _LIBCPP_INLINE_VISIBILITY 593 const size_type& __sz() const _NOEXCEPT 594 {return __size_alloc_.first();} 595 _LIBCPP_INLINE_VISIBILITY 596 __node_allocator& __node_alloc() _NOEXCEPT 597 {return __size_alloc_.second();} 598 _LIBCPP_INLINE_VISIBILITY 599 const __node_allocator& __node_alloc() const _NOEXCEPT 600 {return __size_alloc_.second();} 601 602 _LIBCPP_INLINE_VISIBILITY 603 size_type __node_alloc_max_size() const _NOEXCEPT { 604 return __node_alloc_traits::max_size(__node_alloc()); 605 } 606 _LIBCPP_INLINE_VISIBILITY 607 static void __unlink_nodes(__link_pointer __f, __link_pointer __l) _NOEXCEPT; 608 609 _LIBCPP_INLINE_VISIBILITY 610 __list_imp() 611 _NOEXCEPT_(is_nothrow_default_constructible<__node_allocator>::value); 612 _LIBCPP_INLINE_VISIBILITY 613 __list_imp(const allocator_type& __a); 614 _LIBCPP_INLINE_VISIBILITY 615 __list_imp(const __node_allocator& __a); 616#ifndef _LIBCPP_CXX03_LANG 617 _LIBCPP_HIDE_FROM_ABI __list_imp(__node_allocator&& __a) _NOEXCEPT; 618#endif 619 _LIBCPP_HIDE_FROM_ABI ~__list_imp(); 620 _LIBCPP_HIDE_FROM_ABI void clear() _NOEXCEPT; 621 _LIBCPP_INLINE_VISIBILITY 622 bool empty() const _NOEXCEPT {return __sz() == 0;} 623 624 _LIBCPP_INLINE_VISIBILITY 625 iterator begin() _NOEXCEPT 626 { 627 return iterator(__end_.__next_, this); 628 } 629 _LIBCPP_INLINE_VISIBILITY 630 const_iterator begin() const _NOEXCEPT 631 { 632 return const_iterator(__end_.__next_, this); 633 } 634 _LIBCPP_INLINE_VISIBILITY 635 iterator end() _NOEXCEPT 636 { 637 return iterator(__end_as_link(), this); 638 } 639 _LIBCPP_INLINE_VISIBILITY 640 const_iterator end() const _NOEXCEPT 641 { 642 return const_iterator(__end_as_link(), this); 643 } 644 645 _LIBCPP_HIDE_FROM_ABI void swap(__list_imp& __c) 646#if _LIBCPP_STD_VER >= 14 647 _NOEXCEPT; 648#else 649 _NOEXCEPT_(!__alloc_traits::propagate_on_container_swap::value || 650 __is_nothrow_swappable<allocator_type>::value); 651#endif 652 653 _LIBCPP_INLINE_VISIBILITY 654 void __copy_assign_alloc(const __list_imp& __c) 655 {__copy_assign_alloc(__c, integral_constant<bool, 656 __node_alloc_traits::propagate_on_container_copy_assignment::value>());} 657 658 _LIBCPP_INLINE_VISIBILITY 659 void __move_assign_alloc(__list_imp& __c) 660 _NOEXCEPT_( 661 !__node_alloc_traits::propagate_on_container_move_assignment::value || 662 is_nothrow_move_assignable<__node_allocator>::value) 663 {__move_assign_alloc(__c, integral_constant<bool, 664 __node_alloc_traits::propagate_on_container_move_assignment::value>());} 665 666private: 667 _LIBCPP_INLINE_VISIBILITY 668 void __copy_assign_alloc(const __list_imp& __c, true_type) 669 { 670 if (__node_alloc() != __c.__node_alloc()) 671 clear(); 672 __node_alloc() = __c.__node_alloc(); 673 } 674 675 _LIBCPP_INLINE_VISIBILITY 676 void __copy_assign_alloc(const __list_imp&, false_type) 677 {} 678 679 _LIBCPP_INLINE_VISIBILITY 680 void __move_assign_alloc(__list_imp& __c, true_type) 681 _NOEXCEPT_(is_nothrow_move_assignable<__node_allocator>::value) 682 { 683 __node_alloc() = _VSTD::move(__c.__node_alloc()); 684 } 685 686 _LIBCPP_INLINE_VISIBILITY 687 void __move_assign_alloc(__list_imp&, false_type) 688 _NOEXCEPT 689 {} 690}; 691 692// Unlink nodes [__f, __l] 693template <class _Tp, class _Alloc> 694inline 695void 696__list_imp<_Tp, _Alloc>::__unlink_nodes(__link_pointer __f, __link_pointer __l) 697 _NOEXCEPT 698{ 699 __f->__prev_->__next_ = __l->__next_; 700 __l->__next_->__prev_ = __f->__prev_; 701} 702 703template <class _Tp, class _Alloc> 704inline 705__list_imp<_Tp, _Alloc>::__list_imp() 706 _NOEXCEPT_(is_nothrow_default_constructible<__node_allocator>::value) 707 : __size_alloc_(0, __default_init_tag()) 708{ 709} 710 711template <class _Tp, class _Alloc> 712inline 713__list_imp<_Tp, _Alloc>::__list_imp(const allocator_type& __a) 714 : __size_alloc_(0, __node_allocator(__a)) 715{ 716} 717 718template <class _Tp, class _Alloc> 719inline __list_imp<_Tp, _Alloc>::__list_imp(const __node_allocator& __a) 720 : __size_alloc_(0, __a) {} 721 722#ifndef _LIBCPP_CXX03_LANG 723template <class _Tp, class _Alloc> 724inline __list_imp<_Tp, _Alloc>::__list_imp(__node_allocator&& __a) _NOEXCEPT 725 : __size_alloc_(0, _VSTD::move(__a)) {} 726#endif 727 728template <class _Tp, class _Alloc> 729__list_imp<_Tp, _Alloc>::~__list_imp() { 730 clear(); 731 std::__debug_db_erase_c(this); 732} 733 734template <class _Tp, class _Alloc> 735void 736__list_imp<_Tp, _Alloc>::clear() _NOEXCEPT 737{ 738 if (!empty()) 739 { 740 __node_allocator& __na = __node_alloc(); 741 __link_pointer __f = __end_.__next_; 742 __link_pointer __l = __end_as_link(); 743 __unlink_nodes(__f, __l->__prev_); 744 __sz() = 0; 745 while (__f != __l) 746 { 747 __node_pointer __np = __f->__as_node(); 748 __f = __f->__next_; 749 __node_alloc_traits::destroy(__na, _VSTD::addressof(__np->__value_)); 750 __node_alloc_traits::deallocate(__na, __np, 1); 751 } 752 std::__debug_db_invalidate_all(this); 753 } 754} 755 756template <class _Tp, class _Alloc> 757void 758__list_imp<_Tp, _Alloc>::swap(__list_imp& __c) 759#if _LIBCPP_STD_VER >= 14 760 _NOEXCEPT 761#else 762 _NOEXCEPT_(!__alloc_traits::propagate_on_container_swap::value || 763 __is_nothrow_swappable<allocator_type>::value) 764#endif 765{ 766 _LIBCPP_ASSERT(__alloc_traits::propagate_on_container_swap::value || 767 this->__node_alloc() == __c.__node_alloc(), 768 "list::swap: Either propagate_on_container_swap must be true" 769 " or the allocators must compare equal"); 770 using _VSTD::swap; 771 _VSTD::__swap_allocator(__node_alloc(), __c.__node_alloc()); 772 swap(__sz(), __c.__sz()); 773 swap(__end_, __c.__end_); 774 if (__sz() == 0) 775 __end_.__next_ = __end_.__prev_ = __end_as_link(); 776 else 777 __end_.__prev_->__next_ = __end_.__next_->__prev_ = __end_as_link(); 778 if (__c.__sz() == 0) 779 __c.__end_.__next_ = __c.__end_.__prev_ = __c.__end_as_link(); 780 else 781 __c.__end_.__prev_->__next_ = __c.__end_.__next_->__prev_ = __c.__end_as_link(); 782 783#ifdef _LIBCPP_ENABLE_DEBUG_MODE 784 __libcpp_db* __db = __get_db(); 785 __c_node* __cn1 = __db->__find_c_and_lock(this); 786 __c_node* __cn2 = __db->__find_c(_VSTD::addressof(__c)); 787 _VSTD::swap(__cn1->beg_, __cn2->beg_); 788 _VSTD::swap(__cn1->end_, __cn2->end_); 789 _VSTD::swap(__cn1->cap_, __cn2->cap_); 790 for (__i_node** __p = __cn1->end_; __p != __cn1->beg_;) 791 { 792 --__p; 793 const_iterator* __i = static_cast<const_iterator*>((*__p)->__i_); 794 if (__i->__ptr_ == __c.__end_as_link()) 795 { 796 __cn2->__add(*__p); 797 if (--__cn1->end_ != __p) 798 _VSTD::memmove(__p, __p+1, (__cn1->end_ - __p)*sizeof(__i_node*)); 799 } 800 else 801 (*__p)->__c_ = __cn1; 802 } 803 for (__i_node** __p = __cn2->end_; __p != __cn2->beg_;) 804 { 805 --__p; 806 const_iterator* __i = static_cast<const_iterator*>((*__p)->__i_); 807 if (__i->__ptr_ == __end_as_link()) 808 { 809 __cn1->__add(*__p); 810 if (--__cn2->end_ != __p) 811 _VSTD::memmove(__p, __p+1, (__cn2->end_ - __p)*sizeof(__i_node*)); 812 } 813 else 814 (*__p)->__c_ = __cn2; 815 } 816 __db->unlock(); 817#endif 818} 819 820template <class _Tp, class _Alloc /*= allocator<_Tp>*/> 821class _LIBCPP_TEMPLATE_VIS list 822 : private __list_imp<_Tp, _Alloc> 823{ 824 typedef __list_imp<_Tp, _Alloc> base; 825 typedef typename base::__node __node; 826 typedef typename base::__node_allocator __node_allocator; 827 typedef typename base::__node_pointer __node_pointer; 828 typedef typename base::__node_alloc_traits __node_alloc_traits; 829 typedef typename base::__node_base __node_base; 830 typedef typename base::__node_base_pointer __node_base_pointer; 831 typedef typename base::__link_pointer __link_pointer; 832 833public: 834 typedef _Tp value_type; 835 typedef _Alloc allocator_type; 836 static_assert((is_same<value_type, typename allocator_type::value_type>::value), 837 "Allocator::value_type must be same type as value_type"); 838 typedef value_type& reference; 839 typedef const value_type& const_reference; 840 typedef typename base::pointer pointer; 841 typedef typename base::const_pointer const_pointer; 842 typedef typename base::size_type size_type; 843 typedef typename base::difference_type difference_type; 844 typedef typename base::iterator iterator; 845 typedef typename base::const_iterator const_iterator; 846 typedef _VSTD::reverse_iterator<iterator> reverse_iterator; 847 typedef _VSTD::reverse_iterator<const_iterator> const_reverse_iterator; 848#if _LIBCPP_STD_VER >= 20 849 typedef size_type __remove_return_type; 850#else 851 typedef void __remove_return_type; 852#endif 853 854 static_assert(is_same<allocator_type, __rebind_alloc<allocator_traits<allocator_type>, value_type> >::value, 855 "[allocator.requirements] states that rebinding an allocator to the same type should result in the " 856 "original allocator"); 857 858 _LIBCPP_INLINE_VISIBILITY 859 list() 860 _NOEXCEPT_(is_nothrow_default_constructible<__node_allocator>::value) 861 { 862 _VSTD::__debug_db_insert_c(this); 863 } 864 _LIBCPP_INLINE_VISIBILITY 865 explicit list(const allocator_type& __a) : base(__a) 866 { 867 _VSTD::__debug_db_insert_c(this); 868 } 869 _LIBCPP_HIDE_FROM_ABI explicit list(size_type __n); 870#if _LIBCPP_STD_VER >= 14 871 _LIBCPP_HIDE_FROM_ABI explicit list(size_type __n, const allocator_type& __a); 872#endif 873 _LIBCPP_HIDE_FROM_ABI list(size_type __n, const value_type& __x); 874 template <class = __enable_if_t<__is_allocator<_Alloc>::value> > 875 _LIBCPP_HIDE_FROM_ABI list(size_type __n, const value_type& __x, const allocator_type& __a) : base(__a) 876 { 877 _VSTD::__debug_db_insert_c(this); 878 for (; __n > 0; --__n) 879 push_back(__x); 880 } 881 882 template <class _InpIter> 883 _LIBCPP_HIDE_FROM_ABI list(_InpIter __f, _InpIter __l, 884 __enable_if_t<__is_cpp17_input_iterator<_InpIter>::value>* = 0); 885 template <class _InpIter> 886 _LIBCPP_HIDE_FROM_ABI list(_InpIter __f, _InpIter __l, const allocator_type& __a, 887 __enable_if_t<__is_cpp17_input_iterator<_InpIter>::value>* = 0); 888 889 _LIBCPP_HIDE_FROM_ABI list(const list& __c); 890 _LIBCPP_HIDE_FROM_ABI list(const list& __c, const __type_identity_t<allocator_type>& __a); 891 _LIBCPP_INLINE_VISIBILITY 892 list& operator=(const list& __c); 893#ifndef _LIBCPP_CXX03_LANG 894 _LIBCPP_HIDE_FROM_ABI list(initializer_list<value_type> __il); 895 _LIBCPP_HIDE_FROM_ABI list(initializer_list<value_type> __il, const allocator_type& __a); 896 897 _LIBCPP_INLINE_VISIBILITY 898 list(list&& __c) 899 _NOEXCEPT_(is_nothrow_move_constructible<__node_allocator>::value); 900 _LIBCPP_INLINE_VISIBILITY 901 list(list&& __c, const __type_identity_t<allocator_type>& __a); 902 _LIBCPP_INLINE_VISIBILITY 903 list& operator=(list&& __c) 904 _NOEXCEPT_( 905 __node_alloc_traits::propagate_on_container_move_assignment::value && 906 is_nothrow_move_assignable<__node_allocator>::value); 907 908 _LIBCPP_INLINE_VISIBILITY 909 list& operator=(initializer_list<value_type> __il) 910 {assign(__il.begin(), __il.end()); return *this;} 911 912 _LIBCPP_INLINE_VISIBILITY 913 void assign(initializer_list<value_type> __il) 914 {assign(__il.begin(), __il.end());} 915#endif // _LIBCPP_CXX03_LANG 916 917 template <class _InpIter> 918 _LIBCPP_HIDE_FROM_ABI void assign(_InpIter __f, _InpIter __l, 919 __enable_if_t<__is_cpp17_input_iterator<_InpIter>::value>* = 0); 920 _LIBCPP_HIDE_FROM_ABI void assign(size_type __n, const value_type& __x); 921 922 _LIBCPP_INLINE_VISIBILITY 923 allocator_type get_allocator() const _NOEXCEPT; 924 925 _LIBCPP_INLINE_VISIBILITY 926 size_type size() const _NOEXCEPT {return base::__sz();} 927 _LIBCPP_NODISCARD_AFTER_CXX17 _LIBCPP_INLINE_VISIBILITY 928 bool empty() const _NOEXCEPT {return base::empty();} 929 _LIBCPP_INLINE_VISIBILITY 930 size_type max_size() const _NOEXCEPT 931 { 932 return _VSTD::min<size_type>( 933 base::__node_alloc_max_size(), 934 numeric_limits<difference_type >::max()); 935 } 936 937 _LIBCPP_INLINE_VISIBILITY 938 iterator begin() _NOEXCEPT {return base::begin();} 939 _LIBCPP_INLINE_VISIBILITY 940 const_iterator begin() const _NOEXCEPT {return base::begin();} 941 _LIBCPP_INLINE_VISIBILITY 942 iterator end() _NOEXCEPT {return base::end();} 943 _LIBCPP_INLINE_VISIBILITY 944 const_iterator end() const _NOEXCEPT {return base::end();} 945 _LIBCPP_INLINE_VISIBILITY 946 const_iterator cbegin() const _NOEXCEPT {return base::begin();} 947 _LIBCPP_INLINE_VISIBILITY 948 const_iterator cend() const _NOEXCEPT {return base::end();} 949 950 _LIBCPP_INLINE_VISIBILITY 951 reverse_iterator rbegin() _NOEXCEPT 952 {return reverse_iterator(end());} 953 _LIBCPP_INLINE_VISIBILITY 954 const_reverse_iterator rbegin() const _NOEXCEPT 955 {return const_reverse_iterator(end());} 956 _LIBCPP_INLINE_VISIBILITY 957 reverse_iterator rend() _NOEXCEPT 958 {return reverse_iterator(begin());} 959 _LIBCPP_INLINE_VISIBILITY 960 const_reverse_iterator rend() const _NOEXCEPT 961 {return const_reverse_iterator(begin());} 962 _LIBCPP_INLINE_VISIBILITY 963 const_reverse_iterator crbegin() const _NOEXCEPT 964 {return const_reverse_iterator(end());} 965 _LIBCPP_INLINE_VISIBILITY 966 const_reverse_iterator crend() const _NOEXCEPT 967 {return const_reverse_iterator(begin());} 968 969 _LIBCPP_INLINE_VISIBILITY 970 reference front() 971 { 972 _LIBCPP_ASSERT(!empty(), "list::front called on empty list"); 973 return base::__end_.__next_->__as_node()->__value_; 974 } 975 _LIBCPP_INLINE_VISIBILITY 976 const_reference front() const 977 { 978 _LIBCPP_ASSERT(!empty(), "list::front called on empty list"); 979 return base::__end_.__next_->__as_node()->__value_; 980 } 981 _LIBCPP_INLINE_VISIBILITY 982 reference back() 983 { 984 _LIBCPP_ASSERT(!empty(), "list::back called on empty list"); 985 return base::__end_.__prev_->__as_node()->__value_; 986 } 987 _LIBCPP_INLINE_VISIBILITY 988 const_reference back() const 989 { 990 _LIBCPP_ASSERT(!empty(), "list::back called on empty list"); 991 return base::__end_.__prev_->__as_node()->__value_; 992 } 993 994#ifndef _LIBCPP_CXX03_LANG 995 _LIBCPP_HIDE_FROM_ABI void push_front(value_type&& __x); 996 _LIBCPP_HIDE_FROM_ABI void push_back(value_type&& __x); 997 998 template <class... _Args> 999#if _LIBCPP_STD_VER >= 17 1000 _LIBCPP_HIDE_FROM_ABI reference emplace_front(_Args&&... __args); 1001#else 1002 _LIBCPP_HIDE_FROM_ABI void emplace_front(_Args&&... __args); 1003#endif 1004 template <class... _Args> 1005#if _LIBCPP_STD_VER >= 17 1006 _LIBCPP_HIDE_FROM_ABI reference emplace_back(_Args&&... __args); 1007#else 1008 _LIBCPP_HIDE_FROM_ABI void emplace_back(_Args&&... __args); 1009#endif 1010 template <class... _Args> 1011 _LIBCPP_HIDE_FROM_ABI iterator emplace(const_iterator __p, _Args&&... __args); 1012 1013 _LIBCPP_HIDE_FROM_ABI iterator insert(const_iterator __p, value_type&& __x); 1014 1015 _LIBCPP_INLINE_VISIBILITY 1016 iterator insert(const_iterator __p, initializer_list<value_type> __il) 1017 {return insert(__p, __il.begin(), __il.end());} 1018#endif // _LIBCPP_CXX03_LANG 1019 1020 _LIBCPP_HIDE_FROM_ABI void push_front(const value_type& __x); 1021 _LIBCPP_HIDE_FROM_ABI void push_back(const value_type& __x); 1022 1023#ifndef _LIBCPP_CXX03_LANG 1024 template <class _Arg> 1025 _LIBCPP_INLINE_VISIBILITY 1026 void __emplace_back(_Arg&& __arg) { emplace_back(_VSTD::forward<_Arg>(__arg)); } 1027#else 1028 _LIBCPP_INLINE_VISIBILITY 1029 void __emplace_back(value_type const& __arg) { push_back(__arg); } 1030#endif 1031 1032 _LIBCPP_HIDE_FROM_ABI iterator insert(const_iterator __p, const value_type& __x); 1033 _LIBCPP_HIDE_FROM_ABI iterator insert(const_iterator __p, size_type __n, const value_type& __x); 1034 template <class _InpIter> 1035 _LIBCPP_HIDE_FROM_ABI iterator insert(const_iterator __p, _InpIter __f, _InpIter __l, 1036 __enable_if_t<__is_cpp17_input_iterator<_InpIter>::value>* = 0); 1037 1038 _LIBCPP_INLINE_VISIBILITY 1039 void swap(list& __c) 1040#if _LIBCPP_STD_VER >= 14 1041 _NOEXCEPT 1042#else 1043 _NOEXCEPT_(!__node_alloc_traits::propagate_on_container_swap::value || 1044 __is_nothrow_swappable<__node_allocator>::value) 1045#endif 1046 {base::swap(__c);} 1047 _LIBCPP_INLINE_VISIBILITY 1048 void clear() _NOEXCEPT {base::clear();} 1049 1050 _LIBCPP_HIDE_FROM_ABI void pop_front(); 1051 _LIBCPP_HIDE_FROM_ABI void pop_back(); 1052 1053 _LIBCPP_HIDE_FROM_ABI iterator erase(const_iterator __p); 1054 _LIBCPP_HIDE_FROM_ABI iterator erase(const_iterator __f, const_iterator __l); 1055 1056 _LIBCPP_HIDE_FROM_ABI void resize(size_type __n); 1057 _LIBCPP_HIDE_FROM_ABI void resize(size_type __n, const value_type& __x); 1058 1059 _LIBCPP_HIDE_FROM_ABI void splice(const_iterator __p, list& __c); 1060#ifndef _LIBCPP_CXX03_LANG 1061 _LIBCPP_INLINE_VISIBILITY 1062 void splice(const_iterator __p, list&& __c) {splice(__p, __c);} 1063 _LIBCPP_INLINE_VISIBILITY 1064 void splice(const_iterator __p, list&& __c, const_iterator __i) 1065 {splice(__p, __c, __i);} 1066 _LIBCPP_INLINE_VISIBILITY 1067 void splice(const_iterator __p, list&& __c, const_iterator __f, const_iterator __l) 1068 {splice(__p, __c, __f, __l);} 1069#endif 1070 _LIBCPP_HIDE_FROM_ABI void splice(const_iterator __p, list& __c, const_iterator __i); 1071 _LIBCPP_HIDE_FROM_ABI void splice(const_iterator __p, list& __c, const_iterator __f, const_iterator __l); 1072 1073 _LIBCPP_HIDE_FROM_ABI __remove_return_type remove(const value_type& __x); 1074 template <class _Pred> 1075 _LIBCPP_HIDE_FROM_ABI __remove_return_type remove_if(_Pred __pred); 1076 _LIBCPP_INLINE_VISIBILITY 1077 __remove_return_type unique() { return unique(__equal_to()); } 1078 template <class _BinaryPred> 1079 _LIBCPP_HIDE_FROM_ABI __remove_return_type unique(_BinaryPred __binary_pred); 1080 _LIBCPP_INLINE_VISIBILITY 1081 void merge(list& __c); 1082#ifndef _LIBCPP_CXX03_LANG 1083 _LIBCPP_INLINE_VISIBILITY 1084 void merge(list&& __c) {merge(__c);} 1085 1086 template <class _Comp> 1087 _LIBCPP_INLINE_VISIBILITY 1088 void merge(list&& __c, _Comp __comp) {merge(__c, __comp);} 1089#endif 1090 template <class _Comp> 1091 _LIBCPP_HIDE_FROM_ABI void merge(list& __c, _Comp __comp); 1092 1093 _LIBCPP_INLINE_VISIBILITY 1094 void sort(); 1095 template <class _Comp> 1096 _LIBCPP_INLINE_VISIBILITY 1097 void sort(_Comp __comp); 1098 1099 _LIBCPP_HIDE_FROM_ABI void reverse() _NOEXCEPT; 1100 1101 _LIBCPP_HIDE_FROM_ABI bool __invariants() const; 1102 1103 typedef __allocator_destructor<__node_allocator> __node_destructor; 1104 typedef unique_ptr<__node, __node_destructor> __hold_pointer; 1105 1106 _LIBCPP_INLINE_VISIBILITY 1107 __hold_pointer __allocate_node(__node_allocator& __na) { 1108 __node_pointer __p = __node_alloc_traits::allocate(__na, 1); 1109 __p->__prev_ = nullptr; 1110 return __hold_pointer(__p, __node_destructor(__na, 1)); 1111 } 1112 1113#ifdef _LIBCPP_ENABLE_DEBUG_MODE 1114 1115 bool __dereferenceable(const const_iterator* __i) const; 1116 bool __decrementable(const const_iterator* __i) const; 1117 bool __addable(const const_iterator* __i, ptrdiff_t __n) const; 1118 bool __subscriptable(const const_iterator* __i, ptrdiff_t __n) const; 1119 1120#endif // _LIBCPP_ENABLE_DEBUG_MODE 1121 1122private: 1123 _LIBCPP_INLINE_VISIBILITY 1124 static void __link_nodes (__link_pointer __p, __link_pointer __f, __link_pointer __l); 1125 _LIBCPP_INLINE_VISIBILITY 1126 void __link_nodes_at_front(__link_pointer __f, __link_pointer __l); 1127 _LIBCPP_INLINE_VISIBILITY 1128 void __link_nodes_at_back (__link_pointer __f, __link_pointer __l); 1129 _LIBCPP_HIDE_FROM_ABI iterator __iterator(size_type __n); 1130 // TODO: Make this _LIBCPP_HIDE_FROM_ABI 1131 template <class _Comp> 1132 _LIBCPP_HIDDEN static iterator __sort(iterator __f1, iterator __e2, size_type __n, _Comp& __comp); 1133 1134 _LIBCPP_HIDE_FROM_ABI void __move_assign(list& __c, true_type) 1135 _NOEXCEPT_(is_nothrow_move_assignable<__node_allocator>::value); 1136 _LIBCPP_HIDE_FROM_ABI void __move_assign(list& __c, false_type); 1137}; 1138 1139#if _LIBCPP_STD_VER >= 17 1140template<class _InputIterator, 1141 class _Alloc = allocator<__iter_value_type<_InputIterator>>, 1142 class = enable_if_t<__is_cpp17_input_iterator<_InputIterator>::value>, 1143 class = enable_if_t<__is_allocator<_Alloc>::value> 1144 > 1145list(_InputIterator, _InputIterator) 1146 -> list<__iter_value_type<_InputIterator>, _Alloc>; 1147 1148template<class _InputIterator, 1149 class _Alloc, 1150 class = enable_if_t<__is_cpp17_input_iterator<_InputIterator>::value>, 1151 class = enable_if_t<__is_allocator<_Alloc>::value> 1152 > 1153list(_InputIterator, _InputIterator, _Alloc) 1154 -> list<__iter_value_type<_InputIterator>, _Alloc>; 1155#endif 1156 1157// Link in nodes [__f, __l] just prior to __p 1158template <class _Tp, class _Alloc> 1159inline 1160void 1161list<_Tp, _Alloc>::__link_nodes(__link_pointer __p, __link_pointer __f, __link_pointer __l) 1162{ 1163 __p->__prev_->__next_ = __f; 1164 __f->__prev_ = __p->__prev_; 1165 __p->__prev_ = __l; 1166 __l->__next_ = __p; 1167} 1168 1169// Link in nodes [__f, __l] at the front of the list 1170template <class _Tp, class _Alloc> 1171inline 1172void 1173list<_Tp, _Alloc>::__link_nodes_at_front(__link_pointer __f, __link_pointer __l) 1174{ 1175 __f->__prev_ = base::__end_as_link(); 1176 __l->__next_ = base::__end_.__next_; 1177 __l->__next_->__prev_ = __l; 1178 base::__end_.__next_ = __f; 1179} 1180 1181// Link in nodes [__f, __l] at the back of the list 1182template <class _Tp, class _Alloc> 1183inline 1184void 1185list<_Tp, _Alloc>::__link_nodes_at_back(__link_pointer __f, __link_pointer __l) 1186{ 1187 __l->__next_ = base::__end_as_link(); 1188 __f->__prev_ = base::__end_.__prev_; 1189 __f->__prev_->__next_ = __f; 1190 base::__end_.__prev_ = __l; 1191} 1192 1193 1194template <class _Tp, class _Alloc> 1195inline 1196typename list<_Tp, _Alloc>::iterator 1197list<_Tp, _Alloc>::__iterator(size_type __n) 1198{ 1199 return __n <= base::__sz() / 2 ? _VSTD::next(begin(), __n) 1200 : _VSTD::prev(end(), base::__sz() - __n); 1201} 1202 1203template <class _Tp, class _Alloc> 1204list<_Tp, _Alloc>::list(size_type __n) 1205{ 1206 _VSTD::__debug_db_insert_c(this); 1207 for (; __n > 0; --__n) 1208#ifndef _LIBCPP_CXX03_LANG 1209 emplace_back(); 1210#else 1211 push_back(value_type()); 1212#endif 1213} 1214 1215#if _LIBCPP_STD_VER >= 14 1216template <class _Tp, class _Alloc> 1217list<_Tp, _Alloc>::list(size_type __n, const allocator_type& __a) : base(__a) 1218{ 1219 _VSTD::__debug_db_insert_c(this); 1220 for (; __n > 0; --__n) 1221 emplace_back(); 1222} 1223#endif 1224 1225template <class _Tp, class _Alloc> 1226list<_Tp, _Alloc>::list(size_type __n, const value_type& __x) 1227{ 1228 _VSTD::__debug_db_insert_c(this); 1229 for (; __n > 0; --__n) 1230 push_back(__x); 1231} 1232 1233template <class _Tp, class _Alloc> 1234template <class _InpIter> 1235list<_Tp, _Alloc>::list(_InpIter __f, _InpIter __l, 1236 __enable_if_t<__is_cpp17_input_iterator<_InpIter>::value>*) 1237{ 1238 _VSTD::__debug_db_insert_c(this); 1239 for (; __f != __l; ++__f) 1240 __emplace_back(*__f); 1241} 1242 1243template <class _Tp, class _Alloc> 1244template <class _InpIter> 1245list<_Tp, _Alloc>::list(_InpIter __f, _InpIter __l, const allocator_type& __a, 1246 __enable_if_t<__is_cpp17_input_iterator<_InpIter>::value>*) 1247 : base(__a) 1248{ 1249 _VSTD::__debug_db_insert_c(this); 1250 for (; __f != __l; ++__f) 1251 __emplace_back(*__f); 1252} 1253 1254template <class _Tp, class _Alloc> 1255list<_Tp, _Alloc>::list(const list& __c) 1256 : base(__node_alloc_traits::select_on_container_copy_construction( 1257 __c.__node_alloc())) { 1258 _VSTD::__debug_db_insert_c(this); 1259 for (const_iterator __i = __c.begin(), __e = __c.end(); __i != __e; ++__i) 1260 push_back(*__i); 1261} 1262 1263template <class _Tp, class _Alloc> 1264list<_Tp, _Alloc>::list(const list& __c, const __type_identity_t<allocator_type>& __a) 1265 : base(__a) 1266{ 1267 _VSTD::__debug_db_insert_c(this); 1268 for (const_iterator __i = __c.begin(), __e = __c.end(); __i != __e; ++__i) 1269 push_back(*__i); 1270} 1271 1272#ifndef _LIBCPP_CXX03_LANG 1273 1274template <class _Tp, class _Alloc> 1275list<_Tp, _Alloc>::list(initializer_list<value_type> __il, const allocator_type& __a) 1276 : base(__a) 1277{ 1278 _VSTD::__debug_db_insert_c(this); 1279 for (typename initializer_list<value_type>::const_iterator __i = __il.begin(), 1280 __e = __il.end(); __i != __e; ++__i) 1281 push_back(*__i); 1282} 1283 1284template <class _Tp, class _Alloc> 1285list<_Tp, _Alloc>::list(initializer_list<value_type> __il) 1286{ 1287 _VSTD::__debug_db_insert_c(this); 1288 for (typename initializer_list<value_type>::const_iterator __i = __il.begin(), 1289 __e = __il.end(); __i != __e; ++__i) 1290 push_back(*__i); 1291} 1292 1293template <class _Tp, class _Alloc> 1294inline list<_Tp, _Alloc>::list(list&& __c) 1295 _NOEXCEPT_(is_nothrow_move_constructible<__node_allocator>::value) 1296 : base(_VSTD::move(__c.__node_alloc())) { 1297 _VSTD::__debug_db_insert_c(this); 1298 splice(end(), __c); 1299} 1300 1301template <class _Tp, class _Alloc> 1302inline 1303list<_Tp, _Alloc>::list(list&& __c, const __type_identity_t<allocator_type>& __a) 1304 : base(__a) 1305{ 1306 _VSTD::__debug_db_insert_c(this); 1307 if (__a == __c.get_allocator()) 1308 splice(end(), __c); 1309 else 1310 { 1311 typedef move_iterator<iterator> _Ip; 1312 assign(_Ip(__c.begin()), _Ip(__c.end())); 1313 } 1314} 1315 1316template <class _Tp, class _Alloc> 1317inline 1318list<_Tp, _Alloc>& 1319list<_Tp, _Alloc>::operator=(list&& __c) 1320 _NOEXCEPT_( 1321 __node_alloc_traits::propagate_on_container_move_assignment::value && 1322 is_nothrow_move_assignable<__node_allocator>::value) 1323{ 1324 __move_assign(__c, integral_constant<bool, 1325 __node_alloc_traits::propagate_on_container_move_assignment::value>()); 1326 return *this; 1327} 1328 1329template <class _Tp, class _Alloc> 1330void 1331list<_Tp, _Alloc>::__move_assign(list& __c, false_type) 1332{ 1333 if (base::__node_alloc() != __c.__node_alloc()) 1334 { 1335 typedef move_iterator<iterator> _Ip; 1336 assign(_Ip(__c.begin()), _Ip(__c.end())); 1337 } 1338 else 1339 __move_assign(__c, true_type()); 1340} 1341 1342template <class _Tp, class _Alloc> 1343void 1344list<_Tp, _Alloc>::__move_assign(list& __c, true_type) 1345 _NOEXCEPT_(is_nothrow_move_assignable<__node_allocator>::value) 1346{ 1347 clear(); 1348 base::__move_assign_alloc(__c); 1349 splice(end(), __c); 1350} 1351 1352#endif // _LIBCPP_CXX03_LANG 1353 1354template <class _Tp, class _Alloc> 1355inline 1356list<_Tp, _Alloc>& 1357list<_Tp, _Alloc>::operator=(const list& __c) 1358{ 1359 if (this != _VSTD::addressof(__c)) 1360 { 1361 base::__copy_assign_alloc(__c); 1362 assign(__c.begin(), __c.end()); 1363 } 1364 return *this; 1365} 1366 1367template <class _Tp, class _Alloc> 1368template <class _InpIter> 1369void 1370list<_Tp, _Alloc>::assign(_InpIter __f, _InpIter __l, 1371 __enable_if_t<__is_cpp17_input_iterator<_InpIter>::value>*) 1372{ 1373 iterator __i = begin(); 1374 iterator __e = end(); 1375 for (; __f != __l && __i != __e; ++__f, (void) ++__i) 1376 *__i = *__f; 1377 if (__i == __e) 1378 insert(__e, __f, __l); 1379 else 1380 erase(__i, __e); 1381 std::__debug_db_invalidate_all(this); 1382} 1383 1384template <class _Tp, class _Alloc> 1385void 1386list<_Tp, _Alloc>::assign(size_type __n, const value_type& __x) 1387{ 1388 iterator __i = begin(); 1389 iterator __e = end(); 1390 for (; __n > 0 && __i != __e; --__n, (void) ++__i) 1391 *__i = __x; 1392 if (__i == __e) 1393 insert(__e, __n, __x); 1394 else 1395 erase(__i, __e); 1396 std::__debug_db_invalidate_all(this); 1397} 1398 1399template <class _Tp, class _Alloc> 1400inline 1401_Alloc 1402list<_Tp, _Alloc>::get_allocator() const _NOEXCEPT 1403{ 1404 return allocator_type(base::__node_alloc()); 1405} 1406 1407template <class _Tp, class _Alloc> 1408typename list<_Tp, _Alloc>::iterator 1409list<_Tp, _Alloc>::insert(const_iterator __p, const value_type& __x) 1410{ 1411 _LIBCPP_DEBUG_ASSERT(__get_const_db()->__find_c_from_i(_VSTD::addressof(__p)) == this, 1412 "list::insert(iterator, x) called with an iterator not referring to this list"); 1413 __node_allocator& __na = base::__node_alloc(); 1414 __hold_pointer __hold = __allocate_node(__na); 1415 __node_alloc_traits::construct(__na, _VSTD::addressof(__hold->__value_), __x); 1416 __link_nodes(__p.__ptr_, __hold->__as_link(), __hold->__as_link()); 1417 ++base::__sz(); 1418 return iterator(__hold.release()->__as_link(), this); 1419} 1420 1421template <class _Tp, class _Alloc> 1422typename list<_Tp, _Alloc>::iterator 1423list<_Tp, _Alloc>::insert(const_iterator __p, size_type __n, const value_type& __x) 1424{ 1425 _LIBCPP_DEBUG_ASSERT(__get_const_db()->__find_c_from_i(_VSTD::addressof(__p)) == this, 1426 "list::insert(iterator, n, x) called with an iterator not referring to this list"); 1427 iterator __r(__p.__ptr_, this); 1428 if (__n > 0) 1429 { 1430 size_type __ds = 0; 1431 __node_allocator& __na = base::__node_alloc(); 1432 __hold_pointer __hold = __allocate_node(__na); 1433 __node_alloc_traits::construct(__na, _VSTD::addressof(__hold->__value_), __x); 1434 ++__ds; 1435 __r = iterator(__hold->__as_link(), this); 1436 __hold.release(); 1437 iterator __e = __r; 1438#ifndef _LIBCPP_HAS_NO_EXCEPTIONS 1439 try 1440 { 1441#endif // _LIBCPP_HAS_NO_EXCEPTIONS 1442 for (--__n; __n != 0; --__n, (void) ++__e, ++__ds) 1443 { 1444 __hold.reset(__node_alloc_traits::allocate(__na, 1)); 1445 __node_alloc_traits::construct(__na, _VSTD::addressof(__hold->__value_), __x); 1446 __e.__ptr_->__next_ = __hold->__as_link(); 1447 __hold->__prev_ = __e.__ptr_; 1448 __hold.release(); 1449 } 1450#ifndef _LIBCPP_HAS_NO_EXCEPTIONS 1451 } 1452 catch (...) 1453 { 1454 while (true) 1455 { 1456 __node_alloc_traits::destroy(__na, _VSTD::addressof(*__e)); 1457 __link_pointer __prev = __e.__ptr_->__prev_; 1458 __node_alloc_traits::deallocate(__na, __e.__ptr_->__as_node(), 1); 1459 if (__prev == 0) 1460 break; 1461 __e = iterator(__prev, this); 1462 } 1463 throw; 1464 } 1465#endif // _LIBCPP_HAS_NO_EXCEPTIONS 1466 __link_nodes(__p.__ptr_, __r.__ptr_, __e.__ptr_); 1467 base::__sz() += __ds; 1468 } 1469 return __r; 1470} 1471 1472template <class _Tp, class _Alloc> 1473template <class _InpIter> 1474typename list<_Tp, _Alloc>::iterator 1475list<_Tp, _Alloc>::insert(const_iterator __p, _InpIter __f, _InpIter __l, 1476 __enable_if_t<__is_cpp17_input_iterator<_InpIter>::value>*) 1477{ 1478 _LIBCPP_DEBUG_ASSERT(__get_const_db()->__find_c_from_i(_VSTD::addressof(__p)) == this, 1479 "list::insert(iterator, range) called with an iterator not referring to this list"); 1480 iterator __r(__p.__ptr_, this); 1481 if (__f != __l) 1482 { 1483 size_type __ds = 0; 1484 __node_allocator& __na = base::__node_alloc(); 1485 __hold_pointer __hold = __allocate_node(__na); 1486 __node_alloc_traits::construct(__na, _VSTD::addressof(__hold->__value_), *__f); 1487 ++__ds; 1488 __r = iterator(__hold.get()->__as_link(), this); 1489 __hold.release(); 1490 iterator __e = __r; 1491#ifndef _LIBCPP_HAS_NO_EXCEPTIONS 1492 try 1493 { 1494#endif // _LIBCPP_HAS_NO_EXCEPTIONS 1495 for (++__f; __f != __l; ++__f, (void) ++__e, ++__ds) 1496 { 1497 __hold.reset(__node_alloc_traits::allocate(__na, 1)); 1498 __node_alloc_traits::construct(__na, _VSTD::addressof(__hold->__value_), *__f); 1499 __e.__ptr_->__next_ = __hold.get()->__as_link(); 1500 __hold->__prev_ = __e.__ptr_; 1501 __hold.release(); 1502 } 1503#ifndef _LIBCPP_HAS_NO_EXCEPTIONS 1504 } 1505 catch (...) 1506 { 1507 while (true) 1508 { 1509 __node_alloc_traits::destroy(__na, _VSTD::addressof(*__e)); 1510 __link_pointer __prev = __e.__ptr_->__prev_; 1511 __node_alloc_traits::deallocate(__na, __e.__ptr_->__as_node(), 1); 1512 if (__prev == 0) 1513 break; 1514 __e = iterator(__prev, this); 1515 } 1516 throw; 1517 } 1518#endif // _LIBCPP_HAS_NO_EXCEPTIONS 1519 __link_nodes(__p.__ptr_, __r.__ptr_, __e.__ptr_); 1520 base::__sz() += __ds; 1521 } 1522 return __r; 1523} 1524 1525template <class _Tp, class _Alloc> 1526void 1527list<_Tp, _Alloc>::push_front(const value_type& __x) 1528{ 1529 __node_allocator& __na = base::__node_alloc(); 1530 __hold_pointer __hold = __allocate_node(__na); 1531 __node_alloc_traits::construct(__na, _VSTD::addressof(__hold->__value_), __x); 1532 __link_pointer __nl = __hold->__as_link(); 1533 __link_nodes_at_front(__nl, __nl); 1534 ++base::__sz(); 1535 __hold.release(); 1536} 1537 1538template <class _Tp, class _Alloc> 1539void 1540list<_Tp, _Alloc>::push_back(const value_type& __x) 1541{ 1542 __node_allocator& __na = base::__node_alloc(); 1543 __hold_pointer __hold = __allocate_node(__na); 1544 __node_alloc_traits::construct(__na, _VSTD::addressof(__hold->__value_), __x); 1545 __link_nodes_at_back(__hold.get()->__as_link(), __hold.get()->__as_link()); 1546 ++base::__sz(); 1547 __hold.release(); 1548} 1549 1550#ifndef _LIBCPP_CXX03_LANG 1551 1552template <class _Tp, class _Alloc> 1553void 1554list<_Tp, _Alloc>::push_front(value_type&& __x) 1555{ 1556 __node_allocator& __na = base::__node_alloc(); 1557 __hold_pointer __hold = __allocate_node(__na); 1558 __node_alloc_traits::construct(__na, _VSTD::addressof(__hold->__value_), _VSTD::move(__x)); 1559 __link_nodes_at_front(__hold.get()->__as_link(), __hold.get()->__as_link()); 1560 ++base::__sz(); 1561 __hold.release(); 1562} 1563 1564template <class _Tp, class _Alloc> 1565void 1566list<_Tp, _Alloc>::push_back(value_type&& __x) 1567{ 1568 __node_allocator& __na = base::__node_alloc(); 1569 __hold_pointer __hold = __allocate_node(__na); 1570 __node_alloc_traits::construct(__na, _VSTD::addressof(__hold->__value_), _VSTD::move(__x)); 1571 __link_nodes_at_back(__hold.get()->__as_link(), __hold.get()->__as_link()); 1572 ++base::__sz(); 1573 __hold.release(); 1574} 1575 1576template <class _Tp, class _Alloc> 1577template <class... _Args> 1578#if _LIBCPP_STD_VER >= 17 1579typename list<_Tp, _Alloc>::reference 1580#else 1581void 1582#endif 1583list<_Tp, _Alloc>::emplace_front(_Args&&... __args) 1584{ 1585 __node_allocator& __na = base::__node_alloc(); 1586 __hold_pointer __hold = __allocate_node(__na); 1587 __node_alloc_traits::construct(__na, _VSTD::addressof(__hold->__value_), _VSTD::forward<_Args>(__args)...); 1588 __link_nodes_at_front(__hold.get()->__as_link(), __hold.get()->__as_link()); 1589 ++base::__sz(); 1590#if _LIBCPP_STD_VER >= 17 1591 return __hold.release()->__value_; 1592#else 1593 __hold.release(); 1594#endif 1595} 1596 1597template <class _Tp, class _Alloc> 1598template <class... _Args> 1599#if _LIBCPP_STD_VER >= 17 1600typename list<_Tp, _Alloc>::reference 1601#else 1602void 1603#endif 1604list<_Tp, _Alloc>::emplace_back(_Args&&... __args) 1605{ 1606 __node_allocator& __na = base::__node_alloc(); 1607 __hold_pointer __hold = __allocate_node(__na); 1608 __node_alloc_traits::construct(__na, _VSTD::addressof(__hold->__value_), _VSTD::forward<_Args>(__args)...); 1609 __link_pointer __nl = __hold->__as_link(); 1610 __link_nodes_at_back(__nl, __nl); 1611 ++base::__sz(); 1612#if _LIBCPP_STD_VER >= 17 1613 return __hold.release()->__value_; 1614#else 1615 __hold.release(); 1616#endif 1617} 1618 1619template <class _Tp, class _Alloc> 1620template <class... _Args> 1621typename list<_Tp, _Alloc>::iterator 1622list<_Tp, _Alloc>::emplace(const_iterator __p, _Args&&... __args) 1623{ 1624 _LIBCPP_DEBUG_ASSERT(__get_const_db()->__find_c_from_i(_VSTD::addressof(__p)) == this, 1625 "list::emplace(iterator, args...) called with an iterator not referring to this list"); 1626 __node_allocator& __na = base::__node_alloc(); 1627 __hold_pointer __hold = __allocate_node(__na); 1628 __node_alloc_traits::construct(__na, _VSTD::addressof(__hold->__value_), _VSTD::forward<_Args>(__args)...); 1629 __link_pointer __nl = __hold.get()->__as_link(); 1630 __link_nodes(__p.__ptr_, __nl, __nl); 1631 ++base::__sz(); 1632 __hold.release(); 1633 return iterator(__nl, this); 1634} 1635 1636template <class _Tp, class _Alloc> 1637typename list<_Tp, _Alloc>::iterator 1638list<_Tp, _Alloc>::insert(const_iterator __p, value_type&& __x) 1639{ 1640 _LIBCPP_DEBUG_ASSERT(__get_const_db()->__find_c_from_i(_VSTD::addressof(__p)) == this, 1641 "list::insert(iterator, x) called with an iterator not referring to this list"); 1642 __node_allocator& __na = base::__node_alloc(); 1643 __hold_pointer __hold = __allocate_node(__na); 1644 __node_alloc_traits::construct(__na, _VSTD::addressof(__hold->__value_), _VSTD::move(__x)); 1645 __link_pointer __nl = __hold->__as_link(); 1646 __link_nodes(__p.__ptr_, __nl, __nl); 1647 ++base::__sz(); 1648 __hold.release(); 1649 return iterator(__nl, this); 1650} 1651 1652#endif // _LIBCPP_CXX03_LANG 1653 1654template <class _Tp, class _Alloc> 1655void 1656list<_Tp, _Alloc>::pop_front() 1657{ 1658 _LIBCPP_ASSERT(!empty(), "list::pop_front() called with empty list"); 1659 __node_allocator& __na = base::__node_alloc(); 1660 __link_pointer __n = base::__end_.__next_; 1661 base::__unlink_nodes(__n, __n); 1662 --base::__sz(); 1663#ifdef _LIBCPP_ENABLE_DEBUG_MODE 1664 __c_node* __c = __get_db()->__find_c_and_lock(this); 1665 for (__i_node** __p = __c->end_; __p != __c->beg_; ) 1666 { 1667 --__p; 1668 iterator* __i = static_cast<iterator*>((*__p)->__i_); 1669 if (__i->__ptr_ == __n) 1670 { 1671 (*__p)->__c_ = nullptr; 1672 if (--__c->end_ != __p) 1673 _VSTD::memmove(__p, __p+1, (__c->end_ - __p)*sizeof(__i_node*)); 1674 } 1675 } 1676 __get_db()->unlock(); 1677#endif 1678 __node_pointer __np = __n->__as_node(); 1679 __node_alloc_traits::destroy(__na, _VSTD::addressof(__np->__value_)); 1680 __node_alloc_traits::deallocate(__na, __np, 1); 1681} 1682 1683template <class _Tp, class _Alloc> 1684void 1685list<_Tp, _Alloc>::pop_back() 1686{ 1687 _LIBCPP_ASSERT(!empty(), "list::pop_back() called on an empty list"); 1688 __node_allocator& __na = base::__node_alloc(); 1689 __link_pointer __n = base::__end_.__prev_; 1690 base::__unlink_nodes(__n, __n); 1691 --base::__sz(); 1692#ifdef _LIBCPP_ENABLE_DEBUG_MODE 1693 __c_node* __c = __get_db()->__find_c_and_lock(this); 1694 for (__i_node** __p = __c->end_; __p != __c->beg_; ) 1695 { 1696 --__p; 1697 iterator* __i = static_cast<iterator*>((*__p)->__i_); 1698 if (__i->__ptr_ == __n) 1699 { 1700 (*__p)->__c_ = nullptr; 1701 if (--__c->end_ != __p) 1702 _VSTD::memmove(__p, __p+1, (__c->end_ - __p)*sizeof(__i_node*)); 1703 } 1704 } 1705 __get_db()->unlock(); 1706#endif 1707 __node_pointer __np = __n->__as_node(); 1708 __node_alloc_traits::destroy(__na, _VSTD::addressof(__np->__value_)); 1709 __node_alloc_traits::deallocate(__na, __np, 1); 1710} 1711 1712template <class _Tp, class _Alloc> 1713typename list<_Tp, _Alloc>::iterator 1714list<_Tp, _Alloc>::erase(const_iterator __p) 1715{ 1716 _LIBCPP_DEBUG_ASSERT(__get_const_db()->__find_c_from_i(_VSTD::addressof(__p)) == this, 1717 "list::erase(iterator) called with an iterator not referring to this list"); 1718 _LIBCPP_ASSERT(__p != end(), 1719 "list::erase(iterator) called with a non-dereferenceable iterator"); 1720 __node_allocator& __na = base::__node_alloc(); 1721 __link_pointer __n = __p.__ptr_; 1722 __link_pointer __r = __n->__next_; 1723 base::__unlink_nodes(__n, __n); 1724 --base::__sz(); 1725#ifdef _LIBCPP_ENABLE_DEBUG_MODE 1726 __c_node* __c = __get_db()->__find_c_and_lock(this); 1727 for (__i_node** __ip = __c->end_; __ip != __c->beg_; ) 1728 { 1729 --__ip; 1730 iterator* __i = static_cast<iterator*>((*__ip)->__i_); 1731 if (__i->__ptr_ == __n) 1732 { 1733 (*__ip)->__c_ = nullptr; 1734 if (--__c->end_ != __ip) 1735 _VSTD::memmove(__ip, __ip+1, (__c->end_ - __ip)*sizeof(__i_node*)); 1736 } 1737 } 1738 __get_db()->unlock(); 1739#endif 1740 __node_pointer __np = __n->__as_node(); 1741 __node_alloc_traits::destroy(__na, _VSTD::addressof(__np->__value_)); 1742 __node_alloc_traits::deallocate(__na, __np, 1); 1743 return iterator(__r, this); 1744} 1745 1746template <class _Tp, class _Alloc> 1747typename list<_Tp, _Alloc>::iterator 1748list<_Tp, _Alloc>::erase(const_iterator __f, const_iterator __l) 1749{ 1750 _LIBCPP_DEBUG_ASSERT(__get_const_db()->__find_c_from_i(_VSTD::addressof(__f)) == this, 1751 "list::erase(iterator, iterator) called with an iterator not referring to this list"); 1752 _LIBCPP_DEBUG_ASSERT(__get_const_db()->__find_c_from_i(_VSTD::addressof(__l)) == this, 1753 "list::erase(iterator, iterator) called with an iterator not referring to this list"); 1754 if (__f != __l) 1755 { 1756 __node_allocator& __na = base::__node_alloc(); 1757 base::__unlink_nodes(__f.__ptr_, __l.__ptr_->__prev_); 1758 while (__f != __l) 1759 { 1760 __link_pointer __n = __f.__ptr_; 1761 ++__f; 1762 --base::__sz(); 1763#ifdef _LIBCPP_ENABLE_DEBUG_MODE 1764 __c_node* __c = __get_db()->__find_c_and_lock(this); 1765 for (__i_node** __p = __c->end_; __p != __c->beg_; ) 1766 { 1767 --__p; 1768 iterator* __i = static_cast<iterator*>((*__p)->__i_); 1769 if (__i->__ptr_ == __n) 1770 { 1771 (*__p)->__c_ = nullptr; 1772 if (--__c->end_ != __p) 1773 _VSTD::memmove(__p, __p+1, (__c->end_ - __p)*sizeof(__i_node*)); 1774 } 1775 } 1776 __get_db()->unlock(); 1777#endif 1778 __node_pointer __np = __n->__as_node(); 1779 __node_alloc_traits::destroy(__na, _VSTD::addressof(__np->__value_)); 1780 __node_alloc_traits::deallocate(__na, __np, 1); 1781 } 1782 } 1783 return iterator(__l.__ptr_, this); 1784} 1785 1786template <class _Tp, class _Alloc> 1787void 1788list<_Tp, _Alloc>::resize(size_type __n) 1789{ 1790 if (__n < base::__sz()) 1791 erase(__iterator(__n), end()); 1792 else if (__n > base::__sz()) 1793 { 1794 __n -= base::__sz(); 1795 size_type __ds = 0; 1796 __node_allocator& __na = base::__node_alloc(); 1797 __hold_pointer __hold = __allocate_node(__na); 1798 __node_alloc_traits::construct(__na, _VSTD::addressof(__hold->__value_)); 1799 ++__ds; 1800 iterator __r = iterator(__hold.release()->__as_link(), this); 1801 iterator __e = __r; 1802#ifndef _LIBCPP_HAS_NO_EXCEPTIONS 1803 try 1804 { 1805#endif // _LIBCPP_HAS_NO_EXCEPTIONS 1806 for (--__n; __n != 0; --__n, (void) ++__e, ++__ds) 1807 { 1808 __hold.reset(__node_alloc_traits::allocate(__na, 1)); 1809 __node_alloc_traits::construct(__na, _VSTD::addressof(__hold->__value_)); 1810 __e.__ptr_->__next_ = __hold.get()->__as_link(); 1811 __hold->__prev_ = __e.__ptr_; 1812 __hold.release(); 1813 } 1814#ifndef _LIBCPP_HAS_NO_EXCEPTIONS 1815 } 1816 catch (...) 1817 { 1818 while (true) 1819 { 1820 __node_alloc_traits::destroy(__na, _VSTD::addressof(*__e)); 1821 __link_pointer __prev = __e.__ptr_->__prev_; 1822 __node_alloc_traits::deallocate(__na, __e.__ptr_->__as_node(), 1); 1823 if (__prev == 0) 1824 break; 1825 __e = iterator(__prev, this); 1826 } 1827 throw; 1828 } 1829#endif // _LIBCPP_HAS_NO_EXCEPTIONS 1830 __link_nodes_at_back(__r.__ptr_, __e.__ptr_); 1831 base::__sz() += __ds; 1832 } 1833} 1834 1835template <class _Tp, class _Alloc> 1836void 1837list<_Tp, _Alloc>::resize(size_type __n, const value_type& __x) 1838{ 1839 if (__n < base::__sz()) 1840 erase(__iterator(__n), end()); 1841 else if (__n > base::__sz()) 1842 { 1843 __n -= base::__sz(); 1844 size_type __ds = 0; 1845 __node_allocator& __na = base::__node_alloc(); 1846 __hold_pointer __hold = __allocate_node(__na); 1847 __node_alloc_traits::construct(__na, _VSTD::addressof(__hold->__value_), __x); 1848 ++__ds; 1849 __link_pointer __nl = __hold.release()->__as_link(); 1850 iterator __r = iterator(__nl, this); 1851 iterator __e = __r; 1852#ifndef _LIBCPP_HAS_NO_EXCEPTIONS 1853 try 1854 { 1855#endif // _LIBCPP_HAS_NO_EXCEPTIONS 1856 for (--__n; __n != 0; --__n, (void) ++__e, ++__ds) 1857 { 1858 __hold.reset(__node_alloc_traits::allocate(__na, 1)); 1859 __node_alloc_traits::construct(__na, _VSTD::addressof(__hold->__value_), __x); 1860 __e.__ptr_->__next_ = __hold.get()->__as_link(); 1861 __hold->__prev_ = __e.__ptr_; 1862 __hold.release(); 1863 } 1864#ifndef _LIBCPP_HAS_NO_EXCEPTIONS 1865 } 1866 catch (...) 1867 { 1868 while (true) 1869 { 1870 __node_alloc_traits::destroy(__na, _VSTD::addressof(*__e)); 1871 __link_pointer __prev = __e.__ptr_->__prev_; 1872 __node_alloc_traits::deallocate(__na, __e.__ptr_->__as_node(), 1); 1873 if (__prev == 0) 1874 break; 1875 __e = iterator(__prev, this); 1876 } 1877 throw; 1878 } 1879#endif // _LIBCPP_HAS_NO_EXCEPTIONS 1880 __link_nodes(base::__end_as_link(), __r.__ptr_, __e.__ptr_); 1881 base::__sz() += __ds; 1882 } 1883} 1884 1885template <class _Tp, class _Alloc> 1886void 1887list<_Tp, _Alloc>::splice(const_iterator __p, list& __c) 1888{ 1889 _LIBCPP_ASSERT(this != _VSTD::addressof(__c), 1890 "list::splice(iterator, list) called with this == &list"); 1891 _LIBCPP_DEBUG_ASSERT(__get_const_db()->__find_c_from_i(_VSTD::addressof(__p)) == this, 1892 "list::splice(iterator, list) called with an iterator not referring to this list"); 1893 if (!__c.empty()) 1894 { 1895 __link_pointer __f = __c.__end_.__next_; 1896 __link_pointer __l = __c.__end_.__prev_; 1897 base::__unlink_nodes(__f, __l); 1898 __link_nodes(__p.__ptr_, __f, __l); 1899 base::__sz() += __c.__sz(); 1900 __c.__sz() = 0; 1901#ifdef _LIBCPP_ENABLE_DEBUG_MODE 1902 if (_VSTD::addressof(__c) != this) { 1903 __libcpp_db* __db = __get_db(); 1904 __c_node* __cn1 = __db->__find_c_and_lock(this); 1905 __c_node* __cn2 = __db->__find_c(_VSTD::addressof(__c)); 1906 for (__i_node** __ip = __cn2->end_; __ip != __cn2->beg_;) 1907 { 1908 --__ip; 1909 iterator* __i = static_cast<iterator*>((*__ip)->__i_); 1910 if (__i->__ptr_ != __c.__end_as_link()) 1911 { 1912 __cn1->__add(*__ip); 1913 (*__ip)->__c_ = __cn1; 1914 if (--__cn2->end_ != __ip) 1915 _VSTD::memmove(__ip, __ip+1, (__cn2->end_ - __ip)*sizeof(__i_node*)); 1916 } 1917 } 1918 __db->unlock(); 1919 } 1920#endif 1921 } 1922} 1923 1924template <class _Tp, class _Alloc> 1925void 1926list<_Tp, _Alloc>::splice(const_iterator __p, list& __c, const_iterator __i) 1927{ 1928 _LIBCPP_DEBUG_ASSERT(__get_const_db()->__find_c_from_i(_VSTD::addressof(__p)) == this, 1929 "list::splice(iterator, list, iterator) called with the first iterator not referring to this list"); 1930 _LIBCPP_DEBUG_ASSERT(__get_const_db()->__find_c_from_i(_VSTD::addressof(__i)) == _VSTD::addressof(__c), 1931 "list::splice(iterator, list, iterator) called with the second iterator not referring to the list argument"); 1932 _LIBCPP_DEBUG_ASSERT(__get_const_db()->__dereferenceable(_VSTD::addressof(__i)), 1933 "list::splice(iterator, list, iterator) called with the second iterator not dereferenceable"); 1934 1935 if (__p.__ptr_ != __i.__ptr_ && __p.__ptr_ != __i.__ptr_->__next_) 1936 { 1937 __link_pointer __f = __i.__ptr_; 1938 base::__unlink_nodes(__f, __f); 1939 __link_nodes(__p.__ptr_, __f, __f); 1940 --__c.__sz(); 1941 ++base::__sz(); 1942#ifdef _LIBCPP_ENABLE_DEBUG_MODE 1943 if (_VSTD::addressof(__c) != this) { 1944 __libcpp_db* __db = __get_db(); 1945 __c_node* __cn1 = __db->__find_c_and_lock(this); 1946 __c_node* __cn2 = __db->__find_c(_VSTD::addressof(__c)); 1947 for (__i_node** __ip = __cn2->end_; __ip != __cn2->beg_;) 1948 { 1949 --__ip; 1950 iterator* __j = static_cast<iterator*>((*__ip)->__i_); 1951 if (__j->__ptr_ == __f) 1952 { 1953 __cn1->__add(*__ip); 1954 (*__ip)->__c_ = __cn1; 1955 if (--__cn2->end_ != __ip) 1956 _VSTD::memmove(__ip, __ip+1, (__cn2->end_ - __ip)*sizeof(__i_node*)); 1957 } 1958 } 1959 __db->unlock(); 1960 } 1961#endif 1962 } 1963} 1964 1965template <class _Iterator> 1966_LIBCPP_HIDE_FROM_ABI 1967bool __iterator_in_range(_Iterator __first, _Iterator __last, _Iterator __it) { 1968 for (_Iterator __p = __first; __p != __last; ++__p) { 1969 if (__p == __it) { 1970 return true; 1971 } 1972 } 1973 return false; 1974} 1975 1976template <class _Tp, class _Alloc> 1977void 1978list<_Tp, _Alloc>::splice(const_iterator __p, list& __c, const_iterator __f, const_iterator __l) 1979{ 1980 _LIBCPP_DEBUG_ASSERT(__get_const_db()->__find_c_from_i(_VSTD::addressof(__p)) == this, 1981 "list::splice(iterator, list, iterator, iterator) called with first iterator not referring to this list"); 1982 _LIBCPP_DEBUG_ASSERT(__get_const_db()->__find_c_from_i(_VSTD::addressof(__f)) == _VSTD::addressof(__c), 1983 "list::splice(iterator, list, iterator, iterator) called with second iterator not referring to the list argument"); 1984 _LIBCPP_DEBUG_ASSERT(__get_const_db()->__find_c_from_i(_VSTD::addressof(__l)) == _VSTD::addressof(__c), 1985 "list::splice(iterator, list, iterator, iterator) called with third iterator not referring to the list argument"); 1986 _LIBCPP_DEBUG_ASSERT(this != std::addressof(__c) || !std::__iterator_in_range(__f, __l, __p), 1987 "list::splice(iterator, list, iterator, iterator)" 1988 " called with the first iterator within the range of the second and third iterators"); 1989 1990 if (__f != __l) 1991 { 1992 __link_pointer __first = __f.__ptr_; 1993 --__l; 1994 __link_pointer __last = __l.__ptr_; 1995 if (this != _VSTD::addressof(__c)) 1996 { 1997 size_type __s = _VSTD::distance(__f, __l) + 1; 1998 __c.__sz() -= __s; 1999 base::__sz() += __s; 2000 } 2001 base::__unlink_nodes(__first, __last); 2002 __link_nodes(__p.__ptr_, __first, __last); 2003#ifdef _LIBCPP_ENABLE_DEBUG_MODE 2004 if (_VSTD::addressof(__c) != this) { 2005 __libcpp_db* __db = __get_db(); 2006 __c_node* __cn1 = __db->__find_c_and_lock(this); 2007 __c_node* __cn2 = __db->__find_c(_VSTD::addressof(__c)); 2008 for (__i_node** __ip = __cn2->end_; __ip != __cn2->beg_;) 2009 { 2010 --__ip; 2011 iterator* __j = static_cast<iterator*>((*__ip)->__i_); 2012 for (__link_pointer __k = __f.__ptr_; 2013 __k != __l.__ptr_; __k = __k->__next_) 2014 { 2015 if (__j->__ptr_ == __k) 2016 { 2017 __cn1->__add(*__ip); 2018 (*__ip)->__c_ = __cn1; 2019 if (--__cn2->end_ != __ip) 2020 _VSTD::memmove(__ip, __ip+1, (__cn2->end_ - __ip)*sizeof(__i_node*)); 2021 } 2022 } 2023 } 2024 __db->unlock(); 2025 } 2026#endif 2027 } 2028} 2029 2030template <class _Tp, class _Alloc> 2031typename list<_Tp, _Alloc>::__remove_return_type 2032list<_Tp, _Alloc>::remove(const value_type& __x) 2033{ 2034 list<_Tp, _Alloc> __deleted_nodes(get_allocator()); // collect the nodes we're removing 2035 for (const_iterator __i = begin(), __e = end(); __i != __e;) 2036 { 2037 if (*__i == __x) 2038 { 2039 const_iterator __j = _VSTD::next(__i); 2040 for (; __j != __e && *__j == __x; ++__j) 2041 ; 2042 __deleted_nodes.splice(__deleted_nodes.end(), *this, __i, __j); 2043 __i = __j; 2044 if (__i != __e) 2045 ++__i; 2046 } 2047 else 2048 ++__i; 2049 } 2050 2051 return (__remove_return_type) __deleted_nodes.size(); 2052} 2053 2054template <class _Tp, class _Alloc> 2055template <class _Pred> 2056typename list<_Tp, _Alloc>::__remove_return_type 2057list<_Tp, _Alloc>::remove_if(_Pred __pred) 2058{ 2059 list<_Tp, _Alloc> __deleted_nodes(get_allocator()); // collect the nodes we're removing 2060 for (iterator __i = begin(), __e = end(); __i != __e;) 2061 { 2062 if (__pred(*__i)) 2063 { 2064 iterator __j = _VSTD::next(__i); 2065 for (; __j != __e && __pred(*__j); ++__j) 2066 ; 2067 __deleted_nodes.splice(__deleted_nodes.end(), *this, __i, __j); 2068 __i = __j; 2069 if (__i != __e) 2070 ++__i; 2071 } 2072 else 2073 ++__i; 2074 } 2075 2076 return (__remove_return_type) __deleted_nodes.size(); 2077} 2078 2079template <class _Tp, class _Alloc> 2080template <class _BinaryPred> 2081typename list<_Tp, _Alloc>::__remove_return_type 2082list<_Tp, _Alloc>::unique(_BinaryPred __binary_pred) 2083{ 2084 list<_Tp, _Alloc> __deleted_nodes(get_allocator()); // collect the nodes we're removing 2085 for (iterator __i = begin(), __e = end(); __i != __e;) 2086 { 2087 iterator __j = _VSTD::next(__i); 2088 for (; __j != __e && __binary_pred(*__i, *__j); ++__j) 2089 ; 2090 if (++__i != __j) { 2091 __deleted_nodes.splice(__deleted_nodes.end(), *this, __i, __j); 2092 __i = __j; 2093 } 2094 } 2095 2096 return (__remove_return_type) __deleted_nodes.size(); 2097} 2098 2099template <class _Tp, class _Alloc> 2100inline 2101void 2102list<_Tp, _Alloc>::merge(list& __c) 2103{ 2104 merge(__c, __less<value_type>()); 2105} 2106 2107template <class _Tp, class _Alloc> 2108template <class _Comp> 2109void 2110list<_Tp, _Alloc>::merge(list& __c, _Comp __comp) 2111{ 2112 if (this != _VSTD::addressof(__c)) 2113 { 2114 iterator __f1 = begin(); 2115 iterator __e1 = end(); 2116 iterator __f2 = __c.begin(); 2117 iterator __e2 = __c.end(); 2118 while (__f1 != __e1 && __f2 != __e2) 2119 { 2120 if (__comp(*__f2, *__f1)) 2121 { 2122 size_type __ds = 1; 2123 iterator __m2 = _VSTD::next(__f2); 2124 for (; __m2 != __e2 && __comp(*__m2, *__f1); ++__m2, (void) ++__ds) 2125 ; 2126 base::__sz() += __ds; 2127 __c.__sz() -= __ds; 2128 __link_pointer __f = __f2.__ptr_; 2129 __link_pointer __l = __m2.__ptr_->__prev_; 2130 __f2 = __m2; 2131 base::__unlink_nodes(__f, __l); 2132 __m2 = _VSTD::next(__f1); 2133 __link_nodes(__f1.__ptr_, __f, __l); 2134 __f1 = __m2; 2135 } 2136 else 2137 ++__f1; 2138 } 2139 splice(__e1, __c); 2140#ifdef _LIBCPP_ENABLE_DEBUG_MODE 2141 __libcpp_db* __db = __get_db(); 2142 __c_node* __cn1 = __db->__find_c_and_lock(this); 2143 __c_node* __cn2 = __db->__find_c(_VSTD::addressof(__c)); 2144 for (__i_node** __p = __cn2->end_; __p != __cn2->beg_;) 2145 { 2146 --__p; 2147 iterator* __i = static_cast<iterator*>((*__p)->__i_); 2148 if (__i->__ptr_ != __c.__end_as_link()) 2149 { 2150 __cn1->__add(*__p); 2151 (*__p)->__c_ = __cn1; 2152 if (--__cn2->end_ != __p) 2153 _VSTD::memmove(__p, __p+1, (__cn2->end_ - __p)*sizeof(__i_node*)); 2154 } 2155 } 2156 __db->unlock(); 2157#endif 2158 } 2159} 2160 2161template <class _Tp, class _Alloc> 2162inline 2163void 2164list<_Tp, _Alloc>::sort() 2165{ 2166 sort(__less<value_type>()); 2167} 2168 2169template <class _Tp, class _Alloc> 2170template <class _Comp> 2171inline 2172void 2173list<_Tp, _Alloc>::sort(_Comp __comp) 2174{ 2175 __sort(begin(), end(), base::__sz(), __comp); 2176} 2177 2178template <class _Tp, class _Alloc> 2179template <class _Comp> 2180typename list<_Tp, _Alloc>::iterator 2181list<_Tp, _Alloc>::__sort(iterator __f1, iterator __e2, size_type __n, _Comp& __comp) 2182{ 2183 switch (__n) 2184 { 2185 case 0: 2186 case 1: 2187 return __f1; 2188 case 2: 2189 if (__comp(*--__e2, *__f1)) 2190 { 2191 __link_pointer __f = __e2.__ptr_; 2192 base::__unlink_nodes(__f, __f); 2193 __link_nodes(__f1.__ptr_, __f, __f); 2194 return __e2; 2195 } 2196 return __f1; 2197 } 2198 size_type __n2 = __n / 2; 2199 iterator __e1 = _VSTD::next(__f1, __n2); 2200 iterator __r = __f1 = __sort(__f1, __e1, __n2, __comp); 2201 iterator __f2 = __e1 = __sort(__e1, __e2, __n - __n2, __comp); 2202 if (__comp(*__f2, *__f1)) 2203 { 2204 iterator __m2 = _VSTD::next(__f2); 2205 for (; __m2 != __e2 && __comp(*__m2, *__f1); ++__m2) 2206 ; 2207 __link_pointer __f = __f2.__ptr_; 2208 __link_pointer __l = __m2.__ptr_->__prev_; 2209 __r = __f2; 2210 __e1 = __f2 = __m2; 2211 base::__unlink_nodes(__f, __l); 2212 __m2 = _VSTD::next(__f1); 2213 __link_nodes(__f1.__ptr_, __f, __l); 2214 __f1 = __m2; 2215 } 2216 else 2217 ++__f1; 2218 while (__f1 != __e1 && __f2 != __e2) 2219 { 2220 if (__comp(*__f2, *__f1)) 2221 { 2222 iterator __m2 = _VSTD::next(__f2); 2223 for (; __m2 != __e2 && __comp(*__m2, *__f1); ++__m2) 2224 ; 2225 __link_pointer __f = __f2.__ptr_; 2226 __link_pointer __l = __m2.__ptr_->__prev_; 2227 if (__e1 == __f2) 2228 __e1 = __m2; 2229 __f2 = __m2; 2230 base::__unlink_nodes(__f, __l); 2231 __m2 = _VSTD::next(__f1); 2232 __link_nodes(__f1.__ptr_, __f, __l); 2233 __f1 = __m2; 2234 } 2235 else 2236 ++__f1; 2237 } 2238 return __r; 2239} 2240 2241template <class _Tp, class _Alloc> 2242void 2243list<_Tp, _Alloc>::reverse() _NOEXCEPT 2244{ 2245 if (base::__sz() > 1) 2246 { 2247 iterator __e = end(); 2248 for (iterator __i = begin(); __i.__ptr_ != __e.__ptr_;) 2249 { 2250 _VSTD::swap(__i.__ptr_->__prev_, __i.__ptr_->__next_); 2251 __i.__ptr_ = __i.__ptr_->__prev_; 2252 } 2253 _VSTD::swap(__e.__ptr_->__prev_, __e.__ptr_->__next_); 2254 } 2255} 2256 2257template <class _Tp, class _Alloc> 2258bool 2259list<_Tp, _Alloc>::__invariants() const 2260{ 2261 return size() == _VSTD::distance(begin(), end()); 2262} 2263 2264#ifdef _LIBCPP_ENABLE_DEBUG_MODE 2265 2266template <class _Tp, class _Alloc> 2267bool 2268list<_Tp, _Alloc>::__dereferenceable(const const_iterator* __i) const 2269{ 2270 return __i->__ptr_ != this->__end_as_link(); 2271} 2272 2273template <class _Tp, class _Alloc> 2274bool 2275list<_Tp, _Alloc>::__decrementable(const const_iterator* __i) const 2276{ 2277 return !empty() && __i->__ptr_ != base::__end_.__next_; 2278} 2279 2280template <class _Tp, class _Alloc> 2281bool 2282list<_Tp, _Alloc>::__addable(const const_iterator*, ptrdiff_t) const 2283{ 2284 return false; 2285} 2286 2287template <class _Tp, class _Alloc> 2288bool 2289list<_Tp, _Alloc>::__subscriptable(const const_iterator*, ptrdiff_t) const 2290{ 2291 return false; 2292} 2293 2294#endif // _LIBCPP_ENABLE_DEBUG_MODE 2295 2296template <class _Tp, class _Alloc> 2297inline _LIBCPP_INLINE_VISIBILITY 2298bool 2299operator==(const list<_Tp, _Alloc>& __x, const list<_Tp, _Alloc>& __y) 2300{ 2301 return __x.size() == __y.size() && _VSTD::equal(__x.begin(), __x.end(), __y.begin()); 2302} 2303 2304#if _LIBCPP_STD_VER <= 17 2305 2306template <class _Tp, class _Alloc> 2307inline _LIBCPP_INLINE_VISIBILITY 2308bool 2309operator< (const list<_Tp, _Alloc>& __x, const list<_Tp, _Alloc>& __y) 2310{ 2311 return _VSTD::lexicographical_compare(__x.begin(), __x.end(), __y.begin(), __y.end()); 2312} 2313 2314template <class _Tp, class _Alloc> 2315inline _LIBCPP_INLINE_VISIBILITY 2316bool 2317operator!=(const list<_Tp, _Alloc>& __x, const list<_Tp, _Alloc>& __y) 2318{ 2319 return !(__x == __y); 2320} 2321 2322template <class _Tp, class _Alloc> 2323inline _LIBCPP_INLINE_VISIBILITY 2324bool 2325operator> (const list<_Tp, _Alloc>& __x, const list<_Tp, _Alloc>& __y) 2326{ 2327 return __y < __x; 2328} 2329 2330template <class _Tp, class _Alloc> 2331inline _LIBCPP_INLINE_VISIBILITY 2332bool 2333operator>=(const list<_Tp, _Alloc>& __x, const list<_Tp, _Alloc>& __y) 2334{ 2335 return !(__x < __y); 2336} 2337 2338template <class _Tp, class _Alloc> 2339inline _LIBCPP_INLINE_VISIBILITY 2340bool 2341operator<=(const list<_Tp, _Alloc>& __x, const list<_Tp, _Alloc>& __y) 2342{ 2343 return !(__y < __x); 2344} 2345 2346#else // _LIBCPP_STD_VER <= 17 2347 2348template<class _Tp, class _Allocator> 2349inline _LIBCPP_HIDE_FROM_ABI 2350__synth_three_way_result<_Tp> 2351operator<=>(const list<_Tp, _Allocator>& __x, const list<_Tp, _Allocator>& __y) 2352{ 2353 return std::lexicographical_compare_three_way( 2354 __x.begin(), __x.end(), __y.begin(), __y.end(), std::__synth_three_way<_Tp, _Tp>); 2355} 2356 2357#endif // _LIBCPP_STD_VER <= 17 2358 2359template <class _Tp, class _Alloc> 2360inline _LIBCPP_INLINE_VISIBILITY 2361void 2362swap(list<_Tp, _Alloc>& __x, list<_Tp, _Alloc>& __y) 2363 _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y))) 2364{ 2365 __x.swap(__y); 2366} 2367 2368#if _LIBCPP_STD_VER >= 20 2369template <class _Tp, class _Allocator, class _Predicate> 2370inline _LIBCPP_INLINE_VISIBILITY typename list<_Tp, _Allocator>::size_type 2371erase_if(list<_Tp, _Allocator>& __c, _Predicate __pred) { 2372 return __c.remove_if(__pred); 2373} 2374 2375template <class _Tp, class _Allocator, class _Up> 2376inline _LIBCPP_INLINE_VISIBILITY typename list<_Tp, _Allocator>::size_type 2377erase(list<_Tp, _Allocator>& __c, const _Up& __v) { 2378 return _VSTD::erase_if(__c, [&](auto& __elem) { return __elem == __v; }); 2379} 2380 2381template <> 2382inline constexpr bool __format::__enable_insertable<std::list<char>> = true; 2383#ifndef _LIBCPP_HAS_NO_WIDE_CHARACTERS 2384template <> 2385inline constexpr bool __format::__enable_insertable<std::list<wchar_t>> = true; 2386#endif 2387 2388#endif // _LIBCPP_STD_VER >= 20 2389 2390_LIBCPP_END_NAMESPACE_STD 2391 2392#if _LIBCPP_STD_VER >= 17 2393_LIBCPP_BEGIN_NAMESPACE_STD 2394namespace pmr { 2395template <class _ValueT> 2396using list = std::list<_ValueT, polymorphic_allocator<_ValueT>>; 2397} // namespace pmr 2398_LIBCPP_END_NAMESPACE_STD 2399#endif 2400 2401_LIBCPP_POP_MACROS 2402 2403#if !defined(_LIBCPP_REMOVE_TRANSITIVE_INCLUDES) && _LIBCPP_STD_VER <= 20 2404# include <algorithm> 2405# include <atomic> 2406# include <concepts> 2407# include <cstdlib> 2408# include <functional> 2409# include <iosfwd> 2410# include <iterator> 2411# include <type_traits> 2412# include <typeinfo> 2413#endif 2414 2415#endif // _LIBCPP_LIST 2416