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