stl_vector.h

Go to the documentation of this file.
00001 // Vector implementation -*- C++ -*- 00002 00003 // Copyright (C) 2001, 2002 Free Software Foundation, Inc. 00004 // 00005 // This file is part of the GNU ISO C++ Library. This library is free 00006 // software; you can redistribute it and/or modify it under the 00007 // terms of the GNU General Public License as published by the 00008 // Free Software Foundation; either version 2, or (at your option) 00009 // any later version. 00010 00011 // This library is distributed in the hope that it will be useful, 00012 // but WITHOUT ANY WARRANTY; without even the implied warranty of 00013 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 00014 // GNU General Public License for more details. 00015 00016 // You should have received a copy of the GNU General Public License along 00017 // with this library; see the file COPYING. If not, write to the Free 00018 // Software Foundation, 59 Temple Place - Suite 330, Boston, MA 02111-1307, 00019 // USA. 00020 00021 // As a special exception, you may use this file as part of a free software 00022 // library without restriction. Specifically, if other files instantiate 00023 // templates or use macros or inline functions from this file, or you compile 00024 // this file and link it with other files to produce an executable, this 00025 // file does not by itself cause the resulting executable to be covered by 00026 // the GNU General Public License. This exception does not however 00027 // invalidate any other reasons why the executable file might be covered by 00028 // the GNU General Public License. 00029 00030 /* 00031 * 00032 * Copyright (c) 1994 00033 * Hewlett-Packard Company 00034 * 00035 * Permission to use, copy, modify, distribute and sell this software 00036 * and its documentation for any purpose is hereby granted without fee, 00037 * provided that the above copyright notice appear in all copies and 00038 * that both that copyright notice and this permission notice appear 00039 * in supporting documentation. Hewlett-Packard Company makes no 00040 * representations about the suitability of this software for any 00041 * purpose. It is provided "as is" without express or implied warranty. 00042 * 00043 * 00044 * Copyright (c) 1996 00045 * Silicon Graphics Computer Systems, Inc. 00046 * 00047 * Permission to use, copy, modify, distribute and sell this software 00048 * and its documentation for any purpose is hereby granted without fee, 00049 * provided that the above copyright notice appear in all copies and 00050 * that both that copyright notice and this permission notice appear 00051 * in supporting documentation. Silicon Graphics makes no 00052 * representations about the suitability of this software for any 00053 * purpose. It is provided "as is" without express or implied warranty. 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 // The vector base class serves two purposes. First, its constructor 00072 // and destructor allocate (but don't initialize) storage. This makes 00073 // exception safety easier. Second, the base class encapsulates all of 00074 // the differences between SGI-style allocators and standard-conforming 00075 // allocators. 00076 00077 // Base class for ordinary allocators. 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 // Specialization for allocators that have the property that we don't 00102 // actually have to store an allocator object. 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 // concept requirements 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 // Check whether it's an integral type. If so, it's not an iterator. 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 // assign(), a generalized assignment member function. Two 00408 // versions: one that takes a count, and one that takes a range. 00409 // The range version is a member template, so we dispatch on whether 00410 // or not the type is an integer. 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 // Check whether it's an integral type. If so, it's not an iterator. 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 // This function is only called by the constructor. 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 } // namespace std 01080 01081 #endif /* __GLIBCPP_INTERNAL_VECTOR_H */ 01082 01083 // Local Variables: 01084 // mode:C++ 01085 // End:

Generated on Wed Sep 29 13:54:53 2004 for libstdc++-v3 Source by doxygen 1.3.7