vector.tcc

Go to the documentation of this file.
00001 // Vector implementation (out of line) -*- 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 vector.tcc 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_TCC 00062 #define _VECTOR_TCC 1 00063 00064 namespace _GLIBCXX_STD 00065 { 00066 template<typename _Tp, typename _Alloc> 00067 void 00068 vector<_Tp, _Alloc>:: 00069 reserve(size_type __n) 00070 { 00071 if (__n > this->max_size()) 00072 __throw_length_error(__N("vector::reserve")); 00073 if (this->capacity() < __n) 00074 { 00075 const size_type __old_size = size(); 00076 pointer __tmp = _M_allocate_and_copy(__n, 00077 this->_M_impl._M_start, 00078 this->_M_impl._M_finish); 00079 std::_Destroy(this->_M_impl._M_start, this->_M_impl._M_finish); 00080 _M_deallocate(this->_M_impl._M_start, 00081 this->_M_impl._M_end_of_storage 00082 - this->_M_impl._M_start); 00083 this->_M_impl._M_start = __tmp; 00084 this->_M_impl._M_finish = __tmp + __old_size; 00085 this->_M_impl._M_end_of_storage = this->_M_impl._M_start + __n; 00086 } 00087 } 00088 00089 template<typename _Tp, typename _Alloc> 00090 typename vector<_Tp, _Alloc>::iterator 00091 vector<_Tp, _Alloc>:: 00092 insert(iterator __position, const value_type& __x) 00093 { 00094 size_type __n = __position - begin(); 00095 if (this->_M_impl._M_finish != this->_M_impl._M_end_of_storage 00096 && __position == end()) 00097 { 00098 std::_Construct(this->_M_impl._M_finish, __x); 00099 ++this->_M_impl._M_finish; 00100 } 00101 else 00102 _M_insert_aux(__position, __x); 00103 return begin() + __n; 00104 } 00105 00106 template<typename _Tp, typename _Alloc> 00107 typename vector<_Tp, _Alloc>::iterator 00108 vector<_Tp, _Alloc>:: 00109 erase(iterator __position) 00110 { 00111 if (__position + 1 != end()) 00112 std::copy(__position + 1, end(), __position); 00113 --this->_M_impl._M_finish; 00114 std::_Destroy(this->_M_impl._M_finish); 00115 return __position; 00116 } 00117 00118 template<typename _Tp, typename _Alloc> 00119 typename vector<_Tp, _Alloc>::iterator 00120 vector<_Tp, _Alloc>:: 00121 erase(iterator __first, iterator __last) 00122 { 00123 iterator __i(copy(__last, end(), __first)); 00124 std::_Destroy(__i, end()); 00125 this->_M_impl._M_finish = this->_M_impl._M_finish - (__last - __first); 00126 return __first; 00127 } 00128 00129 template<typename _Tp, typename _Alloc> 00130 vector<_Tp, _Alloc>& 00131 vector<_Tp, _Alloc>:: 00132 operator=(const vector<_Tp, _Alloc>& __x) 00133 { 00134 if (&__x != this) 00135 { 00136 const size_type __xlen = __x.size(); 00137 if (__xlen > capacity()) 00138 { 00139 pointer __tmp = _M_allocate_and_copy(__xlen, __x.begin(), 00140 __x.end()); 00141 std::_Destroy(this->_M_impl._M_start, 00142 this->_M_impl._M_finish); 00143 _M_deallocate(this->_M_impl._M_start, 00144 this->_M_impl._M_end_of_storage 00145 - this->_M_impl._M_start); 00146 this->_M_impl._M_start = __tmp; 00147 this->_M_impl._M_end_of_storage = this->_M_impl._M_start + __xlen; 00148 } 00149 else if (size() >= __xlen) 00150 { 00151 iterator __i(copy(__x.begin(), __x.end(), begin())); 00152 std::_Destroy(__i, end()); 00153 } 00154 else 00155 { 00156 std::copy(__x.begin(), __x.begin() + size(), 00157 this->_M_impl._M_start); 00158 std::uninitialized_copy(__x.begin() + size(), 00159 __x.end(), this->_M_impl._M_finish); 00160 } 00161 this->_M_impl._M_finish = this->_M_impl._M_start + __xlen; 00162 } 00163 return *this; 00164 } 00165 00166 template<typename _Tp, typename _Alloc> 00167 void 00168 vector<_Tp, _Alloc>:: 00169 _M_fill_assign(size_t __n, const value_type& __val) 00170 { 00171 if (__n > capacity()) 00172 { 00173 vector __tmp(__n, __val, get_allocator()); 00174 __tmp.swap(*this); 00175 } 00176 else if (__n > size()) 00177 { 00178 std::fill(begin(), end(), __val); 00179 this->_M_impl._M_finish = std::uninitialized_fill_n(this-> 00180 _M_impl._M_finish, 00181 __n - size(), 00182 __val); 00183 } 00184 else 00185 erase(fill_n(begin(), __n, __val), end()); 00186 } 00187 00188 template<typename _Tp, typename _Alloc> 00189 template<typename _InputIterator> 00190 void 00191 vector<_Tp, _Alloc>:: 00192 _M_assign_aux(_InputIterator __first, _InputIterator __last, 00193 input_iterator_tag) 00194 { 00195 iterator __cur(begin()); 00196 for ( ; __first != __last && __cur != end(); ++__cur, ++__first) 00197 *__cur = *__first; 00198 if (__first == __last) 00199 erase(__cur, end()); 00200 else 00201 insert(end(), __first, __last); 00202 } 00203 00204 template<typename _Tp, typename _Alloc> 00205 template<typename _ForwardIterator> 00206 void 00207 vector<_Tp,_Alloc>:: 00208 _M_assign_aux(_ForwardIterator __first, _ForwardIterator __last, 00209 forward_iterator_tag) 00210 { 00211 size_type __len = std::distance(__first, __last); 00212 00213 if (__len > capacity()) 00214 { 00215 pointer __tmp(_M_allocate_and_copy(__len, __first, __last)); 00216 std::_Destroy(this->_M_impl._M_start, this->_M_impl._M_finish); 00217 _M_deallocate(this->_M_impl._M_start, 00218 this->_M_impl._M_end_of_storage 00219 - this->_M_impl._M_start); 00220 this->_M_impl._M_start = __tmp; 00221 this->_M_impl._M_finish = this->_M_impl._M_start + __len; 00222 this->_M_impl._M_end_of_storage = this->_M_impl._M_finish; 00223 } 00224 else if (size() >= __len) 00225 { 00226 iterator __new_finish(copy(__first, __last, 00227 this->_M_impl._M_start)); 00228 std::_Destroy(__new_finish, end()); 00229 this->_M_impl._M_finish = __new_finish.base(); 00230 } 00231 else 00232 { 00233 _ForwardIterator __mid = __first; 00234 std::advance(__mid, size()); 00235 std::copy(__first, __mid, this->_M_impl._M_start); 00236 this->_M_impl._M_finish = std::uninitialized_copy(__mid, 00237 __last, 00238 this->_M_impl. 00239 _M_finish); 00240 } 00241 } 00242 00243 template<typename _Tp, typename _Alloc> 00244 void 00245 vector<_Tp,_Alloc>:: 00246 _M_insert_aux(iterator __position, const _Tp& __x) 00247 { 00248 if (this->_M_impl._M_finish != this->_M_impl._M_end_of_storage) 00249 { 00250 std::_Construct(this->_M_impl._M_finish, 00251 *(this->_M_impl._M_finish - 1)); 00252 ++this->_M_impl._M_finish; 00253 _Tp __x_copy = __x; 00254 std::copy_backward(__position, 00255 iterator(this->_M_impl._M_finish-2), 00256 iterator(this->_M_impl._M_finish-1)); 00257 *__position = __x_copy; 00258 } 00259 else 00260 { 00261 const size_type __old_size = size(); 00262 const size_type __len = __old_size != 0 ? 2 * __old_size : 1; 00263 iterator __new_start(this->_M_allocate(__len)); 00264 iterator __new_finish(__new_start); 00265 try 00266 { 00267 __new_finish = std::uninitialized_copy(iterator(this-> 00268 _M_impl._M_start), 00269 __position, 00270 __new_start); 00271 std::_Construct(__new_finish.base(), __x); 00272 ++__new_finish; 00273 __new_finish = std::uninitialized_copy(__position, 00274 iterator(this->_M_impl. 00275 _M_finish), 00276 __new_finish); 00277 } 00278 catch(...) 00279 { 00280 std::_Destroy(__new_start,__new_finish); 00281 _M_deallocate(__new_start.base(),__len); 00282 __throw_exception_again; 00283 } 00284 std::_Destroy(begin(), end()); 00285 _M_deallocate(this->_M_impl._M_start, 00286 this->_M_impl._M_end_of_storage 00287 - this->_M_impl._M_start); 00288 this->_M_impl._M_start = __new_start.base(); 00289 this->_M_impl._M_finish = __new_finish.base(); 00290 this->_M_impl._M_end_of_storage = __new_start.base() + __len; 00291 } 00292 } 00293 00294 template<typename _Tp, typename _Alloc> 00295 void 00296 vector<_Tp,_Alloc>:: 00297 _M_fill_insert(iterator __position, size_type __n, const value_type& __x) 00298 { 00299 if (__n != 0) 00300 { 00301 if (size_type(this->_M_impl._M_end_of_storage 00302 - this->_M_impl._M_finish) >= __n) 00303 { 00304 value_type __x_copy = __x; 00305 const size_type __elems_after = end() - __position; 00306 iterator __old_finish(this->_M_impl._M_finish); 00307 if (__elems_after > __n) 00308 { 00309 std::uninitialized_copy(this->_M_impl._M_finish - __n, 00310 this->_M_impl._M_finish, 00311 this->_M_impl._M_finish); 00312 this->_M_impl._M_finish += __n; 00313 std::copy_backward(__position, __old_finish - __n, 00314 __old_finish); 00315 std::fill(__position, __position + __n, __x_copy); 00316 } 00317 else 00318 { 00319 std::uninitialized_fill_n(this->_M_impl._M_finish, 00320 __n - __elems_after, 00321 __x_copy); 00322 this->_M_impl._M_finish += __n - __elems_after; 00323 std::uninitialized_copy(__position, __old_finish, 00324 this->_M_impl._M_finish); 00325 this->_M_impl._M_finish += __elems_after; 00326 std::fill(__position, __old_finish, __x_copy); 00327 } 00328 } 00329 else 00330 { 00331 const size_type __old_size = size(); 00332 const size_type __len = __old_size + std::max(__old_size, __n); 00333 iterator __new_start(this->_M_allocate(__len)); 00334 iterator __new_finish(__new_start); 00335 try 00336 { 00337 __new_finish = std::uninitialized_copy(begin(), __position, 00338 __new_start); 00339 __new_finish = std::uninitialized_fill_n(__new_finish, __n, 00340 __x); 00341 __new_finish = std::uninitialized_copy(__position, end(), 00342 __new_finish); 00343 } 00344 catch(...) 00345 { 00346 std::_Destroy(__new_start,__new_finish); 00347 _M_deallocate(__new_start.base(),__len); 00348 __throw_exception_again; 00349 } 00350 std::_Destroy(this->_M_impl._M_start, this->_M_impl._M_finish); 00351 _M_deallocate(this->_M_impl._M_start, 00352 this->_M_impl._M_end_of_storage 00353 - this->_M_impl._M_start); 00354 this->_M_impl._M_start = __new_start.base(); 00355 this->_M_impl._M_finish = __new_finish.base(); 00356 this->_M_impl._M_end_of_storage = __new_start.base() + __len; 00357 } 00358 } 00359 } 00360 00361 template<typename _Tp, typename _Alloc> template<typename _InputIterator> 00362 void 00363 vector<_Tp,_Alloc>:: 00364 _M_range_insert(iterator __pos, _InputIterator __first, 00365 _InputIterator __last, input_iterator_tag) 00366 { 00367 for ( ; __first != __last; ++__first) 00368 { 00369 __pos = insert(__pos, *__first); 00370 ++__pos; 00371 } 00372 } 00373 00374 template<typename _Tp, typename _Alloc> 00375 template<typename _ForwardIterator> 00376 void 00377 vector<_Tp,_Alloc>:: 00378 _M_range_insert(iterator __position,_ForwardIterator __first, 00379 _ForwardIterator __last, forward_iterator_tag) 00380 { 00381 if (__first != __last) 00382 { 00383 size_type __n = std::distance(__first, __last); 00384 if (size_type(this->_M_impl._M_end_of_storage 00385 - this->_M_impl._M_finish) >= __n) 00386 { 00387 const size_type __elems_after = end() - __position; 00388 iterator __old_finish(this->_M_impl._M_finish); 00389 if (__elems_after > __n) 00390 { 00391 std::uninitialized_copy(this->_M_impl._M_finish - __n, 00392 this->_M_impl._M_finish, 00393 this->_M_impl._M_finish); 00394 this->_M_impl._M_finish += __n; 00395 std::copy_backward(__position, __old_finish - __n, 00396 __old_finish); 00397 std::copy(__first, __last, __position); 00398 } 00399 else 00400 { 00401 _ForwardIterator __mid = __first; 00402 std::advance(__mid, __elems_after); 00403 std::uninitialized_copy(__mid, __last, 00404 this->_M_impl._M_finish); 00405 this->_M_impl._M_finish += __n - __elems_after; 00406 std::uninitialized_copy(__position, __old_finish, 00407 this->_M_impl._M_finish); 00408 this->_M_impl._M_finish += __elems_after; 00409 std::copy(__first, __mid, __position); 00410 } 00411 } 00412 else 00413 { 00414 const size_type __old_size = size(); 00415 const size_type __len = __old_size + std::max(__old_size, __n); 00416 iterator __new_start(this->_M_allocate(__len)); 00417 iterator __new_finish(__new_start); 00418 try 00419 { 00420 __new_finish = std::uninitialized_copy(iterator(this-> 00421 _M_impl. 00422 _M_start), 00423 __position, 00424 __new_start); 00425 __new_finish = std::uninitialized_copy(__first, __last, 00426 __new_finish); 00427 __new_finish = std::uninitialized_copy(__position, 00428 iterator(this-> 00429 _M_impl. 00430 _M_finish), 00431 __new_finish); 00432 } 00433 catch(...) 00434 { 00435 std::_Destroy(__new_start,__new_finish); 00436 _M_deallocate(__new_start.base(), __len); 00437 __throw_exception_again; 00438 } 00439 std::_Destroy(this->_M_impl._M_start, this->_M_impl._M_finish); 00440 _M_deallocate(this->_M_impl._M_start, 00441 this->_M_impl._M_end_of_storage 00442 - this->_M_impl._M_start); 00443 this->_M_impl._M_start = __new_start.base(); 00444 this->_M_impl._M_finish = __new_finish.base(); 00445 this->_M_impl._M_end_of_storage = __new_start.base() + __len; 00446 } 00447 } 00448 } 00449 } // namespace std 00450 00451 #endif /* _VECTOR_TCC */

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