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