00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024
00025
00026
00027
00028
00029
00030
00031
00032
00033
00034
00035
00036
00037
00038
00039
00040
00041
00042
00043
00044
00045
00046
00047
00048
00049
00050
00051
00052
00053
00054
00055
00056
00057
00058
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 }
00436
00437 #endif