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