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