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