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