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