forward_list revision 300770
1251881Speter// -*- C++ -*- 2251881Speter//===----------------------- forward_list ---------------------------------===// 3251881Speter// 4251881Speter// The LLVM Compiler Infrastructure 5251881Speter// 6251881Speter// This file is dual licensed under the MIT and the University of Illinois Open 7251881Speter// Source Licenses. See LICENSE.TXT for details. 8251881Speter// 9251881Speter//===----------------------------------------------------------------------===// 10251881Speter 11251881Speter#ifndef _LIBCPP_FORWARD_LIST 12251881Speter#define _LIBCPP_FORWARD_LIST 13251881Speter 14251881Speter/* 15251881Speter forward_list synopsis 16251881Speter 17251881Speternamespace std 18251881Speter{ 19251881Speter 20251881Spetertemplate <class T, class Allocator = allocator<T>> 21251881Speterclass forward_list 22251881Speter{ 23251881Speterpublic: 24251881Speter typedef T value_type; 25251881Speter typedef Allocator allocator_type; 26251881Speter 27251881Speter typedef value_type& reference; 28251881Speter typedef const value_type& const_reference; 29251881Speter typedef typename allocator_traits<allocator_type>::pointer pointer; 30251881Speter typedef typename allocator_traits<allocator_type>::const_pointer const_pointer; 31251881Speter typedef typename allocator_traits<allocator_type>::size_type size_type; 32251881Speter typedef typename allocator_traits<allocator_type>::difference_type difference_type; 33251881Speter 34251881Speter typedef <details> iterator; 35251881Speter typedef <details> const_iterator; 36251881Speter 37251881Speter forward_list() 38251881Speter noexcept(is_nothrow_default_constructible<allocator_type>::value); 39251881Speter explicit forward_list(const allocator_type& a); 40251881Speter explicit forward_list(size_type n); 41251881Speter explicit forward_list(size_type n, const allocator_type& a); // C++14 42251881Speter forward_list(size_type n, const value_type& v); 43251881Speter forward_list(size_type n, const value_type& v, const allocator_type& a); 44251881Speter template <class InputIterator> 45251881Speter forward_list(InputIterator first, InputIterator last); 46251881Speter template <class InputIterator> 47251881Speter forward_list(InputIterator first, InputIterator last, const allocator_type& a); 48251881Speter forward_list(const forward_list& x); 49251881Speter forward_list(const forward_list& x, const allocator_type& a); 50251881Speter forward_list(forward_list&& x) 51251881Speter noexcept(is_nothrow_move_constructible<allocator_type>::value); 52251881Speter forward_list(forward_list&& x, const allocator_type& a); 53251881Speter forward_list(initializer_list<value_type> il); 54251881Speter forward_list(initializer_list<value_type> il, const allocator_type& a); 55251881Speter 56251881Speter ~forward_list(); 57251881Speter 58251881Speter forward_list& operator=(const forward_list& x); 59251881Speter forward_list& operator=(forward_list&& x) 60251881Speter noexcept( 61251881Speter allocator_type::propagate_on_container_move_assignment::value && 62251881Speter is_nothrow_move_assignable<allocator_type>::value); 63251881Speter forward_list& operator=(initializer_list<value_type> il); 64251881Speter 65251881Speter template <class InputIterator> 66251881Speter void assign(InputIterator first, InputIterator last); 67251881Speter void assign(size_type n, const value_type& v); 68251881Speter void assign(initializer_list<value_type> il); 69251881Speter 70251881Speter allocator_type get_allocator() const noexcept; 71251881Speter 72251881Speter iterator begin() noexcept; 73251881Speter const_iterator begin() const noexcept; 74251881Speter iterator end() noexcept; 75251881Speter const_iterator end() const noexcept; 76251881Speter 77251881Speter const_iterator cbegin() const noexcept; 78251881Speter const_iterator cend() const noexcept; 79251881Speter 80251881Speter iterator before_begin() noexcept; 81251881Speter const_iterator before_begin() const noexcept; 82251881Speter const_iterator cbefore_begin() const noexcept; 83251881Speter 84251881Speter bool empty() const noexcept; 85251881Speter size_type max_size() const noexcept; 86251881Speter 87251881Speter reference front(); 88251881Speter const_reference front() const; 89251881Speter 90251881Speter template <class... Args> void emplace_front(Args&&... args); 91251881Speter void push_front(const value_type& v); 92251881Speter void push_front(value_type&& v); 93251881Speter 94251881Speter void pop_front(); 95251881Speter 96251881Speter template <class... Args> 97251881Speter iterator emplace_after(const_iterator p, Args&&... args); 98251881Speter iterator insert_after(const_iterator p, const value_type& v); 99251881Speter iterator insert_after(const_iterator p, value_type&& v); 100251881Speter iterator insert_after(const_iterator p, size_type n, const value_type& v); 101251881Speter template <class InputIterator> 102251881Speter iterator insert_after(const_iterator p, 103251881Speter InputIterator first, InputIterator last); 104251881Speter iterator insert_after(const_iterator p, initializer_list<value_type> il); 105251881Speter 106251881Speter iterator erase_after(const_iterator p); 107251881Speter iterator erase_after(const_iterator first, const_iterator last); 108251881Speter 109251881Speter void swap(forward_list& x) 110251881Speter noexcept(allocator_traits<allocator_type>::is_always_equal::value); // C++17 111251881Speter 112251881Speter void resize(size_type n); 113251881Speter void resize(size_type n, const value_type& v); 114251881Speter void clear() noexcept; 115251881Speter 116251881Speter void splice_after(const_iterator p, forward_list& x); 117251881Speter void splice_after(const_iterator p, forward_list&& x); 118251881Speter void splice_after(const_iterator p, forward_list& x, const_iterator i); 119251881Speter void splice_after(const_iterator p, forward_list&& x, const_iterator i); 120251881Speter void splice_after(const_iterator p, forward_list& x, 121251881Speter const_iterator first, const_iterator last); 122251881Speter void splice_after(const_iterator p, forward_list&& x, 123251881Speter const_iterator first, const_iterator last); 124251881Speter void remove(const value_type& v); 125251881Speter template <class Predicate> void remove_if(Predicate pred); 126251881Speter void unique(); 127251881Speter template <class BinaryPredicate> void unique(BinaryPredicate binary_pred); 128251881Speter void merge(forward_list& x); 129251881Speter void merge(forward_list&& x); 130251881Speter template <class Compare> void merge(forward_list& x, Compare comp); 131251881Speter template <class Compare> void merge(forward_list&& x, Compare comp); 132251881Speter void sort(); 133251881Speter template <class Compare> void sort(Compare comp); 134251881Speter void reverse() noexcept; 135251881Speter}; 136251881Speter 137251881Spetertemplate <class T, class Allocator> 138251881Speter bool operator==(const forward_list<T, Allocator>& x, 139251881Speter const forward_list<T, Allocator>& y); 140251881Speter 141251881Spetertemplate <class T, class Allocator> 142251881Speter bool operator< (const forward_list<T, Allocator>& x, 143251881Speter const forward_list<T, Allocator>& y); 144251881Speter 145251881Spetertemplate <class T, class Allocator> 146251881Speter bool operator!=(const forward_list<T, Allocator>& x, 147251881Speter const forward_list<T, Allocator>& y); 148251881Speter 149251881Spetertemplate <class T, class Allocator> 150251881Speter bool operator> (const forward_list<T, Allocator>& x, 151251881Speter const forward_list<T, Allocator>& y); 152251881Speter 153251881Spetertemplate <class T, class Allocator> 154251881Speter bool operator>=(const forward_list<T, Allocator>& x, 155251881Speter const forward_list<T, Allocator>& y); 156251881Speter 157251881Spetertemplate <class T, class Allocator> 158251881Speter bool operator<=(const forward_list<T, Allocator>& x, 159251881Speter const forward_list<T, Allocator>& y); 160251881Speter 161251881Spetertemplate <class T, class Allocator> 162251881Speter void swap(forward_list<T, Allocator>& x, forward_list<T, Allocator>& y) 163251881Speter noexcept(noexcept(x.swap(y))); 164251881Speter 165251881Speter} // std 166251881Speter 167251881Speter*/ 168251881Speter 169251881Speter#include <__config> 170251881Speter 171251881Speter#include <initializer_list> 172251881Speter#include <memory> 173251881Speter#include <limits> 174251881Speter#include <iterator> 175251881Speter#include <algorithm> 176251881Speter 177251881Speter#include <__undef_min_max> 178251881Speter 179251881Speter#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) 180251881Speter#pragma GCC system_header 181251881Speter#endif 182251881Speter 183251881Speter_LIBCPP_BEGIN_NAMESPACE_STD 184251881Speter 185251881Spetertemplate <class _Tp, class _VoidPtr> struct __forward_list_node; 186251881Speter 187251881Spetertemplate <class _NodePtr> 188251881Speterstruct __forward_begin_node 189251881Speter{ 190251881Speter typedef _NodePtr pointer; 191251881Speter 192251881Speter pointer __next_; 193251881Speter 194251881Speter _LIBCPP_INLINE_VISIBILITY __forward_begin_node() : __next_(nullptr) {} 195251881Speter}; 196251881Speter 197251881Spetertemplate <class _Tp, class _VoidPtr> 198251881Speterstruct _LIBCPP_HIDDEN __begin_node_of 199251881Speter{ 200251881Speter typedef __forward_begin_node< 201251881Speter typename __rebind_pointer<_VoidPtr, __forward_list_node<_Tp, _VoidPtr> >::type 202251881Speter > type; 203251881Speter}; 204251881Speter 205251881Spetertemplate <class _Tp, class _VoidPtr> 206251881Speterstruct __forward_list_node 207251881Speter : public __begin_node_of<_Tp, _VoidPtr>::type 208251881Speter{ 209251881Speter typedef _Tp value_type; 210251881Speter 211251881Speter value_type __value_; 212251881Speter}; 213251881Speter 214251881Spetertemplate <class _Tp, class _Alloc = allocator<_Tp> > class _LIBCPP_TYPE_VIS_ONLY forward_list; 215251881Spetertemplate<class _NodeConstPtr> class _LIBCPP_TYPE_VIS_ONLY __forward_list_const_iterator; 216251881Speter 217251881Spetertemplate <class _NodePtr> 218251881Speterclass _LIBCPP_TYPE_VIS_ONLY __forward_list_iterator 219251881Speter{ 220251881Speter typedef _NodePtr __node_pointer; 221251881Speter 222251881Speter __node_pointer __ptr_; 223251881Speter 224251881Speter _LIBCPP_INLINE_VISIBILITY 225251881Speter explicit __forward_list_iterator(__node_pointer __p) _NOEXCEPT : __ptr_(__p) {} 226251881Speter 227251881Speter template<class, class> friend class _LIBCPP_TYPE_VIS_ONLY forward_list; 228251881Speter template<class> friend class _LIBCPP_TYPE_VIS_ONLY __forward_list_const_iterator; 229251881Speter 230251881Speterpublic: 231251881Speter typedef forward_iterator_tag iterator_category; 232251881Speter typedef typename pointer_traits<__node_pointer>::element_type::value_type 233251881Speter value_type; 234251881Speter typedef value_type& reference; 235251881Speter typedef typename pointer_traits<__node_pointer>::difference_type 236251881Speter difference_type; 237251881Speter typedef typename __rebind_pointer<__node_pointer, value_type>::type pointer; 238251881Speter 239251881Speter _LIBCPP_INLINE_VISIBILITY 240251881Speter __forward_list_iterator() _NOEXCEPT : __ptr_(nullptr) {} 241251881Speter 242251881Speter _LIBCPP_INLINE_VISIBILITY 243251881Speter reference operator*() const {return __ptr_->__value_;} 244251881Speter _LIBCPP_INLINE_VISIBILITY 245251881Speter pointer operator->() const {return pointer_traits<pointer>::pointer_to(__ptr_->__value_);} 246251881Speter 247251881Speter _LIBCPP_INLINE_VISIBILITY 248251881Speter __forward_list_iterator& operator++() 249251881Speter { 250251881Speter __ptr_ = __ptr_->__next_; 251251881Speter return *this; 252251881Speter } 253251881Speter _LIBCPP_INLINE_VISIBILITY 254251881Speter __forward_list_iterator operator++(int) 255251881Speter { 256251881Speter __forward_list_iterator __t(*this); 257251881Speter ++(*this); 258251881Speter return __t; 259251881Speter } 260251881Speter 261251881Speter friend _LIBCPP_INLINE_VISIBILITY 262251881Speter bool operator==(const __forward_list_iterator& __x, 263251881Speter const __forward_list_iterator& __y) 264251881Speter {return __x.__ptr_ == __y.__ptr_;} 265251881Speter friend _LIBCPP_INLINE_VISIBILITY 266251881Speter bool operator!=(const __forward_list_iterator& __x, 267251881Speter const __forward_list_iterator& __y) 268251881Speter {return !(__x == __y);} 269251881Speter}; 270251881Speter 271251881Spetertemplate <class _NodeConstPtr> 272251881Speterclass _LIBCPP_TYPE_VIS_ONLY __forward_list_const_iterator 273251881Speter{ 274251881Speter typedef _NodeConstPtr __node_const_pointer; 275251881Speter 276251881Speter __node_const_pointer __ptr_; 277251881Speter 278251881Speter _LIBCPP_INLINE_VISIBILITY 279251881Speter explicit __forward_list_const_iterator(__node_const_pointer __p) _NOEXCEPT 280251881Speter : __ptr_(__p) {} 281251881Speter 282251881Speter typedef typename remove_const 283251881Speter < 284251881Speter typename pointer_traits<__node_const_pointer>::element_type 285251881Speter >::type __node; 286251881Speter typedef typename __rebind_pointer<__node_const_pointer, __node>::type __node_pointer; 287251881Speter 288251881Speter template<class, class> friend class forward_list; 289251881Speter 290251881Speterpublic: 291251881Speter typedef forward_iterator_tag iterator_category; 292251881Speter typedef typename __node::value_type value_type; 293251881Speter typedef const value_type& reference; 294251881Speter typedef typename pointer_traits<__node_const_pointer>::difference_type 295251881Speter difference_type; 296251881Speter typedef typename __rebind_pointer<__node_const_pointer, const value_type>::type pointer; 297251881Speter 298251881Speter _LIBCPP_INLINE_VISIBILITY 299251881Speter __forward_list_const_iterator() _NOEXCEPT : __ptr_(nullptr) {} 300251881Speter _LIBCPP_INLINE_VISIBILITY 301251881Speter __forward_list_const_iterator(__forward_list_iterator<__node_pointer> __p) _NOEXCEPT 302251881Speter : __ptr_(__p.__ptr_) {} 303251881Speter 304251881Speter _LIBCPP_INLINE_VISIBILITY 305251881Speter reference operator*() const {return __ptr_->__value_;} 306251881Speter _LIBCPP_INLINE_VISIBILITY 307251881Speter pointer operator->() const {return pointer_traits<pointer>::pointer_to(__ptr_->__value_);} 308251881Speter 309251881Speter _LIBCPP_INLINE_VISIBILITY 310251881Speter __forward_list_const_iterator& operator++() 311251881Speter { 312251881Speter __ptr_ = __ptr_->__next_; 313251881Speter return *this; 314251881Speter } 315251881Speter _LIBCPP_INLINE_VISIBILITY 316251881Speter __forward_list_const_iterator operator++(int) 317251881Speter { 318251881Speter __forward_list_const_iterator __t(*this); 319251881Speter ++(*this); 320251881Speter return __t; 321251881Speter } 322251881Speter 323251881Speter friend _LIBCPP_INLINE_VISIBILITY 324251881Speter bool operator==(const __forward_list_const_iterator& __x, 325251881Speter const __forward_list_const_iterator& __y) 326251881Speter {return __x.__ptr_ == __y.__ptr_;} 327251881Speter friend _LIBCPP_INLINE_VISIBILITY 328251881Speter bool operator!=(const __forward_list_const_iterator& __x, 329251881Speter const __forward_list_const_iterator& __y) 330251881Speter {return !(__x == __y);} 331251881Speter}; 332251881Speter 333251881Spetertemplate <class _Tp, class _Alloc> 334251881Speterclass __forward_list_base 335251881Speter{ 336251881Speterprotected: 337251881Speter typedef _Tp value_type; 338251881Speter typedef _Alloc allocator_type; 339251881Speter 340251881Speter typedef typename allocator_traits<allocator_type>::void_pointer void_pointer; 341251881Speter typedef __forward_list_node<value_type, void_pointer> __node; 342251881Speter typedef typename __begin_node_of<value_type, void_pointer>::type __begin_node; 343251881Speter typedef typename __rebind_alloc_helper<allocator_traits<allocator_type>, __node>::type __node_allocator; 344251881Speter typedef allocator_traits<__node_allocator> __node_traits; 345251881Speter typedef typename __node_traits::pointer __node_pointer; 346251881Speter typedef typename __node_traits::pointer __node_const_pointer; 347251881Speter 348251881Speter typedef typename __rebind_alloc_helper<allocator_traits<allocator_type>, __begin_node>::type __begin_node_allocator; 349251881Speter typedef typename allocator_traits<__begin_node_allocator>::pointer __begin_node_pointer; 350251881Speter 351251881Speter __compressed_pair<__begin_node, __node_allocator> __before_begin_; 352251881Speter 353251881Speter _LIBCPP_INLINE_VISIBILITY 354251881Speter __node_pointer __before_begin() _NOEXCEPT 355251881Speter {return static_cast<__node_pointer>(pointer_traits<__begin_node_pointer>:: 356251881Speter pointer_to(__before_begin_.first()));} 357251881Speter _LIBCPP_INLINE_VISIBILITY 358251881Speter __node_const_pointer __before_begin() const _NOEXCEPT 359251881Speter {return static_cast<__node_const_pointer>(pointer_traits<__begin_node_pointer>:: 360251881Speter pointer_to(const_cast<__begin_node&>(__before_begin_.first())));} 361251881Speter 362251881Speter _LIBCPP_INLINE_VISIBILITY 363251881Speter __node_allocator& __alloc() _NOEXCEPT 364251881Speter {return __before_begin_.second();} 365251881Speter _LIBCPP_INLINE_VISIBILITY 366251881Speter const __node_allocator& __alloc() const _NOEXCEPT 367251881Speter {return __before_begin_.second();} 368251881Speter 369251881Speter typedef __forward_list_iterator<__node_pointer> iterator; 370251881Speter typedef __forward_list_const_iterator<__node_pointer> const_iterator; 371251881Speter 372251881Speter _LIBCPP_INLINE_VISIBILITY 373251881Speter __forward_list_base() 374251881Speter _NOEXCEPT_(is_nothrow_default_constructible<__node_allocator>::value) 375251881Speter : __before_begin_(__begin_node()) {} 376251881Speter _LIBCPP_INLINE_VISIBILITY 377251881Speter __forward_list_base(const allocator_type& __a) 378251881Speter : __before_begin_(__begin_node(), __node_allocator(__a)) {} 379251881Speter 380251881Speter#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 381251881Speterpublic: 382251881Speter __forward_list_base(__forward_list_base&& __x) 383251881Speter _NOEXCEPT_(is_nothrow_move_constructible<__node_allocator>::value); 384251881Speter __forward_list_base(__forward_list_base&& __x, const allocator_type& __a); 385251881Speter#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 386251881Speter 387251881Speterprivate: 388251881Speter __forward_list_base(const __forward_list_base&); 389251881Speter __forward_list_base& operator=(const __forward_list_base&); 390251881Speter 391251881Speterpublic: 392251881Speter ~__forward_list_base(); 393251881Speter 394251881Speterprotected: 395251881Speter _LIBCPP_INLINE_VISIBILITY 396251881Speter void __copy_assign_alloc(const __forward_list_base& __x) 397251881Speter {__copy_assign_alloc(__x, integral_constant<bool, 398251881Speter __node_traits::propagate_on_container_copy_assignment::value>());} 399251881Speter 400251881Speter _LIBCPP_INLINE_VISIBILITY 401251881Speter void __move_assign_alloc(__forward_list_base& __x) 402251881Speter _NOEXCEPT_(!__node_traits::propagate_on_container_move_assignment::value || 403251881Speter is_nothrow_move_assignable<__node_allocator>::value) 404251881Speter {__move_assign_alloc(__x, integral_constant<bool, 405251881Speter __node_traits::propagate_on_container_move_assignment::value>());} 406251881Speter 407251881Speterpublic: 408251881Speter void swap(__forward_list_base& __x) 409251881Speter#if _LIBCPP_STD_VER >= 14 410251881Speter _NOEXCEPT; 411251881Speter#else 412251881Speter _NOEXCEPT_(!__node_traits::propagate_on_container_move_assignment::value || 413251881Speter __is_nothrow_swappable<__node_allocator>::value); 414251881Speter#endif 415251881Speterprotected: 416251881Speter void clear() _NOEXCEPT; 417251881Speter 418251881Speterprivate: 419251881Speter _LIBCPP_INLINE_VISIBILITY 420251881Speter void __copy_assign_alloc(const __forward_list_base&, false_type) {} 421251881Speter _LIBCPP_INLINE_VISIBILITY 422251881Speter void __copy_assign_alloc(const __forward_list_base& __x, true_type) 423251881Speter { 424251881Speter if (__alloc() != __x.__alloc()) 425251881Speter clear(); 426251881Speter __alloc() = __x.__alloc(); 427251881Speter } 428251881Speter 429251881Speter _LIBCPP_INLINE_VISIBILITY 430251881Speter void __move_assign_alloc(__forward_list_base& __x, false_type) _NOEXCEPT 431251881Speter {} 432251881Speter _LIBCPP_INLINE_VISIBILITY 433251881Speter void __move_assign_alloc(__forward_list_base& __x, true_type) 434251881Speter _NOEXCEPT_(is_nothrow_move_assignable<__node_allocator>::value) 435251881Speter {__alloc() = _VSTD::move(__x.__alloc());} 436251881Speter}; 437251881Speter 438251881Speter#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 439251881Speter 440251881Spetertemplate <class _Tp, class _Alloc> 441251881Speterinline _LIBCPP_INLINE_VISIBILITY 442251881Speter__forward_list_base<_Tp, _Alloc>::__forward_list_base(__forward_list_base&& __x) 443251881Speter _NOEXCEPT_(is_nothrow_move_constructible<__node_allocator>::value) 444251881Speter : __before_begin_(_VSTD::move(__x.__before_begin_)) 445251881Speter{ 446251881Speter __x.__before_begin()->__next_ = nullptr; 447251881Speter} 448251881Speter 449251881Spetertemplate <class _Tp, class _Alloc> 450251881Speterinline _LIBCPP_INLINE_VISIBILITY 451251881Speter__forward_list_base<_Tp, _Alloc>::__forward_list_base(__forward_list_base&& __x, 452251881Speter const allocator_type& __a) 453251881Speter : __before_begin_(__begin_node(), __node_allocator(__a)) 454251881Speter{ 455251881Speter if (__alloc() == __x.__alloc()) 456251881Speter { 457251881Speter __before_begin()->__next_ = __x.__before_begin()->__next_; 458251881Speter __x.__before_begin()->__next_ = nullptr; 459251881Speter } 460251881Speter} 461251881Speter 462251881Speter#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 463251881Speter 464251881Spetertemplate <class _Tp, class _Alloc> 465251881Speter__forward_list_base<_Tp, _Alloc>::~__forward_list_base() 466251881Speter{ 467251881Speter clear(); 468251881Speter} 469251881Speter 470251881Spetertemplate <class _Tp, class _Alloc> 471251881Speterinline _LIBCPP_INLINE_VISIBILITY 472251881Spetervoid 473251881Speter__forward_list_base<_Tp, _Alloc>::swap(__forward_list_base& __x) 474251881Speter#if _LIBCPP_STD_VER >= 14 475251881Speter _NOEXCEPT 476251881Speter#else 477251881Speter _NOEXCEPT_(!__node_traits::propagate_on_container_move_assignment::value || 478251881Speter __is_nothrow_swappable<__node_allocator>::value) 479251881Speter#endif 480251881Speter{ 481251881Speter __swap_allocator(__alloc(), __x.__alloc(), 482251881Speter integral_constant<bool, __node_traits::propagate_on_container_swap::value>()); 483251881Speter using _VSTD::swap; 484251881Speter swap(__before_begin()->__next_, __x.__before_begin()->__next_); 485251881Speter} 486251881Speter 487251881Spetertemplate <class _Tp, class _Alloc> 488251881Spetervoid 489251881Speter__forward_list_base<_Tp, _Alloc>::clear() _NOEXCEPT 490251881Speter{ 491251881Speter __node_allocator& __a = __alloc(); 492251881Speter for (__node_pointer __p = __before_begin()->__next_; __p != nullptr;) 493251881Speter { 494251881Speter __node_pointer __next = __p->__next_; 495251881Speter __node_traits::destroy(__a, _VSTD::addressof(__p->__value_)); 496251881Speter __node_traits::deallocate(__a, __p, 1); 497251881Speter __p = __next; 498251881Speter } 499251881Speter __before_begin()->__next_ = nullptr; 500251881Speter} 501251881Speter 502251881Spetertemplate <class _Tp, class _Alloc /*= allocator<_Tp>*/> 503251881Speterclass _LIBCPP_TYPE_VIS_ONLY forward_list 504251881Speter : private __forward_list_base<_Tp, _Alloc> 505251881Speter{ 506251881Speter typedef __forward_list_base<_Tp, _Alloc> base; 507251881Speter typedef typename base::__node_allocator __node_allocator; 508251881Speter typedef typename base::__node __node; 509251881Speter typedef typename base::__node_traits __node_traits; 510251881Speter typedef typename base::__node_pointer __node_pointer; 511251881Speter 512251881Speterpublic: 513251881Speter typedef _Tp value_type; 514251881Speter typedef _Alloc allocator_type; 515251881Speter 516251881Speter static_assert((is_same<typename allocator_type::value_type, value_type>::value), 517251881Speter "Allocator::value_type must be same type as value_type"); 518251881Speter 519251881Speter typedef value_type& reference; 520251881Speter typedef const value_type& const_reference; 521251881Speter typedef typename allocator_traits<allocator_type>::pointer pointer; 522251881Speter typedef typename allocator_traits<allocator_type>::const_pointer const_pointer; 523251881Speter typedef typename allocator_traits<allocator_type>::size_type size_type; 524251881Speter typedef typename allocator_traits<allocator_type>::difference_type difference_type; 525251881Speter 526251881Speter typedef typename base::iterator iterator; 527251881Speter typedef typename base::const_iterator const_iterator; 528251881Speter 529251881Speter _LIBCPP_INLINE_VISIBILITY 530251881Speter forward_list() 531251881Speter _NOEXCEPT_(is_nothrow_default_constructible<__node_allocator>::value) 532251881Speter {} // = default; 533251881Speter explicit forward_list(const allocator_type& __a); 534251881Speter explicit forward_list(size_type __n); 535251881Speter#if _LIBCPP_STD_VER > 11 536251881Speter explicit forward_list(size_type __n, const allocator_type& __a); 537251881Speter#endif 538251881Speter forward_list(size_type __n, const value_type& __v); 539251881Speter forward_list(size_type __n, const value_type& __v, const allocator_type& __a); 540251881Speter template <class _InputIterator> 541251881Speter forward_list(_InputIterator __f, _InputIterator __l, 542251881Speter typename enable_if< 543251881Speter __is_input_iterator<_InputIterator>::value 544251881Speter >::type* = nullptr); 545251881Speter template <class _InputIterator> 546251881Speter forward_list(_InputIterator __f, _InputIterator __l, 547251881Speter const allocator_type& __a, 548251881Speter typename enable_if< 549251881Speter __is_input_iterator<_InputIterator>::value 550251881Speter >::type* = nullptr); 551251881Speter forward_list(const forward_list& __x); 552251881Speter forward_list(const forward_list& __x, const allocator_type& __a); 553251881Speter#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 554251881Speter _LIBCPP_INLINE_VISIBILITY 555251881Speter forward_list(forward_list&& __x) 556251881Speter _NOEXCEPT_(is_nothrow_move_constructible<base>::value) 557251881Speter : base(_VSTD::move(__x)) {} 558251881Speter forward_list(forward_list&& __x, const allocator_type& __a); 559251881Speter#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 560251881Speter#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 561251881Speter forward_list(initializer_list<value_type> __il); 562251881Speter forward_list(initializer_list<value_type> __il, const allocator_type& __a); 563251881Speter#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 564251881Speter 565251881Speter // ~forward_list() = default; 566251881Speter 567251881Speter forward_list& operator=(const forward_list& __x); 568251881Speter#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 569251881Speter forward_list& operator=(forward_list&& __x) 570251881Speter _NOEXCEPT_( 571251881Speter __node_traits::propagate_on_container_move_assignment::value && 572251881Speter is_nothrow_move_assignable<allocator_type>::value); 573251881Speter#endif 574251881Speter#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 575251881Speter forward_list& operator=(initializer_list<value_type> __il); 576251881Speter#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 577251881Speter 578251881Speter template <class _InputIterator> 579251881Speter typename enable_if 580251881Speter < 581251881Speter __is_input_iterator<_InputIterator>::value, 582251881Speter void 583251881Speter >::type 584251881Speter assign(_InputIterator __f, _InputIterator __l); 585251881Speter void assign(size_type __n, const value_type& __v); 586251881Speter#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 587251881Speter void assign(initializer_list<value_type> __il); 588251881Speter#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 589251881Speter 590251881Speter _LIBCPP_INLINE_VISIBILITY 591251881Speter allocator_type get_allocator() const _NOEXCEPT 592251881Speter {return allocator_type(base::__alloc());} 593251881Speter 594251881Speter _LIBCPP_INLINE_VISIBILITY 595251881Speter iterator begin() _NOEXCEPT 596251881Speter {return iterator(base::__before_begin()->__next_);} 597251881Speter _LIBCPP_INLINE_VISIBILITY 598251881Speter const_iterator begin() const _NOEXCEPT 599251881Speter {return const_iterator(base::__before_begin()->__next_);} 600251881Speter _LIBCPP_INLINE_VISIBILITY 601251881Speter iterator end() _NOEXCEPT 602251881Speter {return iterator(nullptr);} 603251881Speter _LIBCPP_INLINE_VISIBILITY 604251881Speter const_iterator end() const _NOEXCEPT 605251881Speter {return const_iterator(nullptr);} 606251881Speter 607251881Speter _LIBCPP_INLINE_VISIBILITY 608251881Speter const_iterator cbegin() const _NOEXCEPT 609251881Speter {return const_iterator(base::__before_begin()->__next_);} 610251881Speter _LIBCPP_INLINE_VISIBILITY 611251881Speter const_iterator cend() const _NOEXCEPT 612251881Speter {return const_iterator(nullptr);} 613251881Speter 614251881Speter _LIBCPP_INLINE_VISIBILITY 615251881Speter iterator before_begin() _NOEXCEPT 616251881Speter {return iterator(base::__before_begin());} 617251881Speter _LIBCPP_INLINE_VISIBILITY 618251881Speter const_iterator before_begin() const _NOEXCEPT 619251881Speter {return const_iterator(base::__before_begin());} 620251881Speter _LIBCPP_INLINE_VISIBILITY 621251881Speter const_iterator cbefore_begin() const _NOEXCEPT 622251881Speter {return const_iterator(base::__before_begin());} 623251881Speter 624251881Speter _LIBCPP_INLINE_VISIBILITY 625251881Speter bool empty() const _NOEXCEPT 626251881Speter {return base::__before_begin()->__next_ == nullptr;} 627251881Speter _LIBCPP_INLINE_VISIBILITY 628251881Speter size_type max_size() const _NOEXCEPT 629251881Speter {return numeric_limits<size_type>::max();} 630251881Speter 631251881Speter _LIBCPP_INLINE_VISIBILITY 632251881Speter reference front() {return base::__before_begin()->__next_->__value_;} 633251881Speter _LIBCPP_INLINE_VISIBILITY 634251881Speter const_reference front() const {return base::__before_begin()->__next_->__value_;} 635251881Speter 636251881Speter#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 637251881Speter#ifndef _LIBCPP_HAS_NO_VARIADICS 638251881Speter template <class... _Args> void emplace_front(_Args&&... __args); 639251881Speter#endif 640251881Speter void push_front(value_type&& __v); 641251881Speter#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 642251881Speter void push_front(const value_type& __v); 643251881Speter 644251881Speter void pop_front(); 645251881Speter 646251881Speter#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 647251881Speter#ifndef _LIBCPP_HAS_NO_VARIADICS 648251881Speter template <class... _Args> 649251881Speter iterator emplace_after(const_iterator __p, _Args&&... __args); 650251881Speter#endif // _LIBCPP_HAS_NO_VARIADICS 651251881Speter iterator insert_after(const_iterator __p, value_type&& __v); 652251881Speter#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 653251881Speter iterator insert_after(const_iterator __p, const value_type& __v); 654251881Speter iterator insert_after(const_iterator __p, size_type __n, const value_type& __v); 655251881Speter template <class _InputIterator> 656251881Speter _LIBCPP_INLINE_VISIBILITY 657251881Speter typename enable_if 658251881Speter < 659251881Speter __is_input_iterator<_InputIterator>::value, 660251881Speter iterator 661251881Speter >::type 662251881Speter insert_after(const_iterator __p, _InputIterator __f, _InputIterator __l); 663251881Speter#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 664251881Speter iterator insert_after(const_iterator __p, initializer_list<value_type> __il) 665251881Speter {return insert_after(__p, __il.begin(), __il.end());} 666251881Speter#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 667251881Speter 668251881Speter iterator erase_after(const_iterator __p); 669251881Speter iterator erase_after(const_iterator __f, const_iterator __l); 670251881Speter 671251881Speter _LIBCPP_INLINE_VISIBILITY 672251881Speter void swap(forward_list& __x) 673251881Speter#if _LIBCPP_STD_VER >= 14 674251881Speter _NOEXCEPT 675251881Speter#else 676251881Speter _NOEXCEPT_(!__node_traits::propagate_on_container_swap::value || 677251881Speter __is_nothrow_swappable<__node_allocator>::value) 678251881Speter#endif 679251881Speter {base::swap(__x);} 680251881Speter 681251881Speter void resize(size_type __n); 682251881Speter void resize(size_type __n, const value_type& __v); 683251881Speter _LIBCPP_INLINE_VISIBILITY 684251881Speter void clear() _NOEXCEPT {base::clear();} 685251881Speter 686251881Speter#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 687251881Speter _LIBCPP_INLINE_VISIBILITY 688251881Speter void splice_after(const_iterator __p, forward_list&& __x); 689251881Speter _LIBCPP_INLINE_VISIBILITY 690251881Speter void splice_after(const_iterator __p, forward_list&& __x, const_iterator __i); 691251881Speter _LIBCPP_INLINE_VISIBILITY 692251881Speter void splice_after(const_iterator __p, forward_list&& __x, 693251881Speter const_iterator __f, const_iterator __l); 694251881Speter#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 695251881Speter void splice_after(const_iterator __p, forward_list& __x); 696251881Speter void splice_after(const_iterator __p, forward_list& __x, const_iterator __i); 697251881Speter void splice_after(const_iterator __p, forward_list& __x, 698251881Speter const_iterator __f, const_iterator __l); 699251881Speter void remove(const value_type& __v); 700251881Speter template <class _Predicate> void remove_if(_Predicate __pred); 701251881Speter _LIBCPP_INLINE_VISIBILITY 702251881Speter void unique() {unique(__equal_to<value_type>());} 703251881Speter template <class _BinaryPredicate> void unique(_BinaryPredicate __binary_pred); 704251881Speter#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 705251881Speter _LIBCPP_INLINE_VISIBILITY 706251881Speter void merge(forward_list&& __x) {merge(__x, __less<value_type>());} 707251881Speter template <class _Compare> 708251881Speter _LIBCPP_INLINE_VISIBILITY 709251881Speter void merge(forward_list&& __x, _Compare __comp) 710251881Speter {merge(__x, _VSTD::move(__comp));} 711251881Speter#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 712251881Speter _LIBCPP_INLINE_VISIBILITY 713251881Speter void merge(forward_list& __x) {merge(__x, __less<value_type>());} 714251881Speter template <class _Compare> void merge(forward_list& __x, _Compare __comp); 715251881Speter _LIBCPP_INLINE_VISIBILITY 716251881Speter void sort() {sort(__less<value_type>());} 717251881Speter template <class _Compare> void sort(_Compare __comp); 718251881Speter void reverse() _NOEXCEPT; 719251881Speter 720251881Speterprivate: 721251881Speter 722251881Speter#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 723251881Speter void __move_assign(forward_list& __x, true_type) 724251881Speter _NOEXCEPT_(is_nothrow_move_assignable<allocator_type>::value); 725251881Speter void __move_assign(forward_list& __x, false_type); 726251881Speter#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 727251881Speter 728251881Speter template <class _Compare> 729251881Speter static 730251881Speter __node_pointer 731251881Speter __merge(__node_pointer __f1, __node_pointer __f2, _Compare& __comp); 732251881Speter 733251881Speter template <class _Compare> 734251881Speter static 735251881Speter __node_pointer 736251881Speter __sort(__node_pointer __f, difference_type __sz, _Compare& __comp); 737251881Speter}; 738251881Speter 739251881Spetertemplate <class _Tp, class _Alloc> 740251881Speterinline _LIBCPP_INLINE_VISIBILITY 741251881Speterforward_list<_Tp, _Alloc>::forward_list(const allocator_type& __a) 742251881Speter : base(__a) 743251881Speter{ 744251881Speter} 745251881Speter 746251881Spetertemplate <class _Tp, class _Alloc> 747251881Speterforward_list<_Tp, _Alloc>::forward_list(size_type __n) 748251881Speter{ 749251881Speter if (__n > 0) 750251881Speter { 751251881Speter __node_allocator& __a = base::__alloc(); 752251881Speter typedef __allocator_destructor<__node_allocator> _Dp; 753251881Speter unique_ptr<__node, _Dp> __h(nullptr, _Dp(__a, 1)); 754251881Speter for (__node_pointer __p = base::__before_begin(); __n > 0; --__n, 755251881Speter __p = __p->__next_) 756251881Speter { 757251881Speter __h.reset(__node_traits::allocate(__a, 1)); 758251881Speter __node_traits::construct(__a, _VSTD::addressof(__h->__value_)); 759251881Speter __h->__next_ = nullptr; 760251881Speter __p->__next_ = __h.release(); 761251881Speter } 762251881Speter } 763251881Speter} 764251881Speter 765251881Speter#if _LIBCPP_STD_VER > 11 766251881Spetertemplate <class _Tp, class _Alloc> 767251881Speterforward_list<_Tp, _Alloc>::forward_list(size_type __n, const allocator_type& __a) 768251881Speter : base ( __a ) 769251881Speter{ 770251881Speter if (__n > 0) 771251881Speter { 772251881Speter __node_allocator& __a = base::__alloc(); 773251881Speter typedef __allocator_destructor<__node_allocator> _Dp; 774251881Speter unique_ptr<__node, _Dp> __h(nullptr, _Dp(__a, 1)); 775251881Speter for (__node_pointer __p = base::__before_begin(); __n > 0; --__n, 776251881Speter __p = __p->__next_) 777251881Speter { 778251881Speter __h.reset(__node_traits::allocate(__a, 1)); 779251881Speter __node_traits::construct(__a, _VSTD::addressof(__h->__value_)); 780251881Speter __h->__next_ = nullptr; 781251881Speter __p->__next_ = __h.release(); 782251881Speter } 783251881Speter } 784251881Speter} 785251881Speter#endif 786251881Speter 787251881Spetertemplate <class _Tp, class _Alloc> 788251881Speterforward_list<_Tp, _Alloc>::forward_list(size_type __n, const value_type& __v) 789251881Speter{ 790251881Speter insert_after(cbefore_begin(), __n, __v); 791251881Speter} 792251881Speter 793251881Spetertemplate <class _Tp, class _Alloc> 794251881Speterforward_list<_Tp, _Alloc>::forward_list(size_type __n, const value_type& __v, 795251881Speter const allocator_type& __a) 796251881Speter : base(__a) 797251881Speter{ 798251881Speter insert_after(cbefore_begin(), __n, __v); 799251881Speter} 800251881Speter 801251881Spetertemplate <class _Tp, class _Alloc> 802251881Spetertemplate <class _InputIterator> 803251881Speterforward_list<_Tp, _Alloc>::forward_list(_InputIterator __f, _InputIterator __l, 804251881Speter typename enable_if< 805251881Speter __is_input_iterator<_InputIterator>::value 806251881Speter >::type*) 807251881Speter{ 808251881Speter insert_after(cbefore_begin(), __f, __l); 809251881Speter} 810251881Speter 811251881Spetertemplate <class _Tp, class _Alloc> 812251881Spetertemplate <class _InputIterator> 813251881Speterforward_list<_Tp, _Alloc>::forward_list(_InputIterator __f, _InputIterator __l, 814251881Speter const allocator_type& __a, 815251881Speter typename enable_if< 816251881Speter __is_input_iterator<_InputIterator>::value 817251881Speter >::type*) 818251881Speter : base(__a) 819251881Speter{ 820251881Speter insert_after(cbefore_begin(), __f, __l); 821251881Speter} 822251881Speter 823251881Spetertemplate <class _Tp, class _Alloc> 824251881Speterforward_list<_Tp, _Alloc>::forward_list(const forward_list& __x) 825251881Speter : base(allocator_type( 826251881Speter __node_traits::select_on_container_copy_construction(__x.__alloc()) 827251881Speter ) 828251881Speter ) 829251881Speter{ 830251881Speter insert_after(cbefore_begin(), __x.begin(), __x.end()); 831251881Speter} 832251881Speter 833251881Spetertemplate <class _Tp, class _Alloc> 834251881Speterforward_list<_Tp, _Alloc>::forward_list(const forward_list& __x, 835251881Speter const allocator_type& __a) 836251881Speter : base(__a) 837251881Speter{ 838251881Speter insert_after(cbefore_begin(), __x.begin(), __x.end()); 839251881Speter} 840251881Speter 841251881Speter#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 842251881Speter 843251881Spetertemplate <class _Tp, class _Alloc> 844251881Speterforward_list<_Tp, _Alloc>::forward_list(forward_list&& __x, 845251881Speter const allocator_type& __a) 846251881Speter : base(_VSTD::move(__x), __a) 847251881Speter{ 848251881Speter if (base::__alloc() != __x.__alloc()) 849251881Speter { 850251881Speter typedef move_iterator<iterator> _Ip; 851251881Speter insert_after(cbefore_begin(), _Ip(__x.begin()), _Ip(__x.end())); 852251881Speter } 853251881Speter} 854251881Speter 855251881Speter#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 856251881Speter 857251881Speter#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 858251881Speter 859251881Spetertemplate <class _Tp, class _Alloc> 860251881Speterforward_list<_Tp, _Alloc>::forward_list(initializer_list<value_type> __il) 861251881Speter{ 862251881Speter insert_after(cbefore_begin(), __il.begin(), __il.end()); 863251881Speter} 864251881Speter 865251881Spetertemplate <class _Tp, class _Alloc> 866251881Speterforward_list<_Tp, _Alloc>::forward_list(initializer_list<value_type> __il, 867251881Speter const allocator_type& __a) 868251881Speter : base(__a) 869251881Speter{ 870251881Speter insert_after(cbefore_begin(), __il.begin(), __il.end()); 871251881Speter} 872251881Speter 873251881Speter#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 874251881Speter 875251881Spetertemplate <class _Tp, class _Alloc> 876251881Speterforward_list<_Tp, _Alloc>& 877251881Speterforward_list<_Tp, _Alloc>::operator=(const forward_list& __x) 878251881Speter{ 879251881Speter if (this != &__x) 880251881Speter { 881251881Speter base::__copy_assign_alloc(__x); 882251881Speter assign(__x.begin(), __x.end()); 883251881Speter } 884251881Speter return *this; 885251881Speter} 886251881Speter 887251881Speter#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 888251881Speter 889251881Spetertemplate <class _Tp, class _Alloc> 890251881Spetervoid 891251881Speterforward_list<_Tp, _Alloc>::__move_assign(forward_list& __x, true_type) 892251881Speter _NOEXCEPT_(is_nothrow_move_assignable<allocator_type>::value) 893251881Speter{ 894251881Speter clear(); 895251881Speter base::__move_assign_alloc(__x); 896251881Speter base::__before_begin()->__next_ = __x.__before_begin()->__next_; 897251881Speter __x.__before_begin()->__next_ = nullptr; 898251881Speter} 899251881Speter 900251881Spetertemplate <class _Tp, class _Alloc> 901251881Spetervoid 902251881Speterforward_list<_Tp, _Alloc>::__move_assign(forward_list& __x, false_type) 903251881Speter{ 904251881Speter if (base::__alloc() == __x.__alloc()) 905251881Speter __move_assign(__x, true_type()); 906251881Speter else 907251881Speter { 908251881Speter typedef move_iterator<iterator> _Ip; 909251881Speter assign(_Ip(__x.begin()), _Ip(__x.end())); 910251881Speter } 911251881Speter} 912251881Speter 913251881Spetertemplate <class _Tp, class _Alloc> 914251881Speterinline _LIBCPP_INLINE_VISIBILITY 915251881Speterforward_list<_Tp, _Alloc>& 916251881Speterforward_list<_Tp, _Alloc>::operator=(forward_list&& __x) 917251881Speter _NOEXCEPT_( 918251881Speter __node_traits::propagate_on_container_move_assignment::value && 919251881Speter is_nothrow_move_assignable<allocator_type>::value) 920251881Speter{ 921251881Speter __move_assign(__x, integral_constant<bool, 922251881Speter __node_traits::propagate_on_container_move_assignment::value>()); 923251881Speter return *this; 924251881Speter} 925251881Speter 926251881Speter#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 927251881Speter 928251881Speter#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 929251881Speter 930251881Spetertemplate <class _Tp, class _Alloc> 931251881Speterinline _LIBCPP_INLINE_VISIBILITY 932251881Speterforward_list<_Tp, _Alloc>& 933251881Speterforward_list<_Tp, _Alloc>::operator=(initializer_list<value_type> __il) 934251881Speter{ 935251881Speter assign(__il.begin(), __il.end()); 936251881Speter return *this; 937251881Speter} 938251881Speter 939251881Speter#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 940251881Speter 941251881Spetertemplate <class _Tp, class _Alloc> 942251881Spetertemplate <class _InputIterator> 943251881Spetertypename enable_if 944251881Speter< 945251881Speter __is_input_iterator<_InputIterator>::value, 946251881Speter void 947251881Speter>::type 948251881Speterforward_list<_Tp, _Alloc>::assign(_InputIterator __f, _InputIterator __l) 949251881Speter{ 950251881Speter iterator __i = before_begin(); 951251881Speter iterator __j = _VSTD::next(__i); 952251881Speter iterator __e = end(); 953251881Speter for (; __j != __e && __f != __l; ++__i, (void) ++__j, ++__f) 954251881Speter *__j = *__f; 955251881Speter if (__j == __e) 956251881Speter insert_after(__i, __f, __l); 957251881Speter else 958251881Speter erase_after(__i, __e); 959251881Speter} 960251881Speter 961251881Spetertemplate <class _Tp, class _Alloc> 962251881Spetervoid 963251881Speterforward_list<_Tp, _Alloc>::assign(size_type __n, const value_type& __v) 964251881Speter{ 965251881Speter iterator __i = before_begin(); 966251881Speter iterator __j = _VSTD::next(__i); 967251881Speter iterator __e = end(); 968251881Speter for (; __j != __e && __n > 0; --__n, ++__i, ++__j) 969251881Speter *__j = __v; 970251881Speter if (__j == __e) 971251881Speter insert_after(__i, __n, __v); 972251881Speter else 973251881Speter erase_after(__i, __e); 974251881Speter} 975251881Speter 976251881Speter#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 977251881Speter 978251881Spetertemplate <class _Tp, class _Alloc> 979251881Speterinline _LIBCPP_INLINE_VISIBILITY 980251881Spetervoid 981251881Speterforward_list<_Tp, _Alloc>::assign(initializer_list<value_type> __il) 982251881Speter{ 983251881Speter assign(__il.begin(), __il.end()); 984251881Speter} 985251881Speter 986251881Speter#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 987251881Speter 988251881Speter#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 989251881Speter#ifndef _LIBCPP_HAS_NO_VARIADICS 990251881Speter 991251881Spetertemplate <class _Tp, class _Alloc> 992251881Spetertemplate <class... _Args> 993251881Spetervoid 994251881Speterforward_list<_Tp, _Alloc>::emplace_front(_Args&&... __args) 995251881Speter{ 996251881Speter __node_allocator& __a = base::__alloc(); 997251881Speter typedef __allocator_destructor<__node_allocator> _Dp; 998251881Speter unique_ptr<__node, _Dp> __h(__node_traits::allocate(__a, 1), _Dp(__a, 1)); 999251881Speter __node_traits::construct(__a, _VSTD::addressof(__h->__value_), 1000251881Speter _VSTD::forward<_Args>(__args)...); 1001251881Speter __h->__next_ = base::__before_begin()->__next_; 1002251881Speter base::__before_begin()->__next_ = __h.release(); 1003251881Speter} 1004251881Speter 1005251881Speter#endif // _LIBCPP_HAS_NO_VARIADICS 1006251881Speter 1007251881Spetertemplate <class _Tp, class _Alloc> 1008251881Spetervoid 1009251881Speterforward_list<_Tp, _Alloc>::push_front(value_type&& __v) 1010251881Speter{ 1011251881Speter __node_allocator& __a = base::__alloc(); 1012251881Speter typedef __allocator_destructor<__node_allocator> _Dp; 1013251881Speter unique_ptr<__node, _Dp> __h(__node_traits::allocate(__a, 1), _Dp(__a, 1)); 1014251881Speter __node_traits::construct(__a, _VSTD::addressof(__h->__value_), _VSTD::move(__v)); 1015251881Speter __h->__next_ = base::__before_begin()->__next_; 1016251881Speter base::__before_begin()->__next_ = __h.release(); 1017251881Speter} 1018251881Speter 1019251881Speter#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 1020251881Speter 1021251881Spetertemplate <class _Tp, class _Alloc> 1022251881Spetervoid 1023251881Speterforward_list<_Tp, _Alloc>::push_front(const value_type& __v) 1024251881Speter{ 1025251881Speter __node_allocator& __a = base::__alloc(); 1026251881Speter typedef __allocator_destructor<__node_allocator> _Dp; 1027251881Speter unique_ptr<__node, _Dp> __h(__node_traits::allocate(__a, 1), _Dp(__a, 1)); 1028251881Speter __node_traits::construct(__a, _VSTD::addressof(__h->__value_), __v); 1029251881Speter __h->__next_ = base::__before_begin()->__next_; 1030251881Speter base::__before_begin()->__next_ = __h.release(); 1031251881Speter} 1032251881Speter 1033251881Spetertemplate <class _Tp, class _Alloc> 1034251881Spetervoid 1035251881Speterforward_list<_Tp, _Alloc>::pop_front() 1036251881Speter{ 1037251881Speter __node_allocator& __a = base::__alloc(); 1038251881Speter __node_pointer __p = base::__before_begin()->__next_; 1039251881Speter base::__before_begin()->__next_ = __p->__next_; 1040251881Speter __node_traits::destroy(__a, _VSTD::addressof(__p->__value_)); 1041251881Speter __node_traits::deallocate(__a, __p, 1); 1042251881Speter} 1043251881Speter 1044251881Speter#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 1045251881Speter#ifndef _LIBCPP_HAS_NO_VARIADICS 1046251881Speter 1047251881Spetertemplate <class _Tp, class _Alloc> 1048251881Spetertemplate <class... _Args> 1049251881Spetertypename forward_list<_Tp, _Alloc>::iterator 1050251881Speterforward_list<_Tp, _Alloc>::emplace_after(const_iterator __p, _Args&&... __args) 1051251881Speter{ 1052251881Speter __node_pointer const __r = __p.__ptr_; 1053251881Speter __node_allocator& __a = base::__alloc(); 1054251881Speter typedef __allocator_destructor<__node_allocator> _Dp; 1055251881Speter unique_ptr<__node, _Dp> __h(__node_traits::allocate(__a, 1), _Dp(__a, 1)); 1056251881Speter __node_traits::construct(__a, _VSTD::addressof(__h->__value_), 1057251881Speter _VSTD::forward<_Args>(__args)...); 1058251881Speter __h->__next_ = __r->__next_; 1059251881Speter __r->__next_ = __h.release(); 1060251881Speter return iterator(__r->__next_); 1061251881Speter} 1062251881Speter 1063251881Speter#endif // _LIBCPP_HAS_NO_VARIADICS 1064251881Speter 1065251881Spetertemplate <class _Tp, class _Alloc> 1066251881Spetertypename forward_list<_Tp, _Alloc>::iterator 1067251881Speterforward_list<_Tp, _Alloc>::insert_after(const_iterator __p, value_type&& __v) 1068251881Speter{ 1069251881Speter __node_pointer const __r = __p.__ptr_; 1070251881Speter __node_allocator& __a = base::__alloc(); 1071251881Speter typedef __allocator_destructor<__node_allocator> _Dp; 1072251881Speter unique_ptr<__node, _Dp> __h(__node_traits::allocate(__a, 1), _Dp(__a, 1)); 1073251881Speter __node_traits::construct(__a, _VSTD::addressof(__h->__value_), _VSTD::move(__v)); 1074251881Speter __h->__next_ = __r->__next_; 1075251881Speter __r->__next_ = __h.release(); 1076251881Speter return iterator(__r->__next_); 1077251881Speter} 1078251881Speter 1079251881Speter#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 1080251881Speter 1081251881Spetertemplate <class _Tp, class _Alloc> 1082251881Spetertypename forward_list<_Tp, _Alloc>::iterator 1083251881Speterforward_list<_Tp, _Alloc>::insert_after(const_iterator __p, const value_type& __v) 1084251881Speter{ 1085251881Speter __node_pointer const __r = __p.__ptr_; 1086251881Speter __node_allocator& __a = base::__alloc(); 1087251881Speter typedef __allocator_destructor<__node_allocator> _Dp; 1088251881Speter unique_ptr<__node, _Dp> __h(__node_traits::allocate(__a, 1), _Dp(__a, 1)); 1089251881Speter __node_traits::construct(__a, _VSTD::addressof(__h->__value_), __v); 1090251881Speter __h->__next_ = __r->__next_; 1091251881Speter __r->__next_ = __h.release(); 1092251881Speter return iterator(__r->__next_); 1093251881Speter} 1094251881Speter 1095251881Spetertemplate <class _Tp, class _Alloc> 1096251881Spetertypename forward_list<_Tp, _Alloc>::iterator 1097251881Speterforward_list<_Tp, _Alloc>::insert_after(const_iterator __p, size_type __n, 1098251881Speter const value_type& __v) 1099251881Speter{ 1100251881Speter __node_pointer __r = __p.__ptr_; 1101251881Speter if (__n > 0) 1102251881Speter { 1103251881Speter __node_allocator& __a = base::__alloc(); 1104251881Speter typedef __allocator_destructor<__node_allocator> _Dp; 1105251881Speter unique_ptr<__node, _Dp> __h(__node_traits::allocate(__a, 1), _Dp(__a, 1)); 1106251881Speter __node_traits::construct(__a, _VSTD::addressof(__h->__value_), __v); 1107251881Speter __node_pointer __first = __h.release(); 1108251881Speter __node_pointer __last = __first; 1109251881Speter#ifndef _LIBCPP_NO_EXCEPTIONS 1110251881Speter try 1111251881Speter { 1112251881Speter#endif // _LIBCPP_NO_EXCEPTIONS 1113251881Speter for (--__n; __n != 0; --__n, __last = __last->__next_) 1114251881Speter { 1115251881Speter __h.reset(__node_traits::allocate(__a, 1)); 1116251881Speter __node_traits::construct(__a, _VSTD::addressof(__h->__value_), __v); 1117251881Speter __last->__next_ = __h.release(); 1118251881Speter } 1119251881Speter#ifndef _LIBCPP_NO_EXCEPTIONS 1120251881Speter } 1121251881Speter catch (...) 1122251881Speter { 1123251881Speter while (__first != nullptr) 1124251881Speter { 1125251881Speter __node_pointer __next = __first->__next_; 1126251881Speter __node_traits::destroy(__a, _VSTD::addressof(__first->__value_)); 1127251881Speter __node_traits::deallocate(__a, __first, 1); 1128251881Speter __first = __next; 1129251881Speter } 1130251881Speter throw; 1131251881Speter } 1132251881Speter#endif // _LIBCPP_NO_EXCEPTIONS 1133251881Speter __last->__next_ = __r->__next_; 1134251881Speter __r->__next_ = __first; 1135251881Speter __r = __last; 1136251881Speter } 1137251881Speter return iterator(__r); 1138251881Speter} 1139251881Speter 1140251881Spetertemplate <class _Tp, class _Alloc> 1141251881Spetertemplate <class _InputIterator> 1142251881Spetertypename enable_if 1143251881Speter< 1144251881Speter __is_input_iterator<_InputIterator>::value, 1145251881Speter typename forward_list<_Tp, _Alloc>::iterator 1146251881Speter>::type 1147251881Speterforward_list<_Tp, _Alloc>::insert_after(const_iterator __p, 1148251881Speter _InputIterator __f, _InputIterator __l) 1149251881Speter{ 1150251881Speter __node_pointer __r = __p.__ptr_; 1151251881Speter if (__f != __l) 1152251881Speter { 1153251881Speter __node_allocator& __a = base::__alloc(); 1154251881Speter typedef __allocator_destructor<__node_allocator> _Dp; 1155251881Speter unique_ptr<__node, _Dp> __h(__node_traits::allocate(__a, 1), _Dp(__a, 1)); 1156251881Speter __node_traits::construct(__a, _VSTD::addressof(__h->__value_), *__f); 1157251881Speter __node_pointer __first = __h.release(); 1158251881Speter __node_pointer __last = __first; 1159251881Speter#ifndef _LIBCPP_NO_EXCEPTIONS 1160251881Speter try 1161251881Speter { 1162251881Speter#endif // _LIBCPP_NO_EXCEPTIONS 1163251881Speter for (++__f; __f != __l; ++__f, ((void)(__last = __last->__next_))) 1164251881Speter { 1165251881Speter __h.reset(__node_traits::allocate(__a, 1)); 1166251881Speter __node_traits::construct(__a, _VSTD::addressof(__h->__value_), *__f); 1167251881Speter __last->__next_ = __h.release(); 1168251881Speter } 1169251881Speter#ifndef _LIBCPP_NO_EXCEPTIONS 1170251881Speter } 1171251881Speter catch (...) 1172251881Speter { 1173251881Speter while (__first != nullptr) 1174251881Speter { 1175251881Speter __node_pointer __next = __first->__next_; 1176251881Speter __node_traits::destroy(__a, _VSTD::addressof(__first->__value_)); 1177251881Speter __node_traits::deallocate(__a, __first, 1); 1178251881Speter __first = __next; 1179251881Speter } 1180251881Speter throw; 1181251881Speter } 1182251881Speter#endif // _LIBCPP_NO_EXCEPTIONS 1183251881Speter __last->__next_ = __r->__next_; 1184251881Speter __r->__next_ = __first; 1185251881Speter __r = __last; 1186251881Speter } 1187251881Speter return iterator(__r); 1188251881Speter} 1189251881Speter 1190251881Spetertemplate <class _Tp, class _Alloc> 1191251881Spetertypename forward_list<_Tp, _Alloc>::iterator 1192251881Speterforward_list<_Tp, _Alloc>::erase_after(const_iterator __f) 1193251881Speter{ 1194251881Speter __node_pointer __p = __f.__ptr_; 1195251881Speter __node_pointer __n = __p->__next_; 1196251881Speter __p->__next_ = __n->__next_; 1197251881Speter __node_allocator& __a = base::__alloc(); 1198251881Speter __node_traits::destroy(__a, _VSTD::addressof(__n->__value_)); 1199251881Speter __node_traits::deallocate(__a, __n, 1); 1200251881Speter return iterator(__p->__next_); 1201251881Speter} 1202251881Speter 1203251881Spetertemplate <class _Tp, class _Alloc> 1204251881Spetertypename forward_list<_Tp, _Alloc>::iterator 1205251881Speterforward_list<_Tp, _Alloc>::erase_after(const_iterator __f, const_iterator __l) 1206251881Speter{ 1207251881Speter __node_pointer __e = __l.__ptr_; 1208251881Speter if (__f != __l) 1209251881Speter { 1210251881Speter __node_pointer __p = __f.__ptr_; 1211251881Speter __node_pointer __n = __p->__next_; 1212251881Speter if (__n != __e) 1213251881Speter { 1214251881Speter __p->__next_ = __e; 1215251881Speter __node_allocator& __a = base::__alloc(); 1216251881Speter do 1217251881Speter { 1218251881Speter __p = __n->__next_; 1219251881Speter __node_traits::destroy(__a, _VSTD::addressof(__n->__value_)); 1220251881Speter __node_traits::deallocate(__a, __n, 1); 1221251881Speter __n = __p; 1222251881Speter } while (__n != __e); 1223251881Speter } 1224251881Speter } 1225251881Speter return iterator(__e); 1226251881Speter} 1227251881Speter 1228251881Spetertemplate <class _Tp, class _Alloc> 1229251881Spetervoid 1230251881Speterforward_list<_Tp, _Alloc>::resize(size_type __n) 1231251881Speter{ 1232251881Speter size_type __sz = 0; 1233251881Speter iterator __p = before_begin(); 1234251881Speter iterator __i = begin(); 1235251881Speter iterator __e = end(); 1236251881Speter for (; __i != __e && __sz < __n; ++__p, ++__i, ++__sz) 1237251881Speter ; 1238251881Speter if (__i != __e) 1239251881Speter erase_after(__p, __e); 1240251881Speter else 1241251881Speter { 1242251881Speter __n -= __sz; 1243251881Speter if (__n > 0) 1244251881Speter { 1245251881Speter __node_allocator& __a = base::__alloc(); 1246251881Speter typedef __allocator_destructor<__node_allocator> _Dp; 1247251881Speter unique_ptr<__node, _Dp> __h(nullptr, _Dp(__a, 1)); 1248251881Speter for (__node_pointer __ptr = __p.__ptr_; __n > 0; --__n, 1249251881Speter __ptr = __ptr->__next_) 1250251881Speter { 1251251881Speter __h.reset(__node_traits::allocate(__a, 1)); 1252251881Speter __node_traits::construct(__a, _VSTD::addressof(__h->__value_)); 1253251881Speter __h->__next_ = nullptr; 1254251881Speter __ptr->__next_ = __h.release(); 1255251881Speter } 1256251881Speter } 1257251881Speter } 1258251881Speter} 1259251881Speter 1260251881Spetertemplate <class _Tp, class _Alloc> 1261251881Spetervoid 1262251881Speterforward_list<_Tp, _Alloc>::resize(size_type __n, const value_type& __v) 1263251881Speter{ 1264251881Speter size_type __sz = 0; 1265251881Speter iterator __p = before_begin(); 1266251881Speter iterator __i = begin(); 1267251881Speter iterator __e = end(); 1268251881Speter for (; __i != __e && __sz < __n; ++__p, ++__i, ++__sz) 1269251881Speter ; 1270251881Speter if (__i != __e) 1271251881Speter erase_after(__p, __e); 1272251881Speter else 1273251881Speter { 1274251881Speter __n -= __sz; 1275251881Speter if (__n > 0) 1276251881Speter { 1277251881Speter __node_allocator& __a = base::__alloc(); 1278251881Speter typedef __allocator_destructor<__node_allocator> _Dp; 1279251881Speter unique_ptr<__node, _Dp> __h(nullptr, _Dp(__a, 1)); 1280251881Speter for (__node_pointer __ptr = __p.__ptr_; __n > 0; --__n, 1281251881Speter __ptr = __ptr->__next_) 1282251881Speter { 1283251881Speter __h.reset(__node_traits::allocate(__a, 1)); 1284251881Speter __node_traits::construct(__a, _VSTD::addressof(__h->__value_), __v); 1285251881Speter __h->__next_ = nullptr; 1286251881Speter __ptr->__next_ = __h.release(); 1287251881Speter } 1288251881Speter } 1289251881Speter } 1290251881Speter} 1291251881Speter 1292251881Spetertemplate <class _Tp, class _Alloc> 1293251881Spetervoid 1294251881Speterforward_list<_Tp, _Alloc>::splice_after(const_iterator __p, 1295251881Speter forward_list& __x) 1296251881Speter{ 1297251881Speter if (!__x.empty()) 1298251881Speter { 1299251881Speter if (__p.__ptr_->__next_ != nullptr) 1300251881Speter { 1301251881Speter const_iterator __lm1 = __x.before_begin(); 1302251881Speter while (__lm1.__ptr_->__next_ != nullptr) 1303251881Speter ++__lm1; 1304251881Speter __lm1.__ptr_->__next_ = __p.__ptr_->__next_; 1305251881Speter } 1306251881Speter __p.__ptr_->__next_ = __x.__before_begin()->__next_; 1307251881Speter __x.__before_begin()->__next_ = nullptr; 1308251881Speter } 1309251881Speter} 1310251881Speter 1311251881Spetertemplate <class _Tp, class _Alloc> 1312251881Spetervoid 1313251881Speterforward_list<_Tp, _Alloc>::splice_after(const_iterator __p, 1314251881Speter forward_list& __x, 1315251881Speter const_iterator __i) 1316251881Speter{ 1317251881Speter const_iterator __lm1 = _VSTD::next(__i); 1318251881Speter if (__p != __i && __p != __lm1) 1319251881Speter { 1320251881Speter __i.__ptr_->__next_ = __lm1.__ptr_->__next_; 1321251881Speter __lm1.__ptr_->__next_ = __p.__ptr_->__next_; 1322251881Speter __p.__ptr_->__next_ = __lm1.__ptr_; 1323251881Speter } 1324251881Speter} 1325251881Speter 1326251881Spetertemplate <class _Tp, class _Alloc> 1327251881Spetervoid 1328251881Speterforward_list<_Tp, _Alloc>::splice_after(const_iterator __p, 1329251881Speter forward_list& __x, 1330251881Speter const_iterator __f, const_iterator __l) 1331251881Speter{ 1332251881Speter if (__f != __l && __p != __f) 1333251881Speter { 1334251881Speter const_iterator __lm1 = __f; 1335251881Speter while (__lm1.__ptr_->__next_ != __l.__ptr_) 1336251881Speter ++__lm1; 1337251881Speter if (__f != __lm1) 1338251881Speter { 1339251881Speter __lm1.__ptr_->__next_ = __p.__ptr_->__next_; 1340251881Speter __p.__ptr_->__next_ = __f.__ptr_->__next_; 1341251881Speter __f.__ptr_->__next_ = __l.__ptr_; 1342251881Speter } 1343251881Speter } 1344251881Speter} 1345251881Speter 1346251881Speter#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 1347251881Speter 1348251881Spetertemplate <class _Tp, class _Alloc> 1349251881Speterinline _LIBCPP_INLINE_VISIBILITY 1350251881Spetervoid 1351251881Speterforward_list<_Tp, _Alloc>::splice_after(const_iterator __p, 1352251881Speter forward_list&& __x) 1353251881Speter{ 1354251881Speter splice_after(__p, __x); 1355251881Speter} 1356251881Speter 1357251881Spetertemplate <class _Tp, class _Alloc> 1358251881Speterinline _LIBCPP_INLINE_VISIBILITY 1359251881Spetervoid 1360251881Speterforward_list<_Tp, _Alloc>::splice_after(const_iterator __p, 1361251881Speter forward_list&& __x, 1362251881Speter const_iterator __i) 1363251881Speter{ 1364251881Speter splice_after(__p, __x, __i); 1365251881Speter} 1366251881Speter 1367251881Spetertemplate <class _Tp, class _Alloc> 1368251881Speterinline _LIBCPP_INLINE_VISIBILITY 1369251881Spetervoid 1370251881Speterforward_list<_Tp, _Alloc>::splice_after(const_iterator __p, 1371251881Speter forward_list&& __x, 1372251881Speter const_iterator __f, const_iterator __l) 1373251881Speter{ 1374251881Speter splice_after(__p, __x, __f, __l); 1375251881Speter} 1376251881Speter 1377251881Speter#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 1378251881Speter 1379251881Spetertemplate <class _Tp, class _Alloc> 1380251881Spetervoid 1381251881Speterforward_list<_Tp, _Alloc>::remove(const value_type& __v) 1382251881Speter{ 1383251881Speter forward_list<_Tp, _Alloc> __deleted_nodes; // collect the nodes we're removing 1384251881Speter iterator __e = end(); 1385251881Speter for (iterator __i = before_begin(); __i.__ptr_->__next_ != nullptr;) 1386251881Speter { 1387251881Speter if (__i.__ptr_->__next_->__value_ == __v) 1388251881Speter { 1389251881Speter iterator __j = _VSTD::next(__i, 2); 1390251881Speter for (; __j != __e && *__j == __v; ++__j) 1391251881Speter ; 1392251881Speter __deleted_nodes.splice_after(__deleted_nodes.before_begin(), *this, __i, __j); 1393251881Speter if (__j == __e) 1394251881Speter break; 1395251881Speter __i = __j; 1396251881Speter } 1397251881Speter else 1398251881Speter ++__i; 1399251881Speter } 1400251881Speter} 1401251881Speter 1402251881Spetertemplate <class _Tp, class _Alloc> 1403251881Spetertemplate <class _Predicate> 1404251881Spetervoid 1405251881Speterforward_list<_Tp, _Alloc>::remove_if(_Predicate __pred) 1406251881Speter{ 1407251881Speter iterator __e = end(); 1408251881Speter for (iterator __i = before_begin(); __i.__ptr_->__next_ != nullptr;) 1409251881Speter { 1410251881Speter if (__pred(__i.__ptr_->__next_->__value_)) 1411251881Speter { 1412251881Speter iterator __j = _VSTD::next(__i, 2); 1413251881Speter for (; __j != __e && __pred(*__j); ++__j) 1414251881Speter ; 1415251881Speter erase_after(__i, __j); 1416251881Speter if (__j == __e) 1417251881Speter break; 1418251881Speter __i = __j; 1419251881Speter } 1420251881Speter else 1421251881Speter ++__i; 1422251881Speter } 1423251881Speter} 1424251881Speter 1425251881Spetertemplate <class _Tp, class _Alloc> 1426251881Spetertemplate <class _BinaryPredicate> 1427251881Spetervoid 1428251881Speterforward_list<_Tp, _Alloc>::unique(_BinaryPredicate __binary_pred) 1429251881Speter{ 1430251881Speter for (iterator __i = begin(), __e = end(); __i != __e;) 1431251881Speter { 1432251881Speter iterator __j = _VSTD::next(__i); 1433251881Speter for (; __j != __e && __binary_pred(*__i, *__j); ++__j) 1434251881Speter ; 1435251881Speter if (__i.__ptr_->__next_ != __j.__ptr_) 1436251881Speter erase_after(__i, __j); 1437251881Speter __i = __j; 1438251881Speter } 1439251881Speter} 1440251881Speter 1441251881Spetertemplate <class _Tp, class _Alloc> 1442251881Spetertemplate <class _Compare> 1443251881Spetervoid 1444251881Speterforward_list<_Tp, _Alloc>::merge(forward_list& __x, _Compare __comp) 1445251881Speter{ 1446251881Speter if (this != &__x) 1447251881Speter { 1448251881Speter base::__before_begin()->__next_ = __merge(base::__before_begin()->__next_, 1449251881Speter __x.__before_begin()->__next_, 1450251881Speter __comp); 1451251881Speter __x.__before_begin()->__next_ = nullptr; 1452251881Speter } 1453251881Speter} 1454251881Speter 1455251881Spetertemplate <class _Tp, class _Alloc> 1456251881Spetertemplate <class _Compare> 1457251881Spetertypename forward_list<_Tp, _Alloc>::__node_pointer 1458251881Speterforward_list<_Tp, _Alloc>::__merge(__node_pointer __f1, __node_pointer __f2, 1459251881Speter _Compare& __comp) 1460251881Speter{ 1461251881Speter if (__f1 == nullptr) 1462251881Speter return __f2; 1463251881Speter if (__f2 == nullptr) 1464251881Speter return __f1; 1465251881Speter __node_pointer __r; 1466251881Speter if (__comp(__f2->__value_, __f1->__value_)) 1467251881Speter { 1468251881Speter __node_pointer __t = __f2; 1469251881Speter while (__t->__next_ != nullptr && 1470251881Speter __comp(__t->__next_->__value_, __f1->__value_)) 1471251881Speter __t = __t->__next_; 1472251881Speter __r = __f2; 1473251881Speter __f2 = __t->__next_; 1474251881Speter __t->__next_ = __f1; 1475251881Speter } 1476251881Speter else 1477251881Speter __r = __f1; 1478251881Speter __node_pointer __p = __f1; 1479251881Speter __f1 = __f1->__next_; 1480251881Speter while (__f1 != nullptr && __f2 != nullptr) 1481251881Speter { 1482251881Speter if (__comp(__f2->__value_, __f1->__value_)) 1483251881Speter { 1484251881Speter __node_pointer __t = __f2; 1485251881Speter while (__t->__next_ != nullptr && 1486251881Speter __comp(__t->__next_->__value_, __f1->__value_)) 1487251881Speter __t = __t->__next_; 1488251881Speter __p->__next_ = __f2; 1489251881Speter __f2 = __t->__next_; 1490251881Speter __t->__next_ = __f1; 1491251881Speter } 1492251881Speter __p = __f1; 1493251881Speter __f1 = __f1->__next_; 1494251881Speter } 1495251881Speter if (__f2 != nullptr) 1496251881Speter __p->__next_ = __f2; 1497251881Speter return __r; 1498251881Speter} 1499251881Speter 1500251881Spetertemplate <class _Tp, class _Alloc> 1501251881Spetertemplate <class _Compare> 1502251881Speterinline _LIBCPP_INLINE_VISIBILITY 1503251881Spetervoid 1504251881Speterforward_list<_Tp, _Alloc>::sort(_Compare __comp) 1505251881Speter{ 1506251881Speter base::__before_begin()->__next_ = __sort(base::__before_begin()->__next_, 1507251881Speter _VSTD::distance(begin(), end()), __comp); 1508251881Speter} 1509251881Speter 1510251881Spetertemplate <class _Tp, class _Alloc> 1511251881Spetertemplate <class _Compare> 1512251881Spetertypename forward_list<_Tp, _Alloc>::__node_pointer 1513251881Speterforward_list<_Tp, _Alloc>::__sort(__node_pointer __f1, difference_type __sz, 1514251881Speter _Compare& __comp) 1515251881Speter{ 1516251881Speter switch (__sz) 1517251881Speter { 1518251881Speter case 0: 1519251881Speter case 1: 1520251881Speter return __f1; 1521251881Speter case 2: 1522251881Speter if (__comp(__f1->__next_->__value_, __f1->__value_)) 1523251881Speter { 1524251881Speter __node_pointer __t = __f1->__next_; 1525251881Speter __t->__next_ = __f1; 1526251881Speter __f1->__next_ = nullptr; 1527251881Speter __f1 = __t; 1528251881Speter } 1529251881Speter return __f1; 1530251881Speter } 1531251881Speter difference_type __sz1 = __sz / 2; 1532251881Speter difference_type __sz2 = __sz - __sz1; 1533251881Speter __node_pointer __t = _VSTD::next(iterator(__f1), __sz1 - 1).__ptr_; 1534251881Speter __node_pointer __f2 = __t->__next_; 1535251881Speter __t->__next_ = nullptr; 1536251881Speter return __merge(__sort(__f1, __sz1, __comp), 1537251881Speter __sort(__f2, __sz2, __comp), __comp); 1538251881Speter} 1539251881Speter 1540251881Spetertemplate <class _Tp, class _Alloc> 1541251881Spetervoid 1542251881Speterforward_list<_Tp, _Alloc>::reverse() _NOEXCEPT 1543251881Speter{ 1544251881Speter __node_pointer __p = base::__before_begin()->__next_; 1545251881Speter if (__p != nullptr) 1546251881Speter { 1547251881Speter __node_pointer __f = __p->__next_; 1548251881Speter __p->__next_ = nullptr; 1549251881Speter while (__f != nullptr) 1550251881Speter { 1551251881Speter __node_pointer __t = __f->__next_; 1552251881Speter __f->__next_ = __p; 1553251881Speter __p = __f; 1554251881Speter __f = __t; 1555251881Speter } 1556251881Speter base::__before_begin()->__next_ = __p; 1557251881Speter } 1558251881Speter} 1559251881Speter 1560251881Spetertemplate <class _Tp, class _Alloc> 1561251881Speterbool operator==(const forward_list<_Tp, _Alloc>& __x, 1562251881Speter const forward_list<_Tp, _Alloc>& __y) 1563251881Speter{ 1564251881Speter typedef forward_list<_Tp, _Alloc> _Cp; 1565251881Speter typedef typename _Cp::const_iterator _Ip; 1566251881Speter _Ip __ix = __x.begin(); 1567251881Speter _Ip __ex = __x.end(); 1568251881Speter _Ip __iy = __y.begin(); 1569251881Speter _Ip __ey = __y.end(); 1570251881Speter for (; __ix != __ex && __iy != __ey; ++__ix, ++__iy) 1571251881Speter if (!(*__ix == *__iy)) 1572251881Speter return false; 1573251881Speter return (__ix == __ex) == (__iy == __ey); 1574251881Speter} 1575251881Speter 1576251881Spetertemplate <class _Tp, class _Alloc> 1577251881Speterinline _LIBCPP_INLINE_VISIBILITY 1578251881Speterbool operator!=(const forward_list<_Tp, _Alloc>& __x, 1579251881Speter const forward_list<_Tp, _Alloc>& __y) 1580251881Speter{ 1581251881Speter return !(__x == __y); 1582251881Speter} 1583251881Speter 1584251881Spetertemplate <class _Tp, class _Alloc> 1585251881Speterinline _LIBCPP_INLINE_VISIBILITY 1586251881Speterbool operator< (const forward_list<_Tp, _Alloc>& __x, 1587251881Speter const forward_list<_Tp, _Alloc>& __y) 1588251881Speter{ 1589251881Speter return _VSTD::lexicographical_compare(__x.begin(), __x.end(), 1590251881Speter __y.begin(), __y.end()); 1591251881Speter} 1592251881Speter 1593251881Spetertemplate <class _Tp, class _Alloc> 1594251881Speterinline _LIBCPP_INLINE_VISIBILITY 1595251881Speterbool operator> (const forward_list<_Tp, _Alloc>& __x, 1596251881Speter const forward_list<_Tp, _Alloc>& __y) 1597251881Speter{ 1598251881Speter return __y < __x; 1599251881Speter} 1600251881Speter 1601251881Spetertemplate <class _Tp, class _Alloc> 1602251881Speterinline _LIBCPP_INLINE_VISIBILITY 1603251881Speterbool operator>=(const forward_list<_Tp, _Alloc>& __x, 1604251881Speter const forward_list<_Tp, _Alloc>& __y) 1605251881Speter{ 1606251881Speter return !(__x < __y); 1607251881Speter} 1608251881Speter 1609251881Spetertemplate <class _Tp, class _Alloc> 1610251881Speterinline _LIBCPP_INLINE_VISIBILITY 1611251881Speterbool operator<=(const forward_list<_Tp, _Alloc>& __x, 1612251881Speter const forward_list<_Tp, _Alloc>& __y) 1613251881Speter{ 1614251881Speter return !(__y < __x); 1615251881Speter} 1616251881Speter 1617251881Spetertemplate <class _Tp, class _Alloc> 1618251881Speterinline _LIBCPP_INLINE_VISIBILITY 1619251881Spetervoid 1620251881Speterswap(forward_list<_Tp, _Alloc>& __x, forward_list<_Tp, _Alloc>& __y) 1621251881Speter _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y))) 1622251881Speter{ 1623251881Speter __x.swap(__y); 1624251881Speter} 1625251881Speter 1626251881Speter_LIBCPP_END_NAMESPACE_STD 1627251881Speter 1628251881Speter#endif // _LIBCPP_FORWARD_LIST 1629251881Speter