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