list revision 249998
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); 43227825Stheraven list(size_type n, const value_type& value); 44227825Stheraven list(size_type n, const value_type& value, const allocator_type& a); 45227825Stheraven template <class Iter> 46227825Stheraven list(Iter first, Iter last); 47227825Stheraven template <class Iter> 48227825Stheraven list(Iter first, Iter last, const allocator_type& a); 49227825Stheraven list(const list& x); 50227825Stheraven list(const list&, const allocator_type& a); 51227825Stheraven list(list&& x) 52227825Stheraven noexcept(is_nothrow_move_constructible<allocator_type>::value); 53227825Stheraven list(list&&, const allocator_type& a); 54227825Stheraven list(initializer_list<value_type>); 55227825Stheraven list(initializer_list<value_type>, const allocator_type& a); 56227825Stheraven 57227825Stheraven ~list(); 58227825Stheraven 59227825Stheraven list& operator=(const list& x); 60227825Stheraven list& operator=(list&& x) 61227825Stheraven noexcept( 62227825Stheraven allocator_type::propagate_on_container_move_assignment::value && 63227825Stheraven is_nothrow_move_assignable<allocator_type>::value); 64227825Stheraven list& operator=(initializer_list<value_type>); 65227825Stheraven template <class Iter> 66227825Stheraven void assign(Iter first, Iter last); 67227825Stheraven void assign(size_type n, const value_type& t); 68227825Stheraven void assign(initializer_list<value_type>); 69227825Stheraven 70227825Stheraven allocator_type get_allocator() const noexcept; 71227825Stheraven 72227825Stheraven iterator begin() noexcept; 73227825Stheraven const_iterator begin() const noexcept; 74227825Stheraven iterator end() noexcept; 75227825Stheraven const_iterator end() const noexcept; 76227825Stheraven reverse_iterator rbegin() noexcept; 77227825Stheraven const_reverse_iterator rbegin() const noexcept; 78227825Stheraven reverse_iterator rend() noexcept; 79227825Stheraven const_reverse_iterator rend() const noexcept; 80227825Stheraven const_iterator cbegin() const noexcept; 81227825Stheraven const_iterator cend() const noexcept; 82227825Stheraven const_reverse_iterator crbegin() const noexcept; 83227825Stheraven const_reverse_iterator crend() const noexcept; 84227825Stheraven 85227825Stheraven reference front(); 86227825Stheraven const_reference front() const; 87227825Stheraven reference back(); 88227825Stheraven const_reference back() const; 89227825Stheraven 90227825Stheraven bool empty() const noexcept; 91227825Stheraven size_type size() const noexcept; 92227825Stheraven size_type max_size() const noexcept; 93227825Stheraven 94227825Stheraven template <class... Args> 95227825Stheraven void emplace_front(Args&&... args); 96227825Stheraven void pop_front(); 97227825Stheraven template <class... Args> 98227825Stheraven void emplace_back(Args&&... args); 99227825Stheraven void pop_back(); 100227825Stheraven void push_front(const value_type& x); 101227825Stheraven void push_front(value_type&& x); 102227825Stheraven void push_back(const value_type& x); 103227825Stheraven void push_back(value_type&& x); 104227825Stheraven template <class... Args> 105227825Stheraven iterator emplace(const_iterator position, Args&&... args); 106227825Stheraven iterator insert(const_iterator position, const value_type& x); 107227825Stheraven iterator insert(const_iterator position, value_type&& x); 108227825Stheraven iterator insert(const_iterator position, size_type n, const value_type& x); 109227825Stheraven template <class Iter> 110227825Stheraven iterator insert(const_iterator position, Iter first, Iter last); 111227825Stheraven iterator insert(const_iterator position, initializer_list<value_type> il); 112227825Stheraven 113227825Stheraven iterator erase(const_iterator position); 114227825Stheraven iterator erase(const_iterator position, const_iterator last); 115227825Stheraven 116227825Stheraven void resize(size_type sz); 117227825Stheraven void resize(size_type sz, const value_type& c); 118227825Stheraven 119227825Stheraven void swap(list&) 120227825Stheraven noexcept(!allocator_type::propagate_on_container_swap::value || 121227825Stheraven __is_nothrow_swappable<allocator_type>::value); 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 179232950Stheraven#include <__undef_min_max> 180232950Stheraven 181227825Stheraven#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) 182227825Stheraven#pragma GCC system_header 183227825Stheraven#endif 184227825Stheraven 185227825Stheraven_LIBCPP_BEGIN_NAMESPACE_STD 186227825Stheraven 187227825Stheraventemplate <class _Tp, class _VoidPtr> struct __list_node; 188227825Stheraven 189227825Stheraventemplate <class _Tp, class _VoidPtr> 190227825Stheravenstruct __list_node_base 191227825Stheraven{ 192227825Stheraven typedef typename pointer_traits<_VoidPtr>::template 193227825Stheraven#ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES 194227825Stheraven rebind<__list_node<_Tp, _VoidPtr> > pointer; 195227825Stheraven#else 196227825Stheraven rebind<__list_node<_Tp, _VoidPtr> >::other pointer; 197227825Stheraven#endif 198227825Stheraven 199227825Stheraven pointer __prev_; 200227825Stheraven pointer __next_; 201227825Stheraven 202227825Stheraven _LIBCPP_INLINE_VISIBILITY 203227825Stheraven __list_node_base() 204227825Stheraven : __prev_(static_cast<pointer>(this)), 205227825Stheraven __next_(static_cast<pointer>(this)) 206227825Stheraven {} 207227825Stheraven}; 208227825Stheraven 209227825Stheraventemplate <class _Tp, class _VoidPtr> 210227825Stheravenstruct __list_node 211227825Stheraven : public __list_node_base<_Tp, _VoidPtr> 212227825Stheraven{ 213227825Stheraven _Tp __value_; 214227825Stheraven}; 215227825Stheraven 216249998Sdimtemplate <class _Tp, class _Alloc> class _LIBCPP_TYPE_VIS list; 217227825Stheraventemplate <class _Tp, class _Alloc> class __list_imp; 218249998Sdimtemplate <class _Tp, class _VoidPtr> class _LIBCPP_TYPE_VIS __list_const_iterator; 219227825Stheraven 220227825Stheraventemplate <class _Tp, class _VoidPtr> 221249998Sdimclass _LIBCPP_TYPE_VIS __list_iterator 222227825Stheraven{ 223227825Stheraven typedef typename pointer_traits<_VoidPtr>::template 224227825Stheraven#ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES 225227825Stheraven rebind<__list_node<_Tp, _VoidPtr> > __node_pointer; 226227825Stheraven#else 227227825Stheraven rebind<__list_node<_Tp, _VoidPtr> >::other __node_pointer; 228227825Stheraven#endif 229227825Stheraven 230227825Stheraven __node_pointer __ptr_; 231227825Stheraven 232227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 233227825Stheraven _LIBCPP_INLINE_VISIBILITY 234227825Stheraven explicit __list_iterator(__node_pointer __p, const void* __c) _NOEXCEPT 235227825Stheraven : __ptr_(__p) 236227825Stheraven { 237227825Stheraven __get_db()->__insert_ic(this, __c); 238227825Stheraven } 239227825Stheraven#else 240227825Stheraven _LIBCPP_INLINE_VISIBILITY 241227825Stheraven explicit __list_iterator(__node_pointer __p) _NOEXCEPT : __ptr_(__p) {} 242227825Stheraven#endif 243227825Stheraven 244227825Stheraven 245227825Stheraven 246227825Stheraven template<class, class> friend class list; 247227825Stheraven template<class, class> friend class __list_imp; 248227825Stheraven template<class, class> friend class __list_const_iterator; 249227825Stheravenpublic: 250227825Stheraven typedef bidirectional_iterator_tag iterator_category; 251227825Stheraven typedef _Tp value_type; 252227825Stheraven typedef value_type& reference; 253227825Stheraven typedef typename pointer_traits<_VoidPtr>::template 254227825Stheraven#ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES 255227825Stheraven rebind<value_type> 256227825Stheraven#else 257227825Stheraven rebind<value_type>::other 258227825Stheraven#endif 259227825Stheraven pointer; 260227825Stheraven typedef typename pointer_traits<pointer>::difference_type difference_type; 261227825Stheraven 262227825Stheraven _LIBCPP_INLINE_VISIBILITY 263227825Stheraven __list_iterator() _NOEXCEPT 264227825Stheraven { 265227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 266227825Stheraven __get_db()->__insert_i(this); 267227825Stheraven#endif 268227825Stheraven } 269227825Stheraven 270227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 271227825Stheraven 272227825Stheraven _LIBCPP_INLINE_VISIBILITY 273227825Stheraven __list_iterator(const __list_iterator& __p) 274227825Stheraven : __ptr_(__p.__ptr_) 275227825Stheraven { 276227825Stheraven __get_db()->__iterator_copy(this, &__p); 277227825Stheraven } 278227825Stheraven 279227825Stheraven _LIBCPP_INLINE_VISIBILITY 280227825Stheraven ~__list_iterator() 281227825Stheraven { 282227825Stheraven __get_db()->__erase_i(this); 283227825Stheraven } 284227825Stheraven 285227825Stheraven _LIBCPP_INLINE_VISIBILITY 286227825Stheraven __list_iterator& operator=(const __list_iterator& __p) 287227825Stheraven { 288227825Stheraven if (this != &__p) 289227825Stheraven { 290227825Stheraven __get_db()->__iterator_copy(this, &__p); 291227825Stheraven __ptr_ = __p.__ptr_; 292227825Stheraven } 293227825Stheraven return *this; 294227825Stheraven } 295227825Stheraven 296227825Stheraven#endif // _LIBCPP_DEBUG_LEVEL >= 2 297227825Stheraven 298227825Stheraven _LIBCPP_INLINE_VISIBILITY 299227825Stheraven reference operator*() const 300227825Stheraven { 301227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 302227825Stheraven _LIBCPP_ASSERT(__get_const_db()->__dereferenceable(this), 303227825Stheraven "Attempted to dereference a non-dereferenceable list::iterator"); 304227825Stheraven#endif 305227825Stheraven return __ptr_->__value_; 306227825Stheraven } 307227825Stheraven _LIBCPP_INLINE_VISIBILITY 308227825Stheraven pointer operator->() const {return &(operator*());} 309227825Stheraven 310227825Stheraven _LIBCPP_INLINE_VISIBILITY 311227825Stheraven __list_iterator& operator++() 312227825Stheraven { 313227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 314227825Stheraven _LIBCPP_ASSERT(__get_const_db()->__dereferenceable(this), 315227825Stheraven "Attempted to increment non-incrementable list::iterator"); 316227825Stheraven#endif 317227825Stheraven __ptr_ = __ptr_->__next_; 318227825Stheraven return *this; 319227825Stheraven } 320227825Stheraven _LIBCPP_INLINE_VISIBILITY 321227825Stheraven __list_iterator operator++(int) {__list_iterator __t(*this); ++(*this); return __t;} 322227825Stheraven 323227825Stheraven _LIBCPP_INLINE_VISIBILITY 324227825Stheraven __list_iterator& operator--() 325227825Stheraven { 326227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 327227825Stheraven _LIBCPP_ASSERT(__get_const_db()->__decrementable(this), 328227825Stheraven "Attempted to decrement non-decrementable list::iterator"); 329227825Stheraven#endif 330227825Stheraven __ptr_ = __ptr_->__prev_; 331227825Stheraven return *this; 332227825Stheraven } 333227825Stheraven _LIBCPP_INLINE_VISIBILITY 334227825Stheraven __list_iterator operator--(int) {__list_iterator __t(*this); --(*this); return __t;} 335227825Stheraven 336227825Stheraven friend _LIBCPP_INLINE_VISIBILITY 337227825Stheraven bool operator==(const __list_iterator& __x, const __list_iterator& __y) 338227825Stheraven { 339227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 340227825Stheraven _LIBCPP_ASSERT(__get_const_db()->__comparable(&__x, &__y), 341227825Stheraven "Attempted to compare non-comparable list::iterator"); 342227825Stheraven#endif 343227825Stheraven return __x.__ptr_ == __y.__ptr_; 344227825Stheraven } 345227825Stheraven friend _LIBCPP_INLINE_VISIBILITY 346227825Stheraven bool operator!=(const __list_iterator& __x, const __list_iterator& __y) 347227825Stheraven {return !(__x == __y);} 348227825Stheraven}; 349227825Stheraven 350227825Stheraventemplate <class _Tp, class _VoidPtr> 351249998Sdimclass _LIBCPP_TYPE_VIS __list_const_iterator 352227825Stheraven{ 353227825Stheraven typedef typename pointer_traits<_VoidPtr>::template 354227825Stheraven#ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES 355227825Stheraven rebind<const __list_node<_Tp, _VoidPtr> > __node_pointer; 356227825Stheraven#else 357227825Stheraven rebind<const __list_node<_Tp, _VoidPtr> >::other __node_pointer; 358227825Stheraven#endif 359227825Stheraven 360227825Stheraven __node_pointer __ptr_; 361227825Stheraven 362227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 363227825Stheraven _LIBCPP_INLINE_VISIBILITY 364227825Stheraven explicit __list_const_iterator(__node_pointer __p, const void* __c) _NOEXCEPT 365227825Stheraven : __ptr_(__p) 366227825Stheraven { 367227825Stheraven __get_db()->__insert_ic(this, __c); 368227825Stheraven } 369227825Stheraven#else 370227825Stheraven _LIBCPP_INLINE_VISIBILITY 371227825Stheraven explicit __list_const_iterator(__node_pointer __p) _NOEXCEPT : __ptr_(__p) {} 372227825Stheraven#endif 373227825Stheraven 374227825Stheraven template<class, class> friend class list; 375227825Stheraven template<class, class> friend class __list_imp; 376227825Stheravenpublic: 377227825Stheraven typedef bidirectional_iterator_tag iterator_category; 378227825Stheraven typedef _Tp value_type; 379227825Stheraven typedef const value_type& reference; 380227825Stheraven typedef typename pointer_traits<_VoidPtr>::template 381227825Stheraven#ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES 382227825Stheraven rebind<const value_type> 383227825Stheraven#else 384227825Stheraven rebind<const value_type>::other 385227825Stheraven#endif 386227825Stheraven pointer; 387227825Stheraven typedef typename pointer_traits<pointer>::difference_type difference_type; 388227825Stheraven 389227825Stheraven _LIBCPP_INLINE_VISIBILITY 390227825Stheraven __list_const_iterator() _NOEXCEPT 391227825Stheraven { 392227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 393227825Stheraven __get_db()->__insert_i(this); 394227825Stheraven#endif 395227825Stheraven } 396227825Stheraven _LIBCPP_INLINE_VISIBILITY 397249998Sdim __list_const_iterator(const __list_iterator<_Tp, _VoidPtr>& __p) _NOEXCEPT 398227825Stheraven : __ptr_(__p.__ptr_) 399227825Stheraven { 400227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 401227825Stheraven __get_db()->__iterator_copy(this, &__p); 402227825Stheraven#endif 403227825Stheraven } 404227825Stheraven 405227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 406227825Stheraven 407227825Stheraven _LIBCPP_INLINE_VISIBILITY 408227825Stheraven __list_const_iterator(const __list_const_iterator& __p) 409227825Stheraven : __ptr_(__p.__ptr_) 410227825Stheraven { 411227825Stheraven __get_db()->__iterator_copy(this, &__p); 412227825Stheraven } 413227825Stheraven 414227825Stheraven _LIBCPP_INLINE_VISIBILITY 415227825Stheraven ~__list_const_iterator() 416227825Stheraven { 417227825Stheraven __get_db()->__erase_i(this); 418227825Stheraven } 419227825Stheraven 420227825Stheraven _LIBCPP_INLINE_VISIBILITY 421227825Stheraven __list_const_iterator& operator=(const __list_const_iterator& __p) 422227825Stheraven { 423227825Stheraven if (this != &__p) 424227825Stheraven { 425227825Stheraven __get_db()->__iterator_copy(this, &__p); 426227825Stheraven __ptr_ = __p.__ptr_; 427227825Stheraven } 428227825Stheraven return *this; 429227825Stheraven } 430227825Stheraven 431227825Stheraven#endif // _LIBCPP_DEBUG_LEVEL >= 2 432227825Stheraven _LIBCPP_INLINE_VISIBILITY 433227825Stheraven reference operator*() const 434227825Stheraven { 435227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 436227825Stheraven _LIBCPP_ASSERT(__get_const_db()->__dereferenceable(this), 437227825Stheraven "Attempted to dereference a non-dereferenceable list::const_iterator"); 438227825Stheraven#endif 439227825Stheraven return __ptr_->__value_; 440227825Stheraven } 441227825Stheraven _LIBCPP_INLINE_VISIBILITY 442227825Stheraven pointer operator->() const {return &(operator*());} 443227825Stheraven 444227825Stheraven _LIBCPP_INLINE_VISIBILITY 445227825Stheraven __list_const_iterator& operator++() 446227825Stheraven { 447227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 448227825Stheraven _LIBCPP_ASSERT(__get_const_db()->__dereferenceable(this), 449227825Stheraven "Attempted to increment non-incrementable list::const_iterator"); 450227825Stheraven#endif 451227825Stheraven __ptr_ = __ptr_->__next_; 452227825Stheraven return *this; 453227825Stheraven } 454227825Stheraven _LIBCPP_INLINE_VISIBILITY 455227825Stheraven __list_const_iterator operator++(int) {__list_const_iterator __t(*this); ++(*this); return __t;} 456227825Stheraven 457227825Stheraven _LIBCPP_INLINE_VISIBILITY 458227825Stheraven __list_const_iterator& operator--() 459227825Stheraven { 460227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 461227825Stheraven _LIBCPP_ASSERT(__get_const_db()->__decrementable(this), 462227825Stheraven "Attempted to decrement non-decrementable list::const_iterator"); 463227825Stheraven#endif 464227825Stheraven __ptr_ = __ptr_->__prev_; 465227825Stheraven return *this; 466227825Stheraven } 467227825Stheraven _LIBCPP_INLINE_VISIBILITY 468227825Stheraven __list_const_iterator operator--(int) {__list_const_iterator __t(*this); --(*this); return __t;} 469227825Stheraven 470227825Stheraven friend _LIBCPP_INLINE_VISIBILITY 471227825Stheraven bool operator==(const __list_const_iterator& __x, const __list_const_iterator& __y) 472227825Stheraven { 473227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 474227825Stheraven _LIBCPP_ASSERT(__get_const_db()->__comparable(&__x, &__y), 475227825Stheraven "Attempted to compare non-comparable list::const_iterator"); 476227825Stheraven#endif 477227825Stheraven return __x.__ptr_ == __y.__ptr_; 478227825Stheraven } 479227825Stheraven friend _LIBCPP_INLINE_VISIBILITY 480227825Stheraven bool operator!=(const __list_const_iterator& __x, const __list_const_iterator& __y) 481227825Stheraven {return !(__x == __y);} 482227825Stheraven}; 483227825Stheraven 484227825Stheraventemplate <class _Tp, class _Alloc> 485227825Stheravenclass __list_imp 486227825Stheraven{ 487227825Stheraven __list_imp(const __list_imp&); 488227825Stheraven __list_imp& operator=(const __list_imp&); 489227825Stheravenprotected: 490227825Stheraven typedef _Tp value_type; 491227825Stheraven typedef _Alloc allocator_type; 492227825Stheraven typedef allocator_traits<allocator_type> __alloc_traits; 493227825Stheraven typedef typename __alloc_traits::size_type size_type; 494227825Stheraven typedef typename __alloc_traits::void_pointer __void_pointer; 495227825Stheraven typedef __list_iterator<value_type, __void_pointer> iterator; 496227825Stheraven typedef __list_const_iterator<value_type, __void_pointer> const_iterator; 497227825Stheraven typedef __list_node_base<value_type, __void_pointer> __node_base; 498227825Stheraven typedef __list_node<value_type, __void_pointer> __node; 499227825Stheraven typedef typename __alloc_traits::template 500227825Stheraven#ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES 501227825Stheraven rebind_alloc<__node> 502227825Stheraven#else 503227825Stheraven rebind_alloc<__node>::other 504227825Stheraven#endif 505227825Stheraven __node_allocator; 506227825Stheraven typedef allocator_traits<__node_allocator> __node_alloc_traits; 507227825Stheraven typedef typename __node_alloc_traits::pointer __node_pointer; 508227825Stheraven typedef typename __node_alloc_traits::const_pointer __node_const_pointer; 509227825Stheraven typedef typename __alloc_traits::pointer pointer; 510227825Stheraven typedef typename __alloc_traits::const_pointer const_pointer; 511227825Stheraven typedef typename __alloc_traits::difference_type difference_type; 512227825Stheraven 513227825Stheraven __node_base __end_; 514227825Stheraven __compressed_pair<size_type, __node_allocator> __size_alloc_; 515227825Stheraven 516227825Stheraven _LIBCPP_INLINE_VISIBILITY 517227825Stheraven size_type& __sz() _NOEXCEPT {return __size_alloc_.first();} 518227825Stheraven _LIBCPP_INLINE_VISIBILITY 519227825Stheraven const size_type& __sz() const _NOEXCEPT 520227825Stheraven {return __size_alloc_.first();} 521227825Stheraven _LIBCPP_INLINE_VISIBILITY 522227825Stheraven __node_allocator& __node_alloc() _NOEXCEPT 523227825Stheraven {return __size_alloc_.second();} 524227825Stheraven _LIBCPP_INLINE_VISIBILITY 525227825Stheraven const __node_allocator& __node_alloc() const _NOEXCEPT 526227825Stheraven {return __size_alloc_.second();} 527227825Stheraven 528227825Stheraven static void __unlink_nodes(__node_base& __f, __node_base& __l) _NOEXCEPT; 529227825Stheraven 530227825Stheraven __list_imp() 531227825Stheraven _NOEXCEPT_(is_nothrow_default_constructible<__node_allocator>::value); 532227825Stheraven __list_imp(const allocator_type& __a); 533227825Stheraven ~__list_imp(); 534227825Stheraven void clear() _NOEXCEPT; 535227825Stheraven _LIBCPP_INLINE_VISIBILITY 536227825Stheraven bool empty() const _NOEXCEPT {return __sz() == 0;} 537227825Stheraven 538227825Stheraven _LIBCPP_INLINE_VISIBILITY 539227825Stheraven iterator begin() _NOEXCEPT 540227825Stheraven { 541227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 542227825Stheraven return iterator(__end_.__next_, this); 543227825Stheraven#else 544227825Stheraven return iterator(__end_.__next_); 545227825Stheraven#endif 546227825Stheraven } 547227825Stheraven _LIBCPP_INLINE_VISIBILITY 548227825Stheraven const_iterator begin() const _NOEXCEPT 549227825Stheraven { 550227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 551227825Stheraven return const_iterator(__end_.__next_, this); 552227825Stheraven#else 553227825Stheraven return const_iterator(__end_.__next_); 554227825Stheraven#endif 555227825Stheraven } 556227825Stheraven _LIBCPP_INLINE_VISIBILITY 557227825Stheraven iterator end() _NOEXCEPT 558227825Stheraven { 559227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 560227825Stheraven return iterator(static_cast<__node_pointer>(&__end_), this); 561227825Stheraven#else 562227825Stheraven return iterator(static_cast<__node_pointer>(&__end_)); 563227825Stheraven#endif 564227825Stheraven } 565227825Stheraven _LIBCPP_INLINE_VISIBILITY 566227825Stheraven const_iterator end() const _NOEXCEPT 567227825Stheraven { 568227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 569227825Stheraven return const_iterator(static_cast<__node_const_pointer>(&__end_), this); 570227825Stheraven#else 571227825Stheraven return const_iterator(static_cast<__node_const_pointer>(&__end_)); 572227825Stheraven#endif 573227825Stheraven } 574227825Stheraven 575227825Stheraven void swap(__list_imp& __c) 576227825Stheraven _NOEXCEPT_(!__node_alloc_traits::propagate_on_container_swap::value || 577227825Stheraven __is_nothrow_swappable<__node_allocator>::value); 578227825Stheraven 579227825Stheraven _LIBCPP_INLINE_VISIBILITY 580227825Stheraven void __copy_assign_alloc(const __list_imp& __c) 581227825Stheraven {__copy_assign_alloc(__c, integral_constant<bool, 582227825Stheraven __node_alloc_traits::propagate_on_container_copy_assignment::value>());} 583227825Stheraven 584227825Stheraven _LIBCPP_INLINE_VISIBILITY 585227825Stheraven void __move_assign_alloc(__list_imp& __c) 586227825Stheraven _NOEXCEPT_( 587227825Stheraven !__node_alloc_traits::propagate_on_container_move_assignment::value || 588227825Stheraven is_nothrow_move_assignable<__node_allocator>::value) 589227825Stheraven {__move_assign_alloc(__c, integral_constant<bool, 590227825Stheraven __node_alloc_traits::propagate_on_container_move_assignment::value>());} 591227825Stheraven 592227825Stheravenprivate: 593227825Stheraven _LIBCPP_INLINE_VISIBILITY 594227825Stheraven static void __swap_alloc(__node_allocator& __x, __node_allocator& __y) 595227825Stheraven _NOEXCEPT_(!__node_alloc_traits::propagate_on_container_swap::value || 596227825Stheraven __is_nothrow_swappable<__node_allocator>::value) 597227825Stheraven {__swap_alloc(__x, __y, integral_constant<bool, 598227825Stheraven __node_alloc_traits::propagate_on_container_swap::value>());} 599227825Stheraven _LIBCPP_INLINE_VISIBILITY 600227825Stheraven static void __swap_alloc(__node_allocator& __x, __node_allocator& __y, true_type) 601227825Stheraven _NOEXCEPT_(__is_nothrow_swappable<__node_allocator>::value) 602227825Stheraven { 603227825Stheraven using _VSTD::swap; 604227825Stheraven swap(__x, __y); 605227825Stheraven } 606227825Stheraven _LIBCPP_INLINE_VISIBILITY 607227825Stheraven static void __swap_alloc(__node_allocator& __x, __node_allocator& __y, false_type) 608227825Stheraven _NOEXCEPT 609227825Stheraven {} 610227825Stheraven 611227825Stheraven _LIBCPP_INLINE_VISIBILITY 612227825Stheraven void __copy_assign_alloc(const __list_imp& __c, true_type) 613227825Stheraven { 614227825Stheraven if (__node_alloc() != __c.__node_alloc()) 615227825Stheraven clear(); 616227825Stheraven __node_alloc() = __c.__node_alloc(); 617227825Stheraven } 618227825Stheraven 619227825Stheraven _LIBCPP_INLINE_VISIBILITY 620227825Stheraven void __copy_assign_alloc(const __list_imp& __c, false_type) 621227825Stheraven {} 622227825Stheraven 623227825Stheraven _LIBCPP_INLINE_VISIBILITY 624227825Stheraven void __move_assign_alloc(__list_imp& __c, true_type) 625227825Stheraven _NOEXCEPT_(is_nothrow_move_assignable<__node_allocator>::value) 626227825Stheraven { 627227825Stheraven __node_alloc() = _VSTD::move(__c.__node_alloc()); 628227825Stheraven } 629227825Stheraven 630227825Stheraven _LIBCPP_INLINE_VISIBILITY 631227825Stheraven void __move_assign_alloc(__list_imp& __c, false_type) 632227825Stheraven _NOEXCEPT 633227825Stheraven {} 634227825Stheraven}; 635227825Stheraven 636227825Stheraven// Unlink nodes [__f, __l] 637227825Stheraventemplate <class _Tp, class _Alloc> 638227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 639227825Stheravenvoid 640227825Stheraven__list_imp<_Tp, _Alloc>::__unlink_nodes(__node_base& __f, __node_base& __l) 641227825Stheraven _NOEXCEPT 642227825Stheraven{ 643227825Stheraven __f.__prev_->__next_ = __l.__next_; 644227825Stheraven __l.__next_->__prev_ = __f.__prev_; 645227825Stheraven} 646227825Stheraven 647227825Stheraventemplate <class _Tp, class _Alloc> 648227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 649227825Stheraven__list_imp<_Tp, _Alloc>::__list_imp() 650227825Stheraven _NOEXCEPT_(is_nothrow_default_constructible<__node_allocator>::value) 651227825Stheraven : __size_alloc_(0) 652227825Stheraven{ 653227825Stheraven} 654227825Stheraven 655227825Stheraventemplate <class _Tp, class _Alloc> 656227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 657227825Stheraven__list_imp<_Tp, _Alloc>::__list_imp(const allocator_type& __a) 658227825Stheraven : __size_alloc_(0, __node_allocator(__a)) 659227825Stheraven{ 660227825Stheraven} 661227825Stheraven 662227825Stheraventemplate <class _Tp, class _Alloc> 663227825Stheraven__list_imp<_Tp, _Alloc>::~__list_imp() 664227825Stheraven{ 665227825Stheraven clear(); 666227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 667227825Stheraven __get_db()->__erase_c(this); 668227825Stheraven#endif 669227825Stheraven} 670227825Stheraven 671227825Stheraventemplate <class _Tp, class _Alloc> 672227825Stheravenvoid 673227825Stheraven__list_imp<_Tp, _Alloc>::clear() _NOEXCEPT 674227825Stheraven{ 675227825Stheraven if (!empty()) 676227825Stheraven { 677227825Stheraven __node_allocator& __na = __node_alloc(); 678227825Stheraven __node_pointer __f = __end_.__next_; 679227825Stheraven __node_pointer __l = static_cast<__node_pointer>(&__end_); 680227825Stheraven __unlink_nodes(*__f, *__l->__prev_); 681227825Stheraven __sz() = 0; 682227825Stheraven while (__f != __l) 683227825Stheraven { 684227825Stheraven __node& __n = *__f; 685227825Stheraven __f = __f->__next_; 686227825Stheraven __node_alloc_traits::destroy(__na, _VSTD::addressof(__n.__value_)); 687227825Stheraven __node_alloc_traits::deallocate(__na, _VSTD::addressof(__n), 1); 688227825Stheraven } 689227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 690227825Stheraven __c_node* __c = __get_db()->__find_c_and_lock(this); 691227825Stheraven for (__i_node** __p = __c->end_; __p != __c->beg_; ) 692227825Stheraven { 693227825Stheraven --__p; 694227825Stheraven const_iterator* __i = static_cast<const_iterator*>((*__p)->__i_); 695227825Stheraven if (__i->__ptr_ != __l) 696227825Stheraven { 697227825Stheraven (*__p)->__c_ = nullptr; 698227825Stheraven if (--__c->end_ != __p) 699227825Stheraven memmove(__p, __p+1, (__c->end_ - __p)*sizeof(__i_node*)); 700227825Stheraven } 701227825Stheraven } 702227825Stheraven __get_db()->unlock(); 703227825Stheraven#endif 704227825Stheraven } 705227825Stheraven} 706227825Stheraven 707227825Stheraventemplate <class _Tp, class _Alloc> 708227825Stheravenvoid 709227825Stheraven__list_imp<_Tp, _Alloc>::swap(__list_imp& __c) 710227825Stheraven _NOEXCEPT_(!__node_alloc_traits::propagate_on_container_swap::value || 711227825Stheraven __is_nothrow_swappable<__node_allocator>::value) 712227825Stheraven{ 713227825Stheraven _LIBCPP_ASSERT(__alloc_traits::propagate_on_container_swap::value || 714227825Stheraven this->__node_alloc() == __c.__node_alloc(), 715227825Stheraven "list::swap: Either propagate_on_container_swap must be true" 716227825Stheraven " or the allocators must compare equal"); 717227825Stheraven using _VSTD::swap; 718227825Stheraven __swap_alloc(__node_alloc(), __c.__node_alloc()); 719227825Stheraven swap(__sz(), __c.__sz()); 720227825Stheraven swap(__end_, __c.__end_); 721227825Stheraven if (__sz() == 0) 722227825Stheraven __end_.__next_ = __end_.__prev_ = &static_cast<__node&>(__end_); 723227825Stheraven else 724227825Stheraven __end_.__prev_->__next_ = __end_.__next_->__prev_ 725227825Stheraven = &static_cast<__node&>(__end_); 726227825Stheraven if (__c.__sz() == 0) 727227825Stheraven __c.__end_.__next_ = __c.__end_.__prev_ 728227825Stheraven = &static_cast<__node&>(__c.__end_); 729227825Stheraven else 730227825Stheraven __c.__end_.__prev_->__next_ = __c.__end_.__next_->__prev_ 731227825Stheraven = &static_cast<__node&>(__c.__end_); 732227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 733227825Stheraven __libcpp_db* __db = __get_db(); 734227825Stheraven __c_node* __cn1 = __db->__find_c_and_lock(this); 735227825Stheraven __c_node* __cn2 = __db->__find_c(&__c); 736227825Stheraven std::swap(__cn1->beg_, __cn2->beg_); 737227825Stheraven std::swap(__cn1->end_, __cn2->end_); 738227825Stheraven std::swap(__cn1->cap_, __cn2->cap_); 739227825Stheraven for (__i_node** __p = __cn1->end_; __p != __cn1->beg_;) 740227825Stheraven { 741227825Stheraven --__p; 742227825Stheraven const_iterator* __i = static_cast<const_iterator*>((*__p)->__i_); 743227825Stheraven if (__i->__ptr_ == static_cast<__node_pointer>(&__c.__end_)) 744227825Stheraven { 745227825Stheraven __cn2->__add(*__p); 746227825Stheraven if (--__cn1->end_ != __p) 747227825Stheraven memmove(__p, __p+1, (__cn1->end_ - __p)*sizeof(__i_node*)); 748227825Stheraven } 749227825Stheraven else 750227825Stheraven (*__p)->__c_ = __cn1; 751227825Stheraven } 752227825Stheraven for (__i_node** __p = __cn2->end_; __p != __cn2->beg_;) 753227825Stheraven { 754227825Stheraven --__p; 755227825Stheraven const_iterator* __i = static_cast<const_iterator*>((*__p)->__i_); 756227825Stheraven if (__i->__ptr_ == static_cast<__node_pointer>(&__end_)) 757227825Stheraven { 758227825Stheraven __cn1->__add(*__p); 759227825Stheraven if (--__cn2->end_ != __p) 760227825Stheraven memmove(__p, __p+1, (__cn2->end_ - __p)*sizeof(__i_node*)); 761227825Stheraven } 762227825Stheraven else 763227825Stheraven (*__p)->__c_ = __cn2; 764227825Stheraven } 765227825Stheraven __db->unlock(); 766227825Stheraven#endif 767227825Stheraven} 768227825Stheraven 769227825Stheraventemplate <class _Tp, class _Alloc = allocator<_Tp> > 770249998Sdimclass _LIBCPP_TYPE_VIS list 771227825Stheraven : private __list_imp<_Tp, _Alloc> 772227825Stheraven{ 773227825Stheraven typedef __list_imp<_Tp, _Alloc> base; 774227825Stheraven typedef typename base::__node __node; 775227825Stheraven typedef typename base::__node_allocator __node_allocator; 776227825Stheraven typedef typename base::__node_pointer __node_pointer; 777227825Stheraven typedef typename base::__node_alloc_traits __node_alloc_traits; 778227825Stheraven 779227825Stheravenpublic: 780227825Stheraven typedef _Tp value_type; 781227825Stheraven typedef _Alloc allocator_type; 782227825Stheraven static_assert((is_same<value_type, typename allocator_type::value_type>::value), 783227825Stheraven "Invalid allocator::value_type"); 784227825Stheraven typedef value_type& reference; 785227825Stheraven typedef const value_type& const_reference; 786227825Stheraven typedef typename base::pointer pointer; 787227825Stheraven typedef typename base::const_pointer const_pointer; 788227825Stheraven typedef typename base::size_type size_type; 789227825Stheraven typedef typename base::difference_type difference_type; 790227825Stheraven typedef typename base::iterator iterator; 791227825Stheraven typedef typename base::const_iterator const_iterator; 792227825Stheraven typedef _VSTD::reverse_iterator<iterator> reverse_iterator; 793227825Stheraven typedef _VSTD::reverse_iterator<const_iterator> const_reverse_iterator; 794227825Stheraven 795227825Stheraven _LIBCPP_INLINE_VISIBILITY 796227825Stheraven list() 797227825Stheraven _NOEXCEPT_(is_nothrow_default_constructible<__node_allocator>::value) 798227825Stheraven { 799227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 800227825Stheraven __get_db()->__insert_c(this); 801227825Stheraven#endif 802227825Stheraven } 803227825Stheraven _LIBCPP_INLINE_VISIBILITY 804227825Stheraven list(const allocator_type& __a) : base(__a) 805227825Stheraven { 806227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 807227825Stheraven __get_db()->__insert_c(this); 808227825Stheraven#endif 809227825Stheraven } 810227825Stheraven list(size_type __n); 811227825Stheraven list(size_type __n, const value_type& __x); 812227825Stheraven list(size_type __n, const value_type& __x, const allocator_type& __a); 813227825Stheraven template <class _InpIter> 814227825Stheraven list(_InpIter __f, _InpIter __l, 815227825Stheraven typename enable_if<__is_input_iterator<_InpIter>::value>::type* = 0); 816227825Stheraven template <class _InpIter> 817227825Stheraven list(_InpIter __f, _InpIter __l, const allocator_type& __a, 818227825Stheraven typename enable_if<__is_input_iterator<_InpIter>::value>::type* = 0); 819227825Stheraven 820227825Stheraven list(const list& __c); 821227825Stheraven list(const list& __c, const allocator_type& __a); 822227825Stheraven list& operator=(const list& __c); 823227825Stheraven#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 824227825Stheraven list(initializer_list<value_type> __il); 825227825Stheraven list(initializer_list<value_type> __il, const allocator_type& __a); 826227825Stheraven#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 827227825Stheraven#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 828227825Stheraven list(list&& __c) 829227825Stheraven _NOEXCEPT_(is_nothrow_move_constructible<__node_allocator>::value); 830227825Stheraven list(list&& __c, const allocator_type& __a); 831227825Stheraven list& operator=(list&& __c) 832227825Stheraven _NOEXCEPT_( 833227825Stheraven __node_alloc_traits::propagate_on_container_move_assignment::value && 834227825Stheraven is_nothrow_move_assignable<__node_allocator>::value); 835227825Stheraven#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 836227825Stheraven#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 837227825Stheraven _LIBCPP_INLINE_VISIBILITY 838227825Stheraven list& operator=(initializer_list<value_type> __il) 839227825Stheraven {assign(__il.begin(), __il.end()); return *this;} 840227825Stheraven#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 841227825Stheraven 842227825Stheraven template <class _InpIter> 843227825Stheraven void assign(_InpIter __f, _InpIter __l, 844227825Stheraven typename enable_if<__is_input_iterator<_InpIter>::value>::type* = 0); 845227825Stheraven void assign(size_type __n, const value_type& __x); 846227825Stheraven#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 847227825Stheraven _LIBCPP_INLINE_VISIBILITY 848227825Stheraven void assign(initializer_list<value_type> __il) 849227825Stheraven {assign(__il.begin(), __il.end());} 850227825Stheraven#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 851227825Stheraven 852227825Stheraven allocator_type get_allocator() const _NOEXCEPT; 853227825Stheraven 854227825Stheraven _LIBCPP_INLINE_VISIBILITY 855227825Stheraven size_type size() const _NOEXCEPT {return base::__sz();} 856227825Stheraven _LIBCPP_INLINE_VISIBILITY 857227825Stheraven bool empty() const _NOEXCEPT {return base::empty();} 858227825Stheraven _LIBCPP_INLINE_VISIBILITY 859227825Stheraven size_type max_size() const _NOEXCEPT 860227825Stheraven {return numeric_limits<difference_type>::max();} 861227825Stheraven 862227825Stheraven _LIBCPP_INLINE_VISIBILITY 863227825Stheraven iterator begin() _NOEXCEPT {return base::begin();} 864227825Stheraven _LIBCPP_INLINE_VISIBILITY 865227825Stheraven const_iterator begin() const _NOEXCEPT {return base::begin();} 866227825Stheraven _LIBCPP_INLINE_VISIBILITY 867227825Stheraven iterator end() _NOEXCEPT {return base::end();} 868227825Stheraven _LIBCPP_INLINE_VISIBILITY 869227825Stheraven const_iterator end() const _NOEXCEPT {return base::end();} 870227825Stheraven _LIBCPP_INLINE_VISIBILITY 871227825Stheraven const_iterator cbegin() const _NOEXCEPT {return base::begin();} 872227825Stheraven _LIBCPP_INLINE_VISIBILITY 873227825Stheraven const_iterator cend() const _NOEXCEPT {return base::end();} 874227825Stheraven 875227825Stheraven _LIBCPP_INLINE_VISIBILITY 876227825Stheraven reverse_iterator rbegin() _NOEXCEPT 877227825Stheraven {return reverse_iterator(end());} 878227825Stheraven _LIBCPP_INLINE_VISIBILITY 879227825Stheraven const_reverse_iterator rbegin() const _NOEXCEPT 880227825Stheraven {return const_reverse_iterator(end());} 881227825Stheraven _LIBCPP_INLINE_VISIBILITY 882227825Stheraven reverse_iterator rend() _NOEXCEPT 883227825Stheraven {return reverse_iterator(begin());} 884227825Stheraven _LIBCPP_INLINE_VISIBILITY 885227825Stheraven const_reverse_iterator rend() const _NOEXCEPT 886227825Stheraven {return const_reverse_iterator(begin());} 887227825Stheraven _LIBCPP_INLINE_VISIBILITY 888227825Stheraven const_reverse_iterator crbegin() const _NOEXCEPT 889227825Stheraven {return const_reverse_iterator(end());} 890227825Stheraven _LIBCPP_INLINE_VISIBILITY 891227825Stheraven const_reverse_iterator crend() const _NOEXCEPT 892227825Stheraven {return const_reverse_iterator(begin());} 893227825Stheraven 894227825Stheraven _LIBCPP_INLINE_VISIBILITY 895227825Stheraven reference front() 896227825Stheraven { 897227825Stheraven _LIBCPP_ASSERT(!empty(), "list::front called on empty list"); 898227825Stheraven return base::__end_.__next_->__value_; 899227825Stheraven } 900227825Stheraven _LIBCPP_INLINE_VISIBILITY 901227825Stheraven const_reference front() const 902227825Stheraven { 903227825Stheraven _LIBCPP_ASSERT(!empty(), "list::front called on empty list"); 904227825Stheraven return base::__end_.__next_->__value_; 905227825Stheraven } 906227825Stheraven _LIBCPP_INLINE_VISIBILITY 907227825Stheraven reference back() 908227825Stheraven { 909227825Stheraven _LIBCPP_ASSERT(!empty(), "list::back called on empty list"); 910227825Stheraven return base::__end_.__prev_->__value_; 911227825Stheraven } 912227825Stheraven _LIBCPP_INLINE_VISIBILITY 913227825Stheraven const_reference back() const 914227825Stheraven { 915227825Stheraven _LIBCPP_ASSERT(!empty(), "list::back called on empty list"); 916227825Stheraven return base::__end_.__prev_->__value_; 917227825Stheraven } 918227825Stheraven 919227825Stheraven#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 920227825Stheraven void push_front(value_type&& __x); 921227825Stheraven void push_back(value_type&& __x); 922227825Stheraven#ifndef _LIBCPP_HAS_NO_VARIADICS 923227825Stheraven template <class... _Args> 924227825Stheraven void emplace_front(_Args&&... __args); 925227825Stheraven template <class... _Args> 926227825Stheraven void emplace_back(_Args&&... __args); 927227825Stheraven template <class... _Args> 928227825Stheraven iterator emplace(const_iterator __p, _Args&&... __args); 929227825Stheraven#endif // _LIBCPP_HAS_NO_VARIADICS 930227825Stheraven iterator insert(const_iterator __p, value_type&& __x); 931227825Stheraven#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 932227825Stheraven 933227825Stheraven void push_front(const value_type& __x); 934227825Stheraven void push_back(const value_type& __x); 935227825Stheraven 936227825Stheraven iterator insert(const_iterator __p, const value_type& __x); 937227825Stheraven iterator insert(const_iterator __p, size_type __n, const value_type& __x); 938227825Stheraven template <class _InpIter> 939227825Stheraven iterator insert(const_iterator __p, _InpIter __f, _InpIter __l, 940227825Stheraven typename enable_if<__is_input_iterator<_InpIter>::value>::type* = 0); 941227825Stheraven#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 942227825Stheraven _LIBCPP_INLINE_VISIBILITY 943227825Stheraven iterator insert(const_iterator __p, initializer_list<value_type> __il) 944227825Stheraven {return insert(__p, __il.begin(), __il.end());} 945227825Stheraven#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 946227825Stheraven 947227825Stheraven _LIBCPP_INLINE_VISIBILITY 948227825Stheraven void swap(list& __c) 949227825Stheraven _NOEXCEPT_(!__node_alloc_traits::propagate_on_container_swap::value || 950227825Stheraven __is_nothrow_swappable<__node_allocator>::value) 951227825Stheraven {base::swap(__c);} 952227825Stheraven _LIBCPP_INLINE_VISIBILITY 953227825Stheraven void clear() _NOEXCEPT {base::clear();} 954227825Stheraven 955227825Stheraven void pop_front(); 956227825Stheraven void pop_back(); 957227825Stheraven 958227825Stheraven iterator erase(const_iterator __p); 959227825Stheraven iterator erase(const_iterator __f, const_iterator __l); 960227825Stheraven 961227825Stheraven void resize(size_type __n); 962227825Stheraven void resize(size_type __n, const value_type& __x); 963227825Stheraven 964227825Stheraven void splice(const_iterator __p, list& __c); 965227825Stheraven#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 966227825Stheraven _LIBCPP_INLINE_VISIBILITY 967227825Stheraven void splice(const_iterator __p, list&& __c) {splice(__p, __c);} 968227825Stheraven#endif 969227825Stheraven void splice(const_iterator __p, list& __c, const_iterator __i); 970227825Stheraven#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 971227825Stheraven _LIBCPP_INLINE_VISIBILITY 972227825Stheraven void splice(const_iterator __p, list&& __c, const_iterator __i) 973227825Stheraven {splice(__p, __c, __i);} 974227825Stheraven#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 975227825Stheraven void splice(const_iterator __p, list& __c, const_iterator __f, const_iterator __l); 976227825Stheraven#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 977227825Stheraven _LIBCPP_INLINE_VISIBILITY 978227825Stheraven void splice(const_iterator __p, list&& __c, const_iterator __f, const_iterator __l) 979227825Stheraven {splice(__p, __c, __f, __l);} 980227825Stheraven#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 981227825Stheraven 982227825Stheraven void remove(const value_type& __x); 983227825Stheraven template <class _Pred> void remove_if(_Pred __pred); 984227825Stheraven void unique(); 985227825Stheraven template <class _BinaryPred> 986227825Stheraven void unique(_BinaryPred __binary_pred); 987227825Stheraven void merge(list& __c); 988227825Stheraven#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 989227825Stheraven _LIBCPP_INLINE_VISIBILITY 990227825Stheraven void merge(list&& __c) {merge(__c);} 991227825Stheraven#endif 992227825Stheraven template <class _Comp> 993227825Stheraven void merge(list& __c, _Comp __comp); 994227825Stheraven#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 995227825Stheraven template <class _Comp> 996227825Stheraven _LIBCPP_INLINE_VISIBILITY 997227825Stheraven void merge(list&& __c, _Comp __comp) {merge(__c, __comp);} 998227825Stheraven#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 999227825Stheraven void sort(); 1000227825Stheraven template <class _Comp> 1001227825Stheraven void sort(_Comp __comp); 1002227825Stheraven 1003227825Stheraven void reverse() _NOEXCEPT; 1004227825Stheraven 1005227825Stheraven bool __invariants() const; 1006227825Stheraven 1007227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 1008227825Stheraven 1009227825Stheraven bool __dereferenceable(const const_iterator* __i) const; 1010227825Stheraven bool __decrementable(const const_iterator* __i) const; 1011227825Stheraven bool __addable(const const_iterator* __i, ptrdiff_t __n) const; 1012227825Stheraven bool __subscriptable(const const_iterator* __i, ptrdiff_t __n) const; 1013227825Stheraven 1014227825Stheraven#endif // _LIBCPP_DEBUG_LEVEL >= 2 1015227825Stheraven 1016227825Stheravenprivate: 1017227825Stheraven static void __link_nodes(__node& __p, __node& __f, __node& __l); 1018227825Stheraven iterator __iterator(size_type __n); 1019227825Stheraven template <class _Comp> 1020227825Stheraven static iterator __sort(iterator __f1, iterator __e2, size_type __n, _Comp& __comp); 1021227825Stheraven 1022227825Stheraven void __move_assign(list& __c, true_type) 1023227825Stheraven _NOEXCEPT_(is_nothrow_move_assignable<__node_allocator>::value); 1024227825Stheraven void __move_assign(list& __c, false_type); 1025227825Stheraven}; 1026227825Stheraven 1027227825Stheraven// Link in nodes [__f, __l] just prior to __p 1028227825Stheraventemplate <class _Tp, class _Alloc> 1029227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 1030227825Stheravenvoid 1031227825Stheravenlist<_Tp, _Alloc>::__link_nodes(__node& __p, __node& __f, __node& __l) 1032227825Stheraven{ 1033227825Stheraven __p.__prev_->__next_ = &__f; 1034227825Stheraven __f.__prev_ = __p.__prev_; 1035227825Stheraven __p.__prev_ = &__l; 1036227825Stheraven __l.__next_ = &__p; 1037227825Stheraven} 1038227825Stheraven 1039227825Stheraventemplate <class _Tp, class _Alloc> 1040227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 1041227825Stheraventypename list<_Tp, _Alloc>::iterator 1042227825Stheravenlist<_Tp, _Alloc>::__iterator(size_type __n) 1043227825Stheraven{ 1044227825Stheraven return __n <= base::__sz() / 2 ? _VSTD::next(begin(), __n) 1045227825Stheraven : _VSTD::prev(end(), base::__sz() - __n); 1046227825Stheraven} 1047227825Stheraven 1048227825Stheraventemplate <class _Tp, class _Alloc> 1049227825Stheravenlist<_Tp, _Alloc>::list(size_type __n) 1050227825Stheraven{ 1051227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 1052227825Stheraven __get_db()->__insert_c(this); 1053227825Stheraven#endif 1054227825Stheraven for (; __n > 0; --__n) 1055227825Stheraven#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 1056227825Stheraven emplace_back(); 1057227825Stheraven#else 1058227825Stheraven push_back(value_type()); 1059227825Stheraven#endif 1060227825Stheraven} 1061227825Stheraven 1062227825Stheraventemplate <class _Tp, class _Alloc> 1063227825Stheravenlist<_Tp, _Alloc>::list(size_type __n, const value_type& __x) 1064227825Stheraven{ 1065227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 1066227825Stheraven __get_db()->__insert_c(this); 1067227825Stheraven#endif 1068227825Stheraven for (; __n > 0; --__n) 1069227825Stheraven push_back(__x); 1070227825Stheraven} 1071227825Stheraven 1072227825Stheraventemplate <class _Tp, class _Alloc> 1073227825Stheravenlist<_Tp, _Alloc>::list(size_type __n, const value_type& __x, const allocator_type& __a) 1074227825Stheraven : base(__a) 1075227825Stheraven{ 1076227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 1077227825Stheraven __get_db()->__insert_c(this); 1078227825Stheraven#endif 1079227825Stheraven for (; __n > 0; --__n) 1080227825Stheraven push_back(__x); 1081227825Stheraven} 1082227825Stheraven 1083227825Stheraventemplate <class _Tp, class _Alloc> 1084227825Stheraventemplate <class _InpIter> 1085227825Stheravenlist<_Tp, _Alloc>::list(_InpIter __f, _InpIter __l, 1086227825Stheraven typename enable_if<__is_input_iterator<_InpIter>::value>::type*) 1087227825Stheraven{ 1088227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 1089227825Stheraven __get_db()->__insert_c(this); 1090227825Stheraven#endif 1091227825Stheraven for (; __f != __l; ++__f) 1092227825Stheraven push_back(*__f); 1093227825Stheraven} 1094227825Stheraven 1095227825Stheraventemplate <class _Tp, class _Alloc> 1096227825Stheraventemplate <class _InpIter> 1097227825Stheravenlist<_Tp, _Alloc>::list(_InpIter __f, _InpIter __l, const allocator_type& __a, 1098227825Stheraven typename enable_if<__is_input_iterator<_InpIter>::value>::type*) 1099227825Stheraven : base(__a) 1100227825Stheraven{ 1101227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 1102227825Stheraven __get_db()->__insert_c(this); 1103227825Stheraven#endif 1104227825Stheraven for (; __f != __l; ++__f) 1105227825Stheraven push_back(*__f); 1106227825Stheraven} 1107227825Stheraven 1108227825Stheraventemplate <class _Tp, class _Alloc> 1109227825Stheravenlist<_Tp, _Alloc>::list(const list& __c) 1110227825Stheraven : base(allocator_type( 1111227825Stheraven __node_alloc_traits::select_on_container_copy_construction( 1112227825Stheraven __c.__node_alloc()))) 1113227825Stheraven{ 1114227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 1115227825Stheraven __get_db()->__insert_c(this); 1116227825Stheraven#endif 1117227825Stheraven for (const_iterator __i = __c.begin(), __e = __c.end(); __i != __e; ++__i) 1118227825Stheraven push_back(*__i); 1119227825Stheraven} 1120227825Stheraven 1121227825Stheraventemplate <class _Tp, class _Alloc> 1122227825Stheravenlist<_Tp, _Alloc>::list(const list& __c, const allocator_type& __a) 1123227825Stheraven : base(__a) 1124227825Stheraven{ 1125227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 1126227825Stheraven __get_db()->__insert_c(this); 1127227825Stheraven#endif 1128227825Stheraven for (const_iterator __i = __c.begin(), __e = __c.end(); __i != __e; ++__i) 1129227825Stheraven push_back(*__i); 1130227825Stheraven} 1131227825Stheraven 1132227825Stheraven#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 1133227825Stheraven 1134227825Stheraventemplate <class _Tp, class _Alloc> 1135227825Stheravenlist<_Tp, _Alloc>::list(initializer_list<value_type> __il, const allocator_type& __a) 1136227825Stheraven : base(__a) 1137227825Stheraven{ 1138227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 1139227825Stheraven __get_db()->__insert_c(this); 1140227825Stheraven#endif 1141227825Stheraven for (typename initializer_list<value_type>::const_iterator __i = __il.begin(), 1142227825Stheraven __e = __il.end(); __i != __e; ++__i) 1143227825Stheraven push_back(*__i); 1144227825Stheraven} 1145227825Stheraven 1146227825Stheraventemplate <class _Tp, class _Alloc> 1147227825Stheravenlist<_Tp, _Alloc>::list(initializer_list<value_type> __il) 1148227825Stheraven{ 1149227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 1150227825Stheraven __get_db()->__insert_c(this); 1151227825Stheraven#endif 1152227825Stheraven for (typename initializer_list<value_type>::const_iterator __i = __il.begin(), 1153227825Stheraven __e = __il.end(); __i != __e; ++__i) 1154227825Stheraven push_back(*__i); 1155227825Stheraven} 1156227825Stheraven 1157227825Stheraven#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 1158227825Stheraven 1159227825Stheraventemplate <class _Tp, class _Alloc> 1160227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 1161227825Stheravenlist<_Tp, _Alloc>& 1162227825Stheravenlist<_Tp, _Alloc>::operator=(const list& __c) 1163227825Stheraven{ 1164227825Stheraven if (this != &__c) 1165227825Stheraven { 1166227825Stheraven base::__copy_assign_alloc(__c); 1167227825Stheraven assign(__c.begin(), __c.end()); 1168227825Stheraven } 1169227825Stheraven return *this; 1170227825Stheraven} 1171227825Stheraven 1172227825Stheraven#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 1173227825Stheraven 1174227825Stheraventemplate <class _Tp, class _Alloc> 1175227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 1176227825Stheravenlist<_Tp, _Alloc>::list(list&& __c) 1177227825Stheraven _NOEXCEPT_(is_nothrow_move_constructible<__node_allocator>::value) 1178227825Stheraven : base(allocator_type(_VSTD::move(__c.__node_alloc()))) 1179227825Stheraven{ 1180227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 1181227825Stheraven __get_db()->__insert_c(this); 1182227825Stheraven#endif 1183227825Stheraven splice(end(), __c); 1184227825Stheraven} 1185227825Stheraven 1186227825Stheraventemplate <class _Tp, class _Alloc> 1187227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 1188227825Stheravenlist<_Tp, _Alloc>::list(list&& __c, const allocator_type& __a) 1189227825Stheraven : base(__a) 1190227825Stheraven{ 1191227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 1192227825Stheraven __get_db()->__insert_c(this); 1193227825Stheraven#endif 1194227825Stheraven if (__a == __c.get_allocator()) 1195227825Stheraven splice(end(), __c); 1196227825Stheraven else 1197227825Stheraven { 1198232950Stheraven typedef move_iterator<iterator> _Ip; 1199232950Stheraven assign(_Ip(__c.begin()), _Ip(__c.end())); 1200227825Stheraven } 1201227825Stheraven} 1202227825Stheraven 1203227825Stheraventemplate <class _Tp, class _Alloc> 1204227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 1205227825Stheravenlist<_Tp, _Alloc>& 1206227825Stheravenlist<_Tp, _Alloc>::operator=(list&& __c) 1207227825Stheraven _NOEXCEPT_( 1208227825Stheraven __node_alloc_traits::propagate_on_container_move_assignment::value && 1209227825Stheraven is_nothrow_move_assignable<__node_allocator>::value) 1210227825Stheraven{ 1211227825Stheraven __move_assign(__c, integral_constant<bool, 1212227825Stheraven __node_alloc_traits::propagate_on_container_move_assignment::value>()); 1213227825Stheraven return *this; 1214227825Stheraven} 1215227825Stheraven 1216227825Stheraventemplate <class _Tp, class _Alloc> 1217227825Stheravenvoid 1218227825Stheravenlist<_Tp, _Alloc>::__move_assign(list& __c, false_type) 1219227825Stheraven{ 1220227825Stheraven if (base::__node_alloc() != __c.__node_alloc()) 1221227825Stheraven { 1222232950Stheraven typedef move_iterator<iterator> _Ip; 1223232950Stheraven assign(_Ip(__c.begin()), _Ip(__c.end())); 1224227825Stheraven } 1225227825Stheraven else 1226227825Stheraven __move_assign(__c, true_type()); 1227227825Stheraven} 1228227825Stheraven 1229227825Stheraventemplate <class _Tp, class _Alloc> 1230227825Stheravenvoid 1231227825Stheravenlist<_Tp, _Alloc>::__move_assign(list& __c, true_type) 1232227825Stheraven _NOEXCEPT_(is_nothrow_move_assignable<__node_allocator>::value) 1233227825Stheraven{ 1234227825Stheraven clear(); 1235227825Stheraven base::__move_assign_alloc(__c); 1236227825Stheraven splice(end(), __c); 1237227825Stheraven} 1238227825Stheraven 1239227825Stheraven#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 1240227825Stheraven 1241227825Stheraventemplate <class _Tp, class _Alloc> 1242227825Stheraventemplate <class _InpIter> 1243227825Stheravenvoid 1244227825Stheravenlist<_Tp, _Alloc>::assign(_InpIter __f, _InpIter __l, 1245227825Stheraven typename enable_if<__is_input_iterator<_InpIter>::value>::type*) 1246227825Stheraven{ 1247227825Stheraven iterator __i = begin(); 1248227825Stheraven iterator __e = end(); 1249227825Stheraven for (; __f != __l && __i != __e; ++__f, ++__i) 1250227825Stheraven *__i = *__f; 1251227825Stheraven if (__i == __e) 1252227825Stheraven insert(__e, __f, __l); 1253227825Stheraven else 1254227825Stheraven erase(__i, __e); 1255227825Stheraven} 1256227825Stheraven 1257227825Stheraventemplate <class _Tp, class _Alloc> 1258227825Stheravenvoid 1259227825Stheravenlist<_Tp, _Alloc>::assign(size_type __n, const value_type& __x) 1260227825Stheraven{ 1261227825Stheraven iterator __i = begin(); 1262227825Stheraven iterator __e = end(); 1263227825Stheraven for (; __n > 0 && __i != __e; --__n, ++__i) 1264227825Stheraven *__i = __x; 1265227825Stheraven if (__i == __e) 1266227825Stheraven insert(__e, __n, __x); 1267227825Stheraven else 1268227825Stheraven erase(__i, __e); 1269227825Stheraven} 1270227825Stheraven 1271227825Stheraventemplate <class _Tp, class _Alloc> 1272227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 1273227825Stheraven_Alloc 1274227825Stheravenlist<_Tp, _Alloc>::get_allocator() const _NOEXCEPT 1275227825Stheraven{ 1276227825Stheraven return allocator_type(base::__node_alloc()); 1277227825Stheraven} 1278227825Stheraven 1279227825Stheraventemplate <class _Tp, class _Alloc> 1280227825Stheraventypename list<_Tp, _Alloc>::iterator 1281227825Stheravenlist<_Tp, _Alloc>::insert(const_iterator __p, const value_type& __x) 1282227825Stheraven{ 1283227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 1284227825Stheraven _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__p) == this, 1285227825Stheraven "list::insert(iterator, x) called with an iterator not" 1286227825Stheraven " referring to this list"); 1287227825Stheraven#endif 1288227825Stheraven __node_allocator& __na = base::__node_alloc(); 1289232950Stheraven typedef __allocator_destructor<__node_allocator> _Dp; 1290232950Stheraven unique_ptr<__node, _Dp> __hold(__node_alloc_traits::allocate(__na, 1), _Dp(__na, 1)); 1291227825Stheraven __hold->__prev_ = 0; 1292227825Stheraven __node_alloc_traits::construct(__na, _VSTD::addressof(__hold->__value_), __x); 1293227825Stheraven __link_nodes(const_cast<__node&>(*__p.__ptr_), *__hold, *__hold); 1294227825Stheraven ++base::__sz(); 1295249998Sdim#if _LIBCPP_DEBUG_LEVEL >= 2 1296249998Sdim return iterator(__hold.release(), this); 1297249998Sdim#else 1298227825Stheraven return iterator(__hold.release()); 1299249998Sdim#endif 1300227825Stheraven} 1301227825Stheraven 1302227825Stheraventemplate <class _Tp, class _Alloc> 1303227825Stheraventypename list<_Tp, _Alloc>::iterator 1304227825Stheravenlist<_Tp, _Alloc>::insert(const_iterator __p, size_type __n, const value_type& __x) 1305227825Stheraven{ 1306227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 1307227825Stheraven _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__p) == this, 1308227825Stheraven "list::insert(iterator, n, x) called with an iterator not" 1309227825Stheraven " referring to this list"); 1310227825Stheraven iterator __r(const_cast<__node_pointer>(__p.__ptr_), this); 1311227825Stheraven#else 1312227825Stheraven iterator __r(const_cast<__node_pointer>(__p.__ptr_)); 1313227825Stheraven#endif 1314227825Stheraven if (__n > 0) 1315227825Stheraven { 1316227825Stheraven size_type __ds = 0; 1317227825Stheraven __node_allocator& __na = base::__node_alloc(); 1318232950Stheraven typedef __allocator_destructor<__node_allocator> _Dp; 1319232950Stheraven unique_ptr<__node, _Dp> __hold(__node_alloc_traits::allocate(__na, 1), _Dp(__na, 1)); 1320227825Stheraven __hold->__prev_ = 0; 1321227825Stheraven __node_alloc_traits::construct(__na, _VSTD::addressof(__hold->__value_), __x); 1322227825Stheraven ++__ds; 1323227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 1324227825Stheraven __r = iterator(__hold.get(), this); 1325227825Stheraven#else 1326227825Stheraven __r = iterator(__hold.get()); 1327227825Stheraven#endif 1328227825Stheraven __hold.release(); 1329227825Stheraven iterator __e = __r; 1330227825Stheraven#ifndef _LIBCPP_NO_EXCEPTIONS 1331227825Stheraven try 1332227825Stheraven { 1333227825Stheraven#endif // _LIBCPP_NO_EXCEPTIONS 1334227825Stheraven for (--__n; __n != 0; --__n, ++__e, ++__ds) 1335227825Stheraven { 1336227825Stheraven __hold.reset(__node_alloc_traits::allocate(__na, 1)); 1337227825Stheraven __node_alloc_traits::construct(__na, _VSTD::addressof(__hold->__value_), __x); 1338227825Stheraven __e.__ptr_->__next_ = __hold.get(); 1339227825Stheraven __hold->__prev_ = __e.__ptr_; 1340227825Stheraven __hold.release(); 1341227825Stheraven } 1342227825Stheraven#ifndef _LIBCPP_NO_EXCEPTIONS 1343227825Stheraven } 1344227825Stheraven catch (...) 1345227825Stheraven { 1346227825Stheraven while (true) 1347227825Stheraven { 1348227825Stheraven __node_alloc_traits::destroy(__na, _VSTD::addressof(*__e)); 1349227825Stheraven __node_pointer __prev = __e.__ptr_->__prev_; 1350227825Stheraven __node_alloc_traits::deallocate(__na, __e.__ptr_, 1); 1351227825Stheraven if (__prev == 0) 1352227825Stheraven break; 1353227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 1354227825Stheraven __e = iterator(__prev, this); 1355227825Stheraven#else 1356227825Stheraven __e = iterator(__prev); 1357227825Stheraven#endif 1358227825Stheraven } 1359227825Stheraven throw; 1360227825Stheraven } 1361227825Stheraven#endif // _LIBCPP_NO_EXCEPTIONS 1362227825Stheraven __link_nodes(const_cast<__node&>(*__p.__ptr_), *__r.__ptr_, *__e.__ptr_); 1363227825Stheraven base::__sz() += __ds; 1364227825Stheraven } 1365227825Stheraven return __r; 1366227825Stheraven} 1367227825Stheraven 1368227825Stheraventemplate <class _Tp, class _Alloc> 1369227825Stheraventemplate <class _InpIter> 1370227825Stheraventypename list<_Tp, _Alloc>::iterator 1371227825Stheravenlist<_Tp, _Alloc>::insert(const_iterator __p, _InpIter __f, _InpIter __l, 1372227825Stheraven typename enable_if<__is_input_iterator<_InpIter>::value>::type*) 1373227825Stheraven{ 1374227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 1375227825Stheraven _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__p) == this, 1376227825Stheraven "list::insert(iterator, range) called with an iterator not" 1377227825Stheraven " referring to this list"); 1378227825Stheraven iterator __r(const_cast<__node_pointer>(__p.__ptr_), this); 1379227825Stheraven#else 1380227825Stheraven iterator __r(const_cast<__node_pointer>(__p.__ptr_)); 1381227825Stheraven#endif 1382227825Stheraven if (__f != __l) 1383227825Stheraven { 1384227825Stheraven size_type __ds = 0; 1385227825Stheraven __node_allocator& __na = base::__node_alloc(); 1386232950Stheraven typedef __allocator_destructor<__node_allocator> _Dp; 1387232950Stheraven unique_ptr<__node, _Dp> __hold(__node_alloc_traits::allocate(__na, 1), _Dp(__na, 1)); 1388227825Stheraven __hold->__prev_ = 0; 1389227825Stheraven __node_alloc_traits::construct(__na, _VSTD::addressof(__hold->__value_), *__f); 1390227825Stheraven ++__ds; 1391227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 1392227825Stheraven __r = iterator(__hold.get(), this); 1393227825Stheraven#else 1394227825Stheraven __r = iterator(__hold.get()); 1395227825Stheraven#endif 1396227825Stheraven __hold.release(); 1397227825Stheraven iterator __e = __r; 1398227825Stheraven#ifndef _LIBCPP_NO_EXCEPTIONS 1399227825Stheraven try 1400227825Stheraven { 1401227825Stheraven#endif // _LIBCPP_NO_EXCEPTIONS 1402227825Stheraven for (++__f; __f != __l; ++__f, ++__e, ++__ds) 1403227825Stheraven { 1404227825Stheraven __hold.reset(__node_alloc_traits::allocate(__na, 1)); 1405227825Stheraven __node_alloc_traits::construct(__na, _VSTD::addressof(__hold->__value_), *__f); 1406227825Stheraven __e.__ptr_->__next_ = __hold.get(); 1407227825Stheraven __hold->__prev_ = __e.__ptr_; 1408227825Stheraven __hold.release(); 1409227825Stheraven } 1410227825Stheraven#ifndef _LIBCPP_NO_EXCEPTIONS 1411227825Stheraven } 1412227825Stheraven catch (...) 1413227825Stheraven { 1414227825Stheraven while (true) 1415227825Stheraven { 1416227825Stheraven __node_alloc_traits::destroy(__na, _VSTD::addressof(*__e)); 1417227825Stheraven __node_pointer __prev = __e.__ptr_->__prev_; 1418227825Stheraven __node_alloc_traits::deallocate(__na, __e.__ptr_, 1); 1419227825Stheraven if (__prev == 0) 1420227825Stheraven break; 1421227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 1422227825Stheraven __e = iterator(__prev, this); 1423227825Stheraven#else 1424227825Stheraven __e = iterator(__prev); 1425227825Stheraven#endif 1426227825Stheraven } 1427227825Stheraven throw; 1428227825Stheraven } 1429227825Stheraven#endif // _LIBCPP_NO_EXCEPTIONS 1430227825Stheraven __link_nodes(const_cast<__node&>(*__p.__ptr_), *__r.__ptr_, *__e.__ptr_); 1431227825Stheraven base::__sz() += __ds; 1432227825Stheraven } 1433227825Stheraven return __r; 1434227825Stheraven} 1435227825Stheraven 1436227825Stheraventemplate <class _Tp, class _Alloc> 1437227825Stheravenvoid 1438227825Stheravenlist<_Tp, _Alloc>::push_front(const value_type& __x) 1439227825Stheraven{ 1440227825Stheraven __node_allocator& __na = base::__node_alloc(); 1441232950Stheraven typedef __allocator_destructor<__node_allocator> _Dp; 1442232950Stheraven unique_ptr<__node, _Dp> __hold(__node_alloc_traits::allocate(__na, 1), _Dp(__na, 1)); 1443227825Stheraven __node_alloc_traits::construct(__na, _VSTD::addressof(__hold->__value_), __x); 1444227825Stheraven __link_nodes(*base::__end_.__next_, *__hold, *__hold); 1445227825Stheraven ++base::__sz(); 1446227825Stheraven __hold.release(); 1447227825Stheraven} 1448227825Stheraven 1449227825Stheraventemplate <class _Tp, class _Alloc> 1450227825Stheravenvoid 1451227825Stheravenlist<_Tp, _Alloc>::push_back(const value_type& __x) 1452227825Stheraven{ 1453227825Stheraven __node_allocator& __na = base::__node_alloc(); 1454232950Stheraven typedef __allocator_destructor<__node_allocator> _Dp; 1455232950Stheraven unique_ptr<__node, _Dp> __hold(__node_alloc_traits::allocate(__na, 1), _Dp(__na, 1)); 1456227825Stheraven __node_alloc_traits::construct(__na, _VSTD::addressof(__hold->__value_), __x); 1457227825Stheraven __link_nodes(static_cast<__node&>(base::__end_), *__hold, *__hold); 1458227825Stheraven ++base::__sz(); 1459227825Stheraven __hold.release(); 1460227825Stheraven} 1461227825Stheraven 1462227825Stheraven#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 1463227825Stheraven 1464227825Stheraventemplate <class _Tp, class _Alloc> 1465227825Stheravenvoid 1466227825Stheravenlist<_Tp, _Alloc>::push_front(value_type&& __x) 1467227825Stheraven{ 1468227825Stheraven __node_allocator& __na = base::__node_alloc(); 1469232950Stheraven typedef __allocator_destructor<__node_allocator> _Dp; 1470232950Stheraven unique_ptr<__node, _Dp> __hold(__node_alloc_traits::allocate(__na, 1), _Dp(__na, 1)); 1471227825Stheraven __node_alloc_traits::construct(__na, _VSTD::addressof(__hold->__value_), _VSTD::move(__x)); 1472227825Stheraven __link_nodes(*base::__end_.__next_, *__hold, *__hold); 1473227825Stheraven ++base::__sz(); 1474227825Stheraven __hold.release(); 1475227825Stheraven} 1476227825Stheraven 1477227825Stheraventemplate <class _Tp, class _Alloc> 1478227825Stheravenvoid 1479227825Stheravenlist<_Tp, _Alloc>::push_back(value_type&& __x) 1480227825Stheraven{ 1481227825Stheraven __node_allocator& __na = base::__node_alloc(); 1482232950Stheraven typedef __allocator_destructor<__node_allocator> _Dp; 1483232950Stheraven unique_ptr<__node, _Dp> __hold(__node_alloc_traits::allocate(__na, 1), _Dp(__na, 1)); 1484227825Stheraven __node_alloc_traits::construct(__na, _VSTD::addressof(__hold->__value_), _VSTD::move(__x)); 1485227825Stheraven __link_nodes(static_cast<__node&>(base::__end_), *__hold, *__hold); 1486227825Stheraven ++base::__sz(); 1487227825Stheraven __hold.release(); 1488227825Stheraven} 1489227825Stheraven 1490227825Stheraven#ifndef _LIBCPP_HAS_NO_VARIADICS 1491227825Stheraven 1492227825Stheraventemplate <class _Tp, class _Alloc> 1493227825Stheraventemplate <class... _Args> 1494227825Stheravenvoid 1495227825Stheravenlist<_Tp, _Alloc>::emplace_front(_Args&&... __args) 1496227825Stheraven{ 1497227825Stheraven __node_allocator& __na = base::__node_alloc(); 1498232950Stheraven typedef __allocator_destructor<__node_allocator> _Dp; 1499232950Stheraven unique_ptr<__node, _Dp> __hold(__node_alloc_traits::allocate(__na, 1), _Dp(__na, 1)); 1500227825Stheraven __node_alloc_traits::construct(__na, _VSTD::addressof(__hold->__value_), _VSTD::forward<_Args>(__args)...); 1501227825Stheraven __link_nodes(*base::__end_.__next_, *__hold, *__hold); 1502227825Stheraven ++base::__sz(); 1503227825Stheraven __hold.release(); 1504227825Stheraven} 1505227825Stheraven 1506227825Stheraventemplate <class _Tp, class _Alloc> 1507227825Stheraventemplate <class... _Args> 1508227825Stheravenvoid 1509227825Stheravenlist<_Tp, _Alloc>::emplace_back(_Args&&... __args) 1510227825Stheraven{ 1511227825Stheraven __node_allocator& __na = base::__node_alloc(); 1512232950Stheraven typedef __allocator_destructor<__node_allocator> _Dp; 1513232950Stheraven unique_ptr<__node, _Dp> __hold(__node_alloc_traits::allocate(__na, 1), _Dp(__na, 1)); 1514227825Stheraven __node_alloc_traits::construct(__na, _VSTD::addressof(__hold->__value_), _VSTD::forward<_Args>(__args)...); 1515227825Stheraven __link_nodes(static_cast<__node&>(base::__end_), *__hold, *__hold); 1516227825Stheraven ++base::__sz(); 1517227825Stheraven __hold.release(); 1518227825Stheraven} 1519227825Stheraven 1520227825Stheraventemplate <class _Tp, class _Alloc> 1521227825Stheraventemplate <class... _Args> 1522227825Stheraventypename list<_Tp, _Alloc>::iterator 1523227825Stheravenlist<_Tp, _Alloc>::emplace(const_iterator __p, _Args&&... __args) 1524227825Stheraven{ 1525249998Sdim#if _LIBCPP_DEBUG_LEVEL >= 2 1526249998Sdim _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__p) == this, 1527249998Sdim "list::emplace(iterator, args...) called with an iterator not" 1528249998Sdim " referring to this list"); 1529249998Sdim#endif 1530227825Stheraven __node_allocator& __na = base::__node_alloc(); 1531232950Stheraven typedef __allocator_destructor<__node_allocator> _Dp; 1532232950Stheraven unique_ptr<__node, _Dp> __hold(__node_alloc_traits::allocate(__na, 1), _Dp(__na, 1)); 1533227825Stheraven __hold->__prev_ = 0; 1534227825Stheraven __node_alloc_traits::construct(__na, _VSTD::addressof(__hold->__value_), _VSTD::forward<_Args>(__args)...); 1535227825Stheraven __link_nodes(const_cast<__node&>(*__p.__ptr_), *__hold, *__hold); 1536227825Stheraven ++base::__sz(); 1537227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 1538227825Stheraven return iterator(__hold.release(), this); 1539227825Stheraven#else 1540227825Stheraven return iterator(__hold.release()); 1541227825Stheraven#endif 1542227825Stheraven} 1543227825Stheraven 1544227825Stheraven#endif // _LIBCPP_HAS_NO_VARIADICS 1545227825Stheraven 1546227825Stheraventemplate <class _Tp, class _Alloc> 1547227825Stheraventypename list<_Tp, _Alloc>::iterator 1548227825Stheravenlist<_Tp, _Alloc>::insert(const_iterator __p, value_type&& __x) 1549227825Stheraven{ 1550227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 1551227825Stheraven _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__p) == this, 1552227825Stheraven "list::insert(iterator, x) called with an iterator not" 1553227825Stheraven " referring to this list"); 1554227825Stheraven#endif 1555227825Stheraven __node_allocator& __na = base::__node_alloc(); 1556232950Stheraven typedef __allocator_destructor<__node_allocator> _Dp; 1557232950Stheraven unique_ptr<__node, _Dp> __hold(__node_alloc_traits::allocate(__na, 1), _Dp(__na, 1)); 1558227825Stheraven __hold->__prev_ = 0; 1559227825Stheraven __node_alloc_traits::construct(__na, _VSTD::addressof(__hold->__value_), _VSTD::move(__x)); 1560227825Stheraven __link_nodes(const_cast<__node&>(*__p.__ptr_), *__hold, *__hold); 1561227825Stheraven ++base::__sz(); 1562227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 1563227825Stheraven return iterator(__hold.release(), this); 1564227825Stheraven#else 1565227825Stheraven return iterator(__hold.release()); 1566227825Stheraven#endif 1567227825Stheraven} 1568227825Stheraven 1569227825Stheraven#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 1570227825Stheraven 1571227825Stheraventemplate <class _Tp, class _Alloc> 1572227825Stheravenvoid 1573227825Stheravenlist<_Tp, _Alloc>::pop_front() 1574227825Stheraven{ 1575227825Stheraven _LIBCPP_ASSERT(!empty(), "list::pop_front() called with empty list"); 1576227825Stheraven __node_allocator& __na = base::__node_alloc(); 1577227825Stheraven __node& __n = *base::__end_.__next_; 1578227825Stheraven base::__unlink_nodes(__n, __n); 1579227825Stheraven --base::__sz(); 1580227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 1581227825Stheraven __c_node* __c = __get_db()->__find_c_and_lock(this); 1582227825Stheraven for (__i_node** __p = __c->end_; __p != __c->beg_; ) 1583227825Stheraven { 1584227825Stheraven --__p; 1585227825Stheraven iterator* __i = static_cast<iterator*>((*__p)->__i_); 1586227825Stheraven if (__i->__ptr_ == &__n) 1587227825Stheraven { 1588227825Stheraven (*__p)->__c_ = nullptr; 1589227825Stheraven if (--__c->end_ != __p) 1590227825Stheraven memmove(__p, __p+1, (__c->end_ - __p)*sizeof(__i_node*)); 1591227825Stheraven } 1592227825Stheraven } 1593227825Stheraven __get_db()->unlock(); 1594227825Stheraven#endif 1595227825Stheraven __node_alloc_traits::destroy(__na, _VSTD::addressof(__n.__value_)); 1596227825Stheraven __node_alloc_traits::deallocate(__na, _VSTD::addressof(__n), 1); 1597227825Stheraven} 1598227825Stheraven 1599227825Stheraventemplate <class _Tp, class _Alloc> 1600227825Stheravenvoid 1601227825Stheravenlist<_Tp, _Alloc>::pop_back() 1602227825Stheraven{ 1603227825Stheraven _LIBCPP_ASSERT(!empty(), "list::pop_front() called with empty list"); 1604227825Stheraven __node_allocator& __na = base::__node_alloc(); 1605227825Stheraven __node& __n = *base::__end_.__prev_; 1606227825Stheraven base::__unlink_nodes(__n, __n); 1607227825Stheraven --base::__sz(); 1608227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 1609227825Stheraven __c_node* __c = __get_db()->__find_c_and_lock(this); 1610227825Stheraven for (__i_node** __p = __c->end_; __p != __c->beg_; ) 1611227825Stheraven { 1612227825Stheraven --__p; 1613227825Stheraven iterator* __i = static_cast<iterator*>((*__p)->__i_); 1614227825Stheraven if (__i->__ptr_ == &__n) 1615227825Stheraven { 1616227825Stheraven (*__p)->__c_ = nullptr; 1617227825Stheraven if (--__c->end_ != __p) 1618227825Stheraven memmove(__p, __p+1, (__c->end_ - __p)*sizeof(__i_node*)); 1619227825Stheraven } 1620227825Stheraven } 1621227825Stheraven __get_db()->unlock(); 1622227825Stheraven#endif 1623227825Stheraven __node_alloc_traits::destroy(__na, _VSTD::addressof(__n.__value_)); 1624227825Stheraven __node_alloc_traits::deallocate(__na, _VSTD::addressof(__n), 1); 1625227825Stheraven} 1626227825Stheraven 1627227825Stheraventemplate <class _Tp, class _Alloc> 1628227825Stheraventypename list<_Tp, _Alloc>::iterator 1629227825Stheravenlist<_Tp, _Alloc>::erase(const_iterator __p) 1630227825Stheraven{ 1631227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 1632227825Stheraven _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__p) == this, 1633227825Stheraven "list::erase(iterator) called with an iterator not" 1634227825Stheraven " referring to this list"); 1635227825Stheraven#endif 1636249998Sdim _LIBCPP_ASSERT(__p != end(), 1637249998Sdim "list::erase(iterator) called with a non-dereferenceable iterator"); 1638227825Stheraven __node_allocator& __na = base::__node_alloc(); 1639227825Stheraven __node& __n = const_cast<__node&>(*__p.__ptr_); 1640227825Stheraven __node_pointer __r = __n.__next_; 1641227825Stheraven base::__unlink_nodes(__n, __n); 1642227825Stheraven --base::__sz(); 1643227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 1644227825Stheraven __c_node* __c = __get_db()->__find_c_and_lock(this); 1645227825Stheraven for (__i_node** __p = __c->end_; __p != __c->beg_; ) 1646227825Stheraven { 1647227825Stheraven --__p; 1648227825Stheraven iterator* __i = static_cast<iterator*>((*__p)->__i_); 1649227825Stheraven if (__i->__ptr_ == &__n) 1650227825Stheraven { 1651227825Stheraven (*__p)->__c_ = nullptr; 1652227825Stheraven if (--__c->end_ != __p) 1653227825Stheraven memmove(__p, __p+1, (__c->end_ - __p)*sizeof(__i_node*)); 1654227825Stheraven } 1655227825Stheraven } 1656227825Stheraven __get_db()->unlock(); 1657227825Stheraven#endif 1658227825Stheraven __node_alloc_traits::destroy(__na, _VSTD::addressof(__n.__value_)); 1659227825Stheraven __node_alloc_traits::deallocate(__na, _VSTD::addressof(__n), 1); 1660227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 1661227825Stheraven return iterator(__r, this); 1662227825Stheraven#else 1663227825Stheraven return iterator(__r); 1664227825Stheraven#endif 1665227825Stheraven} 1666227825Stheraven 1667227825Stheraventemplate <class _Tp, class _Alloc> 1668227825Stheraventypename list<_Tp, _Alloc>::iterator 1669227825Stheravenlist<_Tp, _Alloc>::erase(const_iterator __f, const_iterator __l) 1670227825Stheraven{ 1671227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 1672227825Stheraven _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__f) == this, 1673227825Stheraven "list::erase(iterator, iterator) called with an iterator not" 1674227825Stheraven " referring to this list"); 1675227825Stheraven#endif 1676227825Stheraven if (__f != __l) 1677227825Stheraven { 1678227825Stheraven __node_allocator& __na = base::__node_alloc(); 1679227825Stheraven base::__unlink_nodes(const_cast<__node&>(*__f.__ptr_), *__l.__ptr_->__prev_); 1680227825Stheraven while (__f != __l) 1681227825Stheraven { 1682227825Stheraven __node& __n = const_cast<__node&>(*__f.__ptr_); 1683227825Stheraven ++__f; 1684227825Stheraven --base::__sz(); 1685227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 1686227825Stheraven __c_node* __c = __get_db()->__find_c_and_lock(this); 1687227825Stheraven for (__i_node** __p = __c->end_; __p != __c->beg_; ) 1688227825Stheraven { 1689227825Stheraven --__p; 1690227825Stheraven iterator* __i = static_cast<iterator*>((*__p)->__i_); 1691227825Stheraven if (__i->__ptr_ == &__n) 1692227825Stheraven { 1693227825Stheraven (*__p)->__c_ = nullptr; 1694227825Stheraven if (--__c->end_ != __p) 1695227825Stheraven memmove(__p, __p+1, (__c->end_ - __p)*sizeof(__i_node*)); 1696227825Stheraven } 1697227825Stheraven } 1698227825Stheraven __get_db()->unlock(); 1699227825Stheraven#endif 1700227825Stheraven __node_alloc_traits::destroy(__na, _VSTD::addressof(__n.__value_)); 1701227825Stheraven __node_alloc_traits::deallocate(__na, _VSTD::addressof(__n), 1); 1702227825Stheraven } 1703227825Stheraven } 1704227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 1705227825Stheraven return iterator(const_cast<__node_pointer>(__l.__ptr_), this); 1706227825Stheraven#else 1707227825Stheraven return iterator(const_cast<__node_pointer>(__l.__ptr_)); 1708227825Stheraven#endif 1709227825Stheraven} 1710227825Stheraven 1711227825Stheraventemplate <class _Tp, class _Alloc> 1712227825Stheravenvoid 1713227825Stheravenlist<_Tp, _Alloc>::resize(size_type __n) 1714227825Stheraven{ 1715227825Stheraven if (__n < base::__sz()) 1716227825Stheraven erase(__iterator(__n), end()); 1717227825Stheraven else if (__n > base::__sz()) 1718227825Stheraven { 1719227825Stheraven __n -= base::__sz(); 1720227825Stheraven size_type __ds = 0; 1721227825Stheraven __node_allocator& __na = base::__node_alloc(); 1722232950Stheraven typedef __allocator_destructor<__node_allocator> _Dp; 1723232950Stheraven unique_ptr<__node, _Dp> __hold(__node_alloc_traits::allocate(__na, 1), _Dp(__na, 1)); 1724227825Stheraven __hold->__prev_ = 0; 1725227825Stheraven __node_alloc_traits::construct(__na, _VSTD::addressof(__hold->__value_)); 1726227825Stheraven ++__ds; 1727227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 1728227825Stheraven iterator __r = iterator(__hold.release(), this); 1729227825Stheraven#else 1730227825Stheraven iterator __r = iterator(__hold.release()); 1731227825Stheraven#endif 1732227825Stheraven iterator __e = __r; 1733227825Stheraven#ifndef _LIBCPP_NO_EXCEPTIONS 1734227825Stheraven try 1735227825Stheraven { 1736227825Stheraven#endif // _LIBCPP_NO_EXCEPTIONS 1737227825Stheraven for (--__n; __n != 0; --__n, ++__e, ++__ds) 1738227825Stheraven { 1739227825Stheraven __hold.reset(__node_alloc_traits::allocate(__na, 1)); 1740227825Stheraven __node_alloc_traits::construct(__na, _VSTD::addressof(__hold->__value_)); 1741227825Stheraven __e.__ptr_->__next_ = __hold.get(); 1742227825Stheraven __hold->__prev_ = __e.__ptr_; 1743227825Stheraven __hold.release(); 1744227825Stheraven } 1745227825Stheraven#ifndef _LIBCPP_NO_EXCEPTIONS 1746227825Stheraven } 1747227825Stheraven catch (...) 1748227825Stheraven { 1749227825Stheraven while (true) 1750227825Stheraven { 1751227825Stheraven __node_alloc_traits::destroy(__na, _VSTD::addressof(*__e)); 1752227825Stheraven __node_pointer __prev = __e.__ptr_->__prev_; 1753227825Stheraven __node_alloc_traits::deallocate(__na, __e.__ptr_, 1); 1754227825Stheraven if (__prev == 0) 1755227825Stheraven break; 1756227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 1757227825Stheraven __e = iterator(__prev, this); 1758227825Stheraven#else 1759227825Stheraven __e = iterator(__prev); 1760227825Stheraven#endif 1761227825Stheraven } 1762227825Stheraven throw; 1763227825Stheraven } 1764227825Stheraven#endif // _LIBCPP_NO_EXCEPTIONS 1765227825Stheraven __link_nodes(static_cast<__node&>(base::__end_), *__r.__ptr_, *__e.__ptr_); 1766227825Stheraven base::__sz() += __ds; 1767227825Stheraven } 1768227825Stheraven} 1769227825Stheraven 1770227825Stheraventemplate <class _Tp, class _Alloc> 1771227825Stheravenvoid 1772227825Stheravenlist<_Tp, _Alloc>::resize(size_type __n, const value_type& __x) 1773227825Stheraven{ 1774227825Stheraven if (__n < base::__sz()) 1775227825Stheraven erase(__iterator(__n), end()); 1776227825Stheraven else if (__n > base::__sz()) 1777227825Stheraven { 1778227825Stheraven __n -= base::__sz(); 1779227825Stheraven size_type __ds = 0; 1780227825Stheraven __node_allocator& __na = base::__node_alloc(); 1781232950Stheraven typedef __allocator_destructor<__node_allocator> _Dp; 1782232950Stheraven unique_ptr<__node, _Dp> __hold(__node_alloc_traits::allocate(__na, 1), _Dp(__na, 1)); 1783227825Stheraven __hold->__prev_ = 0; 1784227825Stheraven __node_alloc_traits::construct(__na, _VSTD::addressof(__hold->__value_), __x); 1785227825Stheraven ++__ds; 1786227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 1787227825Stheraven iterator __r = iterator(__hold.release(), this); 1788227825Stheraven#else 1789227825Stheraven iterator __r = iterator(__hold.release()); 1790227825Stheraven#endif 1791227825Stheraven iterator __e = __r; 1792227825Stheraven#ifndef _LIBCPP_NO_EXCEPTIONS 1793227825Stheraven try 1794227825Stheraven { 1795227825Stheraven#endif // _LIBCPP_NO_EXCEPTIONS 1796227825Stheraven for (--__n; __n != 0; --__n, ++__e, ++__ds) 1797227825Stheraven { 1798227825Stheraven __hold.reset(__node_alloc_traits::allocate(__na, 1)); 1799227825Stheraven __node_alloc_traits::construct(__na, _VSTD::addressof(__hold->__value_), __x); 1800227825Stheraven __e.__ptr_->__next_ = __hold.get(); 1801227825Stheraven __hold->__prev_ = __e.__ptr_; 1802227825Stheraven __hold.release(); 1803227825Stheraven } 1804227825Stheraven#ifndef _LIBCPP_NO_EXCEPTIONS 1805227825Stheraven } 1806227825Stheraven catch (...) 1807227825Stheraven { 1808227825Stheraven while (true) 1809227825Stheraven { 1810227825Stheraven __node_alloc_traits::destroy(__na, _VSTD::addressof(*__e)); 1811227825Stheraven __node_pointer __prev = __e.__ptr_->__prev_; 1812227825Stheraven __node_alloc_traits::deallocate(__na, __e.__ptr_, 1); 1813227825Stheraven if (__prev == 0) 1814227825Stheraven break; 1815227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 1816227825Stheraven __e = iterator(__prev, this); 1817227825Stheraven#else 1818227825Stheraven __e = iterator(__prev); 1819227825Stheraven#endif 1820227825Stheraven } 1821227825Stheraven throw; 1822227825Stheraven } 1823227825Stheraven#endif // _LIBCPP_NO_EXCEPTIONS 1824227825Stheraven __link_nodes(static_cast<__node&>(base::__end_), *__r.__ptr_, *__e.__ptr_); 1825227825Stheraven base::__sz() += __ds; 1826227825Stheraven } 1827227825Stheraven} 1828227825Stheraven 1829227825Stheraventemplate <class _Tp, class _Alloc> 1830227825Stheravenvoid 1831227825Stheravenlist<_Tp, _Alloc>::splice(const_iterator __p, list& __c) 1832227825Stheraven{ 1833227825Stheraven _LIBCPP_ASSERT(this != &__c, 1834227825Stheraven "list::splice(iterator, list) called with this == &list"); 1835227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 1836227825Stheraven _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__p) == this, 1837227825Stheraven "list::splice(iterator, list) called with an iterator not" 1838227825Stheraven " referring to this list"); 1839227825Stheraven#endif 1840227825Stheraven if (!__c.empty()) 1841227825Stheraven { 1842227825Stheraven __node& __f = *__c.__end_.__next_; 1843227825Stheraven __node& __l = *__c.__end_.__prev_; 1844227825Stheraven base::__unlink_nodes(__f, __l); 1845227825Stheraven __link_nodes(const_cast<__node&>(*__p.__ptr_), __f, __l); 1846227825Stheraven base::__sz() += __c.__sz(); 1847227825Stheraven __c.__sz() = 0; 1848227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 1849227825Stheraven __libcpp_db* __db = __get_db(); 1850227825Stheraven __c_node* __cn1 = __db->__find_c_and_lock(this); 1851227825Stheraven __c_node* __cn2 = __db->__find_c(&__c); 1852227825Stheraven for (__i_node** __p = __cn2->end_; __p != __cn2->beg_;) 1853227825Stheraven { 1854227825Stheraven --__p; 1855227825Stheraven iterator* __i = static_cast<iterator*>((*__p)->__i_); 1856227825Stheraven if (__i->__ptr_ != static_cast<__node_pointer>(&__c.__end_)) 1857227825Stheraven { 1858227825Stheraven __cn1->__add(*__p); 1859227825Stheraven (*__p)->__c_ = __cn1; 1860227825Stheraven if (--__cn2->end_ != __p) 1861227825Stheraven memmove(__p, __p+1, (__cn2->end_ - __p)*sizeof(__i_node*)); 1862227825Stheraven } 1863227825Stheraven } 1864227825Stheraven __db->unlock(); 1865227825Stheraven#endif 1866227825Stheraven } 1867227825Stheraven} 1868227825Stheraven 1869227825Stheraventemplate <class _Tp, class _Alloc> 1870227825Stheravenvoid 1871227825Stheravenlist<_Tp, _Alloc>::splice(const_iterator __p, list& __c, const_iterator __i) 1872227825Stheraven{ 1873227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 1874227825Stheraven _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__p) == this, 1875227825Stheraven "list::splice(iterator, list, iterator) called with first iterator not" 1876227825Stheraven " referring to this list"); 1877227825Stheraven _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__i) == &__c, 1878227825Stheraven "list::splice(iterator, list, iterator) called with second iterator not" 1879227825Stheraven " referring to list argument"); 1880227825Stheraven _LIBCPP_ASSERT(__get_const_db()->__dereferenceable(&__i), 1881227825Stheraven "list::splice(iterator, list, iterator) called with second iterator not" 1882227825Stheraven " derefereceable"); 1883227825Stheraven#endif 1884227825Stheraven if (__p.__ptr_ != __i.__ptr_ && __p.__ptr_ != __i.__ptr_->__next_) 1885227825Stheraven { 1886227825Stheraven __node& __f = const_cast<__node&>(*__i.__ptr_); 1887227825Stheraven base::__unlink_nodes(__f, __f); 1888227825Stheraven __link_nodes(const_cast<__node&>(*__p.__ptr_), __f, __f); 1889227825Stheraven --__c.__sz(); 1890227825Stheraven ++base::__sz(); 1891227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 1892227825Stheraven __libcpp_db* __db = __get_db(); 1893227825Stheraven __c_node* __cn1 = __db->__find_c_and_lock(this); 1894227825Stheraven __c_node* __cn2 = __db->__find_c(&__c); 1895227825Stheraven for (__i_node** __p = __cn2->end_; __p != __cn2->beg_;) 1896227825Stheraven { 1897227825Stheraven --__p; 1898227825Stheraven iterator* __j = static_cast<iterator*>((*__p)->__i_); 1899227825Stheraven if (__j->__ptr_ == &__f) 1900227825Stheraven { 1901227825Stheraven __cn1->__add(*__p); 1902227825Stheraven (*__p)->__c_ = __cn1; 1903227825Stheraven if (--__cn2->end_ != __p) 1904227825Stheraven memmove(__p, __p+1, (__cn2->end_ - __p)*sizeof(__i_node*)); 1905227825Stheraven } 1906227825Stheraven } 1907227825Stheraven __db->unlock(); 1908227825Stheraven#endif 1909227825Stheraven } 1910227825Stheraven} 1911227825Stheraven 1912227825Stheraventemplate <class _Tp, class _Alloc> 1913227825Stheravenvoid 1914227825Stheravenlist<_Tp, _Alloc>::splice(const_iterator __p, list& __c, const_iterator __f, const_iterator __l) 1915227825Stheraven{ 1916227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 1917227825Stheraven _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__p) == this, 1918227825Stheraven "list::splice(iterator, list, iterator, iterator) called with first iterator not" 1919227825Stheraven " referring to this list"); 1920227825Stheraven _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__f) == &__c, 1921227825Stheraven "list::splice(iterator, list, iterator, iterator) called with second iterator not" 1922227825Stheraven " referring to list argument"); 1923227825Stheraven if (this == &__c) 1924227825Stheraven { 1925227825Stheraven for (const_iterator __i = __f; __i != __l; ++__i) 1926227825Stheraven _LIBCPP_ASSERT(__i != __p, 1927227825Stheraven "list::splice(iterator, list, iterator, iterator)" 1928227825Stheraven " called with the first iterator within the range" 1929227825Stheraven " of the second and third iterators"); 1930227825Stheraven } 1931227825Stheraven#endif 1932227825Stheraven if (__f != __l) 1933227825Stheraven { 1934227825Stheraven if (this != &__c) 1935227825Stheraven { 1936227825Stheraven size_type __s = _VSTD::distance(__f, __l); 1937227825Stheraven __c.__sz() -= __s; 1938227825Stheraven base::__sz() += __s; 1939227825Stheraven } 1940227825Stheraven __node& __first = const_cast<__node&>(*__f.__ptr_); 1941227825Stheraven --__l; 1942227825Stheraven __node& __last = const_cast<__node&>(*__l.__ptr_); 1943227825Stheraven base::__unlink_nodes(__first, __last); 1944227825Stheraven __link_nodes(const_cast<__node&>(*__p.__ptr_), __first, __last); 1945227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 1946227825Stheraven __libcpp_db* __db = __get_db(); 1947227825Stheraven __c_node* __cn1 = __db->__find_c_and_lock(this); 1948227825Stheraven __c_node* __cn2 = __db->__find_c(&__c); 1949227825Stheraven for (__i_node** __p = __cn2->end_; __p != __cn2->beg_;) 1950227825Stheraven { 1951227825Stheraven --__p; 1952227825Stheraven iterator* __j = static_cast<iterator*>((*__p)->__i_); 1953227825Stheraven for (__node_pointer __k = const_cast<__node_pointer>(__f.__ptr_); 1954227825Stheraven __k != __l.__ptr_; __k = __k->__next_) 1955227825Stheraven { 1956227825Stheraven if (__j->__ptr_ == __k) 1957227825Stheraven { 1958227825Stheraven __cn1->__add(*__p); 1959227825Stheraven (*__p)->__c_ = __cn1; 1960227825Stheraven if (--__cn2->end_ != __p) 1961227825Stheraven memmove(__p, __p+1, (__cn2->end_ - __p)*sizeof(__i_node*)); 1962227825Stheraven } 1963227825Stheraven } 1964227825Stheraven } 1965227825Stheraven __db->unlock(); 1966227825Stheraven#endif 1967227825Stheraven } 1968227825Stheraven} 1969227825Stheraven 1970227825Stheraventemplate <class _Tp, class _Alloc> 1971227825Stheravenvoid 1972227825Stheravenlist<_Tp, _Alloc>::remove(const value_type& __x) 1973227825Stheraven{ 1974227825Stheraven for (iterator __i = begin(), __e = end(); __i != __e;) 1975227825Stheraven { 1976227825Stheraven if (*__i == __x) 1977227825Stheraven { 1978227825Stheraven iterator __j = _VSTD::next(__i); 1979227825Stheraven for (; __j != __e && *__j == __x; ++__j) 1980227825Stheraven ; 1981227825Stheraven __i = erase(__i, __j); 1982227825Stheraven } 1983227825Stheraven else 1984227825Stheraven ++__i; 1985227825Stheraven } 1986227825Stheraven} 1987227825Stheraven 1988227825Stheraventemplate <class _Tp, class _Alloc> 1989227825Stheraventemplate <class _Pred> 1990227825Stheravenvoid 1991227825Stheravenlist<_Tp, _Alloc>::remove_if(_Pred __pred) 1992227825Stheraven{ 1993227825Stheraven for (iterator __i = begin(), __e = end(); __i != __e;) 1994227825Stheraven { 1995227825Stheraven if (__pred(*__i)) 1996227825Stheraven { 1997227825Stheraven iterator __j = _VSTD::next(__i); 1998227825Stheraven for (; __j != __e && __pred(*__j); ++__j) 1999227825Stheraven ; 2000227825Stheraven __i = erase(__i, __j); 2001227825Stheraven } 2002227825Stheraven else 2003227825Stheraven ++__i; 2004227825Stheraven } 2005227825Stheraven} 2006227825Stheraven 2007227825Stheraventemplate <class _Tp, class _Alloc> 2008227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 2009227825Stheravenvoid 2010227825Stheravenlist<_Tp, _Alloc>::unique() 2011227825Stheraven{ 2012227825Stheraven unique(__equal_to<value_type>()); 2013227825Stheraven} 2014227825Stheraven 2015227825Stheraventemplate <class _Tp, class _Alloc> 2016227825Stheraventemplate <class _BinaryPred> 2017227825Stheravenvoid 2018227825Stheravenlist<_Tp, _Alloc>::unique(_BinaryPred __binary_pred) 2019227825Stheraven{ 2020227825Stheraven for (iterator __i = begin(), __e = end(); __i != __e;) 2021227825Stheraven { 2022227825Stheraven iterator __j = _VSTD::next(__i); 2023227825Stheraven for (; __j != __e && __binary_pred(*__i, *__j); ++__j) 2024227825Stheraven ; 2025227825Stheraven if (++__i != __j) 2026227825Stheraven __i = erase(__i, __j); 2027227825Stheraven } 2028227825Stheraven} 2029227825Stheraven 2030227825Stheraventemplate <class _Tp, class _Alloc> 2031227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 2032227825Stheravenvoid 2033227825Stheravenlist<_Tp, _Alloc>::merge(list& __c) 2034227825Stheraven{ 2035227825Stheraven merge(__c, __less<value_type>()); 2036227825Stheraven} 2037227825Stheraven 2038227825Stheraventemplate <class _Tp, class _Alloc> 2039227825Stheraventemplate <class _Comp> 2040227825Stheravenvoid 2041227825Stheravenlist<_Tp, _Alloc>::merge(list& __c, _Comp __comp) 2042227825Stheraven{ 2043227825Stheraven if (this != &__c) 2044227825Stheraven { 2045227825Stheraven iterator __f1 = begin(); 2046227825Stheraven iterator __e1 = end(); 2047227825Stheraven iterator __f2 = __c.begin(); 2048227825Stheraven iterator __e2 = __c.end(); 2049227825Stheraven while (__f1 != __e1 && __f2 != __e2) 2050227825Stheraven { 2051227825Stheraven if (__comp(*__f2, *__f1)) 2052227825Stheraven { 2053227825Stheraven size_type __ds = 1; 2054227825Stheraven iterator __m2 = _VSTD::next(__f2); 2055227825Stheraven for (; __m2 != __e2 && __comp(*__m2, *__f1); ++__m2, ++__ds) 2056227825Stheraven ; 2057227825Stheraven base::__sz() += __ds; 2058227825Stheraven __c.__sz() -= __ds; 2059227825Stheraven __node& __f = *__f2.__ptr_; 2060227825Stheraven __node& __l = *__m2.__ptr_->__prev_; 2061227825Stheraven __f2 = __m2; 2062227825Stheraven base::__unlink_nodes(__f, __l); 2063227825Stheraven __m2 = _VSTD::next(__f1); 2064227825Stheraven __link_nodes(*__f1.__ptr_, __f, __l); 2065227825Stheraven __f1 = __m2; 2066227825Stheraven } 2067227825Stheraven else 2068227825Stheraven ++__f1; 2069227825Stheraven } 2070227825Stheraven splice(__e1, __c); 2071227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 2072227825Stheraven __libcpp_db* __db = __get_db(); 2073227825Stheraven __c_node* __cn1 = __db->__find_c_and_lock(this); 2074227825Stheraven __c_node* __cn2 = __db->__find_c(&__c); 2075227825Stheraven for (__i_node** __p = __cn2->end_; __p != __cn2->beg_;) 2076227825Stheraven { 2077227825Stheraven --__p; 2078227825Stheraven iterator* __i = static_cast<iterator*>((*__p)->__i_); 2079227825Stheraven if (__i->__ptr_ != static_cast<__node_pointer>(&__c.__end_)) 2080227825Stheraven { 2081227825Stheraven __cn1->__add(*__p); 2082227825Stheraven (*__p)->__c_ = __cn1; 2083227825Stheraven if (--__cn2->end_ != __p) 2084227825Stheraven memmove(__p, __p+1, (__cn2->end_ - __p)*sizeof(__i_node*)); 2085227825Stheraven } 2086227825Stheraven } 2087227825Stheraven __db->unlock(); 2088227825Stheraven#endif 2089227825Stheraven } 2090227825Stheraven} 2091227825Stheraven 2092227825Stheraventemplate <class _Tp, class _Alloc> 2093227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 2094227825Stheravenvoid 2095227825Stheravenlist<_Tp, _Alloc>::sort() 2096227825Stheraven{ 2097227825Stheraven sort(__less<value_type>()); 2098227825Stheraven} 2099227825Stheraven 2100227825Stheraventemplate <class _Tp, class _Alloc> 2101227825Stheraventemplate <class _Comp> 2102227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 2103227825Stheravenvoid 2104227825Stheravenlist<_Tp, _Alloc>::sort(_Comp __comp) 2105227825Stheraven{ 2106227825Stheraven __sort(begin(), end(), base::__sz(), __comp); 2107227825Stheraven} 2108227825Stheraven 2109227825Stheraventemplate <class _Tp, class _Alloc> 2110227825Stheraventemplate <class _Comp> 2111227825Stheraventypename list<_Tp, _Alloc>::iterator 2112227825Stheravenlist<_Tp, _Alloc>::__sort(iterator __f1, iterator __e2, size_type __n, _Comp& __comp) 2113227825Stheraven{ 2114227825Stheraven switch (__n) 2115227825Stheraven { 2116227825Stheraven case 0: 2117227825Stheraven case 1: 2118227825Stheraven return __f1; 2119227825Stheraven case 2: 2120227825Stheraven if (__comp(*--__e2, *__f1)) 2121227825Stheraven { 2122227825Stheraven __node& __f = *__e2.__ptr_; 2123227825Stheraven base::__unlink_nodes(__f, __f); 2124227825Stheraven __link_nodes(*__f1.__ptr_, __f, __f); 2125227825Stheraven return __e2; 2126227825Stheraven } 2127227825Stheraven return __f1; 2128227825Stheraven } 2129227825Stheraven size_type __n2 = __n / 2; 2130227825Stheraven iterator __e1 = _VSTD::next(__f1, __n2); 2131227825Stheraven iterator __r = __f1 = __sort(__f1, __e1, __n2, __comp); 2132227825Stheraven iterator __f2 = __e1 = __sort(__e1, __e2, __n - __n2, __comp); 2133227825Stheraven if (__comp(*__f2, *__f1)) 2134227825Stheraven { 2135227825Stheraven iterator __m2 = _VSTD::next(__f2); 2136227825Stheraven for (; __m2 != __e2 && __comp(*__m2, *__f1); ++__m2) 2137227825Stheraven ; 2138227825Stheraven __node& __f = *__f2.__ptr_; 2139227825Stheraven __node& __l = *__m2.__ptr_->__prev_; 2140227825Stheraven __r = __f2; 2141227825Stheraven __e1 = __f2 = __m2; 2142227825Stheraven base::__unlink_nodes(__f, __l); 2143227825Stheraven __m2 = _VSTD::next(__f1); 2144227825Stheraven __link_nodes(*__f1.__ptr_, __f, __l); 2145227825Stheraven __f1 = __m2; 2146227825Stheraven } 2147227825Stheraven else 2148227825Stheraven ++__f1; 2149227825Stheraven while (__f1 != __e1 && __f2 != __e2) 2150227825Stheraven { 2151227825Stheraven if (__comp(*__f2, *__f1)) 2152227825Stheraven { 2153227825Stheraven iterator __m2 = _VSTD::next(__f2); 2154227825Stheraven for (; __m2 != __e2 && __comp(*__m2, *__f1); ++__m2) 2155227825Stheraven ; 2156227825Stheraven __node& __f = *__f2.__ptr_; 2157227825Stheraven __node& __l = *__m2.__ptr_->__prev_; 2158227825Stheraven if (__e1 == __f2) 2159227825Stheraven __e1 = __m2; 2160227825Stheraven __f2 = __m2; 2161227825Stheraven base::__unlink_nodes(__f, __l); 2162227825Stheraven __m2 = _VSTD::next(__f1); 2163227825Stheraven __link_nodes(*__f1.__ptr_, __f, __l); 2164227825Stheraven __f1 = __m2; 2165227825Stheraven } 2166227825Stheraven else 2167227825Stheraven ++__f1; 2168227825Stheraven } 2169227825Stheraven return __r; 2170227825Stheraven} 2171227825Stheraven 2172227825Stheraventemplate <class _Tp, class _Alloc> 2173227825Stheravenvoid 2174227825Stheravenlist<_Tp, _Alloc>::reverse() _NOEXCEPT 2175227825Stheraven{ 2176227825Stheraven if (base::__sz() > 1) 2177227825Stheraven { 2178227825Stheraven iterator __e = end(); 2179227825Stheraven for (iterator __i = begin(); __i.__ptr_ != __e.__ptr_;) 2180227825Stheraven { 2181227825Stheraven _VSTD::swap(__i.__ptr_->__prev_, __i.__ptr_->__next_); 2182227825Stheraven __i.__ptr_ = __i.__ptr_->__prev_; 2183227825Stheraven } 2184227825Stheraven _VSTD::swap(__e.__ptr_->__prev_, __e.__ptr_->__next_); 2185227825Stheraven } 2186227825Stheraven} 2187227825Stheraven 2188227825Stheraventemplate <class _Tp, class _Alloc> 2189227825Stheravenbool 2190227825Stheravenlist<_Tp, _Alloc>::__invariants() const 2191227825Stheraven{ 2192227825Stheraven return size() == _VSTD::distance(begin(), end()); 2193227825Stheraven} 2194227825Stheraven 2195227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 2196227825Stheraven 2197227825Stheraventemplate <class _Tp, class _Alloc> 2198227825Stheravenbool 2199227825Stheravenlist<_Tp, _Alloc>::__dereferenceable(const const_iterator* __i) const 2200227825Stheraven{ 2201227825Stheraven return __i->__ptr_ != &this->__end_; 2202227825Stheraven} 2203227825Stheraven 2204227825Stheraventemplate <class _Tp, class _Alloc> 2205227825Stheravenbool 2206227825Stheravenlist<_Tp, _Alloc>::__decrementable(const const_iterator* __i) const 2207227825Stheraven{ 2208227825Stheraven return !empty() && __i->__ptr_ != base::__end_.__next_; 2209227825Stheraven} 2210227825Stheraven 2211227825Stheraventemplate <class _Tp, class _Alloc> 2212227825Stheravenbool 2213227825Stheravenlist<_Tp, _Alloc>::__addable(const const_iterator* __i, ptrdiff_t __n) const 2214227825Stheraven{ 2215227825Stheraven return false; 2216227825Stheraven} 2217227825Stheraven 2218227825Stheraventemplate <class _Tp, class _Alloc> 2219227825Stheravenbool 2220227825Stheravenlist<_Tp, _Alloc>::__subscriptable(const const_iterator* __i, ptrdiff_t __n) const 2221227825Stheraven{ 2222227825Stheraven return false; 2223227825Stheraven} 2224227825Stheraven 2225227825Stheraven#endif // _LIBCPP_DEBUG_LEVEL >= 2 2226227825Stheraven 2227227825Stheraventemplate <class _Tp, class _Alloc> 2228227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 2229227825Stheravenbool 2230227825Stheravenoperator==(const list<_Tp, _Alloc>& __x, const list<_Tp, _Alloc>& __y) 2231227825Stheraven{ 2232227825Stheraven return __x.size() == __y.size() && _VSTD::equal(__x.begin(), __x.end(), __y.begin()); 2233227825Stheraven} 2234227825Stheraven 2235227825Stheraventemplate <class _Tp, class _Alloc> 2236227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 2237227825Stheravenbool 2238227825Stheravenoperator< (const list<_Tp, _Alloc>& __x, const list<_Tp, _Alloc>& __y) 2239227825Stheraven{ 2240227825Stheraven return _VSTD::lexicographical_compare(__x.begin(), __x.end(), __y.begin(), __y.end()); 2241227825Stheraven} 2242227825Stheraven 2243227825Stheraventemplate <class _Tp, class _Alloc> 2244227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 2245227825Stheravenbool 2246227825Stheravenoperator!=(const list<_Tp, _Alloc>& __x, const list<_Tp, _Alloc>& __y) 2247227825Stheraven{ 2248227825Stheraven return !(__x == __y); 2249227825Stheraven} 2250227825Stheraven 2251227825Stheraventemplate <class _Tp, class _Alloc> 2252227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 2253227825Stheravenbool 2254227825Stheravenoperator> (const list<_Tp, _Alloc>& __x, const list<_Tp, _Alloc>& __y) 2255227825Stheraven{ 2256227825Stheraven return __y < __x; 2257227825Stheraven} 2258227825Stheraven 2259227825Stheraventemplate <class _Tp, class _Alloc> 2260227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 2261227825Stheravenbool 2262227825Stheravenoperator>=(const list<_Tp, _Alloc>& __x, const list<_Tp, _Alloc>& __y) 2263227825Stheraven{ 2264227825Stheraven return !(__x < __y); 2265227825Stheraven} 2266227825Stheraven 2267227825Stheraventemplate <class _Tp, class _Alloc> 2268227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 2269227825Stheravenbool 2270227825Stheravenoperator<=(const list<_Tp, _Alloc>& __x, const list<_Tp, _Alloc>& __y) 2271227825Stheraven{ 2272227825Stheraven return !(__y < __x); 2273227825Stheraven} 2274227825Stheraven 2275227825Stheraventemplate <class _Tp, class _Alloc> 2276227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 2277227825Stheravenvoid 2278227825Stheravenswap(list<_Tp, _Alloc>& __x, list<_Tp, _Alloc>& __y) 2279227825Stheraven _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y))) 2280227825Stheraven{ 2281227825Stheraven __x.swap(__y); 2282227825Stheraven} 2283227825Stheraven 2284227825Stheraven_LIBCPP_END_NAMESPACE_STD 2285227825Stheraven 2286227825Stheraven#endif // _LIBCPP_LIST 2287