1	// Vector implementation -*- C++ -*-
2
3	// Copyright (C) 2001-2021 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
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_vector.h
52	* This is an internal header file, included by other library headers.
53	* Do not attempt to use it directly. @headername{vector}
54	*/
55
56	#ifndef _STL_VECTOR_H
57	#define _STL_VECTOR_H 1
58
59	#include <bits/stl_iterator_base_funcs.h>
60	#include <bits/functexcept.h>
61	#include <bits/concept_check.h>
62	#if __cplusplus >= 201103L
63	#include <initializer_list>
64	#endif
65	#if __cplusplus > 201703L
66	# include <compare>
67	#endif
68
69	#include <debug/assertions.h>
70
71	#if _GLIBCXX_SANITIZE_STD_ALLOCATOR && _GLIBCXX_SANITIZE_VECTOR
72	extern "C" void
73	__sanitizer_annotate_contiguous_container(const void*, const void*,
74	const void*, const void*);
75	#endif
76
77	namespace std _GLIBCXX_VISIBILITY(default)
78	{
79	_GLIBCXX_BEGIN_NAMESPACE_VERSION
80	_GLIBCXX_BEGIN_NAMESPACE_CONTAINER
81
82	/// See bits/stl_deque.h's _Deque_base for an explanation.
83	template<typename _Tp, typename _Alloc>
84	struct _Vector_base
85	{
86	typedef typename __gnu_cxx::__alloc_traits<_Alloc>::template
87	rebind<_Tp>::other _Tp_alloc_type;
88	typedef typename __gnu_cxx::__alloc_traits<_Tp_alloc_type>::pointer
89	pointer;
90
91	struct _Vector_impl_data
92	{
93	pointer _M_start;
94	pointer _M_finish;
95	pointer _M_end_of_storage;
96
97	_Vector_impl_data() _GLIBCXX_NOEXCEPT
98	: _M_start(), _M_finish(), _M_end_of_storage()
99	{ }
100
101	#if __cplusplus >= 201103L
102	_Vector_impl_data(_Vector_impl_data&& __x) noexcept
103	: _M_start(__x._M_start), _M_finish(__x._M_finish),
104	_M_end_of_storage(__x._M_end_of_storage)
105	{ __x._M_start = __x._M_finish = __x._M_end_of_storage = pointer(); }
106	#endif
107
108	void
109	_M_copy_data(_Vector_impl_data const& __x) _GLIBCXX_NOEXCEPT
110	{
111	_M_start = __x._M_start;
112	_M_finish = __x._M_finish;
113	_M_end_of_storage = __x._M_end_of_storage;
114	}
115
116	void
117	_M_swap_data(_Vector_impl_data& __x) _GLIBCXX_NOEXCEPT
118	{
119	// Do not use std::swap(_M_start, __x._M_start), etc as it loses
120	// information used by TBAA.
121	_Vector_impl_data __tmp;
122	__tmp._M_copy_data(*this);
123	_M_copy_data(__x);
124	__x._M_copy_data(__tmp);
125	}
126	};
127
128	struct _Vector_impl
129	: public _Tp_alloc_type, public _Vector_impl_data
130	{
131	_Vector_impl() _GLIBCXX_NOEXCEPT_IF(
132	is_nothrow_default_constructible<_Tp_alloc_type>::value)
133	: _Tp_alloc_type()
134	{ }
135
136	_Vector_impl(_Tp_alloc_type const& __a) _GLIBCXX_NOEXCEPT
137	: _Tp_alloc_type(__a)
138	{ }
139
140	#if __cplusplus >= 201103L
141	// Not defaulted, to enforce noexcept(true) even when
142	// !is_nothrow_move_constructible<_Tp_alloc_type>.
143	_Vector_impl(_Vector_impl&& __x) noexcept
144	: _Tp_alloc_type(std::move(__x)), _Vector_impl_data(std::move(__x))
145	{ }
146
147	_Vector_impl(_Tp_alloc_type&& __a) noexcept
148	: _Tp_alloc_type(std::move(__a))
149	{ }
150
151	_Vector_impl(_Tp_alloc_type&& __a, _Vector_impl&& __rv) noexcept
152	: _Tp_alloc_type(std::move(__a)), _Vector_impl_data(std::move(__rv))
153	{ }
154	#endif
155
156	#if _GLIBCXX_SANITIZE_STD_ALLOCATOR && _GLIBCXX_SANITIZE_VECTOR
157	template<typename = _Tp_alloc_type>
158	struct _Asan
159	{
160	typedef typename __gnu_cxx::__alloc_traits<_Tp_alloc_type>
161	::size_type size_type;
162
163	static void _S_shrink(_Vector_impl&, size_type) { }
164	static void _S_on_dealloc(_Vector_impl&) { }
165
166	typedef _Vector_impl& _Reinit;
167
168	struct _Grow
169	{
170	_Grow(_Vector_impl&, size_type) { }
171	void _M_grew(size_type) { }
172	};
173	};
174
175	// Enable ASan annotations for memory obtained from std::allocator.
176	template<typename _Up>
177	struct _Asan<allocator<_Up> >
178	{
179	typedef typename __gnu_cxx::__alloc_traits<_Tp_alloc_type>
180	::size_type size_type;
181
182	// Adjust ASan annotation for [_M_start, _M_end_of_storage) to
183	// mark end of valid region as __curr instead of __prev.
184	static void
185	_S_adjust(_Vector_impl& __impl, pointer __prev, pointer __curr)
186	{
187	__sanitizer_annotate_contiguous_container(__impl._M_start,
188	__impl._M_end_of_storage, __prev, __curr);
189	}
190
191	static void
192	_S_grow(_Vector_impl& __impl, size_type __n)
193	{ _S_adjust(__impl, __impl._M_finish, __impl._M_finish + __n); }
194
195	static void
196	_S_shrink(_Vector_impl& __impl, size_type __n)
197	{ _S_adjust(__impl, __impl._M_finish + __n, __impl._M_finish); }
198
199	static void
200	_S_on_dealloc(_Vector_impl& __impl)
201	{
202	if (__impl._M_start)
203	_S_adjust(__impl, __impl._M_finish, __impl._M_end_of_storage);
204	}
205
206	// Used on reallocation to tell ASan unused capacity is invalid.
207	struct _Reinit
208	{
209	explicit _Reinit(_Vector_impl& __impl) : _M_impl(__impl)
210	{
211	// Mark unused capacity as valid again before deallocating it.
212	_S_on_dealloc(_M_impl);
213	}
214
215	~_Reinit()
216	{
217	// Mark unused capacity as invalid after reallocation.
218	if (_M_impl._M_start)
219	_S_adjust(_M_impl, _M_impl._M_end_of_storage,
220	_M_impl._M_finish);
221	}
222
223	_Vector_impl& _M_impl;
224
225	#if __cplusplus >= 201103L
226	_Reinit(const _Reinit&) = delete;
227	_Reinit& operator=(const _Reinit&) = delete;
228	#endif
229	};
230
231	// Tell ASan when unused capacity is initialized to be valid.
232	struct _Grow
233	{
234	_Grow(_Vector_impl& __impl, size_type __n)
235	: _M_impl(__impl), _M_n(__n)
236	{ _S_grow(_M_impl, __n); }
237
238	~_Grow() { if (_M_n) _S_shrink(_M_impl, _M_n); }
239
240	void _M_grew(size_type __n) { _M_n -= __n; }
241
242	#if __cplusplus >= 201103L
243	_Grow(const _Grow&) = delete;
244	_Grow& operator=(const _Grow&) = delete;
245	#endif
246	private:
247	_Vector_impl& _M_impl;
248	size_type _M_n;
249	};
250	};
251
252	#define _GLIBCXX_ASAN_ANNOTATE_REINIT \
253	typename _Base::_Vector_impl::template _Asan<>::_Reinit const \
254	__attribute__((__unused__)) __reinit_guard(this->_M_impl)
255	#define _GLIBCXX_ASAN_ANNOTATE_GROW(n) \
256	typename _Base::_Vector_impl::template _Asan<>::_Grow \
257	__attribute__((__unused__)) __grow_guard(this->_M_impl, (n))
258	#define _GLIBCXX_ASAN_ANNOTATE_GREW(n) __grow_guard._M_grew(n)
259	#define _GLIBCXX_ASAN_ANNOTATE_SHRINK(n) \
260	_Base::_Vector_impl::template _Asan<>::_S_shrink(this->_M_impl, n)
261	#define _GLIBCXX_ASAN_ANNOTATE_BEFORE_DEALLOC \
262	_Base::_Vector_impl::template _Asan<>::_S_on_dealloc(this->_M_impl)
263	#else // ! (_GLIBCXX_SANITIZE_STD_ALLOCATOR && _GLIBCXX_SANITIZE_VECTOR)
264	#define _GLIBCXX_ASAN_ANNOTATE_REINIT
265	#define _GLIBCXX_ASAN_ANNOTATE_GROW(n)
266	#define _GLIBCXX_ASAN_ANNOTATE_GREW(n)
267	#define _GLIBCXX_ASAN_ANNOTATE_SHRINK(n)
268	#define _GLIBCXX_ASAN_ANNOTATE_BEFORE_DEALLOC
269	#endif // _GLIBCXX_SANITIZE_STD_ALLOCATOR && _GLIBCXX_SANITIZE_VECTOR
270	};
271
272	public:
273	typedef _Alloc allocator_type;
274
275	_Tp_alloc_type&
276	_M_get_Tp_allocator() _GLIBCXX_NOEXCEPT
277	{ return this->_M_impl; }
278
279	const _Tp_alloc_type&
280	_M_get_Tp_allocator() const _GLIBCXX_NOEXCEPT
281	{ return this->_M_impl; }
282
283	allocator_type
284	get_allocator() const _GLIBCXX_NOEXCEPT
285	{ return allocator_type(_M_get_Tp_allocator()); }
286
287	#if __cplusplus >= 201103L
288	_Vector_base() = default;
289	#else
290	_Vector_base() { }
291	#endif
292
293	_Vector_base(const allocator_type& __a) _GLIBCXX_NOEXCEPT
294	: _M_impl(__a) { }
295
296	// Kept for ABI compatibility.
297	#if !_GLIBCXX_INLINE_VERSION
298	_Vector_base(size_t __n)
299	: _M_impl()
300	{ _M_create_storage(__n); }
301	#endif
302
303	_Vector_base(size_t __n, const allocator_type& __a)
304	: _M_impl(__a)
305	{ _M_create_storage(__n); }
306
307	#if __cplusplus >= 201103L
308	_Vector_base(_Vector_base&&) = default;
309
310	// Kept for ABI compatibility.
311	# if !_GLIBCXX_INLINE_VERSION
312	_Vector_base(_Tp_alloc_type&& __a) noexcept
313	: _M_impl(std::move(__a)) { }
314
315	_Vector_base(_Vector_base&& __x, const allocator_type& __a)
316	: _M_impl(__a)
317	{
318	if (__x.get_allocator() == __a)
319	this->_M_impl._M_swap_data(__x._M_impl);
320	else
321	{
322	size_t __n = __x._M_impl._M_finish - __x._M_impl._M_start;
323	_M_create_storage(__n);
324	}
325	}
326	# endif
327
328	_Vector_base(const allocator_type& __a, _Vector_base&& __x)
329	: _M_impl(_Tp_alloc_type(__a), std::move(__x._M_impl))
330	{ }
331	#endif
332
333	~_Vector_base() _GLIBCXX_NOEXCEPT
334	{
335	_M_deallocate(p: _M_impl._M_start,
336	n: _M_impl._M_end_of_storage - _M_impl._M_start);
337	}
338
339	public:
340	_Vector_impl _M_impl;
341
342	pointer
343	_M_allocate(size_t __n)
344	{
345	typedef __gnu_cxx::__alloc_traits<_Tp_alloc_type> _Tr;
346	return __n != 0 ? _Tr::allocate(_M_impl, __n) : pointer();
347	}
348
349	void
350	_M_deallocate(pointer __p, size_t __n)
351	{
352	typedef __gnu_cxx::__alloc_traits<_Tp_alloc_type> _Tr;
353	if (__p)
354	_Tr::deallocate(_M_impl, __p, __n);
355	}
356
357	protected:
358	void
359	_M_create_storage(size_t __n)
360	{
361	this->_M_impl._M_start = this->_M_allocate(__n);
362	this->_M_impl._M_finish = this->_M_impl._M_start;
363	this->_M_impl._M_end_of_storage = this->_M_impl._M_start + __n;
364	}
365	};
366
367	/**
368	* @brief A standard container which offers fixed time access to
369	* individual elements in any order.
370	*
371	* @ingroup sequences
372	*
373	* @tparam _Tp Type of element.
374	* @tparam _Alloc Allocator type, defaults to allocator<_Tp>.
375	*
376	* Meets the requirements of a <a href="tables.html#65">container</a>, a
377	* <a href="tables.html#66">reversible container</a>, and a
378	* <a href="tables.html#67">sequence</a>, including the
379	* <a href="tables.html#68">optional sequence requirements</a> with the
380	* %exception of @c push_front and @c pop_front.
381	*
382	* In some terminology a %vector can be described as a dynamic
383	* C-style array, it offers fast and efficient access to individual
384	* elements in any order and saves the user from worrying about
385	* memory and size allocation. Subscripting ( @c [] ) access is
386	* also provided as with C-style arrays.
387	*/
388	template<typename _Tp, typename _Alloc = std::allocator<_Tp> >
389	class vector : protected _Vector_base<_Tp, _Alloc>
390	{
391	#ifdef _GLIBCXX_CONCEPT_CHECKS
392	// Concept requirements.
393	typedef typename _Alloc::value_type _Alloc_value_type;
394	# if __cplusplus < 201103L
395	__glibcxx_class_requires(_Tp, _SGIAssignableConcept)
396	# endif
397	__glibcxx_class_requires2(_Tp, _Alloc_value_type, _SameTypeConcept)
398	#endif
399
400	#if __cplusplus >= 201103L
401	static_assert(is_same<typename remove_cv<_Tp>::type, _Tp>::value,
402	"std::vector must have a non-const, non-volatile value_type");
403	# if __cplusplus > 201703L || defined __STRICT_ANSI__
404	static_assert(is_same<typename _Alloc::value_type, _Tp>::value,
405	"std::vector must have the same value_type as its allocator");
406	# endif
407	#endif
408
409	typedef _Vector_base<_Tp, _Alloc> _Base;
410	typedef typename _Base::_Tp_alloc_type _Tp_alloc_type;
411	typedef __gnu_cxx::__alloc_traits<_Tp_alloc_type> _Alloc_traits;
412
413	public:
414	typedef _Tp value_type;
415	typedef typename _Base::pointer pointer;
416	typedef typename _Alloc_traits::const_pointer const_pointer;
417	typedef typename _Alloc_traits::reference reference;
418	typedef typename _Alloc_traits::const_reference const_reference;
419	typedef __gnu_cxx::__normal_iterator<pointer, vector> iterator;
420	typedef __gnu_cxx::__normal_iterator<const_pointer, vector>
421	const_iterator;
422	typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
423	typedef std::reverse_iterator<iterator> reverse_iterator;
424	typedef size_t size_type;
425	typedef ptrdiff_t difference_type;
426	typedef _Alloc allocator_type;
427
428	private:
429	#if __cplusplus >= 201103L
430	static constexpr bool
431	_S_nothrow_relocate(true_type)
432	{
433	return noexcept(std::__relocate_a(std::declval<pointer>(),
434	std::declval<pointer>(),
435	std::declval<pointer>(),
436	std::declval<_Tp_alloc_type&>()));
437	}
438
439	static constexpr bool
440	_S_nothrow_relocate(false_type)
441	{ return false; }
442
443	static constexpr bool
444	_S_use_relocate()
445	{
446	// Instantiating std::__relocate_a might cause an error outside the
447	// immediate context (in __relocate_object_a's noexcept-specifier),
448	// so only do it if we know the type can be move-inserted into *this.
449	return _S_nothrow_relocate(__is_move_insertable<_Tp_alloc_type>{});
450	}
451
452	static pointer
453	_S_do_relocate(pointer __first, pointer __last, pointer __result,
454	_Tp_alloc_type& __alloc, true_type) noexcept
455	{
456	return std::__relocate_a(__first, __last, __result, __alloc);
457	}
458
459	static pointer
460	_S_do_relocate(pointer, pointer, pointer __result,
461	_Tp_alloc_type&, false_type) noexcept
462	{ return __result; }
463
464	static pointer
465	_S_relocate(pointer __first, pointer __last, pointer __result,
466	_Tp_alloc_type& __alloc) noexcept
467	{
468	using __do_it = __bool_constant<_S_use_relocate()>;
469	return _S_do_relocate(__first, __last, __result, __alloc, __do_it{});
470	}
471	#endif // C++11
472
473	protected:
474	using _Base::_M_allocate;
475	using _Base::_M_deallocate;
476	using _Base::_M_impl;
477	using _Base::_M_get_Tp_allocator;
478
479	public:
480	// [23.2.4.1] construct/copy/destroy
481	// (assign() and get_allocator() are also listed in this section)
482
483	/**
484	* @brief Creates a %vector with no elements.
485	*/
486	#if __cplusplus >= 201103L
487	vector() = default;
488	#else
489	vector() { }
490	#endif
491
492	/**
493	* @brief Creates a %vector with no elements.
494	* @param __a An allocator object.
495	*/
496	explicit
497	vector(const allocator_type& __a) _GLIBCXX_NOEXCEPT
498	: _Base(__a) { }
499
500	#if __cplusplus >= 201103L
501	/**
502	* @brief Creates a %vector with default constructed elements.
503	* @param __n The number of elements to initially create.
504	* @param __a An allocator.
505	*
506	* This constructor fills the %vector with @a __n default
507	* constructed elements.
508	*/
509	explicit
510	vector(size_type __n, const allocator_type& __a = allocator_type())
511	: _Base(_S_check_init_len(__n, __a), __a)
512	{ _M_default_initialize(__n); }
513
514	/**
515	* @brief Creates a %vector with copies of an exemplar element.
516	* @param __n The number of elements to initially create.
517	* @param __value An element to copy.
518	* @param __a An allocator.
519	*
520	* This constructor fills the %vector with @a __n copies of @a __value.
521	*/
522	vector(size_type __n, const value_type& __value,
523	const allocator_type& __a = allocator_type())
524	: _Base(_S_check_init_len(__n, __a), __a)
525	{ _M_fill_initialize(__n, __value); }
526	#else
527	/**
528	* @brief Creates a %vector with copies of an exemplar element.
529	* @param __n The number of elements to initially create.
530	* @param __value An element to copy.
531	* @param __a An allocator.
532	*
533	* This constructor fills the %vector with @a __n copies of @a __value.
534	*/
535	explicit
536	vector(size_type __n, const value_type& __value = value_type(),
537	const allocator_type& __a = allocator_type())
538	: _Base(_S_check_init_len(__n, __a), __a)
539	{ _M_fill_initialize(__n, __value); }
540	#endif
541
542	/**
543	* @brief %Vector copy constructor.
544	* @param __x A %vector of identical element and allocator types.
545	*
546	* All the elements of @a __x are copied, but any unused capacity in
547	* @a __x will not be copied
548	* (i.e. capacity() == size() in the new %vector).
549	*
550	* The newly-created %vector uses a copy of the allocator object used
551	* by @a __x (unless the allocator traits dictate a different object).
552	*/
553	vector(const vector& __x)
554	: _Base(__x.size(),
555	_Alloc_traits::_S_select_on_copy(__x._M_get_Tp_allocator()))
556	{
557	this->_M_impl._M_finish =
558	std::__uninitialized_copy_a(__x.begin(), __x.end(),
559	this->_M_impl._M_start,
560	_M_get_Tp_allocator());
561	}
562
563	#if __cplusplus >= 201103L
564	/**
565	* @brief %Vector move constructor.
566	*
567	* The newly-created %vector contains the exact contents of the
568	* moved instance.
569	* The contents of the moved instance are a valid, but unspecified
570	* %vector.
571	*/
572	vector(vector&&) noexcept = default;
573
574	/// Copy constructor with alternative allocator
575	vector(const vector& __x, const allocator_type& __a)
576	: _Base(__x.size(), __a)
577	{
578	this->_M_impl._M_finish =
579	std::__uninitialized_copy_a(__x.begin(), __x.end(),
580	this->_M_impl._M_start,
581	_M_get_Tp_allocator());
582	}
583
584	private:
585	vector(vector&& __rv, const allocator_type& __m, true_type) noexcept
586	: _Base(__m, std::move(__rv))
587	{ }
588
589	vector(vector&& __rv, const allocator_type& __m, false_type)
590	: _Base(__m)
591	{
592	if (__rv.get_allocator() == __m)
593	this->_M_impl._M_swap_data(__rv._M_impl);
594	else if (!__rv.empty())
595	{
596	this->_M_create_storage(__rv.size());
597	this->_M_impl._M_finish =
598	std::__uninitialized_move_a(__rv.begin(), __rv.end(),
599	this->_M_impl._M_start,
600	_M_get_Tp_allocator());
601	__rv.clear();
602	}
603	}
604
605	public:
606	/// Move constructor with alternative allocator
607	vector(vector&& __rv, const allocator_type& __m)
608	noexcept( noexcept(
609	vector(std::declval<vector&&>(), std::declval<const allocator_type&>(),
610	std::declval<typename _Alloc_traits::is_always_equal>())) )
611	: vector(std::move(__rv), __m, typename _Alloc_traits::is_always_equal{})
612	{ }
613
614	/**
615	* @brief Builds a %vector from an initializer list.
616	* @param __l An initializer_list.
617	* @param __a An allocator.
618	*
619	* Create a %vector consisting of copies of the elements in the
620	* initializer_list @a __l.
621	*
622	* This will call the element type's copy constructor N times
623	* (where N is @a __l.size()) and do no memory reallocation.
624	*/
625	vector(initializer_list<value_type> __l,
626	const allocator_type& __a = allocator_type())
627	: _Base(__a)
628	{
629	_M_range_initialize(__l.begin(), __l.end(),
630	random_access_iterator_tag());
631	}
632	#endif
633
634	/**
635	* @brief Builds a %vector from a range.
636	* @param __first An input iterator.
637	* @param __last An input iterator.
638	* @param __a An allocator.
639	*
640	* Create a %vector consisting of copies of the elements from
641	* [first,last).
642	*
643	* If the iterators are forward, bidirectional, or
644	* random-access, then this will call the elements' copy
645	* constructor N times (where N is distance(first,last)) and do
646	* no memory reallocation. But if only input iterators are
647	* used, then this will do at most 2N calls to the copy
648	* constructor, and logN memory reallocations.
649	*/
650	#if __cplusplus >= 201103L
651	template<typename _InputIterator,
652	typename = std::_RequireInputIter<_InputIterator>>
653	vector(_InputIterator __first, _InputIterator __last,
654	const allocator_type& __a = allocator_type())
655	: _Base(__a)
656	{
657	_M_range_initialize(__first, __last,
658	std::__iterator_category(__first));
659	}
660	#else
661	template<typename _InputIterator>
662	vector(_InputIterator __first, _InputIterator __last,
663	const allocator_type& __a = allocator_type())
664	: _Base(__a)
665	{
666	// Check whether it's an integral type. If so, it's not an iterator.
667	typedef typename std::__is_integer<_InputIterator>::__type _Integral;
668	_M_initialize_dispatch(__first, __last, _Integral());
669	}
670	#endif
671
672	/**
673	* The dtor only erases the elements, and note that if the
674	* elements themselves are pointers, the pointed-to memory is
675	* not touched in any way. Managing the pointer is the user's
676	* responsibility.
677	*/
678	~vector() _GLIBCXX_NOEXCEPT
679	{
680	std::_Destroy(this->_M_impl._M_start, this->_M_impl._M_finish,
681	_M_get_Tp_allocator());
682	_GLIBCXX_ASAN_ANNOTATE_BEFORE_DEALLOC;
683	}
684
685	/**
686	* @brief %Vector assignment operator.
687	* @param __x A %vector of identical element and allocator types.
688	*
689	* All the elements of @a __x are copied, but any unused capacity in
690	* @a __x will not be copied.
691	*
692	* Whether the allocator is copied depends on the allocator traits.
693	*/
694	vector&
695	operator=(const vector& __x);
696
697	#if __cplusplus >= 201103L
698	/**
699	* @brief %Vector move assignment operator.
700	* @param __x A %vector of identical element and allocator types.
701	*
702	* The contents of @a __x are moved into this %vector (without copying,
703	* if the allocators permit it).
704	* Afterwards @a __x is a valid, but unspecified %vector.
705	*
706	* Whether the allocator is moved depends on the allocator traits.
707	*/
708	vector&
709	operator=(vector&& __x) noexcept(_Alloc_traits::_S_nothrow_move())
710	{
711	constexpr bool __move_storage =
712	_Alloc_traits::_S_propagate_on_move_assign()
713	|| _Alloc_traits::_S_always_equal();
714	_M_move_assign(std::move(__x), __bool_constant<__move_storage>());
715	return *this;
716	}
717
718	/**
719	* @brief %Vector list assignment operator.
720	* @param __l An initializer_list.
721	*
722	* This function fills a %vector with copies of the elements in the
723	* initializer list @a __l.
724	*
725	* Note that the assignment completely changes the %vector and
726	* that the resulting %vector's size is the same as the number
727	* of elements assigned.
728	*/
729	vector&
730	operator=(initializer_list<value_type> __l)
731	{
732	this->_M_assign_aux(__l.begin(), __l.end(),
733	random_access_iterator_tag());
734	return *this;
735	}
736	#endif
737
738	/**
739	* @brief Assigns a given value to a %vector.
740	* @param __n Number of elements to be assigned.
741	* @param __val Value to be assigned.
742	*
743	* This function fills a %vector with @a __n copies of the given
744	* value. Note that the assignment completely changes the
745	* %vector and that the resulting %vector's size is the same as
746	* the number of elements assigned.
747	*/
748	void
749	assign(size_type __n, const value_type& __val)
750	{ _M_fill_assign(__n, __val); }
751
752	/**
753	* @brief Assigns a range to a %vector.
754	* @param __first An input iterator.
755	* @param __last An input iterator.
756	*
757	* This function fills a %vector with copies of the elements in the
758	* range [__first,__last).
759	*
760	* Note that the assignment completely changes the %vector and
761	* that the resulting %vector's size is the same as the number
762	* of elements assigned.
763	*/
764	#if __cplusplus >= 201103L
765	template<typename _InputIterator,
766	typename = std::_RequireInputIter<_InputIterator>>
767	void
768	assign(_InputIterator __first, _InputIterator __last)
769	{ _M_assign_dispatch(__first, __last, __false_type()); }
770	#else
771	template<typename _InputIterator>
772	void
773	assign(_InputIterator __first, _InputIterator __last)
774	{
775	// Check whether it's an integral type. If so, it's not an iterator.
776	typedef typename std::__is_integer<_InputIterator>::__type _Integral;
777	_M_assign_dispatch(__first, __last, _Integral());
778	}
779	#endif
780
781	#if __cplusplus >= 201103L
782	/**
783	* @brief Assigns an initializer list to a %vector.
784	* @param __l An initializer_list.
785	*
786	* This function fills a %vector with copies of the elements in the
787	* initializer list @a __l.
788	*
789	* Note that the assignment completely changes the %vector and
790	* that the resulting %vector's size is the same as the number
791	* of elements assigned.
792	*/
793	void
794	assign(initializer_list<value_type> __l)
795	{
796	this->_M_assign_aux(__l.begin(), __l.end(),
797	random_access_iterator_tag());
798	}
799	#endif
800
801	/// Get a copy of the memory allocation object.
802	using _Base::get_allocator;
803
804	// iterators
805	/**
806	* Returns a read/write iterator that points to the first
807	* element in the %vector. Iteration is done in ordinary
808	* element order.
809	*/
810	iterator
811	begin() _GLIBCXX_NOEXCEPT
812	{ return iterator(this->_M_impl._M_start); }
813
814	/**
815	* Returns a read-only (constant) iterator that points to the
816	* first element in the %vector. Iteration is done in ordinary
817	* element order.
818	*/
819	const_iterator
820	begin() const _GLIBCXX_NOEXCEPT
821	{ return const_iterator(this->_M_impl._M_start); }
822
823	/**
824	* Returns a read/write iterator that points one past the last
825	* element in the %vector. Iteration is done in ordinary
826	* element order.
827	*/
828	iterator
829	end() _GLIBCXX_NOEXCEPT
830	{ return iterator(this->_M_impl._M_finish); }
831
832	/**
833	* Returns a read-only (constant) iterator that points one past
834	* the last element in the %vector. Iteration is done in
835	* ordinary element order.
836	*/
837	const_iterator
838	end() const _GLIBCXX_NOEXCEPT
839	{ return const_iterator(this->_M_impl._M_finish); }
840
841	/**
842	* Returns a read/write reverse iterator that points to the
843	* last element in the %vector. Iteration is done in reverse
844	* element order.
845	*/
846	reverse_iterator
847	rbegin() _GLIBCXX_NOEXCEPT
848	{ return reverse_iterator(end()); }
849
850	/**
851	* Returns a read-only (constant) reverse iterator that points
852	* to the last element in the %vector. Iteration is done in
853	* reverse element order.
854	*/
855	const_reverse_iterator
856	rbegin() const _GLIBCXX_NOEXCEPT
857	{ return const_reverse_iterator(end()); }
858
859	/**
860	* Returns a read/write reverse iterator that points to one
861	* before the first element in the %vector. Iteration is done
862	* in reverse element order.
863	*/
864	reverse_iterator
865	rend() _GLIBCXX_NOEXCEPT
866	{ return reverse_iterator(begin()); }
867
868	/**
869	* Returns a read-only (constant) reverse iterator that points
870	* to one before the first element in the %vector. Iteration
871	* is done in reverse element order.
872	*/
873	const_reverse_iterator
874	rend() const _GLIBCXX_NOEXCEPT
875	{ return const_reverse_iterator(begin()); }
876
877	#if __cplusplus >= 201103L
878	/**
879	* Returns a read-only (constant) iterator that points to the
880	* first element in the %vector. Iteration is done in ordinary
881	* element order.
882	*/
883	const_iterator
884	cbegin() const noexcept
885	{ return const_iterator(this->_M_impl._M_start); }
886
887	/**
888	* Returns a read-only (constant) iterator that points one past
889	* the last element in the %vector. Iteration is done in
890	* ordinary element order.
891	*/
892	const_iterator
893	cend() const noexcept
894	{ return const_iterator(this->_M_impl._M_finish); }
895
896	/**
897	* Returns a read-only (constant) reverse iterator that points
898	* to the last element in the %vector. Iteration is done in
899	* reverse element order.
900	*/
901	const_reverse_iterator
902	crbegin() const noexcept
903	{ return const_reverse_iterator(end()); }
904
905	/**
906	* Returns a read-only (constant) reverse iterator that points
907	* to one before the first element in the %vector. Iteration
908	* is done in reverse element order.
909	*/
910	const_reverse_iterator
911	crend() const noexcept
912	{ return const_reverse_iterator(begin()); }
913	#endif
914
915	// [23.2.4.2] capacity
916	/** Returns the number of elements in the %vector. */
917	size_type
918	size() const _GLIBCXX_NOEXCEPT
919	{ return size_type(this->_M_impl._M_finish - this->_M_impl._M_start); }
920
921	/** Returns the size() of the largest possible %vector. */
922	size_type
923	max_size() const _GLIBCXX_NOEXCEPT
924	{ return _S_max_size(a: _M_get_Tp_allocator()); }
925
926	#if __cplusplus >= 201103L
927	/**
928	* @brief Resizes the %vector to the specified number of elements.
929	* @param __new_size Number of elements the %vector should contain.
930	*
931	* This function will %resize the %vector to the specified
932	* number of elements. If the number is smaller than the
933	* %vector's current size the %vector is truncated, otherwise
934	* default constructed elements are appended.
935	*/
936	void
937	resize(size_type __new_size)
938	{
939	if (__new_size > size())
940	_M_default_append(n: __new_size - size());
941	else if (__new_size < size())
942	_M_erase_at_end(pos: this->_M_impl._M_start + __new_size);
943	}
944
945	/**
946	* @brief Resizes the %vector to the specified number of elements.
947	* @param __new_size Number of elements the %vector should contain.
948	* @param __x Data with which new elements should be populated.
949	*
950	* This function will %resize the %vector to the specified
951	* number of elements. If the number is smaller than the
952	* %vector's current size the %vector is truncated, otherwise
953	* the %vector is extended and new elements are populated with
954	* given data.
955	*/
956	void
957	resize(size_type __new_size, const value_type& __x)
958	{
959	if (__new_size > size())
960	_M_fill_insert(pos: end(), n: __new_size - size(), __x);
961	else if (__new_size < size())
962	_M_erase_at_end(pos: this->_M_impl._M_start + __new_size);
963	}
964	#else
965	/**
966	* @brief Resizes the %vector to the specified number of elements.
967	* @param __new_size Number of elements the %vector should contain.
968	* @param __x Data with which new elements should be populated.
969	*
970	* This function will %resize the %vector to the specified
971	* number of elements. If the number is smaller than the
972	* %vector's current size the %vector is truncated, otherwise
973	* the %vector is extended and new elements are populated with
974	* given data.
975	*/
976	void
977	resize(size_type __new_size, value_type __x = value_type())
978	{
979	if (__new_size > size())
980	_M_fill_insert(end(), __new_size - size(), __x);
981	else if (__new_size < size())
982	_M_erase_at_end(this->_M_impl._M_start + __new_size);
983	}
984	#endif
985
986	#if __cplusplus >= 201103L
987	/** A non-binding request to reduce capacity() to size(). */
988	void
989	shrink_to_fit()
990	{ _M_shrink_to_fit(); }
991	#endif
992
993	/**
994	* Returns the total number of elements that the %vector can
995	* hold before needing to allocate more memory.
996	*/
997	size_type
998	capacity() const _GLIBCXX_NOEXCEPT
999	{ return size_type(this->_M_impl._M_end_of_storage
1000	- this->_M_impl._M_start); }
1001
1002	/**
1003	* Returns true if the %vector is empty. (Thus begin() would
1004	* equal end().)
1005	*/
1006	_GLIBCXX_NODISCARD bool
1007	empty() const _GLIBCXX_NOEXCEPT
1008	{ return begin() == end(); }
1009
1010	/**
1011	* @brief Attempt to preallocate enough memory for specified number of
1012	* elements.
1013	* @param __n Number of elements required.
1014	* @throw std::length_error If @a n exceeds @c max_size().
1015	*
1016	* This function attempts to reserve enough memory for the
1017	* %vector to hold the specified number of elements. If the
1018	* number requested is more than max_size(), length_error is
1019	* thrown.
1020	*
1021	* The advantage of this function is that if optimal code is a
1022	* necessity and the user can determine the number of elements
1023	* that will be required, the user can reserve the memory in
1024	* %advance, and thus prevent a possible reallocation of memory
1025	* and copying of %vector data.
1026	*/
1027	void
1028	reserve(size_type __n);
1029
1030	// element access
1031	/**
1032	* @brief Subscript access to the data contained in the %vector.
1033	* @param __n The index of the element for which data should be
1034	* accessed.
1035	* @return Read/write reference to data.
1036	*
1037	* This operator allows for easy, array-style, data access.
1038	* Note that data access with this operator is unchecked and
1039	* out_of_range lookups are not defined. (For checked lookups
1040	* see at().)
1041	*/
1042	reference
1043	operator[](size_type __n) _GLIBCXX_NOEXCEPT
1044	{
1045	__glibcxx_requires_subscript(__n);
1046	return *(this->_M_impl._M_start + __n);
1047	}
1048
1049	/**
1050	* @brief Subscript access to the data contained in the %vector.
1051	* @param __n The index of the element for which data should be
1052	* accessed.
1053	* @return Read-only (constant) reference to data.
1054	*
1055	* This operator allows for easy, array-style, data access.
1056	* Note that data access with this operator is unchecked and
1057	* out_of_range lookups are not defined. (For checked lookups
1058	* see at().)
1059	*/
1060	const_reference
1061	operator[](size_type __n) const _GLIBCXX_NOEXCEPT
1062	{
1063	__glibcxx_requires_subscript(__n);
1064	return *(this->_M_impl._M_start + __n);
1065	}
1066
1067	protected:
1068	/// Safety check used only from at().
1069	void
1070	_M_range_check(size_type __n) const
1071	{
1072	if (__n >= this->size())
1073	__throw_out_of_range_fmt(__N("vector::_M_range_check: __n "
1074	"(which is %zu) >= this->size() "
1075	"(which is %zu)"),
1076	__n, this->size());
1077	}
1078
1079	public:
1080	/**
1081	* @brief Provides access to the data contained in the %vector.
1082	* @param __n The index of the element for which data should be
1083	* accessed.
1084	* @return Read/write reference to data.
1085	* @throw std::out_of_range If @a __n is an invalid index.
1086	*
1087	* This function provides for safer data access. The parameter
1088	* is first checked that it is in the range of the vector. The
1089	* function throws out_of_range if the check fails.
1090	*/
1091	reference
1092	at(size_type __n)
1093	{
1094	_M_range_check(__n);
1095	return (*this)[__n];
1096	}
1097
1098	/**
1099	* @brief Provides access to the data contained in the %vector.
1100	* @param __n The index of the element for which data should be
1101	* accessed.
1102	* @return Read-only (constant) reference to data.
1103	* @throw std::out_of_range If @a __n is an invalid index.
1104	*
1105	* This function provides for safer data access. The parameter
1106	* is first checked that it is in the range of the vector. The
1107	* function throws out_of_range if the check fails.
1108	*/
1109	const_reference
1110	at(size_type __n) const
1111	{
1112	_M_range_check(__n);
1113	return (*this)[__n];
1114	}
1115
1116	/**
1117	* Returns a read/write reference to the data at the first
1118	* element of the %vector.
1119	*/
1120	reference
1121	front() _GLIBCXX_NOEXCEPT
1122	{
1123	__glibcxx_requires_nonempty();
1124	return *begin();
1125	}
1126
1127	/**
1128	* Returns a read-only (constant) reference to the data at the first
1129	* element of the %vector.
1130	*/
1131	const_reference
1132	front() const _GLIBCXX_NOEXCEPT
1133	{
1134	__glibcxx_requires_nonempty();
1135	return *begin();
1136	}
1137
1138	/**
1139	* Returns a read/write reference to the data at the last
1140	* element of the %vector.
1141	*/
1142	reference
1143	back() _GLIBCXX_NOEXCEPT
1144	{
1145	__glibcxx_requires_nonempty();
1146	return *(end() - 1);
1147	}
1148
1149	/**
1150	* Returns a read-only (constant) reference to the data at the
1151	* last element of the %vector.
1152	*/
1153	const_reference
1154	back() const _GLIBCXX_NOEXCEPT
1155	{
1156	__glibcxx_requires_nonempty();
1157	return *(end() - 1);
1158	}
1159
1160	// _GLIBCXX_RESOLVE_LIB_DEFECTS
1161	// DR 464. Suggestion for new member functions in standard containers.
1162	// data access
1163	/**
1164	* Returns a pointer such that [data(), data() + size()) is a valid
1165	* range. For a non-empty %vector, data() == &front().
1166	*/
1167	_Tp*
1168	data() _GLIBCXX_NOEXCEPT
1169	{ return _M_data_ptr(this->_M_impl._M_start); }
1170
1171	const _Tp*
1172	data() const _GLIBCXX_NOEXCEPT
1173	{ return _M_data_ptr(this->_M_impl._M_start); }
1174
1175	// [23.2.4.3] modifiers
1176	/**
1177	* @brief Add data to the end of the %vector.
1178	* @param __x Data to be added.
1179	*
1180	* This is a typical stack operation. The function creates an
1181	* element at the end of the %vector and assigns the given data
1182	* to it. Due to the nature of a %vector this operation can be
1183	* done in constant time if the %vector has preallocated space
1184	* available.
1185	*/
1186	void
1187	push_back(const value_type& __x)
1188	{
1189	if (this->_M_impl._M_finish != this->_M_impl._M_end_of_storage)
1190	{
1191	_GLIBCXX_ASAN_ANNOTATE_GROW(1);
1192	_Alloc_traits::construct(this->_M_impl, this->_M_impl._M_finish,
1193	__x);
1194	++this->_M_impl._M_finish;
1195	_GLIBCXX_ASAN_ANNOTATE_GREW(1);
1196	}
1197	else
1198	_M_realloc_insert(end(), __x);
1199	}
1200
1201	#if __cplusplus >= 201103L
1202	void
1203	push_back(value_type&& __x)
1204	{ emplace_back(std::move(__x)); }
1205
1206	template<typename... _Args>
1207	#if __cplusplus > 201402L
1208	reference
1209	#else
1210	void
1211	#endif
1212	emplace_back(_Args&&... __args);
1213	#endif
1214
1215	/**
1216	* @brief Removes last element.
1217	*
1218	* This is a typical stack operation. It shrinks the %vector by one.
1219	*
1220	* Note that no data is returned, and if the last element's
1221	* data is needed, it should be retrieved before pop_back() is
1222	* called.
1223	*/
1224	void
1225	pop_back() _GLIBCXX_NOEXCEPT
1226	{
1227	__glibcxx_requires_nonempty();
1228	--this->_M_impl._M_finish;
1229	_Alloc_traits::destroy(this->_M_impl, this->_M_impl._M_finish);
1230	_GLIBCXX_ASAN_ANNOTATE_SHRINK(1);
1231	}
1232
1233	#if __cplusplus >= 201103L
1234	/**
1235	* @brief Inserts an object in %vector before specified iterator.
1236	* @param __position A const_iterator into the %vector.
1237	* @param __args Arguments.
1238	* @return An iterator that points to the inserted data.
1239	*
1240	* This function will insert an object of type T constructed
1241	* with T(std::forward<Args>(args)...) before the specified location.
1242	* Note that this kind of operation could be expensive for a %vector
1243	* and if it is frequently used the user should consider using
1244	* std::list.
1245	*/
1246	template<typename... _Args>
1247	iterator
1248	emplace(const_iterator __position, _Args&&... __args)
1249	{ return _M_emplace_aux(__position, std::forward<_Args>(__args)...); }
1250
1251	/**
1252	* @brief Inserts given value into %vector before specified iterator.
1253	* @param __position A const_iterator into the %vector.
1254	* @param __x Data to be inserted.
1255	* @return An iterator that points to the inserted data.
1256	*
1257	* This function will insert a copy of the given value before
1258	* the specified location. Note that this kind of operation
1259	* could be expensive for a %vector and if it is frequently
1260	* used the user should consider using std::list.
1261	*/
1262	iterator
1263	insert(const_iterator __position, const value_type& __x);
1264	#else
1265	/**
1266	* @brief Inserts given value into %vector before specified iterator.
1267	* @param __position An iterator into the %vector.
1268	* @param __x Data to be inserted.
1269	* @return An iterator that points to the inserted data.
1270	*
1271	* This function will insert a copy of the given value before
1272	* the specified location. Note that this kind of operation
1273	* could be expensive for a %vector and if it is frequently
1274	* used the user should consider using std::list.
1275	*/
1276	iterator
1277	insert(iterator __position, const value_type& __x);
1278	#endif
1279
1280	#if __cplusplus >= 201103L
1281	/**
1282	* @brief Inserts given rvalue into %vector before specified iterator.
1283	* @param __position A const_iterator into the %vector.
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 rvalue before
1288	* the specified location. Note that this kind of operation
1289	* could be expensive for a %vector and if it is frequently
1290	* used the user should consider using std::list.
1291	*/
1292	iterator
1293	insert(const_iterator __position, value_type&& __x)
1294	{ return _M_insert_rval(__position, v: std::move(__x)); }
1295
1296	/**
1297	* @brief Inserts an initializer_list into the %vector.
1298	* @param __position An iterator into the %vector.
1299	* @param __l An initializer_list.
1300	*
1301	* This function will insert copies of the data in the
1302	* initializer_list @a l into the %vector before the location
1303	* specified by @a position.
1304	*
1305	* Note that this kind of operation could be expensive for a
1306	* %vector and if it is frequently used the user should
1307	* consider using std::list.
1308	*/
1309	iterator
1310	insert(const_iterator __position, initializer_list<value_type> __l)
1311	{
1312	auto __offset = __position - cbegin();
1313	_M_range_insert(begin() + __offset, __l.begin(), __l.end(),
1314	std::random_access_iterator_tag());
1315	return begin() + __offset;
1316	}
1317	#endif
1318
1319	#if __cplusplus >= 201103L
1320	/**
1321	* @brief Inserts a number of copies of given data into the %vector.
1322	* @param __position A const_iterator into the %vector.
1323	* @param __n Number of elements to be inserted.
1324	* @param __x Data to be inserted.
1325	* @return An iterator that points to the inserted data.
1326	*
1327	* This function will insert a specified number of copies of
1328	* the given data before the location specified by @a position.
1329	*
1330	* Note that this kind of operation could be expensive for a
1331	* %vector and if it is frequently used the user should
1332	* consider using std::list.
1333	*/
1334	iterator
1335	insert(const_iterator __position, size_type __n, const value_type& __x)
1336	{
1337	difference_type __offset = __position - cbegin();
1338	_M_fill_insert(pos: begin() + __offset, __n, __x);
1339	return begin() + __offset;
1340	}
1341	#else
1342	/**
1343	* @brief Inserts a number of copies of given data into the %vector.
1344	* @param __position An iterator into the %vector.
1345	* @param __n Number of elements to be inserted.
1346	* @param __x Data to be inserted.
1347	*
1348	* This function will insert a specified number of copies of
1349	* the given data before the location specified by @a position.
1350	*
1351	* Note that this kind of operation could be expensive for a
1352	* %vector and if it is frequently used the user should
1353	* consider using std::list.
1354	*/
1355	void
1356	insert(iterator __position, size_type __n, const value_type& __x)
1357	{ _M_fill_insert(__position, __n, __x); }
1358	#endif
1359
1360	#if __cplusplus >= 201103L
1361	/**
1362	* @brief Inserts a range into the %vector.
1363	* @param __position A const_iterator into the %vector.
1364	* @param __first An input iterator.
1365	* @param __last An input iterator.
1366	* @return An iterator that points to the inserted data.
1367	*
1368	* This function will insert copies of the data in the range
1369	* [__first,__last) into the %vector before the location specified
1370	* by @a pos.
1371	*
1372	* Note that this kind of operation could be expensive for a
1373	* %vector and if it is frequently used the user should
1374	* consider using std::list.
1375	*/
1376	template<typename _InputIterator,
1377	typename = std::_RequireInputIter<_InputIterator>>
1378	iterator
1379	insert(const_iterator __position, _InputIterator __first,
1380	_InputIterator __last)
1381	{
1382	difference_type __offset = __position - cbegin();
1383	_M_insert_dispatch(begin() + __offset,
1384	__first, __last, __false_type());
1385	return begin() + __offset;
1386	}
1387	#else
1388	/**
1389	* @brief Inserts a range into the %vector.
1390	* @param __position An iterator into the %vector.
1391	* @param __first An input iterator.
1392	* @param __last An input iterator.
1393	*
1394	* This function will insert copies of the data in the range
1395	* [__first,__last) into the %vector before the location specified
1396	* by @a pos.
1397	*
1398	* Note that this kind of operation could be expensive for a
1399	* %vector and if it is frequently used the user should
1400	* consider using std::list.
1401	*/
1402	template<typename _InputIterator>
1403	void
1404	insert(iterator __position, _InputIterator __first,
1405	_InputIterator __last)
1406	{
1407	// Check whether it's an integral type. If so, it's not an iterator.
1408	typedef typename std::__is_integer<_InputIterator>::__type _Integral;
1409	_M_insert_dispatch(__position, __first, __last, _Integral());
1410	}
1411	#endif
1412
1413	/**
1414	* @brief Remove element at given position.
1415	* @param __position Iterator pointing to element to be erased.
1416	* @return An iterator pointing to the next element (or end()).
1417	*
1418	* This function will erase the element at the given position and thus
1419	* shorten the %vector by one.
1420	*
1421	* Note This operation could be expensive and if it is
1422	* frequently used the user should consider using std::list.
1423	* The user is also cautioned that this function only erases
1424	* the element, and that if the element is itself a pointer,
1425	* the pointed-to memory is not touched in any way. Managing
1426	* the pointer is the user's responsibility.
1427	*/
1428	iterator
1429	#if __cplusplus >= 201103L
1430	erase(const_iterator __position)
1431	{ return _M_erase(begin() + (__position - cbegin())); }
1432	#else
1433	erase(iterator __position)
1434	{ return _M_erase(__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
1446	* [__first,__last) and shorten the %vector accordingly.
1447	*
1448	* Note This operation could be expensive and if it is
1449	* frequently used the user should consider using std::list.
1450	* The user is also cautioned that this function only erases
1451	* the elements, and that if the elements themselves are
1452	* pointers, the pointed-to memory is not touched in any way.
1453	* Managing the pointer is the user's responsibility.
1454	*/
1455	iterator
1456	#if __cplusplus >= 201103L
1457	erase(const_iterator __first, const_iterator __last)
1458	{
1459	const auto __beg = begin();
1460	const auto __cbeg = cbegin();
1461	return _M_erase(__beg + (__first - __cbeg), __beg + (__last - __cbeg));
1462	}
1463	#else
1464	erase(iterator __first, iterator __last)
1465	{ return _M_erase(__first, __last); }
1466	#endif
1467
1468	/**
1469	* @brief Swaps data with another %vector.
1470	* @param __x A %vector of the same element and allocator types.
1471	*
1472	* This exchanges the elements between two vectors in constant time.
1473	* (Three pointers, so it should be quite fast.)
1474	* Note that the global std::swap() function is specialized such that
1475	* std::swap(v1,v2) will feed to this function.
1476	*
1477	* Whether the allocators are swapped depends on the allocator traits.
1478	*/
1479	void
1480	swap(vector& __x) _GLIBCXX_NOEXCEPT
1481	{
1482	#if __cplusplus >= 201103L
1483	__glibcxx_assert(_Alloc_traits::propagate_on_container_swap::value
1484	|| _M_get_Tp_allocator() == __x._M_get_Tp_allocator());
1485	#endif
1486	this->_M_impl._M_swap_data(__x._M_impl);
1487	_Alloc_traits::_S_on_swap(_M_get_Tp_allocator(),
1488	__x._M_get_Tp_allocator());
1489	}
1490
1491	/**
1492	* Erases all the elements. Note that this function only erases the
1493	* elements, and that if the elements themselves are pointers, the
1494	* pointed-to memory is not touched in any way. Managing the pointer is
1495	* the user's responsibility.
1496	*/
1497	void
1498	clear() _GLIBCXX_NOEXCEPT
1499	{ _M_erase_at_end(pos: this->_M_impl._M_start); }
1500
1501	protected:
1502	/**
1503	* Memory expansion handler. Uses the member allocation function to
1504	* obtain @a n bytes of memory, and then copies [first,last) into it.
1505	*/
1506	template<typename _ForwardIterator>
1507	pointer
1508	_M_allocate_and_copy(size_type __n,
1509	_ForwardIterator __first, _ForwardIterator __last)
1510	{
1511	pointer __result = this->_M_allocate(__n);
1512	__try
1513	{
1514	std::__uninitialized_copy_a(__first, __last, __result,
1515	_M_get_Tp_allocator());
1516	return __result;
1517	}
1518	__catch(...)
1519	{
1520	_M_deallocate(__result, __n);
1521	__throw_exception_again;
1522	}
1523	}
1524
1525
1526	// Internal constructor functions follow.
1527
1528	// Called by the range constructor to implement [23.1.1]/9
1529
1530	#if __cplusplus < 201103L
1531	// _GLIBCXX_RESOLVE_LIB_DEFECTS
1532	// 438. Ambiguity in the "do the right thing" clause
1533	template<typename _Integer>
1534	void
1535	_M_initialize_dispatch(_Integer __n, _Integer __value, __true_type)
1536	{
1537	this->_M_impl._M_start = _M_allocate(_S_check_init_len(
1538	static_cast<size_type>(__n), _M_get_Tp_allocator()));
1539	this->_M_impl._M_end_of_storage =
1540	this->_M_impl._M_start + static_cast<size_type>(__n);
1541	_M_fill_initialize(static_cast<size_type>(__n), __value);
1542	}
1543
1544	// Called by the range constructor to implement [23.1.1]/9
1545	template<typename _InputIterator>
1546	void
1547	_M_initialize_dispatch(_InputIterator __first, _InputIterator __last,
1548	__false_type)
1549	{
1550	_M_range_initialize(__first, __last,
1551	std::__iterator_category(__first));
1552	}
1553	#endif
1554
1555	// Called by the second initialize_dispatch above
1556	template<typename _InputIterator>
1557	void
1558	_M_range_initialize(_InputIterator __first, _InputIterator __last,
1559	std::input_iterator_tag)
1560	{
1561	__try {
1562	for (; __first != __last; ++__first)
1563	#if __cplusplus >= 201103L
1564	emplace_back(*__first);
1565	#else
1566	push_back(*__first);
1567	#endif
1568	} __catch(...) {
1569	clear();
1570	__throw_exception_again;
1571	}
1572	}
1573
1574	// Called by the second initialize_dispatch above
1575	template<typename _ForwardIterator>
1576	void
1577	_M_range_initialize(_ForwardIterator __first, _ForwardIterator __last,
1578	std::forward_iterator_tag)
1579	{
1580	const size_type __n = std::distance(__first, __last);
1581	this->_M_impl._M_start
1582	= this->_M_allocate(_S_check_init_len(__n, a: _M_get_Tp_allocator()));
1583	this->_M_impl._M_end_of_storage = this->_M_impl._M_start + __n;
1584	this->_M_impl._M_finish =
1585	std::__uninitialized_copy_a(__first, __last,
1586	this->_M_impl._M_start,
1587	_M_get_Tp_allocator());
1588	}
1589
1590	// Called by the first initialize_dispatch above and by the
1591	// vector(n,value,a) constructor.
1592	void
1593	_M_fill_initialize(size_type __n, const value_type& __value)
1594	{
1595	this->_M_impl._M_finish =
1596	std::__uninitialized_fill_n_a(this->_M_impl._M_start, __n, __value,
1597	_M_get_Tp_allocator());
1598	}
1599
1600	#if __cplusplus >= 201103L
1601	// Called by the vector(n) constructor.
1602	void
1603	_M_default_initialize(size_type __n)
1604	{
1605	this->_M_impl._M_finish =
1606	std::__uninitialized_default_n_a(this->_M_impl._M_start, __n,
1607	_M_get_Tp_allocator());
1608	}
1609	#endif
1610
1611	// Internal assign functions follow. The *_aux functions do the actual
1612	// assignment work for the range versions.
1613
1614	// Called by the range assign to implement [23.1.1]/9
1615
1616	// _GLIBCXX_RESOLVE_LIB_DEFECTS
1617	// 438. Ambiguity in the "do the right thing" clause
1618	template<typename _Integer>
1619	void
1620	_M_assign_dispatch(_Integer __n, _Integer __val, __true_type)
1621	{ _M_fill_assign(__n, __val); }
1622
1623	// Called by the range assign to implement [23.1.1]/9
1624	template<typename _InputIterator>
1625	void
1626	_M_assign_dispatch(_InputIterator __first, _InputIterator __last,
1627	__false_type)
1628	{ _M_assign_aux(__first, __last, std::__iterator_category(__first)); }
1629
1630	// Called by the second assign_dispatch above
1631	template<typename _InputIterator>
1632	void
1633	_M_assign_aux(_InputIterator __first, _InputIterator __last,
1634	std::input_iterator_tag);
1635
1636	// Called by the second assign_dispatch above
1637	template<typename _ForwardIterator>
1638	void
1639	_M_assign_aux(_ForwardIterator __first, _ForwardIterator __last,
1640	std::forward_iterator_tag);
1641
1642	// Called by assign(n,t), and the range assign when it turns out
1643	// to be the same thing.
1644	void
1645	_M_fill_assign(size_type __n, const value_type& __val);
1646
1647	// Internal insert functions follow.
1648
1649	// Called by the range insert to implement [23.1.1]/9
1650
1651	// _GLIBCXX_RESOLVE_LIB_DEFECTS
1652	// 438. Ambiguity in the "do the right thing" clause
1653	template<typename _Integer>
1654	void
1655	_M_insert_dispatch(iterator __pos, _Integer __n, _Integer __val,
1656	__true_type)
1657	{ _M_fill_insert(__pos, __n, x: __val); }
1658
1659	// Called by the range insert to implement [23.1.1]/9
1660	template<typename _InputIterator>
1661	void
1662	_M_insert_dispatch(iterator __pos, _InputIterator __first,
1663	_InputIterator __last, __false_type)
1664	{
1665	_M_range_insert(__pos, __first, __last,
1666	std::__iterator_category(__first));
1667	}
1668
1669	// Called by the second insert_dispatch above
1670	template<typename _InputIterator>
1671	void
1672	_M_range_insert(iterator __pos, _InputIterator __first,
1673	_InputIterator __last, std::input_iterator_tag);
1674
1675	// Called by the second insert_dispatch above
1676	template<typename _ForwardIterator>
1677	void
1678	_M_range_insert(iterator __pos, _ForwardIterator __first,
1679	_ForwardIterator __last, std::forward_iterator_tag);
1680
1681	// Called by insert(p,n,x), and the range insert when it turns out to be
1682	// the same thing.
1683	void
1684	_M_fill_insert(iterator __pos, size_type __n, const value_type& __x);
1685
1686	#if __cplusplus >= 201103L
1687	// Called by resize(n).
1688	void
1689	_M_default_append(size_type __n);
1690
1691	bool
1692	_M_shrink_to_fit();
1693	#endif
1694
1695	#if __cplusplus < 201103L
1696	// Called by insert(p,x)
1697	void
1698	_M_insert_aux(iterator __position, const value_type& __x);
1699
1700	void
1701	_M_realloc_insert(iterator __position, const value_type& __x);
1702	#else
1703	// A value_type object constructed with _Alloc_traits::construct()
1704	// and destroyed with _Alloc_traits::destroy().
1705	struct _Temporary_value
1706	{
1707	template<typename... _Args>
1708	explicit
1709	_Temporary_value(vector* __vec, _Args&&... __args) : _M_this(__vec)
1710	{
1711	_Alloc_traits::construct(_M_this->_M_impl, _M_ptr(),
1712	std::forward<_Args>(__args)...);
1713	}
1714
1715	~_Temporary_value()
1716	{ _Alloc_traits::destroy(_M_this->_M_impl, _M_ptr()); }
1717
1718	value_type&
1719	_M_val() { return *_M_ptr(); }
1720
1721	private:
1722	_Tp*
1723	_M_ptr() { return reinterpret_cast<_Tp*>(&__buf); }
1724
1725	vector* _M_this;
1726	typename aligned_storage<sizeof(_Tp), alignof(_Tp)>::type __buf;
1727	};
1728
1729	// Called by insert(p,x) and other functions when insertion needs to
1730	// reallocate or move existing elements. _Arg is either _Tp& or _Tp.
1731	template<typename _Arg>
1732	void
1733	_M_insert_aux(iterator __position, _Arg&& __arg);
1734
1735	template<typename... _Args>
1736	void
1737	_M_realloc_insert(iterator __position, _Args&&... __args);
1738
1739	// Either move-construct at the end, or forward to _M_insert_aux.
1740	iterator
1741	_M_insert_rval(const_iterator __position, value_type&& __v);
1742
1743	// Try to emplace at the end, otherwise forward to _M_insert_aux.
1744	template<typename... _Args>
1745	iterator
1746	_M_emplace_aux(const_iterator __position, _Args&&... __args);
1747
1748	// Emplacing an rvalue of the correct type can use _M_insert_rval.
1749	iterator
1750	_M_emplace_aux(const_iterator __position, value_type&& __v)
1751	{ return _M_insert_rval(__position, v: std::move(__v)); }
1752	#endif
1753
1754	// Called by _M_fill_insert, _M_insert_aux etc.
1755	size_type
1756	_M_check_len(size_type __n, const char* __s) const
1757	{
1758	if (max_size() - size() < __n)
1759	__throw_length_error(__N(__s));
1760
1761	const size_type __len = size() + (std::max)(size(), __n);
1762	return (__len < size() || __len > max_size()) ? max_size() : __len;
1763	}
1764
1765	// Called by constructors to check initial size.
1766	static size_type
1767	_S_check_init_len(size_type __n, const allocator_type& __a)
1768	{
1769	if (__n > _S_max_size(a: _Tp_alloc_type(__a)))
1770	__throw_length_error(
1771	__N("cannot create std::vector larger than max_size()"));
1772	return __n;
1773	}
1774
1775	static size_type
1776	_S_max_size(const _Tp_alloc_type& __a) _GLIBCXX_NOEXCEPT
1777	{
1778	// std::distance(begin(), end()) cannot be greater than PTRDIFF_MAX,
1779	// and realistically we can't store more than PTRDIFF_MAX/sizeof(T)
1780	// (even if std::allocator_traits::max_size says we can).
1781	const size_t __diffmax
1782	= __gnu_cxx::__numeric_traits<ptrdiff_t>::__max / sizeof(_Tp);
1783	const size_t __allocmax = _Alloc_traits::max_size(__a);
1784	return (std::min)(a: __diffmax, b: __allocmax);
1785	}
1786
1787	// Internal erase functions follow.
1788
1789	// Called by erase(q1,q2), clear(), resize(), _M_fill_assign,
1790	// _M_assign_aux.
1791	void
1792	_M_erase_at_end(pointer __pos) _GLIBCXX_NOEXCEPT
1793	{
1794	if (size_type __n = this->_M_impl._M_finish - __pos)
1795	{
1796	std::_Destroy(__pos, this->_M_impl._M_finish,
1797	_M_get_Tp_allocator());
1798	this->_M_impl._M_finish = __pos;
1799	_GLIBCXX_ASAN_ANNOTATE_SHRINK(__n);
1800	}
1801	}
1802
1803	iterator
1804	_M_erase(iterator __position);
1805
1806	iterator
1807	_M_erase(iterator __first, iterator __last);
1808
1809	#if __cplusplus >= 201103L
1810	private:
1811	// Constant-time move assignment when source object's memory can be
1812	// moved, either because the source's allocator will move too
1813	// or because the allocators are equal.
1814	void
1815	_M_move_assign(vector&& __x, true_type) noexcept
1816	{
1817	vector __tmp(get_allocator());
1818	this->_M_impl._M_swap_data(__x._M_impl);
1819	__tmp._M_impl._M_swap_data(__x._M_impl);
1820	std::__alloc_on_move(_M_get_Tp_allocator(), __x._M_get_Tp_allocator());
1821	}
1822
1823	// Do move assignment when it might not be possible to move source
1824	// object's memory, resulting in a linear-time operation.
1825	void
1826	_M_move_assign(vector&& __x, false_type)
1827	{
1828	if (__x._M_get_Tp_allocator() == this->_M_get_Tp_allocator())
1829	_M_move_assign(std::move(__x), true_type());
1830	else
1831	{
1832	// The rvalue's allocator cannot be moved and is not equal,
1833	// so we need to individually move each element.
1834	this->_M_assign_aux(std::make_move_iterator(__x.begin()),
1835	std::make_move_iterator(__x.end()),
1836	std::random_access_iterator_tag());
1837	__x.clear();
1838	}
1839	}
1840	#endif
1841
1842	template<typename _Up>
1843	_Up*
1844	_M_data_ptr(_Up* __ptr) const _GLIBCXX_NOEXCEPT
1845	{ return __ptr; }
1846
1847	#if __cplusplus >= 201103L
1848	template<typename _Ptr>
1849	typename std::pointer_traits<_Ptr>::element_type*
1850	_M_data_ptr(_Ptr __ptr) const
1851	{ return empty() ? nullptr : std::__to_address(__ptr); }
1852	#else
1853	template<typename _Up>
1854	_Up*
1855	_M_data_ptr(_Up* __ptr) _GLIBCXX_NOEXCEPT
1856	{ return __ptr; }
1857
1858	template<typename _Ptr>
1859	value_type*
1860	_M_data_ptr(_Ptr __ptr)
1861	{ return empty() ? (value_type*)0 : __ptr.operator->(); }
1862
1863	template<typename _Ptr>
1864	const value_type*
1865	_M_data_ptr(_Ptr __ptr) const
1866	{ return empty() ? (const value_type*)0 : __ptr.operator->(); }
1867	#endif
1868	};
1869
1870	#if __cpp_deduction_guides >= 201606
1871	template<typename _InputIterator, typename _ValT
1872	= typename iterator_traits<_InputIterator>::value_type,
1873	typename _Allocator = allocator<_ValT>,
1874	typename = _RequireInputIter<_InputIterator>,
1875	typename = _RequireAllocator<_Allocator>>
1876	vector(_InputIterator, _InputIterator, _Allocator = _Allocator())
1877	-> vector<_ValT, _Allocator>;
1878	#endif
1879
1880	/**
1881	* @brief Vector equality comparison.
1882	* @param __x A %vector.
1883	* @param __y A %vector of the same type as @a __x.
1884	* @return True iff the size and elements of the vectors are equal.
1885	*
1886	* This is an equivalence relation. It is linear in the size of the
1887	* vectors. Vectors are considered equivalent if their sizes are equal,
1888	* and if corresponding elements compare equal.
1889	*/
1890	template<typename _Tp, typename _Alloc>
1891	inline bool
1892	operator==(const vector<_Tp, _Alloc>& __x, const vector<_Tp, _Alloc>& __y)
1893	{ return (__x.size() == __y.size()
1894	&& std::equal(__x.begin(), __x.end(), __y.begin())); }
1895
1896	#if __cpp_lib_three_way_comparison
1897	/**
1898	* @brief Vector ordering relation.
1899	* @param __x A `vector`.
1900	* @param __y A `vector` of the same type as `__x`.
1901	* @return A value indicating whether `__x` is less than, equal to,
1902	* greater than, or incomparable with `__y`.
1903	*
1904	* See `std::lexicographical_compare_three_way()` for how the determination
1905	* is made. This operator is used to synthesize relational operators like
1906	* `<` and `>=` etc.
1907	*/
1908	template<typename _Tp, typename _Alloc>
1909	inline __detail::__synth3way_t<_Tp>
1910	operator<=>(const vector<_Tp, _Alloc>& __x, const vector<_Tp, _Alloc>& __y)
1911	{
1912	return std::lexicographical_compare_three_way(__x.begin(), __x.end(),
1913	__y.begin(), __y.end(),
1914	__detail::__synth3way);
1915	}
1916	#else
1917	/**
1918	* @brief Vector ordering relation.
1919	* @param __x A %vector.
1920	* @param __y A %vector of the same type as @a __x.
1921	* @return True iff @a __x is lexicographically less than @a __y.
1922	*
1923	* This is a total ordering relation. It is linear in the size of the
1924	* vectors. The elements must be comparable with @c <.
1925	*
1926	* See std::lexicographical_compare() for how the determination is made.
1927	*/
1928	template<typename _Tp, typename _Alloc>
1929	inline bool
1930	operator<(const vector<_Tp, _Alloc>& __x, const vector<_Tp, _Alloc>& __y)
1931	{ return std::lexicographical_compare(__x.begin(), __x.end(),
1932	__y.begin(), __y.end()); }
1933
1934	/// Based on operator==
1935	template<typename _Tp, typename _Alloc>
1936	inline bool
1937	operator!=(const vector<_Tp, _Alloc>& __x, const vector<_Tp, _Alloc>& __y)
1938	{ return !(__x == __y); }
1939
1940	/// Based on operator<
1941	template<typename _Tp, typename _Alloc>
1942	inline bool
1943	operator>(const vector<_Tp, _Alloc>& __x, const vector<_Tp, _Alloc>& __y)
1944	{ return __y < __x; }
1945
1946	/// Based on operator<
1947	template<typename _Tp, typename _Alloc>
1948	inline bool
1949	operator<=(const vector<_Tp, _Alloc>& __x, const vector<_Tp, _Alloc>& __y)
1950	{ return !(__y < __x); }
1951
1952	/// Based on operator<
1953	template<typename _Tp, typename _Alloc>
1954	inline bool
1955	operator>=(const vector<_Tp, _Alloc>& __x, const vector<_Tp, _Alloc>& __y)
1956	{ return !(__x < __y); }
1957	#endif // three-way comparison
1958
1959	/// See std::vector::swap().
1960	template<typename _Tp, typename _Alloc>
1961	inline void
1962	swap(vector<_Tp, _Alloc>& __x, vector<_Tp, _Alloc>& __y)
1963	_GLIBCXX_NOEXCEPT_IF(noexcept(__x.swap(__y)))
1964	{ __x.swap(__y); }
1965
1966	_GLIBCXX_END_NAMESPACE_CONTAINER
1967
1968	#if __cplusplus >= 201703L
1969	namespace __detail::__variant
1970	{
1971	template<typename> struct _Never_valueless_alt; // see <variant>
1972
1973	// Provide the strong exception-safety guarantee when emplacing a
1974	// vector into a variant, but only if move assignment cannot throw.
1975	template<typename _Tp, typename _Alloc>
1976	struct _Never_valueless_alt<_GLIBCXX_STD_C::vector<_Tp, _Alloc>>
1977	: std::is_nothrow_move_assignable<_GLIBCXX_STD_C::vector<_Tp, _Alloc>>
1978	{ };
1979	} // namespace __detail::__variant
1980	#endif // C++17
1981
1982	_GLIBCXX_END_NAMESPACE_VERSION
1983	} // namespace std
1984
1985	#endif /* _STL_VECTOR_H */
1986