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