1 // Vector implementation -*- C++ -*-
3 // Copyright (C) 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008, 2009, 2010,
4 // 2011, 2012 Free Software Foundation, Inc.
6 // This file is part of the GNU ISO C++ Library. This library is free
7 // software; you can redistribute it and/or modify it under the
8 // terms of the GNU General Public License as published by the
9 // Free Software Foundation; either version 3, or (at your option)
12 // This library is distributed in the hope that it will be useful,
13 // but WITHOUT ANY WARRANTY; without even the implied warranty of
14 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15 // GNU General Public License for more details.
17 // Under Section 7 of GPL version 3, you are granted additional
18 // permissions described in the GCC Runtime Library Exception, version
19 // 3.1, as published by the Free Software Foundation.
21 // You should have received a copy of the GNU General Public License and
22 // a copy of the GCC Runtime Library Exception along with this program;
23 // see the files COPYING3 and COPYING.RUNTIME respectively. If not, see
24 // <http://www.gnu.org/licenses/>.
29 * Hewlett-Packard Company
31 * Permission to use, copy, modify, distribute and sell this software
32 * and its documentation for any purpose is hereby granted without fee,
33 * provided that the above copyright notice appear in all copies and
34 * that both that copyright notice and this permission notice appear
35 * in supporting documentation. Hewlett-Packard Company makes no
36 * representations about the suitability of this software for any
37 * purpose. It is provided "as is" without express or implied warranty.
41 * Silicon Graphics Computer Systems, Inc.
43 * Permission to use, copy, modify, distribute and sell this software
44 * and its documentation for any purpose is hereby granted without fee,
45 * provided that the above copyright notice appear in all copies and
46 * that both that copyright notice and this permission notice appear
47 * in supporting documentation. Silicon Graphics makes no
48 * representations about the suitability of this software for any
49 * purpose. It is provided "as is" without express or implied warranty.
52 /** @file bits/stl_vector.h
53 * This is an internal header file, included by other library headers.
54 * Do not attempt to use it directly. @headername{vector}
58 #define _STL_VECTOR_H 1
60 #include <bits/stl_iterator_base_funcs.h>
61 #include <bits/functexcept.h>
62 #include <bits/concept_check.h>
63 #ifdef __GXX_EXPERIMENTAL_CXX0X__
64 #include <initializer_list>
67 namespace std
_GLIBCXX_VISIBILITY(default)
69 _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
71 /// See bits/stl_deque.h's _Deque_base for an explanation.
72 template<typename _Tp
, typename _Alloc
>
75 typedef typename
__gnu_cxx::__alloc_traits
<_Alloc
>::template
76 rebind
<_Tp
>::other _Tp_alloc_type
;
77 typedef typename
__gnu_cxx::__alloc_traits
<_Tp_alloc_type
>::pointer
81 : public _Tp_alloc_type
85 pointer _M_end_of_storage
;
88 : _Tp_alloc_type(), _M_start(0), _M_finish(0), _M_end_of_storage(0)
91 _Vector_impl(_Tp_alloc_type
const& __a
)
92 : _Tp_alloc_type(__a
), _M_start(0), _M_finish(0), _M_end_of_storage(0)
95 #ifdef __GXX_EXPERIMENTAL_CXX0X__
96 _Vector_impl(_Tp_alloc_type
&& __a
)
97 : _Tp_alloc_type(std::move(__a
)),
98 _M_start(0), _M_finish(0), _M_end_of_storage(0)
102 void _M_swap_data(_Vector_impl
& __x
)
104 std::swap(_M_start
, __x
._M_start
);
105 std::swap(_M_finish
, __x
._M_finish
);
106 std::swap(_M_end_of_storage
, __x
._M_end_of_storage
);
111 typedef _Alloc allocator_type
;
114 _M_get_Tp_allocator() _GLIBCXX_NOEXCEPT
115 { return *static_cast<_Tp_alloc_type
*>(&this->_M_impl
); }
117 const _Tp_alloc_type
&
118 _M_get_Tp_allocator() const _GLIBCXX_NOEXCEPT
119 { return *static_cast<const _Tp_alloc_type
*>(&this->_M_impl
); }
122 get_allocator() const _GLIBCXX_NOEXCEPT
123 { return allocator_type(_M_get_Tp_allocator()); }
128 _Vector_base(const allocator_type
& __a
)
131 _Vector_base(size_t __n
)
133 { _M_create_storage(__n
); }
135 _Vector_base(size_t __n
, const allocator_type
& __a
)
137 { _M_create_storage(__n
); }
139 #ifdef __GXX_EXPERIMENTAL_CXX0X__
140 _Vector_base(_Tp_alloc_type
&& __a
)
141 : _M_impl(std::move(__a
)) { }
143 _Vector_base(_Vector_base
&& __x
)
144 : _M_impl(std::move(__x
._M_get_Tp_allocator()))
145 { this->_M_impl
._M_swap_data(__x
._M_impl
); }
147 _Vector_base(_Vector_base
&& __x
, const allocator_type
& __a
)
150 if (__x
.get_allocator() == __a
)
151 this->_M_impl
._M_swap_data(__x
._M_impl
);
154 size_t __n
= __x
._M_impl
._M_finish
- __x
._M_impl
._M_start
;
155 _M_create_storage(__n
);
161 { _M_deallocate(this->_M_impl
._M_start
, this->_M_impl
._M_end_of_storage
162 - this->_M_impl
._M_start
); }
165 _Vector_impl _M_impl
;
168 _M_allocate(size_t __n
)
169 { return __n
!= 0 ? _M_impl
.allocate(__n
) : 0; }
172 _M_deallocate(pointer __p
, size_t __n
)
175 _M_impl
.deallocate(__p
, __n
);
180 _M_create_storage(size_t __n
)
182 this->_M_impl
._M_start
= this->_M_allocate(__n
);
183 this->_M_impl
._M_finish
= this->_M_impl
._M_start
;
184 this->_M_impl
._M_end_of_storage
= this->_M_impl
._M_start
+ __n
;
190 * @brief A standard container which offers fixed time access to
191 * individual elements in any order.
195 * @tparam _Tp Type of element.
196 * @tparam _Alloc Allocator type, defaults to allocator<_Tp>.
198 * Meets the requirements of a <a href="tables.html#65">container</a>, a
199 * <a href="tables.html#66">reversible container</a>, and a
200 * <a href="tables.html#67">sequence</a>, including the
201 * <a href="tables.html#68">optional sequence requirements</a> with the
202 * %exception of @c push_front and @c pop_front.
204 * In some terminology a %vector can be described as a dynamic
205 * C-style array, it offers fast and efficient access to individual
206 * elements in any order and saves the user from worrying about
207 * memory and size allocation. Subscripting ( @c [] ) access is
208 * also provided as with C-style arrays.
210 template<typename _Tp
, typename _Alloc
= std::allocator
<_Tp
> >
211 class vector
: protected _Vector_base
<_Tp
, _Alloc
>
213 // Concept requirements.
214 typedef typename
_Alloc::value_type _Alloc_value_type
;
215 __glibcxx_class_requires(_Tp
, _SGIAssignableConcept
)
216 __glibcxx_class_requires2(_Tp
, _Alloc_value_type
, _SameTypeConcept
)
218 typedef _Vector_base
<_Tp
, _Alloc
> _Base
;
219 typedef typename
_Base::_Tp_alloc_type _Tp_alloc_type
;
220 typedef __gnu_cxx::__alloc_traits
<_Tp_alloc_type
> _Alloc_traits
;
223 typedef _Tp value_type
;
224 typedef typename
_Base::pointer pointer
;
225 typedef typename
_Alloc_traits::const_pointer const_pointer
;
226 typedef typename
_Alloc_traits::reference reference
;
227 typedef typename
_Alloc_traits::const_reference const_reference
;
228 typedef __gnu_cxx::__normal_iterator
<pointer
, vector
> iterator
;
229 typedef __gnu_cxx::__normal_iterator
<const_pointer
, vector
>
231 typedef std::reverse_iterator
<const_iterator
> const_reverse_iterator
;
232 typedef std::reverse_iterator
<iterator
> reverse_iterator
;
233 typedef size_t size_type
;
234 typedef ptrdiff_t difference_type
;
235 typedef _Alloc allocator_type
;
238 using _Base::_M_allocate
;
239 using _Base::_M_deallocate
;
240 using _Base::_M_impl
;
241 using _Base::_M_get_Tp_allocator
;
244 // [23.2.4.1] construct/copy/destroy
245 // (assign() and get_allocator() are also listed in this section)
247 * @brief Default constructor creates no elements.
253 * @brief Creates a %vector with no elements.
254 * @param __a An allocator object.
257 vector(const allocator_type
& __a
)
260 #ifdef __GXX_EXPERIMENTAL_CXX0X__
262 * @brief Creates a %vector with default constructed elements.
263 * @param __n The number of elements to initially create.
264 * @param __a An allocator.
266 * This constructor fills the %vector with @a __n default
267 * constructed elements.
270 vector(size_type __n
, const allocator_type
& __a
= allocator_type())
272 { _M_default_initialize(__n
); }
275 * @brief Creates a %vector with copies of an exemplar element.
276 * @param __n The number of elements to initially create.
277 * @param __value An element to copy.
278 * @param __a An allocator.
280 * This constructor fills the %vector with @a __n copies of @a __value.
282 vector(size_type __n
, const value_type
& __value
,
283 const allocator_type
& __a
= allocator_type())
285 { _M_fill_initialize(__n
, __value
); }
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.
293 * This constructor fills the %vector with @a __n copies of @a __value.
296 vector(size_type __n
, const value_type
& __value
= value_type(),
297 const allocator_type
& __a
= allocator_type())
299 { _M_fill_initialize(__n
, __value
); }
303 * @brief %Vector copy constructor.
304 * @param __x A %vector of identical element and allocator types.
306 * The newly-created %vector uses a copy of the allocation
307 * object used by @a __x. All the elements of @a __x are copied,
308 * but any extra memory in
309 * @a __x (for fast expansion) will not be copied.
311 vector(const vector
& __x
)
313 _Alloc_traits::_S_select_on_copy(__x
._M_get_Tp_allocator()))
314 { this->_M_impl
._M_finish
=
315 std::__uninitialized_copy_a(__x
.begin(), __x
.end(),
316 this->_M_impl
._M_start
,
317 _M_get_Tp_allocator());
320 #ifdef __GXX_EXPERIMENTAL_CXX0X__
322 * @brief %Vector move constructor.
323 * @param __x A %vector of identical element and allocator types.
325 * The newly-created %vector contains the exact contents of @a __x.
326 * The contents of @a __x are a valid, but unspecified %vector.
328 vector(vector
&& __x
) noexcept
329 : _Base(std::move(__x
)) { }
331 /// Copy constructor with alternative allocator
332 vector(const vector
& __x
, const allocator_type
& __a
)
333 : _Base(__x
.size(), __a
)
334 { this->_M_impl
._M_finish
=
335 std::__uninitialized_copy_a(__x
.begin(), __x
.end(),
336 this->_M_impl
._M_start
,
337 _M_get_Tp_allocator());
340 /// Move constructor with alternative allocator
341 vector(vector
&& __rv
, const allocator_type
& __m
)
342 : _Base(std::move(__rv
), __m
)
344 if (__rv
.get_allocator() != __m
)
346 this->_M_impl
._M_finish
=
347 std::__uninitialized_move_a(__rv
.begin(), __rv
.end(),
348 this->_M_impl
._M_start
,
349 _M_get_Tp_allocator());
355 * @brief Builds a %vector from an initializer list.
356 * @param __l An initializer_list.
357 * @param __a An allocator.
359 * Create a %vector consisting of copies of the elements in the
360 * initializer_list @a __l.
362 * This will call the element type's copy constructor N times
363 * (where N is @a __l.size()) and do no memory reallocation.
365 vector(initializer_list
<value_type
> __l
,
366 const allocator_type
& __a
= allocator_type())
369 _M_range_initialize(__l
.begin(), __l
.end(),
370 random_access_iterator_tag());
375 * @brief Builds a %vector from a range.
376 * @param __first An input iterator.
377 * @param __last An input iterator.
378 * @param __a An allocator.
380 * Create a %vector consisting of copies of the elements from
383 * If the iterators are forward, bidirectional, or
384 * random-access, then this will call the elements' copy
385 * constructor N times (where N is distance(first,last)) and do
386 * no memory reallocation. But if only input iterators are
387 * used, then this will do at most 2N calls to the copy
388 * constructor, and logN memory reallocations.
390 #ifdef __GXX_EXPERIMENTAL_CXX0X__
391 template<typename _InputIterator
,
392 typename
= std::_RequireInputIter
<_InputIterator
>>
393 vector(_InputIterator __first
, _InputIterator __last
,
394 const allocator_type
& __a
= allocator_type())
396 { _M_initialize_dispatch(__first
, __last
, __false_type()); }
398 template<typename _InputIterator
>
399 vector(_InputIterator __first
, _InputIterator __last
,
400 const allocator_type
& __a
= allocator_type())
403 // Check whether it's an integral type. If so, it's not an iterator.
404 typedef typename
std::__is_integer
<_InputIterator
>::__type _Integral
;
405 _M_initialize_dispatch(__first
, __last
, _Integral());
410 * The dtor only erases the elements, and note that if the
411 * elements themselves are pointers, the pointed-to memory is
412 * not touched in any way. Managing the pointer is the user's
415 ~vector() _GLIBCXX_NOEXCEPT
416 { std::_Destroy(this->_M_impl
._M_start
, this->_M_impl
._M_finish
,
417 _M_get_Tp_allocator()); }
420 * @brief %Vector assignment operator.
421 * @param __x A %vector of identical element and allocator types.
423 * All the elements of @a __x are copied, but any extra memory in
424 * @a __x (for fast expansion) will not be copied. Unlike the
425 * copy constructor, the allocator object is not copied.
428 operator=(const vector
& __x
);
430 #ifdef __GXX_EXPERIMENTAL_CXX0X__
432 * @brief %Vector move assignment operator.
433 * @param __x A %vector of identical element and allocator types.
435 * The contents of @a __x are moved into this %vector (without copying,
436 * if the allocators permit it).
437 * @a __x is a valid, but unspecified %vector.
440 operator=(vector
&& __x
) noexcept(_Alloc_traits::_S_nothrow_move())
442 constexpr bool __move_storage
=
443 _Alloc_traits::_S_propagate_on_move_assign()
444 || _Alloc_traits::_S_always_equal();
445 _M_move_assign(std::move(__x
),
446 integral_constant
<bool, __move_storage
>());
451 * @brief %Vector list assignment operator.
452 * @param __l An initializer_list.
454 * This function fills a %vector with copies of the elements in the
455 * initializer list @a __l.
457 * Note that the assignment completely changes the %vector and
458 * that the resulting %vector's size is the same as the number
459 * of elements assigned. Old data may be lost.
462 operator=(initializer_list
<value_type
> __l
)
464 this->assign(__l
.begin(), __l
.end());
470 * @brief Assigns a given value to a %vector.
471 * @param __n Number of elements to be assigned.
472 * @param __val Value to be assigned.
474 * This function fills a %vector with @a __n copies of the given
475 * value. Note that the assignment completely changes the
476 * %vector and that the resulting %vector's size is the same as
477 * the number of elements assigned. Old data may be lost.
480 assign(size_type __n
, const value_type
& __val
)
481 { _M_fill_assign(__n
, __val
); }
484 * @brief Assigns a range to a %vector.
485 * @param __first An input iterator.
486 * @param __last An input iterator.
488 * This function fills a %vector with copies of the elements in the
489 * range [__first,__last).
491 * Note that the assignment completely changes the %vector and
492 * that the resulting %vector's size is the same as the number
493 * of elements assigned. Old data may be lost.
495 #ifdef __GXX_EXPERIMENTAL_CXX0X__
496 template<typename _InputIterator
,
497 typename
= std::_RequireInputIter
<_InputIterator
>>
499 assign(_InputIterator __first
, _InputIterator __last
)
500 { _M_assign_dispatch(__first
, __last
, __false_type()); }
502 template<typename _InputIterator
>
504 assign(_InputIterator __first
, _InputIterator __last
)
506 // Check whether it's an integral type. If so, it's not an iterator.
507 typedef typename
std::__is_integer
<_InputIterator
>::__type _Integral
;
508 _M_assign_dispatch(__first
, __last
, _Integral());
512 #ifdef __GXX_EXPERIMENTAL_CXX0X__
514 * @brief Assigns an initializer list to a %vector.
515 * @param __l An initializer_list.
517 * This function fills a %vector with copies of the elements in the
518 * initializer list @a __l.
520 * Note that the assignment completely changes the %vector and
521 * that the resulting %vector's size is the same as the number
522 * of elements assigned. Old data may be lost.
525 assign(initializer_list
<value_type
> __l
)
526 { this->assign(__l
.begin(), __l
.end()); }
529 /// Get a copy of the memory allocation object.
530 using _Base::get_allocator
;
534 * Returns a read/write iterator that points to the first
535 * element in the %vector. Iteration is done in ordinary
539 begin() _GLIBCXX_NOEXCEPT
540 { return iterator(this->_M_impl
._M_start
); }
543 * Returns a read-only (constant) iterator that points to the
544 * first element in the %vector. Iteration is done in ordinary
548 begin() const _GLIBCXX_NOEXCEPT
549 { return const_iterator(this->_M_impl
._M_start
); }
552 * Returns a read/write iterator that points one past the last
553 * element in the %vector. Iteration is done in ordinary
557 end() _GLIBCXX_NOEXCEPT
558 { return iterator(this->_M_impl
._M_finish
); }
561 * Returns a read-only (constant) iterator that points one past
562 * the last element in the %vector. Iteration is done in
563 * ordinary element order.
566 end() const _GLIBCXX_NOEXCEPT
567 { return const_iterator(this->_M_impl
._M_finish
); }
570 * Returns a read/write reverse iterator that points to the
571 * last element in the %vector. Iteration is done in reverse
575 rbegin() _GLIBCXX_NOEXCEPT
576 { return reverse_iterator(end()); }
579 * Returns a read-only (constant) reverse iterator that points
580 * to the last element in the %vector. Iteration is done in
581 * reverse element order.
583 const_reverse_iterator
584 rbegin() const _GLIBCXX_NOEXCEPT
585 { return const_reverse_iterator(end()); }
588 * Returns a read/write reverse iterator that points to one
589 * before the first element in the %vector. Iteration is done
590 * in reverse element order.
593 rend() _GLIBCXX_NOEXCEPT
594 { return reverse_iterator(begin()); }
597 * Returns a read-only (constant) reverse iterator that points
598 * to one before the first element in the %vector. Iteration
599 * is done in reverse element order.
601 const_reverse_iterator
602 rend() const _GLIBCXX_NOEXCEPT
603 { return const_reverse_iterator(begin()); }
605 #ifdef __GXX_EXPERIMENTAL_CXX0X__
607 * Returns a read-only (constant) iterator that points to the
608 * first element in the %vector. Iteration is done in ordinary
612 cbegin() const noexcept
613 { return const_iterator(this->_M_impl
._M_start
); }
616 * Returns a read-only (constant) iterator that points one past
617 * the last element in the %vector. Iteration is done in
618 * ordinary element order.
621 cend() const noexcept
622 { return const_iterator(this->_M_impl
._M_finish
); }
625 * Returns a read-only (constant) reverse iterator that points
626 * to the last element in the %vector. Iteration is done in
627 * reverse element order.
629 const_reverse_iterator
630 crbegin() const noexcept
631 { return const_reverse_iterator(end()); }
634 * Returns a read-only (constant) reverse iterator that points
635 * to one before the first element in the %vector. Iteration
636 * is done in reverse element order.
638 const_reverse_iterator
639 crend() const noexcept
640 { return const_reverse_iterator(begin()); }
643 // [23.2.4.2] capacity
644 /** Returns the number of elements in the %vector. */
646 size() const _GLIBCXX_NOEXCEPT
647 { return size_type(this->_M_impl
._M_finish
- this->_M_impl
._M_start
); }
649 /** Returns the size() of the largest possible %vector. */
651 max_size() const _GLIBCXX_NOEXCEPT
652 { return _Alloc_traits::max_size(_M_get_Tp_allocator()); }
654 #ifdef __GXX_EXPERIMENTAL_CXX0X__
656 * @brief Resizes the %vector to the specified number of elements.
657 * @param __new_size Number of elements the %vector should contain.
659 * This function will %resize the %vector to the specified
660 * number of elements. If the number is smaller than the
661 * %vector's current size the %vector is truncated, otherwise
662 * default constructed elements are appended.
665 resize(size_type __new_size
)
667 if (__new_size
> size())
668 _M_default_append(__new_size
- size());
669 else if (__new_size
< size())
670 _M_erase_at_end(this->_M_impl
._M_start
+ __new_size
);
674 * @brief Resizes the %vector to the specified number of elements.
675 * @param __new_size Number of elements the %vector should contain.
676 * @param __x Data with which new elements should be populated.
678 * This function will %resize the %vector to the specified
679 * number of elements. If the number is smaller than the
680 * %vector's current size the %vector is truncated, otherwise
681 * the %vector is extended and new elements are populated with
685 resize(size_type __new_size
, const value_type
& __x
)
687 if (__new_size
> size())
688 insert(end(), __new_size
- size(), __x
);
689 else if (__new_size
< size())
690 _M_erase_at_end(this->_M_impl
._M_start
+ __new_size
);
694 * @brief Resizes the %vector to the specified number of elements.
695 * @param __new_size Number of elements the %vector should contain.
696 * @param __x Data with which new elements should be populated.
698 * This function will %resize the %vector to the specified
699 * number of elements. If the number is smaller than the
700 * %vector's current size the %vector is truncated, otherwise
701 * the %vector is extended and new elements are populated with
705 resize(size_type __new_size
, value_type __x
= value_type())
707 if (__new_size
> size())
708 insert(end(), __new_size
- size(), __x
);
709 else if (__new_size
< size())
710 _M_erase_at_end(this->_M_impl
._M_start
+ __new_size
);
714 #ifdef __GXX_EXPERIMENTAL_CXX0X__
715 /** A non-binding request to reduce capacity() to size(). */
718 { _M_shrink_to_fit(); }
722 * Returns the total number of elements that the %vector can
723 * hold before needing to allocate more memory.
726 capacity() const _GLIBCXX_NOEXCEPT
727 { return size_type(this->_M_impl
._M_end_of_storage
728 - this->_M_impl
._M_start
); }
731 * Returns true if the %vector is empty. (Thus begin() would
735 empty() const _GLIBCXX_NOEXCEPT
736 { return begin() == end(); }
739 * @brief Attempt to preallocate enough memory for specified number of
741 * @param __n Number of elements required.
742 * @throw std::length_error If @a n exceeds @c max_size().
744 * This function attempts to reserve enough memory for the
745 * %vector to hold the specified number of elements. If the
746 * number requested is more than max_size(), length_error is
749 * The advantage of this function is that if optimal code is a
750 * necessity and the user can determine the number of elements
751 * that will be required, the user can reserve the memory in
752 * %advance, and thus prevent a possible reallocation of memory
753 * and copying of %vector data.
756 reserve(size_type __n
);
760 * @brief Subscript access to the data contained in the %vector.
761 * @param __n The index of the element for which data should be
763 * @return Read/write reference to data.
765 * This operator allows for easy, array-style, data access.
766 * Note that data access with this operator is unchecked and
767 * out_of_range lookups are not defined. (For checked lookups
771 operator[](size_type __n
)
772 { return *(this->_M_impl
._M_start
+ __n
); }
775 * @brief Subscript access to the data contained in the %vector.
776 * @param __n The index of the element for which data should be
778 * @return Read-only (constant) reference to data.
780 * This operator allows for easy, array-style, data access.
781 * Note that data access with this operator is unchecked and
782 * out_of_range lookups are not defined. (For checked lookups
786 operator[](size_type __n
) const
787 { return *(this->_M_impl
._M_start
+ __n
); }
790 /// Safety check used only from at().
792 _M_range_check(size_type __n
) const
794 if (__n
>= this->size())
795 __throw_out_of_range(__N("vector::_M_range_check"));
800 * @brief Provides access to the data contained in the %vector.
801 * @param __n The index of the element for which data should be
803 * @return Read/write reference to data.
804 * @throw std::out_of_range If @a __n is an invalid index.
806 * This function provides for safer data access. The parameter
807 * is first checked that it is in the range of the vector. The
808 * function throws out_of_range if the check fails.
818 * @brief Provides access to the data contained in the %vector.
819 * @param __n The index of the element for which data should be
821 * @return Read-only (constant) reference to data.
822 * @throw std::out_of_range If @a __n is an invalid index.
824 * This function provides for safer data access. The parameter
825 * is first checked that it is in the range of the vector. The
826 * function throws out_of_range if the check fails.
829 at(size_type __n
) const
836 * Returns a read/write reference to the data at the first
837 * element of the %vector.
844 * Returns a read-only (constant) reference to the data at the first
845 * element of the %vector.
852 * Returns a read/write reference to the data at the last
853 * element of the %vector.
857 { return *(end() - 1); }
860 * Returns a read-only (constant) reference to the data at the
861 * last element of the %vector.
865 { return *(end() - 1); }
867 // _GLIBCXX_RESOLVE_LIB_DEFECTS
868 // DR 464. Suggestion for new member functions in standard containers.
871 * Returns a pointer such that [data(), data() + size()) is a valid
872 * range. For a non-empty %vector, data() == &front().
874 #ifdef __GXX_EXPERIMENTAL_CXX0X__
879 data() _GLIBCXX_NOEXCEPT
880 { return std::__addressof(front()); }
882 #ifdef __GXX_EXPERIMENTAL_CXX0X__
887 data() const _GLIBCXX_NOEXCEPT
888 { return std::__addressof(front()); }
890 // [23.2.4.3] modifiers
892 * @brief Add data to the end of the %vector.
893 * @param __x Data to be added.
895 * This is a typical stack operation. The function creates an
896 * element at the end of the %vector and assigns the given data
897 * to it. Due to the nature of a %vector this operation can be
898 * done in constant time if the %vector has preallocated space
902 push_back(const value_type
& __x
)
904 if (this->_M_impl
._M_finish
!= this->_M_impl
._M_end_of_storage
)
906 _Alloc_traits::construct(this->_M_impl
, this->_M_impl
._M_finish
,
908 ++this->_M_impl
._M_finish
;
911 #ifdef __GXX_EXPERIMENTAL_CXX0X__
912 _M_emplace_back_aux(__x
);
914 _M_insert_aux(end(), __x
);
918 #ifdef __GXX_EXPERIMENTAL_CXX0X__
920 push_back(value_type
&& __x
)
921 { emplace_back(std::move(__x
)); }
923 template<typename
... _Args
>
925 emplace_back(_Args
&&... __args
);
929 * @brief Removes last element.
931 * This is a typical stack operation. It shrinks the %vector by one.
933 * Note that no data is returned, and if the last element's
934 * data is needed, it should be retrieved before pop_back() is
940 --this->_M_impl
._M_finish
;
941 _Alloc_traits::destroy(this->_M_impl
, this->_M_impl
._M_finish
);
944 #ifdef __GXX_EXPERIMENTAL_CXX0X__
946 * @brief Inserts an object in %vector before specified iterator.
947 * @param __position An iterator into the %vector.
948 * @param __args Arguments.
949 * @return An iterator that points to the inserted data.
951 * This function will insert an object of type T constructed
952 * with T(std::forward<Args>(args)...) before the specified location.
953 * Note that this kind of operation could be expensive for a %vector
954 * and if it is frequently used the user should consider using
957 template<typename
... _Args
>
959 emplace(iterator __position
, _Args
&&... __args
);
963 * @brief Inserts given value into %vector before specified iterator.
964 * @param __position An iterator into the %vector.
965 * @param __x Data to be inserted.
966 * @return An iterator that points to the inserted data.
968 * This function will insert a copy of the given value before
969 * the specified location. Note that this kind of operation
970 * could be expensive for a %vector and if it is frequently
971 * used the user should consider using std::list.
974 insert(iterator __position
, const value_type
& __x
);
976 #ifdef __GXX_EXPERIMENTAL_CXX0X__
978 * @brief Inserts given rvalue into %vector before specified iterator.
979 * @param __position An iterator into the %vector.
980 * @param __x Data to be inserted.
981 * @return An iterator that points to the inserted data.
983 * This function will insert a copy of the given rvalue before
984 * the specified location. Note that this kind of operation
985 * could be expensive for a %vector and if it is frequently
986 * used the user should consider using std::list.
989 insert(iterator __position
, value_type
&& __x
)
990 { return emplace(__position
, std::move(__x
)); }
993 * @brief Inserts an initializer_list into the %vector.
994 * @param __position An iterator into the %vector.
995 * @param __l An initializer_list.
997 * This function will insert copies of the data in the
998 * initializer_list @a l into the %vector before the location
999 * specified by @a position.
1001 * Note that this kind of operation could be expensive for a
1002 * %vector and if it is frequently used the user should
1003 * consider using std::list.
1006 insert(iterator __position
, initializer_list
<value_type
> __l
)
1007 { this->insert(__position
, __l
.begin(), __l
.end()); }
1011 * @brief Inserts a number of copies of given data into the %vector.
1012 * @param __position An iterator into the %vector.
1013 * @param __n Number of elements to be inserted.
1014 * @param __x Data to be inserted.
1016 * This function will insert a specified number of copies of
1017 * the given data before the location specified by @a position.
1019 * Note that this kind of operation could be expensive for a
1020 * %vector and if it is frequently used the user should
1021 * consider using std::list.
1024 insert(iterator __position
, size_type __n
, const value_type
& __x
)
1025 { _M_fill_insert(__position
, __n
, __x
); }
1028 * @brief Inserts a range into the %vector.
1029 * @param __position An iterator into the %vector.
1030 * @param __first An input iterator.
1031 * @param __last An input iterator.
1033 * This function will insert copies of the data in the range
1034 * [__first,__last) into the %vector before the location specified
1037 * Note that this kind of operation could be expensive for a
1038 * %vector and if it is frequently used the user should
1039 * consider using std::list.
1041 #ifdef __GXX_EXPERIMENTAL_CXX0X__
1042 template<typename _InputIterator
,
1043 typename
= std::_RequireInputIter
<_InputIterator
>>
1045 insert(iterator __position
, _InputIterator __first
,
1046 _InputIterator __last
)
1047 { _M_insert_dispatch(__position
, __first
, __last
, __false_type()); }
1049 template<typename _InputIterator
>
1051 insert(iterator __position
, _InputIterator __first
,
1052 _InputIterator __last
)
1054 // Check whether it's an integral type. If so, it's not an iterator.
1055 typedef typename
std::__is_integer
<_InputIterator
>::__type _Integral
;
1056 _M_insert_dispatch(__position
, __first
, __last
, _Integral());
1061 * @brief Remove element at given position.
1062 * @param __position Iterator pointing to element to be erased.
1063 * @return An iterator pointing to the next element (or end()).
1065 * This function will erase the element at the given position and thus
1066 * shorten the %vector by one.
1068 * Note This operation could be expensive and if it is
1069 * frequently used the user should consider using std::list.
1070 * The user is also cautioned that this function only erases
1071 * the element, and that if the element is itself a pointer,
1072 * the pointed-to memory is not touched in any way. Managing
1073 * the pointer is the user's responsibility.
1076 erase(iterator __position
);
1079 * @brief Remove a range of elements.
1080 * @param __first Iterator pointing to the first element to be erased.
1081 * @param __last Iterator pointing to one past the last element to be
1083 * @return An iterator pointing to the element pointed to by @a __last
1084 * prior to erasing (or end()).
1086 * This function will erase the elements in the range
1087 * [__first,__last) and shorten the %vector accordingly.
1089 * Note This operation could be expensive and if it is
1090 * frequently used the user should consider using std::list.
1091 * The user is also cautioned that this function only erases
1092 * the elements, and that if the elements themselves are
1093 * pointers, the pointed-to memory is not touched in any way.
1094 * Managing the pointer is the user's responsibility.
1097 erase(iterator __first
, iterator __last
);
1100 * @brief Swaps data with another %vector.
1101 * @param __x A %vector of the same element and allocator types.
1103 * This exchanges the elements between two vectors in constant time.
1104 * (Three pointers, so it should be quite fast.)
1105 * Note that the global std::swap() function is specialized such that
1106 * std::swap(v1,v2) will feed to this function.
1110 #ifdef __GXX_EXPERIMENTAL_CXX0X__
1111 noexcept(_Alloc_traits::_S_nothrow_swap())
1114 this->_M_impl
._M_swap_data(__x
._M_impl
);
1115 _Alloc_traits::_S_on_swap(_M_get_Tp_allocator(),
1116 __x
._M_get_Tp_allocator());
1120 * Erases all the elements. Note that this function only erases the
1121 * elements, and that if the elements themselves are pointers, the
1122 * pointed-to memory is not touched in any way. Managing the pointer is
1123 * the user's responsibility.
1126 clear() _GLIBCXX_NOEXCEPT
1127 { _M_erase_at_end(this->_M_impl
._M_start
); }
1131 * Memory expansion handler. Uses the member allocation function to
1132 * obtain @a n bytes of memory, and then copies [first,last) into it.
1134 template<typename _ForwardIterator
>
1136 _M_allocate_and_copy(size_type __n
,
1137 _ForwardIterator __first
, _ForwardIterator __last
)
1139 pointer __result
= this->_M_allocate(__n
);
1142 std::__uninitialized_copy_a(__first
, __last
, __result
,
1143 _M_get_Tp_allocator());
1148 _M_deallocate(__result
, __n
);
1149 __throw_exception_again
;
1154 // Internal constructor functions follow.
1156 // Called by the range constructor to implement [23.1.1]/9
1158 // _GLIBCXX_RESOLVE_LIB_DEFECTS
1159 // 438. Ambiguity in the "do the right thing" clause
1160 template<typename _Integer
>
1162 _M_initialize_dispatch(_Integer __n
, _Integer __value
, __true_type
)
1164 this->_M_impl
._M_start
= _M_allocate(static_cast<size_type
>(__n
));
1165 this->_M_impl
._M_end_of_storage
=
1166 this->_M_impl
._M_start
+ static_cast<size_type
>(__n
);
1167 _M_fill_initialize(static_cast<size_type
>(__n
), __value
);
1170 // Called by the range constructor to implement [23.1.1]/9
1171 template<typename _InputIterator
>
1173 _M_initialize_dispatch(_InputIterator __first
, _InputIterator __last
,
1176 typedef typename
std::iterator_traits
<_InputIterator
>::
1177 iterator_category _IterCategory
;
1178 _M_range_initialize(__first
, __last
, _IterCategory());
1181 // Called by the second initialize_dispatch above
1182 template<typename _InputIterator
>
1184 _M_range_initialize(_InputIterator __first
,
1185 _InputIterator __last
, std::input_iterator_tag
)
1187 for (; __first
!= __last
; ++__first
)
1188 push_back(*__first
);
1191 // Called by the second initialize_dispatch above
1192 template<typename _ForwardIterator
>
1194 _M_range_initialize(_ForwardIterator __first
,
1195 _ForwardIterator __last
, std::forward_iterator_tag
)
1197 const size_type __n
= std::distance(__first
, __last
);
1198 this->_M_impl
._M_start
= this->_M_allocate(__n
);
1199 this->_M_impl
._M_end_of_storage
= this->_M_impl
._M_start
+ __n
;
1200 this->_M_impl
._M_finish
=
1201 std::__uninitialized_copy_a(__first
, __last
,
1202 this->_M_impl
._M_start
,
1203 _M_get_Tp_allocator());
1206 // Called by the first initialize_dispatch above and by the
1207 // vector(n,value,a) constructor.
1209 _M_fill_initialize(size_type __n
, const value_type
& __value
)
1211 std::__uninitialized_fill_n_a(this->_M_impl
._M_start
, __n
, __value
,
1212 _M_get_Tp_allocator());
1213 this->_M_impl
._M_finish
= this->_M_impl
._M_end_of_storage
;
1216 #ifdef __GXX_EXPERIMENTAL_CXX0X__
1217 // Called by the vector(n) constructor.
1219 _M_default_initialize(size_type __n
)
1221 std::__uninitialized_default_n_a(this->_M_impl
._M_start
, __n
,
1222 _M_get_Tp_allocator());
1223 this->_M_impl
._M_finish
= this->_M_impl
._M_end_of_storage
;
1227 // Internal assign functions follow. The *_aux functions do the actual
1228 // assignment work for the range versions.
1230 // Called by the range assign to implement [23.1.1]/9
1232 // _GLIBCXX_RESOLVE_LIB_DEFECTS
1233 // 438. Ambiguity in the "do the right thing" clause
1234 template<typename _Integer
>
1236 _M_assign_dispatch(_Integer __n
, _Integer __val
, __true_type
)
1237 { _M_fill_assign(__n
, __val
); }
1239 // Called by the range assign to implement [23.1.1]/9
1240 template<typename _InputIterator
>
1242 _M_assign_dispatch(_InputIterator __first
, _InputIterator __last
,
1245 typedef typename
std::iterator_traits
<_InputIterator
>::
1246 iterator_category _IterCategory
;
1247 _M_assign_aux(__first
, __last
, _IterCategory());
1250 // Called by the second assign_dispatch above
1251 template<typename _InputIterator
>
1253 _M_assign_aux(_InputIterator __first
, _InputIterator __last
,
1254 std::input_iterator_tag
);
1256 // Called by the second assign_dispatch above
1257 template<typename _ForwardIterator
>
1259 _M_assign_aux(_ForwardIterator __first
, _ForwardIterator __last
,
1260 std::forward_iterator_tag
);
1262 // Called by assign(n,t), and the range assign when it turns out
1263 // to be the same thing.
1265 _M_fill_assign(size_type __n
, const value_type
& __val
);
1268 // Internal insert functions follow.
1270 // Called by the range insert to implement [23.1.1]/9
1272 // _GLIBCXX_RESOLVE_LIB_DEFECTS
1273 // 438. Ambiguity in the "do the right thing" clause
1274 template<typename _Integer
>
1276 _M_insert_dispatch(iterator __pos
, _Integer __n
, _Integer __val
,
1278 { _M_fill_insert(__pos
, __n
, __val
); }
1280 // Called by the range insert to implement [23.1.1]/9
1281 template<typename _InputIterator
>
1283 _M_insert_dispatch(iterator __pos
, _InputIterator __first
,
1284 _InputIterator __last
, __false_type
)
1286 typedef typename
std::iterator_traits
<_InputIterator
>::
1287 iterator_category _IterCategory
;
1288 _M_range_insert(__pos
, __first
, __last
, _IterCategory());
1291 // Called by the second insert_dispatch above
1292 template<typename _InputIterator
>
1294 _M_range_insert(iterator __pos
, _InputIterator __first
,
1295 _InputIterator __last
, std::input_iterator_tag
);
1297 // Called by the second insert_dispatch above
1298 template<typename _ForwardIterator
>
1300 _M_range_insert(iterator __pos
, _ForwardIterator __first
,
1301 _ForwardIterator __last
, std::forward_iterator_tag
);
1303 // Called by insert(p,n,x), and the range insert when it turns out to be
1306 _M_fill_insert(iterator __pos
, size_type __n
, const value_type
& __x
);
1308 #ifdef __GXX_EXPERIMENTAL_CXX0X__
1309 // Called by resize(n).
1311 _M_default_append(size_type __n
);
1317 // Called by insert(p,x)
1318 #ifndef __GXX_EXPERIMENTAL_CXX0X__
1320 _M_insert_aux(iterator __position
, const value_type
& __x
);
1322 template<typename
... _Args
>
1324 _M_insert_aux(iterator __position
, _Args
&&... __args
);
1326 template<typename
... _Args
>
1328 _M_emplace_back_aux(_Args
&&... __args
);
1331 // Called by the latter.
1333 _M_check_len(size_type __n
, const char* __s
) const
1335 if (max_size() - size() < __n
)
1336 __throw_length_error(__N(__s
));
1338 const size_type __len
= size() + std::max(size(), __n
);
1339 return (__len
< size() || __len
> max_size()) ? max_size() : __len
;
1342 // Internal erase functions follow.
1344 // Called by erase(q1,q2), clear(), resize(), _M_fill_assign,
1347 _M_erase_at_end(pointer __pos
)
1349 std::_Destroy(__pos
, this->_M_impl
._M_finish
, _M_get_Tp_allocator());
1350 this->_M_impl
._M_finish
= __pos
;
1353 #ifdef __GXX_EXPERIMENTAL_CXX0X__
1355 // Constant-time move assignment when source object's memory can be
1356 // moved, either because the source's allocator will move too
1357 // or because the allocators are equal.
1359 _M_move_assign(vector
&& __x
, std::true_type
) noexcept
1361 const vector
__tmp(std::move(*this));
1362 this->_M_impl
._M_swap_data(__x
._M_impl
);
1363 if (_Alloc_traits::_S_propagate_on_move_assign())
1364 std::__alloc_on_move(_M_get_Tp_allocator(),
1365 __x
._M_get_Tp_allocator());
1368 // Do move assignment when it might not be possible to move source
1369 // object's memory, resulting in a linear-time operation.
1371 _M_move_assign(vector
&& __x
, std::false_type
)
1373 if (__x
._M_get_Tp_allocator() == this->_M_get_Tp_allocator())
1374 _M_move_assign(std::move(__x
), std::true_type());
1377 // The rvalue's allocator cannot be moved and is not equal,
1378 // so we need to individually move each element.
1379 this->assign(std::__make_move_if_noexcept_iterator(__x
.begin()),
1380 std::__make_move_if_noexcept_iterator(__x
.end()));
1389 * @brief Vector equality comparison.
1390 * @param __x A %vector.
1391 * @param __y A %vector of the same type as @a __x.
1392 * @return True iff the size and elements of the vectors are equal.
1394 * This is an equivalence relation. It is linear in the size of the
1395 * vectors. Vectors are considered equivalent if their sizes are equal,
1396 * and if corresponding elements compare equal.
1398 template<typename _Tp
, typename _Alloc
>
1400 operator==(const vector
<_Tp
, _Alloc
>& __x
, const vector
<_Tp
, _Alloc
>& __y
)
1401 { return (__x
.size() == __y
.size()
1402 && std::equal(__x
.begin(), __x
.end(), __y
.begin())); }
1405 * @brief Vector ordering relation.
1406 * @param __x A %vector.
1407 * @param __y A %vector of the same type as @a __x.
1408 * @return True iff @a __x is lexicographically less than @a __y.
1410 * This is a total ordering relation. It is linear in the size of the
1411 * vectors. The elements must be comparable with @c <.
1413 * See std::lexicographical_compare() for how the determination is made.
1415 template<typename _Tp
, typename _Alloc
>
1417 operator<(const vector
<_Tp
, _Alloc
>& __x
, const vector
<_Tp
, _Alloc
>& __y
)
1418 { return std::lexicographical_compare(__x
.begin(), __x
.end(),
1419 __y
.begin(), __y
.end()); }
1421 /// Based on operator==
1422 template<typename _Tp
, typename _Alloc
>
1424 operator!=(const vector
<_Tp
, _Alloc
>& __x
, const vector
<_Tp
, _Alloc
>& __y
)
1425 { return !(__x
== __y
); }
1427 /// Based on operator<
1428 template<typename _Tp
, typename _Alloc
>
1430 operator>(const vector
<_Tp
, _Alloc
>& __x
, const vector
<_Tp
, _Alloc
>& __y
)
1431 { return __y
< __x
; }
1433 /// Based on operator<
1434 template<typename _Tp
, typename _Alloc
>
1436 operator<=(const vector
<_Tp
, _Alloc
>& __x
, const vector
<_Tp
, _Alloc
>& __y
)
1437 { return !(__y
< __x
); }
1439 /// Based on operator<
1440 template<typename _Tp
, typename _Alloc
>
1442 operator>=(const vector
<_Tp
, _Alloc
>& __x
, const vector
<_Tp
, _Alloc
>& __y
)
1443 { return !(__x
< __y
); }
1445 /// See std::vector::swap().
1446 template<typename _Tp
, typename _Alloc
>
1448 swap(vector
<_Tp
, _Alloc
>& __x
, vector
<_Tp
, _Alloc
>& __y
)
1451 _GLIBCXX_END_NAMESPACE_CONTAINER
1454 #endif /* _STL_VECTOR_H */