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 __GLIBCPP_INTERNAL_VECTOR_H
00062
#define __GLIBCPP_INTERNAL_VECTOR_H
00063
00064
#include <bits/stl_iterator_base_funcs.h>
00065
#include <bits/functexcept.h>
00066
#include <bits/concept_check.h>
00067
00068
namespace std
00069 {
00070
00071
00072
00073
00074
00075
00076
00077
00078
template <
class _Tp,
class _Allocator,
bool _IsStatic>
00079
class _Vector_alloc_base {
00080
public:
00081
typedef typename _Alloc_traits<_Tp, _Allocator>::allocator_type
00082 allocator_type;
00083 allocator_type get_allocator()
const {
return _M_data_allocator; }
00084
00085 _Vector_alloc_base(
const allocator_type& __a)
00086 : _M_data_allocator(__a), _M_start(0), _M_finish(0), _M_end_of_storage(0)
00087 {}
00088
00089
protected:
00090 allocator_type _M_data_allocator;
00091 _Tp* _M_start;
00092 _Tp* _M_finish;
00093 _Tp* _M_end_of_storage;
00094
00095 _Tp* _M_allocate(size_t __n)
00096 {
return _M_data_allocator.allocate(__n); }
00097
void _M_deallocate(_Tp* __p, size_t __n)
00098 {
if (__p) _M_data_allocator.deallocate(__p, __n); }
00099 };
00100
00101
00102
00103
template <
class _Tp,
class _Allocator>
00104
class _Vector_alloc_base<_Tp, _Allocator, true> {
00105
public:
00106
typedef typename _Alloc_traits<_Tp, _Allocator>::allocator_type
00107 allocator_type;
00108 allocator_type get_allocator()
const {
return allocator_type(); }
00109
00110 _Vector_alloc_base(
const allocator_type&)
00111 : _M_start(0), _M_finish(0), _M_end_of_storage(0)
00112 {}
00113
00114
protected:
00115 _Tp* _M_start;
00116 _Tp* _M_finish;
00117 _Tp* _M_end_of_storage;
00118
00119
typedef typename _Alloc_traits<_Tp, _Allocator>::_Alloc_type _Alloc_type;
00120 _Tp* _M_allocate(size_t __n)
00121 {
return _Alloc_type::allocate(__n); }
00122
void _M_deallocate(_Tp* __p, size_t __n)
00123 { _Alloc_type::deallocate(__p, __n);}
00124 };
00125
00126
template <
class _Tp,
class _Alloc>
00127
struct _Vector_base
00128 :
public _Vector_alloc_base<_Tp, _Alloc,
00129 _Alloc_traits<_Tp, _Alloc>::_S_instanceless>
00130 {
00131
typedef _Vector_alloc_base<_Tp, _Alloc,
00132 _Alloc_traits<_Tp, _Alloc>::_S_instanceless>
00133 _Base;
00134
typedef typename _Base::allocator_type allocator_type;
00135
00136 _Vector_base(
const allocator_type& __a) : _Base(__a) {}
00137 _Vector_base(size_t __n,
const allocator_type& __a) : _Base(__a) {
00138 _M_start = _M_allocate(__n);
00139 _M_finish = _M_start;
00140 _M_end_of_storage = _M_start + __n;
00141 }
00142
00143 ~_Vector_base() { _M_deallocate(_M_start, _M_end_of_storage - _M_start); }
00144 };
00145
00146
00165
template <
class _Tp,
class _Alloc = allocator<_Tp> >
00166 class vector :
protected _Vector_base<_Tp, _Alloc>
00167 {
00168
00169 __glibcpp_class_requires(_Tp, _SGIAssignableConcept)
00170
00171
private:
00172
typedef _Vector_base<_Tp, _Alloc> _Base;
00173
typedef vector<_Tp, _Alloc> vector_type;
00174
public:
00175
typedef _Tp value_type;
00176
typedef value_type* pointer;
00177
typedef const value_type* const_pointer;
00178
typedef __gnu_cxx::__normal_iterator<pointer, vector_type> iterator;
00179
typedef __gnu_cxx::__normal_iterator<const_pointer, vector_type>
00180 const_iterator;
00181
typedef value_type& reference;
00182
typedef const value_type& const_reference;
00183
typedef size_t size_type;
00184
typedef ptrdiff_t difference_type;
00185
00186
typedef typename _Base::allocator_type allocator_type;
00187 allocator_type get_allocator()
const {
return _Base::get_allocator(); }
00188
00189
typedef reverse_iterator<const_iterator> const_reverse_iterator;
00190
typedef reverse_iterator<iterator> reverse_iterator;
00191
00192
protected:
00193
using _Base::_M_allocate;
00194
using _Base::_M_deallocate;
00195
using _Base::_M_start;
00196
using _Base::_M_finish;
00197
using _Base::_M_end_of_storage;
00198
00199
protected:
00200
void _M_insert_aux(iterator __position,
const _Tp& __x);
00201
void _M_insert_aux(iterator __position);
00202
00203
public:
00208 iterator
begin() {
return iterator (_M_start); }
00209
00214 const_iterator
begin()
const
00215
{
return const_iterator (_M_start); }
00216
00221 iterator
end() {
return iterator (_M_finish); }
00222
00227 const_iterator
end()
const {
return const_iterator (_M_finish); }
00228
00233 reverse_iterator
rbegin()
00234 {
return reverse_iterator(
end()); }
00235
00240 const_reverse_iterator
rbegin()
const
00241
{
return const_reverse_iterator(
end()); }
00242
00248 reverse_iterator
rend()
00249 {
return reverse_iterator(
begin()); }
00250
00256 const_reverse_iterator
rend()
const
00257
{
return const_reverse_iterator(
begin()); }
00258
00260 size_type
size()
const
00261
{
return size_type(
end() -
begin()); }
00262
00264 size_type
max_size()
const
00265
{
return size_type(-1) /
sizeof(_Tp); }
00266
00271 size_type
capacity()
const
00272
{
return size_type(const_iterator(_M_end_of_storage) -
begin()); }
00273
00277 bool empty()
const
00278
{
return begin() ==
end(); }
00279
00289 reference operator[](size_type __n) {
return *(
begin() + __n); }
00290
00300 const_reference operator[](size_type __n)
const {
return *(
begin() + __n); }
00301
00302
void _M_range_check(size_type __n)
const {
00303
if (__n >= this->
size())
00304 __throw_out_of_range(
"vector");
00305 }
00306
00316 reference at(size_type __n)
00317 { _M_range_check(__n);
return (*this)[__n]; }
00318
00328 const_reference at(size_type __n)
const
00329
{ _M_range_check(__n);
return (*this)[__n]; }
00330
00331
00332
explicit vector(
const allocator_type& __a = allocator_type())
00333 : _Base(__a) {}
00334
00335 vector(size_type __n,
const _Tp& __value,
00336
const allocator_type& __a = allocator_type())
00337 : _Base(__n, __a)
00338 { _M_finish =
uninitialized_fill_n(_M_start, __n, __value); }
00339
00340
explicit vector(size_type __n)
00341 : _Base(__n, allocator_type())
00342 { _M_finish =
uninitialized_fill_n(_M_start, __n, _Tp()); }
00343
00344 vector(
const vector<_Tp, _Alloc>& __x)
00345 : _Base(__x.size(), __x.get_allocator())
00346 { _M_finish =
uninitialized_copy(__x.begin(), __x.end(), _M_start); }
00347
00348
00349
template <
class _InputIterator>
00350 vector(_InputIterator __first, _InputIterator __last,
00351
const allocator_type& __a = allocator_type())
00352 : _Base(__a)
00353 {
00354
typedef typename _Is_integer<_InputIterator>::_Integral _Integral;
00355 _M_initialize_aux(__first, __last, _Integral());
00356 }
00357
00358
template <
class _Integer>
00359
void _M_initialize_aux(_Integer __n, _Integer __value, __true_type)
00360 {
00361 _M_start = _M_allocate(__n);
00362 _M_end_of_storage = _M_start + __n;
00363 _M_finish =
uninitialized_fill_n(_M_start, __n, __value);
00364 }
00365
00366
template<
class _InputIterator>
00367
void
00368 _M_initialize_aux(_InputIterator __first, _InputIterator __last, __false_type)
00369 {
00370
typedef typename iterator_traits<_InputIterator>::iterator_category _IterCategory;
00371 _M_range_initialize(__first, __last, _IterCategory());
00372 }
00373
00374 ~vector()
00375 { _Destroy(_M_start, _M_finish); }
00376
00377 vector<_Tp, _Alloc>& operator=(
const vector<_Tp, _Alloc>& __x);
00378
00393 void reserve(size_type __n) {
00394
if (__n > this->
max_size())
00395 __throw_length_error(
"vector::reserve");
00396
if (this->
capacity() < __n) {
00397
const size_type __old_size =
size();
00398 pointer __tmp = _M_allocate_and_copy(__n, _M_start, _M_finish);
00399 _Destroy(_M_start, _M_finish);
00400 _M_deallocate(_M_start, _M_end_of_storage - _M_start);
00401 _M_start = __tmp;
00402 _M_finish = __tmp + __old_size;
00403 _M_end_of_storage = _M_start + __n;
00404 }
00405 }
00406
00407
00408
00409
00410
00411
00423 void assign(size_type __n,
const _Tp& __val) { _M_fill_assign(__n, __val); }
00424
void _M_fill_assign(size_type __n,
const _Tp& __val);
00425
00426
template<
class _InputIterator>
00427
void
00428 assign(_InputIterator __first, _InputIterator __last)
00429 {
00430
typedef typename _Is_integer<_InputIterator>::_Integral _Integral;
00431 _M_assign_dispatch(__first, __last, _Integral());
00432 }
00433
00434
template<
class _Integer>
00435
void
00436 _M_assign_dispatch(_Integer __n, _Integer __val, __true_type)
00437 { _M_fill_assign((size_type) __n, (_Tp) __val); }
00438
00439
template<
class _InputIter>
00440
void
00441 _M_assign_dispatch(_InputIter __first, _InputIter __last, __false_type)
00442 {
00443
typedef typename iterator_traits<_InputIter>::iterator_category _IterCategory;
00444 _M_assign_aux(__first, __last, _IterCategory());
00445 }
00446
00447
template <
class _InputIterator>
00448
void
00449 _M_assign_aux(_InputIterator __first, _InputIterator __last,
00450 input_iterator_tag);
00451
00452
template <
class _ForwardIterator>
00453
void
00454 _M_assign_aux(_ForwardIterator __first, _ForwardIterator __last,
00455 forward_iterator_tag);
00456
00461 reference
front() {
return *
begin(); }
00462
00467 const_reference
front()
const {
return *
begin(); }
00468
00473 reference
back() {
return *(
end() - 1); }
00474
00479 const_reference
back()
const {
return *(
end() - 1); }
00480
00490
void
00491 push_back(
const _Tp& __x)
00492 {
00493
if (_M_finish != _M_end_of_storage) {
00494 _Construct(_M_finish, __x);
00495 ++_M_finish;
00496 }
00497
else
00498 _M_insert_aux(
end(), __x);
00499 }
00500
00501
#ifdef _GLIBCPP_DEPRECATED
00502
00509
void
00510 push_back()
00511 {
00512
if (_M_finish != _M_end_of_storage) {
00513 _Construct(_M_finish);
00514 ++_M_finish;
00515 }
00516
else
00517 _M_insert_aux(
end());
00518 }
00519
#endif
00520
00521
void
00522
swap(
vector<_Tp, _Alloc>& __x)
00523 {
00524
std::swap(_M_start, __x._M_start);
00525
std::swap(_M_finish, __x._M_finish);
00526
std::swap(_M_end_of_storage, __x._M_end_of_storage);
00527 }
00528
00540 iterator
00541 insert(iterator __position,
const _Tp& __x)
00542 {
00543 size_type __n = __position -
begin();
00544
if (_M_finish != _M_end_of_storage && __position ==
end()) {
00545 _Construct(_M_finish, __x);
00546 ++_M_finish;
00547 }
00548
else
00549 _M_insert_aux(iterator(__position), __x);
00550
return begin() + __n;
00551 }
00552
00564
iterator
00565 insert(iterator __position)
00566 {
00567 size_type __n = __position -
begin();
00568
if (_M_finish != _M_end_of_storage && __position ==
end()) {
00569 _Construct(_M_finish);
00570 ++_M_finish;
00571 }
00572
else
00573 _M_insert_aux(iterator(__position));
00574
return begin() + __n;
00575 }
00576
00577
00578
template<
class _InputIterator>
00579
void
00580 insert(
iterator __pos, _InputIterator __first, _InputIterator __last)
00581 {
00582
typedef typename _Is_integer<_InputIterator>::_Integral _Integral;
00583 _M_insert_dispatch(__pos, __first, __last, _Integral());
00584 }
00585
00586
template <
class _Integer>
00587
void
00588 _M_insert_dispatch(iterator __pos, _Integer __n, _Integer __val, __true_type)
00589 { _M_fill_insert(__pos, static_cast<size_type>(__n), static_cast<_Tp>(__val)); }
00590
00591
template<
class _InputIterator>
00592
void
00593 _M_insert_dispatch(iterator __pos,
00594 _InputIterator __first, _InputIterator __last,
00595 __false_type)
00596 {
00597
typedef typename iterator_traits<_InputIterator>::iterator_category _IterCategory;
00598 _M_range_insert(__pos, __first, __last, _IterCategory());
00599 }
00600
00614 void insert (iterator __pos, size_type __n,
const _Tp& __x)
00615 { _M_fill_insert(__pos, __n, __x); }
00616
00617
void _M_fill_insert (
iterator __pos, size_type __n,
const _Tp& __x);
00618
00628 void pop_back() {
00629 --_M_finish;
00630 _Destroy(_M_finish);
00631 }
00632
00647 iterator erase(iterator __position) {
00648
if (__position + 1 !=
end())
00649
copy(__position + 1,
end(), __position);
00650 --_M_finish;
00651 _Destroy(_M_finish);
00652
return __position;
00653 }
00654
00670 iterator erase(iterator __first, iterator __last) {
00671 iterator __i(
copy(__last,
end(), __first));
00672 _Destroy(__i,
end());
00673 _M_finish = _M_finish - (__last - __first);
00674
return __first;
00675 }
00676
00687 void resize(size_type __new_size,
const _Tp& __x) {
00688
if (__new_size <
size())
00689 erase(
begin() + __new_size,
end());
00690
else
00691 insert(
end(), __new_size -
size(), __x);
00692 }
00693
00703 void resize(size_type __new_size) { resize(__new_size, _Tp()); }
00704
00711 void clear() { erase(
begin(),
end()); }
00712
00713
protected:
00714
00715
template <
class _ForwardIterator>
00716 pointer _M_allocate_and_copy(size_type __n, _ForwardIterator __first,
00717 _ForwardIterator __last)
00718 {
00719 pointer __result = _M_allocate(__n);
00720
try {
00721
uninitialized_copy(__first, __last, __result);
00722
return __result;
00723 }
00724
catch(...)
00725 {
00726 _M_deallocate(__result, __n);
00727 __throw_exception_again;
00728 }
00729 }
00730
00731
template <
class _InputIterator>
00732
void _M_range_initialize(_InputIterator __first,
00733 _InputIterator __last, input_iterator_tag)
00734 {
00735
for ( ; __first != __last; ++__first)
00736
push_back(*__first);
00737 }
00738
00739
00740
template <
class _ForwardIterator>
00741
void _M_range_initialize(_ForwardIterator __first,
00742 _ForwardIterator __last, forward_iterator_tag)
00743 {
00744 size_type __n =
distance(__first, __last);
00745 _M_start = _M_allocate(__n);
00746 _M_end_of_storage = _M_start + __n;
00747 _M_finish =
uninitialized_copy(__first, __last, _M_start);
00748 }
00749
00750
template <
class _InputIterator>
00751
void _M_range_insert(iterator __pos,
00752 _InputIterator __first, _InputIterator __last,
00753 input_iterator_tag);
00754
00755
template <
class _ForwardIterator>
00756
void _M_range_insert(iterator __pos,
00757 _ForwardIterator __first, _ForwardIterator __last,
00758 forward_iterator_tag);
00759 };
00760
00761
template <
class _Tp,
class _Alloc>
00762
inline bool
00763
operator==(
const vector<_Tp, _Alloc>& __x,
const vector<_Tp, _Alloc>& __y)
00764 {
00765
return __x.size() == __y.size() &&
00766
equal(__x.begin(), __x.end(), __y.begin());
00767 }
00768
00769
template <
class _Tp,
class _Alloc>
00770
inline bool
00771 operator<(const vector<_Tp, _Alloc>& __x,
const vector<_Tp, _Alloc>& __y)
00772 {
00773
return lexicographical_compare(__x.begin(), __x.end(),
00774 __y.begin(), __y.end());
00775 }
00776
00777
template <
class _Tp,
class _Alloc>
00778
inline void swap(vector<_Tp, _Alloc>& __x, vector<_Tp, _Alloc>& __y)
00779 {
00780 __x.swap(__y);
00781 }
00782
00783
template <
class _Tp,
class _Alloc>
00784
inline bool
00785
operator!=(
const vector<_Tp, _Alloc>& __x,
const vector<_Tp, _Alloc>& __y) {
00786
return !(__x == __y);
00787 }
00788
00789
template <
class _Tp,
class _Alloc>
00790
inline bool
00791
operator>(
const vector<_Tp, _Alloc>& __x,
const vector<_Tp, _Alloc>& __y) {
00792
return __y < __x;
00793 }
00794
00795
template <
class _Tp,
class _Alloc>
00796
inline bool
00797 operator<=(const vector<_Tp, _Alloc>& __x,
const vector<_Tp, _Alloc>& __y) {
00798
return !(__y < __x);
00799 }
00800
00801
template <
class _Tp,
class _Alloc>
00802
inline bool
00803
operator>=(
const vector<_Tp, _Alloc>& __x,
const vector<_Tp, _Alloc>& __y) {
00804
return !(__x < __y);
00805 }
00806
00807
template <
class _Tp,
class _Alloc>
00808 vector<_Tp,_Alloc>&
00809 vector<_Tp,_Alloc>::operator=(
const vector<_Tp, _Alloc>& __x)
00810 {
00811
if (&__x !=
this) {
00812
const size_type __xlen = __x.size();
00813
if (__xlen >
capacity()) {
00814 pointer __tmp = _M_allocate_and_copy(__xlen, __x.begin(), __x.end());
00815 _Destroy(_M_start, _M_finish);
00816 _M_deallocate(_M_start, _M_end_of_storage - _M_start);
00817 _M_start = __tmp;
00818 _M_end_of_storage = _M_start + __xlen;
00819 }
00820
else if (
size() >= __xlen) {
00821 iterator __i(
copy(__x.begin(), __x.end(),
begin()));
00822 _Destroy(__i,
end());
00823 }
00824
else {
00825
copy(__x.begin(), __x.begin() +
size(), _M_start);
00826
uninitialized_copy(__x.begin() +
size(), __x.end(), _M_finish);
00827 }
00828 _M_finish = _M_start + __xlen;
00829 }
00830
return *
this;
00831 }
00832
00833
template <
class _Tp,
class _Alloc>
00834
void vector<_Tp, _Alloc>::_M_fill_assign(size_t __n,
const value_type& __val)
00835 {
00836
if (__n >
capacity()) {
00837 vector<_Tp, _Alloc> __tmp(__n, __val, get_allocator());
00838 __tmp.swap(*
this);
00839 }
00840
else if (__n >
size()) {
00841
fill(
begin(),
end(), __val);
00842 _M_finish =
uninitialized_fill_n(_M_finish, __n -
size(), __val);
00843 }
00844
else
00845
erase(
fill_n(
begin(), __n, __val),
end());
00846 }
00847
00848
template <
class _Tp,
class _Alloc>
template <
class _InputIter>
00849
void vector<_Tp, _Alloc>::_M_assign_aux(_InputIter __first, _InputIter __last,
00850 input_iterator_tag) {
00851 iterator __cur(
begin());
00852
for ( ; __first != __last && __cur !=
end(); ++__cur, ++__first)
00853 *__cur = *__first;
00854
if (__first == __last)
00855
erase(__cur,
end());
00856
else
00857 insert(
end(), __first, __last);
00858 }
00859
00860
template <
class _Tp,
class _Alloc>
template <
class _ForwardIter>
00861
void
00862 vector<_Tp, _Alloc>::_M_assign_aux(_ForwardIter __first, _ForwardIter __last,
00863 forward_iterator_tag) {
00864 size_type __len =
distance(__first, __last);
00865
00866
if (__len >
capacity()) {
00867 pointer __tmp(_M_allocate_and_copy(__len, __first, __last));
00868 _Destroy(_M_start, _M_finish);
00869 _M_deallocate(_M_start, _M_end_of_storage - _M_start);
00870 _M_start = __tmp;
00871 _M_end_of_storage = _M_finish = _M_start + __len;
00872 }
00873
else if (
size() >= __len) {
00874 iterator __new_finish(
copy(__first, __last, _M_start));
00875 _Destroy(__new_finish,
end());
00876 _M_finish = __new_finish.base();
00877 }
00878
else {
00879 _ForwardIter __mid = __first;
00880
advance(__mid,
size());
00881
copy(__first, __mid, _M_start);
00882 _M_finish =
uninitialized_copy(__mid, __last, _M_finish);
00883 }
00884 }
00885
00886
template <
class _Tp,
class _Alloc>
00887
void
00888 vector<_Tp, _Alloc>::_M_insert_aux(iterator __position,
const _Tp& __x)
00889 {
00890
if (_M_finish != _M_end_of_storage) {
00891 _Construct(_M_finish, *(_M_finish - 1));
00892 ++_M_finish;
00893 _Tp __x_copy = __x;
00894
copy_backward(__position, iterator(_M_finish - 2), iterator(_M_finish- 1));
00895 *__position = __x_copy;
00896 }
00897
else {
00898
const size_type __old_size =
size();
00899
const size_type __len = __old_size != 0 ? 2 * __old_size : 1;
00900 iterator __new_start(_M_allocate(__len));
00901 iterator __new_finish(__new_start);
00902
try {
00903 __new_finish =
uninitialized_copy(iterator(_M_start), __position,
00904 __new_start);
00905 _Construct(__new_finish.base(), __x);
00906 ++__new_finish;
00907 __new_finish =
uninitialized_copy(__position, iterator(_M_finish),
00908 __new_finish);
00909 }
00910
catch(...)
00911 {
00912 _Destroy(__new_start,__new_finish);
00913 _M_deallocate(__new_start.base(),__len);
00914 __throw_exception_again;
00915 }
00916 _Destroy(
begin(),
end());
00917 _M_deallocate(_M_start, _M_end_of_storage - _M_start);
00918 _M_start = __new_start.base();
00919 _M_finish = __new_finish.base();
00920 _M_end_of_storage = __new_start.base() + __len;
00921 }
00922 }
00923
00924
template <
class _Tp,
class _Alloc>
00925
void
00926 vector<_Tp, _Alloc>::_M_insert_aux(iterator __position)
00927 {
00928
if (_M_finish != _M_end_of_storage) {
00929 _Construct(_M_finish, *(_M_finish - 1));
00930 ++_M_finish;
00931
copy_backward(__position, iterator(_M_finish - 2),
00932 iterator(_M_finish - 1));
00933 *__position = _Tp();
00934 }
00935
else {
00936
const size_type __old_size =
size();
00937
const size_type __len = __old_size != 0 ? 2 * __old_size : 1;
00938 pointer __new_start = _M_allocate(__len);
00939 pointer __new_finish = __new_start;
00940
try {
00941 __new_finish =
uninitialized_copy(iterator(_M_start), __position,
00942 __new_start);
00943 _Construct(__new_finish);
00944 ++__new_finish;
00945 __new_finish =
uninitialized_copy(__position, iterator(_M_finish),
00946 __new_finish);
00947 }
00948
catch(...)
00949 {
00950 _Destroy(__new_start,__new_finish);
00951 _M_deallocate(__new_start,__len);
00952 __throw_exception_again;
00953 }
00954 _Destroy(
begin(),
end());
00955 _M_deallocate(_M_start, _M_end_of_storage - _M_start);
00956 _M_start = __new_start;
00957 _M_finish = __new_finish;
00958 _M_end_of_storage = __new_start + __len;
00959 }
00960 }
00961
00962
template <
class _Tp,
class _Alloc>
00963
void vector<_Tp, _Alloc>::_M_fill_insert(iterator __position, size_type __n,
00964
const _Tp& __x)
00965 {
00966
if (__n != 0) {
00967
if (size_type(_M_end_of_storage - _M_finish) >= __n) {
00968 _Tp __x_copy = __x;
00969
const size_type __elems_after =
end() - __position;
00970 iterator __old_finish(_M_finish);
00971
if (__elems_after > __n) {
00972
uninitialized_copy(_M_finish - __n, _M_finish, _M_finish);
00973 _M_finish += __n;
00974
copy_backward(__position, __old_finish - __n, __old_finish);
00975
fill(__position, __position + __n, __x_copy);
00976 }
00977
else {
00978
uninitialized_fill_n(_M_finish, __n - __elems_after, __x_copy);
00979 _M_finish += __n - __elems_after;
00980
uninitialized_copy(__position, __old_finish, _M_finish);
00981 _M_finish += __elems_after;
00982
fill(__position, __old_finish, __x_copy);
00983 }
00984 }
00985
else {
00986
const size_type __old_size =
size();
00987
const size_type __len = __old_size +
max(__old_size, __n);
00988 iterator __new_start(_M_allocate(__len));
00989 iterator __new_finish(__new_start);
00990
try {
00991 __new_finish =
uninitialized_copy(
begin(), __position, __new_start);
00992 __new_finish =
uninitialized_fill_n(__new_finish, __n, __x);
00993 __new_finish
00994 =
uninitialized_copy(__position,
end(), __new_finish);
00995 }
00996
catch(...)
00997 {
00998 _Destroy(__new_start,__new_finish);
00999 _M_deallocate(__new_start.base(),__len);
01000 __throw_exception_again;
01001 }
01002 _Destroy(_M_start, _M_finish);
01003 _M_deallocate(_M_start, _M_end_of_storage - _M_start);
01004 _M_start = __new_start.base();
01005 _M_finish = __new_finish.base();
01006 _M_end_of_storage = __new_start.base() + __len;
01007 }
01008 }
01009 }
01010
01011
template <
class _Tp,
class _Alloc>
template <
class _InputIterator>
01012
void
01013 vector<_Tp, _Alloc>::_M_range_insert(iterator __pos,
01014 _InputIterator __first,
01015 _InputIterator __last,
01016 input_iterator_tag)
01017 {
01018
for ( ; __first != __last; ++__first) {
01019 __pos = insert(__pos, *__first);
01020 ++__pos;
01021 }
01022 }
01023
01024
template <
class _Tp,
class _Alloc>
template <
class _ForwardIterator>
01025
void
01026 vector<_Tp, _Alloc>::_M_range_insert(iterator __position,
01027 _ForwardIterator __first,
01028 _ForwardIterator __last,
01029 forward_iterator_tag)
01030 {
01031
if (__first != __last) {
01032 size_type __n =
distance(__first, __last);
01033
if (size_type(_M_end_of_storage - _M_finish) >= __n) {
01034
const size_type __elems_after =
end() - __position;
01035 iterator __old_finish(_M_finish);
01036
if (__elems_after > __n) {
01037
uninitialized_copy(_M_finish - __n, _M_finish, _M_finish);
01038 _M_finish += __n;
01039
copy_backward(__position, __old_finish - __n, __old_finish);
01040
copy(__first, __last, __position);
01041 }
01042
else {
01043 _ForwardIterator __mid = __first;
01044
advance(__mid, __elems_after);
01045
uninitialized_copy(__mid, __last, _M_finish);
01046 _M_finish += __n - __elems_after;
01047
uninitialized_copy(__position, __old_finish, _M_finish);
01048 _M_finish += __elems_after;
01049
copy(__first, __mid, __position);
01050 }
01051 }
01052
else {
01053
const size_type __old_size =
size();
01054
const size_type __len = __old_size +
max(__old_size, __n);
01055 iterator __new_start(_M_allocate(__len));
01056 iterator __new_finish(__new_start);
01057
try {
01058 __new_finish =
uninitialized_copy(iterator(_M_start),
01059 __position, __new_start);
01060 __new_finish =
uninitialized_copy(__first, __last, __new_finish);
01061 __new_finish
01062 =
uninitialized_copy(__position, iterator(_M_finish), __new_finish);
01063 }
01064
catch(...)
01065 {
01066 _Destroy(__new_start,__new_finish);
01067 _M_deallocate(__new_start.base(), __len);
01068 __throw_exception_again;
01069 }
01070 _Destroy(_M_start, _M_finish);
01071 _M_deallocate(_M_start, _M_end_of_storage - _M_start);
01072 _M_start = __new_start.base();
01073 _M_finish = __new_finish.base();
01074 _M_end_of_storage = __new_start.base() + __len;
01075 }
01076 }
01077 }
01078
01079 }
01080
01081
#endif
01082
01083
01084
01085