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