]>
Commit | Line | Data |
---|---|---|
42526146 PE |
1 | // Vector implementation -*- C++ -*- |
2 | ||
8fbc5ae7 | 3 | // Copyright (C) 2001, 2002, 2003 Free Software Foundation, Inc. |
42526146 PE |
4 | // |
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) | |
9 | // any later version. | |
10 | ||
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. | |
15 | ||
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, | |
19 | // USA. | |
20 | ||
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. | |
29 | ||
725dc051 BK |
30 | /* |
31 | * | |
32 | * Copyright (c) 1994 | |
33 | * Hewlett-Packard Company | |
34 | * | |
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. | |
42 | * | |
43 | * | |
44 | * Copyright (c) 1996 | |
45 | * Silicon Graphics Computer Systems, Inc. | |
46 | * | |
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. | |
54 | */ | |
55 | ||
729e3d3f PE |
56 | /** @file stl_vector.h |
57 | * This is an internal header file, included by other library headers. | |
58 | * You should not attempt to use it directly. | |
725dc051 BK |
59 | */ |
60 | ||
3d7c150e BK |
61 | #ifndef _VECTOR_H |
62 | #define _VECTOR_H 1 | |
725dc051 | 63 | |
30a20a1e | 64 | #include <bits/stl_iterator_base_funcs.h> |
e2c09482 | 65 | #include <bits/functexcept.h> |
30a20a1e | 66 | #include <bits/concept_check.h> |
725dc051 | 67 | |
285b36d6 | 68 | namespace __gnu_norm |
ad2a4e2b | 69 | { |
3971a4d2 | 70 | /// @if maint Primary default version. @endif |
ad2a4e2b | 71 | /** |
3971a4d2 PE |
72 | * @if maint |
73 | * See bits/stl_deque.h's _Deque_alloc_base for an explanation. | |
74 | * @endif | |
e4c62b26 | 75 | */ |
af5fb6ab | 76 | template<typename _Tp, typename _Allocator, bool _IsStatic> |
3971a4d2 | 77 | class _Vector_alloc_base |
af5fb6ab BK |
78 | { |
79 | public: | |
80 | typedef typename _Alloc_traits<_Tp, _Allocator>::allocator_type | |
81 | allocator_type; | |
82 | ||
83 | allocator_type | |
84 | get_allocator() const { return _M_data_allocator; } | |
3971a4d2 | 85 | |
af5fb6ab | 86 | _Vector_alloc_base(const allocator_type& __a) |
3971a4d2 | 87 | : _M_data_allocator(__a), _M_start(0), _M_finish(0), _M_end_of_storage(0) |
af5fb6ab | 88 | { } |
3971a4d2 | 89 | |
af5fb6ab BK |
90 | protected: |
91 | allocator_type _M_data_allocator; | |
92 | _Tp* _M_start; | |
93 | _Tp* _M_finish; | |
94 | _Tp* _M_end_of_storage; | |
3971a4d2 | 95 | |
af5fb6ab BK |
96 | _Tp* |
97 | _M_allocate(size_t __n) { return _M_data_allocator.allocate(__n); } | |
3971a4d2 | 98 | |
af5fb6ab BK |
99 | void |
100 | _M_deallocate(_Tp* __p, size_t __n) | |
101 | { if (__p) _M_data_allocator.deallocate(__p, __n); } | |
102 | }; | |
3971a4d2 PE |
103 | |
104 | /// @if maint Specialization for instanceless allocators. @endif | |
af5fb6ab | 105 | template<typename _Tp, typename _Allocator> |
3971a4d2 | 106 | class _Vector_alloc_base<_Tp, _Allocator, true> |
af5fb6ab BK |
107 | { |
108 | public: | |
109 | typedef typename _Alloc_traits<_Tp, _Allocator>::allocator_type | |
110 | allocator_type; | |
111 | ||
112 | allocator_type | |
113 | get_allocator() const { return allocator_type(); } | |
114 | ||
115 | _Vector_alloc_base(const allocator_type&) | |
3971a4d2 | 116 | : _M_start(0), _M_finish(0), _M_end_of_storage(0) |
af5fb6ab | 117 | { } |
3971a4d2 | 118 | |
af5fb6ab BK |
119 | protected: |
120 | _Tp* _M_start; | |
121 | _Tp* _M_finish; | |
122 | _Tp* _M_end_of_storage; | |
3971a4d2 | 123 | |
af5fb6ab BK |
124 | typedef typename _Alloc_traits<_Tp, _Allocator>::_Alloc_type _Alloc_type; |
125 | ||
126 | _Tp* | |
127 | _M_allocate(size_t __n) { return _Alloc_type::allocate(__n); } | |
3971a4d2 | 128 | |
af5fb6ab BK |
129 | void |
130 | _M_deallocate(_Tp* __p, size_t __n) { _Alloc_type::deallocate(__p, __n);} | |
131 | }; | |
3971a4d2 PE |
132 | |
133 | ||
ad2a4e2b | 134 | /** |
3971a4d2 PE |
135 | * @if maint |
136 | * See bits/stl_deque.h's _Deque_base for an explanation. | |
137 | * @endif | |
ad2a4e2b | 138 | */ |
af5fb6ab | 139 | template<typename _Tp, typename _Alloc> |
3971a4d2 PE |
140 | struct _Vector_base |
141 | : public _Vector_alloc_base<_Tp, _Alloc, | |
142 | _Alloc_traits<_Tp, _Alloc>::_S_instanceless> | |
83144cfc | 143 | { |
af5fb6ab BK |
144 | public: |
145 | typedef _Vector_alloc_base<_Tp, _Alloc, | |
146 | _Alloc_traits<_Tp, _Alloc>::_S_instanceless> | |
147 | _Base; | |
148 | typedef typename _Base::allocator_type allocator_type; | |
149 | ||
150 | _Vector_base(const allocator_type& __a) | |
151 | : _Base(__a) { } | |
152 | ||
153 | _Vector_base(size_t __n, const allocator_type& __a) | |
154 | : _Base(__a) | |
155 | { | |
f2ffecb1 | 156 | this->_M_start = this->_M_allocate(__n); |
8fbc5ae7 MM |
157 | this->_M_finish = this->_M_start; |
158 | this->_M_end_of_storage = this->_M_start + __n; | |
af5fb6ab BK |
159 | } |
160 | ||
161 | ~_Vector_base() | |
8fbc5ae7 MM |
162 | { _M_deallocate(this->_M_start, |
163 | this->_M_end_of_storage - this->_M_start); } | |
af5fb6ab | 164 | }; |
3971a4d2 PE |
165 | |
166 | ||
167 | /** | |
168 | * @brief A standard container which offers fixed time access to individual | |
169 | * elements in any order. | |
ad2a4e2b | 170 | * |
3971a4d2 PE |
171 | * @ingroup Containers |
172 | * @ingroup Sequences | |
ad2a4e2b | 173 | * |
3971a4d2 PE |
174 | * Meets the requirements of a <a href="tables.html#65">container</a>, a |
175 | * <a href="tables.html#66">reversible container</a>, and a | |
176 | * <a href="tables.html#67">sequence</a>, including the | |
177 | * <a href="tables.html#68">optional sequence requirements</a> with the | |
178 | * %exception of @c push_front and @c pop_front. | |
ad2a4e2b | 179 | * |
3971a4d2 PE |
180 | * In some terminology a %vector can be described as a dynamic C-style array, |
181 | * it offers fast and efficient access to individual elements in any order | |
182 | * and saves the user from worrying about memory and size allocation. | |
183 | * Subscripting ( @c [] ) access is also provided as with C-style arrays. | |
ad2a4e2b | 184 | */ |
af5fb6ab | 185 | template<typename _Tp, typename _Alloc = allocator<_Tp> > |
3971a4d2 | 186 | class vector : protected _Vector_base<_Tp, _Alloc> |
af5fb6ab BK |
187 | { |
188 | // Concept requirements. | |
3d7c150e | 189 | __glibcxx_class_requires(_Tp, _SGIAssignableConcept) |
af5fb6ab BK |
190 | |
191 | typedef _Vector_base<_Tp, _Alloc> _Base; | |
192 | typedef vector<_Tp, _Alloc> vector_type; | |
193 | ||
194 | public: | |
195 | typedef _Tp value_type; | |
196 | typedef value_type* pointer; | |
197 | typedef const value_type* const_pointer; | |
198 | typedef __gnu_cxx::__normal_iterator<pointer, vector_type> iterator; | |
199 | typedef __gnu_cxx::__normal_iterator<const_pointer, vector_type> | |
200 | const_iterator; | |
201 | typedef std::reverse_iterator<const_iterator> const_reverse_iterator; | |
202 | typedef std::reverse_iterator<iterator> reverse_iterator; | |
203 | typedef value_type& reference; | |
204 | typedef const value_type& const_reference; | |
205 | typedef size_t size_type; | |
206 | typedef ptrdiff_t difference_type; | |
207 | typedef typename _Base::allocator_type allocator_type; | |
208 | ||
209 | protected: | |
210 | /** @if maint | |
211 | * These two functions and three data members are all from the | |
212 | * top-most base class, which varies depending on the type of | |
213 | * %allocator. They should be pretty self-explanatory, as | |
214 | * %vector uses a simple contiguous allocation scheme. @endif | |
215 | */ | |
216 | using _Base::_M_allocate; | |
217 | using _Base::_M_deallocate; | |
218 | using _Base::_M_start; | |
219 | using _Base::_M_finish; | |
220 | using _Base::_M_end_of_storage; | |
221 | ||
222 | public: | |
223 | // [23.2.4.1] construct/copy/destroy | |
224 | // (assign() and get_allocator() are also listed in this section) | |
225 | /** | |
226 | * @brief Default constructor creates no elements. | |
227 | */ | |
228 | explicit | |
229 | vector(const allocator_type& __a = allocator_type()) | |
230 | : _Base(__a) { } | |
231 | ||
232 | /** | |
233 | * @brief Create a %vector with copies of an exemplar element. | |
234 | * @param n The number of elements to initially create. | |
235 | * @param value An element to copy. | |
236 | * | |
237 | * This constructor fills the %vector with @a n copies of @a value. | |
238 | */ | |
239 | vector(size_type __n, const value_type& __value, | |
240 | const allocator_type& __a = allocator_type()) | |
3971a4d2 | 241 | : _Base(__n, __a) |
9dd90ac6 | 242 | { this->_M_finish = std::uninitialized_fill_n(this->_M_start, __n, __value); } |
3971a4d2 | 243 | |
af5fb6ab BK |
244 | /** |
245 | * @brief Create a %vector with default elements. | |
246 | * @param n The number of elements to initially create. | |
247 | * | |
248 | * This constructor fills the %vector with @a n copies of a | |
249 | * default-constructed element. | |
250 | */ | |
251 | explicit | |
252 | vector(size_type __n) | |
3971a4d2 | 253 | : _Base(__n, allocator_type()) |
9dd90ac6 PC |
254 | { this->_M_finish = std::uninitialized_fill_n(this->_M_start, |
255 | __n, value_type()); } | |
af5fb6ab BK |
256 | |
257 | /** | |
258 | * @brief %Vector copy constructor. | |
259 | * @param x A %vector of identical element and allocator types. | |
260 | * | |
261 | * The newly-created %vector uses a copy of the allocation | |
262 | * object used by @a x. All the elements of @a x are copied, | |
263 | * but any extra memory in | |
264 | * @a x (for fast expansion) will not be copied. | |
265 | */ | |
266 | vector(const vector& __x) | |
3971a4d2 | 267 | : _Base(__x.size(), __x.get_allocator()) |
9dd90ac6 PC |
268 | { this->_M_finish = std::uninitialized_copy(__x.begin(), __x.end(), |
269 | this->_M_start); | |
8fbc5ae7 | 270 | } |
3971a4d2 | 271 | |
af5fb6ab BK |
272 | /** |
273 | * @brief Builds a %vector from a range. | |
274 | * @param first An input iterator. | |
275 | * @param last An input iterator. | |
276 | * | |
277 | * Create a %vector consisting of copies of the elements from | |
278 | * [first,last). | |
279 | * | |
280 | * If the iterators are forward, bidirectional, or random-access, then | |
281 | * this will call the elements' copy constructor N times (where N is | |
282 | * distance(first,last)) and do no memory reallocation. But if only | |
283 | * input iterators are used, then this will do at most 2N calls to the | |
284 | * copy constructor, and logN memory reallocations. | |
285 | */ | |
286 | template<typename _InputIterator> | |
287 | vector(_InputIterator __first, _InputIterator __last, | |
288 | const allocator_type& __a = allocator_type()) | |
289 | : _Base(__a) | |
3971a4d2 | 290 | { |
af5fb6ab BK |
291 | // Check whether it's an integral type. If so, it's not an iterator. |
292 | typedef typename _Is_integer<_InputIterator>::_Integral _Integral; | |
293 | _M_initialize_dispatch(__first, __last, _Integral()); | |
294 | } | |
295 | ||
296 | /** | |
297 | * The dtor only erases the elements, and note that if the elements | |
298 | * themselves are pointers, the pointed-to memory is not touched in any | |
299 | * way. Managing the pointer is the user's responsibilty. | |
300 | */ | |
9dd90ac6 | 301 | ~vector() { std::_Destroy(this->_M_start, this->_M_finish); } |
af5fb6ab BK |
302 | |
303 | /** | |
304 | * @brief %Vector assignment operator. | |
305 | * @param x A %vector of identical element and allocator types. | |
306 | * | |
307 | * All the elements of @a x are copied, but any extra memory in | |
308 | * @a x (for fast expansion) will not be copied. Unlike the | |
309 | * copy constructor, the allocator object is not copied. | |
310 | */ | |
311 | vector& | |
312 | operator=(const vector& __x); | |
313 | ||
314 | /** | |
315 | * @brief Assigns a given value to a %vector. | |
316 | * @param n Number of elements to be assigned. | |
317 | * @param val Value to be assigned. | |
318 | * | |
319 | * This function fills a %vector with @a n copies of the given | |
320 | * value. Note that the assignment completely changes the | |
321 | * %vector and that the resulting %vector's size is the same as | |
322 | * the number of elements assigned. Old data may be lost. | |
323 | */ | |
324 | void | |
325 | assign(size_type __n, const value_type& __val) | |
326 | { _M_fill_assign(__n, __val); } | |
327 | ||
328 | /** | |
329 | * @brief Assigns a range to a %vector. | |
330 | * @param first An input iterator. | |
331 | * @param last An input iterator. | |
332 | * | |
333 | * This function fills a %vector with copies of the elements in the | |
334 | * range [first,last). | |
335 | * | |
336 | * Note that the assignment completely changes the %vector and | |
337 | * that the resulting %vector's size is the same as the number | |
338 | * of elements assigned. Old data may be lost. | |
339 | */ | |
340 | template<typename _InputIterator> | |
341 | void | |
342 | assign(_InputIterator __first, _InputIterator __last) | |
3971a4d2 | 343 | { |
af5fb6ab BK |
344 | // Check whether it's an integral type. If so, it's not an iterator. |
345 | typedef typename _Is_integer<_InputIterator>::_Integral _Integral; | |
346 | _M_assign_dispatch(__first, __last, _Integral()); | |
347 | } | |
348 | ||
349 | /// Get a copy of the memory allocation object. | |
350 | allocator_type | |
351 | get_allocator() const { return _Base::get_allocator(); } | |
352 | ||
353 | // iterators | |
354 | /** | |
355 | * Returns a read/write iterator that points to the first element in the | |
356 | * %vector. Iteration is done in ordinary element order. | |
357 | */ | |
358 | iterator | |
8fbc5ae7 | 359 | begin() { return iterator (this->_M_start); } |
af5fb6ab BK |
360 | |
361 | /** | |
362 | * Returns a read-only (constant) iterator that points to the | |
363 | * first element in the %vector. Iteration is done in ordinary | |
364 | * element order. | |
365 | */ | |
366 | const_iterator | |
8fbc5ae7 | 367 | begin() const { return const_iterator (this->_M_start); } |
af5fb6ab BK |
368 | |
369 | /** | |
370 | * Returns a read/write iterator that points one past the last | |
371 | * element in the %vector. Iteration is done in ordinary | |
372 | * element order. | |
373 | */ | |
374 | iterator | |
8fbc5ae7 | 375 | end() { return iterator (this->_M_finish); } |
af5fb6ab BK |
376 | |
377 | /** | |
378 | * Returns a read-only (constant) iterator that points one past the last | |
379 | * element in the %vector. Iteration is done in ordinary element order. | |
380 | */ | |
381 | const_iterator | |
8fbc5ae7 | 382 | end() const { return const_iterator (this->_M_finish); } |
af5fb6ab BK |
383 | |
384 | /** | |
385 | * Returns a read/write reverse iterator that points to the | |
386 | * last element in the %vector. Iteration is done in reverse | |
387 | * element order. | |
388 | */ | |
389 | reverse_iterator | |
390 | rbegin() { return reverse_iterator(end()); } | |
391 | ||
392 | /** | |
393 | * Returns a read-only (constant) reverse iterator that points | |
394 | * to the last element in the %vector. Iteration is done in | |
395 | * reverse element order. | |
396 | */ | |
397 | const_reverse_iterator | |
398 | rbegin() const { return const_reverse_iterator(end()); } | |
399 | ||
400 | /** | |
401 | * Returns a read/write reverse iterator that points to one before the | |
402 | * first element in the %vector. Iteration is done in reverse element | |
403 | * order. | |
404 | */ | |
405 | reverse_iterator | |
406 | rend() { return reverse_iterator(begin()); } | |
407 | ||
408 | /** | |
409 | * Returns a read-only (constant) reverse iterator that points | |
410 | * to one before the first element in the %vector. Iteration | |
411 | * is done in reverse element order. | |
412 | */ | |
413 | const_reverse_iterator | |
414 | rend() const { return const_reverse_iterator(begin()); } | |
415 | ||
416 | // [23.2.4.2] capacity | |
417 | /** Returns the number of elements in the %vector. */ | |
418 | size_type | |
419 | size() const { return size_type(end() - begin()); } | |
420 | ||
421 | /** Returns the size() of the largest possible %vector. */ | |
422 | size_type | |
423 | max_size() const { return size_type(-1) / sizeof(value_type); } | |
424 | ||
425 | /** | |
426 | * @brief Resizes the %vector to the specified number of elements. | |
427 | * @param new_size Number of elements the %vector should contain. | |
428 | * @param x Data with which new elements should be populated. | |
429 | * | |
430 | * This function will %resize the %vector to the specified | |
431 | * number of elements. If the number is smaller than the | |
432 | * %vector's current size the %vector is truncated, otherwise | |
433 | * the %vector is extended and new elements are populated with | |
434 | * given data. | |
435 | */ | |
3971a4d2 | 436 | void |
af5fb6ab | 437 | resize(size_type __new_size, const value_type& __x) |
3971a4d2 | 438 | { |
af5fb6ab BK |
439 | if (__new_size < size()) |
440 | erase(begin() + __new_size, end()); | |
441 | else | |
442 | insert(end(), __new_size - size(), __x); | |
3971a4d2 | 443 | } |
af5fb6ab BK |
444 | |
445 | /** | |
446 | * @brief Resizes the %vector to the specified number of elements. | |
447 | * @param new_size Number of elements the %vector should contain. | |
448 | * | |
449 | * This function will resize the %vector to the specified | |
450 | * number of elements. If the number is smaller than the | |
451 | * %vector's current size the %vector is truncated, otherwise | |
452 | * the %vector is extended and new elements are | |
453 | * default-constructed. | |
454 | */ | |
455 | void | |
456 | resize(size_type __new_size) { resize(__new_size, value_type()); } | |
457 | ||
458 | /** | |
459 | * Returns the total number of elements that the %vector can hold before | |
460 | * needing to allocate more memory. | |
461 | */ | |
462 | size_type | |
463 | capacity() const | |
8fbc5ae7 | 464 | { return size_type(const_iterator(this->_M_end_of_storage) - begin()); } |
af5fb6ab BK |
465 | |
466 | /** | |
467 | * Returns true if the %vector is empty. (Thus begin() would | |
468 | * equal end().) | |
469 | */ | |
470 | bool | |
471 | empty() const { return begin() == end(); } | |
472 | ||
473 | /** | |
474 | * @brief Attempt to preallocate enough memory for specified number of | |
475 | * elements. | |
476 | * @param n Number of elements required. | |
477 | * @throw std::length_error If @a n exceeds @c max_size(). | |
478 | * | |
479 | * This function attempts to reserve enough memory for the | |
480 | * %vector to hold the specified number of elements. If the | |
481 | * number requested is more than max_size(), length_error is | |
482 | * thrown. | |
483 | * | |
484 | * The advantage of this function is that if optimal code is a | |
485 | * necessity and the user can determine the number of elements | |
486 | * that will be required, the user can reserve the memory in | |
487 | * %advance, and thus prevent a possible reallocation of memory | |
488 | * and copying of %vector data. | |
489 | */ | |
490 | void | |
491 | reserve(size_type __n); | |
492 | ||
493 | // element access | |
494 | /** | |
495 | * @brief Subscript access to the data contained in the %vector. | |
496 | * @param n The index of the element for which data should be accessed. | |
497 | * @return Read/write reference to data. | |
498 | * | |
499 | * This operator allows for easy, array-style, data access. | |
500 | * Note that data access with this operator is unchecked and | |
501 | * out_of_range lookups are not defined. (For checked lookups | |
502 | * see at().) | |
503 | */ | |
504 | reference | |
505 | operator[](size_type __n) { return *(begin() + __n); } | |
506 | ||
507 | /** | |
508 | * @brief Subscript access to the data contained in the %vector. | |
509 | * @param n The index of the element for which data should be | |
510 | * accessed. | |
511 | * @return Read-only (constant) reference to data. | |
512 | * | |
513 | * This operator allows for easy, array-style, data access. | |
514 | * Note that data access with this operator is unchecked and | |
515 | * out_of_range lookups are not defined. (For checked lookups | |
516 | * see at().) | |
517 | */ | |
518 | const_reference | |
519 | operator[](size_type __n) const { return *(begin() + __n); } | |
520 | ||
521 | protected: | |
522 | /// @if maint Safety check used only from at(). @endif | |
3971a4d2 | 523 | void |
af5fb6ab | 524 | _M_range_check(size_type __n) const |
3971a4d2 | 525 | { |
af5fb6ab | 526 | if (__n >= this->size()) |
988ad90d | 527 | __throw_out_of_range(__N("vector::_M_range_check")); |
3971a4d2 | 528 | } |
af5fb6ab BK |
529 | |
530 | public: | |
531 | /** | |
532 | * @brief Provides access to the data contained in the %vector. | |
533 | * @param n The index of the element for which data should be | |
534 | * accessed. | |
535 | * @return Read/write reference to data. | |
536 | * @throw std::out_of_range If @a n is an invalid index. | |
537 | * | |
538 | * This function provides for safer data access. The parameter is first | |
539 | * checked that it is in the range of the vector. The function throws | |
540 | * out_of_range if the check fails. | |
541 | */ | |
542 | reference | |
543 | at(size_type __n) { _M_range_check(__n); return (*this)[__n]; } | |
544 | ||
545 | /** | |
546 | * @brief Provides access to the data contained in the %vector. | |
547 | * @param n The index of the element for which data should be | |
548 | * accessed. | |
549 | * @return Read-only (constant) reference to data. | |
550 | * @throw std::out_of_range If @a n is an invalid index. | |
551 | * | |
552 | * This function provides for safer data access. The parameter | |
553 | * is first checked that it is in the range of the vector. The | |
554 | * function throws out_of_range if the check fails. | |
555 | */ | |
556 | const_reference | |
557 | at(size_type __n) const { _M_range_check(__n); return (*this)[__n]; } | |
558 | ||
559 | /** | |
560 | * Returns a read/write reference to the data at the first | |
561 | * element of the %vector. | |
562 | */ | |
563 | reference | |
564 | front() { return *begin(); } | |
565 | ||
566 | /** | |
567 | * Returns a read-only (constant) reference to the data at the first | |
568 | * element of the %vector. | |
569 | */ | |
570 | const_reference | |
571 | front() const { return *begin(); } | |
572 | ||
573 | /** | |
574 | * Returns a read/write reference to the data at the last element of the | |
575 | * %vector. | |
576 | */ | |
577 | reference | |
578 | back() { return *(end() - 1); } | |
579 | ||
580 | /** | |
581 | * Returns a read-only (constant) reference to the data at the last | |
582 | * element of the %vector. | |
583 | */ | |
584 | const_reference | |
585 | back() const { return *(end() - 1); } | |
586 | ||
587 | // [23.2.4.3] modifiers | |
588 | /** | |
589 | * @brief Add data to the end of the %vector. | |
590 | * @param x Data to be added. | |
591 | * | |
592 | * This is a typical stack operation. The function creates an | |
593 | * element at the end of the %vector and assigns the given data | |
594 | * to it. Due to the nature of a %vector this operation can be | |
595 | * done in constant time if the %vector has preallocated space | |
596 | * available. | |
597 | */ | |
3971a4d2 | 598 | void |
af5fb6ab | 599 | push_back(const value_type& __x) |
3971a4d2 | 600 | { |
8fbc5ae7 | 601 | if (this->_M_finish != this->_M_end_of_storage) |
af5fb6ab | 602 | { |
9dd90ac6 | 603 | std::_Construct(this->_M_finish, __x); |
8fbc5ae7 | 604 | ++this->_M_finish; |
af5fb6ab BK |
605 | } |
606 | else | |
607 | _M_insert_aux(end(), __x); | |
3971a4d2 | 608 | } |
af5fb6ab BK |
609 | |
610 | /** | |
611 | * @brief Removes last element. | |
612 | * | |
613 | * This is a typical stack operation. It shrinks the %vector by one. | |
614 | * | |
615 | * Note that no data is returned, and if the last element's data is | |
616 | * needed, it should be retrieved before pop_back() is called. | |
617 | */ | |
3971a4d2 | 618 | void |
af5fb6ab | 619 | pop_back() |
3971a4d2 | 620 | { |
8fbc5ae7 | 621 | --this->_M_finish; |
9dd90ac6 | 622 | std::_Destroy(this->_M_finish); |
3971a4d2 | 623 | } |
af5fb6ab BK |
624 | |
625 | /** | |
626 | * @brief Inserts given value into %vector before specified iterator. | |
627 | * @param position An iterator into the %vector. | |
628 | * @param x Data to be inserted. | |
629 | * @return An iterator that points to the inserted data. | |
630 | * | |
631 | * This function will insert a copy of the given value before | |
632 | * the specified location. Note that this kind of operation | |
633 | * could be expensive for a %vector and if it is frequently | |
634 | * used the user should consider using std::list. | |
635 | */ | |
636 | iterator | |
637 | insert(iterator __position, const value_type& __x); | |
3a9fdf30 | 638 | |
af5fb6ab BK |
639 | /** |
640 | * @brief Inserts a number of copies of given data into the %vector. | |
641 | * @param position An iterator into the %vector. | |
642 | * @param n Number of elements to be inserted. | |
643 | * @param x Data to be inserted. | |
644 | * | |
645 | * This function will insert a specified number of copies of | |
646 | * the given data before the location specified by @a position. | |
647 | * | |
648 | * Note that this kind of operation could be expensive for a | |
649 | * %vector and if it is frequently used the user should | |
650 | * consider using std::list. | |
651 | */ | |
652 | void | |
08addde6 PE |
653 | insert(iterator __position, size_type __n, const value_type& __x) |
654 | { _M_fill_insert(__position, __n, __x); } | |
af5fb6ab BK |
655 | |
656 | /** | |
657 | * @brief Inserts a range into the %vector. | |
08addde6 | 658 | * @param position An iterator into the %vector. |
af5fb6ab BK |
659 | * @param first An input iterator. |
660 | * @param last An input iterator. | |
661 | * | |
662 | * This function will insert copies of the data in the range | |
663 | * [first,last) into the %vector before the location specified | |
664 | * by @a pos. | |
665 | * | |
666 | * Note that this kind of operation could be expensive for a | |
667 | * %vector and if it is frequently used the user should | |
668 | * consider using std::list. | |
669 | */ | |
670 | template<typename _InputIterator> | |
671 | void | |
08addde6 | 672 | insert(iterator __position, _InputIterator __first, _InputIterator __last) |
af5fb6ab BK |
673 | { |
674 | // Check whether it's an integral type. If so, it's not an iterator. | |
675 | typedef typename _Is_integer<_InputIterator>::_Integral _Integral; | |
08addde6 | 676 | _M_insert_dispatch(__position, __first, __last, _Integral()); |
af5fb6ab BK |
677 | } |
678 | ||
679 | /** | |
680 | * @brief Remove element at given position. | |
681 | * @param position Iterator pointing to element to be erased. | |
682 | * @return An iterator pointing to the next element (or end()). | |
683 | * | |
684 | * This function will erase the element at the given position and thus | |
685 | * shorten the %vector by one. | |
686 | * | |
687 | * Note This operation could be expensive and if it is | |
688 | * frequently used the user should consider using std::list. | |
689 | * The user is also cautioned that this function only erases | |
690 | * the element, and that if the element is itself a pointer, | |
691 | * the pointed-to memory is not touched in any way. Managing | |
692 | * the pointer is the user's responsibilty. | |
693 | */ | |
694 | iterator | |
695 | erase(iterator __position); | |
696 | ||
697 | /** | |
698 | * @brief Remove a range of elements. | |
699 | * @param first Iterator pointing to the first element to be erased. | |
700 | * @param last Iterator pointing to one past the last element to be | |
701 | * erased. | |
702 | * @return An iterator pointing to the element pointed to by @a last | |
703 | * prior to erasing (or end()). | |
704 | * | |
705 | * This function will erase the elements in the range [first,last) and | |
706 | * shorten the %vector accordingly. | |
707 | * | |
708 | * Note This operation could be expensive and if it is | |
709 | * frequently used the user should consider using std::list. | |
710 | * The user is also cautioned that this function only erases | |
711 | * the elements, and that if the elements themselves are | |
712 | * pointers, the pointed-to memory is not touched in any way. | |
713 | * Managing the pointer is the user's responsibilty. | |
714 | */ | |
715 | iterator | |
716 | erase(iterator __first, iterator __last); | |
717 | ||
718 | /** | |
719 | * @brief Swaps data with another %vector. | |
720 | * @param x A %vector of the same element and allocator types. | |
721 | * | |
722 | * This exchanges the elements between two vectors in constant time. | |
723 | * (Three pointers, so it should be quite fast.) | |
724 | * Note that the global std::swap() function is specialized such that | |
725 | * std::swap(v1,v2) will feed to this function. | |
726 | */ | |
3971a4d2 | 727 | void |
af5fb6ab | 728 | swap(vector& __x) |
3971a4d2 | 729 | { |
8fbc5ae7 MM |
730 | std::swap(this->_M_start, __x._M_start); |
731 | std::swap(this->_M_finish, __x._M_finish); | |
732 | std::swap(this->_M_end_of_storage, __x._M_end_of_storage); | |
3971a4d2 | 733 | } |
af5fb6ab BK |
734 | |
735 | /** | |
736 | * Erases all the elements. Note that this function only erases the | |
737 | * elements, and that if the elements themselves are pointers, the | |
738 | * pointed-to memory is not touched in any way. Managing the pointer is | |
739 | * the user's responsibilty. | |
740 | */ | |
3971a4d2 | 741 | void |
af5fb6ab BK |
742 | clear() { erase(begin(), end()); } |
743 | ||
744 | protected: | |
745 | /** | |
746 | * @if maint | |
747 | * Memory expansion handler. Uses the member allocation function to | |
748 | * obtain @a n bytes of memory, and then copies [first,last) into it. | |
749 | * @endif | |
750 | */ | |
751 | template<typename _ForwardIterator> | |
752 | pointer | |
753 | _M_allocate_and_copy(size_type __n, | |
754 | _ForwardIterator __first, _ForwardIterator __last) | |
755 | { | |
f2ffecb1 | 756 | pointer __result = this->_M_allocate(__n); |
af5fb6ab BK |
757 | try |
758 | { | |
9dd90ac6 | 759 | std::uninitialized_copy(__first, __last, __result); |
af5fb6ab BK |
760 | return __result; |
761 | } | |
762 | catch(...) | |
763 | { | |
764 | _M_deallocate(__result, __n); | |
765 | __throw_exception_again; | |
766 | } | |
767 | } | |
768 | ||
769 | ||
770 | // Internal constructor functions follow. | |
771 | ||
772 | // Called by the range constructor to implement [23.1.1]/9 | |
773 | template<typename _Integer> | |
774 | void | |
775 | _M_initialize_dispatch(_Integer __n, _Integer __value, __true_type) | |
776 | { | |
8fbc5ae7 MM |
777 | this->_M_start = _M_allocate(__n); |
778 | this->_M_end_of_storage = this->_M_start + __n; | |
9dd90ac6 | 779 | this->_M_finish = std::uninitialized_fill_n(this->_M_start, __n, __value); |
af5fb6ab BK |
780 | } |
781 | ||
782 | // Called by the range constructor to implement [23.1.1]/9 | |
08addde6 | 783 | template<typename _InputIterator> |
af5fb6ab | 784 | void |
08addde6 | 785 | _M_initialize_dispatch(_InputIterator __first, _InputIterator __last, |
af5fb6ab BK |
786 | __false_type) |
787 | { | |
08addde6 | 788 | typedef typename iterator_traits<_InputIterator>::iterator_category |
af5fb6ab BK |
789 | _IterCategory; |
790 | _M_range_initialize(__first, __last, _IterCategory()); | |
791 | } | |
792 | ||
793 | // Called by the second initialize_dispatch above | |
794 | template<typename _InputIterator> | |
795 | void | |
796 | _M_range_initialize(_InputIterator __first, | |
797 | _InputIterator __last, input_iterator_tag) | |
798 | { | |
799 | for ( ; __first != __last; ++__first) | |
800 | push_back(*__first); | |
801 | } | |
802 | ||
803 | // Called by the second initialize_dispatch above | |
804 | template<typename _ForwardIterator> | |
805 | void | |
806 | _M_range_initialize(_ForwardIterator __first, | |
807 | _ForwardIterator __last, forward_iterator_tag) | |
808 | { | |
4977bab6 | 809 | size_type __n = std::distance(__first, __last); |
f2ffecb1 | 810 | this->_M_start = this->_M_allocate(__n); |
8fbc5ae7 | 811 | this->_M_end_of_storage = this->_M_start + __n; |
9dd90ac6 PC |
812 | this->_M_finish = std::uninitialized_copy(__first, __last, |
813 | this->_M_start); | |
af5fb6ab BK |
814 | } |
815 | ||
816 | ||
817 | // Internal assign functions follow. The *_aux functions do the actual | |
818 | // assignment work for the range versions. | |
819 | ||
820 | // Called by the range assign to implement [23.1.1]/9 | |
821 | template<typename _Integer> | |
822 | void | |
823 | _M_assign_dispatch(_Integer __n, _Integer __val, __true_type) | |
824 | { | |
825 | _M_fill_assign(static_cast<size_type>(__n), | |
826 | static_cast<value_type>(__val)); | |
827 | } | |
828 | ||
829 | // Called by the range assign to implement [23.1.1]/9 | |
08addde6 | 830 | template<typename _InputIterator> |
af5fb6ab | 831 | void |
08addde6 | 832 | _M_assign_dispatch(_InputIterator __first, _InputIterator __last, __false_type) |
af5fb6ab | 833 | { |
08addde6 | 834 | typedef typename iterator_traits<_InputIterator>::iterator_category |
af5fb6ab BK |
835 | _IterCategory; |
836 | _M_assign_aux(__first, __last, _IterCategory()); | |
837 | } | |
838 | ||
839 | // Called by the second assign_dispatch above | |
840 | template<typename _InputIterator> | |
841 | void | |
842 | _M_assign_aux(_InputIterator __first, _InputIterator __last, | |
843 | input_iterator_tag); | |
844 | ||
845 | // Called by the second assign_dispatch above | |
846 | template<typename _ForwardIterator> | |
847 | void | |
848 | _M_assign_aux(_ForwardIterator __first, _ForwardIterator __last, | |
849 | forward_iterator_tag); | |
850 | ||
851 | // Called by assign(n,t), and the range assign when it turns out | |
852 | // to be the same thing. | |
3971a4d2 | 853 | void |
af5fb6ab BK |
854 | _M_fill_assign(size_type __n, const value_type& __val); |
855 | ||
856 | ||
857 | // Internal insert functions follow. | |
858 | ||
859 | // Called by the range insert to implement [23.1.1]/9 | |
860 | template<typename _Integer> | |
861 | void | |
862 | _M_insert_dispatch(iterator __pos, _Integer __n, _Integer __val, | |
863 | __true_type) | |
864 | { | |
865 | _M_fill_insert(__pos, static_cast<size_type>(__n), | |
866 | static_cast<value_type>(__val)); | |
867 | } | |
868 | ||
869 | // Called by the range insert to implement [23.1.1]/9 | |
870 | template<typename _InputIterator> | |
871 | void | |
872 | _M_insert_dispatch(iterator __pos, _InputIterator __first, | |
873 | _InputIterator __last, __false_type) | |
874 | { | |
875 | typedef typename iterator_traits<_InputIterator>::iterator_category | |
876 | _IterCategory; | |
877 | _M_range_insert(__pos, __first, __last, _IterCategory()); | |
878 | } | |
879 | ||
880 | // Called by the second insert_dispatch above | |
881 | template<typename _InputIterator> | |
882 | void | |
883 | _M_range_insert(iterator __pos, _InputIterator __first, | |
884 | _InputIterator __last, input_iterator_tag); | |
885 | ||
886 | // Called by the second insert_dispatch above | |
887 | template<typename _ForwardIterator> | |
888 | void | |
889 | _M_range_insert(iterator __pos, _ForwardIterator __first, | |
890 | _ForwardIterator __last, forward_iterator_tag); | |
891 | ||
892 | // Called by insert(p,n,x), and the range insert when it turns out to be | |
893 | // the same thing. | |
894 | void | |
895 | _M_fill_insert(iterator __pos, size_type __n, const value_type& __x); | |
896 | ||
897 | // Called by insert(p,x) | |
898 | void | |
899 | _M_insert_aux(iterator __position, const value_type& __x); | |
af5fb6ab | 900 | }; |
3971a4d2 PE |
901 | |
902 | ||
903 | /** | |
904 | * @brief Vector equality comparison. | |
905 | * @param x A %vector. | |
906 | * @param y A %vector of the same type as @a x. | |
907 | * @return True iff the size and elements of the vectors are equal. | |
908 | * | |
909 | * This is an equivalence relation. It is linear in the size of the | |
910 | * vectors. Vectors are considered equivalent if their sizes are equal, | |
911 | * and if corresponding elements compare equal. | |
912 | */ | |
af5fb6ab | 913 | template<typename _Tp, typename _Alloc> |
3971a4d2 PE |
914 | inline bool |
915 | operator==(const vector<_Tp,_Alloc>& __x, const vector<_Tp,_Alloc>& __y) | |
916 | { | |
917 | return __x.size() == __y.size() && | |
9dd90ac6 | 918 | std::equal(__x.begin(), __x.end(), __y.begin()); |
3971a4d2 PE |
919 | } |
920 | ||
921 | /** | |
922 | * @brief Vector ordering relation. | |
923 | * @param x A %vector. | |
924 | * @param y A %vector of the same type as @a x. | |
9536ca34 | 925 | * @return True iff @a x is lexicographically less than @a y. |
3971a4d2 PE |
926 | * |
927 | * This is a total ordering relation. It is linear in the size of the | |
928 | * vectors. The elements must be comparable with @c <. | |
929 | * | |
9536ca34 | 930 | * See std::lexicographical_compare() for how the determination is made. |
3971a4d2 | 931 | */ |
af5fb6ab | 932 | template<typename _Tp, typename _Alloc> |
3971a4d2 PE |
933 | inline bool |
934 | operator<(const vector<_Tp,_Alloc>& __x, const vector<_Tp,_Alloc>& __y) | |
935 | { | |
9dd90ac6 PC |
936 | return std::lexicographical_compare(__x.begin(), __x.end(), |
937 | __y.begin(), __y.end()); | |
3971a4d2 PE |
938 | } |
939 | ||
940 | /// Based on operator== | |
af5fb6ab | 941 | template<typename _Tp, typename _Alloc> |
3971a4d2 PE |
942 | inline bool |
943 | operator!=(const vector<_Tp,_Alloc>& __x, const vector<_Tp,_Alloc>& __y) | |
944 | { return !(__x == __y); } | |
945 | ||
946 | /// Based on operator< | |
af5fb6ab | 947 | template<typename _Tp, typename _Alloc> |
3971a4d2 PE |
948 | inline bool |
949 | operator>(const vector<_Tp,_Alloc>& __x, const vector<_Tp,_Alloc>& __y) | |
950 | { return __y < __x; } | |
951 | ||
952 | /// Based on operator< | |
af5fb6ab | 953 | template<typename _Tp, typename _Alloc> |
3971a4d2 PE |
954 | inline bool |
955 | operator<=(const vector<_Tp,_Alloc>& __x, const vector<_Tp,_Alloc>& __y) | |
956 | { return !(__y < __x); } | |
957 | ||
958 | /// Based on operator< | |
af5fb6ab | 959 | template<typename _Tp, typename _Alloc> |
3971a4d2 PE |
960 | inline bool |
961 | operator>=(const vector<_Tp,_Alloc>& __x, const vector<_Tp,_Alloc>& __y) | |
962 | { return !(__x < __y); } | |
963 | ||
964 | /// See std::vector::swap(). | |
af5fb6ab | 965 | template<typename _Tp, typename _Alloc> |
3971a4d2 PE |
966 | inline void |
967 | swap(vector<_Tp,_Alloc>& __x, vector<_Tp,_Alloc>& __y) | |
968 | { __x.swap(__y); } | |
285b36d6 | 969 | } // namespace __gnu_norm |
725dc051 | 970 | |
3d7c150e | 971 | #endif /* _VECTOR_H */ |