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