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
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_get_Tp_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(std::copy(__last, end(), __first));
00125 std::_Destroy(__i, end(), _M_get_Tp_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 _M_get_Tp_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(std::copy(__x.begin(), __x.end(), begin()));
00153 std::_Destroy(__i, end(), _M_get_Tp_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 _M_get_Tp_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, _M_get_Tp_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 _M_get_Tp_allocator());
00184 this->_M_impl._M_finish += __n - size();
00185 }
00186 else
00187 erase(std::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 std::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 std::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 _M_get_Tp_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(std::copy(__first, __last,
00230 this->_M_impl._M_start));
00231 std::_Destroy(__new_finish, end(), _M_get_Tp_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 _M_get_Tp_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 if (__old_size == this->max_size())
00266 __throw_length_error(__N("vector::_M_insert_aux"));
00267
00268
00269
00270
00271 size_type __len = __old_size != 0 ? 2 * __old_size : 1;
00272 if (__len < __old_size)
00273 __len = this->max_size();
00274
00275 iterator __new_start(this->_M_allocate(__len));
00276 iterator __new_finish(__new_start);
00277 try
00278 {
00279 __new_finish =
00280 std::__uninitialized_copy_a(iterator(this->_M_impl._M_start),
00281 __position,
00282 __new_start,
00283 _M_get_Tp_allocator());
00284 this->_M_impl.construct(__new_finish.base(), __x);
00285 ++__new_finish;
00286 __new_finish =
00287 std::__uninitialized_copy_a(__position,
00288 iterator(this->_M_impl._M_finish),
00289 __new_finish,
00290 _M_get_Tp_allocator());
00291 }
00292 catch(...)
00293 {
00294 std::_Destroy(__new_start, __new_finish, _M_get_Tp_allocator());
00295 _M_deallocate(__new_start.base(),__len);
00296 __throw_exception_again;
00297 }
00298 std::_Destroy(begin(), end(), _M_get_Tp_allocator());
00299 _M_deallocate(this->_M_impl._M_start,
00300 this->_M_impl._M_end_of_storage
00301 - this->_M_impl._M_start);
00302 this->_M_impl._M_start = __new_start.base();
00303 this->_M_impl._M_finish = __new_finish.base();
00304 this->_M_impl._M_end_of_storage = __new_start.base() + __len;
00305 }
00306 }
00307
00308 template<typename _Tp, typename _Alloc>
00309 void
00310 vector<_Tp, _Alloc>::
00311 _M_fill_insert(iterator __position, size_type __n, const value_type& __x)
00312 {
00313 if (__n != 0)
00314 {
00315 if (size_type(this->_M_impl._M_end_of_storage
00316 - this->_M_impl._M_finish) >= __n)
00317 {
00318 value_type __x_copy = __x;
00319 const size_type __elems_after = end() - __position;
00320 iterator __old_finish(this->_M_impl._M_finish);
00321 if (__elems_after > __n)
00322 {
00323 std::__uninitialized_copy_a(this->_M_impl._M_finish - __n,
00324 this->_M_impl._M_finish,
00325 this->_M_impl._M_finish,
00326 _M_get_Tp_allocator());
00327 this->_M_impl._M_finish += __n;
00328 std::copy_backward(__position, __old_finish - __n,
00329 __old_finish);
00330 std::fill(__position, __position + __n, __x_copy);
00331 }
00332 else
00333 {
00334 std::__uninitialized_fill_n_a(this->_M_impl._M_finish,
00335 __n - __elems_after,
00336 __x_copy,
00337 _M_get_Tp_allocator());
00338 this->_M_impl._M_finish += __n - __elems_after;
00339 std::__uninitialized_copy_a(__position, __old_finish,
00340 this->_M_impl._M_finish,
00341 _M_get_Tp_allocator());
00342 this->_M_impl._M_finish += __elems_after;
00343 std::fill(__position, __old_finish, __x_copy);
00344 }
00345 }
00346 else
00347 {
00348 const size_type __old_size = size();
00349 if (this->max_size() - __old_size < __n)
00350 __throw_length_error(__N("vector::_M_fill_insert"));
00351
00352
00353 size_type __len = __old_size + std::max(__old_size, __n);
00354 if (__len < __old_size)
00355 __len = this->max_size();
00356
00357 iterator __new_start(this->_M_allocate(__len));
00358 iterator __new_finish(__new_start);
00359 try
00360 {
00361 __new_finish =
00362 std::__uninitialized_copy_a(begin(), __position,
00363 __new_start,
00364 _M_get_Tp_allocator());
00365 std::__uninitialized_fill_n_a(__new_finish, __n, __x,
00366 _M_get_Tp_allocator());
00367 __new_finish += __n;
00368 __new_finish =
00369 std::__uninitialized_copy_a(__position, end(), __new_finish,
00370 _M_get_Tp_allocator());
00371 }
00372 catch(...)
00373 {
00374 std::_Destroy(__new_start, __new_finish,
00375 _M_get_Tp_allocator());
00376 _M_deallocate(__new_start.base(), __len);
00377 __throw_exception_again;
00378 }
00379 std::_Destroy(this->_M_impl._M_start, this->_M_impl._M_finish,
00380 _M_get_Tp_allocator());
00381 _M_deallocate(this->_M_impl._M_start,
00382 this->_M_impl._M_end_of_storage
00383 - this->_M_impl._M_start);
00384 this->_M_impl._M_start = __new_start.base();
00385 this->_M_impl._M_finish = __new_finish.base();
00386 this->_M_impl._M_end_of_storage = __new_start.base() + __len;
00387 }
00388 }
00389 }
00390
00391 template<typename _Tp, typename _Alloc> template<typename _InputIterator>
00392 void
00393 vector<_Tp, _Alloc>::
00394 _M_range_insert(iterator __pos, _InputIterator __first,
00395 _InputIterator __last, std::input_iterator_tag)
00396 {
00397 for (; __first != __last; ++__first)
00398 {
00399 __pos = insert(__pos, *__first);
00400 ++__pos;
00401 }
00402 }
00403
00404 template<typename _Tp, typename _Alloc>
00405 template<typename _ForwardIterator>
00406 void
00407 vector<_Tp, _Alloc>::
00408 _M_range_insert(iterator __position, _ForwardIterator __first,
00409 _ForwardIterator __last, std::forward_iterator_tag)
00410 {
00411 if (__first != __last)
00412 {
00413 const size_type __n = std::distance(__first, __last);
00414 if (size_type(this->_M_impl._M_end_of_storage
00415 - this->_M_impl._M_finish) >= __n)
00416 {
00417 const size_type __elems_after = end() - __position;
00418 iterator __old_finish(this->_M_impl._M_finish);
00419 if (__elems_after > __n)
00420 {
00421 std::__uninitialized_copy_a(this->_M_impl._M_finish - __n,
00422 this->_M_impl._M_finish,
00423 this->_M_impl._M_finish,
00424 _M_get_Tp_allocator());
00425 this->_M_impl._M_finish += __n;
00426 std::copy_backward(__position, __old_finish - __n,
00427 __old_finish);
00428 std::copy(__first, __last, __position);
00429 }
00430 else
00431 {
00432 _ForwardIterator __mid = __first;
00433 std::advance(__mid, __elems_after);
00434 std::__uninitialized_copy_a(__mid, __last,
00435 this->_M_impl._M_finish,
00436 _M_get_Tp_allocator());
00437 this->_M_impl._M_finish += __n - __elems_after;
00438 std::__uninitialized_copy_a(__position, __old_finish,
00439 this->_M_impl._M_finish,
00440 _M_get_Tp_allocator());
00441 this->_M_impl._M_finish += __elems_after;
00442 std::copy(__first, __mid, __position);
00443 }
00444 }
00445 else
00446 {
00447 const size_type __old_size = size();
00448 if (this->max_size() - __old_size < __n)
00449 __throw_length_error(__N("vector::_M_range_insert"));
00450
00451
00452 size_type __len = __old_size + std::max(__old_size, __n);
00453 if (__len < __old_size)
00454 __len = this->max_size();
00455
00456 iterator __new_start(this->_M_allocate(__len));
00457 iterator __new_finish(__new_start);
00458 try
00459 {
00460 __new_finish =
00461 std::__uninitialized_copy_a(iterator(this->_M_impl._M_start),
00462 __position,
00463 __new_start,
00464 _M_get_Tp_allocator());
00465 __new_finish =
00466 std::__uninitialized_copy_a(__first, __last, __new_finish,
00467 _M_get_Tp_allocator());
00468 __new_finish =
00469 std::__uninitialized_copy_a(__position,
00470 iterator(this->_M_impl._M_finish),
00471 __new_finish,
00472 _M_get_Tp_allocator());
00473 }
00474 catch(...)
00475 {
00476 std::_Destroy(__new_start,__new_finish,
00477 _M_get_Tp_allocator());
00478 _M_deallocate(__new_start.base(), __len);
00479 __throw_exception_again;
00480 }
00481 std::_Destroy(this->_M_impl._M_start, this->_M_impl._M_finish,
00482 _M_get_Tp_allocator());
00483 _M_deallocate(this->_M_impl._M_start,
00484 this->_M_impl._M_end_of_storage
00485 - this->_M_impl._M_start);
00486 this->_M_impl._M_start = __new_start.base();
00487 this->_M_impl._M_finish = __new_finish.base();
00488 this->_M_impl._M_end_of_storage = __new_start.base() + __len;
00489 }
00490 }
00491 }
00492 }
00493
00494 #endif