vector.tcc

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

Generated on Wed Sep 8 10:19:54 2004 for libstdc++-v3 Source by doxygen 1.3.8