/home/ntakagi/work/STLport-5.1.5/stlport/stl/_vector.h

Go to the documentation of this file.
00001 /*
00002  *
00003  * Copyright (c) 1994
00004  * Hewlett-Packard Company
00005  *
00006  * Copyright (c) 1996,1997
00007  * Silicon Graphics Computer Systems, Inc.
00008  *
00009  * Copyright (c) 1997
00010  * Moscow Center for SPARC Technology
00011  *
00012  * Copyright (c) 1999
00013  * Boris Fomitchev
00014  *
00015  * This material is provided "as is", with absolutely no warranty expressed
00016  * or implied. Any use is at your own risk.
00017  *
00018  * Permission to use or copy this software for any purpose is hereby granted
00019  * without fee, provided the above notices are retained on all copies.
00020  * Permission to modify the code and to distribute modified code is granted,
00021  * provided the above notices are retained, and a notice that the code was
00022  * modified is included with the above copyright notice.
00023  *
00024  */
00025 
00026 /* NOTE: This is an internal header file, included by other STL headers.
00027  *   You should not attempt to use it directly.
00028  */
00029 
00030 #ifndef _STLP_INTERNAL_VECTOR_H
00031 #define _STLP_INTERNAL_VECTOR_H
00032 
00033 #ifndef _STLP_INTERNAL_ALGOBASE_H
00034 #  include <stl/_algobase.h>
00035 #endif
00036 
00037 #ifndef _STLP_INTERNAL_ALLOC_H
00038 #  include <stl/_alloc.h>
00039 #endif
00040 
00041 #ifndef _STLP_INTERNAL_ITERATOR_H
00042 #  include <stl/_iterator.h>
00043 #endif
00044 
00045 #ifndef _STLP_INTERNAL_UNINITIALIZED_H
00046 #  include <stl/_uninitialized.h>
00047 #endif
00048 
00049 _STLP_BEGIN_NAMESPACE
00050 
00051 // The vector base class serves one purpose, its constructor and
00052 // destructor allocate (but don't initialize) storage.  This makes
00053 // exception safety easier.
00054 
00055 _STLP_MOVE_TO_PRIV_NAMESPACE
00056 
00057 template <class _Tp, class _Alloc>
00058 class _Vector_base {
00059 public:
00060   typedef _Vector_base<_Tp, _Alloc> _Self;
00061   _STLP_FORCE_ALLOCATORS(_Tp, _Alloc)
00062   typedef typename _Alloc_traits<_Tp, _Alloc>::allocator_type allocator_type;
00063   typedef _Tp* pointer;
00064   typedef _STLP_alloc_proxy<pointer, _Tp, allocator_type> _AllocProxy;
00065 
00066   _Vector_base(const _Alloc& __a)
00067     : _M_start(0), _M_finish(0), _M_end_of_storage(__a, 0) {}
00068 
00069   _Vector_base(size_t __n, const _Alloc& __a)
00070     : _M_start(0), _M_finish(0), _M_end_of_storage(__a, 0) {
00071     _M_start = _M_end_of_storage.allocate(__n, __n);
00072     _M_finish = _M_start;
00073     _M_end_of_storage._M_data = _M_start + __n;
00074     _STLP_MPWFIX_TRY _STLP_MPWFIX_CATCH
00075   }
00076 
00077   _Vector_base(__move_source<_Self> src)
00078     : _M_start(src.get()._M_start), _M_finish(src.get()._M_finish),
00079       _M_end_of_storage(__move_source<_AllocProxy>(src.get()._M_end_of_storage)) {
00080     //Set the source as empty:
00081     src.get()._M_finish = src.get()._M_end_of_storage._M_data = src.get()._M_start = 0;
00082   }
00083 
00084   ~_Vector_base() {
00085     if (_M_start != _STLP_DEFAULT_CONSTRUCTED(pointer))
00086       _M_end_of_storage.deallocate(_M_start, _M_end_of_storage._M_data - _M_start);
00087   }
00088 
00089 protected:
00090   void _STLP_FUNCTION_THROWS _M_throw_length_error() const;
00091   void _STLP_FUNCTION_THROWS _M_throw_out_of_range() const;
00092 
00093   pointer _M_start;
00094   pointer _M_finish;
00095   _AllocProxy _M_end_of_storage;
00096 };
00097 
00098 #if defined (_STLP_USE_PTR_SPECIALIZATIONS)
00099 #  define vector _STLP_PTR_IMPL_NAME(vector)
00100 #elif defined (_STLP_DEBUG)
00101 #  define vector _STLP_NON_DBG_NAME(vector)
00102 #else
00103 _STLP_MOVE_TO_STD_NAMESPACE
00104 #endif
00105 
00106 template <class _Tp, _STLP_DEFAULT_ALLOCATOR_SELECT(_Tp) >
00107 class vector : protected _STLP_PRIV _Vector_base<_Tp, _Alloc>
00108 #if defined (_STLP_USE_PARTIAL_SPEC_WORKAROUND) && !defined (vector)
00109              , public __stlport_class<vector<_Tp, _Alloc> >
00110 #endif
00111 {
00112 private:
00113   typedef _STLP_PRIV _Vector_base<_Tp, _Alloc> _Base;
00114   typedef vector<_Tp, _Alloc> _Self;
00115 public:
00116   _STLP_FORCE_ALLOCATORS(_Tp, _Alloc)
00117   typedef typename _Base::allocator_type allocator_type;
00118 
00119   typedef _Tp value_type;
00120   typedef value_type* pointer;
00121   typedef const value_type* const_pointer;
00122   typedef value_type* iterator;
00123   typedef const value_type* const_iterator;
00124 
00125   typedef value_type& reference;
00126   typedef const value_type& const_reference;
00127   typedef size_t size_type;
00128   typedef ptrdiff_t difference_type;
00129   typedef random_access_iterator_tag _Iterator_category;
00130 
00131   _STLP_DECLARE_RANDOM_ACCESS_REVERSE_ITERATORS;
00132 
00133   allocator_type get_allocator() const
00134   { return _STLP_CONVERT_ALLOCATOR((const allocator_type&)this->_M_end_of_storage, _Tp); }
00135 
00136 private:
00137   typedef typename __type_traits<_Tp>::has_trivial_assignment_operator _TrivialCopy;
00138   typedef typename __type_traits<_Tp>::has_trivial_copy_constructor _TrivialUCopy;
00139 #if !defined (_STLP_NO_MOVE_SEMANTIC)
00140   typedef typename __move_traits<_Tp>::implemented _Movable;
00141 #else
00142   typedef __false_type _Movable;
00143 #endif
00144 
00145   // handles insertions on overflow
00146   void _M_insert_overflow_aux(pointer __pos, const _Tp& __x, const __false_type& /*_Movable*/,
00147                               size_type __fill_len, bool __atend);
00148   void _M_insert_overflow_aux(pointer __pos, const _Tp& __x, const __true_type& /*_Movable*/,
00149                               size_type __fill_len, bool __atend) {
00150     //We need to take care of self referencing here:
00151     if (_M_is_inside(__x)) {
00152       value_type __x_copy = __x;
00153       _M_insert_overflow_aux(__pos, __x_copy, __false_type(), __fill_len, __atend);
00154       return;
00155     }
00156     _M_insert_overflow_aux(__pos, __x, __false_type(), __fill_len, __atend);
00157   }
00158 
00159   void _M_insert_overflow(pointer __pos, const _Tp& __x, const __false_type& /*_TrivialCopy*/,
00160                           size_type __fill_len, bool __atend = false)
00161   { _M_insert_overflow_aux(__pos, __x, _Movable(), __fill_len, __atend); }
00162   void _M_insert_overflow(pointer __pos, const _Tp& __x, const __true_type& /*_TrivialCopy*/,
00163                           size_type __fill_len, bool __atend = false);
00164   void _M_range_check(size_type __n) const {
00165     if (__n >= size_type(this->_M_finish - this->_M_start))
00166       this->_M_throw_out_of_range();
00167   }
00168 
00169 public:
00170   iterator begin()             { return this->_M_start; }
00171   const_iterator begin() const { return this->_M_start; }
00172   iterator end()               { return this->_M_finish; }
00173   const_iterator end() const   { return this->_M_finish; }
00174 
00175   reverse_iterator rbegin()              { return reverse_iterator(end()); }
00176   const_reverse_iterator rbegin() const  { return const_reverse_iterator(end()); }
00177   reverse_iterator rend()                { return reverse_iterator(begin()); }
00178   const_reverse_iterator rend() const    { return const_reverse_iterator(begin()); }
00179 
00180   size_type size() const        { return size_type(this->_M_finish - this->_M_start); }
00181   size_type max_size() const {
00182     size_type __vector_max_size = size_type(-1) / sizeof(_Tp);
00183     typename allocator_type::size_type __alloc_max_size = this->_M_end_of_storage.max_size();
00184     return (__alloc_max_size < __vector_max_size)?__alloc_max_size:__vector_max_size;
00185   }
00186 
00187   size_type capacity() const    { return size_type(this->_M_end_of_storage._M_data - this->_M_start); }
00188   bool empty() const            { return this->_M_start == this->_M_finish; }
00189 
00190   reference operator[](size_type __n) { return *(begin() + __n); }
00191   const_reference operator[](size_type __n) const { return *(begin() + __n); }
00192 
00193   reference front()             { return *begin(); }
00194   const_reference front() const { return *begin(); }
00195   reference back()              { return *(end() - 1); }
00196   const_reference back() const  { return *(end() - 1); }
00197 
00198   reference at(size_type __n) { _M_range_check(__n); return (*this)[__n]; }
00199   const_reference at(size_type __n) const { _M_range_check(__n); return (*this)[__n]; }
00200 
00201 #if !defined (_STLP_DONT_SUP_DFLT_PARAM)
00202   explicit vector(const allocator_type& __a = allocator_type())
00203 #else
00204   vector()
00205     : _STLP_PRIV _Vector_base<_Tp, _Alloc>(allocator_type()) {}
00206   vector(const allocator_type& __a)
00207 #endif
00208     : _STLP_PRIV _Vector_base<_Tp, _Alloc>(__a) {}
00209 
00210 #if !defined (_STLP_DONT_SUP_DFLT_PARAM)
00211 private:
00212   //We always call _M_initialize with only 1 parameter. Default parameter
00213   //is used to allow explicit instanciation of vector with types with no
00214   //default constructor.
00215   void _M_initialize(size_type __n, const _Tp& __val = _STLP_DEFAULT_CONSTRUCTED(_Tp))
00216   { this->_M_finish = _STLP_PRIV __uninitialized_init(this->_M_start, __n, __val); }
00217 public:
00218   explicit vector(size_type __n)
00219     : _STLP_PRIV _Vector_base<_Tp, _Alloc>(__n, allocator_type())
00220   { _M_initialize(__n); }
00221   vector(size_type __n, const _Tp& __val, const allocator_type& __a = allocator_type())
00222 #else
00223   explicit vector(size_type __n)
00224     : _STLP_PRIV _Vector_base<_Tp, _Alloc>(__n, allocator_type())
00225   { this->_M_finish = _STLP_PRIV __uninitialized_init(this->_M_start, __n, _STLP_DEFAULT_CONSTRUCTED(_Tp)); }
00226   vector(size_type __n, const _Tp& __val)
00227     : _STLP_PRIV _Vector_base<_Tp, _Alloc>(__n, allocator_type())
00228   { this->_M_finish = _STLP_PRIV __uninitialized_fill_n(this->_M_start, __n, __val); }
00229   vector(size_type __n, const _Tp& __val, const allocator_type& __a)
00230 #endif
00231     : _STLP_PRIV _Vector_base<_Tp, _Alloc>(__n, __a)
00232   { this->_M_finish = _STLP_PRIV __uninitialized_fill_n(this->_M_start, __n, __val); }
00233 
00234   vector(const _Self& __x)
00235     : _STLP_PRIV _Vector_base<_Tp, _Alloc>(__x.size(), __x.get_allocator())
00236   { this->_M_finish = _STLP_PRIV __ucopy_ptrs(__x.begin(), __x.end(), this->_M_start, _TrivialUCopy()); }
00237 
00238   vector(__move_source<_Self> src)
00239     : _STLP_PRIV _Vector_base<_Tp, _Alloc>(__move_source<_Base>(src.get()))
00240   {}
00241 
00242 #if defined (_STLP_MEMBER_TEMPLATES)
00243 private:
00244   template <class _Integer>
00245   void _M_initialize_aux(_Integer __n, _Integer __val,
00246                          const __true_type& /*_IsIntegral*/) {
00247     size_type __real_n;
00248     this->_M_start = this->_M_end_of_storage.allocate(__n, __real_n);
00249     this->_M_end_of_storage._M_data = this->_M_start + __real_n;
00250     this->_M_finish = _STLP_PRIV __uninitialized_fill_n(this->_M_start, __n, __val);
00251   }
00252 
00253   template <class _InputIterator>
00254   void _M_initialize_aux(_InputIterator __first, _InputIterator __last,
00255                          const __false_type& /*_IsIntegral*/)
00256   { _M_range_initialize(__first, __last, _STLP_ITERATOR_CATEGORY(__first, _InputIterator)); }
00257 
00258 public:
00259   // Check whether it's an integral type.  If so, it's not an iterator.
00260   template <class _InputIterator>
00261   vector(_InputIterator __first, _InputIterator __last,
00262                const allocator_type& __a _STLP_ALLOCATOR_TYPE_DFL )
00263     : _STLP_PRIV _Vector_base<_Tp, _Alloc>(__a) {
00264     typedef typename _IsIntegral<_InputIterator>::_Ret _Integral;
00265     _M_initialize_aux(__first, __last, _Integral());
00266   }
00267 
00268 #  if defined (_STLP_NEEDS_EXTRA_TEMPLATE_CONSTRUCTORS)
00269   template <class _InputIterator>
00270   vector(_InputIterator __first, _InputIterator __last)
00271     : _STLP_PRIV _Vector_base<_Tp, _Alloc>(allocator_type()) {
00272     typedef typename _IsIntegral<_InputIterator>::_Ret _Integral;
00273     _M_initialize_aux(__first, __last, _Integral());
00274   }
00275 #  endif /* _STLP_NEEDS_EXTRA_TEMPLATE_CONSTRUCTORS */
00276 
00277 #else /* _STLP_MEMBER_TEMPLATES */
00278   vector(const _Tp* __first, const _Tp* __last,
00279          const allocator_type& __a = allocator_type())
00280     : _STLP_PRIV _Vector_base<_Tp, _Alloc>(__last - __first, __a)
00281   { this->_M_finish = _STLP_PRIV __ucopy_ptrs(__first, __last, this->_M_start, _TrivialUCopy()); }
00282 #endif /* _STLP_MEMBER_TEMPLATES */
00283 
00284   //As the vector container is a back insert oriented container it
00285   //seems rather logical to destroy elements in reverse order.
00286   ~vector() { _STLP_STD::_Destroy_Range(rbegin(), rend()); }
00287 
00288   _Self& operator=(const _Self& __x);
00289 
00290   void reserve(size_type __n);
00291 
00292   // assign(), a generalized assignment member function.  Two
00293   // versions: one that takes a count, and one that takes a range.
00294   // The range version is a member template, so we dispatch on whether
00295   // or not the type is an integer.
00296 
00297   void assign(size_type __n, const _Tp& __val) { _M_fill_assign(__n, __val); }
00298   void _M_fill_assign(size_type __n, const _Tp& __val);
00299 
00300 #if defined (_STLP_MEMBER_TEMPLATES)
00301   template <class _ForwardIter>
00302   void _M_assign_aux(_ForwardIter __first, _ForwardIter __last, const forward_iterator_tag &) {
00303 #else
00304   void assign(const_iterator __first, const_iterator __last) {
00305     typedef const_iterator _ForwardIter;
00306 #endif
00307     const size_type __len = distance(__first, __last);
00308     if (__len > capacity()) {
00309       size_type __n = __len;
00310       iterator __tmp = _M_allocate_and_copy(__n, __first, __last);
00311       _M_clear();
00312       _M_set(__tmp, __tmp + __len, __tmp + __n);
00313     }
00314     else if (size() >= __len) {
00315       iterator __new_finish = copy(__first, __last, this->_M_start);
00316       _STLP_STD::_Destroy_Range(__new_finish, this->_M_finish);
00317       this->_M_finish = __new_finish;
00318     }
00319     else {
00320       _ForwardIter __mid = __first;
00321       advance(__mid, size());
00322       copy(__first, __mid, this->_M_start);
00323       this->_M_finish = uninitialized_copy(__mid, __last, this->_M_finish);
00324     }
00325   }
00326 
00327 #if defined (_STLP_MEMBER_TEMPLATES)
00328   template <class _InputIter>
00329   void _M_assign_aux(_InputIter __first, _InputIter __last,
00330                      const input_iterator_tag &) {
00331     iterator __cur = begin();
00332     for ( ; __first != __last && __cur != end(); ++__cur, ++__first)
00333       *__cur = *__first;
00334     if (__first == __last)
00335       erase(__cur, end());
00336     else
00337       insert(end(), __first, __last);
00338   }
00339 
00340   template <class _Integer>
00341   void _M_assign_dispatch(_Integer __n, _Integer __val,
00342                           const __true_type& /*_IsIntegral*/)
00343   { _M_fill_assign(__n, __val); }
00344 
00345   template <class _InputIter>
00346   void _M_assign_dispatch(_InputIter __first, _InputIter __last,
00347                           const __false_type& /*_IsIntegral*/)
00348   { _M_assign_aux(__first, __last, _STLP_ITERATOR_CATEGORY(__first, _InputIter)); }
00349 
00350   template <class _InputIterator>
00351   void assign(_InputIterator __first, _InputIterator __last) {
00352     typedef typename _IsIntegral<_InputIterator>::_Ret _Integral;
00353     _M_assign_dispatch(__first, __last, _Integral());
00354   }
00355 #endif /* _STLP_MEMBER_TEMPLATES */
00356 
00357 #if !defined (_STLP_DONT_SUP_DFLT_PARAM) && !defined (_STLP_NO_ANACHRONISMS)
00358   void push_back(const _Tp& __x = _STLP_DEFAULT_CONSTRUCTED(_Tp)) {
00359 #else
00360   void push_back(const _Tp& __x) {
00361 #endif 
00362     if (this->_M_finish != this->_M_end_of_storage._M_data) {
00363       _Copy_Construct(this->_M_finish, __x);
00364       ++this->_M_finish;
00365     }
00366     else
00367       _M_insert_overflow(this->_M_finish, __x, _TrivialCopy(), 1UL, true);
00368   }
00369 
00370 #if !defined(_STLP_DONT_SUP_DFLT_PARAM) && !defined(_STLP_NO_ANACHRONISMS)
00371   iterator insert(iterator __pos, const _Tp& __x = _STLP_DEFAULT_CONSTRUCTED(_Tp));
00372 #else
00373   iterator insert(iterator __pos, const _Tp& __x);
00374 #endif 
00376 #if defined(_STLP_DONT_SUP_DFLT_PARAM) && !defined(_STLP_NO_ANACHRONISMS)
00377   void push_back() { push_back(_STLP_DEFAULT_CONSTRUCTED(_Tp)); }
00378   iterator insert(iterator __pos) { return insert(__pos, _STLP_DEFAULT_CONSTRUCTED(_Tp)); }
00379 #endif /*_STLP_DONT_SUP_DFLT_PARAM && !_STLP_NO_ANACHRONISMS*/
00380 
00381   void swap(_Self& __x) {
00382     _STLP_STD::swap(this->_M_start, __x._M_start);
00383     _STLP_STD::swap(this->_M_finish, __x._M_finish);
00384     this->_M_end_of_storage.swap(__x._M_end_of_storage);
00385   }
00386 
00387 private:
00388   void _M_fill_insert_aux (iterator __pos, size_type __n, const _Tp& __x, const __true_type& /*_Movable*/);
00389   void _M_fill_insert_aux (iterator __pos, size_type __n, const _Tp& __x, const __false_type& /*_Movable*/);
00390   void _M_fill_insert (iterator __pos, size_type __n, const _Tp& __x);
00391 
00392   bool _M_is_inside(const value_type& __x) const {
00393     return (&__x >= this->_M_start && &__x < this->_M_finish);
00394   }
00395 
00396 #if defined (_STLP_MEMBER_TEMPLATES)
00397   template <class _ForwardIterator>
00398   void _M_range_insert_realloc(iterator __pos,
00399                                _ForwardIterator __first, _ForwardIterator __last,
00400 #else
00401   void _M_range_insert_realloc(iterator __pos,
00402                                const_iterator __first, const_iterator __last,
00403 #endif /* _STLP_MEMBER_TEMPLATES */
00404                                size_type __n) {
00405     const size_type __old_size = size();
00406     size_type __len = __old_size + (max)(__old_size, __n);
00407     pointer __new_start = this->_M_end_of_storage.allocate(__len, __len);
00408     pointer __new_finish = __new_start;
00409     _STLP_TRY {
00410       __new_finish = _STLP_PRIV __uninitialized_move(this->_M_start, __pos, __new_start, _TrivialUCopy(), _Movable());
00411       __new_finish = uninitialized_copy(__first, __last, __new_finish);
00412       __new_finish = _STLP_PRIV __uninitialized_move(__pos, this->_M_finish, __new_finish, _TrivialUCopy(), _Movable());
00413     }
00414     _STLP_UNWIND((_STLP_STD::_Destroy_Range(__new_start,__new_finish),
00415                   this->_M_end_of_storage.deallocate(__new_start,__len)))
00416     _M_clear_after_move();
00417     _M_set(__new_start, __new_finish, __new_start + __len);
00418   }
00419 
00420 #if defined (_STLP_MEMBER_TEMPLATES)
00421   template <class _ForwardIterator>
00422   void _M_range_insert_aux(iterator __pos,
00423                            _ForwardIterator __first, _ForwardIterator __last,
00424 #else
00425   void _M_range_insert_aux(iterator __pos,
00426                            const_iterator __first, const_iterator __last,
00427 #endif /* _STLP_MEMBER_TEMPLATES */
00428                            size_type __n, const __true_type& /*_Movable*/) {
00429     iterator __src = this->_M_finish - 1;
00430     iterator __dst = __src + __n;
00431     for (; __src >= __pos; --__dst, --__src) {
00432       _STLP_STD::_Move_Construct(__dst, *__src);
00433       _STLP_STD::_Destroy_Moved(__src);
00434     }
00435     uninitialized_copy(__first, __last, __pos);
00436     this->_M_finish += __n;
00437   }
00438 
00439 #if defined (_STLP_MEMBER_TEMPLATES)
00440   template <class _ForwardIterator>
00441   void _M_range_insert_aux(iterator __pos,
00442                            _ForwardIterator __first, _ForwardIterator __last,
00443 #else
00444   void _M_range_insert_aux(iterator __pos,
00445                            const_iterator __first, const_iterator __last,
00446 #endif /* _STLP_MEMBER_TEMPLATES */
00447                            size_type __n, const __false_type& /*_Movable*/) {
00448     const size_type __elems_after = this->_M_finish - __pos;
00449     pointer __old_finish = this->_M_finish;
00450     if (__elems_after > __n) {
00451       _STLP_PRIV __ucopy_ptrs(this->_M_finish - __n, this->_M_finish, this->_M_finish, _TrivialUCopy());
00452       this->_M_finish += __n;
00453       _STLP_PRIV __copy_backward_ptrs(__pos, __old_finish - __n, __old_finish, _TrivialCopy());
00454       copy(__first, __last, __pos);
00455     }
00456     else {
00457 #if defined ( _STLP_MEMBER_TEMPLATES )
00458       _ForwardIterator __mid = __first;
00459       advance(__mid, __elems_after);
00460 #else
00461       const_pointer __mid = __first + __elems_after;
00462 #endif
00463       uninitialized_copy(__mid, __last, this->_M_finish);
00464       this->_M_finish += __n - __elems_after;
00465       _STLP_PRIV __ucopy_ptrs(__pos, __old_finish, this->_M_finish, _TrivialUCopy());
00466       this->_M_finish += __elems_after;
00467       copy(__first, __mid, __pos);
00468     } /* elems_after */
00469   }
00470 
00471 
00472 #if defined (_STLP_MEMBER_TEMPLATES)
00473   template <class _Integer>
00474   void _M_insert_dispatch(iterator __pos, _Integer __n, _Integer __val,
00475                           const __true_type&)
00476   { _M_fill_insert(__pos, (size_type) __n, (_Tp) __val); }
00477 
00478   template <class _InputIterator>
00479   void _M_insert_dispatch(iterator __pos,
00480                           _InputIterator __first, _InputIterator __last,
00481                           const __false_type&)
00482   { _M_range_insert(__pos, __first, __last, _STLP_ITERATOR_CATEGORY(__first, _InputIterator)); }
00483 
00484 public:
00485   // Check whether it's an integral type.  If so, it's not an iterator.
00486   template <class _InputIterator>
00487   void insert(iterator __pos, _InputIterator __first, _InputIterator __last) {
00488     typedef typename _IsIntegral<_InputIterator>::_Ret _Integral;
00489     _M_insert_dispatch(__pos, __first, __last, _Integral());
00490   }
00491 
00492 private:
00493   template <class _InputIterator>
00494   void _M_range_insert(iterator __pos,
00495                        _InputIterator __first, _InputIterator __last,
00496                        const input_iterator_tag &) {
00497     for ( ; __first != __last; ++__first) {
00498       __pos = insert(__pos, *__first);
00499       ++__pos;
00500     }
00501   }
00502 
00503   template <class _ForwardIterator>
00504   void _M_range_insert(iterator __pos,
00505                        _ForwardIterator __first, _ForwardIterator __last,
00506                        const forward_iterator_tag &) {
00507 #else /* _STLP_MEMBER_TEMPLATES */
00508 public:
00509   void insert(iterator __pos,
00510               const_iterator __first, const_iterator __last) {
00511 #endif /* _STLP_MEMBER_TEMPLATES */
00512     /* This method do not check self referencing.
00513      * Standard forbids it, checked by the debug mode.
00514      */
00515     if (__first != __last) {
00516       size_type __n = distance(__first, __last);
00517 
00518       if (size_type(this->_M_end_of_storage._M_data - this->_M_finish) >= __n) {
00519         _M_range_insert_aux(__pos, __first, __last, __n, _Movable());
00520       }
00521       else {
00522         _M_range_insert_realloc(__pos, __first, __last, __n);
00523       }
00524     }
00525   }
00526 
00527 public:
00528   void insert (iterator __pos, size_type __n, const _Tp& __x)
00529   { _M_fill_insert(__pos, __n, __x); }
00530 
00531   void pop_back() {
00532     --this->_M_finish;
00533     _STLP_STD::_Destroy(this->_M_finish);
00534   }
00535 
00536 private:
00537   iterator _M_erase(iterator __pos, const __true_type& /*_Movable*/) {
00538     _STLP_STD::_Destroy(__pos);
00539     iterator __dst = __pos, __src = __dst + 1;
00540     iterator __end = end();
00541     for (; __src != __end; ++__dst, ++__src) {
00542       _STLP_STD::_Move_Construct(__dst, *__src);
00543       _STLP_STD::_Destroy_Moved(__src);
00544     }
00545     this->_M_finish = __dst;
00546     return __pos;
00547   }
00548   iterator _M_erase(iterator __pos, const __false_type& /*_Movable*/) {
00549     if (__pos + 1 != end())
00550       _STLP_PRIV __copy_ptrs(__pos + 1, this->_M_finish, __pos, _TrivialCopy());
00551     --this->_M_finish;
00552     _STLP_STD::_Destroy(this->_M_finish);
00553     return __pos;
00554   }
00555   iterator _M_erase(iterator __first, iterator __last, const __true_type& /*_Movable*/) {
00556     iterator __dst = __first, __src = __last;
00557     iterator __end = end();
00558     for (; __dst != __last && __src != __end; ++__dst, ++__src) {
00559       _STLP_STD::_Destroy(__dst);
00560       _STLP_STD::_Move_Construct(__dst, *__src);
00561     }
00562     if (__dst != __last) {
00563       //There is more elements to erase than element to move:
00564       _STLP_STD::_Destroy_Range(__dst, __last);
00565       _STLP_STD::_Destroy_Moved_Range(__last, __end);
00566     }
00567     else {
00568       //There is more element to move than element to erase:
00569       for (; __src != __end; ++__dst, ++__src) {
00570         _STLP_STD::_Destroy_Moved(__dst);
00571         _STLP_STD::_Move_Construct(__dst, *__src);
00572       }
00573       _STLP_STD::_Destroy_Moved_Range(__dst, __end);
00574     }
00575     this->_M_finish = __dst;
00576     return __first;
00577   }
00578   iterator _M_erase(iterator __first, iterator __last, const __false_type& /*_Movable*/) {
00579     pointer __i = _STLP_PRIV __copy_ptrs(__last, this->_M_finish, __first, _TrivialCopy());
00580     _STLP_STD::_Destroy_Range(__i, this->_M_finish);
00581     this->_M_finish = __i;
00582     return __first;
00583   }
00584 
00585 public:
00586   iterator erase(iterator __pos) {
00587     return _M_erase(__pos, _Movable());
00588   }
00589   iterator erase(iterator __first, iterator __last) {
00590     if (__first == __last)
00591       return __first;
00592     return _M_erase(__first, __last, _Movable());
00593   }
00594 
00595 #if !defined (_STLP_DONT_SUP_DFLT_PARAM)
00596   void resize(size_type __new_size, const _Tp& __x = _STLP_DEFAULT_CONSTRUCTED(_Tp)) {
00597 #else
00598   void resize(size_type __new_size, const _Tp& __x) {
00599 #endif /*_STLP_DONT_SUP_DFLT_PARAM*/
00600     if (__new_size < size())
00601       erase(begin() + __new_size, end());
00602     else
00603       insert(end(), __new_size - size(), __x);
00604   }
00605 
00606 #if defined (_STLP_DONT_SUP_DFLT_PARAM)
00607   void resize(size_type __new_size) { resize(__new_size, _STLP_DEFAULT_CONSTRUCTED(_Tp)); }
00608 #endif /*_STLP_DONT_SUP_DFLT_PARAM*/
00609 
00610   void clear() {
00611     erase(begin(), end());
00612   }
00613 
00614 private:
00615   void _M_clear() {
00616     _STLP_STD::_Destroy_Range(rbegin(), rend());
00617     this->_M_end_of_storage.deallocate(this->_M_start, this->_M_end_of_storage._M_data - this->_M_start);
00618   }
00619 
00620   void _M_clear_after_move() {
00621     _STLP_STD::_Destroy_Moved_Range(rbegin(), rend());
00622     this->_M_end_of_storage.deallocate(this->_M_start, this->_M_end_of_storage._M_data - this->_M_start);
00623   }
00624 
00625   void _M_set(pointer __s, pointer __f, pointer __e) {
00626     this->_M_start = __s;
00627     this->_M_finish = __f;
00628     this->_M_end_of_storage._M_data = __e;
00629   }
00630 
00631 #if defined (_STLP_MEMBER_TEMPLATES)
00632   template <class _ForwardIterator>
00633   pointer _M_allocate_and_copy(size_type& __n,
00634                                _ForwardIterator __first, _ForwardIterator __last)
00635 #else /* _STLP_MEMBER_TEMPLATES */
00636   pointer _M_allocate_and_copy(size_type& __n,
00637                                const_pointer __first, const_pointer __last)
00638 #endif /* _STLP_MEMBER_TEMPLATES */
00639   {
00640     pointer __result = this->_M_end_of_storage.allocate(__n, __n);
00641     _STLP_TRY {
00642       uninitialized_copy(__first, __last, __result);
00643       return __result;
00644     }
00645     _STLP_UNWIND(this->_M_end_of_storage.deallocate(__result, __n))
00646     _STLP_RET_AFTER_THROW(__result)
00647   }
00648 
00649 
00650 #if defined (_STLP_MEMBER_TEMPLATES)
00651   template <class _InputIterator>
00652   void _M_range_initialize(_InputIterator __first, _InputIterator __last,
00653                            const input_iterator_tag &) {
00654     for ( ; __first != __last; ++__first)
00655       push_back(*__first);
00656   }
00657   // This function is only called by the constructor.
00658   template <class _ForwardIterator>
00659   void _M_range_initialize(_ForwardIterator __first, _ForwardIterator __last,
00660                            const forward_iterator_tag &) {
00661     size_type __n = distance(__first, __last);
00662     this->_M_start = this->_M_end_of_storage.allocate(__n, __n);
00663     this->_M_end_of_storage._M_data = this->_M_start + __n;
00664     this->_M_finish = uninitialized_copy(__first, __last, this->_M_start);
00665   }
00666 #endif /* _STLP_MEMBER_TEMPLATES */
00667 };
00668 
00669 #if defined (vector)
00670 #  undef vector
00671 _STLP_MOVE_TO_STD_NAMESPACE
00672 #endif
00673 
00674 _STLP_END_NAMESPACE
00675 
00676 #if !defined (_STLP_LINK_TIME_INSTANTIATION)
00677 #  include <stl/_vector.c>
00678 #endif
00679 
00680 #if defined (_STLP_USE_PTR_SPECIALIZATIONS)
00681 #  include <stl/pointers/_vector.h>
00682 #endif
00683 
00684 //We define the bool specialization before the debug interfave
00685 //to benefit of the debug version of vector even for the bool
00686 //specialization.
00687 #if !defined (_STLP_NO_BOOL) || !defined (_STLP_NO_EXTENSIONS)
00688 #  if !defined (_STLP_INTERNAL_BVECTOR_H)
00689 #    include <stl/_bvector.h>
00690 #  endif
00691 #endif
00692 
00693 #if defined (_STLP_DEBUG)
00694 #  include <stl/debug/_vector.h>
00695 #endif
00696 
00697 _STLP_BEGIN_NAMESPACE
00698 
00699 #if !defined (_STLP_NO_BOOL) && !defined (_STLP_NO_EXTENSIONS)
00700 // This typedef is non-standard.  It is provided for backward compatibility.
00701 typedef vector<bool, allocator<bool> > bit_vector;
00702 #endif
00703 
00704 #define _STLP_TEMPLATE_HEADER template <class _Tp, class _Alloc>
00705 #define _STLP_TEMPLATE_CONTAINER vector<_Tp, _Alloc>
00706 #include <stl/_relops_cont.h>
00707 #undef _STLP_TEMPLATE_CONTAINER
00708 #undef _STLP_TEMPLATE_HEADER
00709 
00710 #if defined (_STLP_CLASS_PARTIAL_SPECIALIZATION)
00711 template <class _Tp, class _Alloc>
00712 struct __move_traits<vector<_Tp, _Alloc> > {
00713   typedef __stlp_movable implemented;
00714   typedef typename __move_traits<_Alloc>::complete complete;
00715 #if defined (__BORLANDC__) && (__BORLANDC__ < 0x560)
00716   // disable incorrect "dependent type qualifier" error
00717   typedef __false_type _Ret;
00718 #endif
00719 };
00720 
00721 #  if !defined (_STLP_DEBUG)
00722 template <class _Tp, class _Alloc>
00723 struct _DefaultZeroValue<vector<_Tp, _Alloc> >
00724 { typedef typename __type_traits<_Alloc>::has_trivial_default_constructor _Ret; };
00725 #  endif
00726 
00727 #endif /* _STLP_CLASS_PARTIAL_SPECIALIZATION */
00728 
00729 _STLP_END_NAMESPACE
00730 
00731 #endif /* _STLP_VECTOR_H */
00732 
00733 // Local Variables:
00734 // mode:C++
00735 // End:



Generated on Mon Mar 10 15:32:45 2008 by  doxygen 1.5.1