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

Generated on Sun Sep 12 15:49:59 2004 for libstdc++ source by doxygen 1.3.8