stl_vector.h

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

Generated on Wed Jun 9 11:19:18 2004 for libstdc++-v3 Source by doxygen 1.3.7