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