forward_list revision 232950
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 215227825Stheraventemplate<class _Tp, class _Alloc> class forward_list; 216227825Stheraventemplate<class _NodeConstPtr> class __forward_list_const_iterator; 217227825Stheraven 218227825Stheraventemplate <class _NodePtr> 219227825Stheravenclass _LIBCPP_VISIBLE __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 228227825Stheraven template<class, class> friend class forward_list; 229227825Stheraven template<class> friend class __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; 235227825Stheraven 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 252227825Stheraven pointer operator->() const {return &__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> 279227825Stheravenclass _LIBCPP_VISIBLE __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; 306227825Stheraven 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 326227825Stheraven pointer operator->() const {return &__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; 371227825Stheraven typedef typename __node_traits::const_pointer __node_const_pointer; 372227825Stheraven 373227825Stheraven __compressed_pair<__begin_node, __node_allocator> __before_begin_; 374227825Stheraven 375227825Stheraven _LIBCPP_INLINE_VISIBILITY 376227825Stheraven __node_pointer __before_begin() _NOEXCEPT 377227825Stheraven {return pointer_traits<__node_pointer>::pointer_to( 378227825Stheraven static_cast<__node&>(__before_begin_.first()));} 379227825Stheraven _LIBCPP_INLINE_VISIBILITY 380227825Stheraven __node_const_pointer __before_begin() const _NOEXCEPT 381227825Stheraven {return pointer_traits<__node_const_pointer>::pointer_to( 382227825Stheraven static_cast<const __node&>(__before_begin_.first()));} 383227825Stheraven 384227825Stheraven _LIBCPP_INLINE_VISIBILITY 385227825Stheraven __node_allocator& __alloc() _NOEXCEPT 386227825Stheraven {return __before_begin_.second();} 387227825Stheraven _LIBCPP_INLINE_VISIBILITY 388227825Stheraven const __node_allocator& __alloc() const _NOEXCEPT 389227825Stheraven {return __before_begin_.second();} 390227825Stheraven 391227825Stheraven typedef __forward_list_iterator<__node_pointer> iterator; 392227825Stheraven typedef __forward_list_const_iterator<__node_const_pointer> const_iterator; 393227825Stheraven 394227825Stheraven _LIBCPP_INLINE_VISIBILITY 395227825Stheraven __forward_list_base() 396227825Stheraven _NOEXCEPT_(is_nothrow_default_constructible<__node_allocator>::value) 397227825Stheraven : __before_begin_(__begin_node()) {} 398227825Stheraven _LIBCPP_INLINE_VISIBILITY 399227825Stheraven __forward_list_base(const allocator_type& __a) 400227825Stheraven : __before_begin_(__begin_node(), __node_allocator(__a)) {} 401227825Stheraven 402227825Stheraven#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 403227825Stheravenpublic: 404227825Stheraven __forward_list_base(__forward_list_base&& __x) 405227825Stheraven _NOEXCEPT_(is_nothrow_move_constructible<__node_allocator>::value); 406227825Stheraven __forward_list_base(__forward_list_base&& __x, const allocator_type& __a); 407227825Stheraven#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 408227825Stheraven 409227825Stheravenprivate: 410227825Stheraven __forward_list_base(const __forward_list_base&); 411227825Stheraven __forward_list_base& operator=(const __forward_list_base&); 412227825Stheraven 413227825Stheravenpublic: 414227825Stheraven ~__forward_list_base(); 415227825Stheraven 416227825Stheravenprotected: 417227825Stheraven _LIBCPP_INLINE_VISIBILITY 418227825Stheraven void __copy_assign_alloc(const __forward_list_base& __x) 419227825Stheraven {__copy_assign_alloc(__x, integral_constant<bool, 420227825Stheraven __node_traits::propagate_on_container_copy_assignment::value>());} 421227825Stheraven 422227825Stheraven _LIBCPP_INLINE_VISIBILITY 423227825Stheraven void __move_assign_alloc(__forward_list_base& __x) 424227825Stheraven _NOEXCEPT_(!__node_traits::propagate_on_container_move_assignment::value || 425227825Stheraven is_nothrow_move_assignable<__node_allocator>::value) 426227825Stheraven {__move_assign_alloc(__x, integral_constant<bool, 427227825Stheraven __node_traits::propagate_on_container_move_assignment::value>());} 428227825Stheraven 429227825Stheravenpublic: 430227825Stheraven void swap(__forward_list_base& __x) 431227825Stheraven _NOEXCEPT_(!__node_traits::propagate_on_container_swap::value || 432227825Stheraven __is_nothrow_swappable<__node_allocator>::value); 433227825Stheravenprotected: 434227825Stheraven void clear() _NOEXCEPT; 435227825Stheraven 436227825Stheravenprivate: 437227825Stheraven _LIBCPP_INLINE_VISIBILITY 438227825Stheraven void __copy_assign_alloc(const __forward_list_base&, false_type) {} 439227825Stheraven _LIBCPP_INLINE_VISIBILITY 440227825Stheraven void __copy_assign_alloc(const __forward_list_base& __x, true_type) 441227825Stheraven { 442227825Stheraven if (__alloc() != __x.__alloc()) 443227825Stheraven clear(); 444227825Stheraven __alloc() = __x.__alloc(); 445227825Stheraven } 446227825Stheraven 447227825Stheraven _LIBCPP_INLINE_VISIBILITY 448227825Stheraven void __move_assign_alloc(__forward_list_base& __x, false_type) _NOEXCEPT 449227825Stheraven {} 450227825Stheraven _LIBCPP_INLINE_VISIBILITY 451227825Stheraven void __move_assign_alloc(__forward_list_base& __x, true_type) 452227825Stheraven _NOEXCEPT_(is_nothrow_move_assignable<__node_allocator>::value) 453227825Stheraven {__alloc() = _VSTD::move(__x.__alloc());} 454227825Stheraven 455227825Stheraven _LIBCPP_INLINE_VISIBILITY 456227825Stheraven static void __swap_alloc(__node_allocator& __x, __node_allocator& __y) 457227825Stheraven _NOEXCEPT_(!__node_traits::propagate_on_container_swap::value || 458227825Stheraven __is_nothrow_swappable<__node_allocator>::value) 459227825Stheraven {__swap_alloc(__x, __y, integral_constant<bool, 460227825Stheraven __node_traits::propagate_on_container_swap::value>());} 461227825Stheraven _LIBCPP_INLINE_VISIBILITY 462227825Stheraven static void __swap_alloc(__node_allocator& __x, __node_allocator& __y, 463227825Stheraven false_type) 464227825Stheraven _NOEXCEPT 465227825Stheraven {} 466227825Stheraven _LIBCPP_INLINE_VISIBILITY 467227825Stheraven static void __swap_alloc(__node_allocator& __x, __node_allocator& __y, 468227825Stheraven true_type) 469227825Stheraven _NOEXCEPT_(__is_nothrow_swappable<__node_allocator>::value) 470227825Stheraven { 471227825Stheraven using _VSTD::swap; 472227825Stheraven swap(__x, __y); 473227825Stheraven } 474227825Stheraven}; 475227825Stheraven 476227825Stheraven#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 477227825Stheraven 478227825Stheraventemplate <class _Tp, class _Alloc> 479227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 480227825Stheraven__forward_list_base<_Tp, _Alloc>::__forward_list_base(__forward_list_base&& __x) 481227825Stheraven _NOEXCEPT_(is_nothrow_move_constructible<__node_allocator>::value) 482227825Stheraven : __before_begin_(_VSTD::move(__x.__before_begin_)) 483227825Stheraven{ 484227825Stheraven __x.__before_begin()->__next_ = nullptr; 485227825Stheraven} 486227825Stheraven 487227825Stheraventemplate <class _Tp, class _Alloc> 488227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 489227825Stheraven__forward_list_base<_Tp, _Alloc>::__forward_list_base(__forward_list_base&& __x, 490227825Stheraven const allocator_type& __a) 491227825Stheraven : __before_begin_(__begin_node(), __node_allocator(__a)) 492227825Stheraven{ 493227825Stheraven if (__alloc() == __x.__alloc()) 494227825Stheraven { 495227825Stheraven __before_begin()->__next_ = __x.__before_begin()->__next_; 496227825Stheraven __x.__before_begin()->__next_ = nullptr; 497227825Stheraven } 498227825Stheraven} 499227825Stheraven 500227825Stheraven#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 501227825Stheraven 502227825Stheraventemplate <class _Tp, class _Alloc> 503227825Stheraven__forward_list_base<_Tp, _Alloc>::~__forward_list_base() 504227825Stheraven{ 505227825Stheraven clear(); 506227825Stheraven} 507227825Stheraven 508227825Stheraventemplate <class _Tp, class _Alloc> 509227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 510227825Stheravenvoid 511227825Stheraven__forward_list_base<_Tp, _Alloc>::swap(__forward_list_base& __x) 512227825Stheraven _NOEXCEPT_(!__node_traits::propagate_on_container_swap::value || 513227825Stheraven __is_nothrow_swappable<__node_allocator>::value) 514227825Stheraven{ 515227825Stheraven __swap_alloc(__alloc(), __x.__alloc()); 516227825Stheraven using _VSTD::swap; 517227825Stheraven swap(__before_begin()->__next_, __x.__before_begin()->__next_); 518227825Stheraven} 519227825Stheraven 520227825Stheraventemplate <class _Tp, class _Alloc> 521227825Stheravenvoid 522227825Stheraven__forward_list_base<_Tp, _Alloc>::clear() _NOEXCEPT 523227825Stheraven{ 524227825Stheraven __node_allocator& __a = __alloc(); 525227825Stheraven for (__node_pointer __p = __before_begin()->__next_; __p != nullptr;) 526227825Stheraven { 527227825Stheraven __node_pointer __next = __p->__next_; 528227825Stheraven __node_traits::destroy(__a, _VSTD::addressof(__p->__value_)); 529227825Stheraven __node_traits::deallocate(__a, __p, 1); 530227825Stheraven __p = __next; 531227825Stheraven } 532227825Stheraven __before_begin()->__next_ = nullptr; 533227825Stheraven} 534227825Stheraven 535227825Stheraventemplate <class _Tp, class _Alloc = allocator<_Tp> > 536227825Stheravenclass _LIBCPP_VISIBLE forward_list 537227825Stheraven : private __forward_list_base<_Tp, _Alloc> 538227825Stheraven{ 539227825Stheraven typedef __forward_list_base<_Tp, _Alloc> base; 540227825Stheraven typedef typename base::__node_allocator __node_allocator; 541227825Stheraven typedef typename base::__node __node; 542227825Stheraven typedef typename base::__node_traits __node_traits; 543227825Stheraven typedef typename base::__node_pointer __node_pointer; 544227825Stheraven 545227825Stheravenpublic: 546227825Stheraven typedef _Tp value_type; 547227825Stheraven typedef _Alloc allocator_type; 548227825Stheraven 549227825Stheraven typedef value_type& reference; 550227825Stheraven typedef const value_type& const_reference; 551227825Stheraven typedef typename allocator_traits<allocator_type>::pointer pointer; 552227825Stheraven typedef typename allocator_traits<allocator_type>::const_pointer const_pointer; 553227825Stheraven typedef typename allocator_traits<allocator_type>::size_type size_type; 554227825Stheraven typedef typename allocator_traits<allocator_type>::difference_type difference_type; 555227825Stheraven 556227825Stheraven typedef typename base::iterator iterator; 557227825Stheraven typedef typename base::const_iterator const_iterator; 558227825Stheraven 559227825Stheraven _LIBCPP_INLINE_VISIBILITY 560227825Stheraven forward_list() 561227825Stheraven _NOEXCEPT_(is_nothrow_default_constructible<__node_allocator>::value) 562227825Stheraven {} // = default; 563227825Stheraven explicit forward_list(const allocator_type& __a); 564227825Stheraven explicit forward_list(size_type __n); 565227825Stheraven forward_list(size_type __n, const value_type& __v); 566227825Stheraven forward_list(size_type __n, const value_type& __v, const allocator_type& __a); 567227825Stheraven template <class _InputIterator> 568227825Stheraven forward_list(_InputIterator __f, _InputIterator __l, 569227825Stheraven typename enable_if< 570227825Stheraven __is_input_iterator<_InputIterator>::value 571227825Stheraven >::type* = nullptr); 572227825Stheraven template <class _InputIterator> 573227825Stheraven forward_list(_InputIterator __f, _InputIterator __l, 574227825Stheraven const allocator_type& __a, 575227825Stheraven typename enable_if< 576227825Stheraven __is_input_iterator<_InputIterator>::value 577227825Stheraven >::type* = nullptr); 578227825Stheraven forward_list(const forward_list& __x); 579227825Stheraven forward_list(const forward_list& __x, const allocator_type& __a); 580227825Stheraven#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 581227825Stheraven _LIBCPP_INLINE_VISIBILITY 582227825Stheraven forward_list(forward_list&& __x) 583227825Stheraven _NOEXCEPT_(is_nothrow_move_constructible<base>::value) 584227825Stheraven : base(_VSTD::move(__x)) {} 585227825Stheraven forward_list(forward_list&& __x, const allocator_type& __a); 586227825Stheraven#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 587227825Stheraven#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 588227825Stheraven forward_list(initializer_list<value_type> __il); 589227825Stheraven forward_list(initializer_list<value_type> __il, const allocator_type& __a); 590227825Stheraven#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 591227825Stheraven 592227825Stheraven // ~forward_list() = default; 593227825Stheraven 594227825Stheraven forward_list& operator=(const forward_list& __x); 595227825Stheraven#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 596227825Stheraven forward_list& operator=(forward_list&& __x) 597227825Stheraven _NOEXCEPT_( 598227825Stheraven __node_traits::propagate_on_container_move_assignment::value && 599227825Stheraven is_nothrow_move_assignable<allocator_type>::value); 600227825Stheraven#endif 601227825Stheraven#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 602227825Stheraven forward_list& operator=(initializer_list<value_type> __il); 603227825Stheraven#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 604227825Stheraven 605227825Stheraven template <class _InputIterator> 606227825Stheraven typename enable_if 607227825Stheraven < 608227825Stheraven __is_input_iterator<_InputIterator>::value, 609227825Stheraven void 610227825Stheraven >::type 611227825Stheraven assign(_InputIterator __f, _InputIterator __l); 612227825Stheraven void assign(size_type __n, const value_type& __v); 613227825Stheraven#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 614227825Stheraven void assign(initializer_list<value_type> __il); 615227825Stheraven#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 616227825Stheraven 617227825Stheraven _LIBCPP_INLINE_VISIBILITY 618227825Stheraven allocator_type get_allocator() const _NOEXCEPT 619227825Stheraven {return allocator_type(base::__alloc());} 620227825Stheraven 621227825Stheraven _LIBCPP_INLINE_VISIBILITY 622227825Stheraven iterator begin() _NOEXCEPT 623227825Stheraven {return iterator(base::__before_begin()->__next_);} 624227825Stheraven _LIBCPP_INLINE_VISIBILITY 625227825Stheraven const_iterator begin() const _NOEXCEPT 626227825Stheraven {return const_iterator(base::__before_begin()->__next_);} 627227825Stheraven _LIBCPP_INLINE_VISIBILITY 628227825Stheraven iterator end() _NOEXCEPT 629227825Stheraven {return iterator(nullptr);} 630227825Stheraven _LIBCPP_INLINE_VISIBILITY 631227825Stheraven const_iterator end() const _NOEXCEPT 632227825Stheraven {return const_iterator(nullptr);} 633227825Stheraven 634227825Stheraven _LIBCPP_INLINE_VISIBILITY 635227825Stheraven const_iterator cbegin() const _NOEXCEPT 636227825Stheraven {return const_iterator(base::__before_begin()->__next_);} 637227825Stheraven _LIBCPP_INLINE_VISIBILITY 638227825Stheraven const_iterator cend() const _NOEXCEPT 639227825Stheraven {return const_iterator(nullptr);} 640227825Stheraven 641227825Stheraven _LIBCPP_INLINE_VISIBILITY 642227825Stheraven iterator before_begin() _NOEXCEPT 643227825Stheraven {return iterator(base::__before_begin());} 644227825Stheraven _LIBCPP_INLINE_VISIBILITY 645227825Stheraven const_iterator before_begin() const _NOEXCEPT 646227825Stheraven {return const_iterator(base::__before_begin());} 647227825Stheraven _LIBCPP_INLINE_VISIBILITY 648227825Stheraven const_iterator cbefore_begin() const _NOEXCEPT 649227825Stheraven {return const_iterator(base::__before_begin());} 650227825Stheraven 651227825Stheraven _LIBCPP_INLINE_VISIBILITY 652227825Stheraven bool empty() const _NOEXCEPT 653227825Stheraven {return base::__before_begin()->__next_ == nullptr;} 654227825Stheraven _LIBCPP_INLINE_VISIBILITY 655227825Stheraven size_type max_size() const _NOEXCEPT 656227825Stheraven {return numeric_limits<size_type>::max();} 657227825Stheraven 658227825Stheraven _LIBCPP_INLINE_VISIBILITY 659227825Stheraven reference front() {return base::__before_begin()->__next_->__value_;} 660227825Stheraven _LIBCPP_INLINE_VISIBILITY 661227825Stheraven const_reference front() const {return base::__before_begin()->__next_->__value_;} 662227825Stheraven 663227825Stheraven#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 664227825Stheraven#ifndef _LIBCPP_HAS_NO_VARIADICS 665227825Stheraven template <class... _Args> void emplace_front(_Args&&... __args); 666227825Stheraven#endif 667227825Stheraven void push_front(value_type&& __v); 668227825Stheraven#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 669227825Stheraven void push_front(const value_type& __v); 670227825Stheraven 671227825Stheraven void pop_front(); 672227825Stheraven 673227825Stheraven#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 674227825Stheraven#ifndef _LIBCPP_HAS_NO_VARIADICS 675227825Stheraven template <class... _Args> 676227825Stheraven iterator emplace_after(const_iterator __p, _Args&&... __args); 677227825Stheraven#endif // _LIBCPP_HAS_NO_VARIADICS 678227825Stheraven iterator insert_after(const_iterator __p, value_type&& __v); 679227825Stheraven#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 680227825Stheraven iterator insert_after(const_iterator __p, const value_type& __v); 681227825Stheraven iterator insert_after(const_iterator __p, size_type __n, const value_type& __v); 682227825Stheraven template <class _InputIterator> 683227825Stheraven _LIBCPP_INLINE_VISIBILITY 684227825Stheraven typename enable_if 685227825Stheraven < 686227825Stheraven __is_input_iterator<_InputIterator>::value, 687227825Stheraven iterator 688227825Stheraven >::type 689227825Stheraven insert_after(const_iterator __p, _InputIterator __f, _InputIterator __l); 690227825Stheraven#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 691227825Stheraven iterator insert_after(const_iterator __p, initializer_list<value_type> __il) 692227825Stheraven {return insert_after(__p, __il.begin(), __il.end());} 693227825Stheraven#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 694227825Stheraven 695227825Stheraven iterator erase_after(const_iterator __p); 696227825Stheraven iterator erase_after(const_iterator __f, const_iterator __l); 697227825Stheraven 698227825Stheraven _LIBCPP_INLINE_VISIBILITY 699227825Stheraven void swap(forward_list& __x) 700227825Stheraven _NOEXCEPT_(!__node_traits::propagate_on_container_swap::value || 701227825Stheraven __is_nothrow_swappable<__node_allocator>::value) 702227825Stheraven {base::swap(__x);} 703227825Stheraven 704227825Stheraven void resize(size_type __n); 705227825Stheraven void resize(size_type __n, const value_type& __v); 706227825Stheraven _LIBCPP_INLINE_VISIBILITY 707227825Stheraven void clear() _NOEXCEPT {base::clear();} 708227825Stheraven 709227825Stheraven#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 710227825Stheraven _LIBCPP_INLINE_VISIBILITY 711227825Stheraven void splice_after(const_iterator __p, forward_list&& __x); 712227825Stheraven _LIBCPP_INLINE_VISIBILITY 713227825Stheraven void splice_after(const_iterator __p, forward_list&& __x, const_iterator __i); 714227825Stheraven _LIBCPP_INLINE_VISIBILITY 715227825Stheraven void splice_after(const_iterator __p, forward_list&& __x, 716227825Stheraven const_iterator __f, const_iterator __l); 717227825Stheraven#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 718227825Stheraven void splice_after(const_iterator __p, forward_list& __x); 719227825Stheraven void splice_after(const_iterator __p, forward_list& __x, const_iterator __i); 720227825Stheraven void splice_after(const_iterator __p, forward_list& __x, 721227825Stheraven const_iterator __f, const_iterator __l); 722227825Stheraven void remove(const value_type& __v); 723227825Stheraven template <class _Predicate> void remove_if(_Predicate __pred); 724227825Stheraven _LIBCPP_INLINE_VISIBILITY 725227825Stheraven void unique() {unique(__equal_to<value_type>());} 726227825Stheraven template <class _BinaryPredicate> void unique(_BinaryPredicate __binary_pred); 727227825Stheraven#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 728227825Stheraven _LIBCPP_INLINE_VISIBILITY 729227825Stheraven void merge(forward_list&& __x) {merge(__x, __less<value_type>());} 730227825Stheraven template <class _Compare> 731227825Stheraven _LIBCPP_INLINE_VISIBILITY 732227825Stheraven void merge(forward_list&& __x, _Compare __comp) 733227825Stheraven {merge(__x, _VSTD::move(__comp));} 734227825Stheraven#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 735227825Stheraven _LIBCPP_INLINE_VISIBILITY 736227825Stheraven void merge(forward_list& __x) {merge(__x, __less<value_type>());} 737227825Stheraven template <class _Compare> void merge(forward_list& __x, _Compare __comp); 738227825Stheraven _LIBCPP_INLINE_VISIBILITY 739227825Stheraven void sort() {sort(__less<value_type>());} 740227825Stheraven template <class _Compare> void sort(_Compare __comp); 741227825Stheraven void reverse() _NOEXCEPT; 742227825Stheraven 743227825Stheravenprivate: 744227825Stheraven 745227825Stheraven#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 746227825Stheraven void __move_assign(forward_list& __x, true_type) 747227825Stheraven _NOEXCEPT_(is_nothrow_move_assignable<allocator_type>::value); 748227825Stheraven void __move_assign(forward_list& __x, false_type); 749227825Stheraven#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 750227825Stheraven 751227825Stheraven template <class _Compare> 752227825Stheraven static 753227825Stheraven __node_pointer 754227825Stheraven __merge(__node_pointer __f1, __node_pointer __f2, _Compare& __comp); 755227825Stheraven 756227825Stheraven template <class _Compare> 757227825Stheraven static 758227825Stheraven __node_pointer 759227825Stheraven __sort(__node_pointer __f, difference_type __sz, _Compare& __comp); 760227825Stheraven}; 761227825Stheraven 762227825Stheraventemplate <class _Tp, class _Alloc> 763227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 764227825Stheravenforward_list<_Tp, _Alloc>::forward_list(const allocator_type& __a) 765227825Stheraven : base(__a) 766227825Stheraven{ 767227825Stheraven} 768227825Stheraven 769227825Stheraventemplate <class _Tp, class _Alloc> 770227825Stheravenforward_list<_Tp, _Alloc>::forward_list(size_type __n) 771227825Stheraven{ 772227825Stheraven if (__n > 0) 773227825Stheraven { 774227825Stheraven __node_allocator& __a = base::__alloc(); 775232950Stheraven typedef __allocator_destructor<__node_allocator> _Dp; 776232950Stheraven unique_ptr<__node, _Dp> __h(nullptr, _Dp(__a, 1)); 777227825Stheraven for (__node_pointer __p = base::__before_begin(); __n > 0; --__n, 778227825Stheraven __p = __p->__next_) 779227825Stheraven { 780227825Stheraven __h.reset(__node_traits::allocate(__a, 1)); 781227825Stheraven __node_traits::construct(__a, _VSTD::addressof(__h->__value_)); 782227825Stheraven __h->__next_ = nullptr; 783227825Stheraven __p->__next_ = __h.release(); 784227825Stheraven } 785227825Stheraven } 786227825Stheraven} 787227825Stheraven 788227825Stheraventemplate <class _Tp, class _Alloc> 789227825Stheravenforward_list<_Tp, _Alloc>::forward_list(size_type __n, const value_type& __v) 790227825Stheraven{ 791227825Stheraven insert_after(cbefore_begin(), __n, __v); 792227825Stheraven} 793227825Stheraven 794227825Stheraventemplate <class _Tp, class _Alloc> 795227825Stheravenforward_list<_Tp, _Alloc>::forward_list(size_type __n, const value_type& __v, 796227825Stheraven const allocator_type& __a) 797227825Stheraven : base(__a) 798227825Stheraven{ 799227825Stheraven insert_after(cbefore_begin(), __n, __v); 800227825Stheraven} 801227825Stheraven 802227825Stheraventemplate <class _Tp, class _Alloc> 803227825Stheraventemplate <class _InputIterator> 804227825Stheravenforward_list<_Tp, _Alloc>::forward_list(_InputIterator __f, _InputIterator __l, 805227825Stheraven typename enable_if< 806227825Stheraven __is_input_iterator<_InputIterator>::value 807227825Stheraven >::type*) 808227825Stheraven{ 809227825Stheraven insert_after(cbefore_begin(), __f, __l); 810227825Stheraven} 811227825Stheraven 812227825Stheraventemplate <class _Tp, class _Alloc> 813227825Stheraventemplate <class _InputIterator> 814227825Stheravenforward_list<_Tp, _Alloc>::forward_list(_InputIterator __f, _InputIterator __l, 815227825Stheraven const allocator_type& __a, 816227825Stheraven typename enable_if< 817227825Stheraven __is_input_iterator<_InputIterator>::value 818227825Stheraven >::type*) 819227825Stheraven : base(__a) 820227825Stheraven{ 821227825Stheraven insert_after(cbefore_begin(), __f, __l); 822227825Stheraven} 823227825Stheraven 824227825Stheraventemplate <class _Tp, class _Alloc> 825227825Stheravenforward_list<_Tp, _Alloc>::forward_list(const forward_list& __x) 826227825Stheraven : base(allocator_type( 827227825Stheraven __node_traits::select_on_container_copy_construction(__x.__alloc()) 828227825Stheraven ) 829227825Stheraven ) 830227825Stheraven{ 831227825Stheraven insert_after(cbefore_begin(), __x.begin(), __x.end()); 832227825Stheraven} 833227825Stheraven 834227825Stheraventemplate <class _Tp, class _Alloc> 835227825Stheravenforward_list<_Tp, _Alloc>::forward_list(const forward_list& __x, 836227825Stheraven const allocator_type& __a) 837227825Stheraven : base(__a) 838227825Stheraven{ 839227825Stheraven insert_after(cbefore_begin(), __x.begin(), __x.end()); 840227825Stheraven} 841227825Stheraven 842227825Stheraven#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 843227825Stheraven 844227825Stheraventemplate <class _Tp, class _Alloc> 845227825Stheravenforward_list<_Tp, _Alloc>::forward_list(forward_list&& __x, 846227825Stheraven const allocator_type& __a) 847227825Stheraven : base(_VSTD::move(__x), __a) 848227825Stheraven{ 849227825Stheraven if (base::__alloc() != __x.__alloc()) 850227825Stheraven { 851232950Stheraven typedef move_iterator<iterator> _Ip; 852232950Stheraven insert_after(cbefore_begin(), _Ip(__x.begin()), _Ip(__x.end())); 853227825Stheraven } 854227825Stheraven} 855227825Stheraven 856227825Stheraven#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 857227825Stheraven 858227825Stheraven#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 859227825Stheraven 860227825Stheraventemplate <class _Tp, class _Alloc> 861227825Stheravenforward_list<_Tp, _Alloc>::forward_list(initializer_list<value_type> __il) 862227825Stheraven{ 863227825Stheraven insert_after(cbefore_begin(), __il.begin(), __il.end()); 864227825Stheraven} 865227825Stheraven 866227825Stheraventemplate <class _Tp, class _Alloc> 867227825Stheravenforward_list<_Tp, _Alloc>::forward_list(initializer_list<value_type> __il, 868227825Stheraven const allocator_type& __a) 869227825Stheraven : base(__a) 870227825Stheraven{ 871227825Stheraven insert_after(cbefore_begin(), __il.begin(), __il.end()); 872227825Stheraven} 873227825Stheraven 874227825Stheraven#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 875227825Stheraven 876227825Stheraventemplate <class _Tp, class _Alloc> 877227825Stheravenforward_list<_Tp, _Alloc>& 878227825Stheravenforward_list<_Tp, _Alloc>::operator=(const forward_list& __x) 879227825Stheraven{ 880227825Stheraven if (this != &__x) 881227825Stheraven { 882227825Stheraven base::__copy_assign_alloc(__x); 883227825Stheraven assign(__x.begin(), __x.end()); 884227825Stheraven } 885227825Stheraven return *this; 886227825Stheraven} 887227825Stheraven 888227825Stheraven#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 889227825Stheraven 890227825Stheraventemplate <class _Tp, class _Alloc> 891227825Stheravenvoid 892227825Stheravenforward_list<_Tp, _Alloc>::__move_assign(forward_list& __x, true_type) 893227825Stheraven _NOEXCEPT_(is_nothrow_move_assignable<allocator_type>::value) 894227825Stheraven{ 895227825Stheraven clear(); 896227825Stheraven base::__move_assign_alloc(__x); 897227825Stheraven base::__before_begin()->__next_ = __x.__before_begin()->__next_; 898227825Stheraven __x.__before_begin()->__next_ = nullptr; 899227825Stheraven} 900227825Stheraven 901227825Stheraventemplate <class _Tp, class _Alloc> 902227825Stheravenvoid 903227825Stheravenforward_list<_Tp, _Alloc>::__move_assign(forward_list& __x, false_type) 904227825Stheraven{ 905227825Stheraven if (base::__alloc() == __x.__alloc()) 906227825Stheraven __move_assign(__x, true_type()); 907227825Stheraven else 908227825Stheraven { 909232950Stheraven typedef move_iterator<iterator> _Ip; 910232950Stheraven assign(_Ip(__x.begin()), _Ip(__x.end())); 911227825Stheraven } 912227825Stheraven} 913227825Stheraven 914227825Stheraventemplate <class _Tp, class _Alloc> 915227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 916227825Stheravenforward_list<_Tp, _Alloc>& 917227825Stheravenforward_list<_Tp, _Alloc>::operator=(forward_list&& __x) 918227825Stheraven _NOEXCEPT_( 919227825Stheraven __node_traits::propagate_on_container_move_assignment::value && 920227825Stheraven is_nothrow_move_assignable<allocator_type>::value) 921227825Stheraven{ 922227825Stheraven __move_assign(__x, integral_constant<bool, 923227825Stheraven __node_traits::propagate_on_container_move_assignment::value>()); 924227825Stheraven return *this; 925227825Stheraven} 926227825Stheraven 927227825Stheraven#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 928227825Stheraven 929227825Stheraven#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 930227825Stheraven 931227825Stheraventemplate <class _Tp, class _Alloc> 932227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 933227825Stheravenforward_list<_Tp, _Alloc>& 934227825Stheravenforward_list<_Tp, _Alloc>::operator=(initializer_list<value_type> __il) 935227825Stheraven{ 936227825Stheraven assign(__il.begin(), __il.end()); 937227825Stheraven return *this; 938227825Stheraven} 939227825Stheraven 940227825Stheraven#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 941227825Stheraven 942227825Stheraventemplate <class _Tp, class _Alloc> 943227825Stheraventemplate <class _InputIterator> 944227825Stheraventypename enable_if 945227825Stheraven< 946227825Stheraven __is_input_iterator<_InputIterator>::value, 947227825Stheraven void 948227825Stheraven>::type 949227825Stheravenforward_list<_Tp, _Alloc>::assign(_InputIterator __f, _InputIterator __l) 950227825Stheraven{ 951227825Stheraven iterator __i = before_begin(); 952227825Stheraven iterator __j = _VSTD::next(__i); 953227825Stheraven iterator __e = end(); 954227825Stheraven for (; __j != __e && __f != __l; ++__i, ++__j, ++__f) 955227825Stheraven *__j = *__f; 956227825Stheraven if (__j == __e) 957227825Stheraven insert_after(__i, __f, __l); 958227825Stheraven else 959227825Stheraven erase_after(__i, __e); 960227825Stheraven} 961227825Stheraven 962227825Stheraventemplate <class _Tp, class _Alloc> 963227825Stheravenvoid 964227825Stheravenforward_list<_Tp, _Alloc>::assign(size_type __n, const value_type& __v) 965227825Stheraven{ 966227825Stheraven iterator __i = before_begin(); 967227825Stheraven iterator __j = _VSTD::next(__i); 968227825Stheraven iterator __e = end(); 969227825Stheraven for (; __j != __e && __n > 0; --__n, ++__i, ++__j) 970227825Stheraven *__j = __v; 971227825Stheraven if (__j == __e) 972227825Stheraven insert_after(__i, __n, __v); 973227825Stheraven else 974227825Stheraven erase_after(__i, __e); 975227825Stheraven} 976227825Stheraven 977227825Stheraven#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 978227825Stheraven 979227825Stheraventemplate <class _Tp, class _Alloc> 980227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 981227825Stheravenvoid 982227825Stheravenforward_list<_Tp, _Alloc>::assign(initializer_list<value_type> __il) 983227825Stheraven{ 984227825Stheraven assign(__il.begin(), __il.end()); 985227825Stheraven} 986227825Stheraven 987227825Stheraven#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 988227825Stheraven 989227825Stheraven#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 990227825Stheraven#ifndef _LIBCPP_HAS_NO_VARIADICS 991227825Stheraven 992227825Stheraventemplate <class _Tp, class _Alloc> 993227825Stheraventemplate <class... _Args> 994227825Stheravenvoid 995227825Stheravenforward_list<_Tp, _Alloc>::emplace_front(_Args&&... __args) 996227825Stheraven{ 997227825Stheraven __node_allocator& __a = base::__alloc(); 998232950Stheraven typedef __allocator_destructor<__node_allocator> _Dp; 999232950Stheraven unique_ptr<__node, _Dp> __h(__node_traits::allocate(__a, 1), _Dp(__a, 1)); 1000227825Stheraven __node_traits::construct(__a, _VSTD::addressof(__h->__value_), 1001227825Stheraven _VSTD::forward<_Args>(__args)...); 1002227825Stheraven __h->__next_ = base::__before_begin()->__next_; 1003227825Stheraven base::__before_begin()->__next_ = __h.release(); 1004227825Stheraven} 1005227825Stheraven 1006227825Stheraven#endif // _LIBCPP_HAS_NO_VARIADICS 1007227825Stheraven 1008227825Stheraventemplate <class _Tp, class _Alloc> 1009227825Stheravenvoid 1010227825Stheravenforward_list<_Tp, _Alloc>::push_front(value_type&& __v) 1011227825Stheraven{ 1012227825Stheraven __node_allocator& __a = base::__alloc(); 1013232950Stheraven typedef __allocator_destructor<__node_allocator> _Dp; 1014232950Stheraven unique_ptr<__node, _Dp> __h(__node_traits::allocate(__a, 1), _Dp(__a, 1)); 1015227825Stheraven __node_traits::construct(__a, _VSTD::addressof(__h->__value_), _VSTD::move(__v)); 1016227825Stheraven __h->__next_ = base::__before_begin()->__next_; 1017227825Stheraven base::__before_begin()->__next_ = __h.release(); 1018227825Stheraven} 1019227825Stheraven 1020227825Stheraven#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 1021227825Stheraven 1022227825Stheraventemplate <class _Tp, class _Alloc> 1023227825Stheravenvoid 1024227825Stheravenforward_list<_Tp, _Alloc>::push_front(const value_type& __v) 1025227825Stheraven{ 1026227825Stheraven __node_allocator& __a = base::__alloc(); 1027232950Stheraven typedef __allocator_destructor<__node_allocator> _Dp; 1028232950Stheraven unique_ptr<__node, _Dp> __h(__node_traits::allocate(__a, 1), _Dp(__a, 1)); 1029227825Stheraven __node_traits::construct(__a, _VSTD::addressof(__h->__value_), __v); 1030227825Stheraven __h->__next_ = base::__before_begin()->__next_; 1031227825Stheraven base::__before_begin()->__next_ = __h.release(); 1032227825Stheraven} 1033227825Stheraven 1034227825Stheraventemplate <class _Tp, class _Alloc> 1035227825Stheravenvoid 1036227825Stheravenforward_list<_Tp, _Alloc>::pop_front() 1037227825Stheraven{ 1038227825Stheraven __node_allocator& __a = base::__alloc(); 1039227825Stheraven __node_pointer __p = base::__before_begin()->__next_; 1040227825Stheraven base::__before_begin()->__next_ = __p->__next_; 1041227825Stheraven __node_traits::destroy(__a, _VSTD::addressof(__p->__value_)); 1042227825Stheraven __node_traits::deallocate(__a, __p, 1); 1043227825Stheraven} 1044227825Stheraven 1045227825Stheraven#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 1046227825Stheraven#ifndef _LIBCPP_HAS_NO_VARIADICS 1047227825Stheraven 1048227825Stheraventemplate <class _Tp, class _Alloc> 1049227825Stheraventemplate <class... _Args> 1050227825Stheraventypename forward_list<_Tp, _Alloc>::iterator 1051227825Stheravenforward_list<_Tp, _Alloc>::emplace_after(const_iterator __p, _Args&&... __args) 1052227825Stheraven{ 1053227825Stheraven __node_pointer const __r = const_cast<__node_pointer>(__p.__ptr_); 1054227825Stheraven __node_allocator& __a = base::__alloc(); 1055232950Stheraven typedef __allocator_destructor<__node_allocator> _Dp; 1056232950Stheraven unique_ptr<__node, _Dp> __h(__node_traits::allocate(__a, 1), _Dp(__a, 1)); 1057227825Stheraven __node_traits::construct(__a, _VSTD::addressof(__h->__value_), 1058227825Stheraven _VSTD::forward<_Args>(__args)...); 1059227825Stheraven __h->__next_ = __r->__next_; 1060227825Stheraven __r->__next_ = __h.release(); 1061227825Stheraven return iterator(__r->__next_); 1062227825Stheraven} 1063227825Stheraven 1064227825Stheraven#endif // _LIBCPP_HAS_NO_VARIADICS 1065227825Stheraven 1066227825Stheraventemplate <class _Tp, class _Alloc> 1067227825Stheraventypename forward_list<_Tp, _Alloc>::iterator 1068227825Stheravenforward_list<_Tp, _Alloc>::insert_after(const_iterator __p, value_type&& __v) 1069227825Stheraven{ 1070227825Stheraven __node_pointer const __r = const_cast<__node_pointer>(__p.__ptr_); 1071227825Stheraven __node_allocator& __a = base::__alloc(); 1072232950Stheraven typedef __allocator_destructor<__node_allocator> _Dp; 1073232950Stheraven unique_ptr<__node, _Dp> __h(__node_traits::allocate(__a, 1), _Dp(__a, 1)); 1074227825Stheraven __node_traits::construct(__a, _VSTD::addressof(__h->__value_), _VSTD::move(__v)); 1075227825Stheraven __h->__next_ = __r->__next_; 1076227825Stheraven __r->__next_ = __h.release(); 1077227825Stheraven return iterator(__r->__next_); 1078227825Stheraven} 1079227825Stheraven 1080227825Stheraven#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 1081227825Stheraven 1082227825Stheraventemplate <class _Tp, class _Alloc> 1083227825Stheraventypename forward_list<_Tp, _Alloc>::iterator 1084227825Stheravenforward_list<_Tp, _Alloc>::insert_after(const_iterator __p, const value_type& __v) 1085227825Stheraven{ 1086227825Stheraven __node_pointer const __r = const_cast<__node_pointer>(__p.__ptr_); 1087227825Stheraven __node_allocator& __a = base::__alloc(); 1088232950Stheraven typedef __allocator_destructor<__node_allocator> _Dp; 1089232950Stheraven unique_ptr<__node, _Dp> __h(__node_traits::allocate(__a, 1), _Dp(__a, 1)); 1090227825Stheraven __node_traits::construct(__a, _VSTD::addressof(__h->__value_), __v); 1091227825Stheraven __h->__next_ = __r->__next_; 1092227825Stheraven __r->__next_ = __h.release(); 1093227825Stheraven return iterator(__r->__next_); 1094227825Stheraven} 1095227825Stheraven 1096227825Stheraventemplate <class _Tp, class _Alloc> 1097227825Stheraventypename forward_list<_Tp, _Alloc>::iterator 1098227825Stheravenforward_list<_Tp, _Alloc>::insert_after(const_iterator __p, size_type __n, 1099227825Stheraven const value_type& __v) 1100227825Stheraven{ 1101227825Stheraven __node_pointer __r = const_cast<__node_pointer>(__p.__ptr_); 1102227825Stheraven if (__n > 0) 1103227825Stheraven { 1104227825Stheraven __node_allocator& __a = base::__alloc(); 1105232950Stheraven typedef __allocator_destructor<__node_allocator> _Dp; 1106232950Stheraven unique_ptr<__node, _Dp> __h(__node_traits::allocate(__a, 1), _Dp(__a, 1)); 1107227825Stheraven __node_traits::construct(__a, _VSTD::addressof(__h->__value_), __v); 1108227825Stheraven __node_pointer __first = __h.release(); 1109227825Stheraven __node_pointer __last = __first; 1110227825Stheraven#ifndef _LIBCPP_NO_EXCEPTIONS 1111227825Stheraven try 1112227825Stheraven { 1113227825Stheraven#endif // _LIBCPP_NO_EXCEPTIONS 1114227825Stheraven for (--__n; __n != 0; --__n, __last = __last->__next_) 1115227825Stheraven { 1116227825Stheraven __h.reset(__node_traits::allocate(__a, 1)); 1117227825Stheraven __node_traits::construct(__a, _VSTD::addressof(__h->__value_), __v); 1118227825Stheraven __last->__next_ = __h.release(); 1119227825Stheraven } 1120227825Stheraven#ifndef _LIBCPP_NO_EXCEPTIONS 1121227825Stheraven } 1122227825Stheraven catch (...) 1123227825Stheraven { 1124227825Stheraven while (__first != nullptr) 1125227825Stheraven { 1126227825Stheraven __node_pointer __next = __first->__next_; 1127227825Stheraven __node_traits::destroy(__a, _VSTD::addressof(__first->__value_)); 1128227825Stheraven __node_traits::deallocate(__a, __first, 1); 1129227825Stheraven __first = __next; 1130227825Stheraven } 1131227825Stheraven throw; 1132227825Stheraven } 1133227825Stheraven#endif // _LIBCPP_NO_EXCEPTIONS 1134227825Stheraven __last->__next_ = __r->__next_; 1135227825Stheraven __r->__next_ = __first; 1136227825Stheraven __r = __last; 1137227825Stheraven } 1138227825Stheraven return iterator(__r); 1139227825Stheraven} 1140227825Stheraven 1141227825Stheraventemplate <class _Tp, class _Alloc> 1142227825Stheraventemplate <class _InputIterator> 1143227825Stheraventypename enable_if 1144227825Stheraven< 1145227825Stheraven __is_input_iterator<_InputIterator>::value, 1146227825Stheraven typename forward_list<_Tp, _Alloc>::iterator 1147227825Stheraven>::type 1148227825Stheravenforward_list<_Tp, _Alloc>::insert_after(const_iterator __p, 1149227825Stheraven _InputIterator __f, _InputIterator __l) 1150227825Stheraven{ 1151227825Stheraven __node_pointer __r = const_cast<__node_pointer>(__p.__ptr_); 1152227825Stheraven if (__f != __l) 1153227825Stheraven { 1154227825Stheraven __node_allocator& __a = base::__alloc(); 1155232950Stheraven typedef __allocator_destructor<__node_allocator> _Dp; 1156232950Stheraven unique_ptr<__node, _Dp> __h(__node_traits::allocate(__a, 1), _Dp(__a, 1)); 1157227825Stheraven __node_traits::construct(__a, _VSTD::addressof(__h->__value_), *__f); 1158227825Stheraven __node_pointer __first = __h.release(); 1159227825Stheraven __node_pointer __last = __first; 1160227825Stheraven#ifndef _LIBCPP_NO_EXCEPTIONS 1161227825Stheraven try 1162227825Stheraven { 1163227825Stheraven#endif // _LIBCPP_NO_EXCEPTIONS 1164227825Stheraven for (++__f; __f != __l; ++__f, __last = __last->__next_) 1165227825Stheraven { 1166227825Stheraven __h.reset(__node_traits::allocate(__a, 1)); 1167227825Stheraven __node_traits::construct(__a, _VSTD::addressof(__h->__value_), *__f); 1168227825Stheraven __last->__next_ = __h.release(); 1169227825Stheraven } 1170227825Stheraven#ifndef _LIBCPP_NO_EXCEPTIONS 1171227825Stheraven } 1172227825Stheraven catch (...) 1173227825Stheraven { 1174227825Stheraven while (__first != nullptr) 1175227825Stheraven { 1176227825Stheraven __node_pointer __next = __first->__next_; 1177227825Stheraven __node_traits::destroy(__a, _VSTD::addressof(__first->__value_)); 1178227825Stheraven __node_traits::deallocate(__a, __first, 1); 1179227825Stheraven __first = __next; 1180227825Stheraven } 1181227825Stheraven throw; 1182227825Stheraven } 1183227825Stheraven#endif // _LIBCPP_NO_EXCEPTIONS 1184227825Stheraven __last->__next_ = __r->__next_; 1185227825Stheraven __r->__next_ = __first; 1186227825Stheraven __r = __last; 1187227825Stheraven } 1188227825Stheraven return iterator(__r); 1189227825Stheraven} 1190227825Stheraven 1191227825Stheraventemplate <class _Tp, class _Alloc> 1192227825Stheraventypename forward_list<_Tp, _Alloc>::iterator 1193227825Stheravenforward_list<_Tp, _Alloc>::erase_after(const_iterator __f) 1194227825Stheraven{ 1195227825Stheraven __node_pointer __p = const_cast<__node_pointer>(__f.__ptr_); 1196227825Stheraven __node_pointer __n = __p->__next_; 1197227825Stheraven __p->__next_ = __n->__next_; 1198227825Stheraven __node_allocator& __a = base::__alloc(); 1199227825Stheraven __node_traits::destroy(__a, _VSTD::addressof(__n->__value_)); 1200227825Stheraven __node_traits::deallocate(__a, __n, 1); 1201227825Stheraven return iterator(__p->__next_); 1202227825Stheraven} 1203227825Stheraven 1204227825Stheraventemplate <class _Tp, class _Alloc> 1205227825Stheraventypename forward_list<_Tp, _Alloc>::iterator 1206227825Stheravenforward_list<_Tp, _Alloc>::erase_after(const_iterator __f, const_iterator __l) 1207227825Stheraven{ 1208227825Stheraven __node_pointer __e = const_cast<__node_pointer>(__l.__ptr_); 1209227825Stheraven if (__f != __l) 1210227825Stheraven { 1211227825Stheraven __node_pointer __p = const_cast<__node_pointer>(__f.__ptr_); 1212227825Stheraven __node_pointer __n = __p->__next_; 1213227825Stheraven if (__n != __e) 1214227825Stheraven { 1215227825Stheraven __p->__next_ = __e; 1216227825Stheraven __node_allocator& __a = base::__alloc(); 1217227825Stheraven do 1218227825Stheraven { 1219227825Stheraven __p = __n->__next_; 1220227825Stheraven __node_traits::destroy(__a, _VSTD::addressof(__n->__value_)); 1221227825Stheraven __node_traits::deallocate(__a, __n, 1); 1222227825Stheraven __n = __p; 1223227825Stheraven } while (__n != __e); 1224227825Stheraven } 1225227825Stheraven } 1226227825Stheraven return iterator(__e); 1227227825Stheraven} 1228227825Stheraven 1229227825Stheraventemplate <class _Tp, class _Alloc> 1230227825Stheravenvoid 1231227825Stheravenforward_list<_Tp, _Alloc>::resize(size_type __n) 1232227825Stheraven{ 1233227825Stheraven size_type __sz = 0; 1234227825Stheraven iterator __p = before_begin(); 1235227825Stheraven iterator __i = begin(); 1236227825Stheraven iterator __e = end(); 1237227825Stheraven for (; __i != __e && __sz < __n; ++__p, ++__i, ++__sz) 1238227825Stheraven ; 1239227825Stheraven if (__i != __e) 1240227825Stheraven erase_after(__p, __e); 1241227825Stheraven else 1242227825Stheraven { 1243227825Stheraven __n -= __sz; 1244227825Stheraven if (__n > 0) 1245227825Stheraven { 1246227825Stheraven __node_allocator& __a = base::__alloc(); 1247232950Stheraven typedef __allocator_destructor<__node_allocator> _Dp; 1248232950Stheraven unique_ptr<__node, _Dp> __h(nullptr, _Dp(__a, 1)); 1249227825Stheraven for (__node_pointer __ptr = __p.__ptr_; __n > 0; --__n, 1250227825Stheraven __ptr = __ptr->__next_) 1251227825Stheraven { 1252227825Stheraven __h.reset(__node_traits::allocate(__a, 1)); 1253227825Stheraven __node_traits::construct(__a, _VSTD::addressof(__h->__value_)); 1254227825Stheraven __h->__next_ = nullptr; 1255227825Stheraven __ptr->__next_ = __h.release(); 1256227825Stheraven } 1257227825Stheraven } 1258227825Stheraven } 1259227825Stheraven} 1260227825Stheraven 1261227825Stheraventemplate <class _Tp, class _Alloc> 1262227825Stheravenvoid 1263227825Stheravenforward_list<_Tp, _Alloc>::resize(size_type __n, const value_type& __v) 1264227825Stheraven{ 1265227825Stheraven size_type __sz = 0; 1266227825Stheraven iterator __p = before_begin(); 1267227825Stheraven iterator __i = begin(); 1268227825Stheraven iterator __e = end(); 1269227825Stheraven for (; __i != __e && __sz < __n; ++__p, ++__i, ++__sz) 1270227825Stheraven ; 1271227825Stheraven if (__i != __e) 1272227825Stheraven erase_after(__p, __e); 1273227825Stheraven else 1274227825Stheraven { 1275227825Stheraven __n -= __sz; 1276227825Stheraven if (__n > 0) 1277227825Stheraven { 1278227825Stheraven __node_allocator& __a = base::__alloc(); 1279232950Stheraven typedef __allocator_destructor<__node_allocator> _Dp; 1280232950Stheraven unique_ptr<__node, _Dp> __h(nullptr, _Dp(__a, 1)); 1281227825Stheraven for (__node_pointer __ptr = __p.__ptr_; __n > 0; --__n, 1282227825Stheraven __ptr = __ptr->__next_) 1283227825Stheraven { 1284227825Stheraven __h.reset(__node_traits::allocate(__a, 1)); 1285227825Stheraven __node_traits::construct(__a, _VSTD::addressof(__h->__value_), __v); 1286227825Stheraven __h->__next_ = nullptr; 1287227825Stheraven __ptr->__next_ = __h.release(); 1288227825Stheraven } 1289227825Stheraven } 1290227825Stheraven } 1291227825Stheraven} 1292227825Stheraven 1293227825Stheraventemplate <class _Tp, class _Alloc> 1294227825Stheravenvoid 1295227825Stheravenforward_list<_Tp, _Alloc>::splice_after(const_iterator __p, 1296227825Stheraven forward_list& __x) 1297227825Stheraven{ 1298227825Stheraven if (!__x.empty()) 1299227825Stheraven { 1300227825Stheraven if (__p.__ptr_->__next_ != nullptr) 1301227825Stheraven { 1302227825Stheraven const_iterator __lm1 = __x.before_begin(); 1303227825Stheraven while (__lm1.__ptr_->__next_ != nullptr) 1304227825Stheraven ++__lm1; 1305227825Stheraven const_cast<__node_pointer>(__lm1.__ptr_)->__next_ = 1306227825Stheraven const_cast<__node_pointer>(__p.__ptr_)->__next_; 1307227825Stheraven } 1308227825Stheraven const_cast<__node_pointer>(__p.__ptr_)->__next_ = 1309227825Stheraven const_cast<__node_pointer>(__x.__before_begin())->__next_; 1310227825Stheraven const_cast<__node_pointer>(__x.__before_begin())->__next_ = nullptr; 1311227825Stheraven } 1312227825Stheraven} 1313227825Stheraven 1314227825Stheraventemplate <class _Tp, class _Alloc> 1315227825Stheravenvoid 1316227825Stheravenforward_list<_Tp, _Alloc>::splice_after(const_iterator __p, 1317227825Stheraven forward_list& __x, 1318227825Stheraven const_iterator __i) 1319227825Stheraven{ 1320227825Stheraven const_iterator __lm1 = _VSTD::next(__i); 1321227825Stheraven if (__p != __i && __p != __lm1) 1322227825Stheraven { 1323227825Stheraven const_cast<__node_pointer>(__i.__ptr_)->__next_ = 1324227825Stheraven const_cast<__node_pointer>(__lm1.__ptr_)->__next_; 1325227825Stheraven const_cast<__node_pointer>(__lm1.__ptr_)->__next_ = 1326227825Stheraven const_cast<__node_pointer>(__p.__ptr_)->__next_; 1327227825Stheraven const_cast<__node_pointer>(__p.__ptr_)->__next_ = 1328227825Stheraven const_cast<__node_pointer>(__lm1.__ptr_); 1329227825Stheraven } 1330227825Stheraven} 1331227825Stheraven 1332227825Stheraventemplate <class _Tp, class _Alloc> 1333227825Stheravenvoid 1334227825Stheravenforward_list<_Tp, _Alloc>::splice_after(const_iterator __p, 1335227825Stheraven forward_list& __x, 1336227825Stheraven const_iterator __f, const_iterator __l) 1337227825Stheraven{ 1338227825Stheraven if (__f != __l && __p != __f) 1339227825Stheraven { 1340227825Stheraven const_iterator __lm1 = __f; 1341227825Stheraven while (__lm1.__ptr_->__next_ != __l.__ptr_) 1342227825Stheraven ++__lm1; 1343227825Stheraven if (__f != __lm1) 1344227825Stheraven { 1345227825Stheraven const_cast<__node_pointer>(__lm1.__ptr_)->__next_ = 1346227825Stheraven const_cast<__node_pointer>(__p.__ptr_)->__next_; 1347227825Stheraven const_cast<__node_pointer>(__p.__ptr_)->__next_ = 1348227825Stheraven const_cast<__node_pointer>(__f.__ptr_)->__next_; 1349227825Stheraven const_cast<__node_pointer>(__f.__ptr_)->__next_ = 1350227825Stheraven const_cast<__node_pointer>(__l.__ptr_); 1351227825Stheraven } 1352227825Stheraven } 1353227825Stheraven} 1354227825Stheraven 1355227825Stheraven#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 1356227825Stheraven 1357227825Stheraventemplate <class _Tp, class _Alloc> 1358227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 1359227825Stheravenvoid 1360227825Stheravenforward_list<_Tp, _Alloc>::splice_after(const_iterator __p, 1361227825Stheraven forward_list&& __x) 1362227825Stheraven{ 1363227825Stheraven splice_after(__p, __x); 1364227825Stheraven} 1365227825Stheraven 1366227825Stheraventemplate <class _Tp, class _Alloc> 1367227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 1368227825Stheravenvoid 1369227825Stheravenforward_list<_Tp, _Alloc>::splice_after(const_iterator __p, 1370227825Stheraven forward_list&& __x, 1371227825Stheraven const_iterator __i) 1372227825Stheraven{ 1373227825Stheraven splice_after(__p, __x, __i); 1374227825Stheraven} 1375227825Stheraven 1376227825Stheraventemplate <class _Tp, class _Alloc> 1377227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 1378227825Stheravenvoid 1379227825Stheravenforward_list<_Tp, _Alloc>::splice_after(const_iterator __p, 1380227825Stheraven forward_list&& __x, 1381227825Stheraven const_iterator __f, const_iterator __l) 1382227825Stheraven{ 1383227825Stheraven splice_after(__p, __x, __f, __l); 1384227825Stheraven} 1385227825Stheraven 1386227825Stheraven#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 1387227825Stheraven 1388227825Stheraventemplate <class _Tp, class _Alloc> 1389227825Stheravenvoid 1390227825Stheravenforward_list<_Tp, _Alloc>::remove(const value_type& __v) 1391227825Stheraven{ 1392227825Stheraven iterator __e = end(); 1393227825Stheraven for (iterator __i = before_begin(); __i.__ptr_->__next_ != nullptr;) 1394227825Stheraven { 1395227825Stheraven if (__i.__ptr_->__next_->__value_ == __v) 1396227825Stheraven { 1397227825Stheraven iterator __j = _VSTD::next(__i, 2); 1398227825Stheraven for (; __j != __e && *__j == __v; ++__j) 1399227825Stheraven ; 1400227825Stheraven erase_after(__i, __j); 1401227825Stheraven if (__j == __e) 1402227825Stheraven break; 1403227825Stheraven __i = __j; 1404227825Stheraven } 1405227825Stheraven else 1406227825Stheraven ++__i; 1407227825Stheraven } 1408227825Stheraven} 1409227825Stheraven 1410227825Stheraventemplate <class _Tp, class _Alloc> 1411227825Stheraventemplate <class _Predicate> 1412227825Stheravenvoid 1413227825Stheravenforward_list<_Tp, _Alloc>::remove_if(_Predicate __pred) 1414227825Stheraven{ 1415227825Stheraven iterator __e = end(); 1416227825Stheraven for (iterator __i = before_begin(); __i.__ptr_->__next_ != nullptr;) 1417227825Stheraven { 1418227825Stheraven if (__pred(__i.__ptr_->__next_->__value_)) 1419227825Stheraven { 1420227825Stheraven iterator __j = _VSTD::next(__i, 2); 1421227825Stheraven for (; __j != __e && __pred(*__j); ++__j) 1422227825Stheraven ; 1423227825Stheraven erase_after(__i, __j); 1424227825Stheraven if (__j == __e) 1425227825Stheraven break; 1426227825Stheraven __i = __j; 1427227825Stheraven } 1428227825Stheraven else 1429227825Stheraven ++__i; 1430227825Stheraven } 1431227825Stheraven} 1432227825Stheraven 1433227825Stheraventemplate <class _Tp, class _Alloc> 1434227825Stheraventemplate <class _BinaryPredicate> 1435227825Stheravenvoid 1436227825Stheravenforward_list<_Tp, _Alloc>::unique(_BinaryPredicate __binary_pred) 1437227825Stheraven{ 1438227825Stheraven for (iterator __i = begin(), __e = end(); __i != __e;) 1439227825Stheraven { 1440227825Stheraven iterator __j = _VSTD::next(__i); 1441227825Stheraven for (; __j != __e && __binary_pred(*__i, *__j); ++__j) 1442227825Stheraven ; 1443227825Stheraven if (__i.__ptr_->__next_ != __j.__ptr_) 1444227825Stheraven erase_after(__i, __j); 1445227825Stheraven __i = __j; 1446227825Stheraven } 1447227825Stheraven} 1448227825Stheraven 1449227825Stheraventemplate <class _Tp, class _Alloc> 1450227825Stheraventemplate <class _Compare> 1451227825Stheravenvoid 1452227825Stheravenforward_list<_Tp, _Alloc>::merge(forward_list& __x, _Compare __comp) 1453227825Stheraven{ 1454227825Stheraven if (this != &__x) 1455227825Stheraven { 1456227825Stheraven base::__before_begin()->__next_ = __merge(base::__before_begin()->__next_, 1457227825Stheraven __x.__before_begin()->__next_, 1458227825Stheraven __comp); 1459227825Stheraven __x.__before_begin()->__next_ = nullptr; 1460227825Stheraven } 1461227825Stheraven} 1462227825Stheraven 1463227825Stheraventemplate <class _Tp, class _Alloc> 1464227825Stheraventemplate <class _Compare> 1465227825Stheraventypename forward_list<_Tp, _Alloc>::__node_pointer 1466227825Stheravenforward_list<_Tp, _Alloc>::__merge(__node_pointer __f1, __node_pointer __f2, 1467227825Stheraven _Compare& __comp) 1468227825Stheraven{ 1469227825Stheraven if (__f1 == nullptr) 1470227825Stheraven return __f2; 1471227825Stheraven if (__f2 == nullptr) 1472227825Stheraven return __f1; 1473227825Stheraven __node_pointer __r; 1474227825Stheraven if (__comp(__f2->__value_, __f1->__value_)) 1475227825Stheraven { 1476227825Stheraven __node_pointer __t = __f2; 1477227825Stheraven while (__t->__next_ != nullptr && 1478227825Stheraven __comp(__t->__next_->__value_, __f1->__value_)) 1479227825Stheraven __t = __t->__next_; 1480227825Stheraven __r = __f2; 1481227825Stheraven __f2 = __t->__next_; 1482227825Stheraven __t->__next_ = __f1; 1483227825Stheraven } 1484227825Stheraven else 1485227825Stheraven __r = __f1; 1486227825Stheraven __node_pointer __p = __f1; 1487227825Stheraven __f1 = __f1->__next_; 1488227825Stheraven while (__f1 != nullptr && __f2 != nullptr) 1489227825Stheraven { 1490227825Stheraven if (__comp(__f2->__value_, __f1->__value_)) 1491227825Stheraven { 1492227825Stheraven __node_pointer __t = __f2; 1493227825Stheraven while (__t->__next_ != nullptr && 1494227825Stheraven __comp(__t->__next_->__value_, __f1->__value_)) 1495227825Stheraven __t = __t->__next_; 1496227825Stheraven __p->__next_ = __f2; 1497227825Stheraven __f2 = __t->__next_; 1498227825Stheraven __t->__next_ = __f1; 1499227825Stheraven } 1500227825Stheraven __p = __f1; 1501227825Stheraven __f1 = __f1->__next_; 1502227825Stheraven } 1503227825Stheraven if (__f2 != nullptr) 1504227825Stheraven __p->__next_ = __f2; 1505227825Stheraven return __r; 1506227825Stheraven} 1507227825Stheraven 1508227825Stheraventemplate <class _Tp, class _Alloc> 1509227825Stheraventemplate <class _Compare> 1510227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 1511227825Stheravenvoid 1512227825Stheravenforward_list<_Tp, _Alloc>::sort(_Compare __comp) 1513227825Stheraven{ 1514227825Stheraven base::__before_begin()->__next_ = __sort(base::__before_begin()->__next_, 1515227825Stheraven _VSTD::distance(begin(), end()), __comp); 1516227825Stheraven} 1517227825Stheraven 1518227825Stheraventemplate <class _Tp, class _Alloc> 1519227825Stheraventemplate <class _Compare> 1520227825Stheraventypename forward_list<_Tp, _Alloc>::__node_pointer 1521227825Stheravenforward_list<_Tp, _Alloc>::__sort(__node_pointer __f1, difference_type __sz, 1522227825Stheraven _Compare& __comp) 1523227825Stheraven{ 1524227825Stheraven switch (__sz) 1525227825Stheraven { 1526227825Stheraven case 0: 1527227825Stheraven case 1: 1528227825Stheraven return __f1; 1529227825Stheraven case 2: 1530227825Stheraven if (__comp(__f1->__next_->__value_, __f1->__value_)) 1531227825Stheraven { 1532227825Stheraven __node_pointer __t = __f1->__next_; 1533227825Stheraven __t->__next_ = __f1; 1534227825Stheraven __f1->__next_ = nullptr; 1535227825Stheraven __f1 = __t; 1536227825Stheraven } 1537227825Stheraven return __f1; 1538227825Stheraven } 1539227825Stheraven difference_type __sz1 = __sz / 2; 1540227825Stheraven difference_type __sz2 = __sz - __sz1; 1541227825Stheraven __node_pointer __t = _VSTD::next(iterator(__f1), __sz1 - 1).__ptr_; 1542227825Stheraven __node_pointer __f2 = __t->__next_; 1543227825Stheraven __t->__next_ = nullptr; 1544227825Stheraven return __merge(__sort(__f1, __sz1, __comp), 1545227825Stheraven __sort(__f2, __sz2, __comp), __comp); 1546227825Stheraven} 1547227825Stheraven 1548227825Stheraventemplate <class _Tp, class _Alloc> 1549227825Stheravenvoid 1550227825Stheravenforward_list<_Tp, _Alloc>::reverse() _NOEXCEPT 1551227825Stheraven{ 1552227825Stheraven __node_pointer __p = base::__before_begin()->__next_; 1553227825Stheraven if (__p != nullptr) 1554227825Stheraven { 1555227825Stheraven __node_pointer __f = __p->__next_; 1556227825Stheraven __p->__next_ = nullptr; 1557227825Stheraven while (__f != nullptr) 1558227825Stheraven { 1559227825Stheraven __node_pointer __t = __f->__next_; 1560227825Stheraven __f->__next_ = __p; 1561227825Stheraven __p = __f; 1562227825Stheraven __f = __t; 1563227825Stheraven } 1564227825Stheraven base::__before_begin()->__next_ = __p; 1565227825Stheraven } 1566227825Stheraven} 1567227825Stheraven 1568227825Stheraventemplate <class _Tp, class _Alloc> 1569227825Stheravenbool operator==(const forward_list<_Tp, _Alloc>& __x, 1570227825Stheraven const forward_list<_Tp, _Alloc>& __y) 1571227825Stheraven{ 1572232950Stheraven typedef forward_list<_Tp, _Alloc> _Cp; 1573232950Stheraven typedef typename _Cp::const_iterator _Ip; 1574232950Stheraven _Ip __ix = __x.begin(); 1575232950Stheraven _Ip __ex = __x.end(); 1576232950Stheraven _Ip __iy = __y.begin(); 1577232950Stheraven _Ip __ey = __y.end(); 1578227825Stheraven for (; __ix != __ex && __iy != __ey; ++__ix, ++__iy) 1579227825Stheraven if (!(*__ix == *__iy)) 1580227825Stheraven return false; 1581227825Stheraven return (__ix == __ex) == (__iy == __ey); 1582227825Stheraven} 1583227825Stheraven 1584227825Stheraventemplate <class _Tp, class _Alloc> 1585227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 1586227825Stheravenbool operator!=(const forward_list<_Tp, _Alloc>& __x, 1587227825Stheraven const forward_list<_Tp, _Alloc>& __y) 1588227825Stheraven{ 1589227825Stheraven return !(__x == __y); 1590227825Stheraven} 1591227825Stheraven 1592227825Stheraventemplate <class _Tp, class _Alloc> 1593227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 1594227825Stheravenbool operator< (const forward_list<_Tp, _Alloc>& __x, 1595227825Stheraven const forward_list<_Tp, _Alloc>& __y) 1596227825Stheraven{ 1597227825Stheraven return _VSTD::lexicographical_compare(__x.begin(), __x.end(), 1598227825Stheraven __y.begin(), __y.end()); 1599227825Stheraven} 1600227825Stheraven 1601227825Stheraventemplate <class _Tp, class _Alloc> 1602227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 1603227825Stheravenbool operator> (const forward_list<_Tp, _Alloc>& __x, 1604227825Stheraven const forward_list<_Tp, _Alloc>& __y) 1605227825Stheraven{ 1606227825Stheraven return __y < __x; 1607227825Stheraven} 1608227825Stheraven 1609227825Stheraventemplate <class _Tp, class _Alloc> 1610227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 1611227825Stheravenbool operator>=(const forward_list<_Tp, _Alloc>& __x, 1612227825Stheraven const forward_list<_Tp, _Alloc>& __y) 1613227825Stheraven{ 1614227825Stheraven return !(__x < __y); 1615227825Stheraven} 1616227825Stheraven 1617227825Stheraventemplate <class _Tp, class _Alloc> 1618227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 1619227825Stheravenbool operator<=(const forward_list<_Tp, _Alloc>& __x, 1620227825Stheraven const forward_list<_Tp, _Alloc>& __y) 1621227825Stheraven{ 1622227825Stheraven return !(__y < __x); 1623227825Stheraven} 1624227825Stheraven 1625227825Stheraventemplate <class _Tp, class _Alloc> 1626227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 1627227825Stheravenvoid 1628227825Stheravenswap(forward_list<_Tp, _Alloc>& __x, forward_list<_Tp, _Alloc>& __y) 1629227825Stheraven _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y))) 1630227825Stheraven{ 1631227825Stheraven __x.swap(__y); 1632227825Stheraven} 1633227825Stheraven 1634227825Stheraven_LIBCPP_END_NAMESPACE_STD 1635227825Stheraven 1636227825Stheraven#endif // _LIBCPP_FORWARD_LIST 1637