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