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