list revision 288943
1227825Stheraven// -*- C++ -*- 2227825Stheraven//===---------------------------- list ------------------------------------===// 3227825Stheraven// 4227825Stheraven// The LLVM Compiler Infrastructure 5227825Stheraven// 6227825Stheraven// This file is dual licensed under the MIT and the University of Illinois Open 7227825Stheraven// Source Licenses. See LICENSE.TXT for details. 8227825Stheraven// 9227825Stheraven//===----------------------------------------------------------------------===// 10227825Stheraven 11227825Stheraven#ifndef _LIBCPP_LIST 12227825Stheraven#define _LIBCPP_LIST 13227825Stheraven 14227825Stheraven/* 15227825Stheraven list synopsis 16227825Stheraven 17227825Stheravennamespace std 18227825Stheraven{ 19227825Stheraven 20227825Stheraventemplate <class T, class Alloc = allocator<T> > 21227825Stheravenclass list 22227825Stheraven{ 23227825Stheravenpublic: 24227825Stheraven 25227825Stheraven // types: 26227825Stheraven typedef T value_type; 27227825Stheraven typedef Alloc allocator_type; 28227825Stheraven typedef typename allocator_type::reference reference; 29227825Stheraven typedef typename allocator_type::const_reference const_reference; 30227825Stheraven typedef typename allocator_type::pointer pointer; 31227825Stheraven typedef typename allocator_type::const_pointer const_pointer; 32227825Stheraven typedef implementation-defined iterator; 33227825Stheraven typedef implementation-defined const_iterator; 34227825Stheraven typedef implementation-defined size_type; 35227825Stheraven typedef implementation-defined difference_type; 36227825Stheraven typedef reverse_iterator<iterator> reverse_iterator; 37227825Stheraven typedef reverse_iterator<const_iterator> const_reverse_iterator; 38227825Stheraven 39227825Stheraven list() 40227825Stheraven noexcept(is_nothrow_default_constructible<allocator_type>::value); 41227825Stheraven explicit list(const allocator_type& a); 42227825Stheraven explicit list(size_type n); 43261272Sdim explicit list(size_type n, const allocator_type& a); // C++14 44227825Stheraven list(size_type n, const value_type& value); 45227825Stheraven list(size_type n, const value_type& value, const allocator_type& a); 46227825Stheraven template <class Iter> 47227825Stheraven list(Iter first, Iter last); 48227825Stheraven template <class Iter> 49227825Stheraven list(Iter first, Iter last, const allocator_type& a); 50227825Stheraven list(const list& x); 51227825Stheraven list(const list&, const allocator_type& a); 52227825Stheraven list(list&& x) 53227825Stheraven noexcept(is_nothrow_move_constructible<allocator_type>::value); 54227825Stheraven list(list&&, const allocator_type& a); 55227825Stheraven list(initializer_list<value_type>); 56227825Stheraven list(initializer_list<value_type>, const allocator_type& a); 57227825Stheraven 58227825Stheraven ~list(); 59227825Stheraven 60227825Stheraven list& operator=(const list& x); 61227825Stheraven list& operator=(list&& x) 62227825Stheraven noexcept( 63227825Stheraven allocator_type::propagate_on_container_move_assignment::value && 64227825Stheraven is_nothrow_move_assignable<allocator_type>::value); 65227825Stheraven list& operator=(initializer_list<value_type>); 66227825Stheraven template <class Iter> 67227825Stheraven void assign(Iter first, Iter last); 68227825Stheraven void assign(size_type n, const value_type& t); 69227825Stheraven void assign(initializer_list<value_type>); 70227825Stheraven 71227825Stheraven allocator_type get_allocator() const noexcept; 72227825Stheraven 73227825Stheraven iterator begin() noexcept; 74227825Stheraven const_iterator begin() const noexcept; 75227825Stheraven iterator end() noexcept; 76227825Stheraven const_iterator end() const noexcept; 77227825Stheraven reverse_iterator rbegin() noexcept; 78227825Stheraven const_reverse_iterator rbegin() const noexcept; 79227825Stheraven reverse_iterator rend() noexcept; 80227825Stheraven const_reverse_iterator rend() const noexcept; 81227825Stheraven const_iterator cbegin() const noexcept; 82227825Stheraven const_iterator cend() const noexcept; 83227825Stheraven const_reverse_iterator crbegin() const noexcept; 84227825Stheraven const_reverse_iterator crend() const noexcept; 85227825Stheraven 86227825Stheraven reference front(); 87227825Stheraven const_reference front() const; 88227825Stheraven reference back(); 89227825Stheraven const_reference back() const; 90227825Stheraven 91227825Stheraven bool empty() const noexcept; 92227825Stheraven size_type size() const noexcept; 93227825Stheraven size_type max_size() const noexcept; 94227825Stheraven 95227825Stheraven template <class... Args> 96227825Stheraven void emplace_front(Args&&... args); 97227825Stheraven void pop_front(); 98227825Stheraven template <class... Args> 99227825Stheraven void emplace_back(Args&&... args); 100227825Stheraven void pop_back(); 101227825Stheraven void push_front(const value_type& x); 102227825Stheraven void push_front(value_type&& x); 103227825Stheraven void push_back(const value_type& x); 104227825Stheraven void push_back(value_type&& x); 105227825Stheraven template <class... Args> 106227825Stheraven iterator emplace(const_iterator position, Args&&... args); 107227825Stheraven iterator insert(const_iterator position, const value_type& x); 108227825Stheraven iterator insert(const_iterator position, value_type&& x); 109227825Stheraven iterator insert(const_iterator position, size_type n, const value_type& x); 110227825Stheraven template <class Iter> 111227825Stheraven iterator insert(const_iterator position, Iter first, Iter last); 112227825Stheraven iterator insert(const_iterator position, initializer_list<value_type> il); 113227825Stheraven 114227825Stheraven iterator erase(const_iterator position); 115227825Stheraven iterator erase(const_iterator position, const_iterator last); 116227825Stheraven 117227825Stheraven void resize(size_type sz); 118227825Stheraven void resize(size_type sz, const value_type& c); 119227825Stheraven 120227825Stheraven void swap(list&) 121288943Sdim noexcept(allocator_traits<allocator_type>::is_always_equal::value); // C++17 122227825Stheraven void clear() noexcept; 123227825Stheraven 124227825Stheraven void splice(const_iterator position, list& x); 125227825Stheraven void splice(const_iterator position, list&& x); 126227825Stheraven void splice(const_iterator position, list& x, const_iterator i); 127227825Stheraven void splice(const_iterator position, list&& x, const_iterator i); 128227825Stheraven void splice(const_iterator position, list& x, const_iterator first, 129227825Stheraven const_iterator last); 130227825Stheraven void splice(const_iterator position, list&& x, const_iterator first, 131227825Stheraven const_iterator last); 132227825Stheraven 133227825Stheraven void remove(const value_type& value); 134227825Stheraven template <class Pred> void remove_if(Pred pred); 135227825Stheraven void unique(); 136227825Stheraven template <class BinaryPredicate> 137227825Stheraven void unique(BinaryPredicate binary_pred); 138227825Stheraven void merge(list& x); 139227825Stheraven void merge(list&& x); 140227825Stheraven template <class Compare> 141227825Stheraven void merge(list& x, Compare comp); 142227825Stheraven template <class Compare> 143227825Stheraven void merge(list&& x, Compare comp); 144227825Stheraven void sort(); 145227825Stheraven template <class Compare> 146227825Stheraven void sort(Compare comp); 147227825Stheraven void reverse() noexcept; 148227825Stheraven}; 149227825Stheraven 150227825Stheraventemplate <class T, class Alloc> 151227825Stheraven bool operator==(const list<T,Alloc>& x, const list<T,Alloc>& y); 152227825Stheraventemplate <class T, class Alloc> 153227825Stheraven bool operator< (const list<T,Alloc>& x, const list<T,Alloc>& y); 154227825Stheraventemplate <class T, class Alloc> 155227825Stheraven bool operator!=(const list<T,Alloc>& x, const list<T,Alloc>& y); 156227825Stheraventemplate <class T, class Alloc> 157227825Stheraven bool operator> (const list<T,Alloc>& x, const list<T,Alloc>& y); 158227825Stheraventemplate <class T, class Alloc> 159227825Stheraven bool operator>=(const list<T,Alloc>& x, const list<T,Alloc>& y); 160227825Stheraventemplate <class T, class Alloc> 161227825Stheraven bool operator<=(const list<T,Alloc>& x, const list<T,Alloc>& y); 162227825Stheraven 163227825Stheraventemplate <class T, class Alloc> 164227825Stheraven void swap(list<T,Alloc>& x, list<T,Alloc>& y) 165227825Stheraven noexcept(noexcept(x.swap(y))); 166227825Stheraven 167227825Stheraven} // std 168227825Stheraven 169227825Stheraven*/ 170227825Stheraven 171227825Stheraven#include <__config> 172227825Stheraven 173227825Stheraven#include <memory> 174227825Stheraven#include <limits> 175227825Stheraven#include <initializer_list> 176227825Stheraven#include <iterator> 177227825Stheraven#include <algorithm> 178227825Stheraven 179232924Stheraven#include <__undef_min_max> 180232924Stheraven 181276792Sdim#include <__debug> 182261272Sdim 183227825Stheraven#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) 184227825Stheraven#pragma GCC system_header 185227825Stheraven#endif 186227825Stheraven 187227825Stheraven_LIBCPP_BEGIN_NAMESPACE_STD 188227825Stheraven 189227825Stheraventemplate <class _Tp, class _VoidPtr> struct __list_node; 190227825Stheraven 191227825Stheraventemplate <class _Tp, class _VoidPtr> 192227825Stheravenstruct __list_node_base 193227825Stheraven{ 194227825Stheraven typedef typename pointer_traits<_VoidPtr>::template 195227825Stheraven#ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES 196227825Stheraven rebind<__list_node<_Tp, _VoidPtr> > pointer; 197227825Stheraven#else 198227825Stheraven rebind<__list_node<_Tp, _VoidPtr> >::other pointer; 199227825Stheraven#endif 200227825Stheraven 201253146Stheraven typedef typename pointer_traits<_VoidPtr>::template 202253146Stheraven#ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES 203253146Stheraven rebind<__list_node_base> __base_pointer; 204253146Stheraven#else 205253146Stheraven rebind<__list_node_base>::other __base_pointer; 206253146Stheraven#endif 207253146Stheraven 208227825Stheraven pointer __prev_; 209227825Stheraven pointer __next_; 210227825Stheraven 211227825Stheraven _LIBCPP_INLINE_VISIBILITY 212276792Sdim __list_node_base() : __prev_(__self()), __next_(__self()) {} 213276792Sdim 214276792Sdim _LIBCPP_INLINE_VISIBILITY 215276792Sdim pointer __self() 216276792Sdim { 217276792Sdim return static_cast<pointer>(pointer_traits<__base_pointer>::pointer_to(*this)); 218276792Sdim } 219227825Stheraven}; 220227825Stheraven 221227825Stheraventemplate <class _Tp, class _VoidPtr> 222227825Stheravenstruct __list_node 223227825Stheraven : public __list_node_base<_Tp, _VoidPtr> 224227825Stheraven{ 225227825Stheraven _Tp __value_; 226227825Stheraven}; 227227825Stheraven 228288943Sdimtemplate <class _Tp, class _Alloc = allocator<_Tp> > class _LIBCPP_TYPE_VIS_ONLY list; 229227825Stheraventemplate <class _Tp, class _Alloc> class __list_imp; 230261272Sdimtemplate <class _Tp, class _VoidPtr> class _LIBCPP_TYPE_VIS_ONLY __list_const_iterator; 231227825Stheraven 232227825Stheraventemplate <class _Tp, class _VoidPtr> 233261272Sdimclass _LIBCPP_TYPE_VIS_ONLY __list_iterator 234227825Stheraven{ 235227825Stheraven typedef typename pointer_traits<_VoidPtr>::template 236227825Stheraven#ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES 237227825Stheraven rebind<__list_node<_Tp, _VoidPtr> > __node_pointer; 238227825Stheraven#else 239227825Stheraven rebind<__list_node<_Tp, _VoidPtr> >::other __node_pointer; 240227825Stheraven#endif 241227825Stheraven 242227825Stheraven __node_pointer __ptr_; 243227825Stheraven 244227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 245227825Stheraven _LIBCPP_INLINE_VISIBILITY 246227825Stheraven explicit __list_iterator(__node_pointer __p, const void* __c) _NOEXCEPT 247227825Stheraven : __ptr_(__p) 248227825Stheraven { 249227825Stheraven __get_db()->__insert_ic(this, __c); 250227825Stheraven } 251227825Stheraven#else 252227825Stheraven _LIBCPP_INLINE_VISIBILITY 253227825Stheraven explicit __list_iterator(__node_pointer __p) _NOEXCEPT : __ptr_(__p) {} 254227825Stheraven#endif 255227825Stheraven 256227825Stheraven 257227825Stheraven 258227825Stheraven template<class, class> friend class list; 259227825Stheraven template<class, class> friend class __list_imp; 260227825Stheraven template<class, class> friend class __list_const_iterator; 261227825Stheravenpublic: 262227825Stheraven typedef bidirectional_iterator_tag iterator_category; 263227825Stheraven typedef _Tp value_type; 264227825Stheraven typedef value_type& reference; 265227825Stheraven typedef typename pointer_traits<_VoidPtr>::template 266227825Stheraven#ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES 267227825Stheraven rebind<value_type> 268227825Stheraven#else 269227825Stheraven rebind<value_type>::other 270227825Stheraven#endif 271227825Stheraven pointer; 272227825Stheraven typedef typename pointer_traits<pointer>::difference_type difference_type; 273227825Stheraven 274227825Stheraven _LIBCPP_INLINE_VISIBILITY 275261272Sdim __list_iterator() _NOEXCEPT : __ptr_(nullptr) 276227825Stheraven { 277227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 278227825Stheraven __get_db()->__insert_i(this); 279227825Stheraven#endif 280227825Stheraven } 281227825Stheraven 282227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 283227825Stheraven 284227825Stheraven _LIBCPP_INLINE_VISIBILITY 285227825Stheraven __list_iterator(const __list_iterator& __p) 286227825Stheraven : __ptr_(__p.__ptr_) 287227825Stheraven { 288227825Stheraven __get_db()->__iterator_copy(this, &__p); 289227825Stheraven } 290227825Stheraven 291227825Stheraven _LIBCPP_INLINE_VISIBILITY 292227825Stheraven ~__list_iterator() 293227825Stheraven { 294227825Stheraven __get_db()->__erase_i(this); 295227825Stheraven } 296227825Stheraven 297227825Stheraven _LIBCPP_INLINE_VISIBILITY 298227825Stheraven __list_iterator& operator=(const __list_iterator& __p) 299227825Stheraven { 300227825Stheraven if (this != &__p) 301227825Stheraven { 302227825Stheraven __get_db()->__iterator_copy(this, &__p); 303227825Stheraven __ptr_ = __p.__ptr_; 304227825Stheraven } 305227825Stheraven return *this; 306227825Stheraven } 307227825Stheraven 308227825Stheraven#endif // _LIBCPP_DEBUG_LEVEL >= 2 309227825Stheraven 310227825Stheraven _LIBCPP_INLINE_VISIBILITY 311227825Stheraven reference operator*() const 312227825Stheraven { 313227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 314227825Stheraven _LIBCPP_ASSERT(__get_const_db()->__dereferenceable(this), 315227825Stheraven "Attempted to dereference a non-dereferenceable list::iterator"); 316227825Stheraven#endif 317227825Stheraven return __ptr_->__value_; 318227825Stheraven } 319227825Stheraven _LIBCPP_INLINE_VISIBILITY 320253146Stheraven pointer operator->() const 321253146Stheraven { 322253146Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 323253146Stheraven _LIBCPP_ASSERT(__get_const_db()->__dereferenceable(this), 324253146Stheraven "Attempted to dereference a non-dereferenceable list::iterator"); 325253146Stheraven#endif 326253146Stheraven return pointer_traits<pointer>::pointer_to(__ptr_->__value_); 327253146Stheraven } 328227825Stheraven 329227825Stheraven _LIBCPP_INLINE_VISIBILITY 330227825Stheraven __list_iterator& operator++() 331227825Stheraven { 332227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 333227825Stheraven _LIBCPP_ASSERT(__get_const_db()->__dereferenceable(this), 334227825Stheraven "Attempted to increment non-incrementable list::iterator"); 335227825Stheraven#endif 336227825Stheraven __ptr_ = __ptr_->__next_; 337227825Stheraven return *this; 338227825Stheraven } 339227825Stheraven _LIBCPP_INLINE_VISIBILITY 340227825Stheraven __list_iterator operator++(int) {__list_iterator __t(*this); ++(*this); return __t;} 341227825Stheraven 342227825Stheraven _LIBCPP_INLINE_VISIBILITY 343227825Stheraven __list_iterator& operator--() 344227825Stheraven { 345227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 346227825Stheraven _LIBCPP_ASSERT(__get_const_db()->__decrementable(this), 347227825Stheraven "Attempted to decrement non-decrementable list::iterator"); 348227825Stheraven#endif 349227825Stheraven __ptr_ = __ptr_->__prev_; 350227825Stheraven return *this; 351227825Stheraven } 352227825Stheraven _LIBCPP_INLINE_VISIBILITY 353227825Stheraven __list_iterator operator--(int) {__list_iterator __t(*this); --(*this); return __t;} 354227825Stheraven 355227825Stheraven friend _LIBCPP_INLINE_VISIBILITY 356227825Stheraven bool operator==(const __list_iterator& __x, const __list_iterator& __y) 357227825Stheraven { 358227825Stheraven return __x.__ptr_ == __y.__ptr_; 359227825Stheraven } 360227825Stheraven friend _LIBCPP_INLINE_VISIBILITY 361227825Stheraven bool operator!=(const __list_iterator& __x, const __list_iterator& __y) 362227825Stheraven {return !(__x == __y);} 363227825Stheraven}; 364227825Stheraven 365227825Stheraventemplate <class _Tp, class _VoidPtr> 366261272Sdimclass _LIBCPP_TYPE_VIS_ONLY __list_const_iterator 367227825Stheraven{ 368227825Stheraven typedef typename pointer_traits<_VoidPtr>::template 369227825Stheraven#ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES 370253146Stheraven rebind<__list_node<_Tp, _VoidPtr> > __node_pointer; 371227825Stheraven#else 372253146Stheraven rebind<__list_node<_Tp, _VoidPtr> >::other __node_pointer; 373227825Stheraven#endif 374227825Stheraven 375227825Stheraven __node_pointer __ptr_; 376227825Stheraven 377227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 378227825Stheraven _LIBCPP_INLINE_VISIBILITY 379227825Stheraven explicit __list_const_iterator(__node_pointer __p, const void* __c) _NOEXCEPT 380227825Stheraven : __ptr_(__p) 381227825Stheraven { 382227825Stheraven __get_db()->__insert_ic(this, __c); 383227825Stheraven } 384227825Stheraven#else 385227825Stheraven _LIBCPP_INLINE_VISIBILITY 386227825Stheraven explicit __list_const_iterator(__node_pointer __p) _NOEXCEPT : __ptr_(__p) {} 387227825Stheraven#endif 388227825Stheraven 389227825Stheraven template<class, class> friend class list; 390227825Stheraven template<class, class> friend class __list_imp; 391227825Stheravenpublic: 392227825Stheraven typedef bidirectional_iterator_tag iterator_category; 393227825Stheraven typedef _Tp value_type; 394227825Stheraven typedef const value_type& reference; 395227825Stheraven typedef typename pointer_traits<_VoidPtr>::template 396227825Stheraven#ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES 397227825Stheraven rebind<const value_type> 398227825Stheraven#else 399227825Stheraven rebind<const value_type>::other 400227825Stheraven#endif 401227825Stheraven pointer; 402227825Stheraven typedef typename pointer_traits<pointer>::difference_type difference_type; 403227825Stheraven 404227825Stheraven _LIBCPP_INLINE_VISIBILITY 405261272Sdim __list_const_iterator() _NOEXCEPT : __ptr_(nullptr) 406227825Stheraven { 407227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 408227825Stheraven __get_db()->__insert_i(this); 409227825Stheraven#endif 410227825Stheraven } 411227825Stheraven _LIBCPP_INLINE_VISIBILITY 412249989Sdim __list_const_iterator(const __list_iterator<_Tp, _VoidPtr>& __p) _NOEXCEPT 413227825Stheraven : __ptr_(__p.__ptr_) 414227825Stheraven { 415227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 416227825Stheraven __get_db()->__iterator_copy(this, &__p); 417227825Stheraven#endif 418227825Stheraven } 419227825Stheraven 420227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 421227825Stheraven 422227825Stheraven _LIBCPP_INLINE_VISIBILITY 423227825Stheraven __list_const_iterator(const __list_const_iterator& __p) 424227825Stheraven : __ptr_(__p.__ptr_) 425227825Stheraven { 426227825Stheraven __get_db()->__iterator_copy(this, &__p); 427227825Stheraven } 428227825Stheraven 429227825Stheraven _LIBCPP_INLINE_VISIBILITY 430227825Stheraven ~__list_const_iterator() 431227825Stheraven { 432227825Stheraven __get_db()->__erase_i(this); 433227825Stheraven } 434227825Stheraven 435227825Stheraven _LIBCPP_INLINE_VISIBILITY 436227825Stheraven __list_const_iterator& operator=(const __list_const_iterator& __p) 437227825Stheraven { 438227825Stheraven if (this != &__p) 439227825Stheraven { 440227825Stheraven __get_db()->__iterator_copy(this, &__p); 441227825Stheraven __ptr_ = __p.__ptr_; 442227825Stheraven } 443227825Stheraven return *this; 444227825Stheraven } 445227825Stheraven 446227825Stheraven#endif // _LIBCPP_DEBUG_LEVEL >= 2 447227825Stheraven _LIBCPP_INLINE_VISIBILITY 448227825Stheraven reference operator*() const 449227825Stheraven { 450227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 451227825Stheraven _LIBCPP_ASSERT(__get_const_db()->__dereferenceable(this), 452227825Stheraven "Attempted to dereference a non-dereferenceable list::const_iterator"); 453227825Stheraven#endif 454227825Stheraven return __ptr_->__value_; 455227825Stheraven } 456227825Stheraven _LIBCPP_INLINE_VISIBILITY 457253146Stheraven pointer operator->() const 458253146Stheraven { 459253146Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 460253146Stheraven _LIBCPP_ASSERT(__get_const_db()->__dereferenceable(this), 461253146Stheraven "Attempted to dereference a non-dereferenceable list::iterator"); 462253146Stheraven#endif 463253146Stheraven return pointer_traits<pointer>::pointer_to(__ptr_->__value_); 464253146Stheraven } 465227825Stheraven 466227825Stheraven _LIBCPP_INLINE_VISIBILITY 467227825Stheraven __list_const_iterator& operator++() 468227825Stheraven { 469227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 470227825Stheraven _LIBCPP_ASSERT(__get_const_db()->__dereferenceable(this), 471227825Stheraven "Attempted to increment non-incrementable list::const_iterator"); 472227825Stheraven#endif 473227825Stheraven __ptr_ = __ptr_->__next_; 474227825Stheraven return *this; 475227825Stheraven } 476227825Stheraven _LIBCPP_INLINE_VISIBILITY 477227825Stheraven __list_const_iterator operator++(int) {__list_const_iterator __t(*this); ++(*this); return __t;} 478227825Stheraven 479227825Stheraven _LIBCPP_INLINE_VISIBILITY 480227825Stheraven __list_const_iterator& operator--() 481227825Stheraven { 482227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 483227825Stheraven _LIBCPP_ASSERT(__get_const_db()->__decrementable(this), 484227825Stheraven "Attempted to decrement non-decrementable list::const_iterator"); 485227825Stheraven#endif 486227825Stheraven __ptr_ = __ptr_->__prev_; 487227825Stheraven return *this; 488227825Stheraven } 489227825Stheraven _LIBCPP_INLINE_VISIBILITY 490227825Stheraven __list_const_iterator operator--(int) {__list_const_iterator __t(*this); --(*this); return __t;} 491227825Stheraven 492227825Stheraven friend _LIBCPP_INLINE_VISIBILITY 493227825Stheraven bool operator==(const __list_const_iterator& __x, const __list_const_iterator& __y) 494227825Stheraven { 495227825Stheraven return __x.__ptr_ == __y.__ptr_; 496227825Stheraven } 497227825Stheraven friend _LIBCPP_INLINE_VISIBILITY 498227825Stheraven bool operator!=(const __list_const_iterator& __x, const __list_const_iterator& __y) 499227825Stheraven {return !(__x == __y);} 500227825Stheraven}; 501227825Stheraven 502227825Stheraventemplate <class _Tp, class _Alloc> 503227825Stheravenclass __list_imp 504227825Stheraven{ 505227825Stheraven __list_imp(const __list_imp&); 506227825Stheraven __list_imp& operator=(const __list_imp&); 507227825Stheravenprotected: 508227825Stheraven typedef _Tp value_type; 509227825Stheraven typedef _Alloc allocator_type; 510227825Stheraven typedef allocator_traits<allocator_type> __alloc_traits; 511227825Stheraven typedef typename __alloc_traits::size_type size_type; 512227825Stheraven typedef typename __alloc_traits::void_pointer __void_pointer; 513227825Stheraven typedef __list_iterator<value_type, __void_pointer> iterator; 514227825Stheraven typedef __list_const_iterator<value_type, __void_pointer> const_iterator; 515227825Stheraven typedef __list_node_base<value_type, __void_pointer> __node_base; 516227825Stheraven typedef __list_node<value_type, __void_pointer> __node; 517288943Sdim typedef typename __rebind_alloc_helper<__alloc_traits, __node>::type __node_allocator; 518227825Stheraven typedef allocator_traits<__node_allocator> __node_alloc_traits; 519227825Stheraven typedef typename __node_alloc_traits::pointer __node_pointer; 520253146Stheraven typedef typename __node_alloc_traits::pointer __node_const_pointer; 521227825Stheraven typedef typename __alloc_traits::pointer pointer; 522227825Stheraven typedef typename __alloc_traits::const_pointer const_pointer; 523227825Stheraven typedef typename __alloc_traits::difference_type difference_type; 524227825Stheraven 525288943Sdim typedef typename __rebind_alloc_helper<__alloc_traits, __node_base>::type __node_base_allocator; 526253146Stheraven typedef typename allocator_traits<__node_base_allocator>::pointer __node_base_pointer; 527253146Stheraven 528227825Stheraven __node_base __end_; 529227825Stheraven __compressed_pair<size_type, __node_allocator> __size_alloc_; 530227825Stheraven 531227825Stheraven _LIBCPP_INLINE_VISIBILITY 532227825Stheraven size_type& __sz() _NOEXCEPT {return __size_alloc_.first();} 533227825Stheraven _LIBCPP_INLINE_VISIBILITY 534227825Stheraven const size_type& __sz() const _NOEXCEPT 535227825Stheraven {return __size_alloc_.first();} 536227825Stheraven _LIBCPP_INLINE_VISIBILITY 537227825Stheraven __node_allocator& __node_alloc() _NOEXCEPT 538227825Stheraven {return __size_alloc_.second();} 539227825Stheraven _LIBCPP_INLINE_VISIBILITY 540227825Stheraven const __node_allocator& __node_alloc() const _NOEXCEPT 541227825Stheraven {return __size_alloc_.second();} 542227825Stheraven 543253146Stheraven static void __unlink_nodes(__node_pointer __f, __node_pointer __l) _NOEXCEPT; 544227825Stheraven 545227825Stheraven __list_imp() 546227825Stheraven _NOEXCEPT_(is_nothrow_default_constructible<__node_allocator>::value); 547227825Stheraven __list_imp(const allocator_type& __a); 548227825Stheraven ~__list_imp(); 549227825Stheraven void clear() _NOEXCEPT; 550227825Stheraven _LIBCPP_INLINE_VISIBILITY 551227825Stheraven bool empty() const _NOEXCEPT {return __sz() == 0;} 552227825Stheraven 553227825Stheraven _LIBCPP_INLINE_VISIBILITY 554227825Stheraven iterator begin() _NOEXCEPT 555227825Stheraven { 556227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 557227825Stheraven return iterator(__end_.__next_, this); 558227825Stheraven#else 559227825Stheraven return iterator(__end_.__next_); 560227825Stheraven#endif 561227825Stheraven } 562227825Stheraven _LIBCPP_INLINE_VISIBILITY 563227825Stheraven const_iterator begin() const _NOEXCEPT 564227825Stheraven { 565227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 566227825Stheraven return const_iterator(__end_.__next_, this); 567227825Stheraven#else 568227825Stheraven return const_iterator(__end_.__next_); 569227825Stheraven#endif 570227825Stheraven } 571227825Stheraven _LIBCPP_INLINE_VISIBILITY 572227825Stheraven iterator end() _NOEXCEPT 573227825Stheraven { 574227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 575253146Stheraven return iterator(static_cast<__node_pointer>( 576253146Stheraven pointer_traits<__node_base_pointer>::pointer_to(__end_)), this); 577227825Stheraven#else 578253146Stheraven return iterator(static_cast<__node_pointer>( 579253146Stheraven pointer_traits<__node_base_pointer>::pointer_to(__end_))); 580227825Stheraven#endif 581227825Stheraven } 582227825Stheraven _LIBCPP_INLINE_VISIBILITY 583227825Stheraven const_iterator end() const _NOEXCEPT 584227825Stheraven { 585227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 586253146Stheraven return const_iterator(static_cast<__node_const_pointer>( 587253146Stheraven pointer_traits<__node_base_pointer>::pointer_to(const_cast<__node_base&>(__end_))), this); 588227825Stheraven#else 589253146Stheraven return const_iterator(static_cast<__node_const_pointer>( 590253146Stheraven pointer_traits<__node_base_pointer>::pointer_to(const_cast<__node_base&>(__end_)))); 591227825Stheraven#endif 592227825Stheraven } 593227825Stheraven 594227825Stheraven void swap(__list_imp& __c) 595288943Sdim#if _LIBCPP_STD_VER >= 14 596288943Sdim _NOEXCEPT; 597288943Sdim#else 598288943Sdim _NOEXCEPT_(!__alloc_traits::propagate_on_container_swap::value || 599288943Sdim __is_nothrow_swappable<allocator_type>::value); 600288943Sdim#endif 601227825Stheraven 602227825Stheraven _LIBCPP_INLINE_VISIBILITY 603227825Stheraven void __copy_assign_alloc(const __list_imp& __c) 604227825Stheraven {__copy_assign_alloc(__c, integral_constant<bool, 605227825Stheraven __node_alloc_traits::propagate_on_container_copy_assignment::value>());} 606227825Stheraven 607227825Stheraven _LIBCPP_INLINE_VISIBILITY 608227825Stheraven void __move_assign_alloc(__list_imp& __c) 609227825Stheraven _NOEXCEPT_( 610227825Stheraven !__node_alloc_traits::propagate_on_container_move_assignment::value || 611227825Stheraven is_nothrow_move_assignable<__node_allocator>::value) 612227825Stheraven {__move_assign_alloc(__c, integral_constant<bool, 613227825Stheraven __node_alloc_traits::propagate_on_container_move_assignment::value>());} 614227825Stheraven 615227825Stheravenprivate: 616227825Stheraven _LIBCPP_INLINE_VISIBILITY 617227825Stheraven void __copy_assign_alloc(const __list_imp& __c, true_type) 618227825Stheraven { 619227825Stheraven if (__node_alloc() != __c.__node_alloc()) 620227825Stheraven clear(); 621227825Stheraven __node_alloc() = __c.__node_alloc(); 622227825Stheraven } 623227825Stheraven 624227825Stheraven _LIBCPP_INLINE_VISIBILITY 625227825Stheraven void __copy_assign_alloc(const __list_imp& __c, false_type) 626227825Stheraven {} 627227825Stheraven 628227825Stheraven _LIBCPP_INLINE_VISIBILITY 629227825Stheraven void __move_assign_alloc(__list_imp& __c, true_type) 630227825Stheraven _NOEXCEPT_(is_nothrow_move_assignable<__node_allocator>::value) 631227825Stheraven { 632227825Stheraven __node_alloc() = _VSTD::move(__c.__node_alloc()); 633227825Stheraven } 634227825Stheraven 635227825Stheraven _LIBCPP_INLINE_VISIBILITY 636227825Stheraven void __move_assign_alloc(__list_imp& __c, false_type) 637227825Stheraven _NOEXCEPT 638227825Stheraven {} 639227825Stheraven}; 640227825Stheraven 641227825Stheraven// Unlink nodes [__f, __l] 642227825Stheraventemplate <class _Tp, class _Alloc> 643227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 644227825Stheravenvoid 645253146Stheraven__list_imp<_Tp, _Alloc>::__unlink_nodes(__node_pointer __f, __node_pointer __l) 646227825Stheraven _NOEXCEPT 647227825Stheraven{ 648253146Stheraven __f->__prev_->__next_ = __l->__next_; 649253146Stheraven __l->__next_->__prev_ = __f->__prev_; 650227825Stheraven} 651227825Stheraven 652227825Stheraventemplate <class _Tp, class _Alloc> 653227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 654227825Stheraven__list_imp<_Tp, _Alloc>::__list_imp() 655227825Stheraven _NOEXCEPT_(is_nothrow_default_constructible<__node_allocator>::value) 656227825Stheraven : __size_alloc_(0) 657227825Stheraven{ 658227825Stheraven} 659227825Stheraven 660227825Stheraventemplate <class _Tp, class _Alloc> 661227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 662227825Stheraven__list_imp<_Tp, _Alloc>::__list_imp(const allocator_type& __a) 663227825Stheraven : __size_alloc_(0, __node_allocator(__a)) 664227825Stheraven{ 665227825Stheraven} 666227825Stheraven 667227825Stheraventemplate <class _Tp, class _Alloc> 668227825Stheraven__list_imp<_Tp, _Alloc>::~__list_imp() 669227825Stheraven{ 670227825Stheraven clear(); 671227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 672227825Stheraven __get_db()->__erase_c(this); 673227825Stheraven#endif 674227825Stheraven} 675227825Stheraven 676227825Stheraventemplate <class _Tp, class _Alloc> 677227825Stheravenvoid 678227825Stheraven__list_imp<_Tp, _Alloc>::clear() _NOEXCEPT 679227825Stheraven{ 680227825Stheraven if (!empty()) 681227825Stheraven { 682227825Stheraven __node_allocator& __na = __node_alloc(); 683227825Stheraven __node_pointer __f = __end_.__next_; 684253146Stheraven __node_pointer __l = static_cast<__node_pointer>( 685253146Stheraven pointer_traits<__node_base_pointer>::pointer_to(__end_)); 686253146Stheraven __unlink_nodes(__f, __l->__prev_); 687227825Stheraven __sz() = 0; 688227825Stheraven while (__f != __l) 689227825Stheraven { 690253146Stheraven __node_pointer __n = __f; 691227825Stheraven __f = __f->__next_; 692253146Stheraven __node_alloc_traits::destroy(__na, _VSTD::addressof(__n->__value_)); 693253146Stheraven __node_alloc_traits::deallocate(__na, __n, 1); 694227825Stheraven } 695227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 696227825Stheraven __c_node* __c = __get_db()->__find_c_and_lock(this); 697227825Stheraven for (__i_node** __p = __c->end_; __p != __c->beg_; ) 698227825Stheraven { 699227825Stheraven --__p; 700227825Stheraven const_iterator* __i = static_cast<const_iterator*>((*__p)->__i_); 701227825Stheraven if (__i->__ptr_ != __l) 702227825Stheraven { 703227825Stheraven (*__p)->__c_ = nullptr; 704227825Stheraven if (--__c->end_ != __p) 705227825Stheraven memmove(__p, __p+1, (__c->end_ - __p)*sizeof(__i_node*)); 706227825Stheraven } 707227825Stheraven } 708227825Stheraven __get_db()->unlock(); 709227825Stheraven#endif 710227825Stheraven } 711227825Stheraven} 712227825Stheraven 713227825Stheraventemplate <class _Tp, class _Alloc> 714227825Stheravenvoid 715227825Stheraven__list_imp<_Tp, _Alloc>::swap(__list_imp& __c) 716288943Sdim#if _LIBCPP_STD_VER >= 14 717288943Sdim _NOEXCEPT 718288943Sdim#else 719288943Sdim _NOEXCEPT_(!__alloc_traits::propagate_on_container_swap::value || 720288943Sdim __is_nothrow_swappable<allocator_type>::value) 721288943Sdim#endif 722227825Stheraven{ 723227825Stheraven _LIBCPP_ASSERT(__alloc_traits::propagate_on_container_swap::value || 724227825Stheraven this->__node_alloc() == __c.__node_alloc(), 725227825Stheraven "list::swap: Either propagate_on_container_swap must be true" 726227825Stheraven " or the allocators must compare equal"); 727227825Stheraven using _VSTD::swap; 728288943Sdim __swap_allocator(__node_alloc(), __c.__node_alloc()); 729227825Stheraven swap(__sz(), __c.__sz()); 730227825Stheraven swap(__end_, __c.__end_); 731227825Stheraven if (__sz() == 0) 732276792Sdim __end_.__next_ = __end_.__prev_ = __end_.__self(); 733227825Stheraven else 734276792Sdim __end_.__prev_->__next_ = __end_.__next_->__prev_ = __end_.__self(); 735227825Stheraven if (__c.__sz() == 0) 736276792Sdim __c.__end_.__next_ = __c.__end_.__prev_ = __c.__end_.__self(); 737227825Stheraven else 738276792Sdim __c.__end_.__prev_->__next_ = __c.__end_.__next_->__prev_ = __c.__end_.__self(); 739276792Sdim 740227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 741227825Stheraven __libcpp_db* __db = __get_db(); 742227825Stheraven __c_node* __cn1 = __db->__find_c_and_lock(this); 743227825Stheraven __c_node* __cn2 = __db->__find_c(&__c); 744227825Stheraven std::swap(__cn1->beg_, __cn2->beg_); 745227825Stheraven std::swap(__cn1->end_, __cn2->end_); 746227825Stheraven std::swap(__cn1->cap_, __cn2->cap_); 747227825Stheraven for (__i_node** __p = __cn1->end_; __p != __cn1->beg_;) 748227825Stheraven { 749227825Stheraven --__p; 750227825Stheraven const_iterator* __i = static_cast<const_iterator*>((*__p)->__i_); 751253146Stheraven if (__i->__ptr_ == static_cast<__node_pointer>( 752253146Stheraven pointer_traits<__node_base_pointer>::pointer_to(__c.__end_))) 753227825Stheraven { 754227825Stheraven __cn2->__add(*__p); 755227825Stheraven if (--__cn1->end_ != __p) 756227825Stheraven memmove(__p, __p+1, (__cn1->end_ - __p)*sizeof(__i_node*)); 757227825Stheraven } 758227825Stheraven else 759227825Stheraven (*__p)->__c_ = __cn1; 760227825Stheraven } 761227825Stheraven for (__i_node** __p = __cn2->end_; __p != __cn2->beg_;) 762227825Stheraven { 763227825Stheraven --__p; 764227825Stheraven const_iterator* __i = static_cast<const_iterator*>((*__p)->__i_); 765253146Stheraven if (__i->__ptr_ == static_cast<__node_pointer>( 766253146Stheraven pointer_traits<__node_base_pointer>::pointer_to(__end_))) 767227825Stheraven { 768227825Stheraven __cn1->__add(*__p); 769227825Stheraven if (--__cn2->end_ != __p) 770227825Stheraven memmove(__p, __p+1, (__cn2->end_ - __p)*sizeof(__i_node*)); 771227825Stheraven } 772227825Stheraven else 773227825Stheraven (*__p)->__c_ = __cn2; 774227825Stheraven } 775227825Stheraven __db->unlock(); 776227825Stheraven#endif 777227825Stheraven} 778227825Stheraven 779288943Sdimtemplate <class _Tp, class _Alloc /*= allocator<_Tp>*/> 780261272Sdimclass _LIBCPP_TYPE_VIS_ONLY list 781227825Stheraven : private __list_imp<_Tp, _Alloc> 782227825Stheraven{ 783227825Stheraven typedef __list_imp<_Tp, _Alloc> base; 784227825Stheraven typedef typename base::__node __node; 785227825Stheraven typedef typename base::__node_allocator __node_allocator; 786227825Stheraven typedef typename base::__node_pointer __node_pointer; 787227825Stheraven typedef typename base::__node_alloc_traits __node_alloc_traits; 788253146Stheraven typedef typename base::__node_base __node_base; 789253146Stheraven typedef typename base::__node_base_pointer __node_base_pointer; 790227825Stheraven 791227825Stheravenpublic: 792227825Stheraven typedef _Tp value_type; 793227825Stheraven typedef _Alloc allocator_type; 794227825Stheraven static_assert((is_same<value_type, typename allocator_type::value_type>::value), 795227825Stheraven "Invalid allocator::value_type"); 796227825Stheraven typedef value_type& reference; 797227825Stheraven typedef const value_type& const_reference; 798227825Stheraven typedef typename base::pointer pointer; 799227825Stheraven typedef typename base::const_pointer const_pointer; 800227825Stheraven typedef typename base::size_type size_type; 801227825Stheraven typedef typename base::difference_type difference_type; 802227825Stheraven typedef typename base::iterator iterator; 803227825Stheraven typedef typename base::const_iterator const_iterator; 804227825Stheraven typedef _VSTD::reverse_iterator<iterator> reverse_iterator; 805227825Stheraven typedef _VSTD::reverse_iterator<const_iterator> const_reverse_iterator; 806227825Stheraven 807227825Stheraven _LIBCPP_INLINE_VISIBILITY 808227825Stheraven list() 809227825Stheraven _NOEXCEPT_(is_nothrow_default_constructible<__node_allocator>::value) 810227825Stheraven { 811227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 812227825Stheraven __get_db()->__insert_c(this); 813227825Stheraven#endif 814227825Stheraven } 815227825Stheraven _LIBCPP_INLINE_VISIBILITY 816261272Sdim explicit list(const allocator_type& __a) : base(__a) 817227825Stheraven { 818227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 819227825Stheraven __get_db()->__insert_c(this); 820227825Stheraven#endif 821227825Stheraven } 822261272Sdim explicit list(size_type __n); 823261272Sdim#if _LIBCPP_STD_VER > 11 824261272Sdim explicit list(size_type __n, const allocator_type& __a); 825261272Sdim#endif 826227825Stheraven list(size_type __n, const value_type& __x); 827227825Stheraven list(size_type __n, const value_type& __x, const allocator_type& __a); 828227825Stheraven template <class _InpIter> 829227825Stheraven list(_InpIter __f, _InpIter __l, 830227825Stheraven typename enable_if<__is_input_iterator<_InpIter>::value>::type* = 0); 831227825Stheraven template <class _InpIter> 832227825Stheraven list(_InpIter __f, _InpIter __l, const allocator_type& __a, 833227825Stheraven typename enable_if<__is_input_iterator<_InpIter>::value>::type* = 0); 834227825Stheraven 835227825Stheraven list(const list& __c); 836227825Stheraven list(const list& __c, const allocator_type& __a); 837227825Stheraven list& operator=(const list& __c); 838227825Stheraven#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 839227825Stheraven list(initializer_list<value_type> __il); 840227825Stheraven list(initializer_list<value_type> __il, const allocator_type& __a); 841227825Stheraven#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 842227825Stheraven#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 843227825Stheraven list(list&& __c) 844227825Stheraven _NOEXCEPT_(is_nothrow_move_constructible<__node_allocator>::value); 845227825Stheraven list(list&& __c, const allocator_type& __a); 846227825Stheraven list& operator=(list&& __c) 847227825Stheraven _NOEXCEPT_( 848227825Stheraven __node_alloc_traits::propagate_on_container_move_assignment::value && 849227825Stheraven is_nothrow_move_assignable<__node_allocator>::value); 850227825Stheraven#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 851227825Stheraven#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 852227825Stheraven _LIBCPP_INLINE_VISIBILITY 853227825Stheraven list& operator=(initializer_list<value_type> __il) 854227825Stheraven {assign(__il.begin(), __il.end()); return *this;} 855227825Stheraven#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 856227825Stheraven 857227825Stheraven template <class _InpIter> 858227825Stheraven void assign(_InpIter __f, _InpIter __l, 859227825Stheraven typename enable_if<__is_input_iterator<_InpIter>::value>::type* = 0); 860227825Stheraven void assign(size_type __n, const value_type& __x); 861227825Stheraven#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 862227825Stheraven _LIBCPP_INLINE_VISIBILITY 863227825Stheraven void assign(initializer_list<value_type> __il) 864227825Stheraven {assign(__il.begin(), __il.end());} 865227825Stheraven#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 866227825Stheraven 867227825Stheraven allocator_type get_allocator() const _NOEXCEPT; 868227825Stheraven 869227825Stheraven _LIBCPP_INLINE_VISIBILITY 870227825Stheraven size_type size() const _NOEXCEPT {return base::__sz();} 871227825Stheraven _LIBCPP_INLINE_VISIBILITY 872227825Stheraven bool empty() const _NOEXCEPT {return base::empty();} 873227825Stheraven _LIBCPP_INLINE_VISIBILITY 874227825Stheraven size_type max_size() const _NOEXCEPT 875227825Stheraven {return numeric_limits<difference_type>::max();} 876227825Stheraven 877227825Stheraven _LIBCPP_INLINE_VISIBILITY 878227825Stheraven iterator begin() _NOEXCEPT {return base::begin();} 879227825Stheraven _LIBCPP_INLINE_VISIBILITY 880227825Stheraven const_iterator begin() const _NOEXCEPT {return base::begin();} 881227825Stheraven _LIBCPP_INLINE_VISIBILITY 882227825Stheraven iterator end() _NOEXCEPT {return base::end();} 883227825Stheraven _LIBCPP_INLINE_VISIBILITY 884227825Stheraven const_iterator end() const _NOEXCEPT {return base::end();} 885227825Stheraven _LIBCPP_INLINE_VISIBILITY 886227825Stheraven const_iterator cbegin() const _NOEXCEPT {return base::begin();} 887227825Stheraven _LIBCPP_INLINE_VISIBILITY 888227825Stheraven const_iterator cend() const _NOEXCEPT {return base::end();} 889227825Stheraven 890227825Stheraven _LIBCPP_INLINE_VISIBILITY 891227825Stheraven reverse_iterator rbegin() _NOEXCEPT 892227825Stheraven {return reverse_iterator(end());} 893227825Stheraven _LIBCPP_INLINE_VISIBILITY 894227825Stheraven const_reverse_iterator rbegin() const _NOEXCEPT 895227825Stheraven {return const_reverse_iterator(end());} 896227825Stheraven _LIBCPP_INLINE_VISIBILITY 897227825Stheraven reverse_iterator rend() _NOEXCEPT 898227825Stheraven {return reverse_iterator(begin());} 899227825Stheraven _LIBCPP_INLINE_VISIBILITY 900227825Stheraven const_reverse_iterator rend() const _NOEXCEPT 901227825Stheraven {return const_reverse_iterator(begin());} 902227825Stheraven _LIBCPP_INLINE_VISIBILITY 903227825Stheraven const_reverse_iterator crbegin() const _NOEXCEPT 904227825Stheraven {return const_reverse_iterator(end());} 905227825Stheraven _LIBCPP_INLINE_VISIBILITY 906227825Stheraven const_reverse_iterator crend() const _NOEXCEPT 907227825Stheraven {return const_reverse_iterator(begin());} 908227825Stheraven 909227825Stheraven _LIBCPP_INLINE_VISIBILITY 910227825Stheraven reference front() 911227825Stheraven { 912227825Stheraven _LIBCPP_ASSERT(!empty(), "list::front called on empty list"); 913227825Stheraven return base::__end_.__next_->__value_; 914227825Stheraven } 915227825Stheraven _LIBCPP_INLINE_VISIBILITY 916227825Stheraven const_reference front() const 917227825Stheraven { 918227825Stheraven _LIBCPP_ASSERT(!empty(), "list::front called on empty list"); 919227825Stheraven return base::__end_.__next_->__value_; 920227825Stheraven } 921227825Stheraven _LIBCPP_INLINE_VISIBILITY 922227825Stheraven reference back() 923227825Stheraven { 924227825Stheraven _LIBCPP_ASSERT(!empty(), "list::back called on empty list"); 925227825Stheraven return base::__end_.__prev_->__value_; 926227825Stheraven } 927227825Stheraven _LIBCPP_INLINE_VISIBILITY 928227825Stheraven const_reference back() const 929227825Stheraven { 930227825Stheraven _LIBCPP_ASSERT(!empty(), "list::back called on empty list"); 931227825Stheraven return base::__end_.__prev_->__value_; 932227825Stheraven } 933227825Stheraven 934227825Stheraven#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 935227825Stheraven void push_front(value_type&& __x); 936227825Stheraven void push_back(value_type&& __x); 937227825Stheraven#ifndef _LIBCPP_HAS_NO_VARIADICS 938227825Stheraven template <class... _Args> 939227825Stheraven void emplace_front(_Args&&... __args); 940227825Stheraven template <class... _Args> 941227825Stheraven void emplace_back(_Args&&... __args); 942227825Stheraven template <class... _Args> 943227825Stheraven iterator emplace(const_iterator __p, _Args&&... __args); 944227825Stheraven#endif // _LIBCPP_HAS_NO_VARIADICS 945227825Stheraven iterator insert(const_iterator __p, value_type&& __x); 946227825Stheraven#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 947227825Stheraven 948227825Stheraven void push_front(const value_type& __x); 949227825Stheraven void push_back(const value_type& __x); 950227825Stheraven 951227825Stheraven iterator insert(const_iterator __p, const value_type& __x); 952227825Stheraven iterator insert(const_iterator __p, size_type __n, const value_type& __x); 953227825Stheraven template <class _InpIter> 954227825Stheraven iterator insert(const_iterator __p, _InpIter __f, _InpIter __l, 955227825Stheraven typename enable_if<__is_input_iterator<_InpIter>::value>::type* = 0); 956227825Stheraven#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 957227825Stheraven _LIBCPP_INLINE_VISIBILITY 958227825Stheraven iterator insert(const_iterator __p, initializer_list<value_type> __il) 959227825Stheraven {return insert(__p, __il.begin(), __il.end());} 960227825Stheraven#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 961227825Stheraven 962227825Stheraven _LIBCPP_INLINE_VISIBILITY 963227825Stheraven void swap(list& __c) 964288943Sdim#if _LIBCPP_STD_VER >= 14 965288943Sdim _NOEXCEPT 966288943Sdim#else 967227825Stheraven _NOEXCEPT_(!__node_alloc_traits::propagate_on_container_swap::value || 968227825Stheraven __is_nothrow_swappable<__node_allocator>::value) 969288943Sdim#endif 970227825Stheraven {base::swap(__c);} 971227825Stheraven _LIBCPP_INLINE_VISIBILITY 972227825Stheraven void clear() _NOEXCEPT {base::clear();} 973227825Stheraven 974227825Stheraven void pop_front(); 975227825Stheraven void pop_back(); 976227825Stheraven 977227825Stheraven iterator erase(const_iterator __p); 978227825Stheraven iterator erase(const_iterator __f, const_iterator __l); 979227825Stheraven 980227825Stheraven void resize(size_type __n); 981227825Stheraven void resize(size_type __n, const value_type& __x); 982227825Stheraven 983227825Stheraven void splice(const_iterator __p, list& __c); 984227825Stheraven#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 985227825Stheraven _LIBCPP_INLINE_VISIBILITY 986227825Stheraven void splice(const_iterator __p, list&& __c) {splice(__p, __c);} 987227825Stheraven#endif 988227825Stheraven void splice(const_iterator __p, list& __c, const_iterator __i); 989227825Stheraven#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 990227825Stheraven _LIBCPP_INLINE_VISIBILITY 991227825Stheraven void splice(const_iterator __p, list&& __c, const_iterator __i) 992227825Stheraven {splice(__p, __c, __i);} 993227825Stheraven#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 994227825Stheraven void splice(const_iterator __p, list& __c, const_iterator __f, const_iterator __l); 995227825Stheraven#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 996227825Stheraven _LIBCPP_INLINE_VISIBILITY 997227825Stheraven void splice(const_iterator __p, list&& __c, const_iterator __f, const_iterator __l) 998227825Stheraven {splice(__p, __c, __f, __l);} 999227825Stheraven#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 1000227825Stheraven 1001227825Stheraven void remove(const value_type& __x); 1002227825Stheraven template <class _Pred> void remove_if(_Pred __pred); 1003227825Stheraven void unique(); 1004227825Stheraven template <class _BinaryPred> 1005227825Stheraven void unique(_BinaryPred __binary_pred); 1006227825Stheraven void merge(list& __c); 1007227825Stheraven#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 1008227825Stheraven _LIBCPP_INLINE_VISIBILITY 1009227825Stheraven void merge(list&& __c) {merge(__c);} 1010227825Stheraven#endif 1011227825Stheraven template <class _Comp> 1012227825Stheraven void merge(list& __c, _Comp __comp); 1013227825Stheraven#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 1014227825Stheraven template <class _Comp> 1015227825Stheraven _LIBCPP_INLINE_VISIBILITY 1016227825Stheraven void merge(list&& __c, _Comp __comp) {merge(__c, __comp);} 1017227825Stheraven#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 1018227825Stheraven void sort(); 1019227825Stheraven template <class _Comp> 1020227825Stheraven void sort(_Comp __comp); 1021227825Stheraven 1022227825Stheraven void reverse() _NOEXCEPT; 1023227825Stheraven 1024227825Stheraven bool __invariants() const; 1025227825Stheraven 1026227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 1027227825Stheraven 1028227825Stheraven bool __dereferenceable(const const_iterator* __i) const; 1029227825Stheraven bool __decrementable(const const_iterator* __i) const; 1030227825Stheraven bool __addable(const const_iterator* __i, ptrdiff_t __n) const; 1031227825Stheraven bool __subscriptable(const const_iterator* __i, ptrdiff_t __n) const; 1032227825Stheraven 1033227825Stheraven#endif // _LIBCPP_DEBUG_LEVEL >= 2 1034227825Stheraven 1035227825Stheravenprivate: 1036276792Sdim static void __link_nodes (__node_pointer __p, __node_pointer __f, __node_pointer __l); 1037276792Sdim void __link_nodes_at_front(__node_pointer __f, __node_pointer __l); 1038276792Sdim void __link_nodes_at_back (__node_pointer __f, __node_pointer __l); 1039227825Stheraven iterator __iterator(size_type __n); 1040227825Stheraven template <class _Comp> 1041227825Stheraven static iterator __sort(iterator __f1, iterator __e2, size_type __n, _Comp& __comp); 1042227825Stheraven 1043227825Stheraven void __move_assign(list& __c, true_type) 1044227825Stheraven _NOEXCEPT_(is_nothrow_move_assignable<__node_allocator>::value); 1045227825Stheraven void __move_assign(list& __c, false_type); 1046227825Stheraven}; 1047227825Stheraven 1048227825Stheraven// Link in nodes [__f, __l] just prior to __p 1049227825Stheraventemplate <class _Tp, class _Alloc> 1050227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 1051227825Stheravenvoid 1052253146Stheravenlist<_Tp, _Alloc>::__link_nodes(__node_pointer __p, __node_pointer __f, __node_pointer __l) 1053227825Stheraven{ 1054253146Stheraven __p->__prev_->__next_ = __f; 1055253146Stheraven __f->__prev_ = __p->__prev_; 1056253146Stheraven __p->__prev_ = __l; 1057253146Stheraven __l->__next_ = __p; 1058227825Stheraven} 1059227825Stheraven 1060276792Sdim// Link in nodes [__f, __l] at the front of the list 1061227825Stheraventemplate <class _Tp, class _Alloc> 1062227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 1063276792Sdimvoid 1064276792Sdimlist<_Tp, _Alloc>::__link_nodes_at_front(__node_pointer __f, __node_pointer __l) 1065276792Sdim{ 1066276792Sdim __f->__prev_ = base::__end_.__self(); 1067276792Sdim __l->__next_ = base::__end_.__next_; 1068276792Sdim __l->__next_->__prev_ = __l; 1069276792Sdim base::__end_.__next_ = __f; 1070276792Sdim} 1071276792Sdim 1072276792Sdim// Link in nodes [__f, __l] at the front of the list 1073276792Sdimtemplate <class _Tp, class _Alloc> 1074276792Sdiminline _LIBCPP_INLINE_VISIBILITY 1075276792Sdimvoid 1076276792Sdimlist<_Tp, _Alloc>::__link_nodes_at_back(__node_pointer __f, __node_pointer __l) 1077276792Sdim{ 1078276792Sdim __l->__next_ = base::__end_.__self(); 1079276792Sdim __f->__prev_ = base::__end_.__prev_; 1080276792Sdim __f->__prev_->__next_ = __f; 1081276792Sdim base::__end_.__prev_ = __l; 1082276792Sdim} 1083276792Sdim 1084276792Sdim 1085276792Sdimtemplate <class _Tp, class _Alloc> 1086276792Sdiminline _LIBCPP_INLINE_VISIBILITY 1087227825Stheraventypename list<_Tp, _Alloc>::iterator 1088227825Stheravenlist<_Tp, _Alloc>::__iterator(size_type __n) 1089227825Stheraven{ 1090227825Stheraven return __n <= base::__sz() / 2 ? _VSTD::next(begin(), __n) 1091227825Stheraven : _VSTD::prev(end(), base::__sz() - __n); 1092227825Stheraven} 1093227825Stheraven 1094227825Stheraventemplate <class _Tp, class _Alloc> 1095227825Stheravenlist<_Tp, _Alloc>::list(size_type __n) 1096227825Stheraven{ 1097227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 1098227825Stheraven __get_db()->__insert_c(this); 1099227825Stheraven#endif 1100227825Stheraven for (; __n > 0; --__n) 1101227825Stheraven#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 1102227825Stheraven emplace_back(); 1103227825Stheraven#else 1104227825Stheraven push_back(value_type()); 1105227825Stheraven#endif 1106227825Stheraven} 1107227825Stheraven 1108261272Sdim#if _LIBCPP_STD_VER > 11 1109227825Stheraventemplate <class _Tp, class _Alloc> 1110261272Sdimlist<_Tp, _Alloc>::list(size_type __n, const allocator_type& __a) : base(__a) 1111261272Sdim{ 1112261272Sdim#if _LIBCPP_DEBUG_LEVEL >= 2 1113261272Sdim __get_db()->__insert_c(this); 1114261272Sdim#endif 1115261272Sdim for (; __n > 0; --__n) 1116261272Sdim#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 1117261272Sdim emplace_back(); 1118261272Sdim#else 1119261272Sdim push_back(value_type()); 1120261272Sdim#endif 1121261272Sdim} 1122261272Sdim#endif 1123261272Sdim 1124261272Sdimtemplate <class _Tp, class _Alloc> 1125227825Stheravenlist<_Tp, _Alloc>::list(size_type __n, const value_type& __x) 1126227825Stheraven{ 1127227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 1128227825Stheraven __get_db()->__insert_c(this); 1129227825Stheraven#endif 1130227825Stheraven for (; __n > 0; --__n) 1131227825Stheraven push_back(__x); 1132227825Stheraven} 1133227825Stheraven 1134227825Stheraventemplate <class _Tp, class _Alloc> 1135227825Stheravenlist<_Tp, _Alloc>::list(size_type __n, const value_type& __x, const allocator_type& __a) 1136227825Stheraven : base(__a) 1137227825Stheraven{ 1138227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 1139227825Stheraven __get_db()->__insert_c(this); 1140227825Stheraven#endif 1141227825Stheraven for (; __n > 0; --__n) 1142227825Stheraven push_back(__x); 1143227825Stheraven} 1144227825Stheraven 1145227825Stheraventemplate <class _Tp, class _Alloc> 1146227825Stheraventemplate <class _InpIter> 1147227825Stheravenlist<_Tp, _Alloc>::list(_InpIter __f, _InpIter __l, 1148227825Stheraven typename enable_if<__is_input_iterator<_InpIter>::value>::type*) 1149227825Stheraven{ 1150227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 1151227825Stheraven __get_db()->__insert_c(this); 1152227825Stheraven#endif 1153227825Stheraven for (; __f != __l; ++__f) 1154227825Stheraven push_back(*__f); 1155227825Stheraven} 1156227825Stheraven 1157227825Stheraventemplate <class _Tp, class _Alloc> 1158227825Stheraventemplate <class _InpIter> 1159227825Stheravenlist<_Tp, _Alloc>::list(_InpIter __f, _InpIter __l, const allocator_type& __a, 1160227825Stheraven typename enable_if<__is_input_iterator<_InpIter>::value>::type*) 1161227825Stheraven : base(__a) 1162227825Stheraven{ 1163227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 1164227825Stheraven __get_db()->__insert_c(this); 1165227825Stheraven#endif 1166227825Stheraven for (; __f != __l; ++__f) 1167227825Stheraven push_back(*__f); 1168227825Stheraven} 1169227825Stheraven 1170227825Stheraventemplate <class _Tp, class _Alloc> 1171227825Stheravenlist<_Tp, _Alloc>::list(const list& __c) 1172227825Stheraven : base(allocator_type( 1173227825Stheraven __node_alloc_traits::select_on_container_copy_construction( 1174227825Stheraven __c.__node_alloc()))) 1175227825Stheraven{ 1176227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 1177227825Stheraven __get_db()->__insert_c(this); 1178227825Stheraven#endif 1179227825Stheraven for (const_iterator __i = __c.begin(), __e = __c.end(); __i != __e; ++__i) 1180227825Stheraven push_back(*__i); 1181227825Stheraven} 1182227825Stheraven 1183227825Stheraventemplate <class _Tp, class _Alloc> 1184227825Stheravenlist<_Tp, _Alloc>::list(const list& __c, const allocator_type& __a) 1185227825Stheraven : base(__a) 1186227825Stheraven{ 1187227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 1188227825Stheraven __get_db()->__insert_c(this); 1189227825Stheraven#endif 1190227825Stheraven for (const_iterator __i = __c.begin(), __e = __c.end(); __i != __e; ++__i) 1191227825Stheraven push_back(*__i); 1192227825Stheraven} 1193227825Stheraven 1194227825Stheraven#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 1195227825Stheraven 1196227825Stheraventemplate <class _Tp, class _Alloc> 1197227825Stheravenlist<_Tp, _Alloc>::list(initializer_list<value_type> __il, const allocator_type& __a) 1198227825Stheraven : base(__a) 1199227825Stheraven{ 1200227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 1201227825Stheraven __get_db()->__insert_c(this); 1202227825Stheraven#endif 1203227825Stheraven for (typename initializer_list<value_type>::const_iterator __i = __il.begin(), 1204227825Stheraven __e = __il.end(); __i != __e; ++__i) 1205227825Stheraven push_back(*__i); 1206227825Stheraven} 1207227825Stheraven 1208227825Stheraventemplate <class _Tp, class _Alloc> 1209227825Stheravenlist<_Tp, _Alloc>::list(initializer_list<value_type> __il) 1210227825Stheraven{ 1211227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 1212227825Stheraven __get_db()->__insert_c(this); 1213227825Stheraven#endif 1214227825Stheraven for (typename initializer_list<value_type>::const_iterator __i = __il.begin(), 1215227825Stheraven __e = __il.end(); __i != __e; ++__i) 1216227825Stheraven push_back(*__i); 1217227825Stheraven} 1218227825Stheraven 1219227825Stheraven#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 1220227825Stheraven 1221227825Stheraventemplate <class _Tp, class _Alloc> 1222227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 1223227825Stheravenlist<_Tp, _Alloc>& 1224227825Stheravenlist<_Tp, _Alloc>::operator=(const list& __c) 1225227825Stheraven{ 1226227825Stheraven if (this != &__c) 1227227825Stheraven { 1228227825Stheraven base::__copy_assign_alloc(__c); 1229227825Stheraven assign(__c.begin(), __c.end()); 1230227825Stheraven } 1231227825Stheraven return *this; 1232227825Stheraven} 1233227825Stheraven 1234227825Stheraven#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 1235227825Stheraven 1236227825Stheraventemplate <class _Tp, class _Alloc> 1237227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 1238227825Stheravenlist<_Tp, _Alloc>::list(list&& __c) 1239227825Stheraven _NOEXCEPT_(is_nothrow_move_constructible<__node_allocator>::value) 1240227825Stheraven : base(allocator_type(_VSTD::move(__c.__node_alloc()))) 1241227825Stheraven{ 1242227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 1243227825Stheraven __get_db()->__insert_c(this); 1244227825Stheraven#endif 1245227825Stheraven splice(end(), __c); 1246227825Stheraven} 1247227825Stheraven 1248227825Stheraventemplate <class _Tp, class _Alloc> 1249227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 1250227825Stheravenlist<_Tp, _Alloc>::list(list&& __c, const allocator_type& __a) 1251227825Stheraven : base(__a) 1252227825Stheraven{ 1253227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 1254227825Stheraven __get_db()->__insert_c(this); 1255227825Stheraven#endif 1256227825Stheraven if (__a == __c.get_allocator()) 1257227825Stheraven splice(end(), __c); 1258227825Stheraven else 1259227825Stheraven { 1260232924Stheraven typedef move_iterator<iterator> _Ip; 1261232924Stheraven assign(_Ip(__c.begin()), _Ip(__c.end())); 1262227825Stheraven } 1263227825Stheraven} 1264227825Stheraven 1265227825Stheraventemplate <class _Tp, class _Alloc> 1266227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 1267227825Stheravenlist<_Tp, _Alloc>& 1268227825Stheravenlist<_Tp, _Alloc>::operator=(list&& __c) 1269227825Stheraven _NOEXCEPT_( 1270227825Stheraven __node_alloc_traits::propagate_on_container_move_assignment::value && 1271227825Stheraven is_nothrow_move_assignable<__node_allocator>::value) 1272227825Stheraven{ 1273227825Stheraven __move_assign(__c, integral_constant<bool, 1274227825Stheraven __node_alloc_traits::propagate_on_container_move_assignment::value>()); 1275227825Stheraven return *this; 1276227825Stheraven} 1277227825Stheraven 1278227825Stheraventemplate <class _Tp, class _Alloc> 1279227825Stheravenvoid 1280227825Stheravenlist<_Tp, _Alloc>::__move_assign(list& __c, false_type) 1281227825Stheraven{ 1282227825Stheraven if (base::__node_alloc() != __c.__node_alloc()) 1283227825Stheraven { 1284232924Stheraven typedef move_iterator<iterator> _Ip; 1285232924Stheraven assign(_Ip(__c.begin()), _Ip(__c.end())); 1286227825Stheraven } 1287227825Stheraven else 1288227825Stheraven __move_assign(__c, true_type()); 1289227825Stheraven} 1290227825Stheraven 1291227825Stheraventemplate <class _Tp, class _Alloc> 1292227825Stheravenvoid 1293227825Stheravenlist<_Tp, _Alloc>::__move_assign(list& __c, true_type) 1294227825Stheraven _NOEXCEPT_(is_nothrow_move_assignable<__node_allocator>::value) 1295227825Stheraven{ 1296227825Stheraven clear(); 1297227825Stheraven base::__move_assign_alloc(__c); 1298227825Stheraven splice(end(), __c); 1299227825Stheraven} 1300227825Stheraven 1301227825Stheraven#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 1302227825Stheraven 1303227825Stheraventemplate <class _Tp, class _Alloc> 1304227825Stheraventemplate <class _InpIter> 1305227825Stheravenvoid 1306227825Stheravenlist<_Tp, _Alloc>::assign(_InpIter __f, _InpIter __l, 1307227825Stheraven typename enable_if<__is_input_iterator<_InpIter>::value>::type*) 1308227825Stheraven{ 1309227825Stheraven iterator __i = begin(); 1310227825Stheraven iterator __e = end(); 1311227825Stheraven for (; __f != __l && __i != __e; ++__f, ++__i) 1312227825Stheraven *__i = *__f; 1313227825Stheraven if (__i == __e) 1314227825Stheraven insert(__e, __f, __l); 1315227825Stheraven else 1316227825Stheraven erase(__i, __e); 1317227825Stheraven} 1318227825Stheraven 1319227825Stheraventemplate <class _Tp, class _Alloc> 1320227825Stheravenvoid 1321227825Stheravenlist<_Tp, _Alloc>::assign(size_type __n, const value_type& __x) 1322227825Stheraven{ 1323227825Stheraven iterator __i = begin(); 1324227825Stheraven iterator __e = end(); 1325227825Stheraven for (; __n > 0 && __i != __e; --__n, ++__i) 1326227825Stheraven *__i = __x; 1327227825Stheraven if (__i == __e) 1328227825Stheraven insert(__e, __n, __x); 1329227825Stheraven else 1330227825Stheraven erase(__i, __e); 1331227825Stheraven} 1332227825Stheraven 1333227825Stheraventemplate <class _Tp, class _Alloc> 1334227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 1335227825Stheraven_Alloc 1336227825Stheravenlist<_Tp, _Alloc>::get_allocator() const _NOEXCEPT 1337227825Stheraven{ 1338227825Stheraven return allocator_type(base::__node_alloc()); 1339227825Stheraven} 1340227825Stheraven 1341227825Stheraventemplate <class _Tp, class _Alloc> 1342227825Stheraventypename list<_Tp, _Alloc>::iterator 1343227825Stheravenlist<_Tp, _Alloc>::insert(const_iterator __p, const value_type& __x) 1344227825Stheraven{ 1345227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 1346227825Stheraven _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__p) == this, 1347227825Stheraven "list::insert(iterator, x) called with an iterator not" 1348227825Stheraven " referring to this list"); 1349227825Stheraven#endif 1350227825Stheraven __node_allocator& __na = base::__node_alloc(); 1351232924Stheraven typedef __allocator_destructor<__node_allocator> _Dp; 1352232924Stheraven unique_ptr<__node, _Dp> __hold(__node_alloc_traits::allocate(__na, 1), _Dp(__na, 1)); 1353227825Stheraven __hold->__prev_ = 0; 1354227825Stheraven __node_alloc_traits::construct(__na, _VSTD::addressof(__hold->__value_), __x); 1355253146Stheraven __link_nodes(__p.__ptr_, __hold.get(), __hold.get()); 1356227825Stheraven ++base::__sz(); 1357249989Sdim#if _LIBCPP_DEBUG_LEVEL >= 2 1358249989Sdim return iterator(__hold.release(), this); 1359249989Sdim#else 1360227825Stheraven return iterator(__hold.release()); 1361249989Sdim#endif 1362227825Stheraven} 1363227825Stheraven 1364227825Stheraventemplate <class _Tp, class _Alloc> 1365227825Stheraventypename list<_Tp, _Alloc>::iterator 1366227825Stheravenlist<_Tp, _Alloc>::insert(const_iterator __p, size_type __n, const value_type& __x) 1367227825Stheraven{ 1368227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 1369227825Stheraven _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__p) == this, 1370227825Stheraven "list::insert(iterator, n, x) called with an iterator not" 1371227825Stheraven " referring to this list"); 1372253146Stheraven iterator __r(__p.__ptr_, this); 1373227825Stheraven#else 1374253146Stheraven iterator __r(__p.__ptr_); 1375227825Stheraven#endif 1376227825Stheraven if (__n > 0) 1377227825Stheraven { 1378227825Stheraven size_type __ds = 0; 1379227825Stheraven __node_allocator& __na = base::__node_alloc(); 1380232924Stheraven typedef __allocator_destructor<__node_allocator> _Dp; 1381232924Stheraven unique_ptr<__node, _Dp> __hold(__node_alloc_traits::allocate(__na, 1), _Dp(__na, 1)); 1382227825Stheraven __hold->__prev_ = 0; 1383227825Stheraven __node_alloc_traits::construct(__na, _VSTD::addressof(__hold->__value_), __x); 1384227825Stheraven ++__ds; 1385227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 1386227825Stheraven __r = iterator(__hold.get(), this); 1387227825Stheraven#else 1388227825Stheraven __r = iterator(__hold.get()); 1389227825Stheraven#endif 1390227825Stheraven __hold.release(); 1391227825Stheraven iterator __e = __r; 1392227825Stheraven#ifndef _LIBCPP_NO_EXCEPTIONS 1393227825Stheraven try 1394227825Stheraven { 1395227825Stheraven#endif // _LIBCPP_NO_EXCEPTIONS 1396227825Stheraven for (--__n; __n != 0; --__n, ++__e, ++__ds) 1397227825Stheraven { 1398227825Stheraven __hold.reset(__node_alloc_traits::allocate(__na, 1)); 1399227825Stheraven __node_alloc_traits::construct(__na, _VSTD::addressof(__hold->__value_), __x); 1400227825Stheraven __e.__ptr_->__next_ = __hold.get(); 1401227825Stheraven __hold->__prev_ = __e.__ptr_; 1402227825Stheraven __hold.release(); 1403227825Stheraven } 1404227825Stheraven#ifndef _LIBCPP_NO_EXCEPTIONS 1405227825Stheraven } 1406227825Stheraven catch (...) 1407227825Stheraven { 1408227825Stheraven while (true) 1409227825Stheraven { 1410227825Stheraven __node_alloc_traits::destroy(__na, _VSTD::addressof(*__e)); 1411227825Stheraven __node_pointer __prev = __e.__ptr_->__prev_; 1412227825Stheraven __node_alloc_traits::deallocate(__na, __e.__ptr_, 1); 1413227825Stheraven if (__prev == 0) 1414227825Stheraven break; 1415227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 1416227825Stheraven __e = iterator(__prev, this); 1417227825Stheraven#else 1418227825Stheraven __e = iterator(__prev); 1419227825Stheraven#endif 1420227825Stheraven } 1421227825Stheraven throw; 1422227825Stheraven } 1423227825Stheraven#endif // _LIBCPP_NO_EXCEPTIONS 1424253146Stheraven __link_nodes(__p.__ptr_, __r.__ptr_, __e.__ptr_); 1425227825Stheraven base::__sz() += __ds; 1426227825Stheraven } 1427227825Stheraven return __r; 1428227825Stheraven} 1429227825Stheraven 1430227825Stheraventemplate <class _Tp, class _Alloc> 1431227825Stheraventemplate <class _InpIter> 1432227825Stheraventypename list<_Tp, _Alloc>::iterator 1433227825Stheravenlist<_Tp, _Alloc>::insert(const_iterator __p, _InpIter __f, _InpIter __l, 1434227825Stheraven typename enable_if<__is_input_iterator<_InpIter>::value>::type*) 1435227825Stheraven{ 1436227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 1437227825Stheraven _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__p) == this, 1438227825Stheraven "list::insert(iterator, range) called with an iterator not" 1439227825Stheraven " referring to this list"); 1440253146Stheraven iterator __r(__p.__ptr_, this); 1441227825Stheraven#else 1442253146Stheraven iterator __r(__p.__ptr_); 1443227825Stheraven#endif 1444227825Stheraven if (__f != __l) 1445227825Stheraven { 1446227825Stheraven size_type __ds = 0; 1447227825Stheraven __node_allocator& __na = base::__node_alloc(); 1448232924Stheraven typedef __allocator_destructor<__node_allocator> _Dp; 1449232924Stheraven unique_ptr<__node, _Dp> __hold(__node_alloc_traits::allocate(__na, 1), _Dp(__na, 1)); 1450227825Stheraven __hold->__prev_ = 0; 1451227825Stheraven __node_alloc_traits::construct(__na, _VSTD::addressof(__hold->__value_), *__f); 1452227825Stheraven ++__ds; 1453227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 1454227825Stheraven __r = iterator(__hold.get(), this); 1455227825Stheraven#else 1456227825Stheraven __r = iterator(__hold.get()); 1457227825Stheraven#endif 1458227825Stheraven __hold.release(); 1459227825Stheraven iterator __e = __r; 1460227825Stheraven#ifndef _LIBCPP_NO_EXCEPTIONS 1461227825Stheraven try 1462227825Stheraven { 1463227825Stheraven#endif // _LIBCPP_NO_EXCEPTIONS 1464288943Sdim for (++__f; __f != __l; ++__f, (void) ++__e, (void) ++__ds) 1465227825Stheraven { 1466227825Stheraven __hold.reset(__node_alloc_traits::allocate(__na, 1)); 1467227825Stheraven __node_alloc_traits::construct(__na, _VSTD::addressof(__hold->__value_), *__f); 1468227825Stheraven __e.__ptr_->__next_ = __hold.get(); 1469227825Stheraven __hold->__prev_ = __e.__ptr_; 1470227825Stheraven __hold.release(); 1471227825Stheraven } 1472227825Stheraven#ifndef _LIBCPP_NO_EXCEPTIONS 1473227825Stheraven } 1474227825Stheraven catch (...) 1475227825Stheraven { 1476227825Stheraven while (true) 1477227825Stheraven { 1478227825Stheraven __node_alloc_traits::destroy(__na, _VSTD::addressof(*__e)); 1479227825Stheraven __node_pointer __prev = __e.__ptr_->__prev_; 1480227825Stheraven __node_alloc_traits::deallocate(__na, __e.__ptr_, 1); 1481227825Stheraven if (__prev == 0) 1482227825Stheraven break; 1483227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 1484227825Stheraven __e = iterator(__prev, this); 1485227825Stheraven#else 1486227825Stheraven __e = iterator(__prev); 1487227825Stheraven#endif 1488227825Stheraven } 1489227825Stheraven throw; 1490227825Stheraven } 1491227825Stheraven#endif // _LIBCPP_NO_EXCEPTIONS 1492253146Stheraven __link_nodes(__p.__ptr_, __r.__ptr_, __e.__ptr_); 1493227825Stheraven base::__sz() += __ds; 1494227825Stheraven } 1495227825Stheraven return __r; 1496227825Stheraven} 1497227825Stheraven 1498227825Stheraventemplate <class _Tp, class _Alloc> 1499227825Stheravenvoid 1500227825Stheravenlist<_Tp, _Alloc>::push_front(const value_type& __x) 1501227825Stheraven{ 1502227825Stheraven __node_allocator& __na = base::__node_alloc(); 1503232924Stheraven typedef __allocator_destructor<__node_allocator> _Dp; 1504232924Stheraven unique_ptr<__node, _Dp> __hold(__node_alloc_traits::allocate(__na, 1), _Dp(__na, 1)); 1505227825Stheraven __node_alloc_traits::construct(__na, _VSTD::addressof(__hold->__value_), __x); 1506276792Sdim __link_nodes_at_front(__hold.get(), __hold.get()); 1507227825Stheraven ++base::__sz(); 1508227825Stheraven __hold.release(); 1509227825Stheraven} 1510227825Stheraven 1511227825Stheraventemplate <class _Tp, class _Alloc> 1512227825Stheravenvoid 1513227825Stheravenlist<_Tp, _Alloc>::push_back(const value_type& __x) 1514227825Stheraven{ 1515227825Stheraven __node_allocator& __na = base::__node_alloc(); 1516232924Stheraven typedef __allocator_destructor<__node_allocator> _Dp; 1517232924Stheraven unique_ptr<__node, _Dp> __hold(__node_alloc_traits::allocate(__na, 1), _Dp(__na, 1)); 1518227825Stheraven __node_alloc_traits::construct(__na, _VSTD::addressof(__hold->__value_), __x); 1519276792Sdim __link_nodes_at_back(__hold.get(), __hold.get()); 1520227825Stheraven ++base::__sz(); 1521227825Stheraven __hold.release(); 1522227825Stheraven} 1523227825Stheraven 1524227825Stheraven#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 1525227825Stheraven 1526227825Stheraventemplate <class _Tp, class _Alloc> 1527227825Stheravenvoid 1528227825Stheravenlist<_Tp, _Alloc>::push_front(value_type&& __x) 1529227825Stheraven{ 1530227825Stheraven __node_allocator& __na = base::__node_alloc(); 1531232924Stheraven typedef __allocator_destructor<__node_allocator> _Dp; 1532232924Stheraven unique_ptr<__node, _Dp> __hold(__node_alloc_traits::allocate(__na, 1), _Dp(__na, 1)); 1533227825Stheraven __node_alloc_traits::construct(__na, _VSTD::addressof(__hold->__value_), _VSTD::move(__x)); 1534276792Sdim __link_nodes_at_front(__hold.get(), __hold.get()); 1535227825Stheraven ++base::__sz(); 1536227825Stheraven __hold.release(); 1537227825Stheraven} 1538227825Stheraven 1539227825Stheraventemplate <class _Tp, class _Alloc> 1540227825Stheravenvoid 1541227825Stheravenlist<_Tp, _Alloc>::push_back(value_type&& __x) 1542227825Stheraven{ 1543227825Stheraven __node_allocator& __na = base::__node_alloc(); 1544232924Stheraven typedef __allocator_destructor<__node_allocator> _Dp; 1545232924Stheraven unique_ptr<__node, _Dp> __hold(__node_alloc_traits::allocate(__na, 1), _Dp(__na, 1)); 1546227825Stheraven __node_alloc_traits::construct(__na, _VSTD::addressof(__hold->__value_), _VSTD::move(__x)); 1547276792Sdim __link_nodes_at_back(__hold.get(), __hold.get()); 1548227825Stheraven ++base::__sz(); 1549227825Stheraven __hold.release(); 1550227825Stheraven} 1551227825Stheraven 1552227825Stheraven#ifndef _LIBCPP_HAS_NO_VARIADICS 1553227825Stheraven 1554227825Stheraventemplate <class _Tp, class _Alloc> 1555227825Stheraventemplate <class... _Args> 1556227825Stheravenvoid 1557227825Stheravenlist<_Tp, _Alloc>::emplace_front(_Args&&... __args) 1558227825Stheraven{ 1559227825Stheraven __node_allocator& __na = base::__node_alloc(); 1560232924Stheraven typedef __allocator_destructor<__node_allocator> _Dp; 1561232924Stheraven unique_ptr<__node, _Dp> __hold(__node_alloc_traits::allocate(__na, 1), _Dp(__na, 1)); 1562227825Stheraven __node_alloc_traits::construct(__na, _VSTD::addressof(__hold->__value_), _VSTD::forward<_Args>(__args)...); 1563276792Sdim __link_nodes_at_front(__hold.get(), __hold.get()); 1564227825Stheraven ++base::__sz(); 1565227825Stheraven __hold.release(); 1566227825Stheraven} 1567227825Stheraven 1568227825Stheraventemplate <class _Tp, class _Alloc> 1569227825Stheraventemplate <class... _Args> 1570227825Stheravenvoid 1571227825Stheravenlist<_Tp, _Alloc>::emplace_back(_Args&&... __args) 1572227825Stheraven{ 1573227825Stheraven __node_allocator& __na = base::__node_alloc(); 1574232924Stheraven typedef __allocator_destructor<__node_allocator> _Dp; 1575232924Stheraven unique_ptr<__node, _Dp> __hold(__node_alloc_traits::allocate(__na, 1), _Dp(__na, 1)); 1576227825Stheraven __node_alloc_traits::construct(__na, _VSTD::addressof(__hold->__value_), _VSTD::forward<_Args>(__args)...); 1577276792Sdim __link_nodes_at_back(__hold.get(), __hold.get()); 1578227825Stheraven ++base::__sz(); 1579227825Stheraven __hold.release(); 1580227825Stheraven} 1581227825Stheraven 1582227825Stheraventemplate <class _Tp, class _Alloc> 1583227825Stheraventemplate <class... _Args> 1584227825Stheraventypename list<_Tp, _Alloc>::iterator 1585227825Stheravenlist<_Tp, _Alloc>::emplace(const_iterator __p, _Args&&... __args) 1586227825Stheraven{ 1587249989Sdim#if _LIBCPP_DEBUG_LEVEL >= 2 1588249989Sdim _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__p) == this, 1589249989Sdim "list::emplace(iterator, args...) called with an iterator not" 1590249989Sdim " referring to this list"); 1591249989Sdim#endif 1592227825Stheraven __node_allocator& __na = base::__node_alloc(); 1593232924Stheraven typedef __allocator_destructor<__node_allocator> _Dp; 1594232924Stheraven unique_ptr<__node, _Dp> __hold(__node_alloc_traits::allocate(__na, 1), _Dp(__na, 1)); 1595227825Stheraven __hold->__prev_ = 0; 1596227825Stheraven __node_alloc_traits::construct(__na, _VSTD::addressof(__hold->__value_), _VSTD::forward<_Args>(__args)...); 1597253146Stheraven __link_nodes(__p.__ptr_, __hold.get(), __hold.get()); 1598227825Stheraven ++base::__sz(); 1599227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 1600227825Stheraven return iterator(__hold.release(), this); 1601227825Stheraven#else 1602227825Stheraven return iterator(__hold.release()); 1603227825Stheraven#endif 1604227825Stheraven} 1605227825Stheraven 1606227825Stheraven#endif // _LIBCPP_HAS_NO_VARIADICS 1607227825Stheraven 1608227825Stheraventemplate <class _Tp, class _Alloc> 1609227825Stheraventypename list<_Tp, _Alloc>::iterator 1610227825Stheravenlist<_Tp, _Alloc>::insert(const_iterator __p, value_type&& __x) 1611227825Stheraven{ 1612227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 1613227825Stheraven _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__p) == this, 1614227825Stheraven "list::insert(iterator, x) called with an iterator not" 1615227825Stheraven " referring to this list"); 1616227825Stheraven#endif 1617227825Stheraven __node_allocator& __na = base::__node_alloc(); 1618232924Stheraven typedef __allocator_destructor<__node_allocator> _Dp; 1619232924Stheraven unique_ptr<__node, _Dp> __hold(__node_alloc_traits::allocate(__na, 1), _Dp(__na, 1)); 1620227825Stheraven __hold->__prev_ = 0; 1621227825Stheraven __node_alloc_traits::construct(__na, _VSTD::addressof(__hold->__value_), _VSTD::move(__x)); 1622253146Stheraven __link_nodes(__p.__ptr_, __hold.get(), __hold.get()); 1623227825Stheraven ++base::__sz(); 1624227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 1625227825Stheraven return iterator(__hold.release(), this); 1626227825Stheraven#else 1627227825Stheraven return iterator(__hold.release()); 1628227825Stheraven#endif 1629227825Stheraven} 1630227825Stheraven 1631227825Stheraven#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 1632227825Stheraven 1633227825Stheraventemplate <class _Tp, class _Alloc> 1634227825Stheravenvoid 1635227825Stheravenlist<_Tp, _Alloc>::pop_front() 1636227825Stheraven{ 1637227825Stheraven _LIBCPP_ASSERT(!empty(), "list::pop_front() called with empty list"); 1638227825Stheraven __node_allocator& __na = base::__node_alloc(); 1639253146Stheraven __node_pointer __n = base::__end_.__next_; 1640227825Stheraven base::__unlink_nodes(__n, __n); 1641227825Stheraven --base::__sz(); 1642227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 1643227825Stheraven __c_node* __c = __get_db()->__find_c_and_lock(this); 1644227825Stheraven for (__i_node** __p = __c->end_; __p != __c->beg_; ) 1645227825Stheraven { 1646227825Stheraven --__p; 1647227825Stheraven iterator* __i = static_cast<iterator*>((*__p)->__i_); 1648253146Stheraven if (__i->__ptr_ == __n) 1649227825Stheraven { 1650227825Stheraven (*__p)->__c_ = nullptr; 1651227825Stheraven if (--__c->end_ != __p) 1652227825Stheraven memmove(__p, __p+1, (__c->end_ - __p)*sizeof(__i_node*)); 1653227825Stheraven } 1654227825Stheraven } 1655227825Stheraven __get_db()->unlock(); 1656227825Stheraven#endif 1657253146Stheraven __node_alloc_traits::destroy(__na, _VSTD::addressof(__n->__value_)); 1658253146Stheraven __node_alloc_traits::deallocate(__na, __n, 1); 1659227825Stheraven} 1660227825Stheraven 1661227825Stheraventemplate <class _Tp, class _Alloc> 1662227825Stheravenvoid 1663227825Stheravenlist<_Tp, _Alloc>::pop_back() 1664227825Stheraven{ 1665253146Stheraven _LIBCPP_ASSERT(!empty(), "list::pop_back() called with empty list"); 1666227825Stheraven __node_allocator& __na = base::__node_alloc(); 1667253146Stheraven __node_pointer __n = base::__end_.__prev_; 1668227825Stheraven base::__unlink_nodes(__n, __n); 1669227825Stheraven --base::__sz(); 1670227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 1671227825Stheraven __c_node* __c = __get_db()->__find_c_and_lock(this); 1672227825Stheraven for (__i_node** __p = __c->end_; __p != __c->beg_; ) 1673227825Stheraven { 1674227825Stheraven --__p; 1675227825Stheraven iterator* __i = static_cast<iterator*>((*__p)->__i_); 1676253146Stheraven if (__i->__ptr_ == __n) 1677227825Stheraven { 1678227825Stheraven (*__p)->__c_ = nullptr; 1679227825Stheraven if (--__c->end_ != __p) 1680227825Stheraven memmove(__p, __p+1, (__c->end_ - __p)*sizeof(__i_node*)); 1681227825Stheraven } 1682227825Stheraven } 1683227825Stheraven __get_db()->unlock(); 1684227825Stheraven#endif 1685253146Stheraven __node_alloc_traits::destroy(__na, _VSTD::addressof(__n->__value_)); 1686253146Stheraven __node_alloc_traits::deallocate(__na, __n, 1); 1687227825Stheraven} 1688227825Stheraven 1689227825Stheraventemplate <class _Tp, class _Alloc> 1690227825Stheraventypename list<_Tp, _Alloc>::iterator 1691227825Stheravenlist<_Tp, _Alloc>::erase(const_iterator __p) 1692227825Stheraven{ 1693227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 1694227825Stheraven _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__p) == this, 1695227825Stheraven "list::erase(iterator) called with an iterator not" 1696227825Stheraven " referring to this list"); 1697227825Stheraven#endif 1698249989Sdim _LIBCPP_ASSERT(__p != end(), 1699249989Sdim "list::erase(iterator) called with a non-dereferenceable iterator"); 1700227825Stheraven __node_allocator& __na = base::__node_alloc(); 1701253146Stheraven __node_pointer __n = __p.__ptr_; 1702253146Stheraven __node_pointer __r = __n->__next_; 1703227825Stheraven base::__unlink_nodes(__n, __n); 1704227825Stheraven --base::__sz(); 1705227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 1706227825Stheraven __c_node* __c = __get_db()->__find_c_and_lock(this); 1707227825Stheraven for (__i_node** __p = __c->end_; __p != __c->beg_; ) 1708227825Stheraven { 1709227825Stheraven --__p; 1710227825Stheraven iterator* __i = static_cast<iterator*>((*__p)->__i_); 1711253146Stheraven if (__i->__ptr_ == __n) 1712227825Stheraven { 1713227825Stheraven (*__p)->__c_ = nullptr; 1714227825Stheraven if (--__c->end_ != __p) 1715227825Stheraven memmove(__p, __p+1, (__c->end_ - __p)*sizeof(__i_node*)); 1716227825Stheraven } 1717227825Stheraven } 1718227825Stheraven __get_db()->unlock(); 1719227825Stheraven#endif 1720253146Stheraven __node_alloc_traits::destroy(__na, _VSTD::addressof(__n->__value_)); 1721253146Stheraven __node_alloc_traits::deallocate(__na, __n, 1); 1722227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 1723227825Stheraven return iterator(__r, this); 1724227825Stheraven#else 1725227825Stheraven return iterator(__r); 1726227825Stheraven#endif 1727227825Stheraven} 1728227825Stheraven 1729227825Stheraventemplate <class _Tp, class _Alloc> 1730227825Stheraventypename list<_Tp, _Alloc>::iterator 1731227825Stheravenlist<_Tp, _Alloc>::erase(const_iterator __f, const_iterator __l) 1732227825Stheraven{ 1733227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 1734227825Stheraven _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__f) == this, 1735227825Stheraven "list::erase(iterator, iterator) called with an iterator not" 1736227825Stheraven " referring to this list"); 1737227825Stheraven#endif 1738227825Stheraven if (__f != __l) 1739227825Stheraven { 1740227825Stheraven __node_allocator& __na = base::__node_alloc(); 1741253146Stheraven base::__unlink_nodes(__f.__ptr_, __l.__ptr_->__prev_); 1742227825Stheraven while (__f != __l) 1743227825Stheraven { 1744253146Stheraven __node_pointer __n = __f.__ptr_; 1745227825Stheraven ++__f; 1746227825Stheraven --base::__sz(); 1747227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 1748227825Stheraven __c_node* __c = __get_db()->__find_c_and_lock(this); 1749227825Stheraven for (__i_node** __p = __c->end_; __p != __c->beg_; ) 1750227825Stheraven { 1751227825Stheraven --__p; 1752227825Stheraven iterator* __i = static_cast<iterator*>((*__p)->__i_); 1753253146Stheraven if (__i->__ptr_ == __n) 1754227825Stheraven { 1755227825Stheraven (*__p)->__c_ = nullptr; 1756227825Stheraven if (--__c->end_ != __p) 1757227825Stheraven memmove(__p, __p+1, (__c->end_ - __p)*sizeof(__i_node*)); 1758227825Stheraven } 1759227825Stheraven } 1760227825Stheraven __get_db()->unlock(); 1761227825Stheraven#endif 1762253146Stheraven __node_alloc_traits::destroy(__na, _VSTD::addressof(__n->__value_)); 1763253146Stheraven __node_alloc_traits::deallocate(__na, __n, 1); 1764227825Stheraven } 1765227825Stheraven } 1766227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 1767253146Stheraven return iterator(__l.__ptr_, this); 1768227825Stheraven#else 1769253146Stheraven return iterator(__l.__ptr_); 1770227825Stheraven#endif 1771227825Stheraven} 1772227825Stheraven 1773227825Stheraventemplate <class _Tp, class _Alloc> 1774227825Stheravenvoid 1775227825Stheravenlist<_Tp, _Alloc>::resize(size_type __n) 1776227825Stheraven{ 1777227825Stheraven if (__n < base::__sz()) 1778227825Stheraven erase(__iterator(__n), end()); 1779227825Stheraven else if (__n > base::__sz()) 1780227825Stheraven { 1781227825Stheraven __n -= base::__sz(); 1782227825Stheraven size_type __ds = 0; 1783227825Stheraven __node_allocator& __na = base::__node_alloc(); 1784232924Stheraven typedef __allocator_destructor<__node_allocator> _Dp; 1785232924Stheraven unique_ptr<__node, _Dp> __hold(__node_alloc_traits::allocate(__na, 1), _Dp(__na, 1)); 1786227825Stheraven __hold->__prev_ = 0; 1787227825Stheraven __node_alloc_traits::construct(__na, _VSTD::addressof(__hold->__value_)); 1788227825Stheraven ++__ds; 1789227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 1790227825Stheraven iterator __r = iterator(__hold.release(), this); 1791227825Stheraven#else 1792227825Stheraven iterator __r = iterator(__hold.release()); 1793227825Stheraven#endif 1794227825Stheraven iterator __e = __r; 1795227825Stheraven#ifndef _LIBCPP_NO_EXCEPTIONS 1796227825Stheraven try 1797227825Stheraven { 1798227825Stheraven#endif // _LIBCPP_NO_EXCEPTIONS 1799227825Stheraven for (--__n; __n != 0; --__n, ++__e, ++__ds) 1800227825Stheraven { 1801227825Stheraven __hold.reset(__node_alloc_traits::allocate(__na, 1)); 1802227825Stheraven __node_alloc_traits::construct(__na, _VSTD::addressof(__hold->__value_)); 1803227825Stheraven __e.__ptr_->__next_ = __hold.get(); 1804227825Stheraven __hold->__prev_ = __e.__ptr_; 1805227825Stheraven __hold.release(); 1806227825Stheraven } 1807227825Stheraven#ifndef _LIBCPP_NO_EXCEPTIONS 1808227825Stheraven } 1809227825Stheraven catch (...) 1810227825Stheraven { 1811227825Stheraven while (true) 1812227825Stheraven { 1813227825Stheraven __node_alloc_traits::destroy(__na, _VSTD::addressof(*__e)); 1814227825Stheraven __node_pointer __prev = __e.__ptr_->__prev_; 1815227825Stheraven __node_alloc_traits::deallocate(__na, __e.__ptr_, 1); 1816227825Stheraven if (__prev == 0) 1817227825Stheraven break; 1818227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 1819227825Stheraven __e = iterator(__prev, this); 1820227825Stheraven#else 1821227825Stheraven __e = iterator(__prev); 1822227825Stheraven#endif 1823227825Stheraven } 1824227825Stheraven throw; 1825227825Stheraven } 1826227825Stheraven#endif // _LIBCPP_NO_EXCEPTIONS 1827276792Sdim __link_nodes_at_back(__r.__ptr_, __e.__ptr_); 1828227825Stheraven base::__sz() += __ds; 1829227825Stheraven } 1830227825Stheraven} 1831227825Stheraven 1832227825Stheraventemplate <class _Tp, class _Alloc> 1833227825Stheravenvoid 1834227825Stheravenlist<_Tp, _Alloc>::resize(size_type __n, const value_type& __x) 1835227825Stheraven{ 1836227825Stheraven if (__n < base::__sz()) 1837227825Stheraven erase(__iterator(__n), end()); 1838227825Stheraven else if (__n > base::__sz()) 1839227825Stheraven { 1840227825Stheraven __n -= base::__sz(); 1841227825Stheraven size_type __ds = 0; 1842227825Stheraven __node_allocator& __na = base::__node_alloc(); 1843232924Stheraven typedef __allocator_destructor<__node_allocator> _Dp; 1844232924Stheraven unique_ptr<__node, _Dp> __hold(__node_alloc_traits::allocate(__na, 1), _Dp(__na, 1)); 1845227825Stheraven __hold->__prev_ = 0; 1846227825Stheraven __node_alloc_traits::construct(__na, _VSTD::addressof(__hold->__value_), __x); 1847227825Stheraven ++__ds; 1848227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 1849227825Stheraven iterator __r = iterator(__hold.release(), this); 1850227825Stheraven#else 1851227825Stheraven iterator __r = iterator(__hold.release()); 1852227825Stheraven#endif 1853227825Stheraven iterator __e = __r; 1854227825Stheraven#ifndef _LIBCPP_NO_EXCEPTIONS 1855227825Stheraven try 1856227825Stheraven { 1857227825Stheraven#endif // _LIBCPP_NO_EXCEPTIONS 1858227825Stheraven for (--__n; __n != 0; --__n, ++__e, ++__ds) 1859227825Stheraven { 1860227825Stheraven __hold.reset(__node_alloc_traits::allocate(__na, 1)); 1861227825Stheraven __node_alloc_traits::construct(__na, _VSTD::addressof(__hold->__value_), __x); 1862227825Stheraven __e.__ptr_->__next_ = __hold.get(); 1863227825Stheraven __hold->__prev_ = __e.__ptr_; 1864227825Stheraven __hold.release(); 1865227825Stheraven } 1866227825Stheraven#ifndef _LIBCPP_NO_EXCEPTIONS 1867227825Stheraven } 1868227825Stheraven catch (...) 1869227825Stheraven { 1870227825Stheraven while (true) 1871227825Stheraven { 1872227825Stheraven __node_alloc_traits::destroy(__na, _VSTD::addressof(*__e)); 1873227825Stheraven __node_pointer __prev = __e.__ptr_->__prev_; 1874227825Stheraven __node_alloc_traits::deallocate(__na, __e.__ptr_, 1); 1875227825Stheraven if (__prev == 0) 1876227825Stheraven break; 1877227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 1878227825Stheraven __e = iterator(__prev, this); 1879227825Stheraven#else 1880227825Stheraven __e = iterator(__prev); 1881227825Stheraven#endif 1882227825Stheraven } 1883227825Stheraven throw; 1884227825Stheraven } 1885227825Stheraven#endif // _LIBCPP_NO_EXCEPTIONS 1886253146Stheraven __link_nodes(static_cast<__node_pointer>(pointer_traits<__node_base_pointer>:: 1887253146Stheraven pointer_to(base::__end_)), __r.__ptr_, __e.__ptr_); 1888227825Stheraven base::__sz() += __ds; 1889227825Stheraven } 1890227825Stheraven} 1891227825Stheraven 1892227825Stheraventemplate <class _Tp, class _Alloc> 1893227825Stheravenvoid 1894227825Stheravenlist<_Tp, _Alloc>::splice(const_iterator __p, list& __c) 1895227825Stheraven{ 1896227825Stheraven _LIBCPP_ASSERT(this != &__c, 1897227825Stheraven "list::splice(iterator, list) called with this == &list"); 1898227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 1899227825Stheraven _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__p) == this, 1900227825Stheraven "list::splice(iterator, list) called with an iterator not" 1901227825Stheraven " referring to this list"); 1902227825Stheraven#endif 1903227825Stheraven if (!__c.empty()) 1904227825Stheraven { 1905253146Stheraven __node_pointer __f = __c.__end_.__next_; 1906253146Stheraven __node_pointer __l = __c.__end_.__prev_; 1907227825Stheraven base::__unlink_nodes(__f, __l); 1908253146Stheraven __link_nodes(__p.__ptr_, __f, __l); 1909227825Stheraven base::__sz() += __c.__sz(); 1910227825Stheraven __c.__sz() = 0; 1911227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 1912227825Stheraven __libcpp_db* __db = __get_db(); 1913227825Stheraven __c_node* __cn1 = __db->__find_c_and_lock(this); 1914227825Stheraven __c_node* __cn2 = __db->__find_c(&__c); 1915227825Stheraven for (__i_node** __p = __cn2->end_; __p != __cn2->beg_;) 1916227825Stheraven { 1917227825Stheraven --__p; 1918227825Stheraven iterator* __i = static_cast<iterator*>((*__p)->__i_); 1919253146Stheraven if (__i->__ptr_ != static_cast<__node_pointer>( 1920253146Stheraven pointer_traits<__node_base_pointer>::pointer_to(__c.__end_))) 1921227825Stheraven { 1922227825Stheraven __cn1->__add(*__p); 1923227825Stheraven (*__p)->__c_ = __cn1; 1924227825Stheraven if (--__cn2->end_ != __p) 1925227825Stheraven memmove(__p, __p+1, (__cn2->end_ - __p)*sizeof(__i_node*)); 1926227825Stheraven } 1927227825Stheraven } 1928227825Stheraven __db->unlock(); 1929227825Stheraven#endif 1930227825Stheraven } 1931227825Stheraven} 1932227825Stheraven 1933227825Stheraventemplate <class _Tp, class _Alloc> 1934227825Stheravenvoid 1935227825Stheravenlist<_Tp, _Alloc>::splice(const_iterator __p, list& __c, const_iterator __i) 1936227825Stheraven{ 1937227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 1938227825Stheraven _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__p) == this, 1939227825Stheraven "list::splice(iterator, list, iterator) called with first iterator not" 1940227825Stheraven " referring to this list"); 1941227825Stheraven _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__i) == &__c, 1942227825Stheraven "list::splice(iterator, list, iterator) called with second iterator not" 1943227825Stheraven " referring to list argument"); 1944227825Stheraven _LIBCPP_ASSERT(__get_const_db()->__dereferenceable(&__i), 1945227825Stheraven "list::splice(iterator, list, iterator) called with second iterator not" 1946227825Stheraven " derefereceable"); 1947227825Stheraven#endif 1948227825Stheraven if (__p.__ptr_ != __i.__ptr_ && __p.__ptr_ != __i.__ptr_->__next_) 1949227825Stheraven { 1950253146Stheraven __node_pointer __f = __i.__ptr_; 1951227825Stheraven base::__unlink_nodes(__f, __f); 1952253146Stheraven __link_nodes(__p.__ptr_, __f, __f); 1953227825Stheraven --__c.__sz(); 1954227825Stheraven ++base::__sz(); 1955227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 1956227825Stheraven __libcpp_db* __db = __get_db(); 1957227825Stheraven __c_node* __cn1 = __db->__find_c_and_lock(this); 1958227825Stheraven __c_node* __cn2 = __db->__find_c(&__c); 1959227825Stheraven for (__i_node** __p = __cn2->end_; __p != __cn2->beg_;) 1960227825Stheraven { 1961227825Stheraven --__p; 1962227825Stheraven iterator* __j = static_cast<iterator*>((*__p)->__i_); 1963253146Stheraven if (__j->__ptr_ == __f) 1964227825Stheraven { 1965227825Stheraven __cn1->__add(*__p); 1966227825Stheraven (*__p)->__c_ = __cn1; 1967227825Stheraven if (--__cn2->end_ != __p) 1968227825Stheraven memmove(__p, __p+1, (__cn2->end_ - __p)*sizeof(__i_node*)); 1969227825Stheraven } 1970227825Stheraven } 1971227825Stheraven __db->unlock(); 1972227825Stheraven#endif 1973227825Stheraven } 1974227825Stheraven} 1975227825Stheraven 1976227825Stheraventemplate <class _Tp, class _Alloc> 1977227825Stheravenvoid 1978227825Stheravenlist<_Tp, _Alloc>::splice(const_iterator __p, list& __c, const_iterator __f, const_iterator __l) 1979227825Stheraven{ 1980227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 1981227825Stheraven _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__p) == this, 1982227825Stheraven "list::splice(iterator, list, iterator, iterator) called with first iterator not" 1983227825Stheraven " referring to this list"); 1984227825Stheraven _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__f) == &__c, 1985227825Stheraven "list::splice(iterator, list, iterator, iterator) called with second iterator not" 1986227825Stheraven " referring to list argument"); 1987227825Stheraven if (this == &__c) 1988227825Stheraven { 1989227825Stheraven for (const_iterator __i = __f; __i != __l; ++__i) 1990227825Stheraven _LIBCPP_ASSERT(__i != __p, 1991227825Stheraven "list::splice(iterator, list, iterator, iterator)" 1992227825Stheraven " called with the first iterator within the range" 1993227825Stheraven " of the second and third iterators"); 1994227825Stheraven } 1995227825Stheraven#endif 1996227825Stheraven if (__f != __l) 1997227825Stheraven { 1998227825Stheraven if (this != &__c) 1999227825Stheraven { 2000227825Stheraven size_type __s = _VSTD::distance(__f, __l); 2001227825Stheraven __c.__sz() -= __s; 2002227825Stheraven base::__sz() += __s; 2003227825Stheraven } 2004253146Stheraven __node_pointer __first = __f.__ptr_; 2005227825Stheraven --__l; 2006253146Stheraven __node_pointer __last = __l.__ptr_; 2007227825Stheraven base::__unlink_nodes(__first, __last); 2008253146Stheraven __link_nodes(__p.__ptr_, __first, __last); 2009227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 2010227825Stheraven __libcpp_db* __db = __get_db(); 2011227825Stheraven __c_node* __cn1 = __db->__find_c_and_lock(this); 2012227825Stheraven __c_node* __cn2 = __db->__find_c(&__c); 2013227825Stheraven for (__i_node** __p = __cn2->end_; __p != __cn2->beg_;) 2014227825Stheraven { 2015227825Stheraven --__p; 2016227825Stheraven iterator* __j = static_cast<iterator*>((*__p)->__i_); 2017253146Stheraven for (__node_pointer __k = __f.__ptr_; 2018227825Stheraven __k != __l.__ptr_; __k = __k->__next_) 2019227825Stheraven { 2020227825Stheraven if (__j->__ptr_ == __k) 2021227825Stheraven { 2022227825Stheraven __cn1->__add(*__p); 2023227825Stheraven (*__p)->__c_ = __cn1; 2024227825Stheraven if (--__cn2->end_ != __p) 2025227825Stheraven memmove(__p, __p+1, (__cn2->end_ - __p)*sizeof(__i_node*)); 2026227825Stheraven } 2027227825Stheraven } 2028227825Stheraven } 2029227825Stheraven __db->unlock(); 2030227825Stheraven#endif 2031227825Stheraven } 2032227825Stheraven} 2033227825Stheraven 2034227825Stheraventemplate <class _Tp, class _Alloc> 2035227825Stheravenvoid 2036227825Stheravenlist<_Tp, _Alloc>::remove(const value_type& __x) 2037227825Stheraven{ 2038276792Sdim list<_Tp, _Alloc> __deleted_nodes; // collect the nodes we're removing 2039276792Sdim for (const_iterator __i = begin(), __e = end(); __i != __e;) 2040227825Stheraven { 2041227825Stheraven if (*__i == __x) 2042227825Stheraven { 2043276792Sdim const_iterator __j = _VSTD::next(__i); 2044227825Stheraven for (; __j != __e && *__j == __x; ++__j) 2045227825Stheraven ; 2046276792Sdim __deleted_nodes.splice(__deleted_nodes.end(), *this, __i, __j); 2047276792Sdim __i = __j; 2048276792Sdim if (__i != __e) 2049276792Sdim ++__i; 2050227825Stheraven } 2051227825Stheraven else 2052227825Stheraven ++__i; 2053227825Stheraven } 2054227825Stheraven} 2055227825Stheraven 2056227825Stheraventemplate <class _Tp, class _Alloc> 2057227825Stheraventemplate <class _Pred> 2058227825Stheravenvoid 2059227825Stheravenlist<_Tp, _Alloc>::remove_if(_Pred __pred) 2060227825Stheraven{ 2061227825Stheraven for (iterator __i = begin(), __e = end(); __i != __e;) 2062227825Stheraven { 2063227825Stheraven if (__pred(*__i)) 2064227825Stheraven { 2065227825Stheraven iterator __j = _VSTD::next(__i); 2066227825Stheraven for (; __j != __e && __pred(*__j); ++__j) 2067227825Stheraven ; 2068227825Stheraven __i = erase(__i, __j); 2069276792Sdim if (__i != __e) 2070276792Sdim ++__i; 2071227825Stheraven } 2072227825Stheraven else 2073227825Stheraven ++__i; 2074227825Stheraven } 2075227825Stheraven} 2076227825Stheraven 2077227825Stheraventemplate <class _Tp, class _Alloc> 2078227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 2079227825Stheravenvoid 2080227825Stheravenlist<_Tp, _Alloc>::unique() 2081227825Stheraven{ 2082227825Stheraven unique(__equal_to<value_type>()); 2083227825Stheraven} 2084227825Stheraven 2085227825Stheraventemplate <class _Tp, class _Alloc> 2086227825Stheraventemplate <class _BinaryPred> 2087227825Stheravenvoid 2088227825Stheravenlist<_Tp, _Alloc>::unique(_BinaryPred __binary_pred) 2089227825Stheraven{ 2090227825Stheraven for (iterator __i = begin(), __e = end(); __i != __e;) 2091227825Stheraven { 2092227825Stheraven iterator __j = _VSTD::next(__i); 2093227825Stheraven for (; __j != __e && __binary_pred(*__i, *__j); ++__j) 2094227825Stheraven ; 2095227825Stheraven if (++__i != __j) 2096227825Stheraven __i = erase(__i, __j); 2097227825Stheraven } 2098227825Stheraven} 2099227825Stheraven 2100227825Stheraventemplate <class _Tp, class _Alloc> 2101227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 2102227825Stheravenvoid 2103227825Stheravenlist<_Tp, _Alloc>::merge(list& __c) 2104227825Stheraven{ 2105227825Stheraven merge(__c, __less<value_type>()); 2106227825Stheraven} 2107227825Stheraven 2108227825Stheraventemplate <class _Tp, class _Alloc> 2109227825Stheraventemplate <class _Comp> 2110227825Stheravenvoid 2111227825Stheravenlist<_Tp, _Alloc>::merge(list& __c, _Comp __comp) 2112227825Stheraven{ 2113227825Stheraven if (this != &__c) 2114227825Stheraven { 2115227825Stheraven iterator __f1 = begin(); 2116227825Stheraven iterator __e1 = end(); 2117227825Stheraven iterator __f2 = __c.begin(); 2118227825Stheraven iterator __e2 = __c.end(); 2119227825Stheraven while (__f1 != __e1 && __f2 != __e2) 2120227825Stheraven { 2121227825Stheraven if (__comp(*__f2, *__f1)) 2122227825Stheraven { 2123227825Stheraven size_type __ds = 1; 2124227825Stheraven iterator __m2 = _VSTD::next(__f2); 2125227825Stheraven for (; __m2 != __e2 && __comp(*__m2, *__f1); ++__m2, ++__ds) 2126227825Stheraven ; 2127227825Stheraven base::__sz() += __ds; 2128227825Stheraven __c.__sz() -= __ds; 2129253146Stheraven __node_pointer __f = __f2.__ptr_; 2130253146Stheraven __node_pointer __l = __m2.__ptr_->__prev_; 2131227825Stheraven __f2 = __m2; 2132227825Stheraven base::__unlink_nodes(__f, __l); 2133227825Stheraven __m2 = _VSTD::next(__f1); 2134253146Stheraven __link_nodes(__f1.__ptr_, __f, __l); 2135227825Stheraven __f1 = __m2; 2136227825Stheraven } 2137227825Stheraven else 2138227825Stheraven ++__f1; 2139227825Stheraven } 2140227825Stheraven splice(__e1, __c); 2141227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 2142227825Stheraven __libcpp_db* __db = __get_db(); 2143227825Stheraven __c_node* __cn1 = __db->__find_c_and_lock(this); 2144227825Stheraven __c_node* __cn2 = __db->__find_c(&__c); 2145227825Stheraven for (__i_node** __p = __cn2->end_; __p != __cn2->beg_;) 2146227825Stheraven { 2147227825Stheraven --__p; 2148227825Stheraven iterator* __i = static_cast<iterator*>((*__p)->__i_); 2149253146Stheraven if (__i->__ptr_ != static_cast<__node_pointer>( 2150253146Stheraven pointer_traits<__node_base_pointer>::pointer_to(__c.__end_))) 2151227825Stheraven { 2152227825Stheraven __cn1->__add(*__p); 2153227825Stheraven (*__p)->__c_ = __cn1; 2154227825Stheraven if (--__cn2->end_ != __p) 2155227825Stheraven memmove(__p, __p+1, (__cn2->end_ - __p)*sizeof(__i_node*)); 2156227825Stheraven } 2157227825Stheraven } 2158227825Stheraven __db->unlock(); 2159227825Stheraven#endif 2160227825Stheraven } 2161227825Stheraven} 2162227825Stheraven 2163227825Stheraventemplate <class _Tp, class _Alloc> 2164227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 2165227825Stheravenvoid 2166227825Stheravenlist<_Tp, _Alloc>::sort() 2167227825Stheraven{ 2168227825Stheraven sort(__less<value_type>()); 2169227825Stheraven} 2170227825Stheraven 2171227825Stheraventemplate <class _Tp, class _Alloc> 2172227825Stheraventemplate <class _Comp> 2173227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 2174227825Stheravenvoid 2175227825Stheravenlist<_Tp, _Alloc>::sort(_Comp __comp) 2176227825Stheraven{ 2177227825Stheraven __sort(begin(), end(), base::__sz(), __comp); 2178227825Stheraven} 2179227825Stheraven 2180227825Stheraventemplate <class _Tp, class _Alloc> 2181227825Stheraventemplate <class _Comp> 2182227825Stheraventypename list<_Tp, _Alloc>::iterator 2183227825Stheravenlist<_Tp, _Alloc>::__sort(iterator __f1, iterator __e2, size_type __n, _Comp& __comp) 2184227825Stheraven{ 2185227825Stheraven switch (__n) 2186227825Stheraven { 2187227825Stheraven case 0: 2188227825Stheraven case 1: 2189227825Stheraven return __f1; 2190227825Stheraven case 2: 2191227825Stheraven if (__comp(*--__e2, *__f1)) 2192227825Stheraven { 2193253146Stheraven __node_pointer __f = __e2.__ptr_; 2194227825Stheraven base::__unlink_nodes(__f, __f); 2195253146Stheraven __link_nodes(__f1.__ptr_, __f, __f); 2196227825Stheraven return __e2; 2197227825Stheraven } 2198227825Stheraven return __f1; 2199227825Stheraven } 2200227825Stheraven size_type __n2 = __n / 2; 2201227825Stheraven iterator __e1 = _VSTD::next(__f1, __n2); 2202227825Stheraven iterator __r = __f1 = __sort(__f1, __e1, __n2, __comp); 2203227825Stheraven iterator __f2 = __e1 = __sort(__e1, __e2, __n - __n2, __comp); 2204227825Stheraven if (__comp(*__f2, *__f1)) 2205227825Stheraven { 2206227825Stheraven iterator __m2 = _VSTD::next(__f2); 2207227825Stheraven for (; __m2 != __e2 && __comp(*__m2, *__f1); ++__m2) 2208227825Stheraven ; 2209253146Stheraven __node_pointer __f = __f2.__ptr_; 2210253146Stheraven __node_pointer __l = __m2.__ptr_->__prev_; 2211227825Stheraven __r = __f2; 2212227825Stheraven __e1 = __f2 = __m2; 2213227825Stheraven base::__unlink_nodes(__f, __l); 2214227825Stheraven __m2 = _VSTD::next(__f1); 2215253146Stheraven __link_nodes(__f1.__ptr_, __f, __l); 2216227825Stheraven __f1 = __m2; 2217227825Stheraven } 2218227825Stheraven else 2219227825Stheraven ++__f1; 2220227825Stheraven while (__f1 != __e1 && __f2 != __e2) 2221227825Stheraven { 2222227825Stheraven if (__comp(*__f2, *__f1)) 2223227825Stheraven { 2224227825Stheraven iterator __m2 = _VSTD::next(__f2); 2225227825Stheraven for (; __m2 != __e2 && __comp(*__m2, *__f1); ++__m2) 2226227825Stheraven ; 2227253146Stheraven __node_pointer __f = __f2.__ptr_; 2228253146Stheraven __node_pointer __l = __m2.__ptr_->__prev_; 2229227825Stheraven if (__e1 == __f2) 2230227825Stheraven __e1 = __m2; 2231227825Stheraven __f2 = __m2; 2232227825Stheraven base::__unlink_nodes(__f, __l); 2233227825Stheraven __m2 = _VSTD::next(__f1); 2234253146Stheraven __link_nodes(__f1.__ptr_, __f, __l); 2235227825Stheraven __f1 = __m2; 2236227825Stheraven } 2237227825Stheraven else 2238227825Stheraven ++__f1; 2239227825Stheraven } 2240227825Stheraven return __r; 2241227825Stheraven} 2242227825Stheraven 2243227825Stheraventemplate <class _Tp, class _Alloc> 2244227825Stheravenvoid 2245227825Stheravenlist<_Tp, _Alloc>::reverse() _NOEXCEPT 2246227825Stheraven{ 2247227825Stheraven if (base::__sz() > 1) 2248227825Stheraven { 2249227825Stheraven iterator __e = end(); 2250227825Stheraven for (iterator __i = begin(); __i.__ptr_ != __e.__ptr_;) 2251227825Stheraven { 2252227825Stheraven _VSTD::swap(__i.__ptr_->__prev_, __i.__ptr_->__next_); 2253227825Stheraven __i.__ptr_ = __i.__ptr_->__prev_; 2254227825Stheraven } 2255227825Stheraven _VSTD::swap(__e.__ptr_->__prev_, __e.__ptr_->__next_); 2256227825Stheraven } 2257227825Stheraven} 2258227825Stheraven 2259227825Stheraventemplate <class _Tp, class _Alloc> 2260227825Stheravenbool 2261227825Stheravenlist<_Tp, _Alloc>::__invariants() const 2262227825Stheraven{ 2263227825Stheraven return size() == _VSTD::distance(begin(), end()); 2264227825Stheraven} 2265227825Stheraven 2266227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 2267227825Stheraven 2268227825Stheraventemplate <class _Tp, class _Alloc> 2269227825Stheravenbool 2270227825Stheravenlist<_Tp, _Alloc>::__dereferenceable(const const_iterator* __i) const 2271227825Stheraven{ 2272253146Stheraven return __i->__ptr_ != static_cast<__node_pointer>( 2273253146Stheraven pointer_traits<__node_base_pointer>::pointer_to(const_cast<__node_base&>(this->__end_))); 2274227825Stheraven} 2275227825Stheraven 2276227825Stheraventemplate <class _Tp, class _Alloc> 2277227825Stheravenbool 2278227825Stheravenlist<_Tp, _Alloc>::__decrementable(const const_iterator* __i) const 2279227825Stheraven{ 2280227825Stheraven return !empty() && __i->__ptr_ != base::__end_.__next_; 2281227825Stheraven} 2282227825Stheraven 2283227825Stheraventemplate <class _Tp, class _Alloc> 2284227825Stheravenbool 2285227825Stheravenlist<_Tp, _Alloc>::__addable(const const_iterator* __i, ptrdiff_t __n) const 2286227825Stheraven{ 2287227825Stheraven return false; 2288227825Stheraven} 2289227825Stheraven 2290227825Stheraventemplate <class _Tp, class _Alloc> 2291227825Stheravenbool 2292227825Stheravenlist<_Tp, _Alloc>::__subscriptable(const const_iterator* __i, ptrdiff_t __n) const 2293227825Stheraven{ 2294227825Stheraven return false; 2295227825Stheraven} 2296227825Stheraven 2297227825Stheraven#endif // _LIBCPP_DEBUG_LEVEL >= 2 2298227825Stheraven 2299227825Stheraventemplate <class _Tp, class _Alloc> 2300227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 2301227825Stheravenbool 2302227825Stheravenoperator==(const list<_Tp, _Alloc>& __x, const list<_Tp, _Alloc>& __y) 2303227825Stheraven{ 2304227825Stheraven return __x.size() == __y.size() && _VSTD::equal(__x.begin(), __x.end(), __y.begin()); 2305227825Stheraven} 2306227825Stheraven 2307227825Stheraventemplate <class _Tp, class _Alloc> 2308227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 2309227825Stheravenbool 2310227825Stheravenoperator< (const list<_Tp, _Alloc>& __x, const list<_Tp, _Alloc>& __y) 2311227825Stheraven{ 2312227825Stheraven return _VSTD::lexicographical_compare(__x.begin(), __x.end(), __y.begin(), __y.end()); 2313227825Stheraven} 2314227825Stheraven 2315227825Stheraventemplate <class _Tp, class _Alloc> 2316227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 2317227825Stheravenbool 2318227825Stheravenoperator!=(const list<_Tp, _Alloc>& __x, const list<_Tp, _Alloc>& __y) 2319227825Stheraven{ 2320227825Stheraven return !(__x == __y); 2321227825Stheraven} 2322227825Stheraven 2323227825Stheraventemplate <class _Tp, class _Alloc> 2324227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 2325227825Stheravenbool 2326227825Stheravenoperator> (const list<_Tp, _Alloc>& __x, const list<_Tp, _Alloc>& __y) 2327227825Stheraven{ 2328227825Stheraven return __y < __x; 2329227825Stheraven} 2330227825Stheraven 2331227825Stheraventemplate <class _Tp, class _Alloc> 2332227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 2333227825Stheravenbool 2334227825Stheravenoperator>=(const list<_Tp, _Alloc>& __x, const list<_Tp, _Alloc>& __y) 2335227825Stheraven{ 2336227825Stheraven return !(__x < __y); 2337227825Stheraven} 2338227825Stheraven 2339227825Stheraventemplate <class _Tp, class _Alloc> 2340227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 2341227825Stheravenbool 2342227825Stheravenoperator<=(const list<_Tp, _Alloc>& __x, const list<_Tp, _Alloc>& __y) 2343227825Stheraven{ 2344227825Stheraven return !(__y < __x); 2345227825Stheraven} 2346227825Stheraven 2347227825Stheraventemplate <class _Tp, class _Alloc> 2348227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 2349227825Stheravenvoid 2350227825Stheravenswap(list<_Tp, _Alloc>& __x, list<_Tp, _Alloc>& __y) 2351227825Stheraven _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y))) 2352227825Stheraven{ 2353227825Stheraven __x.swap(__y); 2354227825Stheraven} 2355227825Stheraven 2356227825Stheraven_LIBCPP_END_NAMESPACE_STD 2357227825Stheraven 2358227825Stheraven#endif // _LIBCPP_LIST 2359