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 | |
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 | 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 | |
139 | template <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 | |
143 | template <class T, class Allocator> |
144 | bool operator==(const forward_list<T, Allocator>& x, |
145 | const forward_list<T, Allocator>& y); |
146 | |
147 | template <class T, class Allocator> |
148 | bool operator< (const forward_list<T, Allocator>& x, |
149 | const forward_list<T, Allocator>& y); |
150 | |
151 | template <class T, class Allocator> |
152 | bool operator!=(const forward_list<T, Allocator>& x, |
153 | const forward_list<T, Allocator>& y); |
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); |
162 | |
163 | template <class T, class Allocator> |
164 | bool operator<=(const forward_list<T, Allocator>& x, |
165 | const forward_list<T, Allocator>& y); |
166 | |
167 | template <class T, class Allocator> |
168 | void swap(forward_list<T, Allocator>& x, forward_list<T, Allocator>& y) |
169 | noexcept(noexcept(x.swap(y))); |
170 | |
171 | template <class T, class Allocator, class U> |
172 | void erase(forward_list<T, Allocator>& c, const U& value); // C++20 |
173 | template <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 | |
198 | template <class _Tp, class _VoidPtr> struct __forward_list_node; |
199 | template <class _NodePtr> struct __forward_begin_node; |
200 | |
201 | |
202 | template <class> |
203 | struct __forward_list_node_value_type; |
204 | |
205 | template <class _Tp, class _VoidPtr> |
206 | struct __forward_list_node_value_type<__forward_list_node<_Tp, _VoidPtr> > { |
207 | typedef _Tp type; |
208 | }; |
209 | |
210 | template <class _NodePtr> |
211 | struct __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 | |
248 | template <class _NodePtr> |
249 | struct __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 | |
264 | template <class _Tp, class _VoidPtr> |
265 | struct _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 | |
272 | template <class _Tp, class _VoidPtr> |
273 | struct __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 | |
282 | template <class _Tp, class _Alloc = allocator<_Tp> > class _LIBCPP_TEMPLATE_VIS forward_list; |
283 | template<class _NodeConstPtr> class _LIBCPP_TEMPLATE_VIS __forward_list_const_iterator; |
284 | |
285 | template <class _NodePtr> |
286 | class _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 | |
321 | public: |
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 | |
363 | template <class _NodeConstPtr> |
364 | class _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 | |
402 | public: |
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 | |
447 | template <class _Tp, class _Alloc> |
448 | class __forward_list_base |
449 | { |
450 | protected: |
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(), __default_init_tag()) {} |
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 |
501 | public: |
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 | |
509 | private: |
510 | __forward_list_base(const __forward_list_base&); |
511 | __forward_list_base& operator=(const __forward_list_base&); |
512 | |
513 | public: |
514 | ~__forward_list_base(); |
515 | |
516 | protected: |
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 | |
529 | public: |
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 |
538 | protected: |
539 | void clear() _NOEXCEPT; |
540 | |
541 | private: |
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 | |
563 | template <class _Tp, class _Alloc> |
564 | inline |
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 | |
572 | template <class _Tp, class _Alloc> |
573 | inline |
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 | |
587 | template <class _Tp, class _Alloc> |
588 | __forward_list_base<_Tp, _Alloc>::~__forward_list_base() |
589 | { |
590 | clear(); |
591 | } |
592 | |
593 | template <class _Tp, class _Alloc> |
594 | inline |
595 | void |
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 | |
610 | template <class _Tp, class _Alloc> |
611 | void |
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 | |
625 | template <class _Tp, class _Alloc /*= allocator<_Tp>*/> |
626 | class _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 | |
636 | public: |
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_cpp17_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_cpp17_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_cpp17_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_cpp17_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 | |
850 | private: |
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 |
871 | template<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 | > |
875 | forward_list(_InputIterator, _InputIterator) |
876 | -> forward_list<typename iterator_traits<_InputIterator>::value_type, _Alloc>; |
877 | |
878 | template<class _InputIterator, |
879 | class _Alloc, |
880 | class = typename enable_if<__is_allocator<_Alloc>::value, void>::type |
881 | > |
882 | forward_list(_InputIterator, _InputIterator, _Alloc) |
883 | -> forward_list<typename iterator_traits<_InputIterator>::value_type, _Alloc>; |
884 | #endif |
885 | |
886 | template <class _Tp, class _Alloc> |
887 | inline |
888 | forward_list<_Tp, _Alloc>::forward_list(const allocator_type& __a) |
889 | : base(__a) |
890 | { |
891 | } |
892 | |
893 | template <class _Tp, class _Alloc> |
894 | forward_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 |
913 | template <class _Tp, class _Alloc> |
914 | forward_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 | |
935 | template <class _Tp, class _Alloc> |
936 | forward_list<_Tp, _Alloc>::forward_list(size_type __n, const value_type& __v) |
937 | { |
938 | insert_after(cbefore_begin(), __n, __v); |
939 | } |
940 | |
941 | template <class _Tp, class _Alloc> |
942 | forward_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 | |
949 | template <class _Tp, class _Alloc> |
950 | template <class _InputIterator> |
951 | forward_list<_Tp, _Alloc>::forward_list(_InputIterator __f, _InputIterator __l, |
952 | typename enable_if< |
953 | __is_cpp17_input_iterator<_InputIterator>::value |
954 | >::type*) |
955 | { |
956 | insert_after(cbefore_begin(), __f, __l); |
957 | } |
958 | |
959 | template <class _Tp, class _Alloc> |
960 | template <class _InputIterator> |
961 | forward_list<_Tp, _Alloc>::forward_list(_InputIterator __f, _InputIterator __l, |
962 | const allocator_type& __a, |
963 | typename enable_if< |
964 | __is_cpp17_input_iterator<_InputIterator>::value |
965 | >::type*) |
966 | : base(__a) |
967 | { |
968 | insert_after(cbefore_begin(), __f, __l); |
969 | } |
970 | |
971 | template <class _Tp, class _Alloc> |
972 | forward_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 | |
978 | template <class _Tp, class _Alloc> |
979 | forward_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 | |
986 | template <class _Tp, class _Alloc> |
987 | forward_list<_Tp, _Alloc>& |
988 | forward_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 |
999 | template <class _Tp, class _Alloc> |
1000 | forward_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 | |
1011 | template <class _Tp, class _Alloc> |
1012 | forward_list<_Tp, _Alloc>::forward_list(initializer_list<value_type> __il) |
1013 | { |
1014 | insert_after(cbefore_begin(), __il.begin(), __il.end()); |
1015 | } |
1016 | |
1017 | template <class _Tp, class _Alloc> |
1018 | forward_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 | |
1025 | template <class _Tp, class _Alloc> |
1026 | void |
1027 | forward_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 | |
1036 | template <class _Tp, class _Alloc> |
1037 | void |
1038 | forward_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 | |
1049 | template <class _Tp, class _Alloc> |
1050 | inline |
1051 | forward_list<_Tp, _Alloc>& |
1052 | forward_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 | |
1062 | template <class _Tp, class _Alloc> |
1063 | inline |
1064 | forward_list<_Tp, _Alloc>& |
1065 | forward_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 | |
1073 | template <class _Tp, class _Alloc> |
1074 | template <class _InputIterator> |
1075 | typename enable_if |
1076 | < |
1077 | __is_cpp17_input_iterator<_InputIterator>::value, |
1078 | void |
1079 | >::type |
1080 | forward_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 | |
1093 | template <class _Tp, class _Alloc> |
1094 | void |
1095 | forward_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 | |
1110 | template <class _Tp, class _Alloc> |
1111 | inline |
1112 | void |
1113 | forward_list<_Tp, _Alloc>::assign(initializer_list<value_type> __il) |
1114 | { |
1115 | assign(__il.begin(), __il.end()); |
1116 | } |
1117 | |
1118 | template <class _Tp, class _Alloc> |
1119 | template <class... _Args> |
1120 | #if _LIBCPP_STD_VER > 14 |
1121 | typename forward_list<_Tp, _Alloc>::reference |
1122 | #else |
1123 | void |
1124 | #endif |
1125 | forward_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 | |
1139 | template <class _Tp, class _Alloc> |
1140 | void |
1141 | forward_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 | |
1153 | template <class _Tp, class _Alloc> |
1154 | void |
1155 | forward_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 | |
1165 | template <class _Tp, class _Alloc> |
1166 | void |
1167 | forward_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 | |
1178 | template <class _Tp, class _Alloc> |
1179 | template <class... _Args> |
1180 | typename forward_list<_Tp, _Alloc>::iterator |
1181 | forward_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 | |
1194 | template <class _Tp, class _Alloc> |
1195 | typename forward_list<_Tp, _Alloc>::iterator |
1196 | forward_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 | |
1210 | template <class _Tp, class _Alloc> |
1211 | typename forward_list<_Tp, _Alloc>::iterator |
1212 | forward_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 | |
1224 | template <class _Tp, class _Alloc> |
1225 | typename forward_list<_Tp, _Alloc>::iterator |
1226 | forward_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 | |
1269 | template <class _Tp, class _Alloc> |
1270 | template <class _InputIterator> |
1271 | typename enable_if |
1272 | < |
1273 | __is_cpp17_input_iterator<_InputIterator>::value, |
1274 | typename forward_list<_Tp, _Alloc>::iterator |
1275 | >::type |
1276 | forward_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 | |
1319 | template <class _Tp, class _Alloc> |
1320 | typename forward_list<_Tp, _Alloc>::iterator |
1321 | forward_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 | |
1332 | template <class _Tp, class _Alloc> |
1333 | typename forward_list<_Tp, _Alloc>::iterator |
1334 | forward_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 | |
1358 | template <class _Tp, class _Alloc> |
1359 | void |
1360 | forward_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 | |
1390 | template <class _Tp, class _Alloc> |
1391 | void |
1392 | forward_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 | |
1422 | template <class _Tp, class _Alloc> |
1423 | void |
1424 | forward_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 | |
1441 | template <class _Tp, class _Alloc> |
1442 | void |
1443 | forward_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 | |
1456 | template <class _Tp, class _Alloc> |
1457 | void |
1458 | forward_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 | |
1476 | template <class _Tp, class _Alloc> |
1477 | inline _LIBCPP_INLINE_VISIBILITY |
1478 | void |
1479 | forward_list<_Tp, _Alloc>::splice_after(const_iterator __p, |
1480 | forward_list&& __x) |
1481 | { |
1482 | splice_after(__p, __x); |
1483 | } |
1484 | |
1485 | template <class _Tp, class _Alloc> |
1486 | inline _LIBCPP_INLINE_VISIBILITY |
1487 | void |
1488 | forward_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 | |
1495 | template <class _Tp, class _Alloc> |
1496 | inline _LIBCPP_INLINE_VISIBILITY |
1497 | void |
1498 | forward_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 | |
1505 | template <class _Tp, class _Alloc> |
1506 | typename forward_list<_Tp, _Alloc>::__remove_return_type |
1507 | forward_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 | |
1532 | template <class _Tp, class _Alloc> |
1533 | template <class _Predicate> |
1534 | typename forward_list<_Tp, _Alloc>::__remove_return_type |
1535 | forward_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 | |
1560 | template <class _Tp, class _Alloc> |
1561 | template <class _BinaryPredicate> |
1562 | typename forward_list<_Tp, _Alloc>::__remove_return_type |
1563 | forward_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 | |
1580 | template <class _Tp, class _Alloc> |
1581 | template <class _Compare> |
1582 | void |
1583 | forward_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 | |
1594 | template <class _Tp, class _Alloc> |
1595 | template <class _Compare> |
1596 | typename forward_list<_Tp, _Alloc>::__node_pointer |
1597 | forward_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 | |
1639 | template <class _Tp, class _Alloc> |
1640 | template <class _Compare> |
1641 | inline |
1642 | void |
1643 | forward_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 | |
1649 | template <class _Tp, class _Alloc> |
1650 | template <class _Compare> |
1651 | typename forward_list<_Tp, _Alloc>::__node_pointer |
1652 | forward_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 | |
1679 | template <class _Tp, class _Alloc> |
1680 | void |
1681 | forward_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 | |
1699 | template <class _Tp, class _Alloc> |
1700 | bool 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 | |
1715 | template <class _Tp, class _Alloc> |
1716 | inline _LIBCPP_INLINE_VISIBILITY |
1717 | bool operator!=(const forward_list<_Tp, _Alloc>& __x, |
1718 | const forward_list<_Tp, _Alloc>& __y) |
1719 | { |
1720 | return !(__x == __y); |
1721 | } |
1722 | |
1723 | template <class _Tp, class _Alloc> |
1724 | inline _LIBCPP_INLINE_VISIBILITY |
1725 | bool 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 | |
1732 | template <class _Tp, class _Alloc> |
1733 | inline _LIBCPP_INLINE_VISIBILITY |
1734 | bool operator> (const forward_list<_Tp, _Alloc>& __x, |
1735 | const forward_list<_Tp, _Alloc>& __y) |
1736 | { |
1737 | return __y < __x; |
1738 | } |
1739 | |
1740 | template <class _Tp, class _Alloc> |
1741 | inline _LIBCPP_INLINE_VISIBILITY |
1742 | bool operator>=(const forward_list<_Tp, _Alloc>& __x, |
1743 | const forward_list<_Tp, _Alloc>& __y) |
1744 | { |
1745 | return !(__x < __y); |
1746 | } |
1747 | |
1748 | template <class _Tp, class _Alloc> |
1749 | inline _LIBCPP_INLINE_VISIBILITY |
1750 | bool operator<=(const forward_list<_Tp, _Alloc>& __x, |
1751 | const forward_list<_Tp, _Alloc>& __y) |
1752 | { |
1753 | return !(__y < __x); |
1754 | } |
1755 | |
1756 | template <class _Tp, class _Alloc> |
1757 | inline _LIBCPP_INLINE_VISIBILITY |
1758 | void |
1759 | swap(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 |
1766 | template <class _Tp, class _Allocator, class _Predicate> |
1767 | inline _LIBCPP_INLINE_VISIBILITY |
1768 | void erase_if(forward_list<_Tp, _Allocator>& __c, _Predicate __pred) |
1769 | { __c.remove_if(__pred); } |
1770 | |
1771 | template <class _Tp, class _Allocator, class _Up> |
1772 | inline _LIBCPP_INLINE_VISIBILITY |
1773 | void 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 | |