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