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