forward_list.h source code [include/c++/7/bits/forward

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>
36	#include <bits/stl_iterator_base_types.h>
37	#include <bits/stl_iterator.h>
38	#include <bits/stl_algobase.h>
39	#include <bits/stl_function.h>
40	#include <bits/allocator.h>
41	#include <ext/alloc_traits.h>
42	#include <ext/aligned_buffer.h>
43
44	namespace std _GLIBCXX_VISIBILITY(default)
45	{
46	_GLIBCXX_BEGIN_NAMESPACE_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 __alloc_rebind<_Alloc, _Fwd_list_node<_Tp>> _Node_alloc_type;
278	typedef __gnu_cxx::__alloc_traits<_Node_alloc_type> _Node_alloc_traits;
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:
301	typedef _Fwd_list_iterator<_Tp> iterator;
302	typedef _Fwd_list_const_iterator<_Tp> const_iterator;
303	typedef _Fwd_list_node<_Tp> _Node;
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
313	_Fwd_list_base()
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
321	_Fwd_list_base(_Fwd_list_base&& __lst)
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
328	~_Fwd_list_base()
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>
361	_Fwd_list_node_base*
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
372	_Fwd_list_node_base*
373	_M_erase_after(_Fwd_list_node_base* __pos);
374
375	_Fwd_list_node_base*
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:
410	typedef _Fwd_list_base<_Tp, _Alloc> _Base;
411	typedef _Fwd_list_node<_Tp> _Node;
412	typedef _Fwd_list_node_base _Node_base;
413	typedef typename _Base::_Node_alloc_type _Node_alloc_type;
414	typedef typename _Base::_Node_alloc_traits _Node_alloc_traits;
415	typedef allocator_traits<__alloc_rebind<_Alloc, _Tp>> _Alloc_traits;
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
425	typedef _Fwd_list_iterator<_Tp> iterator;
426	typedef _Fwd_list_const_iterator<_Tp> const_iterator;
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	*/
436	forward_list()
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.
471	insert_after(cbefore_begin(),
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	*/
525	forward_list(const forward_list& __list)
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	*/
550	forward_list(std::initializer_list<_Tp> __il,
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	*/
570	forward_list&
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	*/
585	forward_list&
586	operator=(forward_list&& __list)
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	*/
604	forward_list&
605	operator=(std::initializer_list<_Tp> __il)
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
655	assign(std::initializer_list<_Tp> __il)
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	*/
669	iterator
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	*/
686	iterator
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	*/
704	iterator
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
766	front()
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 modiﬁers:
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
845	pop_front()
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>
862	iterator
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	*/
879	iterator
880	insert_after(const_iterator __pos, const _Tp& __val)
881	{ return iterator(this->_M_insert_after(__pos, __val)); }
882
883	/**
884	*
885	*/
886	iterator
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
945	insert_after(const_iterator __pos, std::initializer_list<_Tp> __il)
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	*/
965	iterator
966	erase_after(const_iterator __pos)
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	*/
988	iterator
989	erase_after(const_iterator __pos, const_iterator __last)
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
1115	splice_after(const_iterator __pos, forward_list&&,
1116	const_iterator __before, const_iterator __last) noexcept
1117	{ _M_splice_after(__pos, __before, __last); }
1118
1119	void
1120	splice_after(const_iterator __pos, forward_list&,
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
1165	unique()
1166	{ unique(std::equal_to<_Tp>()); }
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
1194	merge(forward_list&& __list)
1195	{ merge(std::move(__list), std::less<_Tp>()); }
1196
1197	void
1198	merge(forward_list& __list)
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
1228	sort()
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
1424	swap(forward_list<_Tp, _Alloc>& __lx,
1425	forward_list<_Tp, _Alloc>& __ly)
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
1433