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