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 _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 }
00470
00471
#endif