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 template <class T, class Alloc> 151 bool operator==(const list<T,Alloc>& x, const list<T,Alloc>& y); 152 template <class T, class Alloc> 153 bool operator< (const list<T,Alloc>& x, const list<T,Alloc>& y); 154 template <class T, class Alloc> 155 bool operator!=(const list<T,Alloc>& x, const list<T,Alloc>& y); 156 template <class T, class Alloc> 157 bool operator> (const list<T,Alloc>& x, const list<T,Alloc>& y); 158 template <class T, class Alloc> 159 bool operator>=(const list<T,Alloc>& x, const list<T,Alloc>& y); 160 template <class T, class Alloc> 161 bool operator<=(const list<T,Alloc>& x, const list<T,Alloc>& y); 162 163 template <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 190 template <class _Tp, class _VoidPtr> struct __list_node; 191 template <class _Tp, class _VoidPtr> struct __list_node_base; 192 193 template <class _Tp, class _VoidPtr> 194 struct __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 228 template <class _Tp, class _VoidPtr> 229 struct __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 254 template <class _Tp, class _VoidPtr> 255 struct __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 269 template <class _Tp, class _Alloc = allocator<_Tp> > class _LIBCPP_TEMPLATE_VIS list; 270 template <class _Tp, class _Alloc> class __list_imp; 271 template <class _Tp, class _VoidPtr> class _LIBCPP_TEMPLATE_VIS __list_const_iterator; 272 273 template <class _Tp, class _VoidPtr> 274 class _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; 298 public: 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 396 template <class _Tp, class _VoidPtr> 397 class _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; 418 public: 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 523 template <class _Tp, class _Alloc> 524 class __list_imp 525 { 526 __list_imp(const __list_imp&); 527 __list_imp& operator=(const __list_imp&); 528 protected: 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 648 private: 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] 682 template <class _Tp, class _Alloc> 683 inline 684 void 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 692 template <class _Tp, class _Alloc> 693 inline 694 __list_imp<_Tp, _Alloc>::__list_imp() 695 _NOEXCEPT_(is_nothrow_default_constructible<__node_allocator>::value) 696 : __size_alloc_(0) 697 { 698 } 699 700 template <class _Tp, class _Alloc> 701 inline 702 __list_imp<_Tp, _Alloc>::__list_imp(const allocator_type& __a) 703 : __size_alloc_(0, __node_allocator(__a)) 704 { 705 } 706 707 template <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 716 template <class _Tp, class _Alloc> 717 void 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 738 template <class _Tp, class _Alloc> 739 void 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 802 template <class _Tp, class _Alloc /*= allocator<_Tp>*/> 803 class _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 815 public: 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 1080 private: 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 1097 template <class _Tp, class _Alloc> 1098 inline 1099 void 1100 list<_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 1109 template <class _Tp, class _Alloc> 1110 inline 1111 void 1112 list<_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 1121 template <class _Tp, class _Alloc> 1122 inline 1123 void 1124 list<_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 1133 template <class _Tp, class _Alloc> 1134 inline 1135 typename list<_Tp, _Alloc>::iterator 1136 list<_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 1142 template <class _Tp, class _Alloc> 1143 list<_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 1157 template <class _Tp, class _Alloc> 1158 list<_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 1172 template <class _Tp, class _Alloc> 1173 list<_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 1182 template <class _Tp, class _Alloc> 1183 list<_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 1193 template <class _Tp, class _Alloc> 1194 template <class _InpIter> 1195 list<_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 1205 template <class _Tp, class _Alloc> 1206 template <class _InpIter> 1207 list<_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 1218 template <class _Tp, class _Alloc> 1219 list<_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 1231 template <class _Tp, class _Alloc> 1232 list<_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 1244 template <class _Tp, class _Alloc> 1245 list<_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 1256 template <class _Tp, class _Alloc> 1257 list<_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 1269 template <class _Tp, class _Alloc> 1270 inline 1271 list<_Tp, _Alloc>& 1272 list<_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 1284 template <class _Tp, class _Alloc> 1285 inline 1286 list<_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 1296 template <class _Tp, class _Alloc> 1297 inline 1298 list<_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 1313 template <class _Tp, class _Alloc> 1314 inline 1315 list<_Tp, _Alloc>& 1316 list<_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 1326 template <class _Tp, class _Alloc> 1327 void 1328 list<_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 1339 template <class _Tp, class _Alloc> 1340 void 1341 list<_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 1351 template <class _Tp, class _Alloc> 1352 template <class _InpIter> 1353 void 1354 list<_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 1370 template <class _Tp, class _Alloc> 1371 void 1372 list<_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 1387 template <class _Tp, class _Alloc> 1388 inline 1389 _Alloc 1390 list<_Tp, _Alloc>::get_allocator() const _NOEXCEPT 1391 { 1392 return allocator_type(base::__node_alloc()); 1393 } 1394 1395 template <class _Tp, class _Alloc> 1396 typename list<_Tp, _Alloc>::iterator 1397 list<_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 1418 template <class _Tp, class _Alloc> 1419 typename list<_Tp, _Alloc>::iterator 1420 list<_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 1484 template <class _Tp, class _Alloc> 1485 template <class _InpIter> 1486 typename list<_Tp, _Alloc>::iterator 1487 list<_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 1552 template <class _Tp, class _Alloc> 1553 void 1554 list<_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 1566 template <class _Tp, class _Alloc> 1567 void 1568 list<_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 1581 template <class _Tp, class _Alloc> 1582 void 1583 list<_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 1594 template <class _Tp, class _Alloc> 1595 void 1596 list<_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 1609 template <class _Tp, class _Alloc> 1610 template <class... _Args> 1611 #if _LIBCPP_STD_VER > 14 1612 typename list<_Tp, _Alloc>::reference 1613 #else 1614 void 1615 #endif 1616 list<_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 1631 template <class _Tp, class _Alloc> 1632 template <class... _Args> 1633 #if _LIBCPP_STD_VER > 14 1634 typename list<_Tp, _Alloc>::reference 1635 #else 1636 void 1637 #endif 1638 list<_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 1654 template <class _Tp, class _Alloc> 1655 template <class... _Args> 1656 typename list<_Tp, _Alloc>::iterator 1657 list<_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 1682 template <class _Tp, class _Alloc> 1683 typename list<_Tp, _Alloc>::iterator 1684 list<_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 1709 template <class _Tp, class _Alloc> 1710 void 1711 list<_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 1738 template <class _Tp, class _Alloc> 1739 void 1740 list<_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 1767 template <class _Tp, class _Alloc> 1768 typename list<_Tp, _Alloc>::iterator 1769 list<_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 1808 template <class _Tp, class _Alloc> 1809 typename list<_Tp, _Alloc>::iterator 1810 list<_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 1856 template <class _Tp, class _Alloc> 1857 void 1858 list<_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 1915 template <class _Tp, class _Alloc> 1916 void 1917 list<_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 1975 template <class _Tp, class _Alloc> 1976 void 1977 list<_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 2015 template <class _Tp, class _Alloc> 2016 void 2017 list<_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 2058 template <class _Tp, class _Alloc> 2059 void 2060 list<_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 2116 template <class _Tp, class _Alloc> 2117 void 2118 list<_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 2138 template <class _Tp, class _Alloc> 2139 template <class _Pred> 2140 void 2141 list<_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 2159 template <class _Tp, class _Alloc> 2160 inline 2161 void 2162 list<_Tp, _Alloc>::unique() 2163 { 2164 unique(__equal_to<value_type>()); 2165 } 2166 2167 template <class _Tp, class _Alloc> 2168 template <class _BinaryPred> 2169 void 2170 list<_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 2182 template <class _Tp, class _Alloc> 2183 inline 2184 void 2185 list<_Tp, _Alloc>::merge(list& __c) 2186 { 2187 merge(__c, __less<value_type>()); 2188 } 2189 2190 template <class _Tp, class _Alloc> 2191 template <class _Comp> 2192 void 2193 list<_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 2244 template <class _Tp, class _Alloc> 2245 inline 2246 void 2247 list<_Tp, _Alloc>::sort() 2248 { 2249 sort(__less<value_type>()); 2250 } 2251 2252 template <class _Tp, class _Alloc> 2253 template <class _Comp> 2254 inline 2255 void 2256 list<_Tp, _Alloc>::sort(_Comp __comp) 2257 { 2258 __sort(begin(), end(), base::__sz(), __comp); 2259 } 2260 2261 template <class _Tp, class _Alloc> 2262 template <class _Comp> 2263 typename list<_Tp, _Alloc>::iterator 2264 list<_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 2324 template <class _Tp, class _Alloc> 2325 void 2326 list<_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 2340 template <class _Tp, class _Alloc> 2341 bool 2342 list<_Tp, _Alloc>::__invariants() const 2343 { 2344 return size() == _VSTD::distance(begin(), end()); 2345 } 2346 2347 #if _LIBCPP_DEBUG_LEVEL >= 2 2348 2349 template <class _Tp, class _Alloc> 2350 bool 2351 list<_Tp, _Alloc>::__dereferenceable(const const_iterator* __i) const 2352 { 2353 return __i->__ptr_ != this->__end_as_link(); 2354 } 2355 2356 template <class _Tp, class _Alloc> 2357 bool 2358 list<_Tp, _Alloc>::__decrementable(const const_iterator* __i) const 2359 { 2360 return !empty() && __i->__ptr_ != base::__end_.__next_; 2361 } 2362 2363 template <class _Tp, class _Alloc> 2364 bool 2365 list<_Tp, _Alloc>::__addable(const const_iterator*, ptrdiff_t) const 2366 { 2367 return false; 2368 } 2369 2370 template <class _Tp, class _Alloc> 2371 bool 2372 list<_Tp, _Alloc>::__subscriptable(const const_iterator*, ptrdiff_t) const 2373 { 2374 return false; 2375 } 2376 2377 #endif // _LIBCPP_DEBUG_LEVEL >= 2 2378 2379 template <class _Tp, class _Alloc> 2380 inline _LIBCPP_INLINE_VISIBILITY 2381 bool 2382 operator==(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 2387 template <class _Tp, class _Alloc> 2388 inline _LIBCPP_INLINE_VISIBILITY 2389 bool 2390 operator< (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 2395 template <class _Tp, class _Alloc> 2396 inline _LIBCPP_INLINE_VISIBILITY 2397 bool 2398 operator!=(const list<_Tp, _Alloc>& __x, const list<_Tp, _Alloc>& __y) 2399 { 2400 return !(__x == __y); 2401 } 2402 2403 template <class _Tp, class _Alloc> 2404 inline _LIBCPP_INLINE_VISIBILITY 2405 bool 2406 operator> (const list<_Tp, _Alloc>& __x, const list<_Tp, _Alloc>& __y) 2407 { 2408 return __y < __x; 2409 } 2410 2411 template <class _Tp, class _Alloc> 2412 inline _LIBCPP_INLINE_VISIBILITY 2413 bool 2414 operator>=(const list<_Tp, _Alloc>& __x, const list<_Tp, _Alloc>& __y) 2415 { 2416 return !(__x < __y); 2417 } 2418 2419 template <class _Tp, class _Alloc> 2420 inline _LIBCPP_INLINE_VISIBILITY 2421 bool 2422 operator<=(const list<_Tp, _Alloc>& __x, const list<_Tp, _Alloc>& __y) 2423 { 2424 return !(__y < __x); 2425 } 2426 2427 template <class _Tp, class _Alloc> 2428 inline _LIBCPP_INLINE_VISIBILITY 2429 void 2430 swap(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
