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