2 //===----------------------- forward_list ---------------------------------===//
4 // The LLVM Compiler Infrastructure
6 // This file is dual licensed under the MIT and the University of Illinois Open
7 // Source Licenses. See LICENSE.TXT for details.
9 //===----------------------------------------------------------------------===//
11 #ifndef _LIBCPP_FORWARD_LIST
12 #define _LIBCPP_FORWARD_LIST
20 template <class T, class Allocator = allocator<T>>
25 typedef Allocator allocator_type;
27 typedef value_type& reference;
28 typedef const value_type& const_reference;
29 typedef typename allocator_traits<allocator_type>::pointer pointer;
30 typedef typename allocator_traits<allocator_type>::const_pointer const_pointer;
31 typedef typename allocator_traits<allocator_type>::size_type size_type;
32 typedef typename allocator_traits<allocator_type>::difference_type difference_type;
34 typedef <details> iterator;
35 typedef <details> const_iterator;
38 noexcept(is_nothrow_default_constructible<allocator_type>::value);
39 explicit forward_list(const allocator_type& a);
40 explicit forward_list(size_type n);
41 explicit forward_list(size_type n, const allocator_type& a); // C++14
42 forward_list(size_type n, const value_type& v);
43 forward_list(size_type n, const value_type& v, const allocator_type& a);
44 template <class InputIterator>
45 forward_list(InputIterator first, InputIterator last);
46 template <class InputIterator>
47 forward_list(InputIterator first, InputIterator last, const allocator_type& a);
48 forward_list(const forward_list& x);
49 forward_list(const forward_list& x, const allocator_type& a);
50 forward_list(forward_list&& x)
51 noexcept(is_nothrow_move_constructible<allocator_type>::value);
52 forward_list(forward_list&& x, const allocator_type& a);
53 forward_list(initializer_list<value_type> il);
54 forward_list(initializer_list<value_type> il, const allocator_type& a);
58 forward_list& operator=(const forward_list& x);
59 forward_list& operator=(forward_list&& x)
61 allocator_type::propagate_on_container_move_assignment::value &&
62 is_nothrow_move_assignable<allocator_type>::value);
63 forward_list& operator=(initializer_list<value_type> il);
65 template <class InputIterator>
66 void assign(InputIterator first, InputIterator last);
67 void assign(size_type n, const value_type& v);
68 void assign(initializer_list<value_type> il);
70 allocator_type get_allocator() const noexcept;
72 iterator begin() noexcept;
73 const_iterator begin() const noexcept;
74 iterator end() noexcept;
75 const_iterator end() const noexcept;
77 const_iterator cbegin() const noexcept;
78 const_iterator cend() const noexcept;
80 iterator before_begin() noexcept;
81 const_iterator before_begin() const noexcept;
82 const_iterator cbefore_begin() const noexcept;
84 bool empty() const noexcept;
85 size_type max_size() const noexcept;
88 const_reference front() const;
90 template <class... Args> reference emplace_front(Args&&... args); // reference in C++17
91 void push_front(const value_type& v);
92 void push_front(value_type&& v);
96 template <class... Args>
97 iterator emplace_after(const_iterator p, Args&&... args);
98 iterator insert_after(const_iterator p, const value_type& v);
99 iterator insert_after(const_iterator p, value_type&& v);
100 iterator insert_after(const_iterator p, size_type n, const value_type& v);
101 template <class InputIterator>
102 iterator insert_after(const_iterator p,
103 InputIterator first, InputIterator last);
104 iterator insert_after(const_iterator p, initializer_list<value_type> il);
106 iterator erase_after(const_iterator p);
107 iterator erase_after(const_iterator first, const_iterator last);
109 void swap(forward_list& x)
110 noexcept(allocator_traits<allocator_type>::is_always_equal::value); // C++17
112 void resize(size_type n);
113 void resize(size_type n, const value_type& v);
114 void clear() noexcept;
116 void splice_after(const_iterator p, forward_list& x);
117 void splice_after(const_iterator p, forward_list&& x);
118 void splice_after(const_iterator p, forward_list& x, const_iterator i);
119 void splice_after(const_iterator p, forward_list&& x, const_iterator i);
120 void splice_after(const_iterator p, forward_list& x,
121 const_iterator first, const_iterator last);
122 void splice_after(const_iterator p, forward_list&& x,
123 const_iterator first, const_iterator last);
124 void remove(const value_type& v);
125 template <class Predicate> void remove_if(Predicate pred);
127 template <class BinaryPredicate> void unique(BinaryPredicate binary_pred);
128 void merge(forward_list& x);
129 void merge(forward_list&& x);
130 template <class Compare> void merge(forward_list& x, Compare comp);
131 template <class Compare> void merge(forward_list&& x, Compare comp);
133 template <class Compare> void sort(Compare comp);
134 void reverse() noexcept;
137 template <class T, class Allocator>
138 bool operator==(const forward_list<T, Allocator>& x,
139 const forward_list<T, Allocator>& y);
141 template <class T, class Allocator>
142 bool operator< (const forward_list<T, Allocator>& x,
143 const forward_list<T, Allocator>& y);
145 template <class T, class Allocator>
146 bool operator!=(const forward_list<T, Allocator>& x,
147 const forward_list<T, Allocator>& y);
149 template <class T, class Allocator>
150 bool operator> (const forward_list<T, Allocator>& x,
151 const forward_list<T, Allocator>& y);
153 template <class T, class Allocator>
154 bool operator>=(const forward_list<T, Allocator>& x,
155 const forward_list<T, Allocator>& y);
157 template <class T, class Allocator>
158 bool operator<=(const forward_list<T, Allocator>& x,
159 const forward_list<T, Allocator>& y);
161 template <class T, class Allocator>
162 void swap(forward_list<T, Allocator>& x, forward_list<T, Allocator>& y)
163 noexcept(noexcept(x.swap(y)));
170 #include <initializer_list>
176 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
177 #pragma GCC system_header
181 #include <__undef_macros>
184 _LIBCPP_BEGIN_NAMESPACE_STD
186 template <class _Tp, class _VoidPtr> struct __forward_list_node;
187 template <class _NodePtr> struct __forward_begin_node;
191 struct __forward_list_node_value_type;
193 template <class _Tp, class _VoidPtr>
194 struct __forward_list_node_value_type<__forward_list_node<_Tp, _VoidPtr> > {
198 template <class _NodePtr>
199 struct __forward_node_traits {
201 typedef typename remove_cv<
202 typename pointer_traits<_NodePtr>::element_type>::type __node;
203 typedef typename __forward_list_node_value_type<__node>::type __node_value_type;
204 typedef _NodePtr __node_pointer;
205 typedef __forward_begin_node<_NodePtr> __begin_node;
206 typedef typename __rebind_pointer<_NodePtr, __begin_node>::type
207 __begin_node_pointer;
208 typedef typename __rebind_pointer<_NodePtr, void>::type __void_pointer;
210 #if defined(_LIBCPP_ABI_FORWARD_LIST_REMOVE_NODE_POINTER_UB)
211 typedef __begin_node_pointer __iter_node_pointer;
213 typedef typename conditional<
214 is_pointer<__void_pointer>::value,
215 __begin_node_pointer,
217 >::type __iter_node_pointer;
220 typedef typename conditional<
221 is_same<__iter_node_pointer, __node_pointer>::value,
222 __begin_node_pointer,
224 >::type __non_iter_node_pointer;
226 _LIBCPP_INLINE_VISIBILITY
227 static __iter_node_pointer __as_iter_node(__iter_node_pointer __p) {
230 _LIBCPP_INLINE_VISIBILITY
231 static __iter_node_pointer __as_iter_node(__non_iter_node_pointer __p) {
232 return static_cast<__iter_node_pointer>(static_cast<__void_pointer>(__p));
236 template <class _NodePtr>
237 struct __forward_begin_node
239 typedef _NodePtr pointer;
240 typedef typename __rebind_pointer<_NodePtr, __forward_begin_node>::type __begin_node_pointer;
244 _LIBCPP_INLINE_VISIBILITY __forward_begin_node() : __next_(nullptr) {}
246 _LIBCPP_INLINE_VISIBILITY
247 __begin_node_pointer __next_as_begin() const {
248 return static_cast<__begin_node_pointer>(__next_);
252 template <class _Tp, class _VoidPtr>
253 struct _LIBCPP_HIDDEN __begin_node_of
255 typedef __forward_begin_node<
256 typename __rebind_pointer<_VoidPtr, __forward_list_node<_Tp, _VoidPtr> >::type
260 template <class _Tp, class _VoidPtr>
261 struct __forward_list_node
262 : public __begin_node_of<_Tp, _VoidPtr>::type
264 typedef _Tp value_type;
270 template <class _Tp, class _Alloc = allocator<_Tp> > class _LIBCPP_TEMPLATE_VIS forward_list;
271 template<class _NodeConstPtr> class _LIBCPP_TEMPLATE_VIS __forward_list_const_iterator;
273 template <class _NodePtr>
274 class _LIBCPP_TEMPLATE_VIS __forward_list_iterator
276 typedef __forward_node_traits<_NodePtr> __traits;
277 typedef typename __traits::__node_pointer __node_pointer;
278 typedef typename __traits::__begin_node_pointer __begin_node_pointer;
279 typedef typename __traits::__iter_node_pointer __iter_node_pointer;
280 typedef typename __traits::__void_pointer __void_pointer;
282 __iter_node_pointer __ptr_;
284 _LIBCPP_INLINE_VISIBILITY
285 __begin_node_pointer __get_begin() const {
286 return static_cast<__begin_node_pointer>(
287 static_cast<__void_pointer>(__ptr_));
289 _LIBCPP_INLINE_VISIBILITY
290 __node_pointer __get_unsafe_node_pointer() const {
291 return static_cast<__node_pointer>(
292 static_cast<__void_pointer>(__ptr_));
295 _LIBCPP_INLINE_VISIBILITY
296 explicit __forward_list_iterator(nullptr_t) _NOEXCEPT : __ptr_(nullptr) {}
298 _LIBCPP_INLINE_VISIBILITY
299 explicit __forward_list_iterator(__begin_node_pointer __p) _NOEXCEPT
300 : __ptr_(__traits::__as_iter_node(__p)) {}
302 _LIBCPP_INLINE_VISIBILITY
303 explicit __forward_list_iterator(__node_pointer __p) _NOEXCEPT
304 : __ptr_(__traits::__as_iter_node(__p)) {}
306 template<class, class> friend class _LIBCPP_TEMPLATE_VIS forward_list;
307 template<class> friend class _LIBCPP_TEMPLATE_VIS __forward_list_const_iterator;
310 typedef forward_iterator_tag iterator_category;
311 typedef typename __traits::__node_value_type value_type;
312 typedef value_type& reference;
313 typedef typename pointer_traits<__node_pointer>::difference_type
315 typedef typename __rebind_pointer<__node_pointer, value_type>::type pointer;
317 _LIBCPP_INLINE_VISIBILITY
318 __forward_list_iterator() _NOEXCEPT : __ptr_(nullptr) {}
320 _LIBCPP_INLINE_VISIBILITY
321 reference operator*() const {return __get_unsafe_node_pointer()->__value_;}
322 _LIBCPP_INLINE_VISIBILITY
323 pointer operator->() const {
324 return pointer_traits<pointer>::pointer_to(__get_unsafe_node_pointer()->__value_);
327 _LIBCPP_INLINE_VISIBILITY
328 __forward_list_iterator& operator++()
330 __ptr_ = __traits::__as_iter_node(__ptr_->__next_);
333 _LIBCPP_INLINE_VISIBILITY
334 __forward_list_iterator operator++(int)
336 __forward_list_iterator __t(*this);
341 friend _LIBCPP_INLINE_VISIBILITY
342 bool operator==(const __forward_list_iterator& __x,
343 const __forward_list_iterator& __y)
344 {return __x.__ptr_ == __y.__ptr_;}
345 friend _LIBCPP_INLINE_VISIBILITY
346 bool operator!=(const __forward_list_iterator& __x,
347 const __forward_list_iterator& __y)
348 {return !(__x == __y);}
351 template <class _NodeConstPtr>
352 class _LIBCPP_TEMPLATE_VIS __forward_list_const_iterator
354 static_assert((!is_const<typename pointer_traits<_NodeConstPtr>::element_type>::value), "");
355 typedef _NodeConstPtr _NodePtr;
357 typedef __forward_node_traits<_NodePtr> __traits;
358 typedef typename __traits::__node __node;
359 typedef typename __traits::__node_pointer __node_pointer;
360 typedef typename __traits::__begin_node_pointer __begin_node_pointer;
361 typedef typename __traits::__iter_node_pointer __iter_node_pointer;
362 typedef typename __traits::__void_pointer __void_pointer;
364 __iter_node_pointer __ptr_;
366 __begin_node_pointer __get_begin() const {
367 return static_cast<__begin_node_pointer>(
368 static_cast<__void_pointer>(__ptr_));
370 __node_pointer __get_unsafe_node_pointer() const {
371 return static_cast<__node_pointer>(
372 static_cast<__void_pointer>(__ptr_));
375 _LIBCPP_INLINE_VISIBILITY
376 explicit __forward_list_const_iterator(nullptr_t) _NOEXCEPT
379 _LIBCPP_INLINE_VISIBILITY
380 explicit __forward_list_const_iterator(__begin_node_pointer __p) _NOEXCEPT
381 : __ptr_(__traits::__as_iter_node(__p)) {}
383 _LIBCPP_INLINE_VISIBILITY
384 explicit __forward_list_const_iterator(__node_pointer __p) _NOEXCEPT
385 : __ptr_(__traits::__as_iter_node(__p)) {}
388 template<class, class> friend class forward_list;
391 typedef forward_iterator_tag iterator_category;
392 typedef typename __traits::__node_value_type value_type;
393 typedef const value_type& reference;
394 typedef typename pointer_traits<__node_pointer>::difference_type
396 typedef typename __rebind_pointer<__node_pointer, const value_type>::type
399 _LIBCPP_INLINE_VISIBILITY
400 __forward_list_const_iterator() _NOEXCEPT : __ptr_(nullptr) {}
401 _LIBCPP_INLINE_VISIBILITY
402 __forward_list_const_iterator(__forward_list_iterator<__node_pointer> __p) _NOEXCEPT
403 : __ptr_(__p.__ptr_) {}
405 _LIBCPP_INLINE_VISIBILITY
406 reference operator*() const {return __get_unsafe_node_pointer()->__value_;}
407 _LIBCPP_INLINE_VISIBILITY
408 pointer operator->() const {return pointer_traits<pointer>::pointer_to(
409 __get_unsafe_node_pointer()->__value_);}
411 _LIBCPP_INLINE_VISIBILITY
412 __forward_list_const_iterator& operator++()
414 __ptr_ = __traits::__as_iter_node(__ptr_->__next_);
417 _LIBCPP_INLINE_VISIBILITY
418 __forward_list_const_iterator operator++(int)
420 __forward_list_const_iterator __t(*this);
425 friend _LIBCPP_INLINE_VISIBILITY
426 bool operator==(const __forward_list_const_iterator& __x,
427 const __forward_list_const_iterator& __y)
428 {return __x.__ptr_ == __y.__ptr_;}
429 friend _LIBCPP_INLINE_VISIBILITY
430 bool operator!=(const __forward_list_const_iterator& __x,
431 const __forward_list_const_iterator& __y)
432 {return !(__x == __y);}
435 template <class _Tp, class _Alloc>
436 class __forward_list_base
439 typedef _Tp value_type;
440 typedef _Alloc allocator_type;
442 typedef typename allocator_traits<allocator_type>::void_pointer void_pointer;
443 typedef __forward_list_node<value_type, void_pointer> __node;
444 typedef typename __begin_node_of<value_type, void_pointer>::type __begin_node;
445 typedef typename __rebind_alloc_helper<allocator_traits<allocator_type>, __node>::type __node_allocator;
446 typedef allocator_traits<__node_allocator> __node_traits;
447 typedef typename __node_traits::pointer __node_pointer;
449 typedef typename __rebind_alloc_helper<
450 allocator_traits<allocator_type>, __begin_node
451 >::type __begin_node_allocator;
452 typedef typename allocator_traits<__begin_node_allocator>::pointer
453 __begin_node_pointer;
455 __compressed_pair<__begin_node, __node_allocator> __before_begin_;
457 _LIBCPP_INLINE_VISIBILITY
458 __begin_node_pointer __before_begin() _NOEXCEPT
459 {return pointer_traits<__begin_node_pointer>::pointer_to(__before_begin_.first());}
460 _LIBCPP_INLINE_VISIBILITY
461 __begin_node_pointer __before_begin() const _NOEXCEPT
462 {return pointer_traits<__begin_node_pointer>::pointer_to(const_cast<__begin_node&>(__before_begin_.first()));}
464 _LIBCPP_INLINE_VISIBILITY
465 __node_allocator& __alloc() _NOEXCEPT
466 {return __before_begin_.second();}
467 _LIBCPP_INLINE_VISIBILITY
468 const __node_allocator& __alloc() const _NOEXCEPT
469 {return __before_begin_.second();}
471 typedef __forward_list_iterator<__node_pointer> iterator;
472 typedef __forward_list_const_iterator<__node_pointer> const_iterator;
474 _LIBCPP_INLINE_VISIBILITY
475 __forward_list_base()
476 _NOEXCEPT_(is_nothrow_default_constructible<__node_allocator>::value)
477 : __before_begin_(__begin_node()) {}
478 _LIBCPP_INLINE_VISIBILITY
479 __forward_list_base(const allocator_type& __a)
480 : __before_begin_(__begin_node(), __node_allocator(__a)) {}
482 #ifndef _LIBCPP_CXX03_LANG
484 _LIBCPP_INLINE_VISIBILITY
485 __forward_list_base(__forward_list_base&& __x)
486 _NOEXCEPT_(is_nothrow_move_constructible<__node_allocator>::value);
487 _LIBCPP_INLINE_VISIBILITY
488 __forward_list_base(__forward_list_base&& __x, const allocator_type& __a);
489 #endif // _LIBCPP_CXX03_LANG
492 __forward_list_base(const __forward_list_base&);
493 __forward_list_base& operator=(const __forward_list_base&);
496 ~__forward_list_base();
499 _LIBCPP_INLINE_VISIBILITY
500 void __copy_assign_alloc(const __forward_list_base& __x)
501 {__copy_assign_alloc(__x, integral_constant<bool,
502 __node_traits::propagate_on_container_copy_assignment::value>());}
504 _LIBCPP_INLINE_VISIBILITY
505 void __move_assign_alloc(__forward_list_base& __x)
506 _NOEXCEPT_(!__node_traits::propagate_on_container_move_assignment::value ||
507 is_nothrow_move_assignable<__node_allocator>::value)
508 {__move_assign_alloc(__x, integral_constant<bool,
509 __node_traits::propagate_on_container_move_assignment::value>());}
512 _LIBCPP_INLINE_VISIBILITY
513 void swap(__forward_list_base& __x)
514 #if _LIBCPP_STD_VER >= 14
517 _NOEXCEPT_(!__node_traits::propagate_on_container_move_assignment::value ||
518 __is_nothrow_swappable<__node_allocator>::value);
521 void clear() _NOEXCEPT;
524 _LIBCPP_INLINE_VISIBILITY
525 void __copy_assign_alloc(const __forward_list_base&, false_type) {}
526 _LIBCPP_INLINE_VISIBILITY
527 void __copy_assign_alloc(const __forward_list_base& __x, true_type)
529 if (__alloc() != __x.__alloc())
531 __alloc() = __x.__alloc();
534 _LIBCPP_INLINE_VISIBILITY
535 void __move_assign_alloc(__forward_list_base&, false_type) _NOEXCEPT
537 _LIBCPP_INLINE_VISIBILITY
538 void __move_assign_alloc(__forward_list_base& __x, true_type)
539 _NOEXCEPT_(is_nothrow_move_assignable<__node_allocator>::value)
540 {__alloc() = _VSTD::move(__x.__alloc());}
543 #ifndef _LIBCPP_CXX03_LANG
545 template <class _Tp, class _Alloc>
547 __forward_list_base<_Tp, _Alloc>::__forward_list_base(__forward_list_base&& __x)
548 _NOEXCEPT_(is_nothrow_move_constructible<__node_allocator>::value)
549 : __before_begin_(_VSTD::move(__x.__before_begin_))
551 __x.__before_begin()->__next_ = nullptr;
554 template <class _Tp, class _Alloc>
556 __forward_list_base<_Tp, _Alloc>::__forward_list_base(__forward_list_base&& __x,
557 const allocator_type& __a)
558 : __before_begin_(__begin_node(), __node_allocator(__a))
560 if (__alloc() == __x.__alloc())
562 __before_begin()->__next_ = __x.__before_begin()->__next_;
563 __x.__before_begin()->__next_ = nullptr;
567 #endif // _LIBCPP_CXX03_LANG
569 template <class _Tp, class _Alloc>
570 __forward_list_base<_Tp, _Alloc>::~__forward_list_base()
575 template <class _Tp, class _Alloc>
578 __forward_list_base<_Tp, _Alloc>::swap(__forward_list_base& __x)
579 #if _LIBCPP_STD_VER >= 14
582 _NOEXCEPT_(!__node_traits::propagate_on_container_move_assignment::value ||
583 __is_nothrow_swappable<__node_allocator>::value)
586 __swap_allocator(__alloc(), __x.__alloc(),
587 integral_constant<bool, __node_traits::propagate_on_container_swap::value>());
589 swap(__before_begin()->__next_, __x.__before_begin()->__next_);
592 template <class _Tp, class _Alloc>
594 __forward_list_base<_Tp, _Alloc>::clear() _NOEXCEPT
596 __node_allocator& __a = __alloc();
597 for (__node_pointer __p = __before_begin()->__next_; __p != nullptr;)
599 __node_pointer __next = __p->__next_;
600 __node_traits::destroy(__a, _VSTD::addressof(__p->__value_));
601 __node_traits::deallocate(__a, __p, 1);
604 __before_begin()->__next_ = nullptr;
607 template <class _Tp, class _Alloc /*= allocator<_Tp>*/>
608 class _LIBCPP_TEMPLATE_VIS forward_list
609 : private __forward_list_base<_Tp, _Alloc>
611 typedef __forward_list_base<_Tp, _Alloc> base;
612 typedef typename base::__node_allocator __node_allocator;
613 typedef typename base::__node __node;
614 typedef typename base::__node_traits __node_traits;
615 typedef typename base::__node_pointer __node_pointer;
616 typedef typename base::__begin_node_pointer __begin_node_pointer;
619 typedef _Tp value_type;
620 typedef _Alloc allocator_type;
622 static_assert((is_same<typename allocator_type::value_type, value_type>::value),
623 "Allocator::value_type must be same type as value_type");
625 typedef value_type& reference;
626 typedef const value_type& const_reference;
627 typedef typename allocator_traits<allocator_type>::pointer pointer;
628 typedef typename allocator_traits<allocator_type>::const_pointer const_pointer;
629 typedef typename allocator_traits<allocator_type>::size_type size_type;
630 typedef typename allocator_traits<allocator_type>::difference_type difference_type;
632 typedef typename base::iterator iterator;
633 typedef typename base::const_iterator const_iterator;
635 _LIBCPP_INLINE_VISIBILITY
637 _NOEXCEPT_(is_nothrow_default_constructible<__node_allocator>::value)
639 _LIBCPP_INLINE_VISIBILITY
640 explicit forward_list(const allocator_type& __a);
641 explicit forward_list(size_type __n);
642 #if _LIBCPP_STD_VER > 11
643 explicit forward_list(size_type __n, const allocator_type& __a);
645 forward_list(size_type __n, const value_type& __v);
646 forward_list(size_type __n, const value_type& __v, const allocator_type& __a);
647 template <class _InputIterator>
648 forward_list(_InputIterator __f, _InputIterator __l,
650 __is_input_iterator<_InputIterator>::value
652 template <class _InputIterator>
653 forward_list(_InputIterator __f, _InputIterator __l,
654 const allocator_type& __a,
656 __is_input_iterator<_InputIterator>::value
658 forward_list(const forward_list& __x);
659 forward_list(const forward_list& __x, const allocator_type& __a);
661 forward_list& operator=(const forward_list& __x);
663 #ifndef _LIBCPP_CXX03_LANG
664 _LIBCPP_INLINE_VISIBILITY
665 forward_list(forward_list&& __x)
666 _NOEXCEPT_(is_nothrow_move_constructible<base>::value)
667 : base(_VSTD::move(__x)) {}
668 forward_list(forward_list&& __x, const allocator_type& __a);
670 forward_list(initializer_list<value_type> __il);
671 forward_list(initializer_list<value_type> __il, const allocator_type& __a);
673 _LIBCPP_INLINE_VISIBILITY
674 forward_list& operator=(forward_list&& __x)
676 __node_traits::propagate_on_container_move_assignment::value &&
677 is_nothrow_move_assignable<allocator_type>::value);
679 _LIBCPP_INLINE_VISIBILITY
680 forward_list& operator=(initializer_list<value_type> __il);
682 _LIBCPP_INLINE_VISIBILITY
683 void assign(initializer_list<value_type> __il);
684 #endif // _LIBCPP_CXX03_LANG
686 // ~forward_list() = default;
688 template <class _InputIterator>
691 __is_input_iterator<_InputIterator>::value,
694 assign(_InputIterator __f, _InputIterator __l);
695 void assign(size_type __n, const value_type& __v);
697 _LIBCPP_INLINE_VISIBILITY
698 allocator_type get_allocator() const _NOEXCEPT
699 {return allocator_type(base::__alloc());}
701 _LIBCPP_INLINE_VISIBILITY
702 iterator begin() _NOEXCEPT
703 {return iterator(base::__before_begin()->__next_);}
704 _LIBCPP_INLINE_VISIBILITY
705 const_iterator begin() const _NOEXCEPT
706 {return const_iterator(base::__before_begin()->__next_);}
707 _LIBCPP_INLINE_VISIBILITY
708 iterator end() _NOEXCEPT
709 {return iterator(nullptr);}
710 _LIBCPP_INLINE_VISIBILITY
711 const_iterator end() const _NOEXCEPT
712 {return const_iterator(nullptr);}
714 _LIBCPP_INLINE_VISIBILITY
715 const_iterator cbegin() const _NOEXCEPT
716 {return const_iterator(base::__before_begin()->__next_);}
717 _LIBCPP_INLINE_VISIBILITY
718 const_iterator cend() const _NOEXCEPT
719 {return const_iterator(nullptr);}
721 _LIBCPP_INLINE_VISIBILITY
722 iterator before_begin() _NOEXCEPT
723 {return iterator(base::__before_begin());}
724 _LIBCPP_INLINE_VISIBILITY
725 const_iterator before_begin() const _NOEXCEPT
726 {return const_iterator(base::__before_begin());}
727 _LIBCPP_INLINE_VISIBILITY
728 const_iterator cbefore_begin() const _NOEXCEPT
729 {return const_iterator(base::__before_begin());}
731 _LIBCPP_NODISCARD_AFTER_CXX17 _LIBCPP_INLINE_VISIBILITY
732 bool empty() const _NOEXCEPT
733 {return base::__before_begin()->__next_ == nullptr;}
734 _LIBCPP_INLINE_VISIBILITY
735 size_type max_size() const _NOEXCEPT {
736 return std::min<size_type>(
737 __node_traits::max_size(base::__alloc()),
738 numeric_limits<difference_type>::max());
741 _LIBCPP_INLINE_VISIBILITY
742 reference front() {return base::__before_begin()->__next_->__value_;}
743 _LIBCPP_INLINE_VISIBILITY
744 const_reference front() const {return base::__before_begin()->__next_->__value_;}
746 #ifndef _LIBCPP_CXX03_LANG
747 #if _LIBCPP_STD_VER > 14
748 template <class... _Args> reference emplace_front(_Args&&... __args);
750 template <class... _Args> void emplace_front(_Args&&... __args);
752 void push_front(value_type&& __v);
753 #endif // _LIBCPP_CXX03_LANG
754 void push_front(const value_type& __v);
758 #ifndef _LIBCPP_CXX03_LANG
759 template <class... _Args>
760 iterator emplace_after(const_iterator __p, _Args&&... __args);
762 iterator insert_after(const_iterator __p, value_type&& __v);
763 iterator insert_after(const_iterator __p, initializer_list<value_type> __il)
764 {return insert_after(__p, __il.begin(), __il.end());}
765 #endif // _LIBCPP_CXX03_LANG
766 iterator insert_after(const_iterator __p, const value_type& __v);
767 iterator insert_after(const_iterator __p, size_type __n, const value_type& __v);
768 template <class _InputIterator>
769 _LIBCPP_INLINE_VISIBILITY
772 __is_input_iterator<_InputIterator>::value,
775 insert_after(const_iterator __p, _InputIterator __f, _InputIterator __l);
777 iterator erase_after(const_iterator __p);
778 iterator erase_after(const_iterator __f, const_iterator __l);
780 _LIBCPP_INLINE_VISIBILITY
781 void swap(forward_list& __x)
782 #if _LIBCPP_STD_VER >= 14
785 _NOEXCEPT_(!__node_traits::propagate_on_container_swap::value ||
786 __is_nothrow_swappable<__node_allocator>::value)
790 void resize(size_type __n);
791 void resize(size_type __n, const value_type& __v);
792 _LIBCPP_INLINE_VISIBILITY
793 void clear() _NOEXCEPT {base::clear();}
795 #ifndef _LIBCPP_CXX03_LANG
796 _LIBCPP_INLINE_VISIBILITY
797 void splice_after(const_iterator __p, forward_list&& __x);
798 _LIBCPP_INLINE_VISIBILITY
799 void splice_after(const_iterator __p, forward_list&& __x, const_iterator __i);
800 _LIBCPP_INLINE_VISIBILITY
801 void splice_after(const_iterator __p, forward_list&& __x,
802 const_iterator __f, const_iterator __l);
803 #endif // _LIBCPP_CXX03_LANG
804 void splice_after(const_iterator __p, forward_list& __x);
805 void splice_after(const_iterator __p, forward_list& __x, const_iterator __i);
806 void splice_after(const_iterator __p, forward_list& __x,
807 const_iterator __f, const_iterator __l);
808 void remove(const value_type& __v);
809 template <class _Predicate> void remove_if(_Predicate __pred);
810 _LIBCPP_INLINE_VISIBILITY
811 void unique() {unique(__equal_to<value_type>());}
812 template <class _BinaryPredicate> void unique(_BinaryPredicate __binary_pred);
813 #ifndef _LIBCPP_CXX03_LANG
814 _LIBCPP_INLINE_VISIBILITY
815 void merge(forward_list&& __x) {merge(__x, __less<value_type>());}
816 template <class _Compare>
817 _LIBCPP_INLINE_VISIBILITY
818 void merge(forward_list&& __x, _Compare __comp)
819 {merge(__x, _VSTD::move(__comp));}
820 #endif // _LIBCPP_CXX03_LANG
821 _LIBCPP_INLINE_VISIBILITY
822 void merge(forward_list& __x) {merge(__x, __less<value_type>());}
823 template <class _Compare> void merge(forward_list& __x, _Compare __comp);
824 _LIBCPP_INLINE_VISIBILITY
825 void sort() {sort(__less<value_type>());}
826 template <class _Compare> _LIBCPP_INLINE_VISIBILITY void sort(_Compare __comp);
827 void reverse() _NOEXCEPT;
831 #ifndef _LIBCPP_CXX03_LANG
832 void __move_assign(forward_list& __x, true_type)
833 _NOEXCEPT_(is_nothrow_move_assignable<allocator_type>::value);
834 void __move_assign(forward_list& __x, false_type);
835 #endif // _LIBCPP_CXX03_LANG
837 template <class _Compare>
840 __merge(__node_pointer __f1, __node_pointer __f2, _Compare& __comp);
842 template <class _Compare>
845 __sort(__node_pointer __f, difference_type __sz, _Compare& __comp);
848 template <class _Tp, class _Alloc>
850 forward_list<_Tp, _Alloc>::forward_list(const allocator_type& __a)
855 template <class _Tp, class _Alloc>
856 forward_list<_Tp, _Alloc>::forward_list(size_type __n)
860 __node_allocator& __a = base::__alloc();
861 typedef __allocator_destructor<__node_allocator> _Dp;
862 unique_ptr<__node, _Dp> __h(nullptr, _Dp(__a, 1));
863 for (__begin_node_pointer __p = base::__before_begin(); __n > 0; --__n,
864 __p = __p->__next_as_begin())
866 __h.reset(__node_traits::allocate(__a, 1));
867 __node_traits::construct(__a, _VSTD::addressof(__h->__value_));
868 __h->__next_ = nullptr;
869 __p->__next_ = __h.release();
874 #if _LIBCPP_STD_VER > 11
875 template <class _Tp, class _Alloc>
876 forward_list<_Tp, _Alloc>::forward_list(size_type __n,
877 const allocator_type& __base_alloc)
878 : base ( __base_alloc )
882 __node_allocator& __a = base::__alloc();
883 typedef __allocator_destructor<__node_allocator> _Dp;
884 unique_ptr<__node, _Dp> __h(nullptr, _Dp(__a, 1));
885 for (__begin_node_pointer __p = base::__before_begin(); __n > 0; --__n,
886 __p = __p->__next_as_begin())
888 __h.reset(__node_traits::allocate(__a, 1));
889 __node_traits::construct(__a, _VSTD::addressof(__h->__value_));
890 __h->__next_ = nullptr;
891 __p->__next_ = __h.release();
897 template <class _Tp, class _Alloc>
898 forward_list<_Tp, _Alloc>::forward_list(size_type __n, const value_type& __v)
900 insert_after(cbefore_begin(), __n, __v);
903 template <class _Tp, class _Alloc>
904 forward_list<_Tp, _Alloc>::forward_list(size_type __n, const value_type& __v,
905 const allocator_type& __a)
908 insert_after(cbefore_begin(), __n, __v);
911 template <class _Tp, class _Alloc>
912 template <class _InputIterator>
913 forward_list<_Tp, _Alloc>::forward_list(_InputIterator __f, _InputIterator __l,
915 __is_input_iterator<_InputIterator>::value
918 insert_after(cbefore_begin(), __f, __l);
921 template <class _Tp, class _Alloc>
922 template <class _InputIterator>
923 forward_list<_Tp, _Alloc>::forward_list(_InputIterator __f, _InputIterator __l,
924 const allocator_type& __a,
926 __is_input_iterator<_InputIterator>::value
930 insert_after(cbefore_begin(), __f, __l);
933 template <class _Tp, class _Alloc>
934 forward_list<_Tp, _Alloc>::forward_list(const forward_list& __x)
935 : base(allocator_type(
936 __node_traits::select_on_container_copy_construction(__x.__alloc())
940 insert_after(cbefore_begin(), __x.begin(), __x.end());
943 template <class _Tp, class _Alloc>
944 forward_list<_Tp, _Alloc>::forward_list(const forward_list& __x,
945 const allocator_type& __a)
948 insert_after(cbefore_begin(), __x.begin(), __x.end());
951 template <class _Tp, class _Alloc>
952 forward_list<_Tp, _Alloc>&
953 forward_list<_Tp, _Alloc>::operator=(const forward_list& __x)
957 base::__copy_assign_alloc(__x);
958 assign(__x.begin(), __x.end());
963 #ifndef _LIBCPP_CXX03_LANG
964 template <class _Tp, class _Alloc>
965 forward_list<_Tp, _Alloc>::forward_list(forward_list&& __x,
966 const allocator_type& __a)
967 : base(_VSTD::move(__x), __a)
969 if (base::__alloc() != __x.__alloc())
971 typedef move_iterator<iterator> _Ip;
972 insert_after(cbefore_begin(), _Ip(__x.begin()), _Ip(__x.end()));
976 template <class _Tp, class _Alloc>
977 forward_list<_Tp, _Alloc>::forward_list(initializer_list<value_type> __il)
979 insert_after(cbefore_begin(), __il.begin(), __il.end());
982 template <class _Tp, class _Alloc>
983 forward_list<_Tp, _Alloc>::forward_list(initializer_list<value_type> __il,
984 const allocator_type& __a)
987 insert_after(cbefore_begin(), __il.begin(), __il.end());
990 template <class _Tp, class _Alloc>
992 forward_list<_Tp, _Alloc>::__move_assign(forward_list& __x, true_type)
993 _NOEXCEPT_(is_nothrow_move_assignable<allocator_type>::value)
996 base::__move_assign_alloc(__x);
997 base::__before_begin()->__next_ = __x.__before_begin()->__next_;
998 __x.__before_begin()->__next_ = nullptr;
1001 template <class _Tp, class _Alloc>
1003 forward_list<_Tp, _Alloc>::__move_assign(forward_list& __x, false_type)
1005 if (base::__alloc() == __x.__alloc())
1006 __move_assign(__x, true_type());
1009 typedef move_iterator<iterator> _Ip;
1010 assign(_Ip(__x.begin()), _Ip(__x.end()));
1014 template <class _Tp, class _Alloc>
1016 forward_list<_Tp, _Alloc>&
1017 forward_list<_Tp, _Alloc>::operator=(forward_list&& __x)
1019 __node_traits::propagate_on_container_move_assignment::value &&
1020 is_nothrow_move_assignable<allocator_type>::value)
1022 __move_assign(__x, integral_constant<bool,
1023 __node_traits::propagate_on_container_move_assignment::value>());
1027 template <class _Tp, class _Alloc>
1029 forward_list<_Tp, _Alloc>&
1030 forward_list<_Tp, _Alloc>::operator=(initializer_list<value_type> __il)
1032 assign(__il.begin(), __il.end());
1036 #endif // _LIBCPP_CXX03_LANG
1038 template <class _Tp, class _Alloc>
1039 template <class _InputIterator>
1042 __is_input_iterator<_InputIterator>::value,
1045 forward_list<_Tp, _Alloc>::assign(_InputIterator __f, _InputIterator __l)
1047 iterator __i = before_begin();
1048 iterator __j = _VSTD::next(__i);
1049 iterator __e = end();
1050 for (; __j != __e && __f != __l; ++__i, (void) ++__j, ++__f)
1053 insert_after(__i, __f, __l);
1055 erase_after(__i, __e);
1058 template <class _Tp, class _Alloc>
1060 forward_list<_Tp, _Alloc>::assign(size_type __n, const value_type& __v)
1062 iterator __i = before_begin();
1063 iterator __j = _VSTD::next(__i);
1064 iterator __e = end();
1065 for (; __j != __e && __n > 0; --__n, ++__i, ++__j)
1068 insert_after(__i, __n, __v);
1070 erase_after(__i, __e);
1073 #ifndef _LIBCPP_CXX03_LANG
1075 template <class _Tp, class _Alloc>
1078 forward_list<_Tp, _Alloc>::assign(initializer_list<value_type> __il)
1080 assign(__il.begin(), __il.end());
1083 template <class _Tp, class _Alloc>
1084 template <class... _Args>
1085 #if _LIBCPP_STD_VER > 14
1086 typename forward_list<_Tp, _Alloc>::reference
1090 forward_list<_Tp, _Alloc>::emplace_front(_Args&&... __args)
1092 __node_allocator& __a = base::__alloc();
1093 typedef __allocator_destructor<__node_allocator> _Dp;
1094 unique_ptr<__node, _Dp> __h(__node_traits::allocate(__a, 1), _Dp(__a, 1));
1095 __node_traits::construct(__a, _VSTD::addressof(__h->__value_),
1096 _VSTD::forward<_Args>(__args)...);
1097 __h->__next_ = base::__before_begin()->__next_;
1098 base::__before_begin()->__next_ = __h.release();
1099 #if _LIBCPP_STD_VER > 14
1100 return base::__before_begin()->__next_->__value_;
1104 template <class _Tp, class _Alloc>
1106 forward_list<_Tp, _Alloc>::push_front(value_type&& __v)
1108 __node_allocator& __a = base::__alloc();
1109 typedef __allocator_destructor<__node_allocator> _Dp;
1110 unique_ptr<__node, _Dp> __h(__node_traits::allocate(__a, 1), _Dp(__a, 1));
1111 __node_traits::construct(__a, _VSTD::addressof(__h->__value_), _VSTD::move(__v));
1112 __h->__next_ = base::__before_begin()->__next_;
1113 base::__before_begin()->__next_ = __h.release();
1116 #endif // _LIBCPP_CXX03_LANG
1118 template <class _Tp, class _Alloc>
1120 forward_list<_Tp, _Alloc>::push_front(const value_type& __v)
1122 __node_allocator& __a = base::__alloc();
1123 typedef __allocator_destructor<__node_allocator> _Dp;
1124 unique_ptr<__node, _Dp> __h(__node_traits::allocate(__a, 1), _Dp(__a, 1));
1125 __node_traits::construct(__a, _VSTD::addressof(__h->__value_), __v);
1126 __h->__next_ = base::__before_begin()->__next_;
1127 base::__before_begin()->__next_ = __h.release();
1130 template <class _Tp, class _Alloc>
1132 forward_list<_Tp, _Alloc>::pop_front()
1134 __node_allocator& __a = base::__alloc();
1135 __node_pointer __p = base::__before_begin()->__next_;
1136 base::__before_begin()->__next_ = __p->__next_;
1137 __node_traits::destroy(__a, _VSTD::addressof(__p->__value_));
1138 __node_traits::deallocate(__a, __p, 1);
1141 #ifndef _LIBCPP_CXX03_LANG
1143 template <class _Tp, class _Alloc>
1144 template <class... _Args>
1145 typename forward_list<_Tp, _Alloc>::iterator
1146 forward_list<_Tp, _Alloc>::emplace_after(const_iterator __p, _Args&&... __args)
1148 __begin_node_pointer const __r = __p.__get_begin();
1149 __node_allocator& __a = base::__alloc();
1150 typedef __allocator_destructor<__node_allocator> _Dp;
1151 unique_ptr<__node, _Dp> __h(__node_traits::allocate(__a, 1), _Dp(__a, 1));
1152 __node_traits::construct(__a, _VSTD::addressof(__h->__value_),
1153 _VSTD::forward<_Args>(__args)...);
1154 __h->__next_ = __r->__next_;
1155 __r->__next_ = __h.release();
1156 return iterator(__r->__next_);
1159 template <class _Tp, class _Alloc>
1160 typename forward_list<_Tp, _Alloc>::iterator
1161 forward_list<_Tp, _Alloc>::insert_after(const_iterator __p, value_type&& __v)
1163 __begin_node_pointer const __r = __p.__get_begin();
1164 __node_allocator& __a = base::__alloc();
1165 typedef __allocator_destructor<__node_allocator> _Dp;
1166 unique_ptr<__node, _Dp> __h(__node_traits::allocate(__a, 1), _Dp(__a, 1));
1167 __node_traits::construct(__a, _VSTD::addressof(__h->__value_), _VSTD::move(__v));
1168 __h->__next_ = __r->__next_;
1169 __r->__next_ = __h.release();
1170 return iterator(__r->__next_);
1173 #endif // _LIBCPP_CXX03_LANG
1175 template <class _Tp, class _Alloc>
1176 typename forward_list<_Tp, _Alloc>::iterator
1177 forward_list<_Tp, _Alloc>::insert_after(const_iterator __p, const value_type& __v)
1179 __begin_node_pointer const __r = __p.__get_begin();
1180 __node_allocator& __a = base::__alloc();
1181 typedef __allocator_destructor<__node_allocator> _Dp;
1182 unique_ptr<__node, _Dp> __h(__node_traits::allocate(__a, 1), _Dp(__a, 1));
1183 __node_traits::construct(__a, _VSTD::addressof(__h->__value_), __v);
1184 __h->__next_ = __r->__next_;
1185 __r->__next_ = __h.release();
1186 return iterator(__r->__next_);
1189 template <class _Tp, class _Alloc>
1190 typename forward_list<_Tp, _Alloc>::iterator
1191 forward_list<_Tp, _Alloc>::insert_after(const_iterator __p, size_type __n,
1192 const value_type& __v)
1194 __begin_node_pointer __r = __p.__get_begin();
1197 __node_allocator& __a = base::__alloc();
1198 typedef __allocator_destructor<__node_allocator> _Dp;
1199 unique_ptr<__node, _Dp> __h(__node_traits::allocate(__a, 1), _Dp(__a, 1));
1200 __node_traits::construct(__a, _VSTD::addressof(__h->__value_), __v);
1201 __node_pointer __first = __h.release();
1202 __node_pointer __last = __first;
1203 #ifndef _LIBCPP_NO_EXCEPTIONS
1206 #endif // _LIBCPP_NO_EXCEPTIONS
1207 for (--__n; __n != 0; --__n, __last = __last->__next_)
1209 __h.reset(__node_traits::allocate(__a, 1));
1210 __node_traits::construct(__a, _VSTD::addressof(__h->__value_), __v);
1211 __last->__next_ = __h.release();
1213 #ifndef _LIBCPP_NO_EXCEPTIONS
1217 while (__first != nullptr)
1219 __node_pointer __next = __first->__next_;
1220 __node_traits::destroy(__a, _VSTD::addressof(__first->__value_));
1221 __node_traits::deallocate(__a, __first, 1);
1226 #endif // _LIBCPP_NO_EXCEPTIONS
1227 __last->__next_ = __r->__next_;
1228 __r->__next_ = __first;
1229 __r = static_cast<__begin_node_pointer>(__last);
1231 return iterator(__r);
1234 template <class _Tp, class _Alloc>
1235 template <class _InputIterator>
1238 __is_input_iterator<_InputIterator>::value,
1239 typename forward_list<_Tp, _Alloc>::iterator
1241 forward_list<_Tp, _Alloc>::insert_after(const_iterator __p,
1242 _InputIterator __f, _InputIterator __l)
1244 __begin_node_pointer __r = __p.__get_begin();
1247 __node_allocator& __a = base::__alloc();
1248 typedef __allocator_destructor<__node_allocator> _Dp;
1249 unique_ptr<__node, _Dp> __h(__node_traits::allocate(__a, 1), _Dp(__a, 1));
1250 __node_traits::construct(__a, _VSTD::addressof(__h->__value_), *__f);
1251 __node_pointer __first = __h.release();
1252 __node_pointer __last = __first;
1253 #ifndef _LIBCPP_NO_EXCEPTIONS
1256 #endif // _LIBCPP_NO_EXCEPTIONS
1257 for (++__f; __f != __l; ++__f, ((void)(__last = __last->__next_)))
1259 __h.reset(__node_traits::allocate(__a, 1));
1260 __node_traits::construct(__a, _VSTD::addressof(__h->__value_), *__f);
1261 __last->__next_ = __h.release();
1263 #ifndef _LIBCPP_NO_EXCEPTIONS
1267 while (__first != nullptr)
1269 __node_pointer __next = __first->__next_;
1270 __node_traits::destroy(__a, _VSTD::addressof(__first->__value_));
1271 __node_traits::deallocate(__a, __first, 1);
1276 #endif // _LIBCPP_NO_EXCEPTIONS
1277 __last->__next_ = __r->__next_;
1278 __r->__next_ = __first;
1279 __r = static_cast<__begin_node_pointer>(__last);
1281 return iterator(__r);
1284 template <class _Tp, class _Alloc>
1285 typename forward_list<_Tp, _Alloc>::iterator
1286 forward_list<_Tp, _Alloc>::erase_after(const_iterator __f)
1288 __begin_node_pointer __p = __f.__get_begin();
1289 __node_pointer __n = __p->__next_;
1290 __p->__next_ = __n->__next_;
1291 __node_allocator& __a = base::__alloc();
1292 __node_traits::destroy(__a, _VSTD::addressof(__n->__value_));
1293 __node_traits::deallocate(__a, __n, 1);
1294 return iterator(__p->__next_);
1297 template <class _Tp, class _Alloc>
1298 typename forward_list<_Tp, _Alloc>::iterator
1299 forward_list<_Tp, _Alloc>::erase_after(const_iterator __f, const_iterator __l)
1301 __node_pointer __e = __l.__get_unsafe_node_pointer();
1304 __begin_node_pointer __bp = __f.__get_begin();
1306 __node_pointer __n = __bp->__next_;
1309 __bp->__next_ = __e;
1310 __node_allocator& __a = base::__alloc();
1313 __node_pointer __tmp = __n->__next_;
1314 __node_traits::destroy(__a, _VSTD::addressof(__n->__value_));
1315 __node_traits::deallocate(__a, __n, 1);
1317 } while (__n != __e);
1320 return iterator(__e);
1323 template <class _Tp, class _Alloc>
1325 forward_list<_Tp, _Alloc>::resize(size_type __n)
1328 iterator __p = before_begin();
1329 iterator __i = begin();
1330 iterator __e = end();
1331 for (; __i != __e && __sz < __n; ++__p, ++__i, ++__sz)
1334 erase_after(__p, __e);
1340 __node_allocator& __a = base::__alloc();
1341 typedef __allocator_destructor<__node_allocator> _Dp;
1342 unique_ptr<__node, _Dp> __h(nullptr, _Dp(__a, 1));
1343 for (__begin_node_pointer __ptr = __p.__get_begin(); __n > 0; --__n,
1344 __ptr = __ptr->__next_as_begin())
1346 __h.reset(__node_traits::allocate(__a, 1));
1347 __node_traits::construct(__a, _VSTD::addressof(__h->__value_));
1348 __h->__next_ = nullptr;
1349 __ptr->__next_ = __h.release();
1355 template <class _Tp, class _Alloc>
1357 forward_list<_Tp, _Alloc>::resize(size_type __n, const value_type& __v)
1360 iterator __p = before_begin();
1361 iterator __i = begin();
1362 iterator __e = end();
1363 for (; __i != __e && __sz < __n; ++__p, ++__i, ++__sz)
1366 erase_after(__p, __e);
1372 __node_allocator& __a = base::__alloc();
1373 typedef __allocator_destructor<__node_allocator> _Dp;
1374 unique_ptr<__node, _Dp> __h(nullptr, _Dp(__a, 1));
1375 for (__begin_node_pointer __ptr = __p.__get_begin(); __n > 0; --__n,
1376 __ptr = __ptr->__next_as_begin())
1378 __h.reset(__node_traits::allocate(__a, 1));
1379 __node_traits::construct(__a, _VSTD::addressof(__h->__value_), __v);
1380 __h->__next_ = nullptr;
1381 __ptr->__next_ = __h.release();
1387 template <class _Tp, class _Alloc>
1389 forward_list<_Tp, _Alloc>::splice_after(const_iterator __p,
1394 if (__p.__get_begin()->__next_ != nullptr)
1396 const_iterator __lm1 = __x.before_begin();
1397 while (__lm1.__get_begin()->__next_ != nullptr)
1399 __lm1.__get_begin()->__next_ = __p.__get_begin()->__next_;
1401 __p.__get_begin()->__next_ = __x.__before_begin()->__next_;
1402 __x.__before_begin()->__next_ = nullptr;
1406 template <class _Tp, class _Alloc>
1408 forward_list<_Tp, _Alloc>::splice_after(const_iterator __p,
1409 forward_list& /*__other*/,
1412 const_iterator __lm1 = _VSTD::next(__i);
1413 if (__p != __i && __p != __lm1)
1415 __i.__get_begin()->__next_ = __lm1.__get_begin()->__next_;
1416 __lm1.__get_begin()->__next_ = __p.__get_begin()->__next_;
1417 __p.__get_begin()->__next_ = __lm1.__get_unsafe_node_pointer();
1421 template <class _Tp, class _Alloc>
1423 forward_list<_Tp, _Alloc>::splice_after(const_iterator __p,
1424 forward_list& /*__other*/,
1425 const_iterator __f, const_iterator __l)
1427 if (__f != __l && __p != __f)
1429 const_iterator __lm1 = __f;
1430 while (__lm1.__get_begin()->__next_ != __l.__get_begin())
1434 __lm1.__get_begin()->__next_ = __p.__get_begin()->__next_;
1435 __p.__get_begin()->__next_ = __f.__get_begin()->__next_;
1436 __f.__get_begin()->__next_ = __l.__get_unsafe_node_pointer();
1441 #ifndef _LIBCPP_CXX03_LANG
1443 template <class _Tp, class _Alloc>
1444 inline _LIBCPP_INLINE_VISIBILITY
1446 forward_list<_Tp, _Alloc>::splice_after(const_iterator __p,
1449 splice_after(__p, __x);
1452 template <class _Tp, class _Alloc>
1453 inline _LIBCPP_INLINE_VISIBILITY
1455 forward_list<_Tp, _Alloc>::splice_after(const_iterator __p,
1459 splice_after(__p, __x, __i);
1462 template <class _Tp, class _Alloc>
1463 inline _LIBCPP_INLINE_VISIBILITY
1465 forward_list<_Tp, _Alloc>::splice_after(const_iterator __p,
1467 const_iterator __f, const_iterator __l)
1469 splice_after(__p, __x, __f, __l);
1472 #endif // _LIBCPP_CXX03_LANG
1474 template <class _Tp, class _Alloc>
1476 forward_list<_Tp, _Alloc>::remove(const value_type& __v)
1478 forward_list<_Tp, _Alloc> __deleted_nodes; // collect the nodes we're removing
1479 iterator __e = end();
1480 for (iterator __i = before_begin(); __i.__get_begin()->__next_ != nullptr;)
1482 if (__i.__get_begin()->__next_->__value_ == __v)
1484 iterator __j = _VSTD::next(__i, 2);
1485 for (; __j != __e && *__j == __v; ++__j)
1487 __deleted_nodes.splice_after(__deleted_nodes.before_begin(), *this, __i, __j);
1497 template <class _Tp, class _Alloc>
1498 template <class _Predicate>
1500 forward_list<_Tp, _Alloc>::remove_if(_Predicate __pred)
1502 iterator __e = end();
1503 for (iterator __i = before_begin(); __i.__get_begin()->__next_ != nullptr;)
1505 if (__pred(__i.__get_begin()->__next_->__value_))
1507 iterator __j = _VSTD::next(__i, 2);
1508 for (; __j != __e && __pred(*__j); ++__j)
1510 erase_after(__i, __j);
1520 template <class _Tp, class _Alloc>
1521 template <class _BinaryPredicate>
1523 forward_list<_Tp, _Alloc>::unique(_BinaryPredicate __binary_pred)
1525 for (iterator __i = begin(), __e = end(); __i != __e;)
1527 iterator __j = _VSTD::next(__i);
1528 for (; __j != __e && __binary_pred(*__i, *__j); ++__j)
1530 if (__i.__get_begin()->__next_ != __j.__get_unsafe_node_pointer())
1531 erase_after(__i, __j);
1536 template <class _Tp, class _Alloc>
1537 template <class _Compare>
1539 forward_list<_Tp, _Alloc>::merge(forward_list& __x, _Compare __comp)
1543 base::__before_begin()->__next_ = __merge(base::__before_begin()->__next_,
1544 __x.__before_begin()->__next_,
1546 __x.__before_begin()->__next_ = nullptr;
1550 template <class _Tp, class _Alloc>
1551 template <class _Compare>
1552 typename forward_list<_Tp, _Alloc>::__node_pointer
1553 forward_list<_Tp, _Alloc>::__merge(__node_pointer __f1, __node_pointer __f2,
1556 if (__f1 == nullptr)
1558 if (__f2 == nullptr)
1561 if (__comp(__f2->__value_, __f1->__value_))
1563 __node_pointer __t = __f2;
1564 while (__t->__next_ != nullptr &&
1565 __comp(__t->__next_->__value_, __f1->__value_))
1568 __f2 = __t->__next_;
1569 __t->__next_ = __f1;
1573 __node_pointer __p = __f1;
1574 __f1 = __f1->__next_;
1575 while (__f1 != nullptr && __f2 != nullptr)
1577 if (__comp(__f2->__value_, __f1->__value_))
1579 __node_pointer __t = __f2;
1580 while (__t->__next_ != nullptr &&
1581 __comp(__t->__next_->__value_, __f1->__value_))
1583 __p->__next_ = __f2;
1584 __f2 = __t->__next_;
1585 __t->__next_ = __f1;
1588 __f1 = __f1->__next_;
1590 if (__f2 != nullptr)
1591 __p->__next_ = __f2;
1595 template <class _Tp, class _Alloc>
1596 template <class _Compare>
1599 forward_list<_Tp, _Alloc>::sort(_Compare __comp)
1601 base::__before_begin()->__next_ = __sort(base::__before_begin()->__next_,
1602 _VSTD::distance(begin(), end()), __comp);
1605 template <class _Tp, class _Alloc>
1606 template <class _Compare>
1607 typename forward_list<_Tp, _Alloc>::__node_pointer
1608 forward_list<_Tp, _Alloc>::__sort(__node_pointer __f1, difference_type __sz,
1617 if (__comp(__f1->__next_->__value_, __f1->__value_))
1619 __node_pointer __t = __f1->__next_;
1620 __t->__next_ = __f1;
1621 __f1->__next_ = nullptr;
1626 difference_type __sz1 = __sz / 2;
1627 difference_type __sz2 = __sz - __sz1;
1628 __node_pointer __t = _VSTD::next(iterator(__f1), __sz1 - 1).__get_unsafe_node_pointer();
1629 __node_pointer __f2 = __t->__next_;
1630 __t->__next_ = nullptr;
1631 return __merge(__sort(__f1, __sz1, __comp),
1632 __sort(__f2, __sz2, __comp), __comp);
1635 template <class _Tp, class _Alloc>
1637 forward_list<_Tp, _Alloc>::reverse() _NOEXCEPT
1639 __node_pointer __p = base::__before_begin()->__next_;
1642 __node_pointer __f = __p->__next_;
1643 __p->__next_ = nullptr;
1644 while (__f != nullptr)
1646 __node_pointer __t = __f->__next_;
1651 base::__before_begin()->__next_ = __p;
1655 template <class _Tp, class _Alloc>
1656 bool operator==(const forward_list<_Tp, _Alloc>& __x,
1657 const forward_list<_Tp, _Alloc>& __y)
1659 typedef forward_list<_Tp, _Alloc> _Cp;
1660 typedef typename _Cp::const_iterator _Ip;
1661 _Ip __ix = __x.begin();
1662 _Ip __ex = __x.end();
1663 _Ip __iy = __y.begin();
1664 _Ip __ey = __y.end();
1665 for (; __ix != __ex && __iy != __ey; ++__ix, ++__iy)
1666 if (!(*__ix == *__iy))
1668 return (__ix == __ex) == (__iy == __ey);
1671 template <class _Tp, class _Alloc>
1672 inline _LIBCPP_INLINE_VISIBILITY
1673 bool operator!=(const forward_list<_Tp, _Alloc>& __x,
1674 const forward_list<_Tp, _Alloc>& __y)
1676 return !(__x == __y);
1679 template <class _Tp, class _Alloc>
1680 inline _LIBCPP_INLINE_VISIBILITY
1681 bool operator< (const forward_list<_Tp, _Alloc>& __x,
1682 const forward_list<_Tp, _Alloc>& __y)
1684 return _VSTD::lexicographical_compare(__x.begin(), __x.end(),
1685 __y.begin(), __y.end());
1688 template <class _Tp, class _Alloc>
1689 inline _LIBCPP_INLINE_VISIBILITY
1690 bool operator> (const forward_list<_Tp, _Alloc>& __x,
1691 const forward_list<_Tp, _Alloc>& __y)
1696 template <class _Tp, class _Alloc>
1697 inline _LIBCPP_INLINE_VISIBILITY
1698 bool operator>=(const forward_list<_Tp, _Alloc>& __x,
1699 const forward_list<_Tp, _Alloc>& __y)
1701 return !(__x < __y);
1704 template <class _Tp, class _Alloc>
1705 inline _LIBCPP_INLINE_VISIBILITY
1706 bool operator<=(const forward_list<_Tp, _Alloc>& __x,
1707 const forward_list<_Tp, _Alloc>& __y)
1709 return !(__y < __x);
1712 template <class _Tp, class _Alloc>
1713 inline _LIBCPP_INLINE_VISIBILITY
1715 swap(forward_list<_Tp, _Alloc>& __x, forward_list<_Tp, _Alloc>& __y)
1716 _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y)))
1721 _LIBCPP_END_NAMESPACE_STD
1725 #endif // _LIBCPP_FORWARD_LIST