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