1 // Vector implementation -*- C++ -*-
3 // Copyright (C) 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008, 2009, 2010,
4 // 2011 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 * Meets the requirements of a <a href="tables.html#65">container</a>, a
196 * <a href="tables.html#66">reversible container</a>, and a
197 * <a href="tables.html#67">sequence</a>, including the
198 * <a href="tables.html#68">optional sequence requirements</a> with the
199 * %exception of @c push_front and @c pop_front.
201 * In some terminology a %vector can be described as a dynamic
202 * C-style array, it offers fast and efficient access to individual
203 * elements in any order and saves the user from worrying about
204 * memory and size allocation. Subscripting ( @c [] ) access is
205 * also provided as with C-style arrays.
207 template<typename _Tp, typename _Alloc = std::allocator<_Tp> >
208 class vector : protected _Vector_base<_Tp, _Alloc>
210 // Concept requirements.
211 typedef typename _Alloc::value_type _Alloc_value_type;
212 __glibcxx_class_requires(_Tp, _SGIAssignableConcept)
213 __glibcxx_class_requires2(_Tp, _Alloc_value_type, _SameTypeConcept)
215 typedef _Vector_base<_Tp, _Alloc> _Base;
216 typedef typename _Base::_Tp_alloc_type _Tp_alloc_type;
217 typedef __gnu_cxx::__alloc_traits<_Tp_alloc_type> _Alloc_traits;
220 typedef _Tp value_type;
221 typedef typename _Base::pointer pointer;
222 typedef typename _Alloc_traits::const_pointer const_pointer;
223 typedef typename _Alloc_traits::reference reference;
224 typedef typename _Alloc_traits::const_reference const_reference;
225 typedef __gnu_cxx::__normal_iterator<pointer, vector> iterator;
226 typedef __gnu_cxx::__normal_iterator<const_pointer, vector>
228 typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
229 typedef std::reverse_iterator<iterator> reverse_iterator;
230 typedef size_t size_type;
231 typedef ptrdiff_t difference_type;
232 typedef _Alloc allocator_type;
235 using _Base::_M_allocate;
236 using _Base::_M_deallocate;
237 using _Base::_M_impl;
238 using _Base::_M_get_Tp_allocator;
241 // [23.2.4.1] construct/copy/destroy
242 // (assign() and get_allocator() are also listed in this section)
244 * @brief Default constructor creates no elements.
250 * @brief Creates a %vector with no elements.
251 * @param __a An allocator object.
254 vector(const allocator_type& __a)
257 #ifdef __GXX_EXPERIMENTAL_CXX0X__
259 * @brief Creates a %vector with default constructed elements.
260 * @param __n The number of elements to initially create.
262 * This constructor fills the %vector with @a __n default
263 * constructed elements.
266 vector(size_type __n)
268 { _M_default_initialize(__n); }
271 * @brief Creates a %vector with copies of an exemplar element.
272 * @param __n The number of elements to initially create.
273 * @param __value An element to copy.
274 * @param __a An allocator.
276 * This constructor fills the %vector with @a __n copies of @a __value.
278 vector(size_type __n, const value_type& __value,
279 const allocator_type& __a = allocator_type())
281 { _M_fill_initialize(__n, __value); }
284 * @brief Creates a %vector with copies of an exemplar element.
285 * @param __n The number of elements to initially create.
286 * @param __value An element to copy.
287 * @param __a An allocator.
289 * This constructor fills the %vector with @a __n copies of @a __value.
292 vector(size_type __n, const value_type& __value = value_type(),
293 const allocator_type& __a = allocator_type())
295 { _M_fill_initialize(__n, __value); }
299 * @brief %Vector copy constructor.
300 * @param __x A %vector of identical element and allocator types.
302 * The newly-created %vector uses a copy of the allocation
303 * object used by @a __x. All the elements of @a __x are copied,
304 * but any extra memory in
305 * @a __x (for fast expansion) will not be copied.
307 vector(const vector& __x)
309 _Alloc_traits::_S_select_on_copy(__x._M_get_Tp_allocator()))
310 { this->_M_impl._M_finish =
311 std::__uninitialized_copy_a(__x.begin(), __x.end(),
312 this->_M_impl._M_start,
313 _M_get_Tp_allocator());
316 #ifdef __GXX_EXPERIMENTAL_CXX0X__
318 * @brief %Vector move constructor.
319 * @param __x A %vector of identical element and allocator types.
321 * The newly-created %vector contains the exact contents of @a __x.
322 * The contents of @a __x are a valid, but unspecified %vector.
324 vector(vector&& __x) noexcept
325 : _Base(std::move(__x)) { }
327 /// Copy constructor with alternative allocator
328 vector(const vector& __x, const allocator_type& __a)
329 : _Base(__x.size(), __a)
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());
336 /// Move constructor with alternative allocator
337 vector(vector&& __rv, const allocator_type& __m)
338 : _Base(std::move(__rv), __m)
340 if (__rv.get_allocator() != __m)
342 this->_M_impl._M_finish =
343 std::__uninitialized_move_a(__rv.begin(), __rv.end(),
344 this->_M_impl._M_start,
345 _M_get_Tp_allocator());
351 * @brief Builds a %vector from an initializer list.
352 * @param __l An initializer_list.
353 * @param __a An allocator.
355 * Create a %vector consisting of copies of the elements in the
356 * initializer_list @a __l.
358 * This will call the element type's copy constructor N times
359 * (where N is @a __l.size()) and do no memory reallocation.
361 vector(initializer_list<value_type> __l,
362 const allocator_type& __a = allocator_type())
365 _M_range_initialize(__l.begin(), __l.end(),
366 random_access_iterator_tag());
371 * @brief Builds a %vector from a range.
372 * @param __first An input iterator.
373 * @param __last An input iterator.
374 * @param __a An allocator.
376 * Create a %vector consisting of copies of the elements from
379 * If the iterators are forward, bidirectional, or
380 * random-access, then this will call the elements' copy
381 * constructor N times (where N is distance(first,last)) and do
382 * no memory reallocation. But if only input iterators are
383 * used, then this will do at most 2N calls to the copy
384 * constructor, and logN memory reallocations.
386 template<typename _InputIterator>
387 vector(_InputIterator __first, _InputIterator __last,
388 const allocator_type& __a = allocator_type())
391 // Check whether it's an integral type. If so, it's not an iterator.
392 typedef typename std::__is_integer<_InputIterator>::__type _Integral;
393 _M_initialize_dispatch(__first, __last, _Integral());
397 * The dtor only erases the elements, and note that if the
398 * elements themselves are pointers, the pointed-to memory is
399 * not touched in any way. Managing the pointer is the user's
402 ~vector() _GLIBCXX_NOEXCEPT
403 { std::_Destroy(this->_M_impl._M_start, this->_M_impl._M_finish,
404 _M_get_Tp_allocator()); }
407 * @brief %Vector assignment operator.
408 * @param __x A %vector of identical element and allocator types.
410 * All the elements of @a __x are copied, but any extra memory in
411 * @a __x (for fast expansion) will not be copied. Unlike the
412 * copy constructor, the allocator object is not copied.
415 operator=(const vector& __x);
417 #ifdef __GXX_EXPERIMENTAL_CXX0X__
419 * @brief %Vector move assignment operator.
420 * @param __x A %vector of identical element and allocator types.
422 * The contents of @a __x are moved into this %vector (without copying,
423 * if the allocators permit it).
424 * @a __x is a valid, but unspecified %vector.
427 operator=(vector&& __x) noexcept(_Alloc_traits::_S_nothrow_move())
429 constexpr bool __move_storage =
430 _Alloc_traits::_S_propagate_on_move_assign()
431 || _Alloc_traits::_S_always_equal();
432 _M_move_assign(std::move(__x),
433 integral_constant<bool, __move_storage>());
438 * @brief %Vector list assignment operator.
439 * @param __l An initializer_list.
441 * This function fills a %vector with copies of the elements in the
442 * initializer list @a __l.
444 * Note that the assignment completely changes the %vector and
445 * that the resulting %vector's size is the same as the number
446 * of elements assigned. Old data may be lost.
449 operator=(initializer_list<value_type> __l)
451 this->assign(__l.begin(), __l.end());
457 * @brief Assigns a given value to a %vector.
458 * @param __n Number of elements to be assigned.
459 * @param __val Value to be assigned.
461 * This function fills a %vector with @a __n copies of the given
462 * value. Note that the assignment completely changes the
463 * %vector and that the resulting %vector's size is the same as
464 * the number of elements assigned. Old data may be lost.
467 assign(size_type __n, const value_type& __val)
468 { _M_fill_assign(__n, __val); }
471 * @brief Assigns a range to a %vector.
472 * @param __first An input iterator.
473 * @param __last An input iterator.
475 * This function fills a %vector with copies of the elements in the
476 * range [__first,__last).
478 * Note that the assignment completely changes the %vector and
479 * that the resulting %vector's size is the same as the number
480 * of elements assigned. Old data may be lost.
482 template<typename _InputIterator>
484 assign(_InputIterator __first, _InputIterator __last)
486 // Check whether it's an integral type. If so, it's not an iterator.
487 typedef typename std::__is_integer<_InputIterator>::__type _Integral;
488 _M_assign_dispatch(__first, __last, _Integral());
491 #ifdef __GXX_EXPERIMENTAL_CXX0X__
493 * @brief Assigns an initializer list to a %vector.
494 * @param __l An initializer_list.
496 * This function fills a %vector with copies of the elements in the
497 * initializer list @a __l.
499 * Note that the assignment completely changes the %vector and
500 * that the resulting %vector's size is the same as the number
501 * of elements assigned. Old data may be lost.
504 assign(initializer_list<value_type> __l)
505 { this->assign(__l.begin(), __l.end()); }
508 /// Get a copy of the memory allocation object.
509 using _Base::get_allocator;
513 * Returns a read/write iterator that points to the first
514 * element in the %vector. Iteration is done in ordinary
518 begin() _GLIBCXX_NOEXCEPT
519 { return iterator(this->_M_impl._M_start); }
522 * Returns a read-only (constant) iterator that points to the
523 * first element in the %vector. Iteration is done in ordinary
527 begin() const _GLIBCXX_NOEXCEPT
528 { return const_iterator(this->_M_impl._M_start); }
531 * Returns a read/write iterator that points one past the last
532 * element in the %vector. Iteration is done in ordinary
536 end() _GLIBCXX_NOEXCEPT
537 { return iterator(this->_M_impl._M_finish); }
540 * Returns a read-only (constant) iterator that points one past
541 * the last element in the %vector. Iteration is done in
542 * ordinary element order.
545 end() const _GLIBCXX_NOEXCEPT
546 { return const_iterator(this->_M_impl._M_finish); }
549 * Returns a read/write reverse iterator that points to the
550 * last element in the %vector. Iteration is done in reverse
554 rbegin() _GLIBCXX_NOEXCEPT
555 { return reverse_iterator(end()); }
558 * Returns a read-only (constant) reverse iterator that points
559 * to the last element in the %vector. Iteration is done in
560 * reverse element order.
562 const_reverse_iterator
563 rbegin() const _GLIBCXX_NOEXCEPT
564 { return const_reverse_iterator(end()); }
567 * Returns a read/write reverse iterator that points to one
568 * before the first element in the %vector. Iteration is done
569 * in reverse element order.
572 rend() _GLIBCXX_NOEXCEPT
573 { return reverse_iterator(begin()); }
576 * Returns a read-only (constant) reverse iterator that points
577 * to one before the first element in the %vector. Iteration
578 * is done in reverse element order.
580 const_reverse_iterator
581 rend() const _GLIBCXX_NOEXCEPT
582 { return const_reverse_iterator(begin()); }
584 #ifdef __GXX_EXPERIMENTAL_CXX0X__
586 * Returns a read-only (constant) iterator that points to the
587 * first element in the %vector. Iteration is done in ordinary
591 cbegin() const noexcept
592 { return const_iterator(this->_M_impl._M_start); }
595 * Returns a read-only (constant) iterator that points one past
596 * the last element in the %vector. Iteration is done in
597 * ordinary element order.
600 cend() const noexcept
601 { return const_iterator(this->_M_impl._M_finish); }
604 * Returns a read-only (constant) reverse iterator that points
605 * to the last element in the %vector. Iteration is done in
606 * reverse element order.
608 const_reverse_iterator
609 crbegin() const noexcept
610 { return const_reverse_iterator(end()); }
613 * Returns a read-only (constant) reverse iterator that points
614 * to one before the first element in the %vector. Iteration
615 * is done in reverse element order.
617 const_reverse_iterator
618 crend() const noexcept
619 { return const_reverse_iterator(begin()); }
622 // [23.2.4.2] capacity
623 /** Returns the number of elements in the %vector. */
625 size() const _GLIBCXX_NOEXCEPT
626 { return size_type(this->_M_impl._M_finish - this->_M_impl._M_start); }
628 /** Returns the size() of the largest possible %vector. */
630 max_size() const _GLIBCXX_NOEXCEPT
631 { return _Alloc_traits::max_size(_M_get_Tp_allocator()); }
633 #ifdef __GXX_EXPERIMENTAL_CXX0X__
635 * @brief Resizes the %vector to the specified number of elements.
636 * @param __new_size Number of elements the %vector should contain.
638 * This function will %resize the %vector to the specified
639 * number of elements. If the number is smaller than the
640 * %vector's current size the %vector is truncated, otherwise
641 * default constructed elements are appended.
644 resize(size_type __new_size)
646 if (__new_size > size())
647 _M_default_append(__new_size - size());
648 else if (__new_size < size())
649 _M_erase_at_end(this->_M_impl._M_start + __new_size);
653 * @brief Resizes the %vector to the specified number of elements.
654 * @param __new_size Number of elements the %vector should contain.
655 * @param __x Data with which new elements should be populated.
657 * This function will %resize the %vector to the specified
658 * number of elements. If the number is smaller than the
659 * %vector's current size the %vector is truncated, otherwise
660 * the %vector is extended and new elements are populated with
664 resize(size_type __new_size, const value_type& __x)
666 if (__new_size > size())
667 insert(end(), __new_size - size(), __x);
668 else if (__new_size < size())
669 _M_erase_at_end(this->_M_impl._M_start + __new_size);
673 * @brief Resizes the %vector to the specified number of elements.
674 * @param __new_size Number of elements the %vector should contain.
675 * @param __x Data with which new elements should be populated.
677 * This function will %resize the %vector to the specified
678 * number of elements. If the number is smaller than the
679 * %vector's current size the %vector is truncated, otherwise
680 * the %vector is extended and new elements are populated with
684 resize(size_type __new_size, value_type __x = value_type())
686 if (__new_size > size())
687 insert(end(), __new_size - size(), __x);
688 else if (__new_size < size())
689 _M_erase_at_end(this->_M_impl._M_start + __new_size);
693 #ifdef __GXX_EXPERIMENTAL_CXX0X__
694 /** A non-binding request to reduce capacity() to size(). */
697 { _M_shrink_to_fit(); }
701 * Returns the total number of elements that the %vector can
702 * hold before needing to allocate more memory.
705 capacity() const _GLIBCXX_NOEXCEPT
706 { return size_type(this->_M_impl._M_end_of_storage
707 - this->_M_impl._M_start); }
710 * Returns true if the %vector is empty. (Thus begin() would
714 empty() const _GLIBCXX_NOEXCEPT
715 { return begin() == end(); }
718 * @brief Attempt to preallocate enough memory for specified number of
720 * @param __n Number of elements required.
721 * @throw std::length_error If @a n exceeds @c max_size().
723 * This function attempts to reserve enough memory for the
724 * %vector to hold the specified number of elements. If the
725 * number requested is more than max_size(), length_error is
728 * The advantage of this function is that if optimal code is a
729 * necessity and the user can determine the number of elements
730 * that will be required, the user can reserve the memory in
731 * %advance, and thus prevent a possible reallocation of memory
732 * and copying of %vector data.
735 reserve(size_type __n);
739 * @brief Subscript access to the data contained in the %vector.
740 * @param __n The index of the element for which data should be
742 * @return Read/write reference to data.
744 * This operator allows for easy, array-style, data access.
745 * Note that data access with this operator is unchecked and
746 * out_of_range lookups are not defined. (For checked lookups
750 operator[](size_type __n)
751 { return *(this->_M_impl._M_start + __n); }
754 * @brief Subscript access to the data contained in the %vector.
755 * @param __n The index of the element for which data should be
757 * @return Read-only (constant) reference to data.
759 * This operator allows for easy, array-style, data access.
760 * Note that data access with this operator is unchecked and
761 * out_of_range lookups are not defined. (For checked lookups
765 operator[](size_type __n) const
766 { return *(this->_M_impl._M_start + __n); }
769 /// Safety check used only from at().
771 _M_range_check(size_type __n) const
773 if (__n >= this->size())
774 __throw_out_of_range(__N("vector::_M_range_check"));
779 * @brief Provides access to the data contained in the %vector.
780 * @param __n The index of the element for which data should be
782 * @return Read/write reference to data.
783 * @throw std::out_of_range If @a __n is an invalid index.
785 * This function provides for safer data access. The parameter
786 * is first checked that it is in the range of the vector. The
787 * function throws out_of_range if the check fails.
797 * @brief Provides access to the data contained in the %vector.
798 * @param __n The index of the element for which data should be
800 * @return Read-only (constant) reference to data.
801 * @throw std::out_of_range If @a __n is an invalid index.
803 * This function provides for safer data access. The parameter
804 * is first checked that it is in the range of the vector. The
805 * function throws out_of_range if the check fails.
808 at(size_type __n) const
815 * Returns a read/write reference to the data at the first
816 * element of the %vector.
823 * Returns a read-only (constant) reference to the data at the first
824 * element of the %vector.
831 * Returns a read/write reference to the data at the last
832 * element of the %vector.
836 { return *(end() - 1); }
839 * Returns a read-only (constant) reference to the data at the
840 * last element of the %vector.
844 { return *(end() - 1); }
846 // _GLIBCXX_RESOLVE_LIB_DEFECTS
847 // DR 464. Suggestion for new member functions in standard containers.
850 * Returns a pointer such that [data(), data() + size()) is a valid
851 * range. For a non-empty %vector, data() == &front().
853 #ifdef __GXX_EXPERIMENTAL_CXX0X__
858 data() _GLIBCXX_NOEXCEPT
859 { return std::__addressof(front()); }
861 #ifdef __GXX_EXPERIMENTAL_CXX0X__
866 data() const _GLIBCXX_NOEXCEPT
867 { return std::__addressof(front()); }
869 // [23.2.4.3] modifiers
871 * @brief Add data to the end of the %vector.
872 * @param __x Data to be added.
874 * This is a typical stack operation. The function creates an
875 * element at the end of the %vector and assigns the given data
876 * to it. Due to the nature of a %vector this operation can be
877 * done in constant time if the %vector has preallocated space
881 push_back(const value_type& __x)
883 if (this->_M_impl._M_finish != this->_M_impl._M_end_of_storage)
885 _Alloc_traits::construct(this->_M_impl, this->_M_impl._M_finish,
887 ++this->_M_impl._M_finish;
890 #ifdef __GXX_EXPERIMENTAL_CXX0X__
891 _M_emplace_back_aux(__x);
893 _M_insert_aux(end(), __x);
897 #ifdef __GXX_EXPERIMENTAL_CXX0X__
899 push_back(value_type&& __x)
900 { emplace_back(std::move(__x)); }
902 template<typename... _Args>
904 emplace_back(_Args&&... __args);
908 * @brief Removes last element.
910 * This is a typical stack operation. It shrinks the %vector by one.
912 * Note that no data is returned, and if the last element's
913 * data is needed, it should be retrieved before pop_back() is
919 --this->_M_impl._M_finish;
920 _Alloc_traits::destroy(this->_M_impl, this->_M_impl._M_finish);
923 #ifdef __GXX_EXPERIMENTAL_CXX0X__
925 * @brief Inserts an object in %vector before specified iterator.
926 * @param __position An iterator into the %vector.
927 * @param __args Arguments.
928 * @return An iterator that points to the inserted data.
930 * This function will insert an object of type T constructed
931 * with T(std::forward<Args>(args)...) before the specified location.
932 * Note that this kind of operation could be expensive for a %vector
933 * and if it is frequently used the user should consider using
936 template<typename... _Args>
938 emplace(iterator __position, _Args&&... __args);
942 * @brief Inserts given value into %vector before specified iterator.
943 * @param __position An iterator into the %vector.
944 * @param __x Data to be inserted.
945 * @return An iterator that points to the inserted data.
947 * This function will insert a copy of the given value before
948 * the specified location. Note that this kind of operation
949 * could be expensive for a %vector and if it is frequently
950 * used the user should consider using std::list.
953 insert(iterator __position, const value_type& __x);
955 #ifdef __GXX_EXPERIMENTAL_CXX0X__
957 * @brief Inserts given rvalue into %vector before specified iterator.
958 * @param __position An iterator into the %vector.
959 * @param __x Data to be inserted.
960 * @return An iterator that points to the inserted data.
962 * This function will insert a copy of the given rvalue before
963 * the specified location. Note that this kind of operation
964 * could be expensive for a %vector and if it is frequently
965 * used the user should consider using std::list.
968 insert(iterator __position, value_type&& __x)
969 { return emplace(__position, std::move(__x)); }
972 * @brief Inserts an initializer_list into the %vector.
973 * @param __position An iterator into the %vector.
974 * @param __l An initializer_list.
976 * This function will insert copies of the data in the
977 * initializer_list @a l into the %vector before the location
978 * specified by @a position.
980 * Note that this kind of operation could be expensive for a
981 * %vector and if it is frequently used the user should
982 * consider using std::list.
985 insert(iterator __position, initializer_list<value_type> __l)
986 { this->insert(__position, __l.begin(), __l.end()); }
990 * @brief Inserts a number of copies of given data into the %vector.
991 * @param __position An iterator into the %vector.
992 * @param __n Number of elements to be inserted.
993 * @param __x Data to be inserted.
995 * This function will insert a specified number of copies of
996 * the given data before the location specified by @a position.
998 * Note that this kind of operation could be expensive for a
999 * %vector and if it is frequently used the user should
1000 * consider using std::list.
1003 insert(iterator __position, size_type __n, const value_type& __x)
1004 { _M_fill_insert(__position, __n, __x); }
1007 * @brief Inserts a range into the %vector.
1008 * @param __position An iterator into the %vector.
1009 * @param __first An input iterator.
1010 * @param __last An input iterator.
1012 * This function will insert copies of the data in the range
1013 * [__first,__last) into the %vector before the location specified
1016 * Note that this kind of operation could be expensive for a
1017 * %vector and if it is frequently used the user should
1018 * consider using std::list.
1020 template<typename _InputIterator>
1022 insert(iterator __position, _InputIterator __first,
1023 _InputIterator __last)
1025 // Check whether it's an integral type. If so, it's not an iterator.
1026 typedef typename std::__is_integer<_InputIterator>::__type _Integral;
1027 _M_insert_dispatch(__position, __first, __last, _Integral());
1031 * @brief Remove element at given position.
1032 * @param __position Iterator pointing to element to be erased.
1033 * @return An iterator pointing to the next element (or end()).
1035 * This function will erase the element at the given position and thus
1036 * shorten the %vector by one.
1038 * Note This operation could be expensive and if it is
1039 * frequently used the user should consider using std::list.
1040 * The user is also cautioned that this function only erases
1041 * the element, and that if the element is itself a pointer,
1042 * the pointed-to memory is not touched in any way. Managing
1043 * the pointer is the user's responsibility.
1046 erase(iterator __position);
1049 * @brief Remove a range of elements.
1050 * @param __first Iterator pointing to the first element to be erased.
1051 * @param __last Iterator pointing to one past the last element to be
1053 * @return An iterator pointing to the element pointed to by @a __last
1054 * prior to erasing (or end()).
1056 * This function will erase the elements in the range
1057 * [__first,__last) and shorten the %vector accordingly.
1059 * Note This operation could be expensive and if it is
1060 * frequently used the user should consider using std::list.
1061 * The user is also cautioned that this function only erases
1062 * the elements, and that if the elements themselves are
1063 * pointers, the pointed-to memory is not touched in any way.
1064 * Managing the pointer is the user's responsibility.
1067 erase(iterator __first, iterator __last);
1070 * @brief Swaps data with another %vector.
1071 * @param __x A %vector of the same element and allocator types.
1073 * This exchanges the elements between two vectors in constant time.
1074 * (Three pointers, so it should be quite fast.)
1075 * Note that the global std::swap() function is specialized such that
1076 * std::swap(v1,v2) will feed to this function.
1080 #ifdef __GXX_EXPERIMENTAL_CXX0X__
1081 noexcept(_Alloc_traits::_S_nothrow_swap())
1084 this->_M_impl._M_swap_data(__x._M_impl);
1085 _Alloc_traits::_S_on_swap(_M_get_Tp_allocator(),
1086 __x._M_get_Tp_allocator());
1090 * Erases all the elements. Note that this function only erases the
1091 * elements, and that if the elements themselves are pointers, the
1092 * pointed-to memory is not touched in any way. Managing the pointer is
1093 * the user's responsibility.
1096 clear() _GLIBCXX_NOEXCEPT
1097 { _M_erase_at_end(this->_M_impl._M_start); }
1101 * Memory expansion handler. Uses the member allocation function to
1102 * obtain @a n bytes of memory, and then copies [first,last) into it.
1104 template<typename _ForwardIterator>
1106 _M_allocate_and_copy(size_type __n,
1107 _ForwardIterator __first, _ForwardIterator __last)
1109 pointer __result = this->_M_allocate(__n);
1112 std::__uninitialized_copy_a(__first, __last, __result,
1113 _M_get_Tp_allocator());
1118 _M_deallocate(__result, __n);
1119 __throw_exception_again;
1124 // Internal constructor functions follow.
1126 // Called by the range constructor to implement [23.1.1]/9
1128 // _GLIBCXX_RESOLVE_LIB_DEFECTS
1129 // 438. Ambiguity in the "do the right thing" clause
1130 template<typename _Integer>
1132 _M_initialize_dispatch(_Integer __n, _Integer __value, __true_type)
1134 this->_M_impl._M_start = _M_allocate(static_cast<size_type>(__n));
1135 this->_M_impl._M_end_of_storage =
1136 this->_M_impl._M_start + static_cast<size_type>(__n);
1137 _M_fill_initialize(static_cast<size_type>(__n), __value);
1140 // Called by the range constructor to implement [23.1.1]/9
1141 template<typename _InputIterator>
1143 _M_initialize_dispatch(_InputIterator __first, _InputIterator __last,
1146 typedef typename std::iterator_traits<_InputIterator>::
1147 iterator_category _IterCategory;
1148 _M_range_initialize(__first, __last, _IterCategory());
1151 // Called by the second initialize_dispatch above
1152 template<typename _InputIterator>
1154 _M_range_initialize(_InputIterator __first,
1155 _InputIterator __last, std::input_iterator_tag)
1157 for (; __first != __last; ++__first)
1158 push_back(*__first);
1161 // Called by the second initialize_dispatch above
1162 template<typename _ForwardIterator>
1164 _M_range_initialize(_ForwardIterator __first,
1165 _ForwardIterator __last, std::forward_iterator_tag)
1167 const size_type __n = std::distance(__first, __last);
1168 this->_M_impl._M_start = this->_M_allocate(__n);
1169 this->_M_impl._M_end_of_storage = this->_M_impl._M_start + __n;
1170 this->_M_impl._M_finish =
1171 std::__uninitialized_copy_a(__first, __last,
1172 this->_M_impl._M_start,
1173 _M_get_Tp_allocator());
1176 // Called by the first initialize_dispatch above and by the
1177 // vector(n,value,a) constructor.
1179 _M_fill_initialize(size_type __n, const value_type& __value)
1181 std::__uninitialized_fill_n_a(this->_M_impl._M_start, __n, __value,
1182 _M_get_Tp_allocator());
1183 this->_M_impl._M_finish = this->_M_impl._M_end_of_storage;
1186 #ifdef __GXX_EXPERIMENTAL_CXX0X__
1187 // Called by the vector(n) constructor.
1189 _M_default_initialize(size_type __n)
1191 std::__uninitialized_default_n_a(this->_M_impl._M_start, __n,
1192 _M_get_Tp_allocator());
1193 this->_M_impl._M_finish = this->_M_impl._M_end_of_storage;
1197 // Internal assign functions follow. The *_aux functions do the actual
1198 // assignment work for the range versions.
1200 // Called by the range assign to implement [23.1.1]/9
1202 // _GLIBCXX_RESOLVE_LIB_DEFECTS
1203 // 438. Ambiguity in the "do the right thing" clause
1204 template<typename _Integer>
1206 _M_assign_dispatch(_Integer __n, _Integer __val, __true_type)
1207 { _M_fill_assign(__n, __val); }
1209 // Called by the range assign to implement [23.1.1]/9
1210 template<typename _InputIterator>
1212 _M_assign_dispatch(_InputIterator __first, _InputIterator __last,
1215 typedef typename std::iterator_traits<_InputIterator>::
1216 iterator_category _IterCategory;
1217 _M_assign_aux(__first, __last, _IterCategory());
1220 // Called by the second assign_dispatch above
1221 template<typename _InputIterator>
1223 _M_assign_aux(_InputIterator __first, _InputIterator __last,
1224 std::input_iterator_tag);
1226 // Called by the second assign_dispatch above
1227 template<typename _ForwardIterator>
1229 _M_assign_aux(_ForwardIterator __first, _ForwardIterator __last,
1230 std::forward_iterator_tag);
1232 // Called by assign(n,t), and the range assign when it turns out
1233 // to be the same thing.
1235 _M_fill_assign(size_type __n, const value_type& __val);
1238 // Internal insert functions follow.
1240 // Called by the range insert to implement [23.1.1]/9
1242 // _GLIBCXX_RESOLVE_LIB_DEFECTS
1243 // 438. Ambiguity in the "do the right thing" clause
1244 template<typename _Integer>
1246 _M_insert_dispatch(iterator __pos, _Integer __n, _Integer __val,
1248 { _M_fill_insert(__pos, __n, __val); }
1250 // Called by the range insert to implement [23.1.1]/9
1251 template<typename _InputIterator>
1253 _M_insert_dispatch(iterator __pos, _InputIterator __first,
1254 _InputIterator __last, __false_type)
1256 typedef typename std::iterator_traits<_InputIterator>::
1257 iterator_category _IterCategory;
1258 _M_range_insert(__pos, __first, __last, _IterCategory());
1261 // Called by the second insert_dispatch above
1262 template<typename _InputIterator>
1264 _M_range_insert(iterator __pos, _InputIterator __first,
1265 _InputIterator __last, std::input_iterator_tag);
1267 // Called by the second insert_dispatch above
1268 template<typename _ForwardIterator>
1270 _M_range_insert(iterator __pos, _ForwardIterator __first,
1271 _ForwardIterator __last, std::forward_iterator_tag);
1273 // Called by insert(p,n,x), and the range insert when it turns out to be
1276 _M_fill_insert(iterator __pos, size_type __n, const value_type& __x);
1278 #ifdef __GXX_EXPERIMENTAL_CXX0X__
1279 // Called by resize(n).
1281 _M_default_append(size_type __n);
1287 // Called by insert(p,x)
1288 #ifndef __GXX_EXPERIMENTAL_CXX0X__
1290 _M_insert_aux(iterator __position, const value_type& __x);
1292 template<typename... _Args>
1294 _M_insert_aux(iterator __position, _Args&&... __args);
1296 template<typename... _Args>
1298 _M_emplace_back_aux(_Args&&... __args);
1301 // Called by the latter.
1303 _M_check_len(size_type __n, const char* __s) const
1305 if (max_size() - size() < __n)
1306 __throw_length_error(__N(__s));
1308 const size_type __len = size() + std::max(size(), __n);
1309 return (__len < size() || __len > max_size()) ? max_size() : __len;
1312 // Internal erase functions follow.
1314 // Called by erase(q1,q2), clear(), resize(), _M_fill_assign,
1317 _M_erase_at_end(pointer __pos)
1319 std::_Destroy(__pos, this->_M_impl._M_finish, _M_get_Tp_allocator());
1320 this->_M_impl._M_finish = __pos;
1323 #ifdef __GXX_EXPERIMENTAL_CXX0X__
1325 // Constant-time move assignment when source object's memory can be
1326 // moved, either because the source's allocator will move too
1327 // or because the allocators are equal.
1329 _M_move_assign(vector&& __x, std::true_type) noexcept
1331 const vector __tmp(std::move(*this));
1332 this->_M_impl._M_swap_data(__x._M_impl);
1333 if (_Alloc_traits::_S_propagate_on_move_assign())
1334 std::__alloc_on_move(_M_get_Tp_allocator(),
1335 __x._M_get_Tp_allocator());
1338 // Do move assignment when it might not be possible to move source
1339 // object's memory, resulting in a linear-time operation.
1341 _M_move_assign(vector&& __x, std::false_type)
1343 if (__x._M_get_Tp_allocator() == this->_M_get_Tp_allocator())
1344 _M_move_assign(std::move(__x), std::true_type());
1347 // The rvalue's allocator cannot be moved and is not equal,
1348 // so we need to individually move each element.
1349 this->assign(std::__make_move_if_noexcept_iterator(__x.begin()),
1350 std::__make_move_if_noexcept_iterator(__x.end()));
1359 * @brief Vector equality comparison.
1360 * @param __x A %vector.
1361 * @param __y A %vector of the same type as @a __x.
1362 * @return True iff the size and elements of the vectors are equal.
1364 * This is an equivalence relation. It is linear in the size of the
1365 * vectors. Vectors are considered equivalent if their sizes are equal,
1366 * and if corresponding elements compare equal.
1368 template<typename _Tp, typename _Alloc>
1370 operator==(const vector<_Tp, _Alloc>& __x, const vector<_Tp, _Alloc>& __y)
1371 { return (__x.size() == __y.size()
1372 && std::equal(__x.begin(), __x.end(), __y.begin())); }
1375 * @brief Vector ordering relation.
1376 * @param __x A %vector.
1377 * @param __y A %vector of the same type as @a __x.
1378 * @return True iff @a __x is lexicographically less than @a __y.
1380 * This is a total ordering relation. It is linear in the size of the
1381 * vectors. The elements must be comparable with @c <.
1383 * See std::lexicographical_compare() for how the determination is made.
1385 template<typename _Tp, typename _Alloc>
1387 operator<(const vector<_Tp, _Alloc>& __x, const vector<_Tp, _Alloc>& __y)
1388 { return std::lexicographical_compare(__x.begin(), __x.end(),
1389 __y.begin(), __y.end()); }
1391 /// Based on operator==
1392 template<typename _Tp, typename _Alloc>
1394 operator!=(const vector<_Tp, _Alloc>& __x, const vector<_Tp, _Alloc>& __y)
1395 { return !(__x == __y); }
1397 /// Based on operator<
1398 template<typename _Tp, typename _Alloc>
1400 operator>(const vector<_Tp, _Alloc>& __x, const vector<_Tp, _Alloc>& __y)
1401 { return __y < __x; }
1403 /// Based on operator<
1404 template<typename _Tp, typename _Alloc>
1406 operator<=(const vector<_Tp, _Alloc>& __x, const vector<_Tp, _Alloc>& __y)
1407 { return !(__y < __x); }
1409 /// Based on operator<
1410 template<typename _Tp, typename _Alloc>
1412 operator>=(const vector<_Tp, _Alloc>& __x, const vector<_Tp, _Alloc>& __y)
1413 { return !(__x < __y); }
1415 /// See std::vector::swap().
1416 template<typename _Tp, typename _Alloc>
1418 swap(vector<_Tp, _Alloc>& __x, vector<_Tp, _Alloc>& __y)
1421 _GLIBCXX_END_NAMESPACE_CONTAINER
1424 #endif /* _STL_VECTOR_H */