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