1// -*- C++ -*- 2//===---------------------------- list ------------------------------------===// 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 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; 652#else 653 _NOEXCEPT_(!__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, __default_init_tag()) 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 774#else 775 _NOEXCEPT_(!__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#if _LIBCPP_STD_VER > 17 862 typedef size_type __remove_return_type; 863#else 864 typedef void __remove_return_type; 865#endif 866 867 _LIBCPP_INLINE_VISIBILITY 868 list() 869 _NOEXCEPT_(is_nothrow_default_constructible<__node_allocator>::value) 870 { 871#if _LIBCPP_DEBUG_LEVEL >= 2 872 __get_db()->__insert_c(this); 873#endif 874 } 875 _LIBCPP_INLINE_VISIBILITY 876 explicit list(const allocator_type& __a) : base(__a) 877 { 878#if _LIBCPP_DEBUG_LEVEL >= 2 879 __get_db()->__insert_c(this); 880#endif 881 } 882 explicit list(size_type __n); 883#if _LIBCPP_STD_VER > 11 884 explicit list(size_type __n, const allocator_type& __a); 885#endif 886 list(size_type __n, const value_type& __x); 887 list(size_type __n, const value_type& __x, const allocator_type& __a); 888 template <class _InpIter> 889 list(_InpIter __f, _InpIter __l, 890 typename enable_if<__is_cpp17_input_iterator<_InpIter>::value>::type* = 0); 891 template <class _InpIter> 892 list(_InpIter __f, _InpIter __l, const allocator_type& __a, 893 typename enable_if<__is_cpp17_input_iterator<_InpIter>::value>::type* = 0); 894 895 list(const list& __c); 896 list(const list& __c, const allocator_type& __a); 897 _LIBCPP_INLINE_VISIBILITY 898 list& operator=(const list& __c); 899#ifndef _LIBCPP_CXX03_LANG 900 list(initializer_list<value_type> __il); 901 list(initializer_list<value_type> __il, const allocator_type& __a); 902 903 _LIBCPP_INLINE_VISIBILITY 904 list(list&& __c) 905 _NOEXCEPT_(is_nothrow_move_constructible<__node_allocator>::value); 906 _LIBCPP_INLINE_VISIBILITY 907 list(list&& __c, const allocator_type& __a); 908 _LIBCPP_INLINE_VISIBILITY 909 list& operator=(list&& __c) 910 _NOEXCEPT_( 911 __node_alloc_traits::propagate_on_container_move_assignment::value && 912 is_nothrow_move_assignable<__node_allocator>::value); 913 914 _LIBCPP_INLINE_VISIBILITY 915 list& operator=(initializer_list<value_type> __il) 916 {assign(__il.begin(), __il.end()); return *this;} 917 918 _LIBCPP_INLINE_VISIBILITY 919 void assign(initializer_list<value_type> __il) 920 {assign(__il.begin(), __il.end());} 921#endif // _LIBCPP_CXX03_LANG 922 923 template <class _InpIter> 924 void assign(_InpIter __f, _InpIter __l, 925 typename enable_if<__is_cpp17_input_iterator<_InpIter>::value>::type* = 0); 926 void assign(size_type __n, const value_type& __x); 927 928 _LIBCPP_INLINE_VISIBILITY 929 allocator_type get_allocator() const _NOEXCEPT; 930 931 _LIBCPP_INLINE_VISIBILITY 932 size_type size() const _NOEXCEPT {return base::__sz();} 933 _LIBCPP_NODISCARD_AFTER_CXX17 _LIBCPP_INLINE_VISIBILITY 934 bool empty() const _NOEXCEPT {return base::empty();} 935 _LIBCPP_INLINE_VISIBILITY 936 size_type max_size() const _NOEXCEPT 937 { 938 return std::min<size_type>( 939 base::__node_alloc_max_size(), 940 numeric_limits<difference_type >::max()); 941 } 942 943 _LIBCPP_INLINE_VISIBILITY 944 iterator begin() _NOEXCEPT {return base::begin();} 945 _LIBCPP_INLINE_VISIBILITY 946 const_iterator begin() const _NOEXCEPT {return base::begin();} 947 _LIBCPP_INLINE_VISIBILITY 948 iterator end() _NOEXCEPT {return base::end();} 949 _LIBCPP_INLINE_VISIBILITY 950 const_iterator end() const _NOEXCEPT {return base::end();} 951 _LIBCPP_INLINE_VISIBILITY 952 const_iterator cbegin() const _NOEXCEPT {return base::begin();} 953 _LIBCPP_INLINE_VISIBILITY 954 const_iterator cend() const _NOEXCEPT {return base::end();} 955 956 _LIBCPP_INLINE_VISIBILITY 957 reverse_iterator rbegin() _NOEXCEPT 958 {return reverse_iterator(end());} 959 _LIBCPP_INLINE_VISIBILITY 960 const_reverse_iterator rbegin() const _NOEXCEPT 961 {return const_reverse_iterator(end());} 962 _LIBCPP_INLINE_VISIBILITY 963 reverse_iterator rend() _NOEXCEPT 964 {return reverse_iterator(begin());} 965 _LIBCPP_INLINE_VISIBILITY 966 const_reverse_iterator rend() const _NOEXCEPT 967 {return const_reverse_iterator(begin());} 968 _LIBCPP_INLINE_VISIBILITY 969 const_reverse_iterator crbegin() const _NOEXCEPT 970 {return const_reverse_iterator(end());} 971 _LIBCPP_INLINE_VISIBILITY 972 const_reverse_iterator crend() const _NOEXCEPT 973 {return const_reverse_iterator(begin());} 974 975 _LIBCPP_INLINE_VISIBILITY 976 reference front() 977 { 978 _LIBCPP_ASSERT(!empty(), "list::front called on empty list"); 979 return base::__end_.__next_->__as_node()->__value_; 980 } 981 _LIBCPP_INLINE_VISIBILITY 982 const_reference front() const 983 { 984 _LIBCPP_ASSERT(!empty(), "list::front called on empty list"); 985 return base::__end_.__next_->__as_node()->__value_; 986 } 987 _LIBCPP_INLINE_VISIBILITY 988 reference back() 989 { 990 _LIBCPP_ASSERT(!empty(), "list::back called on empty list"); 991 return base::__end_.__prev_->__as_node()->__value_; 992 } 993 _LIBCPP_INLINE_VISIBILITY 994 const_reference back() const 995 { 996 _LIBCPP_ASSERT(!empty(), "list::back called on empty list"); 997 return base::__end_.__prev_->__as_node()->__value_; 998 } 999 1000#ifndef _LIBCPP_CXX03_LANG 1001 void push_front(value_type&& __x); 1002 void push_back(value_type&& __x); 1003 1004 template <class... _Args> 1005#if _LIBCPP_STD_VER > 14 1006 reference emplace_front(_Args&&... __args); 1007#else 1008 void emplace_front(_Args&&... __args); 1009#endif 1010 template <class... _Args> 1011#if _LIBCPP_STD_VER > 14 1012 reference emplace_back(_Args&&... __args); 1013#else 1014 void emplace_back(_Args&&... __args); 1015#endif 1016 template <class... _Args> 1017 iterator emplace(const_iterator __p, _Args&&... __args); 1018 1019 iterator insert(const_iterator __p, value_type&& __x); 1020 1021 _LIBCPP_INLINE_VISIBILITY 1022 iterator insert(const_iterator __p, initializer_list<value_type> __il) 1023 {return insert(__p, __il.begin(), __il.end());} 1024#endif // _LIBCPP_CXX03_LANG 1025 1026 void push_front(const value_type& __x); 1027 void push_back(const value_type& __x); 1028 1029#ifndef _LIBCPP_CXX03_LANG 1030 template <class _Arg> 1031 _LIBCPP_INLINE_VISIBILITY 1032 void __emplace_back(_Arg&& __arg) { emplace_back(_VSTD::forward<_Arg>(__arg)); } 1033#else 1034 _LIBCPP_INLINE_VISIBILITY 1035 void __emplace_back(value_type const& __arg) { push_back(__arg); } 1036#endif 1037 1038 iterator insert(const_iterator __p, const value_type& __x); 1039 iterator insert(const_iterator __p, size_type __n, const value_type& __x); 1040 template <class _InpIter> 1041 iterator insert(const_iterator __p, _InpIter __f, _InpIter __l, 1042 typename enable_if<__is_cpp17_input_iterator<_InpIter>::value>::type* = 0); 1043 1044 _LIBCPP_INLINE_VISIBILITY 1045 void swap(list& __c) 1046#if _LIBCPP_STD_VER >= 14 1047 _NOEXCEPT 1048#else 1049 _NOEXCEPT_(!__node_alloc_traits::propagate_on_container_swap::value || 1050 __is_nothrow_swappable<__node_allocator>::value) 1051#endif 1052 {base::swap(__c);} 1053 _LIBCPP_INLINE_VISIBILITY 1054 void clear() _NOEXCEPT {base::clear();} 1055 1056 void pop_front(); 1057 void pop_back(); 1058 1059 iterator erase(const_iterator __p); 1060 iterator erase(const_iterator __f, const_iterator __l); 1061 1062 void resize(size_type __n); 1063 void resize(size_type __n, const value_type& __x); 1064 1065 void splice(const_iterator __p, list& __c); 1066#ifndef _LIBCPP_CXX03_LANG 1067 _LIBCPP_INLINE_VISIBILITY 1068 void splice(const_iterator __p, list&& __c) {splice(__p, __c);} 1069 _LIBCPP_INLINE_VISIBILITY 1070 void splice(const_iterator __p, list&& __c, const_iterator __i) 1071 {splice(__p, __c, __i);} 1072 _LIBCPP_INLINE_VISIBILITY 1073 void splice(const_iterator __p, list&& __c, const_iterator __f, const_iterator __l) 1074 {splice(__p, __c, __f, __l);} 1075#endif 1076 void splice(const_iterator __p, list& __c, const_iterator __i); 1077 void splice(const_iterator __p, list& __c, const_iterator __f, const_iterator __l); 1078 1079 __remove_return_type remove(const value_type& __x); 1080 template <class _Pred> __remove_return_type remove_if(_Pred __pred); 1081 _LIBCPP_INLINE_VISIBILITY 1082 __remove_return_type unique() { return unique(__equal_to<value_type>()); } 1083 template <class _BinaryPred> 1084 __remove_return_type unique(_BinaryPred __binary_pred); 1085 _LIBCPP_INLINE_VISIBILITY 1086 void merge(list& __c); 1087#ifndef _LIBCPP_CXX03_LANG 1088 _LIBCPP_INLINE_VISIBILITY 1089 void merge(list&& __c) {merge(__c);} 1090 1091 template <class _Comp> 1092 _LIBCPP_INLINE_VISIBILITY 1093 void merge(list&& __c, _Comp __comp) {merge(__c, __comp);} 1094#endif 1095 template <class _Comp> 1096 void merge(list& __c, _Comp __comp); 1097 1098 _LIBCPP_INLINE_VISIBILITY 1099 void sort(); 1100 template <class _Comp> 1101 _LIBCPP_INLINE_VISIBILITY 1102 void sort(_Comp __comp); 1103 1104 void reverse() _NOEXCEPT; 1105 1106 bool __invariants() const; 1107 1108 typedef __allocator_destructor<__node_allocator> __node_destructor; 1109 typedef unique_ptr<__node, __node_destructor> __hold_pointer; 1110 1111 _LIBCPP_INLINE_VISIBILITY 1112 __hold_pointer __allocate_node(__node_allocator& __na) { 1113 __node_pointer __p = __node_alloc_traits::allocate(__na, 1); 1114 __p->__prev_ = nullptr; 1115 return __hold_pointer(__p, __node_destructor(__na, 1)); 1116 } 1117 1118#if _LIBCPP_DEBUG_LEVEL >= 2 1119 1120 bool __dereferenceable(const const_iterator* __i) const; 1121 bool __decrementable(const const_iterator* __i) const; 1122 bool __addable(const const_iterator* __i, ptrdiff_t __n) const; 1123 bool __subscriptable(const const_iterator* __i, ptrdiff_t __n) const; 1124 1125#endif // _LIBCPP_DEBUG_LEVEL >= 2 1126 1127private: 1128 _LIBCPP_INLINE_VISIBILITY 1129 static void __link_nodes (__link_pointer __p, __link_pointer __f, __link_pointer __l); 1130 _LIBCPP_INLINE_VISIBILITY 1131 void __link_nodes_at_front(__link_pointer __f, __link_pointer __l); 1132 _LIBCPP_INLINE_VISIBILITY 1133 void __link_nodes_at_back (__link_pointer __f, __link_pointer __l); 1134 iterator __iterator(size_type __n); 1135 template <class _Comp> 1136 static iterator __sort(iterator __f1, iterator __e2, size_type __n, _Comp& __comp); 1137 1138 void __move_assign(list& __c, true_type) 1139 _NOEXCEPT_(is_nothrow_move_assignable<__node_allocator>::value); 1140 void __move_assign(list& __c, false_type); 1141}; 1142 1143#ifndef _LIBCPP_HAS_NO_DEDUCTION_GUIDES 1144template<class _InputIterator, 1145 class _Alloc = typename std::allocator<typename iterator_traits<_InputIterator>::value_type>, 1146 class = typename enable_if<__is_allocator<_Alloc>::value, void>::type 1147 > 1148list(_InputIterator, _InputIterator) 1149 -> list<typename iterator_traits<_InputIterator>::value_type, _Alloc>; 1150 1151template<class _InputIterator, 1152 class _Alloc, 1153 class = typename enable_if<__is_allocator<_Alloc>::value, void>::type 1154 > 1155list(_InputIterator, _InputIterator, _Alloc) 1156 -> list<typename iterator_traits<_InputIterator>::value_type, _Alloc>; 1157#endif 1158 1159// Link in nodes [__f, __l] just prior to __p 1160template <class _Tp, class _Alloc> 1161inline 1162void 1163list<_Tp, _Alloc>::__link_nodes(__link_pointer __p, __link_pointer __f, __link_pointer __l) 1164{ 1165 __p->__prev_->__next_ = __f; 1166 __f->__prev_ = __p->__prev_; 1167 __p->__prev_ = __l; 1168 __l->__next_ = __p; 1169} 1170 1171// Link in nodes [__f, __l] at the front of the list 1172template <class _Tp, class _Alloc> 1173inline 1174void 1175list<_Tp, _Alloc>::__link_nodes_at_front(__link_pointer __f, __link_pointer __l) 1176{ 1177 __f->__prev_ = base::__end_as_link(); 1178 __l->__next_ = base::__end_.__next_; 1179 __l->__next_->__prev_ = __l; 1180 base::__end_.__next_ = __f; 1181} 1182 1183// Link in nodes [__f, __l] at the back of the list 1184template <class _Tp, class _Alloc> 1185inline 1186void 1187list<_Tp, _Alloc>::__link_nodes_at_back(__link_pointer __f, __link_pointer __l) 1188{ 1189 __l->__next_ = base::__end_as_link(); 1190 __f->__prev_ = base::__end_.__prev_; 1191 __f->__prev_->__next_ = __f; 1192 base::__end_.__prev_ = __l; 1193} 1194 1195 1196template <class _Tp, class _Alloc> 1197inline 1198typename list<_Tp, _Alloc>::iterator 1199list<_Tp, _Alloc>::__iterator(size_type __n) 1200{ 1201 return __n <= base::__sz() / 2 ? _VSTD::next(begin(), __n) 1202 : _VSTD::prev(end(), base::__sz() - __n); 1203} 1204 1205template <class _Tp, class _Alloc> 1206list<_Tp, _Alloc>::list(size_type __n) 1207{ 1208#if _LIBCPP_DEBUG_LEVEL >= 2 1209 __get_db()->__insert_c(this); 1210#endif 1211 for (; __n > 0; --__n) 1212#ifndef _LIBCPP_CXX03_LANG 1213 emplace_back(); 1214#else 1215 push_back(value_type()); 1216#endif 1217} 1218 1219#if _LIBCPP_STD_VER > 11 1220template <class _Tp, class _Alloc> 1221list<_Tp, _Alloc>::list(size_type __n, const allocator_type& __a) : base(__a) 1222{ 1223#if _LIBCPP_DEBUG_LEVEL >= 2 1224 __get_db()->__insert_c(this); 1225#endif 1226 for (; __n > 0; --__n) 1227 emplace_back(); 1228} 1229#endif 1230 1231template <class _Tp, class _Alloc> 1232list<_Tp, _Alloc>::list(size_type __n, const value_type& __x) 1233{ 1234#if _LIBCPP_DEBUG_LEVEL >= 2 1235 __get_db()->__insert_c(this); 1236#endif 1237 for (; __n > 0; --__n) 1238 push_back(__x); 1239} 1240 1241template <class _Tp, class _Alloc> 1242list<_Tp, _Alloc>::list(size_type __n, const value_type& __x, const allocator_type& __a) 1243 : base(__a) 1244{ 1245#if _LIBCPP_DEBUG_LEVEL >= 2 1246 __get_db()->__insert_c(this); 1247#endif 1248 for (; __n > 0; --__n) 1249 push_back(__x); 1250} 1251 1252template <class _Tp, class _Alloc> 1253template <class _InpIter> 1254list<_Tp, _Alloc>::list(_InpIter __f, _InpIter __l, 1255 typename enable_if<__is_cpp17_input_iterator<_InpIter>::value>::type*) 1256{ 1257#if _LIBCPP_DEBUG_LEVEL >= 2 1258 __get_db()->__insert_c(this); 1259#endif 1260 for (; __f != __l; ++__f) 1261 __emplace_back(*__f); 1262} 1263 1264template <class _Tp, class _Alloc> 1265template <class _InpIter> 1266list<_Tp, _Alloc>::list(_InpIter __f, _InpIter __l, const allocator_type& __a, 1267 typename enable_if<__is_cpp17_input_iterator<_InpIter>::value>::type*) 1268 : base(__a) 1269{ 1270#if _LIBCPP_DEBUG_LEVEL >= 2 1271 __get_db()->__insert_c(this); 1272#endif 1273 for (; __f != __l; ++__f) 1274 __emplace_back(*__f); 1275} 1276 1277template <class _Tp, class _Alloc> 1278list<_Tp, _Alloc>::list(const list& __c) 1279 : base(__node_alloc_traits::select_on_container_copy_construction( 1280 __c.__node_alloc())) { 1281#if _LIBCPP_DEBUG_LEVEL >= 2 1282 __get_db()->__insert_c(this); 1283#endif 1284 for (const_iterator __i = __c.begin(), __e = __c.end(); __i != __e; ++__i) 1285 push_back(*__i); 1286} 1287 1288template <class _Tp, class _Alloc> 1289list<_Tp, _Alloc>::list(const list& __c, const allocator_type& __a) 1290 : base(__a) 1291{ 1292#if _LIBCPP_DEBUG_LEVEL >= 2 1293 __get_db()->__insert_c(this); 1294#endif 1295 for (const_iterator __i = __c.begin(), __e = __c.end(); __i != __e; ++__i) 1296 push_back(*__i); 1297} 1298 1299#ifndef _LIBCPP_CXX03_LANG 1300 1301template <class _Tp, class _Alloc> 1302list<_Tp, _Alloc>::list(initializer_list<value_type> __il, const allocator_type& __a) 1303 : base(__a) 1304{ 1305#if _LIBCPP_DEBUG_LEVEL >= 2 1306 __get_db()->__insert_c(this); 1307#endif 1308 for (typename initializer_list<value_type>::const_iterator __i = __il.begin(), 1309 __e = __il.end(); __i != __e; ++__i) 1310 push_back(*__i); 1311} 1312 1313template <class _Tp, class _Alloc> 1314list<_Tp, _Alloc>::list(initializer_list<value_type> __il) 1315{ 1316#if _LIBCPP_DEBUG_LEVEL >= 2 1317 __get_db()->__insert_c(this); 1318#endif 1319 for (typename initializer_list<value_type>::const_iterator __i = __il.begin(), 1320 __e = __il.end(); __i != __e; ++__i) 1321 push_back(*__i); 1322} 1323 1324template <class _Tp, class _Alloc> 1325inline list<_Tp, _Alloc>::list(list&& __c) 1326 _NOEXCEPT_(is_nothrow_move_constructible<__node_allocator>::value) 1327 : base(_VSTD::move(__c.__node_alloc())) { 1328#if _LIBCPP_DEBUG_LEVEL >= 2 1329 __get_db()->__insert_c(this); 1330#endif 1331 splice(end(), __c); 1332} 1333 1334template <class _Tp, class _Alloc> 1335inline 1336list<_Tp, _Alloc>::list(list&& __c, const allocator_type& __a) 1337 : base(__a) 1338{ 1339#if _LIBCPP_DEBUG_LEVEL >= 2 1340 __get_db()->__insert_c(this); 1341#endif 1342 if (__a == __c.get_allocator()) 1343 splice(end(), __c); 1344 else 1345 { 1346 typedef move_iterator<iterator> _Ip; 1347 assign(_Ip(__c.begin()), _Ip(__c.end())); 1348 } 1349} 1350 1351template <class _Tp, class _Alloc> 1352inline 1353list<_Tp, _Alloc>& 1354list<_Tp, _Alloc>::operator=(list&& __c) 1355 _NOEXCEPT_( 1356 __node_alloc_traits::propagate_on_container_move_assignment::value && 1357 is_nothrow_move_assignable<__node_allocator>::value) 1358{ 1359 __move_assign(__c, integral_constant<bool, 1360 __node_alloc_traits::propagate_on_container_move_assignment::value>()); 1361 return *this; 1362} 1363 1364template <class _Tp, class _Alloc> 1365void 1366list<_Tp, _Alloc>::__move_assign(list& __c, false_type) 1367{ 1368 if (base::__node_alloc() != __c.__node_alloc()) 1369 { 1370 typedef move_iterator<iterator> _Ip; 1371 assign(_Ip(__c.begin()), _Ip(__c.end())); 1372 } 1373 else 1374 __move_assign(__c, true_type()); 1375} 1376 1377template <class _Tp, class _Alloc> 1378void 1379list<_Tp, _Alloc>::__move_assign(list& __c, true_type) 1380 _NOEXCEPT_(is_nothrow_move_assignable<__node_allocator>::value) 1381{ 1382 clear(); 1383 base::__move_assign_alloc(__c); 1384 splice(end(), __c); 1385} 1386 1387#endif // _LIBCPP_CXX03_LANG 1388 1389template <class _Tp, class _Alloc> 1390inline 1391list<_Tp, _Alloc>& 1392list<_Tp, _Alloc>::operator=(const list& __c) 1393{ 1394 if (this != &__c) 1395 { 1396 base::__copy_assign_alloc(__c); 1397 assign(__c.begin(), __c.end()); 1398 } 1399 return *this; 1400} 1401 1402template <class _Tp, class _Alloc> 1403template <class _InpIter> 1404void 1405list<_Tp, _Alloc>::assign(_InpIter __f, _InpIter __l, 1406 typename enable_if<__is_cpp17_input_iterator<_InpIter>::value>::type*) 1407{ 1408 iterator __i = begin(); 1409 iterator __e = end(); 1410 for (; __f != __l && __i != __e; ++__f, ++__i) 1411 *__i = *__f; 1412 if (__i == __e) 1413 insert(__e, __f, __l); 1414 else 1415 erase(__i, __e); 1416#if _LIBCPP_DEBUG_LEVEL >= 2 1417 __get_db()->__invalidate_all(this); 1418#endif 1419} 1420 1421template <class _Tp, class _Alloc> 1422void 1423list<_Tp, _Alloc>::assign(size_type __n, const value_type& __x) 1424{ 1425 iterator __i = begin(); 1426 iterator __e = end(); 1427 for (; __n > 0 && __i != __e; --__n, ++__i) 1428 *__i = __x; 1429 if (__i == __e) 1430 insert(__e, __n, __x); 1431 else 1432 erase(__i, __e); 1433#if _LIBCPP_DEBUG_LEVEL >= 2 1434 __get_db()->__invalidate_all(this); 1435#endif 1436} 1437 1438template <class _Tp, class _Alloc> 1439inline 1440_Alloc 1441list<_Tp, _Alloc>::get_allocator() const _NOEXCEPT 1442{ 1443 return allocator_type(base::__node_alloc()); 1444} 1445 1446template <class _Tp, class _Alloc> 1447typename list<_Tp, _Alloc>::iterator 1448list<_Tp, _Alloc>::insert(const_iterator __p, const value_type& __x) 1449{ 1450#if _LIBCPP_DEBUG_LEVEL >= 2 1451 _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__p) == this, 1452 "list::insert(iterator, x) called with an iterator not" 1453 " referring to this list"); 1454#endif 1455 __node_allocator& __na = base::__node_alloc(); 1456 __hold_pointer __hold = __allocate_node(__na); 1457 __node_alloc_traits::construct(__na, _VSTD::addressof(__hold->__value_), __x); 1458 __link_nodes(__p.__ptr_, __hold->__as_link(), __hold->__as_link()); 1459 ++base::__sz(); 1460#if _LIBCPP_DEBUG_LEVEL >= 2 1461 return iterator(__hold.release()->__as_link(), this); 1462#else 1463 return iterator(__hold.release()->__as_link()); 1464#endif 1465} 1466 1467template <class _Tp, class _Alloc> 1468typename list<_Tp, _Alloc>::iterator 1469list<_Tp, _Alloc>::insert(const_iterator __p, size_type __n, const value_type& __x) 1470{ 1471#if _LIBCPP_DEBUG_LEVEL >= 2 1472 _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__p) == this, 1473 "list::insert(iterator, n, x) called with an iterator not" 1474 " referring to this list"); 1475 iterator __r(__p.__ptr_, this); 1476#else 1477 iterator __r(__p.__ptr_); 1478#endif 1479 if (__n > 0) 1480 { 1481 size_type __ds = 0; 1482 __node_allocator& __na = base::__node_alloc(); 1483 __hold_pointer __hold = __allocate_node(__na); 1484 __node_alloc_traits::construct(__na, _VSTD::addressof(__hold->__value_), __x); 1485 ++__ds; 1486#if _LIBCPP_DEBUG_LEVEL >= 2 1487 __r = iterator(__hold->__as_link(), this); 1488#else 1489 __r = iterator(__hold->__as_link()); 1490#endif 1491 __hold.release(); 1492 iterator __e = __r; 1493#ifndef _LIBCPP_NO_EXCEPTIONS 1494 try 1495 { 1496#endif // _LIBCPP_NO_EXCEPTIONS 1497 for (--__n; __n != 0; --__n, ++__e, ++__ds) 1498 { 1499 __hold.reset(__node_alloc_traits::allocate(__na, 1)); 1500 __node_alloc_traits::construct(__na, _VSTD::addressof(__hold->__value_), __x); 1501 __e.__ptr_->__next_ = __hold->__as_link(); 1502 __hold->__prev_ = __e.__ptr_; 1503 __hold.release(); 1504 } 1505#ifndef _LIBCPP_NO_EXCEPTIONS 1506 } 1507 catch (...) 1508 { 1509 while (true) 1510 { 1511 __node_alloc_traits::destroy(__na, _VSTD::addressof(*__e)); 1512 __link_pointer __prev = __e.__ptr_->__prev_; 1513 __node_alloc_traits::deallocate(__na, __e.__ptr_->__as_node(), 1); 1514 if (__prev == 0) 1515 break; 1516#if _LIBCPP_DEBUG_LEVEL >= 2 1517 __e = iterator(__prev, this); 1518#else 1519 __e = iterator(__prev); 1520#endif 1521 } 1522 throw; 1523 } 1524#endif // _LIBCPP_NO_EXCEPTIONS 1525 __link_nodes(__p.__ptr_, __r.__ptr_, __e.__ptr_); 1526 base::__sz() += __ds; 1527 } 1528 return __r; 1529} 1530 1531template <class _Tp, class _Alloc> 1532template <class _InpIter> 1533typename list<_Tp, _Alloc>::iterator 1534list<_Tp, _Alloc>::insert(const_iterator __p, _InpIter __f, _InpIter __l, 1535 typename enable_if<__is_cpp17_input_iterator<_InpIter>::value>::type*) 1536{ 1537#if _LIBCPP_DEBUG_LEVEL >= 2 1538 _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__p) == this, 1539 "list::insert(iterator, range) called with an iterator not" 1540 " referring to this list"); 1541 iterator __r(__p.__ptr_, this); 1542#else 1543 iterator __r(__p.__ptr_); 1544#endif 1545 if (__f != __l) 1546 { 1547 size_type __ds = 0; 1548 __node_allocator& __na = base::__node_alloc(); 1549 __hold_pointer __hold = __allocate_node(__na); 1550 __node_alloc_traits::construct(__na, _VSTD::addressof(__hold->__value_), *__f); 1551 ++__ds; 1552#if _LIBCPP_DEBUG_LEVEL >= 2 1553 __r = iterator(__hold.get()->__as_link(), this); 1554#else 1555 __r = iterator(__hold.get()->__as_link()); 1556#endif 1557 __hold.release(); 1558 iterator __e = __r; 1559#ifndef _LIBCPP_NO_EXCEPTIONS 1560 try 1561 { 1562#endif // _LIBCPP_NO_EXCEPTIONS 1563 for (++__f; __f != __l; ++__f, (void) ++__e, (void) ++__ds) 1564 { 1565 __hold.reset(__node_alloc_traits::allocate(__na, 1)); 1566 __node_alloc_traits::construct(__na, _VSTD::addressof(__hold->__value_), *__f); 1567 __e.__ptr_->__next_ = __hold.get()->__as_link(); 1568 __hold->__prev_ = __e.__ptr_; 1569 __hold.release(); 1570 } 1571#ifndef _LIBCPP_NO_EXCEPTIONS 1572 } 1573 catch (...) 1574 { 1575 while (true) 1576 { 1577 __node_alloc_traits::destroy(__na, _VSTD::addressof(*__e)); 1578 __link_pointer __prev = __e.__ptr_->__prev_; 1579 __node_alloc_traits::deallocate(__na, __e.__ptr_->__as_node(), 1); 1580 if (__prev == 0) 1581 break; 1582#if _LIBCPP_DEBUG_LEVEL >= 2 1583 __e = iterator(__prev, this); 1584#else 1585 __e = iterator(__prev); 1586#endif 1587 } 1588 throw; 1589 } 1590#endif // _LIBCPP_NO_EXCEPTIONS 1591 __link_nodes(__p.__ptr_, __r.__ptr_, __e.__ptr_); 1592 base::__sz() += __ds; 1593 } 1594 return __r; 1595} 1596 1597template <class _Tp, class _Alloc> 1598void 1599list<_Tp, _Alloc>::push_front(const value_type& __x) 1600{ 1601 __node_allocator& __na = base::__node_alloc(); 1602 __hold_pointer __hold = __allocate_node(__na); 1603 __node_alloc_traits::construct(__na, _VSTD::addressof(__hold->__value_), __x); 1604 __link_pointer __nl = __hold->__as_link(); 1605 __link_nodes_at_front(__nl, __nl); 1606 ++base::__sz(); 1607 __hold.release(); 1608} 1609 1610template <class _Tp, class _Alloc> 1611void 1612list<_Tp, _Alloc>::push_back(const value_type& __x) 1613{ 1614 __node_allocator& __na = base::__node_alloc(); 1615 __hold_pointer __hold = __allocate_node(__na); 1616 __node_alloc_traits::construct(__na, _VSTD::addressof(__hold->__value_), __x); 1617 __link_nodes_at_back(__hold.get()->__as_link(), __hold.get()->__as_link()); 1618 ++base::__sz(); 1619 __hold.release(); 1620} 1621 1622#ifndef _LIBCPP_CXX03_LANG 1623 1624template <class _Tp, class _Alloc> 1625void 1626list<_Tp, _Alloc>::push_front(value_type&& __x) 1627{ 1628 __node_allocator& __na = base::__node_alloc(); 1629 __hold_pointer __hold = __allocate_node(__na); 1630 __node_alloc_traits::construct(__na, _VSTD::addressof(__hold->__value_), _VSTD::move(__x)); 1631 __link_nodes_at_front(__hold.get()->__as_link(), __hold.get()->__as_link()); 1632 ++base::__sz(); 1633 __hold.release(); 1634} 1635 1636template <class _Tp, class _Alloc> 1637void 1638list<_Tp, _Alloc>::push_back(value_type&& __x) 1639{ 1640 __node_allocator& __na = base::__node_alloc(); 1641 __hold_pointer __hold = __allocate_node(__na); 1642 __node_alloc_traits::construct(__na, _VSTD::addressof(__hold->__value_), _VSTD::move(__x)); 1643 __link_nodes_at_back(__hold.get()->__as_link(), __hold.get()->__as_link()); 1644 ++base::__sz(); 1645 __hold.release(); 1646} 1647 1648template <class _Tp, class _Alloc> 1649template <class... _Args> 1650#if _LIBCPP_STD_VER > 14 1651typename list<_Tp, _Alloc>::reference 1652#else 1653void 1654#endif 1655list<_Tp, _Alloc>::emplace_front(_Args&&... __args) 1656{ 1657 __node_allocator& __na = base::__node_alloc(); 1658 __hold_pointer __hold = __allocate_node(__na); 1659 __node_alloc_traits::construct(__na, _VSTD::addressof(__hold->__value_), _VSTD::forward<_Args>(__args)...); 1660 __link_nodes_at_front(__hold.get()->__as_link(), __hold.get()->__as_link()); 1661 ++base::__sz(); 1662#if _LIBCPP_STD_VER > 14 1663 return __hold.release()->__value_; 1664#else 1665 __hold.release(); 1666#endif 1667} 1668 1669template <class _Tp, class _Alloc> 1670template <class... _Args> 1671#if _LIBCPP_STD_VER > 14 1672typename list<_Tp, _Alloc>::reference 1673#else 1674void 1675#endif 1676list<_Tp, _Alloc>::emplace_back(_Args&&... __args) 1677{ 1678 __node_allocator& __na = base::__node_alloc(); 1679 __hold_pointer __hold = __allocate_node(__na); 1680 __node_alloc_traits::construct(__na, _VSTD::addressof(__hold->__value_), _VSTD::forward<_Args>(__args)...); 1681 __link_pointer __nl = __hold->__as_link(); 1682 __link_nodes_at_back(__nl, __nl); 1683 ++base::__sz(); 1684#if _LIBCPP_STD_VER > 14 1685 return __hold.release()->__value_; 1686#else 1687 __hold.release(); 1688#endif 1689} 1690 1691template <class _Tp, class _Alloc> 1692template <class... _Args> 1693typename list<_Tp, _Alloc>::iterator 1694list<_Tp, _Alloc>::emplace(const_iterator __p, _Args&&... __args) 1695{ 1696#if _LIBCPP_DEBUG_LEVEL >= 2 1697 _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__p) == this, 1698 "list::emplace(iterator, args...) called with an iterator not" 1699 " referring to this list"); 1700#endif 1701 __node_allocator& __na = base::__node_alloc(); 1702 __hold_pointer __hold = __allocate_node(__na); 1703 __node_alloc_traits::construct(__na, _VSTD::addressof(__hold->__value_), _VSTD::forward<_Args>(__args)...); 1704 __link_pointer __nl = __hold.get()->__as_link(); 1705 __link_nodes(__p.__ptr_, __nl, __nl); 1706 ++base::__sz(); 1707 __hold.release(); 1708#if _LIBCPP_DEBUG_LEVEL >= 2 1709 return iterator(__nl, this); 1710#else 1711 return iterator(__nl); 1712#endif 1713} 1714 1715template <class _Tp, class _Alloc> 1716typename list<_Tp, _Alloc>::iterator 1717list<_Tp, _Alloc>::insert(const_iterator __p, value_type&& __x) 1718{ 1719#if _LIBCPP_DEBUG_LEVEL >= 2 1720 _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__p) == this, 1721 "list::insert(iterator, x) called with an iterator not" 1722 " referring to this list"); 1723#endif 1724 __node_allocator& __na = base::__node_alloc(); 1725 __hold_pointer __hold = __allocate_node(__na); 1726 __node_alloc_traits::construct(__na, _VSTD::addressof(__hold->__value_), _VSTD::move(__x)); 1727 __link_pointer __nl = __hold->__as_link(); 1728 __link_nodes(__p.__ptr_, __nl, __nl); 1729 ++base::__sz(); 1730 __hold.release(); 1731#if _LIBCPP_DEBUG_LEVEL >= 2 1732 return iterator(__nl, this); 1733#else 1734 return iterator(__nl); 1735#endif 1736} 1737 1738#endif // _LIBCPP_CXX03_LANG 1739 1740template <class _Tp, class _Alloc> 1741void 1742list<_Tp, _Alloc>::pop_front() 1743{ 1744 _LIBCPP_ASSERT(!empty(), "list::pop_front() called with empty list"); 1745 __node_allocator& __na = base::__node_alloc(); 1746 __link_pointer __n = base::__end_.__next_; 1747 base::__unlink_nodes(__n, __n); 1748 --base::__sz(); 1749#if _LIBCPP_DEBUG_LEVEL >= 2 1750 __c_node* __c = __get_db()->__find_c_and_lock(this); 1751 for (__i_node** __p = __c->end_; __p != __c->beg_; ) 1752 { 1753 --__p; 1754 iterator* __i = static_cast<iterator*>((*__p)->__i_); 1755 if (__i->__ptr_ == __n) 1756 { 1757 (*__p)->__c_ = nullptr; 1758 if (--__c->end_ != __p) 1759 memmove(__p, __p+1, (__c->end_ - __p)*sizeof(__i_node*)); 1760 } 1761 } 1762 __get_db()->unlock(); 1763#endif 1764 __node_pointer __np = __n->__as_node(); 1765 __node_alloc_traits::destroy(__na, _VSTD::addressof(__np->__value_)); 1766 __node_alloc_traits::deallocate(__na, __np, 1); 1767} 1768 1769template <class _Tp, class _Alloc> 1770void 1771list<_Tp, _Alloc>::pop_back() 1772{ 1773 _LIBCPP_ASSERT(!empty(), "list::pop_back() called with empty list"); 1774 __node_allocator& __na = base::__node_alloc(); 1775 __link_pointer __n = base::__end_.__prev_; 1776 base::__unlink_nodes(__n, __n); 1777 --base::__sz(); 1778#if _LIBCPP_DEBUG_LEVEL >= 2 1779 __c_node* __c = __get_db()->__find_c_and_lock(this); 1780 for (__i_node** __p = __c->end_; __p != __c->beg_; ) 1781 { 1782 --__p; 1783 iterator* __i = static_cast<iterator*>((*__p)->__i_); 1784 if (__i->__ptr_ == __n) 1785 { 1786 (*__p)->__c_ = nullptr; 1787 if (--__c->end_ != __p) 1788 memmove(__p, __p+1, (__c->end_ - __p)*sizeof(__i_node*)); 1789 } 1790 } 1791 __get_db()->unlock(); 1792#endif 1793 __node_pointer __np = __n->__as_node(); 1794 __node_alloc_traits::destroy(__na, _VSTD::addressof(__np->__value_)); 1795 __node_alloc_traits::deallocate(__na, __np, 1); 1796} 1797 1798template <class _Tp, class _Alloc> 1799typename list<_Tp, _Alloc>::iterator 1800list<_Tp, _Alloc>::erase(const_iterator __p) 1801{ 1802#if _LIBCPP_DEBUG_LEVEL >= 2 1803 _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__p) == this, 1804 "list::erase(iterator) called with an iterator not" 1805 " referring to this list"); 1806#endif 1807 _LIBCPP_ASSERT(__p != end(), 1808 "list::erase(iterator) called with a non-dereferenceable iterator"); 1809 __node_allocator& __na = base::__node_alloc(); 1810 __link_pointer __n = __p.__ptr_; 1811 __link_pointer __r = __n->__next_; 1812 base::__unlink_nodes(__n, __n); 1813 --base::__sz(); 1814#if _LIBCPP_DEBUG_LEVEL >= 2 1815 __c_node* __c = __get_db()->__find_c_and_lock(this); 1816 for (__i_node** __ip = __c->end_; __ip != __c->beg_; ) 1817 { 1818 --__ip; 1819 iterator* __i = static_cast<iterator*>((*__ip)->__i_); 1820 if (__i->__ptr_ == __n) 1821 { 1822 (*__ip)->__c_ = nullptr; 1823 if (--__c->end_ != __ip) 1824 memmove(__ip, __ip+1, (__c->end_ - __ip)*sizeof(__i_node*)); 1825 } 1826 } 1827 __get_db()->unlock(); 1828#endif 1829 __node_pointer __np = __n->__as_node(); 1830 __node_alloc_traits::destroy(__na, _VSTD::addressof(__np->__value_)); 1831 __node_alloc_traits::deallocate(__na, __np, 1); 1832#if _LIBCPP_DEBUG_LEVEL >= 2 1833 return iterator(__r, this); 1834#else 1835 return iterator(__r); 1836#endif 1837} 1838 1839template <class _Tp, class _Alloc> 1840typename list<_Tp, _Alloc>::iterator 1841list<_Tp, _Alloc>::erase(const_iterator __f, const_iterator __l) 1842{ 1843#if _LIBCPP_DEBUG_LEVEL >= 2 1844 _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__f) == this, 1845 "list::erase(iterator, iterator) called with an iterator not" 1846 " referring to this list"); 1847 _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__l) == this, 1848 "list::erase(iterator, iterator) called with an iterator not" 1849 " referring to this list"); 1850#endif 1851 if (__f != __l) 1852 { 1853 __node_allocator& __na = base::__node_alloc(); 1854 base::__unlink_nodes(__f.__ptr_, __l.__ptr_->__prev_); 1855 while (__f != __l) 1856 { 1857 __link_pointer __n = __f.__ptr_; 1858 ++__f; 1859 --base::__sz(); 1860#if _LIBCPP_DEBUG_LEVEL >= 2 1861 __c_node* __c = __get_db()->__find_c_and_lock(this); 1862 for (__i_node** __p = __c->end_; __p != __c->beg_; ) 1863 { 1864 --__p; 1865 iterator* __i = static_cast<iterator*>((*__p)->__i_); 1866 if (__i->__ptr_ == __n) 1867 { 1868 (*__p)->__c_ = nullptr; 1869 if (--__c->end_ != __p) 1870 memmove(__p, __p+1, (__c->end_ - __p)*sizeof(__i_node*)); 1871 } 1872 } 1873 __get_db()->unlock(); 1874#endif 1875 __node_pointer __np = __n->__as_node(); 1876 __node_alloc_traits::destroy(__na, _VSTD::addressof(__np->__value_)); 1877 __node_alloc_traits::deallocate(__na, __np, 1); 1878 } 1879 } 1880#if _LIBCPP_DEBUG_LEVEL >= 2 1881 return iterator(__l.__ptr_, this); 1882#else 1883 return iterator(__l.__ptr_); 1884#endif 1885} 1886 1887template <class _Tp, class _Alloc> 1888void 1889list<_Tp, _Alloc>::resize(size_type __n) 1890{ 1891 if (__n < base::__sz()) 1892 erase(__iterator(__n), end()); 1893 else if (__n > base::__sz()) 1894 { 1895 __n -= base::__sz(); 1896 size_type __ds = 0; 1897 __node_allocator& __na = base::__node_alloc(); 1898 __hold_pointer __hold = __allocate_node(__na); 1899 __node_alloc_traits::construct(__na, _VSTD::addressof(__hold->__value_)); 1900 ++__ds; 1901#if _LIBCPP_DEBUG_LEVEL >= 2 1902 iterator __r = iterator(__hold.release()->__as_link(), this); 1903#else 1904 iterator __r = iterator(__hold.release()->__as_link()); 1905#endif 1906 iterator __e = __r; 1907#ifndef _LIBCPP_NO_EXCEPTIONS 1908 try 1909 { 1910#endif // _LIBCPP_NO_EXCEPTIONS 1911 for (--__n; __n != 0; --__n, ++__e, ++__ds) 1912 { 1913 __hold.reset(__node_alloc_traits::allocate(__na, 1)); 1914 __node_alloc_traits::construct(__na, _VSTD::addressof(__hold->__value_)); 1915 __e.__ptr_->__next_ = __hold.get()->__as_link(); 1916 __hold->__prev_ = __e.__ptr_; 1917 __hold.release(); 1918 } 1919#ifndef _LIBCPP_NO_EXCEPTIONS 1920 } 1921 catch (...) 1922 { 1923 while (true) 1924 { 1925 __node_alloc_traits::destroy(__na, _VSTD::addressof(*__e)); 1926 __link_pointer __prev = __e.__ptr_->__prev_; 1927 __node_alloc_traits::deallocate(__na, __e.__ptr_->__as_node(), 1); 1928 if (__prev == 0) 1929 break; 1930#if _LIBCPP_DEBUG_LEVEL >= 2 1931 __e = iterator(__prev, this); 1932#else 1933 __e = iterator(__prev); 1934#endif 1935 } 1936 throw; 1937 } 1938#endif // _LIBCPP_NO_EXCEPTIONS 1939 __link_nodes_at_back(__r.__ptr_, __e.__ptr_); 1940 base::__sz() += __ds; 1941 } 1942} 1943 1944template <class _Tp, class _Alloc> 1945void 1946list<_Tp, _Alloc>::resize(size_type __n, const value_type& __x) 1947{ 1948 if (__n < base::__sz()) 1949 erase(__iterator(__n), end()); 1950 else if (__n > base::__sz()) 1951 { 1952 __n -= base::__sz(); 1953 size_type __ds = 0; 1954 __node_allocator& __na = base::__node_alloc(); 1955 __hold_pointer __hold = __allocate_node(__na); 1956 __node_alloc_traits::construct(__na, _VSTD::addressof(__hold->__value_), __x); 1957 ++__ds; 1958 __link_pointer __nl = __hold.release()->__as_link(); 1959#if _LIBCPP_DEBUG_LEVEL >= 2 1960 iterator __r = iterator(__nl, this); 1961#else 1962 iterator __r = iterator(__nl); 1963#endif 1964 iterator __e = __r; 1965#ifndef _LIBCPP_NO_EXCEPTIONS 1966 try 1967 { 1968#endif // _LIBCPP_NO_EXCEPTIONS 1969 for (--__n; __n != 0; --__n, ++__e, ++__ds) 1970 { 1971 __hold.reset(__node_alloc_traits::allocate(__na, 1)); 1972 __node_alloc_traits::construct(__na, _VSTD::addressof(__hold->__value_), __x); 1973 __e.__ptr_->__next_ = __hold.get()->__as_link(); 1974 __hold->__prev_ = __e.__ptr_; 1975 __hold.release(); 1976 } 1977#ifndef _LIBCPP_NO_EXCEPTIONS 1978 } 1979 catch (...) 1980 { 1981 while (true) 1982 { 1983 __node_alloc_traits::destroy(__na, _VSTD::addressof(*__e)); 1984 __link_pointer __prev = __e.__ptr_->__prev_; 1985 __node_alloc_traits::deallocate(__na, __e.__ptr_->__as_node(), 1); 1986 if (__prev == 0) 1987 break; 1988#if _LIBCPP_DEBUG_LEVEL >= 2 1989 __e = iterator(__prev, this); 1990#else 1991 __e = iterator(__prev); 1992#endif 1993 } 1994 throw; 1995 } 1996#endif // _LIBCPP_NO_EXCEPTIONS 1997 __link_nodes(base::__end_as_link(), __r.__ptr_, __e.__ptr_); 1998 base::__sz() += __ds; 1999 } 2000} 2001 2002template <class _Tp, class _Alloc> 2003void 2004list<_Tp, _Alloc>::splice(const_iterator __p, list& __c) 2005{ 2006 _LIBCPP_ASSERT(this != &__c, 2007 "list::splice(iterator, list) called with this == &list"); 2008#if _LIBCPP_DEBUG_LEVEL >= 2 2009 _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__p) == this, 2010 "list::splice(iterator, list) called with an iterator not" 2011 " referring to this list"); 2012#endif 2013 if (!__c.empty()) 2014 { 2015 __link_pointer __f = __c.__end_.__next_; 2016 __link_pointer __l = __c.__end_.__prev_; 2017 base::__unlink_nodes(__f, __l); 2018 __link_nodes(__p.__ptr_, __f, __l); 2019 base::__sz() += __c.__sz(); 2020 __c.__sz() = 0; 2021#if _LIBCPP_DEBUG_LEVEL >= 2 2022 if (&__c != this) { 2023 __libcpp_db* __db = __get_db(); 2024 __c_node* __cn1 = __db->__find_c_and_lock(this); 2025 __c_node* __cn2 = __db->__find_c(&__c); 2026 for (__i_node** __ip = __cn2->end_; __ip != __cn2->beg_;) 2027 { 2028 --__ip; 2029 iterator* __i = static_cast<iterator*>((*__ip)->__i_); 2030 if (__i->__ptr_ != __c.__end_as_link()) 2031 { 2032 __cn1->__add(*__ip); 2033 (*__ip)->__c_ = __cn1; 2034 if (--__cn2->end_ != __ip) 2035 memmove(__ip, __ip+1, (__cn2->end_ - __ip)*sizeof(__i_node*)); 2036 } 2037 } 2038 __db->unlock(); 2039 } 2040#endif 2041 } 2042} 2043 2044template <class _Tp, class _Alloc> 2045void 2046list<_Tp, _Alloc>::splice(const_iterator __p, list& __c, const_iterator __i) 2047{ 2048#if _LIBCPP_DEBUG_LEVEL >= 2 2049 _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__p) == this, 2050 "list::splice(iterator, list, iterator) called with first iterator not" 2051 " referring to this list"); 2052 _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__i) == &__c, 2053 "list::splice(iterator, list, iterator) called with second iterator not" 2054 " referring to list argument"); 2055 _LIBCPP_ASSERT(__get_const_db()->__dereferenceable(&__i), 2056 "list::splice(iterator, list, iterator) called with second iterator not" 2057 " derefereceable"); 2058#endif 2059 if (__p.__ptr_ != __i.__ptr_ && __p.__ptr_ != __i.__ptr_->__next_) 2060 { 2061 __link_pointer __f = __i.__ptr_; 2062 base::__unlink_nodes(__f, __f); 2063 __link_nodes(__p.__ptr_, __f, __f); 2064 --__c.__sz(); 2065 ++base::__sz(); 2066#if _LIBCPP_DEBUG_LEVEL >= 2 2067 if (&__c != this) { 2068 __libcpp_db* __db = __get_db(); 2069 __c_node* __cn1 = __db->__find_c_and_lock(this); 2070 __c_node* __cn2 = __db->__find_c(&__c); 2071 for (__i_node** __ip = __cn2->end_; __ip != __cn2->beg_;) 2072 { 2073 --__ip; 2074 iterator* __j = static_cast<iterator*>((*__ip)->__i_); 2075 if (__j->__ptr_ == __f) 2076 { 2077 __cn1->__add(*__ip); 2078 (*__ip)->__c_ = __cn1; 2079 if (--__cn2->end_ != __ip) 2080 memmove(__ip, __ip+1, (__cn2->end_ - __ip)*sizeof(__i_node*)); 2081 } 2082 } 2083 __db->unlock(); 2084 } 2085#endif 2086 } 2087} 2088 2089template <class _Tp, class _Alloc> 2090void 2091list<_Tp, _Alloc>::splice(const_iterator __p, list& __c, const_iterator __f, const_iterator __l) 2092{ 2093#if _LIBCPP_DEBUG_LEVEL >= 2 2094 _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__p) == this, 2095 "list::splice(iterator, list, iterator, iterator) called with first iterator not" 2096 " referring to this list"); 2097 _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__f) == &__c, 2098 "list::splice(iterator, list, iterator, iterator) called with second iterator not" 2099 " referring to list argument"); 2100 if (this == &__c) 2101 { 2102 for (const_iterator __i = __f; __i != __l; ++__i) 2103 _LIBCPP_ASSERT(__i != __p, 2104 "list::splice(iterator, list, iterator, iterator)" 2105 " called with the first iterator within the range" 2106 " of the second and third iterators"); 2107 } 2108#endif 2109 if (__f != __l) 2110 { 2111 __link_pointer __first = __f.__ptr_; 2112 --__l; 2113 __link_pointer __last = __l.__ptr_; 2114 if (this != &__c) 2115 { 2116 size_type __s = _VSTD::distance(__f, __l) + 1; 2117 __c.__sz() -= __s; 2118 base::__sz() += __s; 2119 } 2120 base::__unlink_nodes(__first, __last); 2121 __link_nodes(__p.__ptr_, __first, __last); 2122#if _LIBCPP_DEBUG_LEVEL >= 2 2123 if (&__c != this) { 2124 __libcpp_db* __db = __get_db(); 2125 __c_node* __cn1 = __db->__find_c_and_lock(this); 2126 __c_node* __cn2 = __db->__find_c(&__c); 2127 for (__i_node** __ip = __cn2->end_; __ip != __cn2->beg_;) 2128 { 2129 --__ip; 2130 iterator* __j = static_cast<iterator*>((*__ip)->__i_); 2131 for (__link_pointer __k = __f.__ptr_; 2132 __k != __l.__ptr_; __k = __k->__next_) 2133 { 2134 if (__j->__ptr_ == __k) 2135 { 2136 __cn1->__add(*__ip); 2137 (*__ip)->__c_ = __cn1; 2138 if (--__cn2->end_ != __ip) 2139 memmove(__ip, __ip+1, (__cn2->end_ - __ip)*sizeof(__i_node*)); 2140 } 2141 } 2142 } 2143 __db->unlock(); 2144 } 2145#endif 2146 } 2147} 2148 2149template <class _Tp, class _Alloc> 2150typename list<_Tp, _Alloc>::__remove_return_type 2151list<_Tp, _Alloc>::remove(const value_type& __x) 2152{ 2153 list<_Tp, _Alloc> __deleted_nodes(get_allocator()); // collect the nodes we're removing 2154 for (const_iterator __i = begin(), __e = end(); __i != __e;) 2155 { 2156 if (*__i == __x) 2157 { 2158 const_iterator __j = _VSTD::next(__i); 2159 for (; __j != __e && *__j == __x; ++__j) 2160 ; 2161 __deleted_nodes.splice(__deleted_nodes.end(), *this, __i, __j); 2162 __i = __j; 2163 if (__i != __e) 2164 ++__i; 2165 } 2166 else 2167 ++__i; 2168 } 2169 2170 return (__remove_return_type) __deleted_nodes.size(); 2171} 2172 2173template <class _Tp, class _Alloc> 2174template <class _Pred> 2175typename list<_Tp, _Alloc>::__remove_return_type 2176list<_Tp, _Alloc>::remove_if(_Pred __pred) 2177{ 2178 list<_Tp, _Alloc> __deleted_nodes(get_allocator()); // collect the nodes we're removing 2179 for (iterator __i = begin(), __e = end(); __i != __e;) 2180 { 2181 if (__pred(*__i)) 2182 { 2183 iterator __j = _VSTD::next(__i); 2184 for (; __j != __e && __pred(*__j); ++__j) 2185 ; 2186 __deleted_nodes.splice(__deleted_nodes.end(), *this, __i, __j); 2187 __i = __j; 2188 if (__i != __e) 2189 ++__i; 2190 } 2191 else 2192 ++__i; 2193 } 2194 2195 return (__remove_return_type) __deleted_nodes.size(); 2196} 2197 2198template <class _Tp, class _Alloc> 2199template <class _BinaryPred> 2200typename list<_Tp, _Alloc>::__remove_return_type 2201list<_Tp, _Alloc>::unique(_BinaryPred __binary_pred) 2202{ 2203 list<_Tp, _Alloc> __deleted_nodes(get_allocator()); // collect the nodes we're removing 2204 for (iterator __i = begin(), __e = end(); __i != __e;) 2205 { 2206 iterator __j = _VSTD::next(__i); 2207 for (; __j != __e && __binary_pred(*__i, *__j); ++__j) 2208 ; 2209 if (++__i != __j) { 2210 __deleted_nodes.splice(__deleted_nodes.end(), *this, __i, __j); 2211 __i = __j; 2212 } 2213 } 2214 2215 return (__remove_return_type) __deleted_nodes.size(); 2216} 2217 2218template <class _Tp, class _Alloc> 2219inline 2220void 2221list<_Tp, _Alloc>::merge(list& __c) 2222{ 2223 merge(__c, __less<value_type>()); 2224} 2225 2226template <class _Tp, class _Alloc> 2227template <class _Comp> 2228void 2229list<_Tp, _Alloc>::merge(list& __c, _Comp __comp) 2230{ 2231 if (this != _VSTD::addressof(__c)) 2232 { 2233 iterator __f1 = begin(); 2234 iterator __e1 = end(); 2235 iterator __f2 = __c.begin(); 2236 iterator __e2 = __c.end(); 2237 while (__f1 != __e1 && __f2 != __e2) 2238 { 2239 if (__comp(*__f2, *__f1)) 2240 { 2241 size_type __ds = 1; 2242 iterator __m2 = _VSTD::next(__f2); 2243 for (; __m2 != __e2 && __comp(*__m2, *__f1); ++__m2, ++__ds) 2244 ; 2245 base::__sz() += __ds; 2246 __c.__sz() -= __ds; 2247 __link_pointer __f = __f2.__ptr_; 2248 __link_pointer __l = __m2.__ptr_->__prev_; 2249 __f2 = __m2; 2250 base::__unlink_nodes(__f, __l); 2251 __m2 = _VSTD::next(__f1); 2252 __link_nodes(__f1.__ptr_, __f, __l); 2253 __f1 = __m2; 2254 } 2255 else 2256 ++__f1; 2257 } 2258 splice(__e1, __c); 2259#if _LIBCPP_DEBUG_LEVEL >= 2 2260 __libcpp_db* __db = __get_db(); 2261 __c_node* __cn1 = __db->__find_c_and_lock(this); 2262 __c_node* __cn2 = __db->__find_c(&__c); 2263 for (__i_node** __p = __cn2->end_; __p != __cn2->beg_;) 2264 { 2265 --__p; 2266 iterator* __i = static_cast<iterator*>((*__p)->__i_); 2267 if (__i->__ptr_ != __c.__end_as_link()) 2268 { 2269 __cn1->__add(*__p); 2270 (*__p)->__c_ = __cn1; 2271 if (--__cn2->end_ != __p) 2272 memmove(__p, __p+1, (__cn2->end_ - __p)*sizeof(__i_node*)); 2273 } 2274 } 2275 __db->unlock(); 2276#endif 2277 } 2278} 2279 2280template <class _Tp, class _Alloc> 2281inline 2282void 2283list<_Tp, _Alloc>::sort() 2284{ 2285 sort(__less<value_type>()); 2286} 2287 2288template <class _Tp, class _Alloc> 2289template <class _Comp> 2290inline 2291void 2292list<_Tp, _Alloc>::sort(_Comp __comp) 2293{ 2294 __sort(begin(), end(), base::__sz(), __comp); 2295} 2296 2297template <class _Tp, class _Alloc> 2298template <class _Comp> 2299typename list<_Tp, _Alloc>::iterator 2300list<_Tp, _Alloc>::__sort(iterator __f1, iterator __e2, size_type __n, _Comp& __comp) 2301{ 2302 switch (__n) 2303 { 2304 case 0: 2305 case 1: 2306 return __f1; 2307 case 2: 2308 if (__comp(*--__e2, *__f1)) 2309 { 2310 __link_pointer __f = __e2.__ptr_; 2311 base::__unlink_nodes(__f, __f); 2312 __link_nodes(__f1.__ptr_, __f, __f); 2313 return __e2; 2314 } 2315 return __f1; 2316 } 2317 size_type __n2 = __n / 2; 2318 iterator __e1 = _VSTD::next(__f1, __n2); 2319 iterator __r = __f1 = __sort(__f1, __e1, __n2, __comp); 2320 iterator __f2 = __e1 = __sort(__e1, __e2, __n - __n2, __comp); 2321 if (__comp(*__f2, *__f1)) 2322 { 2323 iterator __m2 = _VSTD::next(__f2); 2324 for (; __m2 != __e2 && __comp(*__m2, *__f1); ++__m2) 2325 ; 2326 __link_pointer __f = __f2.__ptr_; 2327 __link_pointer __l = __m2.__ptr_->__prev_; 2328 __r = __f2; 2329 __e1 = __f2 = __m2; 2330 base::__unlink_nodes(__f, __l); 2331 __m2 = _VSTD::next(__f1); 2332 __link_nodes(__f1.__ptr_, __f, __l); 2333 __f1 = __m2; 2334 } 2335 else 2336 ++__f1; 2337 while (__f1 != __e1 && __f2 != __e2) 2338 { 2339 if (__comp(*__f2, *__f1)) 2340 { 2341 iterator __m2 = _VSTD::next(__f2); 2342 for (; __m2 != __e2 && __comp(*__m2, *__f1); ++__m2) 2343 ; 2344 __link_pointer __f = __f2.__ptr_; 2345 __link_pointer __l = __m2.__ptr_->__prev_; 2346 if (__e1 == __f2) 2347 __e1 = __m2; 2348 __f2 = __m2; 2349 base::__unlink_nodes(__f, __l); 2350 __m2 = _VSTD::next(__f1); 2351 __link_nodes(__f1.__ptr_, __f, __l); 2352 __f1 = __m2; 2353 } 2354 else 2355 ++__f1; 2356 } 2357 return __r; 2358} 2359 2360template <class _Tp, class _Alloc> 2361void 2362list<_Tp, _Alloc>::reverse() _NOEXCEPT 2363{ 2364 if (base::__sz() > 1) 2365 { 2366 iterator __e = end(); 2367 for (iterator __i = begin(); __i.__ptr_ != __e.__ptr_;) 2368 { 2369 _VSTD::swap(__i.__ptr_->__prev_, __i.__ptr_->__next_); 2370 __i.__ptr_ = __i.__ptr_->__prev_; 2371 } 2372 _VSTD::swap(__e.__ptr_->__prev_, __e.__ptr_->__next_); 2373 } 2374} 2375 2376template <class _Tp, class _Alloc> 2377bool 2378list<_Tp, _Alloc>::__invariants() const 2379{ 2380 return size() == _VSTD::distance(begin(), end()); 2381} 2382 2383#if _LIBCPP_DEBUG_LEVEL >= 2 2384 2385template <class _Tp, class _Alloc> 2386bool 2387list<_Tp, _Alloc>::__dereferenceable(const const_iterator* __i) const 2388{ 2389 return __i->__ptr_ != this->__end_as_link(); 2390} 2391 2392template <class _Tp, class _Alloc> 2393bool 2394list<_Tp, _Alloc>::__decrementable(const const_iterator* __i) const 2395{ 2396 return !empty() && __i->__ptr_ != base::__end_.__next_; 2397} 2398 2399template <class _Tp, class _Alloc> 2400bool 2401list<_Tp, _Alloc>::__addable(const const_iterator*, ptrdiff_t) const 2402{ 2403 return false; 2404} 2405 2406template <class _Tp, class _Alloc> 2407bool 2408list<_Tp, _Alloc>::__subscriptable(const const_iterator*, ptrdiff_t) const 2409{ 2410 return false; 2411} 2412 2413#endif // _LIBCPP_DEBUG_LEVEL >= 2 2414 2415template <class _Tp, class _Alloc> 2416inline _LIBCPP_INLINE_VISIBILITY 2417bool 2418operator==(const list<_Tp, _Alloc>& __x, const list<_Tp, _Alloc>& __y) 2419{ 2420 return __x.size() == __y.size() && _VSTD::equal(__x.begin(), __x.end(), __y.begin()); 2421} 2422 2423template <class _Tp, class _Alloc> 2424inline _LIBCPP_INLINE_VISIBILITY 2425bool 2426operator< (const list<_Tp, _Alloc>& __x, const list<_Tp, _Alloc>& __y) 2427{ 2428 return _VSTD::lexicographical_compare(__x.begin(), __x.end(), __y.begin(), __y.end()); 2429} 2430 2431template <class _Tp, class _Alloc> 2432inline _LIBCPP_INLINE_VISIBILITY 2433bool 2434operator!=(const list<_Tp, _Alloc>& __x, const list<_Tp, _Alloc>& __y) 2435{ 2436 return !(__x == __y); 2437} 2438 2439template <class _Tp, class _Alloc> 2440inline _LIBCPP_INLINE_VISIBILITY 2441bool 2442operator> (const list<_Tp, _Alloc>& __x, const list<_Tp, _Alloc>& __y) 2443{ 2444 return __y < __x; 2445} 2446 2447template <class _Tp, class _Alloc> 2448inline _LIBCPP_INLINE_VISIBILITY 2449bool 2450operator>=(const list<_Tp, _Alloc>& __x, const list<_Tp, _Alloc>& __y) 2451{ 2452 return !(__x < __y); 2453} 2454 2455template <class _Tp, class _Alloc> 2456inline _LIBCPP_INLINE_VISIBILITY 2457bool 2458operator<=(const list<_Tp, _Alloc>& __x, const list<_Tp, _Alloc>& __y) 2459{ 2460 return !(__y < __x); 2461} 2462 2463template <class _Tp, class _Alloc> 2464inline _LIBCPP_INLINE_VISIBILITY 2465void 2466swap(list<_Tp, _Alloc>& __x, list<_Tp, _Alloc>& __y) 2467 _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y))) 2468{ 2469 __x.swap(__y); 2470} 2471 2472#if _LIBCPP_STD_VER > 17 2473template <class _Tp, class _Allocator, class _Predicate> 2474inline _LIBCPP_INLINE_VISIBILITY 2475void erase_if(list<_Tp, _Allocator>& __c, _Predicate __pred) 2476{ __c.remove_if(__pred); } 2477 2478template <class _Tp, class _Allocator, class _Up> 2479inline _LIBCPP_INLINE_VISIBILITY 2480void erase(list<_Tp, _Allocator>& __c, const _Up& __v) 2481{ _VSTD::erase_if(__c, [&](auto& __elem) { return __elem == __v; }); } 2482#endif 2483 2484_LIBCPP_END_NAMESPACE_STD 2485 2486_LIBCPP_POP_MACROS 2487 2488#endif // _LIBCPP_LIST 2489