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