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 const 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 std::uninitialized_fill_n(this->_M_impl._M_finish, 00180 __n - size(), __val); 00181 this->_M_impl._M_finish += __n - size(); 00182 } 00183 else 00184 erase(fill_n(begin(), __n, __val), end()); 00185 } 00186 00187 template<typename _Tp, typename _Alloc> 00188 template<typename _InputIterator> 00189 void 00190 vector<_Tp, _Alloc>:: 00191 _M_assign_aux(_InputIterator __first, _InputIterator __last, 00192 input_iterator_tag) 00193 { 00194 iterator __cur(begin()); 00195 for (; __first != __last && __cur != end(); ++__cur, ++__first) 00196 *__cur = *__first; 00197 if (__first == __last) 00198 erase(__cur, end()); 00199 else 00200 insert(end(), __first, __last); 00201 } 00202 00203 template<typename _Tp, typename _Alloc> 00204 template<typename _ForwardIterator> 00205 void 00206 vector<_Tp, _Alloc>:: 00207 _M_assign_aux(_ForwardIterator __first, _ForwardIterator __last, 00208 forward_iterator_tag) 00209 { 00210 const size_type __len = std::distance(__first, __last); 00211 00212 if (__len > capacity()) 00213 { 00214 pointer __tmp(_M_allocate_and_copy(__len, __first, __last)); 00215 std::_Destroy(this->_M_impl._M_start, this->_M_impl._M_finish); 00216 _M_deallocate(this->_M_impl._M_start, 00217 this->_M_impl._M_end_of_storage 00218 - this->_M_impl._M_start); 00219 this->_M_impl._M_start = __tmp; 00220 this->_M_impl._M_finish = this->_M_impl._M_start + __len; 00221 this->_M_impl._M_end_of_storage = this->_M_impl._M_finish; 00222 } 00223 else if (size() >= __len) 00224 { 00225 iterator __new_finish(copy(__first, __last, 00226 this->_M_impl._M_start)); 00227 std::_Destroy(__new_finish, end()); 00228 this->_M_impl._M_finish = __new_finish.base(); 00229 } 00230 else 00231 { 00232 _ForwardIterator __mid = __first; 00233 std::advance(__mid, size()); 00234 std::copy(__first, __mid, this->_M_impl._M_start); 00235 this->_M_impl._M_finish = std::uninitialized_copy(__mid, 00236 __last, 00237 this->_M_impl. 00238 _M_finish); 00239 } 00240 } 00241 00242 template<typename _Tp, typename _Alloc> 00243 void 00244 vector<_Tp, _Alloc>:: 00245 _M_insert_aux(iterator __position, const _Tp& __x) 00246 { 00247 if (this->_M_impl._M_finish != this->_M_impl._M_end_of_storage) 00248 { 00249 std::_Construct(this->_M_impl._M_finish, 00250 *(this->_M_impl._M_finish - 1)); 00251 ++this->_M_impl._M_finish; 00252 _Tp __x_copy = __x; 00253 std::copy_backward(__position, 00254 iterator(this->_M_impl._M_finish-2), 00255 iterator(this->_M_impl._M_finish-1)); 00256 *__position = __x_copy; 00257 } 00258 else 00259 { 00260 const size_type __old_size = size(); 00261 const size_type __len = __old_size != 0 ? 2 * __old_size : 1; 00262 iterator __new_start(this->_M_allocate(__len)); 00263 iterator __new_finish(__new_start); 00264 try 00265 { 00266 __new_finish = std::uninitialized_copy(iterator(this-> 00267 _M_impl._M_start), 00268 __position, 00269 __new_start); 00270 std::_Construct(__new_finish.base(), __x); 00271 ++__new_finish; 00272 __new_finish = std::uninitialized_copy(__position, 00273 iterator(this->_M_impl. 00274 _M_finish), 00275 __new_finish); 00276 } 00277 catch(...) 00278 { 00279 std::_Destroy(__new_start,__new_finish); 00280 _M_deallocate(__new_start.base(),__len); 00281 __throw_exception_again; 00282 } 00283 std::_Destroy(begin(), end()); 00284 _M_deallocate(this->_M_impl._M_start, 00285 this->_M_impl._M_end_of_storage 00286 - this->_M_impl._M_start); 00287 this->_M_impl._M_start = __new_start.base(); 00288 this->_M_impl._M_finish = __new_finish.base(); 00289 this->_M_impl._M_end_of_storage = __new_start.base() + __len; 00290 } 00291 } 00292 00293 template<typename _Tp, typename _Alloc> 00294 void 00295 vector<_Tp, _Alloc>:: 00296 _M_fill_insert(iterator __position, size_type __n, const value_type& __x) 00297 { 00298 if (__n != 0) 00299 { 00300 if (size_type(this->_M_impl._M_end_of_storage 00301 - this->_M_impl._M_finish) >= __n) 00302 { 00303 value_type __x_copy = __x; 00304 const size_type __elems_after = end() - __position; 00305 iterator __old_finish(this->_M_impl._M_finish); 00306 if (__elems_after > __n) 00307 { 00308 std::uninitialized_copy(this->_M_impl._M_finish - __n, 00309 this->_M_impl._M_finish, 00310 this->_M_impl._M_finish); 00311 this->_M_impl._M_finish += __n; 00312 std::copy_backward(__position, __old_finish - __n, 00313 __old_finish); 00314 std::fill(__position, __position + __n, __x_copy); 00315 } 00316 else 00317 { 00318 std::uninitialized_fill_n(this->_M_impl._M_finish, 00319 __n - __elems_after, 00320 __x_copy); 00321 this->_M_impl._M_finish += __n - __elems_after; 00322 std::uninitialized_copy(__position, __old_finish, 00323 this->_M_impl._M_finish); 00324 this->_M_impl._M_finish += __elems_after; 00325 std::fill(__position, __old_finish, __x_copy); 00326 } 00327 } 00328 else 00329 { 00330 const size_type __old_size = size(); 00331 const size_type __len = __old_size + std::max(__old_size, __n); 00332 iterator __new_start(this->_M_allocate(__len)); 00333 iterator __new_finish(__new_start); 00334 try 00335 { 00336 __new_finish = std::uninitialized_copy(begin(), __position, 00337 __new_start); 00338 std::uninitialized_fill_n(__new_finish, __n, __x); 00339 __new_finish += __n; 00340 __new_finish = std::uninitialized_copy(__position, end(), 00341 __new_finish); 00342 } 00343 catch(...) 00344 { 00345 std::_Destroy(__new_start, __new_finish); 00346 _M_deallocate(__new_start.base(), __len); 00347 __throw_exception_again; 00348 } 00349 std::_Destroy(this->_M_impl._M_start, this->_M_impl._M_finish); 00350 _M_deallocate(this->_M_impl._M_start, 00351 this->_M_impl._M_end_of_storage 00352 - this->_M_impl._M_start); 00353 this->_M_impl._M_start = __new_start.base(); 00354 this->_M_impl._M_finish = __new_finish.base(); 00355 this->_M_impl._M_end_of_storage = __new_start.base() + __len; 00356 } 00357 } 00358 } 00359 00360 template<typename _Tp, typename _Alloc> template<typename _InputIterator> 00361 void 00362 vector<_Tp, _Alloc>:: 00363 _M_range_insert(iterator __pos, _InputIterator __first, 00364 _InputIterator __last, input_iterator_tag) 00365 { 00366 for (; __first != __last; ++__first) 00367 { 00368 __pos = insert(__pos, *__first); 00369 ++__pos; 00370 } 00371 } 00372 00373 template<typename _Tp, typename _Alloc> 00374 template<typename _ForwardIterator> 00375 void 00376 vector<_Tp, _Alloc>:: 00377 _M_range_insert(iterator __position,_ForwardIterator __first, 00378 _ForwardIterator __last, forward_iterator_tag) 00379 { 00380 if (__first != __last) 00381 { 00382 const size_type __n = std::distance(__first, __last); 00383 if (size_type(this->_M_impl._M_end_of_storage 00384 - this->_M_impl._M_finish) >= __n) 00385 { 00386 const size_type __elems_after = end() - __position; 00387 iterator __old_finish(this->_M_impl._M_finish); 00388 if (__elems_after > __n) 00389 { 00390 std::uninitialized_copy(this->_M_impl._M_finish - __n, 00391 this->_M_impl._M_finish, 00392 this->_M_impl._M_finish); 00393 this->_M_impl._M_finish += __n; 00394 std::copy_backward(__position, __old_finish - __n, 00395 __old_finish); 00396 std::copy(__first, __last, __position); 00397 } 00398 else 00399 { 00400 _ForwardIterator __mid = __first; 00401 std::advance(__mid, __elems_after); 00402 std::uninitialized_copy(__mid, __last, 00403 this->_M_impl._M_finish); 00404 this->_M_impl._M_finish += __n - __elems_after; 00405 std::uninitialized_copy(__position, __old_finish, 00406 this->_M_impl._M_finish); 00407 this->_M_impl._M_finish += __elems_after; 00408 std::copy(__first, __mid, __position); 00409 } 00410 } 00411 else 00412 { 00413 const size_type __old_size = size(); 00414 const size_type __len = __old_size + std::max(__old_size, __n); 00415 iterator __new_start(this->_M_allocate(__len)); 00416 iterator __new_finish(__new_start); 00417 try 00418 { 00419 __new_finish = std::uninitialized_copy(iterator(this-> 00420 _M_impl. 00421 _M_start), 00422 __position, 00423 __new_start); 00424 __new_finish = std::uninitialized_copy(__first, __last, 00425 __new_finish); 00426 __new_finish = std::uninitialized_copy(__position, 00427 iterator(this-> 00428 _M_impl. 00429 _M_finish), 00430 __new_finish); 00431 } 00432 catch(...) 00433 { 00434 std::_Destroy(__new_start,__new_finish); 00435 _M_deallocate(__new_start.base(), __len); 00436 __throw_exception_again; 00437 } 00438 std::_Destroy(this->_M_impl._M_start, this->_M_impl._M_finish); 00439 _M_deallocate(this->_M_impl._M_start, 00440 this->_M_impl._M_end_of_storage 00441 - this->_M_impl._M_start); 00442 this->_M_impl._M_start = __new_start.base(); 00443 this->_M_impl._M_finish = __new_finish.base(); 00444 this->_M_impl._M_end_of_storage = __new_start.base() + __len; 00445 } 00446 } 00447 } 00448 } // namespace std 00449 00450 #endif /* _VECTOR_TCC */

Generated on Sun Jul 25 00:12:34 2004 for libstdc++ source by doxygen 1.3.7