1 // Vector implementation -*- C++ -*-
3 // Copyright (C) 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008, 2009, 2010
4 // 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 stl_vector.h
53 * This is an internal header file, included by other library headers.
54 * You should not attempt to use it directly.
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 #include <initializer_list>
65 _GLIBCXX_BEGIN_NESTED_NAMESPACE(std, _GLIBCXX_STD_D)
67 /// See bits/stl_deque.h's _Deque_base for an explanation.
68 template<typename _Tp, typename _Alloc>
71 typedef typename _Alloc::template rebind<_Tp>::other _Tp_alloc_type;
74 : public _Tp_alloc_type
76 typename _Tp_alloc_type::pointer _M_start;
77 typename _Tp_alloc_type::pointer _M_finish;
78 typename _Tp_alloc_type::pointer _M_end_of_storage;
81 : _Tp_alloc_type(), _M_start(0), _M_finish(0), _M_end_of_storage(0)
84 _Vector_impl(_Tp_alloc_type const& __a)
85 : _Tp_alloc_type(__a), _M_start(0), _M_finish(0), _M_end_of_storage(0)
90 typedef _Alloc allocator_type;
94 { return *static_cast<_Tp_alloc_type*>(&this->_M_impl); }
97 _M_get_Tp_allocator() const
98 { return *static_cast<const _Tp_alloc_type*>(&this->_M_impl); }
101 get_allocator() const
102 { return allocator_type(_M_get_Tp_allocator()); }
107 _Vector_base(const allocator_type& __a)
110 _Vector_base(size_t __n, const allocator_type& __a)
113 this->_M_impl._M_start = this->_M_allocate(__n);
114 this->_M_impl._M_finish = this->_M_impl._M_start;
115 this->_M_impl._M_end_of_storage = this->_M_impl._M_start + __n;
118 #ifdef __GXX_EXPERIMENTAL_CXX0X__
119 _Vector_base(_Vector_base&& __x)
120 : _M_impl(__x._M_get_Tp_allocator())
122 this->_M_impl._M_start = __x._M_impl._M_start;
123 this->_M_impl._M_finish = __x._M_impl._M_finish;
124 this->_M_impl._M_end_of_storage = __x._M_impl._M_end_of_storage;
125 __x._M_impl._M_start = 0;
126 __x._M_impl._M_finish = 0;
127 __x._M_impl._M_end_of_storage = 0;
132 { _M_deallocate(this->_M_impl._M_start, this->_M_impl._M_end_of_storage
133 - this->_M_impl._M_start); }
136 _Vector_impl _M_impl;
138 typename _Tp_alloc_type::pointer
139 _M_allocate(size_t __n)
140 { return __n != 0 ? _M_impl.allocate(__n) : 0; }
143 _M_deallocate(typename _Tp_alloc_type::pointer __p, size_t __n)
146 _M_impl.deallocate(__p, __n);
152 * @brief A standard container which offers fixed time access to
153 * individual elements in any order.
157 * Meets the requirements of a <a href="tables.html#65">container</a>, a
158 * <a href="tables.html#66">reversible container</a>, and a
159 * <a href="tables.html#67">sequence</a>, including the
160 * <a href="tables.html#68">optional sequence requirements</a> with the
161 * %exception of @c push_front and @c pop_front.
163 * In some terminology a %vector can be described as a dynamic
164 * C-style array, it offers fast and efficient access to individual
165 * elements in any order and saves the user from worrying about
166 * memory and size allocation. Subscripting ( @c [] ) access is
167 * also provided as with C-style arrays.
169 template<typename _Tp, typename _Alloc = std::allocator<_Tp> >
170 class vector : protected _Vector_base<_Tp, _Alloc>
172 // Concept requirements.
173 typedef typename _Alloc::value_type _Alloc_value_type;
174 __glibcxx_class_requires(_Tp, _SGIAssignableConcept)
175 __glibcxx_class_requires2(_Tp, _Alloc_value_type, _SameTypeConcept)
177 typedef _Vector_base<_Tp, _Alloc> _Base;
178 typedef typename _Base::_Tp_alloc_type _Tp_alloc_type;
181 typedef _Tp value_type;
182 typedef typename _Tp_alloc_type::pointer pointer;
183 typedef typename _Tp_alloc_type::const_pointer const_pointer;
184 typedef typename _Tp_alloc_type::reference reference;
185 typedef typename _Tp_alloc_type::const_reference const_reference;
186 typedef __gnu_cxx::__normal_iterator<pointer, vector> iterator;
187 typedef __gnu_cxx::__normal_iterator<const_pointer, vector>
189 typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
190 typedef std::reverse_iterator<iterator> reverse_iterator;
191 typedef size_t size_type;
192 typedef ptrdiff_t difference_type;
193 typedef _Alloc allocator_type;
196 using _Base::_M_allocate;
197 using _Base::_M_deallocate;
198 using _Base::_M_impl;
199 using _Base::_M_get_Tp_allocator;
202 // [23.2.4.1] construct/copy/destroy
203 // (assign() and get_allocator() are also listed in this section)
205 * @brief Default constructor creates no elements.
211 * @brief Creates a %vector with no elements.
212 * @param a An allocator object.
215 vector(const allocator_type& __a)
219 * @brief Creates a %vector with copies of an exemplar element.
220 * @param n The number of elements to initially create.
221 * @param value An element to copy.
222 * @param a An allocator.
224 * This constructor fills the %vector with @a n copies of @a value.
227 vector(size_type __n, const value_type& __value = value_type(),
228 const allocator_type& __a = allocator_type())
230 { _M_fill_initialize(__n, __value); }
233 * @brief %Vector copy constructor.
234 * @param x A %vector of identical element and allocator types.
236 * The newly-created %vector uses a copy of the allocation
237 * object used by @a x. All the elements of @a x are copied,
238 * but any extra memory in
239 * @a x (for fast expansion) will not be copied.
241 vector(const vector& __x)
242 : _Base(__x.size(), __x._M_get_Tp_allocator())
243 { this->_M_impl._M_finish =
244 std::__uninitialized_copy_a(__x.begin(), __x.end(),
245 this->_M_impl._M_start,
246 _M_get_Tp_allocator());
249 #ifdef __GXX_EXPERIMENTAL_CXX0X__
251 * @brief %Vector move constructor.
252 * @param x A %vector of identical element and allocator types.
254 * The newly-created %vector contains the exact contents of @a x.
255 * The contents of @a x are a valid, but unspecified %vector.
258 : _Base(std::forward<_Base>(__x)) { }
261 * @brief Builds a %vector from an initializer list.
262 * @param l An initializer_list.
263 * @param a An allocator.
265 * Create a %vector consisting of copies of the elements in the
266 * initializer_list @a l.
268 * This will call the element type's copy constructor N times
269 * (where N is @a l.size()) and do no memory reallocation.
271 vector(initializer_list<value_type> __l,
272 const allocator_type& __a = allocator_type())
275 _M_range_initialize(__l.begin(), __l.end(),
276 random_access_iterator_tag());
281 * @brief Builds a %vector from a range.
282 * @param first An input iterator.
283 * @param last An input iterator.
284 * @param a An allocator.
286 * Create a %vector consisting of copies of the elements from
289 * If the iterators are forward, bidirectional, or
290 * random-access, then this will call the elements' copy
291 * constructor N times (where N is distance(first,last)) and do
292 * no memory reallocation. But if only input iterators are
293 * used, then this will do at most 2N calls to the copy
294 * constructor, and logN memory reallocations.
296 template<typename _InputIterator>
297 vector(_InputIterator __first, _InputIterator __last,
298 const allocator_type& __a = allocator_type())
301 // Check whether it's an integral type. If so, it's not an iterator.
302 typedef typename std::__is_integer<_InputIterator>::__type _Integral;
303 _M_initialize_dispatch(__first, __last, _Integral());
307 * The dtor only erases the elements, and note that if the
308 * elements themselves are pointers, the pointed-to memory is
309 * not touched in any way. Managing the pointer is the user's
313 { std::_Destroy(this->_M_impl._M_start, this->_M_impl._M_finish,
314 _M_get_Tp_allocator()); }
317 * @brief %Vector assignment operator.
318 * @param x A %vector of identical element and allocator types.
320 * All the elements of @a x are copied, but any extra memory in
321 * @a x (for fast expansion) will not be copied. Unlike the
322 * copy constructor, the allocator object is not copied.
325 operator=(const vector& __x);
327 #ifdef __GXX_EXPERIMENTAL_CXX0X__
329 * @brief %Vector move assignment operator.
330 * @param x A %vector of identical element and allocator types.
332 * The contents of @a x are moved into this %vector (without copying).
333 * @a x is a valid, but unspecified %vector.
336 operator=(vector&& __x)
346 * @brief %Vector list assignment operator.
347 * @param l An initializer_list.
349 * This function fills a %vector with copies of the elements in the
350 * initializer list @a l.
352 * Note that the assignment completely changes the %vector and
353 * that the resulting %vector's size is the same as the number
354 * of elements assigned. Old data may be lost.
357 operator=(initializer_list<value_type> __l)
359 this->assign(__l.begin(), __l.end());
365 * @brief Assigns a given value to a %vector.
366 * @param n Number of elements to be assigned.
367 * @param val Value to be assigned.
369 * This function fills a %vector with @a n copies of the given
370 * value. Note that the assignment completely changes the
371 * %vector and that the resulting %vector's size is the same as
372 * the number of elements assigned. Old data may be lost.
375 assign(size_type __n, const value_type& __val)
376 { _M_fill_assign(__n, __val); }
379 * @brief Assigns a range to a %vector.
380 * @param first An input iterator.
381 * @param last An input iterator.
383 * This function fills a %vector with copies of the elements in the
384 * range [first,last).
386 * Note that the assignment completely changes the %vector and
387 * that the resulting %vector's size is the same as the number
388 * of elements assigned. Old data may be lost.
390 template<typename _InputIterator>
392 assign(_InputIterator __first, _InputIterator __last)
394 // Check whether it's an integral type. If so, it's not an iterator.
395 typedef typename std::__is_integer<_InputIterator>::__type _Integral;
396 _M_assign_dispatch(__first, __last, _Integral());
399 #ifdef __GXX_EXPERIMENTAL_CXX0X__
401 * @brief Assigns an initializer list to a %vector.
402 * @param l An initializer_list.
404 * This function fills a %vector with copies of the elements in the
405 * initializer list @a l.
407 * Note that the assignment completely changes the %vector and
408 * that the resulting %vector's size is the same as the number
409 * of elements assigned. Old data may be lost.
412 assign(initializer_list<value_type> __l)
413 { this->assign(__l.begin(), __l.end()); }
416 /// Get a copy of the memory allocation object.
417 using _Base::get_allocator;
421 * Returns a read/write iterator that points to the first
422 * element in the %vector. Iteration is done in ordinary
427 { return iterator(this->_M_impl._M_start); }
430 * Returns a read-only (constant) iterator that points to the
431 * first element in the %vector. Iteration is done in ordinary
436 { return const_iterator(this->_M_impl._M_start); }
439 * Returns a read/write iterator that points one past the last
440 * element in the %vector. Iteration is done in ordinary
445 { return iterator(this->_M_impl._M_finish); }
448 * Returns a read-only (constant) iterator that points one past
449 * the last element in the %vector. Iteration is done in
450 * ordinary element order.
454 { return const_iterator(this->_M_impl._M_finish); }
457 * Returns a read/write reverse iterator that points to the
458 * last element in the %vector. Iteration is done in reverse
463 { return reverse_iterator(end()); }
466 * Returns a read-only (constant) reverse iterator that points
467 * to the last element in the %vector. Iteration is done in
468 * reverse element order.
470 const_reverse_iterator
472 { return const_reverse_iterator(end()); }
475 * Returns a read/write reverse iterator that points to one
476 * before the first element in the %vector. Iteration is done
477 * in reverse element order.
481 { return reverse_iterator(begin()); }
484 * Returns a read-only (constant) reverse iterator that points
485 * to one before the first element in the %vector. Iteration
486 * is done in reverse element order.
488 const_reverse_iterator
490 { return const_reverse_iterator(begin()); }
492 #ifdef __GXX_EXPERIMENTAL_CXX0X__
494 * Returns a read-only (constant) iterator that points to the
495 * first element in the %vector. Iteration is done in ordinary
500 { return const_iterator(this->_M_impl._M_start); }
503 * Returns a read-only (constant) iterator that points one past
504 * the last element in the %vector. Iteration is done in
505 * ordinary element order.
509 { return const_iterator(this->_M_impl._M_finish); }
512 * Returns a read-only (constant) reverse iterator that points
513 * to the last element in the %vector. Iteration is done in
514 * reverse element order.
516 const_reverse_iterator
518 { return const_reverse_iterator(end()); }
521 * Returns a read-only (constant) reverse iterator that points
522 * to one before the first element in the %vector. Iteration
523 * is done in reverse element order.
525 const_reverse_iterator
527 { return const_reverse_iterator(begin()); }
530 // [23.2.4.2] capacity
531 /** Returns the number of elements in the %vector. */
534 { return size_type(this->_M_impl._M_finish - this->_M_impl._M_start); }
536 /** Returns the size() of the largest possible %vector. */
539 { return _M_get_Tp_allocator().max_size(); }
542 * @brief Resizes the %vector to the specified number of elements.
543 * @param new_size Number of elements the %vector should contain.
544 * @param x Data with which new elements should be populated.
546 * This function will %resize the %vector to the specified
547 * number of elements. If the number is smaller than the
548 * %vector's current size the %vector is truncated, otherwise
549 * the %vector is extended and new elements are populated with
553 resize(size_type __new_size, value_type __x = value_type())
555 if (__new_size < size())
556 _M_erase_at_end(this->_M_impl._M_start + __new_size);
558 insert(end(), __new_size - size(), __x);
561 #ifdef __GXX_EXPERIMENTAL_CXX0X__
562 /** A non-binding request to reduce capacity() to size(). */
565 { std::__shrink_to_fit<vector>::_S_do_it(*this); }
569 * Returns the total number of elements that the %vector can
570 * hold before needing to allocate more memory.
574 { return size_type(this->_M_impl._M_end_of_storage
575 - this->_M_impl._M_start); }
578 * Returns true if the %vector is empty. (Thus begin() would
583 { return begin() == end(); }
586 * @brief Attempt to preallocate enough memory for specified number of
588 * @param n Number of elements required.
589 * @throw std::length_error If @a n exceeds @c max_size().
591 * This function attempts to reserve enough memory for the
592 * %vector to hold the specified number of elements. If the
593 * number requested is more than max_size(), length_error is
596 * The advantage of this function is that if optimal code is a
597 * necessity and the user can determine the number of elements
598 * that will be required, the user can reserve the memory in
599 * %advance, and thus prevent a possible reallocation of memory
600 * and copying of %vector data.
603 reserve(size_type __n);
607 * @brief Subscript access to the data contained in the %vector.
608 * @param n The index of the element for which data should be
610 * @return Read/write reference to data.
612 * This operator allows for easy, array-style, data access.
613 * Note that data access with this operator is unchecked and
614 * out_of_range lookups are not defined. (For checked lookups
618 operator[](size_type __n)
619 { return *(this->_M_impl._M_start + __n); }
622 * @brief Subscript access to the data contained in the %vector.
623 * @param n The index of the element for which data should be
625 * @return Read-only (constant) reference to data.
627 * This operator allows for easy, array-style, data access.
628 * Note that data access with this operator is unchecked and
629 * out_of_range lookups are not defined. (For checked lookups
633 operator[](size_type __n) const
634 { return *(this->_M_impl._M_start + __n); }
637 /// Safety check used only from at().
639 _M_range_check(size_type __n) const
641 if (__n >= this->size())
642 __throw_out_of_range(__N("vector::_M_range_check"));
647 * @brief Provides access to the data contained in the %vector.
648 * @param n The index of the element for which data should be
650 * @return Read/write reference to data.
651 * @throw std::out_of_range If @a n is an invalid index.
653 * This function provides for safer data access. The parameter
654 * is first checked that it is in the range of the vector. The
655 * function throws out_of_range if the check fails.
665 * @brief Provides access to the data contained in the %vector.
666 * @param n The index of the element for which data should be
668 * @return Read-only (constant) reference to data.
669 * @throw std::out_of_range If @a n is an invalid index.
671 * This function provides for safer data access. The parameter
672 * is first checked that it is in the range of the vector. The
673 * function throws out_of_range if the check fails.
676 at(size_type __n) const
683 * Returns a read/write reference to the data at the first
684 * element of the %vector.
691 * Returns a read-only (constant) reference to the data at the first
692 * element of the %vector.
699 * Returns a read/write reference to the data at the last
700 * element of the %vector.
704 { return *(end() - 1); }
707 * Returns a read-only (constant) reference to the data at the
708 * last element of the %vector.
712 { return *(end() - 1); }
714 // _GLIBCXX_RESOLVE_LIB_DEFECTS
715 // DR 464. Suggestion for new member functions in standard containers.
718 * Returns a pointer such that [data(), data() + size()) is a valid
719 * range. For a non-empty %vector, data() == &front().
723 { return pointer(this->_M_impl._M_start); }
727 { return const_pointer(this->_M_impl._M_start); }
729 // [23.2.4.3] modifiers
731 * @brief Add data to the end of the %vector.
732 * @param x Data to be added.
734 * This is a typical stack operation. The function creates an
735 * element at the end of the %vector and assigns the given data
736 * to it. Due to the nature of a %vector this operation can be
737 * done in constant time if the %vector has preallocated space
741 push_back(const value_type& __x)
743 if (this->_M_impl._M_finish != this->_M_impl._M_end_of_storage)
745 this->_M_impl.construct(this->_M_impl._M_finish, __x);
746 ++this->_M_impl._M_finish;
749 _M_insert_aux(end(), __x);
752 #ifdef __GXX_EXPERIMENTAL_CXX0X__
754 push_back(value_type&& __x)
755 { emplace_back(std::move(__x)); }
757 template<typename... _Args>
759 emplace_back(_Args&&... __args);
763 * @brief Removes last element.
765 * This is a typical stack operation. It shrinks the %vector by one.
767 * Note that no data is returned, and if the last element's
768 * data is needed, it should be retrieved before pop_back() is
774 --this->_M_impl._M_finish;
775 this->_M_impl.destroy(this->_M_impl._M_finish);
778 #ifdef __GXX_EXPERIMENTAL_CXX0X__
780 * @brief Inserts an object in %vector before specified iterator.
781 * @param position An iterator into the %vector.
782 * @param args Arguments.
783 * @return An iterator that points to the inserted data.
785 * This function will insert an object of type T constructed
786 * with T(std::forward<Args>(args)...) before the specified location.
787 * Note that this kind of operation could be expensive for a %vector
788 * and if it is frequently used the user should consider using
791 template<typename... _Args>
793 emplace(iterator __position, _Args&&... __args);
797 * @brief Inserts given value into %vector before specified iterator.
798 * @param position An iterator into the %vector.
799 * @param x Data to be inserted.
800 * @return An iterator that points to the inserted data.
802 * This function will insert a copy of the given value before
803 * the specified location. Note that this kind of operation
804 * could be expensive for a %vector and if it is frequently
805 * used the user should consider using std::list.
808 insert(iterator __position, const value_type& __x);
810 #ifdef __GXX_EXPERIMENTAL_CXX0X__
812 * @brief Inserts given rvalue into %vector before specified iterator.
813 * @param position An iterator into the %vector.
814 * @param x Data to be inserted.
815 * @return An iterator that points to the inserted data.
817 * This function will insert a copy of the given rvalue before
818 * the specified location. Note that this kind of operation
819 * could be expensive for a %vector and if it is frequently
820 * used the user should consider using std::list.
823 insert(iterator __position, value_type&& __x)
824 { return emplace(__position, std::move(__x)); }
827 * @brief Inserts an initializer_list into the %vector.
828 * @param position An iterator into the %vector.
829 * @param l An initializer_list.
831 * This function will insert copies of the data in the
832 * initializer_list @a l into the %vector before the location
833 * specified by @a position.
835 * Note that this kind of operation could be expensive for a
836 * %vector and if it is frequently used the user should
837 * consider using std::list.
840 insert(iterator __position, initializer_list<value_type> __l)
841 { this->insert(__position, __l.begin(), __l.end()); }
845 * @brief Inserts a number of copies of given data into the %vector.
846 * @param position An iterator into the %vector.
847 * @param n Number of elements to be inserted.
848 * @param x Data to be inserted.
850 * This function will insert a specified number of copies of
851 * the given data before the location specified by @a position.
853 * Note that this kind of operation could be expensive for a
854 * %vector and if it is frequently used the user should
855 * consider using std::list.
858 insert(iterator __position, size_type __n, const value_type& __x)
859 { _M_fill_insert(__position, __n, __x); }
862 * @brief Inserts a range into the %vector.
863 * @param position An iterator into the %vector.
864 * @param first An input iterator.
865 * @param last An input iterator.
867 * This function will insert copies of the data in the range
868 * [first,last) into the %vector before the location specified
871 * Note that this kind of operation could be expensive for a
872 * %vector and if it is frequently used the user should
873 * consider using std::list.
875 template<typename _InputIterator>
877 insert(iterator __position, _InputIterator __first,
878 _InputIterator __last)
880 // Check whether it's an integral type. If so, it's not an iterator.
881 typedef typename std::__is_integer<_InputIterator>::__type _Integral;
882 _M_insert_dispatch(__position, __first, __last, _Integral());
886 * @brief Remove element at given position.
887 * @param position Iterator pointing to element to be erased.
888 * @return An iterator pointing to the next element (or end()).
890 * This function will erase the element at the given position and thus
891 * shorten the %vector by one.
893 * Note This operation could be expensive and if it is
894 * frequently used the user should consider using std::list.
895 * The user is also cautioned that this function only erases
896 * the element, and that if the element is itself a pointer,
897 * the pointed-to memory is not touched in any way. Managing
898 * the pointer is the user's responsibility.
901 erase(iterator __position);
904 * @brief Remove a range of elements.
905 * @param first Iterator pointing to the first element to be erased.
906 * @param last Iterator pointing to one past the last element to be
908 * @return An iterator pointing to the element pointed to by @a last
909 * prior to erasing (or end()).
911 * This function will erase the elements in the range [first,last) and
912 * shorten the %vector accordingly.
914 * Note This operation could be expensive and if it is
915 * frequently used the user should consider using std::list.
916 * The user is also cautioned that this function only erases
917 * the elements, and that if the elements themselves are
918 * pointers, the pointed-to memory is not touched in any way.
919 * Managing the pointer is the user's responsibility.
922 erase(iterator __first, iterator __last);
925 * @brief Swaps data with another %vector.
926 * @param x A %vector of the same element and allocator types.
928 * This exchanges the elements between two vectors in constant time.
929 * (Three pointers, so it should be quite fast.)
930 * Note that the global std::swap() function is specialized such that
931 * std::swap(v1,v2) will feed to this function.
936 std::swap(this->_M_impl._M_start, __x._M_impl._M_start);
937 std::swap(this->_M_impl._M_finish, __x._M_impl._M_finish);
938 std::swap(this->_M_impl._M_end_of_storage,
939 __x._M_impl._M_end_of_storage);
941 // _GLIBCXX_RESOLVE_LIB_DEFECTS
942 // 431. Swapping containers with unequal allocators.
943 std::__alloc_swap<_Tp_alloc_type>::_S_do_it(_M_get_Tp_allocator(),
944 __x._M_get_Tp_allocator());
948 * Erases all the elements. Note that this function only erases the
949 * elements, and that if the elements themselves are pointers, the
950 * pointed-to memory is not touched in any way. Managing the pointer is
951 * the user's responsibility.
955 { _M_erase_at_end(this->_M_impl._M_start); }
959 * Memory expansion handler. Uses the member allocation function to
960 * obtain @a n bytes of memory, and then copies [first,last) into it.
962 template<typename _ForwardIterator>
964 _M_allocate_and_copy(size_type __n,
965 _ForwardIterator __first, _ForwardIterator __last)
967 pointer __result = this->_M_allocate(__n);
970 std::__uninitialized_copy_a(__first, __last, __result,
971 _M_get_Tp_allocator());
976 _M_deallocate(__result, __n);
977 __throw_exception_again;
982 // Internal constructor functions follow.
984 // Called by the range constructor to implement [23.1.1]/9
986 // _GLIBCXX_RESOLVE_LIB_DEFECTS
987 // 438. Ambiguity in the "do the right thing" clause
988 template<typename _Integer>
990 _M_initialize_dispatch(_Integer __n, _Integer __value, __true_type)
992 this->_M_impl._M_start = _M_allocate(static_cast<size_type>(__n));
993 this->_M_impl._M_end_of_storage =
994 this->_M_impl._M_start + static_cast<size_type>(__n);
995 _M_fill_initialize(static_cast<size_type>(__n), __value);
998 // Called by the range constructor to implement [23.1.1]/9
999 template<typename _InputIterator>
1001 _M_initialize_dispatch(_InputIterator __first, _InputIterator __last,
1004 typedef typename std::iterator_traits<_InputIterator>::
1005 iterator_category _IterCategory;
1006 _M_range_initialize(__first, __last, _IterCategory());
1009 // Called by the second initialize_dispatch above
1010 template<typename _InputIterator>
1012 _M_range_initialize(_InputIterator __first,
1013 _InputIterator __last, std::input_iterator_tag)
1015 for (; __first != __last; ++__first)
1016 push_back(*__first);
1019 // Called by the second initialize_dispatch above
1020 template<typename _ForwardIterator>
1022 _M_range_initialize(_ForwardIterator __first,
1023 _ForwardIterator __last, std::forward_iterator_tag)
1025 const size_type __n = std::distance(__first, __last);
1026 this->_M_impl._M_start = this->_M_allocate(__n);
1027 this->_M_impl._M_end_of_storage = this->_M_impl._M_start + __n;
1028 this->_M_impl._M_finish =
1029 std::__uninitialized_copy_a(__first, __last,
1030 this->_M_impl._M_start,
1031 _M_get_Tp_allocator());
1034 // Called by the first initialize_dispatch above and by the
1035 // vector(n,value,a) constructor.
1037 _M_fill_initialize(size_type __n, const value_type& __value)
1039 std::__uninitialized_fill_n_a(this->_M_impl._M_start, __n, __value,
1040 _M_get_Tp_allocator());
1041 this->_M_impl._M_finish = this->_M_impl._M_end_of_storage;
1045 // Internal assign functions follow. The *_aux functions do the actual
1046 // assignment work for the range versions.
1048 // Called by the range assign to implement [23.1.1]/9
1050 // _GLIBCXX_RESOLVE_LIB_DEFECTS
1051 // 438. Ambiguity in the "do the right thing" clause
1052 template<typename _Integer>
1054 _M_assign_dispatch(_Integer __n, _Integer __val, __true_type)
1055 { _M_fill_assign(__n, __val); }
1057 // Called by the range assign to implement [23.1.1]/9
1058 template<typename _InputIterator>
1060 _M_assign_dispatch(_InputIterator __first, _InputIterator __last,
1063 typedef typename std::iterator_traits<_InputIterator>::
1064 iterator_category _IterCategory;
1065 _M_assign_aux(__first, __last, _IterCategory());
1068 // Called by the second assign_dispatch above
1069 template<typename _InputIterator>
1071 _M_assign_aux(_InputIterator __first, _InputIterator __last,
1072 std::input_iterator_tag);
1074 // Called by the second assign_dispatch above
1075 template<typename _ForwardIterator>
1077 _M_assign_aux(_ForwardIterator __first, _ForwardIterator __last,
1078 std::forward_iterator_tag);
1080 // Called by assign(n,t), and the range assign when it turns out
1081 // to be the same thing.
1083 _M_fill_assign(size_type __n, const value_type& __val);
1086 // Internal insert functions follow.
1088 // Called by the range insert to implement [23.1.1]/9
1090 // _GLIBCXX_RESOLVE_LIB_DEFECTS
1091 // 438. Ambiguity in the "do the right thing" clause
1092 template<typename _Integer>
1094 _M_insert_dispatch(iterator __pos, _Integer __n, _Integer __val,
1096 { _M_fill_insert(__pos, __n, __val); }
1098 // Called by the range insert to implement [23.1.1]/9
1099 template<typename _InputIterator>
1101 _M_insert_dispatch(iterator __pos, _InputIterator __first,
1102 _InputIterator __last, __false_type)
1104 typedef typename std::iterator_traits<_InputIterator>::
1105 iterator_category _IterCategory;
1106 _M_range_insert(__pos, __first, __last, _IterCategory());
1109 // Called by the second insert_dispatch above
1110 template<typename _InputIterator>
1112 _M_range_insert(iterator __pos, _InputIterator __first,
1113 _InputIterator __last, std::input_iterator_tag);
1115 // Called by the second insert_dispatch above
1116 template<typename _ForwardIterator>
1118 _M_range_insert(iterator __pos, _ForwardIterator __first,
1119 _ForwardIterator __last, std::forward_iterator_tag);
1121 // Called by insert(p,n,x), and the range insert when it turns out to be
1124 _M_fill_insert(iterator __pos, size_type __n, const value_type& __x);
1126 // Called by insert(p,x)
1127 #ifndef __GXX_EXPERIMENTAL_CXX0X__
1129 _M_insert_aux(iterator __position, const value_type& __x);
1131 template<typename... _Args>
1133 _M_insert_aux(iterator __position, _Args&&... __args);
1136 // Called by the latter.
1138 _M_check_len(size_type __n, const char* __s) const
1140 if (max_size() - size() < __n)
1141 __throw_length_error(__N(__s));
1143 const size_type __len = size() + std::max(size(), __n);
1144 return (__len < size() || __len > max_size()) ? max_size() : __len;
1147 // Internal erase functions follow.
1149 // Called by erase(q1,q2), clear(), resize(), _M_fill_assign,
1152 _M_erase_at_end(pointer __pos)
1154 std::_Destroy(__pos, this->_M_impl._M_finish, _M_get_Tp_allocator());
1155 this->_M_impl._M_finish = __pos;
1161 * @brief Vector equality comparison.
1162 * @param x A %vector.
1163 * @param y A %vector of the same type as @a x.
1164 * @return True iff the size and elements of the vectors are equal.
1166 * This is an equivalence relation. It is linear in the size of the
1167 * vectors. Vectors are considered equivalent if their sizes are equal,
1168 * and if corresponding elements compare equal.
1170 template<typename _Tp, typename _Alloc>
1172 operator==(const vector<_Tp, _Alloc>& __x, const vector<_Tp, _Alloc>& __y)
1173 { return (__x.size() == __y.size()
1174 && std::equal(__x.begin(), __x.end(), __y.begin())); }
1177 * @brief Vector ordering relation.
1178 * @param x A %vector.
1179 * @param y A %vector of the same type as @a x.
1180 * @return True iff @a x is lexicographically less than @a y.
1182 * This is a total ordering relation. It is linear in the size of the
1183 * vectors. The elements must be comparable with @c <.
1185 * See std::lexicographical_compare() for how the determination is made.
1187 template<typename _Tp, typename _Alloc>
1189 operator<(const vector<_Tp, _Alloc>& __x, const vector<_Tp, _Alloc>& __y)
1190 { return std::lexicographical_compare(__x.begin(), __x.end(),
1191 __y.begin(), __y.end()); }
1193 /// Based on operator==
1194 template<typename _Tp, typename _Alloc>
1196 operator!=(const vector<_Tp, _Alloc>& __x, const vector<_Tp, _Alloc>& __y)
1197 { return !(__x == __y); }
1199 /// Based on operator<
1200 template<typename _Tp, typename _Alloc>
1202 operator>(const vector<_Tp, _Alloc>& __x, const vector<_Tp, _Alloc>& __y)
1203 { return __y < __x; }
1205 /// Based on operator<
1206 template<typename _Tp, typename _Alloc>
1208 operator<=(const vector<_Tp, _Alloc>& __x, const vector<_Tp, _Alloc>& __y)
1209 { return !(__y < __x); }
1211 /// Based on operator<
1212 template<typename _Tp, typename _Alloc>
1214 operator>=(const vector<_Tp, _Alloc>& __x, const vector<_Tp, _Alloc>& __y)
1215 { return !(__x < __y); }
1217 /// See std::vector::swap().
1218 template<typename _Tp, typename _Alloc>
1220 swap(vector<_Tp, _Alloc>& __x, vector<_Tp, _Alloc>& __y)
1223 _GLIBCXX_END_NESTED_NAMESPACE
1225 #endif /* _STL_VECTOR_H */