Debian Codegraph @

libcxx/include/__cxx03/forward_list

raw
1 // -*- C++ -*-
2 //===----------------------------------------------------------------------===//
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___CXX03_FORWARD_LIST
11 #define _LIBCPP___CXX03_FORWARD_LIST
12
13 /*
14 forward_list synopsis
15
16 namespace std
17 {
18
19 template <class T, class Allocator = allocator<T>>
20 class forward_list
21 {
22 public:
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 template<container-compatible-range<T> R>
48 forward_list(from_range_t, R&& rg, const Allocator& = Allocator()); // C++23
49 forward_list(const forward_list& x);
50 forward_list(const forward_list& x, const allocator_type& a);
51 forward_list(forward_list&& x)
52 noexcept(is_nothrow_move_constructible<allocator_type>::value);
53 forward_list(forward_list&& x, const allocator_type& a);
54 forward_list(initializer_list<value_type> il);
55 forward_list(initializer_list<value_type> il, const allocator_type& a);
56
57 ~forward_list();
58
59 forward_list& operator=(const forward_list& x);
60 forward_list& operator=(forward_list&& x)
61 noexcept(
62 allocator_type::propagate_on_container_move_assignment::value &&
63 is_nothrow_move_assignable<allocator_type>::value);
64 forward_list& operator=(initializer_list<value_type> il);
65
66 template <class InputIterator>
67 void assign(InputIterator first, InputIterator last);
68 template<container-compatible-range<T> R>
69 void assign_range(R&& rg); // C++23
70 void assign(size_type n, const value_type& v);
71 void assign(initializer_list<value_type> il);
72
73 allocator_type get_allocator() const noexcept;
74
75 iterator begin() noexcept;
76 const_iterator begin() const noexcept;
77 iterator end() noexcept;
78 const_iterator end() const noexcept;
79
80 const_iterator cbegin() const noexcept;
81 const_iterator cend() const noexcept;
82
83 iterator before_begin() noexcept;
84 const_iterator before_begin() const noexcept;
85 const_iterator cbefore_begin() const noexcept;
86
87 bool empty() const noexcept;
88 size_type max_size() const noexcept;
89
90 reference front();
91 const_reference front() const;
92
93 template <class... Args> reference emplace_front(Args&&... args); // reference in C++17
94 void push_front(const value_type& v);
95 void push_front(value_type&& v);
96 template<container-compatible-range<T> R>
97 void prepend_range(R&& rg); // C++23
98
99 void pop_front();
100
101 template <class... Args>
102 iterator emplace_after(const_iterator p, Args&&... args);
103 iterator insert_after(const_iterator p, const value_type& v);
104 iterator insert_after(const_iterator p, value_type&& v);
105 iterator insert_after(const_iterator p, size_type n, const value_type& v);
106 template <class InputIterator>
107 iterator insert_after(const_iterator p,
108 InputIterator first, InputIterator last);
109 template<container-compatible-range<T> R>
110 iterator insert_range_after(const_iterator position, R&& rg); // C++23
111 iterator insert_after(const_iterator p, initializer_list<value_type> il);
112
113 iterator erase_after(const_iterator p);
114 iterator erase_after(const_iterator first, const_iterator last);
115
116 void swap(forward_list& x)
117 noexcept(allocator_traits<allocator_type>::is_always_equal::value); // C++17
118
119 void resize(size_type n);
120 void resize(size_type n, const value_type& v);
121 void clear() noexcept;
122
123 void splice_after(const_iterator p, forward_list& x);
124 void splice_after(const_iterator p, forward_list&& x);
125 void splice_after(const_iterator p, forward_list& x, const_iterator i);
126 void splice_after(const_iterator p, forward_list&& x, const_iterator i);
127 void splice_after(const_iterator p, forward_list& x,
128 const_iterator first, const_iterator last);
129 void splice_after(const_iterator p, forward_list&& x,
130 const_iterator first, const_iterator last);
131 size_type remove(const value_type& v); // void before C++20
132 template <class Predicate>
133 size_type remove_if(Predicate pred); // void before C++20
134 size_type unique(); // void before C++20
135 template <class BinaryPredicate>
136 size_type unique(BinaryPredicate binary_pred); // void before C++20
137 void merge(forward_list& x);
138 void merge(forward_list&& x);
139 template <class Compare> void merge(forward_list& x, Compare comp);
140 template <class Compare> void merge(forward_list&& x, Compare comp);
141 void sort();
142 template <class Compare> void sort(Compare comp);
143 void reverse() noexcept;
144 };
145
146
147 template <class InputIterator, class Allocator = allocator<typename iterator_traits<InputIterator>::value_type>>
148 forward_list(InputIterator, InputIterator, Allocator = Allocator())
149 -> forward_list<typename iterator_traits<InputIterator>::value_type, Allocator>; // C++17
150
151 template<ranges::input_range R, class Allocator = allocator<ranges::range_value_t<R>>>
152 forward_list(from_range_t, R&&, Allocator = Allocator())
153 -> forward_list<ranges::range_value_t<R>, Allocator>; // C++23
154
155 template <class T, class Allocator>
156 bool operator==(const forward_list<T, Allocator>& x,
157 const forward_list<T, Allocator>& y);
158
159 template <class T, class Allocator>
160 bool operator< (const forward_list<T, Allocator>& x,
161 const forward_list<T, Allocator>& y); // removed in C++20
162
163 template <class T, class Allocator>
164 bool operator!=(const forward_list<T, Allocator>& x,
165 const forward_list<T, Allocator>& y); // removed in C++20
166
167 template <class T, class Allocator>
168 bool operator> (const forward_list<T, Allocator>& x,
169 const forward_list<T, Allocator>& y); // removed in C++20
170
171 template <class T, class Allocator>
172 bool operator>=(const forward_list<T, Allocator>& x,
173 const forward_list<T, Allocator>& y); // removed in C++20
174
175 template <class T, class Allocator>
176 bool operator<=(const forward_list<T, Allocator>& x,
177 const forward_list<T, Allocator>& y); // removed in C++20
178
179 template<class T, class Allocator>
180 synth-three-way-result<T> operator<=>(const forward_list<T, Allocator>& x,
181 const forward_list<T, Allocator>& y); // since C++20
182
183 template <class T, class Allocator>
184 void swap(forward_list<T, Allocator>& x, forward_list<T, Allocator>& y)
185 noexcept(noexcept(x.swap(y)));
186
187 template <class T, class Allocator, class U>
188 typename forward_list<T, Allocator>::size_type
189 erase(forward_list<T, Allocator>& c, const U& value); // C++20
190 template <class T, class Allocator, class Predicate>
191 typename forward_list<T, Allocator>::size_type
192 erase_if(forward_list<T, Allocator>& c, Predicate pred); // C++20
193
194 } // std
195
196 */
197
198 #include <__cxx03/__algorithm/comp.h>
199 #include <__cxx03/__algorithm/lexicographical_compare.h>
200 #include <__cxx03/__algorithm/min.h>
201 #include <__cxx03/__config>
202 #include <__cxx03/__iterator/distance.h>
203 #include <__cxx03/__iterator/iterator_traits.h>
204 #include <__cxx03/__iterator/move_iterator.h>
205 #include <__cxx03/__iterator/next.h>
206 #include <__cxx03/__memory/addressof.h>
207 #include <__cxx03/__memory/allocation_guard.h>
208 #include <__cxx03/__memory/allocator.h>
209 #include <__cxx03/__memory/allocator_traits.h>
210 #include <__cxx03/__memory/compressed_pair.h>
211 #include <__cxx03/__memory/construct_at.h>
212 #include <__cxx03/__memory/pointer_traits.h>
213 #include <__cxx03/__memory/swap_allocator.h>
214 #include <__cxx03/__type_traits/conditional.h>
215 #include <__cxx03/__type_traits/is_allocator.h>
216 #include <__cxx03/__type_traits/is_const.h>
217 #include <__cxx03/__type_traits/is_nothrow_assignable.h>
218 #include <__cxx03/__type_traits/is_nothrow_constructible.h>
219 #include <__cxx03/__type_traits/is_pointer.h>
220 #include <__cxx03/__type_traits/is_same.h>
221 #include <__cxx03/__type_traits/is_swappable.h>
222 #include <__cxx03/__type_traits/type_identity.h>
223 #include <__cxx03/__utility/forward.h>
224 #include <__cxx03/__utility/move.h>
225 #include <__cxx03/limits>
226 #include <__cxx03/new> // __launder
227 #include <__cxx03/version>
228
229 // standard-mandated includes
230
231 // [iterator.range]
232 #include <__cxx03/__iterator/access.h>
233
234 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
235 # pragma GCC system_header
236 #endif
237
238 _LIBCPP_PUSH_MACROS
239 #include <__cxx03/__undef_macros>
240
241 _LIBCPP_BEGIN_NAMESPACE_STD
242
243 template <class _Tp, class _VoidPtr>
244 struct __forward_list_node;
245 template <class _NodePtr>
246 struct __forward_begin_node;
247
248 template <class>
249 struct __forward_list_node_value_type;
250
251 template <class _Tp, class _VoidPtr>
252 struct __forward_list_node_value_type<__forward_list_node<_Tp, _VoidPtr> > {
253 typedef _Tp type;
254 };
255
256 template <class _NodePtr>
257 struct __forward_node_traits {
258 typedef __remove_cv_t<typename pointer_traits<_NodePtr>::element_type> __node_type;
259 typedef typename __forward_list_node_value_type<__node_type>::type __node_value_type;
260 typedef _NodePtr __node_pointer;
261 typedef __forward_begin_node<_NodePtr> __begin_node;
262 typedef __rebind_pointer_t<_NodePtr, __begin_node> __begin_node_pointer;
263 typedef __rebind_pointer_t<_NodePtr, void> __void_pointer;
264
265 #if defined(_LIBCPP_ABI_FORWARD_LIST_REMOVE_NODE_POINTER_UB)
266 typedef __begin_node_pointer __iter_node_pointer;
267 #else
268 typedef __conditional_t<is_pointer<__void_pointer>::value, __begin_node_pointer, __node_pointer> __iter_node_pointer;
269 #endif
270
271 typedef __conditional_t<is_same<__iter_node_pointer, __node_pointer>::value, __begin_node_pointer, __node_pointer>
272 __non_iter_node_pointer;
273
274 _LIBCPP_HIDE_FROM_ABI static __iter_node_pointer __as_iter_node(__iter_node_pointer __p) { return __p; }
275 _LIBCPP_HIDE_FROM_ABI static __iter_node_pointer __as_iter_node(__non_iter_node_pointer __p) {
276 return static_cast<__iter_node_pointer>(static_cast<__void_pointer>(__p));
277 }
278 };
279
280 template <class _NodePtr>
281 struct __forward_begin_node {
282 typedef _NodePtr pointer;
283 typedef __rebind_pointer_t<_NodePtr, __forward_begin_node> __begin_node_pointer;
284
285 pointer __next_;
286
287 _LIBCPP_HIDE_FROM_ABI __forward_begin_node() : __next_(nullptr) {}
288 _LIBCPP_HIDE_FROM_ABI explicit __forward_begin_node(pointer __n) : __next_(__n) {}
289
290 _LIBCPP_HIDE_FROM_ABI __begin_node_pointer __next_as_begin() const {
291 return static_cast<__begin_node_pointer>(__next_);
292 }
293 };
294
295 template <class _Tp, class _VoidPtr>
296 using __begin_node_of = __forward_begin_node<__rebind_pointer_t<_VoidPtr, __forward_list_node<_Tp, _VoidPtr> > >;
297
298 template <class _Tp, class _VoidPtr>
299 struct __forward_list_node : public __begin_node_of<_Tp, _VoidPtr> {
300 typedef _Tp value_type;
301 typedef __begin_node_of<_Tp, _VoidPtr> _Base;
302 typedef typename _Base::pointer _NodePtr;
303
304 // We allow starting the lifetime of nodes without initializing the value held by the node,
305 // since that is handled by the list itself in order to be allocator-aware.
306
307 private:
308 _ALIGNAS_TYPE(_Tp) char __buffer_[sizeof(_Tp)];
309
310 public:
311 _LIBCPP_HIDE_FROM_ABI _Tp& __get_value() { return *std::__launder(reinterpret_cast<_Tp*>(&__buffer_)); }
312
313 _LIBCPP_HIDE_FROM_ABI explicit __forward_list_node(_NodePtr __next) : _Base(__next) {}
314 _LIBCPP_HIDE_FROM_ABI ~__forward_list_node() {}
315 };
316
317 template <class _Tp, class _Alloc = allocator<_Tp> >
318 class _LIBCPP_TEMPLATE_VIS forward_list;
319 template <class _NodeConstPtr>
320 class _LIBCPP_TEMPLATE_VIS __forward_list_const_iterator;
321
322 template <class _NodePtr>
323 class _LIBCPP_TEMPLATE_VIS __forward_list_iterator {
324 typedef __forward_node_traits<_NodePtr> __traits;
325 typedef typename __traits::__node_pointer __node_pointer;
326 typedef typename __traits::__begin_node_pointer __begin_node_pointer;
327 typedef typename __traits::__iter_node_pointer __iter_node_pointer;
328 typedef typename __traits::__void_pointer __void_pointer;
329
330 __iter_node_pointer __ptr_;
331
332 _LIBCPP_HIDE_FROM_ABI __begin_node_pointer __get_begin() const {
333 return static_cast<__begin_node_pointer>(static_cast<__void_pointer>(__ptr_));
334 }
335 _LIBCPP_HIDE_FROM_ABI __node_pointer __get_unsafe_node_pointer() const {
336 return static_cast<__node_pointer>(static_cast<__void_pointer>(__ptr_));
337 }
338
339 _LIBCPP_HIDE_FROM_ABI explicit __forward_list_iterator(nullptr_t) _NOEXCEPT : __ptr_(nullptr) {}
340
341 _LIBCPP_HIDE_FROM_ABI explicit __forward_list_iterator(__begin_node_pointer __p) _NOEXCEPT
342 : __ptr_(__traits::__as_iter_node(__p)) {}
343
344 _LIBCPP_HIDE_FROM_ABI explicit __forward_list_iterator(__node_pointer __p) _NOEXCEPT
345 : __ptr_(__traits::__as_iter_node(__p)) {}
346
347 template <class, class>
348 friend class _LIBCPP_TEMPLATE_VIS forward_list;
349 template <class>
350 friend class _LIBCPP_TEMPLATE_VIS __forward_list_const_iterator;
351
352 public:
353 typedef forward_iterator_tag iterator_category;
354 typedef typename __traits::__node_value_type value_type;
355 typedef value_type& reference;
356 typedef typename pointer_traits<__node_pointer>::difference_type difference_type;
357 typedef __rebind_pointer_t<__node_pointer, value_type> pointer;
358
359 _LIBCPP_HIDE_FROM_ABI __forward_list_iterator() _NOEXCEPT : __ptr_(nullptr) {}
360
361 _LIBCPP_HIDE_FROM_ABI reference operator*() const { return __get_unsafe_node_pointer()->__get_value(); }
362 _LIBCPP_HIDE_FROM_ABI pointer operator->() const {
363 return pointer_traits<pointer>::pointer_to(__get_unsafe_node_pointer()->__get_value());
364 }
365
366 _LIBCPP_HIDE_FROM_ABI __forward_list_iterator& operator++() {
367 __ptr_ = __traits::__as_iter_node(__ptr_->__next_);
368 return *this;
369 }
370 _LIBCPP_HIDE_FROM_ABI __forward_list_iterator operator++(int) {
371 __forward_list_iterator __t(*this);
372 ++(*this);
373 return __t;
374 }
375
376 friend _LIBCPP_HIDE_FROM_ABI bool operator==(const __forward_list_iterator& __x, const __forward_list_iterator& __y) {
377 return __x.__ptr_ == __y.__ptr_;
378 }
379 friend _LIBCPP_HIDE_FROM_ABI bool operator!=(const __forward_list_iterator& __x, const __forward_list_iterator& __y) {
380 return !(__x == __y);
381 }
382 };
383
384 template <class _NodeConstPtr>
385 class _LIBCPP_TEMPLATE_VIS __forward_list_const_iterator {
386 static_assert(!is_const<typename pointer_traits<_NodeConstPtr>::element_type>::value, "");
387 typedef _NodeConstPtr _NodePtr;
388
389 typedef __forward_node_traits<_NodePtr> __traits;
390 typedef typename __traits::__node_type __node_type;
391 typedef typename __traits::__node_pointer __node_pointer;
392 typedef typename __traits::__begin_node_pointer __begin_node_pointer;
393 typedef typename __traits::__iter_node_pointer __iter_node_pointer;
394 typedef typename __traits::__void_pointer __void_pointer;
395
396 __iter_node_pointer __ptr_;
397
398 _LIBCPP_HIDE_FROM_ABI __begin_node_pointer __get_begin() const {
399 return static_cast<__begin_node_pointer>(static_cast<__void_pointer>(__ptr_));
400 }
401 _LIBCPP_HIDE_FROM_ABI __node_pointer __get_unsafe_node_pointer() const {
402 return static_cast<__node_pointer>(static_cast<__void_pointer>(__ptr_));
403 }
404
405 _LIBCPP_HIDE_FROM_ABI explicit __forward_list_const_iterator(nullptr_t) _NOEXCEPT : __ptr_(nullptr) {}
406
407 _LIBCPP_HIDE_FROM_ABI explicit __forward_list_const_iterator(__begin_node_pointer __p) _NOEXCEPT
408 : __ptr_(__traits::__as_iter_node(__p)) {}
409
410 _LIBCPP_HIDE_FROM_ABI explicit __forward_list_const_iterator(__node_pointer __p) _NOEXCEPT
411 : __ptr_(__traits::__as_iter_node(__p)) {}
412
413 template <class, class>
414 friend class forward_list;
415
416 public:
417 typedef forward_iterator_tag iterator_category;
418 typedef typename __traits::__node_value_type value_type;
419 typedef const value_type& reference;
420 typedef typename pointer_traits<__node_pointer>::difference_type difference_type;
421 typedef __rebind_pointer_t<__node_pointer, const value_type> pointer;
422
423 _LIBCPP_HIDE_FROM_ABI __forward_list_const_iterator() _NOEXCEPT : __ptr_(nullptr) {}
424 _LIBCPP_HIDE_FROM_ABI __forward_list_const_iterator(__forward_list_iterator<__node_pointer> __p) _NOEXCEPT
425 : __ptr_(__p.__ptr_) {}
426
427 _LIBCPP_HIDE_FROM_ABI reference operator*() const { return __get_unsafe_node_pointer()->__get_value(); }
428 _LIBCPP_HIDE_FROM_ABI pointer operator->() const {
429 return pointer_traits<pointer>::pointer_to(__get_unsafe_node_pointer()->__get_value());
430 }
431
432 _LIBCPP_HIDE_FROM_ABI __forward_list_const_iterator& operator++() {
433 __ptr_ = __traits::__as_iter_node(__ptr_->__next_);
434 return *this;
435 }
436 _LIBCPP_HIDE_FROM_ABI __forward_list_const_iterator operator++(int) {
437 __forward_list_const_iterator __t(*this);
438 ++(*this);
439 return __t;
440 }
441
442 friend _LIBCPP_HIDE_FROM_ABI bool
443 operator==(const __forward_list_const_iterator& __x, const __forward_list_const_iterator& __y) {
444 return __x.__ptr_ == __y.__ptr_;
445 }
446 friend _LIBCPP_HIDE_FROM_ABI bool
447 operator!=(const __forward_list_const_iterator& __x, const __forward_list_const_iterator& __y) {
448 return !(__x == __y);
449 }
450 };
451
452 template <class _Tp, class _Alloc>
453 class __forward_list_base {
454 protected:
455 typedef _Tp value_type;
456 typedef _Alloc allocator_type;
457
458 typedef typename allocator_traits<allocator_type>::void_pointer void_pointer;
459 typedef __forward_list_node<value_type, void_pointer> __node_type;
460 typedef __begin_node_of<value_type, void_pointer> __begin_node;
461 typedef __rebind_alloc<allocator_traits<allocator_type>, __node_type> __node_allocator;
462 typedef allocator_traits<__node_allocator> __node_traits;
463 typedef typename __node_traits::pointer __node_pointer;
464
465 typedef __rebind_alloc<allocator_traits<allocator_type>, __begin_node> __begin_node_allocator;
466 typedef typename allocator_traits<__begin_node_allocator>::pointer __begin_node_pointer;
467
468 __compressed_pair<__begin_node, __node_allocator> __before_begin_;
469
470 _LIBCPP_HIDE_FROM_ABI __begin_node_pointer __before_begin() _NOEXCEPT {
471 return pointer_traits<__begin_node_pointer>::pointer_to(__before_begin_.first());
472 }
473 _LIBCPP_HIDE_FROM_ABI __begin_node_pointer __before_begin() const _NOEXCEPT {
474 return pointer_traits<__begin_node_pointer>::pointer_to(const_cast<__begin_node&>(__before_begin_.first()));
475 }
476
477 _LIBCPP_HIDE_FROM_ABI __node_allocator& __alloc() _NOEXCEPT { return __before_begin_.second(); }
478 _LIBCPP_HIDE_FROM_ABI const __node_allocator& __alloc() const _NOEXCEPT { return __before_begin_.second(); }
479
480 typedef __forward_list_iterator<__node_pointer> iterator;
481 typedef __forward_list_const_iterator<__node_pointer> const_iterator;
482
483 _LIBCPP_HIDE_FROM_ABI __forward_list_base() : __before_begin_(__begin_node(), __default_init_tag()) {}
484 _LIBCPP_HIDE_FROM_ABI explicit __forward_list_base(const allocator_type& __a)
485 : __before_begin_(__begin_node(), __node_allocator(__a)) {}
486 _LIBCPP_HIDE_FROM_ABI explicit __forward_list_base(const __node_allocator& __a)
487 : __before_begin_(__begin_node(), __a) {}
488
489 public:
490 __forward_list_base(const __forward_list_base&) = delete;
491 __forward_list_base& operator=(const __forward_list_base&) = delete;
492
493 _LIBCPP_HIDE_FROM_ABI ~__forward_list_base();
494
495 protected:
496 _LIBCPP_HIDE_FROM_ABI void __copy_assign_alloc(const __forward_list_base& __x) {
497 __copy_assign_alloc(__x, integral_constant<bool, __node_traits::propagate_on_container_copy_assignment::value>());
498 }
499
500 _LIBCPP_HIDE_FROM_ABI void __move_assign_alloc(__forward_list_base& __x) {
501 __move_assign_alloc(__x, integral_constant<bool, __node_traits::propagate_on_container_move_assignment::value>());
502 }
503
504 template <class... _Args>
505 _LIBCPP_HIDE_FROM_ABI __node_pointer __create_node(__node_pointer __next, _Args&&... __args) {
506 __node_allocator& __a = __alloc();
507 __allocation_guard<__node_allocator> __guard(__a, 1);
508 // Begin the lifetime of the node itself. Note that this doesn't begin the lifetime of the value
509 // held inside the node, since we need to use the allocator's construct() method for that.
510 //
511 // We don't use the allocator's construct() method to construct the node itself since the
512 // Cpp17FooInsertable named requirements don't require the allocator's construct() method
513 // to work on anything other than the value_type.
514 std::__construct_at(std::addressof(*__guard.__get()), __next);
515
516 // Now construct the value_type using the allocator's construct() method.
517 __node_traits::construct(__a, std::addressof(__guard.__get()->__get_value()), std::forward<_Args>(__args)...);
518 return __guard.__release_ptr();
519 }
520
521 _LIBCPP_HIDE_FROM_ABI void __delete_node(__node_pointer __node) {
522 // For the same reason as above, we use the allocator's destroy() method for the value_type,
523 // but not for the node itself.
524 __node_allocator& __a = __alloc();
525 __node_traits::destroy(__a, std::addressof(__node->__get_value()));
526 std::__destroy_at(std::addressof(*__node));
527 __node_traits::deallocate(__a, __node, 1);
528 }
529
530 public:
531 _LIBCPP_HIDE_FROM_ABI void swap(__forward_list_base& __x);
532
533 protected:
534 _LIBCPP_HIDE_FROM_ABI void clear() _NOEXCEPT;
535
536 private:
537 _LIBCPP_HIDE_FROM_ABI void __copy_assign_alloc(const __forward_list_base&, false_type) {}
538 _LIBCPP_HIDE_FROM_ABI void __copy_assign_alloc(const __forward_list_base& __x, true_type) {
539 if (__alloc() != __x.__alloc())
540 clear();
541 __alloc() = __x.__alloc();
542 }
543
544 _LIBCPP_HIDE_FROM_ABI void __move_assign_alloc(__forward_list_base&, false_type) _NOEXCEPT {}
545 _LIBCPP_HIDE_FROM_ABI void __move_assign_alloc(__forward_list_base& __x, true_type) {
546 __alloc() = std::move(__x.__alloc());
547 }
548 };
549
550 template <class _Tp, class _Alloc>
551 __forward_list_base<_Tp, _Alloc>::~__forward_list_base() {
552 clear();
553 }
554
555 template <class _Tp, class _Alloc>
556 inline void __forward_list_base<_Tp, _Alloc>::swap(__forward_list_base& __x) {
557 std::__swap_allocator(
558 __alloc(), __x.__alloc(), integral_constant<bool, __node_traits::propagate_on_container_swap::value>());
559 using std::swap;
560 swap(__before_begin()->__next_, __x.__before_begin()->__next_);
561 }
562
563 template <class _Tp, class _Alloc>
564 void __forward_list_base<_Tp, _Alloc>::clear() _NOEXCEPT {
565 for (__node_pointer __p = __before_begin()->__next_; __p != nullptr;) {
566 __node_pointer __next = __p->__next_;
567 __delete_node(__p);
568 __p = __next;
569 }
570 __before_begin()->__next_ = nullptr;
571 }
572
573 template <class _Tp, class _Alloc /*= allocator<_Tp>*/>
574 class _LIBCPP_TEMPLATE_VIS forward_list : private __forward_list_base<_Tp, _Alloc> {
575 typedef __forward_list_base<_Tp, _Alloc> __base;
576 typedef typename __base::__node_allocator __node_allocator;
577 typedef typename __base::__node_type __node_type;
578 typedef typename __base::__node_traits __node_traits;
579 typedef typename __base::__node_pointer __node_pointer;
580 typedef typename __base::__begin_node_pointer __begin_node_pointer;
581
582 public:
583 typedef _Tp value_type;
584 typedef _Alloc allocator_type;
585
586 static_assert(__check_valid_allocator<allocator_type>::value, "");
587
588 static_assert(is_same<value_type, typename allocator_type::value_type>::value,
589 "Allocator::value_type must be same type as value_type");
590
591 static_assert(!is_same<allocator_type, __node_allocator>::value,
592 "internal allocator type must differ from user-specified type; otherwise overload resolution breaks");
593
594 typedef value_type& reference;
595 typedef const value_type& const_reference;
596 typedef typename allocator_traits<allocator_type>::pointer pointer;
597 typedef typename allocator_traits<allocator_type>::const_pointer const_pointer;
598 typedef typename allocator_traits<allocator_type>::size_type size_type;
599 typedef typename allocator_traits<allocator_type>::difference_type difference_type;
600
601 typedef typename __base::iterator iterator;
602 typedef typename __base::const_iterator const_iterator;
603 typedef void __remove_return_type;
604
605 _LIBCPP_HIDE_FROM_ABI forward_list() {} // = default;
606 _LIBCPP_HIDE_FROM_ABI explicit forward_list(const allocator_type& __a);
607 _LIBCPP_HIDE_FROM_ABI explicit forward_list(size_type __n);
608 _LIBCPP_HIDE_FROM_ABI forward_list(size_type __n, const value_type& __v);
609
610 template <__enable_if_t<__is_allocator<_Alloc>::value, int> = 0>
611 _LIBCPP_HIDE_FROM_ABI forward_list(size_type __n, const value_type& __v, const allocator_type& __a) : __base(__a) {
612 insert_after(cbefore_begin(), __n, __v);
613 }
614
615 template <class _InputIterator, __enable_if_t<__has_input_iterator_category<_InputIterator>::value, int> = 0>
616 _LIBCPP_HIDE_FROM_ABI forward_list(_InputIterator __f, _InputIterator __l);
617
618 template <class _InputIterator, __enable_if_t<__has_input_iterator_category<_InputIterator>::value, int> = 0>
619 _LIBCPP_HIDE_FROM_ABI forward_list(_InputIterator __f, _InputIterator __l, const allocator_type& __a);
620
621 _LIBCPP_HIDE_FROM_ABI forward_list(const forward_list& __x);
622 _LIBCPP_HIDE_FROM_ABI forward_list(const forward_list& __x, const __type_identity_t<allocator_type>& __a);
623
624 _LIBCPP_HIDE_FROM_ABI forward_list& operator=(const forward_list& __x);
625
626 // ~forward_list() = default;
627
628 template <class _InputIterator, __enable_if_t<__has_input_iterator_category<_InputIterator>::value, int> = 0>
629 void _LIBCPP_HIDE_FROM_ABI assign(_InputIterator __f, _InputIterator __l);
630
631 _LIBCPP_HIDE_FROM_ABI void assign(size_type __n, const value_type& __v);
632
633 _LIBCPP_HIDE_FROM_ABI allocator_type get_allocator() const _NOEXCEPT { return allocator_type(__base::__alloc()); }
634
635 _LIBCPP_HIDE_FROM_ABI iterator begin() _NOEXCEPT { return iterator(__base::__before_begin()->__next_); }
636 _LIBCPP_HIDE_FROM_ABI const_iterator begin() const _NOEXCEPT {
637 return const_iterator(__base::__before_begin()->__next_);
638 }
639 _LIBCPP_HIDE_FROM_ABI iterator end() _NOEXCEPT { return iterator(nullptr); }
640 _LIBCPP_HIDE_FROM_ABI const_iterator end() const _NOEXCEPT { return const_iterator(nullptr); }
641
642 _LIBCPP_HIDE_FROM_ABI const_iterator cbegin() const _NOEXCEPT {
643 return const_iterator(__base::__before_begin()->__next_);
644 }
645 _LIBCPP_HIDE_FROM_ABI const_iterator cend() const _NOEXCEPT { return const_iterator(nullptr); }
646
647 _LIBCPP_HIDE_FROM_ABI iterator before_begin() _NOEXCEPT { return iterator(__base::__before_begin()); }
648 _LIBCPP_HIDE_FROM_ABI const_iterator before_begin() const _NOEXCEPT {
649 return const_iterator(__base::__before_begin());
650 }
651 _LIBCPP_HIDE_FROM_ABI const_iterator cbefore_begin() const _NOEXCEPT {
652 return const_iterator(__base::__before_begin());
653 }
654
655 _LIBCPP_NODISCARD _LIBCPP_HIDE_FROM_ABI bool empty() const _NOEXCEPT {
656 return __base::__before_begin()->__next_ == nullptr;
657 }
658 _LIBCPP_HIDE_FROM_ABI size_type max_size() const _NOEXCEPT {
659 return std::min<size_type>(__node_traits::max_size(__base::__alloc()), numeric_limits<difference_type>::max());
660 }
661
662 _LIBCPP_HIDE_FROM_ABI reference front() { return __base::__before_begin()->__next_->__get_value(); }
663 _LIBCPP_HIDE_FROM_ABI const_reference front() const { return __base::__before_begin()->__next_->__get_value(); }
664
665 _LIBCPP_HIDE_FROM_ABI void push_front(const value_type& __v);
666
667 _LIBCPP_HIDE_FROM_ABI void pop_front();
668
669 _LIBCPP_HIDE_FROM_ABI iterator insert_after(const_iterator __p, const value_type& __v);
670 _LIBCPP_HIDE_FROM_ABI iterator insert_after(const_iterator __p, size_type __n, const value_type& __v);
671 template <class _InputIterator, __enable_if_t<__has_input_iterator_category<_InputIterator>::value, int> = 0>
672 _LIBCPP_HIDE_FROM_ABI iterator insert_after(const_iterator __p, _InputIterator __f, _InputIterator __l);
673
674 template <class _InputIterator, class _Sentinel>
675 _LIBCPP_HIDE_FROM_ABI iterator __insert_after_with_sentinel(const_iterator __p, _InputIterator __f, _Sentinel __l);
676
677 _LIBCPP_HIDE_FROM_ABI iterator erase_after(const_iterator __p);
678 _LIBCPP_HIDE_FROM_ABI iterator erase_after(const_iterator __f, const_iterator __l);
679
680 _LIBCPP_HIDE_FROM_ABI void swap(forward_list& __x) { __base::swap(__x); }
681
682 _LIBCPP_HIDE_FROM_ABI void resize(size_type __n);
683 _LIBCPP_HIDE_FROM_ABI void resize(size_type __n, const value_type& __v);
684 _LIBCPP_HIDE_FROM_ABI void clear() _NOEXCEPT { __base::clear(); }
685
686 _LIBCPP_HIDE_FROM_ABI void splice_after(const_iterator __p, forward_list&& __x);
687 _LIBCPP_HIDE_FROM_ABI void splice_after(const_iterator __p, forward_list&& __x, const_iterator __i);
688 _LIBCPP_HIDE_FROM_ABI void
689 splice_after(const_iterator __p, forward_list&& __x, const_iterator __f, const_iterator __l);
690 _LIBCPP_HIDE_FROM_ABI void splice_after(const_iterator __p, forward_list& __x);
691 _LIBCPP_HIDE_FROM_ABI void splice_after(const_iterator __p, forward_list& __x, const_iterator __i);
692 _LIBCPP_HIDE_FROM_ABI void
693 splice_after(const_iterator __p, forward_list& __x, const_iterator __f, const_iterator __l);
694 _LIBCPP_HIDE_FROM_ABI __remove_return_type remove(const value_type& __v);
695 template <class _Predicate>
696 _LIBCPP_HIDE_FROM_ABI __remove_return_type remove_if(_Predicate __pred);
697 _LIBCPP_HIDE_FROM_ABI __remove_return_type unique() { return unique(__equal_to()); }
698 template <class _BinaryPredicate>
699 _LIBCPP_HIDE_FROM_ABI __remove_return_type unique(_BinaryPredicate __binary_pred);
700 _LIBCPP_HIDE_FROM_ABI void merge(forward_list& __x) { merge(__x, __less<>()); }
701 template <class _Compare>
702 _LIBCPP_HIDE_FROM_ABI void merge(forward_list& __x, _Compare __comp);
703 _LIBCPP_HIDE_FROM_ABI void sort() { sort(__less<>()); }
704 template <class _Compare>
705 _LIBCPP_HIDE_FROM_ABI void sort(_Compare __comp);
706 _LIBCPP_HIDE_FROM_ABI void reverse() _NOEXCEPT;
707
708 private:
709 template <class _Iter, class _Sent>
710 _LIBCPP_HIDE_FROM_ABI void __assign_with_sentinel(_Iter __f, _Sent __l);
711
712 template <class _Compare>
713 static _LIBCPP_HIDE_FROM_ABI __node_pointer __merge(__node_pointer __f1, __node_pointer __f2, _Compare& __comp);
714
715 // TODO: Make this _LIBCPP_HIDE_FROM_ABI
716 template <class _Compare>
717 static _LIBCPP_HIDDEN __node_pointer __sort(__node_pointer __f, difference_type __sz, _Compare& __comp);
718 };
719
720 template <class _Tp, class _Alloc>
721 inline forward_list<_Tp, _Alloc>::forward_list(const allocator_type& __a) : __base(__a) {}
722
723 template <class _Tp, class _Alloc>
724 forward_list<_Tp, _Alloc>::forward_list(size_type __n) {
725 if (__n > 0) {
726 for (__begin_node_pointer __p = __base::__before_begin(); __n > 0; --__n, __p = __p->__next_as_begin()) {
727 __p->__next_ = this->__create_node(/* next = */ nullptr);
728 }
729 }
730 }
731
732 template <class _Tp, class _Alloc>
733 forward_list<_Tp, _Alloc>::forward_list(size_type __n, const value_type& __v) {
734 insert_after(cbefore_begin(), __n, __v);
735 }
736
737 template <class _Tp, class _Alloc>
738 template <class _InputIterator, __enable_if_t<__has_input_iterator_category<_InputIterator>::value, int> >
739 forward_list<_Tp, _Alloc>::forward_list(_InputIterator __f, _InputIterator __l) {
740 insert_after(cbefore_begin(), __f, __l);
741 }
742
743 template <class _Tp, class _Alloc>
744 template <class _InputIterator, __enable_if_t<__has_input_iterator_category<_InputIterator>::value, int> >
745 forward_list<_Tp, _Alloc>::forward_list(_InputIterator __f, _InputIterator __l, const allocator_type& __a)
746 : __base(__a) {
747 insert_after(cbefore_begin(), __f, __l);
748 }
749
750 template <class _Tp, class _Alloc>
751 forward_list<_Tp, _Alloc>::forward_list(const forward_list& __x)
752 : __base(__node_traits::select_on_container_copy_construction(__x.__alloc())) {
753 insert_after(cbefore_begin(), __x.begin(), __x.end());
754 }
755
756 template <class _Tp, class _Alloc>
757 forward_list<_Tp, _Alloc>::forward_list(const forward_list& __x, const __type_identity_t<allocator_type>& __a)
758 : __base(__a) {
759 insert_after(cbefore_begin(), __x.begin(), __x.end());
760 }
761
762 template <class _Tp, class _Alloc>
763 forward_list<_Tp, _Alloc>& forward_list<_Tp, _Alloc>::operator=(const forward_list& __x) {
764 if (this != std::addressof(__x)) {
765 __base::__copy_assign_alloc(__x);
766 assign(__x.begin(), __x.end());
767 }
768 return *this;
769 }
770
771 template <class _Tp, class _Alloc>
772 template <class _InputIterator, __enable_if_t<__has_input_iterator_category<_InputIterator>::value, int> >
773 void forward_list<_Tp, _Alloc>::assign(_InputIterator __f, _InputIterator __l) {
774 __assign_with_sentinel(__f, __l);
775 }
776
777 template <class _Tp, class _Alloc>
778 template <class _Iter, class _Sent>
779 _LIBCPP_HIDE_FROM_ABI void forward_list<_Tp, _Alloc>::__assign_with_sentinel(_Iter __f, _Sent __l) {
780 iterator __i = before_begin();
781 iterator __j = std::next(__i);
782 iterator __e = end();
783 for (; __j != __e && __f != __l; ++__i, (void)++__j, ++__f)
784 *__j = *__f;
785 if (__j == __e)
786 __insert_after_with_sentinel(__i, std::move(__f), std::move(__l));
787 else
788 erase_after(__i, __e);
789 }
790
791 template <class _Tp, class _Alloc>
792 void forward_list<_Tp, _Alloc>::assign(size_type __n, const value_type& __v) {
793 iterator __i = before_begin();
794 iterator __j = std::next(__i);
795 iterator __e = end();
796 for (; __j != __e && __n > 0; --__n, ++__i, ++__j)
797 *__j = __v;
798 if (__j == __e)
799 insert_after(__i, __n, __v);
800 else
801 erase_after(__i, __e);
802 }
803
804 template <class _Tp, class _Alloc>
805 void forward_list<_Tp, _Alloc>::push_front(const value_type& __v) {
806 __base::__before_begin()->__next_ = this->__create_node(/* next = */ __base::__before_begin()->__next_, __v);
807 }
808
809 template <class _Tp, class _Alloc>
810 void forward_list<_Tp, _Alloc>::pop_front() {
811 __node_pointer __p = __base::__before_begin()->__next_;
812 __base::__before_begin()->__next_ = __p->__next_;
813 this->__delete_node(__p);
814 }
815
816 template <class _Tp, class _Alloc>
817 typename forward_list<_Tp, _Alloc>::iterator
818 forward_list<_Tp, _Alloc>::insert_after(const_iterator __p, const value_type& __v) {
819 __begin_node_pointer const __r = __p.__get_begin();
820 __r->__next_ = this->__create_node(/* next = */ __r->__next_, __v);
821 return iterator(__r->__next_);
822 }
823
824 template <class _Tp, class _Alloc>
825 typename forward_list<_Tp, _Alloc>::iterator
826 forward_list<_Tp, _Alloc>::insert_after(const_iterator __p, size_type __n, const value_type& __v) {
827 __begin_node_pointer __r = __p.__get_begin();
828 if (__n > 0) {
829 __node_pointer __first = this->__create_node(/* next = */ nullptr, __v);
830 __node_pointer __last = __first;
831 #ifndef _LIBCPP_HAS_NO_EXCEPTIONS
832 try {
833 #endif // _LIBCPP_HAS_NO_EXCEPTIONS
834 for (--__n; __n != 0; --__n, __last = __last->__next_) {
835 __last->__next_ = this->__create_node(/* next = */ nullptr, __v);
836 }
837 #ifndef _LIBCPP_HAS_NO_EXCEPTIONS
838 } catch (...) {
839 while (__first != nullptr) {
840 __node_pointer __next = __first->__next_;
841 this->__delete_node(__first);
842 __first = __next;
843 }
844 throw;
845 }
846 #endif // _LIBCPP_HAS_NO_EXCEPTIONS
847 __last->__next_ = __r->__next_;
848 __r->__next_ = __first;
849 __r = static_cast<__begin_node_pointer>(__last);
850 }
851 return iterator(__r);
852 }
853
854 template <class _Tp, class _Alloc>
855 template <class _InputIterator, __enable_if_t<__has_input_iterator_category<_InputIterator>::value, int> >
856 typename forward_list<_Tp, _Alloc>::iterator
857 forward_list<_Tp, _Alloc>::insert_after(const_iterator __p, _InputIterator __f, _InputIterator __l) {
858 return __insert_after_with_sentinel(__p, std::move(__f), std::move(__l));
859 }
860
861 template <class _Tp, class _Alloc>
862 template <class _InputIterator, class _Sentinel>
863 _LIBCPP_HIDE_FROM_ABI typename forward_list<_Tp, _Alloc>::iterator
864 forward_list<_Tp, _Alloc>::__insert_after_with_sentinel(const_iterator __p, _InputIterator __f, _Sentinel __l) {
865 __begin_node_pointer __r = __p.__get_begin();
866
867 if (__f != __l) {
868 __node_pointer __first = this->__create_node(/* next = */ nullptr, *__f);
869 __node_pointer __last = __first;
870
871 #ifndef _LIBCPP_HAS_NO_EXCEPTIONS
872 try {
873 #endif // _LIBCPP_HAS_NO_EXCEPTIONS
874 for (++__f; __f != __l; ++__f, ((void)(__last = __last->__next_))) {
875 __last->__next_ = this->__create_node(/* next = */ nullptr, *__f);
876 }
877 #ifndef _LIBCPP_HAS_NO_EXCEPTIONS
878 } catch (...) {
879 while (__first != nullptr) {
880 __node_pointer __next = __first->__next_;
881 this->__delete_node(__first);
882 __first = __next;
883 }
884 throw;
885 }
886 #endif // _LIBCPP_HAS_NO_EXCEPTIONS
887
888 __last->__next_ = __r->__next_;
889 __r->__next_ = __first;
890 __r = static_cast<__begin_node_pointer>(__last);
891 }
892
893 return iterator(__r);
894 }
895
896 template <class _Tp, class _Alloc>
897 typename forward_list<_Tp, _Alloc>::iterator forward_list<_Tp, _Alloc>::erase_after(const_iterator __f) {
898 __begin_node_pointer __p = __f.__get_begin();
899 __node_pointer __n = __p->__next_;
900 __p->__next_ = __n->__next_;
901 this->__delete_node(__n);
902 return iterator(__p->__next_);
903 }
904
905 template <class _Tp, class _Alloc>
906 typename forward_list<_Tp, _Alloc>::iterator
907 forward_list<_Tp, _Alloc>::erase_after(const_iterator __f, const_iterator __l) {
908 __node_pointer __e = __l.__get_unsafe_node_pointer();
909 if (__f != __l) {
910 __begin_node_pointer __bp = __f.__get_begin();
911
912 __node_pointer __n = __bp->__next_;
913 if (__n != __e) {
914 __bp->__next_ = __e;
915 do {
916 __node_pointer __tmp = __n->__next_;
917 this->__delete_node(__n);
918 __n = __tmp;
919 } while (__n != __e);
920 }
921 }
922 return iterator(__e);
923 }
924
925 template <class _Tp, class _Alloc>
926 void forward_list<_Tp, _Alloc>::resize(size_type __n) {
927 size_type __sz = 0;
928 iterator __p = before_begin();
929 iterator __i = begin();
930 iterator __e = end();
931 for (; __i != __e && __sz < __n; ++__p, ++__i, ++__sz)
932 ;
933 if (__i != __e)
934 erase_after(__p, __e);
935 else {
936 __n -= __sz;
937 if (__n > 0) {
938 for (__begin_node_pointer __ptr = __p.__get_begin(); __n > 0; --__n, __ptr = __ptr->__next_as_begin()) {
939 __ptr->__next_ = this->__create_node(/* next = */ nullptr);
940 }
941 }
942 }
943 }
944
945 template <class _Tp, class _Alloc>
946 void forward_list<_Tp, _Alloc>::resize(size_type __n, const value_type& __v) {
947 size_type __sz = 0;
948 iterator __p = before_begin();
949 iterator __i = begin();
950 iterator __e = end();
951 for (; __i != __e && __sz < __n; ++__p, ++__i, ++__sz)
952 ;
953 if (__i != __e)
954 erase_after(__p, __e);
955 else {
956 __n -= __sz;
957 if (__n > 0) {
958 for (__begin_node_pointer __ptr = __p.__get_begin(); __n > 0; --__n, __ptr = __ptr->__next_as_begin()) {
959 __ptr->__next_ = this->__create_node(/* next = */ nullptr, __v);
960 }
961 }
962 }
963 }
964
965 template <class _Tp, class _Alloc>
966 void forward_list<_Tp, _Alloc>::splice_after(const_iterator __p, forward_list& __x) {
967 if (!__x.empty()) {
968 if (__p.__get_begin()->__next_ != nullptr) {
969 const_iterator __lm1 = __x.before_begin();
970 while (__lm1.__get_begin()->__next_ != nullptr)
971 ++__lm1;
972 __lm1.__get_begin()->__next_ = __p.__get_begin()->__next_;
973 }
974 __p.__get_begin()->__next_ = __x.__before_begin()->__next_;
975 __x.__before_begin()->__next_ = nullptr;
976 }
977 }
978
979 template <class _Tp, class _Alloc>
980 void forward_list<_Tp, _Alloc>::splice_after(const_iterator __p, forward_list& /*__other*/, const_iterator __i) {
981 const_iterator __lm1 = std::next(__i);
982 if (__p != __i && __p != __lm1) {
983 __i.__get_begin()->__next_ = __lm1.__get_begin()->__next_;
984 __lm1.__get_begin()->__next_ = __p.__get_begin()->__next_;
985 __p.__get_begin()->__next_ = __lm1.__get_unsafe_node_pointer();
986 }
987 }
988
989 template <class _Tp, class _Alloc>
990 void forward_list<_Tp, _Alloc>::splice_after(
991 const_iterator __p, forward_list& /*__other*/, const_iterator __f, const_iterator __l) {
992 if (__f != __l && __p != __f) {
993 const_iterator __lm1 = __f;
994 while (__lm1.__get_begin()->__next_ != __l.__get_begin())
995 ++__lm1;
996 if (__f != __lm1) {
997 __lm1.__get_begin()->__next_ = __p.__get_begin()->__next_;
998 __p.__get_begin()->__next_ = __f.__get_begin()->__next_;
999 __f.__get_begin()->__next_ = __l.__get_unsafe_node_pointer();
1000 }
1001 }
1002 }
1003
1004 template <class _Tp, class _Alloc>
1005 inline _LIBCPP_HIDE_FROM_ABI void forward_list<_Tp, _Alloc>::splice_after(const_iterator __p, forward_list&& __x) {
1006 splice_after(__p, __x);
1007 }
1008
1009 template <class _Tp, class _Alloc>
1010 inline _LIBCPP_HIDE_FROM_ABI void
1011 forward_list<_Tp, _Alloc>::splice_after(const_iterator __p, forward_list&& __x, const_iterator __i) {
1012 splice_after(__p, __x, __i);
1013 }
1014
1015 template <class _Tp, class _Alloc>
1016 inline _LIBCPP_HIDE_FROM_ABI void forward_list<_Tp, _Alloc>::splice_after(
1017 const_iterator __p, forward_list&& __x, const_iterator __f, const_iterator __l) {
1018 splice_after(__p, __x, __f, __l);
1019 }
1020
1021 template <class _Tp, class _Alloc>
1022 typename forward_list<_Tp, _Alloc>::__remove_return_type forward_list<_Tp, _Alloc>::remove(const value_type& __v) {
1023 forward_list<_Tp, _Alloc> __deleted_nodes(get_allocator()); // collect the nodes we're removing
1024 typename forward_list<_Tp, _Alloc>::size_type __count_removed = 0;
1025 const iterator __e = end();
1026 for (iterator __i = before_begin(); __i.__get_begin()->__next_ != nullptr;) {
1027 if (__i.__get_begin()->__next_->__get_value() == __v) {
1028 ++__count_removed;
1029 iterator __j = std::next(__i, 2);
1030 for (; __j != __e && *__j == __v; ++__j)
1031 ++__count_removed;
1032 __deleted_nodes.splice_after(__deleted_nodes.before_begin(), *this, __i, __j);
1033 if (__j == __e)
1034 break;
1035 __i = __j;
1036 } else
1037 ++__i;
1038 }
1039
1040 return (__remove_return_type)__count_removed;
1041 }
1042
1043 template <class _Tp, class _Alloc>
1044 template <class _Predicate>
1045 typename forward_list<_Tp, _Alloc>::__remove_return_type forward_list<_Tp, _Alloc>::remove_if(_Predicate __pred) {
1046 forward_list<_Tp, _Alloc> __deleted_nodes(get_allocator()); // collect the nodes we're removing
1047 typename forward_list<_Tp, _Alloc>::size_type __count_removed = 0;
1048 const iterator __e = end();
1049 for (iterator __i = before_begin(); __i.__get_begin()->__next_ != nullptr;) {
1050 if (__pred(__i.__get_begin()->__next_->__get_value())) {
1051 ++__count_removed;
1052 iterator __j = std::next(__i, 2);
1053 for (; __j != __e && __pred(*__j); ++__j)
1054 ++__count_removed;
1055 __deleted_nodes.splice_after(__deleted_nodes.before_begin(), *this, __i, __j);
1056 if (__j == __e)
1057 break;
1058 __i = __j;
1059 } else
1060 ++__i;
1061 }
1062
1063 return (__remove_return_type)__count_removed;
1064 }
1065
1066 template <class _Tp, class _Alloc>
1067 template <class _BinaryPredicate>
1068 typename forward_list<_Tp, _Alloc>::__remove_return_type
1069 forward_list<_Tp, _Alloc>::unique(_BinaryPredicate __binary_pred) {
1070 forward_list<_Tp, _Alloc> __deleted_nodes(get_allocator()); // collect the nodes we're removing
1071 typename forward_list<_Tp, _Alloc>::size_type __count_removed = 0;
1072 for (iterator __i = begin(), __e = end(); __i != __e;) {
1073 iterator __j = std::next(__i);
1074 for (; __j != __e && __binary_pred(*__i, *__j); ++__j)
1075 ++__count_removed;
1076 if (__i.__get_begin()->__next_ != __j.__get_unsafe_node_pointer())
1077 __deleted_nodes.splice_after(__deleted_nodes.before_begin(), *this, __i, __j);
1078 __i = __j;
1079 }
1080
1081 return (__remove_return_type)__count_removed;
1082 }
1083
1084 template <class _Tp, class _Alloc>
1085 template <class _Compare>
1086 void forward_list<_Tp, _Alloc>::merge(forward_list& __x, _Compare __comp) {
1087 if (this != std::addressof(__x)) {
1088 __base::__before_begin()->__next_ =
1089 __merge(__base::__before_begin()->__next_, __x.__before_begin()->__next_, __comp);
1090 __x.__before_begin()->__next_ = nullptr;
1091 }
1092 }
1093
1094 template <class _Tp, class _Alloc>
1095 template <class _Compare>
1096 typename forward_list<_Tp, _Alloc>::__node_pointer
1097 forward_list<_Tp, _Alloc>::__merge(__node_pointer __f1, __node_pointer __f2, _Compare& __comp) {
1098 if (__f1 == nullptr)
1099 return __f2;
1100 if (__f2 == nullptr)
1101 return __f1;
1102 __node_pointer __r;
1103 if (__comp(__f2->__get_value(), __f1->__get_value())) {
1104 __node_pointer __t = __f2;
1105 while (__t->__next_ != nullptr && __comp(__t->__next_->__get_value(), __f1->__get_value()))
1106 __t = __t->__next_;
1107 __r = __f2;
1108 __f2 = __t->__next_;
1109 __t->__next_ = __f1;
1110 } else
1111 __r = __f1;
1112 __node_pointer __p = __f1;
1113 __f1 = __f1->__next_;
1114 while (__f1 != nullptr && __f2 != nullptr) {
1115 if (__comp(__f2->__get_value(), __f1->__get_value())) {
1116 __node_pointer __t = __f2;
1117 while (__t->__next_ != nullptr && __comp(__t->__next_->__get_value(), __f1->__get_value()))
1118 __t = __t->__next_;
1119 __p->__next_ = __f2;
1120 __f2 = __t->__next_;
1121 __t->__next_ = __f1;
1122 }
1123 __p = __f1;
1124 __f1 = __f1->__next_;
1125 }
1126 if (__f2 != nullptr)
1127 __p->__next_ = __f2;
1128 return __r;
1129 }
1130
1131 template <class _Tp, class _Alloc>
1132 template <class _Compare>
1133 inline void forward_list<_Tp, _Alloc>::sort(_Compare __comp) {
1134 __base::__before_begin()->__next_ = __sort(__base::__before_begin()->__next_, std::distance(begin(), end()), __comp);
1135 }
1136
1137 template <class _Tp, class _Alloc>
1138 template <class _Compare>
1139 typename forward_list<_Tp, _Alloc>::__node_pointer
1140 forward_list<_Tp, _Alloc>::__sort(__node_pointer __f1, difference_type __sz, _Compare& __comp) {
1141 switch (__sz) {
1142 case 0:
1143 case 1:
1144 return __f1;
1145 case 2:
1146 if (__comp(__f1->__next_->__get_value(), __f1->__get_value())) {
1147 __node_pointer __t = __f1->__next_;
1148 __t->__next_ = __f1;
1149 __f1->__next_ = nullptr;
1150 __f1 = __t;
1151 }
1152 return __f1;
1153 }
1154 difference_type __sz1 = __sz / 2;
1155 difference_type __sz2 = __sz - __sz1;
1156 __node_pointer __t = std::next(iterator(__f1), __sz1 - 1).__get_unsafe_node_pointer();
1157 __node_pointer __f2 = __t->__next_;
1158 __t->__next_ = nullptr;
1159 return __merge(__sort(__f1, __sz1, __comp), __sort(__f2, __sz2, __comp), __comp);
1160 }
1161
1162 template <class _Tp, class _Alloc>
1163 void forward_list<_Tp, _Alloc>::reverse() _NOEXCEPT {
1164 __node_pointer __p = __base::__before_begin()->__next_;
1165 if (__p != nullptr) {
1166 __node_pointer __f = __p->__next_;
1167 __p->__next_ = nullptr;
1168 while (__f != nullptr) {
1169 __node_pointer __t = __f->__next_;
1170 __f->__next_ = __p;
1171 __p = __f;
1172 __f = __t;
1173 }
1174 __base::__before_begin()->__next_ = __p;
1175 }
1176 }
1177
1178 template <class _Tp, class _Alloc>
1179 _LIBCPP_HIDE_FROM_ABI bool operator==(const forward_list<_Tp, _Alloc>& __x, const forward_list<_Tp, _Alloc>& __y) {
1180 typedef forward_list<_Tp, _Alloc> _Cp;
1181 typedef typename _Cp::const_iterator _Ip;
1182 _Ip __ix = __x.begin();
1183 _Ip __ex = __x.end();
1184 _Ip __iy = __y.begin();
1185 _Ip __ey = __y.end();
1186 for (; __ix != __ex && __iy != __ey; ++__ix, ++__iy)
1187 if (!(*__ix == *__iy))
1188 return false;
1189 return (__ix == __ex) == (__iy == __ey);
1190 }
1191
1192 template <class _Tp, class _Alloc>
1193 inline _LIBCPP_HIDE_FROM_ABI bool
1194 operator!=(const forward_list<_Tp, _Alloc>& __x, const forward_list<_Tp, _Alloc>& __y) {
1195 return !(__x == __y);
1196 }
1197
1198 template <class _Tp, class _Alloc>
1199 inline _LIBCPP_HIDE_FROM_ABI bool
1200 operator<(const forward_list<_Tp, _Alloc>& __x, const forward_list<_Tp, _Alloc>& __y) {
1201 return std::lexicographical_compare(__x.begin(), __x.end(), __y.begin(), __y.end());
1202 }
1203
1204 template <class _Tp, class _Alloc>
1205 inline _LIBCPP_HIDE_FROM_ABI bool
1206 operator>(const forward_list<_Tp, _Alloc>& __x, const forward_list<_Tp, _Alloc>& __y) {
1207 return __y < __x;
1208 }
1209
1210 template <class _Tp, class _Alloc>
1211 inline _LIBCPP_HIDE_FROM_ABI bool
1212 operator>=(const forward_list<_Tp, _Alloc>& __x, const forward_list<_Tp, _Alloc>& __y) {
1213 return !(__x < __y);
1214 }
1215
1216 template <class _Tp, class _Alloc>
1217 inline _LIBCPP_HIDE_FROM_ABI bool
1218 operator<=(const forward_list<_Tp, _Alloc>& __x, const forward_list<_Tp, _Alloc>& __y) {
1219 return !(__y < __x);
1220 }
1221
1222 template <class _Tp, class _Alloc>
1223 inline _LIBCPP_HIDE_FROM_ABI void swap(forward_list<_Tp, _Alloc>& __x, forward_list<_Tp, _Alloc>& __y) {
1224 __x.swap(__y);
1225 }
1226
1227 _LIBCPP_END_NAMESPACE_STD
1228
1229 _LIBCPP_POP_MACROS
1230
1231 #if !defined(_LIBCPP_REMOVE_TRANSITIVE_INCLUDES)
1232 # include <__cxx03/algorithm>
1233 # include <__cxx03/atomic>
1234 # include <__cxx03/cstdint>
1235 # include <__cxx03/cstdlib>
1236 # include <__cxx03/cstring>
1237 # include <__cxx03/functional>
1238 # include <__cxx03/iosfwd>
1239 # include <__cxx03/iterator>
1240 # include <__cxx03/stdexcept>
1241 # include <__cxx03/type_traits>
1242 # include <__cxx03/typeinfo>
1243 #endif
1244
1245 #endif // _LIBCPP___CXX03_FORWARD_LIST