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