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