headers/cpp/stl_vector.h

   1 /*
   2  *
   3  * Copyright (c) 1994
   4  * Hewlett-Packard Company
   5  *
   6  * Permission to use, copy, modify, distribute and sell this software
   7  * and its documentation for any purpose is hereby granted without fee,
   8  * provided that the above copyright notice appear in all copies and
   9  * that both that copyright notice and this permission notice appear
  10  * in supporting documentation.  Hewlett-Packard Company makes no
  11  * representations about the suitability of this software for any
  12  * purpose.  It is provided "as is" without express or implied warranty.
  13  *
  14  *
  15  * Copyright (c) 1996
  16  * Silicon Graphics Computer Systems, Inc.
  17  *
  18  * Permission to use, copy, modify, distribute and sell this software
  19  * and its documentation for any purpose is hereby granted without fee,
  20  * provided that the above copyright notice appear in all copies and
  21  * that both that copyright notice and this permission notice appear
  22  * in supporting documentation.  Silicon Graphics makes no
  23  * representations about the suitability of this software for any
  24  * purpose.  It is provided "as is" without express or implied warranty.
  25  */
  26
  27 /* NOTE: This is an internal header file, included by other STL headers.
  28  *   You should not attempt to use it directly.
  29  */
  30
  31 #ifndef __SGI_STL_INTERNAL_VECTOR_H
  32 #define __SGI_STL_INTERNAL_VECTOR_H
  33
  34 #include <stdexcept>
  35
  36 __STL_BEGIN_NAMESPACE
  37
  38 #if defined(__sgi) && !defined(__GNUC__) && (_MIPS_SIM != _MIPS_SIM_ABI32)
  39 #pragma set woff 1174
  40 #pragma set woff 1375
  41 #endif
  42
  43 // The vector base class serves two purposes.  First, its constructor
  44 // and destructor allocate (but don't initialize) storage.  This makes
  45 // exception safety easier.  Second, the base class encapsulates all of
  46 // the differences between SGI-style allocators and standard-conforming
  47 // allocators.
  48
  49 #ifdef __STL_USE_STD_ALLOCATORS
  50
  51 // Base class for ordinary allocators.
  52 template <class _Tp, class _Allocator, bool _IsStatic>
  53 class _Vector_alloc_base {
  54 public:
  55   typedef typename _Alloc_traits<_Tp, _Allocator>::allocator_type
  56           allocator_type;
  57   allocator_type get_allocator() const { return _M_data_allocator; }
  58
  59   _Vector_alloc_base(const allocator_type& __a)
  60     : _M_data_allocator(__a), _M_start(0), _M_finish(0), _M_end_of_storage(0)
  61   {}
  62
  63 protected:
  64   allocator_type _M_data_allocator;
  65   _Tp* _M_start;
  66   _Tp* _M_finish;
  67   _Tp* _M_end_of_storage;
  68
  69   _Tp* _M_allocate(size_t __n)
  70     { return _M_data_allocator.allocate(__n); }
  71   void _M_deallocate(_Tp* __p, size_t __n)
  72     { if (__p) _M_data_allocator.deallocate(__p, __n); }
  73 };
  74
  75 // Specialization for allocators that have the property that we don't
  76 // actually have to store an allocator object.
  77 template <class _Tp, class _Allocator>
  78 class _Vector_alloc_base<_Tp, _Allocator, true> {
  79 public:
  80   typedef typename _Alloc_traits<_Tp, _Allocator>::allocator_type
  81           allocator_type;
  82   allocator_type get_allocator() const { return allocator_type(); }
  83
  84   _Vector_alloc_base(const allocator_type&)
  85     : _M_start(0), _M_finish(0), _M_end_of_storage(0)
  86   {}
  87
  88 protected:
  89   _Tp* _M_start;
  90   _Tp* _M_finish;
  91   _Tp* _M_end_of_storage;
  92
  93   typedef typename _Alloc_traits<_Tp, _Allocator>::_Alloc_type _Alloc_type;
  94   _Tp* _M_allocate(size_t __n)
  95     { return _Alloc_type::allocate(__n); }
  96   void _M_deallocate(_Tp* __p, size_t __n)
  97     { _Alloc_type::deallocate(__p, __n);}
  98 };
  99
 100 template <class _Tp, class _Alloc>
 101 struct _Vector_base
 102   : public _Vector_alloc_base<_Tp, _Alloc,
 103                               _Alloc_traits<_Tp, _Alloc>::_S_instanceless>
 104 {
 105   typedef _Vector_alloc_base<_Tp, _Alloc,
 106                              _Alloc_traits<_Tp, _Alloc>::_S_instanceless>
 107           _Base;
 108   typedef typename _Base::allocator_type allocator_type;
 109
 110   _Vector_base(const allocator_type& __a) : _Base(__a) {}
 111   _Vector_base(size_t __n, const allocator_type& __a) : _Base(__a) {
 112     _M_start = _M_allocate(__n);
 113     _M_finish = _M_start;
 114     _M_end_of_storage = _M_start + __n;
 115   }
 116
 117   ~_Vector_base() { _M_deallocate(_M_start, _M_end_of_storage - _M_start); }
 118 };
 119
 120 #else /* __STL_USE_STD_ALLOCATORS */
 121
 122 template <class _Tp, class _Alloc>
 123 class _Vector_base {
 124 public:
 125   typedef _Alloc allocator_type;
 126   allocator_type get_allocator() const { return allocator_type(); }
 127
 128   _Vector_base(const _Alloc&)
 129     : _M_start(0), _M_finish(0), _M_end_of_storage(0) {}
 130   _Vector_base(size_t __n, const _Alloc&)
 131     : _M_start(0), _M_finish(0), _M_end_of_storage(0)
 132   {
 133     _M_start = _M_allocate(__n);
 134     _M_finish = _M_start;
 135     _M_end_of_storage = _M_start + __n;
 136   }
 137
 138   ~_Vector_base() { _M_deallocate(_M_start, _M_end_of_storage - _M_start); }
 139
 140 protected:
 141   _Tp* _M_start;
 142   _Tp* _M_finish;
 143   _Tp* _M_end_of_storage;
 144
 145   typedef simple_alloc<_Tp, _Alloc> _M_data_allocator;
 146   _Tp* _M_allocate(size_t __n)
 147     { return _M_data_allocator::allocate(__n); }
 148   void _M_deallocate(_Tp* __p, size_t __n)
 149     { _M_data_allocator::deallocate(__p, __n); }
 150 };
 151
 152 #endif /* __STL_USE_STD_ALLOCATORS */
 153
 154 template <class _Tp, class _Alloc = __STL_DEFAULT_ALLOCATOR(_Tp) >
 155 class vector : protected _Vector_base<_Tp, _Alloc>
 156 {
 157 private:
 158   typedef _Vector_base<_Tp, _Alloc> _Base;
 159 public:
 160   typedef _Tp value_type;
 161   typedef value_type* pointer;
 162   typedef const value_type* const_pointer;
 163   typedef value_type* iterator;
 164   typedef const value_type* const_iterator;
 165   typedef value_type& reference;
 166   typedef const value_type& const_reference;
 167   typedef size_t size_type;
 168   typedef ptrdiff_t difference_type;
 169
 170   typedef typename _Base::allocator_type allocator_type;
 171   allocator_type get_allocator() const { return _Base::get_allocator(); }
 172
 173 #ifdef __STL_CLASS_PARTIAL_SPECIALIZATION
 174   typedef reverse_iterator<const_iterator> const_reverse_iterator;
 175   typedef reverse_iterator<iterator> reverse_iterator;
 176 #else /* __STL_CLASS_PARTIAL_SPECIALIZATION */
 177   typedef reverse_iterator<const_iterator, value_type, const_reference,
 178                            difference_type>  const_reverse_iterator;
 179   typedef reverse_iterator<iterator, value_type, reference, difference_type>
 180           reverse_iterator;
 181 #endif /* __STL_CLASS_PARTIAL_SPECIALIZATION */
 182
 183 protected:
 184 #ifdef __STL_HAS_NAMESPACES
 185   using _Base::_M_allocate;
 186   using _Base::_M_deallocate;
 187   using _Base::_M_start;
 188   using _Base::_M_finish;
 189   using _Base::_M_end_of_storage;
 190 #endif /* __STL_HAS_NAMESPACES */
 191
 192 protected:
 193   void _M_insert_aux(iterator __position, const _Tp& __x);
 194   void _M_insert_aux(iterator __position);
 195
 196 public:
 197   iterator begin() { return _M_start; }
 198   const_iterator begin() const { return _M_start; }
 199   iterator end() { return _M_finish; }
 200   const_iterator end() const { return _M_finish; }
 201
 202   reverse_iterator rbegin()
 203     { return reverse_iterator(end()); }
 204   const_reverse_iterator rbegin() const
 205     { return const_reverse_iterator(end()); }
 206   reverse_iterator rend()
 207     { return reverse_iterator(begin()); }
 208   const_reverse_iterator rend() const
 209     { return const_reverse_iterator(begin()); }
 210
 211   size_type size() const
 212     { return size_type(end() - begin()); }
 213   size_type max_size() const
 214     { return size_type(-1) / sizeof(_Tp); }
 215   size_type capacity() const
 216     { return size_type(_M_end_of_storage - begin()); }
 217   bool empty() const
 218     { return begin() == end(); }
 219
 220   reference operator[](size_type __n) { return *(begin() + __n); }
 221   const_reference operator[](size_type __n) const { return *(begin() + __n); }
 222
 223   reference at(size_type __n) {
 224           if (__n >= size())
 225                   throw std::out_of_range("vector::at() out_of_range");
 226           return *(begin() + __n);
 227   }
 228
 229   const_reference at(size_type __n) const {
 230           if (__n >= size())
 231                   throw std::out_of_range("vector::at() out_of_range");
 232           return *(begin() + __n);
 233   }
 234
 235   explicit vector(const allocator_type& __a = allocator_type())
 236     : _Base(__a) {}
 237
 238   vector(size_type __n, const _Tp& __value,
 239          const allocator_type& __a = allocator_type())
 240     : _Base(__n, __a)
 241     { _M_finish = uninitialized_fill_n(_M_start, __n, __value); }
 242
 243   explicit vector(size_type __n)
 244     : _Base(__n, allocator_type())
 245     { _M_finish = uninitialized_fill_n(_M_start, __n, _Tp()); }
 246
 247   vector(const vector<_Tp, _Alloc>& __x)
 248     : _Base(__x.size(), __x.get_allocator())
 249     { _M_finish = uninitialized_copy(__x.begin(), __x.end(), _M_start); }
 250
 251 #ifdef __STL_MEMBER_TEMPLATES
 252   // Check whether it's an integral type.  If so, it's not an iterator.
 253   template <class _InputIterator>
 254   vector(_InputIterator __first, _InputIterator __last,
 255          const allocator_type& __a = allocator_type()) : _Base(__a) {
 256     typedef typename _Is_integer<_InputIterator>::_Integral _Integral;
 257     _M_initialize_aux(__first, __last, _Integral());
 258   }
 259
 260   template <class _Integer>
 261   void _M_initialize_aux(_Integer __n, _Integer __value, __true_type) {
 262     _M_start = _M_allocate(__n);
 263     _M_end_of_storage = _M_start + __n;
 264     _M_finish = uninitialized_fill_n(_M_start, __n, __value);
 265   }
 266
 267   template <class _InputIterator>
 268   void _M_initialize_aux(_InputIterator __first, _InputIterator __last,
 269                          __false_type) {
 270     _M_range_initialize(__first, __last, __ITERATOR_CATEGORY(__first));
 271   }
 272
 273 #else
 274   vector(const _Tp* __first, const _Tp* __last,
 275          const allocator_type& __a = allocator_type())
 276     : _Base(__last - __first, __a)
 277     { _M_finish = uninitialized_copy(__first, __last, _M_start); }
 278 #endif /* __STL_MEMBER_TEMPLATES */
 279
 280   ~vector() { destroy(_M_start, _M_finish); }
 281
 282   vector<_Tp, _Alloc>& operator=(const vector<_Tp, _Alloc>& __x);
 283   void reserve(size_type __n) {
 284     if (capacity() < __n) {
 285       const size_type __old_size = size();
 286       iterator __tmp = _M_allocate_and_copy(__n, _M_start, _M_finish);
 287       destroy(_M_start, _M_finish);
 288       _M_deallocate(_M_start, _M_end_of_storage - _M_start);
 289       _M_start = __tmp;
 290       _M_finish = __tmp + __old_size;
 291       _M_end_of_storage = _M_start + __n;
 292     }
 293   }
 294
 295   // assign(), a generalized assignment member function.  Two
 296   // versions: one that takes a count, and one that takes a range.
 297   // The range version is a member template, so we dispatch on whether
 298   // or not the type is an integer.
 299
 300   void assign(size_type __n, const _Tp& __val);
 301
 302 #ifdef __STL_MEMBER_TEMPLATES
 303
 304   template <class _InputIterator>
 305   void assign(_InputIterator __first, _InputIterator __last) {
 306     typedef typename _Is_integer<_InputIterator>::_Integral _Integral;
 307     _M_assign_dispatch(__first, __last, _Integral());
 308   }
 309
 310   template <class _Integer>
 311   void _M_assign_dispatch(_Integer __n, _Integer __val, __true_type)
 312     { assign((size_type) __n, (_Tp) __val); }
 313
 314   template <class _InputIter>
 315   void _M_assign_dispatch(_InputIter __first, _InputIter __last, __false_type)
 316     { _M_assign_aux(__first, __last, __ITERATOR_CATEGORY(__first)); }
 317
 318   template <class _InputIterator>
 319   void _M_assign_aux(_InputIterator __first, _InputIterator __last,
 320                      input_iterator_tag);
 321
 322   template <class _ForwardIterator>
 323   void _M_assign_aux(_ForwardIterator __first, _ForwardIterator __last,
 324                      forward_iterator_tag);
 325
 326 #endif /* __STL_MEMBER_TEMPLATES */
 327
 328   reference front() { return *begin(); }
 329   const_reference front() const { return *begin(); }
 330   reference back() { return *(end() - 1); }
 331   const_reference back() const { return *(end() - 1); }
 332
 333   void push_back(const _Tp& __x) {
 334     if (_M_finish != _M_end_of_storage) {
 335       construct(_M_finish, __x);
 336       ++_M_finish;
 337     }
 338     else
 339       _M_insert_aux(end(), __x);
 340   }
 341   void push_back() {
 342     if (_M_finish != _M_end_of_storage) {
 343       construct(_M_finish);
 344       ++_M_finish;
 345     }
 346     else
 347       _M_insert_aux(end());
 348   }
 349   void swap(vector<_Tp, _Alloc>& __x) {
 350     __STD::swap(_M_start, __x._M_start);
 351     __STD::swap(_M_finish, __x._M_finish);
 352     __STD::swap(_M_end_of_storage, __x._M_end_of_storage);
 353   }
 354
 355   iterator insert(iterator __position, const _Tp& __x) {
 356     size_type __n = __position - begin();
 357     if (_M_finish != _M_end_of_storage && __position == end()) {
 358       construct(_M_finish, __x);
 359       ++_M_finish;
 360     }
 361     else
 362       _M_insert_aux(__position, __x);
 363     return begin() + __n;
 364   }
 365   iterator insert(iterator __position) {
 366     size_type __n = __position - begin();
 367     if (_M_finish != _M_end_of_storage && __position == end()) {
 368       construct(_M_finish);
 369       ++_M_finish;
 370     }
 371     else
 372       _M_insert_aux(__position);
 373     return begin() + __n;
 374   }
 375 #ifdef __STL_MEMBER_TEMPLATES
 376   // Check whether it's an integral type.  If so, it's not an iterator.
 377   template <class _InputIterator>
 378   void insert(iterator __pos, _InputIterator __first, _InputIterator __last) {
 379     typedef typename _Is_integer<_InputIterator>::_Integral _Integral;
 380     _M_insert_dispatch(__pos, __first, __last, _Integral());
 381   }
 382
 383   template <class _Integer>
 384   void _M_insert_dispatch(iterator __pos, _Integer __n, _Integer __val,
 385                           __true_type) {
 386     insert(__pos, (size_type) __n, (_Tp) __val);
 387   }
 388
 389   template <class _InputIterator>
 390   void _M_insert_dispatch(iterator __pos,
 391                           _InputIterator __first, _InputIterator __last,
 392                           __false_type) {
 393     _M_range_insert(__pos, __first, __last, __ITERATOR_CATEGORY(__first));
 394   }
 395 #else /* __STL_MEMBER_TEMPLATES */
 396   void insert(iterator __position,
 397               const_iterator __first, const_iterator __last);
 398 #endif /* __STL_MEMBER_TEMPLATES */
 399
 400   void insert (iterator __pos, size_type __n, const _Tp& __x);
 401
 402   void pop_back() {
 403     --_M_finish;
 404     destroy(_M_finish);
 405   }
 406   iterator erase(iterator __position) {
 407     if (__position + 1 != end())
 408       copy(__position + 1, _M_finish, __position);
 409     --_M_finish;
 410     destroy(_M_finish);
 411     return __position;
 412   }
 413   iterator erase(iterator __first, iterator __last) {
 414     iterator __i = copy(__last, _M_finish, __first);
 415     destroy(__i, _M_finish);
 416     _M_finish = _M_finish - (__last - __first);
 417     return __first;
 418   }
 419
 420   void resize(size_type __new_size, const _Tp& __x) {
 421     if (__new_size < size())
 422       erase(begin() + __new_size, end());
 423     else
 424       insert(end(), __new_size - size(), __x);
 425   }
 426   void resize(size_type __new_size) { resize(__new_size, _Tp()); }
 427   void clear() { erase(begin(), end()); }
 428
 429 protected:
 430
 431 #ifdef __STL_MEMBER_TEMPLATES
 432   template <class _ForwardIterator>
 433   iterator _M_allocate_and_copy(size_type __n, _ForwardIterator __first,
 434                                                _ForwardIterator __last)
 435 {
 436     iterator __result = _M_allocate(__n);
 437     __STL_TRY {
 438       uninitialized_copy(__first, __last, __result);
 439       return __result;
 440     }
 441     __STL_UNWIND(_M_deallocate(__result, __n));
 442   }
 443 #else /* __STL_MEMBER_TEMPLATES */
 444   iterator _M_allocate_and_copy(size_type __n, const_iterator __first,
 445                                                const_iterator __last)
 446   {
 447     iterator __result = _M_allocate(__n);
 448     __STL_TRY {
 449       uninitialized_copy(__first, __last, __result);
 450       return __result;
 451     }
 452     __STL_UNWIND(_M_deallocate(__result, __n));
 453   }
 454 #endif /* __STL_MEMBER_TEMPLATES */
 455
 456
 457 #ifdef __STL_MEMBER_TEMPLATES
 458   template <class _InputIterator>
 459   void _M_range_initialize(_InputIterator __first,
 460                            _InputIterator __last, input_iterator_tag)
 461   {
 462     for ( ; __first != __last; ++__first)
 463       push_back(*__first);
 464   }
 465
 466   // This function is only called by the constructor.
 467   template <class _ForwardIterator>
 468   void _M_range_initialize(_ForwardIterator __first,
 469                            _ForwardIterator __last, forward_iterator_tag)
 470   {
 471     size_type __n = 0;
 472     distance(__first, __last, __n);
 473     _M_start = _M_allocate(__n);
 474     _M_end_of_storage = _M_start + __n;
 475     _M_finish = uninitialized_copy(__first, __last, _M_start);
 476   }
 477
 478   template <class _InputIterator>
 479   void _M_range_insert(iterator __pos,
 480                        _InputIterator __first, _InputIterator __last,
 481                        input_iterator_tag);
 482
 483   template <class _ForwardIterator>
 484   void _M_range_insert(iterator __pos,
 485                        _ForwardIterator __first, _ForwardIterator __last,
 486                        forward_iterator_tag);
 487
 488 #endif /* __STL_MEMBER_TEMPLATES */
 489 };
 490
 491 template <class _Tp, class _Alloc>
 492 inline bool
 493 operator==(const vector<_Tp, _Alloc>& __x, const vector<_Tp, _Alloc>& __y)
 494 {
 495   return __x.size() == __y.size() &&
 496          equal(__x.begin(), __x.end(), __y.begin());
 497 }
 498
 499 template <class _Tp, class _Alloc>
 500 inline bool
 501 operator<(const vector<_Tp, _Alloc>& __x, const vector<_Tp, _Alloc>& __y)
 502 {
 503   return lexicographical_compare(__x.begin(), __x.end(),
 504                                  __y.begin(), __y.end());
 505 }
 506
 507 #ifdef __STL_FUNCTION_TMPL_PARTIAL_ORDER
 508
 509 template <class _Tp, class _Alloc>
 510 inline void swap(vector<_Tp, _Alloc>& __x, vector<_Tp, _Alloc>& __y)
 511 {
 512   __x.swap(__y);
 513 }
 514
 515 #endif /* __STL_FUNCTION_TMPL_PARTIAL_ORDER */
 516
 517 template <class _Tp, class _Alloc>
 518 vector<_Tp,_Alloc>&
 519 vector<_Tp,_Alloc>::operator=(const vector<_Tp, _Alloc>& __x)
 520 {
 521   if (&__x != this) {
 522     const size_type __xlen = __x.size();
 523     if (__xlen > capacity()) {
 524       iterator __tmp = _M_allocate_and_copy(__xlen, __x.begin(), __x.end());
 525       destroy(_M_start, _M_finish);
 526       _M_deallocate(_M_start, _M_end_of_storage - _M_start);
 527       _M_start = __tmp;
 528       _M_end_of_storage = _M_start + __xlen;
 529     }
 530     else if (size() >= __xlen) {
 531       iterator __i = copy(__x.begin(), __x.end(), begin());
 532       destroy(__i, _M_finish);
 533     }
 534     else {
 535       copy(__x.begin(), __x.begin() + size(), _M_start);
 536       uninitialized_copy(__x.begin() + size(), __x.end(), _M_finish);
 537     }
 538     _M_finish = _M_start + __xlen;
 539   }
 540   return *this;
 541 }
 542
 543 template <class _Tp, class _Alloc>
 544 void vector<_Tp, _Alloc>::assign(size_t __n, const value_type& __val) {
 545   if (__n > capacity()) {
 546     vector<_Tp, _Alloc> __tmp(__n, __val, get_allocator());
 547     __tmp.swap(*this);
 548   }
 549   else if (__n > size()) {
 550     fill(begin(), end(), __val);
 551     _M_finish = uninitialized_fill_n(_M_finish, __n - size(), __val);
 552   }
 553   else
 554     erase(fill_n(begin(), __n, __val), end());
 555 }
 556
 557 #ifdef __STL_MEMBER_TEMPLATES
 558
 559 template <class _Tp, class _Alloc> template <class _InputIter>
 560 void vector<_Tp, _Alloc>::_M_assign_aux(_InputIter __first, _InputIter __last,
 561                                         input_iterator_tag) {
 562   iterator __cur = begin();
 563   for ( ; __first != __last && __cur != end(); ++__cur, ++__first)
 564     *__cur = *__first;
 565   if (__first == __last)
 566     erase(__cur, end());
 567   else
 568     insert(end(), __first, __last);
 569 }
 570
 571 template <class _Tp, class _Alloc> template <class _ForwardIter>
 572 void
 573 vector<_Tp, _Alloc>::_M_assign_aux(_ForwardIter __first, _ForwardIter __last,
 574                                    forward_iterator_tag) {
 575   size_type __len = 0;
 576   distance(__first, __last, __len);
 577
 578   if (__len > capacity()) {
 579     iterator __tmp = _M_allocate_and_copy(__len, __first, __last);
 580     destroy(_M_start, _M_finish);
 581     _M_deallocate(_M_start, _M_end_of_storage - _M_start);
 582     _M_start = __tmp;
 583     _M_end_of_storage = _M_finish = _M_start + __len;
 584   }
 585   else if (size() >= __len) {
 586     iterator __new_finish = copy(__first, __last, _M_start);
 587     destroy(__new_finish, _M_finish);
 588     _M_finish = __new_finish;
 589   }
 590   else {
 591     _ForwardIter __mid = __first;
 592     advance(__mid, size());
 593     copy(__first, __mid, _M_start);
 594     _M_finish = uninitialized_copy(__mid, __last, _M_finish);
 595   }
 596 }
 597
 598 #endif /* __STL_MEMBER_TEMPLATES */
 599
 600 template <class _Tp, class _Alloc>
 601 void
 602 vector<_Tp, _Alloc>::_M_insert_aux(iterator __position, const _Tp& __x)
 603 {
 604   if (_M_finish != _M_end_of_storage) {
 605     construct(_M_finish, *(_M_finish - 1));
 606     ++_M_finish;
 607     _Tp __x_copy = __x;
 608     copy_backward(__position, _M_finish - 2, _M_finish - 1);
 609     *__position = __x_copy;
 610   }
 611   else {
 612     const size_type __old_size = size();
 613     const size_type __len = __old_size != 0 ? 2 * __old_size : 1;
 614     iterator __new_start = _M_allocate(__len);
 615     iterator __new_finish = __new_start;
 616     __STL_TRY {
 617       __new_finish = uninitialized_copy(_M_start, __position, __new_start);
 618       construct(__new_finish, __x);
 619       ++__new_finish;
 620       __new_finish = uninitialized_copy(__position, _M_finish, __new_finish);
 621     }
 622     __STL_UNWIND((destroy(__new_start,__new_finish),
 623                   _M_deallocate(__new_start,__len)));
 624     destroy(begin(), end());
 625     _M_deallocate(_M_start, _M_end_of_storage - _M_start);
 626     _M_start = __new_start;
 627     _M_finish = __new_finish;
 628     _M_end_of_storage = __new_start + __len;
 629   }
 630 }
 631
 632 template <class _Tp, class _Alloc>
 633 void
 634 vector<_Tp, _Alloc>::_M_insert_aux(iterator __position)
 635 {
 636   if (_M_finish != _M_end_of_storage) {
 637     construct(_M_finish, *(_M_finish - 1));
 638     ++_M_finish;
 639     copy_backward(__position, _M_finish - 2, _M_finish - 1);
 640     *__position = _Tp();
 641   }
 642   else {
 643     const size_type __old_size = size();
 644     const size_type __len = __old_size != 0 ? 2 * __old_size : 1;
 645     iterator __new_start = _M_allocate(__len);
 646     iterator __new_finish = __new_start;
 647     __STL_TRY {
 648       __new_finish = uninitialized_copy(_M_start, __position, __new_start);
 649       construct(__new_finish);
 650       ++__new_finish;
 651       __new_finish = uninitialized_copy(__position, _M_finish, __new_finish);
 652     }
 653     __STL_UNWIND((destroy(__new_start,__new_finish),
 654                   _M_deallocate(__new_start,__len)));
 655     destroy(begin(), end());
 656     _M_deallocate(_M_start, _M_end_of_storage - _M_start);
 657     _M_start = __new_start;
 658     _M_finish = __new_finish;
 659     _M_end_of_storage = __new_start + __len;
 660   }
 661 }
 662
 663 template <class _Tp, class _Alloc>
 664 void vector<_Tp, _Alloc>::insert(iterator __position, size_type __n,
 665                                  const _Tp& __x)
 666 {
 667   if (__n != 0) {
 668     if (size_type(_M_end_of_storage - _M_finish) >= __n) {
 669       _Tp __x_copy = __x;
 670       const size_type __elems_after = _M_finish - __position;
 671       iterator __old_finish = _M_finish;
 672       if (__elems_after > __n) {
 673         uninitialized_copy(_M_finish - __n, _M_finish, _M_finish);
 674         _M_finish += __n;
 675         copy_backward(__position, __old_finish - __n, __old_finish);
 676         fill(__position, __position + __n, __x_copy);
 677       }
 678       else {
 679         uninitialized_fill_n(_M_finish, __n - __elems_after, __x_copy);
 680         _M_finish += __n - __elems_after;
 681         uninitialized_copy(__position, __old_finish, _M_finish);
 682         _M_finish += __elems_after;
 683         fill(__position, __old_finish, __x_copy);
 684       }
 685     }
 686     else {
 687       const size_type __old_size = size();
 688       const size_type __len = __old_size + max(__old_size, __n);
 689       iterator __new_start = _M_allocate(__len);
 690       iterator __new_finish = __new_start;
 691       __STL_TRY {
 692         __new_finish = uninitialized_copy(_M_start, __position, __new_start);
 693         __new_finish = uninitialized_fill_n(__new_finish, __n, __x);
 694         __new_finish
 695           = uninitialized_copy(__position, _M_finish, __new_finish);
 696       }
 697       __STL_UNWIND((destroy(__new_start,__new_finish),
 698                     _M_deallocate(__new_start,__len)));
 699       destroy(_M_start, _M_finish);
 700       _M_deallocate(_M_start, _M_end_of_storage - _M_start);
 701       _M_start = __new_start;
 702       _M_finish = __new_finish;
 703       _M_end_of_storage = __new_start + __len;
 704     }
 705   }
 706 }
 707
 708 #ifdef __STL_MEMBER_TEMPLATES
 709
 710 template <class _Tp, class _Alloc> template <class _InputIterator>
 711 void
 712 vector<_Tp, _Alloc>::_M_range_insert(iterator __pos,
 713                                      _InputIterator __first,
 714                                      _InputIterator __last,
 715                                      input_iterator_tag)
 716 {
 717   for ( ; __first != __last; ++__first) {
 718     __pos = insert(__pos, *__first);
 719     ++__pos;
 720   }
 721 }
 722
 723 template <class _Tp, class _Alloc> template <class _ForwardIterator>
 724 void
 725 vector<_Tp, _Alloc>::_M_range_insert(iterator __position,
 726                                      _ForwardIterator __first,
 727                                      _ForwardIterator __last,
 728                                      forward_iterator_tag)
 729 {
 730   if (__first != __last) {
 731     size_type __n = 0;
 732     distance(__first, __last, __n);
 733     if (size_type(_M_end_of_storage - _M_finish) >= __n) {
 734       const size_type __elems_after = _M_finish - __position;
 735       iterator __old_finish = _M_finish;
 736       if (__elems_after > __n) {
 737         uninitialized_copy(_M_finish - __n, _M_finish, _M_finish);
 738         _M_finish += __n;
 739         copy_backward(__position, __old_finish - __n, __old_finish);
 740         copy(__first, __last, __position);
 741       }
 742       else {
 743         _ForwardIterator __mid = __first;
 744         advance(__mid, __elems_after);
 745         uninitialized_copy(__mid, __last, _M_finish);
 746         _M_finish += __n - __elems_after;
 747         uninitialized_copy(__position, __old_finish, _M_finish);
 748         _M_finish += __elems_after;
 749         copy(__first, __mid, __position);
 750       }
 751     }
 752     else {
 753       const size_type __old_size = size();
 754       const size_type __len = __old_size + max(__old_size, __n);
 755       iterator __new_start = _M_allocate(__len);
 756       iterator __new_finish = __new_start;
 757       __STL_TRY {
 758         __new_finish = uninitialized_copy(_M_start, __position, __new_start);
 759         __new_finish = uninitialized_copy(__first, __last, __new_finish);
 760         __new_finish
 761           = uninitialized_copy(__position, _M_finish, __new_finish);
 762       }
 763       __STL_UNWIND((destroy(__new_start,__new_finish),
 764                     _M_deallocate(__new_start,__len)));
 765       destroy(_M_start, _M_finish);
 766       _M_deallocate(_M_start, _M_end_of_storage - _M_start);
 767       _M_start = __new_start;
 768       _M_finish = __new_finish;
 769       _M_end_of_storage = __new_start + __len;
 770     }
 771   }
 772 }
 773
 774 #else /* __STL_MEMBER_TEMPLATES */
 775
 776 template <class _Tp, class _Alloc>
 777 void
 778 vector<_Tp, _Alloc>::insert(iterator __position,
 779                             const_iterator __first,
 780                             const_iterator __last)
 781 {
 782   if (__first != __last) {
 783     size_type __n = 0;
 784     distance(__first, __last, __n);
 785     if (size_type(_M_end_of_storage - _M_finish) >= __n) {
 786       const size_type __elems_after = _M_finish - __position;
 787       iterator __old_finish = _M_finish;
 788       if (__elems_after > __n) {
 789         uninitialized_copy(_M_finish - __n, _M_finish, _M_finish);
 790         _M_finish += __n;
 791         copy_backward(__position, __old_finish - __n, __old_finish);
 792         copy(__first, __last, __position);
 793       }
 794       else {
 795         uninitialized_copy(__first + __elems_after, __last, _M_finish);
 796         _M_finish += __n - __elems_after;
 797         uninitialized_copy(__position, __old_finish, _M_finish);
 798         _M_finish += __elems_after;
 799         copy(__first, __first + __elems_after, __position);
 800       }
 801     }
 802     else {
 803       const size_type __old_size = size();
 804       const size_type __len = __old_size + max(__old_size, __n);
 805       iterator __new_start = _M_allocate(__len);
 806       iterator __new_finish = __new_start;
 807       __STL_TRY {
 808         __new_finish = uninitialized_copy(_M_start, __position, __new_start);
 809         __new_finish = uninitialized_copy(__first, __last, __new_finish);
 810         __new_finish
 811           = uninitialized_copy(__position, _M_finish, __new_finish);
 812       }
 813       __STL_UNWIND((destroy(__new_start,__new_finish),
 814                     _M_deallocate(__new_start,__len)));
 815       destroy(_M_start, _M_finish);
 816       _M_deallocate(_M_start, _M_end_of_storage - _M_start);
 817       _M_start = __new_start;
 818       _M_finish = __new_finish;
 819       _M_end_of_storage = __new_start + __len;
 820     }
 821   }
 822 }
 823
 824 #endif /* __STL_MEMBER_TEMPLATES */
 825
 826 #if defined(__sgi) && !defined(__GNUC__) && (_MIPS_SIM != _MIPS_SIM_ABI32)
 827 #pragma reset woff 1174
 828 #pragma reset woff 1375
 829 #endif
 830
 831 __STL_END_NAMESPACE
 832
 833 #endif /* __SGI_STL_INTERNAL_VECTOR_H */
 834
 835 // Local Variables:
 836 // mode:C++
 837 // End: