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