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