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