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