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