forward_list revision 262801
1227825Stheraven// -*- C++ -*- 2227825Stheraven//===----------------------- forward_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_FORWARD_LIST 12227825Stheraven#define _LIBCPP_FORWARD_LIST 13227825Stheraven 14227825Stheraven/* 15227825Stheraven forward_list synopsis 16227825Stheraven 17227825Stheravennamespace std 18227825Stheraven{ 19227825Stheraven 20227825Stheraventemplate <class T, class Allocator = allocator<T>> 21227825Stheravenclass forward_list 22227825Stheraven{ 23227825Stheravenpublic: 24227825Stheraven typedef T value_type; 25227825Stheraven typedef Allocator allocator_type; 26227825Stheraven 27227825Stheraven typedef value_type& reference; 28227825Stheraven typedef const value_type& const_reference; 29227825Stheraven typedef typename allocator_traits<allocator_type>::pointer pointer; 30227825Stheraven typedef typename allocator_traits<allocator_type>::const_pointer const_pointer; 31227825Stheraven typedef typename allocator_traits<allocator_type>::size_type size_type; 32227825Stheraven typedef typename allocator_traits<allocator_type>::difference_type difference_type; 33227825Stheraven 34227825Stheraven typedef <details> iterator; 35227825Stheraven typedef <details> const_iterator; 36227825Stheraven 37227825Stheraven forward_list() 38227825Stheraven noexcept(is_nothrow_default_constructible<allocator_type>::value); 39227825Stheraven explicit forward_list(const allocator_type& a); 40227825Stheraven explicit forward_list(size_type n); 41262801Sdim explicit forward_list(size_type n, const allocator_type& a); // C++14 42227825Stheraven forward_list(size_type n, const value_type& v); 43227825Stheraven forward_list(size_type n, const value_type& v, const allocator_type& a); 44227825Stheraven template <class InputIterator> 45227825Stheraven forward_list(InputIterator first, InputIterator last); 46227825Stheraven template <class InputIterator> 47227825Stheraven forward_list(InputIterator first, InputIterator last, const allocator_type& a); 48227825Stheraven forward_list(const forward_list& x); 49227825Stheraven forward_list(const forward_list& x, const allocator_type& a); 50227825Stheraven forward_list(forward_list&& x) 51227825Stheraven noexcept(is_nothrow_move_constructible<allocator_type>::value); 52227825Stheraven forward_list(forward_list&& x, const allocator_type& a); 53227825Stheraven forward_list(initializer_list<value_type> il); 54227825Stheraven forward_list(initializer_list<value_type> il, const allocator_type& a); 55227825Stheraven 56227825Stheraven ~forward_list(); 57227825Stheraven 58227825Stheraven forward_list& operator=(const forward_list& x); 59227825Stheraven forward_list& operator=(forward_list&& x) 60227825Stheraven noexcept( 61227825Stheraven allocator_type::propagate_on_container_move_assignment::value && 62227825Stheraven is_nothrow_move_assignable<allocator_type>::value); 63227825Stheraven forward_list& operator=(initializer_list<value_type> il); 64227825Stheraven 65227825Stheraven template <class InputIterator> 66227825Stheraven void assign(InputIterator first, InputIterator last); 67227825Stheraven void assign(size_type n, const value_type& v); 68227825Stheraven void assign(initializer_list<value_type> il); 69227825Stheraven 70227825Stheraven allocator_type get_allocator() const noexcept; 71227825Stheraven 72227825Stheraven iterator begin() noexcept; 73227825Stheraven const_iterator begin() const noexcept; 74227825Stheraven iterator end() noexcept; 75227825Stheraven const_iterator end() const noexcept; 76227825Stheraven 77227825Stheraven const_iterator cbegin() const noexcept; 78227825Stheraven const_iterator cend() const noexcept; 79227825Stheraven 80227825Stheraven iterator before_begin() noexcept; 81227825Stheraven const_iterator before_begin() const noexcept; 82227825Stheraven const_iterator cbefore_begin() const noexcept; 83227825Stheraven 84227825Stheraven bool empty() const noexcept; 85227825Stheraven size_type max_size() const noexcept; 86227825Stheraven 87227825Stheraven reference front(); 88227825Stheraven const_reference front() const; 89227825Stheraven 90227825Stheraven template <class... Args> void emplace_front(Args&&... args); 91227825Stheraven void push_front(const value_type& v); 92227825Stheraven void push_front(value_type&& v); 93227825Stheraven 94227825Stheraven void pop_front(); 95227825Stheraven 96227825Stheraven template <class... Args> 97227825Stheraven iterator emplace_after(const_iterator p, Args&&... args); 98227825Stheraven iterator insert_after(const_iterator p, const value_type& v); 99227825Stheraven iterator insert_after(const_iterator p, value_type&& v); 100227825Stheraven iterator insert_after(const_iterator p, size_type n, const value_type& v); 101227825Stheraven template <class InputIterator> 102227825Stheraven iterator insert_after(const_iterator p, 103227825Stheraven InputIterator first, InputIterator last); 104227825Stheraven iterator insert_after(const_iterator p, initializer_list<value_type> il); 105227825Stheraven 106227825Stheraven iterator erase_after(const_iterator p); 107227825Stheraven iterator erase_after(const_iterator first, const_iterator last); 108227825Stheraven 109227825Stheraven void swap(forward_list& x) 110227825Stheraven noexcept(!allocator_type::propagate_on_container_swap::value || 111227825Stheraven __is_nothrow_swappable<allocator_type>::value); 112227825Stheraven 113227825Stheraven void resize(size_type n); 114227825Stheraven void resize(size_type n, const value_type& v); 115227825Stheraven void clear() noexcept; 116227825Stheraven 117227825Stheraven void splice_after(const_iterator p, forward_list& x); 118227825Stheraven void splice_after(const_iterator p, forward_list&& x); 119227825Stheraven void splice_after(const_iterator p, forward_list& x, const_iterator i); 120227825Stheraven void splice_after(const_iterator p, forward_list&& x, const_iterator i); 121227825Stheraven void splice_after(const_iterator p, forward_list& x, 122227825Stheraven const_iterator first, const_iterator last); 123227825Stheraven void splice_after(const_iterator p, forward_list&& x, 124227825Stheraven const_iterator first, const_iterator last); 125227825Stheraven void remove(const value_type& v); 126227825Stheraven template <class Predicate> void remove_if(Predicate pred); 127227825Stheraven void unique(); 128227825Stheraven template <class BinaryPredicate> void unique(BinaryPredicate binary_pred); 129227825Stheraven void merge(forward_list& x); 130227825Stheraven void merge(forward_list&& x); 131227825Stheraven template <class Compare> void merge(forward_list& x, Compare comp); 132227825Stheraven template <class Compare> void merge(forward_list&& x, Compare comp); 133227825Stheraven void sort(); 134227825Stheraven template <class Compare> void sort(Compare comp); 135227825Stheraven void reverse() noexcept; 136227825Stheraven}; 137227825Stheraven 138227825Stheraventemplate <class T, class Allocator> 139227825Stheraven bool operator==(const forward_list<T, Allocator>& x, 140227825Stheraven const forward_list<T, Allocator>& y); 141227825Stheraven 142227825Stheraventemplate <class T, class Allocator> 143227825Stheraven bool operator< (const forward_list<T, Allocator>& x, 144227825Stheraven const forward_list<T, Allocator>& y); 145227825Stheraven 146227825Stheraventemplate <class T, class Allocator> 147227825Stheraven bool operator!=(const forward_list<T, Allocator>& x, 148227825Stheraven const forward_list<T, Allocator>& y); 149227825Stheraven 150227825Stheraventemplate <class T, class Allocator> 151227825Stheraven bool operator> (const forward_list<T, Allocator>& x, 152227825Stheraven const forward_list<T, Allocator>& y); 153227825Stheraven 154227825Stheraventemplate <class T, class Allocator> 155227825Stheraven bool operator>=(const forward_list<T, Allocator>& x, 156227825Stheraven const forward_list<T, Allocator>& y); 157227825Stheraven 158227825Stheraventemplate <class T, class Allocator> 159227825Stheraven bool operator<=(const forward_list<T, Allocator>& x, 160227825Stheraven const forward_list<T, Allocator>& y); 161227825Stheraven 162227825Stheraventemplate <class T, class Allocator> 163227825Stheraven void swap(forward_list<T, Allocator>& x, forward_list<T, Allocator>& y) 164227825Stheraven noexcept(noexcept(x.swap(y))); 165227825Stheraven 166227825Stheraven} // std 167227825Stheraven 168227825Stheraven*/ 169227825Stheraven 170227825Stheraven#include <__config> 171227825Stheraven 172227825Stheraven#include <initializer_list> 173227825Stheraven#include <memory> 174227825Stheraven#include <limits> 175227825Stheraven#include <iterator> 176227825Stheraven#include <algorithm> 177227825Stheraven 178232950Stheraven#include <__undef_min_max> 179232950Stheraven 180227825Stheraven#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) 181227825Stheraven#pragma GCC system_header 182227825Stheraven#endif 183227825Stheraven 184227825Stheraven_LIBCPP_BEGIN_NAMESPACE_STD 185227825Stheraven 186227825Stheraventemplate <class _Tp, class _VoidPtr> struct __forward_list_node; 187227825Stheraven 188227825Stheraventemplate <class _NodePtr> 189227825Stheravenstruct __forward_begin_node 190227825Stheraven{ 191227825Stheraven typedef __forward_begin_node __self; 192227825Stheraven typedef _NodePtr pointer; 193227825Stheraven 194227825Stheraven pointer __next_; 195227825Stheraven 196227825Stheraven _LIBCPP_INLINE_VISIBILITY __forward_begin_node() : __next_(nullptr) {} 197227825Stheraven}; 198227825Stheraven 199227825Stheraventemplate <class _Tp, class _VoidPtr> 200227825Stheravenstruct __forward_list_node 201227825Stheraven : public __forward_begin_node 202227825Stheraven < 203227825Stheraven typename pointer_traits<_VoidPtr>::template 204227825Stheraven#ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES 205227825Stheraven rebind<__forward_list_node<_Tp, _VoidPtr> > 206227825Stheraven#else 207227825Stheraven rebind<__forward_list_node<_Tp, _VoidPtr> >::other 208227825Stheraven#endif 209227825Stheraven > 210227825Stheraven{ 211227825Stheraven typedef _Tp value_type; 212227825Stheraven 213227825Stheraven value_type __value_; 214227825Stheraven}; 215227825Stheraven 216262801Sdimtemplate<class _Tp, class _Alloc> class _LIBCPP_TYPE_VIS_ONLY forward_list; 217262801Sdimtemplate<class _NodeConstPtr> class _LIBCPP_TYPE_VIS_ONLY __forward_list_const_iterator; 218227825Stheraven 219227825Stheraventemplate <class _NodePtr> 220262801Sdimclass _LIBCPP_TYPE_VIS_ONLY __forward_list_iterator 221227825Stheraven{ 222227825Stheraven typedef _NodePtr __node_pointer; 223227825Stheraven 224227825Stheraven __node_pointer __ptr_; 225227825Stheraven 226227825Stheraven _LIBCPP_INLINE_VISIBILITY 227227825Stheraven explicit __forward_list_iterator(__node_pointer __p) _NOEXCEPT : __ptr_(__p) {} 228227825Stheraven 229262801Sdim template<class, class> friend class _LIBCPP_TYPE_VIS_ONLY forward_list; 230262801Sdim template<class> friend class _LIBCPP_TYPE_VIS_ONLY __forward_list_const_iterator; 231227825Stheraven 232227825Stheravenpublic: 233227825Stheraven typedef forward_iterator_tag iterator_category; 234227825Stheraven typedef typename pointer_traits<__node_pointer>::element_type::value_type 235227825Stheraven value_type; 236253159Stheraven typedef value_type& reference; 237227825Stheraven typedef typename pointer_traits<__node_pointer>::difference_type 238227825Stheraven difference_type; 239227825Stheraven typedef typename pointer_traits<__node_pointer>::template 240227825Stheraven#ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES 241227825Stheraven rebind<value_type> 242227825Stheraven#else 243227825Stheraven rebind<value_type>::other 244227825Stheraven#endif 245227825Stheraven pointer; 246227825Stheraven 247227825Stheraven _LIBCPP_INLINE_VISIBILITY 248227825Stheraven __forward_list_iterator() _NOEXCEPT : __ptr_(nullptr) {} 249227825Stheraven 250227825Stheraven _LIBCPP_INLINE_VISIBILITY 251227825Stheraven reference operator*() const {return __ptr_->__value_;} 252227825Stheraven _LIBCPP_INLINE_VISIBILITY 253253159Stheraven pointer operator->() const {return pointer_traits<pointer>::pointer_to(__ptr_->__value_);} 254227825Stheraven 255227825Stheraven _LIBCPP_INLINE_VISIBILITY 256227825Stheraven __forward_list_iterator& operator++() 257227825Stheraven { 258227825Stheraven __ptr_ = __ptr_->__next_; 259227825Stheraven return *this; 260227825Stheraven } 261227825Stheraven _LIBCPP_INLINE_VISIBILITY 262227825Stheraven __forward_list_iterator operator++(int) 263227825Stheraven { 264227825Stheraven __forward_list_iterator __t(*this); 265227825Stheraven ++(*this); 266227825Stheraven return __t; 267227825Stheraven } 268227825Stheraven 269227825Stheraven friend _LIBCPP_INLINE_VISIBILITY 270227825Stheraven bool operator==(const __forward_list_iterator& __x, 271227825Stheraven const __forward_list_iterator& __y) 272227825Stheraven {return __x.__ptr_ == __y.__ptr_;} 273227825Stheraven friend _LIBCPP_INLINE_VISIBILITY 274227825Stheraven bool operator!=(const __forward_list_iterator& __x, 275227825Stheraven const __forward_list_iterator& __y) 276227825Stheraven {return !(__x == __y);} 277227825Stheraven}; 278227825Stheraven 279227825Stheraventemplate <class _NodeConstPtr> 280262801Sdimclass _LIBCPP_TYPE_VIS_ONLY __forward_list_const_iterator 281227825Stheraven{ 282227825Stheraven typedef _NodeConstPtr __node_const_pointer; 283227825Stheraven 284227825Stheraven __node_const_pointer __ptr_; 285227825Stheraven 286227825Stheraven _LIBCPP_INLINE_VISIBILITY 287227825Stheraven explicit __forward_list_const_iterator(__node_const_pointer __p) _NOEXCEPT 288227825Stheraven : __ptr_(__p) {} 289227825Stheraven 290227825Stheraven typedef typename remove_const 291227825Stheraven < 292227825Stheraven typename pointer_traits<__node_const_pointer>::element_type 293227825Stheraven >::type __node; 294227825Stheraven typedef typename pointer_traits<__node_const_pointer>::template 295227825Stheraven#ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES 296227825Stheraven rebind<__node> 297227825Stheraven#else 298227825Stheraven rebind<__node>::other 299227825Stheraven#endif 300227825Stheraven __node_pointer; 301227825Stheraven 302227825Stheraven template<class, class> friend class forward_list; 303227825Stheraven 304227825Stheravenpublic: 305227825Stheraven typedef forward_iterator_tag iterator_category; 306227825Stheraven typedef typename __node::value_type value_type; 307253159Stheraven typedef const value_type& reference; 308227825Stheraven typedef typename pointer_traits<__node_const_pointer>::difference_type 309227825Stheraven difference_type; 310227825Stheraven typedef typename pointer_traits<__node_const_pointer>::template 311227825Stheraven#ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES 312227825Stheraven rebind<const value_type> 313227825Stheraven#else 314227825Stheraven rebind<const value_type>::other 315227825Stheraven#endif 316227825Stheraven pointer; 317227825Stheraven 318227825Stheraven _LIBCPP_INLINE_VISIBILITY 319227825Stheraven __forward_list_const_iterator() _NOEXCEPT : __ptr_(nullptr) {} 320227825Stheraven _LIBCPP_INLINE_VISIBILITY 321227825Stheraven __forward_list_const_iterator(__forward_list_iterator<__node_pointer> __p) _NOEXCEPT 322227825Stheraven : __ptr_(__p.__ptr_) {} 323227825Stheraven 324227825Stheraven _LIBCPP_INLINE_VISIBILITY 325227825Stheraven reference operator*() const {return __ptr_->__value_;} 326227825Stheraven _LIBCPP_INLINE_VISIBILITY 327253159Stheraven pointer operator->() const {return pointer_traits<pointer>::pointer_to(__ptr_->__value_);} 328227825Stheraven 329227825Stheraven _LIBCPP_INLINE_VISIBILITY 330227825Stheraven __forward_list_const_iterator& operator++() 331227825Stheraven { 332227825Stheraven __ptr_ = __ptr_->__next_; 333227825Stheraven return *this; 334227825Stheraven } 335227825Stheraven _LIBCPP_INLINE_VISIBILITY 336227825Stheraven __forward_list_const_iterator operator++(int) 337227825Stheraven { 338227825Stheraven __forward_list_const_iterator __t(*this); 339227825Stheraven ++(*this); 340227825Stheraven return __t; 341227825Stheraven } 342227825Stheraven 343227825Stheraven friend _LIBCPP_INLINE_VISIBILITY 344227825Stheraven bool operator==(const __forward_list_const_iterator& __x, 345227825Stheraven const __forward_list_const_iterator& __y) 346227825Stheraven {return __x.__ptr_ == __y.__ptr_;} 347227825Stheraven friend _LIBCPP_INLINE_VISIBILITY 348227825Stheraven bool operator!=(const __forward_list_const_iterator& __x, 349227825Stheraven const __forward_list_const_iterator& __y) 350227825Stheraven {return !(__x == __y);} 351227825Stheraven}; 352227825Stheraven 353227825Stheraventemplate <class _Tp, class _Alloc> 354227825Stheravenclass __forward_list_base 355227825Stheraven{ 356227825Stheravenprotected: 357227825Stheraven typedef _Tp value_type; 358227825Stheraven typedef _Alloc allocator_type; 359227825Stheraven 360227825Stheraven typedef typename allocator_traits<allocator_type>::void_pointer void_pointer; 361227825Stheraven typedef __forward_list_node<value_type, void_pointer> __node; 362227825Stheraven typedef typename __node::__self __begin_node; 363227825Stheraven typedef typename allocator_traits<allocator_type>::template 364227825Stheraven#ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES 365227825Stheraven rebind_alloc<__node> 366227825Stheraven#else 367227825Stheraven rebind_alloc<__node>::other 368227825Stheraven#endif 369227825Stheraven __node_allocator; 370227825Stheraven typedef allocator_traits<__node_allocator> __node_traits; 371227825Stheraven typedef typename __node_traits::pointer __node_pointer; 372253159Stheraven typedef typename __node_traits::pointer __node_const_pointer; 373227825Stheraven 374253159Stheraven typedef typename allocator_traits<allocator_type>::template 375253159Stheraven#ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES 376253159Stheraven rebind_alloc<__begin_node> 377253159Stheraven#else 378253159Stheraven rebind_alloc<__begin_node>::other 379253159Stheraven#endif 380253159Stheraven __begin_node_allocator; 381253159Stheraven typedef typename allocator_traits<__begin_node_allocator>::pointer __begin_node_pointer; 382253159Stheraven 383227825Stheraven __compressed_pair<__begin_node, __node_allocator> __before_begin_; 384227825Stheraven 385227825Stheraven _LIBCPP_INLINE_VISIBILITY 386227825Stheraven __node_pointer __before_begin() _NOEXCEPT 387253159Stheraven {return static_cast<__node_pointer>(pointer_traits<__begin_node_pointer>:: 388253159Stheraven pointer_to(__before_begin_.first()));} 389227825Stheraven _LIBCPP_INLINE_VISIBILITY 390227825Stheraven __node_const_pointer __before_begin() const _NOEXCEPT 391253159Stheraven {return static_cast<__node_const_pointer>(pointer_traits<__begin_node_pointer>:: 392253159Stheraven pointer_to(const_cast<__begin_node&>(__before_begin_.first())));} 393227825Stheraven 394227825Stheraven _LIBCPP_INLINE_VISIBILITY 395227825Stheraven __node_allocator& __alloc() _NOEXCEPT 396227825Stheraven {return __before_begin_.second();} 397227825Stheraven _LIBCPP_INLINE_VISIBILITY 398227825Stheraven const __node_allocator& __alloc() const _NOEXCEPT 399227825Stheraven {return __before_begin_.second();} 400227825Stheraven 401227825Stheraven typedef __forward_list_iterator<__node_pointer> iterator; 402253159Stheraven typedef __forward_list_const_iterator<__node_pointer> const_iterator; 403227825Stheraven 404227825Stheraven _LIBCPP_INLINE_VISIBILITY 405227825Stheraven __forward_list_base() 406227825Stheraven _NOEXCEPT_(is_nothrow_default_constructible<__node_allocator>::value) 407227825Stheraven : __before_begin_(__begin_node()) {} 408227825Stheraven _LIBCPP_INLINE_VISIBILITY 409227825Stheraven __forward_list_base(const allocator_type& __a) 410227825Stheraven : __before_begin_(__begin_node(), __node_allocator(__a)) {} 411227825Stheraven 412227825Stheraven#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 413227825Stheravenpublic: 414227825Stheraven __forward_list_base(__forward_list_base&& __x) 415227825Stheraven _NOEXCEPT_(is_nothrow_move_constructible<__node_allocator>::value); 416227825Stheraven __forward_list_base(__forward_list_base&& __x, const allocator_type& __a); 417227825Stheraven#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 418227825Stheraven 419227825Stheravenprivate: 420227825Stheraven __forward_list_base(const __forward_list_base&); 421227825Stheraven __forward_list_base& operator=(const __forward_list_base&); 422227825Stheraven 423227825Stheravenpublic: 424227825Stheraven ~__forward_list_base(); 425227825Stheraven 426227825Stheravenprotected: 427227825Stheraven _LIBCPP_INLINE_VISIBILITY 428227825Stheraven void __copy_assign_alloc(const __forward_list_base& __x) 429227825Stheraven {__copy_assign_alloc(__x, integral_constant<bool, 430227825Stheraven __node_traits::propagate_on_container_copy_assignment::value>());} 431227825Stheraven 432227825Stheraven _LIBCPP_INLINE_VISIBILITY 433227825Stheraven void __move_assign_alloc(__forward_list_base& __x) 434227825Stheraven _NOEXCEPT_(!__node_traits::propagate_on_container_move_assignment::value || 435227825Stheraven is_nothrow_move_assignable<__node_allocator>::value) 436227825Stheraven {__move_assign_alloc(__x, integral_constant<bool, 437227825Stheraven __node_traits::propagate_on_container_move_assignment::value>());} 438227825Stheraven 439227825Stheravenpublic: 440227825Stheraven void swap(__forward_list_base& __x) 441227825Stheraven _NOEXCEPT_(!__node_traits::propagate_on_container_swap::value || 442227825Stheraven __is_nothrow_swappable<__node_allocator>::value); 443227825Stheravenprotected: 444227825Stheraven void clear() _NOEXCEPT; 445227825Stheraven 446227825Stheravenprivate: 447227825Stheraven _LIBCPP_INLINE_VISIBILITY 448227825Stheraven void __copy_assign_alloc(const __forward_list_base&, false_type) {} 449227825Stheraven _LIBCPP_INLINE_VISIBILITY 450227825Stheraven void __copy_assign_alloc(const __forward_list_base& __x, true_type) 451227825Stheraven { 452227825Stheraven if (__alloc() != __x.__alloc()) 453227825Stheraven clear(); 454227825Stheraven __alloc() = __x.__alloc(); 455227825Stheraven } 456227825Stheraven 457227825Stheraven _LIBCPP_INLINE_VISIBILITY 458227825Stheraven void __move_assign_alloc(__forward_list_base& __x, false_type) _NOEXCEPT 459227825Stheraven {} 460227825Stheraven _LIBCPP_INLINE_VISIBILITY 461227825Stheraven void __move_assign_alloc(__forward_list_base& __x, true_type) 462227825Stheraven _NOEXCEPT_(is_nothrow_move_assignable<__node_allocator>::value) 463227825Stheraven {__alloc() = _VSTD::move(__x.__alloc());} 464227825Stheraven 465227825Stheraven _LIBCPP_INLINE_VISIBILITY 466227825Stheraven static void __swap_alloc(__node_allocator& __x, __node_allocator& __y) 467227825Stheraven _NOEXCEPT_(!__node_traits::propagate_on_container_swap::value || 468227825Stheraven __is_nothrow_swappable<__node_allocator>::value) 469227825Stheraven {__swap_alloc(__x, __y, integral_constant<bool, 470227825Stheraven __node_traits::propagate_on_container_swap::value>());} 471227825Stheraven _LIBCPP_INLINE_VISIBILITY 472227825Stheraven static void __swap_alloc(__node_allocator& __x, __node_allocator& __y, 473227825Stheraven false_type) 474227825Stheraven _NOEXCEPT 475227825Stheraven {} 476227825Stheraven _LIBCPP_INLINE_VISIBILITY 477227825Stheraven static void __swap_alloc(__node_allocator& __x, __node_allocator& __y, 478227825Stheraven true_type) 479227825Stheraven _NOEXCEPT_(__is_nothrow_swappable<__node_allocator>::value) 480227825Stheraven { 481227825Stheraven using _VSTD::swap; 482227825Stheraven swap(__x, __y); 483227825Stheraven } 484227825Stheraven}; 485227825Stheraven 486227825Stheraven#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 487227825Stheraven 488227825Stheraventemplate <class _Tp, class _Alloc> 489227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 490227825Stheraven__forward_list_base<_Tp, _Alloc>::__forward_list_base(__forward_list_base&& __x) 491227825Stheraven _NOEXCEPT_(is_nothrow_move_constructible<__node_allocator>::value) 492227825Stheraven : __before_begin_(_VSTD::move(__x.__before_begin_)) 493227825Stheraven{ 494227825Stheraven __x.__before_begin()->__next_ = nullptr; 495227825Stheraven} 496227825Stheraven 497227825Stheraventemplate <class _Tp, class _Alloc> 498227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 499227825Stheraven__forward_list_base<_Tp, _Alloc>::__forward_list_base(__forward_list_base&& __x, 500227825Stheraven const allocator_type& __a) 501227825Stheraven : __before_begin_(__begin_node(), __node_allocator(__a)) 502227825Stheraven{ 503227825Stheraven if (__alloc() == __x.__alloc()) 504227825Stheraven { 505227825Stheraven __before_begin()->__next_ = __x.__before_begin()->__next_; 506227825Stheraven __x.__before_begin()->__next_ = nullptr; 507227825Stheraven } 508227825Stheraven} 509227825Stheraven 510227825Stheraven#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 511227825Stheraven 512227825Stheraventemplate <class _Tp, class _Alloc> 513227825Stheraven__forward_list_base<_Tp, _Alloc>::~__forward_list_base() 514227825Stheraven{ 515227825Stheraven clear(); 516227825Stheraven} 517227825Stheraven 518227825Stheraventemplate <class _Tp, class _Alloc> 519227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 520227825Stheravenvoid 521227825Stheraven__forward_list_base<_Tp, _Alloc>::swap(__forward_list_base& __x) 522227825Stheraven _NOEXCEPT_(!__node_traits::propagate_on_container_swap::value || 523227825Stheraven __is_nothrow_swappable<__node_allocator>::value) 524227825Stheraven{ 525227825Stheraven __swap_alloc(__alloc(), __x.__alloc()); 526227825Stheraven using _VSTD::swap; 527227825Stheraven swap(__before_begin()->__next_, __x.__before_begin()->__next_); 528227825Stheraven} 529227825Stheraven 530227825Stheraventemplate <class _Tp, class _Alloc> 531227825Stheravenvoid 532227825Stheraven__forward_list_base<_Tp, _Alloc>::clear() _NOEXCEPT 533227825Stheraven{ 534227825Stheraven __node_allocator& __a = __alloc(); 535227825Stheraven for (__node_pointer __p = __before_begin()->__next_; __p != nullptr;) 536227825Stheraven { 537227825Stheraven __node_pointer __next = __p->__next_; 538227825Stheraven __node_traits::destroy(__a, _VSTD::addressof(__p->__value_)); 539227825Stheraven __node_traits::deallocate(__a, __p, 1); 540227825Stheraven __p = __next; 541227825Stheraven } 542227825Stheraven __before_begin()->__next_ = nullptr; 543227825Stheraven} 544227825Stheraven 545227825Stheraventemplate <class _Tp, class _Alloc = allocator<_Tp> > 546262801Sdimclass _LIBCPP_TYPE_VIS_ONLY forward_list 547227825Stheraven : private __forward_list_base<_Tp, _Alloc> 548227825Stheraven{ 549227825Stheraven typedef __forward_list_base<_Tp, _Alloc> base; 550227825Stheraven typedef typename base::__node_allocator __node_allocator; 551227825Stheraven typedef typename base::__node __node; 552227825Stheraven typedef typename base::__node_traits __node_traits; 553227825Stheraven typedef typename base::__node_pointer __node_pointer; 554227825Stheraven 555227825Stheravenpublic: 556227825Stheraven typedef _Tp value_type; 557227825Stheraven typedef _Alloc allocator_type; 558227825Stheraven 559227825Stheraven typedef value_type& reference; 560227825Stheraven typedef const value_type& const_reference; 561227825Stheraven typedef typename allocator_traits<allocator_type>::pointer pointer; 562227825Stheraven typedef typename allocator_traits<allocator_type>::const_pointer const_pointer; 563227825Stheraven typedef typename allocator_traits<allocator_type>::size_type size_type; 564227825Stheraven typedef typename allocator_traits<allocator_type>::difference_type difference_type; 565227825Stheraven 566227825Stheraven typedef typename base::iterator iterator; 567227825Stheraven typedef typename base::const_iterator const_iterator; 568227825Stheraven 569227825Stheraven _LIBCPP_INLINE_VISIBILITY 570227825Stheraven forward_list() 571227825Stheraven _NOEXCEPT_(is_nothrow_default_constructible<__node_allocator>::value) 572227825Stheraven {} // = default; 573227825Stheraven explicit forward_list(const allocator_type& __a); 574227825Stheraven explicit forward_list(size_type __n); 575262801Sdim#if _LIBCPP_STD_VER > 11 576262801Sdim explicit forward_list(size_type __n, const allocator_type& __a); 577262801Sdim#endif 578227825Stheraven forward_list(size_type __n, const value_type& __v); 579227825Stheraven forward_list(size_type __n, const value_type& __v, const allocator_type& __a); 580227825Stheraven template <class _InputIterator> 581227825Stheraven forward_list(_InputIterator __f, _InputIterator __l, 582227825Stheraven typename enable_if< 583227825Stheraven __is_input_iterator<_InputIterator>::value 584227825Stheraven >::type* = nullptr); 585227825Stheraven template <class _InputIterator> 586227825Stheraven forward_list(_InputIterator __f, _InputIterator __l, 587227825Stheraven const allocator_type& __a, 588227825Stheraven typename enable_if< 589227825Stheraven __is_input_iterator<_InputIterator>::value 590227825Stheraven >::type* = nullptr); 591227825Stheraven forward_list(const forward_list& __x); 592227825Stheraven forward_list(const forward_list& __x, const allocator_type& __a); 593227825Stheraven#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 594227825Stheraven _LIBCPP_INLINE_VISIBILITY 595227825Stheraven forward_list(forward_list&& __x) 596227825Stheraven _NOEXCEPT_(is_nothrow_move_constructible<base>::value) 597227825Stheraven : base(_VSTD::move(__x)) {} 598227825Stheraven forward_list(forward_list&& __x, const allocator_type& __a); 599227825Stheraven#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 600227825Stheraven#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 601227825Stheraven forward_list(initializer_list<value_type> __il); 602227825Stheraven forward_list(initializer_list<value_type> __il, const allocator_type& __a); 603227825Stheraven#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 604227825Stheraven 605227825Stheraven // ~forward_list() = default; 606227825Stheraven 607227825Stheraven forward_list& operator=(const forward_list& __x); 608227825Stheraven#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 609227825Stheraven forward_list& operator=(forward_list&& __x) 610227825Stheraven _NOEXCEPT_( 611227825Stheraven __node_traits::propagate_on_container_move_assignment::value && 612227825Stheraven is_nothrow_move_assignable<allocator_type>::value); 613227825Stheraven#endif 614227825Stheraven#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 615227825Stheraven forward_list& operator=(initializer_list<value_type> __il); 616227825Stheraven#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 617227825Stheraven 618227825Stheraven template <class _InputIterator> 619227825Stheraven typename enable_if 620227825Stheraven < 621227825Stheraven __is_input_iterator<_InputIterator>::value, 622227825Stheraven void 623227825Stheraven >::type 624227825Stheraven assign(_InputIterator __f, _InputIterator __l); 625227825Stheraven void assign(size_type __n, const value_type& __v); 626227825Stheraven#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 627227825Stheraven void assign(initializer_list<value_type> __il); 628227825Stheraven#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 629227825Stheraven 630227825Stheraven _LIBCPP_INLINE_VISIBILITY 631227825Stheraven allocator_type get_allocator() const _NOEXCEPT 632227825Stheraven {return allocator_type(base::__alloc());} 633227825Stheraven 634227825Stheraven _LIBCPP_INLINE_VISIBILITY 635227825Stheraven iterator begin() _NOEXCEPT 636227825Stheraven {return iterator(base::__before_begin()->__next_);} 637227825Stheraven _LIBCPP_INLINE_VISIBILITY 638227825Stheraven const_iterator begin() const _NOEXCEPT 639227825Stheraven {return const_iterator(base::__before_begin()->__next_);} 640227825Stheraven _LIBCPP_INLINE_VISIBILITY 641227825Stheraven iterator end() _NOEXCEPT 642227825Stheraven {return iterator(nullptr);} 643227825Stheraven _LIBCPP_INLINE_VISIBILITY 644227825Stheraven const_iterator end() const _NOEXCEPT 645227825Stheraven {return const_iterator(nullptr);} 646227825Stheraven 647227825Stheraven _LIBCPP_INLINE_VISIBILITY 648227825Stheraven const_iterator cbegin() const _NOEXCEPT 649227825Stheraven {return const_iterator(base::__before_begin()->__next_);} 650227825Stheraven _LIBCPP_INLINE_VISIBILITY 651227825Stheraven const_iterator cend() const _NOEXCEPT 652227825Stheraven {return const_iterator(nullptr);} 653227825Stheraven 654227825Stheraven _LIBCPP_INLINE_VISIBILITY 655227825Stheraven iterator before_begin() _NOEXCEPT 656227825Stheraven {return iterator(base::__before_begin());} 657227825Stheraven _LIBCPP_INLINE_VISIBILITY 658227825Stheraven const_iterator before_begin() const _NOEXCEPT 659227825Stheraven {return const_iterator(base::__before_begin());} 660227825Stheraven _LIBCPP_INLINE_VISIBILITY 661227825Stheraven const_iterator cbefore_begin() const _NOEXCEPT 662227825Stheraven {return const_iterator(base::__before_begin());} 663227825Stheraven 664227825Stheraven _LIBCPP_INLINE_VISIBILITY 665227825Stheraven bool empty() const _NOEXCEPT 666227825Stheraven {return base::__before_begin()->__next_ == nullptr;} 667227825Stheraven _LIBCPP_INLINE_VISIBILITY 668227825Stheraven size_type max_size() const _NOEXCEPT 669227825Stheraven {return numeric_limits<size_type>::max();} 670227825Stheraven 671227825Stheraven _LIBCPP_INLINE_VISIBILITY 672227825Stheraven reference front() {return base::__before_begin()->__next_->__value_;} 673227825Stheraven _LIBCPP_INLINE_VISIBILITY 674227825Stheraven const_reference front() const {return base::__before_begin()->__next_->__value_;} 675227825Stheraven 676227825Stheraven#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 677227825Stheraven#ifndef _LIBCPP_HAS_NO_VARIADICS 678227825Stheraven template <class... _Args> void emplace_front(_Args&&... __args); 679227825Stheraven#endif 680227825Stheraven void push_front(value_type&& __v); 681227825Stheraven#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 682227825Stheraven void push_front(const value_type& __v); 683227825Stheraven 684227825Stheraven void pop_front(); 685227825Stheraven 686227825Stheraven#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 687227825Stheraven#ifndef _LIBCPP_HAS_NO_VARIADICS 688227825Stheraven template <class... _Args> 689227825Stheraven iterator emplace_after(const_iterator __p, _Args&&... __args); 690227825Stheraven#endif // _LIBCPP_HAS_NO_VARIADICS 691227825Stheraven iterator insert_after(const_iterator __p, value_type&& __v); 692227825Stheraven#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 693227825Stheraven iterator insert_after(const_iterator __p, const value_type& __v); 694227825Stheraven iterator insert_after(const_iterator __p, size_type __n, const value_type& __v); 695227825Stheraven template <class _InputIterator> 696227825Stheraven _LIBCPP_INLINE_VISIBILITY 697227825Stheraven typename enable_if 698227825Stheraven < 699227825Stheraven __is_input_iterator<_InputIterator>::value, 700227825Stheraven iterator 701227825Stheraven >::type 702227825Stheraven insert_after(const_iterator __p, _InputIterator __f, _InputIterator __l); 703227825Stheraven#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 704227825Stheraven iterator insert_after(const_iterator __p, initializer_list<value_type> __il) 705227825Stheraven {return insert_after(__p, __il.begin(), __il.end());} 706227825Stheraven#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 707227825Stheraven 708227825Stheraven iterator erase_after(const_iterator __p); 709227825Stheraven iterator erase_after(const_iterator __f, const_iterator __l); 710227825Stheraven 711227825Stheraven _LIBCPP_INLINE_VISIBILITY 712227825Stheraven void swap(forward_list& __x) 713227825Stheraven _NOEXCEPT_(!__node_traits::propagate_on_container_swap::value || 714227825Stheraven __is_nothrow_swappable<__node_allocator>::value) 715227825Stheraven {base::swap(__x);} 716227825Stheraven 717227825Stheraven void resize(size_type __n); 718227825Stheraven void resize(size_type __n, const value_type& __v); 719227825Stheraven _LIBCPP_INLINE_VISIBILITY 720227825Stheraven void clear() _NOEXCEPT {base::clear();} 721227825Stheraven 722227825Stheraven#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 723227825Stheraven _LIBCPP_INLINE_VISIBILITY 724227825Stheraven void splice_after(const_iterator __p, forward_list&& __x); 725227825Stheraven _LIBCPP_INLINE_VISIBILITY 726227825Stheraven void splice_after(const_iterator __p, forward_list&& __x, const_iterator __i); 727227825Stheraven _LIBCPP_INLINE_VISIBILITY 728227825Stheraven void splice_after(const_iterator __p, forward_list&& __x, 729227825Stheraven const_iterator __f, const_iterator __l); 730227825Stheraven#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 731227825Stheraven void splice_after(const_iterator __p, forward_list& __x); 732227825Stheraven void splice_after(const_iterator __p, forward_list& __x, const_iterator __i); 733227825Stheraven void splice_after(const_iterator __p, forward_list& __x, 734227825Stheraven const_iterator __f, const_iterator __l); 735227825Stheraven void remove(const value_type& __v); 736227825Stheraven template <class _Predicate> void remove_if(_Predicate __pred); 737227825Stheraven _LIBCPP_INLINE_VISIBILITY 738227825Stheraven void unique() {unique(__equal_to<value_type>());} 739227825Stheraven template <class _BinaryPredicate> void unique(_BinaryPredicate __binary_pred); 740227825Stheraven#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 741227825Stheraven _LIBCPP_INLINE_VISIBILITY 742227825Stheraven void merge(forward_list&& __x) {merge(__x, __less<value_type>());} 743227825Stheraven template <class _Compare> 744227825Stheraven _LIBCPP_INLINE_VISIBILITY 745227825Stheraven void merge(forward_list&& __x, _Compare __comp) 746227825Stheraven {merge(__x, _VSTD::move(__comp));} 747227825Stheraven#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 748227825Stheraven _LIBCPP_INLINE_VISIBILITY 749227825Stheraven void merge(forward_list& __x) {merge(__x, __less<value_type>());} 750227825Stheraven template <class _Compare> void merge(forward_list& __x, _Compare __comp); 751227825Stheraven _LIBCPP_INLINE_VISIBILITY 752227825Stheraven void sort() {sort(__less<value_type>());} 753227825Stheraven template <class _Compare> void sort(_Compare __comp); 754227825Stheraven void reverse() _NOEXCEPT; 755227825Stheraven 756227825Stheravenprivate: 757227825Stheraven 758227825Stheraven#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 759227825Stheraven void __move_assign(forward_list& __x, true_type) 760227825Stheraven _NOEXCEPT_(is_nothrow_move_assignable<allocator_type>::value); 761227825Stheraven void __move_assign(forward_list& __x, false_type); 762227825Stheraven#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 763227825Stheraven 764227825Stheraven template <class _Compare> 765227825Stheraven static 766227825Stheraven __node_pointer 767227825Stheraven __merge(__node_pointer __f1, __node_pointer __f2, _Compare& __comp); 768227825Stheraven 769227825Stheraven template <class _Compare> 770227825Stheraven static 771227825Stheraven __node_pointer 772227825Stheraven __sort(__node_pointer __f, difference_type __sz, _Compare& __comp); 773227825Stheraven}; 774227825Stheraven 775227825Stheraventemplate <class _Tp, class _Alloc> 776227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 777227825Stheravenforward_list<_Tp, _Alloc>::forward_list(const allocator_type& __a) 778227825Stheraven : base(__a) 779227825Stheraven{ 780227825Stheraven} 781227825Stheraven 782227825Stheraventemplate <class _Tp, class _Alloc> 783227825Stheravenforward_list<_Tp, _Alloc>::forward_list(size_type __n) 784227825Stheraven{ 785227825Stheraven if (__n > 0) 786227825Stheraven { 787227825Stheraven __node_allocator& __a = base::__alloc(); 788232950Stheraven typedef __allocator_destructor<__node_allocator> _Dp; 789232950Stheraven unique_ptr<__node, _Dp> __h(nullptr, _Dp(__a, 1)); 790227825Stheraven for (__node_pointer __p = base::__before_begin(); __n > 0; --__n, 791227825Stheraven __p = __p->__next_) 792227825Stheraven { 793227825Stheraven __h.reset(__node_traits::allocate(__a, 1)); 794227825Stheraven __node_traits::construct(__a, _VSTD::addressof(__h->__value_)); 795227825Stheraven __h->__next_ = nullptr; 796227825Stheraven __p->__next_ = __h.release(); 797227825Stheraven } 798227825Stheraven } 799227825Stheraven} 800227825Stheraven 801262801Sdim#if _LIBCPP_STD_VER > 11 802227825Stheraventemplate <class _Tp, class _Alloc> 803262801Sdimforward_list<_Tp, _Alloc>::forward_list(size_type __n, const allocator_type& __a) 804262801Sdim : base ( __a ) 805262801Sdim{ 806262801Sdim if (__n > 0) 807262801Sdim { 808262801Sdim __node_allocator& __a = base::__alloc(); 809262801Sdim typedef __allocator_destructor<__node_allocator> _Dp; 810262801Sdim unique_ptr<__node, _Dp> __h(nullptr, _Dp(__a, 1)); 811262801Sdim for (__node_pointer __p = base::__before_begin(); __n > 0; --__n, 812262801Sdim __p = __p->__next_) 813262801Sdim { 814262801Sdim __h.reset(__node_traits::allocate(__a, 1)); 815262801Sdim __node_traits::construct(__a, _VSTD::addressof(__h->__value_)); 816262801Sdim __h->__next_ = nullptr; 817262801Sdim __p->__next_ = __h.release(); 818262801Sdim } 819262801Sdim } 820262801Sdim} 821262801Sdim#endif 822262801Sdim 823262801Sdimtemplate <class _Tp, class _Alloc> 824227825Stheravenforward_list<_Tp, _Alloc>::forward_list(size_type __n, const value_type& __v) 825227825Stheraven{ 826227825Stheraven insert_after(cbefore_begin(), __n, __v); 827227825Stheraven} 828227825Stheraven 829227825Stheraventemplate <class _Tp, class _Alloc> 830227825Stheravenforward_list<_Tp, _Alloc>::forward_list(size_type __n, const value_type& __v, 831227825Stheraven const allocator_type& __a) 832227825Stheraven : base(__a) 833227825Stheraven{ 834227825Stheraven insert_after(cbefore_begin(), __n, __v); 835227825Stheraven} 836227825Stheraven 837227825Stheraventemplate <class _Tp, class _Alloc> 838227825Stheraventemplate <class _InputIterator> 839227825Stheravenforward_list<_Tp, _Alloc>::forward_list(_InputIterator __f, _InputIterator __l, 840227825Stheraven typename enable_if< 841227825Stheraven __is_input_iterator<_InputIterator>::value 842227825Stheraven >::type*) 843227825Stheraven{ 844227825Stheraven insert_after(cbefore_begin(), __f, __l); 845227825Stheraven} 846227825Stheraven 847227825Stheraventemplate <class _Tp, class _Alloc> 848227825Stheraventemplate <class _InputIterator> 849227825Stheravenforward_list<_Tp, _Alloc>::forward_list(_InputIterator __f, _InputIterator __l, 850227825Stheraven const allocator_type& __a, 851227825Stheraven typename enable_if< 852227825Stheraven __is_input_iterator<_InputIterator>::value 853227825Stheraven >::type*) 854227825Stheraven : base(__a) 855227825Stheraven{ 856227825Stheraven insert_after(cbefore_begin(), __f, __l); 857227825Stheraven} 858227825Stheraven 859227825Stheraventemplate <class _Tp, class _Alloc> 860227825Stheravenforward_list<_Tp, _Alloc>::forward_list(const forward_list& __x) 861227825Stheraven : base(allocator_type( 862227825Stheraven __node_traits::select_on_container_copy_construction(__x.__alloc()) 863227825Stheraven ) 864227825Stheraven ) 865227825Stheraven{ 866227825Stheraven insert_after(cbefore_begin(), __x.begin(), __x.end()); 867227825Stheraven} 868227825Stheraven 869227825Stheraventemplate <class _Tp, class _Alloc> 870227825Stheravenforward_list<_Tp, _Alloc>::forward_list(const forward_list& __x, 871227825Stheraven const allocator_type& __a) 872227825Stheraven : base(__a) 873227825Stheraven{ 874227825Stheraven insert_after(cbefore_begin(), __x.begin(), __x.end()); 875227825Stheraven} 876227825Stheraven 877227825Stheraven#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 878227825Stheraven 879227825Stheraventemplate <class _Tp, class _Alloc> 880227825Stheravenforward_list<_Tp, _Alloc>::forward_list(forward_list&& __x, 881227825Stheraven const allocator_type& __a) 882227825Stheraven : base(_VSTD::move(__x), __a) 883227825Stheraven{ 884227825Stheraven if (base::__alloc() != __x.__alloc()) 885227825Stheraven { 886232950Stheraven typedef move_iterator<iterator> _Ip; 887232950Stheraven insert_after(cbefore_begin(), _Ip(__x.begin()), _Ip(__x.end())); 888227825Stheraven } 889227825Stheraven} 890227825Stheraven 891227825Stheraven#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 892227825Stheraven 893227825Stheraven#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 894227825Stheraven 895227825Stheraventemplate <class _Tp, class _Alloc> 896227825Stheravenforward_list<_Tp, _Alloc>::forward_list(initializer_list<value_type> __il) 897227825Stheraven{ 898227825Stheraven insert_after(cbefore_begin(), __il.begin(), __il.end()); 899227825Stheraven} 900227825Stheraven 901227825Stheraventemplate <class _Tp, class _Alloc> 902227825Stheravenforward_list<_Tp, _Alloc>::forward_list(initializer_list<value_type> __il, 903227825Stheraven const allocator_type& __a) 904227825Stheraven : base(__a) 905227825Stheraven{ 906227825Stheraven insert_after(cbefore_begin(), __il.begin(), __il.end()); 907227825Stheraven} 908227825Stheraven 909227825Stheraven#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 910227825Stheraven 911227825Stheraventemplate <class _Tp, class _Alloc> 912227825Stheravenforward_list<_Tp, _Alloc>& 913227825Stheravenforward_list<_Tp, _Alloc>::operator=(const forward_list& __x) 914227825Stheraven{ 915227825Stheraven if (this != &__x) 916227825Stheraven { 917227825Stheraven base::__copy_assign_alloc(__x); 918227825Stheraven assign(__x.begin(), __x.end()); 919227825Stheraven } 920227825Stheraven return *this; 921227825Stheraven} 922227825Stheraven 923227825Stheraven#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 924227825Stheraven 925227825Stheraventemplate <class _Tp, class _Alloc> 926227825Stheravenvoid 927227825Stheravenforward_list<_Tp, _Alloc>::__move_assign(forward_list& __x, true_type) 928227825Stheraven _NOEXCEPT_(is_nothrow_move_assignable<allocator_type>::value) 929227825Stheraven{ 930227825Stheraven clear(); 931227825Stheraven base::__move_assign_alloc(__x); 932227825Stheraven base::__before_begin()->__next_ = __x.__before_begin()->__next_; 933227825Stheraven __x.__before_begin()->__next_ = nullptr; 934227825Stheraven} 935227825Stheraven 936227825Stheraventemplate <class _Tp, class _Alloc> 937227825Stheravenvoid 938227825Stheravenforward_list<_Tp, _Alloc>::__move_assign(forward_list& __x, false_type) 939227825Stheraven{ 940227825Stheraven if (base::__alloc() == __x.__alloc()) 941227825Stheraven __move_assign(__x, true_type()); 942227825Stheraven else 943227825Stheraven { 944232950Stheraven typedef move_iterator<iterator> _Ip; 945232950Stheraven assign(_Ip(__x.begin()), _Ip(__x.end())); 946227825Stheraven } 947227825Stheraven} 948227825Stheraven 949227825Stheraventemplate <class _Tp, class _Alloc> 950227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 951227825Stheravenforward_list<_Tp, _Alloc>& 952227825Stheravenforward_list<_Tp, _Alloc>::operator=(forward_list&& __x) 953227825Stheraven _NOEXCEPT_( 954227825Stheraven __node_traits::propagate_on_container_move_assignment::value && 955227825Stheraven is_nothrow_move_assignable<allocator_type>::value) 956227825Stheraven{ 957227825Stheraven __move_assign(__x, integral_constant<bool, 958227825Stheraven __node_traits::propagate_on_container_move_assignment::value>()); 959227825Stheraven return *this; 960227825Stheraven} 961227825Stheraven 962227825Stheraven#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 963227825Stheraven 964227825Stheraven#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 965227825Stheraven 966227825Stheraventemplate <class _Tp, class _Alloc> 967227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 968227825Stheravenforward_list<_Tp, _Alloc>& 969227825Stheravenforward_list<_Tp, _Alloc>::operator=(initializer_list<value_type> __il) 970227825Stheraven{ 971227825Stheraven assign(__il.begin(), __il.end()); 972227825Stheraven return *this; 973227825Stheraven} 974227825Stheraven 975227825Stheraven#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 976227825Stheraven 977227825Stheraventemplate <class _Tp, class _Alloc> 978227825Stheraventemplate <class _InputIterator> 979227825Stheraventypename enable_if 980227825Stheraven< 981227825Stheraven __is_input_iterator<_InputIterator>::value, 982227825Stheraven void 983227825Stheraven>::type 984227825Stheravenforward_list<_Tp, _Alloc>::assign(_InputIterator __f, _InputIterator __l) 985227825Stheraven{ 986227825Stheraven iterator __i = before_begin(); 987227825Stheraven iterator __j = _VSTD::next(__i); 988227825Stheraven iterator __e = end(); 989227825Stheraven for (; __j != __e && __f != __l; ++__i, ++__j, ++__f) 990227825Stheraven *__j = *__f; 991227825Stheraven if (__j == __e) 992227825Stheraven insert_after(__i, __f, __l); 993227825Stheraven else 994227825Stheraven erase_after(__i, __e); 995227825Stheraven} 996227825Stheraven 997227825Stheraventemplate <class _Tp, class _Alloc> 998227825Stheravenvoid 999227825Stheravenforward_list<_Tp, _Alloc>::assign(size_type __n, const value_type& __v) 1000227825Stheraven{ 1001227825Stheraven iterator __i = before_begin(); 1002227825Stheraven iterator __j = _VSTD::next(__i); 1003227825Stheraven iterator __e = end(); 1004227825Stheraven for (; __j != __e && __n > 0; --__n, ++__i, ++__j) 1005227825Stheraven *__j = __v; 1006227825Stheraven if (__j == __e) 1007227825Stheraven insert_after(__i, __n, __v); 1008227825Stheraven else 1009227825Stheraven erase_after(__i, __e); 1010227825Stheraven} 1011227825Stheraven 1012227825Stheraven#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 1013227825Stheraven 1014227825Stheraventemplate <class _Tp, class _Alloc> 1015227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 1016227825Stheravenvoid 1017227825Stheravenforward_list<_Tp, _Alloc>::assign(initializer_list<value_type> __il) 1018227825Stheraven{ 1019227825Stheraven assign(__il.begin(), __il.end()); 1020227825Stheraven} 1021227825Stheraven 1022227825Stheraven#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 1023227825Stheraven 1024227825Stheraven#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 1025227825Stheraven#ifndef _LIBCPP_HAS_NO_VARIADICS 1026227825Stheraven 1027227825Stheraventemplate <class _Tp, class _Alloc> 1028227825Stheraventemplate <class... _Args> 1029227825Stheravenvoid 1030227825Stheravenforward_list<_Tp, _Alloc>::emplace_front(_Args&&... __args) 1031227825Stheraven{ 1032227825Stheraven __node_allocator& __a = base::__alloc(); 1033232950Stheraven typedef __allocator_destructor<__node_allocator> _Dp; 1034232950Stheraven unique_ptr<__node, _Dp> __h(__node_traits::allocate(__a, 1), _Dp(__a, 1)); 1035227825Stheraven __node_traits::construct(__a, _VSTD::addressof(__h->__value_), 1036227825Stheraven _VSTD::forward<_Args>(__args)...); 1037227825Stheraven __h->__next_ = base::__before_begin()->__next_; 1038227825Stheraven base::__before_begin()->__next_ = __h.release(); 1039227825Stheraven} 1040227825Stheraven 1041227825Stheraven#endif // _LIBCPP_HAS_NO_VARIADICS 1042227825Stheraven 1043227825Stheraventemplate <class _Tp, class _Alloc> 1044227825Stheravenvoid 1045227825Stheravenforward_list<_Tp, _Alloc>::push_front(value_type&& __v) 1046227825Stheraven{ 1047227825Stheraven __node_allocator& __a = base::__alloc(); 1048232950Stheraven typedef __allocator_destructor<__node_allocator> _Dp; 1049232950Stheraven unique_ptr<__node, _Dp> __h(__node_traits::allocate(__a, 1), _Dp(__a, 1)); 1050227825Stheraven __node_traits::construct(__a, _VSTD::addressof(__h->__value_), _VSTD::move(__v)); 1051227825Stheraven __h->__next_ = base::__before_begin()->__next_; 1052227825Stheraven base::__before_begin()->__next_ = __h.release(); 1053227825Stheraven} 1054227825Stheraven 1055227825Stheraven#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 1056227825Stheraven 1057227825Stheraventemplate <class _Tp, class _Alloc> 1058227825Stheravenvoid 1059227825Stheravenforward_list<_Tp, _Alloc>::push_front(const value_type& __v) 1060227825Stheraven{ 1061227825Stheraven __node_allocator& __a = base::__alloc(); 1062232950Stheraven typedef __allocator_destructor<__node_allocator> _Dp; 1063232950Stheraven unique_ptr<__node, _Dp> __h(__node_traits::allocate(__a, 1), _Dp(__a, 1)); 1064227825Stheraven __node_traits::construct(__a, _VSTD::addressof(__h->__value_), __v); 1065227825Stheraven __h->__next_ = base::__before_begin()->__next_; 1066227825Stheraven base::__before_begin()->__next_ = __h.release(); 1067227825Stheraven} 1068227825Stheraven 1069227825Stheraventemplate <class _Tp, class _Alloc> 1070227825Stheravenvoid 1071227825Stheravenforward_list<_Tp, _Alloc>::pop_front() 1072227825Stheraven{ 1073227825Stheraven __node_allocator& __a = base::__alloc(); 1074227825Stheraven __node_pointer __p = base::__before_begin()->__next_; 1075227825Stheraven base::__before_begin()->__next_ = __p->__next_; 1076227825Stheraven __node_traits::destroy(__a, _VSTD::addressof(__p->__value_)); 1077227825Stheraven __node_traits::deallocate(__a, __p, 1); 1078227825Stheraven} 1079227825Stheraven 1080227825Stheraven#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 1081227825Stheraven#ifndef _LIBCPP_HAS_NO_VARIADICS 1082227825Stheraven 1083227825Stheraventemplate <class _Tp, class _Alloc> 1084227825Stheraventemplate <class... _Args> 1085227825Stheraventypename forward_list<_Tp, _Alloc>::iterator 1086227825Stheravenforward_list<_Tp, _Alloc>::emplace_after(const_iterator __p, _Args&&... __args) 1087227825Stheraven{ 1088253159Stheraven __node_pointer const __r = __p.__ptr_; 1089227825Stheraven __node_allocator& __a = base::__alloc(); 1090232950Stheraven typedef __allocator_destructor<__node_allocator> _Dp; 1091232950Stheraven unique_ptr<__node, _Dp> __h(__node_traits::allocate(__a, 1), _Dp(__a, 1)); 1092227825Stheraven __node_traits::construct(__a, _VSTD::addressof(__h->__value_), 1093227825Stheraven _VSTD::forward<_Args>(__args)...); 1094227825Stheraven __h->__next_ = __r->__next_; 1095227825Stheraven __r->__next_ = __h.release(); 1096227825Stheraven return iterator(__r->__next_); 1097227825Stheraven} 1098227825Stheraven 1099227825Stheraven#endif // _LIBCPP_HAS_NO_VARIADICS 1100227825Stheraven 1101227825Stheraventemplate <class _Tp, class _Alloc> 1102227825Stheraventypename forward_list<_Tp, _Alloc>::iterator 1103227825Stheravenforward_list<_Tp, _Alloc>::insert_after(const_iterator __p, value_type&& __v) 1104227825Stheraven{ 1105253159Stheraven __node_pointer const __r = __p.__ptr_; 1106227825Stheraven __node_allocator& __a = base::__alloc(); 1107232950Stheraven typedef __allocator_destructor<__node_allocator> _Dp; 1108232950Stheraven unique_ptr<__node, _Dp> __h(__node_traits::allocate(__a, 1), _Dp(__a, 1)); 1109227825Stheraven __node_traits::construct(__a, _VSTD::addressof(__h->__value_), _VSTD::move(__v)); 1110227825Stheraven __h->__next_ = __r->__next_; 1111227825Stheraven __r->__next_ = __h.release(); 1112227825Stheraven return iterator(__r->__next_); 1113227825Stheraven} 1114227825Stheraven 1115227825Stheraven#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 1116227825Stheraven 1117227825Stheraventemplate <class _Tp, class _Alloc> 1118227825Stheraventypename forward_list<_Tp, _Alloc>::iterator 1119227825Stheravenforward_list<_Tp, _Alloc>::insert_after(const_iterator __p, const value_type& __v) 1120227825Stheraven{ 1121253159Stheraven __node_pointer const __r = __p.__ptr_; 1122227825Stheraven __node_allocator& __a = base::__alloc(); 1123232950Stheraven typedef __allocator_destructor<__node_allocator> _Dp; 1124232950Stheraven unique_ptr<__node, _Dp> __h(__node_traits::allocate(__a, 1), _Dp(__a, 1)); 1125227825Stheraven __node_traits::construct(__a, _VSTD::addressof(__h->__value_), __v); 1126227825Stheraven __h->__next_ = __r->__next_; 1127227825Stheraven __r->__next_ = __h.release(); 1128227825Stheraven return iterator(__r->__next_); 1129227825Stheraven} 1130227825Stheraven 1131227825Stheraventemplate <class _Tp, class _Alloc> 1132227825Stheraventypename forward_list<_Tp, _Alloc>::iterator 1133227825Stheravenforward_list<_Tp, _Alloc>::insert_after(const_iterator __p, size_type __n, 1134227825Stheraven const value_type& __v) 1135227825Stheraven{ 1136253159Stheraven __node_pointer __r = __p.__ptr_; 1137227825Stheraven if (__n > 0) 1138227825Stheraven { 1139227825Stheraven __node_allocator& __a = base::__alloc(); 1140232950Stheraven typedef __allocator_destructor<__node_allocator> _Dp; 1141232950Stheraven unique_ptr<__node, _Dp> __h(__node_traits::allocate(__a, 1), _Dp(__a, 1)); 1142227825Stheraven __node_traits::construct(__a, _VSTD::addressof(__h->__value_), __v); 1143227825Stheraven __node_pointer __first = __h.release(); 1144227825Stheraven __node_pointer __last = __first; 1145227825Stheraven#ifndef _LIBCPP_NO_EXCEPTIONS 1146227825Stheraven try 1147227825Stheraven { 1148227825Stheraven#endif // _LIBCPP_NO_EXCEPTIONS 1149227825Stheraven for (--__n; __n != 0; --__n, __last = __last->__next_) 1150227825Stheraven { 1151227825Stheraven __h.reset(__node_traits::allocate(__a, 1)); 1152227825Stheraven __node_traits::construct(__a, _VSTD::addressof(__h->__value_), __v); 1153227825Stheraven __last->__next_ = __h.release(); 1154227825Stheraven } 1155227825Stheraven#ifndef _LIBCPP_NO_EXCEPTIONS 1156227825Stheraven } 1157227825Stheraven catch (...) 1158227825Stheraven { 1159227825Stheraven while (__first != nullptr) 1160227825Stheraven { 1161227825Stheraven __node_pointer __next = __first->__next_; 1162227825Stheraven __node_traits::destroy(__a, _VSTD::addressof(__first->__value_)); 1163227825Stheraven __node_traits::deallocate(__a, __first, 1); 1164227825Stheraven __first = __next; 1165227825Stheraven } 1166227825Stheraven throw; 1167227825Stheraven } 1168227825Stheraven#endif // _LIBCPP_NO_EXCEPTIONS 1169227825Stheraven __last->__next_ = __r->__next_; 1170227825Stheraven __r->__next_ = __first; 1171227825Stheraven __r = __last; 1172227825Stheraven } 1173227825Stheraven return iterator(__r); 1174227825Stheraven} 1175227825Stheraven 1176227825Stheraventemplate <class _Tp, class _Alloc> 1177227825Stheraventemplate <class _InputIterator> 1178227825Stheraventypename enable_if 1179227825Stheraven< 1180227825Stheraven __is_input_iterator<_InputIterator>::value, 1181227825Stheraven typename forward_list<_Tp, _Alloc>::iterator 1182227825Stheraven>::type 1183227825Stheravenforward_list<_Tp, _Alloc>::insert_after(const_iterator __p, 1184227825Stheraven _InputIterator __f, _InputIterator __l) 1185227825Stheraven{ 1186253159Stheraven __node_pointer __r = __p.__ptr_; 1187227825Stheraven if (__f != __l) 1188227825Stheraven { 1189227825Stheraven __node_allocator& __a = base::__alloc(); 1190232950Stheraven typedef __allocator_destructor<__node_allocator> _Dp; 1191232950Stheraven unique_ptr<__node, _Dp> __h(__node_traits::allocate(__a, 1), _Dp(__a, 1)); 1192227825Stheraven __node_traits::construct(__a, _VSTD::addressof(__h->__value_), *__f); 1193227825Stheraven __node_pointer __first = __h.release(); 1194227825Stheraven __node_pointer __last = __first; 1195227825Stheraven#ifndef _LIBCPP_NO_EXCEPTIONS 1196227825Stheraven try 1197227825Stheraven { 1198227825Stheraven#endif // _LIBCPP_NO_EXCEPTIONS 1199227825Stheraven for (++__f; __f != __l; ++__f, __last = __last->__next_) 1200227825Stheraven { 1201227825Stheraven __h.reset(__node_traits::allocate(__a, 1)); 1202227825Stheraven __node_traits::construct(__a, _VSTD::addressof(__h->__value_), *__f); 1203227825Stheraven __last->__next_ = __h.release(); 1204227825Stheraven } 1205227825Stheraven#ifndef _LIBCPP_NO_EXCEPTIONS 1206227825Stheraven } 1207227825Stheraven catch (...) 1208227825Stheraven { 1209227825Stheraven while (__first != nullptr) 1210227825Stheraven { 1211227825Stheraven __node_pointer __next = __first->__next_; 1212227825Stheraven __node_traits::destroy(__a, _VSTD::addressof(__first->__value_)); 1213227825Stheraven __node_traits::deallocate(__a, __first, 1); 1214227825Stheraven __first = __next; 1215227825Stheraven } 1216227825Stheraven throw; 1217227825Stheraven } 1218227825Stheraven#endif // _LIBCPP_NO_EXCEPTIONS 1219227825Stheraven __last->__next_ = __r->__next_; 1220227825Stheraven __r->__next_ = __first; 1221227825Stheraven __r = __last; 1222227825Stheraven } 1223227825Stheraven return iterator(__r); 1224227825Stheraven} 1225227825Stheraven 1226227825Stheraventemplate <class _Tp, class _Alloc> 1227227825Stheraventypename forward_list<_Tp, _Alloc>::iterator 1228227825Stheravenforward_list<_Tp, _Alloc>::erase_after(const_iterator __f) 1229227825Stheraven{ 1230253159Stheraven __node_pointer __p = __f.__ptr_; 1231227825Stheraven __node_pointer __n = __p->__next_; 1232227825Stheraven __p->__next_ = __n->__next_; 1233227825Stheraven __node_allocator& __a = base::__alloc(); 1234227825Stheraven __node_traits::destroy(__a, _VSTD::addressof(__n->__value_)); 1235227825Stheraven __node_traits::deallocate(__a, __n, 1); 1236227825Stheraven return iterator(__p->__next_); 1237227825Stheraven} 1238227825Stheraven 1239227825Stheraventemplate <class _Tp, class _Alloc> 1240227825Stheraventypename forward_list<_Tp, _Alloc>::iterator 1241227825Stheravenforward_list<_Tp, _Alloc>::erase_after(const_iterator __f, const_iterator __l) 1242227825Stheraven{ 1243253159Stheraven __node_pointer __e = __l.__ptr_; 1244227825Stheraven if (__f != __l) 1245227825Stheraven { 1246253159Stheraven __node_pointer __p = __f.__ptr_; 1247227825Stheraven __node_pointer __n = __p->__next_; 1248227825Stheraven if (__n != __e) 1249227825Stheraven { 1250227825Stheraven __p->__next_ = __e; 1251227825Stheraven __node_allocator& __a = base::__alloc(); 1252227825Stheraven do 1253227825Stheraven { 1254227825Stheraven __p = __n->__next_; 1255227825Stheraven __node_traits::destroy(__a, _VSTD::addressof(__n->__value_)); 1256227825Stheraven __node_traits::deallocate(__a, __n, 1); 1257227825Stheraven __n = __p; 1258227825Stheraven } while (__n != __e); 1259227825Stheraven } 1260227825Stheraven } 1261227825Stheraven return iterator(__e); 1262227825Stheraven} 1263227825Stheraven 1264227825Stheraventemplate <class _Tp, class _Alloc> 1265227825Stheravenvoid 1266227825Stheravenforward_list<_Tp, _Alloc>::resize(size_type __n) 1267227825Stheraven{ 1268227825Stheraven size_type __sz = 0; 1269227825Stheraven iterator __p = before_begin(); 1270227825Stheraven iterator __i = begin(); 1271227825Stheraven iterator __e = end(); 1272227825Stheraven for (; __i != __e && __sz < __n; ++__p, ++__i, ++__sz) 1273227825Stheraven ; 1274227825Stheraven if (__i != __e) 1275227825Stheraven erase_after(__p, __e); 1276227825Stheraven else 1277227825Stheraven { 1278227825Stheraven __n -= __sz; 1279227825Stheraven if (__n > 0) 1280227825Stheraven { 1281227825Stheraven __node_allocator& __a = base::__alloc(); 1282232950Stheraven typedef __allocator_destructor<__node_allocator> _Dp; 1283232950Stheraven unique_ptr<__node, _Dp> __h(nullptr, _Dp(__a, 1)); 1284227825Stheraven for (__node_pointer __ptr = __p.__ptr_; __n > 0; --__n, 1285227825Stheraven __ptr = __ptr->__next_) 1286227825Stheraven { 1287227825Stheraven __h.reset(__node_traits::allocate(__a, 1)); 1288227825Stheraven __node_traits::construct(__a, _VSTD::addressof(__h->__value_)); 1289227825Stheraven __h->__next_ = nullptr; 1290227825Stheraven __ptr->__next_ = __h.release(); 1291227825Stheraven } 1292227825Stheraven } 1293227825Stheraven } 1294227825Stheraven} 1295227825Stheraven 1296227825Stheraventemplate <class _Tp, class _Alloc> 1297227825Stheravenvoid 1298227825Stheravenforward_list<_Tp, _Alloc>::resize(size_type __n, const value_type& __v) 1299227825Stheraven{ 1300227825Stheraven size_type __sz = 0; 1301227825Stheraven iterator __p = before_begin(); 1302227825Stheraven iterator __i = begin(); 1303227825Stheraven iterator __e = end(); 1304227825Stheraven for (; __i != __e && __sz < __n; ++__p, ++__i, ++__sz) 1305227825Stheraven ; 1306227825Stheraven if (__i != __e) 1307227825Stheraven erase_after(__p, __e); 1308227825Stheraven else 1309227825Stheraven { 1310227825Stheraven __n -= __sz; 1311227825Stheraven if (__n > 0) 1312227825Stheraven { 1313227825Stheraven __node_allocator& __a = base::__alloc(); 1314232950Stheraven typedef __allocator_destructor<__node_allocator> _Dp; 1315232950Stheraven unique_ptr<__node, _Dp> __h(nullptr, _Dp(__a, 1)); 1316227825Stheraven for (__node_pointer __ptr = __p.__ptr_; __n > 0; --__n, 1317227825Stheraven __ptr = __ptr->__next_) 1318227825Stheraven { 1319227825Stheraven __h.reset(__node_traits::allocate(__a, 1)); 1320227825Stheraven __node_traits::construct(__a, _VSTD::addressof(__h->__value_), __v); 1321227825Stheraven __h->__next_ = nullptr; 1322227825Stheraven __ptr->__next_ = __h.release(); 1323227825Stheraven } 1324227825Stheraven } 1325227825Stheraven } 1326227825Stheraven} 1327227825Stheraven 1328227825Stheraventemplate <class _Tp, class _Alloc> 1329227825Stheravenvoid 1330227825Stheravenforward_list<_Tp, _Alloc>::splice_after(const_iterator __p, 1331227825Stheraven forward_list& __x) 1332227825Stheraven{ 1333227825Stheraven if (!__x.empty()) 1334227825Stheraven { 1335227825Stheraven if (__p.__ptr_->__next_ != nullptr) 1336227825Stheraven { 1337227825Stheraven const_iterator __lm1 = __x.before_begin(); 1338227825Stheraven while (__lm1.__ptr_->__next_ != nullptr) 1339227825Stheraven ++__lm1; 1340253159Stheraven __lm1.__ptr_->__next_ = __p.__ptr_->__next_; 1341227825Stheraven } 1342253159Stheraven __p.__ptr_->__next_ = __x.__before_begin()->__next_; 1343253159Stheraven __x.__before_begin()->__next_ = nullptr; 1344227825Stheraven } 1345227825Stheraven} 1346227825Stheraven 1347227825Stheraventemplate <class _Tp, class _Alloc> 1348227825Stheravenvoid 1349227825Stheravenforward_list<_Tp, _Alloc>::splice_after(const_iterator __p, 1350227825Stheraven forward_list& __x, 1351227825Stheraven const_iterator __i) 1352227825Stheraven{ 1353227825Stheraven const_iterator __lm1 = _VSTD::next(__i); 1354227825Stheraven if (__p != __i && __p != __lm1) 1355227825Stheraven { 1356253159Stheraven __i.__ptr_->__next_ = __lm1.__ptr_->__next_; 1357253159Stheraven __lm1.__ptr_->__next_ = __p.__ptr_->__next_; 1358253159Stheraven __p.__ptr_->__next_ = __lm1.__ptr_; 1359227825Stheraven } 1360227825Stheraven} 1361227825Stheraven 1362227825Stheraventemplate <class _Tp, class _Alloc> 1363227825Stheravenvoid 1364227825Stheravenforward_list<_Tp, _Alloc>::splice_after(const_iterator __p, 1365227825Stheraven forward_list& __x, 1366227825Stheraven const_iterator __f, const_iterator __l) 1367227825Stheraven{ 1368227825Stheraven if (__f != __l && __p != __f) 1369227825Stheraven { 1370227825Stheraven const_iterator __lm1 = __f; 1371227825Stheraven while (__lm1.__ptr_->__next_ != __l.__ptr_) 1372227825Stheraven ++__lm1; 1373227825Stheraven if (__f != __lm1) 1374227825Stheraven { 1375253159Stheraven __lm1.__ptr_->__next_ = __p.__ptr_->__next_; 1376253159Stheraven __p.__ptr_->__next_ = __f.__ptr_->__next_; 1377253159Stheraven __f.__ptr_->__next_ = __l.__ptr_; 1378227825Stheraven } 1379227825Stheraven } 1380227825Stheraven} 1381227825Stheraven 1382227825Stheraven#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 1383227825Stheraven 1384227825Stheraventemplate <class _Tp, class _Alloc> 1385227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 1386227825Stheravenvoid 1387227825Stheravenforward_list<_Tp, _Alloc>::splice_after(const_iterator __p, 1388227825Stheraven forward_list&& __x) 1389227825Stheraven{ 1390227825Stheraven splice_after(__p, __x); 1391227825Stheraven} 1392227825Stheraven 1393227825Stheraventemplate <class _Tp, class _Alloc> 1394227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 1395227825Stheravenvoid 1396227825Stheravenforward_list<_Tp, _Alloc>::splice_after(const_iterator __p, 1397227825Stheraven forward_list&& __x, 1398227825Stheraven const_iterator __i) 1399227825Stheraven{ 1400227825Stheraven splice_after(__p, __x, __i); 1401227825Stheraven} 1402227825Stheraven 1403227825Stheraventemplate <class _Tp, class _Alloc> 1404227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 1405227825Stheravenvoid 1406227825Stheravenforward_list<_Tp, _Alloc>::splice_after(const_iterator __p, 1407227825Stheraven forward_list&& __x, 1408227825Stheraven const_iterator __f, const_iterator __l) 1409227825Stheraven{ 1410227825Stheraven splice_after(__p, __x, __f, __l); 1411227825Stheraven} 1412227825Stheraven 1413227825Stheraven#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 1414227825Stheraven 1415227825Stheraventemplate <class _Tp, class _Alloc> 1416227825Stheravenvoid 1417227825Stheravenforward_list<_Tp, _Alloc>::remove(const value_type& __v) 1418227825Stheraven{ 1419227825Stheraven iterator __e = end(); 1420227825Stheraven for (iterator __i = before_begin(); __i.__ptr_->__next_ != nullptr;) 1421227825Stheraven { 1422227825Stheraven if (__i.__ptr_->__next_->__value_ == __v) 1423227825Stheraven { 1424227825Stheraven iterator __j = _VSTD::next(__i, 2); 1425227825Stheraven for (; __j != __e && *__j == __v; ++__j) 1426227825Stheraven ; 1427227825Stheraven erase_after(__i, __j); 1428227825Stheraven if (__j == __e) 1429227825Stheraven break; 1430227825Stheraven __i = __j; 1431227825Stheraven } 1432227825Stheraven else 1433227825Stheraven ++__i; 1434227825Stheraven } 1435227825Stheraven} 1436227825Stheraven 1437227825Stheraventemplate <class _Tp, class _Alloc> 1438227825Stheraventemplate <class _Predicate> 1439227825Stheravenvoid 1440227825Stheravenforward_list<_Tp, _Alloc>::remove_if(_Predicate __pred) 1441227825Stheraven{ 1442227825Stheraven iterator __e = end(); 1443227825Stheraven for (iterator __i = before_begin(); __i.__ptr_->__next_ != nullptr;) 1444227825Stheraven { 1445227825Stheraven if (__pred(__i.__ptr_->__next_->__value_)) 1446227825Stheraven { 1447227825Stheraven iterator __j = _VSTD::next(__i, 2); 1448227825Stheraven for (; __j != __e && __pred(*__j); ++__j) 1449227825Stheraven ; 1450227825Stheraven erase_after(__i, __j); 1451227825Stheraven if (__j == __e) 1452227825Stheraven break; 1453227825Stheraven __i = __j; 1454227825Stheraven } 1455227825Stheraven else 1456227825Stheraven ++__i; 1457227825Stheraven } 1458227825Stheraven} 1459227825Stheraven 1460227825Stheraventemplate <class _Tp, class _Alloc> 1461227825Stheraventemplate <class _BinaryPredicate> 1462227825Stheravenvoid 1463227825Stheravenforward_list<_Tp, _Alloc>::unique(_BinaryPredicate __binary_pred) 1464227825Stheraven{ 1465227825Stheraven for (iterator __i = begin(), __e = end(); __i != __e;) 1466227825Stheraven { 1467227825Stheraven iterator __j = _VSTD::next(__i); 1468227825Stheraven for (; __j != __e && __binary_pred(*__i, *__j); ++__j) 1469227825Stheraven ; 1470227825Stheraven if (__i.__ptr_->__next_ != __j.__ptr_) 1471227825Stheraven erase_after(__i, __j); 1472227825Stheraven __i = __j; 1473227825Stheraven } 1474227825Stheraven} 1475227825Stheraven 1476227825Stheraventemplate <class _Tp, class _Alloc> 1477227825Stheraventemplate <class _Compare> 1478227825Stheravenvoid 1479227825Stheravenforward_list<_Tp, _Alloc>::merge(forward_list& __x, _Compare __comp) 1480227825Stheraven{ 1481227825Stheraven if (this != &__x) 1482227825Stheraven { 1483227825Stheraven base::__before_begin()->__next_ = __merge(base::__before_begin()->__next_, 1484227825Stheraven __x.__before_begin()->__next_, 1485227825Stheraven __comp); 1486227825Stheraven __x.__before_begin()->__next_ = nullptr; 1487227825Stheraven } 1488227825Stheraven} 1489227825Stheraven 1490227825Stheraventemplate <class _Tp, class _Alloc> 1491227825Stheraventemplate <class _Compare> 1492227825Stheraventypename forward_list<_Tp, _Alloc>::__node_pointer 1493227825Stheravenforward_list<_Tp, _Alloc>::__merge(__node_pointer __f1, __node_pointer __f2, 1494227825Stheraven _Compare& __comp) 1495227825Stheraven{ 1496227825Stheraven if (__f1 == nullptr) 1497227825Stheraven return __f2; 1498227825Stheraven if (__f2 == nullptr) 1499227825Stheraven return __f1; 1500227825Stheraven __node_pointer __r; 1501227825Stheraven if (__comp(__f2->__value_, __f1->__value_)) 1502227825Stheraven { 1503227825Stheraven __node_pointer __t = __f2; 1504227825Stheraven while (__t->__next_ != nullptr && 1505227825Stheraven __comp(__t->__next_->__value_, __f1->__value_)) 1506227825Stheraven __t = __t->__next_; 1507227825Stheraven __r = __f2; 1508227825Stheraven __f2 = __t->__next_; 1509227825Stheraven __t->__next_ = __f1; 1510227825Stheraven } 1511227825Stheraven else 1512227825Stheraven __r = __f1; 1513227825Stheraven __node_pointer __p = __f1; 1514227825Stheraven __f1 = __f1->__next_; 1515227825Stheraven while (__f1 != nullptr && __f2 != nullptr) 1516227825Stheraven { 1517227825Stheraven if (__comp(__f2->__value_, __f1->__value_)) 1518227825Stheraven { 1519227825Stheraven __node_pointer __t = __f2; 1520227825Stheraven while (__t->__next_ != nullptr && 1521227825Stheraven __comp(__t->__next_->__value_, __f1->__value_)) 1522227825Stheraven __t = __t->__next_; 1523227825Stheraven __p->__next_ = __f2; 1524227825Stheraven __f2 = __t->__next_; 1525227825Stheraven __t->__next_ = __f1; 1526227825Stheraven } 1527227825Stheraven __p = __f1; 1528227825Stheraven __f1 = __f1->__next_; 1529227825Stheraven } 1530227825Stheraven if (__f2 != nullptr) 1531227825Stheraven __p->__next_ = __f2; 1532227825Stheraven return __r; 1533227825Stheraven} 1534227825Stheraven 1535227825Stheraventemplate <class _Tp, class _Alloc> 1536227825Stheraventemplate <class _Compare> 1537227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 1538227825Stheravenvoid 1539227825Stheravenforward_list<_Tp, _Alloc>::sort(_Compare __comp) 1540227825Stheraven{ 1541227825Stheraven base::__before_begin()->__next_ = __sort(base::__before_begin()->__next_, 1542227825Stheraven _VSTD::distance(begin(), end()), __comp); 1543227825Stheraven} 1544227825Stheraven 1545227825Stheraventemplate <class _Tp, class _Alloc> 1546227825Stheraventemplate <class _Compare> 1547227825Stheraventypename forward_list<_Tp, _Alloc>::__node_pointer 1548227825Stheravenforward_list<_Tp, _Alloc>::__sort(__node_pointer __f1, difference_type __sz, 1549227825Stheraven _Compare& __comp) 1550227825Stheraven{ 1551227825Stheraven switch (__sz) 1552227825Stheraven { 1553227825Stheraven case 0: 1554227825Stheraven case 1: 1555227825Stheraven return __f1; 1556227825Stheraven case 2: 1557227825Stheraven if (__comp(__f1->__next_->__value_, __f1->__value_)) 1558227825Stheraven { 1559227825Stheraven __node_pointer __t = __f1->__next_; 1560227825Stheraven __t->__next_ = __f1; 1561227825Stheraven __f1->__next_ = nullptr; 1562227825Stheraven __f1 = __t; 1563227825Stheraven } 1564227825Stheraven return __f1; 1565227825Stheraven } 1566227825Stheraven difference_type __sz1 = __sz / 2; 1567227825Stheraven difference_type __sz2 = __sz - __sz1; 1568227825Stheraven __node_pointer __t = _VSTD::next(iterator(__f1), __sz1 - 1).__ptr_; 1569227825Stheraven __node_pointer __f2 = __t->__next_; 1570227825Stheraven __t->__next_ = nullptr; 1571227825Stheraven return __merge(__sort(__f1, __sz1, __comp), 1572227825Stheraven __sort(__f2, __sz2, __comp), __comp); 1573227825Stheraven} 1574227825Stheraven 1575227825Stheraventemplate <class _Tp, class _Alloc> 1576227825Stheravenvoid 1577227825Stheravenforward_list<_Tp, _Alloc>::reverse() _NOEXCEPT 1578227825Stheraven{ 1579227825Stheraven __node_pointer __p = base::__before_begin()->__next_; 1580227825Stheraven if (__p != nullptr) 1581227825Stheraven { 1582227825Stheraven __node_pointer __f = __p->__next_; 1583227825Stheraven __p->__next_ = nullptr; 1584227825Stheraven while (__f != nullptr) 1585227825Stheraven { 1586227825Stheraven __node_pointer __t = __f->__next_; 1587227825Stheraven __f->__next_ = __p; 1588227825Stheraven __p = __f; 1589227825Stheraven __f = __t; 1590227825Stheraven } 1591227825Stheraven base::__before_begin()->__next_ = __p; 1592227825Stheraven } 1593227825Stheraven} 1594227825Stheraven 1595227825Stheraventemplate <class _Tp, class _Alloc> 1596227825Stheravenbool operator==(const forward_list<_Tp, _Alloc>& __x, 1597227825Stheraven const forward_list<_Tp, _Alloc>& __y) 1598227825Stheraven{ 1599232950Stheraven typedef forward_list<_Tp, _Alloc> _Cp; 1600232950Stheraven typedef typename _Cp::const_iterator _Ip; 1601232950Stheraven _Ip __ix = __x.begin(); 1602232950Stheraven _Ip __ex = __x.end(); 1603232950Stheraven _Ip __iy = __y.begin(); 1604232950Stheraven _Ip __ey = __y.end(); 1605227825Stheraven for (; __ix != __ex && __iy != __ey; ++__ix, ++__iy) 1606227825Stheraven if (!(*__ix == *__iy)) 1607227825Stheraven return false; 1608227825Stheraven return (__ix == __ex) == (__iy == __ey); 1609227825Stheraven} 1610227825Stheraven 1611227825Stheraventemplate <class _Tp, class _Alloc> 1612227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 1613227825Stheravenbool operator!=(const forward_list<_Tp, _Alloc>& __x, 1614227825Stheraven const forward_list<_Tp, _Alloc>& __y) 1615227825Stheraven{ 1616227825Stheraven return !(__x == __y); 1617227825Stheraven} 1618227825Stheraven 1619227825Stheraventemplate <class _Tp, class _Alloc> 1620227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 1621227825Stheravenbool operator< (const forward_list<_Tp, _Alloc>& __x, 1622227825Stheraven const forward_list<_Tp, _Alloc>& __y) 1623227825Stheraven{ 1624227825Stheraven return _VSTD::lexicographical_compare(__x.begin(), __x.end(), 1625227825Stheraven __y.begin(), __y.end()); 1626227825Stheraven} 1627227825Stheraven 1628227825Stheraventemplate <class _Tp, class _Alloc> 1629227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 1630227825Stheravenbool operator> (const forward_list<_Tp, _Alloc>& __x, 1631227825Stheraven const forward_list<_Tp, _Alloc>& __y) 1632227825Stheraven{ 1633227825Stheraven return __y < __x; 1634227825Stheraven} 1635227825Stheraven 1636227825Stheraventemplate <class _Tp, class _Alloc> 1637227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 1638227825Stheravenbool operator>=(const forward_list<_Tp, _Alloc>& __x, 1639227825Stheraven const forward_list<_Tp, _Alloc>& __y) 1640227825Stheraven{ 1641227825Stheraven return !(__x < __y); 1642227825Stheraven} 1643227825Stheraven 1644227825Stheraventemplate <class _Tp, class _Alloc> 1645227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 1646227825Stheravenbool operator<=(const forward_list<_Tp, _Alloc>& __x, 1647227825Stheraven const forward_list<_Tp, _Alloc>& __y) 1648227825Stheraven{ 1649227825Stheraven return !(__y < __x); 1650227825Stheraven} 1651227825Stheraven 1652227825Stheraventemplate <class _Tp, class _Alloc> 1653227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 1654227825Stheravenvoid 1655227825Stheravenswap(forward_list<_Tp, _Alloc>& __x, forward_list<_Tp, _Alloc>& __y) 1656227825Stheraven _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y))) 1657227825Stheraven{ 1658227825Stheraven __x.swap(__y); 1659227825Stheraven} 1660227825Stheraven 1661227825Stheraven_LIBCPP_END_NAMESPACE_STD 1662227825Stheraven 1663227825Stheraven#endif // _LIBCPP_FORWARD_LIST 1664