libstdc++
|
00001 // Vector implementation -*- C++ -*- 00002 00003 // Copyright (C) 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008, 2009, 2010, 00004 // 2011 Free Software Foundation, Inc. 00005 // 00006 // This file is part of the GNU ISO C++ Library. This library is free 00007 // software; you can redistribute it and/or modify it under the 00008 // terms of the GNU General Public License as published by the 00009 // Free Software Foundation; either version 3, or (at your option) 00010 // any later version. 00011 00012 // This library is distributed in the hope that it will be useful, 00013 // but WITHOUT ANY WARRANTY; without even the implied warranty of 00014 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 00015 // GNU General Public License for more details. 00016 00017 // Under Section 7 of GPL version 3, you are granted additional 00018 // permissions described in the GCC Runtime Library Exception, version 00019 // 3.1, as published by the Free Software Foundation. 00020 00021 // You should have received a copy of the GNU General Public License and 00022 // a copy of the GCC Runtime Library Exception along with this program; 00023 // see the files COPYING3 and COPYING.RUNTIME respectively. If not, see 00024 // <http://www.gnu.org/licenses/>. 00025 00026 /* 00027 * 00028 * Copyright (c) 1994 00029 * Hewlett-Packard Company 00030 * 00031 * Permission to use, copy, modify, distribute and sell this software 00032 * and its documentation for any purpose is hereby granted without fee, 00033 * provided that the above copyright notice appear in all copies and 00034 * that both that copyright notice and this permission notice appear 00035 * in supporting documentation. Hewlett-Packard Company makes no 00036 * representations about the suitability of this software for any 00037 * purpose. It is provided "as is" without express or implied warranty. 00038 * 00039 * 00040 * Copyright (c) 1996 00041 * Silicon Graphics Computer Systems, Inc. 00042 * 00043 * Permission to use, copy, modify, distribute and sell this software 00044 * and its documentation for any purpose is hereby granted without fee, 00045 * provided that the above copyright notice appear in all copies and 00046 * that both that copyright notice and this permission notice appear 00047 * in supporting documentation. Silicon Graphics makes no 00048 * representations about the suitability of this software for any 00049 * purpose. It is provided "as is" without express or implied warranty. 00050 */ 00051 00052 /** @file bits/stl_vector.h 00053 * This is an internal header file, included by other library headers. 00054 * Do not attempt to use it directly. @headername{vector} 00055 */ 00056 00057 #ifndef _STL_VECTOR_H 00058 #define _STL_VECTOR_H 1 00059 00060 #include <bits/stl_iterator_base_funcs.h> 00061 #include <bits/functexcept.h> 00062 #include <bits/concept_check.h> 00063 #include <initializer_list> 00064 00065 namespace std _GLIBCXX_VISIBILITY(default) 00066 { 00067 _GLIBCXX_BEGIN_NAMESPACE_CONTAINER 00068 00069 /// See bits/stl_deque.h's _Deque_base for an explanation. 00070 template<typename _Tp, typename _Alloc> 00071 struct _Vector_base 00072 { 00073 typedef typename _Alloc::template rebind<_Tp>::other _Tp_alloc_type; 00074 00075 struct _Vector_impl 00076 : public _Tp_alloc_type 00077 { 00078 typename _Tp_alloc_type::pointer _M_start; 00079 typename _Tp_alloc_type::pointer _M_finish; 00080 typename _Tp_alloc_type::pointer _M_end_of_storage; 00081 00082 _Vector_impl() 00083 : _Tp_alloc_type(), _M_start(0), _M_finish(0), _M_end_of_storage(0) 00084 { } 00085 00086 _Vector_impl(_Tp_alloc_type const& __a) 00087 : _Tp_alloc_type(__a), _M_start(0), _M_finish(0), _M_end_of_storage(0) 00088 { } 00089 }; 00090 00091 public: 00092 typedef _Alloc allocator_type; 00093 00094 _Tp_alloc_type& 00095 _M_get_Tp_allocator() 00096 { return *static_cast<_Tp_alloc_type*>(&this->_M_impl); } 00097 00098 const _Tp_alloc_type& 00099 _M_get_Tp_allocator() const 00100 { return *static_cast<const _Tp_alloc_type*>(&this->_M_impl); } 00101 00102 allocator_type 00103 get_allocator() const 00104 { return allocator_type(_M_get_Tp_allocator()); } 00105 00106 _Vector_base() 00107 : _M_impl() { } 00108 00109 _Vector_base(const allocator_type& __a) 00110 : _M_impl(__a) { } 00111 00112 _Vector_base(size_t __n) 00113 : _M_impl() 00114 { 00115 this->_M_impl._M_start = this->_M_allocate(__n); 00116 this->_M_impl._M_finish = this->_M_impl._M_start; 00117 this->_M_impl._M_end_of_storage = this->_M_impl._M_start + __n; 00118 } 00119 00120 _Vector_base(size_t __n, const allocator_type& __a) 00121 : _M_impl(__a) 00122 { 00123 this->_M_impl._M_start = this->_M_allocate(__n); 00124 this->_M_impl._M_finish = this->_M_impl._M_start; 00125 this->_M_impl._M_end_of_storage = this->_M_impl._M_start + __n; 00126 } 00127 00128 #ifdef __GXX_EXPERIMENTAL_CXX0X__ 00129 _Vector_base(_Vector_base&& __x) 00130 : _M_impl(__x._M_get_Tp_allocator()) 00131 { 00132 this->_M_impl._M_start = __x._M_impl._M_start; 00133 this->_M_impl._M_finish = __x._M_impl._M_finish; 00134 this->_M_impl._M_end_of_storage = __x._M_impl._M_end_of_storage; 00135 __x._M_impl._M_start = 0; 00136 __x._M_impl._M_finish = 0; 00137 __x._M_impl._M_end_of_storage = 0; 00138 } 00139 #endif 00140 00141 ~_Vector_base() 00142 { _M_deallocate(this->_M_impl._M_start, this->_M_impl._M_end_of_storage 00143 - this->_M_impl._M_start); } 00144 00145 public: 00146 _Vector_impl _M_impl; 00147 00148 typename _Tp_alloc_type::pointer 00149 _M_allocate(size_t __n) 00150 { return __n != 0 ? _M_impl.allocate(__n) : 0; } 00151 00152 void 00153 _M_deallocate(typename _Tp_alloc_type::pointer __p, size_t __n) 00154 { 00155 if (__p) 00156 _M_impl.deallocate(__p, __n); 00157 } 00158 }; 00159 00160 00161 /** 00162 * @brief A standard container which offers fixed time access to 00163 * individual elements in any order. 00164 * 00165 * @ingroup sequences 00166 * 00167 * Meets the requirements of a <a href="tables.html#65">container</a>, a 00168 * <a href="tables.html#66">reversible container</a>, and a 00169 * <a href="tables.html#67">sequence</a>, including the 00170 * <a href="tables.html#68">optional sequence requirements</a> with the 00171 * %exception of @c push_front and @c pop_front. 00172 * 00173 * In some terminology a %vector can be described as a dynamic 00174 * C-style array, it offers fast and efficient access to individual 00175 * elements in any order and saves the user from worrying about 00176 * memory and size allocation. Subscripting ( @c [] ) access is 00177 * also provided as with C-style arrays. 00178 */ 00179 template<typename _Tp, typename _Alloc = std::allocator<_Tp> > 00180 class vector : protected _Vector_base<_Tp, _Alloc> 00181 { 00182 // Concept requirements. 00183 typedef typename _Alloc::value_type _Alloc_value_type; 00184 __glibcxx_class_requires(_Tp, _SGIAssignableConcept) 00185 __glibcxx_class_requires2(_Tp, _Alloc_value_type, _SameTypeConcept) 00186 00187 typedef _Vector_base<_Tp, _Alloc> _Base; 00188 typedef typename _Base::_Tp_alloc_type _Tp_alloc_type; 00189 00190 public: 00191 typedef _Tp value_type; 00192 typedef typename _Tp_alloc_type::pointer pointer; 00193 typedef typename _Tp_alloc_type::const_pointer const_pointer; 00194 typedef typename _Tp_alloc_type::reference reference; 00195 typedef typename _Tp_alloc_type::const_reference const_reference; 00196 typedef __gnu_cxx::__normal_iterator<pointer, vector> iterator; 00197 typedef __gnu_cxx::__normal_iterator<const_pointer, vector> 00198 const_iterator; 00199 typedef std::reverse_iterator<const_iterator> const_reverse_iterator; 00200 typedef std::reverse_iterator<iterator> reverse_iterator; 00201 typedef size_t size_type; 00202 typedef ptrdiff_t difference_type; 00203 typedef _Alloc allocator_type; 00204 00205 protected: 00206 using _Base::_M_allocate; 00207 using _Base::_M_deallocate; 00208 using _Base::_M_impl; 00209 using _Base::_M_get_Tp_allocator; 00210 00211 public: 00212 // [23.2.4.1] construct/copy/destroy 00213 // (assign() and get_allocator() are also listed in this section) 00214 /** 00215 * @brief Default constructor creates no elements. 00216 */ 00217 vector() 00218 : _Base() { } 00219 00220 /** 00221 * @brief Creates a %vector with no elements. 00222 * @param a An allocator object. 00223 */ 00224 explicit 00225 vector(const allocator_type& __a) 00226 : _Base(__a) { } 00227 00228 #ifdef __GXX_EXPERIMENTAL_CXX0X__ 00229 /** 00230 * @brief Creates a %vector with default constructed elements. 00231 * @param n The number of elements to initially create. 00232 * 00233 * This constructor fills the %vector with @a n default 00234 * constructed elements. 00235 */ 00236 explicit 00237 vector(size_type __n) 00238 : _Base(__n) 00239 { _M_default_initialize(__n); } 00240 00241 /** 00242 * @brief Creates a %vector with copies of an exemplar element. 00243 * @param n The number of elements to initially create. 00244 * @param value An element to copy. 00245 * @param a An allocator. 00246 * 00247 * This constructor fills the %vector with @a n copies of @a value. 00248 */ 00249 vector(size_type __n, const value_type& __value, 00250 const allocator_type& __a = allocator_type()) 00251 : _Base(__n, __a) 00252 { _M_fill_initialize(__n, __value); } 00253 #else 00254 /** 00255 * @brief Creates a %vector with copies of an exemplar element. 00256 * @param n The number of elements to initially create. 00257 * @param value An element to copy. 00258 * @param a An allocator. 00259 * 00260 * This constructor fills the %vector with @a n copies of @a value. 00261 */ 00262 explicit 00263 vector(size_type __n, const value_type& __value = value_type(), 00264 const allocator_type& __a = allocator_type()) 00265 : _Base(__n, __a) 00266 { _M_fill_initialize(__n, __value); } 00267 #endif 00268 00269 /** 00270 * @brief %Vector copy constructor. 00271 * @param x A %vector of identical element and allocator types. 00272 * 00273 * The newly-created %vector uses a copy of the allocation 00274 * object used by @a x. All the elements of @a x are copied, 00275 * but any extra memory in 00276 * @a x (for fast expansion) will not be copied. 00277 */ 00278 vector(const vector& __x) 00279 : _Base(__x.size(), __x._M_get_Tp_allocator()) 00280 { this->_M_impl._M_finish = 00281 std::__uninitialized_copy_a(__x.begin(), __x.end(), 00282 this->_M_impl._M_start, 00283 _M_get_Tp_allocator()); 00284 } 00285 00286 #ifdef __GXX_EXPERIMENTAL_CXX0X__ 00287 /** 00288 * @brief %Vector move constructor. 00289 * @param x A %vector of identical element and allocator types. 00290 * 00291 * The newly-created %vector contains the exact contents of @a x. 00292 * The contents of @a x are a valid, but unspecified %vector. 00293 */ 00294 vector(vector&& __x) 00295 : _Base(std::move(__x)) { } 00296 00297 /** 00298 * @brief Builds a %vector from an initializer list. 00299 * @param l An initializer_list. 00300 * @param a An allocator. 00301 * 00302 * Create a %vector consisting of copies of the elements in the 00303 * initializer_list @a l. 00304 * 00305 * This will call the element type's copy constructor N times 00306 * (where N is @a l.size()) and do no memory reallocation. 00307 */ 00308 vector(initializer_list<value_type> __l, 00309 const allocator_type& __a = allocator_type()) 00310 : _Base(__a) 00311 { 00312 _M_range_initialize(__l.begin(), __l.end(), 00313 random_access_iterator_tag()); 00314 } 00315 #endif 00316 00317 /** 00318 * @brief Builds a %vector from a range. 00319 * @param first An input iterator. 00320 * @param last An input iterator. 00321 * @param a An allocator. 00322 * 00323 * Create a %vector consisting of copies of the elements from 00324 * [first,last). 00325 * 00326 * If the iterators are forward, bidirectional, or 00327 * random-access, then this will call the elements' copy 00328 * constructor N times (where N is distance(first,last)) and do 00329 * no memory reallocation. But if only input iterators are 00330 * used, then this will do at most 2N calls to the copy 00331 * constructor, and logN memory reallocations. 00332 */ 00333 template<typename _InputIterator> 00334 vector(_InputIterator __first, _InputIterator __last, 00335 const allocator_type& __a = allocator_type()) 00336 : _Base(__a) 00337 { 00338 // Check whether it's an integral type. If so, it's not an iterator. 00339 typedef typename std::__is_integer<_InputIterator>::__type _Integral; 00340 _M_initialize_dispatch(__first, __last, _Integral()); 00341 } 00342 00343 /** 00344 * The dtor only erases the elements, and note that if the 00345 * elements themselves are pointers, the pointed-to memory is 00346 * not touched in any way. Managing the pointer is the user's 00347 * responsibility. 00348 */ 00349 ~vector() 00350 { std::_Destroy(this->_M_impl._M_start, this->_M_impl._M_finish, 00351 _M_get_Tp_allocator()); } 00352 00353 /** 00354 * @brief %Vector assignment operator. 00355 * @param x A %vector of identical element and allocator types. 00356 * 00357 * All the elements of @a x are copied, but any extra memory in 00358 * @a x (for fast expansion) will not be copied. Unlike the 00359 * copy constructor, the allocator object is not copied. 00360 */ 00361 vector& 00362 operator=(const vector& __x); 00363 00364 #ifdef __GXX_EXPERIMENTAL_CXX0X__ 00365 /** 00366 * @brief %Vector move assignment operator. 00367 * @param x A %vector of identical element and allocator types. 00368 * 00369 * The contents of @a x are moved into this %vector (without copying). 00370 * @a x is a valid, but unspecified %vector. 00371 */ 00372 vector& 00373 operator=(vector&& __x) 00374 { 00375 // NB: DR 1204. 00376 // NB: DR 675. 00377 this->clear(); 00378 this->swap(__x); 00379 return *this; 00380 } 00381 00382 /** 00383 * @brief %Vector list assignment operator. 00384 * @param l An initializer_list. 00385 * 00386 * This function fills a %vector with copies of the elements in the 00387 * initializer list @a l. 00388 * 00389 * Note that the assignment completely changes the %vector and 00390 * that the resulting %vector's size is the same as the number 00391 * of elements assigned. Old data may be lost. 00392 */ 00393 vector& 00394 operator=(initializer_list<value_type> __l) 00395 { 00396 this->assign(__l.begin(), __l.end()); 00397 return *this; 00398 } 00399 #endif 00400 00401 /** 00402 * @brief Assigns a given value to a %vector. 00403 * @param n Number of elements to be assigned. 00404 * @param val Value to be assigned. 00405 * 00406 * This function fills a %vector with @a n copies of the given 00407 * value. Note that the assignment completely changes the 00408 * %vector and that the resulting %vector's size is the same as 00409 * the number of elements assigned. Old data may be lost. 00410 */ 00411 void 00412 assign(size_type __n, const value_type& __val) 00413 { _M_fill_assign(__n, __val); } 00414 00415 /** 00416 * @brief Assigns a range to a %vector. 00417 * @param first An input iterator. 00418 * @param last An input iterator. 00419 * 00420 * This function fills a %vector with copies of the elements in the 00421 * range [first,last). 00422 * 00423 * Note that the assignment completely changes the %vector and 00424 * that the resulting %vector's size is the same as the number 00425 * of elements assigned. Old data may be lost. 00426 */ 00427 template<typename _InputIterator> 00428 void 00429 assign(_InputIterator __first, _InputIterator __last) 00430 { 00431 // Check whether it's an integral type. If so, it's not an iterator. 00432 typedef typename std::__is_integer<_InputIterator>::__type _Integral; 00433 _M_assign_dispatch(__first, __last, _Integral()); 00434 } 00435 00436 #ifdef __GXX_EXPERIMENTAL_CXX0X__ 00437 /** 00438 * @brief Assigns an initializer list to a %vector. 00439 * @param l An initializer_list. 00440 * 00441 * This function fills a %vector with copies of the elements in the 00442 * initializer list @a l. 00443 * 00444 * Note that the assignment completely changes the %vector and 00445 * that the resulting %vector's size is the same as the number 00446 * of elements assigned. Old data may be lost. 00447 */ 00448 void 00449 assign(initializer_list<value_type> __l) 00450 { this->assign(__l.begin(), __l.end()); } 00451 #endif 00452 00453 /// Get a copy of the memory allocation object. 00454 using _Base::get_allocator; 00455 00456 // iterators 00457 /** 00458 * Returns a read/write iterator that points to the first 00459 * element in the %vector. Iteration is done in ordinary 00460 * element order. 00461 */ 00462 iterator 00463 begin() 00464 { return iterator(this->_M_impl._M_start); } 00465 00466 /** 00467 * Returns a read-only (constant) iterator that points to the 00468 * first element in the %vector. Iteration is done in ordinary 00469 * element order. 00470 */ 00471 const_iterator 00472 begin() const 00473 { return const_iterator(this->_M_impl._M_start); } 00474 00475 /** 00476 * Returns a read/write iterator that points one past the last 00477 * element in the %vector. Iteration is done in ordinary 00478 * element order. 00479 */ 00480 iterator 00481 end() 00482 { return iterator(this->_M_impl._M_finish); } 00483 00484 /** 00485 * Returns a read-only (constant) iterator that points one past 00486 * the last element in the %vector. Iteration is done in 00487 * ordinary element order. 00488 */ 00489 const_iterator 00490 end() const 00491 { return const_iterator(this->_M_impl._M_finish); } 00492 00493 /** 00494 * Returns a read/write reverse iterator that points to the 00495 * last element in the %vector. Iteration is done in reverse 00496 * element order. 00497 */ 00498 reverse_iterator 00499 rbegin() 00500 { return reverse_iterator(end()); } 00501 00502 /** 00503 * Returns a read-only (constant) reverse iterator that points 00504 * to the last element in the %vector. Iteration is done in 00505 * reverse element order. 00506 */ 00507 const_reverse_iterator 00508 rbegin() const 00509 { return const_reverse_iterator(end()); } 00510 00511 /** 00512 * Returns a read/write reverse iterator that points to one 00513 * before the first element in the %vector. Iteration is done 00514 * in reverse element order. 00515 */ 00516 reverse_iterator 00517 rend() 00518 { return reverse_iterator(begin()); } 00519 00520 /** 00521 * Returns a read-only (constant) reverse iterator that points 00522 * to one before the first element in the %vector. Iteration 00523 * is done in reverse element order. 00524 */ 00525 const_reverse_iterator 00526 rend() const 00527 { return const_reverse_iterator(begin()); } 00528 00529 #ifdef __GXX_EXPERIMENTAL_CXX0X__ 00530 /** 00531 * Returns a read-only (constant) iterator that points to the 00532 * first element in the %vector. Iteration is done in ordinary 00533 * element order. 00534 */ 00535 const_iterator 00536 cbegin() const 00537 { return const_iterator(this->_M_impl._M_start); } 00538 00539 /** 00540 * Returns a read-only (constant) iterator that points one past 00541 * the last element in the %vector. Iteration is done in 00542 * ordinary element order. 00543 */ 00544 const_iterator 00545 cend() const 00546 { return const_iterator(this->_M_impl._M_finish); } 00547 00548 /** 00549 * Returns a read-only (constant) reverse iterator that points 00550 * to the last element in the %vector. Iteration is done in 00551 * reverse element order. 00552 */ 00553 const_reverse_iterator 00554 crbegin() const 00555 { return const_reverse_iterator(end()); } 00556 00557 /** 00558 * Returns a read-only (constant) reverse iterator that points 00559 * to one before the first element in the %vector. Iteration 00560 * is done in reverse element order. 00561 */ 00562 const_reverse_iterator 00563 crend() const 00564 { return const_reverse_iterator(begin()); } 00565 #endif 00566 00567 // [23.2.4.2] capacity 00568 /** Returns the number of elements in the %vector. */ 00569 size_type 00570 size() const 00571 { return size_type(this->_M_impl._M_finish - this->_M_impl._M_start); } 00572 00573 /** Returns the size() of the largest possible %vector. */ 00574 size_type 00575 max_size() const 00576 { return _M_get_Tp_allocator().max_size(); } 00577 00578 #ifdef __GXX_EXPERIMENTAL_CXX0X__ 00579 /** 00580 * @brief Resizes the %vector to the specified number of elements. 00581 * @param new_size Number of elements the %vector should contain. 00582 * 00583 * This function will %resize the %vector to the specified 00584 * number of elements. If the number is smaller than the 00585 * %vector's current size the %vector is truncated, otherwise 00586 * default constructed elements are appended. 00587 */ 00588 void 00589 resize(size_type __new_size) 00590 { 00591 if (__new_size > size()) 00592 _M_default_append(__new_size - size()); 00593 else if (__new_size < size()) 00594 _M_erase_at_end(this->_M_impl._M_start + __new_size); 00595 } 00596 00597 /** 00598 * @brief Resizes the %vector to the specified number of elements. 00599 * @param new_size Number of elements the %vector should contain. 00600 * @param x Data with which new elements should be populated. 00601 * 00602 * This function will %resize the %vector to the specified 00603 * number of elements. If the number is smaller than the 00604 * %vector's current size the %vector is truncated, otherwise 00605 * the %vector is extended and new elements are populated with 00606 * given data. 00607 */ 00608 void 00609 resize(size_type __new_size, const value_type& __x) 00610 { 00611 if (__new_size > size()) 00612 insert(end(), __new_size - size(), __x); 00613 else if (__new_size < size()) 00614 _M_erase_at_end(this->_M_impl._M_start + __new_size); 00615 } 00616 #else 00617 /** 00618 * @brief Resizes the %vector to the specified number of elements. 00619 * @param new_size Number of elements the %vector should contain. 00620 * @param x Data with which new elements should be populated. 00621 * 00622 * This function will %resize the %vector to the specified 00623 * number of elements. If the number is smaller than the 00624 * %vector's current size the %vector is truncated, otherwise 00625 * the %vector is extended and new elements are populated with 00626 * given data. 00627 */ 00628 void 00629 resize(size_type __new_size, value_type __x = value_type()) 00630 { 00631 if (__new_size > size()) 00632 insert(end(), __new_size - size(), __x); 00633 else if (__new_size < size()) 00634 _M_erase_at_end(this->_M_impl._M_start + __new_size); 00635 } 00636 #endif 00637 00638 #ifdef __GXX_EXPERIMENTAL_CXX0X__ 00639 /** A non-binding request to reduce capacity() to size(). */ 00640 void 00641 shrink_to_fit() 00642 { std::__shrink_to_fit<vector>::_S_do_it(*this); } 00643 #endif 00644 00645 /** 00646 * Returns the total number of elements that the %vector can 00647 * hold before needing to allocate more memory. 00648 */ 00649 size_type 00650 capacity() const 00651 { return size_type(this->_M_impl._M_end_of_storage 00652 - this->_M_impl._M_start); } 00653 00654 /** 00655 * Returns true if the %vector is empty. (Thus begin() would 00656 * equal end().) 00657 */ 00658 bool 00659 empty() const 00660 { return begin() == end(); } 00661 00662 /** 00663 * @brief Attempt to preallocate enough memory for specified number of 00664 * elements. 00665 * @param n Number of elements required. 00666 * @throw std::length_error If @a n exceeds @c max_size(). 00667 * 00668 * This function attempts to reserve enough memory for the 00669 * %vector to hold the specified number of elements. If the 00670 * number requested is more than max_size(), length_error is 00671 * thrown. 00672 * 00673 * The advantage of this function is that if optimal code is a 00674 * necessity and the user can determine the number of elements 00675 * that will be required, the user can reserve the memory in 00676 * %advance, and thus prevent a possible reallocation of memory 00677 * and copying of %vector data. 00678 */ 00679 void 00680 reserve(size_type __n); 00681 00682 // element access 00683 /** 00684 * @brief Subscript access to the data contained in the %vector. 00685 * @param n The index of the element for which data should be 00686 * accessed. 00687 * @return Read/write reference to data. 00688 * 00689 * This operator allows for easy, array-style, data access. 00690 * Note that data access with this operator is unchecked and 00691 * out_of_range lookups are not defined. (For checked lookups 00692 * see at().) 00693 */ 00694 reference 00695 operator[](size_type __n) 00696 { return *(this->_M_impl._M_start + __n); } 00697 00698 /** 00699 * @brief Subscript access to the data contained in the %vector. 00700 * @param n The index of the element for which data should be 00701 * accessed. 00702 * @return Read-only (constant) reference to data. 00703 * 00704 * This operator allows for easy, array-style, data access. 00705 * Note that data access with this operator is unchecked and 00706 * out_of_range lookups are not defined. (For checked lookups 00707 * see at().) 00708 */ 00709 const_reference 00710 operator[](size_type __n) const 00711 { return *(this->_M_impl._M_start + __n); } 00712 00713 protected: 00714 /// Safety check used only from at(). 00715 void 00716 _M_range_check(size_type __n) const 00717 { 00718 if (__n >= this->size()) 00719 __throw_out_of_range(__N("vector::_M_range_check")); 00720 } 00721 00722 public: 00723 /** 00724 * @brief Provides access to the data contained in the %vector. 00725 * @param n The index of the element for which data should be 00726 * accessed. 00727 * @return Read/write reference to data. 00728 * @throw std::out_of_range If @a n is an invalid index. 00729 * 00730 * This function provides for safer data access. The parameter 00731 * is first checked that it is in the range of the vector. The 00732 * function throws out_of_range if the check fails. 00733 */ 00734 reference 00735 at(size_type __n) 00736 { 00737 _M_range_check(__n); 00738 return (*this)[__n]; 00739 } 00740 00741 /** 00742 * @brief Provides access to the data contained in the %vector. 00743 * @param n The index of the element for which data should be 00744 * accessed. 00745 * @return Read-only (constant) reference to data. 00746 * @throw std::out_of_range If @a n is an invalid index. 00747 * 00748 * This function provides for safer data access. The parameter 00749 * is first checked that it is in the range of the vector. The 00750 * function throws out_of_range if the check fails. 00751 */ 00752 const_reference 00753 at(size_type __n) const 00754 { 00755 _M_range_check(__n); 00756 return (*this)[__n]; 00757 } 00758 00759 /** 00760 * Returns a read/write reference to the data at the first 00761 * element of the %vector. 00762 */ 00763 reference 00764 front() 00765 { return *begin(); } 00766 00767 /** 00768 * Returns a read-only (constant) reference to the data at the first 00769 * element of the %vector. 00770 */ 00771 const_reference 00772 front() const 00773 { return *begin(); } 00774 00775 /** 00776 * Returns a read/write reference to the data at the last 00777 * element of the %vector. 00778 */ 00779 reference 00780 back() 00781 { return *(end() - 1); } 00782 00783 /** 00784 * Returns a read-only (constant) reference to the data at the 00785 * last element of the %vector. 00786 */ 00787 const_reference 00788 back() const 00789 { return *(end() - 1); } 00790 00791 // _GLIBCXX_RESOLVE_LIB_DEFECTS 00792 // DR 464. Suggestion for new member functions in standard containers. 00793 // data access 00794 /** 00795 * Returns a pointer such that [data(), data() + size()) is a valid 00796 * range. For a non-empty %vector, data() == &front(). 00797 */ 00798 #ifdef __GXX_EXPERIMENTAL_CXX0X__ 00799 _Tp* 00800 #else 00801 pointer 00802 #endif 00803 data() 00804 { return std::__addressof(front()); } 00805 00806 #ifdef __GXX_EXPERIMENTAL_CXX0X__ 00807 const _Tp* 00808 #else 00809 const_pointer 00810 #endif 00811 data() const 00812 { return std::__addressof(front()); } 00813 00814 // [23.2.4.3] modifiers 00815 /** 00816 * @brief Add data to the end of the %vector. 00817 * @param x Data to be added. 00818 * 00819 * This is a typical stack operation. The function creates an 00820 * element at the end of the %vector and assigns the given data 00821 * to it. Due to the nature of a %vector this operation can be 00822 * done in constant time if the %vector has preallocated space 00823 * available. 00824 */ 00825 void 00826 push_back(const value_type& __x) 00827 { 00828 if (this->_M_impl._M_finish != this->_M_impl._M_end_of_storage) 00829 { 00830 this->_M_impl.construct(this->_M_impl._M_finish, __x); 00831 ++this->_M_impl._M_finish; 00832 } 00833 else 00834 _M_insert_aux(end(), __x); 00835 } 00836 00837 #ifdef __GXX_EXPERIMENTAL_CXX0X__ 00838 void 00839 push_back(value_type&& __x) 00840 { emplace_back(std::move(__x)); } 00841 00842 template<typename... _Args> 00843 void 00844 emplace_back(_Args&&... __args); 00845 #endif 00846 00847 /** 00848 * @brief Removes last element. 00849 * 00850 * This is a typical stack operation. It shrinks the %vector by one. 00851 * 00852 * Note that no data is returned, and if the last element's 00853 * data is needed, it should be retrieved before pop_back() is 00854 * called. 00855 */ 00856 void 00857 pop_back() 00858 { 00859 --this->_M_impl._M_finish; 00860 this->_M_impl.destroy(this->_M_impl._M_finish); 00861 } 00862 00863 #ifdef __GXX_EXPERIMENTAL_CXX0X__ 00864 /** 00865 * @brief Inserts an object in %vector before specified iterator. 00866 * @param position An iterator into the %vector. 00867 * @param args Arguments. 00868 * @return An iterator that points to the inserted data. 00869 * 00870 * This function will insert an object of type T constructed 00871 * with T(std::forward<Args>(args)...) before the specified location. 00872 * Note that this kind of operation could be expensive for a %vector 00873 * and if it is frequently used the user should consider using 00874 * std::list. 00875 */ 00876 template<typename... _Args> 00877 iterator 00878 emplace(iterator __position, _Args&&... __args); 00879 #endif 00880 00881 /** 00882 * @brief Inserts given value into %vector before specified iterator. 00883 * @param position An iterator into the %vector. 00884 * @param x Data to be inserted. 00885 * @return An iterator that points to the inserted data. 00886 * 00887 * This function will insert a copy of the given value before 00888 * the specified location. Note that this kind of operation 00889 * could be expensive for a %vector and if it is frequently 00890 * used the user should consider using std::list. 00891 */ 00892 iterator 00893 insert(iterator __position, const value_type& __x); 00894 00895 #ifdef __GXX_EXPERIMENTAL_CXX0X__ 00896 /** 00897 * @brief Inserts given rvalue into %vector before specified iterator. 00898 * @param position An iterator into the %vector. 00899 * @param x Data to be inserted. 00900 * @return An iterator that points to the inserted data. 00901 * 00902 * This function will insert a copy of the given rvalue before 00903 * the specified location. Note that this kind of operation 00904 * could be expensive for a %vector and if it is frequently 00905 * used the user should consider using std::list. 00906 */ 00907 iterator 00908 insert(iterator __position, value_type&& __x) 00909 { return emplace(__position, std::move(__x)); } 00910 00911 /** 00912 * @brief Inserts an initializer_list into the %vector. 00913 * @param position An iterator into the %vector. 00914 * @param l An initializer_list. 00915 * 00916 * This function will insert copies of the data in the 00917 * initializer_list @a l into the %vector before the location 00918 * specified by @a position. 00919 * 00920 * Note that this kind of operation could be expensive for a 00921 * %vector and if it is frequently used the user should 00922 * consider using std::list. 00923 */ 00924 void 00925 insert(iterator __position, initializer_list<value_type> __l) 00926 { this->insert(__position, __l.begin(), __l.end()); } 00927 #endif 00928 00929 /** 00930 * @brief Inserts a number of copies of given data into the %vector. 00931 * @param position An iterator into the %vector. 00932 * @param n Number of elements to be inserted. 00933 * @param x Data to be inserted. 00934 * 00935 * This function will insert a specified number of copies of 00936 * the given data before the location specified by @a position. 00937 * 00938 * Note that this kind of operation could be expensive for a 00939 * %vector and if it is frequently used the user should 00940 * consider using std::list. 00941 */ 00942 void 00943 insert(iterator __position, size_type __n, const value_type& __x) 00944 { _M_fill_insert(__position, __n, __x); } 00945 00946 /** 00947 * @brief Inserts a range into the %vector. 00948 * @param position An iterator into the %vector. 00949 * @param first An input iterator. 00950 * @param last An input iterator. 00951 * 00952 * This function will insert copies of the data in the range 00953 * [first,last) into the %vector before the location specified 00954 * by @a pos. 00955 * 00956 * Note that this kind of operation could be expensive for a 00957 * %vector and if it is frequently used the user should 00958 * consider using std::list. 00959 */ 00960 template<typename _InputIterator> 00961 void 00962 insert(iterator __position, _InputIterator __first, 00963 _InputIterator __last) 00964 { 00965 // Check whether it's an integral type. If so, it's not an iterator. 00966 typedef typename std::__is_integer<_InputIterator>::__type _Integral; 00967 _M_insert_dispatch(__position, __first, __last, _Integral()); 00968 } 00969 00970 /** 00971 * @brief Remove element at given position. 00972 * @param position Iterator pointing to element to be erased. 00973 * @return An iterator pointing to the next element (or end()). 00974 * 00975 * This function will erase the element at the given position and thus 00976 * shorten the %vector by one. 00977 * 00978 * Note This operation could be expensive and if it is 00979 * frequently used the user should consider using std::list. 00980 * The user is also cautioned that this function only erases 00981 * the element, and that if the element is itself a pointer, 00982 * the pointed-to memory is not touched in any way. Managing 00983 * the pointer is the user's responsibility. 00984 */ 00985 iterator 00986 erase(iterator __position); 00987 00988 /** 00989 * @brief Remove a range of elements. 00990 * @param first Iterator pointing to the first element to be erased. 00991 * @param last Iterator pointing to one past the last element to be 00992 * erased. 00993 * @return An iterator pointing to the element pointed to by @a last 00994 * prior to erasing (or end()). 00995 * 00996 * This function will erase the elements in the range [first,last) and 00997 * shorten the %vector accordingly. 00998 * 00999 * Note This operation could be expensive and if it is 01000 * frequently used the user should consider using std::list. 01001 * The user is also cautioned that this function only erases 01002 * the elements, and that if the elements themselves are 01003 * pointers, the pointed-to memory is not touched in any way. 01004 * Managing the pointer is the user's responsibility. 01005 */ 01006 iterator 01007 erase(iterator __first, iterator __last); 01008 01009 /** 01010 * @brief Swaps data with another %vector. 01011 * @param x A %vector of the same element and allocator types. 01012 * 01013 * This exchanges the elements between two vectors in constant time. 01014 * (Three pointers, so it should be quite fast.) 01015 * Note that the global std::swap() function is specialized such that 01016 * std::swap(v1,v2) will feed to this function. 01017 */ 01018 void 01019 swap(vector& __x) 01020 { 01021 std::swap(this->_M_impl._M_start, __x._M_impl._M_start); 01022 std::swap(this->_M_impl._M_finish, __x._M_impl._M_finish); 01023 std::swap(this->_M_impl._M_end_of_storage, 01024 __x._M_impl._M_end_of_storage); 01025 01026 // _GLIBCXX_RESOLVE_LIB_DEFECTS 01027 // 431. Swapping containers with unequal allocators. 01028 std::__alloc_swap<_Tp_alloc_type>::_S_do_it(_M_get_Tp_allocator(), 01029 __x._M_get_Tp_allocator()); 01030 } 01031 01032 /** 01033 * Erases all the elements. Note that this function only erases the 01034 * elements, and that if the elements themselves are pointers, the 01035 * pointed-to memory is not touched in any way. Managing the pointer is 01036 * the user's responsibility. 01037 */ 01038 void 01039 clear() 01040 { _M_erase_at_end(this->_M_impl._M_start); } 01041 01042 protected: 01043 /** 01044 * Memory expansion handler. Uses the member allocation function to 01045 * obtain @a n bytes of memory, and then copies [first,last) into it. 01046 */ 01047 template<typename _ForwardIterator> 01048 pointer 01049 _M_allocate_and_copy(size_type __n, 01050 _ForwardIterator __first, _ForwardIterator __last) 01051 { 01052 pointer __result = this->_M_allocate(__n); 01053 __try 01054 { 01055 std::__uninitialized_copy_a(__first, __last, __result, 01056 _M_get_Tp_allocator()); 01057 return __result; 01058 } 01059 __catch(...) 01060 { 01061 _M_deallocate(__result, __n); 01062 __throw_exception_again; 01063 } 01064 } 01065 01066 01067 // Internal constructor functions follow. 01068 01069 // Called by the range constructor to implement [23.1.1]/9 01070 01071 // _GLIBCXX_RESOLVE_LIB_DEFECTS 01072 // 438. Ambiguity in the "do the right thing" clause 01073 template<typename _Integer> 01074 void 01075 _M_initialize_dispatch(_Integer __n, _Integer __value, __true_type) 01076 { 01077 this->_M_impl._M_start = _M_allocate(static_cast<size_type>(__n)); 01078 this->_M_impl._M_end_of_storage = 01079 this->_M_impl._M_start + static_cast<size_type>(__n); 01080 _M_fill_initialize(static_cast<size_type>(__n), __value); 01081 } 01082 01083 // Called by the range constructor to implement [23.1.1]/9 01084 template<typename _InputIterator> 01085 void 01086 _M_initialize_dispatch(_InputIterator __first, _InputIterator __last, 01087 __false_type) 01088 { 01089 typedef typename std::iterator_traits<_InputIterator>:: 01090 iterator_category _IterCategory; 01091 _M_range_initialize(__first, __last, _IterCategory()); 01092 } 01093 01094 // Called by the second initialize_dispatch above 01095 template<typename _InputIterator> 01096 void 01097 _M_range_initialize(_InputIterator __first, 01098 _InputIterator __last, std::input_iterator_tag) 01099 { 01100 for (; __first != __last; ++__first) 01101 push_back(*__first); 01102 } 01103 01104 // Called by the second initialize_dispatch above 01105 template<typename _ForwardIterator> 01106 void 01107 _M_range_initialize(_ForwardIterator __first, 01108 _ForwardIterator __last, std::forward_iterator_tag) 01109 { 01110 const size_type __n = std::distance(__first, __last); 01111 this->_M_impl._M_start = this->_M_allocate(__n); 01112 this->_M_impl._M_end_of_storage = this->_M_impl._M_start + __n; 01113 this->_M_impl._M_finish = 01114 std::__uninitialized_copy_a(__first, __last, 01115 this->_M_impl._M_start, 01116 _M_get_Tp_allocator()); 01117 } 01118 01119 // Called by the first initialize_dispatch above and by the 01120 // vector(n,value,a) constructor. 01121 void 01122 _M_fill_initialize(size_type __n, const value_type& __value) 01123 { 01124 std::__uninitialized_fill_n_a(this->_M_impl._M_start, __n, __value, 01125 _M_get_Tp_allocator()); 01126 this->_M_impl._M_finish = this->_M_impl._M_end_of_storage; 01127 } 01128 01129 #ifdef __GXX_EXPERIMENTAL_CXX0X__ 01130 // Called by the vector(n) constructor. 01131 void 01132 _M_default_initialize(size_type __n) 01133 { 01134 std::__uninitialized_default_n_a(this->_M_impl._M_start, __n, 01135 _M_get_Tp_allocator()); 01136 this->_M_impl._M_finish = this->_M_impl._M_end_of_storage; 01137 } 01138 #endif 01139 01140 // Internal assign functions follow. The *_aux functions do the actual 01141 // assignment work for the range versions. 01142 01143 // Called by the range assign to implement [23.1.1]/9 01144 01145 // _GLIBCXX_RESOLVE_LIB_DEFECTS 01146 // 438. Ambiguity in the "do the right thing" clause 01147 template<typename _Integer> 01148 void 01149 _M_assign_dispatch(_Integer __n, _Integer __val, __true_type) 01150 { _M_fill_assign(__n, __val); } 01151 01152 // Called by the range assign to implement [23.1.1]/9 01153 template<typename _InputIterator> 01154 void 01155 _M_assign_dispatch(_InputIterator __first, _InputIterator __last, 01156 __false_type) 01157 { 01158 typedef typename std::iterator_traits<_InputIterator>:: 01159 iterator_category _IterCategory; 01160 _M_assign_aux(__first, __last, _IterCategory()); 01161 } 01162 01163 // Called by the second assign_dispatch above 01164 template<typename _InputIterator> 01165 void 01166 _M_assign_aux(_InputIterator __first, _InputIterator __last, 01167 std::input_iterator_tag); 01168 01169 // Called by the second assign_dispatch above 01170 template<typename _ForwardIterator> 01171 void 01172 _M_assign_aux(_ForwardIterator __first, _ForwardIterator __last, 01173 std::forward_iterator_tag); 01174 01175 // Called by assign(n,t), and the range assign when it turns out 01176 // to be the same thing. 01177 void 01178 _M_fill_assign(size_type __n, const value_type& __val); 01179 01180 01181 // Internal insert functions follow. 01182 01183 // Called by the range insert to implement [23.1.1]/9 01184 01185 // _GLIBCXX_RESOLVE_LIB_DEFECTS 01186 // 438. Ambiguity in the "do the right thing" clause 01187 template<typename _Integer> 01188 void 01189 _M_insert_dispatch(iterator __pos, _Integer __n, _Integer __val, 01190 __true_type) 01191 { _M_fill_insert(__pos, __n, __val); } 01192 01193 // Called by the range insert to implement [23.1.1]/9 01194 template<typename _InputIterator> 01195 void 01196 _M_insert_dispatch(iterator __pos, _InputIterator __first, 01197 _InputIterator __last, __false_type) 01198 { 01199 typedef typename std::iterator_traits<_InputIterator>:: 01200 iterator_category _IterCategory; 01201 _M_range_insert(__pos, __first, __last, _IterCategory()); 01202 } 01203 01204 // Called by the second insert_dispatch above 01205 template<typename _InputIterator> 01206 void 01207 _M_range_insert(iterator __pos, _InputIterator __first, 01208 _InputIterator __last, std::input_iterator_tag); 01209 01210 // Called by the second insert_dispatch above 01211 template<typename _ForwardIterator> 01212 void 01213 _M_range_insert(iterator __pos, _ForwardIterator __first, 01214 _ForwardIterator __last, std::forward_iterator_tag); 01215 01216 // Called by insert(p,n,x), and the range insert when it turns out to be 01217 // the same thing. 01218 void 01219 _M_fill_insert(iterator __pos, size_type __n, const value_type& __x); 01220 01221 #ifdef __GXX_EXPERIMENTAL_CXX0X__ 01222 // Called by resize(n). 01223 void 01224 _M_default_append(size_type __n); 01225 #endif 01226 01227 // Called by insert(p,x) 01228 #ifndef __GXX_EXPERIMENTAL_CXX0X__ 01229 void 01230 _M_insert_aux(iterator __position, const value_type& __x); 01231 #else 01232 template<typename... _Args> 01233 void 01234 _M_insert_aux(iterator __position, _Args&&... __args); 01235 #endif 01236 01237 // Called by the latter. 01238 size_type 01239 _M_check_len(size_type __n, const char* __s) const 01240 { 01241 if (max_size() - size() < __n) 01242 __throw_length_error(__N(__s)); 01243 01244 const size_type __len = size() + std::max(size(), __n); 01245 return (__len < size() || __len > max_size()) ? max_size() : __len; 01246 } 01247 01248 // Internal erase functions follow. 01249 01250 // Called by erase(q1,q2), clear(), resize(), _M_fill_assign, 01251 // _M_assign_aux. 01252 void 01253 _M_erase_at_end(pointer __pos) 01254 { 01255 std::_Destroy(__pos, this->_M_impl._M_finish, _M_get_Tp_allocator()); 01256 this->_M_impl._M_finish = __pos; 01257 } 01258 }; 01259 01260 01261 /** 01262 * @brief Vector equality comparison. 01263 * @param x A %vector. 01264 * @param y A %vector of the same type as @a x. 01265 * @return True iff the size and elements of the vectors are equal. 01266 * 01267 * This is an equivalence relation. It is linear in the size of the 01268 * vectors. Vectors are considered equivalent if their sizes are equal, 01269 * and if corresponding elements compare equal. 01270 */ 01271 template<typename _Tp, typename _Alloc> 01272 inline bool 01273 operator==(const vector<_Tp, _Alloc>& __x, const vector<_Tp, _Alloc>& __y) 01274 { return (__x.size() == __y.size() 01275 && std::equal(__x.begin(), __x.end(), __y.begin())); } 01276 01277 /** 01278 * @brief Vector ordering relation. 01279 * @param x A %vector. 01280 * @param y A %vector of the same type as @a x. 01281 * @return True iff @a x is lexicographically less than @a y. 01282 * 01283 * This is a total ordering relation. It is linear in the size of the 01284 * vectors. The elements must be comparable with @c <. 01285 * 01286 * See std::lexicographical_compare() for how the determination is made. 01287 */ 01288 template<typename _Tp, typename _Alloc> 01289 inline bool 01290 operator<(const vector<_Tp, _Alloc>& __x, const vector<_Tp, _Alloc>& __y) 01291 { return std::lexicographical_compare(__x.begin(), __x.end(), 01292 __y.begin(), __y.end()); } 01293 01294 /// Based on operator== 01295 template<typename _Tp, typename _Alloc> 01296 inline bool 01297 operator!=(const vector<_Tp, _Alloc>& __x, const vector<_Tp, _Alloc>& __y) 01298 { return !(__x == __y); } 01299 01300 /// Based on operator< 01301 template<typename _Tp, typename _Alloc> 01302 inline bool 01303 operator>(const vector<_Tp, _Alloc>& __x, const vector<_Tp, _Alloc>& __y) 01304 { return __y < __x; } 01305 01306 /// Based on operator< 01307 template<typename _Tp, typename _Alloc> 01308 inline bool 01309 operator<=(const vector<_Tp, _Alloc>& __x, const vector<_Tp, _Alloc>& __y) 01310 { return !(__y < __x); } 01311 01312 /// Based on operator< 01313 template<typename _Tp, typename _Alloc> 01314 inline bool 01315 operator>=(const vector<_Tp, _Alloc>& __x, const vector<_Tp, _Alloc>& __y) 01316 { return !(__x < __y); } 01317 01318 /// See std::vector::swap(). 01319 template<typename _Tp, typename _Alloc> 01320 inline void 01321 swap(vector<_Tp, _Alloc>& __x, vector<_Tp, _Alloc>& __y) 01322 { __x.swap(__y); } 01323 01324 _GLIBCXX_END_NAMESPACE_CONTAINER 01325 } // namespace std 01326 01327 #endif /* _STL_VECTOR_H */