1 // Vector implementation (out of line) -*- C++ -*-
3 // Copyright (C) 2001, 2002 Free Software Foundation, Inc.
5 // This file is part of the GNU ISO C++ Library. This library is free
6 // software; you can redistribute it and/or modify it under the
7 // terms of the GNU General Public License as published by the
8 // Free Software Foundation; either version 2, or (at your option)
11 // This library is distributed in the hope that it will be useful,
12 // but WITHOUT ANY WARRANTY; without even the implied warranty of
13 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 // GNU General Public License for more details.
16 // You should have received a copy of the GNU General Public License along
17 // with this library; see the file COPYING. If not, write to the Free
18 // Software Foundation, 59 Temple Place - Suite 330, Boston, MA 02111-1307,
21 // As a special exception, you may use this file as part of a free software
22 // library without restriction. Specifically, if other files instantiate
23 // templates or use macros or inline functions from this file, or you compile
24 // this file and link it with other files to produce an executable, this
25 // file does not by itself cause the resulting executable to be covered by
26 // the GNU General Public License. This exception does not however
27 // invalidate any other reasons why the executable file might be covered by
28 // the GNU General Public License.
33 * Hewlett-Packard Company
35 * Permission to use, copy, modify, distribute and sell this software
36 * and its documentation for any purpose is hereby granted without fee,
37 * provided that the above copyright notice appear in all copies and
38 * that both that copyright notice and this permission notice appear
39 * in supporting documentation. Hewlett-Packard Company makes no
40 * representations about the suitability of this software for any
41 * purpose. It is provided "as is" without express or implied warranty.
45 * Silicon Graphics Computer Systems, Inc.
47 * Permission to use, copy, modify, distribute and sell this software
48 * and its documentation for any purpose is hereby granted without fee,
49 * provided that the above copyright notice appear in all copies and
50 * that both that copyright notice and this permission notice appear
51 * in supporting documentation. Silicon Graphics makes no
52 * representations about the suitability of this software for any
53 * purpose. It is provided "as is" without express or implied warranty.
57 * This is an internal header file, included by other library headers.
58 * You should not attempt to use it directly.
61 #ifndef __GLIBCPP_INTERNAL_VECTOR_TCC
62 #define __GLIBCPP_INTERNAL_VECTOR_TCC
66 template <typename _Tp, typename _Alloc>
69 reserve(size_type __n)
71 if (__n > this->max_size())
72 __throw_length_error("vector::reserve");
73 if (this->capacity() < __n)
75 const size_type __old_size = size();
76 pointer __tmp = _M_allocate_and_copy(__n, _M_start, _M_finish);
77 _Destroy(_M_start, _M_finish);
78 _M_deallocate(_M_start, _M_end_of_storage - _M_start);
80 _M_finish = __tmp + __old_size;
81 _M_end_of_storage = _M_start + __n;
85 template <typename _Tp, typename _Alloc>
86 typename vector<_Tp,_Alloc>::iterator
88 insert(iterator __position, const value_type& __x)
90 size_type __n = __position - begin();
91 if (_M_finish != _M_end_of_storage && __position == end())
93 _Construct(_M_finish, __x);
97 _M_insert_aux(__position, __x);
101 template <typename _Tp, typename _Alloc>
102 typename vector<_Tp,_Alloc>::iterator
104 erase(iterator __position)
106 if (__position + 1 != end())
107 copy(__position + 1, end(), __position);
113 template <typename _Tp, typename _Alloc>
114 typename vector<_Tp,_Alloc>::iterator
116 erase(iterator __first, iterator __last)
118 iterator __i(copy(__last, end(), __first));
119 _Destroy(__i, end());
120 _M_finish = _M_finish - (__last - __first);
124 template <typename _Tp, typename _Alloc>
127 operator=(const vector<_Tp,_Alloc>& __x)
131 const size_type __xlen = __x.size();
132 if (__xlen > capacity())
134 pointer __tmp = _M_allocate_and_copy(__xlen, __x.begin(), __x.end());
135 _Destroy(_M_start, _M_finish);
136 _M_deallocate(_M_start, _M_end_of_storage - _M_start);
138 _M_end_of_storage = _M_start + __xlen;
140 else if (size() >= __xlen)
142 iterator __i(copy(__x.begin(), __x.end(), begin()));
143 _Destroy(__i, end());
147 copy(__x.begin(), __x.begin() + size(), _M_start);
148 uninitialized_copy(__x.begin() + size(), __x.end(), _M_finish);
150 _M_finish = _M_start + __xlen;
155 template <typename _Tp, typename _Alloc>
158 _M_fill_assign(size_t __n, const value_type& __val)
160 if (__n > capacity())
162 vector __tmp(__n, __val, get_allocator());
165 else if (__n > size())
167 fill(begin(), end(), __val);
168 _M_finish = uninitialized_fill_n(_M_finish, __n - size(), __val);
171 erase(fill_n(begin(), __n, __val), end());
174 template <typename _Tp, typename _Alloc> template <typename _InputIter>
177 _M_assign_aux(_InputIter __first, _InputIter __last, input_iterator_tag)
179 iterator __cur(begin());
180 for ( ; __first != __last && __cur != end(); ++__cur, ++__first)
182 if (__first == __last)
185 insert(end(), __first, __last);
188 template <typename _Tp, typename _Alloc> template <typename _ForwardIter>
191 _M_assign_aux(_ForwardIter __first, _ForwardIter __last,
192 forward_iterator_tag)
194 size_type __len = distance(__first, __last);
196 if (__len > capacity())
198 pointer __tmp(_M_allocate_and_copy(__len, __first, __last));
199 _Destroy(_M_start, _M_finish);
200 _M_deallocate(_M_start, _M_end_of_storage - _M_start);
202 _M_end_of_storage = _M_finish = _M_start + __len;
204 else if (size() >= __len)
206 iterator __new_finish(copy(__first, __last, _M_start));
207 _Destroy(__new_finish, end());
208 _M_finish = __new_finish.base();
212 _ForwardIter __mid = __first;
213 advance(__mid, size());
214 copy(__first, __mid, _M_start);
215 _M_finish = uninitialized_copy(__mid, __last, _M_finish);
219 template <typename _Tp, typename _Alloc>
222 _M_insert_aux(iterator __position, const _Tp& __x)
224 if (_M_finish != _M_end_of_storage)
226 _Construct(_M_finish, *(_M_finish - 1));
229 copy_backward(__position, iterator(_M_finish-2), iterator(_M_finish-1));
230 *__position = __x_copy;
234 const size_type __old_size = size();
235 const size_type __len = __old_size != 0 ? 2 * __old_size : 1;
236 iterator __new_start(_M_allocate(__len));
237 iterator __new_finish(__new_start);
240 __new_finish = uninitialized_copy(iterator(_M_start), __position,
242 _Construct(__new_finish.base(), __x);
244 __new_finish = uninitialized_copy(__position, iterator(_M_finish),
249 _Destroy(__new_start,__new_finish);
250 _M_deallocate(__new_start.base(),__len);
251 __throw_exception_again;
253 _Destroy(begin(), end());
254 _M_deallocate(_M_start, _M_end_of_storage - _M_start);
255 _M_start = __new_start.base();
256 _M_finish = __new_finish.base();
257 _M_end_of_storage = __new_start.base() + __len;
261 #ifdef _GLIBCPP_DEPRECATED
262 template <typename _Tp, typename _Alloc>
265 _M_insert_aux(iterator __position)
267 if (_M_finish != _M_end_of_storage)
269 _Construct(_M_finish, *(_M_finish - 1));
271 copy_backward(__position, iterator(_M_finish - 2),
272 iterator(_M_finish - 1));
273 *__position = value_type();
277 const size_type __old_size = size();
278 const size_type __len = __old_size != 0 ? 2 * __old_size : 1;
279 pointer __new_start = _M_allocate(__len);
280 pointer __new_finish = __new_start;
283 __new_finish = uninitialized_copy(iterator(_M_start), __position,
285 _Construct(__new_finish);
287 __new_finish = uninitialized_copy(__position, iterator(_M_finish),
292 _Destroy(__new_start,__new_finish);
293 _M_deallocate(__new_start,__len);
294 __throw_exception_again;
296 _Destroy(begin(), end());
297 _M_deallocate(_M_start, _M_end_of_storage - _M_start);
298 _M_start = __new_start;
299 _M_finish = __new_finish;
300 _M_end_of_storage = __new_start + __len;
305 template <typename _Tp, typename _Alloc>
308 _M_fill_insert(iterator __position, size_type __n, const value_type& __x)
312 if (size_type(_M_end_of_storage - _M_finish) >= __n) {
313 value_type __x_copy = __x;
314 const size_type __elems_after = end() - __position;
315 iterator __old_finish(_M_finish);
316 if (__elems_after > __n)
318 uninitialized_copy(_M_finish - __n, _M_finish, _M_finish);
320 copy_backward(__position, __old_finish - __n, __old_finish);
321 fill(__position, __position + __n, __x_copy);
325 uninitialized_fill_n(_M_finish, __n - __elems_after, __x_copy);
326 _M_finish += __n - __elems_after;
327 uninitialized_copy(__position, __old_finish, _M_finish);
328 _M_finish += __elems_after;
329 fill(__position, __old_finish, __x_copy);
334 const size_type __old_size = size();
335 const size_type __len = __old_size + max(__old_size, __n);
336 iterator __new_start(_M_allocate(__len));
337 iterator __new_finish(__new_start);
340 __new_finish = uninitialized_copy(begin(), __position,
342 __new_finish = uninitialized_fill_n(__new_finish, __n, __x);
344 = uninitialized_copy(__position, end(), __new_finish);
348 _Destroy(__new_start,__new_finish);
349 _M_deallocate(__new_start.base(),__len);
350 __throw_exception_again;
352 _Destroy(_M_start, _M_finish);
353 _M_deallocate(_M_start, _M_end_of_storage - _M_start);
354 _M_start = __new_start.base();
355 _M_finish = __new_finish.base();
356 _M_end_of_storage = __new_start.base() + __len;
361 template <typename _Tp, typename _Alloc> template <typename _InputIterator>
364 _M_range_insert(iterator __pos,
365 _InputIterator __first, _InputIterator __last,
368 for ( ; __first != __last; ++__first)
370 __pos = insert(__pos, *__first);
375 template <typename _Tp, typename _Alloc> template <typename _ForwardIterator>
378 _M_range_insert(iterator __position,
379 _ForwardIterator __first, _ForwardIterator __last,
380 forward_iterator_tag)
382 if (__first != __last)
384 size_type __n = distance(__first, __last);
385 if (size_type(_M_end_of_storage - _M_finish) >= __n)
387 const size_type __elems_after = end() - __position;
388 iterator __old_finish(_M_finish);
389 if (__elems_after > __n)
391 uninitialized_copy(_M_finish - __n, _M_finish, _M_finish);
393 copy_backward(__position, __old_finish - __n, __old_finish);
394 copy(__first, __last, __position);
398 _ForwardIterator __mid = __first;
399 advance(__mid, __elems_after);
400 uninitialized_copy(__mid, __last, _M_finish);
401 _M_finish += __n - __elems_after;
402 uninitialized_copy(__position, __old_finish, _M_finish);
403 _M_finish += __elems_after;
404 copy(__first, __mid, __position);
409 const size_type __old_size = size();
410 const size_type __len = __old_size + max(__old_size, __n);
411 iterator __new_start(_M_allocate(__len));
412 iterator __new_finish(__new_start);
415 __new_finish = uninitialized_copy(iterator(_M_start),
416 __position, __new_start);
417 __new_finish = uninitialized_copy(__first, __last, __new_finish);
418 __new_finish = uninitialized_copy(__position, iterator(_M_finish),
423 _Destroy(__new_start,__new_finish);
424 _M_deallocate(__new_start.base(), __len);
425 __throw_exception_again;
427 _Destroy(_M_start, _M_finish);
428 _M_deallocate(_M_start, _M_end_of_storage - _M_start);
429 _M_start = __new_start.base();
430 _M_finish = __new_finish.base();
431 _M_end_of_storage = __new_start.base() + __len;
437 #endif /* __GLIBCPP_INTERNAL_VECTOR_TCC */