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