1 | // <forward_list.h> -*- C++ -*- |
2 | |
3 | // Copyright (C) 2008-2021 Free Software Foundation, Inc. |
4 | // |
5 | // This file is part of the GNU ISO C++ Library. This library is free |
6 | // software; you can redistribute it and/or modify it under the |
7 | // terms of the GNU General Public License as published by the |
8 | // Free Software Foundation; either version 3, or (at your option) |
9 | // any later version. |
10 | |
11 | // This library is distributed in the hope that it will be useful, |
12 | // but WITHOUT ANY WARRANTY; without even the implied warranty of |
13 | // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the |
14 | // GNU General Public License for more details. |
15 | |
16 | // Under Section 7 of GPL version 3, you are granted additional |
17 | // permissions described in the GCC Runtime Library Exception, version |
18 | // 3.1, as published by the Free Software Foundation. |
19 | |
20 | // You should have received a copy of the GNU General Public License and |
21 | // a copy of the GCC Runtime Library Exception along with this program; |
22 | // see the files COPYING3 and COPYING.RUNTIME respectively. If not, see |
23 | // <http://www.gnu.org/licenses/>. |
24 | |
25 | /** @file bits/forward_list.h |
26 | * This is an internal header file, included by other library headers. |
27 | * Do not attempt to use it directly. @headername{forward_list} |
28 | */ |
29 | |
30 | #ifndef _FORWARD_LIST_H |
31 | #define _FORWARD_LIST_H 1 |
32 | |
33 | #pragma GCC system_header |
34 | |
35 | #include <initializer_list> |
36 | #include <bits/stl_iterator_base_types.h> |
37 | #include <bits/stl_iterator.h> |
38 | #include <bits/stl_algobase.h> |
39 | #include <bits/stl_function.h> |
40 | #include <bits/allocator.h> |
41 | #include <ext/alloc_traits.h> |
42 | #include <ext/aligned_buffer.h> |
43 | |
44 | namespace std _GLIBCXX_VISIBILITY(default) |
45 | { |
46 | _GLIBCXX_BEGIN_NAMESPACE_VERSION |
47 | _GLIBCXX_BEGIN_NAMESPACE_CONTAINER |
48 | |
49 | /** |
50 | * @brief A helper basic node class for %forward_list. |
51 | * This is just a linked list with nothing inside it. |
52 | * There are purely list shuffling utility methods here. |
53 | */ |
54 | struct _Fwd_list_node_base |
55 | { |
56 | _Fwd_list_node_base() = default; |
57 | _Fwd_list_node_base(_Fwd_list_node_base&& __x) noexcept |
58 | : _M_next(__x._M_next) |
59 | { __x._M_next = nullptr; } |
60 | |
61 | _Fwd_list_node_base(const _Fwd_list_node_base&) = delete; |
62 | _Fwd_list_node_base& operator=(const _Fwd_list_node_base&) = delete; |
63 | |
64 | _Fwd_list_node_base& |
65 | operator=(_Fwd_list_node_base&& __x) noexcept |
66 | { |
67 | _M_next = __x._M_next; |
68 | __x._M_next = nullptr; |
69 | return *this; |
70 | } |
71 | |
72 | _Fwd_list_node_base* _M_next = nullptr; |
73 | |
74 | _Fwd_list_node_base* |
75 | _M_transfer_after(_Fwd_list_node_base* __begin, |
76 | _Fwd_list_node_base* __end) noexcept |
77 | { |
78 | _Fwd_list_node_base* __keep = __begin->_M_next; |
79 | if (__end) |
80 | { |
81 | __begin->_M_next = __end->_M_next; |
82 | __end->_M_next = _M_next; |
83 | } |
84 | else |
85 | __begin->_M_next = nullptr; |
86 | _M_next = __keep; |
87 | return __end; |
88 | } |
89 | |
90 | void |
91 | _M_reverse_after() noexcept |
92 | { |
93 | _Fwd_list_node_base* __tail = _M_next; |
94 | if (!__tail) |
95 | return; |
96 | while (_Fwd_list_node_base* __temp = __tail->_M_next) |
97 | { |
98 | _Fwd_list_node_base* __keep = _M_next; |
99 | _M_next = __temp; |
100 | __tail->_M_next = __temp->_M_next; |
101 | _M_next->_M_next = __keep; |
102 | } |
103 | } |
104 | }; |
105 | |
106 | /** |
107 | * @brief A helper node class for %forward_list. |
108 | * This is just a linked list with uninitialized storage for a |
109 | * data value in each node. |
110 | * There is a sorting utility method. |
111 | */ |
112 | template<typename _Tp> |
113 | struct _Fwd_list_node |
114 | : public _Fwd_list_node_base |
115 | { |
116 | _Fwd_list_node() = default; |
117 | |
118 | __gnu_cxx::__aligned_buffer<_Tp> _M_storage; |
119 | |
120 | _Tp* |
121 | _M_valptr() noexcept |
122 | { return _M_storage._M_ptr(); } |
123 | |
124 | const _Tp* |
125 | _M_valptr() const noexcept |
126 | { return _M_storage._M_ptr(); } |
127 | }; |
128 | |
129 | /** |
130 | * @brief A forward_list::iterator. |
131 | * |
132 | * All the functions are op overloads. |
133 | */ |
134 | template<typename _Tp> |
135 | struct _Fwd_list_iterator |
136 | { |
137 | typedef _Fwd_list_iterator<_Tp> _Self; |
138 | typedef _Fwd_list_node<_Tp> _Node; |
139 | |
140 | typedef _Tp value_type; |
141 | typedef _Tp* pointer; |
142 | typedef _Tp& reference; |
143 | typedef ptrdiff_t difference_type; |
144 | typedef std::forward_iterator_tag iterator_category; |
145 | |
146 | _Fwd_list_iterator() noexcept |
147 | : _M_node() { } |
148 | |
149 | explicit |
150 | _Fwd_list_iterator(_Fwd_list_node_base* __n) noexcept |
151 | : _M_node(__n) { } |
152 | |
153 | reference |
154 | operator*() const noexcept |
155 | { return *static_cast<_Node*>(this->_M_node)->_M_valptr(); } |
156 | |
157 | pointer |
158 | operator->() const noexcept |
159 | { return static_cast<_Node*>(this->_M_node)->_M_valptr(); } |
160 | |
161 | _Self& |
162 | operator++() noexcept |
163 | { |
164 | _M_node = _M_node->_M_next; |
165 | return *this; |
166 | } |
167 | |
168 | _Self |
169 | operator++(int) noexcept |
170 | { |
171 | _Self __tmp(*this); |
172 | _M_node = _M_node->_M_next; |
173 | return __tmp; |
174 | } |
175 | |
176 | /** |
177 | * @brief Forward list iterator equality comparison. |
178 | */ |
179 | friend bool |
180 | operator==(const _Self& __x, const _Self& __y) noexcept |
181 | { return __x._M_node == __y._M_node; } |
182 | |
183 | #if __cpp_impl_three_way_comparison < 201907L |
184 | /** |
185 | * @brief Forward list iterator inequality comparison. |
186 | */ |
187 | friend bool |
188 | operator!=(const _Self& __x, const _Self& __y) noexcept |
189 | { return __x._M_node != __y._M_node; } |
190 | #endif |
191 | |
192 | _Self |
193 | _M_next() const noexcept |
194 | { |
195 | if (_M_node) |
196 | return _Fwd_list_iterator(_M_node->_M_next); |
197 | else |
198 | return _Fwd_list_iterator(nullptr); |
199 | } |
200 | |
201 | _Fwd_list_node_base* _M_node; |
202 | }; |
203 | |
204 | /** |
205 | * @brief A forward_list::const_iterator. |
206 | * |
207 | * All the functions are op overloads. |
208 | */ |
209 | template<typename _Tp> |
210 | struct _Fwd_list_const_iterator |
211 | { |
212 | typedef _Fwd_list_const_iterator<_Tp> _Self; |
213 | typedef const _Fwd_list_node<_Tp> _Node; |
214 | typedef _Fwd_list_iterator<_Tp> iterator; |
215 | |
216 | typedef _Tp value_type; |
217 | typedef const _Tp* pointer; |
218 | typedef const _Tp& reference; |
219 | typedef ptrdiff_t difference_type; |
220 | typedef std::forward_iterator_tag iterator_category; |
221 | |
222 | _Fwd_list_const_iterator() noexcept |
223 | : _M_node() { } |
224 | |
225 | explicit |
226 | _Fwd_list_const_iterator(const _Fwd_list_node_base* __n) noexcept |
227 | : _M_node(__n) { } |
228 | |
229 | _Fwd_list_const_iterator(const iterator& __iter) noexcept |
230 | : _M_node(__iter._M_node) { } |
231 | |
232 | reference |
233 | operator*() const noexcept |
234 | { return *static_cast<_Node*>(this->_M_node)->_M_valptr(); } |
235 | |
236 | pointer |
237 | operator->() const noexcept |
238 | { return static_cast<_Node*>(this->_M_node)->_M_valptr(); } |
239 | |
240 | _Self& |
241 | operator++() noexcept |
242 | { |
243 | _M_node = _M_node->_M_next; |
244 | return *this; |
245 | } |
246 | |
247 | _Self |
248 | operator++(int) noexcept |
249 | { |
250 | _Self __tmp(*this); |
251 | _M_node = _M_node->_M_next; |
252 | return __tmp; |
253 | } |
254 | |
255 | /** |
256 | * @brief Forward list const_iterator equality comparison. |
257 | */ |
258 | friend bool |
259 | operator==(const _Self& __x, const _Self& __y) noexcept |
260 | { return __x._M_node == __y._M_node; } |
261 | |
262 | #if __cpp_impl_three_way_comparison < 201907L |
263 | /** |
264 | * @brief Forward list const_iterator inequality comparison. |
265 | */ |
266 | friend bool |
267 | operator!=(const _Self& __x, const _Self& __y) noexcept |
268 | { return __x._M_node != __y._M_node; } |
269 | #endif |
270 | |
271 | _Self |
272 | _M_next() const noexcept |
273 | { |
274 | if (this->_M_node) |
275 | return _Fwd_list_const_iterator(_M_node->_M_next); |
276 | else |
277 | return _Fwd_list_const_iterator(nullptr); |
278 | } |
279 | |
280 | const _Fwd_list_node_base* _M_node; |
281 | }; |
282 | |
283 | /** |
284 | * @brief Base class for %forward_list. |
285 | */ |
286 | template<typename _Tp, typename _Alloc> |
287 | struct _Fwd_list_base |
288 | { |
289 | protected: |
290 | typedef __alloc_rebind<_Alloc, _Fwd_list_node<_Tp>> _Node_alloc_type; |
291 | typedef __gnu_cxx::__alloc_traits<_Node_alloc_type> _Node_alloc_traits; |
292 | |
293 | struct _Fwd_list_impl |
294 | : public _Node_alloc_type |
295 | { |
296 | _Fwd_list_node_base _M_head; |
297 | |
298 | _Fwd_list_impl() |
299 | noexcept(is_nothrow_default_constructible<_Node_alloc_type>::value) |
300 | : _Node_alloc_type(), _M_head() |
301 | { } |
302 | |
303 | _Fwd_list_impl(_Fwd_list_impl&&) = default; |
304 | |
305 | _Fwd_list_impl(_Fwd_list_impl&& __fl, _Node_alloc_type&& __a) |
306 | : _Node_alloc_type(std::move(__a)), _M_head(std::move(__fl._M_head)) |
307 | { } |
308 | |
309 | _Fwd_list_impl(_Node_alloc_type&& __a) |
310 | : _Node_alloc_type(std::move(__a)), _M_head() |
311 | { } |
312 | }; |
313 | |
314 | _Fwd_list_impl _M_impl; |
315 | |
316 | public: |
317 | typedef _Fwd_list_iterator<_Tp> iterator; |
318 | typedef _Fwd_list_const_iterator<_Tp> const_iterator; |
319 | typedef _Fwd_list_node<_Tp> _Node; |
320 | |
321 | _Node_alloc_type& |
322 | _M_get_Node_allocator() noexcept |
323 | { return this->_M_impl; } |
324 | |
325 | const _Node_alloc_type& |
326 | _M_get_Node_allocator() const noexcept |
327 | { return this->_M_impl; } |
328 | |
329 | _Fwd_list_base() = default; |
330 | |
331 | _Fwd_list_base(_Node_alloc_type&& __a) |
332 | : _M_impl(std::move(__a)) { } |
333 | |
334 | // When allocators are always equal. |
335 | _Fwd_list_base(_Fwd_list_base&& __lst, _Node_alloc_type&& __a, |
336 | std::true_type) |
337 | : _M_impl(std::move(__lst._M_impl), std::move(__a)) |
338 | { } |
339 | |
340 | // When allocators are not always equal. |
341 | _Fwd_list_base(_Fwd_list_base&& __lst, _Node_alloc_type&& __a); |
342 | |
343 | _Fwd_list_base(_Fwd_list_base&&) = default; |
344 | |
345 | ~_Fwd_list_base() |
346 | { _M_erase_after(&_M_impl._M_head, nullptr); } |
347 | |
348 | protected: |
349 | _Node* |
350 | _M_get_node() |
351 | { |
352 | auto __ptr = _Node_alloc_traits::allocate(_M_get_Node_allocator(), 1); |
353 | return std::__to_address(__ptr); |
354 | } |
355 | |
356 | template<typename... _Args> |
357 | _Node* |
358 | _M_create_node(_Args&&... __args) |
359 | { |
360 | _Node* __node = this->_M_get_node(); |
361 | __try |
362 | { |
363 | ::new ((void*)__node) _Node; |
364 | _Node_alloc_traits::construct(_M_get_Node_allocator(), |
365 | __node->_M_valptr(), |
366 | std::forward<_Args>(__args)...); |
367 | } |
368 | __catch(...) |
369 | { |
370 | this->_M_put_node(__node); |
371 | __throw_exception_again; |
372 | } |
373 | return __node; |
374 | } |
375 | |
376 | template<typename... _Args> |
377 | _Fwd_list_node_base* |
378 | _M_insert_after(const_iterator __pos, _Args&&... __args); |
379 | |
380 | void |
381 | _M_put_node(_Node* __p) |
382 | { |
383 | typedef typename _Node_alloc_traits::pointer _Ptr; |
384 | auto __ptr = std::pointer_traits<_Ptr>::pointer_to(*__p); |
385 | _Node_alloc_traits::deallocate(_M_get_Node_allocator(), __ptr, 1); |
386 | } |
387 | |
388 | _Fwd_list_node_base* |
389 | _M_erase_after(_Fwd_list_node_base* __pos); |
390 | |
391 | _Fwd_list_node_base* |
392 | _M_erase_after(_Fwd_list_node_base* __pos, |
393 | _Fwd_list_node_base* __last); |
394 | }; |
395 | |
396 | /** |
397 | * @brief A standard container with linear time access to elements, |
398 | * and fixed time insertion/deletion at any point in the sequence. |
399 | * |
400 | * @ingroup sequences |
401 | * |
402 | * @tparam _Tp Type of element. |
403 | * @tparam _Alloc Allocator type, defaults to allocator<_Tp>. |
404 | * |
405 | * Meets the requirements of a <a href="tables.html#65">container</a>, a |
406 | * <a href="tables.html#67">sequence</a>, including the |
407 | * <a href="tables.html#68">optional sequence requirements</a> with the |
408 | * %exception of @c at and @c operator[]. |
409 | * |
410 | * This is a @e singly @e linked %list. Traversal up the |
411 | * %list requires linear time, but adding and removing elements (or |
412 | * @e nodes) is done in constant time, regardless of where the |
413 | * change takes place. Unlike std::vector and std::deque, |
414 | * random-access iterators are not provided, so subscripting ( @c |
415 | * [] ) access is not allowed. For algorithms which only need |
416 | * sequential access, this lack makes no difference. |
417 | * |
418 | * Also unlike the other standard containers, std::forward_list provides |
419 | * specialized algorithms %unique to linked lists, such as |
420 | * splicing, sorting, and in-place reversal. |
421 | */ |
422 | template<typename _Tp, typename _Alloc = allocator<_Tp>> |
423 | class forward_list : private _Fwd_list_base<_Tp, _Alloc> |
424 | { |
425 | static_assert(is_same<typename remove_cv<_Tp>::type, _Tp>::value, |
426 | "std::forward_list must have a non-const, non-volatile value_type" ); |
427 | #if __cplusplus > 201703L || defined __STRICT_ANSI__ |
428 | static_assert(is_same<typename _Alloc::value_type, _Tp>::value, |
429 | "std::forward_list must have the same value_type as its allocator" ); |
430 | #endif |
431 | |
432 | private: |
433 | typedef _Fwd_list_base<_Tp, _Alloc> _Base; |
434 | typedef _Fwd_list_node_base _Node_base; |
435 | typedef typename _Base::_Node _Node; |
436 | typedef typename _Base::_Node_alloc_type _Node_alloc_type; |
437 | typedef typename _Base::_Node_alloc_traits _Node_alloc_traits; |
438 | typedef allocator_traits<__alloc_rebind<_Alloc, _Tp>> _Alloc_traits; |
439 | |
440 | public: |
441 | // types: |
442 | typedef _Tp value_type; |
443 | typedef typename _Alloc_traits::pointer pointer; |
444 | typedef typename _Alloc_traits::const_pointer const_pointer; |
445 | typedef value_type& reference; |
446 | typedef const value_type& const_reference; |
447 | |
448 | typedef typename _Base::iterator iterator; |
449 | typedef typename _Base::const_iterator const_iterator; |
450 | typedef std::size_t size_type; |
451 | typedef std::ptrdiff_t difference_type; |
452 | typedef _Alloc allocator_type; |
453 | |
454 | // 23.3.4.2 construct/copy/destroy: |
455 | |
456 | /** |
457 | * @brief Creates a %forward_list with no elements. |
458 | */ |
459 | forward_list() = default; |
460 | |
461 | /** |
462 | * @brief Creates a %forward_list with no elements. |
463 | * @param __al An allocator object. |
464 | */ |
465 | explicit |
466 | forward_list(const _Alloc& __al) noexcept |
467 | : _Base(_Node_alloc_type(__al)) |
468 | { } |
469 | |
470 | /** |
471 | * @brief Copy constructor with allocator argument. |
472 | * @param __list Input list to copy. |
473 | * @param __al An allocator object. |
474 | */ |
475 | forward_list(const forward_list& __list, const _Alloc& __al) |
476 | : _Base(_Node_alloc_type(__al)) |
477 | { _M_range_initialize(__list.begin(), __list.end()); } |
478 | |
479 | private: |
480 | forward_list(forward_list&& __list, _Node_alloc_type&& __al, |
481 | false_type) |
482 | : _Base(std::move(__list), std::move(__al)) |
483 | { |
484 | // If __list is not empty it means its allocator is not equal to __a, |
485 | // so we need to move from each element individually. |
486 | insert_after(cbefore_begin(), |
487 | std::__make_move_if_noexcept_iterator(__list.begin()), |
488 | std::__make_move_if_noexcept_iterator(__list.end())); |
489 | } |
490 | |
491 | forward_list(forward_list&& __list, _Node_alloc_type&& __al, |
492 | true_type) |
493 | noexcept |
494 | : _Base(std::move(__list), _Node_alloc_type(__al), true_type{}) |
495 | { } |
496 | |
497 | public: |
498 | /** |
499 | * @brief Move constructor with allocator argument. |
500 | * @param __list Input list to move. |
501 | * @param __al An allocator object. |
502 | */ |
503 | forward_list(forward_list&& __list, const _Alloc& __al) |
504 | noexcept(_Node_alloc_traits::_S_always_equal()) |
505 | : forward_list(std::move(__list), _Node_alloc_type(__al), |
506 | typename _Node_alloc_traits::is_always_equal{}) |
507 | { } |
508 | |
509 | /** |
510 | * @brief Creates a %forward_list with default constructed elements. |
511 | * @param __n The number of elements to initially create. |
512 | * @param __al An allocator object. |
513 | * |
514 | * This constructor creates the %forward_list with @a __n default |
515 | * constructed elements. |
516 | */ |
517 | explicit |
518 | forward_list(size_type __n, const _Alloc& __al = _Alloc()) |
519 | : _Base(_Node_alloc_type(__al)) |
520 | { _M_default_initialize(__n); } |
521 | |
522 | /** |
523 | * @brief Creates a %forward_list with copies of an exemplar element. |
524 | * @param __n The number of elements to initially create. |
525 | * @param __value An element to copy. |
526 | * @param __al An allocator object. |
527 | * |
528 | * This constructor fills the %forward_list with @a __n copies of |
529 | * @a __value. |
530 | */ |
531 | forward_list(size_type __n, const _Tp& __value, |
532 | const _Alloc& __al = _Alloc()) |
533 | : _Base(_Node_alloc_type(__al)) |
534 | { _M_fill_initialize(__n, __value); } |
535 | |
536 | /** |
537 | * @brief Builds a %forward_list from a range. |
538 | * @param __first An input iterator. |
539 | * @param __last An input iterator. |
540 | * @param __al An allocator object. |
541 | * |
542 | * Create a %forward_list consisting of copies of the elements from |
543 | * [@a __first,@a __last). This is linear in N (where N is |
544 | * distance(@a __first,@a __last)). |
545 | */ |
546 | template<typename _InputIterator, |
547 | typename = std::_RequireInputIter<_InputIterator>> |
548 | forward_list(_InputIterator __first, _InputIterator __last, |
549 | const _Alloc& __al = _Alloc()) |
550 | : _Base(_Node_alloc_type(__al)) |
551 | { _M_range_initialize(__first, __last); } |
552 | |
553 | /** |
554 | * @brief The %forward_list copy constructor. |
555 | * @param __list A %forward_list of identical element and allocator |
556 | * types. |
557 | */ |
558 | forward_list(const forward_list& __list) |
559 | : _Base(_Node_alloc_traits::_S_select_on_copy( |
560 | __list._M_get_Node_allocator())) |
561 | { _M_range_initialize(__list.begin(), __list.end()); } |
562 | |
563 | /** |
564 | * @brief The %forward_list move constructor. |
565 | * @param __list A %forward_list of identical element and allocator |
566 | * types. |
567 | * |
568 | * The newly-created %forward_list contains the exact contents of the |
569 | * moved instance. The contents of the moved instance are a valid, but |
570 | * unspecified %forward_list. |
571 | */ |
572 | forward_list(forward_list&&) = default; |
573 | |
574 | /** |
575 | * @brief Builds a %forward_list from an initializer_list |
576 | * @param __il An initializer_list of value_type. |
577 | * @param __al An allocator object. |
578 | * |
579 | * Create a %forward_list consisting of copies of the elements |
580 | * in the initializer_list @a __il. This is linear in __il.size(). |
581 | */ |
582 | forward_list(std::initializer_list<_Tp> __il, |
583 | const _Alloc& __al = _Alloc()) |
584 | : _Base(_Node_alloc_type(__al)) |
585 | { _M_range_initialize(__il.begin(), __il.end()); } |
586 | |
587 | /** |
588 | * @brief The forward_list dtor. |
589 | */ |
590 | ~forward_list() noexcept |
591 | { } |
592 | |
593 | /** |
594 | * @brief The %forward_list assignment operator. |
595 | * @param __list A %forward_list of identical element and allocator |
596 | * types. |
597 | * |
598 | * All the elements of @a __list are copied. |
599 | * |
600 | * Whether the allocator is copied depends on the allocator traits. |
601 | */ |
602 | forward_list& |
603 | operator=(const forward_list& __list); |
604 | |
605 | /** |
606 | * @brief The %forward_list move assignment operator. |
607 | * @param __list A %forward_list of identical element and allocator |
608 | * types. |
609 | * |
610 | * The contents of @a __list are moved into this %forward_list |
611 | * (without copying, if the allocators permit it). |
612 | * |
613 | * Afterwards @a __list is a valid, but unspecified %forward_list |
614 | * |
615 | * Whether the allocator is moved depends on the allocator traits. |
616 | */ |
617 | forward_list& |
618 | operator=(forward_list&& __list) |
619 | noexcept(_Node_alloc_traits::_S_nothrow_move()) |
620 | { |
621 | constexpr bool __move_storage = |
622 | _Node_alloc_traits::_S_propagate_on_move_assign() |
623 | || _Node_alloc_traits::_S_always_equal(); |
624 | _M_move_assign(std::move(__list), __bool_constant<__move_storage>()); |
625 | return *this; |
626 | } |
627 | |
628 | /** |
629 | * @brief The %forward_list initializer list assignment operator. |
630 | * @param __il An initializer_list of value_type. |
631 | * |
632 | * Replace the contents of the %forward_list with copies of the |
633 | * elements in the initializer_list @a __il. This is linear in |
634 | * __il.size(). |
635 | */ |
636 | forward_list& |
637 | operator=(std::initializer_list<_Tp> __il) |
638 | { |
639 | assign(__il); |
640 | return *this; |
641 | } |
642 | |
643 | /** |
644 | * @brief Assigns a range to a %forward_list. |
645 | * @param __first An input iterator. |
646 | * @param __last An input iterator. |
647 | * |
648 | * This function fills a %forward_list with copies of the elements |
649 | * in the range [@a __first,@a __last). |
650 | * |
651 | * Note that the assignment completely changes the %forward_list and |
652 | * that the number of elements of the resulting %forward_list is the |
653 | * same as the number of elements assigned. |
654 | */ |
655 | template<typename _InputIterator, |
656 | typename = std::_RequireInputIter<_InputIterator>> |
657 | void |
658 | assign(_InputIterator __first, _InputIterator __last) |
659 | { |
660 | typedef is_assignable<_Tp, decltype(*__first)> __assignable; |
661 | _M_assign(__first, __last, __assignable()); |
662 | } |
663 | |
664 | /** |
665 | * @brief Assigns a given value to a %forward_list. |
666 | * @param __n Number of elements to be assigned. |
667 | * @param __val Value to be assigned. |
668 | * |
669 | * This function fills a %forward_list with @a __n copies of the |
670 | * given value. Note that the assignment completely changes the |
671 | * %forward_list, and that the resulting %forward_list has __n |
672 | * elements. |
673 | */ |
674 | void |
675 | assign(size_type __n, const _Tp& __val) |
676 | { _M_assign_n(__n, __val, is_copy_assignable<_Tp>()); } |
677 | |
678 | /** |
679 | * @brief Assigns an initializer_list to a %forward_list. |
680 | * @param __il An initializer_list of value_type. |
681 | * |
682 | * Replace the contents of the %forward_list with copies of the |
683 | * elements in the initializer_list @a __il. This is linear in |
684 | * il.size(). |
685 | */ |
686 | void |
687 | assign(std::initializer_list<_Tp> __il) |
688 | { assign(__il.begin(), __il.end()); } |
689 | |
690 | /// Get a copy of the memory allocation object. |
691 | allocator_type |
692 | get_allocator() const noexcept |
693 | { return allocator_type(this->_M_get_Node_allocator()); } |
694 | |
695 | // 23.3.4.3 iterators: |
696 | |
697 | /** |
698 | * Returns a read/write iterator that points before the first element |
699 | * in the %forward_list. Iteration is done in ordinary element order. |
700 | */ |
701 | iterator |
702 | before_begin() noexcept |
703 | { return iterator(&this->_M_impl._M_head); } |
704 | |
705 | /** |
706 | * Returns a read-only (constant) iterator that points before the |
707 | * first element in the %forward_list. Iteration is done in ordinary |
708 | * element order. |
709 | */ |
710 | const_iterator |
711 | before_begin() const noexcept |
712 | { return const_iterator(&this->_M_impl._M_head); } |
713 | |
714 | /** |
715 | * Returns a read/write iterator that points to the first element |
716 | * in the %forward_list. Iteration is done in ordinary element order. |
717 | */ |
718 | iterator |
719 | begin() noexcept |
720 | { return iterator(this->_M_impl._M_head._M_next); } |
721 | |
722 | /** |
723 | * Returns a read-only (constant) iterator that points to the first |
724 | * element in the %forward_list. Iteration is done in ordinary |
725 | * element order. |
726 | */ |
727 | const_iterator |
728 | begin() const noexcept |
729 | { return const_iterator(this->_M_impl._M_head._M_next); } |
730 | |
731 | /** |
732 | * Returns a read/write iterator that points one past the last |
733 | * element in the %forward_list. Iteration is done in ordinary |
734 | * element order. |
735 | */ |
736 | iterator |
737 | end() noexcept |
738 | { return iterator(nullptr); } |
739 | |
740 | /** |
741 | * Returns a read-only iterator that points one past the last |
742 | * element in the %forward_list. Iteration is done in ordinary |
743 | * element order. |
744 | */ |
745 | const_iterator |
746 | end() const noexcept |
747 | { return const_iterator(nullptr); } |
748 | |
749 | /** |
750 | * Returns a read-only (constant) iterator that points to the |
751 | * first element in the %forward_list. Iteration is done in ordinary |
752 | * element order. |
753 | */ |
754 | const_iterator |
755 | cbegin() const noexcept |
756 | { return const_iterator(this->_M_impl._M_head._M_next); } |
757 | |
758 | /** |
759 | * Returns a read-only (constant) iterator that points before the |
760 | * first element in the %forward_list. Iteration is done in ordinary |
761 | * element order. |
762 | */ |
763 | const_iterator |
764 | cbefore_begin() const noexcept |
765 | { return const_iterator(&this->_M_impl._M_head); } |
766 | |
767 | /** |
768 | * Returns a read-only (constant) iterator that points one past |
769 | * the last element in the %forward_list. Iteration is done in |
770 | * ordinary element order. |
771 | */ |
772 | const_iterator |
773 | cend() const noexcept |
774 | { return const_iterator(nullptr); } |
775 | |
776 | /** |
777 | * Returns true if the %forward_list is empty. (Thus begin() would |
778 | * equal end().) |
779 | */ |
780 | _GLIBCXX_NODISCARD bool |
781 | empty() const noexcept |
782 | { return this->_M_impl._M_head._M_next == nullptr; } |
783 | |
784 | /** |
785 | * Returns the largest possible number of elements of %forward_list. |
786 | */ |
787 | size_type |
788 | max_size() const noexcept |
789 | { return _Node_alloc_traits::max_size(this->_M_get_Node_allocator()); } |
790 | |
791 | // 23.3.4.4 element access: |
792 | |
793 | /** |
794 | * Returns a read/write reference to the data at the first |
795 | * element of the %forward_list. |
796 | */ |
797 | reference |
798 | front() |
799 | { |
800 | _Node* __front = static_cast<_Node*>(this->_M_impl._M_head._M_next); |
801 | return *__front->_M_valptr(); |
802 | } |
803 | |
804 | /** |
805 | * Returns a read-only (constant) reference to the data at the first |
806 | * element of the %forward_list. |
807 | */ |
808 | const_reference |
809 | front() const |
810 | { |
811 | _Node* __front = static_cast<_Node*>(this->_M_impl._M_head._M_next); |
812 | return *__front->_M_valptr(); |
813 | } |
814 | |
815 | // 23.3.4.5 modifiers: |
816 | |
817 | /** |
818 | * @brief Constructs object in %forward_list at the front of the |
819 | * list. |
820 | * @param __args Arguments. |
821 | * |
822 | * This function will insert an object of type Tp constructed |
823 | * with Tp(std::forward<Args>(args)...) at the front of the list |
824 | * Due to the nature of a %forward_list this operation can |
825 | * be done in constant time, and does not invalidate iterators |
826 | * and references. |
827 | */ |
828 | template<typename... _Args> |
829 | #if __cplusplus > 201402L |
830 | reference |
831 | #else |
832 | void |
833 | #endif |
834 | emplace_front(_Args&&... __args) |
835 | { |
836 | this->_M_insert_after(cbefore_begin(), |
837 | std::forward<_Args>(__args)...); |
838 | #if __cplusplus > 201402L |
839 | return front(); |
840 | #endif |
841 | } |
842 | |
843 | /** |
844 | * @brief Add data to the front of the %forward_list. |
845 | * @param __val Data to be added. |
846 | * |
847 | * This is a typical stack operation. The function creates an |
848 | * element at the front of the %forward_list and assigns the given |
849 | * data to it. Due to the nature of a %forward_list this operation |
850 | * can be done in constant time, and does not invalidate iterators |
851 | * and references. |
852 | */ |
853 | void |
854 | push_front(const _Tp& __val) |
855 | { this->_M_insert_after(cbefore_begin(), __val); } |
856 | |
857 | /** |
858 | * |
859 | */ |
860 | void |
861 | push_front(_Tp&& __val) |
862 | { this->_M_insert_after(cbefore_begin(), std::move(__val)); } |
863 | |
864 | /** |
865 | * @brief Removes first element. |
866 | * |
867 | * This is a typical stack operation. It shrinks the %forward_list |
868 | * by one. Due to the nature of a %forward_list this operation can |
869 | * be done in constant time, and only invalidates iterators/references |
870 | * to the element being removed. |
871 | * |
872 | * Note that no data is returned, and if the first element's data |
873 | * is needed, it should be retrieved before pop_front() is |
874 | * called. |
875 | */ |
876 | void |
877 | pop_front() |
878 | { this->_M_erase_after(&this->_M_impl._M_head); } |
879 | |
880 | /** |
881 | * @brief Constructs object in %forward_list after the specified |
882 | * iterator. |
883 | * @param __pos A const_iterator into the %forward_list. |
884 | * @param __args Arguments. |
885 | * @return An iterator that points to the inserted data. |
886 | * |
887 | * This function will insert an object of type T constructed |
888 | * with T(std::forward<Args>(args)...) after the specified |
889 | * location. Due to the nature of a %forward_list this operation can |
890 | * be done in constant time, and does not invalidate iterators |
891 | * and references. |
892 | */ |
893 | template<typename... _Args> |
894 | iterator |
895 | emplace_after(const_iterator __pos, _Args&&... __args) |
896 | { return iterator(this->_M_insert_after(__pos, |
897 | std::forward<_Args>(__args)...)); } |
898 | |
899 | /** |
900 | * @brief Inserts given value into %forward_list after specified |
901 | * iterator. |
902 | * @param __pos An iterator into the %forward_list. |
903 | * @param __val Data to be inserted. |
904 | * @return An iterator that points to the inserted data. |
905 | * |
906 | * This function will insert a copy of the given value after |
907 | * the specified location. Due to the nature of a %forward_list this |
908 | * operation can be done in constant time, and does not |
909 | * invalidate iterators and references. |
910 | */ |
911 | iterator |
912 | insert_after(const_iterator __pos, const _Tp& __val) |
913 | { return iterator(this->_M_insert_after(__pos, __val)); } |
914 | |
915 | /** |
916 | * |
917 | */ |
918 | iterator |
919 | insert_after(const_iterator __pos, _Tp&& __val) |
920 | { return iterator(this->_M_insert_after(__pos, std::move(__val))); } |
921 | |
922 | /** |
923 | * @brief Inserts a number of copies of given data into the |
924 | * %forward_list. |
925 | * @param __pos An iterator into the %forward_list. |
926 | * @param __n Number of elements to be inserted. |
927 | * @param __val Data to be inserted. |
928 | * @return An iterator pointing to the last inserted copy of |
929 | * @a val or @a pos if @a n == 0. |
930 | * |
931 | * This function will insert a specified number of copies of the |
932 | * given data after the location specified by @a pos. |
933 | * |
934 | * This operation is linear in the number of elements inserted and |
935 | * does not invalidate iterators and references. |
936 | */ |
937 | iterator |
938 | insert_after(const_iterator __pos, size_type __n, const _Tp& __val); |
939 | |
940 | /** |
941 | * @brief Inserts a range into the %forward_list. |
942 | * @param __pos An iterator into the %forward_list. |
943 | * @param __first An input iterator. |
944 | * @param __last An input iterator. |
945 | * @return An iterator pointing to the last inserted element or |
946 | * @a __pos if @a __first == @a __last. |
947 | * |
948 | * This function will insert copies of the data in the range |
949 | * [@a __first,@a __last) into the %forward_list after the |
950 | * location specified by @a __pos. |
951 | * |
952 | * This operation is linear in the number of elements inserted and |
953 | * does not invalidate iterators and references. |
954 | */ |
955 | template<typename _InputIterator, |
956 | typename = std::_RequireInputIter<_InputIterator>> |
957 | iterator |
958 | insert_after(const_iterator __pos, |
959 | _InputIterator __first, _InputIterator __last); |
960 | |
961 | /** |
962 | * @brief Inserts the contents of an initializer_list into |
963 | * %forward_list after the specified iterator. |
964 | * @param __pos An iterator into the %forward_list. |
965 | * @param __il An initializer_list of value_type. |
966 | * @return An iterator pointing to the last inserted element |
967 | * or @a __pos if @a __il is empty. |
968 | * |
969 | * This function will insert copies of the data in the |
970 | * initializer_list @a __il into the %forward_list before the location |
971 | * specified by @a __pos. |
972 | * |
973 | * This operation is linear in the number of elements inserted and |
974 | * does not invalidate iterators and references. |
975 | */ |
976 | iterator |
977 | insert_after(const_iterator __pos, std::initializer_list<_Tp> __il) |
978 | { return insert_after(__pos, __il.begin(), __il.end()); } |
979 | |
980 | /** |
981 | * @brief Removes the element pointed to by the iterator following |
982 | * @c pos. |
983 | * @param __pos Iterator pointing before element to be erased. |
984 | * @return An iterator pointing to the element following the one |
985 | * that was erased, or end() if no such element exists. |
986 | * |
987 | * This function will erase the element at the given position and |
988 | * thus shorten the %forward_list by one. |
989 | * |
990 | * Due to the nature of a %forward_list this operation can be done |
991 | * in constant time, and only invalidates iterators/references to |
992 | * the element being removed. The user is also cautioned that |
993 | * this function only erases the element, and that if the element |
994 | * is itself a pointer, the pointed-to memory is not touched in |
995 | * any way. Managing the pointer is the user's responsibility. |
996 | */ |
997 | iterator |
998 | erase_after(const_iterator __pos) |
999 | { return iterator(this->_M_erase_after(const_cast<_Node_base*> |
1000 | (__pos._M_node))); } |
1001 | |
1002 | /** |
1003 | * @brief Remove a range of elements. |
1004 | * @param __pos Iterator pointing before the first element to be |
1005 | * erased. |
1006 | * @param __last Iterator pointing to one past the last element to be |
1007 | * erased. |
1008 | * @return @ __last. |
1009 | * |
1010 | * This function will erase the elements in the range |
1011 | * @a (__pos,__last) and shorten the %forward_list accordingly. |
1012 | * |
1013 | * This operation is linear time in the size of the range and only |
1014 | * invalidates iterators/references to the element being removed. |
1015 | * The user is also cautioned that this function only erases the |
1016 | * elements, and that if the elements themselves are pointers, the |
1017 | * pointed-to memory is not touched in any way. Managing the pointer |
1018 | * is the user's responsibility. |
1019 | */ |
1020 | iterator |
1021 | erase_after(const_iterator __pos, const_iterator __last) |
1022 | { return iterator(this->_M_erase_after(const_cast<_Node_base*> |
1023 | (__pos._M_node), |
1024 | const_cast<_Node_base*> |
1025 | (__last._M_node))); } |
1026 | |
1027 | /** |
1028 | * @brief Swaps data with another %forward_list. |
1029 | * @param __list A %forward_list of the same element and allocator |
1030 | * types. |
1031 | * |
1032 | * This exchanges the elements between two lists in constant |
1033 | * time. Note that the global std::swap() function is |
1034 | * specialized such that std::swap(l1,l2) will feed to this |
1035 | * function. |
1036 | * |
1037 | * Whether the allocators are swapped depends on the allocator traits. |
1038 | */ |
1039 | void |
1040 | swap(forward_list& __list) noexcept |
1041 | { |
1042 | std::swap(this->_M_impl._M_head._M_next, |
1043 | __list._M_impl._M_head._M_next); |
1044 | _Node_alloc_traits::_S_on_swap(this->_M_get_Node_allocator(), |
1045 | __list._M_get_Node_allocator()); |
1046 | } |
1047 | |
1048 | /** |
1049 | * @brief Resizes the %forward_list to the specified number of |
1050 | * elements. |
1051 | * @param __sz Number of elements the %forward_list should contain. |
1052 | * |
1053 | * This function will %resize the %forward_list to the specified |
1054 | * number of elements. If the number is smaller than the |
1055 | * %forward_list's current number of elements the %forward_list |
1056 | * is truncated, otherwise the %forward_list is extended and the |
1057 | * new elements are default constructed. |
1058 | */ |
1059 | void |
1060 | resize(size_type __sz); |
1061 | |
1062 | /** |
1063 | * @brief Resizes the %forward_list to the specified number of |
1064 | * elements. |
1065 | * @param __sz Number of elements the %forward_list should contain. |
1066 | * @param __val Data with which new elements should be populated. |
1067 | * |
1068 | * This function will %resize the %forward_list to the specified |
1069 | * number of elements. If the number is smaller than the |
1070 | * %forward_list's current number of elements the %forward_list |
1071 | * is truncated, otherwise the %forward_list is extended and new |
1072 | * elements are populated with given data. |
1073 | */ |
1074 | void |
1075 | resize(size_type __sz, const value_type& __val); |
1076 | |
1077 | /** |
1078 | * @brief Erases all the elements. |
1079 | * |
1080 | * Note that this function only erases |
1081 | * the elements, and that if the elements themselves are |
1082 | * pointers, the pointed-to memory is not touched in any way. |
1083 | * Managing the pointer is the user's responsibility. |
1084 | */ |
1085 | void |
1086 | clear() noexcept |
1087 | { this->_M_erase_after(&this->_M_impl._M_head, nullptr); } |
1088 | |
1089 | // 23.3.4.6 forward_list operations: |
1090 | |
1091 | /** |
1092 | * @brief Insert contents of another %forward_list. |
1093 | * @param __pos Iterator referencing the element to insert after. |
1094 | * @param __list Source list. |
1095 | * |
1096 | * The elements of @a list are inserted in constant time after |
1097 | * the element referenced by @a pos. @a list becomes an empty |
1098 | * list. |
1099 | * |
1100 | * Requires this != @a x. |
1101 | */ |
1102 | void |
1103 | splice_after(const_iterator __pos, forward_list&& __list) noexcept |
1104 | { |
1105 | if (!__list.empty()) |
1106 | _M_splice_after(__pos, before: __list.before_begin(), last: __list.end()); |
1107 | } |
1108 | |
1109 | void |
1110 | splice_after(const_iterator __pos, forward_list& __list) noexcept |
1111 | { splice_after(__pos, std::move(__list)); } |
1112 | |
1113 | /** |
1114 | * @brief Insert element from another %forward_list. |
1115 | * @param __pos Iterator referencing the element to insert after. |
1116 | * @param __list Source list. |
1117 | * @param __i Iterator referencing the element before the element |
1118 | * to move. |
1119 | * |
1120 | * Removes the element in list @a list referenced by @a i and |
1121 | * inserts it into the current list after @a pos. |
1122 | */ |
1123 | void |
1124 | splice_after(const_iterator __pos, forward_list&& __list, |
1125 | const_iterator __i) noexcept; |
1126 | |
1127 | void |
1128 | splice_after(const_iterator __pos, forward_list& __list, |
1129 | const_iterator __i) noexcept |
1130 | { splice_after(__pos, std::move(__list), __i); } |
1131 | |
1132 | /** |
1133 | * @brief Insert range from another %forward_list. |
1134 | * @param __pos Iterator referencing the element to insert after. |
1135 | * @param __list Source list. |
1136 | * @param __before Iterator referencing before the start of range |
1137 | * in list. |
1138 | * @param __last Iterator referencing the end of range in list. |
1139 | * |
1140 | * Removes elements in the range (__before,__last) and inserts them |
1141 | * after @a __pos in constant time. |
1142 | * |
1143 | * Undefined if @a __pos is in (__before,__last). |
1144 | * @{ |
1145 | */ |
1146 | void |
1147 | splice_after(const_iterator __pos, forward_list&&, |
1148 | const_iterator __before, const_iterator __last) noexcept |
1149 | { _M_splice_after(__pos, __before, __last); } |
1150 | |
1151 | void |
1152 | splice_after(const_iterator __pos, forward_list&, |
1153 | const_iterator __before, const_iterator __last) noexcept |
1154 | { _M_splice_after(__pos, __before, __last); } |
1155 | /// @} |
1156 | |
1157 | private: |
1158 | #if __cplusplus > 201703L |
1159 | # define __cpp_lib_list_remove_return_type 201806L |
1160 | using __remove_return_type = size_type; |
1161 | # define _GLIBCXX_FWDLIST_REMOVE_RETURN_TYPE_TAG \ |
1162 | __attribute__((__abi_tag__("__cxx20"))) |
1163 | #else |
1164 | using __remove_return_type = void; |
1165 | # define _GLIBCXX_FWDLIST_REMOVE_RETURN_TYPE_TAG |
1166 | #endif |
1167 | public: |
1168 | |
1169 | /** |
1170 | * @brief Remove all elements equal to value. |
1171 | * @param __val The value to remove. |
1172 | * |
1173 | * Removes every element in the list equal to @a __val. |
1174 | * Remaining elements stay in list order. Note that this |
1175 | * function only erases the elements, and that if the elements |
1176 | * themselves are pointers, the pointed-to memory is not |
1177 | * touched in any way. Managing the pointer is the user's |
1178 | * responsibility. |
1179 | */ |
1180 | _GLIBCXX_FWDLIST_REMOVE_RETURN_TYPE_TAG |
1181 | __remove_return_type |
1182 | remove(const _Tp& __val); |
1183 | |
1184 | /** |
1185 | * @brief Remove all elements satisfying a predicate. |
1186 | * @param __pred Unary predicate function or object. |
1187 | * |
1188 | * Removes every element in the list for which the predicate |
1189 | * returns true. Remaining elements stay in list order. Note |
1190 | * that this function only erases the elements, and that if the |
1191 | * elements themselves are pointers, the pointed-to memory is |
1192 | * not touched in any way. Managing the pointer is the user's |
1193 | * responsibility. |
1194 | */ |
1195 | template<typename _Pred> |
1196 | __remove_return_type |
1197 | remove_if(_Pred __pred); |
1198 | |
1199 | /** |
1200 | * @brief Remove consecutive duplicate elements. |
1201 | * |
1202 | * For each consecutive set of elements with the same value, |
1203 | * remove all but the first one. Remaining elements stay in |
1204 | * list order. Note that this function only erases the |
1205 | * elements, and that if the elements themselves are pointers, |
1206 | * the pointed-to memory is not touched in any way. Managing |
1207 | * the pointer is the user's responsibility. |
1208 | */ |
1209 | _GLIBCXX_FWDLIST_REMOVE_RETURN_TYPE_TAG |
1210 | __remove_return_type |
1211 | unique() |
1212 | { return unique(std::equal_to<_Tp>()); } |
1213 | |
1214 | #undef _GLIBCXX_FWDLIST_REMOVE_RETURN_TYPE_TAG |
1215 | |
1216 | /** |
1217 | * @brief Remove consecutive elements satisfying a predicate. |
1218 | * @param __binary_pred Binary predicate function or object. |
1219 | * |
1220 | * For each consecutive set of elements [first,last) that |
1221 | * satisfy predicate(first,i) where i is an iterator in |
1222 | * [first,last), remove all but the first one. Remaining |
1223 | * elements stay in list order. Note that this function only |
1224 | * erases the elements, and that if the elements themselves are |
1225 | * pointers, the pointed-to memory is not touched in any way. |
1226 | * Managing the pointer is the user's responsibility. |
1227 | */ |
1228 | template<typename _BinPred> |
1229 | __remove_return_type |
1230 | unique(_BinPred __binary_pred); |
1231 | |
1232 | /** |
1233 | * @brief Merge sorted lists. |
1234 | * @param __list Sorted list to merge. |
1235 | * |
1236 | * Assumes that both @a list and this list are sorted according to |
1237 | * operator<(). Merges elements of @a __list into this list in |
1238 | * sorted order, leaving @a __list empty when complete. Elements in |
1239 | * this list precede elements in @a __list that are equal. |
1240 | */ |
1241 | void |
1242 | merge(forward_list&& __list) |
1243 | { merge(std::move(__list), std::less<_Tp>()); } |
1244 | |
1245 | void |
1246 | merge(forward_list& __list) |
1247 | { merge(std::move(__list)); } |
1248 | |
1249 | /** |
1250 | * @brief Merge sorted lists according to comparison function. |
1251 | * @param __list Sorted list to merge. |
1252 | * @param __comp Comparison function defining sort order. |
1253 | * |
1254 | * Assumes that both @a __list and this list are sorted according to |
1255 | * comp. Merges elements of @a __list into this list |
1256 | * in sorted order, leaving @a __list empty when complete. Elements |
1257 | * in this list precede elements in @a __list that are equivalent |
1258 | * according to comp(). |
1259 | */ |
1260 | template<typename _Comp> |
1261 | void |
1262 | merge(forward_list&& __list, _Comp __comp); |
1263 | |
1264 | template<typename _Comp> |
1265 | void |
1266 | merge(forward_list& __list, _Comp __comp) |
1267 | { merge(std::move(__list), __comp); } |
1268 | |
1269 | /** |
1270 | * @brief Sort the elements of the list. |
1271 | * |
1272 | * Sorts the elements of this list in NlogN time. Equivalent |
1273 | * elements remain in list order. |
1274 | */ |
1275 | void |
1276 | sort() |
1277 | { sort(std::less<_Tp>()); } |
1278 | |
1279 | /** |
1280 | * @brief Sort the forward_list using a comparison function. |
1281 | * |
1282 | * Sorts the elements of this list in NlogN time. Equivalent |
1283 | * elements remain in list order. |
1284 | */ |
1285 | template<typename _Comp> |
1286 | void |
1287 | sort(_Comp __comp); |
1288 | |
1289 | /** |
1290 | * @brief Reverse the elements in list. |
1291 | * |
1292 | * Reverse the order of elements in the list in linear time. |
1293 | */ |
1294 | void |
1295 | reverse() noexcept |
1296 | { this->_M_impl._M_head._M_reverse_after(); } |
1297 | |
1298 | private: |
1299 | // Called by the range constructor to implement [23.3.4.2]/9 |
1300 | template<typename _InputIterator> |
1301 | void |
1302 | _M_range_initialize(_InputIterator __first, _InputIterator __last); |
1303 | |
1304 | // Called by forward_list(n,v,a), and the range constructor when it |
1305 | // turns out to be the same thing. |
1306 | void |
1307 | _M_fill_initialize(size_type __n, const value_type& __value); |
1308 | |
1309 | // Called by splice_after and insert_after. |
1310 | iterator |
1311 | _M_splice_after(const_iterator __pos, const_iterator __before, |
1312 | const_iterator __last); |
1313 | |
1314 | // Called by forward_list(n). |
1315 | void |
1316 | _M_default_initialize(size_type __n); |
1317 | |
1318 | // Called by resize(sz). |
1319 | void |
1320 | _M_default_insert_after(const_iterator __pos, size_type __n); |
1321 | |
1322 | // Called by operator=(forward_list&&) |
1323 | void |
1324 | _M_move_assign(forward_list&& __list, true_type) noexcept |
1325 | { |
1326 | clear(); |
1327 | this->_M_impl._M_head._M_next = __list._M_impl._M_head._M_next; |
1328 | __list._M_impl._M_head._M_next = nullptr; |
1329 | std::__alloc_on_move(this->_M_get_Node_allocator(), |
1330 | __list._M_get_Node_allocator()); |
1331 | } |
1332 | |
1333 | // Called by operator=(forward_list&&) |
1334 | void |
1335 | _M_move_assign(forward_list&& __list, false_type) |
1336 | { |
1337 | if (__list._M_get_Node_allocator() == this->_M_get_Node_allocator()) |
1338 | _M_move_assign(std::move(__list), true_type()); |
1339 | else |
1340 | // The rvalue's allocator cannot be moved, or is not equal, |
1341 | // so we need to individually move each element. |
1342 | this->assign(std::make_move_iterator(__list.begin()), |
1343 | std::make_move_iterator(__list.end())); |
1344 | } |
1345 | |
1346 | // Called by assign(_InputIterator, _InputIterator) if _Tp is |
1347 | // CopyAssignable. |
1348 | template<typename _InputIterator> |
1349 | void |
1350 | _M_assign(_InputIterator __first, _InputIterator __last, true_type) |
1351 | { |
1352 | auto __prev = before_begin(); |
1353 | auto __curr = begin(); |
1354 | auto __end = end(); |
1355 | while (__curr != __end && __first != __last) |
1356 | { |
1357 | *__curr = *__first; |
1358 | ++__prev; |
1359 | ++__curr; |
1360 | ++__first; |
1361 | } |
1362 | if (__first != __last) |
1363 | insert_after(__prev, __first, __last); |
1364 | else if (__curr != __end) |
1365 | erase_after(__prev, __end); |
1366 | } |
1367 | |
1368 | // Called by assign(_InputIterator, _InputIterator) if _Tp is not |
1369 | // CopyAssignable. |
1370 | template<typename _InputIterator> |
1371 | void |
1372 | _M_assign(_InputIterator __first, _InputIterator __last, false_type) |
1373 | { |
1374 | clear(); |
1375 | insert_after(cbefore_begin(), __first, __last); |
1376 | } |
1377 | |
1378 | // Called by assign(size_type, const _Tp&) if Tp is CopyAssignable |
1379 | void |
1380 | _M_assign_n(size_type __n, const _Tp& __val, true_type) |
1381 | { |
1382 | auto __prev = before_begin(); |
1383 | auto __curr = begin(); |
1384 | auto __end = end(); |
1385 | while (__curr != __end && __n > 0) |
1386 | { |
1387 | *__curr = __val; |
1388 | ++__prev; |
1389 | ++__curr; |
1390 | --__n; |
1391 | } |
1392 | if (__n > 0) |
1393 | insert_after(__prev, __n, __val); |
1394 | else if (__curr != __end) |
1395 | erase_after(__prev, __end); |
1396 | } |
1397 | |
1398 | // Called by assign(size_type, const _Tp&) if Tp is non-CopyAssignable |
1399 | void |
1400 | _M_assign_n(size_type __n, const _Tp& __val, false_type) |
1401 | { |
1402 | clear(); |
1403 | insert_after(cbefore_begin(), __n, __val); |
1404 | } |
1405 | }; |
1406 | |
1407 | #if __cpp_deduction_guides >= 201606 |
1408 | template<typename _InputIterator, typename _ValT |
1409 | = typename iterator_traits<_InputIterator>::value_type, |
1410 | typename _Allocator = allocator<_ValT>, |
1411 | typename = _RequireInputIter<_InputIterator>, |
1412 | typename = _RequireAllocator<_Allocator>> |
1413 | forward_list(_InputIterator, _InputIterator, _Allocator = _Allocator()) |
1414 | -> forward_list<_ValT, _Allocator>; |
1415 | #endif |
1416 | |
1417 | /** |
1418 | * @brief Forward list equality comparison. |
1419 | * @param __lx A %forward_list |
1420 | * @param __ly A %forward_list of the same type as @a __lx. |
1421 | * @return True iff the elements of the forward lists are equal. |
1422 | * |
1423 | * This is an equivalence relation. It is linear in the number of |
1424 | * elements of the forward lists. Deques are considered equivalent |
1425 | * if corresponding elements compare equal. |
1426 | */ |
1427 | template<typename _Tp, typename _Alloc> |
1428 | bool |
1429 | operator==(const forward_list<_Tp, _Alloc>& __lx, |
1430 | const forward_list<_Tp, _Alloc>& __ly); |
1431 | |
1432 | #if __cpp_lib_three_way_comparison |
1433 | /** |
1434 | * @brief Forward list ordering relation. |
1435 | * @param __x A `forward_list`. |
1436 | * @param __y A `forward_list` of the same type as `__x`. |
1437 | * @return A value indicating whether `__x` is less than, equal to, |
1438 | * greater than, or incomparable with `__y`. |
1439 | * |
1440 | * See `std::lexicographical_compare_three_way()` for how the determination |
1441 | * is made. This operator is used to synthesize relational operators like |
1442 | * `<` and `>=` etc. |
1443 | */ |
1444 | template<typename _Tp, typename _Alloc> |
1445 | inline __detail::__synth3way_t<_Tp> |
1446 | operator<=>(const forward_list<_Tp, _Alloc>& __x, |
1447 | const forward_list<_Tp, _Alloc>& __y) |
1448 | { |
1449 | return std::lexicographical_compare_three_way(__x.begin(), __x.end(), |
1450 | __y.begin(), __y.end(), |
1451 | __detail::__synth3way); |
1452 | } |
1453 | #else |
1454 | /** |
1455 | * @brief Forward list ordering relation. |
1456 | * @param __lx A %forward_list. |
1457 | * @param __ly A %forward_list of the same type as @a __lx. |
1458 | * @return True iff @a __lx is lexicographically less than @a __ly. |
1459 | * |
1460 | * This is a total ordering relation. It is linear in the number of |
1461 | * elements of the forward lists. The elements must be comparable |
1462 | * with @c <. |
1463 | * |
1464 | * See std::lexicographical_compare() for how the determination is made. |
1465 | */ |
1466 | template<typename _Tp, typename _Alloc> |
1467 | inline bool |
1468 | operator<(const forward_list<_Tp, _Alloc>& __lx, |
1469 | const forward_list<_Tp, _Alloc>& __ly) |
1470 | { return std::lexicographical_compare(__lx.cbegin(), __lx.cend(), |
1471 | __ly.cbegin(), __ly.cend()); } |
1472 | |
1473 | /// Based on operator== |
1474 | template<typename _Tp, typename _Alloc> |
1475 | inline bool |
1476 | operator!=(const forward_list<_Tp, _Alloc>& __lx, |
1477 | const forward_list<_Tp, _Alloc>& __ly) |
1478 | { return !(__lx == __ly); } |
1479 | |
1480 | /// Based on operator< |
1481 | template<typename _Tp, typename _Alloc> |
1482 | inline bool |
1483 | operator>(const forward_list<_Tp, _Alloc>& __lx, |
1484 | const forward_list<_Tp, _Alloc>& __ly) |
1485 | { return (__ly < __lx); } |
1486 | |
1487 | /// Based on operator< |
1488 | template<typename _Tp, typename _Alloc> |
1489 | inline bool |
1490 | operator>=(const forward_list<_Tp, _Alloc>& __lx, |
1491 | const forward_list<_Tp, _Alloc>& __ly) |
1492 | { return !(__lx < __ly); } |
1493 | |
1494 | /// Based on operator< |
1495 | template<typename _Tp, typename _Alloc> |
1496 | inline bool |
1497 | operator<=(const forward_list<_Tp, _Alloc>& __lx, |
1498 | const forward_list<_Tp, _Alloc>& __ly) |
1499 | { return !(__ly < __lx); } |
1500 | #endif // three-way comparison |
1501 | |
1502 | /// See std::forward_list::swap(). |
1503 | template<typename _Tp, typename _Alloc> |
1504 | inline void |
1505 | swap(forward_list<_Tp, _Alloc>& __lx, |
1506 | forward_list<_Tp, _Alloc>& __ly) |
1507 | noexcept(noexcept(__lx.swap(__ly))) |
1508 | { __lx.swap(__ly); } |
1509 | |
1510 | _GLIBCXX_END_NAMESPACE_CONTAINER |
1511 | _GLIBCXX_END_NAMESPACE_VERSION |
1512 | } // namespace std |
1513 | |
1514 | #endif // _FORWARD_LIST_H |
1515 | |