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 #ifndef __SGI_STL_INTERNAL_VECTOR_H
00061 #define __SGI_STL_INTERNAL_VECTOR_H
00062
00063 #include <bits/stl_iterator_base_funcs.h>
00064 #include <bits/functexcept.h>
00065 #include <bits/concept_check.h>
00066
00067 namespace std
00068 {
00069
00070
00071
00072
00073
00074
00075
00076
00077 template <class _Tp, class _Allocator, bool _IsStatic>
00078 class _Vector_alloc_base {
00079 public:
00080 typedef typename _Alloc_traits<_Tp, _Allocator>::allocator_type
00081 allocator_type;
00082 allocator_type get_allocator() const { return _M_data_allocator; }
00083
00084 _Vector_alloc_base(const allocator_type& __a)
00085 : _M_data_allocator(__a), _M_start(0), _M_finish(0), _M_end_of_storage(0)
00086 {}
00087
00088 protected:
00089 allocator_type _M_data_allocator;
00090 _Tp* _M_start;
00091 _Tp* _M_finish;
00092 _Tp* _M_end_of_storage;
00093
00094 _Tp* _M_allocate(size_t __n)
00095 { return _M_data_allocator.allocate(__n); }
00096 void _M_deallocate(_Tp* __p, size_t __n)
00097 { if (__p) _M_data_allocator.deallocate(__p, __n); }
00098 };
00099
00100
00101
00102 template <class _Tp, class _Allocator>
00103 class _Vector_alloc_base<_Tp, _Allocator, true> {
00104 public:
00105 typedef typename _Alloc_traits<_Tp, _Allocator>::allocator_type
00106 allocator_type;
00107 allocator_type get_allocator() const { return allocator_type(); }
00108
00109 _Vector_alloc_base(const allocator_type&)
00110 : _M_start(0), _M_finish(0), _M_end_of_storage(0)
00111 {}
00112
00113 protected:
00114 _Tp* _M_start;
00115 _Tp* _M_finish;
00116 _Tp* _M_end_of_storage;
00117
00118 typedef typename _Alloc_traits<_Tp, _Allocator>::_Alloc_type _Alloc_type;
00119 _Tp* _M_allocate(size_t __n)
00120 { return _Alloc_type::allocate(__n); }
00121 void _M_deallocate(_Tp* __p, size_t __n)
00122 { _Alloc_type::deallocate(__p, __n);}
00123 };
00124
00125 template <class _Tp, class _Alloc>
00126 struct _Vector_base
00127 : public _Vector_alloc_base<_Tp, _Alloc,
00128 _Alloc_traits<_Tp, _Alloc>::_S_instanceless>
00129 {
00130 typedef _Vector_alloc_base<_Tp, _Alloc,
00131 _Alloc_traits<_Tp, _Alloc>::_S_instanceless>
00132 _Base;
00133 typedef typename _Base::allocator_type allocator_type;
00134
00135 _Vector_base(const allocator_type& __a) : _Base(__a) {}
00136 _Vector_base(size_t __n, const allocator_type& __a) : _Base(__a) {
00137 _M_start = _M_allocate(__n);
00138 _M_finish = _M_start;
00139 _M_end_of_storage = _M_start + __n;
00140 }
00141
00142 ~_Vector_base() { _M_deallocate(_M_start, _M_end_of_storage - _M_start); }
00143 };
00144
00145
00146 template <class _Tp, class _Alloc = allocator<_Tp> >
00147 class vector : protected _Vector_base<_Tp, _Alloc>
00148 {
00149
00150 __glibcpp_class_requires(_Tp, _SGIAssignableConcept);
00151
00152 private:
00153 typedef _Vector_base<_Tp, _Alloc> _Base;
00154 typedef vector<_Tp, _Alloc> vector_type;
00155 public:
00156 typedef _Tp value_type;
00157 typedef value_type* pointer;
00158 typedef const value_type* const_pointer;
00159 typedef __normal_iterator<pointer, vector_type> iterator;
00160 typedef __normal_iterator<const_pointer, vector_type> const_iterator;
00161 typedef value_type& reference;
00162 typedef const value_type& const_reference;
00163 typedef size_t size_type;
00164 typedef ptrdiff_t difference_type;
00165
00166 typedef typename _Base::allocator_type allocator_type;
00167 allocator_type get_allocator() const { return _Base::get_allocator(); }
00168
00169 typedef reverse_iterator<const_iterator> const_reverse_iterator;
00170 typedef reverse_iterator<iterator> reverse_iterator;
00171
00172 protected:
00173 using _Base::_M_allocate;
00174 using _Base::_M_deallocate;
00175 using _Base::_M_start;
00176 using _Base::_M_finish;
00177 using _Base::_M_end_of_storage;
00178
00179 protected:
00180 void _M_insert_aux(iterator __position, const _Tp& __x);
00181 void _M_insert_aux(iterator __position);
00182
00183 public:
00184 iterator begin() { return iterator (_M_start); }
00185 const_iterator begin() const
00186 { return const_iterator (_M_start); }
00187 iterator end() { return iterator (_M_finish); }
00188 const_iterator end() const { return const_iterator (_M_finish); }
00189
00190 reverse_iterator rbegin()
00191 { return reverse_iterator(end()); }
00192 const_reverse_iterator rbegin() const
00193 { return const_reverse_iterator(end()); }
00194 reverse_iterator rend()
00195 { return reverse_iterator(begin()); }
00196 const_reverse_iterator rend() const
00197 { return const_reverse_iterator(begin()); }
00198
00199 size_type size() const
00200 { return size_type(end() - begin()); }
00201 size_type max_size() const
00202 { return size_type(-1) / sizeof(_Tp); }
00203 size_type capacity() const
00204 { return size_type(const_iterator(_M_end_of_storage) - begin()); }
00205 bool empty() const
00206 { return begin() == end(); }
00207
00208 reference operator[](size_type __n) { return *(begin() + __n); }
00209 const_reference operator[](size_type __n) const { return *(begin() + __n); }
00210
00211 void _M_range_check(size_type __n) const {
00212 if (__n >= this->size())
00213 __throw_out_of_range("vector");
00214 }
00215
00216 reference at(size_type __n)
00217 { _M_range_check(__n); return (*this)[__n]; }
00218 const_reference at(size_type __n) const
00219 { _M_range_check(__n); return (*this)[__n]; }
00220
00221 explicit vector(const allocator_type& __a = allocator_type())
00222 : _Base(__a) {}
00223
00224 vector(size_type __n, const _Tp& __value,
00225 const allocator_type& __a = allocator_type())
00226 : _Base(__n, __a)
00227 { _M_finish = uninitialized_fill_n(_M_start, __n, __value); }
00228
00229 explicit vector(size_type __n)
00230 : _Base(__n, allocator_type())
00231 { _M_finish = uninitialized_fill_n(_M_start, __n, _Tp()); }
00232
00233 vector(const vector<_Tp, _Alloc>& __x)
00234 : _Base(__x.size(), __x.get_allocator())
00235 { _M_finish = uninitialized_copy(__x.begin(), __x.end(), _M_start); }
00236
00237
00238 template <class _InputIterator>
00239 vector(_InputIterator __first, _InputIterator __last,
00240 const allocator_type& __a = allocator_type()) : _Base(__a) {
00241 typedef typename _Is_integer<_InputIterator>::_Integral _Integral;
00242 _M_initialize_aux(__first, __last, _Integral());
00243 }
00244
00245 template <class _Integer>
00246 void _M_initialize_aux(_Integer __n, _Integer __value, __true_type) {
00247 _M_start = _M_allocate(__n);
00248 _M_end_of_storage = _M_start + __n;
00249 _M_finish = uninitialized_fill_n(_M_start, __n, __value);
00250 }
00251
00252 template <class _InputIterator>
00253 void _M_initialize_aux(_InputIterator __first, _InputIterator __last,
00254 __false_type) {
00255 _M_range_initialize(__first, __last, __iterator_category(__first));
00256 }
00257
00258 ~vector() { destroy(_M_start, _M_finish); }
00259
00260 vector<_Tp, _Alloc>& operator=(const vector<_Tp, _Alloc>& __x);
00261 void reserve(size_type __n) {
00262 if (capacity() < __n) {
00263 const size_type __old_size = size();
00264 pointer __tmp = _M_allocate_and_copy(__n, _M_start, _M_finish);
00265 destroy(_M_start, _M_finish);
00266 _M_deallocate(_M_start, _M_end_of_storage - _M_start);
00267 _M_start = __tmp;
00268 _M_finish = __tmp + __old_size;
00269 _M_end_of_storage = _M_start + __n;
00270 }
00271 }
00272
00273
00274
00275
00276
00277
00278 void assign(size_type __n, const _Tp& __val) { _M_fill_assign(__n, __val); }
00279 void _M_fill_assign(size_type __n, const _Tp& __val);
00280
00281 template <class _InputIterator>
00282 void assign(_InputIterator __first, _InputIterator __last) {
00283 typedef typename _Is_integer<_InputIterator>::_Integral _Integral;
00284 _M_assign_dispatch(__first, __last, _Integral());
00285 }
00286
00287 template <class _Integer>
00288 void _M_assign_dispatch(_Integer __n, _Integer __val, __true_type)
00289 { _M_fill_assign((size_type) __n, (_Tp) __val); }
00290
00291 template <class _InputIter>
00292 void _M_assign_dispatch(_InputIter __first, _InputIter __last, __false_type)
00293 { _M_assign_aux(__first, __last, __iterator_category(__first)); }
00294
00295 template <class _InputIterator>
00296 void _M_assign_aux(_InputIterator __first, _InputIterator __last,
00297 input_iterator_tag);
00298
00299 template <class _ForwardIterator>
00300 void _M_assign_aux(_ForwardIterator __first, _ForwardIterator __last,
00301 forward_iterator_tag);
00302
00303 reference front() { return *begin(); }
00304 const_reference front() const { return *begin(); }
00305 reference back() { return *(end() - 1); }
00306 const_reference back() const { return *(end() - 1); }
00307
00308 void push_back(const _Tp& __x) {
00309 if (_M_finish != _M_end_of_storage) {
00310 construct(_M_finish, __x);
00311 ++_M_finish;
00312 }
00313 else
00314 _M_insert_aux(end(), __x);
00315 }
00316 void push_back() {
00317 if (_M_finish != _M_end_of_storage) {
00318 construct(_M_finish);
00319 ++_M_finish;
00320 }
00321 else
00322 _M_insert_aux(end());
00323 }
00324 void swap(vector<_Tp, _Alloc>& __x) {
00325 std::swap(_M_start, __x._M_start);
00326 std::swap(_M_finish, __x._M_finish);
00327 std::swap(_M_end_of_storage, __x._M_end_of_storage);
00328 }
00329
00330 iterator insert(iterator __position, const _Tp& __x) {
00331 size_type __n = __position - begin();
00332 if (_M_finish != _M_end_of_storage && __position == end()) {
00333 construct(_M_finish, __x);
00334 ++_M_finish;
00335 }
00336 else
00337 _M_insert_aux(iterator(__position), __x);
00338 return begin() + __n;
00339 }
00340 iterator insert(iterator __position) {
00341 size_type __n = __position - begin();
00342 if (_M_finish != _M_end_of_storage && __position == end()) {
00343 construct(_M_finish);
00344 ++_M_finish;
00345 }
00346 else
00347 _M_insert_aux(iterator(__position));
00348 return begin() + __n;
00349 }
00350
00351 template <class _InputIterator>
00352 void insert(iterator __pos, _InputIterator __first, _InputIterator __last) {
00353 typedef typename _Is_integer<_InputIterator>::_Integral _Integral;
00354 _M_insert_dispatch(__pos, __first, __last, _Integral());
00355 }
00356
00357 template <class _Integer>
00358 void _M_insert_dispatch(iterator __pos, _Integer __n, _Integer __val,
00359 __true_type)
00360 { _M_fill_insert(__pos, (size_type) __n, (_Tp) __val); }
00361
00362 template <class _InputIterator>
00363 void _M_insert_dispatch(iterator __pos,
00364 _InputIterator __first, _InputIterator __last,
00365 __false_type) {
00366 _M_range_insert(__pos, __first, __last, __iterator_category(__first));
00367 }
00368
00369 void insert (iterator __pos, size_type __n, const _Tp& __x)
00370 { _M_fill_insert(__pos, __n, __x); }
00371
00372 void _M_fill_insert (iterator __pos, size_type __n, const _Tp& __x);
00373
00374 void pop_back() {
00375 --_M_finish;
00376 destroy(_M_finish);
00377 }
00378 iterator erase(iterator __position) {
00379 if (__position + 1 != end())
00380 copy(__position + 1, end(), __position);
00381 --_M_finish;
00382 destroy(_M_finish);
00383 return __position;
00384 }
00385 iterator erase(iterator __first, iterator __last) {
00386 iterator __i(copy(__last, end(), __first));
00387 destroy(__i, end());
00388 _M_finish = _M_finish - (__last - __first);
00389 return __first;
00390 }
00391
00392 void resize(size_type __new_size, const _Tp& __x) {
00393 if (__new_size < size())
00394 erase(begin() + __new_size, end());
00395 else
00396 insert(end(), __new_size - size(), __x);
00397 }
00398 void resize(size_type __new_size) { resize(__new_size, _Tp()); }
00399 void clear() { erase(begin(), end()); }
00400
00401 protected:
00402
00403 template <class _ForwardIterator>
00404 pointer _M_allocate_and_copy(size_type __n, _ForwardIterator __first,
00405 _ForwardIterator __last)
00406 {
00407 pointer __result = _M_allocate(__n);
00408 __STL_TRY {
00409 uninitialized_copy(__first, __last, __result);
00410 return __result;
00411 }
00412 __STL_UNWIND(_M_deallocate(__result, __n));
00413 }
00414
00415 template <class _InputIterator>
00416 void _M_range_initialize(_InputIterator __first,
00417 _InputIterator __last, input_iterator_tag)
00418 {
00419 for ( ; __first != __last; ++__first)
00420 push_back(*__first);
00421 }
00422
00423
00424 template <class _ForwardIterator>
00425 void _M_range_initialize(_ForwardIterator __first,
00426 _ForwardIterator __last, forward_iterator_tag)
00427 {
00428 size_type __n = 0;
00429 distance(__first, __last, __n);
00430 _M_start = _M_allocate(__n);
00431 _M_end_of_storage = _M_start + __n;
00432 _M_finish = uninitialized_copy(__first, __last, _M_start);
00433 }
00434
00435 template <class _InputIterator>
00436 void _M_range_insert(iterator __pos,
00437 _InputIterator __first, _InputIterator __last,
00438 input_iterator_tag);
00439
00440 template <class _ForwardIterator>
00441 void _M_range_insert(iterator __pos,
00442 _ForwardIterator __first, _ForwardIterator __last,
00443 forward_iterator_tag);
00444 };
00445
00446 template <class _Tp, class _Alloc>
00447 inline bool
00448 operator==(const vector<_Tp, _Alloc>& __x, const vector<_Tp, _Alloc>& __y)
00449 {
00450 return __x.size() == __y.size() &&
00451 equal(__x.begin(), __x.end(), __y.begin());
00452 }
00453
00454 template <class _Tp, class _Alloc>
00455 inline bool
00456 operator<(const vector<_Tp, _Alloc>& __x, const vector<_Tp, _Alloc>& __y)
00457 {
00458 return lexicographical_compare(__x.begin(), __x.end(),
00459 __y.begin(), __y.end());
00460 }
00461
00462 template <class _Tp, class _Alloc>
00463 inline void swap(vector<_Tp, _Alloc>& __x, vector<_Tp, _Alloc>& __y)
00464 {
00465 __x.swap(__y);
00466 }
00467
00468 template <class _Tp, class _Alloc>
00469 inline bool
00470 operator!=(const vector<_Tp, _Alloc>& __x, const vector<_Tp, _Alloc>& __y) {
00471 return !(__x == __y);
00472 }
00473
00474 template <class _Tp, class _Alloc>
00475 inline bool
00476 operator>(const vector<_Tp, _Alloc>& __x, const vector<_Tp, _Alloc>& __y) {
00477 return __y < __x;
00478 }
00479
00480 template <class _Tp, class _Alloc>
00481 inline bool
00482 operator<=(const vector<_Tp, _Alloc>& __x, const vector<_Tp, _Alloc>& __y) {
00483 return !(__y < __x);
00484 }
00485
00486 template <class _Tp, class _Alloc>
00487 inline bool
00488 operator>=(const vector<_Tp, _Alloc>& __x, const vector<_Tp, _Alloc>& __y) {
00489 return !(__x < __y);
00490 }
00491
00492 template <class _Tp, class _Alloc>
00493 vector<_Tp,_Alloc>&
00494 vector<_Tp,_Alloc>::operator=(const vector<_Tp, _Alloc>& __x)
00495 {
00496 if (&__x != this) {
00497 const size_type __xlen = __x.size();
00498 if (__xlen > capacity()) {
00499 pointer __tmp = _M_allocate_and_copy(__xlen, __x.begin(), __x.end());
00500 destroy(_M_start, _M_finish);
00501 _M_deallocate(_M_start, _M_end_of_storage - _M_start);
00502 _M_start = __tmp;
00503 _M_end_of_storage = _M_start + __xlen;
00504 }
00505 else if (size() >= __xlen) {
00506 iterator __i(copy(__x.begin(), __x.end(), begin()));
00507 destroy(__i, end());
00508 }
00509 else {
00510 copy(__x.begin(), __x.begin() + size(), _M_start);
00511 uninitialized_copy(__x.begin() + size(), __x.end(), _M_finish);
00512 }
00513 _M_finish = _M_start + __xlen;
00514 }
00515 return *this;
00516 }
00517
00518 template <class _Tp, class _Alloc>
00519 void vector<_Tp, _Alloc>::_M_fill_assign(size_t __n, const value_type& __val)
00520 {
00521 if (__n > capacity()) {
00522 vector<_Tp, _Alloc> __tmp(__n, __val, get_allocator());
00523 __tmp.swap(*this);
00524 }
00525 else if (__n > size()) {
00526 fill(begin(), end(), __val);
00527 _M_finish = uninitialized_fill_n(_M_finish, __n - size(), __val);
00528 }
00529 else
00530 erase(fill_n(begin(), __n, __val), end());
00531 }
00532
00533 template <class _Tp, class _Alloc> template <class _InputIter>
00534 void vector<_Tp, _Alloc>::_M_assign_aux(_InputIter __first, _InputIter __last,
00535 input_iterator_tag) {
00536 iterator __cur(begin());
00537 for ( ; __first != __last && __cur != end(); ++__cur, ++__first)
00538 *__cur = *__first;
00539 if (__first == __last)
00540 erase(__cur, end());
00541 else
00542 insert(end(), __first, __last);
00543 }
00544
00545 template <class _Tp, class _Alloc> template <class _ForwardIter>
00546 void
00547 vector<_Tp, _Alloc>::_M_assign_aux(_ForwardIter __first, _ForwardIter __last,
00548 forward_iterator_tag) {
00549 size_type __len = 0;
00550 distance(__first, __last, __len);
00551
00552 if (__len > capacity()) {
00553 pointer __tmp(_M_allocate_and_copy(__len, __first, __last));
00554 destroy(_M_start, _M_finish);
00555 _M_deallocate(_M_start, _M_end_of_storage - _M_start);
00556 _M_start = __tmp;
00557 _M_end_of_storage = _M_finish = _M_start + __len;
00558 }
00559 else if (size() >= __len) {
00560 iterator __new_finish(copy(__first, __last, _M_start));
00561 destroy(__new_finish, end());
00562 _M_finish = __new_finish.base();
00563 }
00564 else {
00565 _ForwardIter __mid = __first;
00566 advance(__mid, size());
00567 copy(__first, __mid, _M_start);
00568 _M_finish = uninitialized_copy(__mid, __last, _M_finish);
00569 }
00570 }
00571
00572 template <class _Tp, class _Alloc>
00573 void
00574 vector<_Tp, _Alloc>::_M_insert_aux(iterator __position, const _Tp& __x)
00575 {
00576 if (_M_finish != _M_end_of_storage) {
00577 construct(_M_finish, *(_M_finish - 1));
00578 ++_M_finish;
00579 _Tp __x_copy = __x;
00580 copy_backward(__position, iterator(_M_finish - 2), iterator(_M_finish- 1));
00581 *__position = __x_copy;
00582 }
00583 else {
00584 const size_type __old_size = size();
00585 const size_type __len = __old_size != 0 ? 2 * __old_size : 1;
00586 iterator __new_start(_M_allocate(__len));
00587 iterator __new_finish(__new_start);
00588 __STL_TRY {
00589 __new_finish = uninitialized_copy(iterator(_M_start), __position,
00590 __new_start);
00591 construct(__new_finish.base(), __x);
00592 ++__new_finish;
00593 __new_finish = uninitialized_copy(__position, iterator(_M_finish),
00594 __new_finish);
00595 }
00596 __STL_UNWIND((destroy(__new_start,__new_finish),
00597 _M_deallocate(__new_start.base(),__len)));
00598 destroy(begin(), end());
00599 _M_deallocate(_M_start, _M_end_of_storage - _M_start);
00600 _M_start = __new_start.base();
00601 _M_finish = __new_finish.base();
00602 _M_end_of_storage = __new_start.base() + __len;
00603 }
00604 }
00605
00606 template <class _Tp, class _Alloc>
00607 void
00608 vector<_Tp, _Alloc>::_M_insert_aux(iterator __position)
00609 {
00610 if (_M_finish != _M_end_of_storage) {
00611 construct(_M_finish, *(_M_finish - 1));
00612 ++_M_finish;
00613 copy_backward(__position, iterator(_M_finish - 2),
00614 iterator(_M_finish - 1));
00615 *__position = _Tp();
00616 }
00617 else {
00618 const size_type __old_size = size();
00619 const size_type __len = __old_size != 0 ? 2 * __old_size : 1;
00620 pointer __new_start = _M_allocate(__len);
00621 pointer __new_finish = __new_start;
00622 __STL_TRY {
00623 __new_finish = uninitialized_copy(iterator(_M_start), __position,
00624 __new_start);
00625 construct(__new_finish);
00626 ++__new_finish;
00627 __new_finish = uninitialized_copy(__position, iterator(_M_finish),
00628 __new_finish);
00629 }
00630 __STL_UNWIND((destroy(__new_start,__new_finish),
00631 _M_deallocate(__new_start,__len)));
00632 destroy(begin(), end());
00633 _M_deallocate(_M_start, _M_end_of_storage - _M_start);
00634 _M_start = __new_start;
00635 _M_finish = __new_finish;
00636 _M_end_of_storage = __new_start + __len;
00637 }
00638 }
00639
00640 template <class _Tp, class _Alloc>
00641 void vector<_Tp, _Alloc>::_M_fill_insert(iterator __position, size_type __n,
00642 const _Tp& __x)
00643 {
00644 if (__n != 0) {
00645 if (size_type(_M_end_of_storage - _M_finish) >= __n) {
00646 _Tp __x_copy = __x;
00647 const size_type __elems_after = end() - __position;
00648 iterator __old_finish(_M_finish);
00649 if (__elems_after > __n) {
00650 uninitialized_copy(_M_finish - __n, _M_finish, _M_finish);
00651 _M_finish += __n;
00652 copy_backward(__position, __old_finish - __n, __old_finish);
00653 fill(__position, __position + __n, __x_copy);
00654 }
00655 else {
00656 uninitialized_fill_n(_M_finish, __n - __elems_after, __x_copy);
00657 _M_finish += __n - __elems_after;
00658 uninitialized_copy(__position, __old_finish, _M_finish);
00659 _M_finish += __elems_after;
00660 fill(__position, __old_finish, __x_copy);
00661 }
00662 }
00663 else {
00664 const size_type __old_size = size();
00665 const size_type __len = __old_size + max(__old_size, __n);
00666 iterator __new_start(_M_allocate(__len));
00667 iterator __new_finish(__new_start);
00668 __STL_TRY {
00669 __new_finish = uninitialized_copy(begin(), __position, __new_start);
00670 __new_finish = uninitialized_fill_n(__new_finish, __n, __x);
00671 __new_finish
00672 = uninitialized_copy(__position, end(), __new_finish);
00673 }
00674 __STL_UNWIND((destroy(__new_start,__new_finish),
00675 _M_deallocate(__new_start.base(),__len)));
00676 destroy(_M_start, _M_finish);
00677 _M_deallocate(_M_start, _M_end_of_storage - _M_start);
00678 _M_start = __new_start.base();
00679 _M_finish = __new_finish.base();
00680 _M_end_of_storage = __new_start.base() + __len;
00681 }
00682 }
00683 }
00684
00685 template <class _Tp, class _Alloc> template <class _InputIterator>
00686 void
00687 vector<_Tp, _Alloc>::_M_range_insert(iterator __pos,
00688 _InputIterator __first,
00689 _InputIterator __last,
00690 input_iterator_tag)
00691 {
00692 for ( ; __first != __last; ++__first) {
00693 __pos = insert(__pos, *__first);
00694 ++__pos;
00695 }
00696 }
00697
00698 template <class _Tp, class _Alloc> template <class _ForwardIterator>
00699 void
00700 vector<_Tp, _Alloc>::_M_range_insert(iterator __position,
00701 _ForwardIterator __first,
00702 _ForwardIterator __last,
00703 forward_iterator_tag)
00704 {
00705 if (__first != __last) {
00706 size_type __n = 0;
00707 distance(__first, __last, __n);
00708 if (size_type(_M_end_of_storage - _M_finish) >= __n) {
00709 const size_type __elems_after = end() - __position;
00710 iterator __old_finish(_M_finish);
00711 if (__elems_after > __n) {
00712 uninitialized_copy(_M_finish - __n, _M_finish, _M_finish);
00713 _M_finish += __n;
00714 copy_backward(__position, __old_finish - __n, __old_finish);
00715 copy(__first, __last, __position);
00716 }
00717 else {
00718 _ForwardIterator __mid = __first;
00719 advance(__mid, __elems_after);
00720 uninitialized_copy(__mid, __last, _M_finish);
00721 _M_finish += __n - __elems_after;
00722 uninitialized_copy(__position, __old_finish, _M_finish);
00723 _M_finish += __elems_after;
00724 copy(__first, __mid, __position);
00725 }
00726 }
00727 else {
00728 const size_type __old_size = size();
00729 const size_type __len = __old_size + max(__old_size, __n);
00730 iterator __new_start(_M_allocate(__len));
00731 iterator __new_finish(__new_start);
00732 __STL_TRY {
00733 __new_finish = uninitialized_copy(iterator(_M_start),
00734 __position, __new_start);
00735 __new_finish = uninitialized_copy(__first, __last, __new_finish);
00736 __new_finish
00737 = uninitialized_copy(__position, iterator(_M_finish), __new_finish);
00738 }
00739 __STL_UNWIND((destroy(__new_start,__new_finish),
00740 _M_deallocate(__new_start.base(),__len)));
00741 destroy(_M_start, _M_finish);
00742 _M_deallocate(_M_start, _M_end_of_storage - _M_start);
00743 _M_start = __new_start.base();
00744 _M_finish = __new_finish.base();
00745 _M_end_of_storage = __new_start.base() + __len;
00746 }
00747 }
00748 }
00749
00750 }
00751
00752 #endif
00753
00754
00755
00756