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