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 _GLIBCXX_BEGIN_NESTED_NAMESPACE(std, _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, this->_M_impl._M_start,
00077 this->_M_impl._M_finish);
00078 std::_Destroy(this->_M_impl._M_start, this->_M_impl._M_finish,
00079 _M_get_Tp_allocator());
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 this->_M_impl.construct(this->_M_impl._M_finish, __x);
00099 ++this->_M_impl._M_finish;
00100 }
00101 else
00102 _M_insert_aux(__position, __x);
00103 return iterator(this->_M_impl._M_start + __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 this->_M_impl.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 if (__last != end())
00124 std::copy(__last, end(), __first);
00125 _M_erase_at_end(__first.base() + (end() - __last));
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, this->_M_impl._M_finish,
00142 _M_get_Tp_allocator());
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 std::_Destroy(std::copy(__x.begin(), __x.end(), begin()),
00152 end(), _M_get_Tp_allocator());
00153 }
00154 else
00155 {
00156 std::copy(__x._M_impl._M_start, __x._M_impl._M_start + size(),
00157 this->_M_impl._M_start);
00158 std::__uninitialized_copy_a(__x._M_impl._M_start + size(),
00159 __x._M_impl._M_finish,
00160 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 _M_erase_at_end(std::fill_n(this->_M_impl._M_start, __n, __val));
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 pointer __cur(this->_M_impl._M_start);
00198 for (; __first != __last && __cur != this->_M_impl._M_finish;
00199 ++__cur, ++__first)
00200 *__cur = *__first;
00201 if (__first == __last)
00202 _M_erase_at_end(__cur);
00203 else
00204 insert(end(), __first, __last);
00205 }
00206
00207 template<typename _Tp, typename _Alloc>
00208 template<typename _ForwardIterator>
00209 void
00210 vector<_Tp, _Alloc>::
00211 _M_assign_aux(_ForwardIterator __first, _ForwardIterator __last,
00212 std::forward_iterator_tag)
00213 {
00214 const size_type __len = std::distance(__first, __last);
00215
00216 if (__len > capacity())
00217 {
00218 pointer __tmp(_M_allocate_and_copy(__len, __first, __last));
00219 std::_Destroy(this->_M_impl._M_start, this->_M_impl._M_finish,
00220 _M_get_Tp_allocator());
00221 _M_deallocate(this->_M_impl._M_start,
00222 this->_M_impl._M_end_of_storage
00223 - this->_M_impl._M_start);
00224 this->_M_impl._M_start = __tmp;
00225 this->_M_impl._M_finish = this->_M_impl._M_start + __len;
00226 this->_M_impl._M_end_of_storage = this->_M_impl._M_finish;
00227 }
00228 else if (size() >= __len)
00229 _M_erase_at_end(std::copy(__first, __last, this->_M_impl._M_start));
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 =
00236 std::__uninitialized_copy_a(__mid, __last,
00237 this->_M_impl._M_finish,
00238 _M_get_Tp_allocator());
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 this->_M_impl.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.base(),
00254 this->_M_impl._M_finish - 2,
00255 this->_M_impl._M_finish - 1);
00256 *__position = __x_copy;
00257 }
00258 else
00259 {
00260 const size_type __old_size = size();
00261 if (__old_size == this->max_size())
00262 __throw_length_error(__N("vector::_M_insert_aux"));
00263
00264
00265
00266
00267 size_type __len = __old_size != 0 ? 2 * __old_size : 1;
00268 if (__len < __old_size)
00269 __len = this->max_size();
00270
00271 pointer __new_start(this->_M_allocate(__len));
00272 pointer __new_finish(__new_start);
00273 try
00274 {
00275 __new_finish =
00276 std::__uninitialized_copy_a(this->_M_impl._M_start,
00277 __position.base(), __new_start,
00278 _M_get_Tp_allocator());
00279 this->_M_impl.construct(__new_finish, __x);
00280 ++__new_finish;
00281 __new_finish =
00282 std::__uninitialized_copy_a(__position.base(),
00283 this->_M_impl._M_finish,
00284 __new_finish,
00285 _M_get_Tp_allocator());
00286 }
00287 catch(...)
00288 {
00289 std::_Destroy(__new_start, __new_finish, _M_get_Tp_allocator());
00290 _M_deallocate(__new_start, __len);
00291 __throw_exception_again;
00292 }
00293 std::_Destroy(this->_M_impl._M_start, this->_M_impl._M_finish,
00294 _M_get_Tp_allocator());
00295 _M_deallocate(this->_M_impl._M_start,
00296 this->_M_impl._M_end_of_storage
00297 - this->_M_impl._M_start);
00298 this->_M_impl._M_start = __new_start;
00299 this->_M_impl._M_finish = __new_finish;
00300 this->_M_impl._M_end_of_storage = __new_start + __len;
00301 }
00302 }
00303
00304 template<typename _Tp, typename _Alloc>
00305 void
00306 vector<_Tp, _Alloc>::
00307 _M_fill_insert(iterator __position, size_type __n, const value_type& __x)
00308 {
00309 if (__n != 0)
00310 {
00311 if (size_type(this->_M_impl._M_end_of_storage
00312 - this->_M_impl._M_finish) >= __n)
00313 {
00314 value_type __x_copy = __x;
00315 const size_type __elems_after = end() - __position;
00316 pointer __old_finish(this->_M_impl._M_finish);
00317 if (__elems_after > __n)
00318 {
00319 std::__uninitialized_copy_a(this->_M_impl._M_finish - __n,
00320 this->_M_impl._M_finish,
00321 this->_M_impl._M_finish,
00322 _M_get_Tp_allocator());
00323 this->_M_impl._M_finish += __n;
00324 std::copy_backward(__position.base(), __old_finish - __n,
00325 __old_finish);
00326 std::fill(__position.base(), __position.base() + __n,
00327 __x_copy);
00328 }
00329 else
00330 {
00331 std::__uninitialized_fill_n_a(this->_M_impl._M_finish,
00332 __n - __elems_after,
00333 __x_copy,
00334 _M_get_Tp_allocator());
00335 this->_M_impl._M_finish += __n - __elems_after;
00336 std::__uninitialized_copy_a(__position.base(), __old_finish,
00337 this->_M_impl._M_finish,
00338 _M_get_Tp_allocator());
00339 this->_M_impl._M_finish += __elems_after;
00340 std::fill(__position.base(), __old_finish, __x_copy);
00341 }
00342 }
00343 else
00344 {
00345 const size_type __old_size = size();
00346 if (this->max_size() - __old_size < __n)
00347 __throw_length_error(__N("vector::_M_fill_insert"));
00348
00349
00350 size_type __len = __old_size + std::max(__old_size, __n);
00351 if (__len < __old_size)
00352 __len = this->max_size();
00353
00354 pointer __new_start(this->_M_allocate(__len));
00355 pointer __new_finish(__new_start);
00356 try
00357 {
00358 __new_finish =
00359 std::__uninitialized_copy_a(this->_M_impl._M_start,
00360 __position.base(),
00361 __new_start,
00362 _M_get_Tp_allocator());
00363 std::__uninitialized_fill_n_a(__new_finish, __n, __x,
00364 _M_get_Tp_allocator());
00365 __new_finish += __n;
00366 __new_finish =
00367 std::__uninitialized_copy_a(__position.base(),
00368 this->_M_impl._M_finish,
00369 __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, __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;
00385 this->_M_impl._M_finish = __new_finish;
00386 this->_M_impl._M_end_of_storage = __new_start + __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 pointer __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.base(), __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.base(),
00439 __old_finish,
00440 this->_M_impl._M_finish,
00441 _M_get_Tp_allocator());
00442 this->_M_impl._M_finish += __elems_after;
00443 std::copy(__first, __mid, __position);
00444 }
00445 }
00446 else
00447 {
00448 const size_type __old_size = size();
00449 if (this->max_size() - __old_size < __n)
00450 __throw_length_error(__N("vector::_M_range_insert"));
00451
00452
00453 size_type __len = __old_size + std::max(__old_size, __n);
00454 if (__len < __old_size)
00455 __len = this->max_size();
00456
00457 pointer __new_start(this->_M_allocate(__len));
00458 pointer __new_finish(__new_start);
00459 try
00460 {
00461 __new_finish =
00462 std::__uninitialized_copy_a(this->_M_impl._M_start,
00463 __position.base(),
00464 __new_start,
00465 _M_get_Tp_allocator());
00466 __new_finish =
00467 std::__uninitialized_copy_a(__first, __last, __new_finish,
00468 _M_get_Tp_allocator());
00469 __new_finish =
00470 std::__uninitialized_copy_a(__position.base(),
00471 this->_M_impl._M_finish,
00472 __new_finish,
00473 _M_get_Tp_allocator());
00474 }
00475 catch(...)
00476 {
00477 std::_Destroy(__new_start, __new_finish,
00478 _M_get_Tp_allocator());
00479 _M_deallocate(__new_start, __len);
00480 __throw_exception_again;
00481 }
00482 std::_Destroy(this->_M_impl._M_start, this->_M_impl._M_finish,
00483 _M_get_Tp_allocator());
00484 _M_deallocate(this->_M_impl._M_start,
00485 this->_M_impl._M_end_of_storage
00486 - this->_M_impl._M_start);
00487 this->_M_impl._M_start = __new_start;
00488 this->_M_impl._M_finish = __new_finish;
00489 this->_M_impl._M_end_of_storage = __new_start + __len;
00490 }
00491 }
00492 }
00493
00494 _GLIBCXX_END_NESTED_NAMESPACE
00495
00496 #endif