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
68namespace 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(__N("vector::_M_range_check: __n "
826 "(which is %zu) >= this->size() "
827 "(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,
1306 _InputIterator __last, std::input_iterator_tag)
1307 {
1308 for (; __first != __last; ++__first)
1309#if __cplusplus >= 201103L
1310 emplace_back(*__first);
1311#else
1312 push_back(*__first);
1313#endif
1314 }
1315
1316 // Called by the second initialize_dispatch above
1317 template<typename _ForwardIterator>
1318 void
1319 _M_range_initialize(_ForwardIterator __first,
1320 _ForwardIterator __last, std::forward_iterator_tag)
1321 {
1322 const size_type __n = std::distance(__first, __last);
1323 this->_M_impl._M_start = this->_M_allocate(__n);
1324 this->_M_impl._M_end_of_storage = this->_M_impl._M_start + __n;
1325 this->_M_impl._M_finish =
1326 std::__uninitialized_copy_a(__first, __last,
1327 this->_M_impl._M_start,
1328 _M_get_Tp_allocator());
1329 }
1330
1331 // Called by the first initialize_dispatch above and by the
1332 // vector(n,value,a) constructor.
1333 void
1334 _M_fill_initialize(size_type __n, const value_type& __value)
1335 {
1336 this->_M_impl._M_finish =
1337 std::__uninitialized_fill_n_a(this->_M_impl._M_start, __n, __value,
1338 _M_get_Tp_allocator());
1339 }
1340
1341#if __cplusplus >= 201103L
1342 // Called by the vector(n) constructor.
1343 void
1344 _M_default_initialize(size_type __n)
1345 {
1346 this->_M_impl._M_finish =
1347 std::__uninitialized_default_n_a(this->_M_impl._M_start, __n,
1348 _M_get_Tp_allocator());
1349 }
1350#endif
1351
1352 // Internal assign functions follow. The *_aux functions do the actual
1353 // assignment work for the range versions.
1354
1355 // Called by the range assign to implement [23.1.1]/9
1356
1357 // _GLIBCXX_RESOLVE_LIB_DEFECTS
1358 // 438. Ambiguity in the "do the right thing" clause
1359 template<typename _Integer>
1360 void
1361 _M_assign_dispatch(_Integer __n, _Integer __val, __true_type)
1362 { _M_fill_assign(__n, __val); }
1363
1364 // Called by the range assign to implement [23.1.1]/9
1365 template<typename _InputIterator>
1366 void
1367 _M_assign_dispatch(_InputIterator __first, _InputIterator __last,
1368 __false_type)
1369 { _M_assign_aux(__first, __last, std::__iterator_category(__first)); }
1370
1371 // Called by the second assign_dispatch above
1372 template<typename _InputIterator>
1373 void
1374 _M_assign_aux(_InputIterator __first, _InputIterator __last,
1375 std::input_iterator_tag);
1376
1377 // Called by the second assign_dispatch above
1378 template<typename _ForwardIterator>
1379 void
1380 _M_assign_aux(_ForwardIterator __first, _ForwardIterator __last,
1381 std::forward_iterator_tag);
1382
1383 // Called by assign(n,t), and the range assign when it turns out
1384 // to be the same thing.
1385 void
1386 _M_fill_assign(size_type __n, const value_type& __val);
1387
1388 // Internal insert functions follow.
1389
1390 // Called by the range insert to implement [23.1.1]/9
1391
1392 // _GLIBCXX_RESOLVE_LIB_DEFECTS
1393 // 438. Ambiguity in the "do the right thing" clause
1394 template<typename _Integer>
1395 void
1396 _M_insert_dispatch(iterator __pos, _Integer __n, _Integer __val,
1397 __true_type)
1398 { _M_fill_insert(__pos, __n, __val); }
1399
1400 // Called by the range insert to implement [23.1.1]/9
1401 template<typename _InputIterator>
1402 void
1403 _M_insert_dispatch(iterator __pos, _InputIterator __first,
1404 _InputIterator __last, __false_type)
1405 {
1406 _M_range_insert(__pos, __first, __last,
1407 std::__iterator_category(__first));
1408 }
1409
1410 // Called by the second insert_dispatch above
1411 template<typename _InputIterator>
1412 void
1413 _M_range_insert(iterator __pos, _InputIterator __first,
1414 _InputIterator __last, std::input_iterator_tag);
1415
1416 // Called by the second insert_dispatch above
1417 template<typename _ForwardIterator>
1418 void
1419 _M_range_insert(iterator __pos, _ForwardIterator __first,
1420 _ForwardIterator __last, std::forward_iterator_tag);
1421
1422 // Called by insert(p,n,x), and the range insert when it turns out to be
1423 // the same thing.
1424 void
1425 _M_fill_insert(iterator __pos, size_type __n, const value_type& __x);
1426
1427#if __cplusplus >= 201103L
1428 // Called by resize(n).
1429 void
1430 _M_default_append(size_type __n);
1431
1432 bool
1433 _M_shrink_to_fit();
1434#endif
1435
1436#if __cplusplus < 201103L
1437 // Called by insert(p,x)
1438 void
1439 _M_insert_aux(iterator __position, const value_type& __x);
1440
1441 void
1442 _M_realloc_insert(iterator __position, const value_type& __x);
1443#else
1444 // A value_type object constructed with _Alloc_traits::construct()
1445 // and destroyed with _Alloc_traits::destroy().
1446 struct _Temporary_value
1447 {
1448 template<typename... _Args>
1449 explicit
1450 _Temporary_value(vector* __vec, _Args&&... __args) : _M_this(__vec)
1451 {
1452 _Alloc_traits::construct(_M_this->_M_impl, _M_ptr(),
1453 std::forward<_Args>(__args)...);
1454 }
1455
1456 ~_Temporary_value()
1457 { _Alloc_traits::destroy(_M_this->_M_impl, _M_ptr()); }
1458
1459 value_type&
1460 _M_val() { return *reinterpret_cast<_Tp*>(&__buf); }
1461
1462 private:
1463 pointer
1464 _M_ptr() { return pointer_traits<pointer>::pointer_to(_M_val()); }
1465
1466 vector* _M_this;
1467 typename aligned_storage<sizeof(_Tp), alignof(_Tp)>::type __buf;
1468 };
1469
1470 // Called by insert(p,x) and other functions when insertion needs to
1471 // reallocate or move existing elements. _Arg is either _Tp& or _Tp.
1472 template<typename _Arg>
1473 void
1474 _M_insert_aux(iterator __position, _Arg&& __arg);
1475
1476 template<typename... _Args>
1477 void
1478 _M_realloc_insert(iterator __position, _Args&&... __args);
1479
1480 // Either move-construct at the end, or forward to _M_insert_aux.
1481 iterator
1482 _M_insert_rval(const_iterator __position, value_type&& __v);
1483
1484 // Try to emplace at the end, otherwise forward to _M_insert_aux.
1485 template<typename... _Args>
1486 iterator
1487 _M_emplace_aux(const_iterator __position, _Args&&... __args);
1488
1489 // Emplacing an rvalue of the correct type can use _M_insert_rval.
1490 iterator
1491 _M_emplace_aux(const_iterator __position, value_type&& __v)
1492 { return _M_insert_rval(__position, std::move(__v)); }
1493#endif
1494
1495 // Called by _M_fill_insert, _M_insert_aux etc.
1496 size_type
1497 _M_check_len(size_type __n, const char* __s) const
1498 {
1499 if (max_size() - size() < __n)
1500 __throw_length_error(__N(__s));
1501
1502 const size_type __len = size() + std::max(size(), __n);
1503 return (__len < size() || __len > max_size()) ? max_size() : __len;
1504 }
1505
1506 // Internal erase functions follow.
1507
1508 // Called by erase(q1,q2), clear(), resize(), _M_fill_assign,
1509 // _M_assign_aux.
1510 void
1511 _M_erase_at_end(pointer __pos) _GLIBCXX_NOEXCEPT
1512 {
1513 std::_Destroy(__pos, this->_M_impl._M_finish, _M_get_Tp_allocator());
1514 this->_M_impl._M_finish = __pos;
1515 }
1516
1517 iterator
1518 _M_erase(iterator __position);
1519
1520 iterator
1521 _M_erase(iterator __first, iterator __last);
1522
1523#if __cplusplus >= 201103L
1524 private:
1525 // Constant-time move assignment when source object's memory can be
1526 // moved, either because the source's allocator will move too
1527 // or because the allocators are equal.
1528 void
1529 _M_move_assign(vector&& __x, std::true_type) noexcept
1530 {
1531 vector __tmp(get_allocator());
1532 this->_M_impl._M_swap_data(__tmp._M_impl);
1533 this->_M_impl._M_swap_data(__x._M_impl);
1534 std::__alloc_on_move(_M_get_Tp_allocator(), __x._M_get_Tp_allocator());
1535 }
1536
1537 // Do move assignment when it might not be possible to move source
1538 // object's memory, resulting in a linear-time operation.
1539 void
1540 _M_move_assign(vector&& __x, std::false_type)
1541 {
1542 if (__x._M_get_Tp_allocator() == this->_M_get_Tp_allocator())
1543 _M_move_assign(std::move(__x), std::true_type());
1544 else
1545 {
1546 // The rvalue's allocator cannot be moved and is not equal,
1547 // so we need to individually move each element.
1548 this->assign(std::__make_move_if_noexcept_iterator(__x.begin()),
1549 std::__make_move_if_noexcept_iterator(__x.end()));
1550 __x.clear();
1551 }
1552 }
1553#endif
1554
1555 template<typename _Up>
1556 _Up*
1557 _M_data_ptr(_Up* __ptr) const _GLIBCXX_NOEXCEPT
1558 { return __ptr; }
1559
1560#if __cplusplus >= 201103L
1561 template<typename _Ptr>
1562 typename std::pointer_traits<_Ptr>::element_type*
1563 _M_data_ptr(_Ptr __ptr) const
1564 { return empty() ? nullptr : std::__addressof(*__ptr); }
1565#else
1566 template<typename _Up>
1567 _Up*
1568 _M_data_ptr(_Up* __ptr) _GLIBCXX_NOEXCEPT
1569 { return __ptr; }
1570
1571 template<typename _Ptr>
1572 value_type*
1573 _M_data_ptr(_Ptr __ptr)
1574 { return __ptr.operator->(); }
1575
1576 template<typename _Ptr>
1577 const value_type*
1578 _M_data_ptr(_Ptr __ptr) const
1579 { return __ptr.operator->(); }
1580#endif
1581 };
1582
1583
1584 /**
1585 * @brief Vector equality comparison.
1586 * @param __x A %vector.
1587 * @param __y A %vector of the same type as @a __x.
1588 * @return True iff the size and elements of the vectors are equal.
1589 *
1590 * This is an equivalence relation. It is linear in the size of the
1591 * vectors. Vectors are considered equivalent if their sizes are equal,
1592 * and if corresponding elements compare equal.
1593 */
1594 template<typename _Tp, typename _Alloc>
1595 inline bool
1596 operator==(const vector<_Tp, _Alloc>& __x, const vector<_Tp, _Alloc>& __y)
1597 { return (__x.size() == __y.size()
1598 && std::equal(__x.begin(), __x.end(), __y.begin())); }
1599
1600 /**
1601 * @brief Vector ordering relation.
1602 * @param __x A %vector.
1603 * @param __y A %vector of the same type as @a __x.
1604 * @return True iff @a __x is lexicographically less than @a __y.
1605 *
1606 * This is a total ordering relation. It is linear in the size of the
1607 * vectors. The elements must be comparable with @c <.
1608 *
1609 * See std::lexicographical_compare() for how the determination is made.
1610 */
1611 template<typename _Tp, typename _Alloc>
1612 inline bool
1613 operator<(const vector<_Tp, _Alloc>& __x, const vector<_Tp, _Alloc>& __y)
1614 { return std::lexicographical_compare(__x.begin(), __x.end(),
1615 __y.begin(), __y.end()); }
1616
1617 /// Based on operator==
1618 template<typename _Tp, typename _Alloc>
1619 inline bool
1620 operator!=(const vector<_Tp, _Alloc>& __x, const vector<_Tp, _Alloc>& __y)
1621 { return !(__x == __y); }
1622
1623 /// Based on operator<
1624 template<typename _Tp, typename _Alloc>
1625 inline bool
1626 operator>(const vector<_Tp, _Alloc>& __x, const vector<_Tp, _Alloc>& __y)
1627 { return __y < __x; }
1628
1629 /// Based on operator<
1630 template<typename _Tp, typename _Alloc>
1631 inline bool
1632 operator<=(const vector<_Tp, _Alloc>& __x, const vector<_Tp, _Alloc>& __y)
1633 { return !(__y < __x); }
1634
1635 /// Based on operator<
1636 template<typename _Tp, typename _Alloc>
1637 inline bool
1638 operator>=(const vector<_Tp, _Alloc>& __x, const vector<_Tp, _Alloc>& __y)
1639 { return !(__x < __y); }
1640
1641 /// See std::vector::swap().
1642 template<typename _Tp, typename _Alloc>
1643 inline void
1644 swap(vector<_Tp, _Alloc>& __x, vector<_Tp, _Alloc>& __y)
1645 _GLIBCXX_NOEXCEPT_IF(noexcept(__x.swap(__y)))
1646 { __x.swap(__y); }
1647
1648_GLIBCXX_END_NAMESPACE_CONTAINER
1649} // namespace std
1650
1651#endif /* _STL_VECTOR_H */
1652