list revision 262801
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); 43262801Sdim explicit list(size_type n, const allocator_type& a); // C++14 44227825Stheraven list(size_type n, const value_type& value); 45227825Stheraven list(size_type n, const value_type& value, const allocator_type& a); 46227825Stheraven template <class Iter> 47227825Stheraven list(Iter first, Iter last); 48227825Stheraven template <class Iter> 49227825Stheraven list(Iter first, Iter last, const allocator_type& a); 50227825Stheraven list(const list& x); 51227825Stheraven list(const list&, const allocator_type& a); 52227825Stheraven list(list&& x) 53227825Stheraven noexcept(is_nothrow_move_constructible<allocator_type>::value); 54227825Stheraven list(list&&, const allocator_type& a); 55227825Stheraven list(initializer_list<value_type>); 56227825Stheraven list(initializer_list<value_type>, const allocator_type& a); 57227825Stheraven 58227825Stheraven ~list(); 59227825Stheraven 60227825Stheraven list& operator=(const list& x); 61227825Stheraven list& operator=(list&& x) 62227825Stheraven noexcept( 63227825Stheraven allocator_type::propagate_on_container_move_assignment::value && 64227825Stheraven is_nothrow_move_assignable<allocator_type>::value); 65227825Stheraven list& operator=(initializer_list<value_type>); 66227825Stheraven template <class Iter> 67227825Stheraven void assign(Iter first, Iter last); 68227825Stheraven void assign(size_type n, const value_type& t); 69227825Stheraven void assign(initializer_list<value_type>); 70227825Stheraven 71227825Stheraven allocator_type get_allocator() const noexcept; 72227825Stheraven 73227825Stheraven iterator begin() noexcept; 74227825Stheraven const_iterator begin() const noexcept; 75227825Stheraven iterator end() noexcept; 76227825Stheraven const_iterator end() const noexcept; 77227825Stheraven reverse_iterator rbegin() noexcept; 78227825Stheraven const_reverse_iterator rbegin() const noexcept; 79227825Stheraven reverse_iterator rend() noexcept; 80227825Stheraven const_reverse_iterator rend() const noexcept; 81227825Stheraven const_iterator cbegin() const noexcept; 82227825Stheraven const_iterator cend() const noexcept; 83227825Stheraven const_reverse_iterator crbegin() const noexcept; 84227825Stheraven const_reverse_iterator crend() const noexcept; 85227825Stheraven 86227825Stheraven reference front(); 87227825Stheraven const_reference front() const; 88227825Stheraven reference back(); 89227825Stheraven const_reference back() const; 90227825Stheraven 91227825Stheraven bool empty() const noexcept; 92227825Stheraven size_type size() const noexcept; 93227825Stheraven size_type max_size() const noexcept; 94227825Stheraven 95227825Stheraven template <class... Args> 96227825Stheraven void emplace_front(Args&&... args); 97227825Stheraven void pop_front(); 98227825Stheraven template <class... Args> 99227825Stheraven void emplace_back(Args&&... args); 100227825Stheraven void pop_back(); 101227825Stheraven void push_front(const value_type& x); 102227825Stheraven void push_front(value_type&& x); 103227825Stheraven void push_back(const value_type& x); 104227825Stheraven void push_back(value_type&& x); 105227825Stheraven template <class... Args> 106227825Stheraven iterator emplace(const_iterator position, Args&&... args); 107227825Stheraven iterator insert(const_iterator position, const value_type& x); 108227825Stheraven iterator insert(const_iterator position, value_type&& x); 109227825Stheraven iterator insert(const_iterator position, size_type n, const value_type& x); 110227825Stheraven template <class Iter> 111227825Stheraven iterator insert(const_iterator position, Iter first, Iter last); 112227825Stheraven iterator insert(const_iterator position, initializer_list<value_type> il); 113227825Stheraven 114227825Stheraven iterator erase(const_iterator position); 115227825Stheraven iterator erase(const_iterator position, const_iterator last); 116227825Stheraven 117227825Stheraven void resize(size_type sz); 118227825Stheraven void resize(size_type sz, const value_type& c); 119227825Stheraven 120227825Stheraven void swap(list&) 121227825Stheraven noexcept(!allocator_type::propagate_on_container_swap::value || 122227825Stheraven __is_nothrow_swappable<allocator_type>::value); 123227825Stheraven void clear() noexcept; 124227825Stheraven 125227825Stheraven void splice(const_iterator position, list& x); 126227825Stheraven void splice(const_iterator position, list&& x); 127227825Stheraven void splice(const_iterator position, list& x, const_iterator i); 128227825Stheraven void splice(const_iterator position, list&& x, const_iterator i); 129227825Stheraven void splice(const_iterator position, list& x, const_iterator first, 130227825Stheraven const_iterator last); 131227825Stheraven void splice(const_iterator position, list&& x, const_iterator first, 132227825Stheraven const_iterator last); 133227825Stheraven 134227825Stheraven void remove(const value_type& value); 135227825Stheraven template <class Pred> void remove_if(Pred pred); 136227825Stheraven void unique(); 137227825Stheraven template <class BinaryPredicate> 138227825Stheraven void unique(BinaryPredicate binary_pred); 139227825Stheraven void merge(list& x); 140227825Stheraven void merge(list&& x); 141227825Stheraven template <class Compare> 142227825Stheraven void merge(list& x, Compare comp); 143227825Stheraven template <class Compare> 144227825Stheraven void merge(list&& x, Compare comp); 145227825Stheraven void sort(); 146227825Stheraven template <class Compare> 147227825Stheraven void sort(Compare comp); 148227825Stheraven void reverse() noexcept; 149227825Stheraven}; 150227825Stheraven 151227825Stheraventemplate <class T, class Alloc> 152227825Stheraven bool operator==(const list<T,Alloc>& x, const list<T,Alloc>& y); 153227825Stheraventemplate <class T, class Alloc> 154227825Stheraven bool operator< (const list<T,Alloc>& x, const list<T,Alloc>& y); 155227825Stheraventemplate <class T, class Alloc> 156227825Stheraven bool operator!=(const list<T,Alloc>& x, const list<T,Alloc>& y); 157227825Stheraventemplate <class T, class Alloc> 158227825Stheraven bool operator> (const list<T,Alloc>& x, const list<T,Alloc>& y); 159227825Stheraventemplate <class T, class Alloc> 160227825Stheraven bool operator>=(const list<T,Alloc>& x, const list<T,Alloc>& y); 161227825Stheraventemplate <class T, class Alloc> 162227825Stheraven bool operator<=(const list<T,Alloc>& x, const list<T,Alloc>& y); 163227825Stheraven 164227825Stheraventemplate <class T, class Alloc> 165227825Stheraven void swap(list<T,Alloc>& x, list<T,Alloc>& y) 166227825Stheraven noexcept(noexcept(x.swap(y))); 167227825Stheraven 168227825Stheraven} // std 169227825Stheraven 170227825Stheraven*/ 171227825Stheraven 172227825Stheraven#include <__config> 173227825Stheraven 174227825Stheraven#include <memory> 175227825Stheraven#include <limits> 176227825Stheraven#include <initializer_list> 177227825Stheraven#include <iterator> 178227825Stheraven#include <algorithm> 179227825Stheraven 180232950Stheraven#include <__undef_min_max> 181232950Stheraven 182262801Sdim#ifdef _LIBCPP_DEBUG 183262801Sdim# include <__debug> 184262801Sdim#else 185262801Sdim# define _LIBCPP_ASSERT(x, m) ((void)0) 186262801Sdim#endif 187262801Sdim 188227825Stheraven#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) 189227825Stheraven#pragma GCC system_header 190227825Stheraven#endif 191227825Stheraven 192227825Stheraven_LIBCPP_BEGIN_NAMESPACE_STD 193227825Stheraven 194227825Stheraventemplate <class _Tp, class _VoidPtr> struct __list_node; 195227825Stheraven 196227825Stheraventemplate <class _Tp, class _VoidPtr> 197227825Stheravenstruct __list_node_base 198227825Stheraven{ 199227825Stheraven typedef typename pointer_traits<_VoidPtr>::template 200227825Stheraven#ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES 201227825Stheraven rebind<__list_node<_Tp, _VoidPtr> > pointer; 202227825Stheraven#else 203227825Stheraven rebind<__list_node<_Tp, _VoidPtr> >::other pointer; 204227825Stheraven#endif 205227825Stheraven 206253159Stheraven typedef typename pointer_traits<_VoidPtr>::template 207253159Stheraven#ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES 208253159Stheraven rebind<__list_node_base> __base_pointer; 209253159Stheraven#else 210253159Stheraven rebind<__list_node_base>::other __base_pointer; 211253159Stheraven#endif 212253159Stheraven 213227825Stheraven pointer __prev_; 214227825Stheraven pointer __next_; 215227825Stheraven 216227825Stheraven _LIBCPP_INLINE_VISIBILITY 217227825Stheraven __list_node_base() 218253159Stheraven : __prev_(static_cast<pointer>(pointer_traits<__base_pointer>::pointer_to(*this))), 219253159Stheraven __next_(static_cast<pointer>(pointer_traits<__base_pointer>::pointer_to(*this))) 220227825Stheraven {} 221227825Stheraven}; 222227825Stheraven 223227825Stheraventemplate <class _Tp, class _VoidPtr> 224227825Stheravenstruct __list_node 225227825Stheraven : public __list_node_base<_Tp, _VoidPtr> 226227825Stheraven{ 227227825Stheraven _Tp __value_; 228227825Stheraven}; 229227825Stheraven 230262801Sdimtemplate <class _Tp, class _Alloc> class _LIBCPP_TYPE_VIS_ONLY list; 231227825Stheraventemplate <class _Tp, class _Alloc> class __list_imp; 232262801Sdimtemplate <class _Tp, class _VoidPtr> class _LIBCPP_TYPE_VIS_ONLY __list_const_iterator; 233227825Stheraven 234227825Stheraventemplate <class _Tp, class _VoidPtr> 235262801Sdimclass _LIBCPP_TYPE_VIS_ONLY __list_iterator 236227825Stheraven{ 237227825Stheraven typedef typename pointer_traits<_VoidPtr>::template 238227825Stheraven#ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES 239227825Stheraven rebind<__list_node<_Tp, _VoidPtr> > __node_pointer; 240227825Stheraven#else 241227825Stheraven rebind<__list_node<_Tp, _VoidPtr> >::other __node_pointer; 242227825Stheraven#endif 243227825Stheraven 244227825Stheraven __node_pointer __ptr_; 245227825Stheraven 246227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 247227825Stheraven _LIBCPP_INLINE_VISIBILITY 248227825Stheraven explicit __list_iterator(__node_pointer __p, const void* __c) _NOEXCEPT 249227825Stheraven : __ptr_(__p) 250227825Stheraven { 251227825Stheraven __get_db()->__insert_ic(this, __c); 252227825Stheraven } 253227825Stheraven#else 254227825Stheraven _LIBCPP_INLINE_VISIBILITY 255227825Stheraven explicit __list_iterator(__node_pointer __p) _NOEXCEPT : __ptr_(__p) {} 256227825Stheraven#endif 257227825Stheraven 258227825Stheraven 259227825Stheraven 260227825Stheraven template<class, class> friend class list; 261227825Stheraven template<class, class> friend class __list_imp; 262227825Stheraven template<class, class> friend class __list_const_iterator; 263227825Stheravenpublic: 264227825Stheraven typedef bidirectional_iterator_tag iterator_category; 265227825Stheraven typedef _Tp value_type; 266227825Stheraven typedef value_type& reference; 267227825Stheraven typedef typename pointer_traits<_VoidPtr>::template 268227825Stheraven#ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES 269227825Stheraven rebind<value_type> 270227825Stheraven#else 271227825Stheraven rebind<value_type>::other 272227825Stheraven#endif 273227825Stheraven pointer; 274227825Stheraven typedef typename pointer_traits<pointer>::difference_type difference_type; 275227825Stheraven 276227825Stheraven _LIBCPP_INLINE_VISIBILITY 277262801Sdim __list_iterator() _NOEXCEPT : __ptr_(nullptr) 278227825Stheraven { 279227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 280227825Stheraven __get_db()->__insert_i(this); 281227825Stheraven#endif 282227825Stheraven } 283227825Stheraven 284227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 285227825Stheraven 286227825Stheraven _LIBCPP_INLINE_VISIBILITY 287227825Stheraven __list_iterator(const __list_iterator& __p) 288227825Stheraven : __ptr_(__p.__ptr_) 289227825Stheraven { 290227825Stheraven __get_db()->__iterator_copy(this, &__p); 291227825Stheraven } 292227825Stheraven 293227825Stheraven _LIBCPP_INLINE_VISIBILITY 294227825Stheraven ~__list_iterator() 295227825Stheraven { 296227825Stheraven __get_db()->__erase_i(this); 297227825Stheraven } 298227825Stheraven 299227825Stheraven _LIBCPP_INLINE_VISIBILITY 300227825Stheraven __list_iterator& operator=(const __list_iterator& __p) 301227825Stheraven { 302227825Stheraven if (this != &__p) 303227825Stheraven { 304227825Stheraven __get_db()->__iterator_copy(this, &__p); 305227825Stheraven __ptr_ = __p.__ptr_; 306227825Stheraven } 307227825Stheraven return *this; 308227825Stheraven } 309227825Stheraven 310227825Stheraven#endif // _LIBCPP_DEBUG_LEVEL >= 2 311227825Stheraven 312227825Stheraven _LIBCPP_INLINE_VISIBILITY 313227825Stheraven reference operator*() const 314227825Stheraven { 315227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 316227825Stheraven _LIBCPP_ASSERT(__get_const_db()->__dereferenceable(this), 317227825Stheraven "Attempted to dereference a non-dereferenceable list::iterator"); 318227825Stheraven#endif 319227825Stheraven return __ptr_->__value_; 320227825Stheraven } 321227825Stheraven _LIBCPP_INLINE_VISIBILITY 322253159Stheraven pointer operator->() const 323253159Stheraven { 324253159Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 325253159Stheraven _LIBCPP_ASSERT(__get_const_db()->__dereferenceable(this), 326253159Stheraven "Attempted to dereference a non-dereferenceable list::iterator"); 327253159Stheraven#endif 328253159Stheraven return pointer_traits<pointer>::pointer_to(__ptr_->__value_); 329253159Stheraven } 330227825Stheraven 331227825Stheraven _LIBCPP_INLINE_VISIBILITY 332227825Stheraven __list_iterator& operator++() 333227825Stheraven { 334227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 335227825Stheraven _LIBCPP_ASSERT(__get_const_db()->__dereferenceable(this), 336227825Stheraven "Attempted to increment non-incrementable list::iterator"); 337227825Stheraven#endif 338227825Stheraven __ptr_ = __ptr_->__next_; 339227825Stheraven return *this; 340227825Stheraven } 341227825Stheraven _LIBCPP_INLINE_VISIBILITY 342227825Stheraven __list_iterator operator++(int) {__list_iterator __t(*this); ++(*this); return __t;} 343227825Stheraven 344227825Stheraven _LIBCPP_INLINE_VISIBILITY 345227825Stheraven __list_iterator& operator--() 346227825Stheraven { 347227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 348227825Stheraven _LIBCPP_ASSERT(__get_const_db()->__decrementable(this), 349227825Stheraven "Attempted to decrement non-decrementable list::iterator"); 350227825Stheraven#endif 351227825Stheraven __ptr_ = __ptr_->__prev_; 352227825Stheraven return *this; 353227825Stheraven } 354227825Stheraven _LIBCPP_INLINE_VISIBILITY 355227825Stheraven __list_iterator operator--(int) {__list_iterator __t(*this); --(*this); return __t;} 356227825Stheraven 357227825Stheraven friend _LIBCPP_INLINE_VISIBILITY 358227825Stheraven bool operator==(const __list_iterator& __x, const __list_iterator& __y) 359227825Stheraven { 360227825Stheraven return __x.__ptr_ == __y.__ptr_; 361227825Stheraven } 362227825Stheraven friend _LIBCPP_INLINE_VISIBILITY 363227825Stheraven bool operator!=(const __list_iterator& __x, const __list_iterator& __y) 364227825Stheraven {return !(__x == __y);} 365227825Stheraven}; 366227825Stheraven 367227825Stheraventemplate <class _Tp, class _VoidPtr> 368262801Sdimclass _LIBCPP_TYPE_VIS_ONLY __list_const_iterator 369227825Stheraven{ 370227825Stheraven typedef typename pointer_traits<_VoidPtr>::template 371227825Stheraven#ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES 372253159Stheraven rebind<__list_node<_Tp, _VoidPtr> > __node_pointer; 373227825Stheraven#else 374253159Stheraven rebind<__list_node<_Tp, _VoidPtr> >::other __node_pointer; 375227825Stheraven#endif 376227825Stheraven 377227825Stheraven __node_pointer __ptr_; 378227825Stheraven 379227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 380227825Stheraven _LIBCPP_INLINE_VISIBILITY 381227825Stheraven explicit __list_const_iterator(__node_pointer __p, const void* __c) _NOEXCEPT 382227825Stheraven : __ptr_(__p) 383227825Stheraven { 384227825Stheraven __get_db()->__insert_ic(this, __c); 385227825Stheraven } 386227825Stheraven#else 387227825Stheraven _LIBCPP_INLINE_VISIBILITY 388227825Stheraven explicit __list_const_iterator(__node_pointer __p) _NOEXCEPT : __ptr_(__p) {} 389227825Stheraven#endif 390227825Stheraven 391227825Stheraven template<class, class> friend class list; 392227825Stheraven template<class, class> friend class __list_imp; 393227825Stheravenpublic: 394227825Stheraven typedef bidirectional_iterator_tag iterator_category; 395227825Stheraven typedef _Tp value_type; 396227825Stheraven typedef const value_type& reference; 397227825Stheraven typedef typename pointer_traits<_VoidPtr>::template 398227825Stheraven#ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES 399227825Stheraven rebind<const value_type> 400227825Stheraven#else 401227825Stheraven rebind<const value_type>::other 402227825Stheraven#endif 403227825Stheraven pointer; 404227825Stheraven typedef typename pointer_traits<pointer>::difference_type difference_type; 405227825Stheraven 406227825Stheraven _LIBCPP_INLINE_VISIBILITY 407262801Sdim __list_const_iterator() _NOEXCEPT : __ptr_(nullptr) 408227825Stheraven { 409227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 410227825Stheraven __get_db()->__insert_i(this); 411227825Stheraven#endif 412227825Stheraven } 413227825Stheraven _LIBCPP_INLINE_VISIBILITY 414249998Sdim __list_const_iterator(const __list_iterator<_Tp, _VoidPtr>& __p) _NOEXCEPT 415227825Stheraven : __ptr_(__p.__ptr_) 416227825Stheraven { 417227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 418227825Stheraven __get_db()->__iterator_copy(this, &__p); 419227825Stheraven#endif 420227825Stheraven } 421227825Stheraven 422227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 423227825Stheraven 424227825Stheraven _LIBCPP_INLINE_VISIBILITY 425227825Stheraven __list_const_iterator(const __list_const_iterator& __p) 426227825Stheraven : __ptr_(__p.__ptr_) 427227825Stheraven { 428227825Stheraven __get_db()->__iterator_copy(this, &__p); 429227825Stheraven } 430227825Stheraven 431227825Stheraven _LIBCPP_INLINE_VISIBILITY 432227825Stheraven ~__list_const_iterator() 433227825Stheraven { 434227825Stheraven __get_db()->__erase_i(this); 435227825Stheraven } 436227825Stheraven 437227825Stheraven _LIBCPP_INLINE_VISIBILITY 438227825Stheraven __list_const_iterator& operator=(const __list_const_iterator& __p) 439227825Stheraven { 440227825Stheraven if (this != &__p) 441227825Stheraven { 442227825Stheraven __get_db()->__iterator_copy(this, &__p); 443227825Stheraven __ptr_ = __p.__ptr_; 444227825Stheraven } 445227825Stheraven return *this; 446227825Stheraven } 447227825Stheraven 448227825Stheraven#endif // _LIBCPP_DEBUG_LEVEL >= 2 449227825Stheraven _LIBCPP_INLINE_VISIBILITY 450227825Stheraven reference operator*() const 451227825Stheraven { 452227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 453227825Stheraven _LIBCPP_ASSERT(__get_const_db()->__dereferenceable(this), 454227825Stheraven "Attempted to dereference a non-dereferenceable list::const_iterator"); 455227825Stheraven#endif 456227825Stheraven return __ptr_->__value_; 457227825Stheraven } 458227825Stheraven _LIBCPP_INLINE_VISIBILITY 459253159Stheraven pointer operator->() const 460253159Stheraven { 461253159Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 462253159Stheraven _LIBCPP_ASSERT(__get_const_db()->__dereferenceable(this), 463253159Stheraven "Attempted to dereference a non-dereferenceable list::iterator"); 464253159Stheraven#endif 465253159Stheraven return pointer_traits<pointer>::pointer_to(__ptr_->__value_); 466253159Stheraven } 467227825Stheraven 468227825Stheraven _LIBCPP_INLINE_VISIBILITY 469227825Stheraven __list_const_iterator& operator++() 470227825Stheraven { 471227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 472227825Stheraven _LIBCPP_ASSERT(__get_const_db()->__dereferenceable(this), 473227825Stheraven "Attempted to increment non-incrementable list::const_iterator"); 474227825Stheraven#endif 475227825Stheraven __ptr_ = __ptr_->__next_; 476227825Stheraven return *this; 477227825Stheraven } 478227825Stheraven _LIBCPP_INLINE_VISIBILITY 479227825Stheraven __list_const_iterator operator++(int) {__list_const_iterator __t(*this); ++(*this); return __t;} 480227825Stheraven 481227825Stheraven _LIBCPP_INLINE_VISIBILITY 482227825Stheraven __list_const_iterator& operator--() 483227825Stheraven { 484227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 485227825Stheraven _LIBCPP_ASSERT(__get_const_db()->__decrementable(this), 486227825Stheraven "Attempted to decrement non-decrementable list::const_iterator"); 487227825Stheraven#endif 488227825Stheraven __ptr_ = __ptr_->__prev_; 489227825Stheraven return *this; 490227825Stheraven } 491227825Stheraven _LIBCPP_INLINE_VISIBILITY 492227825Stheraven __list_const_iterator operator--(int) {__list_const_iterator __t(*this); --(*this); return __t;} 493227825Stheraven 494227825Stheraven friend _LIBCPP_INLINE_VISIBILITY 495227825Stheraven bool operator==(const __list_const_iterator& __x, const __list_const_iterator& __y) 496227825Stheraven { 497227825Stheraven return __x.__ptr_ == __y.__ptr_; 498227825Stheraven } 499227825Stheraven friend _LIBCPP_INLINE_VISIBILITY 500227825Stheraven bool operator!=(const __list_const_iterator& __x, const __list_const_iterator& __y) 501227825Stheraven {return !(__x == __y);} 502227825Stheraven}; 503227825Stheraven 504227825Stheraventemplate <class _Tp, class _Alloc> 505227825Stheravenclass __list_imp 506227825Stheraven{ 507227825Stheraven __list_imp(const __list_imp&); 508227825Stheraven __list_imp& operator=(const __list_imp&); 509227825Stheravenprotected: 510227825Stheraven typedef _Tp value_type; 511227825Stheraven typedef _Alloc allocator_type; 512227825Stheraven typedef allocator_traits<allocator_type> __alloc_traits; 513227825Stheraven typedef typename __alloc_traits::size_type size_type; 514227825Stheraven typedef typename __alloc_traits::void_pointer __void_pointer; 515227825Stheraven typedef __list_iterator<value_type, __void_pointer> iterator; 516227825Stheraven typedef __list_const_iterator<value_type, __void_pointer> const_iterator; 517227825Stheraven typedef __list_node_base<value_type, __void_pointer> __node_base; 518227825Stheraven typedef __list_node<value_type, __void_pointer> __node; 519227825Stheraven typedef typename __alloc_traits::template 520227825Stheraven#ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES 521227825Stheraven rebind_alloc<__node> 522227825Stheraven#else 523227825Stheraven rebind_alloc<__node>::other 524227825Stheraven#endif 525227825Stheraven __node_allocator; 526227825Stheraven typedef allocator_traits<__node_allocator> __node_alloc_traits; 527227825Stheraven typedef typename __node_alloc_traits::pointer __node_pointer; 528253159Stheraven typedef typename __node_alloc_traits::pointer __node_const_pointer; 529227825Stheraven typedef typename __alloc_traits::pointer pointer; 530227825Stheraven typedef typename __alloc_traits::const_pointer const_pointer; 531227825Stheraven typedef typename __alloc_traits::difference_type difference_type; 532227825Stheraven 533253159Stheraven typedef typename __alloc_traits::template 534253159Stheraven#ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES 535253159Stheraven rebind_alloc<__node_base> 536253159Stheraven#else 537253159Stheraven rebind_alloc<__node_base>::other 538253159Stheraven#endif 539253159Stheraven __node_base_allocator; 540253159Stheraven typedef typename allocator_traits<__node_base_allocator>::pointer __node_base_pointer; 541253159Stheraven 542227825Stheraven __node_base __end_; 543227825Stheraven __compressed_pair<size_type, __node_allocator> __size_alloc_; 544227825Stheraven 545227825Stheraven _LIBCPP_INLINE_VISIBILITY 546227825Stheraven size_type& __sz() _NOEXCEPT {return __size_alloc_.first();} 547227825Stheraven _LIBCPP_INLINE_VISIBILITY 548227825Stheraven const size_type& __sz() const _NOEXCEPT 549227825Stheraven {return __size_alloc_.first();} 550227825Stheraven _LIBCPP_INLINE_VISIBILITY 551227825Stheraven __node_allocator& __node_alloc() _NOEXCEPT 552227825Stheraven {return __size_alloc_.second();} 553227825Stheraven _LIBCPP_INLINE_VISIBILITY 554227825Stheraven const __node_allocator& __node_alloc() const _NOEXCEPT 555227825Stheraven {return __size_alloc_.second();} 556227825Stheraven 557253159Stheraven static void __unlink_nodes(__node_pointer __f, __node_pointer __l) _NOEXCEPT; 558227825Stheraven 559227825Stheraven __list_imp() 560227825Stheraven _NOEXCEPT_(is_nothrow_default_constructible<__node_allocator>::value); 561227825Stheraven __list_imp(const allocator_type& __a); 562227825Stheraven ~__list_imp(); 563227825Stheraven void clear() _NOEXCEPT; 564227825Stheraven _LIBCPP_INLINE_VISIBILITY 565227825Stheraven bool empty() const _NOEXCEPT {return __sz() == 0;} 566227825Stheraven 567227825Stheraven _LIBCPP_INLINE_VISIBILITY 568227825Stheraven iterator begin() _NOEXCEPT 569227825Stheraven { 570227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 571227825Stheraven return iterator(__end_.__next_, this); 572227825Stheraven#else 573227825Stheraven return iterator(__end_.__next_); 574227825Stheraven#endif 575227825Stheraven } 576227825Stheraven _LIBCPP_INLINE_VISIBILITY 577227825Stheraven const_iterator begin() const _NOEXCEPT 578227825Stheraven { 579227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 580227825Stheraven return const_iterator(__end_.__next_, this); 581227825Stheraven#else 582227825Stheraven return const_iterator(__end_.__next_); 583227825Stheraven#endif 584227825Stheraven } 585227825Stheraven _LIBCPP_INLINE_VISIBILITY 586227825Stheraven iterator end() _NOEXCEPT 587227825Stheraven { 588227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 589253159Stheraven return iterator(static_cast<__node_pointer>( 590253159Stheraven pointer_traits<__node_base_pointer>::pointer_to(__end_)), this); 591227825Stheraven#else 592253159Stheraven return iterator(static_cast<__node_pointer>( 593253159Stheraven pointer_traits<__node_base_pointer>::pointer_to(__end_))); 594227825Stheraven#endif 595227825Stheraven } 596227825Stheraven _LIBCPP_INLINE_VISIBILITY 597227825Stheraven const_iterator end() const _NOEXCEPT 598227825Stheraven { 599227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 600253159Stheraven return const_iterator(static_cast<__node_const_pointer>( 601253159Stheraven pointer_traits<__node_base_pointer>::pointer_to(const_cast<__node_base&>(__end_))), this); 602227825Stheraven#else 603253159Stheraven return const_iterator(static_cast<__node_const_pointer>( 604253159Stheraven pointer_traits<__node_base_pointer>::pointer_to(const_cast<__node_base&>(__end_)))); 605227825Stheraven#endif 606227825Stheraven } 607227825Stheraven 608227825Stheraven void swap(__list_imp& __c) 609227825Stheraven _NOEXCEPT_(!__node_alloc_traits::propagate_on_container_swap::value || 610227825Stheraven __is_nothrow_swappable<__node_allocator>::value); 611227825Stheraven 612227825Stheraven _LIBCPP_INLINE_VISIBILITY 613227825Stheraven void __copy_assign_alloc(const __list_imp& __c) 614227825Stheraven {__copy_assign_alloc(__c, integral_constant<bool, 615227825Stheraven __node_alloc_traits::propagate_on_container_copy_assignment::value>());} 616227825Stheraven 617227825Stheraven _LIBCPP_INLINE_VISIBILITY 618227825Stheraven void __move_assign_alloc(__list_imp& __c) 619227825Stheraven _NOEXCEPT_( 620227825Stheraven !__node_alloc_traits::propagate_on_container_move_assignment::value || 621227825Stheraven is_nothrow_move_assignable<__node_allocator>::value) 622227825Stheraven {__move_assign_alloc(__c, integral_constant<bool, 623227825Stheraven __node_alloc_traits::propagate_on_container_move_assignment::value>());} 624227825Stheraven 625227825Stheravenprivate: 626227825Stheraven _LIBCPP_INLINE_VISIBILITY 627227825Stheraven static void __swap_alloc(__node_allocator& __x, __node_allocator& __y) 628227825Stheraven _NOEXCEPT_(!__node_alloc_traits::propagate_on_container_swap::value || 629227825Stheraven __is_nothrow_swappable<__node_allocator>::value) 630227825Stheraven {__swap_alloc(__x, __y, integral_constant<bool, 631227825Stheraven __node_alloc_traits::propagate_on_container_swap::value>());} 632227825Stheraven _LIBCPP_INLINE_VISIBILITY 633227825Stheraven static void __swap_alloc(__node_allocator& __x, __node_allocator& __y, true_type) 634227825Stheraven _NOEXCEPT_(__is_nothrow_swappable<__node_allocator>::value) 635227825Stheraven { 636227825Stheraven using _VSTD::swap; 637227825Stheraven swap(__x, __y); 638227825Stheraven } 639227825Stheraven _LIBCPP_INLINE_VISIBILITY 640227825Stheraven static void __swap_alloc(__node_allocator& __x, __node_allocator& __y, false_type) 641227825Stheraven _NOEXCEPT 642227825Stheraven {} 643227825Stheraven 644227825Stheraven _LIBCPP_INLINE_VISIBILITY 645227825Stheraven void __copy_assign_alloc(const __list_imp& __c, true_type) 646227825Stheraven { 647227825Stheraven if (__node_alloc() != __c.__node_alloc()) 648227825Stheraven clear(); 649227825Stheraven __node_alloc() = __c.__node_alloc(); 650227825Stheraven } 651227825Stheraven 652227825Stheraven _LIBCPP_INLINE_VISIBILITY 653227825Stheraven void __copy_assign_alloc(const __list_imp& __c, false_type) 654227825Stheraven {} 655227825Stheraven 656227825Stheraven _LIBCPP_INLINE_VISIBILITY 657227825Stheraven void __move_assign_alloc(__list_imp& __c, true_type) 658227825Stheraven _NOEXCEPT_(is_nothrow_move_assignable<__node_allocator>::value) 659227825Stheraven { 660227825Stheraven __node_alloc() = _VSTD::move(__c.__node_alloc()); 661227825Stheraven } 662227825Stheraven 663227825Stheraven _LIBCPP_INLINE_VISIBILITY 664227825Stheraven void __move_assign_alloc(__list_imp& __c, false_type) 665227825Stheraven _NOEXCEPT 666227825Stheraven {} 667227825Stheraven}; 668227825Stheraven 669227825Stheraven// Unlink nodes [__f, __l] 670227825Stheraventemplate <class _Tp, class _Alloc> 671227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 672227825Stheravenvoid 673253159Stheraven__list_imp<_Tp, _Alloc>::__unlink_nodes(__node_pointer __f, __node_pointer __l) 674227825Stheraven _NOEXCEPT 675227825Stheraven{ 676253159Stheraven __f->__prev_->__next_ = __l->__next_; 677253159Stheraven __l->__next_->__prev_ = __f->__prev_; 678227825Stheraven} 679227825Stheraven 680227825Stheraventemplate <class _Tp, class _Alloc> 681227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 682227825Stheraven__list_imp<_Tp, _Alloc>::__list_imp() 683227825Stheraven _NOEXCEPT_(is_nothrow_default_constructible<__node_allocator>::value) 684227825Stheraven : __size_alloc_(0) 685227825Stheraven{ 686227825Stheraven} 687227825Stheraven 688227825Stheraventemplate <class _Tp, class _Alloc> 689227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 690227825Stheraven__list_imp<_Tp, _Alloc>::__list_imp(const allocator_type& __a) 691227825Stheraven : __size_alloc_(0, __node_allocator(__a)) 692227825Stheraven{ 693227825Stheraven} 694227825Stheraven 695227825Stheraventemplate <class _Tp, class _Alloc> 696227825Stheraven__list_imp<_Tp, _Alloc>::~__list_imp() 697227825Stheraven{ 698227825Stheraven clear(); 699227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 700227825Stheraven __get_db()->__erase_c(this); 701227825Stheraven#endif 702227825Stheraven} 703227825Stheraven 704227825Stheraventemplate <class _Tp, class _Alloc> 705227825Stheravenvoid 706227825Stheraven__list_imp<_Tp, _Alloc>::clear() _NOEXCEPT 707227825Stheraven{ 708227825Stheraven if (!empty()) 709227825Stheraven { 710227825Stheraven __node_allocator& __na = __node_alloc(); 711227825Stheraven __node_pointer __f = __end_.__next_; 712253159Stheraven __node_pointer __l = static_cast<__node_pointer>( 713253159Stheraven pointer_traits<__node_base_pointer>::pointer_to(__end_)); 714253159Stheraven __unlink_nodes(__f, __l->__prev_); 715227825Stheraven __sz() = 0; 716227825Stheraven while (__f != __l) 717227825Stheraven { 718253159Stheraven __node_pointer __n = __f; 719227825Stheraven __f = __f->__next_; 720253159Stheraven __node_alloc_traits::destroy(__na, _VSTD::addressof(__n->__value_)); 721253159Stheraven __node_alloc_traits::deallocate(__na, __n, 1); 722227825Stheraven } 723227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 724227825Stheraven __c_node* __c = __get_db()->__find_c_and_lock(this); 725227825Stheraven for (__i_node** __p = __c->end_; __p != __c->beg_; ) 726227825Stheraven { 727227825Stheraven --__p; 728227825Stheraven const_iterator* __i = static_cast<const_iterator*>((*__p)->__i_); 729227825Stheraven if (__i->__ptr_ != __l) 730227825Stheraven { 731227825Stheraven (*__p)->__c_ = nullptr; 732227825Stheraven if (--__c->end_ != __p) 733227825Stheraven memmove(__p, __p+1, (__c->end_ - __p)*sizeof(__i_node*)); 734227825Stheraven } 735227825Stheraven } 736227825Stheraven __get_db()->unlock(); 737227825Stheraven#endif 738227825Stheraven } 739227825Stheraven} 740227825Stheraven 741227825Stheraventemplate <class _Tp, class _Alloc> 742227825Stheravenvoid 743227825Stheraven__list_imp<_Tp, _Alloc>::swap(__list_imp& __c) 744227825Stheraven _NOEXCEPT_(!__node_alloc_traits::propagate_on_container_swap::value || 745227825Stheraven __is_nothrow_swappable<__node_allocator>::value) 746227825Stheraven{ 747227825Stheraven _LIBCPP_ASSERT(__alloc_traits::propagate_on_container_swap::value || 748227825Stheraven this->__node_alloc() == __c.__node_alloc(), 749227825Stheraven "list::swap: Either propagate_on_container_swap must be true" 750227825Stheraven " or the allocators must compare equal"); 751227825Stheraven using _VSTD::swap; 752227825Stheraven __swap_alloc(__node_alloc(), __c.__node_alloc()); 753227825Stheraven swap(__sz(), __c.__sz()); 754227825Stheraven swap(__end_, __c.__end_); 755227825Stheraven if (__sz() == 0) 756253159Stheraven __end_.__next_ = __end_.__prev_ = static_cast<__node_pointer>( 757253159Stheraven pointer_traits<__node_base_pointer>::pointer_to(__end_)); 758227825Stheraven else 759227825Stheraven __end_.__prev_->__next_ = __end_.__next_->__prev_ 760253159Stheraven = static_cast<__node_pointer>( 761253159Stheraven pointer_traits<__node_base_pointer>::pointer_to(__end_)); 762227825Stheraven if (__c.__sz() == 0) 763227825Stheraven __c.__end_.__next_ = __c.__end_.__prev_ 764253159Stheraven = static_cast<__node_pointer>( 765253159Stheraven pointer_traits<__node_base_pointer>::pointer_to(__c.__end_)); 766227825Stheraven else 767227825Stheraven __c.__end_.__prev_->__next_ = __c.__end_.__next_->__prev_ 768253159Stheraven = static_cast<__node_pointer>( 769253159Stheraven pointer_traits<__node_base_pointer>::pointer_to(__c.__end_)); 770227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 771227825Stheraven __libcpp_db* __db = __get_db(); 772227825Stheraven __c_node* __cn1 = __db->__find_c_and_lock(this); 773227825Stheraven __c_node* __cn2 = __db->__find_c(&__c); 774227825Stheraven std::swap(__cn1->beg_, __cn2->beg_); 775227825Stheraven std::swap(__cn1->end_, __cn2->end_); 776227825Stheraven std::swap(__cn1->cap_, __cn2->cap_); 777227825Stheraven for (__i_node** __p = __cn1->end_; __p != __cn1->beg_;) 778227825Stheraven { 779227825Stheraven --__p; 780227825Stheraven const_iterator* __i = static_cast<const_iterator*>((*__p)->__i_); 781253159Stheraven if (__i->__ptr_ == static_cast<__node_pointer>( 782253159Stheraven pointer_traits<__node_base_pointer>::pointer_to(__c.__end_))) 783227825Stheraven { 784227825Stheraven __cn2->__add(*__p); 785227825Stheraven if (--__cn1->end_ != __p) 786227825Stheraven memmove(__p, __p+1, (__cn1->end_ - __p)*sizeof(__i_node*)); 787227825Stheraven } 788227825Stheraven else 789227825Stheraven (*__p)->__c_ = __cn1; 790227825Stheraven } 791227825Stheraven for (__i_node** __p = __cn2->end_; __p != __cn2->beg_;) 792227825Stheraven { 793227825Stheraven --__p; 794227825Stheraven const_iterator* __i = static_cast<const_iterator*>((*__p)->__i_); 795253159Stheraven if (__i->__ptr_ == static_cast<__node_pointer>( 796253159Stheraven pointer_traits<__node_base_pointer>::pointer_to(__end_))) 797227825Stheraven { 798227825Stheraven __cn1->__add(*__p); 799227825Stheraven if (--__cn2->end_ != __p) 800227825Stheraven memmove(__p, __p+1, (__cn2->end_ - __p)*sizeof(__i_node*)); 801227825Stheraven } 802227825Stheraven else 803227825Stheraven (*__p)->__c_ = __cn2; 804227825Stheraven } 805227825Stheraven __db->unlock(); 806227825Stheraven#endif 807227825Stheraven} 808227825Stheraven 809227825Stheraventemplate <class _Tp, class _Alloc = allocator<_Tp> > 810262801Sdimclass _LIBCPP_TYPE_VIS_ONLY list 811227825Stheraven : private __list_imp<_Tp, _Alloc> 812227825Stheraven{ 813227825Stheraven typedef __list_imp<_Tp, _Alloc> base; 814227825Stheraven typedef typename base::__node __node; 815227825Stheraven typedef typename base::__node_allocator __node_allocator; 816227825Stheraven typedef typename base::__node_pointer __node_pointer; 817227825Stheraven typedef typename base::__node_alloc_traits __node_alloc_traits; 818253159Stheraven typedef typename base::__node_base __node_base; 819253159Stheraven typedef typename base::__node_base_pointer __node_base_pointer; 820227825Stheraven 821227825Stheravenpublic: 822227825Stheraven typedef _Tp value_type; 823227825Stheraven typedef _Alloc allocator_type; 824227825Stheraven static_assert((is_same<value_type, typename allocator_type::value_type>::value), 825227825Stheraven "Invalid allocator::value_type"); 826227825Stheraven typedef value_type& reference; 827227825Stheraven typedef const value_type& const_reference; 828227825Stheraven typedef typename base::pointer pointer; 829227825Stheraven typedef typename base::const_pointer const_pointer; 830227825Stheraven typedef typename base::size_type size_type; 831227825Stheraven typedef typename base::difference_type difference_type; 832227825Stheraven typedef typename base::iterator iterator; 833227825Stheraven typedef typename base::const_iterator const_iterator; 834227825Stheraven typedef _VSTD::reverse_iterator<iterator> reverse_iterator; 835227825Stheraven typedef _VSTD::reverse_iterator<const_iterator> const_reverse_iterator; 836227825Stheraven 837227825Stheraven _LIBCPP_INLINE_VISIBILITY 838227825Stheraven list() 839227825Stheraven _NOEXCEPT_(is_nothrow_default_constructible<__node_allocator>::value) 840227825Stheraven { 841227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 842227825Stheraven __get_db()->__insert_c(this); 843227825Stheraven#endif 844227825Stheraven } 845227825Stheraven _LIBCPP_INLINE_VISIBILITY 846262801Sdim explicit list(const allocator_type& __a) : base(__a) 847227825Stheraven { 848227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 849227825Stheraven __get_db()->__insert_c(this); 850227825Stheraven#endif 851227825Stheraven } 852262801Sdim explicit list(size_type __n); 853262801Sdim#if _LIBCPP_STD_VER > 11 854262801Sdim explicit list(size_type __n, const allocator_type& __a); 855262801Sdim#endif 856227825Stheraven list(size_type __n, const value_type& __x); 857227825Stheraven list(size_type __n, const value_type& __x, const allocator_type& __a); 858227825Stheraven template <class _InpIter> 859227825Stheraven list(_InpIter __f, _InpIter __l, 860227825Stheraven typename enable_if<__is_input_iterator<_InpIter>::value>::type* = 0); 861227825Stheraven template <class _InpIter> 862227825Stheraven list(_InpIter __f, _InpIter __l, const allocator_type& __a, 863227825Stheraven typename enable_if<__is_input_iterator<_InpIter>::value>::type* = 0); 864227825Stheraven 865227825Stheraven list(const list& __c); 866227825Stheraven list(const list& __c, const allocator_type& __a); 867227825Stheraven list& operator=(const list& __c); 868227825Stheraven#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 869227825Stheraven list(initializer_list<value_type> __il); 870227825Stheraven list(initializer_list<value_type> __il, const allocator_type& __a); 871227825Stheraven#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 872227825Stheraven#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 873227825Stheraven list(list&& __c) 874227825Stheraven _NOEXCEPT_(is_nothrow_move_constructible<__node_allocator>::value); 875227825Stheraven list(list&& __c, const allocator_type& __a); 876227825Stheraven list& operator=(list&& __c) 877227825Stheraven _NOEXCEPT_( 878227825Stheraven __node_alloc_traits::propagate_on_container_move_assignment::value && 879227825Stheraven is_nothrow_move_assignable<__node_allocator>::value); 880227825Stheraven#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 881227825Stheraven#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 882227825Stheraven _LIBCPP_INLINE_VISIBILITY 883227825Stheraven list& operator=(initializer_list<value_type> __il) 884227825Stheraven {assign(__il.begin(), __il.end()); return *this;} 885227825Stheraven#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 886227825Stheraven 887227825Stheraven template <class _InpIter> 888227825Stheraven void assign(_InpIter __f, _InpIter __l, 889227825Stheraven typename enable_if<__is_input_iterator<_InpIter>::value>::type* = 0); 890227825Stheraven void assign(size_type __n, const value_type& __x); 891227825Stheraven#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 892227825Stheraven _LIBCPP_INLINE_VISIBILITY 893227825Stheraven void assign(initializer_list<value_type> __il) 894227825Stheraven {assign(__il.begin(), __il.end());} 895227825Stheraven#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 896227825Stheraven 897227825Stheraven allocator_type get_allocator() const _NOEXCEPT; 898227825Stheraven 899227825Stheraven _LIBCPP_INLINE_VISIBILITY 900227825Stheraven size_type size() const _NOEXCEPT {return base::__sz();} 901227825Stheraven _LIBCPP_INLINE_VISIBILITY 902227825Stheraven bool empty() const _NOEXCEPT {return base::empty();} 903227825Stheraven _LIBCPP_INLINE_VISIBILITY 904227825Stheraven size_type max_size() const _NOEXCEPT 905227825Stheraven {return numeric_limits<difference_type>::max();} 906227825Stheraven 907227825Stheraven _LIBCPP_INLINE_VISIBILITY 908227825Stheraven iterator begin() _NOEXCEPT {return base::begin();} 909227825Stheraven _LIBCPP_INLINE_VISIBILITY 910227825Stheraven const_iterator begin() const _NOEXCEPT {return base::begin();} 911227825Stheraven _LIBCPP_INLINE_VISIBILITY 912227825Stheraven iterator end() _NOEXCEPT {return base::end();} 913227825Stheraven _LIBCPP_INLINE_VISIBILITY 914227825Stheraven const_iterator end() const _NOEXCEPT {return base::end();} 915227825Stheraven _LIBCPP_INLINE_VISIBILITY 916227825Stheraven const_iterator cbegin() const _NOEXCEPT {return base::begin();} 917227825Stheraven _LIBCPP_INLINE_VISIBILITY 918227825Stheraven const_iterator cend() const _NOEXCEPT {return base::end();} 919227825Stheraven 920227825Stheraven _LIBCPP_INLINE_VISIBILITY 921227825Stheraven reverse_iterator rbegin() _NOEXCEPT 922227825Stheraven {return reverse_iterator(end());} 923227825Stheraven _LIBCPP_INLINE_VISIBILITY 924227825Stheraven const_reverse_iterator rbegin() const _NOEXCEPT 925227825Stheraven {return const_reverse_iterator(end());} 926227825Stheraven _LIBCPP_INLINE_VISIBILITY 927227825Stheraven reverse_iterator rend() _NOEXCEPT 928227825Stheraven {return reverse_iterator(begin());} 929227825Stheraven _LIBCPP_INLINE_VISIBILITY 930227825Stheraven const_reverse_iterator rend() const _NOEXCEPT 931227825Stheraven {return const_reverse_iterator(begin());} 932227825Stheraven _LIBCPP_INLINE_VISIBILITY 933227825Stheraven const_reverse_iterator crbegin() const _NOEXCEPT 934227825Stheraven {return const_reverse_iterator(end());} 935227825Stheraven _LIBCPP_INLINE_VISIBILITY 936227825Stheraven const_reverse_iterator crend() const _NOEXCEPT 937227825Stheraven {return const_reverse_iterator(begin());} 938227825Stheraven 939227825Stheraven _LIBCPP_INLINE_VISIBILITY 940227825Stheraven reference front() 941227825Stheraven { 942227825Stheraven _LIBCPP_ASSERT(!empty(), "list::front called on empty list"); 943227825Stheraven return base::__end_.__next_->__value_; 944227825Stheraven } 945227825Stheraven _LIBCPP_INLINE_VISIBILITY 946227825Stheraven const_reference front() const 947227825Stheraven { 948227825Stheraven _LIBCPP_ASSERT(!empty(), "list::front called on empty list"); 949227825Stheraven return base::__end_.__next_->__value_; 950227825Stheraven } 951227825Stheraven _LIBCPP_INLINE_VISIBILITY 952227825Stheraven reference back() 953227825Stheraven { 954227825Stheraven _LIBCPP_ASSERT(!empty(), "list::back called on empty list"); 955227825Stheraven return base::__end_.__prev_->__value_; 956227825Stheraven } 957227825Stheraven _LIBCPP_INLINE_VISIBILITY 958227825Stheraven const_reference back() const 959227825Stheraven { 960227825Stheraven _LIBCPP_ASSERT(!empty(), "list::back called on empty list"); 961227825Stheraven return base::__end_.__prev_->__value_; 962227825Stheraven } 963227825Stheraven 964227825Stheraven#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 965227825Stheraven void push_front(value_type&& __x); 966227825Stheraven void push_back(value_type&& __x); 967227825Stheraven#ifndef _LIBCPP_HAS_NO_VARIADICS 968227825Stheraven template <class... _Args> 969227825Stheraven void emplace_front(_Args&&... __args); 970227825Stheraven template <class... _Args> 971227825Stheraven void emplace_back(_Args&&... __args); 972227825Stheraven template <class... _Args> 973227825Stheraven iterator emplace(const_iterator __p, _Args&&... __args); 974227825Stheraven#endif // _LIBCPP_HAS_NO_VARIADICS 975227825Stheraven iterator insert(const_iterator __p, value_type&& __x); 976227825Stheraven#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 977227825Stheraven 978227825Stheraven void push_front(const value_type& __x); 979227825Stheraven void push_back(const value_type& __x); 980227825Stheraven 981227825Stheraven iterator insert(const_iterator __p, const value_type& __x); 982227825Stheraven iterator insert(const_iterator __p, size_type __n, const value_type& __x); 983227825Stheraven template <class _InpIter> 984227825Stheraven iterator insert(const_iterator __p, _InpIter __f, _InpIter __l, 985227825Stheraven typename enable_if<__is_input_iterator<_InpIter>::value>::type* = 0); 986227825Stheraven#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 987227825Stheraven _LIBCPP_INLINE_VISIBILITY 988227825Stheraven iterator insert(const_iterator __p, initializer_list<value_type> __il) 989227825Stheraven {return insert(__p, __il.begin(), __il.end());} 990227825Stheraven#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 991227825Stheraven 992227825Stheraven _LIBCPP_INLINE_VISIBILITY 993227825Stheraven void swap(list& __c) 994227825Stheraven _NOEXCEPT_(!__node_alloc_traits::propagate_on_container_swap::value || 995227825Stheraven __is_nothrow_swappable<__node_allocator>::value) 996227825Stheraven {base::swap(__c);} 997227825Stheraven _LIBCPP_INLINE_VISIBILITY 998227825Stheraven void clear() _NOEXCEPT {base::clear();} 999227825Stheraven 1000227825Stheraven void pop_front(); 1001227825Stheraven void pop_back(); 1002227825Stheraven 1003227825Stheraven iterator erase(const_iterator __p); 1004227825Stheraven iterator erase(const_iterator __f, const_iterator __l); 1005227825Stheraven 1006227825Stheraven void resize(size_type __n); 1007227825Stheraven void resize(size_type __n, const value_type& __x); 1008227825Stheraven 1009227825Stheraven void splice(const_iterator __p, list& __c); 1010227825Stheraven#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 1011227825Stheraven _LIBCPP_INLINE_VISIBILITY 1012227825Stheraven void splice(const_iterator __p, list&& __c) {splice(__p, __c);} 1013227825Stheraven#endif 1014227825Stheraven void splice(const_iterator __p, list& __c, const_iterator __i); 1015227825Stheraven#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 1016227825Stheraven _LIBCPP_INLINE_VISIBILITY 1017227825Stheraven void splice(const_iterator __p, list&& __c, const_iterator __i) 1018227825Stheraven {splice(__p, __c, __i);} 1019227825Stheraven#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 1020227825Stheraven void splice(const_iterator __p, list& __c, const_iterator __f, const_iterator __l); 1021227825Stheraven#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 1022227825Stheraven _LIBCPP_INLINE_VISIBILITY 1023227825Stheraven void splice(const_iterator __p, list&& __c, const_iterator __f, const_iterator __l) 1024227825Stheraven {splice(__p, __c, __f, __l);} 1025227825Stheraven#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 1026227825Stheraven 1027227825Stheraven void remove(const value_type& __x); 1028227825Stheraven template <class _Pred> void remove_if(_Pred __pred); 1029227825Stheraven void unique(); 1030227825Stheraven template <class _BinaryPred> 1031227825Stheraven void unique(_BinaryPred __binary_pred); 1032227825Stheraven void merge(list& __c); 1033227825Stheraven#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 1034227825Stheraven _LIBCPP_INLINE_VISIBILITY 1035227825Stheraven void merge(list&& __c) {merge(__c);} 1036227825Stheraven#endif 1037227825Stheraven template <class _Comp> 1038227825Stheraven void merge(list& __c, _Comp __comp); 1039227825Stheraven#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 1040227825Stheraven template <class _Comp> 1041227825Stheraven _LIBCPP_INLINE_VISIBILITY 1042227825Stheraven void merge(list&& __c, _Comp __comp) {merge(__c, __comp);} 1043227825Stheraven#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 1044227825Stheraven void sort(); 1045227825Stheraven template <class _Comp> 1046227825Stheraven void sort(_Comp __comp); 1047227825Stheraven 1048227825Stheraven void reverse() _NOEXCEPT; 1049227825Stheraven 1050227825Stheraven bool __invariants() const; 1051227825Stheraven 1052227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 1053227825Stheraven 1054227825Stheraven bool __dereferenceable(const const_iterator* __i) const; 1055227825Stheraven bool __decrementable(const const_iterator* __i) const; 1056227825Stheraven bool __addable(const const_iterator* __i, ptrdiff_t __n) const; 1057227825Stheraven bool __subscriptable(const const_iterator* __i, ptrdiff_t __n) const; 1058227825Stheraven 1059227825Stheraven#endif // _LIBCPP_DEBUG_LEVEL >= 2 1060227825Stheraven 1061227825Stheravenprivate: 1062253159Stheraven static void __link_nodes(__node_pointer __p, __node_pointer __f, __node_pointer __l); 1063227825Stheraven iterator __iterator(size_type __n); 1064227825Stheraven template <class _Comp> 1065227825Stheraven static iterator __sort(iterator __f1, iterator __e2, size_type __n, _Comp& __comp); 1066227825Stheraven 1067227825Stheraven void __move_assign(list& __c, true_type) 1068227825Stheraven _NOEXCEPT_(is_nothrow_move_assignable<__node_allocator>::value); 1069227825Stheraven void __move_assign(list& __c, false_type); 1070227825Stheraven}; 1071227825Stheraven 1072227825Stheraven// Link in nodes [__f, __l] just prior to __p 1073227825Stheraventemplate <class _Tp, class _Alloc> 1074227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 1075227825Stheravenvoid 1076253159Stheravenlist<_Tp, _Alloc>::__link_nodes(__node_pointer __p, __node_pointer __f, __node_pointer __l) 1077227825Stheraven{ 1078253159Stheraven __p->__prev_->__next_ = __f; 1079253159Stheraven __f->__prev_ = __p->__prev_; 1080253159Stheraven __p->__prev_ = __l; 1081253159Stheraven __l->__next_ = __p; 1082227825Stheraven} 1083227825Stheraven 1084227825Stheraventemplate <class _Tp, class _Alloc> 1085227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 1086227825Stheraventypename list<_Tp, _Alloc>::iterator 1087227825Stheravenlist<_Tp, _Alloc>::__iterator(size_type __n) 1088227825Stheraven{ 1089227825Stheraven return __n <= base::__sz() / 2 ? _VSTD::next(begin(), __n) 1090227825Stheraven : _VSTD::prev(end(), base::__sz() - __n); 1091227825Stheraven} 1092227825Stheraven 1093227825Stheraventemplate <class _Tp, class _Alloc> 1094227825Stheravenlist<_Tp, _Alloc>::list(size_type __n) 1095227825Stheraven{ 1096227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 1097227825Stheraven __get_db()->__insert_c(this); 1098227825Stheraven#endif 1099227825Stheraven for (; __n > 0; --__n) 1100227825Stheraven#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 1101227825Stheraven emplace_back(); 1102227825Stheraven#else 1103227825Stheraven push_back(value_type()); 1104227825Stheraven#endif 1105227825Stheraven} 1106227825Stheraven 1107262801Sdim#if _LIBCPP_STD_VER > 11 1108227825Stheraventemplate <class _Tp, class _Alloc> 1109262801Sdimlist<_Tp, _Alloc>::list(size_type __n, const allocator_type& __a) : base(__a) 1110262801Sdim{ 1111262801Sdim#if _LIBCPP_DEBUG_LEVEL >= 2 1112262801Sdim __get_db()->__insert_c(this); 1113262801Sdim#endif 1114262801Sdim for (; __n > 0; --__n) 1115262801Sdim#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 1116262801Sdim emplace_back(); 1117262801Sdim#else 1118262801Sdim push_back(value_type()); 1119262801Sdim#endif 1120262801Sdim} 1121262801Sdim#endif 1122262801Sdim 1123262801Sdimtemplate <class _Tp, class _Alloc> 1124227825Stheravenlist<_Tp, _Alloc>::list(size_type __n, const value_type& __x) 1125227825Stheraven{ 1126227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 1127227825Stheraven __get_db()->__insert_c(this); 1128227825Stheraven#endif 1129227825Stheraven for (; __n > 0; --__n) 1130227825Stheraven push_back(__x); 1131227825Stheraven} 1132227825Stheraven 1133227825Stheraventemplate <class _Tp, class _Alloc> 1134227825Stheravenlist<_Tp, _Alloc>::list(size_type __n, const value_type& __x, const allocator_type& __a) 1135227825Stheraven : base(__a) 1136227825Stheraven{ 1137227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 1138227825Stheraven __get_db()->__insert_c(this); 1139227825Stheraven#endif 1140227825Stheraven for (; __n > 0; --__n) 1141227825Stheraven push_back(__x); 1142227825Stheraven} 1143227825Stheraven 1144227825Stheraventemplate <class _Tp, class _Alloc> 1145227825Stheraventemplate <class _InpIter> 1146227825Stheravenlist<_Tp, _Alloc>::list(_InpIter __f, _InpIter __l, 1147227825Stheraven typename enable_if<__is_input_iterator<_InpIter>::value>::type*) 1148227825Stheraven{ 1149227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 1150227825Stheraven __get_db()->__insert_c(this); 1151227825Stheraven#endif 1152227825Stheraven for (; __f != __l; ++__f) 1153227825Stheraven push_back(*__f); 1154227825Stheraven} 1155227825Stheraven 1156227825Stheraventemplate <class _Tp, class _Alloc> 1157227825Stheraventemplate <class _InpIter> 1158227825Stheravenlist<_Tp, _Alloc>::list(_InpIter __f, _InpIter __l, const allocator_type& __a, 1159227825Stheraven typename enable_if<__is_input_iterator<_InpIter>::value>::type*) 1160227825Stheraven : base(__a) 1161227825Stheraven{ 1162227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 1163227825Stheraven __get_db()->__insert_c(this); 1164227825Stheraven#endif 1165227825Stheraven for (; __f != __l; ++__f) 1166227825Stheraven push_back(*__f); 1167227825Stheraven} 1168227825Stheraven 1169227825Stheraventemplate <class _Tp, class _Alloc> 1170227825Stheravenlist<_Tp, _Alloc>::list(const list& __c) 1171227825Stheraven : base(allocator_type( 1172227825Stheraven __node_alloc_traits::select_on_container_copy_construction( 1173227825Stheraven __c.__node_alloc()))) 1174227825Stheraven{ 1175227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 1176227825Stheraven __get_db()->__insert_c(this); 1177227825Stheraven#endif 1178227825Stheraven for (const_iterator __i = __c.begin(), __e = __c.end(); __i != __e; ++__i) 1179227825Stheraven push_back(*__i); 1180227825Stheraven} 1181227825Stheraven 1182227825Stheraventemplate <class _Tp, class _Alloc> 1183227825Stheravenlist<_Tp, _Alloc>::list(const list& __c, const allocator_type& __a) 1184227825Stheraven : base(__a) 1185227825Stheraven{ 1186227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 1187227825Stheraven __get_db()->__insert_c(this); 1188227825Stheraven#endif 1189227825Stheraven for (const_iterator __i = __c.begin(), __e = __c.end(); __i != __e; ++__i) 1190227825Stheraven push_back(*__i); 1191227825Stheraven} 1192227825Stheraven 1193227825Stheraven#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 1194227825Stheraven 1195227825Stheraventemplate <class _Tp, class _Alloc> 1196227825Stheravenlist<_Tp, _Alloc>::list(initializer_list<value_type> __il, const allocator_type& __a) 1197227825Stheraven : base(__a) 1198227825Stheraven{ 1199227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 1200227825Stheraven __get_db()->__insert_c(this); 1201227825Stheraven#endif 1202227825Stheraven for (typename initializer_list<value_type>::const_iterator __i = __il.begin(), 1203227825Stheraven __e = __il.end(); __i != __e; ++__i) 1204227825Stheraven push_back(*__i); 1205227825Stheraven} 1206227825Stheraven 1207227825Stheraventemplate <class _Tp, class _Alloc> 1208227825Stheravenlist<_Tp, _Alloc>::list(initializer_list<value_type> __il) 1209227825Stheraven{ 1210227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 1211227825Stheraven __get_db()->__insert_c(this); 1212227825Stheraven#endif 1213227825Stheraven for (typename initializer_list<value_type>::const_iterator __i = __il.begin(), 1214227825Stheraven __e = __il.end(); __i != __e; ++__i) 1215227825Stheraven push_back(*__i); 1216227825Stheraven} 1217227825Stheraven 1218227825Stheraven#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 1219227825Stheraven 1220227825Stheraventemplate <class _Tp, class _Alloc> 1221227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 1222227825Stheravenlist<_Tp, _Alloc>& 1223227825Stheravenlist<_Tp, _Alloc>::operator=(const list& __c) 1224227825Stheraven{ 1225227825Stheraven if (this != &__c) 1226227825Stheraven { 1227227825Stheraven base::__copy_assign_alloc(__c); 1228227825Stheraven assign(__c.begin(), __c.end()); 1229227825Stheraven } 1230227825Stheraven return *this; 1231227825Stheraven} 1232227825Stheraven 1233227825Stheraven#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 1234227825Stheraven 1235227825Stheraventemplate <class _Tp, class _Alloc> 1236227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 1237227825Stheravenlist<_Tp, _Alloc>::list(list&& __c) 1238227825Stheraven _NOEXCEPT_(is_nothrow_move_constructible<__node_allocator>::value) 1239227825Stheraven : base(allocator_type(_VSTD::move(__c.__node_alloc()))) 1240227825Stheraven{ 1241227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 1242227825Stheraven __get_db()->__insert_c(this); 1243227825Stheraven#endif 1244227825Stheraven splice(end(), __c); 1245227825Stheraven} 1246227825Stheraven 1247227825Stheraventemplate <class _Tp, class _Alloc> 1248227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 1249227825Stheravenlist<_Tp, _Alloc>::list(list&& __c, const allocator_type& __a) 1250227825Stheraven : base(__a) 1251227825Stheraven{ 1252227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 1253227825Stheraven __get_db()->__insert_c(this); 1254227825Stheraven#endif 1255227825Stheraven if (__a == __c.get_allocator()) 1256227825Stheraven splice(end(), __c); 1257227825Stheraven else 1258227825Stheraven { 1259232950Stheraven typedef move_iterator<iterator> _Ip; 1260232950Stheraven assign(_Ip(__c.begin()), _Ip(__c.end())); 1261227825Stheraven } 1262227825Stheraven} 1263227825Stheraven 1264227825Stheraventemplate <class _Tp, class _Alloc> 1265227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 1266227825Stheravenlist<_Tp, _Alloc>& 1267227825Stheravenlist<_Tp, _Alloc>::operator=(list&& __c) 1268227825Stheraven _NOEXCEPT_( 1269227825Stheraven __node_alloc_traits::propagate_on_container_move_assignment::value && 1270227825Stheraven is_nothrow_move_assignable<__node_allocator>::value) 1271227825Stheraven{ 1272227825Stheraven __move_assign(__c, integral_constant<bool, 1273227825Stheraven __node_alloc_traits::propagate_on_container_move_assignment::value>()); 1274227825Stheraven return *this; 1275227825Stheraven} 1276227825Stheraven 1277227825Stheraventemplate <class _Tp, class _Alloc> 1278227825Stheravenvoid 1279227825Stheravenlist<_Tp, _Alloc>::__move_assign(list& __c, false_type) 1280227825Stheraven{ 1281227825Stheraven if (base::__node_alloc() != __c.__node_alloc()) 1282227825Stheraven { 1283232950Stheraven typedef move_iterator<iterator> _Ip; 1284232950Stheraven assign(_Ip(__c.begin()), _Ip(__c.end())); 1285227825Stheraven } 1286227825Stheraven else 1287227825Stheraven __move_assign(__c, true_type()); 1288227825Stheraven} 1289227825Stheraven 1290227825Stheraventemplate <class _Tp, class _Alloc> 1291227825Stheravenvoid 1292227825Stheravenlist<_Tp, _Alloc>::__move_assign(list& __c, true_type) 1293227825Stheraven _NOEXCEPT_(is_nothrow_move_assignable<__node_allocator>::value) 1294227825Stheraven{ 1295227825Stheraven clear(); 1296227825Stheraven base::__move_assign_alloc(__c); 1297227825Stheraven splice(end(), __c); 1298227825Stheraven} 1299227825Stheraven 1300227825Stheraven#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 1301227825Stheraven 1302227825Stheraventemplate <class _Tp, class _Alloc> 1303227825Stheraventemplate <class _InpIter> 1304227825Stheravenvoid 1305227825Stheravenlist<_Tp, _Alloc>::assign(_InpIter __f, _InpIter __l, 1306227825Stheraven typename enable_if<__is_input_iterator<_InpIter>::value>::type*) 1307227825Stheraven{ 1308227825Stheraven iterator __i = begin(); 1309227825Stheraven iterator __e = end(); 1310227825Stheraven for (; __f != __l && __i != __e; ++__f, ++__i) 1311227825Stheraven *__i = *__f; 1312227825Stheraven if (__i == __e) 1313227825Stheraven insert(__e, __f, __l); 1314227825Stheraven else 1315227825Stheraven erase(__i, __e); 1316227825Stheraven} 1317227825Stheraven 1318227825Stheraventemplate <class _Tp, class _Alloc> 1319227825Stheravenvoid 1320227825Stheravenlist<_Tp, _Alloc>::assign(size_type __n, const value_type& __x) 1321227825Stheraven{ 1322227825Stheraven iterator __i = begin(); 1323227825Stheraven iterator __e = end(); 1324227825Stheraven for (; __n > 0 && __i != __e; --__n, ++__i) 1325227825Stheraven *__i = __x; 1326227825Stheraven if (__i == __e) 1327227825Stheraven insert(__e, __n, __x); 1328227825Stheraven else 1329227825Stheraven erase(__i, __e); 1330227825Stheraven} 1331227825Stheraven 1332227825Stheraventemplate <class _Tp, class _Alloc> 1333227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 1334227825Stheraven_Alloc 1335227825Stheravenlist<_Tp, _Alloc>::get_allocator() const _NOEXCEPT 1336227825Stheraven{ 1337227825Stheraven return allocator_type(base::__node_alloc()); 1338227825Stheraven} 1339227825Stheraven 1340227825Stheraventemplate <class _Tp, class _Alloc> 1341227825Stheraventypename list<_Tp, _Alloc>::iterator 1342227825Stheravenlist<_Tp, _Alloc>::insert(const_iterator __p, const value_type& __x) 1343227825Stheraven{ 1344227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 1345227825Stheraven _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__p) == this, 1346227825Stheraven "list::insert(iterator, x) called with an iterator not" 1347227825Stheraven " referring to this list"); 1348227825Stheraven#endif 1349227825Stheraven __node_allocator& __na = base::__node_alloc(); 1350232950Stheraven typedef __allocator_destructor<__node_allocator> _Dp; 1351232950Stheraven unique_ptr<__node, _Dp> __hold(__node_alloc_traits::allocate(__na, 1), _Dp(__na, 1)); 1352227825Stheraven __hold->__prev_ = 0; 1353227825Stheraven __node_alloc_traits::construct(__na, _VSTD::addressof(__hold->__value_), __x); 1354253159Stheraven __link_nodes(__p.__ptr_, __hold.get(), __hold.get()); 1355227825Stheraven ++base::__sz(); 1356249998Sdim#if _LIBCPP_DEBUG_LEVEL >= 2 1357249998Sdim return iterator(__hold.release(), this); 1358249998Sdim#else 1359227825Stheraven return iterator(__hold.release()); 1360249998Sdim#endif 1361227825Stheraven} 1362227825Stheraven 1363227825Stheraventemplate <class _Tp, class _Alloc> 1364227825Stheraventypename list<_Tp, _Alloc>::iterator 1365227825Stheravenlist<_Tp, _Alloc>::insert(const_iterator __p, size_type __n, const value_type& __x) 1366227825Stheraven{ 1367227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 1368227825Stheraven _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__p) == this, 1369227825Stheraven "list::insert(iterator, n, x) called with an iterator not" 1370227825Stheraven " referring to this list"); 1371253159Stheraven iterator __r(__p.__ptr_, this); 1372227825Stheraven#else 1373253159Stheraven iterator __r(__p.__ptr_); 1374227825Stheraven#endif 1375227825Stheraven if (__n > 0) 1376227825Stheraven { 1377227825Stheraven size_type __ds = 0; 1378227825Stheraven __node_allocator& __na = base::__node_alloc(); 1379232950Stheraven typedef __allocator_destructor<__node_allocator> _Dp; 1380232950Stheraven unique_ptr<__node, _Dp> __hold(__node_alloc_traits::allocate(__na, 1), _Dp(__na, 1)); 1381227825Stheraven __hold->__prev_ = 0; 1382227825Stheraven __node_alloc_traits::construct(__na, _VSTD::addressof(__hold->__value_), __x); 1383227825Stheraven ++__ds; 1384227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 1385227825Stheraven __r = iterator(__hold.get(), this); 1386227825Stheraven#else 1387227825Stheraven __r = iterator(__hold.get()); 1388227825Stheraven#endif 1389227825Stheraven __hold.release(); 1390227825Stheraven iterator __e = __r; 1391227825Stheraven#ifndef _LIBCPP_NO_EXCEPTIONS 1392227825Stheraven try 1393227825Stheraven { 1394227825Stheraven#endif // _LIBCPP_NO_EXCEPTIONS 1395227825Stheraven for (--__n; __n != 0; --__n, ++__e, ++__ds) 1396227825Stheraven { 1397227825Stheraven __hold.reset(__node_alloc_traits::allocate(__na, 1)); 1398227825Stheraven __node_alloc_traits::construct(__na, _VSTD::addressof(__hold->__value_), __x); 1399227825Stheraven __e.__ptr_->__next_ = __hold.get(); 1400227825Stheraven __hold->__prev_ = __e.__ptr_; 1401227825Stheraven __hold.release(); 1402227825Stheraven } 1403227825Stheraven#ifndef _LIBCPP_NO_EXCEPTIONS 1404227825Stheraven } 1405227825Stheraven catch (...) 1406227825Stheraven { 1407227825Stheraven while (true) 1408227825Stheraven { 1409227825Stheraven __node_alloc_traits::destroy(__na, _VSTD::addressof(*__e)); 1410227825Stheraven __node_pointer __prev = __e.__ptr_->__prev_; 1411227825Stheraven __node_alloc_traits::deallocate(__na, __e.__ptr_, 1); 1412227825Stheraven if (__prev == 0) 1413227825Stheraven break; 1414227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 1415227825Stheraven __e = iterator(__prev, this); 1416227825Stheraven#else 1417227825Stheraven __e = iterator(__prev); 1418227825Stheraven#endif 1419227825Stheraven } 1420227825Stheraven throw; 1421227825Stheraven } 1422227825Stheraven#endif // _LIBCPP_NO_EXCEPTIONS 1423253159Stheraven __link_nodes(__p.__ptr_, __r.__ptr_, __e.__ptr_); 1424227825Stheraven base::__sz() += __ds; 1425227825Stheraven } 1426227825Stheraven return __r; 1427227825Stheraven} 1428227825Stheraven 1429227825Stheraventemplate <class _Tp, class _Alloc> 1430227825Stheraventemplate <class _InpIter> 1431227825Stheraventypename list<_Tp, _Alloc>::iterator 1432227825Stheravenlist<_Tp, _Alloc>::insert(const_iterator __p, _InpIter __f, _InpIter __l, 1433227825Stheraven typename enable_if<__is_input_iterator<_InpIter>::value>::type*) 1434227825Stheraven{ 1435227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 1436227825Stheraven _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__p) == this, 1437227825Stheraven "list::insert(iterator, range) called with an iterator not" 1438227825Stheraven " referring to this list"); 1439253159Stheraven iterator __r(__p.__ptr_, this); 1440227825Stheraven#else 1441253159Stheraven iterator __r(__p.__ptr_); 1442227825Stheraven#endif 1443227825Stheraven if (__f != __l) 1444227825Stheraven { 1445227825Stheraven size_type __ds = 0; 1446227825Stheraven __node_allocator& __na = base::__node_alloc(); 1447232950Stheraven typedef __allocator_destructor<__node_allocator> _Dp; 1448232950Stheraven unique_ptr<__node, _Dp> __hold(__node_alloc_traits::allocate(__na, 1), _Dp(__na, 1)); 1449227825Stheraven __hold->__prev_ = 0; 1450227825Stheraven __node_alloc_traits::construct(__na, _VSTD::addressof(__hold->__value_), *__f); 1451227825Stheraven ++__ds; 1452227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 1453227825Stheraven __r = iterator(__hold.get(), this); 1454227825Stheraven#else 1455227825Stheraven __r = iterator(__hold.get()); 1456227825Stheraven#endif 1457227825Stheraven __hold.release(); 1458227825Stheraven iterator __e = __r; 1459227825Stheraven#ifndef _LIBCPP_NO_EXCEPTIONS 1460227825Stheraven try 1461227825Stheraven { 1462227825Stheraven#endif // _LIBCPP_NO_EXCEPTIONS 1463227825Stheraven for (++__f; __f != __l; ++__f, ++__e, ++__ds) 1464227825Stheraven { 1465227825Stheraven __hold.reset(__node_alloc_traits::allocate(__na, 1)); 1466227825Stheraven __node_alloc_traits::construct(__na, _VSTD::addressof(__hold->__value_), *__f); 1467227825Stheraven __e.__ptr_->__next_ = __hold.get(); 1468227825Stheraven __hold->__prev_ = __e.__ptr_; 1469227825Stheraven __hold.release(); 1470227825Stheraven } 1471227825Stheraven#ifndef _LIBCPP_NO_EXCEPTIONS 1472227825Stheraven } 1473227825Stheraven catch (...) 1474227825Stheraven { 1475227825Stheraven while (true) 1476227825Stheraven { 1477227825Stheraven __node_alloc_traits::destroy(__na, _VSTD::addressof(*__e)); 1478227825Stheraven __node_pointer __prev = __e.__ptr_->__prev_; 1479227825Stheraven __node_alloc_traits::deallocate(__na, __e.__ptr_, 1); 1480227825Stheraven if (__prev == 0) 1481227825Stheraven break; 1482227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 1483227825Stheraven __e = iterator(__prev, this); 1484227825Stheraven#else 1485227825Stheraven __e = iterator(__prev); 1486227825Stheraven#endif 1487227825Stheraven } 1488227825Stheraven throw; 1489227825Stheraven } 1490227825Stheraven#endif // _LIBCPP_NO_EXCEPTIONS 1491253159Stheraven __link_nodes(__p.__ptr_, __r.__ptr_, __e.__ptr_); 1492227825Stheraven base::__sz() += __ds; 1493227825Stheraven } 1494227825Stheraven return __r; 1495227825Stheraven} 1496227825Stheraven 1497227825Stheraventemplate <class _Tp, class _Alloc> 1498227825Stheravenvoid 1499227825Stheravenlist<_Tp, _Alloc>::push_front(const value_type& __x) 1500227825Stheraven{ 1501227825Stheraven __node_allocator& __na = base::__node_alloc(); 1502232950Stheraven typedef __allocator_destructor<__node_allocator> _Dp; 1503232950Stheraven unique_ptr<__node, _Dp> __hold(__node_alloc_traits::allocate(__na, 1), _Dp(__na, 1)); 1504227825Stheraven __node_alloc_traits::construct(__na, _VSTD::addressof(__hold->__value_), __x); 1505253159Stheraven __link_nodes(base::__end_.__next_, __hold.get(), __hold.get()); 1506227825Stheraven ++base::__sz(); 1507227825Stheraven __hold.release(); 1508227825Stheraven} 1509227825Stheraven 1510227825Stheraventemplate <class _Tp, class _Alloc> 1511227825Stheravenvoid 1512227825Stheravenlist<_Tp, _Alloc>::push_back(const value_type& __x) 1513227825Stheraven{ 1514227825Stheraven __node_allocator& __na = base::__node_alloc(); 1515232950Stheraven typedef __allocator_destructor<__node_allocator> _Dp; 1516232950Stheraven unique_ptr<__node, _Dp> __hold(__node_alloc_traits::allocate(__na, 1), _Dp(__na, 1)); 1517227825Stheraven __node_alloc_traits::construct(__na, _VSTD::addressof(__hold->__value_), __x); 1518253159Stheraven __link_nodes(static_cast<__node_pointer>(pointer_traits<__node_base_pointer>:: 1519253159Stheraven pointer_to(base::__end_)), __hold.get(), __hold.get()); 1520227825Stheraven ++base::__sz(); 1521227825Stheraven __hold.release(); 1522227825Stheraven} 1523227825Stheraven 1524227825Stheraven#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 1525227825Stheraven 1526227825Stheraventemplate <class _Tp, class _Alloc> 1527227825Stheravenvoid 1528227825Stheravenlist<_Tp, _Alloc>::push_front(value_type&& __x) 1529227825Stheraven{ 1530227825Stheraven __node_allocator& __na = base::__node_alloc(); 1531232950Stheraven typedef __allocator_destructor<__node_allocator> _Dp; 1532232950Stheraven unique_ptr<__node, _Dp> __hold(__node_alloc_traits::allocate(__na, 1), _Dp(__na, 1)); 1533227825Stheraven __node_alloc_traits::construct(__na, _VSTD::addressof(__hold->__value_), _VSTD::move(__x)); 1534253159Stheraven __link_nodes(base::__end_.__next_, __hold.get(), __hold.get()); 1535227825Stheraven ++base::__sz(); 1536227825Stheraven __hold.release(); 1537227825Stheraven} 1538227825Stheraven 1539227825Stheraventemplate <class _Tp, class _Alloc> 1540227825Stheravenvoid 1541227825Stheravenlist<_Tp, _Alloc>::push_back(value_type&& __x) 1542227825Stheraven{ 1543227825Stheraven __node_allocator& __na = base::__node_alloc(); 1544232950Stheraven typedef __allocator_destructor<__node_allocator> _Dp; 1545232950Stheraven unique_ptr<__node, _Dp> __hold(__node_alloc_traits::allocate(__na, 1), _Dp(__na, 1)); 1546227825Stheraven __node_alloc_traits::construct(__na, _VSTD::addressof(__hold->__value_), _VSTD::move(__x)); 1547253159Stheraven __link_nodes(static_cast<__node_pointer>(pointer_traits<__node_base_pointer>:: 1548253159Stheraven pointer_to(base::__end_)), __hold.get(), __hold.get()); 1549227825Stheraven ++base::__sz(); 1550227825Stheraven __hold.release(); 1551227825Stheraven} 1552227825Stheraven 1553227825Stheraven#ifndef _LIBCPP_HAS_NO_VARIADICS 1554227825Stheraven 1555227825Stheraventemplate <class _Tp, class _Alloc> 1556227825Stheraventemplate <class... _Args> 1557227825Stheravenvoid 1558227825Stheravenlist<_Tp, _Alloc>::emplace_front(_Args&&... __args) 1559227825Stheraven{ 1560227825Stheraven __node_allocator& __na = base::__node_alloc(); 1561232950Stheraven typedef __allocator_destructor<__node_allocator> _Dp; 1562232950Stheraven unique_ptr<__node, _Dp> __hold(__node_alloc_traits::allocate(__na, 1), _Dp(__na, 1)); 1563227825Stheraven __node_alloc_traits::construct(__na, _VSTD::addressof(__hold->__value_), _VSTD::forward<_Args>(__args)...); 1564253159Stheraven __link_nodes(base::__end_.__next_, __hold.get(), __hold.get()); 1565227825Stheraven ++base::__sz(); 1566227825Stheraven __hold.release(); 1567227825Stheraven} 1568227825Stheraven 1569227825Stheraventemplate <class _Tp, class _Alloc> 1570227825Stheraventemplate <class... _Args> 1571227825Stheravenvoid 1572227825Stheravenlist<_Tp, _Alloc>::emplace_back(_Args&&... __args) 1573227825Stheraven{ 1574227825Stheraven __node_allocator& __na = base::__node_alloc(); 1575232950Stheraven typedef __allocator_destructor<__node_allocator> _Dp; 1576232950Stheraven unique_ptr<__node, _Dp> __hold(__node_alloc_traits::allocate(__na, 1), _Dp(__na, 1)); 1577227825Stheraven __node_alloc_traits::construct(__na, _VSTD::addressof(__hold->__value_), _VSTD::forward<_Args>(__args)...); 1578253159Stheraven __link_nodes(static_cast<__node_pointer>(pointer_traits<__node_base_pointer>:: 1579253159Stheraven pointer_to(base::__end_)), __hold.get(), __hold.get()); 1580227825Stheraven ++base::__sz(); 1581227825Stheraven __hold.release(); 1582227825Stheraven} 1583227825Stheraven 1584227825Stheraventemplate <class _Tp, class _Alloc> 1585227825Stheraventemplate <class... _Args> 1586227825Stheraventypename list<_Tp, _Alloc>::iterator 1587227825Stheravenlist<_Tp, _Alloc>::emplace(const_iterator __p, _Args&&... __args) 1588227825Stheraven{ 1589249998Sdim#if _LIBCPP_DEBUG_LEVEL >= 2 1590249998Sdim _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__p) == this, 1591249998Sdim "list::emplace(iterator, args...) called with an iterator not" 1592249998Sdim " referring to this list"); 1593249998Sdim#endif 1594227825Stheraven __node_allocator& __na = base::__node_alloc(); 1595232950Stheraven typedef __allocator_destructor<__node_allocator> _Dp; 1596232950Stheraven unique_ptr<__node, _Dp> __hold(__node_alloc_traits::allocate(__na, 1), _Dp(__na, 1)); 1597227825Stheraven __hold->__prev_ = 0; 1598227825Stheraven __node_alloc_traits::construct(__na, _VSTD::addressof(__hold->__value_), _VSTD::forward<_Args>(__args)...); 1599253159Stheraven __link_nodes(__p.__ptr_, __hold.get(), __hold.get()); 1600227825Stheraven ++base::__sz(); 1601227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 1602227825Stheraven return iterator(__hold.release(), this); 1603227825Stheraven#else 1604227825Stheraven return iterator(__hold.release()); 1605227825Stheraven#endif 1606227825Stheraven} 1607227825Stheraven 1608227825Stheraven#endif // _LIBCPP_HAS_NO_VARIADICS 1609227825Stheraven 1610227825Stheraventemplate <class _Tp, class _Alloc> 1611227825Stheraventypename list<_Tp, _Alloc>::iterator 1612227825Stheravenlist<_Tp, _Alloc>::insert(const_iterator __p, value_type&& __x) 1613227825Stheraven{ 1614227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 1615227825Stheraven _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__p) == this, 1616227825Stheraven "list::insert(iterator, x) called with an iterator not" 1617227825Stheraven " referring to this list"); 1618227825Stheraven#endif 1619227825Stheraven __node_allocator& __na = base::__node_alloc(); 1620232950Stheraven typedef __allocator_destructor<__node_allocator> _Dp; 1621232950Stheraven unique_ptr<__node, _Dp> __hold(__node_alloc_traits::allocate(__na, 1), _Dp(__na, 1)); 1622227825Stheraven __hold->__prev_ = 0; 1623227825Stheraven __node_alloc_traits::construct(__na, _VSTD::addressof(__hold->__value_), _VSTD::move(__x)); 1624253159Stheraven __link_nodes(__p.__ptr_, __hold.get(), __hold.get()); 1625227825Stheraven ++base::__sz(); 1626227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 1627227825Stheraven return iterator(__hold.release(), this); 1628227825Stheraven#else 1629227825Stheraven return iterator(__hold.release()); 1630227825Stheraven#endif 1631227825Stheraven} 1632227825Stheraven 1633227825Stheraven#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 1634227825Stheraven 1635227825Stheraventemplate <class _Tp, class _Alloc> 1636227825Stheravenvoid 1637227825Stheravenlist<_Tp, _Alloc>::pop_front() 1638227825Stheraven{ 1639227825Stheraven _LIBCPP_ASSERT(!empty(), "list::pop_front() called with empty list"); 1640227825Stheraven __node_allocator& __na = base::__node_alloc(); 1641253159Stheraven __node_pointer __n = base::__end_.__next_; 1642227825Stheraven base::__unlink_nodes(__n, __n); 1643227825Stheraven --base::__sz(); 1644227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 1645227825Stheraven __c_node* __c = __get_db()->__find_c_and_lock(this); 1646227825Stheraven for (__i_node** __p = __c->end_; __p != __c->beg_; ) 1647227825Stheraven { 1648227825Stheraven --__p; 1649227825Stheraven iterator* __i = static_cast<iterator*>((*__p)->__i_); 1650253159Stheraven if (__i->__ptr_ == __n) 1651227825Stheraven { 1652227825Stheraven (*__p)->__c_ = nullptr; 1653227825Stheraven if (--__c->end_ != __p) 1654227825Stheraven memmove(__p, __p+1, (__c->end_ - __p)*sizeof(__i_node*)); 1655227825Stheraven } 1656227825Stheraven } 1657227825Stheraven __get_db()->unlock(); 1658227825Stheraven#endif 1659253159Stheraven __node_alloc_traits::destroy(__na, _VSTD::addressof(__n->__value_)); 1660253159Stheraven __node_alloc_traits::deallocate(__na, __n, 1); 1661227825Stheraven} 1662227825Stheraven 1663227825Stheraventemplate <class _Tp, class _Alloc> 1664227825Stheravenvoid 1665227825Stheravenlist<_Tp, _Alloc>::pop_back() 1666227825Stheraven{ 1667253159Stheraven _LIBCPP_ASSERT(!empty(), "list::pop_back() called with empty list"); 1668227825Stheraven __node_allocator& __na = base::__node_alloc(); 1669253159Stheraven __node_pointer __n = base::__end_.__prev_; 1670227825Stheraven base::__unlink_nodes(__n, __n); 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_); 1678253159Stheraven 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 1687253159Stheraven __node_alloc_traits::destroy(__na, _VSTD::addressof(__n->__value_)); 1688253159Stheraven __node_alloc_traits::deallocate(__na, __n, 1); 1689227825Stheraven} 1690227825Stheraven 1691227825Stheraventemplate <class _Tp, class _Alloc> 1692227825Stheraventypename list<_Tp, _Alloc>::iterator 1693227825Stheravenlist<_Tp, _Alloc>::erase(const_iterator __p) 1694227825Stheraven{ 1695227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 1696227825Stheraven _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__p) == this, 1697227825Stheraven "list::erase(iterator) called with an iterator not" 1698227825Stheraven " referring to this list"); 1699227825Stheraven#endif 1700249998Sdim _LIBCPP_ASSERT(__p != end(), 1701249998Sdim "list::erase(iterator) called with a non-dereferenceable iterator"); 1702227825Stheraven __node_allocator& __na = base::__node_alloc(); 1703253159Stheraven __node_pointer __n = __p.__ptr_; 1704253159Stheraven __node_pointer __r = __n->__next_; 1705227825Stheraven base::__unlink_nodes(__n, __n); 1706227825Stheraven --base::__sz(); 1707227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 1708227825Stheraven __c_node* __c = __get_db()->__find_c_and_lock(this); 1709227825Stheraven for (__i_node** __p = __c->end_; __p != __c->beg_; ) 1710227825Stheraven { 1711227825Stheraven --__p; 1712227825Stheraven iterator* __i = static_cast<iterator*>((*__p)->__i_); 1713253159Stheraven if (__i->__ptr_ == __n) 1714227825Stheraven { 1715227825Stheraven (*__p)->__c_ = nullptr; 1716227825Stheraven if (--__c->end_ != __p) 1717227825Stheraven memmove(__p, __p+1, (__c->end_ - __p)*sizeof(__i_node*)); 1718227825Stheraven } 1719227825Stheraven } 1720227825Stheraven __get_db()->unlock(); 1721227825Stheraven#endif 1722253159Stheraven __node_alloc_traits::destroy(__na, _VSTD::addressof(__n->__value_)); 1723253159Stheraven __node_alloc_traits::deallocate(__na, __n, 1); 1724227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 1725227825Stheraven return iterator(__r, this); 1726227825Stheraven#else 1727227825Stheraven return iterator(__r); 1728227825Stheraven#endif 1729227825Stheraven} 1730227825Stheraven 1731227825Stheraventemplate <class _Tp, class _Alloc> 1732227825Stheraventypename list<_Tp, _Alloc>::iterator 1733227825Stheravenlist<_Tp, _Alloc>::erase(const_iterator __f, const_iterator __l) 1734227825Stheraven{ 1735227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 1736227825Stheraven _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__f) == this, 1737227825Stheraven "list::erase(iterator, iterator) called with an iterator not" 1738227825Stheraven " referring to this list"); 1739227825Stheraven#endif 1740227825Stheraven if (__f != __l) 1741227825Stheraven { 1742227825Stheraven __node_allocator& __na = base::__node_alloc(); 1743253159Stheraven base::__unlink_nodes(__f.__ptr_, __l.__ptr_->__prev_); 1744227825Stheraven while (__f != __l) 1745227825Stheraven { 1746253159Stheraven __node_pointer __n = __f.__ptr_; 1747227825Stheraven ++__f; 1748227825Stheraven --base::__sz(); 1749227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 1750227825Stheraven __c_node* __c = __get_db()->__find_c_and_lock(this); 1751227825Stheraven for (__i_node** __p = __c->end_; __p != __c->beg_; ) 1752227825Stheraven { 1753227825Stheraven --__p; 1754227825Stheraven iterator* __i = static_cast<iterator*>((*__p)->__i_); 1755253159Stheraven if (__i->__ptr_ == __n) 1756227825Stheraven { 1757227825Stheraven (*__p)->__c_ = nullptr; 1758227825Stheraven if (--__c->end_ != __p) 1759227825Stheraven memmove(__p, __p+1, (__c->end_ - __p)*sizeof(__i_node*)); 1760227825Stheraven } 1761227825Stheraven } 1762227825Stheraven __get_db()->unlock(); 1763227825Stheraven#endif 1764253159Stheraven __node_alloc_traits::destroy(__na, _VSTD::addressof(__n->__value_)); 1765253159Stheraven __node_alloc_traits::deallocate(__na, __n, 1); 1766227825Stheraven } 1767227825Stheraven } 1768227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 1769253159Stheraven return iterator(__l.__ptr_, this); 1770227825Stheraven#else 1771253159Stheraven return iterator(__l.__ptr_); 1772227825Stheraven#endif 1773227825Stheraven} 1774227825Stheraven 1775227825Stheraventemplate <class _Tp, class _Alloc> 1776227825Stheravenvoid 1777227825Stheravenlist<_Tp, _Alloc>::resize(size_type __n) 1778227825Stheraven{ 1779227825Stheraven if (__n < base::__sz()) 1780227825Stheraven erase(__iterator(__n), end()); 1781227825Stheraven else if (__n > base::__sz()) 1782227825Stheraven { 1783227825Stheraven __n -= base::__sz(); 1784227825Stheraven size_type __ds = 0; 1785227825Stheraven __node_allocator& __na = base::__node_alloc(); 1786232950Stheraven typedef __allocator_destructor<__node_allocator> _Dp; 1787232950Stheraven unique_ptr<__node, _Dp> __hold(__node_alloc_traits::allocate(__na, 1), _Dp(__na, 1)); 1788227825Stheraven __hold->__prev_ = 0; 1789227825Stheraven __node_alloc_traits::construct(__na, _VSTD::addressof(__hold->__value_)); 1790227825Stheraven ++__ds; 1791227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 1792227825Stheraven iterator __r = iterator(__hold.release(), this); 1793227825Stheraven#else 1794227825Stheraven iterator __r = iterator(__hold.release()); 1795227825Stheraven#endif 1796227825Stheraven iterator __e = __r; 1797227825Stheraven#ifndef _LIBCPP_NO_EXCEPTIONS 1798227825Stheraven try 1799227825Stheraven { 1800227825Stheraven#endif // _LIBCPP_NO_EXCEPTIONS 1801227825Stheraven for (--__n; __n != 0; --__n, ++__e, ++__ds) 1802227825Stheraven { 1803227825Stheraven __hold.reset(__node_alloc_traits::allocate(__na, 1)); 1804227825Stheraven __node_alloc_traits::construct(__na, _VSTD::addressof(__hold->__value_)); 1805227825Stheraven __e.__ptr_->__next_ = __hold.get(); 1806227825Stheraven __hold->__prev_ = __e.__ptr_; 1807227825Stheraven __hold.release(); 1808227825Stheraven } 1809227825Stheraven#ifndef _LIBCPP_NO_EXCEPTIONS 1810227825Stheraven } 1811227825Stheraven catch (...) 1812227825Stheraven { 1813227825Stheraven while (true) 1814227825Stheraven { 1815227825Stheraven __node_alloc_traits::destroy(__na, _VSTD::addressof(*__e)); 1816227825Stheraven __node_pointer __prev = __e.__ptr_->__prev_; 1817227825Stheraven __node_alloc_traits::deallocate(__na, __e.__ptr_, 1); 1818227825Stheraven if (__prev == 0) 1819227825Stheraven break; 1820227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 1821227825Stheraven __e = iterator(__prev, this); 1822227825Stheraven#else 1823227825Stheraven __e = iterator(__prev); 1824227825Stheraven#endif 1825227825Stheraven } 1826227825Stheraven throw; 1827227825Stheraven } 1828227825Stheraven#endif // _LIBCPP_NO_EXCEPTIONS 1829253159Stheraven __link_nodes(static_cast<__node_pointer>(pointer_traits<__node_base_pointer>:: 1830253159Stheraven pointer_to(base::__end_)), __r.__ptr_, __e.__ptr_); 1831227825Stheraven base::__sz() += __ds; 1832227825Stheraven } 1833227825Stheraven} 1834227825Stheraven 1835227825Stheraventemplate <class _Tp, class _Alloc> 1836227825Stheravenvoid 1837227825Stheravenlist<_Tp, _Alloc>::resize(size_type __n, const value_type& __x) 1838227825Stheraven{ 1839227825Stheraven if (__n < base::__sz()) 1840227825Stheraven erase(__iterator(__n), end()); 1841227825Stheraven else if (__n > base::__sz()) 1842227825Stheraven { 1843227825Stheraven __n -= base::__sz(); 1844227825Stheraven size_type __ds = 0; 1845227825Stheraven __node_allocator& __na = base::__node_alloc(); 1846232950Stheraven typedef __allocator_destructor<__node_allocator> _Dp; 1847232950Stheraven unique_ptr<__node, _Dp> __hold(__node_alloc_traits::allocate(__na, 1), _Dp(__na, 1)); 1848227825Stheraven __hold->__prev_ = 0; 1849227825Stheraven __node_alloc_traits::construct(__na, _VSTD::addressof(__hold->__value_), __x); 1850227825Stheraven ++__ds; 1851227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 1852227825Stheraven iterator __r = iterator(__hold.release(), this); 1853227825Stheraven#else 1854227825Stheraven iterator __r = iterator(__hold.release()); 1855227825Stheraven#endif 1856227825Stheraven iterator __e = __r; 1857227825Stheraven#ifndef _LIBCPP_NO_EXCEPTIONS 1858227825Stheraven try 1859227825Stheraven { 1860227825Stheraven#endif // _LIBCPP_NO_EXCEPTIONS 1861227825Stheraven for (--__n; __n != 0; --__n, ++__e, ++__ds) 1862227825Stheraven { 1863227825Stheraven __hold.reset(__node_alloc_traits::allocate(__na, 1)); 1864227825Stheraven __node_alloc_traits::construct(__na, _VSTD::addressof(__hold->__value_), __x); 1865227825Stheraven __e.__ptr_->__next_ = __hold.get(); 1866227825Stheraven __hold->__prev_ = __e.__ptr_; 1867227825Stheraven __hold.release(); 1868227825Stheraven } 1869227825Stheraven#ifndef _LIBCPP_NO_EXCEPTIONS 1870227825Stheraven } 1871227825Stheraven catch (...) 1872227825Stheraven { 1873227825Stheraven while (true) 1874227825Stheraven { 1875227825Stheraven __node_alloc_traits::destroy(__na, _VSTD::addressof(*__e)); 1876227825Stheraven __node_pointer __prev = __e.__ptr_->__prev_; 1877227825Stheraven __node_alloc_traits::deallocate(__na, __e.__ptr_, 1); 1878227825Stheraven if (__prev == 0) 1879227825Stheraven break; 1880227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 1881227825Stheraven __e = iterator(__prev, this); 1882227825Stheraven#else 1883227825Stheraven __e = iterator(__prev); 1884227825Stheraven#endif 1885227825Stheraven } 1886227825Stheraven throw; 1887227825Stheraven } 1888227825Stheraven#endif // _LIBCPP_NO_EXCEPTIONS 1889253159Stheraven __link_nodes(static_cast<__node_pointer>(pointer_traits<__node_base_pointer>:: 1890253159Stheraven pointer_to(base::__end_)), __r.__ptr_, __e.__ptr_); 1891227825Stheraven base::__sz() += __ds; 1892227825Stheraven } 1893227825Stheraven} 1894227825Stheraven 1895227825Stheraventemplate <class _Tp, class _Alloc> 1896227825Stheravenvoid 1897227825Stheravenlist<_Tp, _Alloc>::splice(const_iterator __p, list& __c) 1898227825Stheraven{ 1899227825Stheraven _LIBCPP_ASSERT(this != &__c, 1900227825Stheraven "list::splice(iterator, list) called with this == &list"); 1901227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 1902227825Stheraven _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__p) == this, 1903227825Stheraven "list::splice(iterator, list) called with an iterator not" 1904227825Stheraven " referring to this list"); 1905227825Stheraven#endif 1906227825Stheraven if (!__c.empty()) 1907227825Stheraven { 1908253159Stheraven __node_pointer __f = __c.__end_.__next_; 1909253159Stheraven __node_pointer __l = __c.__end_.__prev_; 1910227825Stheraven base::__unlink_nodes(__f, __l); 1911253159Stheraven __link_nodes(__p.__ptr_, __f, __l); 1912227825Stheraven base::__sz() += __c.__sz(); 1913227825Stheraven __c.__sz() = 0; 1914227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 1915227825Stheraven __libcpp_db* __db = __get_db(); 1916227825Stheraven __c_node* __cn1 = __db->__find_c_and_lock(this); 1917227825Stheraven __c_node* __cn2 = __db->__find_c(&__c); 1918227825Stheraven for (__i_node** __p = __cn2->end_; __p != __cn2->beg_;) 1919227825Stheraven { 1920227825Stheraven --__p; 1921227825Stheraven iterator* __i = static_cast<iterator*>((*__p)->__i_); 1922253159Stheraven if (__i->__ptr_ != static_cast<__node_pointer>( 1923253159Stheraven pointer_traits<__node_base_pointer>::pointer_to(__c.__end_))) 1924227825Stheraven { 1925227825Stheraven __cn1->__add(*__p); 1926227825Stheraven (*__p)->__c_ = __cn1; 1927227825Stheraven if (--__cn2->end_ != __p) 1928227825Stheraven memmove(__p, __p+1, (__cn2->end_ - __p)*sizeof(__i_node*)); 1929227825Stheraven } 1930227825Stheraven } 1931227825Stheraven __db->unlock(); 1932227825Stheraven#endif 1933227825Stheraven } 1934227825Stheraven} 1935227825Stheraven 1936227825Stheraventemplate <class _Tp, class _Alloc> 1937227825Stheravenvoid 1938227825Stheravenlist<_Tp, _Alloc>::splice(const_iterator __p, list& __c, const_iterator __i) 1939227825Stheraven{ 1940227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 1941227825Stheraven _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__p) == this, 1942227825Stheraven "list::splice(iterator, list, iterator) called with first iterator not" 1943227825Stheraven " referring to this list"); 1944227825Stheraven _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__i) == &__c, 1945227825Stheraven "list::splice(iterator, list, iterator) called with second iterator not" 1946227825Stheraven " referring to list argument"); 1947227825Stheraven _LIBCPP_ASSERT(__get_const_db()->__dereferenceable(&__i), 1948227825Stheraven "list::splice(iterator, list, iterator) called with second iterator not" 1949227825Stheraven " derefereceable"); 1950227825Stheraven#endif 1951227825Stheraven if (__p.__ptr_ != __i.__ptr_ && __p.__ptr_ != __i.__ptr_->__next_) 1952227825Stheraven { 1953253159Stheraven __node_pointer __f = __i.__ptr_; 1954227825Stheraven base::__unlink_nodes(__f, __f); 1955253159Stheraven __link_nodes(__p.__ptr_, __f, __f); 1956227825Stheraven --__c.__sz(); 1957227825Stheraven ++base::__sz(); 1958227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 1959227825Stheraven __libcpp_db* __db = __get_db(); 1960227825Stheraven __c_node* __cn1 = __db->__find_c_and_lock(this); 1961227825Stheraven __c_node* __cn2 = __db->__find_c(&__c); 1962227825Stheraven for (__i_node** __p = __cn2->end_; __p != __cn2->beg_;) 1963227825Stheraven { 1964227825Stheraven --__p; 1965227825Stheraven iterator* __j = static_cast<iterator*>((*__p)->__i_); 1966253159Stheraven if (__j->__ptr_ == __f) 1967227825Stheraven { 1968227825Stheraven __cn1->__add(*__p); 1969227825Stheraven (*__p)->__c_ = __cn1; 1970227825Stheraven if (--__cn2->end_ != __p) 1971227825Stheraven memmove(__p, __p+1, (__cn2->end_ - __p)*sizeof(__i_node*)); 1972227825Stheraven } 1973227825Stheraven } 1974227825Stheraven __db->unlock(); 1975227825Stheraven#endif 1976227825Stheraven } 1977227825Stheraven} 1978227825Stheraven 1979227825Stheraventemplate <class _Tp, class _Alloc> 1980227825Stheravenvoid 1981227825Stheravenlist<_Tp, _Alloc>::splice(const_iterator __p, list& __c, const_iterator __f, const_iterator __l) 1982227825Stheraven{ 1983227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 1984227825Stheraven _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__p) == this, 1985227825Stheraven "list::splice(iterator, list, iterator, iterator) called with first iterator not" 1986227825Stheraven " referring to this list"); 1987227825Stheraven _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__f) == &__c, 1988227825Stheraven "list::splice(iterator, list, iterator, iterator) called with second iterator not" 1989227825Stheraven " referring to list argument"); 1990227825Stheraven if (this == &__c) 1991227825Stheraven { 1992227825Stheraven for (const_iterator __i = __f; __i != __l; ++__i) 1993227825Stheraven _LIBCPP_ASSERT(__i != __p, 1994227825Stheraven "list::splice(iterator, list, iterator, iterator)" 1995227825Stheraven " called with the first iterator within the range" 1996227825Stheraven " of the second and third iterators"); 1997227825Stheraven } 1998227825Stheraven#endif 1999227825Stheraven if (__f != __l) 2000227825Stheraven { 2001227825Stheraven if (this != &__c) 2002227825Stheraven { 2003227825Stheraven size_type __s = _VSTD::distance(__f, __l); 2004227825Stheraven __c.__sz() -= __s; 2005227825Stheraven base::__sz() += __s; 2006227825Stheraven } 2007253159Stheraven __node_pointer __first = __f.__ptr_; 2008227825Stheraven --__l; 2009253159Stheraven __node_pointer __last = __l.__ptr_; 2010227825Stheraven base::__unlink_nodes(__first, __last); 2011253159Stheraven __link_nodes(__p.__ptr_, __first, __last); 2012227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 2013227825Stheraven __libcpp_db* __db = __get_db(); 2014227825Stheraven __c_node* __cn1 = __db->__find_c_and_lock(this); 2015227825Stheraven __c_node* __cn2 = __db->__find_c(&__c); 2016227825Stheraven for (__i_node** __p = __cn2->end_; __p != __cn2->beg_;) 2017227825Stheraven { 2018227825Stheraven --__p; 2019227825Stheraven iterator* __j = static_cast<iterator*>((*__p)->__i_); 2020253159Stheraven for (__node_pointer __k = __f.__ptr_; 2021227825Stheraven __k != __l.__ptr_; __k = __k->__next_) 2022227825Stheraven { 2023227825Stheraven if (__j->__ptr_ == __k) 2024227825Stheraven { 2025227825Stheraven __cn1->__add(*__p); 2026227825Stheraven (*__p)->__c_ = __cn1; 2027227825Stheraven if (--__cn2->end_ != __p) 2028227825Stheraven memmove(__p, __p+1, (__cn2->end_ - __p)*sizeof(__i_node*)); 2029227825Stheraven } 2030227825Stheraven } 2031227825Stheraven } 2032227825Stheraven __db->unlock(); 2033227825Stheraven#endif 2034227825Stheraven } 2035227825Stheraven} 2036227825Stheraven 2037227825Stheraventemplate <class _Tp, class _Alloc> 2038227825Stheravenvoid 2039227825Stheravenlist<_Tp, _Alloc>::remove(const value_type& __x) 2040227825Stheraven{ 2041227825Stheraven for (iterator __i = begin(), __e = end(); __i != __e;) 2042227825Stheraven { 2043227825Stheraven if (*__i == __x) 2044227825Stheraven { 2045227825Stheraven iterator __j = _VSTD::next(__i); 2046227825Stheraven for (; __j != __e && *__j == __x; ++__j) 2047227825Stheraven ; 2048227825Stheraven __i = erase(__i, __j); 2049227825Stheraven } 2050227825Stheraven else 2051227825Stheraven ++__i; 2052227825Stheraven } 2053227825Stheraven} 2054227825Stheraven 2055227825Stheraventemplate <class _Tp, class _Alloc> 2056227825Stheraventemplate <class _Pred> 2057227825Stheravenvoid 2058227825Stheravenlist<_Tp, _Alloc>::remove_if(_Pred __pred) 2059227825Stheraven{ 2060227825Stheraven for (iterator __i = begin(), __e = end(); __i != __e;) 2061227825Stheraven { 2062227825Stheraven if (__pred(*__i)) 2063227825Stheraven { 2064227825Stheraven iterator __j = _VSTD::next(__i); 2065227825Stheraven for (; __j != __e && __pred(*__j); ++__j) 2066227825Stheraven ; 2067227825Stheraven __i = erase(__i, __j); 2068227825Stheraven } 2069227825Stheraven else 2070227825Stheraven ++__i; 2071227825Stheraven } 2072227825Stheraven} 2073227825Stheraven 2074227825Stheraventemplate <class _Tp, class _Alloc> 2075227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 2076227825Stheravenvoid 2077227825Stheravenlist<_Tp, _Alloc>::unique() 2078227825Stheraven{ 2079227825Stheraven unique(__equal_to<value_type>()); 2080227825Stheraven} 2081227825Stheraven 2082227825Stheraventemplate <class _Tp, class _Alloc> 2083227825Stheraventemplate <class _BinaryPred> 2084227825Stheravenvoid 2085227825Stheravenlist<_Tp, _Alloc>::unique(_BinaryPred __binary_pred) 2086227825Stheraven{ 2087227825Stheraven for (iterator __i = begin(), __e = end(); __i != __e;) 2088227825Stheraven { 2089227825Stheraven iterator __j = _VSTD::next(__i); 2090227825Stheraven for (; __j != __e && __binary_pred(*__i, *__j); ++__j) 2091227825Stheraven ; 2092227825Stheraven if (++__i != __j) 2093227825Stheraven __i = erase(__i, __j); 2094227825Stheraven } 2095227825Stheraven} 2096227825Stheraven 2097227825Stheraventemplate <class _Tp, class _Alloc> 2098227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 2099227825Stheravenvoid 2100227825Stheravenlist<_Tp, _Alloc>::merge(list& __c) 2101227825Stheraven{ 2102227825Stheraven merge(__c, __less<value_type>()); 2103227825Stheraven} 2104227825Stheraven 2105227825Stheraventemplate <class _Tp, class _Alloc> 2106227825Stheraventemplate <class _Comp> 2107227825Stheravenvoid 2108227825Stheravenlist<_Tp, _Alloc>::merge(list& __c, _Comp __comp) 2109227825Stheraven{ 2110227825Stheraven if (this != &__c) 2111227825Stheraven { 2112227825Stheraven iterator __f1 = begin(); 2113227825Stheraven iterator __e1 = end(); 2114227825Stheraven iterator __f2 = __c.begin(); 2115227825Stheraven iterator __e2 = __c.end(); 2116227825Stheraven while (__f1 != __e1 && __f2 != __e2) 2117227825Stheraven { 2118227825Stheraven if (__comp(*__f2, *__f1)) 2119227825Stheraven { 2120227825Stheraven size_type __ds = 1; 2121227825Stheraven iterator __m2 = _VSTD::next(__f2); 2122227825Stheraven for (; __m2 != __e2 && __comp(*__m2, *__f1); ++__m2, ++__ds) 2123227825Stheraven ; 2124227825Stheraven base::__sz() += __ds; 2125227825Stheraven __c.__sz() -= __ds; 2126253159Stheraven __node_pointer __f = __f2.__ptr_; 2127253159Stheraven __node_pointer __l = __m2.__ptr_->__prev_; 2128227825Stheraven __f2 = __m2; 2129227825Stheraven base::__unlink_nodes(__f, __l); 2130227825Stheraven __m2 = _VSTD::next(__f1); 2131253159Stheraven __link_nodes(__f1.__ptr_, __f, __l); 2132227825Stheraven __f1 = __m2; 2133227825Stheraven } 2134227825Stheraven else 2135227825Stheraven ++__f1; 2136227825Stheraven } 2137227825Stheraven splice(__e1, __c); 2138227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 2139227825Stheraven __libcpp_db* __db = __get_db(); 2140227825Stheraven __c_node* __cn1 = __db->__find_c_and_lock(this); 2141227825Stheraven __c_node* __cn2 = __db->__find_c(&__c); 2142227825Stheraven for (__i_node** __p = __cn2->end_; __p != __cn2->beg_;) 2143227825Stheraven { 2144227825Stheraven --__p; 2145227825Stheraven iterator* __i = static_cast<iterator*>((*__p)->__i_); 2146253159Stheraven if (__i->__ptr_ != static_cast<__node_pointer>( 2147253159Stheraven pointer_traits<__node_base_pointer>::pointer_to(__c.__end_))) 2148227825Stheraven { 2149227825Stheraven __cn1->__add(*__p); 2150227825Stheraven (*__p)->__c_ = __cn1; 2151227825Stheraven if (--__cn2->end_ != __p) 2152227825Stheraven memmove(__p, __p+1, (__cn2->end_ - __p)*sizeof(__i_node*)); 2153227825Stheraven } 2154227825Stheraven } 2155227825Stheraven __db->unlock(); 2156227825Stheraven#endif 2157227825Stheraven } 2158227825Stheraven} 2159227825Stheraven 2160227825Stheraventemplate <class _Tp, class _Alloc> 2161227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 2162227825Stheravenvoid 2163227825Stheravenlist<_Tp, _Alloc>::sort() 2164227825Stheraven{ 2165227825Stheraven sort(__less<value_type>()); 2166227825Stheraven} 2167227825Stheraven 2168227825Stheraventemplate <class _Tp, class _Alloc> 2169227825Stheraventemplate <class _Comp> 2170227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 2171227825Stheravenvoid 2172227825Stheravenlist<_Tp, _Alloc>::sort(_Comp __comp) 2173227825Stheraven{ 2174227825Stheraven __sort(begin(), end(), base::__sz(), __comp); 2175227825Stheraven} 2176227825Stheraven 2177227825Stheraventemplate <class _Tp, class _Alloc> 2178227825Stheraventemplate <class _Comp> 2179227825Stheraventypename list<_Tp, _Alloc>::iterator 2180227825Stheravenlist<_Tp, _Alloc>::__sort(iterator __f1, iterator __e2, size_type __n, _Comp& __comp) 2181227825Stheraven{ 2182227825Stheraven switch (__n) 2183227825Stheraven { 2184227825Stheraven case 0: 2185227825Stheraven case 1: 2186227825Stheraven return __f1; 2187227825Stheraven case 2: 2188227825Stheraven if (__comp(*--__e2, *__f1)) 2189227825Stheraven { 2190253159Stheraven __node_pointer __f = __e2.__ptr_; 2191227825Stheraven base::__unlink_nodes(__f, __f); 2192253159Stheraven __link_nodes(__f1.__ptr_, __f, __f); 2193227825Stheraven return __e2; 2194227825Stheraven } 2195227825Stheraven return __f1; 2196227825Stheraven } 2197227825Stheraven size_type __n2 = __n / 2; 2198227825Stheraven iterator __e1 = _VSTD::next(__f1, __n2); 2199227825Stheraven iterator __r = __f1 = __sort(__f1, __e1, __n2, __comp); 2200227825Stheraven iterator __f2 = __e1 = __sort(__e1, __e2, __n - __n2, __comp); 2201227825Stheraven if (__comp(*__f2, *__f1)) 2202227825Stheraven { 2203227825Stheraven iterator __m2 = _VSTD::next(__f2); 2204227825Stheraven for (; __m2 != __e2 && __comp(*__m2, *__f1); ++__m2) 2205227825Stheraven ; 2206253159Stheraven __node_pointer __f = __f2.__ptr_; 2207253159Stheraven __node_pointer __l = __m2.__ptr_->__prev_; 2208227825Stheraven __r = __f2; 2209227825Stheraven __e1 = __f2 = __m2; 2210227825Stheraven base::__unlink_nodes(__f, __l); 2211227825Stheraven __m2 = _VSTD::next(__f1); 2212253159Stheraven __link_nodes(__f1.__ptr_, __f, __l); 2213227825Stheraven __f1 = __m2; 2214227825Stheraven } 2215227825Stheraven else 2216227825Stheraven ++__f1; 2217227825Stheraven while (__f1 != __e1 && __f2 != __e2) 2218227825Stheraven { 2219227825Stheraven if (__comp(*__f2, *__f1)) 2220227825Stheraven { 2221227825Stheraven iterator __m2 = _VSTD::next(__f2); 2222227825Stheraven for (; __m2 != __e2 && __comp(*__m2, *__f1); ++__m2) 2223227825Stheraven ; 2224253159Stheraven __node_pointer __f = __f2.__ptr_; 2225253159Stheraven __node_pointer __l = __m2.__ptr_->__prev_; 2226227825Stheraven if (__e1 == __f2) 2227227825Stheraven __e1 = __m2; 2228227825Stheraven __f2 = __m2; 2229227825Stheraven base::__unlink_nodes(__f, __l); 2230227825Stheraven __m2 = _VSTD::next(__f1); 2231253159Stheraven __link_nodes(__f1.__ptr_, __f, __l); 2232227825Stheraven __f1 = __m2; 2233227825Stheraven } 2234227825Stheraven else 2235227825Stheraven ++__f1; 2236227825Stheraven } 2237227825Stheraven return __r; 2238227825Stheraven} 2239227825Stheraven 2240227825Stheraventemplate <class _Tp, class _Alloc> 2241227825Stheravenvoid 2242227825Stheravenlist<_Tp, _Alloc>::reverse() _NOEXCEPT 2243227825Stheraven{ 2244227825Stheraven if (base::__sz() > 1) 2245227825Stheraven { 2246227825Stheraven iterator __e = end(); 2247227825Stheraven for (iterator __i = begin(); __i.__ptr_ != __e.__ptr_;) 2248227825Stheraven { 2249227825Stheraven _VSTD::swap(__i.__ptr_->__prev_, __i.__ptr_->__next_); 2250227825Stheraven __i.__ptr_ = __i.__ptr_->__prev_; 2251227825Stheraven } 2252227825Stheraven _VSTD::swap(__e.__ptr_->__prev_, __e.__ptr_->__next_); 2253227825Stheraven } 2254227825Stheraven} 2255227825Stheraven 2256227825Stheraventemplate <class _Tp, class _Alloc> 2257227825Stheravenbool 2258227825Stheravenlist<_Tp, _Alloc>::__invariants() const 2259227825Stheraven{ 2260227825Stheraven return size() == _VSTD::distance(begin(), end()); 2261227825Stheraven} 2262227825Stheraven 2263227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 2264227825Stheraven 2265227825Stheraventemplate <class _Tp, class _Alloc> 2266227825Stheravenbool 2267227825Stheravenlist<_Tp, _Alloc>::__dereferenceable(const const_iterator* __i) const 2268227825Stheraven{ 2269253159Stheraven return __i->__ptr_ != static_cast<__node_pointer>( 2270253159Stheraven pointer_traits<__node_base_pointer>::pointer_to(const_cast<__node_base&>(this->__end_))); 2271227825Stheraven} 2272227825Stheraven 2273227825Stheraventemplate <class _Tp, class _Alloc> 2274227825Stheravenbool 2275227825Stheravenlist<_Tp, _Alloc>::__decrementable(const const_iterator* __i) const 2276227825Stheraven{ 2277227825Stheraven return !empty() && __i->__ptr_ != base::__end_.__next_; 2278227825Stheraven} 2279227825Stheraven 2280227825Stheraventemplate <class _Tp, class _Alloc> 2281227825Stheravenbool 2282227825Stheravenlist<_Tp, _Alloc>::__addable(const const_iterator* __i, ptrdiff_t __n) const 2283227825Stheraven{ 2284227825Stheraven return false; 2285227825Stheraven} 2286227825Stheraven 2287227825Stheraventemplate <class _Tp, class _Alloc> 2288227825Stheravenbool 2289227825Stheravenlist<_Tp, _Alloc>::__subscriptable(const const_iterator* __i, ptrdiff_t __n) const 2290227825Stheraven{ 2291227825Stheraven return false; 2292227825Stheraven} 2293227825Stheraven 2294227825Stheraven#endif // _LIBCPP_DEBUG_LEVEL >= 2 2295227825Stheraven 2296227825Stheraventemplate <class _Tp, class _Alloc> 2297227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 2298227825Stheravenbool 2299227825Stheravenoperator==(const list<_Tp, _Alloc>& __x, const list<_Tp, _Alloc>& __y) 2300227825Stheraven{ 2301227825Stheraven return __x.size() == __y.size() && _VSTD::equal(__x.begin(), __x.end(), __y.begin()); 2302227825Stheraven} 2303227825Stheraven 2304227825Stheraventemplate <class _Tp, class _Alloc> 2305227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 2306227825Stheravenbool 2307227825Stheravenoperator< (const list<_Tp, _Alloc>& __x, const list<_Tp, _Alloc>& __y) 2308227825Stheraven{ 2309227825Stheraven return _VSTD::lexicographical_compare(__x.begin(), __x.end(), __y.begin(), __y.end()); 2310227825Stheraven} 2311227825Stheraven 2312227825Stheraventemplate <class _Tp, class _Alloc> 2313227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 2314227825Stheravenbool 2315227825Stheravenoperator!=(const list<_Tp, _Alloc>& __x, const list<_Tp, _Alloc>& __y) 2316227825Stheraven{ 2317227825Stheraven return !(__x == __y); 2318227825Stheraven} 2319227825Stheraven 2320227825Stheraventemplate <class _Tp, class _Alloc> 2321227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 2322227825Stheravenbool 2323227825Stheravenoperator> (const list<_Tp, _Alloc>& __x, const list<_Tp, _Alloc>& __y) 2324227825Stheraven{ 2325227825Stheraven return __y < __x; 2326227825Stheraven} 2327227825Stheraven 2328227825Stheraventemplate <class _Tp, class _Alloc> 2329227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 2330227825Stheravenbool 2331227825Stheravenoperator>=(const list<_Tp, _Alloc>& __x, const list<_Tp, _Alloc>& __y) 2332227825Stheraven{ 2333227825Stheraven return !(__x < __y); 2334227825Stheraven} 2335227825Stheraven 2336227825Stheraventemplate <class _Tp, class _Alloc> 2337227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 2338227825Stheravenbool 2339227825Stheravenoperator<=(const list<_Tp, _Alloc>& __x, const list<_Tp, _Alloc>& __y) 2340227825Stheraven{ 2341227825Stheraven return !(__y < __x); 2342227825Stheraven} 2343227825Stheraven 2344227825Stheraventemplate <class _Tp, class _Alloc> 2345227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 2346227825Stheravenvoid 2347227825Stheravenswap(list<_Tp, _Alloc>& __x, list<_Tp, _Alloc>& __y) 2348227825Stheraven _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y))) 2349227825Stheraven{ 2350227825Stheraven __x.swap(__y); 2351227825Stheraven} 2352227825Stheraven 2353227825Stheraven_LIBCPP_END_NAMESPACE_STD 2354227825Stheraven 2355227825Stheraven#endif // _LIBCPP_LIST 2356