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