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 forward_list;
216 template<class _NodeConstPtr> class __forward_list_const_iterator;
218 template <class _NodePtr>
219 class _LIBCPP_VISIBLE __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 forward_list;
229 template<class> friend class __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 &__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_VISIBLE __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 &__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::const_pointer __node_const_pointer;
373 __compressed_pair<__begin_node, __node_allocator> __before_begin_;
375 _LIBCPP_INLINE_VISIBILITY
376 __node_pointer __before_begin() _NOEXCEPT
377 {return pointer_traits<__node_pointer>::pointer_to(
378 static_cast<__node&>(__before_begin_.first()));}
379 _LIBCPP_INLINE_VISIBILITY
380 __node_const_pointer __before_begin() const _NOEXCEPT
381 {return pointer_traits<__node_const_pointer>::pointer_to(
382 static_cast<const __node&>(__before_begin_.first()));}
384 _LIBCPP_INLINE_VISIBILITY
385 __node_allocator& __alloc() _NOEXCEPT
386 {return __before_begin_.second();}
387 _LIBCPP_INLINE_VISIBILITY
388 const __node_allocator& __alloc() const _NOEXCEPT
389 {return __before_begin_.second();}
391 typedef __forward_list_iterator<__node_pointer> iterator;
392 typedef __forward_list_const_iterator<__node_const_pointer> const_iterator;
394 _LIBCPP_INLINE_VISIBILITY
395 __forward_list_base()
396 _NOEXCEPT_(is_nothrow_default_constructible<__node_allocator>::value)
397 : __before_begin_(__begin_node()) {}
398 _LIBCPP_INLINE_VISIBILITY
399 __forward_list_base(const allocator_type& __a)
400 : __before_begin_(__begin_node(), __node_allocator(__a)) {}
402 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
404 __forward_list_base(__forward_list_base&& __x)
405 _NOEXCEPT_(is_nothrow_move_constructible<__node_allocator>::value);
406 __forward_list_base(__forward_list_base&& __x, const allocator_type& __a);
407 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
410 __forward_list_base(const __forward_list_base&);
411 __forward_list_base& operator=(const __forward_list_base&);
414 ~__forward_list_base();
417 _LIBCPP_INLINE_VISIBILITY
418 void __copy_assign_alloc(const __forward_list_base& __x)
419 {__copy_assign_alloc(__x, integral_constant<bool,
420 __node_traits::propagate_on_container_copy_assignment::value>());}
422 _LIBCPP_INLINE_VISIBILITY
423 void __move_assign_alloc(__forward_list_base& __x)
424 _NOEXCEPT_(!__node_traits::propagate_on_container_move_assignment::value ||
425 is_nothrow_move_assignable<__node_allocator>::value)
426 {__move_assign_alloc(__x, integral_constant<bool,
427 __node_traits::propagate_on_container_move_assignment::value>());}
430 void swap(__forward_list_base& __x)
431 _NOEXCEPT_(!__node_traits::propagate_on_container_swap::value ||
432 __is_nothrow_swappable<__node_allocator>::value);
434 void clear() _NOEXCEPT;
437 _LIBCPP_INLINE_VISIBILITY
438 void __copy_assign_alloc(const __forward_list_base&, false_type) {}
439 _LIBCPP_INLINE_VISIBILITY
440 void __copy_assign_alloc(const __forward_list_base& __x, true_type)
442 if (__alloc() != __x.__alloc())
444 __alloc() = __x.__alloc();
447 _LIBCPP_INLINE_VISIBILITY
448 void __move_assign_alloc(__forward_list_base& __x, false_type) _NOEXCEPT
450 _LIBCPP_INLINE_VISIBILITY
451 void __move_assign_alloc(__forward_list_base& __x, true_type)
452 _NOEXCEPT_(is_nothrow_move_assignable<__node_allocator>::value)
453 {__alloc() = _VSTD::move(__x.__alloc());}
455 _LIBCPP_INLINE_VISIBILITY
456 static void __swap_alloc(__node_allocator& __x, __node_allocator& __y)
457 _NOEXCEPT_(!__node_traits::propagate_on_container_swap::value ||
458 __is_nothrow_swappable<__node_allocator>::value)
459 {__swap_alloc(__x, __y, integral_constant<bool,
460 __node_traits::propagate_on_container_swap::value>());}
461 _LIBCPP_INLINE_VISIBILITY
462 static void __swap_alloc(__node_allocator& __x, __node_allocator& __y,
466 _LIBCPP_INLINE_VISIBILITY
467 static void __swap_alloc(__node_allocator& __x, __node_allocator& __y,
469 _NOEXCEPT_(__is_nothrow_swappable<__node_allocator>::value)
476 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
478 template <class _Tp, class _Alloc>
479 inline _LIBCPP_INLINE_VISIBILITY
480 __forward_list_base<_Tp, _Alloc>::__forward_list_base(__forward_list_base&& __x)
481 _NOEXCEPT_(is_nothrow_move_constructible<__node_allocator>::value)
482 : __before_begin_(_VSTD::move(__x.__before_begin_))
484 __x.__before_begin()->__next_ = nullptr;
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 const allocator_type& __a)
491 : __before_begin_(__begin_node(), __node_allocator(__a))
493 if (__alloc() == __x.__alloc())
495 __before_begin()->__next_ = __x.__before_begin()->__next_;
496 __x.__before_begin()->__next_ = nullptr;
500 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
502 template <class _Tp, class _Alloc>
503 __forward_list_base<_Tp, _Alloc>::~__forward_list_base()
508 template <class _Tp, class _Alloc>
509 inline _LIBCPP_INLINE_VISIBILITY
511 __forward_list_base<_Tp, _Alloc>::swap(__forward_list_base& __x)
512 _NOEXCEPT_(!__node_traits::propagate_on_container_swap::value ||
513 __is_nothrow_swappable<__node_allocator>::value)
515 __swap_alloc(__alloc(), __x.__alloc());
517 swap(__before_begin()->__next_, __x.__before_begin()->__next_);
520 template <class _Tp, class _Alloc>
522 __forward_list_base<_Tp, _Alloc>::clear() _NOEXCEPT
524 __node_allocator& __a = __alloc();
525 for (__node_pointer __p = __before_begin()->__next_; __p != nullptr;)
527 __node_pointer __next = __p->__next_;
528 __node_traits::destroy(__a, _VSTD::addressof(__p->__value_));
529 __node_traits::deallocate(__a, __p, 1);
532 __before_begin()->__next_ = nullptr;
535 template <class _Tp, class _Alloc = allocator<_Tp> >
536 class _LIBCPP_VISIBLE forward_list
537 : private __forward_list_base<_Tp, _Alloc>
539 typedef __forward_list_base<_Tp, _Alloc> base;
540 typedef typename base::__node_allocator __node_allocator;
541 typedef typename base::__node __node;
542 typedef typename base::__node_traits __node_traits;
543 typedef typename base::__node_pointer __node_pointer;
546 typedef _Tp value_type;
547 typedef _Alloc allocator_type;
549 typedef value_type& reference;
550 typedef const value_type& const_reference;
551 typedef typename allocator_traits<allocator_type>::pointer pointer;
552 typedef typename allocator_traits<allocator_type>::const_pointer const_pointer;
553 typedef typename allocator_traits<allocator_type>::size_type size_type;
554 typedef typename allocator_traits<allocator_type>::difference_type difference_type;
556 typedef typename base::iterator iterator;
557 typedef typename base::const_iterator const_iterator;
559 _LIBCPP_INLINE_VISIBILITY
561 _NOEXCEPT_(is_nothrow_default_constructible<__node_allocator>::value)
563 explicit forward_list(const allocator_type& __a);
564 explicit forward_list(size_type __n);
565 forward_list(size_type __n, const value_type& __v);
566 forward_list(size_type __n, const value_type& __v, const allocator_type& __a);
567 template <class _InputIterator>
568 forward_list(_InputIterator __f, _InputIterator __l,
570 __is_input_iterator<_InputIterator>::value
572 template <class _InputIterator>
573 forward_list(_InputIterator __f, _InputIterator __l,
574 const allocator_type& __a,
576 __is_input_iterator<_InputIterator>::value
578 forward_list(const forward_list& __x);
579 forward_list(const forward_list& __x, const allocator_type& __a);
580 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
581 _LIBCPP_INLINE_VISIBILITY
582 forward_list(forward_list&& __x)
583 _NOEXCEPT_(is_nothrow_move_constructible<base>::value)
584 : base(_VSTD::move(__x)) {}
585 forward_list(forward_list&& __x, const allocator_type& __a);
586 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
587 #ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
588 forward_list(initializer_list<value_type> __il);
589 forward_list(initializer_list<value_type> __il, const allocator_type& __a);
590 #endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
592 // ~forward_list() = default;
594 forward_list& operator=(const forward_list& __x);
595 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
596 forward_list& operator=(forward_list&& __x)
598 __node_traits::propagate_on_container_move_assignment::value &&
599 is_nothrow_move_assignable<allocator_type>::value);
601 #ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
602 forward_list& operator=(initializer_list<value_type> __il);
603 #endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
605 template <class _InputIterator>
608 __is_input_iterator<_InputIterator>::value,
611 assign(_InputIterator __f, _InputIterator __l);
612 void assign(size_type __n, const value_type& __v);
613 #ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
614 void assign(initializer_list<value_type> __il);
615 #endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
617 _LIBCPP_INLINE_VISIBILITY
618 allocator_type get_allocator() const _NOEXCEPT
619 {return allocator_type(base::__alloc());}
621 _LIBCPP_INLINE_VISIBILITY
622 iterator begin() _NOEXCEPT
623 {return iterator(base::__before_begin()->__next_);}
624 _LIBCPP_INLINE_VISIBILITY
625 const_iterator begin() const _NOEXCEPT
626 {return const_iterator(base::__before_begin()->__next_);}
627 _LIBCPP_INLINE_VISIBILITY
628 iterator end() _NOEXCEPT
629 {return iterator(nullptr);}
630 _LIBCPP_INLINE_VISIBILITY
631 const_iterator end() const _NOEXCEPT
632 {return const_iterator(nullptr);}
634 _LIBCPP_INLINE_VISIBILITY
635 const_iterator cbegin() const _NOEXCEPT
636 {return const_iterator(base::__before_begin()->__next_);}
637 _LIBCPP_INLINE_VISIBILITY
638 const_iterator cend() const _NOEXCEPT
639 {return const_iterator(nullptr);}
641 _LIBCPP_INLINE_VISIBILITY
642 iterator before_begin() _NOEXCEPT
643 {return iterator(base::__before_begin());}
644 _LIBCPP_INLINE_VISIBILITY
645 const_iterator before_begin() const _NOEXCEPT
646 {return const_iterator(base::__before_begin());}
647 _LIBCPP_INLINE_VISIBILITY
648 const_iterator cbefore_begin() const _NOEXCEPT
649 {return const_iterator(base::__before_begin());}
651 _LIBCPP_INLINE_VISIBILITY
652 bool empty() const _NOEXCEPT
653 {return base::__before_begin()->__next_ == nullptr;}
654 _LIBCPP_INLINE_VISIBILITY
655 size_type max_size() const _NOEXCEPT
656 {return numeric_limits<size_type>::max();}
658 _LIBCPP_INLINE_VISIBILITY
659 reference front() {return base::__before_begin()->__next_->__value_;}
660 _LIBCPP_INLINE_VISIBILITY
661 const_reference front() const {return base::__before_begin()->__next_->__value_;}
663 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
664 #ifndef _LIBCPP_HAS_NO_VARIADICS
665 template <class... _Args> void emplace_front(_Args&&... __args);
667 void push_front(value_type&& __v);
668 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
669 void push_front(const value_type& __v);
673 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
674 #ifndef _LIBCPP_HAS_NO_VARIADICS
675 template <class... _Args>
676 iterator emplace_after(const_iterator __p, _Args&&... __args);
677 #endif // _LIBCPP_HAS_NO_VARIADICS
678 iterator insert_after(const_iterator __p, value_type&& __v);
679 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
680 iterator insert_after(const_iterator __p, const value_type& __v);
681 iterator insert_after(const_iterator __p, size_type __n, const value_type& __v);
682 template <class _InputIterator>
683 _LIBCPP_INLINE_VISIBILITY
686 __is_input_iterator<_InputIterator>::value,
689 insert_after(const_iterator __p, _InputIterator __f, _InputIterator __l);
690 #ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
691 iterator insert_after(const_iterator __p, initializer_list<value_type> __il)
692 {return insert_after(__p, __il.begin(), __il.end());}
693 #endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
695 iterator erase_after(const_iterator __p);
696 iterator erase_after(const_iterator __f, const_iterator __l);
698 _LIBCPP_INLINE_VISIBILITY
699 void swap(forward_list& __x)
700 _NOEXCEPT_(!__node_traits::propagate_on_container_swap::value ||
701 __is_nothrow_swappable<__node_allocator>::value)
704 void resize(size_type __n);
705 void resize(size_type __n, const value_type& __v);
706 _LIBCPP_INLINE_VISIBILITY
707 void clear() _NOEXCEPT {base::clear();}
709 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
710 _LIBCPP_INLINE_VISIBILITY
711 void splice_after(const_iterator __p, forward_list&& __x);
712 _LIBCPP_INLINE_VISIBILITY
713 void splice_after(const_iterator __p, forward_list&& __x, const_iterator __i);
714 _LIBCPP_INLINE_VISIBILITY
715 void splice_after(const_iterator __p, forward_list&& __x,
716 const_iterator __f, const_iterator __l);
717 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
718 void splice_after(const_iterator __p, forward_list& __x);
719 void splice_after(const_iterator __p, forward_list& __x, const_iterator __i);
720 void splice_after(const_iterator __p, forward_list& __x,
721 const_iterator __f, const_iterator __l);
722 void remove(const value_type& __v);
723 template <class _Predicate> void remove_if(_Predicate __pred);
724 _LIBCPP_INLINE_VISIBILITY
725 void unique() {unique(__equal_to<value_type>());}
726 template <class _BinaryPredicate> void unique(_BinaryPredicate __binary_pred);
727 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
728 _LIBCPP_INLINE_VISIBILITY
729 void merge(forward_list&& __x) {merge(__x, __less<value_type>());}
730 template <class _Compare>
731 _LIBCPP_INLINE_VISIBILITY
732 void merge(forward_list&& __x, _Compare __comp)
733 {merge(__x, _VSTD::move(__comp));}
734 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
735 _LIBCPP_INLINE_VISIBILITY
736 void merge(forward_list& __x) {merge(__x, __less<value_type>());}
737 template <class _Compare> void merge(forward_list& __x, _Compare __comp);
738 _LIBCPP_INLINE_VISIBILITY
739 void sort() {sort(__less<value_type>());}
740 template <class _Compare> void sort(_Compare __comp);
741 void reverse() _NOEXCEPT;
745 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
746 void __move_assign(forward_list& __x, true_type)
747 _NOEXCEPT_(is_nothrow_move_assignable<allocator_type>::value);
748 void __move_assign(forward_list& __x, false_type);
749 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
751 template <class _Compare>
754 __merge(__node_pointer __f1, __node_pointer __f2, _Compare& __comp);
756 template <class _Compare>
759 __sort(__node_pointer __f, difference_type __sz, _Compare& __comp);
762 template <class _Tp, class _Alloc>
763 inline _LIBCPP_INLINE_VISIBILITY
764 forward_list<_Tp, _Alloc>::forward_list(const allocator_type& __a)
769 template <class _Tp, class _Alloc>
770 forward_list<_Tp, _Alloc>::forward_list(size_type __n)
774 __node_allocator& __a = base::__alloc();
775 typedef __allocator_destructor<__node_allocator> _Dp;
776 unique_ptr<__node, _Dp> __h(nullptr, _Dp(__a, 1));
777 for (__node_pointer __p = base::__before_begin(); __n > 0; --__n,
780 __h.reset(__node_traits::allocate(__a, 1));
781 __node_traits::construct(__a, _VSTD::addressof(__h->__value_));
782 __h->__next_ = nullptr;
783 __p->__next_ = __h.release();
788 template <class _Tp, class _Alloc>
789 forward_list<_Tp, _Alloc>::forward_list(size_type __n, const value_type& __v)
791 insert_after(cbefore_begin(), __n, __v);
794 template <class _Tp, class _Alloc>
795 forward_list<_Tp, _Alloc>::forward_list(size_type __n, const value_type& __v,
796 const allocator_type& __a)
799 insert_after(cbefore_begin(), __n, __v);
802 template <class _Tp, class _Alloc>
803 template <class _InputIterator>
804 forward_list<_Tp, _Alloc>::forward_list(_InputIterator __f, _InputIterator __l,
806 __is_input_iterator<_InputIterator>::value
809 insert_after(cbefore_begin(), __f, __l);
812 template <class _Tp, class _Alloc>
813 template <class _InputIterator>
814 forward_list<_Tp, _Alloc>::forward_list(_InputIterator __f, _InputIterator __l,
815 const allocator_type& __a,
817 __is_input_iterator<_InputIterator>::value
821 insert_after(cbefore_begin(), __f, __l);
824 template <class _Tp, class _Alloc>
825 forward_list<_Tp, _Alloc>::forward_list(const forward_list& __x)
826 : base(allocator_type(
827 __node_traits::select_on_container_copy_construction(__x.__alloc())
831 insert_after(cbefore_begin(), __x.begin(), __x.end());
834 template <class _Tp, class _Alloc>
835 forward_list<_Tp, _Alloc>::forward_list(const forward_list& __x,
836 const allocator_type& __a)
839 insert_after(cbefore_begin(), __x.begin(), __x.end());
842 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
844 template <class _Tp, class _Alloc>
845 forward_list<_Tp, _Alloc>::forward_list(forward_list&& __x,
846 const allocator_type& __a)
847 : base(_VSTD::move(__x), __a)
849 if (base::__alloc() != __x.__alloc())
851 typedef move_iterator<iterator> _Ip;
852 insert_after(cbefore_begin(), _Ip(__x.begin()), _Ip(__x.end()));
856 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
858 #ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
860 template <class _Tp, class _Alloc>
861 forward_list<_Tp, _Alloc>::forward_list(initializer_list<value_type> __il)
863 insert_after(cbefore_begin(), __il.begin(), __il.end());
866 template <class _Tp, class _Alloc>
867 forward_list<_Tp, _Alloc>::forward_list(initializer_list<value_type> __il,
868 const allocator_type& __a)
871 insert_after(cbefore_begin(), __il.begin(), __il.end());
874 #endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
876 template <class _Tp, class _Alloc>
877 forward_list<_Tp, _Alloc>&
878 forward_list<_Tp, _Alloc>::operator=(const forward_list& __x)
882 base::__copy_assign_alloc(__x);
883 assign(__x.begin(), __x.end());
888 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
890 template <class _Tp, class _Alloc>
892 forward_list<_Tp, _Alloc>::__move_assign(forward_list& __x, true_type)
893 _NOEXCEPT_(is_nothrow_move_assignable<allocator_type>::value)
896 base::__move_assign_alloc(__x);
897 base::__before_begin()->__next_ = __x.__before_begin()->__next_;
898 __x.__before_begin()->__next_ = nullptr;
901 template <class _Tp, class _Alloc>
903 forward_list<_Tp, _Alloc>::__move_assign(forward_list& __x, false_type)
905 if (base::__alloc() == __x.__alloc())
906 __move_assign(__x, true_type());
909 typedef move_iterator<iterator> _Ip;
910 assign(_Ip(__x.begin()), _Ip(__x.end()));
914 template <class _Tp, class _Alloc>
915 inline _LIBCPP_INLINE_VISIBILITY
916 forward_list<_Tp, _Alloc>&
917 forward_list<_Tp, _Alloc>::operator=(forward_list&& __x)
919 __node_traits::propagate_on_container_move_assignment::value &&
920 is_nothrow_move_assignable<allocator_type>::value)
922 __move_assign(__x, integral_constant<bool,
923 __node_traits::propagate_on_container_move_assignment::value>());
927 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
929 #ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
931 template <class _Tp, class _Alloc>
932 inline _LIBCPP_INLINE_VISIBILITY
933 forward_list<_Tp, _Alloc>&
934 forward_list<_Tp, _Alloc>::operator=(initializer_list<value_type> __il)
936 assign(__il.begin(), __il.end());
940 #endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
942 template <class _Tp, class _Alloc>
943 template <class _InputIterator>
946 __is_input_iterator<_InputIterator>::value,
949 forward_list<_Tp, _Alloc>::assign(_InputIterator __f, _InputIterator __l)
951 iterator __i = before_begin();
952 iterator __j = _VSTD::next(__i);
953 iterator __e = end();
954 for (; __j != __e && __f != __l; ++__i, ++__j, ++__f)
957 insert_after(__i, __f, __l);
959 erase_after(__i, __e);
962 template <class _Tp, class _Alloc>
964 forward_list<_Tp, _Alloc>::assign(size_type __n, const value_type& __v)
966 iterator __i = before_begin();
967 iterator __j = _VSTD::next(__i);
968 iterator __e = end();
969 for (; __j != __e && __n > 0; --__n, ++__i, ++__j)
972 insert_after(__i, __n, __v);
974 erase_after(__i, __e);
977 #ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
979 template <class _Tp, class _Alloc>
980 inline _LIBCPP_INLINE_VISIBILITY
982 forward_list<_Tp, _Alloc>::assign(initializer_list<value_type> __il)
984 assign(__il.begin(), __il.end());
987 #endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
989 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
990 #ifndef _LIBCPP_HAS_NO_VARIADICS
992 template <class _Tp, class _Alloc>
993 template <class... _Args>
995 forward_list<_Tp, _Alloc>::emplace_front(_Args&&... __args)
997 __node_allocator& __a = base::__alloc();
998 typedef __allocator_destructor<__node_allocator> _Dp;
999 unique_ptr<__node, _Dp> __h(__node_traits::allocate(__a, 1), _Dp(__a, 1));
1000 __node_traits::construct(__a, _VSTD::addressof(__h->__value_),
1001 _VSTD::forward<_Args>(__args)...);
1002 __h->__next_ = base::__before_begin()->__next_;
1003 base::__before_begin()->__next_ = __h.release();
1006 #endif // _LIBCPP_HAS_NO_VARIADICS
1008 template <class _Tp, class _Alloc>
1010 forward_list<_Tp, _Alloc>::push_front(value_type&& __v)
1012 __node_allocator& __a = base::__alloc();
1013 typedef __allocator_destructor<__node_allocator> _Dp;
1014 unique_ptr<__node, _Dp> __h(__node_traits::allocate(__a, 1), _Dp(__a, 1));
1015 __node_traits::construct(__a, _VSTD::addressof(__h->__value_), _VSTD::move(__v));
1016 __h->__next_ = base::__before_begin()->__next_;
1017 base::__before_begin()->__next_ = __h.release();
1020 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
1022 template <class _Tp, class _Alloc>
1024 forward_list<_Tp, _Alloc>::push_front(const value_type& __v)
1026 __node_allocator& __a = base::__alloc();
1027 typedef __allocator_destructor<__node_allocator> _Dp;
1028 unique_ptr<__node, _Dp> __h(__node_traits::allocate(__a, 1), _Dp(__a, 1));
1029 __node_traits::construct(__a, _VSTD::addressof(__h->__value_), __v);
1030 __h->__next_ = base::__before_begin()->__next_;
1031 base::__before_begin()->__next_ = __h.release();
1034 template <class _Tp, class _Alloc>
1036 forward_list<_Tp, _Alloc>::pop_front()
1038 __node_allocator& __a = base::__alloc();
1039 __node_pointer __p = base::__before_begin()->__next_;
1040 base::__before_begin()->__next_ = __p->__next_;
1041 __node_traits::destroy(__a, _VSTD::addressof(__p->__value_));
1042 __node_traits::deallocate(__a, __p, 1);
1045 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
1046 #ifndef _LIBCPP_HAS_NO_VARIADICS
1048 template <class _Tp, class _Alloc>
1049 template <class... _Args>
1050 typename forward_list<_Tp, _Alloc>::iterator
1051 forward_list<_Tp, _Alloc>::emplace_after(const_iterator __p, _Args&&... __args)
1053 __node_pointer const __r = const_cast<__node_pointer>(__p.__ptr_);
1054 __node_allocator& __a = base::__alloc();
1055 typedef __allocator_destructor<__node_allocator> _Dp;
1056 unique_ptr<__node, _Dp> __h(__node_traits::allocate(__a, 1), _Dp(__a, 1));
1057 __node_traits::construct(__a, _VSTD::addressof(__h->__value_),
1058 _VSTD::forward<_Args>(__args)...);
1059 __h->__next_ = __r->__next_;
1060 __r->__next_ = __h.release();
1061 return iterator(__r->__next_);
1064 #endif // _LIBCPP_HAS_NO_VARIADICS
1066 template <class _Tp, class _Alloc>
1067 typename forward_list<_Tp, _Alloc>::iterator
1068 forward_list<_Tp, _Alloc>::insert_after(const_iterator __p, value_type&& __v)
1070 __node_pointer const __r = const_cast<__node_pointer>(__p.__ptr_);
1071 __node_allocator& __a = base::__alloc();
1072 typedef __allocator_destructor<__node_allocator> _Dp;
1073 unique_ptr<__node, _Dp> __h(__node_traits::allocate(__a, 1), _Dp(__a, 1));
1074 __node_traits::construct(__a, _VSTD::addressof(__h->__value_), _VSTD::move(__v));
1075 __h->__next_ = __r->__next_;
1076 __r->__next_ = __h.release();
1077 return iterator(__r->__next_);
1080 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
1082 template <class _Tp, class _Alloc>
1083 typename forward_list<_Tp, _Alloc>::iterator
1084 forward_list<_Tp, _Alloc>::insert_after(const_iterator __p, const value_type& __v)
1086 __node_pointer const __r = const_cast<__node_pointer>(__p.__ptr_);
1087 __node_allocator& __a = base::__alloc();
1088 typedef __allocator_destructor<__node_allocator> _Dp;
1089 unique_ptr<__node, _Dp> __h(__node_traits::allocate(__a, 1), _Dp(__a, 1));
1090 __node_traits::construct(__a, _VSTD::addressof(__h->__value_), __v);
1091 __h->__next_ = __r->__next_;
1092 __r->__next_ = __h.release();
1093 return iterator(__r->__next_);
1096 template <class _Tp, class _Alloc>
1097 typename forward_list<_Tp, _Alloc>::iterator
1098 forward_list<_Tp, _Alloc>::insert_after(const_iterator __p, size_type __n,
1099 const value_type& __v)
1101 __node_pointer __r = const_cast<__node_pointer>(__p.__ptr_);
1104 __node_allocator& __a = base::__alloc();
1105 typedef __allocator_destructor<__node_allocator> _Dp;
1106 unique_ptr<__node, _Dp> __h(__node_traits::allocate(__a, 1), _Dp(__a, 1));
1107 __node_traits::construct(__a, _VSTD::addressof(__h->__value_), __v);
1108 __node_pointer __first = __h.release();
1109 __node_pointer __last = __first;
1110 #ifndef _LIBCPP_NO_EXCEPTIONS
1113 #endif // _LIBCPP_NO_EXCEPTIONS
1114 for (--__n; __n != 0; --__n, __last = __last->__next_)
1116 __h.reset(__node_traits::allocate(__a, 1));
1117 __node_traits::construct(__a, _VSTD::addressof(__h->__value_), __v);
1118 __last->__next_ = __h.release();
1120 #ifndef _LIBCPP_NO_EXCEPTIONS
1124 while (__first != nullptr)
1126 __node_pointer __next = __first->__next_;
1127 __node_traits::destroy(__a, _VSTD::addressof(__first->__value_));
1128 __node_traits::deallocate(__a, __first, 1);
1133 #endif // _LIBCPP_NO_EXCEPTIONS
1134 __last->__next_ = __r->__next_;
1135 __r->__next_ = __first;
1138 return iterator(__r);
1141 template <class _Tp, class _Alloc>
1142 template <class _InputIterator>
1145 __is_input_iterator<_InputIterator>::value,
1146 typename forward_list<_Tp, _Alloc>::iterator
1148 forward_list<_Tp, _Alloc>::insert_after(const_iterator __p,
1149 _InputIterator __f, _InputIterator __l)
1151 __node_pointer __r = const_cast<__node_pointer>(__p.__ptr_);
1154 __node_allocator& __a = base::__alloc();
1155 typedef __allocator_destructor<__node_allocator> _Dp;
1156 unique_ptr<__node, _Dp> __h(__node_traits::allocate(__a, 1), _Dp(__a, 1));
1157 __node_traits::construct(__a, _VSTD::addressof(__h->__value_), *__f);
1158 __node_pointer __first = __h.release();
1159 __node_pointer __last = __first;
1160 #ifndef _LIBCPP_NO_EXCEPTIONS
1163 #endif // _LIBCPP_NO_EXCEPTIONS
1164 for (++__f; __f != __l; ++__f, __last = __last->__next_)
1166 __h.reset(__node_traits::allocate(__a, 1));
1167 __node_traits::construct(__a, _VSTD::addressof(__h->__value_), *__f);
1168 __last->__next_ = __h.release();
1170 #ifndef _LIBCPP_NO_EXCEPTIONS
1174 while (__first != nullptr)
1176 __node_pointer __next = __first->__next_;
1177 __node_traits::destroy(__a, _VSTD::addressof(__first->__value_));
1178 __node_traits::deallocate(__a, __first, 1);
1183 #endif // _LIBCPP_NO_EXCEPTIONS
1184 __last->__next_ = __r->__next_;
1185 __r->__next_ = __first;
1188 return iterator(__r);
1191 template <class _Tp, class _Alloc>
1192 typename forward_list<_Tp, _Alloc>::iterator
1193 forward_list<_Tp, _Alloc>::erase_after(const_iterator __f)
1195 __node_pointer __p = const_cast<__node_pointer>(__f.__ptr_);
1196 __node_pointer __n = __p->__next_;
1197 __p->__next_ = __n->__next_;
1198 __node_allocator& __a = base::__alloc();
1199 __node_traits::destroy(__a, _VSTD::addressof(__n->__value_));
1200 __node_traits::deallocate(__a, __n, 1);
1201 return iterator(__p->__next_);
1204 template <class _Tp, class _Alloc>
1205 typename forward_list<_Tp, _Alloc>::iterator
1206 forward_list<_Tp, _Alloc>::erase_after(const_iterator __f, const_iterator __l)
1208 __node_pointer __e = const_cast<__node_pointer>(__l.__ptr_);
1211 __node_pointer __p = const_cast<__node_pointer>(__f.__ptr_);
1212 __node_pointer __n = __p->__next_;
1216 __node_allocator& __a = base::__alloc();
1220 __node_traits::destroy(__a, _VSTD::addressof(__n->__value_));
1221 __node_traits::deallocate(__a, __n, 1);
1223 } while (__n != __e);
1226 return iterator(__e);
1229 template <class _Tp, class _Alloc>
1231 forward_list<_Tp, _Alloc>::resize(size_type __n)
1234 iterator __p = before_begin();
1235 iterator __i = begin();
1236 iterator __e = end();
1237 for (; __i != __e && __sz < __n; ++__p, ++__i, ++__sz)
1240 erase_after(__p, __e);
1246 __node_allocator& __a = base::__alloc();
1247 typedef __allocator_destructor<__node_allocator> _Dp;
1248 unique_ptr<__node, _Dp> __h(nullptr, _Dp(__a, 1));
1249 for (__node_pointer __ptr = __p.__ptr_; __n > 0; --__n,
1250 __ptr = __ptr->__next_)
1252 __h.reset(__node_traits::allocate(__a, 1));
1253 __node_traits::construct(__a, _VSTD::addressof(__h->__value_));
1254 __h->__next_ = nullptr;
1255 __ptr->__next_ = __h.release();
1261 template <class _Tp, class _Alloc>
1263 forward_list<_Tp, _Alloc>::resize(size_type __n, const value_type& __v)
1266 iterator __p = before_begin();
1267 iterator __i = begin();
1268 iterator __e = end();
1269 for (; __i != __e && __sz < __n; ++__p, ++__i, ++__sz)
1272 erase_after(__p, __e);
1278 __node_allocator& __a = base::__alloc();
1279 typedef __allocator_destructor<__node_allocator> _Dp;
1280 unique_ptr<__node, _Dp> __h(nullptr, _Dp(__a, 1));
1281 for (__node_pointer __ptr = __p.__ptr_; __n > 0; --__n,
1282 __ptr = __ptr->__next_)
1284 __h.reset(__node_traits::allocate(__a, 1));
1285 __node_traits::construct(__a, _VSTD::addressof(__h->__value_), __v);
1286 __h->__next_ = nullptr;
1287 __ptr->__next_ = __h.release();
1293 template <class _Tp, class _Alloc>
1295 forward_list<_Tp, _Alloc>::splice_after(const_iterator __p,
1300 if (__p.__ptr_->__next_ != nullptr)
1302 const_iterator __lm1 = __x.before_begin();
1303 while (__lm1.__ptr_->__next_ != nullptr)
1305 const_cast<__node_pointer>(__lm1.__ptr_)->__next_ =
1306 const_cast<__node_pointer>(__p.__ptr_)->__next_;
1308 const_cast<__node_pointer>(__p.__ptr_)->__next_ =
1309 const_cast<__node_pointer>(__x.__before_begin())->__next_;
1310 const_cast<__node_pointer>(__x.__before_begin())->__next_ = nullptr;
1314 template <class _Tp, class _Alloc>
1316 forward_list<_Tp, _Alloc>::splice_after(const_iterator __p,
1320 const_iterator __lm1 = _VSTD::next(__i);
1321 if (__p != __i && __p != __lm1)
1323 const_cast<__node_pointer>(__i.__ptr_)->__next_ =
1324 const_cast<__node_pointer>(__lm1.__ptr_)->__next_;
1325 const_cast<__node_pointer>(__lm1.__ptr_)->__next_ =
1326 const_cast<__node_pointer>(__p.__ptr_)->__next_;
1327 const_cast<__node_pointer>(__p.__ptr_)->__next_ =
1328 const_cast<__node_pointer>(__lm1.__ptr_);
1332 template <class _Tp, class _Alloc>
1334 forward_list<_Tp, _Alloc>::splice_after(const_iterator __p,
1336 const_iterator __f, const_iterator __l)
1338 if (__f != __l && __p != __f)
1340 const_iterator __lm1 = __f;
1341 while (__lm1.__ptr_->__next_ != __l.__ptr_)
1345 const_cast<__node_pointer>(__lm1.__ptr_)->__next_ =
1346 const_cast<__node_pointer>(__p.__ptr_)->__next_;
1347 const_cast<__node_pointer>(__p.__ptr_)->__next_ =
1348 const_cast<__node_pointer>(__f.__ptr_)->__next_;
1349 const_cast<__node_pointer>(__f.__ptr_)->__next_ =
1350 const_cast<__node_pointer>(__l.__ptr_);
1355 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
1357 template <class _Tp, class _Alloc>
1358 inline _LIBCPP_INLINE_VISIBILITY
1360 forward_list<_Tp, _Alloc>::splice_after(const_iterator __p,
1363 splice_after(__p, __x);
1366 template <class _Tp, class _Alloc>
1367 inline _LIBCPP_INLINE_VISIBILITY
1369 forward_list<_Tp, _Alloc>::splice_after(const_iterator __p,
1373 splice_after(__p, __x, __i);
1376 template <class _Tp, class _Alloc>
1377 inline _LIBCPP_INLINE_VISIBILITY
1379 forward_list<_Tp, _Alloc>::splice_after(const_iterator __p,
1381 const_iterator __f, const_iterator __l)
1383 splice_after(__p, __x, __f, __l);
1386 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
1388 template <class _Tp, class _Alloc>
1390 forward_list<_Tp, _Alloc>::remove(const value_type& __v)
1392 iterator __e = end();
1393 for (iterator __i = before_begin(); __i.__ptr_->__next_ != nullptr;)
1395 if (__i.__ptr_->__next_->__value_ == __v)
1397 iterator __j = _VSTD::next(__i, 2);
1398 for (; __j != __e && *__j == __v; ++__j)
1400 erase_after(__i, __j);
1410 template <class _Tp, class _Alloc>
1411 template <class _Predicate>
1413 forward_list<_Tp, _Alloc>::remove_if(_Predicate __pred)
1415 iterator __e = end();
1416 for (iterator __i = before_begin(); __i.__ptr_->__next_ != nullptr;)
1418 if (__pred(__i.__ptr_->__next_->__value_))
1420 iterator __j = _VSTD::next(__i, 2);
1421 for (; __j != __e && __pred(*__j); ++__j)
1423 erase_after(__i, __j);
1433 template <class _Tp, class _Alloc>
1434 template <class _BinaryPredicate>
1436 forward_list<_Tp, _Alloc>::unique(_BinaryPredicate __binary_pred)
1438 for (iterator __i = begin(), __e = end(); __i != __e;)
1440 iterator __j = _VSTD::next(__i);
1441 for (; __j != __e && __binary_pred(*__i, *__j); ++__j)
1443 if (__i.__ptr_->__next_ != __j.__ptr_)
1444 erase_after(__i, __j);
1449 template <class _Tp, class _Alloc>
1450 template <class _Compare>
1452 forward_list<_Tp, _Alloc>::merge(forward_list& __x, _Compare __comp)
1456 base::__before_begin()->__next_ = __merge(base::__before_begin()->__next_,
1457 __x.__before_begin()->__next_,
1459 __x.__before_begin()->__next_ = nullptr;
1463 template <class _Tp, class _Alloc>
1464 template <class _Compare>
1465 typename forward_list<_Tp, _Alloc>::__node_pointer
1466 forward_list<_Tp, _Alloc>::__merge(__node_pointer __f1, __node_pointer __f2,
1469 if (__f1 == nullptr)
1471 if (__f2 == nullptr)
1474 if (__comp(__f2->__value_, __f1->__value_))
1476 __node_pointer __t = __f2;
1477 while (__t->__next_ != nullptr &&
1478 __comp(__t->__next_->__value_, __f1->__value_))
1481 __f2 = __t->__next_;
1482 __t->__next_ = __f1;
1486 __node_pointer __p = __f1;
1487 __f1 = __f1->__next_;
1488 while (__f1 != nullptr && __f2 != nullptr)
1490 if (__comp(__f2->__value_, __f1->__value_))
1492 __node_pointer __t = __f2;
1493 while (__t->__next_ != nullptr &&
1494 __comp(__t->__next_->__value_, __f1->__value_))
1496 __p->__next_ = __f2;
1497 __f2 = __t->__next_;
1498 __t->__next_ = __f1;
1501 __f1 = __f1->__next_;
1503 if (__f2 != nullptr)
1504 __p->__next_ = __f2;
1508 template <class _Tp, class _Alloc>
1509 template <class _Compare>
1510 inline _LIBCPP_INLINE_VISIBILITY
1512 forward_list<_Tp, _Alloc>::sort(_Compare __comp)
1514 base::__before_begin()->__next_ = __sort(base::__before_begin()->__next_,
1515 _VSTD::distance(begin(), end()), __comp);
1518 template <class _Tp, class _Alloc>
1519 template <class _Compare>
1520 typename forward_list<_Tp, _Alloc>::__node_pointer
1521 forward_list<_Tp, _Alloc>::__sort(__node_pointer __f1, difference_type __sz,
1530 if (__comp(__f1->__next_->__value_, __f1->__value_))
1532 __node_pointer __t = __f1->__next_;
1533 __t->__next_ = __f1;
1534 __f1->__next_ = nullptr;
1539 difference_type __sz1 = __sz / 2;
1540 difference_type __sz2 = __sz - __sz1;
1541 __node_pointer __t = _VSTD::next(iterator(__f1), __sz1 - 1).__ptr_;
1542 __node_pointer __f2 = __t->__next_;
1543 __t->__next_ = nullptr;
1544 return __merge(__sort(__f1, __sz1, __comp),
1545 __sort(__f2, __sz2, __comp), __comp);
1548 template <class _Tp, class _Alloc>
1550 forward_list<_Tp, _Alloc>::reverse() _NOEXCEPT
1552 __node_pointer __p = base::__before_begin()->__next_;
1555 __node_pointer __f = __p->__next_;
1556 __p->__next_ = nullptr;
1557 while (__f != nullptr)
1559 __node_pointer __t = __f->__next_;
1564 base::__before_begin()->__next_ = __p;
1568 template <class _Tp, class _Alloc>
1569 bool operator==(const forward_list<_Tp, _Alloc>& __x,
1570 const forward_list<_Tp, _Alloc>& __y)
1572 typedef forward_list<_Tp, _Alloc> _Cp;
1573 typedef typename _Cp::const_iterator _Ip;
1574 _Ip __ix = __x.begin();
1575 _Ip __ex = __x.end();
1576 _Ip __iy = __y.begin();
1577 _Ip __ey = __y.end();
1578 for (; __ix != __ex && __iy != __ey; ++__ix, ++__iy)
1579 if (!(*__ix == *__iy))
1581 return (__ix == __ex) == (__iy == __ey);
1584 template <class _Tp, class _Alloc>
1585 inline _LIBCPP_INLINE_VISIBILITY
1586 bool operator!=(const forward_list<_Tp, _Alloc>& __x,
1587 const forward_list<_Tp, _Alloc>& __y)
1589 return !(__x == __y);
1592 template <class _Tp, class _Alloc>
1593 inline _LIBCPP_INLINE_VISIBILITY
1594 bool operator< (const forward_list<_Tp, _Alloc>& __x,
1595 const forward_list<_Tp, _Alloc>& __y)
1597 return _VSTD::lexicographical_compare(__x.begin(), __x.end(),
1598 __y.begin(), __y.end());
1601 template <class _Tp, class _Alloc>
1602 inline _LIBCPP_INLINE_VISIBILITY
1603 bool operator> (const forward_list<_Tp, _Alloc>& __x,
1604 const forward_list<_Tp, _Alloc>& __y)
1609 template <class _Tp, class _Alloc>
1610 inline _LIBCPP_INLINE_VISIBILITY
1611 bool operator>=(const forward_list<_Tp, _Alloc>& __x,
1612 const forward_list<_Tp, _Alloc>& __y)
1614 return !(__x < __y);
1617 template <class _Tp, class _Alloc>
1618 inline _LIBCPP_INLINE_VISIBILITY
1619 bool operator<=(const forward_list<_Tp, _Alloc>& __x,
1620 const forward_list<_Tp, _Alloc>& __y)
1622 return !(__y < __x);
1625 template <class _Tp, class _Alloc>
1626 inline _LIBCPP_INLINE_VISIBILITY
1628 swap(forward_list<_Tp, _Alloc>& __x, forward_list<_Tp, _Alloc>& __y)
1629 _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y)))
1634 _LIBCPP_END_NAMESPACE_STD
1636 #endif // _LIBCPP_FORWARD_LIST