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