00001 // Vector implementation -*- C++ -*- 00002 00003 // Copyright (C) 2001, 2002, 2003, 2004, 2005 Free Software Foundation, Inc. 00004 // 00005 // This file is part of the GNU ISO C++ Library. This library is free 00006 // software; you can redistribute it and/or modify it under the 00007 // terms of the GNU General Public License as published by the 00008 // Free Software Foundation; either version 2, or (at your option) 00009 // any later version. 00010 00011 // This library is distributed in the hope that it will be useful, 00012 // but WITHOUT ANY WARRANTY; without even the implied warranty of 00013 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 00014 // GNU General Public License for more details. 00015 00016 // You should have received a copy of the GNU General Public License along 00017 // with this library; see the file COPYING. If not, write to the Free 00018 // Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, 00019 // USA. 00020 00021 // As a special exception, you may use this file as part of a free software 00022 // library without restriction. Specifically, if other files instantiate 00023 // templates or use macros or inline functions from this file, or you compile 00024 // this file and link it with other files to produce an executable, this 00025 // file does not by itself cause the resulting executable to be covered by 00026 // the GNU General Public License. This exception does not however 00027 // invalidate any other reasons why the executable file might be covered by 00028 // the GNU General Public License. 00029 00030 /* 00031 * 00032 * Copyright (c) 1994 00033 * Hewlett-Packard Company 00034 * 00035 * Permission to use, copy, modify, distribute and sell this software 00036 * and its documentation for any purpose is hereby granted without fee, 00037 * provided that the above copyright notice appear in all copies and 00038 * that both that copyright notice and this permission notice appear 00039 * in supporting documentation. Hewlett-Packard Company makes no 00040 * representations about the suitability of this software for any 00041 * purpose. It is provided "as is" without express or implied warranty. 00042 * 00043 * 00044 * Copyright (c) 1996 00045 * Silicon Graphics Computer Systems, Inc. 00046 * 00047 * Permission to use, copy, modify, distribute and sell this software 00048 * and its documentation for any purpose is hereby granted without fee, 00049 * provided that the above copyright notice appear in all copies and 00050 * that both that copyright notice and this permission notice appear 00051 * in supporting documentation. Silicon Graphics makes no 00052 * representations about the suitability of this software for any 00053 * purpose. It is provided "as is" without express or implied warranty. 00054 */ 00055 00056 /** @file stl_vector.h 00057 * This is an internal header file, included by other library headers. 00058 * You should not attempt to use it directly. 00059 */ 00060 00061 #ifndef _VECTOR_H 00062 #define _VECTOR_H 1 00063 00064 #include <bits/stl_iterator_base_funcs.h> 00065 #include <bits/functexcept.h> 00066 #include <bits/concept_check.h> 00067 00068 namespace _GLIBCXX_STD 00069 { 00070 /** 00071 * @if maint 00072 * See bits/stl_deque.h's _Deque_base for an explanation. 00073 * @endif 00074 */ 00075 template<typename _Tp, typename _Alloc> 00076 struct _Vector_base 00077 { 00078 typedef typename _Alloc::template rebind<_Tp>::other _Tp_alloc_type; 00079 00080 struct _Vector_impl 00081 : public _Tp_alloc_type 00082 { 00083 _Tp* _M_start; 00084 _Tp* _M_finish; 00085 _Tp* _M_end_of_storage; 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 _M_get_Tp_allocator(); } 00105 00106 _Vector_base(const allocator_type& __a) 00107 : _M_impl(__a) 00108 { } 00109 00110 _Vector_base(size_t __n, const allocator_type& __a) 00111 : _M_impl(__a) 00112 { 00113 this->_M_impl._M_start = this->_M_allocate(__n); 00114 this->_M_impl._M_finish = this->_M_impl._M_start; 00115 this->_M_impl._M_end_of_storage = this->_M_impl._M_start + __n; 00116 } 00117 00118 ~_Vector_base() 00119 { _M_deallocate(this->_M_impl._M_start, this->_M_impl._M_end_of_storage 00120 - this->_M_impl._M_start); } 00121 00122 public: 00123 _Vector_impl _M_impl; 00124 00125 _Tp* 00126 _M_allocate(size_t __n) 00127 { return _M_impl.allocate(__n); } 00128 00129 void 00130 _M_deallocate(_Tp* __p, size_t __n) 00131 { 00132 if (__p) 00133 _M_impl.deallocate(__p, __n); 00134 } 00135 }; 00136 00137 00138 /** 00139 * @brief A standard container which offers fixed time access to 00140 * individual elements in any order. 00141 * 00142 * @ingroup Containers 00143 * @ingroup Sequences 00144 * 00145 * Meets the requirements of a <a href="tables.html#65">container</a>, a 00146 * <a href="tables.html#66">reversible container</a>, and a 00147 * <a href="tables.html#67">sequence</a>, including the 00148 * <a href="tables.html#68">optional sequence requirements</a> with the 00149 * %exception of @c push_front and @c pop_front. 00150 * 00151 * In some terminology a %vector can be described as a dynamic 00152 * C-style array, it offers fast and efficient access to individual 00153 * elements in any order and saves the user from worrying about 00154 * memory and size allocation. Subscripting ( @c [] ) access is 00155 * also provided as with C-style arrays. 00156 */ 00157 template<typename _Tp, typename _Alloc = std::allocator<_Tp> > 00158 class vector : protected _Vector_base<_Tp, _Alloc> 00159 { 00160 // Concept requirements. 00161 typedef typename _Alloc::value_type _Alloc_value_type; 00162 __glibcxx_class_requires(_Tp, _SGIAssignableConcept) 00163 __glibcxx_class_requires2(_Tp, _Alloc_value_type, _SameTypeConcept) 00164 00165 typedef _Vector_base<_Tp, _Alloc> _Base; 00166 typedef vector<_Tp, _Alloc> vector_type; 00167 typedef typename _Base::_Tp_alloc_type _Tp_alloc_type; 00168 00169 public: 00170 typedef _Tp value_type; 00171 typedef typename _Tp_alloc_type::pointer pointer; 00172 typedef typename _Tp_alloc_type::const_pointer const_pointer; 00173 typedef typename _Tp_alloc_type::reference reference; 00174 typedef typename _Tp_alloc_type::const_reference const_reference; 00175 typedef __gnu_cxx::__normal_iterator<pointer, vector_type> iterator; 00176 typedef __gnu_cxx::__normal_iterator<const_pointer, vector_type> 00177 const_iterator; 00178 typedef std::reverse_iterator<const_iterator> const_reverse_iterator; 00179 typedef std::reverse_iterator<iterator> reverse_iterator; 00180 typedef size_t size_type; 00181 typedef ptrdiff_t difference_type; 00182 typedef _Alloc allocator_type; 00183 00184 protected: 00185 /** @if maint 00186 * These two functions and three data members are all from the 00187 * base class. They should be pretty self-explanatory, as 00188 * %vector uses a simple contiguous allocation scheme. @endif 00189 */ 00190 using _Base::_M_allocate; 00191 using _Base::_M_deallocate; 00192 using _Base::_M_impl; 00193 using _Base::_M_get_Tp_allocator; 00194 00195 public: 00196 // [23.2.4.1] construct/copy/destroy 00197 // (assign() and get_allocator() are also listed in this section) 00198 /** 00199 * @brief Default constructor creates no elements. 00200 */ 00201 explicit 00202 vector(const allocator_type& __a = allocator_type()) 00203 : _Base(__a) 00204 { } 00205 00206 /** 00207 * @brief Create a %vector with copies of an exemplar element. 00208 * @param n The number of elements to initially create. 00209 * @param value An element to copy. 00210 * 00211 * This constructor fills the %vector with @a n copies of @a value. 00212 */ 00213 explicit 00214 vector(size_type __n, const value_type& __value = value_type(), 00215 const allocator_type& __a = allocator_type()) 00216 : _Base(__n, __a) 00217 { 00218 std::__uninitialized_fill_n_a(this->_M_impl._M_start, __n, __value, 00219 _M_get_Tp_allocator()); 00220 this->_M_impl._M_finish = this->_M_impl._M_start + __n; 00221 } 00222 00223 /** 00224 * @brief %Vector copy constructor. 00225 * @param x A %vector of identical element and allocator types. 00226 * 00227 * The newly-created %vector uses a copy of the allocation 00228 * object used by @a x. All the elements of @a x are copied, 00229 * but any extra memory in 00230 * @a x (for fast expansion) will not be copied. 00231 */ 00232 vector(const vector& __x) 00233 : _Base(__x.size(), __x.get_allocator()) 00234 { this->_M_impl._M_finish = 00235 std::__uninitialized_copy_a(__x.begin(), __x.end(), 00236 this->_M_impl._M_start, 00237 _M_get_Tp_allocator()); 00238 } 00239 00240 /** 00241 * @brief Builds a %vector from a range. 00242 * @param first An input iterator. 00243 * @param last An input iterator. 00244 * 00245 * Create a %vector consisting of copies of the elements from 00246 * [first,last). 00247 * 00248 * If the iterators are forward, bidirectional, or 00249 * random-access, then this will call the elements' copy 00250 * constructor N times (where N is distance(first,last)) and do 00251 * no memory reallocation. But if only input iterators are 00252 * used, then this will do at most 2N calls to the copy 00253 * constructor, and logN memory reallocations. 00254 */ 00255 template<typename _InputIterator> 00256 vector(_InputIterator __first, _InputIterator __last, 00257 const allocator_type& __a = allocator_type()) 00258 : _Base(__a) 00259 { 00260 // Check whether it's an integral type. If so, it's not an iterator. 00261 typedef typename std::__is_integer<_InputIterator>::__type _Integral; 00262 _M_initialize_dispatch(__first, __last, _Integral()); 00263 } 00264 00265 /** 00266 * The dtor only erases the elements, and note that if the 00267 * elements themselves are pointers, the pointed-to memory is 00268 * not touched in any way. Managing the pointer is the user's 00269 * responsibilty. 00270 */ 00271 ~vector() 00272 { std::_Destroy(this->_M_impl._M_start, this->_M_impl._M_finish, 00273 _M_get_Tp_allocator()); 00274 } 00275 00276 /** 00277 * @brief %Vector assignment operator. 00278 * @param x A %vector of identical element and allocator types. 00279 * 00280 * All the elements of @a x are copied, but any extra memory in 00281 * @a x (for fast expansion) will not be copied. Unlike the 00282 * copy constructor, the allocator object is not copied. 00283 */ 00284 vector& 00285 operator=(const vector& __x); 00286 00287 /** 00288 * @brief Assigns a given value to a %vector. 00289 * @param n Number of elements to be assigned. 00290 * @param val Value to be assigned. 00291 * 00292 * This function fills a %vector with @a n copies of the given 00293 * value. Note that the assignment completely changes the 00294 * %vector and that the resulting %vector's size is the same as 00295 * the number of elements assigned. Old data may be lost. 00296 */ 00297 void 00298 assign(size_type __n, const value_type& __val) 00299 { _M_fill_assign(__n, __val); } 00300 00301 /** 00302 * @brief Assigns a range to a %vector. 00303 * @param first An input iterator. 00304 * @param last An input iterator. 00305 * 00306 * This function fills a %vector with copies of the elements in the 00307 * range [first,last). 00308 * 00309 * Note that the assignment completely changes the %vector and 00310 * that the resulting %vector's size is the same as the number 00311 * of elements assigned. Old data may be lost. 00312 */ 00313 template<typename _InputIterator> 00314 void 00315 assign(_InputIterator __first, _InputIterator __last) 00316 { 00317 // Check whether it's an integral type. If so, it's not an iterator. 00318 typedef typename std::__is_integer<_InputIterator>::__type _Integral; 00319 _M_assign_dispatch(__first, __last, _Integral()); 00320 } 00321 00322 /// Get a copy of the memory allocation object. 00323 using _Base::get_allocator; 00324 00325 // iterators 00326 /** 00327 * Returns a read/write iterator that points to the first 00328 * element in the %vector. Iteration is done in ordinary 00329 * element order. 00330 */ 00331 iterator 00332 begin() 00333 { return iterator (this->_M_impl._M_start); } 00334 00335 /** 00336 * Returns a read-only (constant) iterator that points to the 00337 * first element in the %vector. Iteration is done in ordinary 00338 * element order. 00339 */ 00340 const_iterator 00341 begin() const 00342 { return const_iterator (this->_M_impl._M_start); } 00343 00344 /** 00345 * Returns a read/write iterator that points one past the last 00346 * element in the %vector. Iteration is done in ordinary 00347 * element order. 00348 */ 00349 iterator 00350 end() 00351 { return iterator (this->_M_impl._M_finish); } 00352 00353 /** 00354 * Returns a read-only (constant) iterator that points one past 00355 * the last element in the %vector. Iteration is done in 00356 * ordinary element order. 00357 */ 00358 const_iterator 00359 end() const 00360 { return const_iterator (this->_M_impl._M_finish); } 00361 00362 /** 00363 * Returns a read/write reverse iterator that points to the 00364 * last element in the %vector. Iteration is done in reverse 00365 * element order. 00366 */ 00367 reverse_iterator 00368 rbegin() 00369 { return reverse_iterator(end()); } 00370 00371 /** 00372 * Returns a read-only (constant) reverse iterator that points 00373 * to the last element in the %vector. Iteration is done in 00374 * reverse element order. 00375 */ 00376 const_reverse_iterator 00377 rbegin() const 00378 { return const_reverse_iterator(end()); } 00379 00380 /** 00381 * Returns a read/write reverse iterator that points to one 00382 * before the first element in the %vector. Iteration is done 00383 * in reverse element order. 00384 */ 00385 reverse_iterator 00386 rend() 00387 { return reverse_iterator(begin()); } 00388 00389 /** 00390 * Returns a read-only (constant) reverse iterator that points 00391 * to one before the first element in the %vector. Iteration 00392 * is done in reverse element order. 00393 */ 00394 const_reverse_iterator 00395 rend() const 00396 { return const_reverse_iterator(begin()); } 00397 00398 // [23.2.4.2] capacity 00399 /** Returns the number of elements in the %vector. */ 00400 size_type 00401 size() const 00402 { return size_type(end() - begin()); } 00403 00404 /** Returns the size() of the largest possible %vector. */ 00405 size_type 00406 max_size() const 00407 { return size_type(-1) / sizeof(value_type); } 00408 00409 /** 00410 * @brief Resizes the %vector to the specified number of elements. 00411 * @param new_size Number of elements the %vector should contain. 00412 * @param x Data with which new elements should be populated. 00413 * 00414 * This function will %resize the %vector to the specified 00415 * number of elements. If the number is smaller than the 00416 * %vector's current size the %vector is truncated, otherwise 00417 * the %vector is extended and new elements are populated with 00418 * given data. 00419 */ 00420 void 00421 resize(size_type __new_size, value_type __x = value_type()) 00422 { 00423 if (__new_size < size()) 00424 erase(begin() + __new_size, end()); 00425 else 00426 insert(end(), __new_size - size(), __x); 00427 } 00428 00429 /** 00430 * Returns the total number of elements that the %vector can 00431 * hold before needing to allocate more memory. 00432 */ 00433 size_type 00434 capacity() const 00435 { return size_type(const_iterator(this->_M_impl._M_end_of_storage) 00436 - begin()); } 00437 00438 /** 00439 * Returns true if the %vector is empty. (Thus begin() would 00440 * equal end().) 00441 */ 00442 bool 00443 empty() const 00444 { return begin() == end(); } 00445 00446 /** 00447 * @brief Attempt to preallocate enough memory for specified number of 00448 * elements. 00449 * @param n Number of elements required. 00450 * @throw std::length_error If @a n exceeds @c max_size(). 00451 * 00452 * This function attempts to reserve enough memory for the 00453 * %vector to hold the specified number of elements. If the 00454 * number requested is more than max_size(), length_error is 00455 * thrown. 00456 * 00457 * The advantage of this function is that if optimal code is a 00458 * necessity and the user can determine the number of elements 00459 * that will be required, the user can reserve the memory in 00460 * %advance, and thus prevent a possible reallocation of memory 00461 * and copying of %vector data. 00462 */ 00463 void 00464 reserve(size_type __n); 00465 00466 // element access 00467 /** 00468 * @brief Subscript access to the data contained in the %vector. 00469 * @param n The index of the element for which data should be 00470 * accessed. 00471 * @return Read/write reference to data. 00472 * 00473 * This operator allows for easy, array-style, data access. 00474 * Note that data access with this operator is unchecked and 00475 * out_of_range lookups are not defined. (For checked lookups 00476 * see at().) 00477 */ 00478 reference 00479 operator[](size_type __n) 00480 { return *(begin() + __n); } 00481 00482 /** 00483 * @brief Subscript access to the data contained in the %vector. 00484 * @param n The index of the element for which data should be 00485 * accessed. 00486 * @return Read-only (constant) reference to data. 00487 * 00488 * This operator allows for easy, array-style, data access. 00489 * Note that data access with this operator is unchecked and 00490 * out_of_range lookups are not defined. (For checked lookups 00491 * see at().) 00492 */ 00493 const_reference 00494 operator[](size_type __n) const 00495 { return *(begin() + __n); } 00496 00497 protected: 00498 /// @if maint Safety check used only from at(). @endif 00499 void 00500 _M_range_check(size_type __n) const 00501 { 00502 if (__n >= this->size()) 00503 __throw_out_of_range(__N("vector::_M_range_check")); 00504 } 00505 00506 public: 00507 /** 00508 * @brief Provides access to the data contained in the %vector. 00509 * @param n The index of the element for which data should be 00510 * accessed. 00511 * @return Read/write reference to data. 00512 * @throw std::out_of_range If @a n is an invalid index. 00513 * 00514 * This function provides for safer data access. The parameter 00515 * is first checked that it is in the range of the vector. The 00516 * function throws out_of_range if the check fails. 00517 */ 00518 reference 00519 at(size_type __n) 00520 { 00521 _M_range_check(__n); 00522 return (*this)[__n]; 00523 } 00524 00525 /** 00526 * @brief Provides access to the data contained in the %vector. 00527 * @param n The index of the element for which data should be 00528 * accessed. 00529 * @return Read-only (constant) reference to data. 00530 * @throw std::out_of_range If @a n is an invalid index. 00531 * 00532 * This function provides for safer data access. The parameter 00533 * is first checked that it is in the range of the vector. The 00534 * function throws out_of_range if the check fails. 00535 */ 00536 const_reference 00537 at(size_type __n) const 00538 { 00539 _M_range_check(__n); 00540 return (*this)[__n]; 00541 } 00542 00543 /** 00544 * Returns a read/write reference to the data at the first 00545 * element of the %vector. 00546 */ 00547 reference 00548 front() 00549 { return *begin(); } 00550 00551 /** 00552 * Returns a read-only (constant) reference to the data at the first 00553 * element of the %vector. 00554 */ 00555 const_reference 00556 front() const 00557 { return *begin(); } 00558 00559 /** 00560 * Returns a read/write reference to the data at the last 00561 * element of the %vector. 00562 */ 00563 reference 00564 back() 00565 { return *(end() - 1); } 00566 00567 /** 00568 * Returns a read-only (constant) reference to the data at the 00569 * last element of the %vector. 00570 */ 00571 const_reference 00572 back() const 00573 { return *(end() - 1); } 00574 00575 // _GLIBCXX_RESOLVE_LIB_DEFECTS 00576 // DR 464. Suggestion for new member functions in standard containers. 00577 // data access 00578 /** 00579 * Returns a pointer such that [data(), data() + size()) is a valid 00580 * range. For a non-empty %vector, data() == &front(). 00581 */ 00582 pointer 00583 data() 00584 { return pointer(this->_M_impl._M_start); } 00585 00586 const_pointer 00587 data() const 00588 { return const_pointer(this->_M_impl._M_start); } 00589 00590 // [23.2.4.3] modifiers 00591 /** 00592 * @brief Add data to the end of the %vector. 00593 * @param x Data to be added. 00594 * 00595 * This is a typical stack operation. The function creates an 00596 * element at the end of the %vector and assigns the given data 00597 * to it. Due to the nature of a %vector this operation can be 00598 * done in constant time if the %vector has preallocated space 00599 * available. 00600 */ 00601 void 00602 push_back(const value_type& __x) 00603 { 00604 if (this->_M_impl._M_finish != this->_M_impl._M_end_of_storage) 00605 { 00606 this->_M_impl.construct(this->_M_impl._M_finish, __x); 00607 ++this->_M_impl._M_finish; 00608 } 00609 else 00610 _M_insert_aux(end(), __x); 00611 } 00612 00613 /** 00614 * @brief Removes last element. 00615 * 00616 * This is a typical stack operation. It shrinks the %vector by one. 00617 * 00618 * Note that no data is returned, and if the last element's 00619 * data is needed, it should be retrieved before pop_back() is 00620 * called. 00621 */ 00622 void 00623 pop_back() 00624 { 00625 --this->_M_impl._M_finish; 00626 this->_M_impl.destroy(this->_M_impl._M_finish); 00627 } 00628 00629 /** 00630 * @brief Inserts given value into %vector before specified iterator. 00631 * @param position An iterator into the %vector. 00632 * @param x Data to be inserted. 00633 * @return An iterator that points to the inserted data. 00634 * 00635 * This function will insert a copy of the given value before 00636 * the specified location. Note that this kind of operation 00637 * could be expensive for a %vector and if it is frequently 00638 * used the user should consider using std::list. 00639 */ 00640 iterator 00641 insert(iterator __position, const value_type& __x); 00642 00643 /** 00644 * @brief Inserts a number of copies of given data into the %vector. 00645 * @param position An iterator into the %vector. 00646 * @param n Number of elements to be inserted. 00647 * @param x Data to be inserted. 00648 * 00649 * This function will insert a specified number of copies of 00650 * the given data before the location specified by @a position. 00651 * 00652 * Note that this kind of operation could be expensive for a 00653 * %vector and if it is frequently used the user should 00654 * consider using std::list. 00655 */ 00656 void 00657 insert(iterator __position, size_type __n, const value_type& __x) 00658 { _M_fill_insert(__position, __n, __x); } 00659 00660 /** 00661 * @brief Inserts a range into the %vector. 00662 * @param position An iterator into the %vector. 00663 * @param first An input iterator. 00664 * @param last An input iterator. 00665 * 00666 * This function will insert copies of the data in the range 00667 * [first,last) into the %vector before the location specified 00668 * by @a pos. 00669 * 00670 * Note that this kind of operation could be expensive for a 00671 * %vector and if it is frequently used the user should 00672 * consider using std::list. 00673 */ 00674 template<typename _InputIterator> 00675 void 00676 insert(iterator __position, _InputIterator __first, 00677 _InputIterator __last) 00678 { 00679 // Check whether it's an integral type. If so, it's not an iterator. 00680 typedef typename std::__is_integer<_InputIterator>::__type _Integral; 00681 _M_insert_dispatch(__position, __first, __last, _Integral()); 00682 } 00683 00684 /** 00685 * @brief Remove element at given position. 00686 * @param position Iterator pointing to element to be erased. 00687 * @return An iterator pointing to the next element (or end()). 00688 * 00689 * This function will erase the element at the given position and thus 00690 * shorten the %vector by one. 00691 * 00692 * Note This operation could be expensive and if it is 00693 * frequently used the user should consider using std::list. 00694 * The user is also cautioned that this function only erases 00695 * the element, and that if the element is itself a pointer, 00696 * the pointed-to memory is not touched in any way. Managing 00697 * the pointer is the user's responsibilty. 00698 */ 00699 iterator 00700 erase(iterator __position); 00701 00702 /** 00703 * @brief Remove a range of elements. 00704 * @param first Iterator pointing to the first element to be erased. 00705 * @param last Iterator pointing to one past the last element to be 00706 * erased. 00707 * @return An iterator pointing to the element pointed to by @a last 00708 * prior to erasing (or end()). 00709 * 00710 * This function will erase the elements in the range [first,last) and 00711 * shorten the %vector accordingly. 00712 * 00713 * Note This operation could be expensive and if it is 00714 * frequently used the user should consider using std::list. 00715 * The user is also cautioned that this function only erases 00716 * the elements, and that if the elements themselves are 00717 * pointers, the pointed-to memory is not touched in any way. 00718 * Managing the pointer is the user's responsibilty. 00719 */ 00720 iterator 00721 erase(iterator __first, iterator __last); 00722 00723 /** 00724 * @brief Swaps data with another %vector. 00725 * @param x A %vector of the same element and allocator types. 00726 * 00727 * This exchanges the elements between two vectors in constant time. 00728 * (Three pointers, so it should be quite fast.) 00729 * Note that the global std::swap() function is specialized such that 00730 * std::swap(v1,v2) will feed to this function. 00731 */ 00732 void 00733 swap(vector& __x) 00734 { 00735 std::swap(this->_M_impl._M_start, __x._M_impl._M_start); 00736 std::swap(this->_M_impl._M_finish, __x._M_impl._M_finish); 00737 std::swap(this->_M_impl._M_end_of_storage, 00738 __x._M_impl._M_end_of_storage); 00739 } 00740 00741 /** 00742 * Erases all the elements. Note that this function only erases the 00743 * elements, and that if the elements themselves are pointers, the 00744 * pointed-to memory is not touched in any way. Managing the pointer is 00745 * the user's responsibilty. 00746 */ 00747 void 00748 clear() 00749 { 00750 std::_Destroy(this->_M_impl._M_start, this->_M_impl._M_finish, 00751 _M_get_Tp_allocator()); 00752 this->_M_impl._M_finish = this->_M_impl._M_start; 00753 } 00754 00755 protected: 00756 /** 00757 * @if maint 00758 * Memory expansion handler. Uses the member allocation function to 00759 * obtain @a n bytes of memory, and then copies [first,last) into it. 00760 * @endif 00761 */ 00762 template<typename _ForwardIterator> 00763 pointer 00764 _M_allocate_and_copy(size_type __n, 00765 _ForwardIterator __first, _ForwardIterator __last) 00766 { 00767 pointer __result = this->_M_allocate(__n); 00768 try 00769 { 00770 std::__uninitialized_copy_a(__first, __last, __result, 00771 _M_get_Tp_allocator()); 00772 return __result; 00773 } 00774 catch(...) 00775 { 00776 _M_deallocate(__result, __n); 00777 __throw_exception_again; 00778 } 00779 } 00780 00781 00782 // Internal constructor functions follow. 00783 00784 // Called by the range constructor to implement [23.1.1]/9 00785 template<typename _Integer> 00786 void 00787 _M_initialize_dispatch(_Integer __n, _Integer __value, __true_type) 00788 { 00789 this->_M_impl._M_start = _M_allocate(__n); 00790 this->_M_impl._M_end_of_storage = this->_M_impl._M_start + __n; 00791 std::__uninitialized_fill_n_a(this->_M_impl._M_start, __n, __value, 00792 _M_get_Tp_allocator()); 00793 this->_M_impl._M_finish = this->_M_impl._M_end_of_storage; 00794 } 00795 00796 // Called by the range constructor to implement [23.1.1]/9 00797 template<typename _InputIterator> 00798 void 00799 _M_initialize_dispatch(_InputIterator __first, _InputIterator __last, 00800 __false_type) 00801 { 00802 typedef typename std::iterator_traits<_InputIterator>:: 00803 iterator_category _IterCategory; 00804 _M_range_initialize(__first, __last, _IterCategory()); 00805 } 00806 00807 // Called by the second initialize_dispatch above 00808 template<typename _InputIterator> 00809 void 00810 _M_range_initialize(_InputIterator __first, 00811 _InputIterator __last, std::input_iterator_tag) 00812 { 00813 for (; __first != __last; ++__first) 00814 push_back(*__first); 00815 } 00816 00817 // Called by the second initialize_dispatch above 00818 template<typename _ForwardIterator> 00819 void 00820 _M_range_initialize(_ForwardIterator __first, 00821 _ForwardIterator __last, std::forward_iterator_tag) 00822 { 00823 const size_type __n = std::distance(__first, __last); 00824 this->_M_impl._M_start = this->_M_allocate(__n); 00825 this->_M_impl._M_end_of_storage = this->_M_impl._M_start + __n; 00826 this->_M_impl._M_finish = 00827 std::__uninitialized_copy_a(__first, __last, 00828 this->_M_impl._M_start, 00829 _M_get_Tp_allocator()); 00830 } 00831 00832 00833 // Internal assign functions follow. The *_aux functions do the actual 00834 // assignment work for the range versions. 00835 00836 // Called by the range assign to implement [23.1.1]/9 00837 template<typename _Integer> 00838 void 00839 _M_assign_dispatch(_Integer __n, _Integer __val, __true_type) 00840 { 00841 _M_fill_assign(static_cast<size_type>(__n), 00842 static_cast<value_type>(__val)); 00843 } 00844 00845 // Called by the range assign to implement [23.1.1]/9 00846 template<typename _InputIterator> 00847 void 00848 _M_assign_dispatch(_InputIterator __first, _InputIterator __last, 00849 __false_type) 00850 { 00851 typedef typename std::iterator_traits<_InputIterator>:: 00852 iterator_category _IterCategory; 00853 _M_assign_aux(__first, __last, _IterCategory()); 00854 } 00855 00856 // Called by the second assign_dispatch above 00857 template<typename _InputIterator> 00858 void 00859 _M_assign_aux(_InputIterator __first, _InputIterator __last, 00860 std::input_iterator_tag); 00861 00862 // Called by the second assign_dispatch above 00863 template<typename _ForwardIterator> 00864 void 00865 _M_assign_aux(_ForwardIterator __first, _ForwardIterator __last, 00866 std::forward_iterator_tag); 00867 00868 // Called by assign(n,t), and the range assign when it turns out 00869 // to be the same thing. 00870 void 00871 _M_fill_assign(size_type __n, const value_type& __val); 00872 00873 00874 // Internal insert functions follow. 00875 00876 // Called by the range insert to implement [23.1.1]/9 00877 template<typename _Integer> 00878 void 00879 _M_insert_dispatch(iterator __pos, _Integer __n, _Integer __val, 00880 __true_type) 00881 { 00882 _M_fill_insert(__pos, static_cast<size_type>(__n), 00883 static_cast<value_type>(__val)); 00884 } 00885 00886 // Called by the range insert to implement [23.1.1]/9 00887 template<typename _InputIterator> 00888 void 00889 _M_insert_dispatch(iterator __pos, _InputIterator __first, 00890 _InputIterator __last, __false_type) 00891 { 00892 typedef typename std::iterator_traits<_InputIterator>:: 00893 iterator_category _IterCategory; 00894 _M_range_insert(__pos, __first, __last, _IterCategory()); 00895 } 00896 00897 // Called by the second insert_dispatch above 00898 template<typename _InputIterator> 00899 void 00900 _M_range_insert(iterator __pos, _InputIterator __first, 00901 _InputIterator __last, std::input_iterator_tag); 00902 00903 // Called by the second insert_dispatch above 00904 template<typename _ForwardIterator> 00905 void 00906 _M_range_insert(iterator __pos, _ForwardIterator __first, 00907 _ForwardIterator __last, std::forward_iterator_tag); 00908 00909 // Called by insert(p,n,x), and the range insert when it turns out to be 00910 // the same thing. 00911 void 00912 _M_fill_insert(iterator __pos, size_type __n, const value_type& __x); 00913 00914 // Called by insert(p,x) 00915 void 00916 _M_insert_aux(iterator __position, const value_type& __x); 00917 }; 00918 00919 00920 /** 00921 * @brief Vector equality comparison. 00922 * @param x A %vector. 00923 * @param y A %vector of the same type as @a x. 00924 * @return True iff the size and elements of the vectors are equal. 00925 * 00926 * This is an equivalence relation. It is linear in the size of the 00927 * vectors. Vectors are considered equivalent if their sizes are equal, 00928 * and if corresponding elements compare equal. 00929 */ 00930 template<typename _Tp, typename _Alloc> 00931 inline bool 00932 operator==(const vector<_Tp, _Alloc>& __x, const vector<_Tp, _Alloc>& __y) 00933 { return (__x.size() == __y.size() 00934 && std::equal(__x.begin(), __x.end(), __y.begin())); } 00935 00936 /** 00937 * @brief Vector ordering relation. 00938 * @param x A %vector. 00939 * @param y A %vector of the same type as @a x. 00940 * @return True iff @a x is lexicographically less than @a y. 00941 * 00942 * This is a total ordering relation. It is linear in the size of the 00943 * vectors. The elements must be comparable with @c <. 00944 * 00945 * See std::lexicographical_compare() for how the determination is made. 00946 */ 00947 template<typename _Tp, typename _Alloc> 00948 inline bool 00949 operator<(const vector<_Tp, _Alloc>& __x, const vector<_Tp, _Alloc>& __y) 00950 { return std::lexicographical_compare(__x.begin(), __x.end(), 00951 __y.begin(), __y.end()); } 00952 00953 /// Based on operator== 00954 template<typename _Tp, typename _Alloc> 00955 inline bool 00956 operator!=(const vector<_Tp, _Alloc>& __x, const vector<_Tp, _Alloc>& __y) 00957 { return !(__x == __y); } 00958 00959 /// Based on operator< 00960 template<typename _Tp, typename _Alloc> 00961 inline bool 00962 operator>(const vector<_Tp, _Alloc>& __x, const vector<_Tp, _Alloc>& __y) 00963 { return __y < __x; } 00964 00965 /// Based on operator< 00966 template<typename _Tp, typename _Alloc> 00967 inline bool 00968 operator<=(const vector<_Tp, _Alloc>& __x, const vector<_Tp, _Alloc>& __y) 00969 { return !(__y < __x); } 00970 00971 /// Based on operator< 00972 template<typename _Tp, typename _Alloc> 00973 inline bool 00974 operator>=(const vector<_Tp, _Alloc>& __x, const vector<_Tp, _Alloc>& __y) 00975 { return !(__x < __y); } 00976 00977 /// See std::vector::swap(). 00978 template<typename _Tp, typename _Alloc> 00979 inline void 00980 swap(vector<_Tp, _Alloc>& __x, vector<_Tp, _Alloc>& __y) 00981 { __x.swap(__y); } 00982 } // namespace std 00983 00984 #endif /* _VECTOR_H */