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