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