Branch data Line data Source code
1 : : // Vector implementation -*- C++ -*-
2 : :
3 : : // Copyright (C) 2001-2015 Free Software Foundation, Inc.
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 3, 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 : : // Under Section 7 of GPL version 3, you are granted additional
17 : : // permissions described in the GCC Runtime Library Exception, version
18 : : // 3.1, as published by the Free Software Foundation.
19 : :
20 : : // You should have received a copy of the GNU General Public License and
21 : : // a copy of the GCC Runtime Library Exception along with this program;
22 : : // see the files COPYING3 and COPYING.RUNTIME respectively. If not, see
23 : : // <http://www.gnu.org/licenses/>.
24 : :
25 : : /*
26 : : *
27 : : * Copyright (c) 1994
28 : : * Hewlett-Packard Company
29 : : *
30 : : * Permission to use, copy, modify, distribute and sell this software
31 : : * and its documentation for any purpose is hereby granted without fee,
32 : : * provided that the above copyright notice appear in all copies and
33 : : * that both that copyright notice and this permission notice appear
34 : : * in supporting documentation. Hewlett-Packard Company makes no
35 : : * representations about the suitability of this software for any
36 : : * purpose. It is provided "as is" without express or implied warranty.
37 : : *
38 : : *
39 : : * Copyright (c) 1996
40 : : * Silicon Graphics Computer Systems, Inc.
41 : : *
42 : : * Permission to use, copy, modify, distribute and sell this software
43 : : * and its documentation for any purpose is hereby granted without fee,
44 : : * provided that the above copyright notice appear in all copies and
45 : : * that both that copyright notice and this permission notice appear
46 : : * in supporting documentation. Silicon Graphics makes no
47 : : * representations about the suitability of this software for any
48 : : * purpose. It is provided "as is" without express or implied warranty.
49 : : */
50 : :
51 : : /** @file bits/stl_vector.h
52 : : * This is an internal header file, included by other library headers.
53 : : * Do not attempt to use it directly. @headername{vector}
54 : : */
55 : :
56 : : #ifndef _STL_VECTOR_H
57 : : #define _STL_VECTOR_H 1
58 : :
59 : : #include <bits/stl_iterator_base_funcs.h>
60 : : #include <bits/functexcept.h>
61 : : #include <bits/concept_check.h>
62 : : #if __cplusplus >= 201103L
63 : : #include <initializer_list>
64 : : #endif
65 : :
66 : : namespace std _GLIBCXX_VISIBILITY(default)
67 : : {
68 : : _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
69 : :
70 : : /// See bits/stl_deque.h's _Deque_base for an explanation.
71 : : template<typename _Tp, typename _Alloc>
72 : : struct _Vector_base
73 : : {
74 : : typedef typename __gnu_cxx::__alloc_traits<_Alloc>::template
75 : : rebind<_Tp>::other _Tp_alloc_type;
76 : : typedef typename __gnu_cxx::__alloc_traits<_Tp_alloc_type>::pointer
77 : : pointer;
78 : :
79 : 5 : struct _Vector_impl
80 : : : public _Tp_alloc_type
81 : : {
82 : : pointer _M_start;
83 : : pointer _M_finish;
84 : : pointer _M_end_of_storage;
85 : :
86 : : _Vector_impl()
87 : 4 : : _Tp_alloc_type(), _M_start(), _M_finish(), _M_end_of_storage()
88 : : { }
89 : :
90 : : _Vector_impl(_Tp_alloc_type const& __a) _GLIBCXX_NOEXCEPT
91 : 1 : : _Tp_alloc_type(__a), _M_start(), _M_finish(), _M_end_of_storage()
92 : : { }
93 : :
94 : : #if __cplusplus >= 201103L
95 : : _Vector_impl(_Tp_alloc_type&& __a) noexcept
96 : : : _Tp_alloc_type(std::move(__a)),
97 : : _M_start(), _M_finish(), _M_end_of_storage()
98 : : { }
99 : : #endif
100 : :
101 : : void _M_swap_data(_Vector_impl& __x) _GLIBCXX_NOEXCEPT
102 : : {
103 : : std::swap(_M_start, __x._M_start);
104 : : std::swap(_M_finish, __x._M_finish);
105 : : std::swap(_M_end_of_storage, __x._M_end_of_storage);
106 : : }
107 : : };
108 : :
109 : : public:
110 : : typedef _Alloc allocator_type;
111 : :
112 : : _Tp_alloc_type&
113 : : _M_get_Tp_allocator() _GLIBCXX_NOEXCEPT
114 : 0 : { return *static_cast<_Tp_alloc_type*>(&this->_M_impl); }
115 : :
116 : : const _Tp_alloc_type&
117 : : _M_get_Tp_allocator() const _GLIBCXX_NOEXCEPT
118 : : { return *static_cast<const _Tp_alloc_type*>(&this->_M_impl); }
119 : :
120 : : allocator_type
121 : : get_allocator() const _GLIBCXX_NOEXCEPT
122 : : { return allocator_type(_M_get_Tp_allocator()); }
123 : :
124 : : _Vector_base()
125 : : : _M_impl() { }
126 : :
127 : : _Vector_base(const allocator_type& __a) _GLIBCXX_NOEXCEPT
128 : : : _M_impl(__a) { }
129 : :
130 : : _Vector_base(size_t __n)
131 : : : _M_impl()
132 : : { _M_create_storage(__n); }
133 : :
134 : : _Vector_base(size_t __n, const allocator_type& __a)
135 : : : _M_impl(__a)
136 : : { _M_create_storage(__n); }
137 : :
138 : : #if __cplusplus >= 201103L
139 : : _Vector_base(_Tp_alloc_type&& __a) noexcept
140 : : : _M_impl(std::move(__a)) { }
141 : :
142 : : _Vector_base(_Vector_base&& __x) noexcept
143 : : : _M_impl(std::move(__x._M_get_Tp_allocator()))
144 : : { this->_M_impl._M_swap_data(__x._M_impl); }
145 : :
146 : : _Vector_base(_Vector_base&& __x, const allocator_type& __a)
147 : : : _M_impl(__a)
148 : : {
149 : : if (__x.get_allocator() == __a)
150 : : this->_M_impl._M_swap_data(__x._M_impl);
151 : : else
152 : : {
153 : : size_t __n = __x._M_impl._M_finish - __x._M_impl._M_start;
154 : : _M_create_storage(__n);
155 : : }
156 : : }
157 : : #endif
158 : :
159 : : ~_Vector_base() _GLIBCXX_NOEXCEPT
160 : : { _M_deallocate(this->_M_impl._M_start, this->_M_impl._M_end_of_storage
161 : 10 : - this->_M_impl._M_start); }
162 : :
163 : : public:
164 : : _Vector_impl _M_impl;
165 : :
166 : : pointer
167 : 10 : _M_allocate(size_t __n)
168 : : {
169 : : typedef __gnu_cxx::__alloc_traits<_Tp_alloc_type> _Tr;
170 [ + - ]: 5 : return __n != 0 ? _Tr::allocate(_M_impl, __n) : pointer();
171 : : }
172 : :
173 : : void
174 : : _M_deallocate(pointer __p, size_t __n)
175 : : {
176 : : typedef __gnu_cxx::__alloc_traits<_Tp_alloc_type> _Tr;
177 [ + + ][ + + ]: 9 : if (__p)
[ # # ][ + - ]
[ # # ]
178 : : _Tr::deallocate(_M_impl, __p, __n);
179 : : }
180 : :
181 : : private:
182 : : void
183 : : _M_create_storage(size_t __n)
184 : : {
185 : 1 : this->_M_impl._M_start = this->_M_allocate(__n);
186 : 1 : this->_M_impl._M_finish = this->_M_impl._M_start;
187 : 1 : this->_M_impl._M_end_of_storage = this->_M_impl._M_start + __n;
188 : : }
189 : : };
190 : :
191 : :
192 : : /**
193 : : * @brief A standard container which offers fixed time access to
194 : : * individual elements in any order.
195 : : *
196 : : * @ingroup sequences
197 : : *
198 : : * @tparam _Tp Type of element.
199 : : * @tparam _Alloc Allocator type, defaults to allocator<_Tp>.
200 : : *
201 : : * Meets the requirements of a <a href="tables.html#65">container</a>, a
202 : : * <a href="tables.html#66">reversible container</a>, and a
203 : : * <a href="tables.html#67">sequence</a>, including the
204 : : * <a href="tables.html#68">optional sequence requirements</a> with the
205 : : * %exception of @c push_front and @c pop_front.
206 : : *
207 : : * In some terminology a %vector can be described as a dynamic
208 : : * C-style array, it offers fast and efficient access to individual
209 : : * elements in any order and saves the user from worrying about
210 : : * memory and size allocation. Subscripting ( @c [] ) access is
211 : : * also provided as with C-style arrays.
212 : : */
213 : : template<typename _Tp, typename _Alloc = std::allocator<_Tp> >
214 : : class vector : protected _Vector_base<_Tp, _Alloc>
215 : : {
216 : : // Concept requirements.
217 : : typedef typename _Alloc::value_type _Alloc_value_type;
218 : : __glibcxx_class_requires(_Tp, _SGIAssignableConcept)
219 : : __glibcxx_class_requires2(_Tp, _Alloc_value_type, _SameTypeConcept)
220 : :
221 : : typedef _Vector_base<_Tp, _Alloc> _Base;
222 : : typedef typename _Base::_Tp_alloc_type _Tp_alloc_type;
223 : : typedef __gnu_cxx::__alloc_traits<_Tp_alloc_type> _Alloc_traits;
224 : :
225 : : public:
226 : : typedef _Tp value_type;
227 : : typedef typename _Base::pointer pointer;
228 : : typedef typename _Alloc_traits::const_pointer const_pointer;
229 : : typedef typename _Alloc_traits::reference reference;
230 : : typedef typename _Alloc_traits::const_reference const_reference;
231 : : typedef __gnu_cxx::__normal_iterator<pointer, vector> iterator;
232 : : typedef __gnu_cxx::__normal_iterator<const_pointer, vector>
233 : : const_iterator;
234 : : typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
235 : : typedef std::reverse_iterator<iterator> reverse_iterator;
236 : : typedef size_t size_type;
237 : : typedef ptrdiff_t difference_type;
238 : : typedef _Alloc allocator_type;
239 : :
240 : : protected:
241 : : using _Base::_M_allocate;
242 : : using _Base::_M_deallocate;
243 : : using _Base::_M_impl;
244 : : using _Base::_M_get_Tp_allocator;
245 : :
246 : : public:
247 : : // [23.2.4.1] construct/copy/destroy
248 : : // (assign() and get_allocator() are also listed in this section)
249 : :
250 : : /**
251 : : * @brief Creates a %vector with no elements.
252 : : */
253 : : vector()
254 : : #if __cplusplus >= 201103L
255 : : noexcept(is_nothrow_default_constructible<_Alloc>::value)
256 : : #endif
257 : : : _Base() { }
258 : :
259 : : /**
260 : : * @brief Creates a %vector with no elements.
261 : : * @param __a An allocator object.
262 : : */
263 : : explicit
264 : : vector(const allocator_type& __a) _GLIBCXX_NOEXCEPT
265 : : : _Base(__a) { }
266 : :
267 : : #if __cplusplus >= 201103L
268 : : /**
269 : : * @brief Creates a %vector with default constructed elements.
270 : : * @param __n The number of elements to initially create.
271 : : * @param __a An allocator.
272 : : *
273 : : * This constructor fills the %vector with @a __n default
274 : : * constructed elements.
275 : : */
276 : : explicit
277 : : vector(size_type __n, const allocator_type& __a = allocator_type())
278 : : : _Base(__n, __a)
279 : : { _M_default_initialize(__n); }
280 : :
281 : : /**
282 : : * @brief Creates a %vector with copies of an exemplar element.
283 : : * @param __n The number of elements to initially create.
284 : : * @param __value An element to copy.
285 : : * @param __a An allocator.
286 : : *
287 : : * This constructor fills the %vector with @a __n copies of @a __value.
288 : : */
289 : 0 : vector(size_type __n, const value_type& __value,
290 : : const allocator_type& __a = allocator_type())
291 : : : _Base(__n, __a)
292 : 0 : { _M_fill_initialize(__n, __value); }
293 : : #else
294 : : /**
295 : : * @brief Creates a %vector with copies of an exemplar element.
296 : : * @param __n The number of elements to initially create.
297 : : * @param __value An element to copy.
298 : : * @param __a An allocator.
299 : : *
300 : : * This constructor fills the %vector with @a __n copies of @a __value.
301 : : */
302 : : explicit
303 : : vector(size_type __n, const value_type& __value = value_type(),
304 : : const allocator_type& __a = allocator_type())
305 : : : _Base(__n, __a)
306 : : { _M_fill_initialize(__n, __value); }
307 : : #endif
308 : :
309 : : /**
310 : : * @brief %Vector copy constructor.
311 : : * @param __x A %vector of identical element and allocator types.
312 : : *
313 : : * The newly-created %vector uses a copy of the allocation
314 : : * object used by @a __x. All the elements of @a __x are copied,
315 : : * but any extra memory in
316 : : * @a __x (for fast expansion) will not be copied.
317 : : */
318 : 1 : vector(const vector& __x)
319 : : : _Base(__x.size(),
320 : : _Alloc_traits::_S_select_on_copy(__x._M_get_Tp_allocator()))
321 : 1 : { this->_M_impl._M_finish =
322 : : std::__uninitialized_copy_a(__x.begin(), __x.end(),
323 : : this->_M_impl._M_start,
324 : : _M_get_Tp_allocator());
325 : 1 : }
326 : :
327 : : #if __cplusplus >= 201103L
328 : : /**
329 : : * @brief %Vector move constructor.
330 : : * @param __x A %vector of identical element and allocator types.
331 : : *
332 : : * The newly-created %vector contains the exact contents of @a __x.
333 : : * The contents of @a __x are a valid, but unspecified %vector.
334 : : */
335 : : vector(vector&& __x) noexcept
336 : : : _Base(std::move(__x)) { }
337 : :
338 : : /// Copy constructor with alternative allocator
339 : : vector(const vector& __x, const allocator_type& __a)
340 : : : _Base(__x.size(), __a)
341 : : { this->_M_impl._M_finish =
342 : : std::__uninitialized_copy_a(__x.begin(), __x.end(),
343 : : this->_M_impl._M_start,
344 : : _M_get_Tp_allocator());
345 : : }
346 : :
347 : : /// Move constructor with alternative allocator
348 : : vector(vector&& __rv, const allocator_type& __m)
349 : : noexcept(_Alloc_traits::_S_always_equal())
350 : : : _Base(std::move(__rv), __m)
351 : : {
352 : : if (__rv.get_allocator() != __m)
353 : : {
354 : : this->_M_impl._M_finish =
355 : : std::__uninitialized_move_a(__rv.begin(), __rv.end(),
356 : : this->_M_impl._M_start,
357 : : _M_get_Tp_allocator());
358 : : __rv.clear();
359 : : }
360 : : }
361 : :
362 : : /**
363 : : * @brief Builds a %vector from an initializer list.
364 : : * @param __l An initializer_list.
365 : : * @param __a An allocator.
366 : : *
367 : : * Create a %vector consisting of copies of the elements in the
368 : : * initializer_list @a __l.
369 : : *
370 : : * This will call the element type's copy constructor N times
371 : : * (where N is @a __l.size()) and do no memory reallocation.
372 : : */
373 : : vector(initializer_list<value_type> __l,
374 : : const allocator_type& __a = allocator_type())
375 : : : _Base(__a)
376 : : {
377 : : _M_range_initialize(__l.begin(), __l.end(),
378 : : random_access_iterator_tag());
379 : : }
380 : : #endif
381 : :
382 : : /**
383 : : * @brief Builds a %vector from a range.
384 : : * @param __first An input iterator.
385 : : * @param __last An input iterator.
386 : : * @param __a An allocator.
387 : : *
388 : : * Create a %vector consisting of copies of the elements from
389 : : * [first,last).
390 : : *
391 : : * If the iterators are forward, bidirectional, or
392 : : * random-access, then this will call the elements' copy
393 : : * constructor N times (where N is distance(first,last)) and do
394 : : * no memory reallocation. But if only input iterators are
395 : : * used, then this will do at most 2N calls to the copy
396 : : * constructor, and logN memory reallocations.
397 : : */
398 : : #if __cplusplus >= 201103L
399 : : template<typename _InputIterator,
400 : : typename = std::_RequireInputIter<_InputIterator>>
401 : : vector(_InputIterator __first, _InputIterator __last,
402 : : const allocator_type& __a = allocator_type())
403 : : : _Base(__a)
404 : : { _M_initialize_dispatch(__first, __last, __false_type()); }
405 : : #else
406 : : template<typename _InputIterator>
407 : : vector(_InputIterator __first, _InputIterator __last,
408 : : const allocator_type& __a = allocator_type())
409 : : : _Base(__a)
410 : : {
411 : : // Check whether it's an integral type. If so, it's not an iterator.
412 : : typedef typename std::__is_integer<_InputIterator>::__type _Integral;
413 : : _M_initialize_dispatch(__first, __last, _Integral());
414 : : }
415 : : #endif
416 : :
417 : : /**
418 : : * The dtor only erases the elements, and note that if the
419 : : * elements themselves are pointers, the pointed-to memory is
420 : : * not touched in any way. Managing the pointer is the user's
421 : : * responsibility.
422 : : */
423 : 5 : ~vector() _GLIBCXX_NOEXCEPT
424 : 5 : { std::_Destroy(this->_M_impl._M_start, this->_M_impl._M_finish,
425 : 5 : _M_get_Tp_allocator()); }
426 : :
427 : : /**
428 : : * @brief %Vector assignment operator.
429 : : * @param __x A %vector of identical element and allocator types.
430 : : *
431 : : * All the elements of @a __x are copied, but any extra memory in
432 : : * @a __x (for fast expansion) will not be copied. Unlike the
433 : : * copy constructor, the allocator object is not copied.
434 : : */
435 : : vector&
436 : : operator=(const vector& __x);
437 : :
438 : : #if __cplusplus >= 201103L
439 : : /**
440 : : * @brief %Vector move assignment operator.
441 : : * @param __x A %vector of identical element and allocator types.
442 : : *
443 : : * The contents of @a __x are moved into this %vector (without copying,
444 : : * if the allocators permit it).
445 : : * @a __x is a valid, but unspecified %vector.
446 : : */
447 : : vector&
448 : : operator=(vector&& __x) noexcept(_Alloc_traits::_S_nothrow_move())
449 : : {
450 : : constexpr bool __move_storage =
451 : : _Alloc_traits::_S_propagate_on_move_assign()
452 : : || _Alloc_traits::_S_always_equal();
453 : : _M_move_assign(std::move(__x),
454 : : integral_constant<bool, __move_storage>());
455 : : return *this;
456 : : }
457 : :
458 : : /**
459 : : * @brief %Vector list assignment operator.
460 : : * @param __l An initializer_list.
461 : : *
462 : : * This function fills a %vector with copies of the elements in the
463 : : * initializer list @a __l.
464 : : *
465 : : * Note that the assignment completely changes the %vector and
466 : : * that the resulting %vector's size is the same as the number
467 : : * of elements assigned. Old data may be lost.
468 : : */
469 : : vector&
470 : : operator=(initializer_list<value_type> __l)
471 : : {
472 : : this->assign(__l.begin(), __l.end());
473 : : return *this;
474 : : }
475 : : #endif
476 : :
477 : : /**
478 : : * @brief Assigns a given value to a %vector.
479 : : * @param __n Number of elements to be assigned.
480 : : * @param __val Value to be assigned.
481 : : *
482 : : * This function fills a %vector with @a __n copies of the given
483 : : * value. Note that the assignment completely changes the
484 : : * %vector and that the resulting %vector's size is the same as
485 : : * the number of elements assigned. Old data may be lost.
486 : : */
487 : : void
488 : : assign(size_type __n, const value_type& __val)
489 [ # # ]: 0 : { _M_fill_assign(__n, __val); }
490 : :
491 : : /**
492 : : * @brief Assigns a range to a %vector.
493 : : * @param __first An input iterator.
494 : : * @param __last An input iterator.
495 : : *
496 : : * This function fills a %vector with copies of the elements in the
497 : : * range [__first,__last).
498 : : *
499 : : * Note that the assignment completely changes the %vector and
500 : : * that the resulting %vector's size is the same as the number
501 : : * of elements assigned. Old data may be lost.
502 : : */
503 : : #if __cplusplus >= 201103L
504 : : template<typename _InputIterator,
505 : : typename = std::_RequireInputIter<_InputIterator>>
506 : : void
507 : : assign(_InputIterator __first, _InputIterator __last)
508 : : { _M_assign_dispatch(__first, __last, __false_type()); }
509 : : #else
510 : : template<typename _InputIterator>
511 : : void
512 : : assign(_InputIterator __first, _InputIterator __last)
513 : : {
514 : : // Check whether it's an integral type. If so, it's not an iterator.
515 : : typedef typename std::__is_integer<_InputIterator>::__type _Integral;
516 : : _M_assign_dispatch(__first, __last, _Integral());
517 : : }
518 : : #endif
519 : :
520 : : #if __cplusplus >= 201103L
521 : : /**
522 : : * @brief Assigns an initializer list to a %vector.
523 : : * @param __l An initializer_list.
524 : : *
525 : : * This function fills a %vector with copies of the elements in the
526 : : * initializer list @a __l.
527 : : *
528 : : * Note that the assignment completely changes the %vector and
529 : : * that the resulting %vector's size is the same as the number
530 : : * of elements assigned. Old data may be lost.
531 : : */
532 : : void
533 : : assign(initializer_list<value_type> __l)
534 : : { this->assign(__l.begin(), __l.end()); }
535 : : #endif
536 : :
537 : : /// Get a copy of the memory allocation object.
538 : : using _Base::get_allocator;
539 : :
540 : : // iterators
541 : : /**
542 : : * Returns a read/write iterator that points to the first
543 : : * element in the %vector. Iteration is done in ordinary
544 : : * element order.
545 : : */
546 : : iterator
547 : : begin() _GLIBCXX_NOEXCEPT
548 : : { return iterator(this->_M_impl._M_start); }
549 : :
550 : : /**
551 : : * Returns a read-only (constant) iterator that points to the
552 : : * first element in the %vector. Iteration is done in ordinary
553 : : * element order.
554 : : */
555 : : const_iterator
556 : : begin() const _GLIBCXX_NOEXCEPT
557 : : { return const_iterator(this->_M_impl._M_start); }
558 : :
559 : : /**
560 : : * Returns a read/write iterator that points one past the last
561 : : * element in the %vector. Iteration is done in ordinary
562 : : * element order.
563 : : */
564 : : iterator
565 : : end() _GLIBCXX_NOEXCEPT
566 : : { return iterator(this->_M_impl._M_finish); }
567 : :
568 : : /**
569 : : * Returns a read-only (constant) iterator that points one past
570 : : * the last element in the %vector. Iteration is done in
571 : : * ordinary element order.
572 : : */
573 : : const_iterator
574 : : end() const _GLIBCXX_NOEXCEPT
575 : : { return const_iterator(this->_M_impl._M_finish); }
576 : :
577 : : /**
578 : : * Returns a read/write reverse iterator that points to the
579 : : * last element in the %vector. Iteration is done in reverse
580 : : * element order.
581 : : */
582 : : reverse_iterator
583 : : rbegin() _GLIBCXX_NOEXCEPT
584 : : { return reverse_iterator(end()); }
585 : :
586 : : /**
587 : : * Returns a read-only (constant) reverse iterator that points
588 : : * to the last element in the %vector. Iteration is done in
589 : : * reverse element order.
590 : : */
591 : : const_reverse_iterator
592 : : rbegin() const _GLIBCXX_NOEXCEPT
593 : : { return const_reverse_iterator(end()); }
594 : :
595 : : /**
596 : : * Returns a read/write reverse iterator that points to one
597 : : * before the first element in the %vector. Iteration is done
598 : : * in reverse element order.
599 : : */
600 : : reverse_iterator
601 : : rend() _GLIBCXX_NOEXCEPT
602 : : { return reverse_iterator(begin()); }
603 : :
604 : : /**
605 : : * Returns a read-only (constant) reverse iterator that points
606 : : * to one before the first element in the %vector. Iteration
607 : : * is done in reverse element order.
608 : : */
609 : : const_reverse_iterator
610 : : rend() const _GLIBCXX_NOEXCEPT
611 : : { return const_reverse_iterator(begin()); }
612 : :
613 : : #if __cplusplus >= 201103L
614 : : /**
615 : : * Returns a read-only (constant) iterator that points to the
616 : : * first element in the %vector. Iteration is done in ordinary
617 : : * element order.
618 : : */
619 : : const_iterator
620 : : cbegin() const noexcept
621 : : { return const_iterator(this->_M_impl._M_start); }
622 : :
623 : : /**
624 : : * Returns a read-only (constant) iterator that points one past
625 : : * the last element in the %vector. Iteration is done in
626 : : * ordinary element order.
627 : : */
628 : : const_iterator
629 : : cend() const noexcept
630 : : { return const_iterator(this->_M_impl._M_finish); }
631 : :
632 : : /**
633 : : * Returns a read-only (constant) reverse iterator that points
634 : : * to the last element in the %vector. Iteration is done in
635 : : * reverse element order.
636 : : */
637 : : const_reverse_iterator
638 : : crbegin() const noexcept
639 : : { return const_reverse_iterator(end()); }
640 : :
641 : : /**
642 : : * Returns a read-only (constant) reverse iterator that points
643 : : * to one before the first element in the %vector. Iteration
644 : : * is done in reverse element order.
645 : : */
646 : : const_reverse_iterator
647 : : crend() const noexcept
648 : : { return const_reverse_iterator(begin()); }
649 : : #endif
650 : :
651 : : // [23.2.4.2] capacity
652 : : /** Returns the number of elements in the %vector. */
653 : : size_type
654 : : size() const _GLIBCXX_NOEXCEPT
655 : 9 : { return size_type(this->_M_impl._M_finish - this->_M_impl._M_start); }
656 : :
657 : : /** Returns the size() of the largest possible %vector. */
658 : : size_type
659 : : max_size() const _GLIBCXX_NOEXCEPT
660 : : { return _Alloc_traits::max_size(_M_get_Tp_allocator()); }
661 : :
662 : : #if __cplusplus >= 201103L
663 : : /**
664 : : * @brief Resizes the %vector to the specified number of elements.
665 : : * @param __new_size Number of elements the %vector should contain.
666 : : *
667 : : * This function will %resize the %vector to the specified
668 : : * number of elements. If the number is smaller than the
669 : : * %vector's current size the %vector is truncated, otherwise
670 : : * default constructed elements are appended.
671 : : */
672 : : void
673 : : resize(size_type __new_size)
674 : : {
675 : : if (__new_size > size())
676 : : _M_default_append(__new_size - size());
677 : : else if (__new_size < size())
678 : : _M_erase_at_end(this->_M_impl._M_start + __new_size);
679 : : }
680 : :
681 : : /**
682 : : * @brief Resizes the %vector to the specified number of elements.
683 : : * @param __new_size Number of elements the %vector should contain.
684 : : * @param __x Data with which new elements should be populated.
685 : : *
686 : : * This function will %resize the %vector to the specified
687 : : * number of elements. If the number is smaller than the
688 : : * %vector's current size the %vector is truncated, otherwise
689 : : * the %vector is extended and new elements are populated with
690 : : * given data.
691 : : */
692 : : void
693 : : resize(size_type __new_size, const value_type& __x)
694 : : {
695 : : if (__new_size > size())
696 : : insert(end(), __new_size - size(), __x);
697 : : else if (__new_size < size())
698 : : _M_erase_at_end(this->_M_impl._M_start + __new_size);
699 : : }
700 : : #else
701 : : /**
702 : : * @brief Resizes the %vector to the specified number of elements.
703 : : * @param __new_size Number of elements the %vector should contain.
704 : : * @param __x Data with which new elements should be populated.
705 : : *
706 : : * This function will %resize the %vector to the specified
707 : : * number of elements. If the number is smaller than the
708 : : * %vector's current size the %vector is truncated, otherwise
709 : : * the %vector is extended and new elements are populated with
710 : : * given data.
711 : : */
712 : : void
713 : : resize(size_type __new_size, value_type __x = value_type())
714 : : {
715 : : if (__new_size > size())
716 : : insert(end(), __new_size - size(), __x);
717 : : else if (__new_size < size())
718 : : _M_erase_at_end(this->_M_impl._M_start + __new_size);
719 : : }
720 : : #endif
721 : :
722 : : #if __cplusplus >= 201103L
723 : : /** A non-binding request to reduce capacity() to size(). */
724 : : void
725 : : shrink_to_fit()
726 : : { _M_shrink_to_fit(); }
727 : : #endif
728 : :
729 : : /**
730 : : * Returns the total number of elements that the %vector can
731 : : * hold before needing to allocate more memory.
732 : : */
733 : : size_type
734 : : capacity() const _GLIBCXX_NOEXCEPT
735 : : { return size_type(this->_M_impl._M_end_of_storage
736 : 0 : - this->_M_impl._M_start); }
737 : :
738 : : /**
739 : : * Returns true if the %vector is empty. (Thus begin() would
740 : : * equal end().)
741 : : */
742 : : bool
743 : : empty() const _GLIBCXX_NOEXCEPT
744 : : { return begin() == end(); }
745 : :
746 : : /**
747 : : * @brief Attempt to preallocate enough memory for specified number of
748 : : * elements.
749 : : * @param __n Number of elements required.
750 : : * @throw std::length_error If @a n exceeds @c max_size().
751 : : *
752 : : * This function attempts to reserve enough memory for the
753 : : * %vector to hold the specified number of elements. If the
754 : : * number requested is more than max_size(), length_error is
755 : : * thrown.
756 : : *
757 : : * The advantage of this function is that if optimal code is a
758 : : * necessity and the user can determine the number of elements
759 : : * that will be required, the user can reserve the memory in
760 : : * %advance, and thus prevent a possible reallocation of memory
761 : : * and copying of %vector data.
762 : : */
763 : : void
764 : : reserve(size_type __n);
765 : :
766 : : // element access
767 : : /**
768 : : * @brief Subscript access to the data contained in the %vector.
769 : : * @param __n The index of the element for which data should be
770 : : * accessed.
771 : : * @return Read/write reference to data.
772 : : *
773 : : * This operator allows for easy, array-style, data access.
774 : : * Note that data access with this operator is unchecked and
775 : : * out_of_range lookups are not defined. (For checked lookups
776 : : * see at().)
777 : : */
778 : : reference
779 : : operator[](size_type __n) _GLIBCXX_NOEXCEPT
780 : : { return *(this->_M_impl._M_start + __n); }
781 : :
782 : : /**
783 : : * @brief Subscript access to the data contained in the %vector.
784 : : * @param __n The index of the element for which data should be
785 : : * accessed.
786 : : * @return Read-only (constant) reference to data.
787 : : *
788 : : * This operator allows for easy, array-style, data access.
789 : : * Note that data access with this operator is unchecked and
790 : : * out_of_range lookups are not defined. (For checked lookups
791 : : * see at().)
792 : : */
793 : : const_reference
794 : : operator[](size_type __n) const _GLIBCXX_NOEXCEPT
795 : : { return *(this->_M_impl._M_start + __n); }
796 : :
797 : : protected:
798 : : /// Safety check used only from at().
799 : : void
800 : : _M_range_check(size_type __n) const
801 : : {
802 : : if (__n >= this->size())
803 : : __throw_out_of_range_fmt(__N("vector::_M_range_check: __n "
804 : : "(which is %zu) >= this->size() "
805 : : "(which is %zu)"),
806 : : __n, this->size());
807 : : }
808 : :
809 : : public:
810 : : /**
811 : : * @brief Provides access to the data contained in the %vector.
812 : : * @param __n The index of the element for which data should be
813 : : * accessed.
814 : : * @return Read/write reference to data.
815 : : * @throw std::out_of_range If @a __n is an invalid index.
816 : : *
817 : : * This function provides for safer data access. The parameter
818 : : * is first checked that it is in the range of the vector. The
819 : : * function throws out_of_range if the check fails.
820 : : */
821 : : reference
822 : : at(size_type __n)
823 : : {
824 : : _M_range_check(__n);
825 : : return (*this)[__n];
826 : : }
827 : :
828 : : /**
829 : : * @brief Provides access to the data contained in the %vector.
830 : : * @param __n The index of the element for which data should be
831 : : * accessed.
832 : : * @return Read-only (constant) reference to data.
833 : : * @throw std::out_of_range If @a __n is an invalid index.
834 : : *
835 : : * This function provides for safer data access. The parameter
836 : : * is first checked that it is in the range of the vector. The
837 : : * function throws out_of_range if the check fails.
838 : : */
839 : : const_reference
840 : : at(size_type __n) const
841 : : {
842 : : _M_range_check(__n);
843 : : return (*this)[__n];
844 : : }
845 : :
846 : : /**
847 : : * Returns a read/write reference to the data at the first
848 : : * element of the %vector.
849 : : */
850 : : reference
851 : : front() _GLIBCXX_NOEXCEPT
852 : : { return *begin(); }
853 : :
854 : : /**
855 : : * Returns a read-only (constant) reference to the data at the first
856 : : * element of the %vector.
857 : : */
858 : : const_reference
859 : : front() const _GLIBCXX_NOEXCEPT
860 : : { return *begin(); }
861 : :
862 : : /**
863 : : * Returns a read/write reference to the data at the last
864 : : * element of the %vector.
865 : : */
866 : : reference
867 : : back() _GLIBCXX_NOEXCEPT
868 : : { return *(end() - 1); }
869 : :
870 : : /**
871 : : * Returns a read-only (constant) reference to the data at the
872 : : * last element of the %vector.
873 : : */
874 : : const_reference
875 : : back() const _GLIBCXX_NOEXCEPT
876 : : { return *(end() - 1); }
877 : :
878 : : // _GLIBCXX_RESOLVE_LIB_DEFECTS
879 : : // DR 464. Suggestion for new member functions in standard containers.
880 : : // data access
881 : : /**
882 : : * Returns a pointer such that [data(), data() + size()) is a valid
883 : : * range. For a non-empty %vector, data() == &front().
884 : : */
885 : : #if __cplusplus >= 201103L
886 : : _Tp*
887 : : #else
888 : : pointer
889 : : #endif
890 : : data() _GLIBCXX_NOEXCEPT
891 : : { return _M_data_ptr(this->_M_impl._M_start); }
892 : :
893 : : #if __cplusplus >= 201103L
894 : : const _Tp*
895 : : #else
896 : : const_pointer
897 : : #endif
898 : : data() const _GLIBCXX_NOEXCEPT
899 : : { return _M_data_ptr(this->_M_impl._M_start); }
900 : :
901 : : // [23.2.4.3] modifiers
902 : : /**
903 : : * @brief Add data to the end of the %vector.
904 : : * @param __x Data to be added.
905 : : *
906 : : * This is a typical stack operation. The function creates an
907 : : * element at the end of the %vector and assigns the given data
908 : : * to it. Due to the nature of a %vector this operation can be
909 : : * done in constant time if the %vector has preallocated space
910 : : * available.
911 : : */
912 : : void
913 : 0 : push_back(const value_type& __x)
914 : : {
915 [ # # ]: 0 : if (this->_M_impl._M_finish != this->_M_impl._M_end_of_storage)
916 : : {
917 : : _Alloc_traits::construct(this->_M_impl, this->_M_impl._M_finish,
918 : : __x);
919 : 0 : ++this->_M_impl._M_finish;
920 : : }
921 : : else
922 : : #if __cplusplus >= 201103L
923 : 0 : _M_emplace_back_aux(__x);
924 : : #else
925 : : _M_insert_aux(end(), __x);
926 : : #endif
927 : 0 : }
928 : :
929 : : #if __cplusplus >= 201103L
930 : : void
931 : : push_back(value_type&& __x)
932 [ + - ][ + - ]: 4 : { emplace_back(std::move(__x)); }
933 : :
934 : : template<typename... _Args>
935 : : void
936 : : emplace_back(_Args&&... __args);
937 : : #endif
938 : :
939 : : /**
940 : : * @brief Removes last element.
941 : : *
942 : : * This is a typical stack operation. It shrinks the %vector by one.
943 : : *
944 : : * Note that no data is returned, and if the last element's
945 : : * data is needed, it should be retrieved before pop_back() is
946 : : * called.
947 : : */
948 : : void
949 : : pop_back() _GLIBCXX_NOEXCEPT
950 : : {
951 : : --this->_M_impl._M_finish;
952 : : _Alloc_traits::destroy(this->_M_impl, this->_M_impl._M_finish);
953 : : }
954 : :
955 : : #if __cplusplus >= 201103L
956 : : /**
957 : : * @brief Inserts an object in %vector before specified iterator.
958 : : * @param __position A const_iterator into the %vector.
959 : : * @param __args Arguments.
960 : : * @return An iterator that points to the inserted data.
961 : : *
962 : : * This function will insert an object of type T constructed
963 : : * with T(std::forward<Args>(args)...) before the specified location.
964 : : * Note that this kind of operation could be expensive for a %vector
965 : : * and if it is frequently used the user should consider using
966 : : * std::list.
967 : : */
968 : : template<typename... _Args>
969 : : iterator
970 : : emplace(const_iterator __position, _Args&&... __args);
971 : :
972 : : /**
973 : : * @brief Inserts given value into %vector before specified iterator.
974 : : * @param __position A const_iterator into the %vector.
975 : : * @param __x Data to be inserted.
976 : : * @return An iterator that points to the inserted data.
977 : : *
978 : : * This function will insert a copy of the given value before
979 : : * the specified location. Note that this kind of operation
980 : : * could be expensive for a %vector and if it is frequently
981 : : * used the user should consider using std::list.
982 : : */
983 : : iterator
984 : : insert(const_iterator __position, const value_type& __x);
985 : : #else
986 : : /**
987 : : * @brief Inserts given value into %vector before specified iterator.
988 : : * @param __position An iterator into the %vector.
989 : : * @param __x Data to be inserted.
990 : : * @return An iterator that points to the inserted data.
991 : : *
992 : : * This function will insert a copy of the given value before
993 : : * the specified location. Note that this kind of operation
994 : : * could be expensive for a %vector and if it is frequently
995 : : * used the user should consider using std::list.
996 : : */
997 : : iterator
998 : : insert(iterator __position, const value_type& __x);
999 : : #endif
1000 : :
1001 : : #if __cplusplus >= 201103L
1002 : : /**
1003 : : * @brief Inserts given rvalue into %vector before specified iterator.
1004 : : * @param __position A const_iterator into the %vector.
1005 : : * @param __x Data to be inserted.
1006 : : * @return An iterator that points to the inserted data.
1007 : : *
1008 : : * This function will insert a copy of the given rvalue before
1009 : : * the specified location. Note that this kind of operation
1010 : : * could be expensive for a %vector and if it is frequently
1011 : : * used the user should consider using std::list.
1012 : : */
1013 : : iterator
1014 : : insert(const_iterator __position, value_type&& __x)
1015 : : { return emplace(__position, std::move(__x)); }
1016 : :
1017 : : /**
1018 : : * @brief Inserts an initializer_list into the %vector.
1019 : : * @param __position An iterator into the %vector.
1020 : : * @param __l An initializer_list.
1021 : : *
1022 : : * This function will insert copies of the data in the
1023 : : * initializer_list @a l into the %vector before the location
1024 : : * specified by @a position.
1025 : : *
1026 : : * Note that this kind of operation could be expensive for a
1027 : : * %vector and if it is frequently used the user should
1028 : : * consider using std::list.
1029 : : */
1030 : : iterator
1031 : : insert(const_iterator __position, initializer_list<value_type> __l)
1032 : : { return this->insert(__position, __l.begin(), __l.end()); }
1033 : : #endif
1034 : :
1035 : : #if __cplusplus >= 201103L
1036 : : /**
1037 : : * @brief Inserts a number of copies of given data into the %vector.
1038 : : * @param __position A const_iterator into the %vector.
1039 : : * @param __n Number of elements to be inserted.
1040 : : * @param __x Data to be inserted.
1041 : : * @return An iterator that points to the inserted data.
1042 : : *
1043 : : * This function will insert a specified number of copies of
1044 : : * the given data before the location specified by @a position.
1045 : : *
1046 : : * Note that this kind of operation could be expensive for a
1047 : : * %vector and if it is frequently used the user should
1048 : : * consider using std::list.
1049 : : */
1050 : : iterator
1051 : : insert(const_iterator __position, size_type __n, const value_type& __x)
1052 : : {
1053 : : difference_type __offset = __position - cbegin();
1054 : : _M_fill_insert(begin() + __offset, __n, __x);
1055 : : return begin() + __offset;
1056 : : }
1057 : : #else
1058 : : /**
1059 : : * @brief Inserts a number of copies of given data into the %vector.
1060 : : * @param __position An iterator into the %vector.
1061 : : * @param __n Number of elements to be inserted.
1062 : : * @param __x Data to be inserted.
1063 : : *
1064 : : * This function will insert a specified number of copies of
1065 : : * the given data before the location specified by @a position.
1066 : : *
1067 : : * Note that this kind of operation could be expensive for a
1068 : : * %vector and if it is frequently used the user should
1069 : : * consider using std::list.
1070 : : */
1071 : : void
1072 : : insert(iterator __position, size_type __n, const value_type& __x)
1073 : : { _M_fill_insert(__position, __n, __x); }
1074 : : #endif
1075 : :
1076 : : #if __cplusplus >= 201103L
1077 : : /**
1078 : : * @brief Inserts a range into the %vector.
1079 : : * @param __position A const_iterator into the %vector.
1080 : : * @param __first An input iterator.
1081 : : * @param __last An input iterator.
1082 : : * @return An iterator that points to the inserted data.
1083 : : *
1084 : : * This function will insert copies of the data in the range
1085 : : * [__first,__last) into the %vector before the location specified
1086 : : * by @a pos.
1087 : : *
1088 : : * Note that this kind of operation could be expensive for a
1089 : : * %vector and if it is frequently used the user should
1090 : : * consider using std::list.
1091 : : */
1092 : : template<typename _InputIterator,
1093 : : typename = std::_RequireInputIter<_InputIterator>>
1094 : : iterator
1095 : : insert(const_iterator __position, _InputIterator __first,
1096 : : _InputIterator __last)
1097 : : {
1098 : : difference_type __offset = __position - cbegin();
1099 : : _M_insert_dispatch(begin() + __offset,
1100 : : __first, __last, __false_type());
1101 : : return begin() + __offset;
1102 : : }
1103 : : #else
1104 : : /**
1105 : : * @brief Inserts a range into the %vector.
1106 : : * @param __position An iterator into the %vector.
1107 : : * @param __first An input iterator.
1108 : : * @param __last An input iterator.
1109 : : *
1110 : : * This function will insert copies of the data in the range
1111 : : * [__first,__last) into the %vector before the location specified
1112 : : * by @a pos.
1113 : : *
1114 : : * Note that this kind of operation could be expensive for a
1115 : : * %vector and if it is frequently used the user should
1116 : : * consider using std::list.
1117 : : */
1118 : : template<typename _InputIterator>
1119 : : void
1120 : : insert(iterator __position, _InputIterator __first,
1121 : : _InputIterator __last)
1122 : : {
1123 : : // Check whether it's an integral type. If so, it's not an iterator.
1124 : : typedef typename std::__is_integer<_InputIterator>::__type _Integral;
1125 : : _M_insert_dispatch(__position, __first, __last, _Integral());
1126 : : }
1127 : : #endif
1128 : :
1129 : : /**
1130 : : * @brief Remove element at given position.
1131 : : * @param __position Iterator pointing to element to be erased.
1132 : : * @return An iterator pointing to the next element (or end()).
1133 : : *
1134 : : * This function will erase the element at the given position and thus
1135 : : * shorten the %vector by one.
1136 : : *
1137 : : * Note This operation could be expensive and if it is
1138 : : * frequently used the user should consider using std::list.
1139 : : * The user is also cautioned that this function only erases
1140 : : * the element, and that if the element is itself a pointer,
1141 : : * the pointed-to memory is not touched in any way. Managing
1142 : : * the pointer is the user's responsibility.
1143 : : */
1144 : : iterator
1145 : : #if __cplusplus >= 201103L
1146 : : erase(const_iterator __position)
1147 : : { return _M_erase(begin() + (__position - cbegin())); }
1148 : : #else
1149 : : erase(iterator __position)
1150 : : { return _M_erase(__position); }
1151 : : #endif
1152 : :
1153 : : /**
1154 : : * @brief Remove a range of elements.
1155 : : * @param __first Iterator pointing to the first element to be erased.
1156 : : * @param __last Iterator pointing to one past the last element to be
1157 : : * erased.
1158 : : * @return An iterator pointing to the element pointed to by @a __last
1159 : : * prior to erasing (or end()).
1160 : : *
1161 : : * This function will erase the elements in the range
1162 : : * [__first,__last) and shorten the %vector accordingly.
1163 : : *
1164 : : * Note This operation could be expensive and if it is
1165 : : * frequently used the user should consider using std::list.
1166 : : * The user is also cautioned that this function only erases
1167 : : * the elements, and that if the elements themselves are
1168 : : * pointers, the pointed-to memory is not touched in any way.
1169 : : * Managing the pointer is the user's responsibility.
1170 : : */
1171 : : iterator
1172 : : #if __cplusplus >= 201103L
1173 : : erase(const_iterator __first, const_iterator __last)
1174 : : {
1175 : : const auto __beg = begin();
1176 : : const auto __cbeg = cbegin();
1177 : : return _M_erase(__beg + (__first - __cbeg), __beg + (__last - __cbeg));
1178 : : }
1179 : : #else
1180 : : erase(iterator __first, iterator __last)
1181 : : { return _M_erase(__first, __last); }
1182 : : #endif
1183 : :
1184 : : /**
1185 : : * @brief Swaps data with another %vector.
1186 : : * @param __x A %vector of the same element and allocator types.
1187 : : *
1188 : : * This exchanges the elements between two vectors in constant time.
1189 : : * (Three pointers, so it should be quite fast.)
1190 : : * Note that the global std::swap() function is specialized such that
1191 : : * std::swap(v1,v2) will feed to this function.
1192 : : */
1193 : : void
1194 : : swap(vector& __x)
1195 : : #if __cplusplus >= 201103L
1196 : : noexcept(_Alloc_traits::_S_nothrow_swap())
1197 : : #endif
1198 : : {
1199 : : this->_M_impl._M_swap_data(__x._M_impl);
1200 : : _Alloc_traits::_S_on_swap(_M_get_Tp_allocator(),
1201 : : __x._M_get_Tp_allocator());
1202 : : }
1203 : :
1204 : : /**
1205 : : * Erases all the elements. Note that this function only erases the
1206 : : * elements, and that if the elements themselves are pointers, the
1207 : : * pointed-to memory is not touched in any way. Managing the pointer is
1208 : : * the user's responsibility.
1209 : : */
1210 : : void
1211 : : clear() _GLIBCXX_NOEXCEPT
1212 : : { _M_erase_at_end(this->_M_impl._M_start); }
1213 : :
1214 : : protected:
1215 : : /**
1216 : : * Memory expansion handler. Uses the member allocation function to
1217 : : * obtain @a n bytes of memory, and then copies [first,last) into it.
1218 : : */
1219 : : template<typename _ForwardIterator>
1220 : : pointer
1221 : : _M_allocate_and_copy(size_type __n,
1222 : : _ForwardIterator __first, _ForwardIterator __last)
1223 : : {
1224 : 0 : pointer __result = this->_M_allocate(__n);
1225 : : __try
1226 : : {
1227 : : std::__uninitialized_copy_a(__first, __last, __result,
1228 : : _M_get_Tp_allocator());
1229 : : return __result;
1230 : : }
1231 : : __catch(...)
1232 : : {
1233 : : _M_deallocate(__result, __n);
1234 : : __throw_exception_again;
1235 : : }
1236 : : }
1237 : :
1238 : :
1239 : : // Internal constructor functions follow.
1240 : :
1241 : : // Called by the range constructor to implement [23.1.1]/9
1242 : :
1243 : : // _GLIBCXX_RESOLVE_LIB_DEFECTS
1244 : : // 438. Ambiguity in the "do the right thing" clause
1245 : : template<typename _Integer>
1246 : : void
1247 : : _M_initialize_dispatch(_Integer __n, _Integer __value, __true_type)
1248 : : {
1249 : : this->_M_impl._M_start = _M_allocate(static_cast<size_type>(__n));
1250 : : this->_M_impl._M_end_of_storage =
1251 : : this->_M_impl._M_start + static_cast<size_type>(__n);
1252 : : _M_fill_initialize(static_cast<size_type>(__n), __value);
1253 : : }
1254 : :
1255 : : // Called by the range constructor to implement [23.1.1]/9
1256 : : template<typename _InputIterator>
1257 : : void
1258 : : _M_initialize_dispatch(_InputIterator __first, _InputIterator __last,
1259 : : __false_type)
1260 : : {
1261 : : typedef typename std::iterator_traits<_InputIterator>::
1262 : : iterator_category _IterCategory;
1263 : : _M_range_initialize(__first, __last, _IterCategory());
1264 : : }
1265 : :
1266 : : // Called by the second initialize_dispatch above
1267 : : template<typename _InputIterator>
1268 : : void
1269 : : _M_range_initialize(_InputIterator __first,
1270 : : _InputIterator __last, std::input_iterator_tag)
1271 : : {
1272 : : for (; __first != __last; ++__first)
1273 : : #if __cplusplus >= 201103L
1274 : : emplace_back(*__first);
1275 : : #else
1276 : : push_back(*__first);
1277 : : #endif
1278 : : }
1279 : :
1280 : : // Called by the second initialize_dispatch above
1281 : : template<typename _ForwardIterator>
1282 : : void
1283 : : _M_range_initialize(_ForwardIterator __first,
1284 : : _ForwardIterator __last, std::forward_iterator_tag)
1285 : : {
1286 : : const size_type __n = std::distance(__first, __last);
1287 : : this->_M_impl._M_start = this->_M_allocate(__n);
1288 : : this->_M_impl._M_end_of_storage = this->_M_impl._M_start + __n;
1289 : : this->_M_impl._M_finish =
1290 : : std::__uninitialized_copy_a(__first, __last,
1291 : : this->_M_impl._M_start,
1292 : : _M_get_Tp_allocator());
1293 : : }
1294 : :
1295 : : // Called by the first initialize_dispatch above and by the
1296 : : // vector(n,value,a) constructor.
1297 : : void
1298 : : _M_fill_initialize(size_type __n, const value_type& __value)
1299 : : {
1300 : 0 : this->_M_impl._M_finish =
1301 : : std::__uninitialized_fill_n_a(this->_M_impl._M_start, __n, __value,
1302 : : _M_get_Tp_allocator());
1303 : : }
1304 : :
1305 : : #if __cplusplus >= 201103L
1306 : : // Called by the vector(n) constructor.
1307 : : void
1308 : : _M_default_initialize(size_type __n)
1309 : : {
1310 : : this->_M_impl._M_finish =
1311 : : std::__uninitialized_default_n_a(this->_M_impl._M_start, __n,
1312 : : _M_get_Tp_allocator());
1313 : : }
1314 : : #endif
1315 : :
1316 : : // Internal assign functions follow. The *_aux functions do the actual
1317 : : // assignment work for the range versions.
1318 : :
1319 : : // Called by the range assign to implement [23.1.1]/9
1320 : :
1321 : : // _GLIBCXX_RESOLVE_LIB_DEFECTS
1322 : : // 438. Ambiguity in the "do the right thing" clause
1323 : : template<typename _Integer>
1324 : : void
1325 : : _M_assign_dispatch(_Integer __n, _Integer __val, __true_type)
1326 : : { _M_fill_assign(__n, __val); }
1327 : :
1328 : : // Called by the range assign to implement [23.1.1]/9
1329 : : template<typename _InputIterator>
1330 : : void
1331 : : _M_assign_dispatch(_InputIterator __first, _InputIterator __last,
1332 : : __false_type)
1333 : : {
1334 : : typedef typename std::iterator_traits<_InputIterator>::
1335 : : iterator_category _IterCategory;
1336 : : _M_assign_aux(__first, __last, _IterCategory());
1337 : : }
1338 : :
1339 : : // Called by the second assign_dispatch above
1340 : : template<typename _InputIterator>
1341 : : void
1342 : : _M_assign_aux(_InputIterator __first, _InputIterator __last,
1343 : : std::input_iterator_tag);
1344 : :
1345 : : // Called by the second assign_dispatch above
1346 : : template<typename _ForwardIterator>
1347 : : void
1348 : : _M_assign_aux(_ForwardIterator __first, _ForwardIterator __last,
1349 : : std::forward_iterator_tag);
1350 : :
1351 : : // Called by assign(n,t), and the range assign when it turns out
1352 : : // to be the same thing.
1353 : : void
1354 : : _M_fill_assign(size_type __n, const value_type& __val);
1355 : :
1356 : :
1357 : : // Internal insert functions follow.
1358 : :
1359 : : // Called by the range insert to implement [23.1.1]/9
1360 : :
1361 : : // _GLIBCXX_RESOLVE_LIB_DEFECTS
1362 : : // 438. Ambiguity in the "do the right thing" clause
1363 : : template<typename _Integer>
1364 : : void
1365 : : _M_insert_dispatch(iterator __pos, _Integer __n, _Integer __val,
1366 : : __true_type)
1367 : : { _M_fill_insert(__pos, __n, __val); }
1368 : :
1369 : : // Called by the range insert to implement [23.1.1]/9
1370 : : template<typename _InputIterator>
1371 : : void
1372 : : _M_insert_dispatch(iterator __pos, _InputIterator __first,
1373 : : _InputIterator __last, __false_type)
1374 : : {
1375 : : typedef typename std::iterator_traits<_InputIterator>::
1376 : : iterator_category _IterCategory;
1377 : : _M_range_insert(__pos, __first, __last, _IterCategory());
1378 : : }
1379 : :
1380 : : // Called by the second insert_dispatch above
1381 : : template<typename _InputIterator>
1382 : : void
1383 : : _M_range_insert(iterator __pos, _InputIterator __first,
1384 : : _InputIterator __last, std::input_iterator_tag);
1385 : :
1386 : : // Called by the second insert_dispatch above
1387 : : template<typename _ForwardIterator>
1388 : : void
1389 : : _M_range_insert(iterator __pos, _ForwardIterator __first,
1390 : : _ForwardIterator __last, std::forward_iterator_tag);
1391 : :
1392 : : // Called by insert(p,n,x), and the range insert when it turns out to be
1393 : : // the same thing.
1394 : : void
1395 : : _M_fill_insert(iterator __pos, size_type __n, const value_type& __x);
1396 : :
1397 : : #if __cplusplus >= 201103L
1398 : : // Called by resize(n).
1399 : : void
1400 : : _M_default_append(size_type __n);
1401 : :
1402 : : bool
1403 : : _M_shrink_to_fit();
1404 : : #endif
1405 : :
1406 : : // Called by insert(p,x)
1407 : : #if __cplusplus < 201103L
1408 : : void
1409 : : _M_insert_aux(iterator __position, const value_type& __x);
1410 : : #else
1411 : : template<typename... _Args>
1412 : : void
1413 : : _M_insert_aux(iterator __position, _Args&&... __args);
1414 : :
1415 : : template<typename... _Args>
1416 : : void
1417 : : _M_emplace_back_aux(_Args&&... __args);
1418 : : #endif
1419 : :
1420 : : // Called by the latter.
1421 : : size_type
1422 : 8 : _M_check_len(size_type __n, const char* __s) const
1423 : : {
1424 [ - + ]: 4 : if (max_size() - size() < __n)
1425 : 0 : __throw_length_error(__N(__s));
1426 : :
1427 : 8 : const size_type __len = size() + std::max(size(), __n);
1428 [ + - ][ - + ]: 4 : return (__len < size() || __len > max_size()) ? max_size() : __len;
1429 : : }
1430 : :
1431 : : // Internal erase functions follow.
1432 : :
1433 : : // Called by erase(q1,q2), clear(), resize(), _M_fill_assign,
1434 : : // _M_assign_aux.
1435 : : void
1436 : : _M_erase_at_end(pointer __pos) _GLIBCXX_NOEXCEPT
1437 : : {
1438 : 0 : std::_Destroy(__pos, this->_M_impl._M_finish, _M_get_Tp_allocator());
1439 : 0 : this->_M_impl._M_finish = __pos;
1440 : : }
1441 : :
1442 : : iterator
1443 : : _M_erase(iterator __position);
1444 : :
1445 : : iterator
1446 : : _M_erase(iterator __first, iterator __last);
1447 : :
1448 : : #if __cplusplus >= 201103L
1449 : : private:
1450 : : // Constant-time move assignment when source object's memory can be
1451 : : // moved, either because the source's allocator will move too
1452 : : // or because the allocators are equal.
1453 : : void
1454 : : _M_move_assign(vector&& __x, std::true_type) noexcept
1455 : : {
1456 : : vector __tmp(get_allocator());
1457 : : this->_M_impl._M_swap_data(__tmp._M_impl);
1458 : : this->_M_impl._M_swap_data(__x._M_impl);
1459 : : std::__alloc_on_move(_M_get_Tp_allocator(), __x._M_get_Tp_allocator());
1460 : : }
1461 : :
1462 : : // Do move assignment when it might not be possible to move source
1463 : : // object's memory, resulting in a linear-time operation.
1464 : : void
1465 : : _M_move_assign(vector&& __x, std::false_type)
1466 : : {
1467 : : if (__x._M_get_Tp_allocator() == this->_M_get_Tp_allocator())
1468 : : _M_move_assign(std::move(__x), std::true_type());
1469 : : else
1470 : : {
1471 : : // The rvalue's allocator cannot be moved and is not equal,
1472 : : // so we need to individually move each element.
1473 : : this->assign(std::__make_move_if_noexcept_iterator(__x.begin()),
1474 : : std::__make_move_if_noexcept_iterator(__x.end()));
1475 : : __x.clear();
1476 : : }
1477 : : }
1478 : : #endif
1479 : :
1480 : : #if __cplusplus >= 201103L
1481 : : template<typename _Up>
1482 : : _Up*
1483 : : _M_data_ptr(_Up* __ptr) const
1484 : : { return __ptr; }
1485 : :
1486 : : template<typename _Ptr>
1487 : : typename std::pointer_traits<_Ptr>::element_type*
1488 : : _M_data_ptr(_Ptr __ptr) const
1489 : : { return empty() ? nullptr : std::__addressof(*__ptr); }
1490 : : #else
1491 : : template<typename _Ptr>
1492 : : _Ptr
1493 : : _M_data_ptr(_Ptr __ptr) const
1494 : : { return __ptr; }
1495 : : #endif
1496 : : };
1497 : :
1498 : :
1499 : : /**
1500 : : * @brief Vector equality comparison.
1501 : : * @param __x A %vector.
1502 : : * @param __y A %vector of the same type as @a __x.
1503 : : * @return True iff the size and elements of the vectors are equal.
1504 : : *
1505 : : * This is an equivalence relation. It is linear in the size of the
1506 : : * vectors. Vectors are considered equivalent if their sizes are equal,
1507 : : * and if corresponding elements compare equal.
1508 : : */
1509 : : template<typename _Tp, typename _Alloc>
1510 : : inline bool
1511 : : operator==(const vector<_Tp, _Alloc>& __x, const vector<_Tp, _Alloc>& __y)
1512 : : { return (__x.size() == __y.size()
1513 : : && std::equal(__x.begin(), __x.end(), __y.begin())); }
1514 : :
1515 : : /**
1516 : : * @brief Vector ordering relation.
1517 : : * @param __x A %vector.
1518 : : * @param __y A %vector of the same type as @a __x.
1519 : : * @return True iff @a __x is lexicographically less than @a __y.
1520 : : *
1521 : : * This is a total ordering relation. It is linear in the size of the
1522 : : * vectors. The elements must be comparable with @c <.
1523 : : *
1524 : : * See std::lexicographical_compare() for how the determination is made.
1525 : : */
1526 : : template<typename _Tp, typename _Alloc>
1527 : : inline bool
1528 : : operator<(const vector<_Tp, _Alloc>& __x, const vector<_Tp, _Alloc>& __y)
1529 : : { return std::lexicographical_compare(__x.begin(), __x.end(),
1530 : : __y.begin(), __y.end()); }
1531 : :
1532 : : /// Based on operator==
1533 : : template<typename _Tp, typename _Alloc>
1534 : : inline bool
1535 : : operator!=(const vector<_Tp, _Alloc>& __x, const vector<_Tp, _Alloc>& __y)
1536 : : { return !(__x == __y); }
1537 : :
1538 : : /// Based on operator<
1539 : : template<typename _Tp, typename _Alloc>
1540 : : inline bool
1541 : : operator>(const vector<_Tp, _Alloc>& __x, const vector<_Tp, _Alloc>& __y)
1542 : : { return __y < __x; }
1543 : :
1544 : : /// Based on operator<
1545 : : template<typename _Tp, typename _Alloc>
1546 : : inline bool
1547 : : operator<=(const vector<_Tp, _Alloc>& __x, const vector<_Tp, _Alloc>& __y)
1548 : : { return !(__y < __x); }
1549 : :
1550 : : /// Based on operator<
1551 : : template<typename _Tp, typename _Alloc>
1552 : : inline bool
1553 : : operator>=(const vector<_Tp, _Alloc>& __x, const vector<_Tp, _Alloc>& __y)
1554 : : { return !(__x < __y); }
1555 : :
1556 : : /// See std::vector::swap().
1557 : : template<typename _Tp, typename _Alloc>
1558 : : inline void
1559 : : swap(vector<_Tp, _Alloc>& __x, vector<_Tp, _Alloc>& __y)
1560 : : { __x.swap(__y); }
1561 : :
1562 : : _GLIBCXX_END_NAMESPACE_CONTAINER
1563 : : } // namespace std
1564 : :
1565 : : #endif /* _STL_VECTOR_H */
|
