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