Branch data Line data Source code
1 : : // Vector implementation -*- C++ -*-
2 : :
3 : : // Copyright (C) 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008
4 : : // Free Software Foundation, Inc.
5 : : //
6 : : // This file is part of the GNU ISO C++ Library. This library is free
7 : : // software; you can redistribute it and/or modify it under the
8 : : // terms of the GNU General Public License as published by the
9 : : // Free Software Foundation; either version 2, or (at your option)
10 : : // any later version.
11 : :
12 : : // This library is distributed in the hope that it will be useful,
13 : : // but WITHOUT ANY WARRANTY; without even the implied warranty of
14 : : // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15 : : // GNU General Public License for more details.
16 : :
17 : : // You should have received a copy of the GNU General Public License along
18 : : // with this library; see the file COPYING. If not, write to the Free
19 : : // Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301,
20 : : // USA.
21 : :
22 : : // As a special exception, you may use this file as part of a free software
23 : : // library without restriction. Specifically, if other files instantiate
24 : : // templates or use macros or inline functions from this file, or you compile
25 : : // this file and link it with other files to produce an executable, this
26 : : // file does not by itself cause the resulting executable to be covered by
27 : : // the GNU General Public License. This exception does not however
28 : : // invalidate any other reasons why the executable file might be covered by
29 : : // the GNU General Public License.
30 : :
31 : : /*
32 : : *
33 : : * Copyright (c) 1994
34 : : * Hewlett-Packard Company
35 : : *
36 : : * Permission to use, copy, modify, distribute and sell this software
37 : : * and its documentation for any purpose is hereby granted without fee,
38 : : * provided that the above copyright notice appear in all copies and
39 : : * that both that copyright notice and this permission notice appear
40 : : * in supporting documentation. Hewlett-Packard Company makes no
41 : : * representations about the suitability of this software for any
42 : : * purpose. It is provided "as is" without express or implied warranty.
43 : : *
44 : : *
45 : : * Copyright (c) 1996
46 : : * Silicon Graphics Computer Systems, Inc.
47 : : *
48 : : * Permission to use, copy, modify, distribute and sell this software
49 : : * and its documentation for any purpose is hereby granted without fee,
50 : : * provided that the above copyright notice appear in all copies and
51 : : * that both that copyright notice and this permission notice appear
52 : : * in supporting documentation. Silicon Graphics makes no
53 : : * representations about the suitability of this software for any
54 : : * purpose. It is provided "as is" without express or implied warranty.
55 : : */
56 : :
57 : : /** @file stl_vector.h
58 : : * This is an internal header file, included by other library headers.
59 : : * You should not attempt to use it directly.
60 : : */
61 : :
62 : : #ifndef _STL_VECTOR_H
63 : : #define _STL_VECTOR_H 1
64 : :
65 : : #include <bits/stl_iterator_base_funcs.h>
66 : : #include <bits/functexcept.h>
67 : : #include <bits/concept_check.h>
68 : :
69 : : _GLIBCXX_BEGIN_NESTED_NAMESPACE(std, _GLIBCXX_STD_D)
70 : :
71 : : /// See bits/stl_deque.h's _Deque_base for an explanation.
72 : : template<typename _Tp, typename _Alloc>
73 : : struct _Vector_base
74 : : {
75 : : typedef typename _Alloc::template rebind<_Tp>::other _Tp_alloc_type;
76 : :
77 : : struct _Vector_impl
78 : : : public _Tp_alloc_type
79 : 120468 : {
80 : : _Tp* _M_start;
81 : : _Tp* _M_finish;
82 : : _Tp* _M_end_of_storage;
83 : :
84 : : _Vector_impl()
85 : 233354 : : _Tp_alloc_type(), _M_start(0), _M_finish(0), _M_end_of_storage(0)
86 : : { }
87 : :
88 : : _Vector_impl(_Tp_alloc_type const& __a)
89 : 10388 : : _Tp_alloc_type(__a), _M_start(0), _M_finish(0), _M_end_of_storage(0)
90 : : { }
91 : : };
92 : :
93 : : public:
94 : : typedef _Alloc allocator_type;
95 : :
96 : : _Tp_alloc_type&
97 : : _M_get_Tp_allocator()
98 : 112517 : { return *static_cast<_Tp_alloc_type*>(&this->_M_impl); }
99 : :
100 : : const _Tp_alloc_type&
101 : : _M_get_Tp_allocator() const
102 : 34658 : { return *static_cast<const _Tp_alloc_type*>(&this->_M_impl); }
103 : :
104 : : allocator_type
105 : : get_allocator() const
106 : : { return allocator_type(_M_get_Tp_allocator()); }
107 : :
108 : : _Vector_base()
109 : 116682 : : _M_impl() { }
110 : :
111 : : _Vector_base(const allocator_type& __a)
112 : : : _M_impl(__a) { }
113 : :
114 : : _Vector_base(size_t __n, const allocator_type& __a)
115 : 5194 : : _M_impl(__a)
116 : : {
117 : 5194 : this->_M_impl._M_start = this->_M_allocate(__n);
118 : 5194 : this->_M_impl._M_finish = this->_M_impl._M_start;
119 : 5194 : this->_M_impl._M_end_of_storage = this->_M_impl._M_start + __n;
120 : : }
121 : :
122 : : #ifdef __GXX_EXPERIMENTAL_CXX0X__
123 : : _Vector_base(_Vector_base&& __x)
124 : : : _M_impl(__x._M_get_Tp_allocator())
125 : : {
126 : : this->_M_impl._M_start = __x._M_impl._M_start;
127 : : this->_M_impl._M_finish = __x._M_impl._M_finish;
128 : : this->_M_impl._M_end_of_storage = __x._M_impl._M_end_of_storage;
129 : : __x._M_impl._M_start = 0;
130 : : __x._M_impl._M_finish = 0;
131 : : __x._M_impl._M_end_of_storage = 0;
132 : : }
133 : : #endif
134 : :
135 : 5284 : ~_Vector_base()
136 : 246220 : { _M_deallocate(this->_M_impl._M_start, this->_M_impl._M_end_of_storage
137 : 5284 : - this->_M_impl._M_start); }
138 : :
139 : : public:
140 : : _Vector_impl _M_impl;
141 : :
142 : : _Tp*
143 : 5465 : _M_allocate(size_t __n)
144 [ + + ][ + - ]: 39157 : { return __n != 0 ? _M_impl.allocate(__n) : 0; }
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ # # ][ + - ]
145 : :
146 : : void
147 : : _M_deallocate(_Tp* __p, size_t __n)
148 : : {
149 [ + + ][ + + ]: 135241 : if (__p)
[ + + ][ + + ]
[ + + ][ + + ]
[ # # + + ]
[ + + + - ]
[ + + + + ]
[ # # ][ + + ]
[ + + # # ]
[ + + ][ + - ]
[ # # ]
[ # # # # ]
[ # # # #
# # ][ # #
+ + # # ]
[ # # + +
# # ]
[ # # # # ]
[ + + ][ # # ]
[ # # ][ + + ]
[ # # ][ # # ]
[ + + # # ]
[ + + ][ # # ]
[ # # ][ + + ]
[ + + ][ # # ]
150 : 19134 : _M_impl.deallocate(__p, __n);
151 : : }
152 : : };
153 : :
154 : :
155 : : /**
156 : : * @brief A standard container which offers fixed time access to
157 : : * individual elements in any order.
158 : : *
159 : : * @ingroup Containers
160 : : * @ingroup Sequences
161 : : *
162 : : * Meets the requirements of a <a href="tables.html#65">container</a>, a
163 : : * <a href="tables.html#66">reversible container</a>, and a
164 : : * <a href="tables.html#67">sequence</a>, including the
165 : : * <a href="tables.html#68">optional sequence requirements</a> with the
166 : : * %exception of @c push_front and @c pop_front.
167 : : *
168 : : * In some terminology a %vector can be described as a dynamic
169 : : * C-style array, it offers fast and efficient access to individual
170 : : * elements in any order and saves the user from worrying about
171 : : * memory and size allocation. Subscripting ( @c [] ) access is
172 : : * also provided as with C-style arrays.
173 : : */
174 : : template<typename _Tp, typename _Alloc = std::allocator<_Tp> >
175 : : class vector : protected _Vector_base<_Tp, _Alloc>
176 : : {
177 : : // Concept requirements.
178 : : typedef typename _Alloc::value_type _Alloc_value_type;
179 : : __glibcxx_class_requires(_Tp, _SGIAssignableConcept)
180 : : __glibcxx_class_requires2(_Tp, _Alloc_value_type, _SameTypeConcept)
181 : :
182 : : typedef _Vector_base<_Tp, _Alloc> _Base;
183 : : typedef vector<_Tp, _Alloc> vector_type;
184 : : typedef typename _Base::_Tp_alloc_type _Tp_alloc_type;
185 : :
186 : : public:
187 : : typedef _Tp value_type;
188 : : typedef typename _Tp_alloc_type::pointer pointer;
189 : : typedef typename _Tp_alloc_type::const_pointer const_pointer;
190 : : typedef typename _Tp_alloc_type::reference reference;
191 : : typedef typename _Tp_alloc_type::const_reference const_reference;
192 : : typedef __gnu_cxx::__normal_iterator<pointer, vector_type> iterator;
193 : : typedef __gnu_cxx::__normal_iterator<const_pointer, vector_type>
194 : : const_iterator;
195 : : typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
196 : : typedef std::reverse_iterator<iterator> reverse_iterator;
197 : : typedef size_t size_type;
198 : : typedef ptrdiff_t difference_type;
199 : : typedef _Alloc allocator_type;
200 : :
201 : : protected:
202 : : using _Base::_M_allocate;
203 : : using _Base::_M_deallocate;
204 : : using _Base::_M_impl;
205 : : using _Base::_M_get_Tp_allocator;
206 : :
207 : : public:
208 : : // [23.2.4.1] construct/copy/destroy
209 : : // (assign() and get_allocator() are also listed in this section)
210 : : /**
211 : : * @brief Default constructor creates no elements.
212 : : */
213 : : vector()
214 : 116682 : : _Base() { }
215 : :
216 : : /**
217 : : * @brief Creates a %vector with no elements.
218 : : * @param a An allocator object.
219 : : */
220 : : explicit
221 : : vector(const allocator_type& __a)
222 : : : _Base(__a) { }
223 : :
224 : : /**
225 : : * @brief Creates a %vector with copies of an exemplar element.
226 : : * @param n The number of elements to initially create.
227 : : * @param value An element to copy.
228 : : * @param a An allocator.
229 : : *
230 : : * This constructor fills the %vector with @a n copies of @a value.
231 : : */
232 : : explicit
233 : : vector(size_type __n, const value_type& __value = value_type(),
234 : 0 : const allocator_type& __a = allocator_type())
235 : 0 : : _Base(__n, __a)
236 : 0 : { _M_fill_initialize(__n, __value); }
237 : :
238 : : /**
239 : : * @brief %Vector copy constructor.
240 : : * @param x A %vector of identical element and allocator types.
241 : : *
242 : : * The newly-created %vector uses a copy of the allocation
243 : : * object used by @a x. All the elements of @a x are copied,
244 : : * but any extra memory in
245 : : * @a x (for fast expansion) will not be copied.
246 : : */
247 : 5122 : vector(const vector& __x)
248 : 10388 : : _Base(__x.size(), __x._M_get_Tp_allocator())
249 : 25010 : { this->_M_impl._M_finish =
250 : : std::__uninitialized_copy_a(__x.begin(), __x.end(),
251 : : this->_M_impl._M_start,
252 : : _M_get_Tp_allocator());
253 : 5122 : }
254 : :
255 : : #ifdef __GXX_EXPERIMENTAL_CXX0X__
256 : : /**
257 : : * @brief %Vector move constructor.
258 : : * @param x A %vector of identical element and allocator types.
259 : : *
260 : : * The newly-created %vector contains the exact contents of @a x.
261 : : * The contents of @a x are a valid, but unspecified %vector.
262 : : */
263 : : vector(vector&& __x)
264 : : : _Base(std::forward<_Base>(__x)) { }
265 : : #endif
266 : :
267 : : /**
268 : : * @brief Builds a %vector from a range.
269 : : * @param first An input iterator.
270 : : * @param last An input iterator.
271 : : * @param a An allocator.
272 : : *
273 : : * Create a %vector consisting of copies of the elements from
274 : : * [first,last).
275 : : *
276 : : * If the iterators are forward, bidirectional, or
277 : : * random-access, then this will call the elements' copy
278 : : * constructor N times (where N is distance(first,last)) and do
279 : : * no memory reallocation. But if only input iterators are
280 : : * used, then this will do at most 2N calls to the copy
281 : : * constructor, and logN memory reallocations.
282 : : */
283 : : template<typename _InputIterator>
284 : : vector(_InputIterator __first, _InputIterator __last,
285 : : const allocator_type& __a = allocator_type())
286 : : : _Base(__a)
287 : : {
288 : : // Check whether it's an integral type. If so, it's not an iterator.
289 : : typedef typename std::__is_integer<_InputIterator>::__type _Integral;
290 : : _M_initialize_dispatch(__first, __last, _Integral());
291 : : }
292 : :
293 : : /**
294 : : * The dtor only erases the elements, and note that if the
295 : : * elements themselves are pointers, the pointed-to memory is
296 : : * not touched in any way. Managing the pointer is the user's
297 : : * responsibility.
298 : : */
299 : 120101 : ~vector()
300 : 124382 : { std::_Destroy(this->_M_impl._M_start, this->_M_impl._M_finish,
301 : 120101 : _M_get_Tp_allocator()); }
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 : : #ifdef __GXX_EXPERIMENTAL_CXX0X__
315 : : /**
316 : : * @brief %Vector move assignment operator.
317 : : * @param x A %vector of identical element and allocator types.
318 : : *
319 : : * The contents of @a x are moved into this %vector (without copying).
320 : : * @a x is a valid, but unspecified %vector.
321 : : */
322 : : vector&
323 : : operator=(vector&& __x)
324 : : {
325 : : // NB: DR 675.
326 : : this->clear();
327 : : this->swap(__x);
328 : : return *this;
329 : : }
330 : : #endif
331 : :
332 : : /**
333 : : * @brief Assigns a given value to a %vector.
334 : : * @param n Number of elements to be assigned.
335 : : * @param val Value to be assigned.
336 : : *
337 : : * This function fills a %vector with @a n copies of the given
338 : : * value. Note that the assignment completely changes the
339 : : * %vector and that the resulting %vector's size is the same as
340 : : * the number of elements assigned. Old data may be lost.
341 : : */
342 : : void
343 : : assign(size_type __n, const value_type& __val)
344 : : { _M_fill_assign(__n, __val); }
345 : :
346 : : /**
347 : : * @brief Assigns a range to a %vector.
348 : : * @param first An input iterator.
349 : : * @param last An input iterator.
350 : : *
351 : : * This function fills a %vector with copies of the elements in the
352 : : * range [first,last).
353 : : *
354 : : * Note that the assignment completely changes the %vector and
355 : : * that the resulting %vector's size is the same as the number
356 : : * of elements assigned. Old data may be lost.
357 : : */
358 : : template<typename _InputIterator>
359 : : void
360 : : assign(_InputIterator __first, _InputIterator __last)
361 : : {
362 : : // Check whether it's an integral type. If so, it's not an iterator.
363 : : typedef typename std::__is_integer<_InputIterator>::__type _Integral;
364 : : _M_assign_dispatch(__first, __last, _Integral());
365 : : }
366 : :
367 : : /// Get a copy of the memory allocation object.
368 : : using _Base::get_allocator;
369 : :
370 : : // iterators
371 : : /**
372 : : * Returns a read/write iterator that points to the first
373 : : * element in the %vector. Iteration is done in ordinary
374 : : * element order.
375 : : */
376 : : iterator
377 : : begin()
378 : 4880110 : { return iterator(this->_M_impl._M_start); }
379 : :
380 : : /**
381 : : * Returns a read-only (constant) iterator that points to the
382 : : * first element in the %vector. Iteration is done in ordinary
383 : : * element order.
384 : : */
385 : : const_iterator
386 : : begin() const
387 : 10476 : { return const_iterator(this->_M_impl._M_start); }
388 : :
389 : : /**
390 : : * Returns a read/write iterator that points one past the last
391 : : * element in the %vector. Iteration is done in ordinary
392 : : * element order.
393 : : */
394 : : iterator
395 : : end()
396 : 6637786 : { return iterator(this->_M_impl._M_finish); }
397 : :
398 : : /**
399 : : * Returns a read-only (constant) iterator that points one past
400 : : * the last element in the %vector. Iteration is done in
401 : : * ordinary element order.
402 : : */
403 : : const_iterator
404 : : end() const
405 : 10476 : { return const_iterator(this->_M_impl._M_finish); }
406 : :
407 : : /**
408 : : * Returns a read/write reverse iterator that points to the
409 : : * last element in the %vector. Iteration is done in reverse
410 : : * element order.
411 : : */
412 : : reverse_iterator
413 : : rbegin()
414 : : { return reverse_iterator(end()); }
415 : :
416 : : /**
417 : : * Returns a read-only (constant) reverse iterator that points
418 : : * to the last element in the %vector. Iteration is done in
419 : : * reverse element order.
420 : : */
421 : : const_reverse_iterator
422 : : rbegin() const
423 : : { return const_reverse_iterator(end()); }
424 : :
425 : : /**
426 : : * Returns a read/write reverse iterator that points to one
427 : : * before the first element in the %vector. Iteration is done
428 : : * in reverse element order.
429 : : */
430 : : reverse_iterator
431 : : rend()
432 : : { return reverse_iterator(begin()); }
433 : :
434 : : /**
435 : : * Returns a read-only (constant) reverse iterator that points
436 : : * to one before the first element in the %vector. Iteration
437 : : * is done in reverse element order.
438 : : */
439 : : const_reverse_iterator
440 : : rend() const
441 : : { return const_reverse_iterator(begin()); }
442 : :
443 : : #ifdef __GXX_EXPERIMENTAL_CXX0X__
444 : : /**
445 : : * Returns a read-only (constant) iterator that points to the
446 : : * first element in the %vector. Iteration is done in ordinary
447 : : * element order.
448 : : */
449 : : const_iterator
450 : : cbegin() const
451 : : { return const_iterator(this->_M_impl._M_start); }
452 : :
453 : : /**
454 : : * Returns a read-only (constant) iterator that points one past
455 : : * the last element in the %vector. Iteration is done in
456 : : * ordinary element order.
457 : : */
458 : : const_iterator
459 : : cend() const
460 : : { return const_iterator(this->_M_impl._M_finish); }
461 : :
462 : : /**
463 : : * Returns a read-only (constant) reverse iterator that points
464 : : * to the last element in the %vector. Iteration is done in
465 : : * reverse element order.
466 : : */
467 : : const_reverse_iterator
468 : : crbegin() const
469 : : { return const_reverse_iterator(end()); }
470 : :
471 : : /**
472 : : * Returns a read-only (constant) reverse iterator that points
473 : : * to one before the first element in the %vector. Iteration
474 : : * is done in reverse element order.
475 : : */
476 : : const_reverse_iterator
477 : : crend() const
478 : : { return const_reverse_iterator(begin()); }
479 : : #endif
480 : :
481 : : // [23.2.4.2] capacity
482 : : /** Returns the number of elements in the %vector. */
483 : : size_type
484 : : size() const
485 : 34958029 : { return size_type(this->_M_impl._M_finish - this->_M_impl._M_start); }
486 : :
487 : : /** Returns the size() of the largest possible %vector. */
488 : : size_type
489 : : max_size() const
490 : 88392 : { return _M_get_Tp_allocator().max_size(); }
491 : :
492 : : /**
493 : : * @brief Resizes the %vector to the specified number of elements.
494 : : * @param new_size Number of elements the %vector should contain.
495 : : * @param x Data with which new elements should be populated.
496 : : *
497 : : * This function will %resize the %vector to the specified
498 : : * number of elements. If the number is smaller than the
499 : : * %vector's current size the %vector is truncated, otherwise
500 : : * the %vector is extended and new elements are populated with
501 : : * given data.
502 : : */
503 : : void
504 : 0 : resize(size_type __new_size, value_type __x = value_type())
505 : : {
506 [ # # ]: 0 : if (__new_size < size())
507 : 0 : _M_erase_at_end(this->_M_impl._M_start + __new_size);
508 : : else
509 : 0 : insert(end(), __new_size - size(), __x);
510 : 0 : }
511 : :
512 : : /**
513 : : * Returns the total number of elements that the %vector can
514 : : * hold before needing to allocate more memory.
515 : : */
516 : : size_type
517 : : capacity() const
518 : : { return size_type(this->_M_impl._M_end_of_storage
519 : 44 : - this->_M_impl._M_start); }
520 : :
521 : : /**
522 : : * Returns true if the %vector is empty. (Thus begin() would
523 : : * equal end().)
524 : : */
525 : : bool
526 : : empty() const
527 : 0 : { return begin() == end(); }
528 : :
529 : : /**
530 : : * @brief Attempt to preallocate enough memory for specified number of
531 : : * elements.
532 : : * @param n Number of elements required.
533 : : * @throw std::length_error If @a n exceeds @c max_size().
534 : : *
535 : : * This function attempts to reserve enough memory for the
536 : : * %vector to hold the specified number of elements. If the
537 : : * number requested is more than max_size(), length_error is
538 : : * thrown.
539 : : *
540 : : * The advantage of this function is that if optimal code is a
541 : : * necessity and the user can determine the number of elements
542 : : * that will be required, the user can reserve the memory in
543 : : * %advance, and thus prevent a possible reallocation of memory
544 : : * and copying of %vector data.
545 : : */
546 : : void
547 : : reserve(size_type __n);
548 : :
549 : : // element access
550 : : /**
551 : : * @brief Subscript access to the data contained in the %vector.
552 : : * @param n The index of the element for which data should be
553 : : * accessed.
554 : : * @return Read/write reference to data.
555 : : *
556 : : * This operator allows for easy, array-style, data access.
557 : : * Note that data access with this operator is unchecked and
558 : : * out_of_range lookups are not defined. (For checked lookups
559 : : * see at().)
560 : : */
561 : : reference
562 : : operator[](size_type __n)
563 : 52705921 : { return *(this->_M_impl._M_start + __n); }
564 : :
565 : : /**
566 : : * @brief Subscript access to the data contained in the %vector.
567 : : * @param n The index of the element for which data should be
568 : : * accessed.
569 : : * @return Read-only (constant) reference to data.
570 : : *
571 : : * This operator allows for easy, array-style, data access.
572 : : * Note that data access with this operator is unchecked and
573 : : * out_of_range lookups are not defined. (For checked lookups
574 : : * see at().)
575 : : */
576 : : const_reference
577 : : operator[](size_type __n) const
578 : 5044550 : { return *(this->_M_impl._M_start + __n); }
579 : :
580 : : protected:
581 : : /// Safety check used only from at().
582 : : void
583 : : _M_range_check(size_type __n) const
584 : : {
585 : : if (__n >= this->size())
586 : : __throw_out_of_range(__N("vector::_M_range_check"));
587 : : }
588 : :
589 : : public:
590 : : /**
591 : : * @brief Provides access to the data contained in the %vector.
592 : : * @param n The index of the element for which data should be
593 : : * accessed.
594 : : * @return Read/write reference to data.
595 : : * @throw std::out_of_range If @a n is an invalid index.
596 : : *
597 : : * This function provides for safer data access. The parameter
598 : : * is first checked that it is in the range of the vector. The
599 : : * function throws out_of_range if the check fails.
600 : : */
601 : : reference
602 : : at(size_type __n)
603 : : {
604 : : _M_range_check(__n);
605 : : return (*this)[__n];
606 : : }
607 : :
608 : : /**
609 : : * @brief Provides access to the data contained in the %vector.
610 : : * @param n The index of the element for which data should be
611 : : * accessed.
612 : : * @return Read-only (constant) reference to data.
613 : : * @throw std::out_of_range If @a n is an invalid index.
614 : : *
615 : : * This function provides for safer data access. The parameter
616 : : * is first checked that it is in the range of the vector. The
617 : : * function throws out_of_range if the check fails.
618 : : */
619 : : const_reference
620 : : at(size_type __n) const
621 : : {
622 : : _M_range_check(__n);
623 : : return (*this)[__n];
624 : : }
625 : :
626 : : /**
627 : : * Returns a read/write reference to the data at the first
628 : : * element of the %vector.
629 : : */
630 : : reference
631 : : front()
632 : : { return *begin(); }
633 : :
634 : : /**
635 : : * Returns a read-only (constant) reference to the data at the first
636 : : * element of the %vector.
637 : : */
638 : : const_reference
639 : : front() const
640 : : { return *begin(); }
641 : :
642 : : /**
643 : : * Returns a read/write reference to the data at the last
644 : : * element of the %vector.
645 : : */
646 : : reference
647 : : back()
648 : 52 : { return *(end() - 1); }
649 : :
650 : : /**
651 : : * Returns a read-only (constant) reference to the data at the
652 : : * last element of the %vector.
653 : : */
654 : : const_reference
655 : : back() const
656 : : { return *(end() - 1); }
657 : :
658 : : // _GLIBCXX_RESOLVE_LIB_DEFECTS
659 : : // DR 464. Suggestion for new member functions in standard containers.
660 : : // data access
661 : : /**
662 : : * Returns a pointer such that [data(), data() + size()) is a valid
663 : : * range. For a non-empty %vector, data() == &front().
664 : : */
665 : : pointer
666 : : data()
667 : : { return pointer(this->_M_impl._M_start); }
668 : :
669 : : const_pointer
670 : : data() const
671 : : { return const_pointer(this->_M_impl._M_start); }
672 : :
673 : : // [23.2.4.3] modifiers
674 : : /**
675 : : * @brief Add data to the end of the %vector.
676 : : * @param x Data to be added.
677 : : *
678 : : * This is a typical stack operation. The function creates an
679 : : * element at the end of the %vector and assigns the given data
680 : : * to it. Due to the nature of a %vector this operation can be
681 : : * done in constant time if the %vector has preallocated space
682 : : * available.
683 : : */
684 : : #ifndef __GXX_EXPERIMENTAL_CXX0X__
685 : : void
686 : 19830 : push_back(const value_type& __x)
687 : : {
688 [ + + + + ]: 20860 : if (this->_M_impl._M_finish != this->_M_impl._M_end_of_storage)
[ # # ][ + + ]
[ - + ][ + + ]
[ + + + +
+ + + + -
+ ][ + + ]
[ + + # # ]
[ # # ][ + + ]
689 : : {
690 : 6128 : this->_M_impl.construct(this->_M_impl._M_finish, __x);
691 : 6128 : ++this->_M_impl._M_finish;
692 : : }
693 : : else
694 : 14732 : _M_insert_aux(end(), __x);
695 : 19830 : }
696 : : #else
697 : : template<typename... _Args>
698 : : void
699 : : push_back(_Args&&... __args)
700 : : {
701 : : if (this->_M_impl._M_finish != this->_M_impl._M_end_of_storage)
702 : : {
703 : : this->_M_impl.construct(this->_M_impl._M_finish,
704 : : std::forward<_Args>(__args)...);
705 : : ++this->_M_impl._M_finish;
706 : : }
707 : : else
708 : : _M_insert_aux(end(), std::forward<_Args>(__args)...);
709 : : }
710 : : #endif
711 : :
712 : : /**
713 : : * @brief Removes last element.
714 : : *
715 : : * This is a typical stack operation. It shrinks the %vector by one.
716 : : *
717 : : * Note that no data is returned, and if the last element's
718 : : * data is needed, it should be retrieved before pop_back() is
719 : : * called.
720 : : */
721 : : void
722 : : pop_back()
723 : : {
724 : : --this->_M_impl._M_finish;
725 : : this->_M_impl.destroy(this->_M_impl._M_finish);
726 : : }
727 : :
728 : : #ifdef __GXX_EXPERIMENTAL_CXX0X__
729 : : /**
730 : : * @brief Inserts an object in %vector before specified iterator.
731 : : * @param position An iterator into the %vector.
732 : : * @param args Arguments.
733 : : * @return An iterator that points to the inserted data.
734 : : *
735 : : * This function will insert an object of type T constructed
736 : : * with T(std::forward<Args>(args)...) before the specified location.
737 : : * Note that this kind of operation could be expensive for a %vector
738 : : * and if it is frequently used the user should consider using
739 : : * std::list.
740 : : */
741 : : template<typename... _Args>
742 : : iterator
743 : : emplace(iterator __position, _Args&&... __args);
744 : : #endif
745 : :
746 : : /**
747 : : * @brief Inserts given value into %vector before specified iterator.
748 : : * @param position An iterator into the %vector.
749 : : * @param x Data to be inserted.
750 : : * @return An iterator that points to the inserted data.
751 : : *
752 : : * This function will insert a copy of the given value before
753 : : * the specified location. Note that this kind of operation
754 : : * could be expensive for a %vector and if it is frequently
755 : : * used the user should consider using std::list.
756 : : */
757 : : iterator
758 : : insert(iterator __position, const value_type& __x);
759 : :
760 : : #ifdef __GXX_EXPERIMENTAL_CXX0X__
761 : : /**
762 : : * @brief Inserts given rvalue into %vector before specified iterator.
763 : : * @param position An iterator into the %vector.
764 : : * @param x Data to be inserted.
765 : : * @return An iterator that points to the inserted data.
766 : : *
767 : : * This function will insert a copy of the given rvalue before
768 : : * the specified location. Note that this kind of operation
769 : : * could be expensive for a %vector and if it is frequently
770 : : * used the user should consider using std::list.
771 : : */
772 : : iterator
773 : : insert(iterator __position, value_type&& __x)
774 : : { return emplace(__position, std::move(__x)); }
775 : : #endif
776 : :
777 : : /**
778 : : * @brief Inserts a number of copies of given data into the %vector.
779 : : * @param position An iterator into the %vector.
780 : : * @param n Number of elements to be inserted.
781 : : * @param x Data to be inserted.
782 : : *
783 : : * This function will insert a specified number of copies of
784 : : * the given data before the location specified by @a position.
785 : : *
786 : : * Note that this kind of operation could be expensive for a
787 : : * %vector and if it is frequently used the user should
788 : : * consider using std::list.
789 : : */
790 : : void
791 : : insert(iterator __position, size_type __n, const value_type& __x)
792 : 0 : { _M_fill_insert(__position, __n, __x); }
793 : :
794 : : /**
795 : : * @brief Inserts a range into the %vector.
796 : : * @param position An iterator into the %vector.
797 : : * @param first An input iterator.
798 : : * @param last An input iterator.
799 : : *
800 : : * This function will insert copies of the data in the range
801 : : * [first,last) into the %vector before the location specified
802 : : * by @a pos.
803 : : *
804 : : * Note that this kind of operation could be expensive for a
805 : : * %vector and if it is frequently used the user should
806 : : * consider using std::list.
807 : : */
808 : : template<typename _InputIterator>
809 : : void
810 : : insert(iterator __position, _InputIterator __first,
811 : : _InputIterator __last)
812 : : {
813 : : // Check whether it's an integral type. If so, it's not an iterator.
814 : : typedef typename std::__is_integer<_InputIterator>::__type _Integral;
815 : : _M_insert_dispatch(__position, __first, __last, _Integral());
816 : : }
817 : :
818 : : /**
819 : : * @brief Remove element at given position.
820 : : * @param position Iterator pointing to element to be erased.
821 : : * @return An iterator pointing to the next element (or end()).
822 : : *
823 : : * This function will erase the element at the given position and thus
824 : : * shorten the %vector by one.
825 : : *
826 : : * Note This operation could be expensive and if it is
827 : : * frequently used the user should consider using std::list.
828 : : * The user is also cautioned that this function only erases
829 : : * the element, and that if the element is itself a pointer,
830 : : * the pointed-to memory is not touched in any way. Managing
831 : : * the pointer is the user's responsibility.
832 : : */
833 : : iterator
834 : : erase(iterator __position);
835 : :
836 : : /**
837 : : * @brief Remove a range of elements.
838 : : * @param first Iterator pointing to the first element to be erased.
839 : : * @param last Iterator pointing to one past the last element to be
840 : : * erased.
841 : : * @return An iterator pointing to the element pointed to by @a last
842 : : * prior to erasing (or end()).
843 : : *
844 : : * This function will erase the elements in the range [first,last) and
845 : : * shorten the %vector accordingly.
846 : : *
847 : : * Note This operation could be expensive and if it is
848 : : * frequently used the user should consider using std::list.
849 : : * The user is also cautioned that this function only erases
850 : : * the elements, and that if the elements themselves are
851 : : * pointers, the pointed-to memory is not touched in any way.
852 : : * Managing the pointer is the user's responsibility.
853 : : */
854 : : iterator
855 : : erase(iterator __first, iterator __last);
856 : :
857 : : /**
858 : : * @brief Swaps data with another %vector.
859 : : * @param x A %vector of the same element and allocator types.
860 : : *
861 : : * This exchanges the elements between two vectors in constant time.
862 : : * (Three pointers, so it should be quite fast.)
863 : : * Note that the global std::swap() function is specialized such that
864 : : * std::swap(v1,v2) will feed to this function.
865 : : */
866 : : void
867 : : #ifdef __GXX_EXPERIMENTAL_CXX0X__
868 : : swap(vector&& __x)
869 : : #else
870 : : swap(vector& __x)
871 : : #endif
872 : : {
873 : : std::swap(this->_M_impl._M_start, __x._M_impl._M_start);
874 : : std::swap(this->_M_impl._M_finish, __x._M_impl._M_finish);
875 : : std::swap(this->_M_impl._M_end_of_storage,
876 : : __x._M_impl._M_end_of_storage);
877 : :
878 : : // _GLIBCXX_RESOLVE_LIB_DEFECTS
879 : : // 431. Swapping containers with unequal allocators.
880 : : std::__alloc_swap<_Tp_alloc_type>::_S_do_it(_M_get_Tp_allocator(),
881 : : __x._M_get_Tp_allocator());
882 : : }
883 : :
884 : : /**
885 : : * Erases all the elements. Note that this function only erases the
886 : : * elements, and that if the elements themselves are pointers, the
887 : : * pointed-to memory is not touched in any way. Managing the pointer is
888 : : * the user's responsibility.
889 : : */
890 : : void
891 : : clear()
892 : 1958 : { _M_erase_at_end(this->_M_impl._M_start); }
893 : :
894 : : protected:
895 : : /**
896 : : * Memory expansion handler. Uses the member allocation function to
897 : : * obtain @a n bytes of memory, and then copies [first,last) into it.
898 : : */
899 : : template<typename _ForwardIterator>
900 : : pointer
901 : : _M_allocate_and_copy(size_type __n,
902 : : _ForwardIterator __first, _ForwardIterator __last)
903 : : {
904 : 79 : pointer __result = this->_M_allocate(__n);
905 : : try
906 : : {
907 : 82 : std::__uninitialized_copy_a(__first, __last, __result,
908 : : _M_get_Tp_allocator());
909 : 41 : return __result;
910 : : }
911 : 0 : catch(...)
912 : : {
913 : 0 : _M_deallocate(__result, __n);
914 : 0 : __throw_exception_again;
915 : : }
916 : : }
917 : :
918 : :
919 : : // Internal constructor functions follow.
920 : :
921 : : // Called by the range constructor to implement [23.1.1]/9
922 : :
923 : : // _GLIBCXX_RESOLVE_LIB_DEFECTS
924 : : // 438. Ambiguity in the "do the right thing" clause
925 : : template<typename _Integer>
926 : : void
927 : : _M_initialize_dispatch(_Integer __n, _Integer __value, __true_type)
928 : : {
929 : : this->_M_impl._M_start = _M_allocate(static_cast<size_type>(__n));
930 : : this->_M_impl._M_end_of_storage =
931 : : this->_M_impl._M_start + static_cast<size_type>(__n);
932 : : _M_fill_initialize(static_cast<size_type>(__n), __value);
933 : : }
934 : :
935 : : // Called by the range constructor to implement [23.1.1]/9
936 : : template<typename _InputIterator>
937 : : void
938 : : _M_initialize_dispatch(_InputIterator __first, _InputIterator __last,
939 : : __false_type)
940 : : {
941 : : typedef typename std::iterator_traits<_InputIterator>::
942 : : iterator_category _IterCategory;
943 : : _M_range_initialize(__first, __last, _IterCategory());
944 : : }
945 : :
946 : : // Called by the second initialize_dispatch above
947 : : template<typename _InputIterator>
948 : : void
949 : : _M_range_initialize(_InputIterator __first,
950 : : _InputIterator __last, std::input_iterator_tag)
951 : : {
952 : : for (; __first != __last; ++__first)
953 : : push_back(*__first);
954 : : }
955 : :
956 : : // Called by the second initialize_dispatch above
957 : : template<typename _ForwardIterator>
958 : : void
959 : : _M_range_initialize(_ForwardIterator __first,
960 : : _ForwardIterator __last, std::forward_iterator_tag)
961 : : {
962 : : const size_type __n = std::distance(__first, __last);
963 : : this->_M_impl._M_start = this->_M_allocate(__n);
964 : : this->_M_impl._M_end_of_storage = this->_M_impl._M_start + __n;
965 : : this->_M_impl._M_finish =
966 : : std::__uninitialized_copy_a(__first, __last,
967 : : this->_M_impl._M_start,
968 : : _M_get_Tp_allocator());
969 : : }
970 : :
971 : : // Called by the first initialize_dispatch above and by the
972 : : // vector(n,value,a) constructor.
973 : : void
974 : : _M_fill_initialize(size_type __n, const value_type& __value)
975 : : {
976 : 0 : std::__uninitialized_fill_n_a(this->_M_impl._M_start, __n, __value,
977 : : _M_get_Tp_allocator());
978 : 0 : this->_M_impl._M_finish = this->_M_impl._M_end_of_storage;
979 : : }
980 : :
981 : :
982 : : // Internal assign functions follow. The *_aux functions do the actual
983 : : // assignment work for the range versions.
984 : :
985 : : // Called by the range assign to implement [23.1.1]/9
986 : :
987 : : // _GLIBCXX_RESOLVE_LIB_DEFECTS
988 : : // 438. Ambiguity in the "do the right thing" clause
989 : : template<typename _Integer>
990 : : void
991 : : _M_assign_dispatch(_Integer __n, _Integer __val, __true_type)
992 : : { _M_fill_assign(__n, __val); }
993 : :
994 : : // Called by the range assign to implement [23.1.1]/9
995 : : template<typename _InputIterator>
996 : : void
997 : : _M_assign_dispatch(_InputIterator __first, _InputIterator __last,
998 : : __false_type)
999 : : {
1000 : : typedef typename std::iterator_traits<_InputIterator>::
1001 : : iterator_category _IterCategory;
1002 : : _M_assign_aux(__first, __last, _IterCategory());
1003 : : }
1004 : :
1005 : : // Called by the second assign_dispatch above
1006 : : template<typename _InputIterator>
1007 : : void
1008 : : _M_assign_aux(_InputIterator __first, _InputIterator __last,
1009 : : std::input_iterator_tag);
1010 : :
1011 : : // Called by the second assign_dispatch above
1012 : : template<typename _ForwardIterator>
1013 : : void
1014 : : _M_assign_aux(_ForwardIterator __first, _ForwardIterator __last,
1015 : : std::forward_iterator_tag);
1016 : :
1017 : : // Called by assign(n,t), and the range assign when it turns out
1018 : : // to be the same thing.
1019 : : void
1020 : : _M_fill_assign(size_type __n, const value_type& __val);
1021 : :
1022 : :
1023 : : // Internal insert functions follow.
1024 : :
1025 : : // Called by the range insert to implement [23.1.1]/9
1026 : :
1027 : : // _GLIBCXX_RESOLVE_LIB_DEFECTS
1028 : : // 438. Ambiguity in the "do the right thing" clause
1029 : : template<typename _Integer>
1030 : : void
1031 : : _M_insert_dispatch(iterator __pos, _Integer __n, _Integer __val,
1032 : : __true_type)
1033 : : { _M_fill_insert(__pos, __n, __val); }
1034 : :
1035 : : // Called by the range insert to implement [23.1.1]/9
1036 : : template<typename _InputIterator>
1037 : : void
1038 : : _M_insert_dispatch(iterator __pos, _InputIterator __first,
1039 : : _InputIterator __last, __false_type)
1040 : : {
1041 : : typedef typename std::iterator_traits<_InputIterator>::
1042 : : iterator_category _IterCategory;
1043 : : _M_range_insert(__pos, __first, __last, _IterCategory());
1044 : : }
1045 : :
1046 : : // Called by the second insert_dispatch above
1047 : : template<typename _InputIterator>
1048 : : void
1049 : : _M_range_insert(iterator __pos, _InputIterator __first,
1050 : : _InputIterator __last, std::input_iterator_tag);
1051 : :
1052 : : // Called by the second insert_dispatch above
1053 : : template<typename _ForwardIterator>
1054 : : void
1055 : : _M_range_insert(iterator __pos, _ForwardIterator __first,
1056 : : _ForwardIterator __last, std::forward_iterator_tag);
1057 : :
1058 : : // Called by insert(p,n,x), and the range insert when it turns out to be
1059 : : // the same thing.
1060 : : void
1061 : : _M_fill_insert(iterator __pos, size_type __n, const value_type& __x);
1062 : :
1063 : : // Called by insert(p,x)
1064 : : #ifndef __GXX_EXPERIMENTAL_CXX0X__
1065 : : void
1066 : : _M_insert_aux(iterator __position, const value_type& __x);
1067 : : #else
1068 : : template<typename... _Args>
1069 : : void
1070 : : _M_insert_aux(iterator __position, _Args&&... __args);
1071 : : #endif
1072 : :
1073 : : // Called by the latter.
1074 : : size_type
1075 : 0 : _M_check_len(size_type __n, const char* __s) const
1076 : : {
1077 [ - + ][ - + ]: 14732 : if (max_size() - size() < __n)
[ - + ][ - + ]
[ - + ][ # # ]
[ - + ]
1078 : 0 : __throw_length_error(__N(__s));
1079 : :
1080 : 29464 : const size_type __len = size() + std::max(size(), __n);
1081 [ + - ][ - + ]: 14732 : return (__len < size() || __len > max_size()) ? max_size() : __len;
[ + - ][ - + ]
[ + - ][ - + ]
[ + - ][ - + ]
[ + - ][ - + ]
[ # # ][ # # ]
[ + - ][ - + ]
1082 : : }
1083 : :
1084 : : // Internal erase functions follow.
1085 : :
1086 : : // Called by erase(q1,q2), clear(), resize(), _M_fill_assign,
1087 : : // _M_assign_aux.
1088 : : void
1089 : : _M_erase_at_end(pointer __pos)
1090 : : {
1091 : 2044 : std::_Destroy(__pos, this->_M_impl._M_finish, _M_get_Tp_allocator());
1092 : 1958 : this->_M_impl._M_finish = __pos;
1093 : : }
1094 : : };
1095 : :
1096 : :
1097 : : /**
1098 : : * @brief Vector equality comparison.
1099 : : * @param x A %vector.
1100 : : * @param y A %vector of the same type as @a x.
1101 : : * @return True iff the size and elements of the vectors are equal.
1102 : : *
1103 : : * This is an equivalence relation. It is linear in the size of the
1104 : : * vectors. Vectors are considered equivalent if their sizes are equal,
1105 : : * and if corresponding elements compare equal.
1106 : : */
1107 : : template<typename _Tp, typename _Alloc>
1108 : : inline bool
1109 : : operator==(const vector<_Tp, _Alloc>& __x, const vector<_Tp, _Alloc>& __y)
1110 : : { return (__x.size() == __y.size()
1111 : : && std::equal(__x.begin(), __x.end(), __y.begin())); }
1112 : :
1113 : : /**
1114 : : * @brief Vector ordering relation.
1115 : : * @param x A %vector.
1116 : : * @param y A %vector of the same type as @a x.
1117 : : * @return True iff @a x is lexicographically less than @a y.
1118 : : *
1119 : : * This is a total ordering relation. It is linear in the size of the
1120 : : * vectors. The elements must be comparable with @c <.
1121 : : *
1122 : : * See std::lexicographical_compare() for how the determination is made.
1123 : : */
1124 : : template<typename _Tp, typename _Alloc>
1125 : : inline bool
1126 : : operator<(const vector<_Tp, _Alloc>& __x, const vector<_Tp, _Alloc>& __y)
1127 : : { return std::lexicographical_compare(__x.begin(), __x.end(),
1128 : : __y.begin(), __y.end()); }
1129 : :
1130 : : /// Based on operator==
1131 : : template<typename _Tp, typename _Alloc>
1132 : : inline bool
1133 : : operator!=(const vector<_Tp, _Alloc>& __x, const vector<_Tp, _Alloc>& __y)
1134 : : { return !(__x == __y); }
1135 : :
1136 : : /// Based on operator<
1137 : : template<typename _Tp, typename _Alloc>
1138 : : inline bool
1139 : : operator>(const vector<_Tp, _Alloc>& __x, const vector<_Tp, _Alloc>& __y)
1140 : : { return __y < __x; }
1141 : :
1142 : : /// Based on operator<
1143 : : template<typename _Tp, typename _Alloc>
1144 : : inline bool
1145 : : operator<=(const vector<_Tp, _Alloc>& __x, const vector<_Tp, _Alloc>& __y)
1146 : : { return !(__y < __x); }
1147 : :
1148 : : /// Based on operator<
1149 : : template<typename _Tp, typename _Alloc>
1150 : : inline bool
1151 : : operator>=(const vector<_Tp, _Alloc>& __x, const vector<_Tp, _Alloc>& __y)
1152 : : { return !(__x < __y); }
1153 : :
1154 : : /// See std::vector::swap().
1155 : : template<typename _Tp, typename _Alloc>
1156 : : inline void
1157 : : swap(vector<_Tp, _Alloc>& __x, vector<_Tp, _Alloc>& __y)
1158 : : { __x.swap(__y); }
1159 : :
1160 : : #ifdef __GXX_EXPERIMENTAL_CXX0X__
1161 : : template<typename _Tp, typename _Alloc>
1162 : : inline void
1163 : : swap(vector<_Tp, _Alloc>&& __x, vector<_Tp, _Alloc>& __y)
1164 : : { __x.swap(__y); }
1165 : :
1166 : : template<typename _Tp, typename _Alloc>
1167 : : inline void
1168 : : swap(vector<_Tp, _Alloc>& __x, vector<_Tp, _Alloc>&& __y)
1169 : : { __x.swap(__y); }
1170 : : #endif
1171 : :
1172 : : _GLIBCXX_END_NESTED_NAMESPACE
1173 : :
1174 : : #endif /* _STL_VECTOR_H */
|
