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 
72extern "C" void 
73__sanitizer_annotate_contiguous_container(const void*, const void*, 
74 const void*, const void*); 
75#endif 
76 
77namespace 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 _Vector_impl_data() _GLIBCXX_NOEXCEPT 
98 : _M_start(), _M_finish(), _M_end_of_storage() 
99 { } 
100 
101#if __cplusplus >= 201103L 
102 _Vector_impl_data(_Vector_impl_data&& __x) noexcept 
103 : _M_start(__x._M_start), _M_finish(__x._M_finish), 
104 _M_end_of_storage(__x._M_end_of_storage) 
105 { __x._M_start = __x._M_finish = __x._M_end_of_storage = pointer(); } 
106#endif 
107 
108 void 
109 _M_copy_data(_Vector_impl_data const& __x) _GLIBCXX_NOEXCEPT 
110 { 
111 _M_start = __x._M_start; 
112 _M_finish = __x._M_finish; 
113 _M_end_of_storage = __x._M_end_of_storage; 
114 } 
115 
116 void 
117 _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 _Vector_impl_data __tmp; 
122 __tmp._M_copy_data(*this); 
123 _M_copy_data(__x); 
124 __x._M_copy_data(__tmp); 
125 } 
126 }; 
127 
128 struct _Vector_impl 
129 : public _Tp_alloc_type, public _Vector_impl_data 
130 { 
131 _Vector_impl() _GLIBCXX_NOEXCEPT_IF( 
132 is_nothrow_default_constructible<_Tp_alloc_type>::value) 
133 : _Tp_alloc_type() 
134 { } 
135 
136 _Vector_impl(_Tp_alloc_type const& __a) _GLIBCXX_NOEXCEPT 
137 : _Tp_alloc_type(__a) 
138 { } 
139 
140#if __cplusplus >= 201103L 
141 // Not defaulted, to enforce noexcept(true) even when 
142 // !is_nothrow_move_constructible<_Tp_alloc_type>. 
143 _Vector_impl(_Vector_impl&& __x) noexcept 
144 : _Tp_alloc_type(std::move(__x)), _Vector_impl_data(std::move(__x)) 
145 { } 
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 _M_get_Tp_allocator() _GLIBCXX_NOEXCEPT 
277 { return this->_M_impl; } 
278 
279 const _Tp_alloc_type& 
280 _M_get_Tp_allocator() const _GLIBCXX_NOEXCEPT 
281 { return this->_M_impl; } 
282 
283 allocator_type 
284 get_allocator() const _GLIBCXX_NOEXCEPT 
285 { return allocator_type(_M_get_Tp_allocator()); } 
286 
287#if __cplusplus >= 201103L 
288 _Vector_base() = default; 
289#else 
290 _Vector_base() { } 
291#endif 
292 
293 _Vector_base(const allocator_type& __a) _GLIBCXX_NOEXCEPT 
294 : _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 _Vector_base(size_t __n, const allocator_type& __a) 
304 : _M_impl(__a) 
305 { _M_create_storage(__n); } 
306 
307#if __cplusplus >= 201103L 
308 _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 ~_Vector_base() _GLIBCXX_NOEXCEPT 
334 { 
335 _M_deallocate(p: _M_impl._M_start, 
336 n: _M_impl._M_end_of_storage - _M_impl._M_start); 
337 } 
338 
339 public: 
340 _Vector_impl _M_impl; 
341 
342 pointer 
343 _M_allocate(size_t __n) 
344 { 
345 typedef __gnu_cxx::__alloc_traits<_Tp_alloc_type> _Tr; 
346 return __n != 0 ? _Tr::allocate(_M_impl, __n) : pointer(); 
347 } 
348 
349 void 
350 _M_deallocate(pointer __p, size_t __n) 
351 { 
352 typedef __gnu_cxx::__alloc_traits<_Tp_alloc_type> _Tr; 
353 if (__p) 
354 _Tr::deallocate(_M_impl, __p, __n); 
355 } 
356 
357 protected: 
358 void 
359 _M_create_storage(size_t __n) 
360 { 
361 this->_M_impl._M_start = this->_M_allocate(__n); 
362 this->_M_impl._M_finish = this->_M_impl._M_start; 
363 this->_M_impl._M_end_of_storage = this->_M_impl._M_start + __n; 
364 } 
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 _S_do_relocate(pointer __first, pointer __last, pointer __result, 
454 _Tp_alloc_type& __alloc, true_type) noexcept 
455 { 
456 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 _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 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 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 vector(const allocator_type& __a) _GLIBCXX_NOEXCEPT 
498 : _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 vector(size_type __n, const allocator_type& __a = allocator_type()) 
511 : _Base(_S_check_init_len(__n, __a), __a) 
512 { _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 vector(size_type __n, const value_type& __value, 
523 const allocator_type& __a = allocator_type()) 
524 : _Base(_S_check_init_len(__n, __a), __a) 
525 { _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 vector(const vector& __x) 
554 : _Base(__x.size(), 
555 _Alloc_traits::_S_select_on_copy(__x._M_get_Tp_allocator())) 
556 { 
557 this->_M_impl._M_finish = 
558 std::__uninitialized_copy_a(__x.begin(), __x.end(), 
559 this->_M_impl._M_start, 
560 _M_get_Tp_allocator()); 
561 } 
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 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 vector(initializer_list<value_type> __l, 
626 const allocator_type& __a = allocator_type()) 
627 : _Base(__a) 
628 { 
629 _M_range_initialize(__l.begin(), __l.end(), 
630 random_access_iterator_tag()); 
631 } 
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 vector(_InputIterator __first, _InputIterator __last, 
654 const allocator_type& __a = allocator_type()) 
655 : _Base(__a) 
656 { 
657 _M_range_initialize(__first, __last, 
658 std::__iterator_category(__first)); 
659 } 
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 ~vector() _GLIBCXX_NOEXCEPT 
679 { 
680 std::_Destroy(this->_M_impl._M_start, this->_M_impl._M_finish, 
681 _M_get_Tp_allocator()); 
682 _GLIBCXX_ASAN_ANNOTATE_BEFORE_DEALLOC; 
683 } 
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 operator=(vector&& __x) noexcept(_Alloc_traits::_S_nothrow_move()) 
710 { 
711 constexpr bool __move_storage = 
712 _Alloc_traits::_S_propagate_on_move_assign() 
713 || _Alloc_traits::_S_always_equal(); 
714 _M_move_assign(std::move(__x), __bool_constant<__move_storage>()); 
715 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 operator=(initializer_list<value_type> __l) 
731 { 
732 this->_M_assign_aux(__l.begin(), __l.end(), 
733 random_access_iterator_tag()); 
734 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 assign(size_type __n, const value_type& __val) 
750 { _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 begin() _GLIBCXX_NOEXCEPT 
812 { 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 begin() const _GLIBCXX_NOEXCEPT 
821 { 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 end() _GLIBCXX_NOEXCEPT 
830 { 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 end() const _GLIBCXX_NOEXCEPT 
839 { 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 rbegin() _GLIBCXX_NOEXCEPT 
848 { 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 rbegin() const _GLIBCXX_NOEXCEPT 
857 { 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 rend() _GLIBCXX_NOEXCEPT 
866 { 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 rend() const _GLIBCXX_NOEXCEPT 
875 { 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 cbegin() const noexcept 
885 { 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 cend() const noexcept 
894 { 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 size() const _GLIBCXX_NOEXCEPT 
919 { 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 max_size() const _GLIBCXX_NOEXCEPT 
924 { return _S_max_size(a: _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 resize(size_type __new_size) 
938 { 
939 if (__new_size > size()) 
940 _M_default_append(n: __new_size - size()); 
941 else if (__new_size < size()) 
942 _M_erase_at_end(pos: this->_M_impl._M_start + __new_size); 
943 } 
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(pos: end(), n: __new_size - size(), __x); 
961 else if (__new_size < size()) 
962 _M_erase_at_end(pos: 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 shrink_to_fit() 
990 { _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 capacity() const _GLIBCXX_NOEXCEPT 
999 { return size_type(this->_M_impl._M_end_of_storage 
1000 - 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 empty() const _GLIBCXX_NOEXCEPT 
1008 { 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 operator[](size_type __n) _GLIBCXX_NOEXCEPT 
1044 { 
1045 __glibcxx_requires_subscript(__n); 
1046 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 operator[](size_type __n) const _GLIBCXX_NOEXCEPT 
1062 { 
1063 __glibcxx_requires_subscript(__n); 
1064 return *(this->_M_impl._M_start + __n); 
1065 } 
1066 
1067 protected: 
1068 /// Safety check used only from at(). 
1069 void 
1070 _M_range_check(size_type __n) const 
1071 { 
1072 if (__n >= this->size()) 
1073 __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 } 
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 at(size_type __n) 
1093 { 
1094 _M_range_check(__n); 
1095 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 at(size_type __n) const 
1111 { 
1112 _M_range_check(__n); 
1113 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 front() _GLIBCXX_NOEXCEPT 
1122 { 
1123 __glibcxx_requires_nonempty(); 
1124 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 front() const _GLIBCXX_NOEXCEPT 
1133 { 
1134 __glibcxx_requires_nonempty(); 
1135 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 back() _GLIBCXX_NOEXCEPT 
1144 { 
1145 __glibcxx_requires_nonempty(); 
1146 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 back() const _GLIBCXX_NOEXCEPT 
1155 { 
1156 __glibcxx_requires_nonempty(); 
1157 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 data() _GLIBCXX_NOEXCEPT 
1169 { return _M_data_ptr(this->_M_impl._M_start); } 
1170 
1171 const _Tp* 
1172 data() const _GLIBCXX_NOEXCEPT 
1173 { 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 push_back(const value_type& __x) 
1188 { 
1189 if (this->_M_impl._M_finish != this->_M_impl._M_end_of_storage) 
1190 { 
1191 _GLIBCXX_ASAN_ANNOTATE_GROW(1); 
1192 _Alloc_traits::construct(this->_M_impl, this->_M_impl._M_finish, 
1193 __x); 
1194 ++this->_M_impl._M_finish; 
1195 _GLIBCXX_ASAN_ANNOTATE_GREW(1); 
1196 } 
1197 else 
1198 _M_realloc_insert(end(), __x); 
1199 } 
1200 
1201#if __cplusplus >= 201103L 
1202 void 
1203 push_back(value_type&& __x) 
1204 { 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 pop_back() _GLIBCXX_NOEXCEPT 
1226 { 
1227 __glibcxx_requires_nonempty(); 
1228 --this->_M_impl._M_finish; 
1229 _Alloc_traits::destroy(this->_M_impl, this->_M_impl._M_finish); 
1230 _GLIBCXX_ASAN_ANNOTATE_SHRINK(1); 
1231 } 
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 emplace(const_iterator __position, _Args&&... __args) 
1249 { 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 insert(const_iterator __position, value_type&& __x) 
1294 { return _M_insert_rval(__position, v: 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(pos: 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 insert(const_iterator __position, _InputIterator __first, 
1380 _InputIterator __last) 
1381 { 
1382 difference_type __offset = __position - cbegin(); 
1383 _M_insert_dispatch(begin() + __offset, 
1384 __first, __last, __false_type()); 
1385 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 erase(const_iterator __position) 
1431 { 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 erase(const_iterator __first, const_iterator __last) 
1458 { 
1459 const auto __beg = begin(); 
1460 const auto __cbeg = cbegin(); 
1461 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 swap(vector& __x) _GLIBCXX_NOEXCEPT 
1481 { 
1482#if __cplusplus >= 201103L 
1483 __glibcxx_assert(_Alloc_traits::propagate_on_container_swap::value 
1484 || _M_get_Tp_allocator() == __x._M_get_Tp_allocator()); 
1485#endif 
1486 this->_M_impl._M_swap_data(__x._M_impl); 
1487 _Alloc_traits::_S_on_swap(_M_get_Tp_allocator(), 
1488 __x._M_get_Tp_allocator()); 
1489 } 
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 clear() _GLIBCXX_NOEXCEPT 
1499 { _M_erase_at_end(pos: 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 _M_allocate_and_copy(size_type __n, 
1509 _ForwardIterator __first, _ForwardIterator __last) 
1510 { 
1511 pointer __result = this->_M_allocate(__n); 
1512 __try 
1513 { 
1514 std::__uninitialized_copy_a(__first, __last, __result, 
1515 _M_get_Tp_allocator()); 
1516 return __result; 
1517 } 
1518 __catch(...) 
1519 { 
1520 _M_deallocate(__result, __n); 
1521 __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 _M_range_initialize(_ForwardIterator __first, _ForwardIterator __last, 
1578 std::forward_iterator_tag) 
1579 { 
1580 const size_type __n = std::distance(__first, __last); 
1581 this->_M_impl._M_start 
1582 = this->_M_allocate(_S_check_init_len(__n, a: _M_get_Tp_allocator())); 
1583 this->_M_impl._M_end_of_storage = this->_M_impl._M_start + __n; 
1584 this->_M_impl._M_finish = 
1585 std::__uninitialized_copy_a(__first, __last, 
1586 this->_M_impl._M_start, 
1587 _M_get_Tp_allocator()); 
1588 } 
1589 
1590 // Called by the first initialize_dispatch above and by the 
1591 // vector(n,value,a) constructor. 
1592 void 
1593 _M_fill_initialize(size_type __n, const value_type& __value) 
1594 { 
1595 this->_M_impl._M_finish = 
1596 std::__uninitialized_fill_n_a(this->_M_impl._M_start, __n, __value, 
1597 _M_get_Tp_allocator()); 
1598 } 
1599 
1600#if __cplusplus >= 201103L 
1601 // Called by the vector(n) constructor. 
1602 void 
1603 _M_default_initialize(size_type __n) 
1604 { 
1605 this->_M_impl._M_finish = 
1606 std::__uninitialized_default_n_a(this->_M_impl._M_start, __n, 
1607 _M_get_Tp_allocator()); 
1608 } 
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, x: __val); } 
1658 
1659 // Called by the range insert to implement [23.1.1]/9 
1660 template<typename _InputIterator> 
1661 void 
1662 _M_insert_dispatch(iterator __pos, _InputIterator __first, 
1663 _InputIterator __last, __false_type) 
1664 { 
1665 _M_range_insert(__pos, __first, __last, 
1666 std::__iterator_category(__first)); 
1667 } 
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 _Temporary_value(vector* __vec, _Args&&... __args) : _M_this(__vec) 
1710 { 
1711 _Alloc_traits::construct(_M_this->_M_impl, _M_ptr(), 
1712 std::forward<_Args>(__args)...); 
1713 } 
1714 
1715 ~_Temporary_value() 
1716 { _Alloc_traits::destroy(_M_this->_M_impl, _M_ptr()); } 
1717 
1718 value_type& 
1719 _M_val() { return *_M_ptr(); } 
1720 
1721 private: 
1722 _Tp* 
1723 _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 _M_emplace_aux(const_iterator __position, value_type&& __v) 
1751 { return _M_insert_rval(__position, v: std::move(__v)); } 
1752#endif 
1753 
1754 // Called by _M_fill_insert, _M_insert_aux etc. 
1755 size_type 
1756 _M_check_len(size_type __n, const char* __s) const 
1757 { 
1758 if (max_size() - size() < __n) 
1759 __throw_length_error(__N(__s)); 
1760 
1761 const size_type __len = size() + (std::max)(size(), __n); 
1762 return (__len < size() || __len > max_size()) ? max_size() : __len; 
1763 } 
1764 
1765 // Called by constructors to check initial size. 
1766 static size_type 
1767 _S_check_init_len(size_type __n, const allocator_type& __a) 
1768 { 
1769 if (__n > _S_max_size(a: _Tp_alloc_type(__a))) 
1770 __throw_length_error( 
1771 __N("cannot create std::vector larger than max_size()")); 
1772 return __n; 
1773 } 
1774 
1775 static size_type 
1776 _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 const size_t __diffmax 
1782 = __gnu_cxx::__numeric_traits<ptrdiff_t>::__max / sizeof(_Tp); 
1783 const size_t __allocmax = _Alloc_traits::max_size(__a); 
1784 return (std::min)(a: __diffmax, b: __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 _M_erase_at_end(pointer __pos) _GLIBCXX_NOEXCEPT 
1793 { 
1794 if (size_type __n = this->_M_impl._M_finish - __pos) 
1795 { 
1796 std::_Destroy(__pos, this->_M_impl._M_finish, 
1797 _M_get_Tp_allocator()); 
1798 this->_M_impl._M_finish = __pos; 
1799 _GLIBCXX_ASAN_ANNOTATE_SHRINK(__n); 
1800 } 
1801 } 
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 _M_move_assign(vector&& __x, true_type) noexcept 
1816 { 
1817 vector __tmp(get_allocator()); 
1818 this->_M_impl._M_swap_data(__x._M_impl); 
1819 __tmp._M_impl._M_swap_data(__x._M_impl); 
1820 std::__alloc_on_move(_M_get_Tp_allocator(), __x._M_get_Tp_allocator()); 
1821 } 
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 _M_data_ptr(_Up* __ptr) const _GLIBCXX_NOEXCEPT 
1845 { 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 operator==(const vector<_Tp, _Alloc>& __x, const vector<_Tp, _Alloc>& __y) 
1893 { return (__x.size() == __y.size() 
1894 && 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 swap(vector<_Tp, _Alloc>& __x, vector<_Tp, _Alloc>& __y) 
1963 _GLIBCXX_NOEXCEPT_IF(noexcept(__x.swap(__y))) 
1964 { __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 */ 
1986