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