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