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 Tue Dec 23 12:34:13 2003 for libstdc++-v3 Source by doxygen 1.3.4