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 forward_list(size_type n, const value_type& v);
42 forward_list(size_type n, const value_type& v, const allocator_type& a);
43 template <class InputIterator>
44 forward_list(InputIterator first, InputIterator last);
45 template <class InputIterator>
46 forward_list(InputIterator first, InputIterator last, const allocator_type& a);
47 forward_list(const forward_list& x);
48 forward_list(const forward_list& x, const allocator_type& a);
49 forward_list(forward_list&& x)
50 noexcept(is_nothrow_move_constructible<allocator_type>::value);
51 forward_list(forward_list&& x, const allocator_type& a);
52 forward_list(initializer_list<value_type> il);
53 forward_list(initializer_list<value_type> il, const allocator_type& a);
57 forward_list& operator=(const forward_list& x);
58 forward_list& operator=(forward_list&& x)
60 allocator_type::propagate_on_container_move_assignment::value &&
61 is_nothrow_move_assignable<allocator_type>::value);
62 forward_list& operator=(initializer_list<value_type> il);
64 template <class InputIterator>
65 void assign(InputIterator first, InputIterator last);
66 void assign(size_type n, const value_type& v);
67 void assign(initializer_list<value_type> il);
69 allocator_type get_allocator() const noexcept;
71 iterator begin() noexcept;
72 const_iterator begin() const noexcept;
73 iterator end() noexcept;
74 const_iterator end() const noexcept;
76 const_iterator cbegin() const noexcept;
77 const_iterator cend() const noexcept;
79 iterator before_begin() noexcept;
80 const_iterator before_begin() const noexcept;
81 const_iterator cbefore_begin() const noexcept;
83 bool empty() const noexcept;
84 size_type max_size() const noexcept;
87 const_reference front() const;
89 template <class... Args> void emplace_front(Args&&... args);
90 void push_front(const value_type& v);
91 void push_front(value_type&& v);
95 template <class... Args>
96 iterator emplace_after(const_iterator p, Args&&... args);
97 iterator insert_after(const_iterator p, const value_type& v);
98 iterator insert_after(const_iterator p, value_type&& v);
99 iterator insert_after(const_iterator p, size_type n, const value_type& v);
100 template <class InputIterator>
101 iterator insert_after(const_iterator p,
102 InputIterator first, InputIterator last);
103 iterator insert_after(const_iterator p, initializer_list<value_type> il);
105 iterator erase_after(const_iterator p);
106 iterator erase_after(const_iterator first, const_iterator last);
108 void swap(forward_list& x)
109 noexcept(!allocator_type::propagate_on_container_swap::value ||
110 __is_nothrow_swappable<allocator_type>::value);
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)));
171 #include <initializer_list>
177 #include <__undef_min_max>
179 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
180 #pragma GCC system_header
183 _LIBCPP_BEGIN_NAMESPACE_STD
185 template <class _Tp, class _VoidPtr> struct __forward_list_node;
187 template <class _NodePtr>
188 struct __forward_begin_node
190 typedef __forward_begin_node __self;
191 typedef _NodePtr pointer;
195 _LIBCPP_INLINE_VISIBILITY __forward_begin_node() : __next_(nullptr) {}
198 template <class _Tp, class _VoidPtr>
199 struct __forward_list_node
200 : public __forward_begin_node
202 typename pointer_traits<_VoidPtr>::template
203 #ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES
204 rebind<__forward_list_node<_Tp, _VoidPtr> >
206 rebind<__forward_list_node<_Tp, _VoidPtr> >::other
210 typedef _Tp value_type;
215 template<class _Tp, class _Alloc> class _LIBCPP_TYPE_VIS forward_list;
216 template<class _NodeConstPtr> class _LIBCPP_TYPE_VIS __forward_list_const_iterator;
218 template <class _NodePtr>
219 class _LIBCPP_TYPE_VIS __forward_list_iterator
221 typedef _NodePtr __node_pointer;
223 __node_pointer __ptr_;
225 _LIBCPP_INLINE_VISIBILITY
226 explicit __forward_list_iterator(__node_pointer __p) _NOEXCEPT : __ptr_(__p) {}
228 template<class, class> friend class _LIBCPP_TYPE_VIS forward_list;
229 template<class> friend class _LIBCPP_TYPE_VIS __forward_list_const_iterator;
232 typedef forward_iterator_tag iterator_category;
233 typedef typename pointer_traits<__node_pointer>::element_type::value_type
235 typedef value_type& reference;
236 typedef typename pointer_traits<__node_pointer>::difference_type
238 typedef typename pointer_traits<__node_pointer>::template
239 #ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES
242 rebind<value_type>::other
246 _LIBCPP_INLINE_VISIBILITY
247 __forward_list_iterator() _NOEXCEPT : __ptr_(nullptr) {}
249 _LIBCPP_INLINE_VISIBILITY
250 reference operator*() const {return __ptr_->__value_;}
251 _LIBCPP_INLINE_VISIBILITY
252 pointer operator->() const {return pointer_traits<pointer>::pointer_to(__ptr_->__value_);}
254 _LIBCPP_INLINE_VISIBILITY
255 __forward_list_iterator& operator++()
257 __ptr_ = __ptr_->__next_;
260 _LIBCPP_INLINE_VISIBILITY
261 __forward_list_iterator operator++(int)
263 __forward_list_iterator __t(*this);
268 friend _LIBCPP_INLINE_VISIBILITY
269 bool operator==(const __forward_list_iterator& __x,
270 const __forward_list_iterator& __y)
271 {return __x.__ptr_ == __y.__ptr_;}
272 friend _LIBCPP_INLINE_VISIBILITY
273 bool operator!=(const __forward_list_iterator& __x,
274 const __forward_list_iterator& __y)
275 {return !(__x == __y);}
278 template <class _NodeConstPtr>
279 class _LIBCPP_TYPE_VIS __forward_list_const_iterator
281 typedef _NodeConstPtr __node_const_pointer;
283 __node_const_pointer __ptr_;
285 _LIBCPP_INLINE_VISIBILITY
286 explicit __forward_list_const_iterator(__node_const_pointer __p) _NOEXCEPT
289 typedef typename remove_const
291 typename pointer_traits<__node_const_pointer>::element_type
293 typedef typename pointer_traits<__node_const_pointer>::template
294 #ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES
297 rebind<__node>::other
301 template<class, class> friend class forward_list;
304 typedef forward_iterator_tag iterator_category;
305 typedef typename __node::value_type value_type;
306 typedef const value_type& reference;
307 typedef typename pointer_traits<__node_const_pointer>::difference_type
309 typedef typename pointer_traits<__node_const_pointer>::template
310 #ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES
311 rebind<const value_type>
313 rebind<const value_type>::other
317 _LIBCPP_INLINE_VISIBILITY
318 __forward_list_const_iterator() _NOEXCEPT : __ptr_(nullptr) {}
319 _LIBCPP_INLINE_VISIBILITY
320 __forward_list_const_iterator(__forward_list_iterator<__node_pointer> __p) _NOEXCEPT
321 : __ptr_(__p.__ptr_) {}
323 _LIBCPP_INLINE_VISIBILITY
324 reference operator*() const {return __ptr_->__value_;}
325 _LIBCPP_INLINE_VISIBILITY
326 pointer operator->() const {return pointer_traits<pointer>::pointer_to(__ptr_->__value_);}
328 _LIBCPP_INLINE_VISIBILITY
329 __forward_list_const_iterator& operator++()
331 __ptr_ = __ptr_->__next_;
334 _LIBCPP_INLINE_VISIBILITY
335 __forward_list_const_iterator operator++(int)
337 __forward_list_const_iterator __t(*this);
342 friend _LIBCPP_INLINE_VISIBILITY
343 bool operator==(const __forward_list_const_iterator& __x,
344 const __forward_list_const_iterator& __y)
345 {return __x.__ptr_ == __y.__ptr_;}
346 friend _LIBCPP_INLINE_VISIBILITY
347 bool operator!=(const __forward_list_const_iterator& __x,
348 const __forward_list_const_iterator& __y)
349 {return !(__x == __y);}
352 template <class _Tp, class _Alloc>
353 class __forward_list_base
356 typedef _Tp value_type;
357 typedef _Alloc allocator_type;
359 typedef typename allocator_traits<allocator_type>::void_pointer void_pointer;
360 typedef __forward_list_node<value_type, void_pointer> __node;
361 typedef typename __node::__self __begin_node;
362 typedef typename allocator_traits<allocator_type>::template
363 #ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES
366 rebind_alloc<__node>::other
369 typedef allocator_traits<__node_allocator> __node_traits;
370 typedef typename __node_traits::pointer __node_pointer;
371 typedef typename __node_traits::pointer __node_const_pointer;
373 typedef typename allocator_traits<allocator_type>::template
374 #ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES
375 rebind_alloc<__begin_node>
377 rebind_alloc<__begin_node>::other
379 __begin_node_allocator;
380 typedef typename allocator_traits<__begin_node_allocator>::pointer __begin_node_pointer;
382 __compressed_pair<__begin_node, __node_allocator> __before_begin_;
384 _LIBCPP_INLINE_VISIBILITY
385 __node_pointer __before_begin() _NOEXCEPT
386 {return static_cast<__node_pointer>(pointer_traits<__begin_node_pointer>::
387 pointer_to(__before_begin_.first()));}
388 _LIBCPP_INLINE_VISIBILITY
389 __node_const_pointer __before_begin() const _NOEXCEPT
390 {return static_cast<__node_const_pointer>(pointer_traits<__begin_node_pointer>::
391 pointer_to(const_cast<__begin_node&>(__before_begin_.first())));}
393 _LIBCPP_INLINE_VISIBILITY
394 __node_allocator& __alloc() _NOEXCEPT
395 {return __before_begin_.second();}
396 _LIBCPP_INLINE_VISIBILITY
397 const __node_allocator& __alloc() const _NOEXCEPT
398 {return __before_begin_.second();}
400 typedef __forward_list_iterator<__node_pointer> iterator;
401 typedef __forward_list_const_iterator<__node_pointer> const_iterator;
403 _LIBCPP_INLINE_VISIBILITY
404 __forward_list_base()
405 _NOEXCEPT_(is_nothrow_default_constructible<__node_allocator>::value)
406 : __before_begin_(__begin_node()) {}
407 _LIBCPP_INLINE_VISIBILITY
408 __forward_list_base(const allocator_type& __a)
409 : __before_begin_(__begin_node(), __node_allocator(__a)) {}
411 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
413 __forward_list_base(__forward_list_base&& __x)
414 _NOEXCEPT_(is_nothrow_move_constructible<__node_allocator>::value);
415 __forward_list_base(__forward_list_base&& __x, const allocator_type& __a);
416 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
419 __forward_list_base(const __forward_list_base&);
420 __forward_list_base& operator=(const __forward_list_base&);
423 ~__forward_list_base();
426 _LIBCPP_INLINE_VISIBILITY
427 void __copy_assign_alloc(const __forward_list_base& __x)
428 {__copy_assign_alloc(__x, integral_constant<bool,
429 __node_traits::propagate_on_container_copy_assignment::value>());}
431 _LIBCPP_INLINE_VISIBILITY
432 void __move_assign_alloc(__forward_list_base& __x)
433 _NOEXCEPT_(!__node_traits::propagate_on_container_move_assignment::value ||
434 is_nothrow_move_assignable<__node_allocator>::value)
435 {__move_assign_alloc(__x, integral_constant<bool,
436 __node_traits::propagate_on_container_move_assignment::value>());}
439 void swap(__forward_list_base& __x)
440 _NOEXCEPT_(!__node_traits::propagate_on_container_swap::value ||
441 __is_nothrow_swappable<__node_allocator>::value);
443 void clear() _NOEXCEPT;
446 _LIBCPP_INLINE_VISIBILITY
447 void __copy_assign_alloc(const __forward_list_base&, false_type) {}
448 _LIBCPP_INLINE_VISIBILITY
449 void __copy_assign_alloc(const __forward_list_base& __x, true_type)
451 if (__alloc() != __x.__alloc())
453 __alloc() = __x.__alloc();
456 _LIBCPP_INLINE_VISIBILITY
457 void __move_assign_alloc(__forward_list_base& __x, false_type) _NOEXCEPT
459 _LIBCPP_INLINE_VISIBILITY
460 void __move_assign_alloc(__forward_list_base& __x, true_type)
461 _NOEXCEPT_(is_nothrow_move_assignable<__node_allocator>::value)
462 {__alloc() = _VSTD::move(__x.__alloc());}
464 _LIBCPP_INLINE_VISIBILITY
465 static void __swap_alloc(__node_allocator& __x, __node_allocator& __y)
466 _NOEXCEPT_(!__node_traits::propagate_on_container_swap::value ||
467 __is_nothrow_swappable<__node_allocator>::value)
468 {__swap_alloc(__x, __y, integral_constant<bool,
469 __node_traits::propagate_on_container_swap::value>());}
470 _LIBCPP_INLINE_VISIBILITY
471 static void __swap_alloc(__node_allocator& __x, __node_allocator& __y,
475 _LIBCPP_INLINE_VISIBILITY
476 static void __swap_alloc(__node_allocator& __x, __node_allocator& __y,
478 _NOEXCEPT_(__is_nothrow_swappable<__node_allocator>::value)
485 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
487 template <class _Tp, class _Alloc>
488 inline _LIBCPP_INLINE_VISIBILITY
489 __forward_list_base<_Tp, _Alloc>::__forward_list_base(__forward_list_base&& __x)
490 _NOEXCEPT_(is_nothrow_move_constructible<__node_allocator>::value)
491 : __before_begin_(_VSTD::move(__x.__before_begin_))
493 __x.__before_begin()->__next_ = nullptr;
496 template <class _Tp, class _Alloc>
497 inline _LIBCPP_INLINE_VISIBILITY
498 __forward_list_base<_Tp, _Alloc>::__forward_list_base(__forward_list_base&& __x,
499 const allocator_type& __a)
500 : __before_begin_(__begin_node(), __node_allocator(__a))
502 if (__alloc() == __x.__alloc())
504 __before_begin()->__next_ = __x.__before_begin()->__next_;
505 __x.__before_begin()->__next_ = nullptr;
509 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
511 template <class _Tp, class _Alloc>
512 __forward_list_base<_Tp, _Alloc>::~__forward_list_base()
517 template <class _Tp, class _Alloc>
518 inline _LIBCPP_INLINE_VISIBILITY
520 __forward_list_base<_Tp, _Alloc>::swap(__forward_list_base& __x)
521 _NOEXCEPT_(!__node_traits::propagate_on_container_swap::value ||
522 __is_nothrow_swappable<__node_allocator>::value)
524 __swap_alloc(__alloc(), __x.__alloc());
526 swap(__before_begin()->__next_, __x.__before_begin()->__next_);
529 template <class _Tp, class _Alloc>
531 __forward_list_base<_Tp, _Alloc>::clear() _NOEXCEPT
533 __node_allocator& __a = __alloc();
534 for (__node_pointer __p = __before_begin()->__next_; __p != nullptr;)
536 __node_pointer __next = __p->__next_;
537 __node_traits::destroy(__a, _VSTD::addressof(__p->__value_));
538 __node_traits::deallocate(__a, __p, 1);
541 __before_begin()->__next_ = nullptr;
544 template <class _Tp, class _Alloc = allocator<_Tp> >
545 class _LIBCPP_TYPE_VIS forward_list
546 : private __forward_list_base<_Tp, _Alloc>
548 typedef __forward_list_base<_Tp, _Alloc> base;
549 typedef typename base::__node_allocator __node_allocator;
550 typedef typename base::__node __node;
551 typedef typename base::__node_traits __node_traits;
552 typedef typename base::__node_pointer __node_pointer;
555 typedef _Tp value_type;
556 typedef _Alloc allocator_type;
558 typedef value_type& reference;
559 typedef const value_type& const_reference;
560 typedef typename allocator_traits<allocator_type>::pointer pointer;
561 typedef typename allocator_traits<allocator_type>::const_pointer const_pointer;
562 typedef typename allocator_traits<allocator_type>::size_type size_type;
563 typedef typename allocator_traits<allocator_type>::difference_type difference_type;
565 typedef typename base::iterator iterator;
566 typedef typename base::const_iterator const_iterator;
568 _LIBCPP_INLINE_VISIBILITY
570 _NOEXCEPT_(is_nothrow_default_constructible<__node_allocator>::value)
572 explicit forward_list(const allocator_type& __a);
573 explicit forward_list(size_type __n);
574 forward_list(size_type __n, const value_type& __v);
575 forward_list(size_type __n, const value_type& __v, const allocator_type& __a);
576 template <class _InputIterator>
577 forward_list(_InputIterator __f, _InputIterator __l,
579 __is_input_iterator<_InputIterator>::value
581 template <class _InputIterator>
582 forward_list(_InputIterator __f, _InputIterator __l,
583 const allocator_type& __a,
585 __is_input_iterator<_InputIterator>::value
587 forward_list(const forward_list& __x);
588 forward_list(const forward_list& __x, const allocator_type& __a);
589 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
590 _LIBCPP_INLINE_VISIBILITY
591 forward_list(forward_list&& __x)
592 _NOEXCEPT_(is_nothrow_move_constructible<base>::value)
593 : base(_VSTD::move(__x)) {}
594 forward_list(forward_list&& __x, const allocator_type& __a);
595 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
596 #ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
597 forward_list(initializer_list<value_type> __il);
598 forward_list(initializer_list<value_type> __il, const allocator_type& __a);
599 #endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
601 // ~forward_list() = default;
603 forward_list& operator=(const forward_list& __x);
604 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
605 forward_list& operator=(forward_list&& __x)
607 __node_traits::propagate_on_container_move_assignment::value &&
608 is_nothrow_move_assignable<allocator_type>::value);
610 #ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
611 forward_list& operator=(initializer_list<value_type> __il);
612 #endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
614 template <class _InputIterator>
617 __is_input_iterator<_InputIterator>::value,
620 assign(_InputIterator __f, _InputIterator __l);
621 void assign(size_type __n, const value_type& __v);
622 #ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
623 void assign(initializer_list<value_type> __il);
624 #endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
626 _LIBCPP_INLINE_VISIBILITY
627 allocator_type get_allocator() const _NOEXCEPT
628 {return allocator_type(base::__alloc());}
630 _LIBCPP_INLINE_VISIBILITY
631 iterator begin() _NOEXCEPT
632 {return iterator(base::__before_begin()->__next_);}
633 _LIBCPP_INLINE_VISIBILITY
634 const_iterator begin() const _NOEXCEPT
635 {return const_iterator(base::__before_begin()->__next_);}
636 _LIBCPP_INLINE_VISIBILITY
637 iterator end() _NOEXCEPT
638 {return iterator(nullptr);}
639 _LIBCPP_INLINE_VISIBILITY
640 const_iterator end() const _NOEXCEPT
641 {return const_iterator(nullptr);}
643 _LIBCPP_INLINE_VISIBILITY
644 const_iterator cbegin() const _NOEXCEPT
645 {return const_iterator(base::__before_begin()->__next_);}
646 _LIBCPP_INLINE_VISIBILITY
647 const_iterator cend() const _NOEXCEPT
648 {return const_iterator(nullptr);}
650 _LIBCPP_INLINE_VISIBILITY
651 iterator before_begin() _NOEXCEPT
652 {return iterator(base::__before_begin());}
653 _LIBCPP_INLINE_VISIBILITY
654 const_iterator before_begin() const _NOEXCEPT
655 {return const_iterator(base::__before_begin());}
656 _LIBCPP_INLINE_VISIBILITY
657 const_iterator cbefore_begin() const _NOEXCEPT
658 {return const_iterator(base::__before_begin());}
660 _LIBCPP_INLINE_VISIBILITY
661 bool empty() const _NOEXCEPT
662 {return base::__before_begin()->__next_ == nullptr;}
663 _LIBCPP_INLINE_VISIBILITY
664 size_type max_size() const _NOEXCEPT
665 {return numeric_limits<size_type>::max();}
667 _LIBCPP_INLINE_VISIBILITY
668 reference front() {return base::__before_begin()->__next_->__value_;}
669 _LIBCPP_INLINE_VISIBILITY
670 const_reference front() const {return base::__before_begin()->__next_->__value_;}
672 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
673 #ifndef _LIBCPP_HAS_NO_VARIADICS
674 template <class... _Args> void emplace_front(_Args&&... __args);
676 void push_front(value_type&& __v);
677 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
678 void push_front(const value_type& __v);
682 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
683 #ifndef _LIBCPP_HAS_NO_VARIADICS
684 template <class... _Args>
685 iterator emplace_after(const_iterator __p, _Args&&... __args);
686 #endif // _LIBCPP_HAS_NO_VARIADICS
687 iterator insert_after(const_iterator __p, value_type&& __v);
688 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
689 iterator insert_after(const_iterator __p, const value_type& __v);
690 iterator insert_after(const_iterator __p, size_type __n, const value_type& __v);
691 template <class _InputIterator>
692 _LIBCPP_INLINE_VISIBILITY
695 __is_input_iterator<_InputIterator>::value,
698 insert_after(const_iterator __p, _InputIterator __f, _InputIterator __l);
699 #ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
700 iterator insert_after(const_iterator __p, initializer_list<value_type> __il)
701 {return insert_after(__p, __il.begin(), __il.end());}
702 #endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
704 iterator erase_after(const_iterator __p);
705 iterator erase_after(const_iterator __f, const_iterator __l);
707 _LIBCPP_INLINE_VISIBILITY
708 void swap(forward_list& __x)
709 _NOEXCEPT_(!__node_traits::propagate_on_container_swap::value ||
710 __is_nothrow_swappable<__node_allocator>::value)
713 void resize(size_type __n);
714 void resize(size_type __n, const value_type& __v);
715 _LIBCPP_INLINE_VISIBILITY
716 void clear() _NOEXCEPT {base::clear();}
718 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
719 _LIBCPP_INLINE_VISIBILITY
720 void splice_after(const_iterator __p, forward_list&& __x);
721 _LIBCPP_INLINE_VISIBILITY
722 void splice_after(const_iterator __p, forward_list&& __x, const_iterator __i);
723 _LIBCPP_INLINE_VISIBILITY
724 void splice_after(const_iterator __p, forward_list&& __x,
725 const_iterator __f, const_iterator __l);
726 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
727 void splice_after(const_iterator __p, forward_list& __x);
728 void splice_after(const_iterator __p, forward_list& __x, const_iterator __i);
729 void splice_after(const_iterator __p, forward_list& __x,
730 const_iterator __f, const_iterator __l);
731 void remove(const value_type& __v);
732 template <class _Predicate> void remove_if(_Predicate __pred);
733 _LIBCPP_INLINE_VISIBILITY
734 void unique() {unique(__equal_to<value_type>());}
735 template <class _BinaryPredicate> void unique(_BinaryPredicate __binary_pred);
736 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
737 _LIBCPP_INLINE_VISIBILITY
738 void merge(forward_list&& __x) {merge(__x, __less<value_type>());}
739 template <class _Compare>
740 _LIBCPP_INLINE_VISIBILITY
741 void merge(forward_list&& __x, _Compare __comp)
742 {merge(__x, _VSTD::move(__comp));}
743 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
744 _LIBCPP_INLINE_VISIBILITY
745 void merge(forward_list& __x) {merge(__x, __less<value_type>());}
746 template <class _Compare> void merge(forward_list& __x, _Compare __comp);
747 _LIBCPP_INLINE_VISIBILITY
748 void sort() {sort(__less<value_type>());}
749 template <class _Compare> void sort(_Compare __comp);
750 void reverse() _NOEXCEPT;
754 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
755 void __move_assign(forward_list& __x, true_type)
756 _NOEXCEPT_(is_nothrow_move_assignable<allocator_type>::value);
757 void __move_assign(forward_list& __x, false_type);
758 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
760 template <class _Compare>
763 __merge(__node_pointer __f1, __node_pointer __f2, _Compare& __comp);
765 template <class _Compare>
768 __sort(__node_pointer __f, difference_type __sz, _Compare& __comp);
771 template <class _Tp, class _Alloc>
772 inline _LIBCPP_INLINE_VISIBILITY
773 forward_list<_Tp, _Alloc>::forward_list(const allocator_type& __a)
778 template <class _Tp, class _Alloc>
779 forward_list<_Tp, _Alloc>::forward_list(size_type __n)
783 __node_allocator& __a = base::__alloc();
784 typedef __allocator_destructor<__node_allocator> _Dp;
785 unique_ptr<__node, _Dp> __h(nullptr, _Dp(__a, 1));
786 for (__node_pointer __p = base::__before_begin(); __n > 0; --__n,
789 __h.reset(__node_traits::allocate(__a, 1));
790 __node_traits::construct(__a, _VSTD::addressof(__h->__value_));
791 __h->__next_ = nullptr;
792 __p->__next_ = __h.release();
797 template <class _Tp, class _Alloc>
798 forward_list<_Tp, _Alloc>::forward_list(size_type __n, const value_type& __v)
800 insert_after(cbefore_begin(), __n, __v);
803 template <class _Tp, class _Alloc>
804 forward_list<_Tp, _Alloc>::forward_list(size_type __n, const value_type& __v,
805 const allocator_type& __a)
808 insert_after(cbefore_begin(), __n, __v);
811 template <class _Tp, class _Alloc>
812 template <class _InputIterator>
813 forward_list<_Tp, _Alloc>::forward_list(_InputIterator __f, _InputIterator __l,
815 __is_input_iterator<_InputIterator>::value
818 insert_after(cbefore_begin(), __f, __l);
821 template <class _Tp, class _Alloc>
822 template <class _InputIterator>
823 forward_list<_Tp, _Alloc>::forward_list(_InputIterator __f, _InputIterator __l,
824 const allocator_type& __a,
826 __is_input_iterator<_InputIterator>::value
830 insert_after(cbefore_begin(), __f, __l);
833 template <class _Tp, class _Alloc>
834 forward_list<_Tp, _Alloc>::forward_list(const forward_list& __x)
835 : base(allocator_type(
836 __node_traits::select_on_container_copy_construction(__x.__alloc())
840 insert_after(cbefore_begin(), __x.begin(), __x.end());
843 template <class _Tp, class _Alloc>
844 forward_list<_Tp, _Alloc>::forward_list(const forward_list& __x,
845 const allocator_type& __a)
848 insert_after(cbefore_begin(), __x.begin(), __x.end());
851 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
853 template <class _Tp, class _Alloc>
854 forward_list<_Tp, _Alloc>::forward_list(forward_list&& __x,
855 const allocator_type& __a)
856 : base(_VSTD::move(__x), __a)
858 if (base::__alloc() != __x.__alloc())
860 typedef move_iterator<iterator> _Ip;
861 insert_after(cbefore_begin(), _Ip(__x.begin()), _Ip(__x.end()));
865 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
867 #ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
869 template <class _Tp, class _Alloc>
870 forward_list<_Tp, _Alloc>::forward_list(initializer_list<value_type> __il)
872 insert_after(cbefore_begin(), __il.begin(), __il.end());
875 template <class _Tp, class _Alloc>
876 forward_list<_Tp, _Alloc>::forward_list(initializer_list<value_type> __il,
877 const allocator_type& __a)
880 insert_after(cbefore_begin(), __il.begin(), __il.end());
883 #endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
885 template <class _Tp, class _Alloc>
886 forward_list<_Tp, _Alloc>&
887 forward_list<_Tp, _Alloc>::operator=(const forward_list& __x)
891 base::__copy_assign_alloc(__x);
892 assign(__x.begin(), __x.end());
897 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
899 template <class _Tp, class _Alloc>
901 forward_list<_Tp, _Alloc>::__move_assign(forward_list& __x, true_type)
902 _NOEXCEPT_(is_nothrow_move_assignable<allocator_type>::value)
905 base::__move_assign_alloc(__x);
906 base::__before_begin()->__next_ = __x.__before_begin()->__next_;
907 __x.__before_begin()->__next_ = nullptr;
910 template <class _Tp, class _Alloc>
912 forward_list<_Tp, _Alloc>::__move_assign(forward_list& __x, false_type)
914 if (base::__alloc() == __x.__alloc())
915 __move_assign(__x, true_type());
918 typedef move_iterator<iterator> _Ip;
919 assign(_Ip(__x.begin()), _Ip(__x.end()));
923 template <class _Tp, class _Alloc>
924 inline _LIBCPP_INLINE_VISIBILITY
925 forward_list<_Tp, _Alloc>&
926 forward_list<_Tp, _Alloc>::operator=(forward_list&& __x)
928 __node_traits::propagate_on_container_move_assignment::value &&
929 is_nothrow_move_assignable<allocator_type>::value)
931 __move_assign(__x, integral_constant<bool,
932 __node_traits::propagate_on_container_move_assignment::value>());
936 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
938 #ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
940 template <class _Tp, class _Alloc>
941 inline _LIBCPP_INLINE_VISIBILITY
942 forward_list<_Tp, _Alloc>&
943 forward_list<_Tp, _Alloc>::operator=(initializer_list<value_type> __il)
945 assign(__il.begin(), __il.end());
949 #endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
951 template <class _Tp, class _Alloc>
952 template <class _InputIterator>
955 __is_input_iterator<_InputIterator>::value,
958 forward_list<_Tp, _Alloc>::assign(_InputIterator __f, _InputIterator __l)
960 iterator __i = before_begin();
961 iterator __j = _VSTD::next(__i);
962 iterator __e = end();
963 for (; __j != __e && __f != __l; ++__i, ++__j, ++__f)
966 insert_after(__i, __f, __l);
968 erase_after(__i, __e);
971 template <class _Tp, class _Alloc>
973 forward_list<_Tp, _Alloc>::assign(size_type __n, const value_type& __v)
975 iterator __i = before_begin();
976 iterator __j = _VSTD::next(__i);
977 iterator __e = end();
978 for (; __j != __e && __n > 0; --__n, ++__i, ++__j)
981 insert_after(__i, __n, __v);
983 erase_after(__i, __e);
986 #ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
988 template <class _Tp, class _Alloc>
989 inline _LIBCPP_INLINE_VISIBILITY
991 forward_list<_Tp, _Alloc>::assign(initializer_list<value_type> __il)
993 assign(__il.begin(), __il.end());
996 #endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
998 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
999 #ifndef _LIBCPP_HAS_NO_VARIADICS
1001 template <class _Tp, class _Alloc>
1002 template <class... _Args>
1004 forward_list<_Tp, _Alloc>::emplace_front(_Args&&... __args)
1006 __node_allocator& __a = base::__alloc();
1007 typedef __allocator_destructor<__node_allocator> _Dp;
1008 unique_ptr<__node, _Dp> __h(__node_traits::allocate(__a, 1), _Dp(__a, 1));
1009 __node_traits::construct(__a, _VSTD::addressof(__h->__value_),
1010 _VSTD::forward<_Args>(__args)...);
1011 __h->__next_ = base::__before_begin()->__next_;
1012 base::__before_begin()->__next_ = __h.release();
1015 #endif // _LIBCPP_HAS_NO_VARIADICS
1017 template <class _Tp, class _Alloc>
1019 forward_list<_Tp, _Alloc>::push_front(value_type&& __v)
1021 __node_allocator& __a = base::__alloc();
1022 typedef __allocator_destructor<__node_allocator> _Dp;
1023 unique_ptr<__node, _Dp> __h(__node_traits::allocate(__a, 1), _Dp(__a, 1));
1024 __node_traits::construct(__a, _VSTD::addressof(__h->__value_), _VSTD::move(__v));
1025 __h->__next_ = base::__before_begin()->__next_;
1026 base::__before_begin()->__next_ = __h.release();
1029 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
1031 template <class _Tp, class _Alloc>
1033 forward_list<_Tp, _Alloc>::push_front(const value_type& __v)
1035 __node_allocator& __a = base::__alloc();
1036 typedef __allocator_destructor<__node_allocator> _Dp;
1037 unique_ptr<__node, _Dp> __h(__node_traits::allocate(__a, 1), _Dp(__a, 1));
1038 __node_traits::construct(__a, _VSTD::addressof(__h->__value_), __v);
1039 __h->__next_ = base::__before_begin()->__next_;
1040 base::__before_begin()->__next_ = __h.release();
1043 template <class _Tp, class _Alloc>
1045 forward_list<_Tp, _Alloc>::pop_front()
1047 __node_allocator& __a = base::__alloc();
1048 __node_pointer __p = base::__before_begin()->__next_;
1049 base::__before_begin()->__next_ = __p->__next_;
1050 __node_traits::destroy(__a, _VSTD::addressof(__p->__value_));
1051 __node_traits::deallocate(__a, __p, 1);
1054 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
1055 #ifndef _LIBCPP_HAS_NO_VARIADICS
1057 template <class _Tp, class _Alloc>
1058 template <class... _Args>
1059 typename forward_list<_Tp, _Alloc>::iterator
1060 forward_list<_Tp, _Alloc>::emplace_after(const_iterator __p, _Args&&... __args)
1062 __node_pointer const __r = __p.__ptr_;
1063 __node_allocator& __a = base::__alloc();
1064 typedef __allocator_destructor<__node_allocator> _Dp;
1065 unique_ptr<__node, _Dp> __h(__node_traits::allocate(__a, 1), _Dp(__a, 1));
1066 __node_traits::construct(__a, _VSTD::addressof(__h->__value_),
1067 _VSTD::forward<_Args>(__args)...);
1068 __h->__next_ = __r->__next_;
1069 __r->__next_ = __h.release();
1070 return iterator(__r->__next_);
1073 #endif // _LIBCPP_HAS_NO_VARIADICS
1075 template <class _Tp, class _Alloc>
1076 typename forward_list<_Tp, _Alloc>::iterator
1077 forward_list<_Tp, _Alloc>::insert_after(const_iterator __p, value_type&& __v)
1079 __node_pointer const __r = __p.__ptr_;
1080 __node_allocator& __a = base::__alloc();
1081 typedef __allocator_destructor<__node_allocator> _Dp;
1082 unique_ptr<__node, _Dp> __h(__node_traits::allocate(__a, 1), _Dp(__a, 1));
1083 __node_traits::construct(__a, _VSTD::addressof(__h->__value_), _VSTD::move(__v));
1084 __h->__next_ = __r->__next_;
1085 __r->__next_ = __h.release();
1086 return iterator(__r->__next_);
1089 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
1091 template <class _Tp, class _Alloc>
1092 typename forward_list<_Tp, _Alloc>::iterator
1093 forward_list<_Tp, _Alloc>::insert_after(const_iterator __p, const value_type& __v)
1095 __node_pointer const __r = __p.__ptr_;
1096 __node_allocator& __a = base::__alloc();
1097 typedef __allocator_destructor<__node_allocator> _Dp;
1098 unique_ptr<__node, _Dp> __h(__node_traits::allocate(__a, 1), _Dp(__a, 1));
1099 __node_traits::construct(__a, _VSTD::addressof(__h->__value_), __v);
1100 __h->__next_ = __r->__next_;
1101 __r->__next_ = __h.release();
1102 return iterator(__r->__next_);
1105 template <class _Tp, class _Alloc>
1106 typename forward_list<_Tp, _Alloc>::iterator
1107 forward_list<_Tp, _Alloc>::insert_after(const_iterator __p, size_type __n,
1108 const value_type& __v)
1110 __node_pointer __r = __p.__ptr_;
1113 __node_allocator& __a = base::__alloc();
1114 typedef __allocator_destructor<__node_allocator> _Dp;
1115 unique_ptr<__node, _Dp> __h(__node_traits::allocate(__a, 1), _Dp(__a, 1));
1116 __node_traits::construct(__a, _VSTD::addressof(__h->__value_), __v);
1117 __node_pointer __first = __h.release();
1118 __node_pointer __last = __first;
1119 #ifndef _LIBCPP_NO_EXCEPTIONS
1122 #endif // _LIBCPP_NO_EXCEPTIONS
1123 for (--__n; __n != 0; --__n, __last = __last->__next_)
1125 __h.reset(__node_traits::allocate(__a, 1));
1126 __node_traits::construct(__a, _VSTD::addressof(__h->__value_), __v);
1127 __last->__next_ = __h.release();
1129 #ifndef _LIBCPP_NO_EXCEPTIONS
1133 while (__first != nullptr)
1135 __node_pointer __next = __first->__next_;
1136 __node_traits::destroy(__a, _VSTD::addressof(__first->__value_));
1137 __node_traits::deallocate(__a, __first, 1);
1142 #endif // _LIBCPP_NO_EXCEPTIONS
1143 __last->__next_ = __r->__next_;
1144 __r->__next_ = __first;
1147 return iterator(__r);
1150 template <class _Tp, class _Alloc>
1151 template <class _InputIterator>
1154 __is_input_iterator<_InputIterator>::value,
1155 typename forward_list<_Tp, _Alloc>::iterator
1157 forward_list<_Tp, _Alloc>::insert_after(const_iterator __p,
1158 _InputIterator __f, _InputIterator __l)
1160 __node_pointer __r = __p.__ptr_;
1163 __node_allocator& __a = base::__alloc();
1164 typedef __allocator_destructor<__node_allocator> _Dp;
1165 unique_ptr<__node, _Dp> __h(__node_traits::allocate(__a, 1), _Dp(__a, 1));
1166 __node_traits::construct(__a, _VSTD::addressof(__h->__value_), *__f);
1167 __node_pointer __first = __h.release();
1168 __node_pointer __last = __first;
1169 #ifndef _LIBCPP_NO_EXCEPTIONS
1172 #endif // _LIBCPP_NO_EXCEPTIONS
1173 for (++__f; __f != __l; ++__f, __last = __last->__next_)
1175 __h.reset(__node_traits::allocate(__a, 1));
1176 __node_traits::construct(__a, _VSTD::addressof(__h->__value_), *__f);
1177 __last->__next_ = __h.release();
1179 #ifndef _LIBCPP_NO_EXCEPTIONS
1183 while (__first != nullptr)
1185 __node_pointer __next = __first->__next_;
1186 __node_traits::destroy(__a, _VSTD::addressof(__first->__value_));
1187 __node_traits::deallocate(__a, __first, 1);
1192 #endif // _LIBCPP_NO_EXCEPTIONS
1193 __last->__next_ = __r->__next_;
1194 __r->__next_ = __first;
1197 return iterator(__r);
1200 template <class _Tp, class _Alloc>
1201 typename forward_list<_Tp, _Alloc>::iterator
1202 forward_list<_Tp, _Alloc>::erase_after(const_iterator __f)
1204 __node_pointer __p = __f.__ptr_;
1205 __node_pointer __n = __p->__next_;
1206 __p->__next_ = __n->__next_;
1207 __node_allocator& __a = base::__alloc();
1208 __node_traits::destroy(__a, _VSTD::addressof(__n->__value_));
1209 __node_traits::deallocate(__a, __n, 1);
1210 return iterator(__p->__next_);
1213 template <class _Tp, class _Alloc>
1214 typename forward_list<_Tp, _Alloc>::iterator
1215 forward_list<_Tp, _Alloc>::erase_after(const_iterator __f, const_iterator __l)
1217 __node_pointer __e = __l.__ptr_;
1220 __node_pointer __p = __f.__ptr_;
1221 __node_pointer __n = __p->__next_;
1225 __node_allocator& __a = base::__alloc();
1229 __node_traits::destroy(__a, _VSTD::addressof(__n->__value_));
1230 __node_traits::deallocate(__a, __n, 1);
1232 } while (__n != __e);
1235 return iterator(__e);
1238 template <class _Tp, class _Alloc>
1240 forward_list<_Tp, _Alloc>::resize(size_type __n)
1243 iterator __p = before_begin();
1244 iterator __i = begin();
1245 iterator __e = end();
1246 for (; __i != __e && __sz < __n; ++__p, ++__i, ++__sz)
1249 erase_after(__p, __e);
1255 __node_allocator& __a = base::__alloc();
1256 typedef __allocator_destructor<__node_allocator> _Dp;
1257 unique_ptr<__node, _Dp> __h(nullptr, _Dp(__a, 1));
1258 for (__node_pointer __ptr = __p.__ptr_; __n > 0; --__n,
1259 __ptr = __ptr->__next_)
1261 __h.reset(__node_traits::allocate(__a, 1));
1262 __node_traits::construct(__a, _VSTD::addressof(__h->__value_));
1263 __h->__next_ = nullptr;
1264 __ptr->__next_ = __h.release();
1270 template <class _Tp, class _Alloc>
1272 forward_list<_Tp, _Alloc>::resize(size_type __n, const value_type& __v)
1275 iterator __p = before_begin();
1276 iterator __i = begin();
1277 iterator __e = end();
1278 for (; __i != __e && __sz < __n; ++__p, ++__i, ++__sz)
1281 erase_after(__p, __e);
1287 __node_allocator& __a = base::__alloc();
1288 typedef __allocator_destructor<__node_allocator> _Dp;
1289 unique_ptr<__node, _Dp> __h(nullptr, _Dp(__a, 1));
1290 for (__node_pointer __ptr = __p.__ptr_; __n > 0; --__n,
1291 __ptr = __ptr->__next_)
1293 __h.reset(__node_traits::allocate(__a, 1));
1294 __node_traits::construct(__a, _VSTD::addressof(__h->__value_), __v);
1295 __h->__next_ = nullptr;
1296 __ptr->__next_ = __h.release();
1302 template <class _Tp, class _Alloc>
1304 forward_list<_Tp, _Alloc>::splice_after(const_iterator __p,
1309 if (__p.__ptr_->__next_ != nullptr)
1311 const_iterator __lm1 = __x.before_begin();
1312 while (__lm1.__ptr_->__next_ != nullptr)
1314 __lm1.__ptr_->__next_ = __p.__ptr_->__next_;
1316 __p.__ptr_->__next_ = __x.__before_begin()->__next_;
1317 __x.__before_begin()->__next_ = nullptr;
1321 template <class _Tp, class _Alloc>
1323 forward_list<_Tp, _Alloc>::splice_after(const_iterator __p,
1327 const_iterator __lm1 = _VSTD::next(__i);
1328 if (__p != __i && __p != __lm1)
1330 __i.__ptr_->__next_ = __lm1.__ptr_->__next_;
1331 __lm1.__ptr_->__next_ = __p.__ptr_->__next_;
1332 __p.__ptr_->__next_ = __lm1.__ptr_;
1336 template <class _Tp, class _Alloc>
1338 forward_list<_Tp, _Alloc>::splice_after(const_iterator __p,
1340 const_iterator __f, const_iterator __l)
1342 if (__f != __l && __p != __f)
1344 const_iterator __lm1 = __f;
1345 while (__lm1.__ptr_->__next_ != __l.__ptr_)
1349 __lm1.__ptr_->__next_ = __p.__ptr_->__next_;
1350 __p.__ptr_->__next_ = __f.__ptr_->__next_;
1351 __f.__ptr_->__next_ = __l.__ptr_;
1356 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
1358 template <class _Tp, class _Alloc>
1359 inline _LIBCPP_INLINE_VISIBILITY
1361 forward_list<_Tp, _Alloc>::splice_after(const_iterator __p,
1364 splice_after(__p, __x);
1367 template <class _Tp, class _Alloc>
1368 inline _LIBCPP_INLINE_VISIBILITY
1370 forward_list<_Tp, _Alloc>::splice_after(const_iterator __p,
1374 splice_after(__p, __x, __i);
1377 template <class _Tp, class _Alloc>
1378 inline _LIBCPP_INLINE_VISIBILITY
1380 forward_list<_Tp, _Alloc>::splice_after(const_iterator __p,
1382 const_iterator __f, const_iterator __l)
1384 splice_after(__p, __x, __f, __l);
1387 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
1389 template <class _Tp, class _Alloc>
1391 forward_list<_Tp, _Alloc>::remove(const value_type& __v)
1393 iterator __e = end();
1394 for (iterator __i = before_begin(); __i.__ptr_->__next_ != nullptr;)
1396 if (__i.__ptr_->__next_->__value_ == __v)
1398 iterator __j = _VSTD::next(__i, 2);
1399 for (; __j != __e && *__j == __v; ++__j)
1401 erase_after(__i, __j);
1411 template <class _Tp, class _Alloc>
1412 template <class _Predicate>
1414 forward_list<_Tp, _Alloc>::remove_if(_Predicate __pred)
1416 iterator __e = end();
1417 for (iterator __i = before_begin(); __i.__ptr_->__next_ != nullptr;)
1419 if (__pred(__i.__ptr_->__next_->__value_))
1421 iterator __j = _VSTD::next(__i, 2);
1422 for (; __j != __e && __pred(*__j); ++__j)
1424 erase_after(__i, __j);
1434 template <class _Tp, class _Alloc>
1435 template <class _BinaryPredicate>
1437 forward_list<_Tp, _Alloc>::unique(_BinaryPredicate __binary_pred)
1439 for (iterator __i = begin(), __e = end(); __i != __e;)
1441 iterator __j = _VSTD::next(__i);
1442 for (; __j != __e && __binary_pred(*__i, *__j); ++__j)
1444 if (__i.__ptr_->__next_ != __j.__ptr_)
1445 erase_after(__i, __j);
1450 template <class _Tp, class _Alloc>
1451 template <class _Compare>
1453 forward_list<_Tp, _Alloc>::merge(forward_list& __x, _Compare __comp)
1457 base::__before_begin()->__next_ = __merge(base::__before_begin()->__next_,
1458 __x.__before_begin()->__next_,
1460 __x.__before_begin()->__next_ = nullptr;
1464 template <class _Tp, class _Alloc>
1465 template <class _Compare>
1466 typename forward_list<_Tp, _Alloc>::__node_pointer
1467 forward_list<_Tp, _Alloc>::__merge(__node_pointer __f1, __node_pointer __f2,
1470 if (__f1 == nullptr)
1472 if (__f2 == nullptr)
1475 if (__comp(__f2->__value_, __f1->__value_))
1477 __node_pointer __t = __f2;
1478 while (__t->__next_ != nullptr &&
1479 __comp(__t->__next_->__value_, __f1->__value_))
1482 __f2 = __t->__next_;
1483 __t->__next_ = __f1;
1487 __node_pointer __p = __f1;
1488 __f1 = __f1->__next_;
1489 while (__f1 != nullptr && __f2 != nullptr)
1491 if (__comp(__f2->__value_, __f1->__value_))
1493 __node_pointer __t = __f2;
1494 while (__t->__next_ != nullptr &&
1495 __comp(__t->__next_->__value_, __f1->__value_))
1497 __p->__next_ = __f2;
1498 __f2 = __t->__next_;
1499 __t->__next_ = __f1;
1502 __f1 = __f1->__next_;
1504 if (__f2 != nullptr)
1505 __p->__next_ = __f2;
1509 template <class _Tp, class _Alloc>
1510 template <class _Compare>
1511 inline _LIBCPP_INLINE_VISIBILITY
1513 forward_list<_Tp, _Alloc>::sort(_Compare __comp)
1515 base::__before_begin()->__next_ = __sort(base::__before_begin()->__next_,
1516 _VSTD::distance(begin(), end()), __comp);
1519 template <class _Tp, class _Alloc>
1520 template <class _Compare>
1521 typename forward_list<_Tp, _Alloc>::__node_pointer
1522 forward_list<_Tp, _Alloc>::__sort(__node_pointer __f1, difference_type __sz,
1531 if (__comp(__f1->__next_->__value_, __f1->__value_))
1533 __node_pointer __t = __f1->__next_;
1534 __t->__next_ = __f1;
1535 __f1->__next_ = nullptr;
1540 difference_type __sz1 = __sz / 2;
1541 difference_type __sz2 = __sz - __sz1;
1542 __node_pointer __t = _VSTD::next(iterator(__f1), __sz1 - 1).__ptr_;
1543 __node_pointer __f2 = __t->__next_;
1544 __t->__next_ = nullptr;
1545 return __merge(__sort(__f1, __sz1, __comp),
1546 __sort(__f2, __sz2, __comp), __comp);
1549 template <class _Tp, class _Alloc>
1551 forward_list<_Tp, _Alloc>::reverse() _NOEXCEPT
1553 __node_pointer __p = base::__before_begin()->__next_;
1556 __node_pointer __f = __p->__next_;
1557 __p->__next_ = nullptr;
1558 while (__f != nullptr)
1560 __node_pointer __t = __f->__next_;
1565 base::__before_begin()->__next_ = __p;
1569 template <class _Tp, class _Alloc>
1570 bool operator==(const forward_list<_Tp, _Alloc>& __x,
1571 const forward_list<_Tp, _Alloc>& __y)
1573 typedef forward_list<_Tp, _Alloc> _Cp;
1574 typedef typename _Cp::const_iterator _Ip;
1575 _Ip __ix = __x.begin();
1576 _Ip __ex = __x.end();
1577 _Ip __iy = __y.begin();
1578 _Ip __ey = __y.end();
1579 for (; __ix != __ex && __iy != __ey; ++__ix, ++__iy)
1580 if (!(*__ix == *__iy))
1582 return (__ix == __ex) == (__iy == __ey);
1585 template <class _Tp, class _Alloc>
1586 inline _LIBCPP_INLINE_VISIBILITY
1587 bool operator!=(const forward_list<_Tp, _Alloc>& __x,
1588 const forward_list<_Tp, _Alloc>& __y)
1590 return !(__x == __y);
1593 template <class _Tp, class _Alloc>
1594 inline _LIBCPP_INLINE_VISIBILITY
1595 bool operator< (const forward_list<_Tp, _Alloc>& __x,
1596 const forward_list<_Tp, _Alloc>& __y)
1598 return _VSTD::lexicographical_compare(__x.begin(), __x.end(),
1599 __y.begin(), __y.end());
1602 template <class _Tp, class _Alloc>
1603 inline _LIBCPP_INLINE_VISIBILITY
1604 bool operator> (const forward_list<_Tp, _Alloc>& __x,
1605 const forward_list<_Tp, _Alloc>& __y)
1610 template <class _Tp, class _Alloc>
1611 inline _LIBCPP_INLINE_VISIBILITY
1612 bool operator>=(const forward_list<_Tp, _Alloc>& __x,
1613 const forward_list<_Tp, _Alloc>& __y)
1615 return !(__x < __y);
1618 template <class _Tp, class _Alloc>
1619 inline _LIBCPP_INLINE_VISIBILITY
1620 bool operator<=(const forward_list<_Tp, _Alloc>& __x,
1621 const forward_list<_Tp, _Alloc>& __y)
1623 return !(__y < __x);
1626 template <class _Tp, class _Alloc>
1627 inline _LIBCPP_INLINE_VISIBILITY
1629 swap(forward_list<_Tp, _Alloc>& __x, forward_list<_Tp, _Alloc>& __y)
1630 _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y)))
1635 _LIBCPP_END_NAMESPACE_STD
1637 #endif // _LIBCPP_FORWARD_LIST