2 //===----------------------- forward_list ---------------------------------===//
4 // The LLVM Compiler Infrastructure
6 // This file is dual licensed under the MIT and the University of Illinois Open
7 // Source Licenses. See LICENSE.TXT for details.
9 //===----------------------------------------------------------------------===//
11 #ifndef _LIBCPP_FORWARD_LIST
12 #define _LIBCPP_FORWARD_LIST
20 template <class T, class Allocator = allocator<T>>
25 typedef Allocator allocator_type;
27 typedef value_type& reference;
28 typedef const value_type& const_reference;
29 typedef typename allocator_traits<allocator_type>::pointer pointer;
30 typedef typename allocator_traits<allocator_type>::const_pointer const_pointer;
31 typedef typename allocator_traits<allocator_type>::size_type size_type;
32 typedef typename allocator_traits<allocator_type>::difference_type difference_type;
34 typedef <details> iterator;
35 typedef <details> const_iterator;
38 noexcept(is_nothrow_default_constructible<allocator_type>::value);
39 explicit forward_list(const allocator_type& a);
40 explicit forward_list(size_type n);
41 explicit forward_list(size_type n, const allocator_type& a); // C++14
42 forward_list(size_type n, const value_type& v);
43 forward_list(size_type n, const value_type& v, const allocator_type& a);
44 template <class InputIterator>
45 forward_list(InputIterator first, InputIterator last);
46 template <class InputIterator>
47 forward_list(InputIterator first, InputIterator last, const allocator_type& a);
48 forward_list(const forward_list& x);
49 forward_list(const forward_list& x, const allocator_type& a);
50 forward_list(forward_list&& x)
51 noexcept(is_nothrow_move_constructible<allocator_type>::value);
52 forward_list(forward_list&& x, const allocator_type& a);
53 forward_list(initializer_list<value_type> il);
54 forward_list(initializer_list<value_type> il, const allocator_type& a);
58 forward_list& operator=(const forward_list& x);
59 forward_list& operator=(forward_list&& x)
61 allocator_type::propagate_on_container_move_assignment::value &&
62 is_nothrow_move_assignable<allocator_type>::value);
63 forward_list& operator=(initializer_list<value_type> il);
65 template <class InputIterator>
66 void assign(InputIterator first, InputIterator last);
67 void assign(size_type n, const value_type& v);
68 void assign(initializer_list<value_type> il);
70 allocator_type get_allocator() const noexcept;
72 iterator begin() noexcept;
73 const_iterator begin() const noexcept;
74 iterator end() noexcept;
75 const_iterator end() const noexcept;
77 const_iterator cbegin() const noexcept;
78 const_iterator cend() const noexcept;
80 iterator before_begin() noexcept;
81 const_iterator before_begin() const noexcept;
82 const_iterator cbefore_begin() const noexcept;
84 bool empty() const noexcept;
85 size_type max_size() const noexcept;
88 const_reference front() const;
90 template <class... Args> reference emplace_front(Args&&... args); // reference in C++17
91 void push_front(const value_type& v);
92 void push_front(value_type&& v);
96 template <class... Args>
97 iterator emplace_after(const_iterator p, Args&&... args);
98 iterator insert_after(const_iterator p, const value_type& v);
99 iterator insert_after(const_iterator p, value_type&& v);
100 iterator insert_after(const_iterator p, size_type n, const value_type& v);
101 template <class InputIterator>
102 iterator insert_after(const_iterator p,
103 InputIterator first, InputIterator last);
104 iterator insert_after(const_iterator p, initializer_list<value_type> il);
106 iterator erase_after(const_iterator p);
107 iterator erase_after(const_iterator first, const_iterator last);
109 void swap(forward_list& x)
110 noexcept(allocator_traits<allocator_type>::is_always_equal::value); // C++17
112 void resize(size_type n);
113 void resize(size_type n, const value_type& v);
114 void clear() noexcept;
116 void splice_after(const_iterator p, forward_list& x);
117 void splice_after(const_iterator p, forward_list&& x);
118 void splice_after(const_iterator p, forward_list& x, const_iterator i);
119 void splice_after(const_iterator p, forward_list&& x, const_iterator i);
120 void splice_after(const_iterator p, forward_list& x,
121 const_iterator first, const_iterator last);
122 void splice_after(const_iterator p, forward_list&& x,
123 const_iterator first, const_iterator last);
124 void remove(const value_type& v);
125 template <class Predicate> void remove_if(Predicate pred);
127 template <class BinaryPredicate> void unique(BinaryPredicate binary_pred);
128 void merge(forward_list& x);
129 void merge(forward_list&& x);
130 template <class Compare> void merge(forward_list& x, Compare comp);
131 template <class Compare> void merge(forward_list&& x, Compare comp);
133 template <class Compare> void sort(Compare comp);
134 void reverse() noexcept;
137 template <class T, class Allocator>
138 bool operator==(const forward_list<T, Allocator>& x,
139 const forward_list<T, Allocator>& y);
141 template <class T, class Allocator>
142 bool operator< (const forward_list<T, Allocator>& x,
143 const forward_list<T, Allocator>& y);
145 template <class T, class Allocator>
146 bool operator!=(const forward_list<T, Allocator>& x,
147 const forward_list<T, Allocator>& y);
149 template <class T, class Allocator>
150 bool operator> (const forward_list<T, Allocator>& x,
151 const forward_list<T, Allocator>& y);
153 template <class T, class Allocator>
154 bool operator>=(const forward_list<T, Allocator>& x,
155 const forward_list<T, Allocator>& y);
157 template <class T, class Allocator>
158 bool operator<=(const forward_list<T, Allocator>& x,
159 const forward_list<T, Allocator>& y);
161 template <class T, class Allocator>
162 void swap(forward_list<T, Allocator>& x, forward_list<T, Allocator>& y)
163 noexcept(noexcept(x.swap(y)));
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;
186 template <class _NodePtr> struct __forward_begin_node;
190 struct __forward_list_node_value_type;
192 template <class _Tp, class _VoidPtr>
193 struct __forward_list_node_value_type<__forward_list_node<_Tp, _VoidPtr> > {
197 template <class _NodePtr>
198 struct __forward_node_traits {
200 typedef typename remove_cv<
201 typename pointer_traits<_NodePtr>::element_type>::type __node;
202 typedef typename __forward_list_node_value_type<__node>::type __node_value_type;
203 typedef _NodePtr __node_pointer;
204 typedef __forward_begin_node<_NodePtr> __begin_node;
205 typedef typename __rebind_pointer<_NodePtr, __begin_node>::type
206 __begin_node_pointer;
207 typedef typename __rebind_pointer<_NodePtr, void>::type __void_pointer;
209 #if defined(_LIBCPP_ABI_FORWARD_LIST_REMOVE_NODE_POINTER_UB)
210 typedef __begin_node_pointer __iter_node_pointer;
212 typedef typename conditional<
213 is_pointer<__void_pointer>::value,
214 __begin_node_pointer,
216 >::type __iter_node_pointer;
219 typedef typename conditional<
220 is_same<__iter_node_pointer, __node_pointer>::value,
221 __begin_node_pointer,
223 >::type __non_iter_node_pointer;
225 _LIBCPP_INLINE_VISIBILITY
226 static __iter_node_pointer __as_iter_node(__iter_node_pointer __p) {
229 _LIBCPP_INLINE_VISIBILITY
230 static __iter_node_pointer __as_iter_node(__non_iter_node_pointer __p) {
231 return static_cast<__iter_node_pointer>(static_cast<__void_pointer>(__p));
235 template <class _NodePtr>
236 struct __forward_begin_node
238 typedef _NodePtr pointer;
239 typedef typename __rebind_pointer<_NodePtr, __forward_begin_node>::type __begin_node_pointer;
243 _LIBCPP_INLINE_VISIBILITY __forward_begin_node() : __next_(nullptr) {}
245 _LIBCPP_INLINE_VISIBILITY
246 __begin_node_pointer __next_as_begin() const {
247 return static_cast<__begin_node_pointer>(__next_);
251 template <class _Tp, class _VoidPtr>
252 struct _LIBCPP_HIDDEN __begin_node_of
254 typedef __forward_begin_node<
255 typename __rebind_pointer<_VoidPtr, __forward_list_node<_Tp, _VoidPtr> >::type
259 template <class _Tp, class _VoidPtr>
260 struct __forward_list_node
261 : public __begin_node_of<_Tp, _VoidPtr>::type
263 typedef _Tp value_type;
269 template <class _Tp, class _Alloc = allocator<_Tp> > class _LIBCPP_TEMPLATE_VIS forward_list;
270 template<class _NodeConstPtr> class _LIBCPP_TEMPLATE_VIS __forward_list_const_iterator;
272 template <class _NodePtr>
273 class _LIBCPP_TEMPLATE_VIS __forward_list_iterator
275 typedef __forward_node_traits<_NodePtr> __traits;
276 typedef typename __traits::__node_pointer __node_pointer;
277 typedef typename __traits::__begin_node_pointer __begin_node_pointer;
278 typedef typename __traits::__iter_node_pointer __iter_node_pointer;
279 typedef typename __traits::__void_pointer __void_pointer;
281 __iter_node_pointer __ptr_;
283 _LIBCPP_INLINE_VISIBILITY
284 __begin_node_pointer __get_begin() const {
285 return static_cast<__begin_node_pointer>(
286 static_cast<__void_pointer>(__ptr_));
288 _LIBCPP_INLINE_VISIBILITY
289 __node_pointer __get_unsafe_node_pointer() const {
290 return static_cast<__node_pointer>(
291 static_cast<__void_pointer>(__ptr_));
294 _LIBCPP_INLINE_VISIBILITY
295 explicit __forward_list_iterator(nullptr_t) _NOEXCEPT : __ptr_(nullptr) {}
297 _LIBCPP_INLINE_VISIBILITY
298 explicit __forward_list_iterator(__begin_node_pointer __p) _NOEXCEPT
299 : __ptr_(__traits::__as_iter_node(__p)) {}
301 _LIBCPP_INLINE_VISIBILITY
302 explicit __forward_list_iterator(__node_pointer __p) _NOEXCEPT
303 : __ptr_(__traits::__as_iter_node(__p)) {}
305 template<class, class> friend class _LIBCPP_TEMPLATE_VIS forward_list;
306 template<class> friend class _LIBCPP_TEMPLATE_VIS __forward_list_const_iterator;
309 typedef forward_iterator_tag iterator_category;
310 typedef typename __traits::__node_value_type value_type;
311 typedef value_type& reference;
312 typedef typename pointer_traits<__node_pointer>::difference_type
314 typedef typename __rebind_pointer<__node_pointer, value_type>::type pointer;
316 _LIBCPP_INLINE_VISIBILITY
317 __forward_list_iterator() _NOEXCEPT : __ptr_(nullptr) {}
319 _LIBCPP_INLINE_VISIBILITY
320 reference operator*() const {return __get_unsafe_node_pointer()->__value_;}
321 _LIBCPP_INLINE_VISIBILITY
322 pointer operator->() const {
323 return pointer_traits<pointer>::pointer_to(__get_unsafe_node_pointer()->__value_);
326 _LIBCPP_INLINE_VISIBILITY
327 __forward_list_iterator& operator++()
329 __ptr_ = __traits::__as_iter_node(__ptr_->__next_);
332 _LIBCPP_INLINE_VISIBILITY
333 __forward_list_iterator operator++(int)
335 __forward_list_iterator __t(*this);
340 friend _LIBCPP_INLINE_VISIBILITY
341 bool operator==(const __forward_list_iterator& __x,
342 const __forward_list_iterator& __y)
343 {return __x.__ptr_ == __y.__ptr_;}
344 friend _LIBCPP_INLINE_VISIBILITY
345 bool operator!=(const __forward_list_iterator& __x,
346 const __forward_list_iterator& __y)
347 {return !(__x == __y);}
350 template <class _NodeConstPtr>
351 class _LIBCPP_TEMPLATE_VIS __forward_list_const_iterator
353 static_assert((!is_const<typename pointer_traits<_NodeConstPtr>::element_type>::value), "");
354 typedef _NodeConstPtr _NodePtr;
356 typedef __forward_node_traits<_NodePtr> __traits;
357 typedef typename __traits::__node __node;
358 typedef typename __traits::__node_pointer __node_pointer;
359 typedef typename __traits::__begin_node_pointer __begin_node_pointer;
360 typedef typename __traits::__iter_node_pointer __iter_node_pointer;
361 typedef typename __traits::__void_pointer __void_pointer;
363 __iter_node_pointer __ptr_;
365 __begin_node_pointer __get_begin() const {
366 return static_cast<__begin_node_pointer>(
367 static_cast<__void_pointer>(__ptr_));
369 __node_pointer __get_unsafe_node_pointer() const {
370 return static_cast<__node_pointer>(
371 static_cast<__void_pointer>(__ptr_));
374 _LIBCPP_INLINE_VISIBILITY
375 explicit __forward_list_const_iterator(nullptr_t) _NOEXCEPT
378 _LIBCPP_INLINE_VISIBILITY
379 explicit __forward_list_const_iterator(__begin_node_pointer __p) _NOEXCEPT
380 : __ptr_(__traits::__as_iter_node(__p)) {}
382 _LIBCPP_INLINE_VISIBILITY
383 explicit __forward_list_const_iterator(__node_pointer __p) _NOEXCEPT
384 : __ptr_(__traits::__as_iter_node(__p)) {}
387 template<class, class> friend class forward_list;
390 typedef forward_iterator_tag iterator_category;
391 typedef typename __traits::__node_value_type value_type;
392 typedef const value_type& reference;
393 typedef typename pointer_traits<__node_pointer>::difference_type
395 typedef typename __rebind_pointer<__node_pointer, const value_type>::type
398 _LIBCPP_INLINE_VISIBILITY
399 __forward_list_const_iterator() _NOEXCEPT : __ptr_(nullptr) {}
400 _LIBCPP_INLINE_VISIBILITY
401 __forward_list_const_iterator(__forward_list_iterator<__node_pointer> __p) _NOEXCEPT
402 : __ptr_(__p.__ptr_) {}
404 _LIBCPP_INLINE_VISIBILITY
405 reference operator*() const {return __get_unsafe_node_pointer()->__value_;}
406 _LIBCPP_INLINE_VISIBILITY
407 pointer operator->() const {return pointer_traits<pointer>::pointer_to(
408 __get_unsafe_node_pointer()->__value_);}
410 _LIBCPP_INLINE_VISIBILITY
411 __forward_list_const_iterator& operator++()
413 __ptr_ = __traits::__as_iter_node(__ptr_->__next_);
416 _LIBCPP_INLINE_VISIBILITY
417 __forward_list_const_iterator operator++(int)
419 __forward_list_const_iterator __t(*this);
424 friend _LIBCPP_INLINE_VISIBILITY
425 bool operator==(const __forward_list_const_iterator& __x,
426 const __forward_list_const_iterator& __y)
427 {return __x.__ptr_ == __y.__ptr_;}
428 friend _LIBCPP_INLINE_VISIBILITY
429 bool operator!=(const __forward_list_const_iterator& __x,
430 const __forward_list_const_iterator& __y)
431 {return !(__x == __y);}
434 template <class _Tp, class _Alloc>
435 class __forward_list_base
438 typedef _Tp value_type;
439 typedef _Alloc allocator_type;
441 typedef typename allocator_traits<allocator_type>::void_pointer void_pointer;
442 typedef __forward_list_node<value_type, void_pointer> __node;
443 typedef typename __begin_node_of<value_type, void_pointer>::type __begin_node;
444 typedef typename __rebind_alloc_helper<allocator_traits<allocator_type>, __node>::type __node_allocator;
445 typedef allocator_traits<__node_allocator> __node_traits;
446 typedef typename __node_traits::pointer __node_pointer;
448 typedef typename __rebind_alloc_helper<
449 allocator_traits<allocator_type>, __begin_node
450 >::type __begin_node_allocator;
451 typedef typename allocator_traits<__begin_node_allocator>::pointer
452 __begin_node_pointer;
454 __compressed_pair<__begin_node, __node_allocator> __before_begin_;
456 _LIBCPP_INLINE_VISIBILITY
457 __begin_node_pointer __before_begin() _NOEXCEPT
458 {return pointer_traits<__begin_node_pointer>::pointer_to(__before_begin_.first());}
459 _LIBCPP_INLINE_VISIBILITY
460 __begin_node_pointer __before_begin() const _NOEXCEPT
461 {return pointer_traits<__begin_node_pointer>::pointer_to(const_cast<__begin_node&>(__before_begin_.first()));}
463 _LIBCPP_INLINE_VISIBILITY
464 __node_allocator& __alloc() _NOEXCEPT
465 {return __before_begin_.second();}
466 _LIBCPP_INLINE_VISIBILITY
467 const __node_allocator& __alloc() const _NOEXCEPT
468 {return __before_begin_.second();}
470 typedef __forward_list_iterator<__node_pointer> iterator;
471 typedef __forward_list_const_iterator<__node_pointer> const_iterator;
473 _LIBCPP_INLINE_VISIBILITY
474 __forward_list_base()
475 _NOEXCEPT_(is_nothrow_default_constructible<__node_allocator>::value)
476 : __before_begin_(__begin_node()) {}
477 _LIBCPP_INLINE_VISIBILITY
478 __forward_list_base(const allocator_type& __a)
479 : __before_begin_(__begin_node(), __node_allocator(__a)) {}
481 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
483 _LIBCPP_INLINE_VISIBILITY
484 __forward_list_base(__forward_list_base&& __x)
485 _NOEXCEPT_(is_nothrow_move_constructible<__node_allocator>::value);
486 _LIBCPP_INLINE_VISIBILITY
487 __forward_list_base(__forward_list_base&& __x, const allocator_type& __a);
488 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
491 __forward_list_base(const __forward_list_base&);
492 __forward_list_base& operator=(const __forward_list_base&);
495 ~__forward_list_base();
498 _LIBCPP_INLINE_VISIBILITY
499 void __copy_assign_alloc(const __forward_list_base& __x)
500 {__copy_assign_alloc(__x, integral_constant<bool,
501 __node_traits::propagate_on_container_copy_assignment::value>());}
503 _LIBCPP_INLINE_VISIBILITY
504 void __move_assign_alloc(__forward_list_base& __x)
505 _NOEXCEPT_(!__node_traits::propagate_on_container_move_assignment::value ||
506 is_nothrow_move_assignable<__node_allocator>::value)
507 {__move_assign_alloc(__x, integral_constant<bool,
508 __node_traits::propagate_on_container_move_assignment::value>());}
511 _LIBCPP_INLINE_VISIBILITY
512 void swap(__forward_list_base& __x)
513 #if _LIBCPP_STD_VER >= 14
516 _NOEXCEPT_(!__node_traits::propagate_on_container_move_assignment::value ||
517 __is_nothrow_swappable<__node_allocator>::value);
520 void clear() _NOEXCEPT;
523 _LIBCPP_INLINE_VISIBILITY
524 void __copy_assign_alloc(const __forward_list_base&, false_type) {}
525 _LIBCPP_INLINE_VISIBILITY
526 void __copy_assign_alloc(const __forward_list_base& __x, true_type)
528 if (__alloc() != __x.__alloc())
530 __alloc() = __x.__alloc();
533 _LIBCPP_INLINE_VISIBILITY
534 void __move_assign_alloc(__forward_list_base&, false_type) _NOEXCEPT
536 _LIBCPP_INLINE_VISIBILITY
537 void __move_assign_alloc(__forward_list_base& __x, true_type)
538 _NOEXCEPT_(is_nothrow_move_assignable<__node_allocator>::value)
539 {__alloc() = _VSTD::move(__x.__alloc());}
542 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
544 template <class _Tp, class _Alloc>
546 __forward_list_base<_Tp, _Alloc>::__forward_list_base(__forward_list_base&& __x)
547 _NOEXCEPT_(is_nothrow_move_constructible<__node_allocator>::value)
548 : __before_begin_(_VSTD::move(__x.__before_begin_))
550 __x.__before_begin()->__next_ = nullptr;
553 template <class _Tp, class _Alloc>
555 __forward_list_base<_Tp, _Alloc>::__forward_list_base(__forward_list_base&& __x,
556 const allocator_type& __a)
557 : __before_begin_(__begin_node(), __node_allocator(__a))
559 if (__alloc() == __x.__alloc())
561 __before_begin()->__next_ = __x.__before_begin()->__next_;
562 __x.__before_begin()->__next_ = nullptr;
566 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
568 template <class _Tp, class _Alloc>
569 __forward_list_base<_Tp, _Alloc>::~__forward_list_base()
574 template <class _Tp, class _Alloc>
577 __forward_list_base<_Tp, _Alloc>::swap(__forward_list_base& __x)
578 #if _LIBCPP_STD_VER >= 14
581 _NOEXCEPT_(!__node_traits::propagate_on_container_move_assignment::value ||
582 __is_nothrow_swappable<__node_allocator>::value)
585 __swap_allocator(__alloc(), __x.__alloc(),
586 integral_constant<bool, __node_traits::propagate_on_container_swap::value>());
588 swap(__before_begin()->__next_, __x.__before_begin()->__next_);
591 template <class _Tp, class _Alloc>
593 __forward_list_base<_Tp, _Alloc>::clear() _NOEXCEPT
595 __node_allocator& __a = __alloc();
596 for (__node_pointer __p = __before_begin()->__next_; __p != nullptr;)
598 __node_pointer __next = __p->__next_;
599 __node_traits::destroy(__a, _VSTD::addressof(__p->__value_));
600 __node_traits::deallocate(__a, __p, 1);
603 __before_begin()->__next_ = nullptr;
606 template <class _Tp, class _Alloc /*= allocator<_Tp>*/>
607 class _LIBCPP_TEMPLATE_VIS forward_list
608 : private __forward_list_base<_Tp, _Alloc>
610 typedef __forward_list_base<_Tp, _Alloc> base;
611 typedef typename base::__node_allocator __node_allocator;
612 typedef typename base::__node __node;
613 typedef typename base::__node_traits __node_traits;
614 typedef typename base::__node_pointer __node_pointer;
615 typedef typename base::__begin_node_pointer __begin_node_pointer;
618 typedef _Tp value_type;
619 typedef _Alloc allocator_type;
621 static_assert((is_same<typename allocator_type::value_type, value_type>::value),
622 "Allocator::value_type must be same type as value_type");
624 typedef value_type& reference;
625 typedef const value_type& const_reference;
626 typedef typename allocator_traits<allocator_type>::pointer pointer;
627 typedef typename allocator_traits<allocator_type>::const_pointer const_pointer;
628 typedef typename allocator_traits<allocator_type>::size_type size_type;
629 typedef typename allocator_traits<allocator_type>::difference_type difference_type;
631 typedef typename base::iterator iterator;
632 typedef typename base::const_iterator const_iterator;
634 _LIBCPP_INLINE_VISIBILITY
636 _NOEXCEPT_(is_nothrow_default_constructible<__node_allocator>::value)
638 _LIBCPP_INLINE_VISIBILITY
639 explicit forward_list(const allocator_type& __a);
640 explicit forward_list(size_type __n);
641 #if _LIBCPP_STD_VER > 11
642 explicit forward_list(size_type __n, const allocator_type& __a);
644 forward_list(size_type __n, const value_type& __v);
645 forward_list(size_type __n, const value_type& __v, const allocator_type& __a);
646 template <class _InputIterator>
647 forward_list(_InputIterator __f, _InputIterator __l,
649 __is_input_iterator<_InputIterator>::value
651 template <class _InputIterator>
652 forward_list(_InputIterator __f, _InputIterator __l,
653 const allocator_type& __a,
655 __is_input_iterator<_InputIterator>::value
657 forward_list(const forward_list& __x);
658 forward_list(const forward_list& __x, const allocator_type& __a);
659 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
660 _LIBCPP_INLINE_VISIBILITY
661 forward_list(forward_list&& __x)
662 _NOEXCEPT_(is_nothrow_move_constructible<base>::value)
663 : base(_VSTD::move(__x)) {}
664 forward_list(forward_list&& __x, const allocator_type& __a);
665 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
666 #ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
667 forward_list(initializer_list<value_type> __il);
668 forward_list(initializer_list<value_type> __il, const allocator_type& __a);
669 #endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
671 // ~forward_list() = default;
673 forward_list& operator=(const forward_list& __x);
674 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
675 _LIBCPP_INLINE_VISIBILITY
676 forward_list& operator=(forward_list&& __x)
678 __node_traits::propagate_on_container_move_assignment::value &&
679 is_nothrow_move_assignable<allocator_type>::value);
681 #ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
682 _LIBCPP_INLINE_VISIBILITY
683 forward_list& operator=(initializer_list<value_type> __il);
684 #endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
686 template <class _InputIterator>
689 __is_input_iterator<_InputIterator>::value,
692 assign(_InputIterator __f, _InputIterator __l);
693 void assign(size_type __n, const value_type& __v);
694 #ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
695 _LIBCPP_INLINE_VISIBILITY
696 void assign(initializer_list<value_type> __il);
697 #endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
699 _LIBCPP_INLINE_VISIBILITY
700 allocator_type get_allocator() const _NOEXCEPT
701 {return allocator_type(base::__alloc());}
703 _LIBCPP_INLINE_VISIBILITY
704 iterator begin() _NOEXCEPT
705 {return iterator(base::__before_begin()->__next_);}
706 _LIBCPP_INLINE_VISIBILITY
707 const_iterator begin() const _NOEXCEPT
708 {return const_iterator(base::__before_begin()->__next_);}
709 _LIBCPP_INLINE_VISIBILITY
710 iterator end() _NOEXCEPT
711 {return iterator(nullptr);}
712 _LIBCPP_INLINE_VISIBILITY
713 const_iterator end() const _NOEXCEPT
714 {return const_iterator(nullptr);}
716 _LIBCPP_INLINE_VISIBILITY
717 const_iterator cbegin() const _NOEXCEPT
718 {return const_iterator(base::__before_begin()->__next_);}
719 _LIBCPP_INLINE_VISIBILITY
720 const_iterator cend() const _NOEXCEPT
721 {return const_iterator(nullptr);}
723 _LIBCPP_INLINE_VISIBILITY
724 iterator before_begin() _NOEXCEPT
725 {return iterator(base::__before_begin());}
726 _LIBCPP_INLINE_VISIBILITY
727 const_iterator before_begin() const _NOEXCEPT
728 {return const_iterator(base::__before_begin());}
729 _LIBCPP_INLINE_VISIBILITY
730 const_iterator cbefore_begin() const _NOEXCEPT
731 {return const_iterator(base::__before_begin());}
733 _LIBCPP_INLINE_VISIBILITY
734 bool empty() const _NOEXCEPT
735 {return base::__before_begin()->__next_ == nullptr;}
736 _LIBCPP_INLINE_VISIBILITY
737 size_type max_size() const _NOEXCEPT {
738 return std::min<size_type>(
739 __node_traits::max_size(base::__alloc()),
740 numeric_limits<difference_type>::max());
743 _LIBCPP_INLINE_VISIBILITY
744 reference front() {return base::__before_begin()->__next_->__value_;}
745 _LIBCPP_INLINE_VISIBILITY
746 const_reference front() const {return base::__before_begin()->__next_->__value_;}
748 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
749 #ifndef _LIBCPP_HAS_NO_VARIADICS
750 #if _LIBCPP_STD_VER > 14
751 template <class... _Args> reference emplace_front(_Args&&... __args);
753 template <class... _Args> void emplace_front(_Args&&... __args);
756 void push_front(value_type&& __v);
757 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
758 void push_front(const value_type& __v);
762 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
763 #ifndef _LIBCPP_HAS_NO_VARIADICS
764 template <class... _Args>
765 iterator emplace_after(const_iterator __p, _Args&&... __args);
766 #endif // _LIBCPP_HAS_NO_VARIADICS
767 iterator insert_after(const_iterator __p, value_type&& __v);
768 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
769 iterator insert_after(const_iterator __p, const value_type& __v);
770 iterator insert_after(const_iterator __p, size_type __n, const value_type& __v);
771 template <class _InputIterator>
772 _LIBCPP_INLINE_VISIBILITY
775 __is_input_iterator<_InputIterator>::value,
778 insert_after(const_iterator __p, _InputIterator __f, _InputIterator __l);
779 #ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
780 iterator insert_after(const_iterator __p, initializer_list<value_type> __il)
781 {return insert_after(__p, __il.begin(), __il.end());}
782 #endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
784 iterator erase_after(const_iterator __p);
785 iterator erase_after(const_iterator __f, const_iterator __l);
787 _LIBCPP_INLINE_VISIBILITY
788 void swap(forward_list& __x)
789 #if _LIBCPP_STD_VER >= 14
792 _NOEXCEPT_(!__node_traits::propagate_on_container_swap::value ||
793 __is_nothrow_swappable<__node_allocator>::value)
797 void resize(size_type __n);
798 void resize(size_type __n, const value_type& __v);
799 _LIBCPP_INLINE_VISIBILITY
800 void clear() _NOEXCEPT {base::clear();}
802 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
803 _LIBCPP_INLINE_VISIBILITY
804 void splice_after(const_iterator __p, forward_list&& __x);
805 _LIBCPP_INLINE_VISIBILITY
806 void splice_after(const_iterator __p, forward_list&& __x, const_iterator __i);
807 _LIBCPP_INLINE_VISIBILITY
808 void splice_after(const_iterator __p, forward_list&& __x,
809 const_iterator __f, const_iterator __l);
810 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
811 void splice_after(const_iterator __p, forward_list& __x);
812 void splice_after(const_iterator __p, forward_list& __x, const_iterator __i);
813 void splice_after(const_iterator __p, forward_list& __x,
814 const_iterator __f, const_iterator __l);
815 void remove(const value_type& __v);
816 template <class _Predicate> void remove_if(_Predicate __pred);
817 _LIBCPP_INLINE_VISIBILITY
818 void unique() {unique(__equal_to<value_type>());}
819 template <class _BinaryPredicate> void unique(_BinaryPredicate __binary_pred);
820 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
821 _LIBCPP_INLINE_VISIBILITY
822 void merge(forward_list&& __x) {merge(__x, __less<value_type>());}
823 template <class _Compare>
824 _LIBCPP_INLINE_VISIBILITY
825 void merge(forward_list&& __x, _Compare __comp)
826 {merge(__x, _VSTD::move(__comp));}
827 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
828 _LIBCPP_INLINE_VISIBILITY
829 void merge(forward_list& __x) {merge(__x, __less<value_type>());}
830 template <class _Compare> void merge(forward_list& __x, _Compare __comp);
831 _LIBCPP_INLINE_VISIBILITY
832 void sort() {sort(__less<value_type>());}
833 template <class _Compare> _LIBCPP_INLINE_VISIBILITY void sort(_Compare __comp);
834 void reverse() _NOEXCEPT;
838 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
839 void __move_assign(forward_list& __x, true_type)
840 _NOEXCEPT_(is_nothrow_move_assignable<allocator_type>::value);
841 void __move_assign(forward_list& __x, false_type);
842 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
844 template <class _Compare>
847 __merge(__node_pointer __f1, __node_pointer __f2, _Compare& __comp);
849 template <class _Compare>
852 __sort(__node_pointer __f, difference_type __sz, _Compare& __comp);
855 template <class _Tp, class _Alloc>
857 forward_list<_Tp, _Alloc>::forward_list(const allocator_type& __a)
862 template <class _Tp, class _Alloc>
863 forward_list<_Tp, _Alloc>::forward_list(size_type __n)
867 __node_allocator& __a = base::__alloc();
868 typedef __allocator_destructor<__node_allocator> _Dp;
869 unique_ptr<__node, _Dp> __h(nullptr, _Dp(__a, 1));
870 for (__begin_node_pointer __p = base::__before_begin(); __n > 0; --__n,
871 __p = __p->__next_as_begin())
873 __h.reset(__node_traits::allocate(__a, 1));
874 __node_traits::construct(__a, _VSTD::addressof(__h->__value_));
875 __h->__next_ = nullptr;
876 __p->__next_ = __h.release();
881 #if _LIBCPP_STD_VER > 11
882 template <class _Tp, class _Alloc>
883 forward_list<_Tp, _Alloc>::forward_list(size_type __n,
884 const allocator_type& __base_alloc)
885 : base ( __base_alloc )
889 __node_allocator& __a = base::__alloc();
890 typedef __allocator_destructor<__node_allocator> _Dp;
891 unique_ptr<__node, _Dp> __h(nullptr, _Dp(__a, 1));
892 for (__begin_node_pointer __p = base::__before_begin(); __n > 0; --__n,
893 __p = __p->__next_as_begin())
895 __h.reset(__node_traits::allocate(__a, 1));
896 __node_traits::construct(__a, _VSTD::addressof(__h->__value_));
897 __h->__next_ = nullptr;
898 __p->__next_ = __h.release();
904 template <class _Tp, class _Alloc>
905 forward_list<_Tp, _Alloc>::forward_list(size_type __n, const value_type& __v)
907 insert_after(cbefore_begin(), __n, __v);
910 template <class _Tp, class _Alloc>
911 forward_list<_Tp, _Alloc>::forward_list(size_type __n, const value_type& __v,
912 const allocator_type& __a)
915 insert_after(cbefore_begin(), __n, __v);
918 template <class _Tp, class _Alloc>
919 template <class _InputIterator>
920 forward_list<_Tp, _Alloc>::forward_list(_InputIterator __f, _InputIterator __l,
922 __is_input_iterator<_InputIterator>::value
925 insert_after(cbefore_begin(), __f, __l);
928 template <class _Tp, class _Alloc>
929 template <class _InputIterator>
930 forward_list<_Tp, _Alloc>::forward_list(_InputIterator __f, _InputIterator __l,
931 const allocator_type& __a,
933 __is_input_iterator<_InputIterator>::value
937 insert_after(cbefore_begin(), __f, __l);
940 template <class _Tp, class _Alloc>
941 forward_list<_Tp, _Alloc>::forward_list(const forward_list& __x)
942 : base(allocator_type(
943 __node_traits::select_on_container_copy_construction(__x.__alloc())
947 insert_after(cbefore_begin(), __x.begin(), __x.end());
950 template <class _Tp, class _Alloc>
951 forward_list<_Tp, _Alloc>::forward_list(const forward_list& __x,
952 const allocator_type& __a)
955 insert_after(cbefore_begin(), __x.begin(), __x.end());
958 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
960 template <class _Tp, class _Alloc>
961 forward_list<_Tp, _Alloc>::forward_list(forward_list&& __x,
962 const allocator_type& __a)
963 : base(_VSTD::move(__x), __a)
965 if (base::__alloc() != __x.__alloc())
967 typedef move_iterator<iterator> _Ip;
968 insert_after(cbefore_begin(), _Ip(__x.begin()), _Ip(__x.end()));
972 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
974 #ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
976 template <class _Tp, class _Alloc>
977 forward_list<_Tp, _Alloc>::forward_list(initializer_list<value_type> __il)
979 insert_after(cbefore_begin(), __il.begin(), __il.end());
982 template <class _Tp, class _Alloc>
983 forward_list<_Tp, _Alloc>::forward_list(initializer_list<value_type> __il,
984 const allocator_type& __a)
987 insert_after(cbefore_begin(), __il.begin(), __il.end());
990 #endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
992 template <class _Tp, class _Alloc>
993 forward_list<_Tp, _Alloc>&
994 forward_list<_Tp, _Alloc>::operator=(const forward_list& __x)
998 base::__copy_assign_alloc(__x);
999 assign(__x.begin(), __x.end());
1004 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
1006 template <class _Tp, class _Alloc>
1008 forward_list<_Tp, _Alloc>::__move_assign(forward_list& __x, true_type)
1009 _NOEXCEPT_(is_nothrow_move_assignable<allocator_type>::value)
1012 base::__move_assign_alloc(__x);
1013 base::__before_begin()->__next_ = __x.__before_begin()->__next_;
1014 __x.__before_begin()->__next_ = nullptr;
1017 template <class _Tp, class _Alloc>
1019 forward_list<_Tp, _Alloc>::__move_assign(forward_list& __x, false_type)
1021 if (base::__alloc() == __x.__alloc())
1022 __move_assign(__x, true_type());
1025 typedef move_iterator<iterator> _Ip;
1026 assign(_Ip(__x.begin()), _Ip(__x.end()));
1030 template <class _Tp, class _Alloc>
1032 forward_list<_Tp, _Alloc>&
1033 forward_list<_Tp, _Alloc>::operator=(forward_list&& __x)
1035 __node_traits::propagate_on_container_move_assignment::value &&
1036 is_nothrow_move_assignable<allocator_type>::value)
1038 __move_assign(__x, integral_constant<bool,
1039 __node_traits::propagate_on_container_move_assignment::value>());
1043 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
1045 #ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
1047 template <class _Tp, class _Alloc>
1049 forward_list<_Tp, _Alloc>&
1050 forward_list<_Tp, _Alloc>::operator=(initializer_list<value_type> __il)
1052 assign(__il.begin(), __il.end());
1056 #endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
1058 template <class _Tp, class _Alloc>
1059 template <class _InputIterator>
1062 __is_input_iterator<_InputIterator>::value,
1065 forward_list<_Tp, _Alloc>::assign(_InputIterator __f, _InputIterator __l)
1067 iterator __i = before_begin();
1068 iterator __j = _VSTD::next(__i);
1069 iterator __e = end();
1070 for (; __j != __e && __f != __l; ++__i, (void) ++__j, ++__f)
1073 insert_after(__i, __f, __l);
1075 erase_after(__i, __e);
1078 template <class _Tp, class _Alloc>
1080 forward_list<_Tp, _Alloc>::assign(size_type __n, const value_type& __v)
1082 iterator __i = before_begin();
1083 iterator __j = _VSTD::next(__i);
1084 iterator __e = end();
1085 for (; __j != __e && __n > 0; --__n, ++__i, ++__j)
1088 insert_after(__i, __n, __v);
1090 erase_after(__i, __e);
1093 #ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
1095 template <class _Tp, class _Alloc>
1098 forward_list<_Tp, _Alloc>::assign(initializer_list<value_type> __il)
1100 assign(__il.begin(), __il.end());
1103 #endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
1105 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
1106 #ifndef _LIBCPP_HAS_NO_VARIADICS
1108 template <class _Tp, class _Alloc>
1109 template <class... _Args>
1110 #if _LIBCPP_STD_VER > 14
1111 typename forward_list<_Tp, _Alloc>::reference
1115 forward_list<_Tp, _Alloc>::emplace_front(_Args&&... __args)
1117 __node_allocator& __a = base::__alloc();
1118 typedef __allocator_destructor<__node_allocator> _Dp;
1119 unique_ptr<__node, _Dp> __h(__node_traits::allocate(__a, 1), _Dp(__a, 1));
1120 __node_traits::construct(__a, _VSTD::addressof(__h->__value_),
1121 _VSTD::forward<_Args>(__args)...);
1122 __h->__next_ = base::__before_begin()->__next_;
1123 base::__before_begin()->__next_ = __h.release();
1124 #if _LIBCPP_STD_VER > 14
1125 return base::__before_begin()->__next_->__value_;
1129 #endif // _LIBCPP_HAS_NO_VARIADICS
1131 template <class _Tp, class _Alloc>
1133 forward_list<_Tp, _Alloc>::push_front(value_type&& __v)
1135 __node_allocator& __a = base::__alloc();
1136 typedef __allocator_destructor<__node_allocator> _Dp;
1137 unique_ptr<__node, _Dp> __h(__node_traits::allocate(__a, 1), _Dp(__a, 1));
1138 __node_traits::construct(__a, _VSTD::addressof(__h->__value_), _VSTD::move(__v));
1139 __h->__next_ = base::__before_begin()->__next_;
1140 base::__before_begin()->__next_ = __h.release();
1143 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
1145 template <class _Tp, class _Alloc>
1147 forward_list<_Tp, _Alloc>::push_front(const value_type& __v)
1149 __node_allocator& __a = base::__alloc();
1150 typedef __allocator_destructor<__node_allocator> _Dp;
1151 unique_ptr<__node, _Dp> __h(__node_traits::allocate(__a, 1), _Dp(__a, 1));
1152 __node_traits::construct(__a, _VSTD::addressof(__h->__value_), __v);
1153 __h->__next_ = base::__before_begin()->__next_;
1154 base::__before_begin()->__next_ = __h.release();
1157 template <class _Tp, class _Alloc>
1159 forward_list<_Tp, _Alloc>::pop_front()
1161 __node_allocator& __a = base::__alloc();
1162 __node_pointer __p = base::__before_begin()->__next_;
1163 base::__before_begin()->__next_ = __p->__next_;
1164 __node_traits::destroy(__a, _VSTD::addressof(__p->__value_));
1165 __node_traits::deallocate(__a, __p, 1);
1168 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
1169 #ifndef _LIBCPP_HAS_NO_VARIADICS
1171 template <class _Tp, class _Alloc>
1172 template <class... _Args>
1173 typename forward_list<_Tp, _Alloc>::iterator
1174 forward_list<_Tp, _Alloc>::emplace_after(const_iterator __p, _Args&&... __args)
1176 __begin_node_pointer const __r = __p.__get_begin();
1177 __node_allocator& __a = base::__alloc();
1178 typedef __allocator_destructor<__node_allocator> _Dp;
1179 unique_ptr<__node, _Dp> __h(__node_traits::allocate(__a, 1), _Dp(__a, 1));
1180 __node_traits::construct(__a, _VSTD::addressof(__h->__value_),
1181 _VSTD::forward<_Args>(__args)...);
1182 __h->__next_ = __r->__next_;
1183 __r->__next_ = __h.release();
1184 return iterator(__r->__next_);
1187 #endif // _LIBCPP_HAS_NO_VARIADICS
1189 template <class _Tp, class _Alloc>
1190 typename forward_list<_Tp, _Alloc>::iterator
1191 forward_list<_Tp, _Alloc>::insert_after(const_iterator __p, value_type&& __v)
1193 __begin_node_pointer const __r = __p.__get_begin();
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_), _VSTD::move(__v));
1198 __h->__next_ = __r->__next_;
1199 __r->__next_ = __h.release();
1200 return iterator(__r->__next_);
1203 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
1205 template <class _Tp, class _Alloc>
1206 typename forward_list<_Tp, _Alloc>::iterator
1207 forward_list<_Tp, _Alloc>::insert_after(const_iterator __p, const value_type& __v)
1209 __begin_node_pointer const __r = __p.__get_begin();
1210 __node_allocator& __a = base::__alloc();
1211 typedef __allocator_destructor<__node_allocator> _Dp;
1212 unique_ptr<__node, _Dp> __h(__node_traits::allocate(__a, 1), _Dp(__a, 1));
1213 __node_traits::construct(__a, _VSTD::addressof(__h->__value_), __v);
1214 __h->__next_ = __r->__next_;
1215 __r->__next_ = __h.release();
1216 return iterator(__r->__next_);
1219 template <class _Tp, class _Alloc>
1220 typename forward_list<_Tp, _Alloc>::iterator
1221 forward_list<_Tp, _Alloc>::insert_after(const_iterator __p, size_type __n,
1222 const value_type& __v)
1224 __begin_node_pointer __r = __p.__get_begin();
1227 __node_allocator& __a = base::__alloc();
1228 typedef __allocator_destructor<__node_allocator> _Dp;
1229 unique_ptr<__node, _Dp> __h(__node_traits::allocate(__a, 1), _Dp(__a, 1));
1230 __node_traits::construct(__a, _VSTD::addressof(__h->__value_), __v);
1231 __node_pointer __first = __h.release();
1232 __node_pointer __last = __first;
1233 #ifndef _LIBCPP_NO_EXCEPTIONS
1236 #endif // _LIBCPP_NO_EXCEPTIONS
1237 for (--__n; __n != 0; --__n, __last = __last->__next_)
1239 __h.reset(__node_traits::allocate(__a, 1));
1240 __node_traits::construct(__a, _VSTD::addressof(__h->__value_), __v);
1241 __last->__next_ = __h.release();
1243 #ifndef _LIBCPP_NO_EXCEPTIONS
1247 while (__first != nullptr)
1249 __node_pointer __next = __first->__next_;
1250 __node_traits::destroy(__a, _VSTD::addressof(__first->__value_));
1251 __node_traits::deallocate(__a, __first, 1);
1256 #endif // _LIBCPP_NO_EXCEPTIONS
1257 __last->__next_ = __r->__next_;
1258 __r->__next_ = __first;
1259 __r = static_cast<__begin_node_pointer>(__last);
1261 return iterator(__r);
1264 template <class _Tp, class _Alloc>
1265 template <class _InputIterator>
1268 __is_input_iterator<_InputIterator>::value,
1269 typename forward_list<_Tp, _Alloc>::iterator
1271 forward_list<_Tp, _Alloc>::insert_after(const_iterator __p,
1272 _InputIterator __f, _InputIterator __l)
1274 __begin_node_pointer __r = __p.__get_begin();
1277 __node_allocator& __a = base::__alloc();
1278 typedef __allocator_destructor<__node_allocator> _Dp;
1279 unique_ptr<__node, _Dp> __h(__node_traits::allocate(__a, 1), _Dp(__a, 1));
1280 __node_traits::construct(__a, _VSTD::addressof(__h->__value_), *__f);
1281 __node_pointer __first = __h.release();
1282 __node_pointer __last = __first;
1283 #ifndef _LIBCPP_NO_EXCEPTIONS
1286 #endif // _LIBCPP_NO_EXCEPTIONS
1287 for (++__f; __f != __l; ++__f, ((void)(__last = __last->__next_)))
1289 __h.reset(__node_traits::allocate(__a, 1));
1290 __node_traits::construct(__a, _VSTD::addressof(__h->__value_), *__f);
1291 __last->__next_ = __h.release();
1293 #ifndef _LIBCPP_NO_EXCEPTIONS
1297 while (__first != nullptr)
1299 __node_pointer __next = __first->__next_;
1300 __node_traits::destroy(__a, _VSTD::addressof(__first->__value_));
1301 __node_traits::deallocate(__a, __first, 1);
1306 #endif // _LIBCPP_NO_EXCEPTIONS
1307 __last->__next_ = __r->__next_;
1308 __r->__next_ = __first;
1309 __r = static_cast<__begin_node_pointer>(__last);
1311 return iterator(__r);
1314 template <class _Tp, class _Alloc>
1315 typename forward_list<_Tp, _Alloc>::iterator
1316 forward_list<_Tp, _Alloc>::erase_after(const_iterator __f)
1318 __begin_node_pointer __p = __f.__get_begin();
1319 __node_pointer __n = __p->__next_;
1320 __p->__next_ = __n->__next_;
1321 __node_allocator& __a = base::__alloc();
1322 __node_traits::destroy(__a, _VSTD::addressof(__n->__value_));
1323 __node_traits::deallocate(__a, __n, 1);
1324 return iterator(__p->__next_);
1327 template <class _Tp, class _Alloc>
1328 typename forward_list<_Tp, _Alloc>::iterator
1329 forward_list<_Tp, _Alloc>::erase_after(const_iterator __f, const_iterator __l)
1331 __node_pointer __e = __l.__get_unsafe_node_pointer();
1334 __begin_node_pointer __bp = __f.__get_begin();
1336 __node_pointer __n = __bp->__next_;
1339 __bp->__next_ = __e;
1340 __node_allocator& __a = base::__alloc();
1343 __node_pointer __tmp = __n->__next_;
1344 __node_traits::destroy(__a, _VSTD::addressof(__n->__value_));
1345 __node_traits::deallocate(__a, __n, 1);
1347 } while (__n != __e);
1350 return iterator(__e);
1353 template <class _Tp, class _Alloc>
1355 forward_list<_Tp, _Alloc>::resize(size_type __n)
1358 iterator __p = before_begin();
1359 iterator __i = begin();
1360 iterator __e = end();
1361 for (; __i != __e && __sz < __n; ++__p, ++__i, ++__sz)
1364 erase_after(__p, __e);
1370 __node_allocator& __a = base::__alloc();
1371 typedef __allocator_destructor<__node_allocator> _Dp;
1372 unique_ptr<__node, _Dp> __h(nullptr, _Dp(__a, 1));
1373 for (__begin_node_pointer __ptr = __p.__get_begin(); __n > 0; --__n,
1374 __ptr = __ptr->__next_as_begin())
1376 __h.reset(__node_traits::allocate(__a, 1));
1377 __node_traits::construct(__a, _VSTD::addressof(__h->__value_));
1378 __h->__next_ = nullptr;
1379 __ptr->__next_ = __h.release();
1385 template <class _Tp, class _Alloc>
1387 forward_list<_Tp, _Alloc>::resize(size_type __n, const value_type& __v)
1390 iterator __p = before_begin();
1391 iterator __i = begin();
1392 iterator __e = end();
1393 for (; __i != __e && __sz < __n; ++__p, ++__i, ++__sz)
1396 erase_after(__p, __e);
1402 __node_allocator& __a = base::__alloc();
1403 typedef __allocator_destructor<__node_allocator> _Dp;
1404 unique_ptr<__node, _Dp> __h(nullptr, _Dp(__a, 1));
1405 for (__begin_node_pointer __ptr = __p.__get_begin(); __n > 0; --__n,
1406 __ptr = __ptr->__next_as_begin())
1408 __h.reset(__node_traits::allocate(__a, 1));
1409 __node_traits::construct(__a, _VSTD::addressof(__h->__value_), __v);
1410 __h->__next_ = nullptr;
1411 __ptr->__next_ = __h.release();
1417 template <class _Tp, class _Alloc>
1419 forward_list<_Tp, _Alloc>::splice_after(const_iterator __p,
1424 if (__p.__get_begin()->__next_ != nullptr)
1426 const_iterator __lm1 = __x.before_begin();
1427 while (__lm1.__get_begin()->__next_ != nullptr)
1429 __lm1.__get_begin()->__next_ = __p.__get_begin()->__next_;
1431 __p.__get_begin()->__next_ = __x.__before_begin()->__next_;
1432 __x.__before_begin()->__next_ = nullptr;
1436 template <class _Tp, class _Alloc>
1438 forward_list<_Tp, _Alloc>::splice_after(const_iterator __p,
1439 forward_list& /*__other*/,
1442 const_iterator __lm1 = _VSTD::next(__i);
1443 if (__p != __i && __p != __lm1)
1445 __i.__get_begin()->__next_ = __lm1.__get_begin()->__next_;
1446 __lm1.__get_begin()->__next_ = __p.__get_begin()->__next_;
1447 __p.__get_begin()->__next_ = __lm1.__get_unsafe_node_pointer();
1451 template <class _Tp, class _Alloc>
1453 forward_list<_Tp, _Alloc>::splice_after(const_iterator __p,
1454 forward_list& /*__other*/,
1455 const_iterator __f, const_iterator __l)
1457 if (__f != __l && __p != __f)
1459 const_iterator __lm1 = __f;
1460 while (__lm1.__get_begin()->__next_ != __l.__get_begin())
1464 __lm1.__get_begin()->__next_ = __p.__get_begin()->__next_;
1465 __p.__get_begin()->__next_ = __f.__get_begin()->__next_;
1466 __f.__get_begin()->__next_ = __l.__get_unsafe_node_pointer();
1471 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
1473 template <class _Tp, class _Alloc>
1474 inline _LIBCPP_INLINE_VISIBILITY
1476 forward_list<_Tp, _Alloc>::splice_after(const_iterator __p,
1479 splice_after(__p, __x);
1482 template <class _Tp, class _Alloc>
1483 inline _LIBCPP_INLINE_VISIBILITY
1485 forward_list<_Tp, _Alloc>::splice_after(const_iterator __p,
1489 splice_after(__p, __x, __i);
1492 template <class _Tp, class _Alloc>
1493 inline _LIBCPP_INLINE_VISIBILITY
1495 forward_list<_Tp, _Alloc>::splice_after(const_iterator __p,
1497 const_iterator __f, const_iterator __l)
1499 splice_after(__p, __x, __f, __l);
1502 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
1504 template <class _Tp, class _Alloc>
1506 forward_list<_Tp, _Alloc>::remove(const value_type& __v)
1508 forward_list<_Tp, _Alloc> __deleted_nodes; // collect the nodes we're removing
1509 iterator __e = end();
1510 for (iterator __i = before_begin(); __i.__get_begin()->__next_ != nullptr;)
1512 if (__i.__get_begin()->__next_->__value_ == __v)
1514 iterator __j = _VSTD::next(__i, 2);
1515 for (; __j != __e && *__j == __v; ++__j)
1517 __deleted_nodes.splice_after(__deleted_nodes.before_begin(), *this, __i, __j);
1527 template <class _Tp, class _Alloc>
1528 template <class _Predicate>
1530 forward_list<_Tp, _Alloc>::remove_if(_Predicate __pred)
1532 iterator __e = end();
1533 for (iterator __i = before_begin(); __i.__get_begin()->__next_ != nullptr;)
1535 if (__pred(__i.__get_begin()->__next_->__value_))
1537 iterator __j = _VSTD::next(__i, 2);
1538 for (; __j != __e && __pred(*__j); ++__j)
1540 erase_after(__i, __j);
1550 template <class _Tp, class _Alloc>
1551 template <class _BinaryPredicate>
1553 forward_list<_Tp, _Alloc>::unique(_BinaryPredicate __binary_pred)
1555 for (iterator __i = begin(), __e = end(); __i != __e;)
1557 iterator __j = _VSTD::next(__i);
1558 for (; __j != __e && __binary_pred(*__i, *__j); ++__j)
1560 if (__i.__get_begin()->__next_ != __j.__get_unsafe_node_pointer())
1561 erase_after(__i, __j);
1566 template <class _Tp, class _Alloc>
1567 template <class _Compare>
1569 forward_list<_Tp, _Alloc>::merge(forward_list& __x, _Compare __comp)
1573 base::__before_begin()->__next_ = __merge(base::__before_begin()->__next_,
1574 __x.__before_begin()->__next_,
1576 __x.__before_begin()->__next_ = nullptr;
1580 template <class _Tp, class _Alloc>
1581 template <class _Compare>
1582 typename forward_list<_Tp, _Alloc>::__node_pointer
1583 forward_list<_Tp, _Alloc>::__merge(__node_pointer __f1, __node_pointer __f2,
1586 if (__f1 == nullptr)
1588 if (__f2 == nullptr)
1591 if (__comp(__f2->__value_, __f1->__value_))
1593 __node_pointer __t = __f2;
1594 while (__t->__next_ != nullptr &&
1595 __comp(__t->__next_->__value_, __f1->__value_))
1598 __f2 = __t->__next_;
1599 __t->__next_ = __f1;
1603 __node_pointer __p = __f1;
1604 __f1 = __f1->__next_;
1605 while (__f1 != nullptr && __f2 != nullptr)
1607 if (__comp(__f2->__value_, __f1->__value_))
1609 __node_pointer __t = __f2;
1610 while (__t->__next_ != nullptr &&
1611 __comp(__t->__next_->__value_, __f1->__value_))
1613 __p->__next_ = __f2;
1614 __f2 = __t->__next_;
1615 __t->__next_ = __f1;
1618 __f1 = __f1->__next_;
1620 if (__f2 != nullptr)
1621 __p->__next_ = __f2;
1625 template <class _Tp, class _Alloc>
1626 template <class _Compare>
1629 forward_list<_Tp, _Alloc>::sort(_Compare __comp)
1631 base::__before_begin()->__next_ = __sort(base::__before_begin()->__next_,
1632 _VSTD::distance(begin(), end()), __comp);
1635 template <class _Tp, class _Alloc>
1636 template <class _Compare>
1637 typename forward_list<_Tp, _Alloc>::__node_pointer
1638 forward_list<_Tp, _Alloc>::__sort(__node_pointer __f1, difference_type __sz,
1647 if (__comp(__f1->__next_->__value_, __f1->__value_))
1649 __node_pointer __t = __f1->__next_;
1650 __t->__next_ = __f1;
1651 __f1->__next_ = nullptr;
1656 difference_type __sz1 = __sz / 2;
1657 difference_type __sz2 = __sz - __sz1;
1658 __node_pointer __t = _VSTD::next(iterator(__f1), __sz1 - 1).__get_unsafe_node_pointer();
1659 __node_pointer __f2 = __t->__next_;
1660 __t->__next_ = nullptr;
1661 return __merge(__sort(__f1, __sz1, __comp),
1662 __sort(__f2, __sz2, __comp), __comp);
1665 template <class _Tp, class _Alloc>
1667 forward_list<_Tp, _Alloc>::reverse() _NOEXCEPT
1669 __node_pointer __p = base::__before_begin()->__next_;
1672 __node_pointer __f = __p->__next_;
1673 __p->__next_ = nullptr;
1674 while (__f != nullptr)
1676 __node_pointer __t = __f->__next_;
1681 base::__before_begin()->__next_ = __p;
1685 template <class _Tp, class _Alloc>
1686 bool operator==(const forward_list<_Tp, _Alloc>& __x,
1687 const forward_list<_Tp, _Alloc>& __y)
1689 typedef forward_list<_Tp, _Alloc> _Cp;
1690 typedef typename _Cp::const_iterator _Ip;
1691 _Ip __ix = __x.begin();
1692 _Ip __ex = __x.end();
1693 _Ip __iy = __y.begin();
1694 _Ip __ey = __y.end();
1695 for (; __ix != __ex && __iy != __ey; ++__ix, ++__iy)
1696 if (!(*__ix == *__iy))
1698 return (__ix == __ex) == (__iy == __ey);
1701 template <class _Tp, class _Alloc>
1702 inline _LIBCPP_INLINE_VISIBILITY
1703 bool operator!=(const forward_list<_Tp, _Alloc>& __x,
1704 const forward_list<_Tp, _Alloc>& __y)
1706 return !(__x == __y);
1709 template <class _Tp, class _Alloc>
1710 inline _LIBCPP_INLINE_VISIBILITY
1711 bool operator< (const forward_list<_Tp, _Alloc>& __x,
1712 const forward_list<_Tp, _Alloc>& __y)
1714 return _VSTD::lexicographical_compare(__x.begin(), __x.end(),
1715 __y.begin(), __y.end());
1718 template <class _Tp, class _Alloc>
1719 inline _LIBCPP_INLINE_VISIBILITY
1720 bool operator> (const forward_list<_Tp, _Alloc>& __x,
1721 const forward_list<_Tp, _Alloc>& __y)
1726 template <class _Tp, class _Alloc>
1727 inline _LIBCPP_INLINE_VISIBILITY
1728 bool operator>=(const forward_list<_Tp, _Alloc>& __x,
1729 const forward_list<_Tp, _Alloc>& __y)
1731 return !(__x < __y);
1734 template <class _Tp, class _Alloc>
1735 inline _LIBCPP_INLINE_VISIBILITY
1736 bool operator<=(const forward_list<_Tp, _Alloc>& __x,
1737 const forward_list<_Tp, _Alloc>& __y)
1739 return !(__y < __x);
1742 template <class _Tp, class _Alloc>
1743 inline _LIBCPP_INLINE_VISIBILITY
1745 swap(forward_list<_Tp, _Alloc>& __x, forward_list<_Tp, _Alloc>& __y)
1746 _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y)))
1751 _LIBCPP_END_NAMESPACE_STD
1753 #endif // _LIBCPP_FORWARD_LIST