2 //===----------------------- forward_list ---------------------------------===//
4 // The LLVM Compiler Infrastructure
6 // This file is dual licensed under the MIT and the University of Illinois Open
7 // Source Licenses. See LICENSE.TXT for details.
9 //===----------------------------------------------------------------------===//
11 #ifndef _LIBCPP_FORWARD_LIST
12 #define _LIBCPP_FORWARD_LIST
20 template <class T, class Allocator = allocator<T>>
25 typedef Allocator allocator_type;
27 typedef value_type& reference;
28 typedef const value_type& const_reference;
29 typedef typename allocator_traits<allocator_type>::pointer pointer;
30 typedef typename allocator_traits<allocator_type>::const_pointer const_pointer;
31 typedef typename allocator_traits<allocator_type>::size_type size_type;
32 typedef typename allocator_traits<allocator_type>::difference_type difference_type;
34 typedef <details> iterator;
35 typedef <details> const_iterator;
38 noexcept(is_nothrow_default_constructible<allocator_type>::value);
39 explicit forward_list(const allocator_type& a);
40 explicit forward_list(size_type n);
41 explicit forward_list(size_type n, const allocator_type& a); // C++14
42 forward_list(size_type n, const value_type& v);
43 forward_list(size_type n, const value_type& v, const allocator_type& a);
44 template <class InputIterator>
45 forward_list(InputIterator first, InputIterator last);
46 template <class InputIterator>
47 forward_list(InputIterator first, InputIterator last, const allocator_type& a);
48 forward_list(const forward_list& x);
49 forward_list(const forward_list& x, const allocator_type& a);
50 forward_list(forward_list&& x)
51 noexcept(is_nothrow_move_constructible<allocator_type>::value);
52 forward_list(forward_list&& x, const allocator_type& a);
53 forward_list(initializer_list<value_type> il);
54 forward_list(initializer_list<value_type> il, const allocator_type& a);
58 forward_list& operator=(const forward_list& x);
59 forward_list& operator=(forward_list&& x)
61 allocator_type::propagate_on_container_move_assignment::value &&
62 is_nothrow_move_assignable<allocator_type>::value);
63 forward_list& operator=(initializer_list<value_type> il);
65 template <class InputIterator>
66 void assign(InputIterator first, InputIterator last);
67 void assign(size_type n, const value_type& v);
68 void assign(initializer_list<value_type> il);
70 allocator_type get_allocator() const noexcept;
72 iterator begin() noexcept;
73 const_iterator begin() const noexcept;
74 iterator end() noexcept;
75 const_iterator end() const noexcept;
77 const_iterator cbegin() const noexcept;
78 const_iterator cend() const noexcept;
80 iterator before_begin() noexcept;
81 const_iterator before_begin() const noexcept;
82 const_iterator cbefore_begin() const noexcept;
84 bool empty() const noexcept;
85 size_type max_size() const noexcept;
88 const_reference front() const;
90 template <class... Args> void emplace_front(Args&&... args);
91 void push_front(const value_type& v);
92 void push_front(value_type&& v);
96 template <class... Args>
97 iterator emplace_after(const_iterator p, Args&&... args);
98 iterator insert_after(const_iterator p, const value_type& v);
99 iterator insert_after(const_iterator p, value_type&& v);
100 iterator insert_after(const_iterator p, size_type n, const value_type& v);
101 template <class InputIterator>
102 iterator insert_after(const_iterator p,
103 InputIterator first, InputIterator last);
104 iterator insert_after(const_iterator p, initializer_list<value_type> il);
106 iterator erase_after(const_iterator p);
107 iterator erase_after(const_iterator first, const_iterator last);
109 void swap(forward_list& x)
110 noexcept(!allocator_type::propagate_on_container_swap::value ||
111 __is_nothrow_swappable<allocator_type>::value);
113 void resize(size_type n);
114 void resize(size_type n, const value_type& v);
115 void clear() noexcept;
117 void splice_after(const_iterator p, forward_list& x);
118 void splice_after(const_iterator p, forward_list&& x);
119 void splice_after(const_iterator p, forward_list& x, const_iterator i);
120 void splice_after(const_iterator p, forward_list&& x, const_iterator i);
121 void splice_after(const_iterator p, forward_list& x,
122 const_iterator first, const_iterator last);
123 void splice_after(const_iterator p, forward_list&& x,
124 const_iterator first, const_iterator last);
125 void remove(const value_type& v);
126 template <class Predicate> void remove_if(Predicate pred);
128 template <class BinaryPredicate> void unique(BinaryPredicate binary_pred);
129 void merge(forward_list& x);
130 void merge(forward_list&& x);
131 template <class Compare> void merge(forward_list& x, Compare comp);
132 template <class Compare> void merge(forward_list&& x, Compare comp);
134 template <class Compare> void sort(Compare comp);
135 void reverse() noexcept;
138 template <class T, class Allocator>
139 bool operator==(const forward_list<T, Allocator>& x,
140 const forward_list<T, Allocator>& y);
142 template <class T, class Allocator>
143 bool operator< (const forward_list<T, Allocator>& x,
144 const forward_list<T, Allocator>& y);
146 template <class T, class Allocator>
147 bool operator!=(const forward_list<T, Allocator>& x,
148 const forward_list<T, Allocator>& y);
150 template <class T, class Allocator>
151 bool operator> (const forward_list<T, Allocator>& x,
152 const forward_list<T, Allocator>& y);
154 template <class T, class Allocator>
155 bool operator>=(const forward_list<T, Allocator>& x,
156 const forward_list<T, Allocator>& y);
158 template <class T, class Allocator>
159 bool operator<=(const forward_list<T, Allocator>& x,
160 const forward_list<T, Allocator>& y);
162 template <class T, class Allocator>
163 void swap(forward_list<T, Allocator>& x, forward_list<T, Allocator>& y)
164 noexcept(noexcept(x.swap(y)));
172 #include <initializer_list>
178 #include <__undef_min_max>
180 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
181 #pragma GCC system_header
184 _LIBCPP_BEGIN_NAMESPACE_STD
186 template <class _Tp, class _VoidPtr> struct __forward_list_node;
188 template <class _NodePtr>
189 struct __forward_begin_node
191 typedef _NodePtr pointer;
195 _LIBCPP_INLINE_VISIBILITY __forward_begin_node() : __next_(nullptr) {}
198 template <class _Tp, class _VoidPtr>
199 struct _LIBCPP_HIDDEN __begin_node_of
201 typedef __forward_begin_node
203 typename pointer_traits<_VoidPtr>::template
204 #ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES
205 rebind<__forward_list_node<_Tp, _VoidPtr> >
207 rebind<__forward_list_node<_Tp, _VoidPtr> >::other
212 template <class _Tp, class _VoidPtr>
213 struct __forward_list_node
214 : public __begin_node_of<_Tp, _VoidPtr>::type
216 typedef _Tp value_type;
221 template<class _Tp, class _Alloc> class _LIBCPP_TYPE_VIS_ONLY forward_list;
222 template<class _NodeConstPtr> class _LIBCPP_TYPE_VIS_ONLY __forward_list_const_iterator;
224 template <class _NodePtr>
225 class _LIBCPP_TYPE_VIS_ONLY __forward_list_iterator
227 typedef _NodePtr __node_pointer;
229 __node_pointer __ptr_;
231 _LIBCPP_INLINE_VISIBILITY
232 explicit __forward_list_iterator(__node_pointer __p) _NOEXCEPT : __ptr_(__p) {}
234 template<class, class> friend class _LIBCPP_TYPE_VIS_ONLY forward_list;
235 template<class> friend class _LIBCPP_TYPE_VIS_ONLY __forward_list_const_iterator;
238 typedef forward_iterator_tag iterator_category;
239 typedef typename pointer_traits<__node_pointer>::element_type::value_type
241 typedef value_type& reference;
242 typedef typename pointer_traits<__node_pointer>::difference_type
244 typedef typename pointer_traits<__node_pointer>::template
245 #ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES
248 rebind<value_type>::other
252 _LIBCPP_INLINE_VISIBILITY
253 __forward_list_iterator() _NOEXCEPT : __ptr_(nullptr) {}
255 _LIBCPP_INLINE_VISIBILITY
256 reference operator*() const {return __ptr_->__value_;}
257 _LIBCPP_INLINE_VISIBILITY
258 pointer operator->() const {return pointer_traits<pointer>::pointer_to(__ptr_->__value_);}
260 _LIBCPP_INLINE_VISIBILITY
261 __forward_list_iterator& operator++()
263 __ptr_ = __ptr_->__next_;
266 _LIBCPP_INLINE_VISIBILITY
267 __forward_list_iterator operator++(int)
269 __forward_list_iterator __t(*this);
274 friend _LIBCPP_INLINE_VISIBILITY
275 bool operator==(const __forward_list_iterator& __x,
276 const __forward_list_iterator& __y)
277 {return __x.__ptr_ == __y.__ptr_;}
278 friend _LIBCPP_INLINE_VISIBILITY
279 bool operator!=(const __forward_list_iterator& __x,
280 const __forward_list_iterator& __y)
281 {return !(__x == __y);}
284 template <class _NodeConstPtr>
285 class _LIBCPP_TYPE_VIS_ONLY __forward_list_const_iterator
287 typedef _NodeConstPtr __node_const_pointer;
289 __node_const_pointer __ptr_;
291 _LIBCPP_INLINE_VISIBILITY
292 explicit __forward_list_const_iterator(__node_const_pointer __p) _NOEXCEPT
295 typedef typename remove_const
297 typename pointer_traits<__node_const_pointer>::element_type
299 typedef typename pointer_traits<__node_const_pointer>::template
300 #ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES
303 rebind<__node>::other
307 template<class, class> friend class forward_list;
310 typedef forward_iterator_tag iterator_category;
311 typedef typename __node::value_type value_type;
312 typedef const value_type& reference;
313 typedef typename pointer_traits<__node_const_pointer>::difference_type
315 typedef typename pointer_traits<__node_const_pointer>::template
316 #ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES
317 rebind<const value_type>
319 rebind<const value_type>::other
323 _LIBCPP_INLINE_VISIBILITY
324 __forward_list_const_iterator() _NOEXCEPT : __ptr_(nullptr) {}
325 _LIBCPP_INLINE_VISIBILITY
326 __forward_list_const_iterator(__forward_list_iterator<__node_pointer> __p) _NOEXCEPT
327 : __ptr_(__p.__ptr_) {}
329 _LIBCPP_INLINE_VISIBILITY
330 reference operator*() const {return __ptr_->__value_;}
331 _LIBCPP_INLINE_VISIBILITY
332 pointer operator->() const {return pointer_traits<pointer>::pointer_to(__ptr_->__value_);}
334 _LIBCPP_INLINE_VISIBILITY
335 __forward_list_const_iterator& operator++()
337 __ptr_ = __ptr_->__next_;
340 _LIBCPP_INLINE_VISIBILITY
341 __forward_list_const_iterator operator++(int)
343 __forward_list_const_iterator __t(*this);
348 friend _LIBCPP_INLINE_VISIBILITY
349 bool operator==(const __forward_list_const_iterator& __x,
350 const __forward_list_const_iterator& __y)
351 {return __x.__ptr_ == __y.__ptr_;}
352 friend _LIBCPP_INLINE_VISIBILITY
353 bool operator!=(const __forward_list_const_iterator& __x,
354 const __forward_list_const_iterator& __y)
355 {return !(__x == __y);}
358 template <class _Tp, class _Alloc>
359 class __forward_list_base
362 typedef _Tp value_type;
363 typedef _Alloc allocator_type;
365 typedef typename allocator_traits<allocator_type>::void_pointer void_pointer;
366 typedef __forward_list_node<value_type, void_pointer> __node;
367 typedef typename __begin_node_of<value_type, void_pointer>::type __begin_node;
368 typedef typename allocator_traits<allocator_type>::template
369 #ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES
372 rebind_alloc<__node>::other
375 typedef allocator_traits<__node_allocator> __node_traits;
376 typedef typename __node_traits::pointer __node_pointer;
377 typedef typename __node_traits::pointer __node_const_pointer;
379 typedef typename allocator_traits<allocator_type>::template
380 #ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES
381 rebind_alloc<__begin_node>
383 rebind_alloc<__begin_node>::other
385 __begin_node_allocator;
386 typedef typename allocator_traits<__begin_node_allocator>::pointer __begin_node_pointer;
388 __compressed_pair<__begin_node, __node_allocator> __before_begin_;
390 _LIBCPP_INLINE_VISIBILITY
391 __node_pointer __before_begin() _NOEXCEPT
392 {return static_cast<__node_pointer>(pointer_traits<__begin_node_pointer>::
393 pointer_to(__before_begin_.first()));}
394 _LIBCPP_INLINE_VISIBILITY
395 __node_const_pointer __before_begin() const _NOEXCEPT
396 {return static_cast<__node_const_pointer>(pointer_traits<__begin_node_pointer>::
397 pointer_to(const_cast<__begin_node&>(__before_begin_.first())));}
399 _LIBCPP_INLINE_VISIBILITY
400 __node_allocator& __alloc() _NOEXCEPT
401 {return __before_begin_.second();}
402 _LIBCPP_INLINE_VISIBILITY
403 const __node_allocator& __alloc() const _NOEXCEPT
404 {return __before_begin_.second();}
406 typedef __forward_list_iterator<__node_pointer> iterator;
407 typedef __forward_list_const_iterator<__node_pointer> const_iterator;
409 _LIBCPP_INLINE_VISIBILITY
410 __forward_list_base()
411 _NOEXCEPT_(is_nothrow_default_constructible<__node_allocator>::value)
412 : __before_begin_(__begin_node()) {}
413 _LIBCPP_INLINE_VISIBILITY
414 __forward_list_base(const allocator_type& __a)
415 : __before_begin_(__begin_node(), __node_allocator(__a)) {}
417 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
419 __forward_list_base(__forward_list_base&& __x)
420 _NOEXCEPT_(is_nothrow_move_constructible<__node_allocator>::value);
421 __forward_list_base(__forward_list_base&& __x, const allocator_type& __a);
422 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
425 __forward_list_base(const __forward_list_base&);
426 __forward_list_base& operator=(const __forward_list_base&);
429 ~__forward_list_base();
432 _LIBCPP_INLINE_VISIBILITY
433 void __copy_assign_alloc(const __forward_list_base& __x)
434 {__copy_assign_alloc(__x, integral_constant<bool,
435 __node_traits::propagate_on_container_copy_assignment::value>());}
437 _LIBCPP_INLINE_VISIBILITY
438 void __move_assign_alloc(__forward_list_base& __x)
439 _NOEXCEPT_(!__node_traits::propagate_on_container_move_assignment::value ||
440 is_nothrow_move_assignable<__node_allocator>::value)
441 {__move_assign_alloc(__x, integral_constant<bool,
442 __node_traits::propagate_on_container_move_assignment::value>());}
445 void swap(__forward_list_base& __x)
446 _NOEXCEPT_(!__node_traits::propagate_on_container_swap::value ||
447 __is_nothrow_swappable<__node_allocator>::value);
449 void clear() _NOEXCEPT;
452 _LIBCPP_INLINE_VISIBILITY
453 void __copy_assign_alloc(const __forward_list_base&, false_type) {}
454 _LIBCPP_INLINE_VISIBILITY
455 void __copy_assign_alloc(const __forward_list_base& __x, true_type)
457 if (__alloc() != __x.__alloc())
459 __alloc() = __x.__alloc();
462 _LIBCPP_INLINE_VISIBILITY
463 void __move_assign_alloc(__forward_list_base& __x, false_type) _NOEXCEPT
465 _LIBCPP_INLINE_VISIBILITY
466 void __move_assign_alloc(__forward_list_base& __x, true_type)
467 _NOEXCEPT_(is_nothrow_move_assignable<__node_allocator>::value)
468 {__alloc() = _VSTD::move(__x.__alloc());}
470 _LIBCPP_INLINE_VISIBILITY
471 static void __swap_alloc(__node_allocator& __x, __node_allocator& __y)
472 _NOEXCEPT_(!__node_traits::propagate_on_container_swap::value ||
473 __is_nothrow_swappable<__node_allocator>::value)
474 {__swap_alloc(__x, __y, integral_constant<bool,
475 __node_traits::propagate_on_container_swap::value>());}
476 _LIBCPP_INLINE_VISIBILITY
477 static void __swap_alloc(__node_allocator& __x, __node_allocator& __y,
481 _LIBCPP_INLINE_VISIBILITY
482 static void __swap_alloc(__node_allocator& __x, __node_allocator& __y,
484 _NOEXCEPT_(__is_nothrow_swappable<__node_allocator>::value)
491 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
493 template <class _Tp, class _Alloc>
494 inline _LIBCPP_INLINE_VISIBILITY
495 __forward_list_base<_Tp, _Alloc>::__forward_list_base(__forward_list_base&& __x)
496 _NOEXCEPT_(is_nothrow_move_constructible<__node_allocator>::value)
497 : __before_begin_(_VSTD::move(__x.__before_begin_))
499 __x.__before_begin()->__next_ = nullptr;
502 template <class _Tp, class _Alloc>
503 inline _LIBCPP_INLINE_VISIBILITY
504 __forward_list_base<_Tp, _Alloc>::__forward_list_base(__forward_list_base&& __x,
505 const allocator_type& __a)
506 : __before_begin_(__begin_node(), __node_allocator(__a))
508 if (__alloc() == __x.__alloc())
510 __before_begin()->__next_ = __x.__before_begin()->__next_;
511 __x.__before_begin()->__next_ = nullptr;
515 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
517 template <class _Tp, class _Alloc>
518 __forward_list_base<_Tp, _Alloc>::~__forward_list_base()
523 template <class _Tp, class _Alloc>
524 inline _LIBCPP_INLINE_VISIBILITY
526 __forward_list_base<_Tp, _Alloc>::swap(__forward_list_base& __x)
527 _NOEXCEPT_(!__node_traits::propagate_on_container_swap::value ||
528 __is_nothrow_swappable<__node_allocator>::value)
530 __swap_alloc(__alloc(), __x.__alloc());
532 swap(__before_begin()->__next_, __x.__before_begin()->__next_);
535 template <class _Tp, class _Alloc>
537 __forward_list_base<_Tp, _Alloc>::clear() _NOEXCEPT
539 __node_allocator& __a = __alloc();
540 for (__node_pointer __p = __before_begin()->__next_; __p != nullptr;)
542 __node_pointer __next = __p->__next_;
543 __node_traits::destroy(__a, _VSTD::addressof(__p->__value_));
544 __node_traits::deallocate(__a, __p, 1);
547 __before_begin()->__next_ = nullptr;
550 template <class _Tp, class _Alloc = allocator<_Tp> >
551 class _LIBCPP_TYPE_VIS_ONLY forward_list
552 : private __forward_list_base<_Tp, _Alloc>
554 typedef __forward_list_base<_Tp, _Alloc> base;
555 typedef typename base::__node_allocator __node_allocator;
556 typedef typename base::__node __node;
557 typedef typename base::__node_traits __node_traits;
558 typedef typename base::__node_pointer __node_pointer;
561 typedef _Tp value_type;
562 typedef _Alloc allocator_type;
564 typedef value_type& reference;
565 typedef const value_type& const_reference;
566 typedef typename allocator_traits<allocator_type>::pointer pointer;
567 typedef typename allocator_traits<allocator_type>::const_pointer const_pointer;
568 typedef typename allocator_traits<allocator_type>::size_type size_type;
569 typedef typename allocator_traits<allocator_type>::difference_type difference_type;
571 typedef typename base::iterator iterator;
572 typedef typename base::const_iterator const_iterator;
574 _LIBCPP_INLINE_VISIBILITY
576 _NOEXCEPT_(is_nothrow_default_constructible<__node_allocator>::value)
578 explicit forward_list(const allocator_type& __a);
579 explicit forward_list(size_type __n);
580 #if _LIBCPP_STD_VER > 11
581 explicit forward_list(size_type __n, const allocator_type& __a);
583 forward_list(size_type __n, const value_type& __v);
584 forward_list(size_type __n, const value_type& __v, const allocator_type& __a);
585 template <class _InputIterator>
586 forward_list(_InputIterator __f, _InputIterator __l,
588 __is_input_iterator<_InputIterator>::value
590 template <class _InputIterator>
591 forward_list(_InputIterator __f, _InputIterator __l,
592 const allocator_type& __a,
594 __is_input_iterator<_InputIterator>::value
596 forward_list(const forward_list& __x);
597 forward_list(const forward_list& __x, const allocator_type& __a);
598 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
599 _LIBCPP_INLINE_VISIBILITY
600 forward_list(forward_list&& __x)
601 _NOEXCEPT_(is_nothrow_move_constructible<base>::value)
602 : base(_VSTD::move(__x)) {}
603 forward_list(forward_list&& __x, const allocator_type& __a);
604 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
605 #ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
606 forward_list(initializer_list<value_type> __il);
607 forward_list(initializer_list<value_type> __il, const allocator_type& __a);
608 #endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
610 // ~forward_list() = default;
612 forward_list& operator=(const forward_list& __x);
613 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
614 forward_list& operator=(forward_list&& __x)
616 __node_traits::propagate_on_container_move_assignment::value &&
617 is_nothrow_move_assignable<allocator_type>::value);
619 #ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
620 forward_list& operator=(initializer_list<value_type> __il);
621 #endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
623 template <class _InputIterator>
626 __is_input_iterator<_InputIterator>::value,
629 assign(_InputIterator __f, _InputIterator __l);
630 void assign(size_type __n, const value_type& __v);
631 #ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
632 void assign(initializer_list<value_type> __il);
633 #endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
635 _LIBCPP_INLINE_VISIBILITY
636 allocator_type get_allocator() const _NOEXCEPT
637 {return allocator_type(base::__alloc());}
639 _LIBCPP_INLINE_VISIBILITY
640 iterator begin() _NOEXCEPT
641 {return iterator(base::__before_begin()->__next_);}
642 _LIBCPP_INLINE_VISIBILITY
643 const_iterator begin() const _NOEXCEPT
644 {return const_iterator(base::__before_begin()->__next_);}
645 _LIBCPP_INLINE_VISIBILITY
646 iterator end() _NOEXCEPT
647 {return iterator(nullptr);}
648 _LIBCPP_INLINE_VISIBILITY
649 const_iterator end() const _NOEXCEPT
650 {return const_iterator(nullptr);}
652 _LIBCPP_INLINE_VISIBILITY
653 const_iterator cbegin() const _NOEXCEPT
654 {return const_iterator(base::__before_begin()->__next_);}
655 _LIBCPP_INLINE_VISIBILITY
656 const_iterator cend() const _NOEXCEPT
657 {return const_iterator(nullptr);}
659 _LIBCPP_INLINE_VISIBILITY
660 iterator before_begin() _NOEXCEPT
661 {return iterator(base::__before_begin());}
662 _LIBCPP_INLINE_VISIBILITY
663 const_iterator before_begin() const _NOEXCEPT
664 {return const_iterator(base::__before_begin());}
665 _LIBCPP_INLINE_VISIBILITY
666 const_iterator cbefore_begin() const _NOEXCEPT
667 {return const_iterator(base::__before_begin());}
669 _LIBCPP_INLINE_VISIBILITY
670 bool empty() const _NOEXCEPT
671 {return base::__before_begin()->__next_ == nullptr;}
672 _LIBCPP_INLINE_VISIBILITY
673 size_type max_size() const _NOEXCEPT
674 {return numeric_limits<size_type>::max();}
676 _LIBCPP_INLINE_VISIBILITY
677 reference front() {return base::__before_begin()->__next_->__value_;}
678 _LIBCPP_INLINE_VISIBILITY
679 const_reference front() const {return base::__before_begin()->__next_->__value_;}
681 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
682 #ifndef _LIBCPP_HAS_NO_VARIADICS
683 template <class... _Args> void emplace_front(_Args&&... __args);
685 void push_front(value_type&& __v);
686 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
687 void push_front(const value_type& __v);
691 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
692 #ifndef _LIBCPP_HAS_NO_VARIADICS
693 template <class... _Args>
694 iterator emplace_after(const_iterator __p, _Args&&... __args);
695 #endif // _LIBCPP_HAS_NO_VARIADICS
696 iterator insert_after(const_iterator __p, value_type&& __v);
697 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
698 iterator insert_after(const_iterator __p, const value_type& __v);
699 iterator insert_after(const_iterator __p, size_type __n, const value_type& __v);
700 template <class _InputIterator>
701 _LIBCPP_INLINE_VISIBILITY
704 __is_input_iterator<_InputIterator>::value,
707 insert_after(const_iterator __p, _InputIterator __f, _InputIterator __l);
708 #ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
709 iterator insert_after(const_iterator __p, initializer_list<value_type> __il)
710 {return insert_after(__p, __il.begin(), __il.end());}
711 #endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
713 iterator erase_after(const_iterator __p);
714 iterator erase_after(const_iterator __f, const_iterator __l);
716 _LIBCPP_INLINE_VISIBILITY
717 void swap(forward_list& __x)
718 _NOEXCEPT_(!__node_traits::propagate_on_container_swap::value ||
719 __is_nothrow_swappable<__node_allocator>::value)
722 void resize(size_type __n);
723 void resize(size_type __n, const value_type& __v);
724 _LIBCPP_INLINE_VISIBILITY
725 void clear() _NOEXCEPT {base::clear();}
727 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
728 _LIBCPP_INLINE_VISIBILITY
729 void splice_after(const_iterator __p, forward_list&& __x);
730 _LIBCPP_INLINE_VISIBILITY
731 void splice_after(const_iterator __p, forward_list&& __x, const_iterator __i);
732 _LIBCPP_INLINE_VISIBILITY
733 void splice_after(const_iterator __p, forward_list&& __x,
734 const_iterator __f, const_iterator __l);
735 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
736 void splice_after(const_iterator __p, forward_list& __x);
737 void splice_after(const_iterator __p, forward_list& __x, const_iterator __i);
738 void splice_after(const_iterator __p, forward_list& __x,
739 const_iterator __f, const_iterator __l);
740 void remove(const value_type& __v);
741 template <class _Predicate> void remove_if(_Predicate __pred);
742 _LIBCPP_INLINE_VISIBILITY
743 void unique() {unique(__equal_to<value_type>());}
744 template <class _BinaryPredicate> void unique(_BinaryPredicate __binary_pred);
745 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
746 _LIBCPP_INLINE_VISIBILITY
747 void merge(forward_list&& __x) {merge(__x, __less<value_type>());}
748 template <class _Compare>
749 _LIBCPP_INLINE_VISIBILITY
750 void merge(forward_list&& __x, _Compare __comp)
751 {merge(__x, _VSTD::move(__comp));}
752 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
753 _LIBCPP_INLINE_VISIBILITY
754 void merge(forward_list& __x) {merge(__x, __less<value_type>());}
755 template <class _Compare> void merge(forward_list& __x, _Compare __comp);
756 _LIBCPP_INLINE_VISIBILITY
757 void sort() {sort(__less<value_type>());}
758 template <class _Compare> void sort(_Compare __comp);
759 void reverse() _NOEXCEPT;
763 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
764 void __move_assign(forward_list& __x, true_type)
765 _NOEXCEPT_(is_nothrow_move_assignable<allocator_type>::value);
766 void __move_assign(forward_list& __x, false_type);
767 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
769 template <class _Compare>
772 __merge(__node_pointer __f1, __node_pointer __f2, _Compare& __comp);
774 template <class _Compare>
777 __sort(__node_pointer __f, difference_type __sz, _Compare& __comp);
780 template <class _Tp, class _Alloc>
781 inline _LIBCPP_INLINE_VISIBILITY
782 forward_list<_Tp, _Alloc>::forward_list(const allocator_type& __a)
787 template <class _Tp, class _Alloc>
788 forward_list<_Tp, _Alloc>::forward_list(size_type __n)
792 __node_allocator& __a = base::__alloc();
793 typedef __allocator_destructor<__node_allocator> _Dp;
794 unique_ptr<__node, _Dp> __h(nullptr, _Dp(__a, 1));
795 for (__node_pointer __p = base::__before_begin(); __n > 0; --__n,
798 __h.reset(__node_traits::allocate(__a, 1));
799 __node_traits::construct(__a, _VSTD::addressof(__h->__value_));
800 __h->__next_ = nullptr;
801 __p->__next_ = __h.release();
806 #if _LIBCPP_STD_VER > 11
807 template <class _Tp, class _Alloc>
808 forward_list<_Tp, _Alloc>::forward_list(size_type __n, const allocator_type& __a)
813 __node_allocator& __a = base::__alloc();
814 typedef __allocator_destructor<__node_allocator> _Dp;
815 unique_ptr<__node, _Dp> __h(nullptr, _Dp(__a, 1));
816 for (__node_pointer __p = base::__before_begin(); __n > 0; --__n,
819 __h.reset(__node_traits::allocate(__a, 1));
820 __node_traits::construct(__a, _VSTD::addressof(__h->__value_));
821 __h->__next_ = nullptr;
822 __p->__next_ = __h.release();
828 template <class _Tp, class _Alloc>
829 forward_list<_Tp, _Alloc>::forward_list(size_type __n, const value_type& __v)
831 insert_after(cbefore_begin(), __n, __v);
834 template <class _Tp, class _Alloc>
835 forward_list<_Tp, _Alloc>::forward_list(size_type __n, const value_type& __v,
836 const allocator_type& __a)
839 insert_after(cbefore_begin(), __n, __v);
842 template <class _Tp, class _Alloc>
843 template <class _InputIterator>
844 forward_list<_Tp, _Alloc>::forward_list(_InputIterator __f, _InputIterator __l,
846 __is_input_iterator<_InputIterator>::value
849 insert_after(cbefore_begin(), __f, __l);
852 template <class _Tp, class _Alloc>
853 template <class _InputIterator>
854 forward_list<_Tp, _Alloc>::forward_list(_InputIterator __f, _InputIterator __l,
855 const allocator_type& __a,
857 __is_input_iterator<_InputIterator>::value
861 insert_after(cbefore_begin(), __f, __l);
864 template <class _Tp, class _Alloc>
865 forward_list<_Tp, _Alloc>::forward_list(const forward_list& __x)
866 : base(allocator_type(
867 __node_traits::select_on_container_copy_construction(__x.__alloc())
871 insert_after(cbefore_begin(), __x.begin(), __x.end());
874 template <class _Tp, class _Alloc>
875 forward_list<_Tp, _Alloc>::forward_list(const forward_list& __x,
876 const allocator_type& __a)
879 insert_after(cbefore_begin(), __x.begin(), __x.end());
882 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
884 template <class _Tp, class _Alloc>
885 forward_list<_Tp, _Alloc>::forward_list(forward_list&& __x,
886 const allocator_type& __a)
887 : base(_VSTD::move(__x), __a)
889 if (base::__alloc() != __x.__alloc())
891 typedef move_iterator<iterator> _Ip;
892 insert_after(cbefore_begin(), _Ip(__x.begin()), _Ip(__x.end()));
896 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
898 #ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
900 template <class _Tp, class _Alloc>
901 forward_list<_Tp, _Alloc>::forward_list(initializer_list<value_type> __il)
903 insert_after(cbefore_begin(), __il.begin(), __il.end());
906 template <class _Tp, class _Alloc>
907 forward_list<_Tp, _Alloc>::forward_list(initializer_list<value_type> __il,
908 const allocator_type& __a)
911 insert_after(cbefore_begin(), __il.begin(), __il.end());
914 #endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
916 template <class _Tp, class _Alloc>
917 forward_list<_Tp, _Alloc>&
918 forward_list<_Tp, _Alloc>::operator=(const forward_list& __x)
922 base::__copy_assign_alloc(__x);
923 assign(__x.begin(), __x.end());
928 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
930 template <class _Tp, class _Alloc>
932 forward_list<_Tp, _Alloc>::__move_assign(forward_list& __x, true_type)
933 _NOEXCEPT_(is_nothrow_move_assignable<allocator_type>::value)
936 base::__move_assign_alloc(__x);
937 base::__before_begin()->__next_ = __x.__before_begin()->__next_;
938 __x.__before_begin()->__next_ = nullptr;
941 template <class _Tp, class _Alloc>
943 forward_list<_Tp, _Alloc>::__move_assign(forward_list& __x, false_type)
945 if (base::__alloc() == __x.__alloc())
946 __move_assign(__x, true_type());
949 typedef move_iterator<iterator> _Ip;
950 assign(_Ip(__x.begin()), _Ip(__x.end()));
954 template <class _Tp, class _Alloc>
955 inline _LIBCPP_INLINE_VISIBILITY
956 forward_list<_Tp, _Alloc>&
957 forward_list<_Tp, _Alloc>::operator=(forward_list&& __x)
959 __node_traits::propagate_on_container_move_assignment::value &&
960 is_nothrow_move_assignable<allocator_type>::value)
962 __move_assign(__x, integral_constant<bool,
963 __node_traits::propagate_on_container_move_assignment::value>());
967 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
969 #ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
971 template <class _Tp, class _Alloc>
972 inline _LIBCPP_INLINE_VISIBILITY
973 forward_list<_Tp, _Alloc>&
974 forward_list<_Tp, _Alloc>::operator=(initializer_list<value_type> __il)
976 assign(__il.begin(), __il.end());
980 #endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
982 template <class _Tp, class _Alloc>
983 template <class _InputIterator>
986 __is_input_iterator<_InputIterator>::value,
989 forward_list<_Tp, _Alloc>::assign(_InputIterator __f, _InputIterator __l)
991 iterator __i = before_begin();
992 iterator __j = _VSTD::next(__i);
993 iterator __e = end();
994 for (; __j != __e && __f != __l; ++__i, (void) ++__j, ++__f)
997 insert_after(__i, __f, __l);
999 erase_after(__i, __e);
1002 template <class _Tp, class _Alloc>
1004 forward_list<_Tp, _Alloc>::assign(size_type __n, const value_type& __v)
1006 iterator __i = before_begin();
1007 iterator __j = _VSTD::next(__i);
1008 iterator __e = end();
1009 for (; __j != __e && __n > 0; --__n, ++__i, ++__j)
1012 insert_after(__i, __n, __v);
1014 erase_after(__i, __e);
1017 #ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
1019 template <class _Tp, class _Alloc>
1020 inline _LIBCPP_INLINE_VISIBILITY
1022 forward_list<_Tp, _Alloc>::assign(initializer_list<value_type> __il)
1024 assign(__il.begin(), __il.end());
1027 #endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
1029 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
1030 #ifndef _LIBCPP_HAS_NO_VARIADICS
1032 template <class _Tp, class _Alloc>
1033 template <class... _Args>
1035 forward_list<_Tp, _Alloc>::emplace_front(_Args&&... __args)
1037 __node_allocator& __a = base::__alloc();
1038 typedef __allocator_destructor<__node_allocator> _Dp;
1039 unique_ptr<__node, _Dp> __h(__node_traits::allocate(__a, 1), _Dp(__a, 1));
1040 __node_traits::construct(__a, _VSTD::addressof(__h->__value_),
1041 _VSTD::forward<_Args>(__args)...);
1042 __h->__next_ = base::__before_begin()->__next_;
1043 base::__before_begin()->__next_ = __h.release();
1046 #endif // _LIBCPP_HAS_NO_VARIADICS
1048 template <class _Tp, class _Alloc>
1050 forward_list<_Tp, _Alloc>::push_front(value_type&& __v)
1052 __node_allocator& __a = base::__alloc();
1053 typedef __allocator_destructor<__node_allocator> _Dp;
1054 unique_ptr<__node, _Dp> __h(__node_traits::allocate(__a, 1), _Dp(__a, 1));
1055 __node_traits::construct(__a, _VSTD::addressof(__h->__value_), _VSTD::move(__v));
1056 __h->__next_ = base::__before_begin()->__next_;
1057 base::__before_begin()->__next_ = __h.release();
1060 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
1062 template <class _Tp, class _Alloc>
1064 forward_list<_Tp, _Alloc>::push_front(const value_type& __v)
1066 __node_allocator& __a = base::__alloc();
1067 typedef __allocator_destructor<__node_allocator> _Dp;
1068 unique_ptr<__node, _Dp> __h(__node_traits::allocate(__a, 1), _Dp(__a, 1));
1069 __node_traits::construct(__a, _VSTD::addressof(__h->__value_), __v);
1070 __h->__next_ = base::__before_begin()->__next_;
1071 base::__before_begin()->__next_ = __h.release();
1074 template <class _Tp, class _Alloc>
1076 forward_list<_Tp, _Alloc>::pop_front()
1078 __node_allocator& __a = base::__alloc();
1079 __node_pointer __p = base::__before_begin()->__next_;
1080 base::__before_begin()->__next_ = __p->__next_;
1081 __node_traits::destroy(__a, _VSTD::addressof(__p->__value_));
1082 __node_traits::deallocate(__a, __p, 1);
1085 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
1086 #ifndef _LIBCPP_HAS_NO_VARIADICS
1088 template <class _Tp, class _Alloc>
1089 template <class... _Args>
1090 typename forward_list<_Tp, _Alloc>::iterator
1091 forward_list<_Tp, _Alloc>::emplace_after(const_iterator __p, _Args&&... __args)
1093 __node_pointer const __r = __p.__ptr_;
1094 __node_allocator& __a = base::__alloc();
1095 typedef __allocator_destructor<__node_allocator> _Dp;
1096 unique_ptr<__node, _Dp> __h(__node_traits::allocate(__a, 1), _Dp(__a, 1));
1097 __node_traits::construct(__a, _VSTD::addressof(__h->__value_),
1098 _VSTD::forward<_Args>(__args)...);
1099 __h->__next_ = __r->__next_;
1100 __r->__next_ = __h.release();
1101 return iterator(__r->__next_);
1104 #endif // _LIBCPP_HAS_NO_VARIADICS
1106 template <class _Tp, class _Alloc>
1107 typename forward_list<_Tp, _Alloc>::iterator
1108 forward_list<_Tp, _Alloc>::insert_after(const_iterator __p, value_type&& __v)
1110 __node_pointer const __r = __p.__ptr_;
1111 __node_allocator& __a = base::__alloc();
1112 typedef __allocator_destructor<__node_allocator> _Dp;
1113 unique_ptr<__node, _Dp> __h(__node_traits::allocate(__a, 1), _Dp(__a, 1));
1114 __node_traits::construct(__a, _VSTD::addressof(__h->__value_), _VSTD::move(__v));
1115 __h->__next_ = __r->__next_;
1116 __r->__next_ = __h.release();
1117 return iterator(__r->__next_);
1120 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
1122 template <class _Tp, class _Alloc>
1123 typename forward_list<_Tp, _Alloc>::iterator
1124 forward_list<_Tp, _Alloc>::insert_after(const_iterator __p, const value_type& __v)
1126 __node_pointer const __r = __p.__ptr_;
1127 __node_allocator& __a = base::__alloc();
1128 typedef __allocator_destructor<__node_allocator> _Dp;
1129 unique_ptr<__node, _Dp> __h(__node_traits::allocate(__a, 1), _Dp(__a, 1));
1130 __node_traits::construct(__a, _VSTD::addressof(__h->__value_), __v);
1131 __h->__next_ = __r->__next_;
1132 __r->__next_ = __h.release();
1133 return iterator(__r->__next_);
1136 template <class _Tp, class _Alloc>
1137 typename forward_list<_Tp, _Alloc>::iterator
1138 forward_list<_Tp, _Alloc>::insert_after(const_iterator __p, size_type __n,
1139 const value_type& __v)
1141 __node_pointer __r = __p.__ptr_;
1144 __node_allocator& __a = base::__alloc();
1145 typedef __allocator_destructor<__node_allocator> _Dp;
1146 unique_ptr<__node, _Dp> __h(__node_traits::allocate(__a, 1), _Dp(__a, 1));
1147 __node_traits::construct(__a, _VSTD::addressof(__h->__value_), __v);
1148 __node_pointer __first = __h.release();
1149 __node_pointer __last = __first;
1150 #ifndef _LIBCPP_NO_EXCEPTIONS
1153 #endif // _LIBCPP_NO_EXCEPTIONS
1154 for (--__n; __n != 0; --__n, __last = __last->__next_)
1156 __h.reset(__node_traits::allocate(__a, 1));
1157 __node_traits::construct(__a, _VSTD::addressof(__h->__value_), __v);
1158 __last->__next_ = __h.release();
1160 #ifndef _LIBCPP_NO_EXCEPTIONS
1164 while (__first != nullptr)
1166 __node_pointer __next = __first->__next_;
1167 __node_traits::destroy(__a, _VSTD::addressof(__first->__value_));
1168 __node_traits::deallocate(__a, __first, 1);
1173 #endif // _LIBCPP_NO_EXCEPTIONS
1174 __last->__next_ = __r->__next_;
1175 __r->__next_ = __first;
1178 return iterator(__r);
1181 template <class _Tp, class _Alloc>
1182 template <class _InputIterator>
1185 __is_input_iterator<_InputIterator>::value,
1186 typename forward_list<_Tp, _Alloc>::iterator
1188 forward_list<_Tp, _Alloc>::insert_after(const_iterator __p,
1189 _InputIterator __f, _InputIterator __l)
1191 __node_pointer __r = __p.__ptr_;
1194 __node_allocator& __a = base::__alloc();
1195 typedef __allocator_destructor<__node_allocator> _Dp;
1196 unique_ptr<__node, _Dp> __h(__node_traits::allocate(__a, 1), _Dp(__a, 1));
1197 __node_traits::construct(__a, _VSTD::addressof(__h->__value_), *__f);
1198 __node_pointer __first = __h.release();
1199 __node_pointer __last = __first;
1200 #ifndef _LIBCPP_NO_EXCEPTIONS
1203 #endif // _LIBCPP_NO_EXCEPTIONS
1204 for (++__f; __f != __l; ++__f, ((void)(__last = __last->__next_)))
1206 __h.reset(__node_traits::allocate(__a, 1));
1207 __node_traits::construct(__a, _VSTD::addressof(__h->__value_), *__f);
1208 __last->__next_ = __h.release();
1210 #ifndef _LIBCPP_NO_EXCEPTIONS
1214 while (__first != nullptr)
1216 __node_pointer __next = __first->__next_;
1217 __node_traits::destroy(__a, _VSTD::addressof(__first->__value_));
1218 __node_traits::deallocate(__a, __first, 1);
1223 #endif // _LIBCPP_NO_EXCEPTIONS
1224 __last->__next_ = __r->__next_;
1225 __r->__next_ = __first;
1228 return iterator(__r);
1231 template <class _Tp, class _Alloc>
1232 typename forward_list<_Tp, _Alloc>::iterator
1233 forward_list<_Tp, _Alloc>::erase_after(const_iterator __f)
1235 __node_pointer __p = __f.__ptr_;
1236 __node_pointer __n = __p->__next_;
1237 __p->__next_ = __n->__next_;
1238 __node_allocator& __a = base::__alloc();
1239 __node_traits::destroy(__a, _VSTD::addressof(__n->__value_));
1240 __node_traits::deallocate(__a, __n, 1);
1241 return iterator(__p->__next_);
1244 template <class _Tp, class _Alloc>
1245 typename forward_list<_Tp, _Alloc>::iterator
1246 forward_list<_Tp, _Alloc>::erase_after(const_iterator __f, const_iterator __l)
1248 __node_pointer __e = __l.__ptr_;
1251 __node_pointer __p = __f.__ptr_;
1252 __node_pointer __n = __p->__next_;
1256 __node_allocator& __a = base::__alloc();
1260 __node_traits::destroy(__a, _VSTD::addressof(__n->__value_));
1261 __node_traits::deallocate(__a, __n, 1);
1263 } while (__n != __e);
1266 return iterator(__e);
1269 template <class _Tp, class _Alloc>
1271 forward_list<_Tp, _Alloc>::resize(size_type __n)
1274 iterator __p = before_begin();
1275 iterator __i = begin();
1276 iterator __e = end();
1277 for (; __i != __e && __sz < __n; ++__p, ++__i, ++__sz)
1280 erase_after(__p, __e);
1286 __node_allocator& __a = base::__alloc();
1287 typedef __allocator_destructor<__node_allocator> _Dp;
1288 unique_ptr<__node, _Dp> __h(nullptr, _Dp(__a, 1));
1289 for (__node_pointer __ptr = __p.__ptr_; __n > 0; --__n,
1290 __ptr = __ptr->__next_)
1292 __h.reset(__node_traits::allocate(__a, 1));
1293 __node_traits::construct(__a, _VSTD::addressof(__h->__value_));
1294 __h->__next_ = nullptr;
1295 __ptr->__next_ = __h.release();
1301 template <class _Tp, class _Alloc>
1303 forward_list<_Tp, _Alloc>::resize(size_type __n, const value_type& __v)
1306 iterator __p = before_begin();
1307 iterator __i = begin();
1308 iterator __e = end();
1309 for (; __i != __e && __sz < __n; ++__p, ++__i, ++__sz)
1312 erase_after(__p, __e);
1318 __node_allocator& __a = base::__alloc();
1319 typedef __allocator_destructor<__node_allocator> _Dp;
1320 unique_ptr<__node, _Dp> __h(nullptr, _Dp(__a, 1));
1321 for (__node_pointer __ptr = __p.__ptr_; __n > 0; --__n,
1322 __ptr = __ptr->__next_)
1324 __h.reset(__node_traits::allocate(__a, 1));
1325 __node_traits::construct(__a, _VSTD::addressof(__h->__value_), __v);
1326 __h->__next_ = nullptr;
1327 __ptr->__next_ = __h.release();
1333 template <class _Tp, class _Alloc>
1335 forward_list<_Tp, _Alloc>::splice_after(const_iterator __p,
1340 if (__p.__ptr_->__next_ != nullptr)
1342 const_iterator __lm1 = __x.before_begin();
1343 while (__lm1.__ptr_->__next_ != nullptr)
1345 __lm1.__ptr_->__next_ = __p.__ptr_->__next_;
1347 __p.__ptr_->__next_ = __x.__before_begin()->__next_;
1348 __x.__before_begin()->__next_ = nullptr;
1352 template <class _Tp, class _Alloc>
1354 forward_list<_Tp, _Alloc>::splice_after(const_iterator __p,
1358 const_iterator __lm1 = _VSTD::next(__i);
1359 if (__p != __i && __p != __lm1)
1361 __i.__ptr_->__next_ = __lm1.__ptr_->__next_;
1362 __lm1.__ptr_->__next_ = __p.__ptr_->__next_;
1363 __p.__ptr_->__next_ = __lm1.__ptr_;
1367 template <class _Tp, class _Alloc>
1369 forward_list<_Tp, _Alloc>::splice_after(const_iterator __p,
1371 const_iterator __f, const_iterator __l)
1373 if (__f != __l && __p != __f)
1375 const_iterator __lm1 = __f;
1376 while (__lm1.__ptr_->__next_ != __l.__ptr_)
1380 __lm1.__ptr_->__next_ = __p.__ptr_->__next_;
1381 __p.__ptr_->__next_ = __f.__ptr_->__next_;
1382 __f.__ptr_->__next_ = __l.__ptr_;
1387 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
1389 template <class _Tp, class _Alloc>
1390 inline _LIBCPP_INLINE_VISIBILITY
1392 forward_list<_Tp, _Alloc>::splice_after(const_iterator __p,
1395 splice_after(__p, __x);
1398 template <class _Tp, class _Alloc>
1399 inline _LIBCPP_INLINE_VISIBILITY
1401 forward_list<_Tp, _Alloc>::splice_after(const_iterator __p,
1405 splice_after(__p, __x, __i);
1408 template <class _Tp, class _Alloc>
1409 inline _LIBCPP_INLINE_VISIBILITY
1411 forward_list<_Tp, _Alloc>::splice_after(const_iterator __p,
1413 const_iterator __f, const_iterator __l)
1415 splice_after(__p, __x, __f, __l);
1418 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
1420 template <class _Tp, class _Alloc>
1422 forward_list<_Tp, _Alloc>::remove(const value_type& __v)
1424 forward_list<_Tp, _Alloc> __deleted_nodes; // collect the nodes we're removing
1425 iterator __e = end();
1426 for (iterator __i = before_begin(); __i.__ptr_->__next_ != nullptr;)
1428 if (__i.__ptr_->__next_->__value_ == __v)
1430 iterator __j = _VSTD::next(__i, 2);
1431 for (; __j != __e && *__j == __v; ++__j)
1433 __deleted_nodes.splice_after(__deleted_nodes.before_begin(), *this, __i, __j);
1443 template <class _Tp, class _Alloc>
1444 template <class _Predicate>
1446 forward_list<_Tp, _Alloc>::remove_if(_Predicate __pred)
1448 iterator __e = end();
1449 for (iterator __i = before_begin(); __i.__ptr_->__next_ != nullptr;)
1451 if (__pred(__i.__ptr_->__next_->__value_))
1453 iterator __j = _VSTD::next(__i, 2);
1454 for (; __j != __e && __pred(*__j); ++__j)
1456 erase_after(__i, __j);
1466 template <class _Tp, class _Alloc>
1467 template <class _BinaryPredicate>
1469 forward_list<_Tp, _Alloc>::unique(_BinaryPredicate __binary_pred)
1471 for (iterator __i = begin(), __e = end(); __i != __e;)
1473 iterator __j = _VSTD::next(__i);
1474 for (; __j != __e && __binary_pred(*__i, *__j); ++__j)
1476 if (__i.__ptr_->__next_ != __j.__ptr_)
1477 erase_after(__i, __j);
1482 template <class _Tp, class _Alloc>
1483 template <class _Compare>
1485 forward_list<_Tp, _Alloc>::merge(forward_list& __x, _Compare __comp)
1489 base::__before_begin()->__next_ = __merge(base::__before_begin()->__next_,
1490 __x.__before_begin()->__next_,
1492 __x.__before_begin()->__next_ = nullptr;
1496 template <class _Tp, class _Alloc>
1497 template <class _Compare>
1498 typename forward_list<_Tp, _Alloc>::__node_pointer
1499 forward_list<_Tp, _Alloc>::__merge(__node_pointer __f1, __node_pointer __f2,
1502 if (__f1 == nullptr)
1504 if (__f2 == nullptr)
1507 if (__comp(__f2->__value_, __f1->__value_))
1509 __node_pointer __t = __f2;
1510 while (__t->__next_ != nullptr &&
1511 __comp(__t->__next_->__value_, __f1->__value_))
1514 __f2 = __t->__next_;
1515 __t->__next_ = __f1;
1519 __node_pointer __p = __f1;
1520 __f1 = __f1->__next_;
1521 while (__f1 != nullptr && __f2 != nullptr)
1523 if (__comp(__f2->__value_, __f1->__value_))
1525 __node_pointer __t = __f2;
1526 while (__t->__next_ != nullptr &&
1527 __comp(__t->__next_->__value_, __f1->__value_))
1529 __p->__next_ = __f2;
1530 __f2 = __t->__next_;
1531 __t->__next_ = __f1;
1534 __f1 = __f1->__next_;
1536 if (__f2 != nullptr)
1537 __p->__next_ = __f2;
1541 template <class _Tp, class _Alloc>
1542 template <class _Compare>
1543 inline _LIBCPP_INLINE_VISIBILITY
1545 forward_list<_Tp, _Alloc>::sort(_Compare __comp)
1547 base::__before_begin()->__next_ = __sort(base::__before_begin()->__next_,
1548 _VSTD::distance(begin(), end()), __comp);
1551 template <class _Tp, class _Alloc>
1552 template <class _Compare>
1553 typename forward_list<_Tp, _Alloc>::__node_pointer
1554 forward_list<_Tp, _Alloc>::__sort(__node_pointer __f1, difference_type __sz,
1563 if (__comp(__f1->__next_->__value_, __f1->__value_))
1565 __node_pointer __t = __f1->__next_;
1566 __t->__next_ = __f1;
1567 __f1->__next_ = nullptr;
1572 difference_type __sz1 = __sz / 2;
1573 difference_type __sz2 = __sz - __sz1;
1574 __node_pointer __t = _VSTD::next(iterator(__f1), __sz1 - 1).__ptr_;
1575 __node_pointer __f2 = __t->__next_;
1576 __t->__next_ = nullptr;
1577 return __merge(__sort(__f1, __sz1, __comp),
1578 __sort(__f2, __sz2, __comp), __comp);
1581 template <class _Tp, class _Alloc>
1583 forward_list<_Tp, _Alloc>::reverse() _NOEXCEPT
1585 __node_pointer __p = base::__before_begin()->__next_;
1588 __node_pointer __f = __p->__next_;
1589 __p->__next_ = nullptr;
1590 while (__f != nullptr)
1592 __node_pointer __t = __f->__next_;
1597 base::__before_begin()->__next_ = __p;
1601 template <class _Tp, class _Alloc>
1602 bool operator==(const forward_list<_Tp, _Alloc>& __x,
1603 const forward_list<_Tp, _Alloc>& __y)
1605 typedef forward_list<_Tp, _Alloc> _Cp;
1606 typedef typename _Cp::const_iterator _Ip;
1607 _Ip __ix = __x.begin();
1608 _Ip __ex = __x.end();
1609 _Ip __iy = __y.begin();
1610 _Ip __ey = __y.end();
1611 for (; __ix != __ex && __iy != __ey; ++__ix, ++__iy)
1612 if (!(*__ix == *__iy))
1614 return (__ix == __ex) == (__iy == __ey);
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 !(__x == __y);
1625 template <class _Tp, class _Alloc>
1626 inline _LIBCPP_INLINE_VISIBILITY
1627 bool operator< (const forward_list<_Tp, _Alloc>& __x,
1628 const forward_list<_Tp, _Alloc>& __y)
1630 return _VSTD::lexicographical_compare(__x.begin(), __x.end(),
1631 __y.begin(), __y.end());
1634 template <class _Tp, class _Alloc>
1635 inline _LIBCPP_INLINE_VISIBILITY
1636 bool operator> (const forward_list<_Tp, _Alloc>& __x,
1637 const forward_list<_Tp, _Alloc>& __y)
1642 template <class _Tp, class _Alloc>
1643 inline _LIBCPP_INLINE_VISIBILITY
1644 bool operator>=(const forward_list<_Tp, _Alloc>& __x,
1645 const forward_list<_Tp, _Alloc>& __y)
1647 return !(__x < __y);
1650 template <class _Tp, class _Alloc>
1651 inline _LIBCPP_INLINE_VISIBILITY
1652 bool operator<=(const forward_list<_Tp, _Alloc>& __x,
1653 const forward_list<_Tp, _Alloc>& __y)
1655 return !(__y < __x);
1658 template <class _Tp, class _Alloc>
1659 inline _LIBCPP_INLINE_VISIBILITY
1661 swap(forward_list<_Tp, _Alloc>& __x, forward_list<_Tp, _Alloc>& __y)
1662 _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y)))
1667 _LIBCPP_END_NAMESPACE_STD
1669 #endif // _LIBCPP_FORWARD_LIST