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
00062 #ifndef _VECTOR_TCC
00063 #define _VECTOR_TCC 1
00064
00065 _GLIBCXX_BEGIN_NESTED_NAMESPACE(std, _GLIBCXX_STD_D)
00066
00067 template<typename _Tp, typename _Alloc>
00068 void
00069 vector<_Tp, _Alloc>::
00070 reserve(size_type __n)
00071 {
00072 if (__n > this->max_size())
00073 __throw_length_error(__N("vector::reserve"));
00074 if (this->capacity() < __n)
00075 {
00076 const size_type __old_size = size();
00077 pointer __tmp = _M_allocate_and_copy(__n,
00078 _GLIBCXX_MAKE_MOVE_ITERATOR(this->_M_impl._M_start),
00079 _GLIBCXX_MAKE_MOVE_ITERATOR(this->_M_impl._M_finish));
00080 std::_Destroy(this->_M_impl._M_start, this->_M_impl._M_finish,
00081 _M_get_Tp_allocator());
00082 _M_deallocate(this->_M_impl._M_start,
00083 this->_M_impl._M_end_of_storage
00084 - this->_M_impl._M_start);
00085 this->_M_impl._M_start = __tmp;
00086 this->_M_impl._M_finish = __tmp + __old_size;
00087 this->_M_impl._M_end_of_storage = this->_M_impl._M_start + __n;
00088 }
00089 }
00090
00091 template<typename _Tp, typename _Alloc>
00092 typename vector<_Tp, _Alloc>::iterator
00093 vector<_Tp, _Alloc>::
00094 insert(iterator __position, const value_type& __x)
00095 {
00096 const size_type __n = __position - begin();
00097 if (this->_M_impl._M_finish != this->_M_impl._M_end_of_storage
00098 && __position == end())
00099 {
00100 this->_M_impl.construct(this->_M_impl._M_finish, __x);
00101 ++this->_M_impl._M_finish;
00102 }
00103 else
00104 {
00105 #ifdef __GXX_EXPERIMENTAL_CXX0X__
00106 if (this->_M_impl._M_finish != this->_M_impl._M_end_of_storage)
00107 {
00108 _Tp __x_copy = __x;
00109 _M_insert_aux(__position, std::move(__x_copy));
00110 }
00111 else
00112 #endif
00113 _M_insert_aux(__position, __x);
00114 }
00115 return iterator(this->_M_impl._M_start + __n);
00116 }
00117
00118 template<typename _Tp, typename _Alloc>
00119 typename vector<_Tp, _Alloc>::iterator
00120 vector<_Tp, _Alloc>::
00121 erase(iterator __position)
00122 {
00123 if (__position + 1 != end())
00124 _GLIBCXX_MOVE3(__position + 1, end(), __position);
00125 --this->_M_impl._M_finish;
00126 this->_M_impl.destroy(this->_M_impl._M_finish);
00127 return __position;
00128 }
00129
00130 template<typename _Tp, typename _Alloc>
00131 typename vector<_Tp, _Alloc>::iterator
00132 vector<_Tp, _Alloc>::
00133 erase(iterator __first, iterator __last)
00134 {
00135 if (__last != end())
00136 _GLIBCXX_MOVE3(__last, end(), __first);
00137 _M_erase_at_end(__first.base() + (end() - __last));
00138 return __first;
00139 }
00140
00141 template<typename _Tp, typename _Alloc>
00142 vector<_Tp, _Alloc>&
00143 vector<_Tp, _Alloc>::
00144 operator=(const vector<_Tp, _Alloc>& __x)
00145 {
00146 if (&__x != this)
00147 {
00148 const size_type __xlen = __x.size();
00149 if (__xlen > capacity())
00150 {
00151 pointer __tmp = _M_allocate_and_copy(__xlen, __x.begin(),
00152 __x.end());
00153 std::_Destroy(this->_M_impl._M_start, this->_M_impl._M_finish,
00154 _M_get_Tp_allocator());
00155 _M_deallocate(this->_M_impl._M_start,
00156 this->_M_impl._M_end_of_storage
00157 - this->_M_impl._M_start);
00158 this->_M_impl._M_start = __tmp;
00159 this->_M_impl._M_end_of_storage = this->_M_impl._M_start + __xlen;
00160 }
00161 else if (size() >= __xlen)
00162 {
00163 std::_Destroy(std::copy(__x.begin(), __x.end(), begin()),
00164 end(), _M_get_Tp_allocator());
00165 }
00166 else
00167 {
00168 std::copy(__x._M_impl._M_start, __x._M_impl._M_start + size(),
00169 this->_M_impl._M_start);
00170 std::__uninitialized_copy_a(__x._M_impl._M_start + size(),
00171 __x._M_impl._M_finish,
00172 this->_M_impl._M_finish,
00173 _M_get_Tp_allocator());
00174 }
00175 this->_M_impl._M_finish = this->_M_impl._M_start + __xlen;
00176 }
00177 return *this;
00178 }
00179
00180 template<typename _Tp, typename _Alloc>
00181 void
00182 vector<_Tp, _Alloc>::
00183 _M_fill_assign(size_t __n, const value_type& __val)
00184 {
00185 if (__n > capacity())
00186 {
00187 vector __tmp(__n, __val, _M_get_Tp_allocator());
00188 __tmp.swap(*this);
00189 }
00190 else if (__n > size())
00191 {
00192 std::fill(begin(), end(), __val);
00193 std::__uninitialized_fill_n_a(this->_M_impl._M_finish,
00194 __n - size(), __val,
00195 _M_get_Tp_allocator());
00196 this->_M_impl._M_finish += __n - size();
00197 }
00198 else
00199 _M_erase_at_end(std::fill_n(this->_M_impl._M_start, __n, __val));
00200 }
00201
00202 template<typename _Tp, typename _Alloc>
00203 template<typename _InputIterator>
00204 void
00205 vector<_Tp, _Alloc>::
00206 _M_assign_aux(_InputIterator __first, _InputIterator __last,
00207 std::input_iterator_tag)
00208 {
00209 pointer __cur(this->_M_impl._M_start);
00210 for (; __first != __last && __cur != this->_M_impl._M_finish;
00211 ++__cur, ++__first)
00212 *__cur = *__first;
00213 if (__first == __last)
00214 _M_erase_at_end(__cur);
00215 else
00216 insert(end(), __first, __last);
00217 }
00218
00219 template<typename _Tp, typename _Alloc>
00220 template<typename _ForwardIterator>
00221 void
00222 vector<_Tp, _Alloc>::
00223 _M_assign_aux(_ForwardIterator __first, _ForwardIterator __last,
00224 std::forward_iterator_tag)
00225 {
00226 const size_type __len = std::distance(__first, __last);
00227
00228 if (__len > capacity())
00229 {
00230 pointer __tmp(_M_allocate_and_copy(__len, __first, __last));
00231 std::_Destroy(this->_M_impl._M_start, this->_M_impl._M_finish,
00232 _M_get_Tp_allocator());
00233 _M_deallocate(this->_M_impl._M_start,
00234 this->_M_impl._M_end_of_storage
00235 - this->_M_impl._M_start);
00236 this->_M_impl._M_start = __tmp;
00237 this->_M_impl._M_finish = this->_M_impl._M_start + __len;
00238 this->_M_impl._M_end_of_storage = this->_M_impl._M_finish;
00239 }
00240 else if (size() >= __len)
00241 _M_erase_at_end(std::copy(__first, __last, this->_M_impl._M_start));
00242 else
00243 {
00244 _ForwardIterator __mid = __first;
00245 std::advance(__mid, size());
00246 std::copy(__first, __mid, this->_M_impl._M_start);
00247 this->_M_impl._M_finish =
00248 std::__uninitialized_copy_a(__mid, __last,
00249 this->_M_impl._M_finish,
00250 _M_get_Tp_allocator());
00251 }
00252 }
00253
00254 #ifdef __GXX_EXPERIMENTAL_CXX0X__
00255 template<typename _Tp, typename _Alloc>
00256 template<typename... _Args>
00257 typename vector<_Tp, _Alloc>::iterator
00258 vector<_Tp, _Alloc>::
00259 emplace(iterator __position, _Args&&... __args)
00260 {
00261 const size_type __n = __position - begin();
00262 if (this->_M_impl._M_finish != this->_M_impl._M_end_of_storage
00263 && __position == end())
00264 {
00265 this->_M_impl.construct(this->_M_impl._M_finish,
00266 std::forward<_Args>(__args)...);
00267 ++this->_M_impl._M_finish;
00268 }
00269 else
00270 _M_insert_aux(__position, std::forward<_Args>(__args)...);
00271 return iterator(this->_M_impl._M_start + __n);
00272 }
00273
00274 template<typename _Tp, typename _Alloc>
00275 template<typename... _Args>
00276 void
00277 vector<_Tp, _Alloc>::
00278 _M_insert_aux(iterator __position, _Args&&... __args)
00279 #else
00280 template<typename _Tp, typename _Alloc>
00281 void
00282 vector<_Tp, _Alloc>::
00283 _M_insert_aux(iterator __position, const _Tp& __x)
00284 #endif
00285 {
00286 if (this->_M_impl._M_finish != this->_M_impl._M_end_of_storage)
00287 {
00288 this->_M_impl.construct(this->_M_impl._M_finish,
00289 _GLIBCXX_MOVE(*(this->_M_impl._M_finish
00290 - 1)));
00291 ++this->_M_impl._M_finish;
00292 #ifndef __GXX_EXPERIMENTAL_CXX0X__
00293 _Tp __x_copy = __x;
00294 #endif
00295 _GLIBCXX_MOVE_BACKWARD3(__position.base(),
00296 this->_M_impl._M_finish - 2,
00297 this->_M_impl._M_finish - 1);
00298 #ifndef __GXX_EXPERIMENTAL_CXX0X__
00299 *__position = __x_copy;
00300 #else
00301 *__position = _Tp(std::forward<_Args>(__args)...);
00302 #endif
00303 }
00304 else
00305 {
00306 const size_type __len =
00307 _M_check_len(size_type(1), "vector::_M_insert_aux");
00308 pointer __new_start(this->_M_allocate(__len));
00309 pointer __new_finish(__new_start);
00310 try
00311 {
00312 #ifdef __GXX_EXPERIMENTAL_CXX0X__
00313 this->_M_impl.construct(__new_start + (__position - begin()),
00314 std::forward<_Args>(__args)...);
00315 #endif
00316 __new_finish =
00317 std::__uninitialized_move_a(this->_M_impl._M_start,
00318 __position.base(), __new_start,
00319 _M_get_Tp_allocator());
00320 #ifndef __GXX_EXPERIMENTAL_CXX0X__
00321 this->_M_impl.construct(__new_finish, __x);
00322 #endif
00323 ++__new_finish;
00324 __new_finish =
00325 std::__uninitialized_move_a(__position.base(),
00326 this->_M_impl._M_finish,
00327 __new_finish,
00328 _M_get_Tp_allocator());
00329 }
00330 catch(...)
00331 {
00332 std::_Destroy(__new_start, __new_finish, _M_get_Tp_allocator());
00333 _M_deallocate(__new_start, __len);
00334 __throw_exception_again;
00335 }
00336 std::_Destroy(this->_M_impl._M_start, this->_M_impl._M_finish,
00337 _M_get_Tp_allocator());
00338 _M_deallocate(this->_M_impl._M_start,
00339 this->_M_impl._M_end_of_storage
00340 - this->_M_impl._M_start);
00341 this->_M_impl._M_start = __new_start;
00342 this->_M_impl._M_finish = __new_finish;
00343 this->_M_impl._M_end_of_storage = __new_start + __len;
00344 }
00345 }
00346
00347 template<typename _Tp, typename _Alloc>
00348 void
00349 vector<_Tp, _Alloc>::
00350 _M_fill_insert(iterator __position, size_type __n, const value_type& __x)
00351 {
00352 if (__n != 0)
00353 {
00354 #ifdef __GXX_EXPERIMENTAL_CXX0X__
00355 value_type __x_copy = __x;
00356 #endif
00357 if (size_type(this->_M_impl._M_end_of_storage
00358 - this->_M_impl._M_finish) >= __n)
00359 {
00360 #ifndef __GXX_EXPERIMENTAL_CXX0X__
00361 value_type __x_copy = __x;
00362 #endif
00363 const size_type __elems_after = end() - __position;
00364 pointer __old_finish(this->_M_impl._M_finish);
00365 if (__elems_after > __n)
00366 {
00367 std::__uninitialized_move_a(this->_M_impl._M_finish - __n,
00368 this->_M_impl._M_finish,
00369 this->_M_impl._M_finish,
00370 _M_get_Tp_allocator());
00371 this->_M_impl._M_finish += __n;
00372 _GLIBCXX_MOVE_BACKWARD3(__position.base(),
00373 __old_finish - __n, __old_finish);
00374 std::fill(__position.base(), __position.base() + __n,
00375 __x_copy);
00376 }
00377 else
00378 {
00379 std::__uninitialized_fill_n_a(this->_M_impl._M_finish,
00380 __n - __elems_after,
00381 __x_copy,
00382 _M_get_Tp_allocator());
00383 this->_M_impl._M_finish += __n - __elems_after;
00384 std::__uninitialized_move_a(__position.base(), __old_finish,
00385 this->_M_impl._M_finish,
00386 _M_get_Tp_allocator());
00387 this->_M_impl._M_finish += __elems_after;
00388 std::fill(__position.base(), __old_finish, __x_copy);
00389 }
00390 }
00391 else
00392 {
00393 const size_type __len =
00394 _M_check_len(__n, "vector::_M_fill_insert");
00395 pointer __new_start(this->_M_allocate(__len));
00396 pointer __new_finish(__new_start);
00397 try
00398 {
00399 __new_finish =
00400 std::__uninitialized_move_a(this->_M_impl._M_start,
00401 __position.base(),
00402 __new_start,
00403 _M_get_Tp_allocator());
00404 #ifdef __GXX_EXPERIMENTAL_CXX0X__
00405 std::__uninitialized_fill_n_a(__new_finish, __n, __x_copy,
00406 #else
00407 std::__uninitialized_fill_n_a(__new_finish, __n, __x,
00408 #endif
00409 _M_get_Tp_allocator());
00410 __new_finish += __n;
00411 __new_finish =
00412 std::__uninitialized_move_a(__position.base(),
00413 this->_M_impl._M_finish,
00414 __new_finish,
00415 _M_get_Tp_allocator());
00416 }
00417 catch(...)
00418 {
00419 std::_Destroy(__new_start, __new_finish,
00420 _M_get_Tp_allocator());
00421 _M_deallocate(__new_start, __len);
00422 __throw_exception_again;
00423 }
00424 std::_Destroy(this->_M_impl._M_start, this->_M_impl._M_finish,
00425 _M_get_Tp_allocator());
00426 _M_deallocate(this->_M_impl._M_start,
00427 this->_M_impl._M_end_of_storage
00428 - this->_M_impl._M_start);
00429 this->_M_impl._M_start = __new_start;
00430 this->_M_impl._M_finish = __new_finish;
00431 this->_M_impl._M_end_of_storage = __new_start + __len;
00432 }
00433 }
00434 }
00435
00436 template<typename _Tp, typename _Alloc>
00437 template<typename _InputIterator>
00438 void
00439 vector<_Tp, _Alloc>::
00440 _M_range_insert(iterator __pos, _InputIterator __first,
00441 _InputIterator __last, std::input_iterator_tag)
00442 {
00443 for (; __first != __last; ++__first)
00444 {
00445 __pos = insert(__pos, *__first);
00446 ++__pos;
00447 }
00448 }
00449
00450 template<typename _Tp, typename _Alloc>
00451 template<typename _ForwardIterator>
00452 void
00453 vector<_Tp, _Alloc>::
00454 _M_range_insert(iterator __position, _ForwardIterator __first,
00455 _ForwardIterator __last, std::forward_iterator_tag)
00456 {
00457 if (__first != __last)
00458 {
00459 const size_type __n = std::distance(__first, __last);
00460 if (size_type(this->_M_impl._M_end_of_storage
00461 - this->_M_impl._M_finish) >= __n)
00462 {
00463 const size_type __elems_after = end() - __position;
00464 pointer __old_finish(this->_M_impl._M_finish);
00465 if (__elems_after > __n)
00466 {
00467 std::__uninitialized_move_a(this->_M_impl._M_finish - __n,
00468 this->_M_impl._M_finish,
00469 this->_M_impl._M_finish,
00470 _M_get_Tp_allocator());
00471 this->_M_impl._M_finish += __n;
00472 _GLIBCXX_MOVE_BACKWARD3(__position.base(),
00473 __old_finish - __n, __old_finish);
00474 std::copy(__first, __last, __position);
00475 }
00476 else
00477 {
00478 _ForwardIterator __mid = __first;
00479 std::advance(__mid, __elems_after);
00480 std::__uninitialized_copy_a(__mid, __last,
00481 this->_M_impl._M_finish,
00482 _M_get_Tp_allocator());
00483 this->_M_impl._M_finish += __n - __elems_after;
00484 std::__uninitialized_move_a(__position.base(),
00485 __old_finish,
00486 this->_M_impl._M_finish,
00487 _M_get_Tp_allocator());
00488 this->_M_impl._M_finish += __elems_after;
00489 std::copy(__first, __mid, __position);
00490 }
00491 }
00492 else
00493 {
00494 const size_type __len =
00495 _M_check_len(__n, "vector::_M_range_insert");
00496 pointer __new_start(this->_M_allocate(__len));
00497 pointer __new_finish(__new_start);
00498 try
00499 {
00500 __new_finish =
00501 std::__uninitialized_move_a(this->_M_impl._M_start,
00502 __position.base(),
00503 __new_start,
00504 _M_get_Tp_allocator());
00505 __new_finish =
00506 std::__uninitialized_copy_a(__first, __last,
00507 __new_finish,
00508 _M_get_Tp_allocator());
00509 __new_finish =
00510 std::__uninitialized_move_a(__position.base(),
00511 this->_M_impl._M_finish,
00512 __new_finish,
00513 _M_get_Tp_allocator());
00514 }
00515 catch(...)
00516 {
00517 std::_Destroy(__new_start, __new_finish,
00518 _M_get_Tp_allocator());
00519 _M_deallocate(__new_start, __len);
00520 __throw_exception_again;
00521 }
00522 std::_Destroy(this->_M_impl._M_start, this->_M_impl._M_finish,
00523 _M_get_Tp_allocator());
00524 _M_deallocate(this->_M_impl._M_start,
00525 this->_M_impl._M_end_of_storage
00526 - this->_M_impl._M_start);
00527 this->_M_impl._M_start = __new_start;
00528 this->_M_impl._M_finish = __new_finish;
00529 this->_M_impl._M_end_of_storage = __new_start + __len;
00530 }
00531 }
00532 }
00533
00534
00535
00536
00537 template<typename _Alloc>
00538 void
00539 vector<bool, _Alloc>::
00540 reserve(size_type __n)
00541 {
00542 if (__n > this->max_size())
00543 __throw_length_error(__N("vector::reserve"));
00544 if (this->capacity() < __n)
00545 {
00546 _Bit_type* __q = this->_M_allocate(__n);
00547 this->_M_impl._M_finish = _M_copy_aligned(begin(), end(),
00548 iterator(__q, 0));
00549 this->_M_deallocate();
00550 this->_M_impl._M_start = iterator(__q, 0);
00551 this->_M_impl._M_end_of_storage = (__q + (__n + int(_S_word_bit) - 1)
00552 / int(_S_word_bit));
00553 }
00554 }
00555
00556 template<typename _Alloc>
00557 void
00558 vector<bool, _Alloc>::
00559 _M_fill_insert(iterator __position, size_type __n, bool __x)
00560 {
00561 if (__n == 0)
00562 return;
00563 if (capacity() - size() >= __n)
00564 {
00565 std::copy_backward(__position, end(),
00566 this->_M_impl._M_finish + difference_type(__n));
00567 std::fill(__position, __position + difference_type(__n), __x);
00568 this->_M_impl._M_finish += difference_type(__n);
00569 }
00570 else
00571 {
00572 const size_type __len =
00573 _M_check_len(__n, "vector<bool>::_M_fill_insert");
00574 _Bit_type * __q = this->_M_allocate(__len);
00575 iterator __i = _M_copy_aligned(begin(), __position,
00576 iterator(__q, 0));
00577 std::fill(__i, __i + difference_type(__n), __x);
00578 this->_M_impl._M_finish = std::copy(__position, end(),
00579 __i + difference_type(__n));
00580 this->_M_deallocate();
00581 this->_M_impl._M_end_of_storage = (__q + ((__len
00582 + int(_S_word_bit) - 1)
00583 / int(_S_word_bit)));
00584 this->_M_impl._M_start = iterator(__q, 0);
00585 }
00586 }
00587
00588 template<typename _Alloc>
00589 template<typename _ForwardIterator>
00590 void
00591 vector<bool, _Alloc>::
00592 _M_insert_range(iterator __position, _ForwardIterator __first,
00593 _ForwardIterator __last, std::forward_iterator_tag)
00594 {
00595 if (__first != __last)
00596 {
00597 size_type __n = std::distance(__first, __last);
00598 if (capacity() - size() >= __n)
00599 {
00600 std::copy_backward(__position, end(),
00601 this->_M_impl._M_finish
00602 + difference_type(__n));
00603 std::copy(__first, __last, __position);
00604 this->_M_impl._M_finish += difference_type(__n);
00605 }
00606 else
00607 {
00608 const size_type __len =
00609 _M_check_len(__n, "vector<bool>::_M_insert_range");
00610 _Bit_type * __q = this->_M_allocate(__len);
00611 iterator __i = _M_copy_aligned(begin(), __position,
00612 iterator(__q, 0));
00613 __i = std::copy(__first, __last, __i);
00614 this->_M_impl._M_finish = std::copy(__position, end(), __i);
00615 this->_M_deallocate();
00616 this->_M_impl._M_end_of_storage = (__q
00617 + ((__len
00618 + int(_S_word_bit) - 1)
00619 / int(_S_word_bit)));
00620 this->_M_impl._M_start = iterator(__q, 0);
00621 }
00622 }
00623 }
00624
00625 template<typename _Alloc>
00626 void
00627 vector<bool, _Alloc>::
00628 _M_insert_aux(iterator __position, bool __x)
00629 {
00630 if (this->_M_impl._M_finish._M_p != this->_M_impl._M_end_of_storage)
00631 {
00632 std::copy_backward(__position, this->_M_impl._M_finish,
00633 this->_M_impl._M_finish + 1);
00634 *__position = __x;
00635 ++this->_M_impl._M_finish;
00636 }
00637 else
00638 {
00639 const size_type __len =
00640 _M_check_len(size_type(1), "vector<bool>::_M_insert_aux");
00641 _Bit_type * __q = this->_M_allocate(__len);
00642 iterator __i = _M_copy_aligned(begin(), __position,
00643 iterator(__q, 0));
00644 *__i++ = __x;
00645 this->_M_impl._M_finish = std::copy(__position, end(), __i);
00646 this->_M_deallocate();
00647 this->_M_impl._M_end_of_storage = (__q + ((__len
00648 + int(_S_word_bit) - 1)
00649 / int(_S_word_bit)));
00650 this->_M_impl._M_start = iterator(__q, 0);
00651 }
00652 }
00653
00654 _GLIBCXX_END_NESTED_NAMESPACE
00655
00656 #endif