include/c++/stl/stl/_vector.h

   1 /*
   2  *
   3  * Copyright (c) 1994
   4  * Hewlett-Packard Company
   5  *
   6  * Copyright (c) 1996,1997
   7  * Silicon Graphics Computer Systems, Inc.
   8  *
   9  * Copyright (c) 1997
  10  * Moscow Center for SPARC Technology
  11  *
  12  * Copyright (c) 1999
  13  * Boris Fomitchev
  14  *
  15  * This material is provided "as is", with absolutely no warranty expressed
  16  * or implied. Any use is at your own risk.
  17  *
  18  * Permission to use or copy this software for any purpose is hereby granted
  19  * without fee, provided the above notices are retained on all copies.
  20  * Permission to modify the code and to distribute modified code is granted,
  21  * provided the above notices are retained, and a notice that the code was
  22  * modified is included with the above copyright notice.
  23  *
  24  */
  25
  26 /* NOTE: This is an internal header file, included by other STL headers.
  27  *   You should not attempt to use it directly.
  28  */
  29
  30 #ifndef _STLP_INTERNAL_VECTOR_H
  31 #define _STLP_INTERNAL_VECTOR_H
  32
  33 #ifndef _STLP_INTERNAL_ALGOBASE_H
  34 #  include <stl/_algobase.h>
  35 #endif
  36
  37 #ifndef _STLP_INTERNAL_ALLOC_H
  38 #  include <stl/_alloc.h>
  39 #endif
  40
  41 #ifndef _STLP_INTERNAL_ITERATOR_H
  42 #  include <stl/_iterator.h>
  43 #endif
  44
  45 #ifndef _STLP_INTERNAL_UNINITIALIZED_H
  46 #  include <stl/_uninitialized.h>
  47 #endif
  48
  49 _STLP_BEGIN_NAMESPACE
  50
  51 // The vector base class serves one purpose, its constructor and
  52 // destructor allocate (but don't initialize) storage.  This makes
  53 // exception safety easier.
  54
  55 _STLP_MOVE_TO_PRIV_NAMESPACE
  56
  57 template <class _Tp, class _Alloc>
  58 class _Vector_base {
  59 public:
  60   typedef _Vector_base<_Tp, _Alloc> _Self;
  61   _STLP_FORCE_ALLOCATORS(_Tp, _Alloc)
  62   typedef typename _Alloc_traits<_Tp, _Alloc>::allocator_type allocator_type;
  63   typedef _Tp* pointer;
  64   typedef _STLP_alloc_proxy<pointer, _Tp, allocator_type> _AllocProxy;
  65
  66   _Vector_base(const _Alloc& __a)
  67     : _M_start(0), _M_finish(0), _M_end_of_storage(__a, 0) {}
  68
  69   _Vector_base(size_t __n, const _Alloc& __a)
  70     : _M_start(0), _M_finish(0), _M_end_of_storage(__a, 0) {
  71     _M_start = _M_end_of_storage.allocate(__n, __n);
  72     _M_finish = _M_start;
  73     _M_end_of_storage._M_data = _M_start + __n;
  74     _STLP_MPWFIX_TRY _STLP_MPWFIX_CATCH
  75   }
  76
  77   _Vector_base(__move_source<_Self> src)
  78     : _M_start(src.get()._M_start), _M_finish(src.get()._M_finish),
  79       _M_end_of_storage(__move_source<_AllocProxy>(src.get()._M_end_of_storage)) {
  80     //Set the source as empty:
  81     src.get()._M_finish = src.get()._M_end_of_storage._M_data = src.get()._M_start = 0;
  82   }
  83
  84   ~_Vector_base() {
  85     if (_M_start != _STLP_DEFAULT_CONSTRUCTED(pointer))
  86       _M_end_of_storage.deallocate(_M_start, _M_end_of_storage._M_data - _M_start);
  87   }
  88
  89 protected:
  90   void _STLP_FUNCTION_THROWS _M_throw_length_error() const;
  91   void _STLP_FUNCTION_THROWS _M_throw_out_of_range() const;
  92
  93   pointer _M_start;
  94   pointer _M_finish;
  95   _AllocProxy _M_end_of_storage;
  96 };
  97
  98 #if defined (_STLP_USE_PTR_SPECIALIZATIONS)
  99 #  define vector _STLP_PTR_IMPL_NAME(vector)
 100 #elif defined (_STLP_DEBUG)
 101 #  define vector _STLP_NON_DBG_NAME(vector)
 102 #else
 103 _STLP_MOVE_TO_STD_NAMESPACE
 104 #endif
 105
 106 template <class _Tp, _STLP_DEFAULT_ALLOCATOR_SELECT(_Tp) >
 107 class vector : protected _STLP_PRIV _Vector_base<_Tp, _Alloc>
 108 #if defined (_STLP_USE_PARTIAL_SPEC_WORKAROUND) && !defined (vector)
 109              , public __stlport_class<vector<_Tp, _Alloc> >
 110 #endif
 111 {
 112 private:
 113   typedef _STLP_PRIV _Vector_base<_Tp, _Alloc> _Base;
 114   typedef vector<_Tp, _Alloc> _Self;
 115 public:
 116   _STLP_FORCE_ALLOCATORS(_Tp, _Alloc)
 117   typedef typename _Base::allocator_type allocator_type;
 118
 119   typedef _Tp value_type;
 120   typedef value_type* pointer;
 121   typedef const value_type* const_pointer;
 122   typedef value_type* iterator;
 123   typedef const value_type* const_iterator;
 124
 125   typedef value_type& reference;
 126   typedef const value_type& const_reference;
 127   typedef size_t size_type;
 128   typedef ptrdiff_t difference_type;
 129   typedef random_access_iterator_tag _Iterator_category;
 130
 131   _STLP_DECLARE_RANDOM_ACCESS_REVERSE_ITERATORS;
 132
 133   allocator_type get_allocator() const
 134   { return _STLP_CONVERT_ALLOCATOR((const allocator_type&)this->_M_end_of_storage, _Tp); }
 135
 136 private:
 137   typedef typename __type_traits<_Tp>::has_trivial_assignment_operator _TrivialCopy;
 138   typedef typename __type_traits<_Tp>::has_trivial_copy_constructor _TrivialUCopy;
 139 #if !defined (_STLP_NO_MOVE_SEMANTIC)
 140   typedef typename __move_traits<_Tp>::implemented _Movable;
 141 #else
 142   typedef __false_type _Movable;
 143 #endif
 144
 145   // handles insertions on overflow
 146   void _M_insert_overflow_aux(pointer __pos, const _Tp& __x, const __false_type& /*_Movable*/,
 147                               size_type __fill_len, bool __atend);
 148   void _M_insert_overflow_aux(pointer __pos, const _Tp& __x, const __true_type& /*_Movable*/,
 149                               size_type __fill_len, bool __atend) {
 150     //We need to take care of self referencing here:
 151     if (_M_is_inside(__x)) {
 152       value_type __x_copy = __x;
 153       _M_insert_overflow_aux(__pos, __x_copy, __false_type(), __fill_len, __atend);
 154       return;
 155     }
 156     _M_insert_overflow_aux(__pos, __x, __false_type(), __fill_len, __atend);
 157   }
 158
 159   void _M_insert_overflow(pointer __pos, const _Tp& __x, const __false_type& /*_TrivialCopy*/,
 160                           size_type __fill_len, bool __atend = false)
 161   { _M_insert_overflow_aux(__pos, __x, _Movable(), __fill_len, __atend); }
 162   void _M_insert_overflow(pointer __pos, const _Tp& __x, const __true_type& /*_TrivialCopy*/,
 163                           size_type __fill_len, bool __atend = false);
 164   void _M_range_check(size_type __n) const {
 165     if (__n >= size_type(this->_M_finish - this->_M_start))
 166       this->_M_throw_out_of_range();
 167   }
 168
 169 public:
 170   iterator begin()             { return this->_M_start; }
 171   const_iterator begin() const { return this->_M_start; }
 172   iterator end()               { return this->_M_finish; }
 173   const_iterator end() const   { return this->_M_finish; }
 174
 175   reverse_iterator rbegin()              { return reverse_iterator(end()); }
 176   const_reverse_iterator rbegin() const  { return const_reverse_iterator(end()); }
 177   reverse_iterator rend()                { return reverse_iterator(begin()); }
 178   const_reverse_iterator rend() const    { return const_reverse_iterator(begin()); }
 179
 180   size_type size() const        { return size_type(this->_M_finish - this->_M_start); }
 181   size_type max_size() const {
 182     size_type __vector_max_size = size_type(-1) / sizeof(_Tp);
 183     typename allocator_type::size_type __alloc_max_size = this->_M_end_of_storage.max_size();
 184     return (__alloc_max_size < __vector_max_size)?__alloc_max_size:__vector_max_size;
 185   }
 186
 187   size_type capacity() const    { return size_type(this->_M_end_of_storage._M_data - this->_M_start); }
 188   bool empty() const            { return this->_M_start == this->_M_finish; }
 189
 190   reference operator[](size_type __n) { return *(begin() + __n); }
 191   const_reference operator[](size_type __n) const { return *(begin() + __n); }
 192
 193   reference front()             { return *begin(); }
 194   const_reference front() const { return *begin(); }
 195   reference back()              { return *(end() - 1); }
 196   const_reference back() const  { return *(end() - 1); }
 197
 198   reference at(size_type __n) { _M_range_check(__n); return (*this)[__n]; }
 199   const_reference at(size_type __n) const { _M_range_check(__n); return (*this)[__n]; }
 200
 201 #if !defined (_STLP_DONT_SUP_DFLT_PARAM)
 202   explicit vector(const allocator_type& __a = allocator_type())
 203 #else
 204   vector()
 205     : _STLP_PRIV _Vector_base<_Tp, _Alloc>(allocator_type()) {}
 206   vector(const allocator_type& __a)
 207 #endif
 208     : _STLP_PRIV _Vector_base<_Tp, _Alloc>(__a) {}
 209
 210 #if !defined (_STLP_DONT_SUP_DFLT_PARAM)
 211 private:
 212   //We always call _M_initialize with only 1 parameter. Default parameter
 213   //is used to allow explicit instanciation of vector with types with no
 214   //default constructor.
 215   void _M_initialize(size_type __n, const _Tp& __val = _STLP_DEFAULT_CONSTRUCTED(_Tp))
 216   { this->_M_finish = _STLP_PRIV __uninitialized_init(this->_M_start, __n, __val); }
 217 public:
 218   explicit vector(size_type __n)
 219     : _STLP_PRIV _Vector_base<_Tp, _Alloc>(__n, allocator_type())
 220   { _M_initialize(__n); }
 221   vector(size_type __n, const _Tp& __val, const allocator_type& __a = allocator_type())
 222 #else
 223   explicit vector(size_type __n)
 224     : _STLP_PRIV _Vector_base<_Tp, _Alloc>(__n, allocator_type())
 225   { this->_M_finish = _STLP_PRIV __uninitialized_init(this->_M_start, __n, _STLP_DEFAULT_CONSTRUCTED(_Tp)); }
 226   vector(size_type __n, const _Tp& __val)
 227     : _STLP_PRIV _Vector_base<_Tp, _Alloc>(__n, allocator_type())
 228   { this->_M_finish = _STLP_PRIV __uninitialized_fill_n(this->_M_start, __n, __val); }
 229   vector(size_type __n, const _Tp& __val, const allocator_type& __a)
 230 #endif
 231     : _STLP_PRIV _Vector_base<_Tp, _Alloc>(__n, __a)
 232   { this->_M_finish = _STLP_PRIV __uninitialized_fill_n(this->_M_start, __n, __val); }
 233
 234   vector(const _Self& __x)
 235     : _STLP_PRIV _Vector_base<_Tp, _Alloc>(__x.size(), __x.get_allocator())
 236   { this->_M_finish = _STLP_PRIV __ucopy_ptrs(__x.begin(), __x.end(), this->_M_start, _TrivialUCopy()); }
 237
 238   vector(__move_source<_Self> src)
 239     : _STLP_PRIV _Vector_base<_Tp, _Alloc>(__move_source<_Base>(src.get()))
 240   {}
 241
 242 #if defined (_STLP_MEMBER_TEMPLATES)
 243 private:
 244   template <class _Integer>
 245   void _M_initialize_aux(_Integer __n, _Integer __val,
 246                          const __true_type& /*_IsIntegral*/) {
 247     size_type __real_n;
 248     this->_M_start = this->_M_end_of_storage.allocate(__n, __real_n);
 249     this->_M_end_of_storage._M_data = this->_M_start + __real_n;
 250     this->_M_finish = _STLP_PRIV __uninitialized_fill_n(this->_M_start, __n, __val);
 251   }
 252
 253   template <class _InputIterator>
 254   void _M_initialize_aux(_InputIterator __first, _InputIterator __last,
 255                          const __false_type& /*_IsIntegral*/)
 256   { _M_range_initialize(__first, __last, _STLP_ITERATOR_CATEGORY(__first, _InputIterator)); }
 257
 258 public:
 259   // Check whether it's an integral type.  If so, it's not an iterator.
 260   template <class _InputIterator>
 261   vector(_InputIterator __first, _InputIterator __last,
 262                const allocator_type& __a _STLP_ALLOCATOR_TYPE_DFL )
 263     : _STLP_PRIV _Vector_base<_Tp, _Alloc>(__a) {
 264     typedef typename _IsIntegral<_InputIterator>::_Ret _Integral;
 265     _M_initialize_aux(__first, __last, _Integral());
 266   }
 267
 268 #  if defined (_STLP_NEEDS_EXTRA_TEMPLATE_CONSTRUCTORS)
 269   template <class _InputIterator>
 270   vector(_InputIterator __first, _InputIterator __last)
 271     : _STLP_PRIV _Vector_base<_Tp, _Alloc>(allocator_type()) {
 272     typedef typename _IsIntegral<_InputIterator>::_Ret _Integral;
 273     _M_initialize_aux(__first, __last, _Integral());
 274   }
 275 #  endif /* _STLP_NEEDS_EXTRA_TEMPLATE_CONSTRUCTORS */
 276
 277 #else /* _STLP_MEMBER_TEMPLATES */
 278   vector(const _Tp* __first, const _Tp* __last,
 279          const allocator_type& __a = allocator_type())
 280     : _STLP_PRIV _Vector_base<_Tp, _Alloc>(__last - __first, __a)
 281   { this->_M_finish = _STLP_PRIV __ucopy_ptrs(__first, __last, this->_M_start, _TrivialUCopy()); }
 282 #endif /* _STLP_MEMBER_TEMPLATES */
 283
 284   //As the vector container is a back insert oriented container it
 285   //seems rather logical to destroy elements in reverse order.
 286   ~vector() { _STLP_STD::_Destroy_Range(rbegin(), rend()); }
 287
 288   _Self& operator=(const _Self& __x);
 289
 290   void reserve(size_type __n);
 291
 292   // assign(), a generalized assignment member function.  Two
 293   // versions: one that takes a count, and one that takes a range.
 294   // The range version is a member template, so we dispatch on whether
 295   // or not the type is an integer.
 296
 297   void assign(size_type __n, const _Tp& __val) { _M_fill_assign(__n, __val); }
 298   void _M_fill_assign(size_type __n, const _Tp& __val);
 299
 300 #if defined (_STLP_MEMBER_TEMPLATES)
 301   template <class _ForwardIter>
 302   void _M_assign_aux(_ForwardIter __first, _ForwardIter __last, const forward_iterator_tag &) {
 303 #else
 304   void assign(const_iterator __first, const_iterator __last) {
 305     typedef const_iterator _ForwardIter;
 306 #endif
 307     const size_type __len = distance(__first, __last);
 308     if (__len > capacity()) {
 309       size_type __n = __len;
 310       iterator __tmp = _M_allocate_and_copy(__n, __first, __last);
 311       _M_clear();
 312       _M_set(__tmp, __tmp + __len, __tmp + __n);
 313     }
 314     else if (size() >= __len) {
 315       iterator __new_finish = copy(__first, __last, this->_M_start);
 316       _STLP_STD::_Destroy_Range(__new_finish, this->_M_finish);
 317       this->_M_finish = __new_finish;
 318     }
 319     else {
 320       _ForwardIter __mid = __first;
 321       advance(__mid, size());
 322       copy(__first, __mid, this->_M_start);
 323       this->_M_finish = uninitialized_copy(__mid, __last, this->_M_finish);
 324     }
 325   }
 326
 327 #if defined (_STLP_MEMBER_TEMPLATES)
 328   template <class _InputIter>
 329   void _M_assign_aux(_InputIter __first, _InputIter __last,
 330                      const input_iterator_tag &) {
 331     iterator __cur = begin();
 332     for ( ; __first != __last && __cur != end(); ++__cur, ++__first)
 333       *__cur = *__first;
 334     if (__first == __last)
 335       erase(__cur, end());
 336     else
 337       insert(end(), __first, __last);
 338   }
 339
 340   template <class _Integer>
 341   void _M_assign_dispatch(_Integer __n, _Integer __val,
 342                           const __true_type& /*_IsIntegral*/)
 343   { _M_fill_assign(__n, __val); }
 344
 345   template <class _InputIter>
 346   void _M_assign_dispatch(_InputIter __first, _InputIter __last,
 347                           const __false_type& /*_IsIntegral*/)
 348   { _M_assign_aux(__first, __last, _STLP_ITERATOR_CATEGORY(__first, _InputIter)); }
 349
 350   template <class _InputIterator>
 351   void assign(_InputIterator __first, _InputIterator __last) {
 352     typedef typename _IsIntegral<_InputIterator>::_Ret _Integral;
 353     _M_assign_dispatch(__first, __last, _Integral());
 354   }
 355 #endif /* _STLP_MEMBER_TEMPLATES */
 356
 357 #if !defined (_STLP_DONT_SUP_DFLT_PARAM) && !defined (_STLP_NO_ANACHRONISMS)
 358   void push_back(const _Tp& __x = _STLP_DEFAULT_CONSTRUCTED(_Tp)) {
 359 #else
 360   void push_back(const _Tp& __x) {
 361 #endif /*!_STLP_DONT_SUP_DFLT_PARAM && !_STLP_NO_ANACHRONISMS*/
 362     if (this->_M_finish != this->_M_end_of_storage._M_data) {
 363       _Copy_Construct(this->_M_finish, __x);
 364       ++this->_M_finish;
 365     }
 366     else
 367       _M_insert_overflow(this->_M_finish, __x, _TrivialCopy(), 1UL, true);
 368   }
 369
 370 #if !defined(_STLP_DONT_SUP_DFLT_PARAM) && !defined(_STLP_NO_ANACHRONISMS)
 371   iterator insert(iterator __pos, const _Tp& __x = _STLP_DEFAULT_CONSTRUCTED(_Tp));
 372 #else
 373   iterator insert(iterator __pos, const _Tp& __x);
 374 #endif /*!_STLP_DONT_SUP_DFLT_PARAM && !_STLP_NO_ANACHRONISMS*/
 375
 376 #if defined(_STLP_DONT_SUP_DFLT_PARAM) && !defined(_STLP_NO_ANACHRONISMS)
 377   void push_back() { push_back(_STLP_DEFAULT_CONSTRUCTED(_Tp)); }
 378   iterator insert(iterator __pos) { return insert(__pos, _STLP_DEFAULT_CONSTRUCTED(_Tp)); }
 379 #endif /*_STLP_DONT_SUP_DFLT_PARAM && !_STLP_NO_ANACHRONISMS*/
 380
 381   void swap(_Self& __x) {
 382     _STLP_STD::swap(this->_M_start, __x._M_start);
 383     _STLP_STD::swap(this->_M_finish, __x._M_finish);
 384     this->_M_end_of_storage.swap(__x._M_end_of_storage);
 385   }
 386
 387 private:
 388   void _M_fill_insert_aux (iterator __pos, size_type __n, const _Tp& __x, const __true_type& /*_Movable*/);
 389   void _M_fill_insert_aux (iterator __pos, size_type __n, const _Tp& __x, const __false_type& /*_Movable*/);
 390   void _M_fill_insert (iterator __pos, size_type __n, const _Tp& __x);
 391
 392   bool _M_is_inside(const value_type& __x) const {
 393     return (&__x >= this->_M_start && &__x < this->_M_finish);
 394   }
 395
 396 #if defined (_STLP_MEMBER_TEMPLATES)
 397   template <class _ForwardIterator>
 398   void _M_range_insert_realloc(iterator __pos,
 399                                _ForwardIterator __first, _ForwardIterator __last,
 400 #else
 401   void _M_range_insert_realloc(iterator __pos,
 402                                const_iterator __first, const_iterator __last,
 403 #endif /* _STLP_MEMBER_TEMPLATES */
 404                                size_type __n) {
 405     const size_type __old_size = size();
 406     size_type __len = __old_size + (max)(__old_size, __n);
 407     pointer __new_start = this->_M_end_of_storage.allocate(__len, __len);
 408     pointer __new_finish = __new_start;
 409     _STLP_TRY {
 410       __new_finish = _STLP_PRIV __uninitialized_move(this->_M_start, __pos, __new_start, _TrivialUCopy(), _Movable());
 411       __new_finish = uninitialized_copy(__first, __last, __new_finish);
 412       __new_finish = _STLP_PRIV __uninitialized_move(__pos, this->_M_finish, __new_finish, _TrivialUCopy(), _Movable());
 413     }
 414     _STLP_UNWIND((_STLP_STD::_Destroy_Range(__new_start,__new_finish),
 415                   this->_M_end_of_storage.deallocate(__new_start,__len)))
 416     _M_clear_after_move();
 417     _M_set(__new_start, __new_finish, __new_start + __len);
 418   }
 419
 420 #if defined (_STLP_MEMBER_TEMPLATES)
 421   template <class _ForwardIterator>
 422   void _M_range_insert_aux(iterator __pos,
 423                            _ForwardIterator __first, _ForwardIterator __last,
 424 #else
 425   void _M_range_insert_aux(iterator __pos,
 426                            const_iterator __first, const_iterator __last,
 427 #endif /* _STLP_MEMBER_TEMPLATES */
 428                            size_type __n, const __true_type& /*_Movable*/) {
 429     iterator __src = this->_M_finish - 1;
 430     iterator __dst = __src + __n;
 431     for (; __src >= __pos; --__dst, --__src) {
 432       _STLP_STD::_Move_Construct(__dst, *__src);
 433       _STLP_STD::_Destroy_Moved(__src);
 434     }
 435     uninitialized_copy(__first, __last, __pos);
 436     this->_M_finish += __n;
 437   }
 438
 439 #if defined (_STLP_MEMBER_TEMPLATES)
 440   template <class _ForwardIterator>
 441   void _M_range_insert_aux(iterator __pos,
 442                            _ForwardIterator __first, _ForwardIterator __last,
 443 #else
 444   void _M_range_insert_aux(iterator __pos,
 445                            const_iterator __first, const_iterator __last,
 446 #endif /* _STLP_MEMBER_TEMPLATES */
 447                            size_type __n, const __false_type& /*_Movable*/) {
 448     const size_type __elems_after = this->_M_finish - __pos;
 449     pointer __old_finish = this->_M_finish;
 450     if (__elems_after > __n) {
 451       _STLP_PRIV __ucopy_ptrs(this->_M_finish - __n, this->_M_finish, this->_M_finish, _TrivialUCopy());
 452       this->_M_finish += __n;
 453       _STLP_PRIV __copy_backward_ptrs(__pos, __old_finish - __n, __old_finish, _TrivialCopy());
 454       copy(__first, __last, __pos);
 455     }
 456     else {
 457 #if defined ( _STLP_MEMBER_TEMPLATES )
 458       _ForwardIterator __mid = __first;
 459       advance(__mid, __elems_after);
 460 #else
 461       const_pointer __mid = __first + __elems_after;
 462 #endif
 463       uninitialized_copy(__mid, __last, this->_M_finish);
 464       this->_M_finish += __n - __elems_after;
 465       _STLP_PRIV __ucopy_ptrs(__pos, __old_finish, this->_M_finish, _TrivialUCopy());
 466       this->_M_finish += __elems_after;
 467       copy(__first, __mid, __pos);
 468     } /* elems_after */
 469   }
 470
 471
 472 #if defined (_STLP_MEMBER_TEMPLATES)
 473   template <class _Integer>
 474   void _M_insert_dispatch(iterator __pos, _Integer __n, _Integer __val,
 475                           const __true_type&)
 476   { _M_fill_insert(__pos, (size_type) __n, (_Tp) __val); }
 477
 478   template <class _InputIterator>
 479   void _M_insert_dispatch(iterator __pos,
 480                           _InputIterator __first, _InputIterator __last,
 481                           const __false_type&)
 482   { _M_range_insert(__pos, __first, __last, _STLP_ITERATOR_CATEGORY(__first, _InputIterator)); }
 483
 484 public:
 485   // Check whether it's an integral type.  If so, it's not an iterator.
 486   template <class _InputIterator>
 487   void insert(iterator __pos, _InputIterator __first, _InputIterator __last) {
 488     typedef typename _IsIntegral<_InputIterator>::_Ret _Integral;
 489     _M_insert_dispatch(__pos, __first, __last, _Integral());
 490   }
 491
 492 private:
 493   template <class _InputIterator>
 494   void _M_range_insert(iterator __pos,
 495                        _InputIterator __first, _InputIterator __last,
 496                        const input_iterator_tag &) {
 497     for ( ; __first != __last; ++__first) {
 498       __pos = insert(__pos, *__first);
 499       ++__pos;
 500     }
 501   }
 502
 503   template <class _ForwardIterator>
 504   void _M_range_insert(iterator __pos,
 505                        _ForwardIterator __first, _ForwardIterator __last,
 506                        const forward_iterator_tag &) {
 507 #else /* _STLP_MEMBER_TEMPLATES */
 508 public:
 509   void insert(iterator __pos,
 510               const_iterator __first, const_iterator __last) {
 511 #endif /* _STLP_MEMBER_TEMPLATES */
 512     /* This method do not check self referencing.
 513      * Standard forbids it, checked by the debug mode.
 514      */
 515     if (__first != __last) {
 516       size_type __n = distance(__first, __last);
 517
 518       if (size_type(this->_M_end_of_storage._M_data - this->_M_finish) >= __n) {
 519         _M_range_insert_aux(__pos, __first, __last, __n, _Movable());
 520       }
 521       else {
 522         _M_range_insert_realloc(__pos, __first, __last, __n);
 523       }
 524     }
 525   }
 526
 527 public:
 528   void insert (iterator __pos, size_type __n, const _Tp& __x)
 529   { _M_fill_insert(__pos, __n, __x); }
 530
 531   void pop_back() {
 532     --this->_M_finish;
 533     _STLP_STD::_Destroy(this->_M_finish);
 534   }
 535
 536 private:
 537   iterator _M_erase(iterator __pos, const __true_type& /*_Movable*/) {
 538     _STLP_STD::_Destroy(__pos);
 539     iterator __dst = __pos, __src = __dst + 1;
 540     iterator __end = end();
 541     for (; __src != __end; ++__dst, ++__src) {
 542       _STLP_STD::_Move_Construct(__dst, *__src);
 543       _STLP_STD::_Destroy_Moved(__src);
 544     }
 545     this->_M_finish = __dst;
 546     return __pos;
 547   }
 548   iterator _M_erase(iterator __pos, const __false_type& /*_Movable*/) {
 549     if (__pos + 1 != end())
 550       _STLP_PRIV __copy_ptrs(__pos + 1, this->_M_finish, __pos, _TrivialCopy());
 551     --this->_M_finish;
 552     _STLP_STD::_Destroy(this->_M_finish);
 553     return __pos;
 554   }
 555   iterator _M_erase(iterator __first, iterator __last, const __true_type& /*_Movable*/) {
 556     iterator __dst = __first, __src = __last;
 557     iterator __end = end();
 558     for (; __dst != __last && __src != __end; ++__dst, ++__src) {
 559       _STLP_STD::_Destroy(__dst);
 560       _STLP_STD::_Move_Construct(__dst, *__src);
 561     }
 562     if (__dst != __last) {
 563       //There is more elements to erase than element to move:
 564       _STLP_STD::_Destroy_Range(__dst, __last);
 565       _STLP_STD::_Destroy_Moved_Range(__last, __end);
 566     }
 567     else {
 568       //There is more element to move than element to erase:
 569       for (; __src != __end; ++__dst, ++__src) {
 570         _STLP_STD::_Destroy_Moved(__dst);
 571         _STLP_STD::_Move_Construct(__dst, *__src);
 572       }
 573       _STLP_STD::_Destroy_Moved_Range(__dst, __end);
 574     }
 575     this->_M_finish = __dst;
 576     return __first;
 577   }
 578   iterator _M_erase(iterator __first, iterator __last, const __false_type& /*_Movable*/) {
 579     pointer __i = _STLP_PRIV __copy_ptrs(__last, this->_M_finish, __first, _TrivialCopy());
 580     _STLP_STD::_Destroy_Range(__i, this->_M_finish);
 581     this->_M_finish = __i;
 582     return __first;
 583   }
 584
 585 public:
 586   iterator erase(iterator __pos) {
 587     return _M_erase(__pos, _Movable());
 588   }
 589   iterator erase(iterator __first, iterator __last) {
 590     if (__first == __last)
 591       return __first;
 592     return _M_erase(__first, __last, _Movable());
 593   }
 594
 595 #if !defined (_STLP_DONT_SUP_DFLT_PARAM)
 596   void resize(size_type __new_size, const _Tp& __x = _STLP_DEFAULT_CONSTRUCTED(_Tp)) {
 597 #else
 598   void resize(size_type __new_size, const _Tp& __x) {
 599 #endif /*_STLP_DONT_SUP_DFLT_PARAM*/
 600     if (__new_size < size())
 601       erase(begin() + __new_size, end());
 602     else
 603       insert(end(), __new_size - size(), __x);
 604   }
 605
 606 #if defined (_STLP_DONT_SUP_DFLT_PARAM)
 607   void resize(size_type __new_size) { resize(__new_size, _STLP_DEFAULT_CONSTRUCTED(_Tp)); }
 608 #endif /*_STLP_DONT_SUP_DFLT_PARAM*/
 609
 610   void clear() {
 611     erase(begin(), end());
 612   }
 613
 614 private:
 615   void _M_clear() {
 616     _STLP_STD::_Destroy_Range(rbegin(), rend());
 617     this->_M_end_of_storage.deallocate(this->_M_start, this->_M_end_of_storage._M_data - this->_M_start);
 618   }
 619
 620   void _M_clear_after_move() {
 621     _STLP_STD::_Destroy_Moved_Range(rbegin(), rend());
 622     this->_M_end_of_storage.deallocate(this->_M_start, this->_M_end_of_storage._M_data - this->_M_start);
 623   }
 624
 625   void _M_set(pointer __s, pointer __f, pointer __e) {
 626     this->_M_start = __s;
 627     this->_M_finish = __f;
 628     this->_M_end_of_storage._M_data = __e;
 629   }
 630
 631 #if defined (_STLP_MEMBER_TEMPLATES)
 632   template <class _ForwardIterator>
 633   pointer _M_allocate_and_copy(size_type& __n,
 634                                _ForwardIterator __first, _ForwardIterator __last)
 635 #else /* _STLP_MEMBER_TEMPLATES */
 636   pointer _M_allocate_and_copy(size_type& __n,
 637                                const_pointer __first, const_pointer __last)
 638 #endif /* _STLP_MEMBER_TEMPLATES */
 639   {
 640     pointer __result = this->_M_end_of_storage.allocate(__n, __n);
 641     _STLP_TRY {
 642       uninitialized_copy(__first, __last, __result);
 643       return __result;
 644     }
 645     _STLP_UNWIND(this->_M_end_of_storage.deallocate(__result, __n))
 646     _STLP_RET_AFTER_THROW(__result)
 647   }
 648
 649
 650 #if defined (_STLP_MEMBER_TEMPLATES)
 651   template <class _InputIterator>
 652   void _M_range_initialize(_InputIterator __first, _InputIterator __last,
 653                            const input_iterator_tag &) {
 654     for ( ; __first != __last; ++__first)
 655       push_back(*__first);
 656   }
 657   // This function is only called by the constructor.
 658   template <class _ForwardIterator>
 659   void _M_range_initialize(_ForwardIterator __first, _ForwardIterator __last,
 660                            const forward_iterator_tag &) {
 661     size_type __n = distance(__first, __last);
 662     this->_M_start = this->_M_end_of_storage.allocate(__n, __n);
 663     this->_M_end_of_storage._M_data = this->_M_start + __n;
 664     this->_M_finish = uninitialized_copy(__first, __last, this->_M_start);
 665   }
 666 #endif /* _STLP_MEMBER_TEMPLATES */
 667 };
 668
 669 #if defined (vector)
 670 #  undef vector
 671 _STLP_MOVE_TO_STD_NAMESPACE
 672 #endif
 673
 674 _STLP_END_NAMESPACE
 675
 676 #if !defined (_STLP_LINK_TIME_INSTANTIATION)
 677 #  include <stl/_vector.c>
 678 #endif
 679
 680 #if defined (_STLP_USE_PTR_SPECIALIZATIONS)
 681 #  include <stl/pointers/_vector.h>
 682 #endif
 683
 684 //We define the bool specialization before the debug interfave
 685 //to benefit of the debug version of vector even for the bool
 686 //specialization.
 687 #if !defined (_STLP_NO_BOOL) || !defined (_STLP_NO_EXTENSIONS)
 688 #  if !defined (_STLP_INTERNAL_BVECTOR_H)
 689 #    include <stl/_bvector.h>
 690 #  endif
 691 #endif
 692
 693 #if defined (_STLP_DEBUG)
 694 #  include <stl/debug/_vector.h>
 695 #endif
 696
 697 _STLP_BEGIN_NAMESPACE
 698
 699 #if !defined (_STLP_NO_BOOL) && !defined (_STLP_NO_EXTENSIONS)
 700 // This typedef is non-standard.  It is provided for backward compatibility.
 701 typedef vector<bool, allocator<bool> > bit_vector;
 702 #endif
 703
 704 #define _STLP_TEMPLATE_HEADER template <class _Tp, class _Alloc>
 705 #define _STLP_TEMPLATE_CONTAINER vector<_Tp, _Alloc>
 706 #include <stl/_relops_cont.h>
 707 #undef _STLP_TEMPLATE_CONTAINER
 708 #undef _STLP_TEMPLATE_HEADER
 709
 710 #if defined (_STLP_CLASS_PARTIAL_SPECIALIZATION)
 711 template <class _Tp, class _Alloc>
 712 struct __move_traits<vector<_Tp, _Alloc> > {
 713   typedef __stlp_movable implemented;
 714   typedef typename __move_traits<_Alloc>::complete complete;
 715 #if defined (__BORLANDC__) && (__BORLANDC__ < 0x560)
 716   // disable incorrect "dependent type qualifier" error
 717   typedef __false_type _Ret;
 718 #endif
 719 };
 720
 721 #  if !defined (_STLP_DEBUG)
 722 template <class _Tp, class _Alloc>
 723 struct _DefaultZeroValue<vector<_Tp, _Alloc> >
 724 { typedef typename __type_traits<_Alloc>::has_trivial_default_constructor _Ret; };
 725 #  endif
 726
 727 #endif /* _STLP_CLASS_PARTIAL_SPECIALIZATION */
 728
 729 _STLP_END_NAMESPACE
 730
 731 #endif /* _STLP_VECTOR_H */
 732
 733 // Local Variables:
 734 // mode:C++
 735 // End: