1// -*- C++ -*-
2//===----------------------- forward_list ---------------------------------===//
3//
4// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
5// See https://llvm.org/LICENSE.txt for license information.
6// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
7//
8//===----------------------------------------------------------------------===//
9
10#ifndef _LIBCPP_FORWARD_LIST
11#define _LIBCPP_FORWARD_LIST
12
13/*
14 forward_list synopsis
15
16namespace std
17{
18
19template <class T, class Allocator = allocator<T>>
20class forward_list
21{
22public:
23 typedef T value_type;
24 typedef Allocator allocator_type;
25
26 typedef value_type& reference;
27 typedef const value_type& const_reference;
28 typedef typename allocator_traits<allocator_type>::pointer pointer;
29 typedef typename allocator_traits<allocator_type>::const_pointer const_pointer;
30 typedef typename allocator_traits<allocator_type>::size_type size_type;
31 typedef typename allocator_traits<allocator_type>::difference_type difference_type;
32
33 typedef <details> iterator;
34 typedef <details> const_iterator;
35
36 forward_list()
37 noexcept(is_nothrow_default_constructible<allocator_type>::value);
38 explicit forward_list(const allocator_type& a);
39 explicit forward_list(size_type n);
40 explicit forward_list(size_type n, const allocator_type& a); // C++14
41 forward_list(size_type n, const value_type& v);
42 forward_list(size_type n, const value_type& v, const allocator_type& a);
43 template <class InputIterator>
44 forward_list(InputIterator first, InputIterator last);
45 template <class InputIterator>
46 forward_list(InputIterator first, InputIterator last, const allocator_type& a);
47 forward_list(const forward_list& x);
48 forward_list(const forward_list& x, const allocator_type& a);
49 forward_list(forward_list&& x)
50 noexcept(is_nothrow_move_constructible<allocator_type>::value);
51 forward_list(forward_list&& x, const allocator_type& a);
52 forward_list(initializer_list<value_type> il);
53 forward_list(initializer_list<value_type> il, const allocator_type& a);
54
55 ~forward_list();
56
57 forward_list& operator=(const forward_list& x);
58 forward_list& operator=(forward_list&& x)
59 noexcept(
60 allocator_type::propagate_on_container_move_assignment::value &&
61 is_nothrow_move_assignable<allocator_type>::value);
62 forward_list& operator=(initializer_list<value_type> il);
63
64 template <class InputIterator>
65 void assign(InputIterator first, InputIterator last);
66 void assign(size_type n, const value_type& v);
67 void assign(initializer_list<value_type> il);
68
69 allocator_type get_allocator() const noexcept;
70
71 iterator begin() noexcept;
72 const_iterator begin() const noexcept;
73 iterator end() noexcept;
74 const_iterator end() const noexcept;
75
76 const_iterator cbegin() const noexcept;
77 const_iterator cend() const noexcept;
78
79 iterator before_begin() noexcept;
80 const_iterator before_begin() const noexcept;
81 const_iterator cbefore_begin() const noexcept;
82
83 bool empty() const noexcept;
84 size_type max_size() const noexcept;
85
86 reference front();
87 const_reference front() const;
88
89 template <class... Args> reference emplace_front(Args&&... args); // reference in C++17
90 void push_front(const value_type& v);
91 void push_front(value_type&& v);
92
93 void pop_front();
94
95 template <class... Args>
96 iterator emplace_after(const_iterator p, Args&&... args);
97 iterator insert_after(const_iterator p, const value_type& v);
98 iterator insert_after(const_iterator p, value_type&& v);
99 iterator insert_after(const_iterator p, size_type n, const value_type& v);
100 template <class InputIterator>
101 iterator insert_after(const_iterator p,
102 InputIterator first, InputIterator last);
103 iterator insert_after(const_iterator p, initializer_list<value_type> il);
104
105 iterator erase_after(const_iterator p);
106 iterator erase_after(const_iterator first, const_iterator last);
107
108 void swap(forward_list& x)
109 noexcept(allocator_traits<allocator_type>::is_always_equal::value); // C++17
110
111 void resize(size_type n);
112 void resize(size_type n, const value_type& v);
113 void clear() noexcept;
114
115 void splice_after(const_iterator p, forward_list& x);
116 void splice_after(const_iterator p, forward_list&& x);
117 void splice_after(const_iterator p, forward_list& x, const_iterator i);
118 void splice_after(const_iterator p, forward_list&& x, const_iterator i);
119 void splice_after(const_iterator p, forward_list& x,
120 const_iterator first, const_iterator last);
121 void splice_after(const_iterator p, forward_list&& x,
122 const_iterator first, const_iterator last);
123 size_type remove(const value_type& v); // void before C++20
124 template <class Predicate>
125 size_type remove_if(Predicate pred); // void before C++20
126 size_type unique(); // void before C++20
127 template <class BinaryPredicate>
128 size_type unique(BinaryPredicate binary_pred); // void before C++20
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);
133 void sort();
134 template <class Compare> void sort(Compare comp);
135 void reverse() noexcept;
136};
137
138
139template <class InputIterator, class Allocator = allocator<typename iterator_traits<InputIterator>::value_type>>
140 forward_list(InputIterator, InputIterator, Allocator = Allocator())
141 -> forward_list<typename iterator_traits<InputIterator>::value_type, Allocator>; // C++17
142
143template <class T, class Allocator>
144 bool operator==(const forward_list<T, Allocator>& x,
145 const forward_list<T, Allocator>& y);
146
147template <class T, class Allocator>
148 bool operator< (const forward_list<T, Allocator>& x,
149 const forward_list<T, Allocator>& y);
150
151template <class T, class Allocator>
152 bool operator!=(const forward_list<T, Allocator>& x,
153 const forward_list<T, Allocator>& y);
154
155template <class T, class Allocator>
156 bool operator> (const forward_list<T, Allocator>& x,
157 const forward_list<T, Allocator>& y);
158
159template <class T, class Allocator>
160 bool operator>=(const forward_list<T, Allocator>& x,
161 const forward_list<T, Allocator>& y);
162
163template <class T, class Allocator>
164 bool operator<=(const forward_list<T, Allocator>& x,
165 const forward_list<T, Allocator>& y);
166
167template <class T, class Allocator>
168 void swap(forward_list<T, Allocator>& x, forward_list<T, Allocator>& y)
169 noexcept(noexcept(x.swap(y)));
170
171template <class T, class Allocator, class U>
172 void erase(forward_list<T, Allocator>& c, const U& value); // C++20
173template <class T, class Allocator, class Predicate>
174 void erase_if(forward_list<T, Allocator>& c, Predicate pred); // C++20
175
176} // std
177
178*/
179
180#include <__config>
181#include <initializer_list>
182#include <memory>
183#include <limits>
184#include <iterator>
185#include <algorithm>
186#include <version>
187
188#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
189#pragma GCC system_header
190#endif
191
192_LIBCPP_PUSH_MACROS
193#include <__undef_macros>
194
195
196_LIBCPP_BEGIN_NAMESPACE_STD
197
198template <class _Tp, class _VoidPtr> struct __forward_list_node;
199template <class _NodePtr> struct __forward_begin_node;
200
201
202template <class>
203struct __forward_list_node_value_type;
204
205template <class _Tp, class _VoidPtr>
206struct __forward_list_node_value_type<__forward_list_node<_Tp, _VoidPtr> > {
207 typedef _Tp type;
208};
209
210template <class _NodePtr>
211struct __forward_node_traits {
212
213 typedef typename remove_cv<
214 typename pointer_traits<_NodePtr>::element_type>::type __node;
215 typedef typename __forward_list_node_value_type<__node>::type __node_value_type;
216 typedef _NodePtr __node_pointer;
217 typedef __forward_begin_node<_NodePtr> __begin_node;
218 typedef typename __rebind_pointer<_NodePtr, __begin_node>::type
219 __begin_node_pointer;
220 typedef typename __rebind_pointer<_NodePtr, void>::type __void_pointer;
221
222#if defined(_LIBCPP_ABI_FORWARD_LIST_REMOVE_NODE_POINTER_UB)
223 typedef __begin_node_pointer __iter_node_pointer;
224#else
225 typedef typename conditional<
226 is_pointer<__void_pointer>::value,
227 __begin_node_pointer,
228 __node_pointer
229 >::type __iter_node_pointer;
230#endif
231
232 typedef typename conditional<
233 is_same<__iter_node_pointer, __node_pointer>::value,
234 __begin_node_pointer,
235 __node_pointer
236 >::type __non_iter_node_pointer;
237
238 _LIBCPP_INLINE_VISIBILITY
239 static __iter_node_pointer __as_iter_node(__iter_node_pointer __p) {
240 return __p;
241 }
242 _LIBCPP_INLINE_VISIBILITY
243 static __iter_node_pointer __as_iter_node(__non_iter_node_pointer __p) {
244 return static_cast<__iter_node_pointer>(static_cast<__void_pointer>(__p));
245 }
246};
247
248template <class _NodePtr>
249struct __forward_begin_node
250{
251 typedef _NodePtr pointer;
252 typedef typename __rebind_pointer<_NodePtr, __forward_begin_node>::type __begin_node_pointer;
253
254 pointer __next_;
255
256 _LIBCPP_INLINE_VISIBILITY __forward_begin_node() : __next_(nullptr) {}
257
258 _LIBCPP_INLINE_VISIBILITY
259 __begin_node_pointer __next_as_begin() const {
260 return static_cast<__begin_node_pointer>(__next_);
261 }
262};
263
264template <class _Tp, class _VoidPtr>
265struct _LIBCPP_HIDDEN __begin_node_of
266{
267 typedef __forward_begin_node<
268 typename __rebind_pointer<_VoidPtr, __forward_list_node<_Tp, _VoidPtr> >::type
269 > type;
270};
271
272template <class _Tp, class _VoidPtr>
273struct __forward_list_node
274 : public __begin_node_of<_Tp, _VoidPtr>::type
275{
276 typedef _Tp value_type;
277
278 value_type __value_;
279};
280
281
282template <class _Tp, class _Alloc = allocator<_Tp> > class _LIBCPP_TEMPLATE_VIS forward_list;
283template<class _NodeConstPtr> class _LIBCPP_TEMPLATE_VIS __forward_list_const_iterator;
284
285template <class _NodePtr>
286class _LIBCPP_TEMPLATE_VIS __forward_list_iterator
287{
288 typedef __forward_node_traits<_NodePtr> __traits;
289 typedef typename __traits::__node_pointer __node_pointer;
290 typedef typename __traits::__begin_node_pointer __begin_node_pointer;
291 typedef typename __traits::__iter_node_pointer __iter_node_pointer;
292 typedef typename __traits::__void_pointer __void_pointer;
293
294 __iter_node_pointer __ptr_;
295
296 _LIBCPP_INLINE_VISIBILITY
297 __begin_node_pointer __get_begin() const {
298 return static_cast<__begin_node_pointer>(
299 static_cast<__void_pointer>(__ptr_));
300 }
301 _LIBCPP_INLINE_VISIBILITY
302 __node_pointer __get_unsafe_node_pointer() const {
303 return static_cast<__node_pointer>(
304 static_cast<__void_pointer>(__ptr_));
305 }
306
307 _LIBCPP_INLINE_VISIBILITY
308 explicit __forward_list_iterator(nullptr_t) _NOEXCEPT : __ptr_(nullptr) {}
309
310 _LIBCPP_INLINE_VISIBILITY
311 explicit __forward_list_iterator(__begin_node_pointer __p) _NOEXCEPT
312 : __ptr_(__traits::__as_iter_node(__p)) {}
313
314 _LIBCPP_INLINE_VISIBILITY
315 explicit __forward_list_iterator(__node_pointer __p) _NOEXCEPT
316 : __ptr_(__traits::__as_iter_node(__p)) {}
317
318 template<class, class> friend class _LIBCPP_TEMPLATE_VIS forward_list;
319 template<class> friend class _LIBCPP_TEMPLATE_VIS __forward_list_const_iterator;
320
321public:
322 typedef forward_iterator_tag iterator_category;
323 typedef typename __traits::__node_value_type value_type;
324 typedef value_type& reference;
325 typedef typename pointer_traits<__node_pointer>::difference_type
326 difference_type;
327 typedef typename __rebind_pointer<__node_pointer, value_type>::type pointer;
328
329 _LIBCPP_INLINE_VISIBILITY
330 __forward_list_iterator() _NOEXCEPT : __ptr_(nullptr) {}
331
332 _LIBCPP_INLINE_VISIBILITY
333 reference operator*() const {return __get_unsafe_node_pointer()->__value_;}
334 _LIBCPP_INLINE_VISIBILITY
335 pointer operator->() const {
336 return pointer_traits<pointer>::pointer_to(__get_unsafe_node_pointer()->__value_);
337 }
338
339 _LIBCPP_INLINE_VISIBILITY
340 __forward_list_iterator& operator++()
341 {
342 __ptr_ = __traits::__as_iter_node(__ptr_->__next_);
343 return *this;
344 }
345 _LIBCPP_INLINE_VISIBILITY
346 __forward_list_iterator operator++(int)
347 {
348 __forward_list_iterator __t(*this);
349 ++(*this);
350 return __t;
351 }
352
353 friend _LIBCPP_INLINE_VISIBILITY
354 bool operator==(const __forward_list_iterator& __x,
355 const __forward_list_iterator& __y)
356 {return __x.__ptr_ == __y.__ptr_;}
357 friend _LIBCPP_INLINE_VISIBILITY
358 bool operator!=(const __forward_list_iterator& __x,
359 const __forward_list_iterator& __y)
360 {return !(__x == __y);}
361};
362
363template <class _NodeConstPtr>
364class _LIBCPP_TEMPLATE_VIS __forward_list_const_iterator
365{
366 static_assert((!is_const<typename pointer_traits<_NodeConstPtr>::element_type>::value), "");
367 typedef _NodeConstPtr _NodePtr;
368
369 typedef __forward_node_traits<_NodePtr> __traits;
370 typedef typename __traits::__node __node;
371 typedef typename __traits::__node_pointer __node_pointer;
372 typedef typename __traits::__begin_node_pointer __begin_node_pointer;
373 typedef typename __traits::__iter_node_pointer __iter_node_pointer;
374 typedef typename __traits::__void_pointer __void_pointer;
375
376 __iter_node_pointer __ptr_;
377
378 __begin_node_pointer __get_begin() const {
379 return static_cast<__begin_node_pointer>(
380 static_cast<__void_pointer>(__ptr_));
381 }
382 __node_pointer __get_unsafe_node_pointer() const {
383 return static_cast<__node_pointer>(
384 static_cast<__void_pointer>(__ptr_));
385 }
386
387 _LIBCPP_INLINE_VISIBILITY
388 explicit __forward_list_const_iterator(nullptr_t) _NOEXCEPT
389 : __ptr_(nullptr) {}
390
391 _LIBCPP_INLINE_VISIBILITY
392 explicit __forward_list_const_iterator(__begin_node_pointer __p) _NOEXCEPT
393 : __ptr_(__traits::__as_iter_node(__p)) {}
394
395 _LIBCPP_INLINE_VISIBILITY
396 explicit __forward_list_const_iterator(__node_pointer __p) _NOEXCEPT
397 : __ptr_(__traits::__as_iter_node(__p)) {}
398
399
400 template<class, class> friend class forward_list;
401
402public:
403 typedef forward_iterator_tag iterator_category;
404 typedef typename __traits::__node_value_type value_type;
405 typedef const value_type& reference;
406 typedef typename pointer_traits<__node_pointer>::difference_type
407 difference_type;
408 typedef typename __rebind_pointer<__node_pointer, const value_type>::type
409 pointer;
410
411 _LIBCPP_INLINE_VISIBILITY
412 __forward_list_const_iterator() _NOEXCEPT : __ptr_(nullptr) {}
413 _LIBCPP_INLINE_VISIBILITY
414 __forward_list_const_iterator(__forward_list_iterator<__node_pointer> __p) _NOEXCEPT
415 : __ptr_(__p.__ptr_) {}
416
417 _LIBCPP_INLINE_VISIBILITY
418 reference operator*() const {return __get_unsafe_node_pointer()->__value_;}
419 _LIBCPP_INLINE_VISIBILITY
420 pointer operator->() const {return pointer_traits<pointer>::pointer_to(
421 __get_unsafe_node_pointer()->__value_);}
422
423 _LIBCPP_INLINE_VISIBILITY
424 __forward_list_const_iterator& operator++()
425 {
426 __ptr_ = __traits::__as_iter_node(__ptr_->__next_);
427 return *this;
428 }
429 _LIBCPP_INLINE_VISIBILITY
430 __forward_list_const_iterator operator++(int)
431 {
432 __forward_list_const_iterator __t(*this);
433 ++(*this);
434 return __t;
435 }
436
437 friend _LIBCPP_INLINE_VISIBILITY
438 bool operator==(const __forward_list_const_iterator& __x,
439 const __forward_list_const_iterator& __y)
440 {return __x.__ptr_ == __y.__ptr_;}
441 friend _LIBCPP_INLINE_VISIBILITY
442 bool operator!=(const __forward_list_const_iterator& __x,
443 const __forward_list_const_iterator& __y)
444 {return !(__x == __y);}
445};
446
447template <class _Tp, class _Alloc>
448class __forward_list_base
449{
450protected:
451 typedef _Tp value_type;
452 typedef _Alloc allocator_type;
453
454 typedef typename allocator_traits<allocator_type>::void_pointer void_pointer;
455 typedef __forward_list_node<value_type, void_pointer> __node;
456 typedef typename __begin_node_of<value_type, void_pointer>::type __begin_node;
457 typedef typename __rebind_alloc_helper<allocator_traits<allocator_type>, __node>::type __node_allocator;
458 typedef allocator_traits<__node_allocator> __node_traits;
459 typedef typename __node_traits::pointer __node_pointer;
460
461 typedef typename __rebind_alloc_helper<
462 allocator_traits<allocator_type>, __begin_node
463 >::type __begin_node_allocator;
464 typedef typename allocator_traits<__begin_node_allocator>::pointer
465 __begin_node_pointer;
466
467 static_assert((!is_same<allocator_type, __node_allocator>::value),
468 "internal allocator type must differ from user-specified "
469 "type; otherwise overload resolution breaks");
470
471 __compressed_pair<__begin_node, __node_allocator> __before_begin_;
472
473 _LIBCPP_INLINE_VISIBILITY
474 __begin_node_pointer __before_begin() _NOEXCEPT
475 {return pointer_traits<__begin_node_pointer>::pointer_to(__before_begin_.first());}
476 _LIBCPP_INLINE_VISIBILITY
477 __begin_node_pointer __before_begin() const _NOEXCEPT
478 {return pointer_traits<__begin_node_pointer>::pointer_to(const_cast<__begin_node&>(__before_begin_.first()));}
479
480 _LIBCPP_INLINE_VISIBILITY
481 __node_allocator& __alloc() _NOEXCEPT
482 {return __before_begin_.second();}
483 _LIBCPP_INLINE_VISIBILITY
484 const __node_allocator& __alloc() const _NOEXCEPT
485 {return __before_begin_.second();}
486
487 typedef __forward_list_iterator<__node_pointer> iterator;
488 typedef __forward_list_const_iterator<__node_pointer> const_iterator;
489
490 _LIBCPP_INLINE_VISIBILITY
491 __forward_list_base()
492 _NOEXCEPT_(is_nothrow_default_constructible<__node_allocator>::value)
493 : __before_begin_(__begin_node()) {}
494 _LIBCPP_INLINE_VISIBILITY
495 explicit __forward_list_base(const allocator_type& __a)
496 : __before_begin_(__begin_node(), __node_allocator(__a)) {}
497 _LIBCPP_INLINE_VISIBILITY
498 explicit __forward_list_base(const __node_allocator& __a)
499 : __before_begin_(__begin_node(), __a) {}
500#ifndef _LIBCPP_CXX03_LANG
501public:
502 _LIBCPP_INLINE_VISIBILITY
503 __forward_list_base(__forward_list_base&& __x)
504 _NOEXCEPT_(is_nothrow_move_constructible<__node_allocator>::value);
505 _LIBCPP_INLINE_VISIBILITY
506 __forward_list_base(__forward_list_base&& __x, const allocator_type& __a);
507#endif // _LIBCPP_CXX03_LANG
508
509private:
510 __forward_list_base(const __forward_list_base&);
511 __forward_list_base& operator=(const __forward_list_base&);
512
513public:
514 ~__forward_list_base();
515
516protected:
517 _LIBCPP_INLINE_VISIBILITY
518 void __copy_assign_alloc(const __forward_list_base& __x)
519 {__copy_assign_alloc(__x, integral_constant<bool,
520 __node_traits::propagate_on_container_copy_assignment::value>());}
521
522 _LIBCPP_INLINE_VISIBILITY
523 void __move_assign_alloc(__forward_list_base& __x)
524 _NOEXCEPT_(!__node_traits::propagate_on_container_move_assignment::value ||
525 is_nothrow_move_assignable<__node_allocator>::value)
526 {__move_assign_alloc(__x, integral_constant<bool,
527 __node_traits::propagate_on_container_move_assignment::value>());}
528
529public:
530 _LIBCPP_INLINE_VISIBILITY
531 void swap(__forward_list_base& __x)
532#if _LIBCPP_STD_VER >= 14
533 _NOEXCEPT;
534#else
535 _NOEXCEPT_(!__node_traits::propagate_on_container_move_assignment::value ||
536 __is_nothrow_swappable<__node_allocator>::value);
537#endif
538protected:
539 void clear() _NOEXCEPT;
540
541private:
542 _LIBCPP_INLINE_VISIBILITY
543 void __copy_assign_alloc(const __forward_list_base&, false_type) {}
544 _LIBCPP_INLINE_VISIBILITY
545 void __copy_assign_alloc(const __forward_list_base& __x, true_type)
546 {
547 if (__alloc() != __x.__alloc())
548 clear();
549 __alloc() = __x.__alloc();
550 }
551
552 _LIBCPP_INLINE_VISIBILITY
553 void __move_assign_alloc(__forward_list_base&, false_type) _NOEXCEPT
554 {}
555 _LIBCPP_INLINE_VISIBILITY
556 void __move_assign_alloc(__forward_list_base& __x, true_type)
557 _NOEXCEPT_(is_nothrow_move_assignable<__node_allocator>::value)
558 {__alloc() = _VSTD::move(__x.__alloc());}
559};
560
561#ifndef _LIBCPP_CXX03_LANG
562
563template <class _Tp, class _Alloc>
564inline
565__forward_list_base<_Tp, _Alloc>::__forward_list_base(__forward_list_base&& __x)
566 _NOEXCEPT_(is_nothrow_move_constructible<__node_allocator>::value)
567 : __before_begin_(_VSTD::move(__x.__before_begin_))
568{
569 __x.__before_begin()->__next_ = nullptr;
570}
571
572template <class _Tp, class _Alloc>
573inline
574__forward_list_base<_Tp, _Alloc>::__forward_list_base(__forward_list_base&& __x,
575 const allocator_type& __a)
576 : __before_begin_(__begin_node(), __node_allocator(__a))
577{
578 if (__alloc() == __x.__alloc())
579 {
580 __before_begin()->__next_ = __x.__before_begin()->__next_;
581 __x.__before_begin()->__next_ = nullptr;
582 }
583}
584
585#endif // _LIBCPP_CXX03_LANG
586
587template <class _Tp, class _Alloc>
588__forward_list_base<_Tp, _Alloc>::~__forward_list_base()
589{
590 clear();
591}
592
593template <class _Tp, class _Alloc>
594inline
595void
596__forward_list_base<_Tp, _Alloc>::swap(__forward_list_base& __x)
597#if _LIBCPP_STD_VER >= 14
598 _NOEXCEPT
599#else
600 _NOEXCEPT_(!__node_traits::propagate_on_container_move_assignment::value ||
601 __is_nothrow_swappable<__node_allocator>::value)
602#endif
603{
604 __swap_allocator(__alloc(), __x.__alloc(),
605 integral_constant<bool, __node_traits::propagate_on_container_swap::value>());
606 using _VSTD::swap;
607 swap(__before_begin()->__next_, __x.__before_begin()->__next_);
608}
609
610template <class _Tp, class _Alloc>
611void
612__forward_list_base<_Tp, _Alloc>::clear() _NOEXCEPT
613{
614 __node_allocator& __a = __alloc();
615 for (__node_pointer __p = __before_begin()->__next_; __p != nullptr;)
616 {
617 __node_pointer __next = __p->__next_;
618 __node_traits::destroy(__a, _VSTD::addressof(__p->__value_));
619 __node_traits::deallocate(__a, __p, 1);
620 __p = __next;
621 }
622 __before_begin()->__next_ = nullptr;
623}
624
625template <class _Tp, class _Alloc /*= allocator<_Tp>*/>
626class _LIBCPP_TEMPLATE_VIS forward_list
627 : private __forward_list_base<_Tp, _Alloc>
628{
629 typedef __forward_list_base<_Tp, _Alloc> base;
630 typedef typename base::__node_allocator __node_allocator;
631 typedef typename base::__node __node;
632 typedef typename base::__node_traits __node_traits;
633 typedef typename base::__node_pointer __node_pointer;
634 typedef typename base::__begin_node_pointer __begin_node_pointer;
635
636public:
637 typedef _Tp value_type;
638 typedef _Alloc allocator_type;
639
640 static_assert((is_same<typename allocator_type::value_type, value_type>::value),
641 "Allocator::value_type must be same type as value_type");
642
643 typedef value_type& reference;
644 typedef const value_type& const_reference;
645 typedef typename allocator_traits<allocator_type>::pointer pointer;
646 typedef typename allocator_traits<allocator_type>::const_pointer const_pointer;
647 typedef typename allocator_traits<allocator_type>::size_type size_type;
648 typedef typename allocator_traits<allocator_type>::difference_type difference_type;
649
650 typedef typename base::iterator iterator;
651 typedef typename base::const_iterator const_iterator;
652#if _LIBCPP_STD_VER > 17
653 typedef size_type __remove_return_type;
654#else
655 typedef void __remove_return_type;
656#endif
657
658 _LIBCPP_INLINE_VISIBILITY
659 forward_list()
660 _NOEXCEPT_(is_nothrow_default_constructible<__node_allocator>::value)
661 {} // = default;
662 _LIBCPP_INLINE_VISIBILITY
663 explicit forward_list(const allocator_type& __a);
664 explicit forward_list(size_type __n);
665#if _LIBCPP_STD_VER > 11
666 explicit forward_list(size_type __n, const allocator_type& __a);
667#endif
668 forward_list(size_type __n, const value_type& __v);
669 forward_list(size_type __n, const value_type& __v, const allocator_type& __a);
670 template <class _InputIterator>
671 forward_list(_InputIterator __f, _InputIterator __l,
672 typename enable_if<
673 __is_input_iterator<_InputIterator>::value
674 >::type* = nullptr);
675 template <class _InputIterator>
676 forward_list(_InputIterator __f, _InputIterator __l,
677 const allocator_type& __a,
678 typename enable_if<
679 __is_input_iterator<_InputIterator>::value
680 >::type* = nullptr);
681 forward_list(const forward_list& __x);
682 forward_list(const forward_list& __x, const allocator_type& __a);
683
684 forward_list& operator=(const forward_list& __x);
685
686#ifndef _LIBCPP_CXX03_LANG
687 _LIBCPP_INLINE_VISIBILITY
688 forward_list(forward_list&& __x)
689 _NOEXCEPT_(is_nothrow_move_constructible<base>::value)
690 : base(_VSTD::move(__x)) {}
691 forward_list(forward_list&& __x, const allocator_type& __a);
692
693 forward_list(initializer_list<value_type> __il);
694 forward_list(initializer_list<value_type> __il, const allocator_type& __a);
695
696 _LIBCPP_INLINE_VISIBILITY
697 forward_list& operator=(forward_list&& __x)
698 _NOEXCEPT_(
699 __node_traits::propagate_on_container_move_assignment::value &&
700 is_nothrow_move_assignable<allocator_type>::value);
701
702 _LIBCPP_INLINE_VISIBILITY
703 forward_list& operator=(initializer_list<value_type> __il);
704
705 _LIBCPP_INLINE_VISIBILITY
706 void assign(initializer_list<value_type> __il);
707#endif // _LIBCPP_CXX03_LANG
708
709 // ~forward_list() = default;
710
711 template <class _InputIterator>
712 typename enable_if
713 <
714 __is_input_iterator<_InputIterator>::value,
715 void
716 >::type
717 assign(_InputIterator __f, _InputIterator __l);
718 void assign(size_type __n, const value_type& __v);
719
720 _LIBCPP_INLINE_VISIBILITY
721 allocator_type get_allocator() const _NOEXCEPT
722 {return allocator_type(base::__alloc());}
723
724 _LIBCPP_INLINE_VISIBILITY
725 iterator begin() _NOEXCEPT
726 {return iterator(base::__before_begin()->__next_);}
727 _LIBCPP_INLINE_VISIBILITY
728 const_iterator begin() const _NOEXCEPT
729 {return const_iterator(base::__before_begin()->__next_);}
730 _LIBCPP_INLINE_VISIBILITY
731 iterator end() _NOEXCEPT
732 {return iterator(nullptr);}
733 _LIBCPP_INLINE_VISIBILITY
734 const_iterator end() const _NOEXCEPT
735 {return const_iterator(nullptr);}
736
737 _LIBCPP_INLINE_VISIBILITY
738 const_iterator cbegin() const _NOEXCEPT
739 {return const_iterator(base::__before_begin()->__next_);}
740 _LIBCPP_INLINE_VISIBILITY
741 const_iterator cend() const _NOEXCEPT
742 {return const_iterator(nullptr);}
743
744 _LIBCPP_INLINE_VISIBILITY
745 iterator before_begin() _NOEXCEPT
746 {return iterator(base::__before_begin());}
747 _LIBCPP_INLINE_VISIBILITY
748 const_iterator before_begin() const _NOEXCEPT
749 {return const_iterator(base::__before_begin());}
750 _LIBCPP_INLINE_VISIBILITY
751 const_iterator cbefore_begin() const _NOEXCEPT
752 {return const_iterator(base::__before_begin());}
753
754 _LIBCPP_NODISCARD_AFTER_CXX17 _LIBCPP_INLINE_VISIBILITY
755 bool empty() const _NOEXCEPT
756 {return base::__before_begin()->__next_ == nullptr;}
757 _LIBCPP_INLINE_VISIBILITY
758 size_type max_size() const _NOEXCEPT {
759 return std::min<size_type>(
760 __node_traits::max_size(base::__alloc()),
761 numeric_limits<difference_type>::max());
762 }
763
764 _LIBCPP_INLINE_VISIBILITY
765 reference front() {return base::__before_begin()->__next_->__value_;}
766 _LIBCPP_INLINE_VISIBILITY
767 const_reference front() const {return base::__before_begin()->__next_->__value_;}
768
769#ifndef _LIBCPP_CXX03_LANG
770#if _LIBCPP_STD_VER > 14
771 template <class... _Args> reference emplace_front(_Args&&... __args);
772#else
773 template <class... _Args> void emplace_front(_Args&&... __args);
774#endif
775 void push_front(value_type&& __v);
776#endif // _LIBCPP_CXX03_LANG
777 void push_front(const value_type& __v);
778
779 void pop_front();
780
781#ifndef _LIBCPP_CXX03_LANG
782 template <class... _Args>
783 iterator emplace_after(const_iterator __p, _Args&&... __args);
784
785 iterator insert_after(const_iterator __p, value_type&& __v);
786 iterator insert_after(const_iterator __p, initializer_list<value_type> __il)
787 {return insert_after(__p, __il.begin(), __il.end());}
788#endif // _LIBCPP_CXX03_LANG
789 iterator insert_after(const_iterator __p, const value_type& __v);
790 iterator insert_after(const_iterator __p, size_type __n, const value_type& __v);
791 template <class _InputIterator>
792 _LIBCPP_INLINE_VISIBILITY
793 typename enable_if
794 <
795 __is_input_iterator<_InputIterator>::value,
796 iterator
797 >::type
798 insert_after(const_iterator __p, _InputIterator __f, _InputIterator __l);
799
800 iterator erase_after(const_iterator __p);
801 iterator erase_after(const_iterator __f, const_iterator __l);
802
803 _LIBCPP_INLINE_VISIBILITY
804 void swap(forward_list& __x)
805#if _LIBCPP_STD_VER >= 14
806 _NOEXCEPT
807#else
808 _NOEXCEPT_(!__node_traits::propagate_on_container_swap::value ||
809 __is_nothrow_swappable<__node_allocator>::value)
810#endif
811 {base::swap(__x);}
812
813 void resize(size_type __n);
814 void resize(size_type __n, const value_type& __v);
815 _LIBCPP_INLINE_VISIBILITY
816 void clear() _NOEXCEPT {base::clear();}
817
818 _LIBCPP_INLINE_VISIBILITY
819 void splice_after(const_iterator __p, forward_list&& __x);
820 _LIBCPP_INLINE_VISIBILITY
821 void splice_after(const_iterator __p, forward_list&& __x, const_iterator __i);
822 _LIBCPP_INLINE_VISIBILITY
823 void splice_after(const_iterator __p, forward_list&& __x,
824 const_iterator __f, const_iterator __l);
825 void splice_after(const_iterator __p, forward_list& __x);
826 void splice_after(const_iterator __p, forward_list& __x, const_iterator __i);
827 void splice_after(const_iterator __p, forward_list& __x,
828 const_iterator __f, const_iterator __l);
829 __remove_return_type remove(const value_type& __v);
830 template <class _Predicate> __remove_return_type remove_if(_Predicate __pred);
831 _LIBCPP_INLINE_VISIBILITY
832 __remove_return_type unique() {return unique(__equal_to<value_type>());}
833 template <class _BinaryPredicate> __remove_return_type unique(_BinaryPredicate __binary_pred);
834#ifndef _LIBCPP_CXX03_LANG
835 _LIBCPP_INLINE_VISIBILITY
836 void merge(forward_list&& __x) {merge(__x, __less<value_type>());}
837 template <class _Compare>
838 _LIBCPP_INLINE_VISIBILITY
839 void merge(forward_list&& __x, _Compare __comp)
840 {merge(__x, _VSTD::move(__comp));}
841#endif // _LIBCPP_CXX03_LANG
842 _LIBCPP_INLINE_VISIBILITY
843 void merge(forward_list& __x) {merge(__x, __less<value_type>());}
844 template <class _Compare> void merge(forward_list& __x, _Compare __comp);
845 _LIBCPP_INLINE_VISIBILITY
846 void sort() {sort(__less<value_type>());}
847 template <class _Compare> _LIBCPP_INLINE_VISIBILITY void sort(_Compare __comp);
848 void reverse() _NOEXCEPT;
849
850private:
851
852#ifndef _LIBCPP_CXX03_LANG
853 void __move_assign(forward_list& __x, true_type)
854 _NOEXCEPT_(is_nothrow_move_assignable<allocator_type>::value);
855 void __move_assign(forward_list& __x, false_type);
856#endif // _LIBCPP_CXX03_LANG
857
858 template <class _Compare>
859 static
860 __node_pointer
861 __merge(__node_pointer __f1, __node_pointer __f2, _Compare& __comp);
862
863 template <class _Compare>
864 static
865 __node_pointer
866 __sort(__node_pointer __f, difference_type __sz, _Compare& __comp);
867};
868
869
870#ifndef _LIBCPP_HAS_NO_DEDUCTION_GUIDES
871template<class _InputIterator,
872 class _Alloc = typename std::allocator<typename iterator_traits<_InputIterator>::value_type>,
873 class = typename enable_if<__is_allocator<_Alloc>::value, void>::type
874 >
875forward_list(_InputIterator, _InputIterator)
876 -> forward_list<typename iterator_traits<_InputIterator>::value_type, _Alloc>;
877
878template<class _InputIterator,
879 class _Alloc,
880 class = typename enable_if<__is_allocator<_Alloc>::value, void>::type
881 >
882forward_list(_InputIterator, _InputIterator, _Alloc)
883 -> forward_list<typename iterator_traits<_InputIterator>::value_type, _Alloc>;
884#endif
885
886template <class _Tp, class _Alloc>
887inline
888forward_list<_Tp, _Alloc>::forward_list(const allocator_type& __a)
889 : base(__a)
890{
891}
892
893template <class _Tp, class _Alloc>
894forward_list<_Tp, _Alloc>::forward_list(size_type __n)
895{
896 if (__n > 0)
897 {
898 __node_allocator& __a = base::__alloc();
899 typedef __allocator_destructor<__node_allocator> _Dp;
900 unique_ptr<__node, _Dp> __h(nullptr, _Dp(__a, 1));
901 for (__begin_node_pointer __p = base::__before_begin(); __n > 0; --__n,
902 __p = __p->__next_as_begin())
903 {
904 __h.reset(__node_traits::allocate(__a, 1));
905 __node_traits::construct(__a, _VSTD::addressof(__h->__value_));
906 __h->__next_ = nullptr;
907 __p->__next_ = __h.release();
908 }
909 }
910}
911
912#if _LIBCPP_STD_VER > 11
913template <class _Tp, class _Alloc>
914forward_list<_Tp, _Alloc>::forward_list(size_type __n,
915 const allocator_type& __base_alloc)
916 : base ( __base_alloc )
917{
918 if (__n > 0)
919 {
920 __node_allocator& __a = base::__alloc();
921 typedef __allocator_destructor<__node_allocator> _Dp;
922 unique_ptr<__node, _Dp> __h(nullptr, _Dp(__a, 1));
923 for (__begin_node_pointer __p = base::__before_begin(); __n > 0; --__n,
924 __p = __p->__next_as_begin())
925 {
926 __h.reset(__node_traits::allocate(__a, 1));
927 __node_traits::construct(__a, _VSTD::addressof(__h->__value_));
928 __h->__next_ = nullptr;
929 __p->__next_ = __h.release();
930 }
931 }
932}
933#endif
934
935template <class _Tp, class _Alloc>
936forward_list<_Tp, _Alloc>::forward_list(size_type __n, const value_type& __v)
937{
938 insert_after(cbefore_begin(), __n, __v);
939}
940
941template <class _Tp, class _Alloc>
942forward_list<_Tp, _Alloc>::forward_list(size_type __n, const value_type& __v,
943 const allocator_type& __a)
944 : base(__a)
945{
946 insert_after(cbefore_begin(), __n, __v);
947}
948
949template <class _Tp, class _Alloc>
950template <class _InputIterator>
951forward_list<_Tp, _Alloc>::forward_list(_InputIterator __f, _InputIterator __l,
952 typename enable_if<
953 __is_input_iterator<_InputIterator>::value
954 >::type*)
955{
956 insert_after(cbefore_begin(), __f, __l);
957}
958
959template <class _Tp, class _Alloc>
960template <class _InputIterator>
961forward_list<_Tp, _Alloc>::forward_list(_InputIterator __f, _InputIterator __l,
962 const allocator_type& __a,
963 typename enable_if<
964 __is_input_iterator<_InputIterator>::value
965 >::type*)
966 : base(__a)
967{
968 insert_after(cbefore_begin(), __f, __l);
969}
970
971template <class _Tp, class _Alloc>
972forward_list<_Tp, _Alloc>::forward_list(const forward_list& __x)
973 : base(
974 __node_traits::select_on_container_copy_construction(__x.__alloc())) {
975 insert_after(cbefore_begin(), __x.begin(), __x.end());
976}
977
978template <class _Tp, class _Alloc>
979forward_list<_Tp, _Alloc>::forward_list(const forward_list& __x,
980 const allocator_type& __a)
981 : base(__a)
982{
983 insert_after(cbefore_begin(), __x.begin(), __x.end());
984}
985
986template <class _Tp, class _Alloc>
987forward_list<_Tp, _Alloc>&
988forward_list<_Tp, _Alloc>::operator=(const forward_list& __x)
989{
990 if (this != &__x)
991 {
992 base::__copy_assign_alloc(__x);
993 assign(__x.begin(), __x.end());
994 }
995 return *this;
996}
997
998#ifndef _LIBCPP_CXX03_LANG
999template <class _Tp, class _Alloc>
1000forward_list<_Tp, _Alloc>::forward_list(forward_list&& __x,
1001 const allocator_type& __a)
1002 : base(_VSTD::move(__x), __a)
1003{
1004 if (base::__alloc() != __x.__alloc())
1005 {
1006 typedef move_iterator<iterator> _Ip;
1007 insert_after(cbefore_begin(), _Ip(__x.begin()), _Ip(__x.end()));
1008 }
1009}
1010
1011template <class _Tp, class _Alloc>
1012forward_list<_Tp, _Alloc>::forward_list(initializer_list<value_type> __il)
1013{
1014 insert_after(cbefore_begin(), __il.begin(), __il.end());
1015}
1016
1017template <class _Tp, class _Alloc>
1018forward_list<_Tp, _Alloc>::forward_list(initializer_list<value_type> __il,
1019 const allocator_type& __a)
1020 : base(__a)
1021{
1022 insert_after(cbefore_begin(), __il.begin(), __il.end());
1023}
1024
1025template <class _Tp, class _Alloc>
1026void
1027forward_list<_Tp, _Alloc>::__move_assign(forward_list& __x, true_type)
1028 _NOEXCEPT_(is_nothrow_move_assignable<allocator_type>::value)
1029{
1030 clear();
1031 base::__move_assign_alloc(__x);
1032 base::__before_begin()->__next_ = __x.__before_begin()->__next_;
1033 __x.__before_begin()->__next_ = nullptr;
1034}
1035
1036template <class _Tp, class _Alloc>
1037void
1038forward_list<_Tp, _Alloc>::__move_assign(forward_list& __x, false_type)
1039{
1040 if (base::__alloc() == __x.__alloc())
1041 __move_assign(__x, true_type());
1042 else
1043 {
1044 typedef move_iterator<iterator> _Ip;
1045 assign(_Ip(__x.begin()), _Ip(__x.end()));
1046 }
1047}
1048
1049template <class _Tp, class _Alloc>
1050inline
1051forward_list<_Tp, _Alloc>&
1052forward_list<_Tp, _Alloc>::operator=(forward_list&& __x)
1053 _NOEXCEPT_(
1054 __node_traits::propagate_on_container_move_assignment::value &&
1055 is_nothrow_move_assignable<allocator_type>::value)
1056{
1057 __move_assign(__x, integral_constant<bool,
1058 __node_traits::propagate_on_container_move_assignment::value>());
1059 return *this;
1060}
1061
1062template <class _Tp, class _Alloc>
1063inline
1064forward_list<_Tp, _Alloc>&
1065forward_list<_Tp, _Alloc>::operator=(initializer_list<value_type> __il)
1066{
1067 assign(__il.begin(), __il.end());
1068 return *this;
1069}
1070
1071#endif // _LIBCPP_CXX03_LANG
1072
1073template <class _Tp, class _Alloc>
1074template <class _InputIterator>
1075typename enable_if
1076<
1077 __is_input_iterator<_InputIterator>::value,
1078 void
1079>::type
1080forward_list<_Tp, _Alloc>::assign(_InputIterator __f, _InputIterator __l)
1081{
1082 iterator __i = before_begin();
1083 iterator __j = _VSTD::next(__i);
1084 iterator __e = end();
1085 for (; __j != __e && __f != __l; ++__i, (void) ++__j, ++__f)
1086 *__j = *__f;
1087 if (__j == __e)
1088 insert_after(__i, __f, __l);
1089 else
1090 erase_after(__i, __e);
1091}
1092
1093template <class _Tp, class _Alloc>
1094void
1095forward_list<_Tp, _Alloc>::assign(size_type __n, const value_type& __v)
1096{
1097 iterator __i = before_begin();
1098 iterator __j = _VSTD::next(__i);
1099 iterator __e = end();
1100 for (; __j != __e && __n > 0; --__n, ++__i, ++__j)
1101 *__j = __v;
1102 if (__j == __e)
1103 insert_after(__i, __n, __v);
1104 else
1105 erase_after(__i, __e);
1106}
1107
1108#ifndef _LIBCPP_CXX03_LANG
1109
1110template <class _Tp, class _Alloc>
1111inline
1112void
1113forward_list<_Tp, _Alloc>::assign(initializer_list<value_type> __il)
1114{
1115 assign(__il.begin(), __il.end());
1116}
1117
1118template <class _Tp, class _Alloc>
1119template <class... _Args>
1120#if _LIBCPP_STD_VER > 14
1121typename forward_list<_Tp, _Alloc>::reference
1122#else
1123void
1124#endif
1125forward_list<_Tp, _Alloc>::emplace_front(_Args&&... __args)
1126{
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_),
1131 _VSTD::forward<_Args>(__args)...);
1132 __h->__next_ = base::__before_begin()->__next_;
1133 base::__before_begin()->__next_ = __h.release();
1134#if _LIBCPP_STD_VER > 14
1135 return base::__before_begin()->__next_->__value_;
1136#endif
1137}
1138
1139template <class _Tp, class _Alloc>
1140void
1141forward_list<_Tp, _Alloc>::push_front(value_type&& __v)
1142{
1143 __node_allocator& __a = base::__alloc();
1144 typedef __allocator_destructor<__node_allocator> _Dp;
1145 unique_ptr<__node, _Dp> __h(__node_traits::allocate(__a, 1), _Dp(__a, 1));
1146 __node_traits::construct(__a, _VSTD::addressof(__h->__value_), _VSTD::move(__v));
1147 __h->__next_ = base::__before_begin()->__next_;
1148 base::__before_begin()->__next_ = __h.release();
1149}
1150
1151#endif // _LIBCPP_CXX03_LANG
1152
1153template <class _Tp, class _Alloc>
1154void
1155forward_list<_Tp, _Alloc>::push_front(const value_type& __v)
1156{
1157 __node_allocator& __a = base::__alloc();
1158 typedef __allocator_destructor<__node_allocator> _Dp;
1159 unique_ptr<__node, _Dp> __h(__node_traits::allocate(__a, 1), _Dp(__a, 1));
1160 __node_traits::construct(__a, _VSTD::addressof(__h->__value_), __v);
1161 __h->__next_ = base::__before_begin()->__next_;
1162 base::__before_begin()->__next_ = __h.release();
1163}
1164
1165template <class _Tp, class _Alloc>
1166void
1167forward_list<_Tp, _Alloc>::pop_front()
1168{
1169 __node_allocator& __a = base::__alloc();
1170 __node_pointer __p = base::__before_begin()->__next_;
1171 base::__before_begin()->__next_ = __p->__next_;
1172 __node_traits::destroy(__a, _VSTD::addressof(__p->__value_));
1173 __node_traits::deallocate(__a, __p, 1);
1174}
1175
1176#ifndef _LIBCPP_CXX03_LANG
1177
1178template <class _Tp, class _Alloc>
1179template <class... _Args>
1180typename forward_list<_Tp, _Alloc>::iterator
1181forward_list<_Tp, _Alloc>::emplace_after(const_iterator __p, _Args&&... __args)
1182{
1183 __begin_node_pointer const __r = __p.__get_begin();
1184 __node_allocator& __a = base::__alloc();
1185 typedef __allocator_destructor<__node_allocator> _Dp;
1186 unique_ptr<__node, _Dp> __h(__node_traits::allocate(__a, 1), _Dp(__a, 1));
1187 __node_traits::construct(__a, _VSTD::addressof(__h->__value_),
1188 _VSTD::forward<_Args>(__args)...);
1189 __h->__next_ = __r->__next_;
1190 __r->__next_ = __h.release();
1191 return iterator(__r->__next_);
1192}
1193
1194template <class _Tp, class _Alloc>
1195typename forward_list<_Tp, _Alloc>::iterator
1196forward_list<_Tp, _Alloc>::insert_after(const_iterator __p, value_type&& __v)
1197{
1198 __begin_node_pointer const __r = __p.__get_begin();
1199 __node_allocator& __a = base::__alloc();
1200 typedef __allocator_destructor<__node_allocator> _Dp;
1201 unique_ptr<__node, _Dp> __h(__node_traits::allocate(__a, 1), _Dp(__a, 1));
1202 __node_traits::construct(__a, _VSTD::addressof(__h->__value_), _VSTD::move(__v));
1203 __h->__next_ = __r->__next_;
1204 __r->__next_ = __h.release();
1205 return iterator(__r->__next_);
1206}
1207
1208#endif // _LIBCPP_CXX03_LANG
1209
1210template <class _Tp, class _Alloc>
1211typename forward_list<_Tp, _Alloc>::iterator
1212forward_list<_Tp, _Alloc>::insert_after(const_iterator __p, const value_type& __v)
1213{
1214 __begin_node_pointer const __r = __p.__get_begin();
1215 __node_allocator& __a = base::__alloc();
1216 typedef __allocator_destructor<__node_allocator> _Dp;
1217 unique_ptr<__node, _Dp> __h(__node_traits::allocate(__a, 1), _Dp(__a, 1));
1218 __node_traits::construct(__a, _VSTD::addressof(__h->__value_), __v);
1219 __h->__next_ = __r->__next_;
1220 __r->__next_ = __h.release();
1221 return iterator(__r->__next_);
1222}
1223
1224template <class _Tp, class _Alloc>
1225typename forward_list<_Tp, _Alloc>::iterator
1226forward_list<_Tp, _Alloc>::insert_after(const_iterator __p, size_type __n,
1227 const value_type& __v)
1228{
1229 __begin_node_pointer __r = __p.__get_begin();
1230 if (__n > 0)
1231 {
1232 __node_allocator& __a = base::__alloc();
1233 typedef __allocator_destructor<__node_allocator> _Dp;
1234 unique_ptr<__node, _Dp> __h(__node_traits::allocate(__a, 1), _Dp(__a, 1));
1235 __node_traits::construct(__a, _VSTD::addressof(__h->__value_), __v);
1236 __node_pointer __first = __h.release();
1237 __node_pointer __last = __first;
1238#ifndef _LIBCPP_NO_EXCEPTIONS
1239 try
1240 {
1241#endif // _LIBCPP_NO_EXCEPTIONS
1242 for (--__n; __n != 0; --__n, __last = __last->__next_)
1243 {
1244 __h.reset(__node_traits::allocate(__a, 1));
1245 __node_traits::construct(__a, _VSTD::addressof(__h->__value_), __v);
1246 __last->__next_ = __h.release();
1247 }
1248#ifndef _LIBCPP_NO_EXCEPTIONS
1249 }
1250 catch (...)
1251 {
1252 while (__first != nullptr)
1253 {
1254 __node_pointer __next = __first->__next_;
1255 __node_traits::destroy(__a, _VSTD::addressof(__first->__value_));
1256 __node_traits::deallocate(__a, __first, 1);
1257 __first = __next;
1258 }
1259 throw;
1260 }
1261#endif // _LIBCPP_NO_EXCEPTIONS
1262 __last->__next_ = __r->__next_;
1263 __r->__next_ = __first;
1264 __r = static_cast<__begin_node_pointer>(__last);
1265 }
1266 return iterator(__r);
1267}
1268
1269template <class _Tp, class _Alloc>
1270template <class _InputIterator>
1271typename enable_if
1272<
1273 __is_input_iterator<_InputIterator>::value,
1274 typename forward_list<_Tp, _Alloc>::iterator
1275>::type
1276forward_list<_Tp, _Alloc>::insert_after(const_iterator __p,
1277 _InputIterator __f, _InputIterator __l)
1278{
1279 __begin_node_pointer __r = __p.__get_begin();
1280 if (__f != __l)
1281 {
1282 __node_allocator& __a = base::__alloc();
1283 typedef __allocator_destructor<__node_allocator> _Dp;
1284 unique_ptr<__node, _Dp> __h(__node_traits::allocate(__a, 1), _Dp(__a, 1));
1285 __node_traits::construct(__a, _VSTD::addressof(__h->__value_), *__f);
1286 __node_pointer __first = __h.release();
1287 __node_pointer __last = __first;
1288#ifndef _LIBCPP_NO_EXCEPTIONS
1289 try
1290 {
1291#endif // _LIBCPP_NO_EXCEPTIONS
1292 for (++__f; __f != __l; ++__f, ((void)(__last = __last->__next_)))
1293 {
1294 __h.reset(__node_traits::allocate(__a, 1));
1295 __node_traits::construct(__a, _VSTD::addressof(__h->__value_), *__f);
1296 __last->__next_ = __h.release();
1297 }
1298#ifndef _LIBCPP_NO_EXCEPTIONS
1299 }
1300 catch (...)
1301 {
1302 while (__first != nullptr)
1303 {
1304 __node_pointer __next = __first->__next_;
1305 __node_traits::destroy(__a, _VSTD::addressof(__first->__value_));
1306 __node_traits::deallocate(__a, __first, 1);
1307 __first = __next;
1308 }
1309 throw;
1310 }
1311#endif // _LIBCPP_NO_EXCEPTIONS
1312 __last->__next_ = __r->__next_;
1313 __r->__next_ = __first;
1314 __r = static_cast<__begin_node_pointer>(__last);
1315 }
1316 return iterator(__r);
1317}
1318
1319template <class _Tp, class _Alloc>
1320typename forward_list<_Tp, _Alloc>::iterator
1321forward_list<_Tp, _Alloc>::erase_after(const_iterator __f)
1322{
1323 __begin_node_pointer __p = __f.__get_begin();
1324 __node_pointer __n = __p->__next_;
1325 __p->__next_ = __n->__next_;
1326 __node_allocator& __a = base::__alloc();
1327 __node_traits::destroy(__a, _VSTD::addressof(__n->__value_));
1328 __node_traits::deallocate(__a, __n, 1);
1329 return iterator(__p->__next_);
1330}
1331
1332template <class _Tp, class _Alloc>
1333typename forward_list<_Tp, _Alloc>::iterator
1334forward_list<_Tp, _Alloc>::erase_after(const_iterator __f, const_iterator __l)
1335{
1336 __node_pointer __e = __l.__get_unsafe_node_pointer();
1337 if (__f != __l)
1338 {
1339 __begin_node_pointer __bp = __f.__get_begin();
1340
1341 __node_pointer __n = __bp->__next_;
1342 if (__n != __e)
1343 {
1344 __bp->__next_ = __e;
1345 __node_allocator& __a = base::__alloc();
1346 do
1347 {
1348 __node_pointer __tmp = __n->__next_;
1349 __node_traits::destroy(__a, _VSTD::addressof(__n->__value_));
1350 __node_traits::deallocate(__a, __n, 1);
1351 __n = __tmp;
1352 } while (__n != __e);
1353 }
1354 }
1355 return iterator(__e);
1356}
1357
1358template <class _Tp, class _Alloc>
1359void
1360forward_list<_Tp, _Alloc>::resize(size_type __n)
1361{
1362 size_type __sz = 0;
1363 iterator __p = before_begin();
1364 iterator __i = begin();
1365 iterator __e = end();
1366 for (; __i != __e && __sz < __n; ++__p, ++__i, ++__sz)
1367 ;
1368 if (__i != __e)
1369 erase_after(__p, __e);
1370 else
1371 {
1372 __n -= __sz;
1373 if (__n > 0)
1374 {
1375 __node_allocator& __a = base::__alloc();
1376 typedef __allocator_destructor<__node_allocator> _Dp;
1377 unique_ptr<__node, _Dp> __h(nullptr, _Dp(__a, 1));
1378 for (__begin_node_pointer __ptr = __p.__get_begin(); __n > 0; --__n,
1379 __ptr = __ptr->__next_as_begin())
1380 {
1381 __h.reset(__node_traits::allocate(__a, 1));
1382 __node_traits::construct(__a, _VSTD::addressof(__h->__value_));
1383 __h->__next_ = nullptr;
1384 __ptr->__next_ = __h.release();
1385 }
1386 }
1387 }
1388}
1389
1390template <class _Tp, class _Alloc>
1391void
1392forward_list<_Tp, _Alloc>::resize(size_type __n, const value_type& __v)
1393{
1394 size_type __sz = 0;
1395 iterator __p = before_begin();
1396 iterator __i = begin();
1397 iterator __e = end();
1398 for (; __i != __e && __sz < __n; ++__p, ++__i, ++__sz)
1399 ;
1400 if (__i != __e)
1401 erase_after(__p, __e);
1402 else
1403 {
1404 __n -= __sz;
1405 if (__n > 0)
1406 {
1407 __node_allocator& __a = base::__alloc();
1408 typedef __allocator_destructor<__node_allocator> _Dp;
1409 unique_ptr<__node, _Dp> __h(nullptr, _Dp(__a, 1));
1410 for (__begin_node_pointer __ptr = __p.__get_begin(); __n > 0; --__n,
1411 __ptr = __ptr->__next_as_begin())
1412 {
1413 __h.reset(__node_traits::allocate(__a, 1));
1414 __node_traits::construct(__a, _VSTD::addressof(__h->__value_), __v);
1415 __h->__next_ = nullptr;
1416 __ptr->__next_ = __h.release();
1417 }
1418 }
1419 }
1420}
1421
1422template <class _Tp, class _Alloc>
1423void
1424forward_list<_Tp, _Alloc>::splice_after(const_iterator __p,
1425 forward_list& __x)
1426{
1427 if (!__x.empty())
1428 {
1429 if (__p.__get_begin()->__next_ != nullptr)
1430 {
1431 const_iterator __lm1 = __x.before_begin();
1432 while (__lm1.__get_begin()->__next_ != nullptr)
1433 ++__lm1;
1434 __lm1.__get_begin()->__next_ = __p.__get_begin()->__next_;
1435 }
1436 __p.__get_begin()->__next_ = __x.__before_begin()->__next_;
1437 __x.__before_begin()->__next_ = nullptr;
1438 }
1439}
1440
1441template <class _Tp, class _Alloc>
1442void
1443forward_list<_Tp, _Alloc>::splice_after(const_iterator __p,
1444 forward_list& /*__other*/,
1445 const_iterator __i)
1446{
1447 const_iterator __lm1 = _VSTD::next(__i);
1448 if (__p != __i && __p != __lm1)
1449 {
1450 __i.__get_begin()->__next_ = __lm1.__get_begin()->__next_;
1451 __lm1.__get_begin()->__next_ = __p.__get_begin()->__next_;
1452 __p.__get_begin()->__next_ = __lm1.__get_unsafe_node_pointer();
1453 }
1454}
1455
1456template <class _Tp, class _Alloc>
1457void
1458forward_list<_Tp, _Alloc>::splice_after(const_iterator __p,
1459 forward_list& /*__other*/,
1460 const_iterator __f, const_iterator __l)
1461{
1462 if (__f != __l && __p != __f)
1463 {
1464 const_iterator __lm1 = __f;
1465 while (__lm1.__get_begin()->__next_ != __l.__get_begin())
1466 ++__lm1;
1467 if (__f != __lm1)
1468 {
1469 __lm1.__get_begin()->__next_ = __p.__get_begin()->__next_;
1470 __p.__get_begin()->__next_ = __f.__get_begin()->__next_;
1471 __f.__get_begin()->__next_ = __l.__get_unsafe_node_pointer();
1472 }
1473 }
1474}
1475
1476template <class _Tp, class _Alloc>
1477inline _LIBCPP_INLINE_VISIBILITY
1478void
1479forward_list<_Tp, _Alloc>::splice_after(const_iterator __p,
1480 forward_list&& __x)
1481{
1482 splice_after(__p, __x);
1483}
1484
1485template <class _Tp, class _Alloc>
1486inline _LIBCPP_INLINE_VISIBILITY
1487void
1488forward_list<_Tp, _Alloc>::splice_after(const_iterator __p,
1489 forward_list&& __x,
1490 const_iterator __i)
1491{
1492 splice_after(__p, __x, __i);
1493}
1494
1495template <class _Tp, class _Alloc>
1496inline _LIBCPP_INLINE_VISIBILITY
1497void
1498forward_list<_Tp, _Alloc>::splice_after(const_iterator __p,
1499 forward_list&& __x,
1500 const_iterator __f, const_iterator __l)
1501{
1502 splice_after(__p, __x, __f, __l);
1503}
1504
1505template <class _Tp, class _Alloc>
1506typename forward_list<_Tp, _Alloc>::__remove_return_type
1507forward_list<_Tp, _Alloc>::remove(const value_type& __v)
1508{
1509 forward_list<_Tp, _Alloc> __deleted_nodes(get_allocator()); // collect the nodes we're removing
1510 typename forward_list<_Tp, _Alloc>::size_type __count_removed = 0;
1511 const iterator __e = end();
1512 for (iterator __i = before_begin(); __i.__get_begin()->__next_ != nullptr;)
1513 {
1514 if (__i.__get_begin()->__next_->__value_ == __v)
1515 {
1516 ++__count_removed;
1517 iterator __j = _VSTD::next(__i, 2);
1518 for (; __j != __e && *__j == __v; ++__j)
1519 ++__count_removed;
1520 __deleted_nodes.splice_after(__deleted_nodes.before_begin(), *this, __i, __j);
1521 if (__j == __e)
1522 break;
1523 __i = __j;
1524 }
1525 else
1526 ++__i;
1527 }
1528
1529 return (__remove_return_type) __count_removed;
1530}
1531
1532template <class _Tp, class _Alloc>
1533template <class _Predicate>
1534typename forward_list<_Tp, _Alloc>::__remove_return_type
1535forward_list<_Tp, _Alloc>::remove_if(_Predicate __pred)
1536{
1537 forward_list<_Tp, _Alloc> __deleted_nodes(get_allocator()); // collect the nodes we're removing
1538 typename forward_list<_Tp, _Alloc>::size_type __count_removed = 0;
1539 const iterator __e = end();
1540 for (iterator __i = before_begin(); __i.__get_begin()->__next_ != nullptr;)
1541 {
1542 if (__pred(__i.__get_begin()->__next_->__value_))
1543 {
1544 ++__count_removed;
1545 iterator __j = _VSTD::next(__i, 2);
1546 for (; __j != __e && __pred(*__j); ++__j)
1547 ++__count_removed;
1548 __deleted_nodes.splice_after(__deleted_nodes.before_begin(), *this, __i, __j);
1549 if (__j == __e)
1550 break;
1551 __i = __j;
1552 }
1553 else
1554 ++__i;
1555 }
1556
1557 return (__remove_return_type) __count_removed;
1558}
1559
1560template <class _Tp, class _Alloc>
1561template <class _BinaryPredicate>
1562typename forward_list<_Tp, _Alloc>::__remove_return_type
1563forward_list<_Tp, _Alloc>::unique(_BinaryPredicate __binary_pred)
1564{
1565 forward_list<_Tp, _Alloc> __deleted_nodes(get_allocator()); // collect the nodes we're removing
1566 typename forward_list<_Tp, _Alloc>::size_type __count_removed = 0;
1567 for (iterator __i = begin(), __e = end(); __i != __e;)
1568 {
1569 iterator __j = _VSTD::next(__i);
1570 for (; __j != __e && __binary_pred(*__i, *__j); ++__j)
1571 ++__count_removed;
1572 if (__i.__get_begin()->__next_ != __j.__get_unsafe_node_pointer())
1573 __deleted_nodes.splice_after(__deleted_nodes.before_begin(), *this, __i, __j);
1574 __i = __j;
1575 }
1576
1577 return (__remove_return_type) __count_removed;
1578}
1579
1580template <class _Tp, class _Alloc>
1581template <class _Compare>
1582void
1583forward_list<_Tp, _Alloc>::merge(forward_list& __x, _Compare __comp)
1584{
1585 if (this != &__x)
1586 {
1587 base::__before_begin()->__next_ = __merge(base::__before_begin()->__next_,
1588 __x.__before_begin()->__next_,
1589 __comp);
1590 __x.__before_begin()->__next_ = nullptr;
1591 }
1592}
1593
1594template <class _Tp, class _Alloc>
1595template <class _Compare>
1596typename forward_list<_Tp, _Alloc>::__node_pointer
1597forward_list<_Tp, _Alloc>::__merge(__node_pointer __f1, __node_pointer __f2,
1598 _Compare& __comp)
1599{
1600 if (__f1 == nullptr)
1601 return __f2;
1602 if (__f2 == nullptr)
1603 return __f1;
1604 __node_pointer __r;
1605 if (__comp(__f2->__value_, __f1->__value_))
1606 {
1607 __node_pointer __t = __f2;
1608 while (__t->__next_ != nullptr &&
1609 __comp(__t->__next_->__value_, __f1->__value_))
1610 __t = __t->__next_;
1611 __r = __f2;
1612 __f2 = __t->__next_;
1613 __t->__next_ = __f1;
1614 }
1615 else
1616 __r = __f1;
1617 __node_pointer __p = __f1;
1618 __f1 = __f1->__next_;
1619 while (__f1 != nullptr && __f2 != nullptr)
1620 {
1621 if (__comp(__f2->__value_, __f1->__value_))
1622 {
1623 __node_pointer __t = __f2;
1624 while (__t->__next_ != nullptr &&
1625 __comp(__t->__next_->__value_, __f1->__value_))
1626 __t = __t->__next_;
1627 __p->__next_ = __f2;
1628 __f2 = __t->__next_;
1629 __t->__next_ = __f1;
1630 }
1631 __p = __f1;
1632 __f1 = __f1->__next_;
1633 }
1634 if (__f2 != nullptr)
1635 __p->__next_ = __f2;
1636 return __r;
1637}
1638
1639template <class _Tp, class _Alloc>
1640template <class _Compare>
1641inline
1642void
1643forward_list<_Tp, _Alloc>::sort(_Compare __comp)
1644{
1645 base::__before_begin()->__next_ = __sort(base::__before_begin()->__next_,
1646 _VSTD::distance(begin(), end()), __comp);
1647}
1648
1649template <class _Tp, class _Alloc>
1650template <class _Compare>
1651typename forward_list<_Tp, _Alloc>::__node_pointer
1652forward_list<_Tp, _Alloc>::__sort(__node_pointer __f1, difference_type __sz,
1653 _Compare& __comp)
1654{
1655 switch (__sz)
1656 {
1657 case 0:
1658 case 1:
1659 return __f1;
1660 case 2:
1661 if (__comp(__f1->__next_->__value_, __f1->__value_))
1662 {
1663 __node_pointer __t = __f1->__next_;
1664 __t->__next_ = __f1;
1665 __f1->__next_ = nullptr;
1666 __f1 = __t;
1667 }
1668 return __f1;
1669 }
1670 difference_type __sz1 = __sz / 2;
1671 difference_type __sz2 = __sz - __sz1;
1672 __node_pointer __t = _VSTD::next(iterator(__f1), __sz1 - 1).__get_unsafe_node_pointer();
1673 __node_pointer __f2 = __t->__next_;
1674 __t->__next_ = nullptr;
1675 return __merge(__sort(__f1, __sz1, __comp),
1676 __sort(__f2, __sz2, __comp), __comp);
1677}
1678
1679template <class _Tp, class _Alloc>
1680void
1681forward_list<_Tp, _Alloc>::reverse() _NOEXCEPT
1682{
1683 __node_pointer __p = base::__before_begin()->__next_;
1684 if (__p != nullptr)
1685 {
1686 __node_pointer __f = __p->__next_;
1687 __p->__next_ = nullptr;
1688 while (__f != nullptr)
1689 {
1690 __node_pointer __t = __f->__next_;
1691 __f->__next_ = __p;
1692 __p = __f;
1693 __f = __t;
1694 }
1695 base::__before_begin()->__next_ = __p;
1696 }
1697}
1698
1699template <class _Tp, class _Alloc>
1700bool operator==(const forward_list<_Tp, _Alloc>& __x,
1701 const forward_list<_Tp, _Alloc>& __y)
1702{
1703 typedef forward_list<_Tp, _Alloc> _Cp;
1704 typedef typename _Cp::const_iterator _Ip;
1705 _Ip __ix = __x.begin();
1706 _Ip __ex = __x.end();
1707 _Ip __iy = __y.begin();
1708 _Ip __ey = __y.end();
1709 for (; __ix != __ex && __iy != __ey; ++__ix, ++__iy)
1710 if (!(*__ix == *__iy))
1711 return false;
1712 return (__ix == __ex) == (__iy == __ey);
1713}
1714
1715template <class _Tp, class _Alloc>
1716inline _LIBCPP_INLINE_VISIBILITY
1717bool operator!=(const forward_list<_Tp, _Alloc>& __x,
1718 const forward_list<_Tp, _Alloc>& __y)
1719{
1720 return !(__x == __y);
1721}
1722
1723template <class _Tp, class _Alloc>
1724inline _LIBCPP_INLINE_VISIBILITY
1725bool operator< (const forward_list<_Tp, _Alloc>& __x,
1726 const forward_list<_Tp, _Alloc>& __y)
1727{
1728 return _VSTD::lexicographical_compare(__x.begin(), __x.end(),
1729 __y.begin(), __y.end());
1730}
1731
1732template <class _Tp, class _Alloc>
1733inline _LIBCPP_INLINE_VISIBILITY
1734bool operator> (const forward_list<_Tp, _Alloc>& __x,
1735 const forward_list<_Tp, _Alloc>& __y)
1736{
1737 return __y < __x;
1738}
1739
1740template <class _Tp, class _Alloc>
1741inline _LIBCPP_INLINE_VISIBILITY
1742bool operator>=(const forward_list<_Tp, _Alloc>& __x,
1743 const forward_list<_Tp, _Alloc>& __y)
1744{
1745 return !(__x < __y);
1746}
1747
1748template <class _Tp, class _Alloc>
1749inline _LIBCPP_INLINE_VISIBILITY
1750bool operator<=(const forward_list<_Tp, _Alloc>& __x,
1751 const forward_list<_Tp, _Alloc>& __y)
1752{
1753 return !(__y < __x);
1754}
1755
1756template <class _Tp, class _Alloc>
1757inline _LIBCPP_INLINE_VISIBILITY
1758void
1759swap(forward_list<_Tp, _Alloc>& __x, forward_list<_Tp, _Alloc>& __y)
1760 _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y)))
1761{
1762 __x.swap(__y);
1763}
1764
1765#if _LIBCPP_STD_VER > 17
1766template <class _Tp, class _Allocator, class _Predicate>
1767inline _LIBCPP_INLINE_VISIBILITY
1768void erase_if(forward_list<_Tp, _Allocator>& __c, _Predicate __pred)
1769{ __c.remove_if(__pred); }
1770
1771template <class _Tp, class _Allocator, class _Up>
1772inline _LIBCPP_INLINE_VISIBILITY
1773void erase(forward_list<_Tp, _Allocator>& __c, const _Up& __v)
1774{ _VSTD::erase_if(__c, [&](auto& __elem) { return __elem == __v; }); }
1775#endif
1776
1777_LIBCPP_END_NAMESPACE_STD
1778
1779_LIBCPP_POP_MACROS
1780
1781#endif // _LIBCPP_FORWARD_LIST
1782