vector.tcc

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

Generated on Wed Aug 4 21:43:23 2004 for libstdc++-v3 Source by doxygen 1.3.8