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

1	// Vector implementation -- C++ --
2
3	// Copyright (C) 2001-2017 Free Software Foundation, Inc.
4	//
5	// This file is part of the GNU ISO C++ Library. This library is free
6	// software; you can redistribute it and/or modify it under the
7	// terms of the GNU General Public License as published by the
8	// Free Software Foundation; either version 3, or (at your option)
9	// any later version.
10
11	// This library is distributed in the hope that it will be useful,
12	// but WITHOUT ANY WARRANTY; without even the implied warranty of
13	// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14	// GNU General Public License for more details.
15
16	// Under Section 7 of GPL version 3, you are granted additional
17	// permissions described in the GCC Runtime Library Exception, version
18	// 3.1, as published by the Free Software Foundation.
19
20	// You should have received a copy of the GNU General Public License and
21	// a copy of the GCC Runtime Library Exception along with this program;
22	// see the files COPYING3 and COPYING.RUNTIME respectively. If not, see
23	// <http://www.gnu.org/licenses/>.
24
25	/*
26	*
27	* Copyright (c) 1994
28	* Hewlett-Packard Company
29	*
30	* Permission to use, copy, modify, distribute and sell this software
31	* and its documentation for any purpose is hereby granted without fee,
32	* provided that the above copyright notice appear in all copies and
33	* that both that copyright notice and this permission notice appear
34	* in supporting documentation. Hewlett-Packard Company makes no
35	* representations about the suitability of this software for any
36	* purpose. It is provided "as is" without express or implied warranty.
37	*
38	*
39	* Copyright (c) 1996
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
66	#include <debug/assertions.h>
67
68	namespace std _GLIBCXX_VISIBILITY(default)
69	{
70	_GLIBCXX_BEGIN_NAMESPACE_CONTAINER
71
72	/// See bits/stl_deque.h's _Deque_base for an explanation.
73	template<typename _Tp, typename _Alloc>
74	struct _Vector_base
75	{
76	typedef typename __gnu_cxx::__alloc_traits<_Alloc>::template
77	rebind<_Tp>::other _Tp_alloc_type;
78	typedef typename __gnu_cxx::__alloc_traits<_Tp_alloc_type>::pointer
79	pointer;
80
81	struct _Vector_impl
82	: public _Tp_alloc_type
83	{
84	pointer _M_start;
85	pointer _M_finish;
86	pointer _M_end_of_storage;
87
88	_Vector_impl()
89	: _Tp_alloc_type(), _M_start(), _M_finish(), _M_end_of_storage()
90	{ }
91
92	_Vector_impl(_Tp_alloc_type const& __a) _GLIBCXX_NOEXCEPT
93	: _Tp_alloc_type(__a), _M_start(), _M_finish(), _M_end_of_storage()
94	{ }
95
96	#if __cplusplus >= 201103L
97	_Vector_impl(_Tp_alloc_type&& __a) noexcept
98	: _Tp_alloc_type(std::move(__a)),
99	_M_start(), _M_finish(), _M_end_of_storage()
100	{ }
101	#endif
102
103	void _M_swap_data(_Vector_impl& __x) _GLIBCXX_NOEXCEPT
104	{
105	std::swap(_M_start, __x._M_start);
106	std::swap(_M_finish, __x._M_finish);
107	std::swap(_M_end_of_storage, __x._M_end_of_storage);
108	}
109	};
110
111	public:
112	typedef _Alloc allocator_type;
113
114	_Tp_alloc_type&
115	_M_get_Tp_allocator() _GLIBCXX_NOEXCEPT
116	{ return static_cast<_Tp_alloc_type>(&this->_M_impl); }
117
118	const _Tp_alloc_type&
119	_M_get_Tp_allocator() const _GLIBCXX_NOEXCEPT
120	{ return static_cast<const _Tp_alloc_type>(&this->_M_impl); }
121
122	allocator_type
123	get_allocator() const _GLIBCXX_NOEXCEPT
124	{ return allocator_type(_M_get_Tp_allocator()); }
125
126	_Vector_base()
127	: _M_impl() { }
128
129	_Vector_base(const allocator_type& __a) _GLIBCXX_NOEXCEPT
130	: _M_impl(__a) { }
131
132	_Vector_base(size_t __n)
133	: _M_impl()
134	{ _M_create_storage(__n); }
135
136	_Vector_base(size_t __n, const allocator_type& __a)
137	: _M_impl(__a)
138	{ _M_create_storage(__n); }
139
140	#if __cplusplus >= 201103L
141	_Vector_base(_Tp_alloc_type&& __a) noexcept
142	: _M_impl(std::move(__a)) { }
143
144	_Vector_base(_Vector_base&& __x) noexcept
145	: _M_impl(std::move(__x._M_get_Tp_allocator()))
146	{ this->_M_impl._M_swap_data(__x._M_impl); }
147
148	_Vector_base(_Vector_base&& __x, const allocator_type& __a)
149	: _M_impl(__a)
150	{
151	if (__x.get_allocator() == __a)
152	this->_M_impl._M_swap_data(__x._M_impl);
153	else
154	{
155	size_t __n = __x._M_impl._M_finish - __x._M_impl._M_start;
156	_M_create_storage(__n);
157	}
158	}
159	#endif
160
161	~_Vector_base() _GLIBCXX_NOEXCEPT
162	{ _M_deallocate(this->_M_impl._M_start, this->_M_impl._M_end_of_storage
163	- this->_M_impl._M_start); }
164
165	public:
166	_Vector_impl _M_impl;
167
168	pointer
169	_M_allocate(size_t __n)
170	{
171	typedef __gnu_cxx::__alloc_traits<_Tp_alloc_type> _Tr;
172	return __n != 0 ? _Tr::allocate(_M_impl, __n) : pointer();
173	}
174
175	void
176	_M_deallocate(pointer __p, size_t __n)
177	{
178	typedef __gnu_cxx::__alloc_traits<_Tp_alloc_type> _Tr;
179	if (__p)
180	_Tr::deallocate(_M_impl, __p, __n);
181	}
182
183	private:
184	void
185	_M_create_storage(size_t __n)
186	{
187	this->_M_impl._M_start = this->_M_allocate(__n);
188	this->_M_impl._M_finish = this->_M_impl._M_start;
189	this->_M_impl._M_end_of_storage = this->_M_impl._M_start + __n;
190	}
191	};
192
193
194	/**
195	* @brief A standard container which offers fixed time access to
196	* individual elements in any order.
197	*
198	* @ingroup sequences
199	*
200	* @tparam _Tp Type of element.
201	* @tparam _Alloc Allocator type, defaults to allocator<_Tp>.
202	*
203	* Meets the requirements of a <a href="tables.html#65">container</a>, a
204	* <a href="tables.html#66">reversible container</a>, and a
205	* <a href="tables.html#67">sequence</a>, including the
206	* <a href="tables.html#68">optional sequence requirements</a> with the
207	* %exception of @c push_front and @c pop_front.
208	*
209	* In some terminology a %vector can be described as a dynamic
210	* C-style array, it offers fast and efficient access to individual
211	* elements in any order and saves the user from worrying about
212	* memory and size allocation. Subscripting ( @c [] ) access is
213	* also provided as with C-style arrays.
214	*/
215	template<typename _Tp, typename _Alloc = std::allocator<_Tp> >
216	class vector : protected _Vector_base<_Tp, _Alloc>
217	{
218	#ifdef _GLIBCXX_CONCEPT_CHECKS
219	// Concept requirements.
220	typedef typename _Alloc::value_type _Alloc_value_type;
221	# if __cplusplus < 201103L
222	__glibcxx_class_requires(_Tp, _SGIAssignableConcept)
223	# endif
224	__glibcxx_class_requires2(_Tp, _Alloc_value_type, _SameTypeConcept)
225	#endif
226
227	typedef _Vector_base<_Tp, _Alloc> _Base;
228	typedef typename _Base::_Tp_alloc_type _Tp_alloc_type;
229	typedef __gnu_cxx::__alloc_traits<_Tp_alloc_type> _Alloc_traits;
230
231	public:
232	typedef _Tp value_type;
233	typedef typename _Base::pointer pointer;
234	typedef typename _Alloc_traits::const_pointer const_pointer;
235	typedef typename _Alloc_traits::reference reference;
236	typedef typename _Alloc_traits::const_reference const_reference;
237	typedef __gnu_cxx::__normal_iterator<pointer, vector> iterator;
238	typedef __gnu_cxx::__normal_iterator<const_pointer, vector>
239	const_iterator;
240	typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
241	typedef std::reverse_iterator<iterator> reverse_iterator;
242	typedef size_t size_type;
243	typedef ptrdiff_t difference_type;
244	typedef _Alloc allocator_type;
245
246	protected:
247	using _Base::_M_allocate;
248	using _Base::_M_deallocate;
249	using _Base::_M_impl;
250	using _Base::_M_get_Tp_allocator;
251
252	public:
253	// [23.2.4.1] construct/copy/destroy
254	// (assign() and get_allocator() are also listed in this section)
255
256	/**
257	* @brief Creates a %vector with no elements.
258	*/
259	vector()
260	#if __cplusplus >= 201103L
261	noexcept(is_nothrow_default_constructible<_Alloc>::value)
262	#endif
263	: _Base() { }
264
265	/**
266	* @brief Creates a %vector with no elements.
267	* @param __a An allocator object.
268	*/
269	explicit
270	vector(const allocator_type& __a) _GLIBCXX_NOEXCEPT
271	: _Base(__a) { }
272
273	#if __cplusplus >= 201103L
274	/**
275	* @brief Creates a %vector with default constructed elements.
276	* @param __n The number of elements to initially create.
277	* @param __a An allocator.
278	*
279	* This constructor fills the %vector with @a __n default
280	* constructed elements.
281	*/
282	explicit
283	vector(size_type __n, const allocator_type& __a = allocator_type())
284	: _Base(__n, __a)
285	{ _M_default_initialize(__n); }
286
287	/**
288	* @brief Creates a %vector with copies of an exemplar element.
289	* @param __n The number of elements to initially create.
290	* @param __value An element to copy.
291	* @param __a An allocator.
292	*
293	* This constructor fills the %vector with @a __n copies of @a __value.
294	*/
295	vector(size_type __n, const value_type& __value,
296	const allocator_type& __a = allocator_type())
297	: _Base(__n, __a)
298	{ _M_fill_initialize(__n, __value); }
299	#else
300	/**
301	* @brief Creates a %vector with copies of an exemplar element.
302	* @param __n The number of elements to initially create.
303	* @param __value An element to copy.
304	* @param __a An allocator.
305	*
306	* This constructor fills the %vector with @a __n copies of @a __value.
307	*/
308	explicit
309	vector(size_type __n, const value_type& __value = value_type(),
310	const allocator_type& __a = allocator_type())
311	: _Base(__n, __a)
312	{ _M_fill_initialize(__n, __value); }
313	#endif
314
315	/**
316	* @brief %Vector copy constructor.
317	* @param __x A %vector of identical element and allocator types.
318	*
319	* All the elements of @a __x are copied, but any unused capacity in
320	* @a __x will not be copied
321	* (i.e. capacity() == size() in the new %vector).
322	*
323	* The newly-created %vector uses a copy of the allocator object used
324	* by @a __x (unless the allocator traits dictate a different object).
325	*/
326	vector(const vector& __x)
327	: _Base(__x.size(),
328	_Alloc_traits::_S_select_on_copy(__x._M_get_Tp_allocator()))
329	{
330	this->_M_impl._M_finish =
331	std::__uninitialized_copy_a(__x.begin(), __x.end(),
332	this->_M_impl._M_start,
333	_M_get_Tp_allocator());
334	}
335
336	#if __cplusplus >= 201103L
337	/**
338	* @brief %Vector move constructor.
339	* @param __x A %vector of identical element and allocator types.
340	*
341	* The newly-created %vector contains the exact contents of @a __x.
342	* The contents of @a __x are a valid, but unspecified %vector.
343	*/
344	vector(vector&& __x) noexcept
345	: _Base(std::move(__x)) { }
346
347	/// Copy constructor with alternative allocator
348	vector(const vector& __x, const allocator_type& __a)
349	: _Base(__x.size(), __a)
350	{
351	this->_M_impl._M_finish =
352	std::__uninitialized_copy_a(__x.begin(), __x.end(),
353	this->_M_impl._M_start,
354	_M_get_Tp_allocator());
355	}
356
357	/// Move constructor with alternative allocator
358	vector(vector&& __rv, const allocator_type& __m)
359	noexcept(_Alloc_traits::_S_always_equal())
360	: _Base(std::move(__rv), __m)
361	{
362	if (__rv.get_allocator() != __m)
363	{
364	this->_M_impl._M_finish =
365	std::__uninitialized_move_a(__rv.begin(), __rv.end(),
366	this->_M_impl._M_start,
367	_M_get_Tp_allocator());
368	__rv.clear();
369	}
370	}
371
372	/**
373	* @brief Builds a %vector from an initializer list.
374	* @param __l An initializer_list.
375	* @param __a An allocator.
376	*
377	* Create a %vector consisting of copies of the elements in the
378	* initializer_list @a __l.
379	*
380	* This will call the element type's copy constructor N times
381	* (where N is @a __l.size()) and do no memory reallocation.
382	*/
383	vector(initializer_list<value_type> __l,
384	const allocator_type& __a = allocator_type())
385	: _Base(__a)
386	{
387	_M_range_initialize(__l.begin(), __l.end(),
388	random_access_iterator_tag());
389	}
390	#endif
391
392	/**
393	* @brief Builds a %vector from a range.
394	* @param __first An input iterator.
395	* @param __last An input iterator.
396	* @param __a An allocator.
397	*
398	* Create a %vector consisting of copies of the elements from
399	* [first,last).
400	*
401	* If the iterators are forward, bidirectional, or
402	* random-access, then this will call the elements' copy
403	* constructor N times (where N is distance(first,last)) and do
404	* no memory reallocation. But if only input iterators are
405	* used, then this will do at most 2N calls to the copy
406	* constructor, and logN memory reallocations.
407	*/
408	#if __cplusplus >= 201103L
409	template<typename _InputIterator,
410	typename = std::_RequireInputIter<_InputIterator>>
411	vector(_InputIterator __first, _InputIterator __last,
412	const allocator_type& __a = allocator_type())
413	: _Base(__a)
414	{ _M_initialize_dispatch(__first, __last, __false_type()); }
415	#else
416	template<typename _InputIterator>
417	vector(_InputIterator __first, _InputIterator __last,
418	const allocator_type& __a = allocator_type())
419	: _Base(__a)
420	{
421	// Check whether it's an integral type. If so, it's not an iterator.
422	typedef typename std::__is_integer<_InputIterator>::__type _Integral;
423	_M_initialize_dispatch(__first, __last, _Integral());
424	}
425	#endif
426
427	/**
428	* The dtor only erases the elements, and note that if the
429	* elements themselves are pointers, the pointed-to memory is
430	* not touched in any way. Managing the pointer is the user's
431	* responsibility.
432	*/
433	~vector() _GLIBCXX_NOEXCEPT
434	{ std::_Destroy(this->_M_impl._M_start, this->_M_impl._M_finish,
435	_M_get_Tp_allocator()); }
436
437	/**
438	* @brief %Vector assignment operator.
439	* @param __x A %vector of identical element and allocator types.
440	*
441	* All the elements of @a __x are copied, but any unused capacity in
442	* @a __x will not be copied.
443	*
444	* Whether the allocator is copied depends on the allocator traits.
445	*/
446	vector&
447	operator=(const vector& __x);
448
449	#if __cplusplus >= 201103L
450	/**
451	* @brief %Vector move assignment operator.
452	* @param __x A %vector of identical element and allocator types.
453	*
454	* The contents of @a __x are moved into this %vector (without copying,
455	* if the allocators permit it).
456	* Afterwards @a __x is a valid, but unspecified %vector.
457	*
458	* Whether the allocator is moved depends on the allocator traits.
459	*/
460	vector&
461	operator=(vector&& __x) noexcept(_Alloc_traits::_S_nothrow_move())
462	{
463	constexpr bool __move_storage =
464	_Alloc_traits::_S_propagate_on_move_assign()
465	\|\| _Alloc_traits::_S_always_equal();
466	_M_move_assign(std::move(__x), __bool_constant<__move_storage>());
467	return *this;
468	}
469
470	/**
471	* @brief %Vector list assignment operator.
472	* @param __l An initializer_list.
473	*
474	* This function fills a %vector with copies of the elements in the
475	* initializer list @a __l.
476	*
477	* Note that the assignment completely changes the %vector and
478	* that the resulting %vector's size is the same as the number
479	* of elements assigned.
480	*/
481	vector&
482	operator=(initializer_list<value_type> __l)
483	{
484	this->_M_assign_aux(__l.begin(), __l.end(),
485	random_access_iterator_tag());
486	return *this;
487	}
488	#endif
489
490	/**
491	* @brief Assigns a given value to a %vector.
492	* @param __n Number of elements to be assigned.
493	* @param __val Value to be assigned.
494	*
495	* This function fills a %vector with @a __n copies of the given
496	* value. Note that the assignment completely changes the
497	* %vector and that the resulting %vector's size is the same as
498	* the number of elements assigned.
499	*/
500	void
501	assign(size_type __n, const value_type& __val)
502	{ _M_fill_assign(__n, __val); }
503
504	/**
505	* @brief Assigns a range to a %vector.
506	* @param __first An input iterator.
507	* @param __last An input iterator.
508	*
509	* This function fills a %vector with copies of the elements in the
510	* range [__first,__last).
511	*
512	* Note that the assignment completely changes the %vector and
513	* that the resulting %vector's size is the same as the number
514	* of elements assigned.
515	*/
516	#if __cplusplus >= 201103L
517	template<typename _InputIterator,
518	typename = std::_RequireInputIter<_InputIterator>>
519	void
520	assign(_InputIterator __first, _InputIterator __last)
521	{ _M_assign_dispatch(__first, __last, __false_type()); }
522	#else
523	template<typename _InputIterator>
524	void
525	assign(_InputIterator __first, _InputIterator __last)
526	{
527	// Check whether it's an integral type. If so, it's not an iterator.
528	typedef typename std::__is_integer<_InputIterator>::__type _Integral;
529	_M_assign_dispatch(__first, __last, _Integral());
530	}
531	#endif
532
533	#if __cplusplus >= 201103L
534	/**
535	* @brief Assigns an initializer list to a %vector.
536	* @param __l An initializer_list.
537	*
538	* This function fills a %vector with copies of the elements in the
539	* initializer list @a __l.
540	*
541	* Note that the assignment completely changes the %vector and
542	* that the resulting %vector's size is the same as the number
543	* of elements assigned.
544	*/
545	void
546	assign(initializer_list<value_type> __l)
547	{
548	this->_M_assign_aux(__l.begin(), __l.end(),
549	random_access_iterator_tag());
550	}
551	#endif
552
553	/// Get a copy of the memory allocation object.
554	using _Base::get_allocator;
555
556	// iterators
557	/**
558	* Returns a read/write iterator that points to the first
559	* element in the %vector. Iteration is done in ordinary
560	* element order.
561	*/
562	iterator
563	begin() _GLIBCXX_NOEXCEPT
564	{ return iterator(this->_M_impl._M_start); }
565
566	/**
567	* Returns a read-only (constant) iterator that points to the
568	* first element in the %vector. Iteration is done in ordinary
569	* element order.
570	*/
571	const_iterator
572	begin() const _GLIBCXX_NOEXCEPT
573	{ return const_iterator(this->_M_impl._M_start); }
574
575	/**
576	* Returns a read/write iterator that points one past the last
577	* element in the %vector. Iteration is done in ordinary
578	* element order.
579	*/
580	iterator
581	end() _GLIBCXX_NOEXCEPT
582	{ return iterator(this->_M_impl._M_finish); }
583
584	/**
585	* Returns a read-only (constant) iterator that points one past
586	* the last element in the %vector. Iteration is done in
587	* ordinary element order.
588	*/
589	const_iterator
590	end() const _GLIBCXX_NOEXCEPT
591	{ return const_iterator(this->_M_impl._M_finish); }
592
593	/**
594	* Returns a read/write reverse iterator that points to the
595	* last element in the %vector. Iteration is done in reverse
596	* element order.
597	*/
598	reverse_iterator
599	rbegin() _GLIBCXX_NOEXCEPT
600	{ return reverse_iterator(end()); }
601
602	/**
603	* Returns a read-only (constant) reverse iterator that points
604	* to the last element in the %vector. Iteration is done in
605	* reverse element order.
606	*/
607	const_reverse_iterator
608	rbegin() const _GLIBCXX_NOEXCEPT
609	{ return const_reverse_iterator(end()); }
610
611	/**
612	* Returns a read/write reverse iterator that points to one
613	* before the first element in the %vector. Iteration is done
614	* in reverse element order.
615	*/
616	reverse_iterator
617	rend() _GLIBCXX_NOEXCEPT
618	{ return reverse_iterator(begin()); }
619
620	/**
621	* Returns a read-only (constant) reverse iterator that points
622	* to one before the first element in the %vector. Iteration
623	* is done in reverse element order.
624	*/
625	const_reverse_iterator
626	rend() const _GLIBCXX_NOEXCEPT
627	{ return const_reverse_iterator(begin()); }
628
629	#if __cplusplus >= 201103L
630	/**
631	* Returns a read-only (constant) iterator that points to the
632	* first element in the %vector. Iteration is done in ordinary
633	* element order.
634	*/
635	const_iterator
636	cbegin() const noexcept
637	{ return const_iterator(this->_M_impl._M_start); }
638
639	/**
640	* Returns a read-only (constant) iterator that points one past
641	* the last element in the %vector. Iteration is done in
642	* ordinary element order.
643	*/
644	const_iterator
645	cend() const noexcept
646	{ return const_iterator(this->_M_impl._M_finish); }
647
648	/**
649	* Returns a read-only (constant) reverse iterator that points
650	* to the last element in the %vector. Iteration is done in
651	* reverse element order.
652	*/
653	const_reverse_iterator
654	crbegin() const noexcept
655	{ return const_reverse_iterator(end()); }
656
657	/**
658	* Returns a read-only (constant) reverse iterator that points
659	* to one before the first element in the %vector. Iteration
660	* is done in reverse element order.
661	*/
662	const_reverse_iterator
663	crend() const noexcept
664	{ return const_reverse_iterator(begin()); }
665	#endif
666
667	// [23.2.4.2] capacity
668	/** Returns the number of elements in the %vector. */
669	size_type
670	size() const _GLIBCXX_NOEXCEPT
671	{ return size_type(this->_M_impl._M_finish - this->_M_impl._M_start); }
672
673	/** Returns the size() of the largest possible %vector. */
674	size_type
675	max_size() const _GLIBCXX_NOEXCEPT
676	{ return _Alloc_traits::max_size(_M_get_Tp_allocator()); }
677
678	#if __cplusplus >= 201103L
679	/**
680	* @brief Resizes the %vector to the specified number of elements.
681	* @param __new_size Number of elements the %vector should contain.
682	*
683	* This function will %resize the %vector to the specified
684	* number of elements. If the number is smaller than the
685	* %vector's current size the %vector is truncated, otherwise
686	* default constructed elements are appended.
687	*/
688	void
689	resize(size_type __new_size)
690	{
691	if (__new_size > size())
692	_M_default_append(__new_size - size());
693	else if (__new_size < size())
694	_M_erase_at_end(this->_M_impl._M_start + __new_size);
695	}
696
697	/**
698	* @brief Resizes the %vector to the specified number of elements.
699	* @param __new_size Number of elements the %vector should contain.
700	* @param __x Data with which new elements should be populated.
701	*
702	* This function will %resize the %vector to the specified
703	* number of elements. If the number is smaller than the
704	* %vector's current size the %vector is truncated, otherwise
705	* the %vector is extended and new elements are populated with
706	* given data.
707	*/
708	void
709	resize(size_type __new_size, const value_type& __x)
710	{
711	if (__new_size > size())
712	_M_fill_insert(end(), __new_size - size(), __x);
713	else if (__new_size < size())
714	_M_erase_at_end(this->_M_impl._M_start + __new_size);
715	}
716	#else
717	/**
718	* @brief Resizes the %vector to the specified number of elements.
719	* @param __new_size Number of elements the %vector should contain.
720	* @param __x Data with which new elements should be populated.
721	*
722	* This function will %resize the %vector to the specified
723	* number of elements. If the number is smaller than the
724	* %vector's current size the %vector is truncated, otherwise
725	* the %vector is extended and new elements are populated with
726	* given data.
727	*/
728	void
729	resize(size_type __new_size, value_type __x = value_type())
730	{
731	if (__new_size > size())
732	_M_fill_insert(end(), __new_size - size(), __x);
733	else if (__new_size < size())
734	_M_erase_at_end(this->_M_impl._M_start + __new_size);
735	}
736	#endif
737
738	#if __cplusplus >= 201103L
739	/** A non-binding request to reduce capacity() to size(). */
740	void
741	shrink_to_fit()
742	{ _M_shrink_to_fit(); }
743	#endif
744
745	/**
746	* Returns the total number of elements that the %vector can
747	* hold before needing to allocate more memory.
748	*/
749	size_type
750	capacity() const _GLIBCXX_NOEXCEPT
751	{ return size_type(this->_M_impl._M_end_of_storage
752	- this->_M_impl._M_start); }
753
754	/**
755	* Returns true if the %vector is empty. (Thus begin() would
756	* equal end().)
757	*/
758	bool
759	empty() const _GLIBCXX_NOEXCEPT
760	{ return begin() == end(); }
761
762	/**
763	* @brief Attempt to preallocate enough memory for specified number of
764	* elements.
765	* @param __n Number of elements required.
766	* @throw std::length_error If @a n exceeds @c max_size().
767	*
768	* This function attempts to reserve enough memory for the
769	* %vector to hold the specified number of elements. If the
770	* number requested is more than max_size(), length_error is
771	* thrown.
772	*
773	* The advantage of this function is that if optimal code is a
774	* necessity and the user can determine the number of elements
775	* that will be required, the user can reserve the memory in
776	* %advance, and thus prevent a possible reallocation of memory
777	* and copying of %vector data.
778	*/
779	void
780	reserve(size_type __n);
781
782	// element access
783	/**
784	* @brief Subscript access to the data contained in the %vector.
785	* @param __n The index of the element for which data should be
786	* accessed.
787	* @return Read/write reference to data.
788	*
789	* This operator allows for easy, array-style, data access.
790	* Note that data access with this operator is unchecked and
791	* out_of_range lookups are not defined. (For checked lookups
792	* see at().)
793	*/
794	reference
795	operator[](size_type __n) _GLIBCXX_NOEXCEPT
796	{
797	__glibcxx_requires_subscript(__n);
798	return *(this->_M_impl._M_start + __n);
799	}
800
801	/**
802	* @brief Subscript access to the data contained in the %vector.
803	* @param __n The index of the element for which data should be
804	* accessed.
805	* @return Read-only (constant) reference to data.
806	*
807	* This operator allows for easy, array-style, data access.
808	* Note that data access with this operator is unchecked and
809	* out_of_range lookups are not defined. (For checked lookups
810	* see at().)
811	*/
812	const_reference
813	operator[](size_type __n) const _GLIBCXX_NOEXCEPT
814	{
815	__glibcxx_requires_subscript(__n);
816	return *(this->_M_impl._M_start + __n);
817	}
818
819	protected:
820	/// Safety check used only from at().
821	void
822	_M_range_check(size_type __n) const
823	{
824	if (__n >= this->size())
825	__throw_out_of_range_fmt(= this->size() " "(which is %zu)")" file_link="../../../x86_64-linux-gnu/c++/7/bits/c++config.h.html#595" macro="true">__N("vector::_M_range_check: __n "
826	= this->size() " "(which is %zu)")" file_link="../../../x86_64-linux-gnu/c++/7/bits/c++config.h.html#595" macro="true"> "(which is %zu) >= this->size() "
827	= this->size() " "(which is %zu)")" file_link="../../../x86_64-linux-gnu/c++/7/bits/c++config.h.html#595" macro="true"> "(which is %zu)"),
828	__n, this->size());
829	}
830
831	public:
832	/**
833	* @brief Provides access to the data contained in the %vector.
834	* @param __n The index of the element for which data should be
835	* accessed.
836	* @return Read/write reference to data.
837	* @throw std::out_of_range If @a __n is an invalid index.
838	*
839	* This function provides for safer data access. The parameter
840	* is first checked that it is in the range of the vector. The
841	* function throws out_of_range if the check fails.
842	*/
843	reference
844	at(size_type __n)
845	{
846	_M_range_check(__n);
847	return (*this)[__n];
848	}
849
850	/**
851	* @brief Provides access to the data contained in the %vector.
852	* @param __n The index of the element for which data should be
853	* accessed.
854	* @return Read-only (constant) reference to data.
855	* @throw std::out_of_range If @a __n is an invalid index.
856	*
857	* This function provides for safer data access. The parameter
858	* is first checked that it is in the range of the vector. The
859	* function throws out_of_range if the check fails.
860	*/
861	const_reference
862	at(size_type __n) const
863	{
864	_M_range_check(__n);
865	return (*this)[__n];
866	}
867
868	/**
869	* Returns a read/write reference to the data at the first
870	* element of the %vector.
871	*/
872	reference
873	front() _GLIBCXX_NOEXCEPT
874	{
875	__glibcxx_requires_nonempty();
876	return *begin();
877	}
878
879	/**
880	* Returns a read-only (constant) reference to the data at the first
881	* element of the %vector.
882	*/
883	const_reference
884	front() const _GLIBCXX_NOEXCEPT
885	{
886	__glibcxx_requires_nonempty();
887	return *begin();
888	}
889
890	/**
891	* Returns a read/write reference to the data at the last
892	* element of the %vector.
893	*/
894	reference
895	back() _GLIBCXX_NOEXCEPT
896	{
897	__glibcxx_requires_nonempty();
898	return *(end() - 1);
899	}
900
901	/**
902	* Returns a read-only (constant) reference to the data at the
903	* last element of the %vector.
904	*/
905	const_reference
906	back() const _GLIBCXX_NOEXCEPT
907	{
908	__glibcxx_requires_nonempty();
909	return *(end() - 1);
910	}
911
912	// _GLIBCXX_RESOLVE_LIB_DEFECTS
913	// DR 464. Suggestion for new member functions in standard containers.
914	// data access
915	/**
916	* Returns a pointer such that [data(), data() + size()) is a valid
917	* range. For a non-empty %vector, data() == &front().
918	*/
919	_Tp*
920	data() _GLIBCXX_NOEXCEPT
921	{ return _M_data_ptr(this->_M_impl._M_start); }
922
923	const _Tp*
924	data() const _GLIBCXX_NOEXCEPT
925	{ return _M_data_ptr(this->_M_impl._M_start); }
926
927	// [23.2.4.3] modifiers
928	/**
929	* @brief Add data to the end of the %vector.
930	* @param __x Data to be added.
931	*
932	* This is a typical stack operation. The function creates an
933	* element at the end of the %vector and assigns the given data
934	* to it. Due to the nature of a %vector this operation can be
935	* done in constant time if the %vector has preallocated space
936	* available.
937	*/
938	void
939	push_back(const value_type& __x)
940	{
941	if (this->_M_impl._M_finish != this->_M_impl._M_end_of_storage)
942	{
943	_Alloc_traits::construct(this->_M_impl, this->_M_impl._M_finish,
944	__x);
945	++this->_M_impl._M_finish;
946	}
947	else
948	_M_realloc_insert(end(), __x);
949	}
950
951	#if __cplusplus >= 201103L
952	void
953	push_back(value_type&& __x)
954	{ emplace_back(std::move(__x)); }
955
956	template<typename... _Args>
957	#if __cplusplus > 201402L
958	reference
959	#else
960	void
961	#endif
962	emplace_back(_Args&&... __args);
963	#endif
964
965	/**
966	* @brief Removes last element.
967	*
968	* This is a typical stack operation. It shrinks the %vector by one.
969	*
970	* Note that no data is returned, and if the last element's
971	* data is needed, it should be retrieved before pop_back() is
972	* called.
973	*/
974	void
975	pop_back() _GLIBCXX_NOEXCEPT
976	{
977	__glibcxx_requires_nonempty();
978	--this->_M_impl._M_finish;
979	_Alloc_traits::destroy(this->_M_impl, this->_M_impl._M_finish);
980	}
981
982	#if __cplusplus >= 201103L
983	/**
984	* @brief Inserts an object in %vector before specified iterator.
985	* @param __position A const_iterator into the %vector.
986	* @param __args Arguments.
987	* @return An iterator that points to the inserted data.
988	*
989	* This function will insert an object of type T constructed
990	* with T(std::forward<Args>(args)...) before the specified location.
991	* Note that this kind of operation could be expensive for a %vector
992	* and if it is frequently used the user should consider using
993	* std::list.
994	*/
995	template<typename... _Args>
996	iterator
997	emplace(const_iterator __position, _Args&&... __args)
998	{ return _M_emplace_aux(__position, std::forward<_Args>(__args)...); }
999
1000	/**
1001	* @brief Inserts given value into %vector before specified iterator.
1002	* @param __position A const_iterator into the %vector.
1003	* @param __x Data to be inserted.
1004	* @return An iterator that points to the inserted data.
1005	*
1006	* This function will insert a copy of the given value before
1007	* the specified location. Note that this kind of operation
1008	* could be expensive for a %vector and if it is frequently
1009	* used the user should consider using std::list.
1010	*/
1011	iterator
1012	insert(const_iterator __position, const value_type& __x);
1013	#else
1014	/**
1015	* @brief Inserts given value into %vector before specified iterator.
1016	* @param __position An iterator into the %vector.
1017	* @param __x Data to be inserted.
1018	* @return An iterator that points to the inserted data.
1019	*
1020	* This function will insert a copy of the given value before
1021	* the specified location. Note that this kind of operation
1022	* could be expensive for a %vector and if it is frequently
1023	* used the user should consider using std::list.
1024	*/
1025	iterator
1026	insert(iterator __position, const value_type& __x);
1027	#endif
1028
1029	#if __cplusplus >= 201103L
1030	/**
1031	* @brief Inserts given rvalue into %vector before specified iterator.
1032	* @param __position A const_iterator into the %vector.
1033	* @param __x Data to be inserted.
1034	* @return An iterator that points to the inserted data.
1035	*
1036	* This function will insert a copy of the given rvalue before
1037	* the specified location. Note that this kind of operation
1038	* could be expensive for a %vector and if it is frequently
1039	* used the user should consider using std::list.
1040	*/
1041	iterator
1042	insert(const_iterator __position, value_type&& __x)
1043	{ return _M_insert_rval(__position, std::move(__x)); }
1044
1045	/**
1046	* @brief Inserts an initializer_list into the %vector.
1047	* @param __position An iterator into the %vector.
1048	* @param __l An initializer_list.
1049	*
1050	* This function will insert copies of the data in the
1051	* initializer_list @a l into the %vector before the location
1052	* specified by @a position.
1053	*
1054	* Note that this kind of operation could be expensive for a
1055	* %vector and if it is frequently used the user should
1056	* consider using std::list.
1057	*/
1058	iterator
1059	insert(const_iterator __position, initializer_list<value_type> __l)
1060	{
1061	auto __offset = __position - cbegin();
1062	_M_range_insert(begin() + __offset, __l.begin(), __l.end(),
1063	std::random_access_iterator_tag());
1064	return begin() + __offset;
1065	}
1066	#endif
1067
1068	#if __cplusplus >= 201103L
1069	/**
1070	* @brief Inserts a number of copies of given data into the %vector.
1071	* @param __position A const_iterator into the %vector.
1072	* @param __n Number of elements to be inserted.
1073	* @param __x Data to be inserted.
1074	* @return An iterator that points to the inserted data.
1075	*
1076	* This function will insert a specified number of copies of
1077	* the given data before the location specified by @a position.
1078	*
1079	* Note that this kind of operation could be expensive for a
1080	* %vector and if it is frequently used the user should
1081	* consider using std::list.
1082	*/
1083	iterator
1084	insert(const_iterator __position, size_type __n, const value_type& __x)
1085	{
1086	difference_type __offset = __position - cbegin();
1087	_M_fill_insert(begin() + __offset, __n, __x);
1088	return begin() + __offset;
1089	}
1090	#else
1091	/**
1092	* @brief Inserts a number of copies of given data into the %vector.
1093	* @param __position An iterator into the %vector.
1094	* @param __n Number of elements to be inserted.
1095	* @param __x Data to be inserted.
1096	*
1097	* This function will insert a specified number of copies of
1098	* the given data before the location specified by @a position.
1099	*
1100	* Note that this kind of operation could be expensive for a
1101	* %vector and if it is frequently used the user should
1102	* consider using std::list.
1103	*/
1104	void
1105	insert(iterator __position, size_type __n, const value_type& __x)
1106	{ _M_fill_insert(__position, __n, __x); }
1107	#endif
1108
1109	#if __cplusplus >= 201103L
1110	/**
1111	* @brief Inserts a range into the %vector.
1112	* @param __position A const_iterator into the %vector.
1113	* @param __first An input iterator.
1114	* @param __last An input iterator.
1115	* @return An iterator that points to the inserted data.
1116	*
1117	* This function will insert copies of the data in the range
1118	* [__first,__last) into the %vector before the location specified
1119	* by @a pos.
1120	*
1121	* Note that this kind of operation could be expensive for a
1122	* %vector and if it is frequently used the user should
1123	* consider using std::list.
1124	*/
1125	template<typename _InputIterator,
1126	typename = std::_RequireInputIter<_InputIterator>>
1127	iterator
1128	insert(const_iterator __position, _InputIterator __first,
1129	_InputIterator __last)
1130	{
1131	difference_type __offset = __position - cbegin();
1132	_M_insert_dispatch(begin() + __offset,
1133	__first, __last, __false_type());
1134	return begin() + __offset;
1135	}
1136	#else
1137	/**
1138	* @brief Inserts a range into the %vector.
1139	* @param __position An iterator into the %vector.
1140	* @param __first An input iterator.
1141	* @param __last An input iterator.
1142	*
1143	* This function will insert copies of the data in the range
1144	* [__first,__last) into the %vector before the location specified
1145	* by @a pos.
1146	*
1147	* Note that this kind of operation could be expensive for a
1148	* %vector and if it is frequently used the user should
1149	* consider using std::list.
1150	*/
1151	template<typename _InputIterator>
1152	void
1153	insert(iterator __position, _InputIterator __first,
1154	_InputIterator __last)
1155	{
1156	// Check whether it's an integral type. If so, it's not an iterator.
1157	typedef typename std::__is_integer<_InputIterator>::__type _Integral;
1158	_M_insert_dispatch(__position, __first, __last, _Integral());
1159	}
1160	#endif
1161
1162	/**
1163	* @brief Remove element at given position.
1164	* @param __position Iterator pointing to element to be erased.
1165	* @return An iterator pointing to the next element (or end()).
1166	*
1167	* This function will erase the element at the given position and thus
1168	* shorten the %vector by one.
1169	*
1170	* Note This operation could be expensive and if it is
1171	* frequently used the user should consider using std::list.
1172	* The user is also cautioned that this function only erases
1173	* the element, and that if the element is itself a pointer,
1174	* the pointed-to memory is not touched in any way. Managing
1175	* the pointer is the user's responsibility.
1176	*/
1177	iterator
1178	#if __cplusplus >= 201103L
1179	erase(const_iterator __position)
1180	{ return _M_erase(begin() + (__position - cbegin())); }
1181	#else
1182	erase(iterator __position)
1183	{ return _M_erase(__position); }
1184	#endif
1185
1186	/**
1187	* @brief Remove a range of elements.
1188	* @param __first Iterator pointing to the first element to be erased.
1189	* @param __last Iterator pointing to one past the last element to be
1190	* erased.
1191	* @return An iterator pointing to the element pointed to by @a __last
1192	* prior to erasing (or end()).
1193	*
1194	* This function will erase the elements in the range
1195	* [__first,__last) and shorten the %vector accordingly.
1196	*
1197	* Note This operation could be expensive and if it is
1198	* frequently used the user should consider using std::list.
1199	* The user is also cautioned that this function only erases
1200	* the elements, and that if the elements themselves are
1201	* pointers, the pointed-to memory is not touched in any way.
1202	* Managing the pointer is the user's responsibility.
1203	*/
1204	iterator
1205	#if __cplusplus >= 201103L
1206	erase(const_iterator __first, const_iterator __last)
1207	{
1208	const auto __beg = begin();
1209	const auto __cbeg = cbegin();
1210	return _M_erase(__beg + (__first - __cbeg), __beg + (__last - __cbeg));
1211	}
1212	#else
1213	erase(iterator __first, iterator __last)
1214	{ return _M_erase(__first, __last); }
1215	#endif
1216
1217	/**
1218	* @brief Swaps data with another %vector.
1219	* @param __x A %vector of the same element and allocator types.
1220	*
1221	* This exchanges the elements between two vectors in constant time.
1222	* (Three pointers, so it should be quite fast.)
1223	* Note that the global std::swap() function is specialized such that
1224	* std::swap(v1,v2) will feed to this function.
1225	*
1226	* Whether the allocators are swapped depends on the allocator traits.
1227	*/
1228	void
1229	swap(vector& __x) _GLIBCXX_NOEXCEPT
1230	{
1231	#if __cplusplus >= 201103L
1232	__glibcxx_assert(_Alloc_traits::propagate_on_container_swap::value
1233	\|\| _M_get_Tp_allocator() == __x._M_get_Tp_allocator());
1234	#endif
1235	this->_M_impl._M_swap_data(__x._M_impl);
1236	_Alloc_traits::_S_on_swap(_M_get_Tp_allocator(),
1237	__x._M_get_Tp_allocator());
1238	}
1239
1240	/**
1241	* Erases all the elements. Note that this function only erases the
1242	* elements, and that if the elements themselves are pointers, the
1243	* pointed-to memory is not touched in any way. Managing the pointer is
1244	* the user's responsibility.
1245	*/
1246	void
1247	clear() _GLIBCXX_NOEXCEPT
1248	{ _M_erase_at_end(this->_M_impl._M_start); }
1249
1250	protected:
1251	/**
1252	* Memory expansion handler. Uses the member allocation function to
1253	* obtain @a n bytes of memory, and then copies [first,last) into it.
1254	*/
1255	template<typename _ForwardIterator>
1256	pointer
1257	_M_allocate_and_copy(size_type __n,
1258	_ForwardIterator __first, _ForwardIterator __last)
1259	{
1260	pointer __result = this->_M_allocate(__n);
1261	__try
1262	{
1263	std::__uninitialized_copy_a(__first, __last, __result,
1264	_M_get_Tp_allocator());
1265	return __result;
1266	}
1267	__catch(...)
1268	{
1269	_M_deallocate(__result, __n);
1270	__throw_exception_again;
1271	}
1272	}
1273
1274
1275	// Internal constructor functions follow.
1276
1277	// Called by the range constructor to implement [23.1.1]/9
1278
1279	// _GLIBCXX_RESOLVE_LIB_DEFECTS
1280	// 438. Ambiguity in the "do the right thing" clause
1281	template<typename _Integer>
1282	void
1283	_M_initialize_dispatch(_Integer __n, _Integer __value, __true_type)
1284	{
1285	this->_M_impl._M_start = _M_allocate(static_cast<size_type>(__n));
1286	this->_M_impl._M_end_of_storage =
1287	this->_M_impl._M_start + static_cast<size_type>(__n);
1288	_M_fill_initialize(static_cast<size_type>(__n), __value);
1289	}
1290
1291	// Called by the range constructor to implement [23.1.1]/9
1292	template<typename _InputIterator>
1293	void
1294	_M_initialize_dispatch(_InputIterator __first, _InputIterator __last,
1295	__false_type)
1296	{
1297	typedef typename std::iterator_traits<_InputIterator>::
1298	iterator_category _IterCategory;
1299	_M_range_initialize(__first, __last, _IterCategory());
1300	}
1301
1302	// Called by the second initialize_dispatch above
1303	template<typename _InputIterator>
1304	void
1305	_M_range_initialize(_InputIterator __first, _InputIterator __last,
1306	std::input_iterator_tag)
1307	{
1308	__try {
1309	for (; __first != __last; ++__first)
1310	#if __cplusplus >= 201103L
1311	emplace_back(*__first);
1312	#else
1313	push_back(*__first);
1314	#endif
1315	} __catch(...) {
1316	clear();
1317	__throw_exception_again;
1318	}
1319	}
1320
1321	// Called by the second initialize_dispatch above
1322	template<typename _ForwardIterator>
1323	void
1324	_M_range_initialize(_ForwardIterator __first, _ForwardIterator __last,
1325	std::forward_iterator_tag)
1326	{
1327	const size_type __n = std::distance(__first, __last);
1328	this->_M_impl._M_start = this->_M_allocate(__n);
1329	this->_M_impl._M_end_of_storage = this->_M_impl._M_start + __n;
1330	this->_M_impl._M_finish =
1331	std::__uninitialized_copy_a(__first, __last,
1332	this->_M_impl._M_start,
1333	_M_get_Tp_allocator());
1334	}
1335
1336	// Called by the first initialize_dispatch above and by the
1337	// vector(n,value,a) constructor.
1338	void
1339	_M_fill_initialize(size_type __n, const value_type& __value)
1340	{
1341	this->_M_impl._M_finish =
1342	std::__uninitialized_fill_n_a(this->_M_impl._M_start, __n, __value,
1343	_M_get_Tp_allocator());
1344	}
1345
1346	#if __cplusplus >= 201103L
1347	// Called by the vector(n) constructor.
1348	void
1349	_M_default_initialize(size_type __n)
1350	{
1351	this->_M_impl._M_finish =
1352	std::__uninitialized_default_n_a(this->_M_impl._M_start, __n,
1353	_M_get_Tp_allocator());
1354	}
1355	#endif
1356
1357	// Internal assign functions follow. The *_aux functions do the actual
1358	// assignment work for the range versions.
1359
1360	// Called by the range assign to implement [23.1.1]/9
1361
1362	// _GLIBCXX_RESOLVE_LIB_DEFECTS
1363	// 438. Ambiguity in the "do the right thing" clause
1364	template<typename _Integer>
1365	void
1366	_M_assign_dispatch(_Integer __n, _Integer __val, __true_type)
1367	{ _M_fill_assign(__n, __val); }
1368
1369	// Called by the range assign to implement [23.1.1]/9
1370	template<typename _InputIterator>
1371	void
1372	_M_assign_dispatch(_InputIterator __first, _InputIterator __last,
1373	__false_type)
1374	{ _M_assign_aux(__first, __last, std::__iterator_category(__first)); }
1375
1376	// Called by the second assign_dispatch above
1377	template<typename _InputIterator>
1378	void
1379	_M_assign_aux(_InputIterator __first, _InputIterator __last,
1380	std::input_iterator_tag);
1381
1382	// Called by the second assign_dispatch above
1383	template<typename _ForwardIterator>
1384	void
1385	_M_assign_aux(_ForwardIterator __first, _ForwardIterator __last,
1386	std::forward_iterator_tag);
1387
1388	// Called by assign(n,t), and the range assign when it turns out
1389	// to be the same thing.
1390	void
1391	_M_fill_assign(size_type __n, const value_type& __val);
1392
1393	// Internal insert functions follow.
1394
1395	// Called by the range insert to implement [23.1.1]/9
1396
1397	// _GLIBCXX_RESOLVE_LIB_DEFECTS
1398	// 438. Ambiguity in the "do the right thing" clause
1399	template<typename _Integer>
1400	void
1401	_M_insert_dispatch(iterator __pos, _Integer __n, _Integer __val,
1402	__true_type)
1403	{ _M_fill_insert(__pos, __n, __val); }
1404
1405	// Called by the range insert to implement [23.1.1]/9
1406	template<typename _InputIterator>
1407	void
1408	_M_insert_dispatch(iterator __pos, _InputIterator __first,
1409	_InputIterator __last, __false_type)
1410	{
1411	_M_range_insert(__pos, __first, __last,
1412	std::__iterator_category(__first));
1413	}
1414
1415	// Called by the second insert_dispatch above
1416	template<typename _InputIterator>
1417	void
1418	_M_range_insert(iterator __pos, _InputIterator __first,
1419	_InputIterator __last, std::input_iterator_tag);
1420
1421	// Called by the second insert_dispatch above
1422	template<typename _ForwardIterator>
1423	void
1424	_M_range_insert(iterator __pos, _ForwardIterator __first,
1425	_ForwardIterator __last, std::forward_iterator_tag);
1426
1427	// Called by insert(p,n,x), and the range insert when it turns out to be
1428	// the same thing.
1429	void
1430	_M_fill_insert(iterator __pos, size_type __n, const value_type& __x);
1431
1432	#if __cplusplus >= 201103L
1433	// Called by resize(n).
1434	void
1435	_M_default_append(size_type __n);
1436
1437	bool
1438	_M_shrink_to_fit();
1439	#endif
1440
1441	#if __cplusplus < 201103L
1442	// Called by insert(p,x)
1443	void
1444	_M_insert_aux(iterator __position, const value_type& __x);
1445
1446	void
1447	_M_realloc_insert(iterator __position, const value_type& __x);
1448	#else
1449	// A value_type object constructed with _Alloc_traits::construct()
1450	// and destroyed with _Alloc_traits::destroy().
1451	struct _Temporary_value
1452	{
1453	template<typename... _Args>
1454	explicit
1455	_Temporary_value(vector* __vec, _Args&&... __args) : _M_this(__vec)
1456	{
1457	_Alloc_traits::construct(_M_this->_M_impl, _M_ptr(),
1458	std::forward<_Args>(__args)...);
1459	}
1460
1461	~_Temporary_value()
1462	{ _Alloc_traits::destroy(_M_this->_M_impl, _M_ptr()); }
1463
1464	value_type&
1465	_M_val() { return reinterpret_cast<_Tp>(&__buf); }
1466
1467	private:
1468	pointer
1469	_M_ptr() { return pointer_traits<pointer>::pointer_to(_M_val()); }
1470
1471	vector* _M_this;
1472	typename aligned_storage<sizeof(_Tp), alignof(_Tp)>::type __buf;
1473	};
1474
1475	// Called by insert(p,x) and other functions when insertion needs to
1476	// reallocate or move existing elements. _Arg is either _Tp& or _Tp.
1477	template<typename _Arg>
1478	void
1479	_M_insert_aux(iterator __position, _Arg&& __arg);
1480
1481	template<typename... _Args>
1482	void
1483	_M_realloc_insert(iterator __position, _Args&&... __args);
1484
1485	// Either move-construct at the end, or forward to _M_insert_aux.
1486	iterator
1487	_M_insert_rval(const_iterator __position, value_type&& __v);
1488
1489	// Try to emplace at the end, otherwise forward to _M_insert_aux.
1490	template<typename... _Args>
1491	iterator
1492	_M_emplace_aux(const_iterator __position, _Args&&... __args);
1493
1494	// Emplacing an rvalue of the correct type can use _M_insert_rval.
1495	iterator
1496	_M_emplace_aux(const_iterator __position, value_type&& __v)
1497	{ return _M_insert_rval(__position, std::move(__v)); }
1498	#endif
1499
1500	// Called by _M_fill_insert, _M_insert_aux etc.
1501	size_type
1502	_M_check_len(size_type __n, const char* __s) const
1503	{
1504	if (max_size() - size() < __n)
1505	__throw_length_error(__N(__s));
1506
1507	const size_type __len = size() + std::max(size(), __n);
1508	return (__len < size() \|\| __len > max_size()) ? max_size() : __len;
1509	}
1510
1511	// Internal erase functions follow.
1512
1513	// Called by erase(q1,q2), clear(), resize(), _M_fill_assign,
1514	// _M_assign_aux.
1515	void
1516	_M_erase_at_end(pointer __pos) _GLIBCXX_NOEXCEPT
1517	{
1518	std::_Destroy(__pos, this->_M_impl._M_finish, _M_get_Tp_allocator());
1519	this->_M_impl._M_finish = __pos;
1520	}
1521
1522	iterator
1523	_M_erase(iterator __position);
1524
1525	iterator
1526	_M_erase(iterator __first, iterator __last);
1527
1528	#if __cplusplus >= 201103L
1529	private:
1530	// Constant-time move assignment when source object's memory can be
1531	// moved, either because the source's allocator will move too
1532	// or because the allocators are equal.
1533	void
1534	_M_move_assign(vector&& __x, std::true_type) noexcept
1535	{
1536	vector __tmp(get_allocator());
1537	this->_M_impl._M_swap_data(__tmp._M_impl);
1538	this->_M_impl._M_swap_data(__x._M_impl);
1539	std::__alloc_on_move(_M_get_Tp_allocator(), __x._M_get_Tp_allocator());
1540	}
1541
1542	// Do move assignment when it might not be possible to move source
1543	// object's memory, resulting in a linear-time operation.
1544	void
1545	_M_move_assign(vector&& __x, std::false_type)
1546	{
1547	if (__x._M_get_Tp_allocator() == this->_M_get_Tp_allocator())
1548	_M_move_assign(std::move(__x), std::true_type());
1549	else
1550	{
1551	// The rvalue's allocator cannot be moved and is not equal,
1552	// so we need to individually move each element.
1553	this->assign(std::__make_move_if_noexcept_iterator(__x.begin()),
1554	std::__make_move_if_noexcept_iterator(__x.end()));
1555	__x.clear();
1556	}
1557	}
1558	#endif
1559
1560	template<typename _Up>
1561	_Up*
1562	_M_data_ptr(_Up* __ptr) const _GLIBCXX_NOEXCEPT
1563	{ return __ptr; }
1564
1565	#if __cplusplus >= 201103L
1566	template<typename _Ptr>
1567	typename std::pointer_traits<_Ptr>::element_type*
1568	_M_data_ptr(_Ptr __ptr) const
1569	{ return empty() ? nullptr : std::__addressof(*__ptr); }
1570	#else
1571	template<typename _Up>
1572	_Up*
1573	_M_data_ptr(_Up* __ptr) _GLIBCXX_NOEXCEPT
1574	{ return __ptr; }
1575
1576	template<typename _Ptr>
1577	value_type*
1578	_M_data_ptr(_Ptr __ptr)
1579	{ return __ptr.operator->(); }
1580
1581	template<typename _Ptr>
1582	const value_type*
1583	_M_data_ptr(_Ptr __ptr) const
1584	{ return __ptr.operator->(); }
1585	#endif
1586	};
1587
1588
1589	/**
1590	* @brief Vector equality comparison.
1591	* @param __x A %vector.
1592	* @param __y A %vector of the same type as @a __x.
1593	* @return True iff the size and elements of the vectors are equal.
1594	*
1595	* This is an equivalence relation. It is linear in the size of the
1596	* vectors. Vectors are considered equivalent if their sizes are equal,
1597	* and if corresponding elements compare equal.
1598	*/
1599	template<typename _Tp, typename _Alloc>
1600	inline bool
1601	operator==(const vector<_Tp, _Alloc>& __x, const vector<_Tp, _Alloc>& __y)
1602	{ return (__x.size() == __y.size()
1603	&& std::equal(__x.begin(), __x.end(), __y.begin())); }
1604
1605	/**
1606	* @brief Vector ordering relation.
1607	* @param __x A %vector.
1608	* @param __y A %vector of the same type as @a __x.
1609	* @return True iff @a __x is lexicographically less than @a __y.
1610	*
1611	* This is a total ordering relation. It is linear in the size of the
1612	* vectors. The elements must be comparable with @c <.
1613	*
1614	* See std::lexicographical_compare() for how the determination is made.
1615	*/
1616	template<typename _Tp, typename _Alloc>
1617	inline bool
1618	operator<(const vector<_Tp, _Alloc>& __x, const vector<_Tp, _Alloc>& __y)
1619	{ return std::lexicographical_compare(__x.begin(), __x.end(),
1620	__y.begin(), __y.end()); }
1621
1622	/// Based on operator==
1623	template<typename _Tp, typename _Alloc>
1624	inline bool
1625	operator!=(const vector<_Tp, _Alloc>& __x, const vector<_Tp, _Alloc>& __y)
1626	{ return !(__x == __y); }
1627
1628	/// Based on operator<
1629	template<typename _Tp, typename _Alloc>
1630	inline bool
1631	operator>(const vector<_Tp, _Alloc>& __x, const vector<_Tp, _Alloc>& __y)
1632	{ return __y < __x; }
1633
1634	/// Based on operator<
1635	template<typename _Tp, typename _Alloc>
1636	inline bool
1637	operator<=(const vector<_Tp, _Alloc>& __x, const vector<_Tp, _Alloc>& __y)
1638	{ return !(__y < __x); }
1639
1640	/// Based on operator<
1641	template<typename _Tp, typename _Alloc>
1642	inline bool
1643	operator>=(const vector<_Tp, _Alloc>& __x, const vector<_Tp, _Alloc>& __y)
1644	{ return !(__x < __y); }
1645
1646	/// See std::vector::swap().
1647	template<typename _Tp, typename _Alloc>
1648	inline void
1649	swap(vector<_Tp, _Alloc>& __x, vector<_Tp, _Alloc>& __y)
1650	_GLIBCXX_NOEXCEPT_IF(noexcept(__x.swap(__y)))
1651	{ __x.swap(__y); }
1652
1653	_GLIBCXX_END_NAMESPACE_CONTAINER
1654	} // namespace std
1655
1656	#endif /* _STL_VECTOR_H */
1657