stl_list.h source code [include/c++/7/bits/stl

1	// List implementation -- C++ --
2
3	// Copyright (C) 2001-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	/*
26	*
27	* Copyright (c) 1994
28	* Hewlett-Packard Company
29	*
30	* Permission to use, copy, modify, distribute and sell this software
31	* and its documentation for any purpose is hereby granted without fee,
32	* provided that the above copyright notice appear in all copies and
33	* that both that copyright notice and this permission notice appear
34	* in supporting documentation. Hewlett-Packard Company makes no
35	* representations about the suitability of this software for any
36	* purpose. It is provided "as is" without express or implied warranty.
37	*
38	*
39	* Copyright (c) 1996,1997
40	* Silicon Graphics Computer Systems, Inc.
41	*
42	* Permission to use, copy, modify, distribute and sell this software
43	* and its documentation for any purpose is hereby granted without fee,
44	* provided that the above copyright notice appear in all copies and
45	* that both that copyright notice and this permission notice appear
46	* in supporting documentation. Silicon Graphics makes no
47	* representations about the suitability of this software for any
48	* purpose. It is provided "as is" without express or implied warranty.
49	*/
50
51	/** @file bits/stl_list.h
52	* This is an internal header file, included by other library headers.
53	* Do not attempt to use it directly. @headername{list}
54	*/
55
56	#ifndef _STL_LIST_H
57	#define _STL_LIST_H 1
58
59	#include <bits/concept_check.h>
60	#include <ext/alloc_traits.h>
61	#if __cplusplus >= 201103L
62	#include <initializer_list>
63	#include <bits/allocated_ptr.h>
64	#include <ext/aligned_buffer.h>
65	#endif
66
67	namespace std _GLIBCXX_VISIBILITY(default)
68	{
69	namespace __detail
70	{
71	_GLIBCXX_BEGIN_NAMESPACE_VERSION
72
73	// Supporting structures are split into common and templated
74	// types; the latter publicly inherits from the former in an
75	// effort to reduce code duplication. This results in some
76	// "needless" static_cast'ing later on, but it's all safe
77	// downcasting.
78
79	/// Common part of a node in the %list.
80	struct _List_node_base
81	{
82	_List_node_base* _M_next;
83	_List_node_base* _M_prev;
84
85	static void
86	swap(_List_node_base& __x, _List_node_base& __y) _GLIBCXX_USE_NOEXCEPT;
87
88	void
89	_M_transfer(_List_node_base* const __first,
90	_List_node_base* const __last) _GLIBCXX_USE_NOEXCEPT;
91
92	void
93	_M_reverse() _GLIBCXX_USE_NOEXCEPT;
94
95	void
96	_M_hook(_List_node_base* const __position) _GLIBCXX_USE_NOEXCEPT;
97
98	void
99	_M_unhook() _GLIBCXX_USE_NOEXCEPT;
100	};
101
102	_GLIBCXX_END_NAMESPACE_VERSION
103	} // namespace detail
104
105	_GLIBCXX_BEGIN_NAMESPACE_CONTAINER
106
107	/// An actual node in the %list.
108	template<typename _Tp>
109	struct _List_node : public __detail::_List_node_base
110	{
111	#if __cplusplus >= 201103L
112	__gnu_cxx::__aligned_membuf<_Tp> _M_storage;
113	_Tp* _M_valptr() { return _M_storage._M_ptr(); }
114	_Tp const* _M_valptr() const { return _M_storage._M_ptr(); }
115	#else
116	_Tp _M_data;
117	_Tp* _M_valptr() { return std::__addressof(_M_data); }
118	_Tp const* _M_valptr() const { return std::__addressof(_M_data); }
119	#endif
120	};
121
122	/**
123	* @brief A list::iterator.
124	*
125	* All the functions are op overloads.
126	*/
127	template<typename _Tp>
128	struct _List_iterator
129	{
130	typedef _List_iterator<_Tp> _Self;
131	typedef _List_node<_Tp> _Node;
132
133	typedef ptrdiff_t difference_type;
134	typedef std::bidirectional_iterator_tag iterator_category;
135	typedef _Tp value_type;
136	typedef _Tp* pointer;
137	typedef _Tp& reference;
138
139	_List_iterator() _GLIBCXX_NOEXCEPT
140	: _M_node() { }
141
142	explicit
143	_List_iterator(__detail::_List_node_base* __x) _GLIBCXX_NOEXCEPT
144	: _M_node(__x) { }
145
146	_Self
147	_M_const_cast() const _GLIBCXX_NOEXCEPT
148	{ return *this; }
149
150	// Must downcast from _List_node_base to _List_node to get to value.
151	reference
152	operator*() const _GLIBCXX_NOEXCEPT
153	{ return static_cast<_Node>(_M_node)->_M_valptr(); }
154
155	pointer
156	operator->() const _GLIBCXX_NOEXCEPT
157	{ return static_cast<_Node*>(_M_node)->_M_valptr(); }
158
159	_Self&
160	operator++() _GLIBCXX_NOEXCEPT
161	{
162	_M_node = _M_node->_M_next;
163	return *this;
164	}
165
166	_Self
167	operator++(int) _GLIBCXX_NOEXCEPT
168	{
169	_Self __tmp = *this;
170	_M_node = _M_node->_M_next;
171	return __tmp;
172	}
173
174	_Self&
175	operator--() _GLIBCXX_NOEXCEPT
176	{
177	_M_node = _M_node->_M_prev;
178	return *this;
179	}
180
181	_Self
182	operator--(int) _GLIBCXX_NOEXCEPT
183	{
184	_Self __tmp = *this;
185	_M_node = _M_node->_M_prev;
186	return __tmp;
187	}
188
189	bool
190	operator==(const _Self& __x) const _GLIBCXX_NOEXCEPT
191	{ return _M_node == __x._M_node; }
192
193	bool
194	operator!=(const _Self& __x) const _GLIBCXX_NOEXCEPT
195	{ return _M_node != __x._M_node; }
196
197	// The only member points to the %list element.
198	__detail::_List_node_base* _M_node;
199	};
200
201	/**
202	* @brief A list::const_iterator.
203	*
204	* All the functions are op overloads.
205	*/
206	template<typename _Tp>
207	struct _List_const_iterator
208	{
209	typedef _List_const_iterator<_Tp> _Self;
210	typedef const _List_node<_Tp> _Node;
211	typedef _List_iterator<_Tp> iterator;
212
213	typedef ptrdiff_t difference_type;
214	typedef std::bidirectional_iterator_tag iterator_category;
215	typedef _Tp value_type;
216	typedef const _Tp* pointer;
217	typedef const _Tp& reference;
218
219	_List_const_iterator() _GLIBCXX_NOEXCEPT
220	: _M_node() { }
221
222	explicit
223	_List_const_iterator(const __detail::_List_node_base* __x)
224	_GLIBCXX_NOEXCEPT
225	: _M_node(__x) { }
226
227	_List_const_iterator(const iterator& __x) _GLIBCXX_NOEXCEPT
228	: _M_node(__x._M_node) { }
229
230	iterator
231	_M_const_cast() const _GLIBCXX_NOEXCEPT
232	{ return iterator(const_cast<__detail::_List_node_base*>(_M_node)); }
233
234	// Must downcast from List_node_base to _List_node to get to value.
235	reference
236	operator*() const _GLIBCXX_NOEXCEPT
237	{ return static_cast<_Node>(_M_node)->_M_valptr(); }
238
239	pointer
240	operator->() const _GLIBCXX_NOEXCEPT
241	{ return static_cast<_Node*>(_M_node)->_M_valptr(); }
242
243	_Self&
244	operator++() _GLIBCXX_NOEXCEPT
245	{
246	_M_node = _M_node->_M_next;
247	return *this;
248	}
249
250	_Self
251	operator++(int) _GLIBCXX_NOEXCEPT
252	{
253	_Self __tmp = *this;
254	_M_node = _M_node->_M_next;
255	return __tmp;
256	}
257
258	_Self&
259	operator--() _GLIBCXX_NOEXCEPT
260	{
261	_M_node = _M_node->_M_prev;
262	return *this;
263	}
264
265	_Self
266	operator--(int) _GLIBCXX_NOEXCEPT
267	{
268	_Self __tmp = *this;
269	_M_node = _M_node->_M_prev;
270	return __tmp;
271	}
272
273	bool
274	operator==(const _Self& __x) const _GLIBCXX_NOEXCEPT
275	{ return _M_node == __x._M_node; }
276
277	bool
278	operator!=(const _Self& __x) const _GLIBCXX_NOEXCEPT
279	{ return _M_node != __x._M_node; }
280
281	// The only member points to the %list element.
282	const __detail::_List_node_base* _M_node;
283	};
284
285	template<typename _Val>
286	inline bool
287	operator==(const _List_iterator<_Val>& __x,
288	const _List_const_iterator<_Val>& __y) _GLIBCXX_NOEXCEPT
289	{ return __x._M_node == __y._M_node; }
290
291	template<typename _Val>
292	inline bool
293	operator!=(const _List_iterator<_Val>& __x,
294	const _List_const_iterator<_Val>& __y) _GLIBCXX_NOEXCEPT
295	{ return __x._M_node != __y._M_node; }
296
297	_GLIBCXX_BEGIN_NAMESPACE_CXX11
298	/// See bits/stl_deque.h's _Deque_base for an explanation.
299	template<typename _Tp, typename _Alloc>
300	class _List_base
301	{
302	protected:
303	typedef typename __gnu_cxx::__alloc_traits<_Alloc>::template
304	rebind<_Tp>::other _Tp_alloc_type;
305	typedef __gnu_cxx::__alloc_traits<_Tp_alloc_type> _Tp_alloc_traits;
306	typedef typename _Tp_alloc_traits::template
307	rebind<_List_node<_Tp> >::other _Node_alloc_type;
308	typedef __gnu_cxx::__alloc_traits<_Node_alloc_type> _Node_alloc_traits;
309
310	static size_t
311	_S_distance(const __detail::_List_node_base* __first,
312	const __detail::_List_node_base* __last)
313	{
314	size_t __n = 0;
315	while (__first != __last)
316	{
317	__first = __first->_M_next;
318	++__n;
319	}
320	return __n;
321	}
322
323	struct _List_impl
324	: public _Node_alloc_type
325	{
326	#if _GLIBCXX_USE_CXX11_ABI
327	_List_node<size_t> _M_node;
328	#else
329	__detail::_List_node_base _M_node;
330	#endif
331
332	_List_impl() _GLIBCXX_NOEXCEPT
333	: _Node_alloc_type(), _M_node()
334	{ }
335
336	_List_impl(const _Node_alloc_type& __a) _GLIBCXX_NOEXCEPT
337	: _Node_alloc_type(__a), _M_node()
338	{ }
339
340	#if __cplusplus >= 201103L
341	_List_impl(_Node_alloc_type&& __a) noexcept
342	: _Node_alloc_type(std::move(__a)), _M_node()
343	{ }
344	#endif
345	};
346
347	_List_impl _M_impl;
348
349	#if _GLIBCXX_USE_CXX11_ABI
350	size_t _M_get_size() const { return *_M_impl._M_node._M_valptr(); }
351
352	void _M_set_size(size_t __n) { *_M_impl._M_node._M_valptr() = __n; }
353
354	void _M_inc_size(size_t __n) { *_M_impl._M_node._M_valptr() += __n; }
355
356	void _M_dec_size(size_t __n) { *_M_impl._M_node._M_valptr() -= __n; }
357
358	size_t
359	_M_distance(const __detail::_List_node_base* __first,
360	const __detail::_List_node_base* __last) const
361	{ return _S_distance(__first, __last); }
362
363	// return the stored size
364	size_t _M_node_count() const { return *_M_impl._M_node._M_valptr(); }
365	#else
366	// dummy implementations used when the size is not stored
367	size_t _M_get_size() const { return 0; }
368	void _M_set_size(size_t) { }
369	void _M_inc_size(size_t) { }
370	void _M_dec_size(size_t) { }
371	size_t _M_distance(const void, const void) const { return 0; }
372
373	// count the number of nodes
374	size_t _M_node_count() const
375	{
376	return _S_distance(_M_impl._M_node._M_next,
377	std::__addressof(_M_impl._M_node));
378	}
379	#endif
380
381	typename _Node_alloc_traits::pointer
382	_M_get_node()
383	{ return _Node_alloc_traits::allocate(_M_impl, 1); }
384
385	void
386	_M_put_node(typename _Node_alloc_traits::pointer __p) _GLIBCXX_NOEXCEPT
387	{ _Node_alloc_traits::deallocate(_M_impl, __p, 1); }
388
389	public:
390	typedef _Alloc allocator_type;
391
392	_Node_alloc_type&
393	_M_get_Node_allocator() _GLIBCXX_NOEXCEPT
394	{ return _M_impl; }
395
396	const _Node_alloc_type&
397	_M_get_Node_allocator() const _GLIBCXX_NOEXCEPT
398	{ return _M_impl; }
399
400	_List_base()
401	: _M_impl()
402	{ _M_init(); }
403
404	_List_base(const _Node_alloc_type& __a) _GLIBCXX_NOEXCEPT
405	: _M_impl(__a)
406	{ _M_init(); }
407
408	#if __cplusplus >= 201103L
409	_List_base(_List_base&& __x) noexcept
410	: _M_impl(std::move(__x._M_get_Node_allocator()))
411	{ _M_move_nodes(std::move(__x)); }
412
413	_List_base(_List_base&& __x, _Node_alloc_type&& __a)
414	: _M_impl(std::move(__a))
415	{
416	if (__x._M_get_Node_allocator() == _M_get_Node_allocator())
417	_M_move_nodes(std::move(__x));
418	else
419	_M_init(); // Caller must move individual elements.
420	}
421
422	void
423	_M_move_nodes(_List_base&& __x)
424	{
425	auto* const __xnode = std::__addressof(__x._M_impl._M_node);
426	if (__xnode->_M_next == __xnode)
427	_M_init();
428	else
429	{
430	auto* const __node = std::__addressof(_M_impl._M_node);
431	__node->_M_next = __xnode->_M_next;
432	__node->_M_prev = __xnode->_M_prev;
433	__node->_M_next->_M_prev = __node->_M_prev->_M_next = __node;
434	_M_set_size(__x._M_get_size());
435	__x._M_init();
436	}
437	}
438	#endif
439
440	// This is what actually destroys the list.
441	~_List_base() _GLIBCXX_NOEXCEPT
442	{ _M_clear(); }
443
444	void
445	_M_clear() _GLIBCXX_NOEXCEPT;
446
447	void
448	_M_init() _GLIBCXX_NOEXCEPT
449	{
450	this->_M_impl._M_node._M_next = &this->_M_impl._M_node;
451	this->_M_impl._M_node._M_prev = &this->_M_impl._M_node;
452	_M_set_size(0);
453	}
454	};
455
456	/**
457	* @brief A standard container with linear time access to elements,
458	* and fixed time insertion/deletion at any point in the sequence.
459	*
460	* @ingroup sequences
461	*
462	* @tparam _Tp Type of element.
463	* @tparam _Alloc Allocator type, defaults to allocator<_Tp>.
464	*
465	* Meets the requirements of a <a href="tables.html#65">container</a>, a
466	* <a href="tables.html#66">reversible container</a>, and a
467	* <a href="tables.html#67">sequence</a>, including the
468	* <a href="tables.html#68">optional sequence requirements</a> with the
469	* %exception of @c at and @c operator[].
470	*
471	* This is a @e doubly @e linked %list. Traversal up and down the
472	* %list requires linear time, but adding and removing elements (or
473	* @e nodes) is done in constant time, regardless of where the
474	* change takes place. Unlike std::vector and std::deque,
475	* random-access iterators are not provided, so subscripting ( @c
476	* [] ) access is not allowed. For algorithms which only need
477	* sequential access, this lack makes no difference.
478	*
479	* Also unlike the other standard containers, std::list provides
480	* specialized algorithms %unique to linked lists, such as
481	* splicing, sorting, and in-place reversal.
482	*
483	* A couple points on memory allocation for list<Tp>:
484	*
485	* First, we never actually allocate a Tp, we allocate
486	* List_node<Tp>'s and trust [20.1.5]/4 to DTRT. This is to ensure
487	* that after elements from %list<X,Alloc1> are spliced into
488	* %list<X,Alloc2>, destroying the memory of the second %list is a
489	* valid operation, i.e., Alloc1 giveth and Alloc2 taketh away.
490	*
491	* Second, a %list conceptually represented as
492	* @code
493	* A <---> B <---> C <---> D
494	* @endcode
495	* is actually circular; a link exists between A and D. The %list
496	* class holds (as its only data member) a private list::iterator
497	* pointing to @e D, not to @e A! To get to the head of the %list,
498	* we start at the tail and move forward by one. When this member
499	* iterator's next/previous pointers refer to itself, the %list is
500	* %empty.
501	*/
502	template<typename _Tp, typename _Alloc = std::allocator<_Tp> >
503	class list : protected _List_base<_Tp, _Alloc>
504	{
505	#ifdef _GLIBCXX_CONCEPT_CHECKS
506	// concept requirements
507	typedef typename _Alloc::value_type _Alloc_value_type;
508	# if __cplusplus < 201103L
509	__glibcxx_class_requires(_Tp, _SGIAssignableConcept)
510	# endif
511	__glibcxx_class_requires2(_Tp, _Alloc_value_type, _SameTypeConcept)
512	#endif
513
514	typedef _List_base<_Tp, _Alloc> _Base;
515	typedef typename _Base::_Tp_alloc_type _Tp_alloc_type;
516	typedef typename _Base::_Tp_alloc_traits _Tp_alloc_traits;
517	typedef typename _Base::_Node_alloc_type _Node_alloc_type;
518	typedef typename _Base::_Node_alloc_traits _Node_alloc_traits;
519
520	public:
521	typedef _Tp value_type;
522	typedef typename _Tp_alloc_traits::pointer pointer;
523	typedef typename _Tp_alloc_traits::const_pointer const_pointer;
524	typedef typename _Tp_alloc_traits::reference reference;
525	typedef typename _Tp_alloc_traits::const_reference const_reference;
526	typedef _List_iterator<_Tp> iterator;
527	typedef _List_const_iterator<_Tp> const_iterator;
528	typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
529	typedef std::reverse_iterator<iterator> reverse_iterator;
530	typedef size_t size_type;
531	typedef ptrdiff_t difference_type;
532	typedef _Alloc allocator_type;
533
534	protected:
535	// Note that pointers-to-_Node's can be ctor-converted to
536	// iterator types.
537	typedef _List_node<_Tp> _Node;
538
539	using _Base::_M_impl;
540	using _Base::_M_put_node;
541	using _Base::_M_get_node;
542	using _Base::_M_get_Node_allocator;
543
544	/**
545	* @param __args An instance of user data.
546	*
547	* Allocates space for a new node and constructs a copy of
548	* @a __args in it.
549	*/
550	#if __cplusplus < 201103L
551	_Node*
552	_M_create_node(const value_type& __x)
553	{
554	_Node* __p = this->_M_get_node();
555	__try
556	{
557	_Tp_alloc_type __alloc(_M_get_Node_allocator());
558	__alloc.construct(__p->_M_valptr(), __x);
559	}
560	__catch(...)
561	{
562	_M_put_node(__p);
563	__throw_exception_again;
564	}
565	return __p;
566	}
567	#else
568	template<typename... _Args>
569	_Node*
570	_M_create_node(_Args&&... __args)
571	{
572	auto __p = this->_M_get_node();
573	auto& __alloc = _M_get_Node_allocator();
574	__allocated_ptr<_Node_alloc_type> __guard{__alloc, __p};
575	_Node_alloc_traits::construct(__alloc, __p->_M_valptr(),
576	std::forward<_Args>(__args)...);
577	__guard = nullptr;
578	return __p;
579	}
580	#endif
581
582	public:
583	// [23.2.2.1] construct/copy/destroy
584	// (assign() and get_allocator() are also listed in this section)
585
586	/**
587	* @brief Creates a %list with no elements.
588	*/
589	list()
590	#if __cplusplus >= 201103L
591	noexcept(is_nothrow_default_constructible<_Node_alloc_type>::value)
592	#endif
593	: _Base() { }
594
595	/**
596	* @brief Creates a %list with no elements.
597	* @param __a An allocator object.
598	*/
599	explicit
600	list(const allocator_type& __a) _GLIBCXX_NOEXCEPT
601	: _Base(_Node_alloc_type(__a)) { }
602
603	#if __cplusplus >= 201103L
604	/**
605	* @brief Creates a %list with default constructed elements.
606	* @param __n The number of elements to initially create.
607	* @param __a An allocator object.
608	*
609	* This constructor fills the %list with @a __n default
610	* constructed elements.
611	*/
612	explicit
613	list(size_type __n, const allocator_type& __a = allocator_type())
614	: _Base(_Node_alloc_type(__a))
615	{ _M_default_initialize(__n); }
616
617	/**
618	* @brief Creates a %list with copies of an exemplar element.
619	* @param __n The number of elements to initially create.
620	* @param __value An element to copy.
621	* @param __a An allocator object.
622	*
623	* This constructor fills the %list with @a __n copies of @a __value.
624	*/
625	list(size_type __n, const value_type& __value,
626	const allocator_type& __a = allocator_type())
627	: _Base(_Node_alloc_type(__a))
628	{ _M_fill_initialize(__n, __value); }
629	#else
630	/**
631	* @brief Creates a %list with copies of an exemplar element.
632	* @param __n The number of elements to initially create.
633	* @param __value An element to copy.
634	* @param __a An allocator object.
635	*
636	* This constructor fills the %list with @a __n copies of @a __value.
637	*/
638	explicit
639	list(size_type __n, const value_type& __value = value_type(),
640	const allocator_type& __a = allocator_type())
641	: _Base(_Node_alloc_type(__a))
642	{ _M_fill_initialize(__n, __value); }
643	#endif
644
645	/**
646	* @brief %List copy constructor.
647	* @param __x A %list of identical element and allocator types.
648	*
649	* The newly-created %list uses a copy of the allocation object used
650	* by @a __x (unless the allocator traits dictate a different object).
651	*/
652	list(const list& __x)
653	: _Base(_Node_alloc_traits::
654	_S_select_on_copy(__x._M_get_Node_allocator()))
655	{ _M_initialize_dispatch(__x.begin(), __x.end(), __false_type()); }
656
657	#if __cplusplus >= 201103L
658	/**
659	* @brief %List move constructor.
660	* @param __x A %list of identical element and allocator types.
661	*
662	* The newly-created %list contains the exact contents of @a __x.
663	* The contents of @a __x are a valid, but unspecified %list.
664	*/
665	list(list&& __x) noexcept
666	: _Base(std::move(__x)) { }
667
668	/**
669	* @brief Builds a %list from an initializer_list
670	* @param __l An initializer_list of value_type.
671	* @param __a An allocator object.
672	*
673	* Create a %list consisting of copies of the elements in the
674	* initializer_list @a __l. This is linear in __l.size().
675	*/
676	list(initializer_list<value_type> __l,
677	const allocator_type& __a = allocator_type())
678	: _Base(_Node_alloc_type(__a))
679	{ _M_initialize_dispatch(__l.begin(), __l.end(), __false_type()); }
680
681	list(const list& __x, const allocator_type& __a)
682	: _Base(_Node_alloc_type(__a))
683	{ _M_initialize_dispatch(__x.begin(), __x.end(), __false_type()); }
684
685	list(list&& __x, const allocator_type& __a)
686	noexcept(_Node_alloc_traits::_S_always_equal())
687	: _Base(std::move(__x), _Node_alloc_type(__a))
688	{
689	// If __x is not empty it means its allocator is not equal to __a,
690	// so we need to move from each element individually.
691	insert(begin(), std::__make_move_if_noexcept_iterator(__x.begin()),
692	std::__make_move_if_noexcept_iterator(__x.end()));
693	}
694	#endif
695
696	/**
697	* @brief Builds a %list from a range.
698	* @param __first An input iterator.
699	* @param __last An input iterator.
700	* @param __a An allocator object.
701	*
702	* Create a %list consisting of copies of the elements from
703	* [@a __first,@a __last). This is linear in N (where N is
704	* distance(@a __first,@a __last)).
705	*/
706	#if __cplusplus >= 201103L
707	template<typename _InputIterator,
708	typename = std::_RequireInputIter<_InputIterator>>
709	list(_InputIterator __first, _InputIterator __last,
710	const allocator_type& __a = allocator_type())
711	: _Base(_Node_alloc_type(__a))
712	{ _M_initialize_dispatch(__first, __last, __false_type()); }
713	#else
714	template<typename _InputIterator>
715	list(_InputIterator __first, _InputIterator __last,
716	const allocator_type& __a = allocator_type())
717	: _Base(_Node_alloc_type(__a))
718	{
719	// Check whether it's an integral type. If so, it's not an iterator.
720	typedef typename std::__is_integer<_InputIterator>::__type _Integral;
721	_M_initialize_dispatch(__first, __last, _Integral());
722	}
723	#endif
724
725	#if __cplusplus >= 201103L
726	/**
727	* No explicit dtor needed as the _Base dtor takes care of
728	* things. The _Base dtor only erases the elements, and note
729	* that if the elements themselves are pointers, the pointed-to
730	* memory is not touched in any way. Managing the pointer is
731	* the user's responsibility.
732	*/
733	~list() = default;
734	#endif
735
736	/**
737	* @brief %List assignment operator.
738	* @param __x A %list of identical element and allocator types.
739	*
740	* All the elements of @a __x are copied.
741	*
742	* Whether the allocator is copied depends on the allocator traits.
743	*/
744	list&
745	operator=(const list& __x);
746
747	#if __cplusplus >= 201103L
748	/**
749	* @brief %List move assignment operator.
750	* @param __x A %list of identical element and allocator types.
751	*
752	* The contents of @a __x are moved into this %list (without copying).
753	*
754	* Afterwards @a __x is a valid, but unspecified %list
755	*
756	* Whether the allocator is moved depends on the allocator traits.
757	*/
758	list&
759	operator=(list&& __x)
760	noexcept(_Node_alloc_traits::_S_nothrow_move())
761	{
762	constexpr bool __move_storage =
763	_Node_alloc_traits::_S_propagate_on_move_assign()
764	\|\| _Node_alloc_traits::_S_always_equal();
765	_M_move_assign(std::move(__x), __bool_constant<__move_storage>());
766	return *this;
767	}
768
769	/**
770	* @brief %List initializer list assignment operator.
771	* @param __l An initializer_list of value_type.
772	*
773	* Replace the contents of the %list with copies of the elements
774	* in the initializer_list @a __l. This is linear in l.size().
775	*/
776	list&
777	operator=(initializer_list<value_type> __l)
778	{
779	this->assign(__l.begin(), __l.end());
780	return *this;
781	}
782	#endif
783
784	/**
785	* @brief Assigns a given value to a %list.
786	* @param __n Number of elements to be assigned.
787	* @param __val Value to be assigned.
788	*
789	* This function fills a %list with @a __n copies of the given
790	* value. Note that the assignment completely changes the %list
791	* and that the resulting %list's size is the same as the number
792	* of elements assigned.
793	*/
794	void
795	assign(size_type __n, const value_type& __val)
796	{ _M_fill_assign(__n, __val); }
797
798	/**
799	* @brief Assigns a range to a %list.
800	* @param __first An input iterator.
801	* @param __last An input iterator.
802	*
803	* This function fills a %list with copies of the elements in the
804	* range [@a __first,@a __last).
805	*
806	* Note that the assignment completely changes the %list and
807	* that the resulting %list's size is the same as the number of
808	* elements assigned.
809	*/
810	#if __cplusplus >= 201103L
811	template<typename _InputIterator,
812	typename = std::_RequireInputIter<_InputIterator>>
813	void
814	assign(_InputIterator __first, _InputIterator __last)
815	{ _M_assign_dispatch(__first, __last, __false_type()); }
816	#else
817	template<typename _InputIterator>
818	void
819	assign(_InputIterator __first, _InputIterator __last)
820	{
821	// Check whether it's an integral type. If so, it's not an iterator.
822	typedef typename std::__is_integer<_InputIterator>::__type _Integral;
823	_M_assign_dispatch(__first, __last, _Integral());
824	}
825	#endif
826
827	#if __cplusplus >= 201103L
828	/**
829	* @brief Assigns an initializer_list to a %list.
830	* @param __l An initializer_list of value_type.
831	*
832	* Replace the contents of the %list with copies of the elements
833	* in the initializer_list @a __l. This is linear in __l.size().
834	*/
835	void
836	assign(initializer_list<value_type> __l)
837	{ this->_M_assign_dispatch(__l.begin(), __l.end(), __false_type()); }
838	#endif
839
840	/// Get a copy of the memory allocation object.
841	allocator_type
842	get_allocator() const _GLIBCXX_NOEXCEPT
843	{ return allocator_type(_Base::_M_get_Node_allocator()); }
844
845	// iterators
846	/**
847	* Returns a read/write iterator that points to the first element in the
848	* %list. Iteration is done in ordinary element order.
849	*/
850	iterator
851	begin() _GLIBCXX_NOEXCEPT
852	{ return iterator(this->_M_impl._M_node._M_next); }
853
854	/**
855	* Returns a read-only (constant) iterator that points to the
856	* first element in the %list. Iteration is done in ordinary
857	* element order.
858	*/
859	const_iterator
860	begin() const _GLIBCXX_NOEXCEPT
861	{ return const_iterator(this->_M_impl._M_node._M_next); }
862
863	/**
864	* Returns a read/write iterator that points one past the last
865	* element in the %list. Iteration is done in ordinary element
866	* order.
867	*/
868	iterator
869	end() _GLIBCXX_NOEXCEPT
870	{ return iterator(&this->_M_impl._M_node); }
871
872	/**
873	* Returns a read-only (constant) iterator that points one past
874	* the last element in the %list. Iteration is done in ordinary
875	* element order.
876	*/
877	const_iterator
878	end() const _GLIBCXX_NOEXCEPT
879	{ return const_iterator(&this->_M_impl._M_node); }
880
881	/**
882	* Returns a read/write reverse iterator that points to the last
883	* element in the %list. Iteration is done in reverse element
884	* order.
885	*/
886	reverse_iterator
887	rbegin() _GLIBCXX_NOEXCEPT
888	{ return reverse_iterator(end()); }
889
890	/**
891	* Returns a read-only (constant) reverse iterator that points to
892	* the last element in the %list. Iteration is done in reverse
893	* element order.
894	*/
895	const_reverse_iterator
896	rbegin() const _GLIBCXX_NOEXCEPT
897	{ return const_reverse_iterator(end()); }
898
899	/**
900	* Returns a read/write reverse iterator that points to one
901	* before the first element in the %list. Iteration is done in
902	* reverse element order.
903	*/
904	reverse_iterator
905	rend() _GLIBCXX_NOEXCEPT
906	{ return reverse_iterator(begin()); }
907
908	/**
909	* Returns a read-only (constant) reverse iterator that points to one
910	* before the first element in the %list. Iteration is done in reverse
911	* element order.
912	*/
913	const_reverse_iterator
914	rend() const _GLIBCXX_NOEXCEPT
915	{ return const_reverse_iterator(begin()); }
916
917	#if __cplusplus >= 201103L
918	/**
919	* Returns a read-only (constant) iterator that points to the
920	* first element in the %list. Iteration is done in ordinary
921	* element order.
922	*/
923	const_iterator
924	cbegin() const noexcept
925	{ return const_iterator(this->_M_impl._M_node._M_next); }
926
927	/**
928	* Returns a read-only (constant) iterator that points one past
929	* the last element in the %list. Iteration is done in ordinary
930	* element order.
931	*/
932	const_iterator
933	cend() const noexcept
934	{ return const_iterator(&this->_M_impl._M_node); }
935
936	/**
937	* Returns a read-only (constant) reverse iterator that points to
938	* the last element in the %list. Iteration is done in reverse
939	* element order.
940	*/
941	const_reverse_iterator
942	crbegin() const noexcept
943	{ return const_reverse_iterator(end()); }
944
945	/**
946	* Returns a read-only (constant) reverse iterator that points to one
947	* before the first element in the %list. Iteration is done in reverse
948	* element order.
949	*/
950	const_reverse_iterator
951	crend() const noexcept
952	{ return const_reverse_iterator(begin()); }
953	#endif
954
955	// [23.2.2.2] capacity
956	/**
957	* Returns true if the %list is empty. (Thus begin() would equal
958	* end().)
959	*/
960	bool
961	empty() const _GLIBCXX_NOEXCEPT
962	{ return this->_M_impl._M_node._M_next == &this->_M_impl._M_node; }
963
964	/** Returns the number of elements in the %list. */
965	size_type
966	size() const _GLIBCXX_NOEXCEPT
967	{ return this->_M_node_count(); }
968
969	/** Returns the size() of the largest possible %list. */
970	size_type
971	max_size() const _GLIBCXX_NOEXCEPT
972	{ return _Node_alloc_traits::max_size(_M_get_Node_allocator()); }
973
974	#if __cplusplus >= 201103L
975	/**
976	* @brief Resizes the %list to the specified number of elements.
977	* @param __new_size Number of elements the %list should contain.
978	*
979	* This function will %resize the %list to the specified number
980	* of elements. If the number is smaller than the %list's
981	* current size the %list is truncated, otherwise default
982	* constructed elements are appended.
983	*/
984	void
985	resize(size_type __new_size);
986
987	/**
988	* @brief Resizes the %list to the specified number of elements.
989	* @param __new_size Number of elements the %list should contain.
990	* @param __x Data with which new elements should be populated.
991	*
992	* This function will %resize the %list to the specified number
993	* of elements. If the number is smaller than the %list's
994	* current size the %list is truncated, otherwise the %list is
995	* extended and new elements are populated with given data.
996	*/
997	void
998	resize(size_type __new_size, const value_type& __x);
999	#else
1000	/**
1001	* @brief Resizes the %list to the specified number of elements.
1002	* @param __new_size Number of elements the %list should contain.
1003	* @param __x Data with which new elements should be populated.
1004	*
1005	* This function will %resize the %list to the specified number
1006	* of elements. If the number is smaller than the %list's
1007	* current size the %list is truncated, otherwise the %list is
1008	* extended and new elements are populated with given data.
1009	*/
1010	void
1011	resize(size_type __new_size, value_type __x = value_type());
1012	#endif
1013
1014	// element access
1015	/**
1016	* Returns a read/write reference to the data at the first
1017	* element of the %list.
1018	*/
1019	reference
1020	front() _GLIBCXX_NOEXCEPT
1021	{ return *begin(); }
1022
1023	/**
1024	* Returns a read-only (constant) reference to the data at the first
1025	* element of the %list.
1026	*/
1027	const_reference
1028	front() const _GLIBCXX_NOEXCEPT
1029	{ return *begin(); }
1030
1031	/**
1032	* Returns a read/write reference to the data at the last element
1033	* of the %list.
1034	*/
1035	reference
1036	back() _GLIBCXX_NOEXCEPT
1037	{
1038	iterator __tmp = end();
1039	--__tmp;
1040	return *__tmp;
1041	}
1042
1043	/**
1044	* Returns a read-only (constant) reference to the data at the last
1045	* element of the %list.
1046	*/
1047	const_reference
1048	back() const _GLIBCXX_NOEXCEPT
1049	{
1050	const_iterator __tmp = end();
1051	--__tmp;
1052	return *__tmp;
1053	}
1054
1055	// [23.2.2.3] modifiers
1056	/**
1057	* @brief Add data to the front of the %list.
1058	* @param __x Data to be added.
1059	*
1060	* This is a typical stack operation. The function creates an
1061	* element at the front of the %list and assigns the given data
1062	* to it. Due to the nature of a %list this operation can be
1063	* done in constant time, and does not invalidate iterators and
1064	* references.
1065	*/
1066	void
1067	push_front(const value_type& __x)
1068	{ this->_M_insert(begin(), __x); }
1069
1070	#if __cplusplus >= 201103L
1071	void
1072	push_front(value_type&& __x)
1073	{ this->_M_insert(begin(), std::move(__x)); }
1074
1075	template<typename... _Args>
1076	#if __cplusplus > 201402L
1077	reference
1078	#else
1079	void
1080	#endif
1081	emplace_front(_Args&&... __args)
1082	{
1083	this->_M_insert(begin(), std::forward<_Args>(__args)...);
1084	#if __cplusplus > 201402L
1085	return front();
1086	#endif
1087	}
1088	#endif
1089
1090	/**
1091	* @brief Removes first element.
1092	*
1093	* This is a typical stack operation. It shrinks the %list by
1094	* one. Due to the nature of a %list this operation can be done
1095	* in constant time, and only invalidates iterators/references to
1096	* the element being removed.
1097	*
1098	* Note that no data is returned, and if the first element's data
1099	* is needed, it should be retrieved before pop_front() is
1100	* called.
1101	*/
1102	void
1103	pop_front() _GLIBCXX_NOEXCEPT
1104	{ this->_M_erase(begin()); }
1105
1106	/**
1107	* @brief Add data to the end of the %list.
1108	* @param __x Data to be added.
1109	*
1110	* This is a typical stack operation. The function creates an
1111	* element at the end of the %list and assigns the given data to
1112	* it. Due to the nature of a %list this operation can be done
1113	* in constant time, and does not invalidate iterators and
1114	* references.
1115	*/
1116	void
1117	push_back(const value_type& __x)
1118	{ this->_M_insert(end(), __x); }
1119
1120	#if __cplusplus >= 201103L
1121	void
1122	push_back(value_type&& __x)
1123	{ this->_M_insert(end(), std::move(__x)); }
1124
1125	template<typename... _Args>
1126	#if __cplusplus > 201402L
1127	reference
1128	#else
1129	void
1130	#endif
1131	emplace_back(_Args&&... __args)
1132	{
1133	this->_M_insert(end(), std::forward<_Args>(__args)...);
1134	#if __cplusplus > 201402L
1135	return back();
1136	#endif
1137	}
1138	#endif
1139
1140	/**
1141	* @brief Removes last element.
1142	*
1143	* This is a typical stack operation. It shrinks the %list by
1144	* one. Due to the nature of a %list this operation can be done
1145	* in constant time, and only invalidates iterators/references to
1146	* the element being removed.
1147	*
1148	* Note that no data is returned, and if the last element's data
1149	* is needed, it should be retrieved before pop_back() is called.
1150	*/
1151	void
1152	pop_back() _GLIBCXX_NOEXCEPT
1153	{ this->_M_erase(iterator(this->_M_impl._M_node._M_prev)); }
1154
1155	#if __cplusplus >= 201103L
1156	/**
1157	* @brief Constructs object in %list before specified iterator.
1158	* @param __position A const_iterator into the %list.
1159	* @param __args Arguments.
1160	* @return An iterator that points to the inserted data.
1161	*
1162	* This function will insert an object of type T constructed
1163	* with T(std::forward<Args>(args)...) before the specified
1164	* location. Due to the nature of a %list this operation can
1165	* be done in constant time, and does not invalidate iterators
1166	* and references.
1167	*/
1168	template<typename... _Args>
1169	iterator
1170	emplace(const_iterator __position, _Args&&... __args);
1171
1172	/**
1173	* @brief Inserts given value into %list before specified iterator.
1174	* @param __position A const_iterator into the %list.
1175	* @param __x Data to be inserted.
1176	* @return An iterator that points to the inserted data.
1177	*
1178	* This function will insert a copy of the given value before
1179	* the specified location. Due to the nature of a %list this
1180	* operation can be done in constant time, and does not
1181	* invalidate iterators and references.
1182	*/
1183	iterator
1184	insert(const_iterator __position, const value_type& __x);
1185	#else
1186	/**
1187	* @brief Inserts given value into %list before specified iterator.
1188	* @param __position An iterator into the %list.
1189	* @param __x Data to be inserted.
1190	* @return An iterator that points to the inserted data.
1191	*
1192	* This function will insert a copy of the given value before
1193	* the specified location. Due to the nature of a %list this
1194	* operation can be done in constant time, and does not
1195	* invalidate iterators and references.
1196	*/
1197	iterator
1198	insert(iterator __position, const value_type& __x);
1199	#endif
1200
1201	#if __cplusplus >= 201103L
1202	/**
1203	* @brief Inserts given rvalue into %list before specified iterator.
1204	* @param __position A const_iterator into the %list.
1205	* @param __x Data to be inserted.
1206	* @return An iterator that points to the inserted data.
1207	*
1208	* This function will insert a copy of the given rvalue before
1209	* the specified location. Due to the nature of a %list this
1210	* operation can be done in constant time, and does not
1211	* invalidate iterators and references.
1212	*/
1213	iterator
1214	insert(const_iterator __position, value_type&& __x)
1215	{ return emplace(__position, std::move(__x)); }
1216
1217	/**
1218	* @brief Inserts the contents of an initializer_list into %list
1219	* before specified const_iterator.
1220	* @param __p A const_iterator into the %list.
1221	* @param __l An initializer_list of value_type.
1222	* @return An iterator pointing to the first element inserted
1223	* (or __position).
1224	*
1225	* This function will insert copies of the data in the
1226	* initializer_list @a l into the %list before the location
1227	* specified by @a p.
1228	*
1229	* This operation is linear in the number of elements inserted and
1230	* does not invalidate iterators and references.
1231	*/
1232	iterator
1233	insert(const_iterator __p, initializer_list<value_type> __l)
1234	{ return this->insert(__p, __l.begin(), __l.end()); }
1235	#endif
1236
1237	#if __cplusplus >= 201103L
1238	/**
1239	* @brief Inserts a number of copies of given data into the %list.
1240	* @param __position A const_iterator into the %list.
1241	* @param __n Number of elements to be inserted.
1242	* @param __x Data to be inserted.
1243	* @return An iterator pointing to the first element inserted
1244	* (or __position).
1245	*
1246	* This function will insert a specified number of copies of the
1247	* given data before the location specified by @a position.
1248	*
1249	* This operation is linear in the number of elements inserted and
1250	* does not invalidate iterators and references.
1251	*/
1252	iterator
1253	insert(const_iterator __position, size_type __n, const value_type& __x);
1254	#else
1255	/**
1256	* @brief Inserts a number of copies of given data into the %list.
1257	* @param __position An iterator into the %list.
1258	* @param __n Number of elements to be inserted.
1259	* @param __x Data to be inserted.
1260	*
1261	* This function will insert a specified number of copies of the
1262	* given data before the location specified by @a position.
1263	*
1264	* This operation is linear in the number of elements inserted and
1265	* does not invalidate iterators and references.
1266	*/
1267	void
1268	insert(iterator __position, size_type __n, const value_type& __x)
1269	{
1270	list __tmp(__n, __x, get_allocator());
1271	splice(__position, __tmp);
1272	}
1273	#endif
1274
1275	#if __cplusplus >= 201103L
1276	/**
1277	* @brief Inserts a range into the %list.
1278	* @param __position A const_iterator into the %list.
1279	* @param __first An input iterator.
1280	* @param __last An input iterator.
1281	* @return An iterator pointing to the first element inserted
1282	* (or __position).
1283	*
1284	* This function will insert copies of the data in the range [@a
1285	* first,@a last) into the %list before the location specified by
1286	* @a position.
1287	*
1288	* This operation is linear in the number of elements inserted and
1289	* does not invalidate iterators and references.
1290	*/
1291	template<typename _InputIterator,
1292	typename = std::_RequireInputIter<_InputIterator>>
1293	iterator
1294	insert(const_iterator __position, _InputIterator __first,
1295	_InputIterator __last);
1296	#else
1297	/**
1298	* @brief Inserts a range into the %list.
1299	* @param __position An iterator into the %list.
1300	* @param __first An input iterator.
1301	* @param __last An input iterator.
1302	*
1303	* This function will insert copies of the data in the range [@a
1304	* first,@a last) into the %list before the location specified by
1305	* @a position.
1306	*
1307	* This operation is linear in the number of elements inserted and
1308	* does not invalidate iterators and references.
1309	*/
1310	template<typename _InputIterator>
1311	void
1312	insert(iterator __position, _InputIterator __first,
1313	_InputIterator __last)
1314	{
1315	list __tmp(__first, __last, get_allocator());
1316	splice(__position, __tmp);
1317	}
1318	#endif
1319
1320	/**
1321	* @brief Remove element at given position.
1322	* @param __position Iterator pointing to element to be erased.
1323	* @return An iterator pointing to the next element (or end()).
1324	*
1325	* This function will erase the element at the given position and thus
1326	* shorten the %list by one.
1327	*
1328	* Due to the nature of a %list this operation can be done in
1329	* constant time, and only invalidates iterators/references to
1330	* the element being removed. The user is also cautioned that
1331	* this function only erases the element, and that if the element
1332	* is itself a pointer, the pointed-to memory is not touched in
1333	* any way. Managing the pointer is the user's responsibility.
1334	*/
1335	iterator
1336	#if __cplusplus >= 201103L
1337	erase(const_iterator __position) noexcept;
1338	#else
1339	erase(iterator __position);
1340	#endif
1341
1342	/**
1343	* @brief Remove a range of elements.
1344	* @param __first Iterator pointing to the first element to be erased.
1345	* @param __last Iterator pointing to one past the last element to be
1346	* erased.
1347	* @return An iterator pointing to the element pointed to by @a last
1348	* prior to erasing (or end()).
1349	*
1350	* This function will erase the elements in the range @a
1351	* [first,last) and shorten the %list accordingly.
1352	*
1353	* This operation is linear time in the size of the range and only
1354	* invalidates iterators/references to the element being removed.
1355	* The user is also cautioned that this function only erases the
1356	* elements, and that if the elements themselves are pointers, the
1357	* pointed-to memory is not touched in any way. Managing the pointer
1358	* is the user's responsibility.
1359	*/
1360	iterator
1361	#if __cplusplus >= 201103L
1362	erase(const_iterator __first, const_iterator __last) noexcept
1363	#else
1364	erase(iterator __first, iterator __last)
1365	#endif
1366	{
1367	while (__first != __last)
1368	__first = erase(__first);
1369	return __last._M_const_cast();
1370	}
1371
1372	/**
1373	* @brief Swaps data with another %list.
1374	* @param __x A %list of the same element and allocator types.
1375	*
1376	* This exchanges the elements between two lists in constant
1377	* time. Note that the global std::swap() function is
1378	* specialized such that std::swap(l1,l2) will feed to this
1379	* function.
1380	*
1381	* Whether the allocators are swapped depends on the allocator traits.
1382	*/
1383	void
1384	swap(list& __x) _GLIBCXX_NOEXCEPT
1385	{
1386	__detail::_List_node_base::swap(this->_M_impl._M_node,
1387	__x._M_impl._M_node);
1388
1389	size_t __xsize = __x._M_get_size();
1390	__x._M_set_size(this->_M_get_size());
1391	this->_M_set_size(__xsize);
1392
1393	_Node_alloc_traits::_S_on_swap(this->_M_get_Node_allocator(),
1394	__x._M_get_Node_allocator());
1395	}
1396
1397	/**
1398	* Erases all the elements. Note that this function only erases
1399	* the elements, and that if the elements themselves are
1400	* pointers, the pointed-to memory is not touched in any way.
1401	* Managing the pointer is the user's responsibility.
1402	*/
1403	void
1404	clear() _GLIBCXX_NOEXCEPT
1405	{
1406	_Base::_M_clear();
1407	_Base::_M_init();
1408	}
1409
1410	// [23.2.2.4] list operations
1411	/**
1412	* @brief Insert contents of another %list.
1413	* @param __position Iterator referencing the element to insert before.
1414	* @param __x Source list.
1415	*
1416	* The elements of @a __x are inserted in constant time in front of
1417	* the element referenced by @a __position. @a __x becomes an empty
1418	* list.
1419	*
1420	* Requires this != @a __x.
1421	*/
1422	void
1423	#if __cplusplus >= 201103L
1424	splice(const_iterator __position, list&& __x) noexcept
1425	#else
1426	splice(iterator __position, list& __x)
1427	#endif
1428	{
1429	if (!__x.empty())
1430	{
1431	_M_check_equal_allocators(__x);
1432
1433	this->_M_transfer(__position._M_const_cast(),
1434	__x.begin(), __x.end());
1435
1436	this->_M_inc_size(__x._M_get_size());
1437	__x._M_set_size(0);
1438	}
1439	}
1440
1441	#if __cplusplus >= 201103L
1442	void
1443	splice(const_iterator __position, list& __x) noexcept
1444	{ splice(__position, std::move(__x)); }
1445	#endif
1446
1447	#if __cplusplus >= 201103L
1448	/**
1449	* @brief Insert element from another %list.
1450	* @param __position Const_iterator referencing the element to
1451	* insert before.
1452	* @param __x Source list.
1453	* @param __i Const_iterator referencing the element to move.
1454	*
1455	* Removes the element in list @a __x referenced by @a __i and
1456	* inserts it into the current list before @a __position.
1457	*/
1458	void
1459	splice(const_iterator __position, list&& __x, const_iterator __i) noexcept
1460	#else
1461	/**
1462	* @brief Insert element from another %list.
1463	* @param __position Iterator referencing the element to insert before.
1464	* @param __x Source list.
1465	* @param __i Iterator referencing the element to move.
1466	*
1467	* Removes the element in list @a __x referenced by @a __i and
1468	* inserts it into the current list before @a __position.
1469	*/
1470	void
1471	splice(iterator __position, list& __x, iterator __i)
1472	#endif
1473	{
1474	iterator __j = __i._M_const_cast();
1475	++__j;
1476	if (__position == __i \|\| __position == __j)
1477	return;
1478
1479	if (this != std::__addressof(__x))
1480	_M_check_equal_allocators(__x);
1481
1482	this->_M_transfer(__position._M_const_cast(),
1483	__i._M_const_cast(), __j);
1484
1485	this->_M_inc_size(1);
1486	__x._M_dec_size(1);
1487	}
1488
1489	#if __cplusplus >= 201103L
1490	/**
1491	* @brief Insert element from another %list.
1492	* @param __position Const_iterator referencing the element to
1493	* insert before.
1494	* @param __x Source list.
1495	* @param __i Const_iterator referencing the element to move.
1496	*
1497	* Removes the element in list @a __x referenced by @a __i and
1498	* inserts it into the current list before @a __position.
1499	*/
1500	void
1501	splice(const_iterator __position, list& __x, const_iterator __i) noexcept
1502	{ splice(__position, std::move(__x), __i); }
1503	#endif
1504
1505	#if __cplusplus >= 201103L
1506	/**
1507	* @brief Insert range from another %list.
1508	* @param __position Const_iterator referencing the element to
1509	* insert before.
1510	* @param __x Source list.
1511	* @param __first Const_iterator referencing the start of range in x.
1512	* @param __last Const_iterator referencing the end of range in x.
1513	*
1514	* Removes elements in the range [__first,__last) and inserts them
1515	* before @a __position in constant time.
1516	*
1517	* Undefined if @a __position is in [__first,__last).
1518	*/
1519	void
1520	splice(const_iterator __position, list&& __x, const_iterator __first,
1521	const_iterator __last) noexcept
1522	#else
1523	/**
1524	* @brief Insert range from another %list.
1525	* @param __position Iterator referencing the element to insert before.
1526	* @param __x Source list.
1527	* @param __first Iterator referencing the start of range in x.
1528	* @param __last Iterator referencing the end of range in x.
1529	*
1530	* Removes elements in the range [__first,__last) and inserts them
1531	* before @a __position in constant time.
1532	*
1533	* Undefined if @a __position is in [__first,__last).
1534	*/
1535	void
1536	splice(iterator __position, list& __x, iterator __first,
1537	iterator __last)
1538	#endif
1539	{
1540	if (__first != __last)
1541	{
1542	if (this != std::__addressof(__x))
1543	_M_check_equal_allocators(__x);
1544
1545	size_t __n = this->_M_distance(__first._M_node, __last._M_node);
1546	this->_M_inc_size(__n);
1547	__x._M_dec_size(__n);
1548
1549	this->_M_transfer(__position._M_const_cast(),
1550	__first._M_const_cast(),
1551	__last._M_const_cast());
1552	}
1553	}
1554
1555	#if __cplusplus >= 201103L
1556	/**
1557	* @brief Insert range from another %list.
1558	* @param __position Const_iterator referencing the element to
1559	* insert before.
1560	* @param __x Source list.
1561	* @param __first Const_iterator referencing the start of range in x.
1562	* @param __last Const_iterator referencing the end of range in x.
1563	*
1564	* Removes elements in the range [__first,__last) and inserts them
1565	* before @a __position in constant time.
1566	*
1567	* Undefined if @a __position is in [__first,__last).
1568	*/
1569	void
1570	splice(const_iterator __position, list& __x, const_iterator __first,
1571	const_iterator __last) noexcept
1572	{ splice(__position, std::move(__x), __first, __last); }
1573	#endif
1574
1575	/**
1576	* @brief Remove all elements equal to value.
1577	* @param __value The value to remove.
1578	*
1579	* Removes every element in the list equal to @a value.
1580	* Remaining elements stay in list order. Note that this
1581	* function only erases the elements, and that if the elements
1582	* themselves are pointers, the pointed-to memory is not
1583	* touched in any way. Managing the pointer is the user's
1584	* responsibility.
1585	*/
1586	void
1587	remove(const _Tp& __value);
1588
1589	/**
1590	* @brief Remove all elements satisfying a predicate.
1591	* @tparam _Predicate Unary predicate function or object.
1592	*
1593	* Removes every element in the list for which the predicate
1594	* returns true. Remaining elements stay in list order. Note
1595	* that this function only erases the elements, and that if the
1596	* elements themselves are pointers, the pointed-to memory is
1597	* not touched in any way. Managing the pointer is the user's
1598	* responsibility.
1599	*/
1600	template<typename _Predicate>
1601	void
1602	remove_if(_Predicate);
1603
1604	/**
1605	* @brief Remove consecutive duplicate elements.
1606	*
1607	* For each consecutive set of elements with the same value,
1608	* remove all but the first one. Remaining elements stay in
1609	* list order. Note that this function only erases the
1610	* elements, and that if the elements themselves are pointers,
1611	* the pointed-to memory is not touched in any way. Managing
1612	* the pointer is the user's responsibility.
1613	*/
1614	void
1615	unique();
1616
1617	/**
1618	* @brief Remove consecutive elements satisfying a predicate.
1619	* @tparam _BinaryPredicate Binary predicate function or object.
1620	*
1621	* For each consecutive set of elements [first,last) that
1622	* satisfy predicate(first,i) where i is an iterator in
1623	* [first,last), remove all but the first one. Remaining
1624	* elements stay in list order. Note that this function only
1625	* erases the elements, and that if the elements themselves are
1626	* pointers, the pointed-to memory is not touched in any way.
1627	* Managing the pointer is the user's responsibility.
1628	*/
1629	template<typename _BinaryPredicate>
1630	void
1631	unique(_BinaryPredicate);
1632
1633	/**
1634	* @brief Merge sorted lists.
1635	* @param __x Sorted list to merge.
1636	*
1637	* Assumes that both @a __x and this list are sorted according to
1638	* operator<(). Merges elements of @a __x into this list in
1639	* sorted order, leaving @a __x empty when complete. Elements in
1640	* this list precede elements in @a __x that are equal.
1641	*/
1642	#if __cplusplus >= 201103L
1643	void
1644	merge(list&& __x);
1645
1646	void
1647	merge(list& __x)
1648	{ merge(std::move(__x)); }
1649	#else
1650	void
1651	merge(list& __x);
1652	#endif
1653
1654	/**
1655	* @brief Merge sorted lists according to comparison function.
1656	* @tparam _StrictWeakOrdering Comparison function defining
1657	* sort order.
1658	* @param __x Sorted list to merge.
1659	* @param __comp Comparison functor.
1660	*
1661	* Assumes that both @a __x and this list are sorted according to
1662	* StrictWeakOrdering. Merges elements of @a __x into this list
1663	* in sorted order, leaving @a __x empty when complete. Elements
1664	* in this list precede elements in @a __x that are equivalent
1665	* according to StrictWeakOrdering().
1666	*/
1667	#if __cplusplus >= 201103L
1668	template<typename _StrictWeakOrdering>
1669	void
1670	merge(list&& __x, _StrictWeakOrdering __comp);
1671
1672	template<typename _StrictWeakOrdering>
1673	void
1674	merge(list& __x, _StrictWeakOrdering __comp)
1675	{ merge(std::move(__x), __comp); }
1676	#else
1677	template<typename _StrictWeakOrdering>
1678	void
1679	merge(list& __x, _StrictWeakOrdering __comp);
1680	#endif
1681
1682	/**
1683	* @brief Reverse the elements in list.
1684	*
1685	* Reverse the order of elements in the list in linear time.
1686	*/
1687	void
1688	reverse() _GLIBCXX_NOEXCEPT
1689	{ this->_M_impl._M_node._M_reverse(); }
1690
1691	/**
1692	* @brief Sort the elements.
1693	*
1694	* Sorts the elements of this list in NlogN time. Equivalent
1695	* elements remain in list order.
1696	*/
1697	void
1698	sort();
1699
1700	/**
1701	* @brief Sort the elements according to comparison function.
1702	*
1703	* Sorts the elements of this list in NlogN time. Equivalent
1704	* elements remain in list order.
1705	*/
1706	template<typename _StrictWeakOrdering>
1707	void
1708	sort(_StrictWeakOrdering);
1709
1710	protected:
1711	// Internal constructor functions follow.
1712
1713	// Called by the range constructor to implement [23.1.1]/9
1714
1715	// _GLIBCXX_RESOLVE_LIB_DEFECTS
1716	// 438. Ambiguity in the "do the right thing" clause
1717	template<typename _Integer>
1718	void
1719	_M_initialize_dispatch(_Integer __n, _Integer __x, __true_type)
1720	{ _M_fill_initialize(static_cast<size_type>(__n), __x); }
1721
1722	// Called by the range constructor to implement [23.1.1]/9
1723	template<typename _InputIterator>
1724	void
1725	_M_initialize_dispatch(_InputIterator __first, _InputIterator __last,
1726	__false_type)
1727	{
1728	for (; __first != __last; ++__first)
1729	#if __cplusplus >= 201103L
1730	emplace_back(*__first);
1731	#else
1732	push_back(*__first);
1733	#endif
1734	}
1735
1736	// Called by list(n,v,a), and the range constructor when it turns out
1737	// to be the same thing.
1738	void
1739	_M_fill_initialize(size_type __n, const value_type& __x)
1740	{
1741	for (; __n; --__n)
1742	push_back(__x);
1743	}
1744
1745	#if __cplusplus >= 201103L
1746	// Called by list(n).
1747	void
1748	_M_default_initialize(size_type __n)
1749	{
1750	for (; __n; --__n)
1751	emplace_back();
1752	}
1753
1754	// Called by resize(sz).
1755	void
1756	_M_default_append(size_type __n);
1757	#endif
1758
1759	// Internal assign functions follow.
1760
1761	// Called by the range assign to implement [23.1.1]/9
1762
1763	// _GLIBCXX_RESOLVE_LIB_DEFECTS
1764	// 438. Ambiguity in the "do the right thing" clause
1765	template<typename _Integer>
1766	void
1767	_M_assign_dispatch(_Integer __n, _Integer __val, __true_type)
1768	{ _M_fill_assign(__n, __val); }
1769
1770	// Called by the range assign to implement [23.1.1]/9
1771	template<typename _InputIterator>
1772	void
1773	_M_assign_dispatch(_InputIterator __first, _InputIterator __last,
1774	__false_type);
1775
1776	// Called by assign(n,t), and the range assign when it turns out
1777	// to be the same thing.
1778	void
1779	_M_fill_assign(size_type __n, const value_type& __val);
1780
1781
1782	// Moves the elements from [first,last) before position.
1783	void
1784	_M_transfer(iterator __position, iterator __first, iterator __last)
1785	{ __position._M_node->_M_transfer(__first._M_node, __last._M_node); }
1786
1787	// Inserts new element at position given and with value given.
1788	#if __cplusplus < 201103L
1789	void
1790	_M_insert(iterator __position, const value_type& __x)
1791	{
1792	_Node* __tmp = _M_create_node(__x);
1793	__tmp->_M_hook(__position._M_node);
1794	this->_M_inc_size(1);
1795	}
1796	#else
1797	template<typename... _Args>
1798	void
1799	_M_insert(iterator __position, _Args&&... __args)
1800	{
1801	_Node* __tmp = _M_create_node(std::forward<_Args>(__args)...);
1802	__tmp->_M_hook(__position._M_node);
1803	this->_M_inc_size(1);
1804	}
1805	#endif
1806
1807	// Erases element at position given.
1808	void
1809	_M_erase(iterator __position) _GLIBCXX_NOEXCEPT
1810	{
1811	this->_M_dec_size(1);
1812	__position._M_node->_M_unhook();
1813	_Node* __n = static_cast<_Node*>(__position._M_node);
1814	#if __cplusplus >= 201103L
1815	_Node_alloc_traits::destroy(_M_get_Node_allocator(), __n->_M_valptr());
1816	#else
1817	_Tp_alloc_type(_M_get_Node_allocator()).destroy(__n->_M_valptr());
1818	#endif
1819
1820	_M_put_node(__n);
1821	}
1822
1823	// To implement the splice (and merge) bits of N1599.
1824	void
1825	_M_check_equal_allocators(list& __x) _GLIBCXX_NOEXCEPT
1826	{
1827	if (std::__alloc_neq<typename _Base::_Node_alloc_type>::
1828	_S_do_it(_M_get_Node_allocator(), __x._M_get_Node_allocator()))
1829	__builtin_abort();
1830	}
1831
1832	// Used to implement resize.
1833	const_iterator
1834	_M_resize_pos(size_type& __new_size) const;
1835
1836	#if __cplusplus >= 201103L
1837	void
1838	_M_move_assign(list&& __x, true_type) noexcept
1839	{
1840	this->_M_clear();
1841	if (__x.empty())
1842	this->_M_init();
1843	else
1844	{
1845	this->_M_impl._M_node._M_next = __x._M_impl._M_node._M_next;
1846	this->_M_impl._M_node._M_next->_M_prev = &this->_M_impl._M_node;
1847	this->_M_impl._M_node._M_prev = __x._M_impl._M_node._M_prev;
1848	this->_M_impl._M_node._M_prev->_M_next = &this->_M_impl._M_node;
1849	this->_M_set_size(__x._M_get_size());
1850	__x._M_init();
1851	}
1852	std::__alloc_on_move(this->_M_get_Node_allocator(),
1853	__x._M_get_Node_allocator());
1854	}
1855
1856	void
1857	_M_move_assign(list&& __x, false_type)
1858	{
1859	if (__x._M_get_Node_allocator() == this->_M_get_Node_allocator())
1860	_M_move_assign(std::move(__x), true_type{});
1861	else
1862	// The rvalue's allocator cannot be moved, or is not equal,
1863	// so we need to individually move each element.
1864	_M_assign_dispatch(std::__make_move_if_noexcept_iterator(__x.begin()),
1865	std::__make_move_if_noexcept_iterator(__x.end()),
1866	__false_type{});
1867	}
1868	#endif
1869	};
1870	_GLIBCXX_END_NAMESPACE_CXX11
1871
1872	/**
1873	* @brief List equality comparison.
1874	* @param __x A %list.
1875	* @param __y A %list of the same type as @a __x.
1876	* @return True iff the size and elements of the lists are equal.
1877	*
1878	* This is an equivalence relation. It is linear in the size of
1879	* the lists. Lists are considered equivalent if their sizes are
1880	* equal, and if corresponding elements compare equal.
1881	*/
1882	template<typename _Tp, typename _Alloc>
1883	inline bool
1884	operator==(const list<_Tp, _Alloc>& __x, const list<_Tp, _Alloc>& __y)
1885	{
1886	#if _GLIBCXX_USE_CXX11_ABI
1887	if (__x.size() != __y.size())
1888	return false;
1889	#endif
1890
1891	typedef typename list<_Tp, _Alloc>::const_iterator const_iterator;
1892	const_iterator __end1 = __x.end();
1893	const_iterator __end2 = __y.end();
1894
1895	const_iterator __i1 = __x.begin();
1896	const_iterator __i2 = __y.begin();
1897	while (__i1 != __end1 && __i2 != __end2 && __i1 == __i2)
1898	{
1899	++__i1;
1900	++__i2;
1901	}
1902	return __i1 == __end1 && __i2 == __end2;
1903	}
1904
1905	/**
1906	* @brief List ordering relation.
1907	* @param __x A %list.
1908	* @param __y A %list of the same type as @a __x.
1909	* @return True iff @a __x is lexicographically less than @a __y.
1910	*
1911	* This is a total ordering relation. It is linear in the size of the
1912	* lists. The elements must be comparable with @c <.
1913	*
1914	* See std::lexicographical_compare() for how the determination is made.
1915	*/
1916	template<typename _Tp, typename _Alloc>
1917	inline bool
1918	operator<(const list<_Tp, _Alloc>& __x, const list<_Tp, _Alloc>& __y)
1919	{ return std::lexicographical_compare(__x.begin(), __x.end(),
1920	__y.begin(), __y.end()); }
1921
1922	/// Based on operator==
1923	template<typename _Tp, typename _Alloc>
1924	inline bool
1925	operator!=(const list<_Tp, _Alloc>& __x, const list<_Tp, _Alloc>& __y)
1926	{ return !(__x == __y); }
1927
1928	/// Based on operator<
1929	template<typename _Tp, typename _Alloc>
1930	inline bool
1931	operator>(const list<_Tp, _Alloc>& __x, const list<_Tp, _Alloc>& __y)
1932	{ return __y < __x; }
1933
1934	/// Based on operator<
1935	template<typename _Tp, typename _Alloc>
1936	inline bool
1937	operator<=(const list<_Tp, _Alloc>& __x, const list<_Tp, _Alloc>& __y)
1938	{ return !(__y < __x); }
1939
1940	/// Based on operator<
1941	template<typename _Tp, typename _Alloc>
1942	inline bool
1943	operator>=(const list<_Tp, _Alloc>& __x, const list<_Tp, _Alloc>& __y)
1944	{ return !(__x < __y); }
1945
1946	/// See std::list::swap().
1947	template<typename _Tp, typename _Alloc>
1948	inline void
1949	swap(list<_Tp, _Alloc>& __x, list<_Tp, _Alloc>& __y)
1950	_GLIBCXX_NOEXCEPT_IF(noexcept(__x.swap(__y)))
1951	{ __x.swap(__y); }
1952
1953	_GLIBCXX_END_NAMESPACE_CONTAINER
1954
1955	#if _GLIBCXX_USE_CXX11_ABI
1956	_GLIBCXX_BEGIN_NAMESPACE_VERSION
1957
1958	// Detect when distance is used to compute the size of the whole list.
1959	template<typename _Tp>
1960	inline ptrdiff_t
1961	__distance(_GLIBCXX_STD_C::_List_iterator<_Tp> __first,
1962	_GLIBCXX_STD_C::_List_iterator<_Tp> __last,
1963	input_iterator_tag __tag)
1964	{
1965	typedef _GLIBCXX_STD_C::_List_const_iterator<_Tp> _CIter;
1966	return std::__distance(_CIter(__first), _CIter(__last), __tag);
1967	}
1968
1969	template<typename _Tp>
1970	inline ptrdiff_t
1971	__distance(_GLIBCXX_STD_C::_List_const_iterator<_Tp> __first,
1972	_GLIBCXX_STD_C::_List_const_iterator<_Tp> __last,
1973	input_iterator_tag)
1974	{
1975	typedef _GLIBCXX_STD_C::_List_node<size_t> _Sentinel;
1976	_GLIBCXX_STD_C::_List_const_iterator<_Tp> __beyond = __last;
1977	++__beyond;
1978	bool __whole = __first == __beyond;
1979	if (__builtin_constant_p (__whole) && __whole)
1980	return static_cast<const _Sentinel>(__last._M_node)->_M_valptr();
1981
1982	ptrdiff_t __n = 0;
1983	while (__first != __last)
1984	{
1985	++__first;
1986	++__n;
1987	}
1988	return __n;
1989	}
1990
1991	_GLIBCXX_END_NAMESPACE_VERSION
1992	#endif
1993	} // namespace std
1994
1995	#endif /* _STL_LIST_H */
1996