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
const 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
std::uninitialized_fill_n(this->_M_impl._M_finish,
00180 __n - size(), __val);
00181 this->_M_impl._M_finish += __n -
size();
00182 }
00183
else
00184
erase(
fill_n(
begin(), __n, __val),
end());
00185 }
00186
00187
template<
typename _Tp,
typename _Alloc>
00188
template<
typename _InputIterator>
00189
void
00190 vector<_Tp, _Alloc>::
00191 _M_assign_aux(_InputIterator __first, _InputIterator __last,
00192 input_iterator_tag)
00193 {
00194 iterator __cur(
begin());
00195
for (; __first != __last && __cur !=
end(); ++__cur, ++__first)
00196 *__cur = *__first;
00197
if (__first == __last)
00198
erase(__cur,
end());
00199
else
00200
insert(
end(), __first, __last);
00201 }
00202
00203
template<
typename _Tp,
typename _Alloc>
00204
template<
typename _ForwardIterator>
00205
void
00206 vector<_Tp, _Alloc>::
00207 _M_assign_aux(_ForwardIterator __first, _ForwardIterator __last,
00208 forward_iterator_tag)
00209 {
00210
const size_type __len =
std::distance(__first, __last);
00211
00212
if (__len >
capacity())
00213 {
00214 pointer __tmp(_M_allocate_and_copy(__len, __first, __last));
00215 std::_Destroy(this->_M_impl._M_start, this->_M_impl._M_finish);
00216 _M_deallocate(this->_M_impl._M_start,
00217 this->_M_impl._M_end_of_storage
00218 - this->_M_impl._M_start);
00219 this->_M_impl._M_start = __tmp;
00220 this->_M_impl._M_finish = this->_M_impl._M_start + __len;
00221 this->_M_impl._M_end_of_storage = this->_M_impl._M_finish;
00222 }
00223
else if (
size() >= __len)
00224 {
00225 iterator __new_finish(
copy(__first, __last,
00226 this->_M_impl._M_start));
00227 std::_Destroy(__new_finish,
end());
00228 this->_M_impl._M_finish = __new_finish.base();
00229 }
00230
else
00231 {
00232 _ForwardIterator __mid = __first;
00233
std::advance(__mid,
size());
00234
std::copy(__first, __mid, this->_M_impl._M_start);
00235 this->_M_impl._M_finish =
std::uninitialized_copy(__mid,
00236 __last,
00237 this->_M_impl.
00238 _M_finish);
00239 }
00240 }
00241
00242
template<
typename _Tp,
typename _Alloc>
00243
void
00244 vector<_Tp, _Alloc>::
00245 _M_insert_aux(iterator __position,
const _Tp& __x)
00246 {
00247
if (this->_M_impl._M_finish != this->_M_impl._M_end_of_storage)
00248 {
00249 std::_Construct(this->_M_impl._M_finish,
00250 *(this->_M_impl._M_finish - 1));
00251 ++this->_M_impl._M_finish;
00252 _Tp __x_copy = __x;
00253
std::copy_backward(__position,
00254 iterator(this->_M_impl._M_finish-2),
00255 iterator(this->_M_impl._M_finish-1));
00256 *__position = __x_copy;
00257 }
00258
else
00259 {
00260
const size_type __old_size =
size();
00261
const size_type __len = __old_size != 0 ? 2 * __old_size : 1;
00262 iterator __new_start(this->_M_allocate(__len));
00263 iterator __new_finish(__new_start);
00264
try
00265 {
00266 __new_finish =
std::uninitialized_copy(iterator(this->
00267 _M_impl._M_start),
00268 __position,
00269 __new_start);
00270 std::_Construct(__new_finish.base(), __x);
00271 ++__new_finish;
00272 __new_finish =
std::uninitialized_copy(__position,
00273 iterator(this->_M_impl.
00274 _M_finish),
00275 __new_finish);
00276 }
00277
catch(...)
00278 {
00279 std::_Destroy(__new_start,__new_finish);
00280 _M_deallocate(__new_start.base(),__len);
00281 __throw_exception_again;
00282 }
00283 std::_Destroy(
begin(),
end());
00284 _M_deallocate(this->_M_impl._M_start,
00285 this->_M_impl._M_end_of_storage
00286 - this->_M_impl._M_start);
00287 this->_M_impl._M_start = __new_start.base();
00288 this->_M_impl._M_finish = __new_finish.base();
00289 this->_M_impl._M_end_of_storage = __new_start.base() + __len;
00290 }
00291 }
00292
00293
template<
typename _Tp,
typename _Alloc>
00294
void
00295 vector<_Tp, _Alloc>::
00296 _M_fill_insert(iterator __position, size_type __n,
const value_type& __x)
00297 {
00298
if (__n != 0)
00299 {
00300
if (size_type(this->_M_impl._M_end_of_storage
00301 - this->_M_impl._M_finish) >= __n)
00302 {
00303 value_type __x_copy = __x;
00304
const size_type __elems_after =
end() - __position;
00305 iterator __old_finish(this->_M_impl._M_finish);
00306
if (__elems_after > __n)
00307 {
00308
std::uninitialized_copy(this->_M_impl._M_finish - __n,
00309 this->_M_impl._M_finish,
00310 this->_M_impl._M_finish);
00311 this->_M_impl._M_finish += __n;
00312
std::copy_backward(__position, __old_finish - __n,
00313 __old_finish);
00314
std::fill(__position, __position + __n, __x_copy);
00315 }
00316
else
00317 {
00318
std::uninitialized_fill_n(this->_M_impl._M_finish,
00319 __n - __elems_after,
00320 __x_copy);
00321 this->_M_impl._M_finish += __n - __elems_after;
00322
std::uninitialized_copy(__position, __old_finish,
00323 this->_M_impl._M_finish);
00324 this->_M_impl._M_finish += __elems_after;
00325
std::fill(__position, __old_finish, __x_copy);
00326 }
00327 }
00328
else
00329 {
00330
const size_type __old_size =
size();
00331
const size_type __len = __old_size +
std::max(__old_size, __n);
00332 iterator __new_start(this->_M_allocate(__len));
00333 iterator __new_finish(__new_start);
00334
try
00335 {
00336 __new_finish =
std::uninitialized_copy(
begin(), __position,
00337 __new_start);
00338
std::uninitialized_fill_n(__new_finish, __n, __x);
00339 __new_finish += __n;
00340 __new_finish =
std::uninitialized_copy(__position,
end(),
00341 __new_finish);
00342 }
00343
catch(...)
00344 {
00345 std::_Destroy(__new_start, __new_finish);
00346 _M_deallocate(__new_start.base(), __len);
00347 __throw_exception_again;
00348 }
00349 std::_Destroy(this->_M_impl._M_start, this->_M_impl._M_finish);
00350 _M_deallocate(this->_M_impl._M_start,
00351 this->_M_impl._M_end_of_storage
00352 - this->_M_impl._M_start);
00353 this->_M_impl._M_start = __new_start.base();
00354 this->_M_impl._M_finish = __new_finish.base();
00355 this->_M_impl._M_end_of_storage = __new_start.base() + __len;
00356 }
00357 }
00358 }
00359
00360
template<
typename _Tp,
typename _Alloc>
template<
typename _InputIterator>
00361
void
00362 vector<_Tp, _Alloc>::
00363 _M_range_insert(iterator __pos, _InputIterator __first,
00364 _InputIterator __last, input_iterator_tag)
00365 {
00366
for (; __first != __last; ++__first)
00367 {
00368 __pos =
insert(__pos, *__first);
00369 ++__pos;
00370 }
00371 }
00372
00373
template<
typename _Tp,
typename _Alloc>
00374
template<
typename _ForwardIterator>
00375
void
00376 vector<_Tp, _Alloc>::
00377 _M_range_insert(iterator __position,_ForwardIterator __first,
00378 _ForwardIterator __last, forward_iterator_tag)
00379 {
00380
if (__first != __last)
00381 {
00382
const size_type __n =
std::distance(__first, __last);
00383
if (size_type(this->_M_impl._M_end_of_storage
00384 - this->_M_impl._M_finish) >= __n)
00385 {
00386
const size_type __elems_after =
end() - __position;
00387 iterator __old_finish(this->_M_impl._M_finish);
00388
if (__elems_after > __n)
00389 {
00390
std::uninitialized_copy(this->_M_impl._M_finish - __n,
00391 this->_M_impl._M_finish,
00392 this->_M_impl._M_finish);
00393 this->_M_impl._M_finish += __n;
00394
std::copy_backward(__position, __old_finish - __n,
00395 __old_finish);
00396
std::copy(__first, __last, __position);
00397 }
00398
else
00399 {
00400 _ForwardIterator __mid = __first;
00401
std::advance(__mid, __elems_after);
00402
std::uninitialized_copy(__mid, __last,
00403 this->_M_impl._M_finish);
00404 this->_M_impl._M_finish += __n - __elems_after;
00405
std::uninitialized_copy(__position, __old_finish,
00406 this->_M_impl._M_finish);
00407 this->_M_impl._M_finish += __elems_after;
00408
std::copy(__first, __mid, __position);
00409 }
00410 }
00411
else
00412 {
00413
const size_type __old_size =
size();
00414
const size_type __len = __old_size +
std::max(__old_size, __n);
00415 iterator __new_start(this->_M_allocate(__len));
00416 iterator __new_finish(__new_start);
00417
try
00418 {
00419 __new_finish =
std::uninitialized_copy(iterator(this->
00420 _M_impl.
00421 _M_start),
00422 __position,
00423 __new_start);
00424 __new_finish =
std::uninitialized_copy(__first, __last,
00425 __new_finish);
00426 __new_finish =
std::uninitialized_copy(__position,
00427 iterator(this->
00428 _M_impl.
00429 _M_finish),
00430 __new_finish);
00431 }
00432
catch(...)
00433 {
00434 std::_Destroy(__new_start,__new_finish);
00435 _M_deallocate(__new_start.base(), __len);
00436 __throw_exception_again;
00437 }
00438 std::_Destroy(this->_M_impl._M_start, this->_M_impl._M_finish);
00439 _M_deallocate(this->_M_impl._M_start,
00440 this->_M_impl._M_end_of_storage
00441 - this->_M_impl._M_start);
00442 this->_M_impl._M_start = __new_start.base();
00443 this->_M_impl._M_finish = __new_finish.base();
00444 this->_M_impl._M_end_of_storage = __new_start.base() + __len;
00445 }
00446 }
00447 }
00448 }
00449
00450
#endif