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