libstdc++
vector.tcc
Go to the documentation of this file.
1// Vector implementation (out of line) -*- C++ -*-
2
3// Copyright (C) 2001-2025 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/vector.tcc
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 _VECTOR_TCC
57#define _VECTOR_TCC 1
58
59namespace std _GLIBCXX_VISIBILITY(default)
60{
61_GLIBCXX_BEGIN_NAMESPACE_VERSION
62_GLIBCXX_BEGIN_NAMESPACE_CONTAINER
63
64#pragma GCC diagnostic push
65#pragma GCC diagnostic ignored "-Wc++17-extensions" // if constexpr
66
67 template<typename _Tp, typename _Alloc>
68 _GLIBCXX20_CONSTEXPR
69 void
70 vector<_Tp, _Alloc>::
71 reserve(size_type __n)
72 {
73 if (__n > this->max_size())
74 __throw_length_error(__N("vector::reserve"));
75 if (this->capacity() < __n)
76 {
77 const size_type __old_size = size();
78 pointer __tmp;
79#if __cplusplus >= 201103L
80 if constexpr (_S_use_relocate())
81 {
82 __tmp = this->_M_allocate(__n);
83 std::__relocate_a(this->_M_impl._M_start, this->_M_impl._M_finish,
84 __tmp, _M_get_Tp_allocator());
85 }
86 else
87#endif
88 {
89 __tmp = _M_allocate_and_copy(__n,
90 _GLIBCXX_MAKE_MOVE_IF_NOEXCEPT_ITERATOR(this->_M_impl._M_start),
91 _GLIBCXX_MAKE_MOVE_IF_NOEXCEPT_ITERATOR(this->_M_impl._M_finish));
92 std::_Destroy(this->_M_impl._M_start, this->_M_impl._M_finish,
93 _M_get_Tp_allocator());
94 }
95 _GLIBCXX_ASAN_ANNOTATE_REINIT;
96 _M_deallocate(this->_M_impl._M_start,
97 this->_M_impl._M_end_of_storage
98 - this->_M_impl._M_start);
99 this->_M_impl._M_start = __tmp;
100 this->_M_impl._M_finish = __tmp + __old_size;
101 this->_M_impl._M_end_of_storage = this->_M_impl._M_start + __n;
102 }
103 }
104#pragma GCC diagnostic pop
105
106#if __cplusplus >= 201103L
107 template<typename _Tp, typename _Alloc>
108 template<typename... _Args>
109#if __cplusplus > 201402L
110 _GLIBCXX20_CONSTEXPR
111 typename vector<_Tp, _Alloc>::reference
112#else
113 void
114#endif
115 vector<_Tp, _Alloc>::
116 emplace_back(_Args&&... __args)
117 {
118 if (this->_M_impl._M_finish != this->_M_impl._M_end_of_storage)
119 {
120 _GLIBCXX_ASAN_ANNOTATE_GROW(1);
121 _Alloc_traits::construct(this->_M_impl, this->_M_impl._M_finish,
122 std::forward<_Args>(__args)...);
123 ++this->_M_impl._M_finish;
124 _GLIBCXX_ASAN_ANNOTATE_GREW(1);
125 }
126 else
127 _M_realloc_append(std::forward<_Args>(__args)...);
128#if __cplusplus > 201402L
129 return back();
130#endif
131 }
132#endif
133
134 template<typename _Tp, typename _Alloc>
135 _GLIBCXX20_CONSTEXPR
136 typename vector<_Tp, _Alloc>::iterator
137 vector<_Tp, _Alloc>::
138#if __cplusplus >= 201103L
139 insert(const_iterator __position, const value_type& __x)
140#else
141 insert(iterator __position, const value_type& __x)
142#endif
143 {
144 const size_type __n = __position - begin();
145 if (this->_M_impl._M_finish != this->_M_impl._M_end_of_storage)
146 {
147 __glibcxx_assert(__position != const_iterator());
148 if (!(__position != const_iterator()))
149 __builtin_unreachable(); // PR 106434
150
151 if (__position == end())
152 {
153 _GLIBCXX_ASAN_ANNOTATE_GROW(1);
154 _Alloc_traits::construct(this->_M_impl, this->_M_impl._M_finish,
155 __x);
156 ++this->_M_impl._M_finish;
157 _GLIBCXX_ASAN_ANNOTATE_GREW(1);
158 }
159 else
160 {
161#if __cplusplus >= 201103L
162 const auto __pos = begin() + (__position - cbegin());
163 // __x could be an existing element of this vector, so make a
164 // copy of it before _M_insert_aux moves elements around.
165 _Temporary_value __x_copy(this, __x);
166 _M_insert_aux(__pos, std::move(__x_copy._M_val()));
167#else
168 _M_insert_aux(__position, __x);
169#endif
170 }
171 }
172 else
173#if __cplusplus >= 201103L
174 _M_realloc_insert(begin() + (__position - cbegin()), __x);
175#else
176 _M_realloc_insert(__position, __x);
177#endif
178
179 return iterator(this->_M_impl._M_start + __n);
180 }
181
182 template<typename _Tp, typename _Alloc>
183 _GLIBCXX20_CONSTEXPR
184 typename vector<_Tp, _Alloc>::iterator
185 vector<_Tp, _Alloc>::
186 _M_erase(iterator __position)
187 {
188 if (__position + 1 != end())
189 _GLIBCXX_MOVE3(__position + 1, end(), __position);
190 --this->_M_impl._M_finish;
191 _Alloc_traits::destroy(this->_M_impl, this->_M_impl._M_finish);
192 _GLIBCXX_ASAN_ANNOTATE_SHRINK(1);
193 return __position;
194 }
195
196 template<typename _Tp, typename _Alloc>
197 _GLIBCXX20_CONSTEXPR
198 typename vector<_Tp, _Alloc>::iterator
199 vector<_Tp, _Alloc>::
200 _M_erase(iterator __first, iterator __last)
201 {
202 if (__first != __last)
203 {
204 if (__last != end())
205 _GLIBCXX_MOVE3(__last, end(), __first);
206 _M_erase_at_end(__first.base() + (end() - __last));
207 }
208 return __first;
209 }
210
211 template<typename _Tp, typename _Alloc>
212 _GLIBCXX20_CONSTEXPR
213 vector<_Tp, _Alloc>&
214 vector<_Tp, _Alloc>::
215 operator=(const vector<_Tp, _Alloc>& __x)
216 {
217 if (std::__addressof(__x) != this)
218 {
219 _GLIBCXX_ASAN_ANNOTATE_REINIT;
220#if __cplusplus >= 201103L
221 if (_Alloc_traits::_S_propagate_on_copy_assign())
222 {
223 if (!_Alloc_traits::_S_always_equal()
224 && _M_get_Tp_allocator() != __x._M_get_Tp_allocator())
225 {
226 // replacement allocator cannot free existing storage
227 this->clear();
228 _M_deallocate(this->_M_impl._M_start,
229 this->_M_impl._M_end_of_storage
230 - this->_M_impl._M_start);
231 this->_M_impl._M_start = nullptr;
232 this->_M_impl._M_finish = nullptr;
233 this->_M_impl._M_end_of_storage = nullptr;
234 }
235 std::__alloc_on_copy(_M_get_Tp_allocator(),
236 __x._M_get_Tp_allocator());
237 }
238#endif
239 const size_type __xlen = __x.size();
240 if (__xlen > capacity())
241 {
242 pointer __tmp = _M_allocate_and_copy(__xlen, __x.begin(),
243 __x.end());
244 std::_Destroy(this->_M_impl._M_start, this->_M_impl._M_finish,
245 _M_get_Tp_allocator());
246 _M_deallocate(this->_M_impl._M_start,
247 this->_M_impl._M_end_of_storage
248 - this->_M_impl._M_start);
249 this->_M_impl._M_start = __tmp;
250 this->_M_impl._M_end_of_storage = this->_M_impl._M_start + __xlen;
251 }
252 else if (size() >= __xlen)
253 {
254 std::_Destroy(std::copy(__x.begin(), __x.end(), begin()),
255 end(), _M_get_Tp_allocator());
256 }
257 else
258 {
259 std::copy(__x._M_impl._M_start, __x._M_impl._M_start + size(),
260 this->_M_impl._M_start);
261 std::__uninitialized_copy_a(__x._M_impl._M_start + size(),
262 __x._M_impl._M_finish,
263 this->_M_impl._M_finish,
264 _M_get_Tp_allocator());
265 }
266 this->_M_impl._M_finish = this->_M_impl._M_start + __xlen;
267 }
268 return *this;
269 }
270
271 template<typename _Tp, typename _Alloc>
272 _GLIBCXX20_CONSTEXPR
273 void
274 vector<_Tp, _Alloc>::
275 _M_fill_assign(size_t __n, const value_type& __val)
276 {
277 const size_type __sz = size();
278 if (__n > capacity())
279 {
280 if (__n <= __sz)
281 __builtin_unreachable();
282 vector __tmp(__n, __val, _M_get_Tp_allocator());
283 __tmp._M_impl._M_swap_data(this->_M_impl);
284 }
285 else if (__n > __sz)
286 {
287 std::fill(begin(), end(), __val);
288 const size_type __add = __n - __sz;
289 _GLIBCXX_ASAN_ANNOTATE_GROW(__add);
290 this->_M_impl._M_finish =
291 std::__uninitialized_fill_n_a(this->_M_impl._M_finish,
292 __add, __val, _M_get_Tp_allocator());
293 _GLIBCXX_ASAN_ANNOTATE_GREW(__add);
294 }
295 else
296 _M_erase_at_end(std::fill_n(this->_M_impl._M_start, __n, __val));
297 }
298
299 template<typename _Tp, typename _Alloc>
300 template<typename _InputIterator>
301 _GLIBCXX20_CONSTEXPR
302 void
303 vector<_Tp, _Alloc>::
304 _M_assign_aux(_InputIterator __first, _InputIterator __last,
305 std::input_iterator_tag)
306 {
307 pointer __cur(this->_M_impl._M_start);
308 for (; __first != __last && __cur != this->_M_impl._M_finish;
309 ++__cur, (void)++__first)
310 *__cur = *__first;
311 if (__first == __last)
312 _M_erase_at_end(__cur);
313 else
314 _M_range_insert(end(), __first, __last,
315 std::__iterator_category(__first));
316 }
317
318 template<typename _Tp, typename _Alloc>
319 template<typename _ForwardIterator>
320 _GLIBCXX20_CONSTEXPR
321 void
322 vector<_Tp, _Alloc>::
323 _M_assign_aux(_ForwardIterator __first, _ForwardIterator __last,
324 std::forward_iterator_tag)
325 {
326 const size_type __sz = size();
327 const size_type __len = std::distance(__first, __last);
328
329 if (__len > capacity())
330 {
331 if (__len <= __sz)
332 __builtin_unreachable();
333
334 _S_check_init_len(__len, _M_get_Tp_allocator());
335 pointer __tmp(_M_allocate_and_copy(__len, __first, __last));
336 std::_Destroy(this->_M_impl._M_start, this->_M_impl._M_finish,
337 _M_get_Tp_allocator());
338 _GLIBCXX_ASAN_ANNOTATE_REINIT;
339 _M_deallocate(this->_M_impl._M_start,
340 this->_M_impl._M_end_of_storage
341 - this->_M_impl._M_start);
342 this->_M_impl._M_start = __tmp;
343 this->_M_impl._M_finish = this->_M_impl._M_start + __len;
344 this->_M_impl._M_end_of_storage = this->_M_impl._M_finish;
345 }
346 else if (__sz >= __len)
347 _M_erase_at_end(std::copy(__first, __last, this->_M_impl._M_start));
348 else
349 {
350 _ForwardIterator __mid = __first;
351 std::advance(__mid, __sz);
352 std::copy(__first, __mid, this->_M_impl._M_start);
353 const size_type __attribute__((__unused__)) __n = __len - __sz;
354 _GLIBCXX_ASAN_ANNOTATE_GROW(__n);
355 this->_M_impl._M_finish =
356 std::__uninitialized_copy_a(__mid, __last,
357 this->_M_impl._M_finish,
358 _M_get_Tp_allocator());
359 _GLIBCXX_ASAN_ANNOTATE_GREW(__n);
360 }
361 }
362
363#if __cplusplus >= 201103L
364 template<typename _Tp, typename _Alloc>
365 _GLIBCXX20_CONSTEXPR
366 auto
367 vector<_Tp, _Alloc>::
368 _M_insert_rval(const_iterator __position, value_type&& __v) -> iterator
369 {
370 const auto __n = __position - cbegin();
371 if (this->_M_impl._M_finish != this->_M_impl._M_end_of_storage)
372 if (__position == cend())
373 {
374 _GLIBCXX_ASAN_ANNOTATE_GROW(1);
375 _Alloc_traits::construct(this->_M_impl, this->_M_impl._M_finish,
376 std::move(__v));
377 ++this->_M_impl._M_finish;
378 _GLIBCXX_ASAN_ANNOTATE_GREW(1);
379 }
380 else
381 _M_insert_aux(begin() + __n, std::move(__v));
382 else
383 _M_realloc_insert(begin() + __n, std::move(__v));
384
385 return iterator(this->_M_impl._M_start + __n);
386 }
387
388 template<typename _Tp, typename _Alloc>
389 template<typename... _Args>
390 _GLIBCXX20_CONSTEXPR
391 auto
392 vector<_Tp, _Alloc>::
393 _M_emplace_aux(const_iterator __position, _Args&&... __args)
394 -> iterator
395 {
396 const auto __n = __position - cbegin();
397 if (this->_M_impl._M_finish != this->_M_impl._M_end_of_storage)
398 if (__position == cend())
399 {
400 _GLIBCXX_ASAN_ANNOTATE_GROW(1);
401 _Alloc_traits::construct(this->_M_impl, this->_M_impl._M_finish,
402 std::forward<_Args>(__args)...);
403 ++this->_M_impl._M_finish;
404 _GLIBCXX_ASAN_ANNOTATE_GREW(1);
405 }
406 else
407 {
408 // We need to construct a temporary because something in __args...
409 // could alias one of the elements of the container and so we
410 // need to use it before _M_insert_aux moves elements around.
411 _Temporary_value __tmp(this, std::forward<_Args>(__args)...);
412 _M_insert_aux(begin() + __n, std::move(__tmp._M_val()));
413 }
414 else
415 _M_realloc_insert(begin() + __n, std::forward<_Args>(__args)...);
416
417 return iterator(this->_M_impl._M_start + __n);
418 }
419
420 template<typename _Tp, typename _Alloc>
421 template<typename _Arg>
422 _GLIBCXX20_CONSTEXPR
423 void
424 vector<_Tp, _Alloc>::
425 _M_insert_aux(iterator __position, _Arg&& __arg)
426#else
427 template<typename _Tp, typename _Alloc>
428 void
429 vector<_Tp, _Alloc>::
430 _M_insert_aux(iterator __position, const _Tp& __x)
431#endif
432 {
433 _GLIBCXX_ASAN_ANNOTATE_GROW(1);
434 _Alloc_traits::construct(this->_M_impl, this->_M_impl._M_finish,
435 _GLIBCXX_MOVE(*(this->_M_impl._M_finish - 1)));
436 ++this->_M_impl._M_finish;
437 _GLIBCXX_ASAN_ANNOTATE_GREW(1);
438#if __cplusplus < 201103L
439 _Tp __x_copy = __x;
440#endif
441 _GLIBCXX_MOVE_BACKWARD3(__position.base(),
442 this->_M_impl._M_finish - 2,
443 this->_M_impl._M_finish - 1);
444#if __cplusplus < 201103L
445 *__position = __x_copy;
446#else
447 *__position = std::forward<_Arg>(__arg);
448#endif
449 }
450
451#pragma GCC diagnostic push
452#pragma GCC diagnostic ignored "-Wc++17-extensions" // if constexpr
453#if __cplusplus >= 201103L
454 template<typename _Tp, typename _Alloc>
455 template<typename... _Args>
456 _GLIBCXX20_CONSTEXPR
457 void
458 vector<_Tp, _Alloc>::
459 _M_realloc_insert(iterator __position, _Args&&... __args)
460#else
461 template<typename _Tp, typename _Alloc>
462 void
463 vector<_Tp, _Alloc>::
464 _M_realloc_insert(iterator __position, const _Tp& __x)
465#endif
466 {
467 const size_type __len = _M_check_len(1u, "vector::_M_realloc_insert");
468 if (__len <= 0)
469 __builtin_unreachable();
470 pointer __old_start = this->_M_impl._M_start;
471 pointer __old_finish = this->_M_impl._M_finish;
472 const size_type __elems_before = __position - begin();
473 pointer __new_start(this->_M_allocate(__len));
474 pointer __new_finish(__new_start);
475
476 {
477 _Guard_alloc __guard(__new_start, __len, *this);
478
479 // The order of the three operations is dictated by the C++11
480 // case, where the moves could alter a new element belonging
481 // to the existing vector. This is an issue only for callers
482 // taking the element by lvalue ref (see last bullet of C++11
483 // [res.on.arguments]).
484
485 // If this throws, the existing elements are unchanged.
486#if __cplusplus >= 201103L
487 _Alloc_traits::construct(this->_M_impl,
488 std::__to_address(__new_start + __elems_before),
489 std::forward<_Args>(__args)...);
490#else
491 _Alloc_traits::construct(this->_M_impl,
492 __new_start + __elems_before,
493 __x);
494#endif
495
496#if __cplusplus >= 201103L
497 if constexpr (_S_use_relocate())
498 {
499 // Relocation cannot throw.
500 __new_finish = std::__relocate_a(__old_start, __position.base(),
501 __new_start,
502 _M_get_Tp_allocator());
503 ++__new_finish;
504 __new_finish = std::__relocate_a(__position.base(), __old_finish,
505 __new_finish,
506 _M_get_Tp_allocator());
507 }
508 else
509#endif
510 {
511 // RAII type to destroy initialized elements.
512 struct _Guard_elts
513 {
514 pointer _M_first, _M_last; // Elements to destroy
515 _Tp_alloc_type& _M_alloc;
516
517 _GLIBCXX20_CONSTEXPR
518 _Guard_elts(pointer __elt, _Tp_alloc_type& __a)
519 : _M_first(__elt), _M_last(__elt + 1), _M_alloc(__a)
520 { }
521
522 _GLIBCXX20_CONSTEXPR
523 ~_Guard_elts()
524 { std::_Destroy(_M_first, _M_last, _M_alloc); }
525
526 private:
527 _Guard_elts(const _Guard_elts&);
528 };
529
530 // Guard the new element so it will be destroyed if anything throws.
531 _Guard_elts __guard_elts(__new_start + __elems_before, _M_impl);
532
533 __new_finish = std::__uninitialized_move_if_noexcept_a(
534 __old_start, __position.base(),
535 __new_start, _M_get_Tp_allocator());
536
537 ++__new_finish;
538 // Guard everything before the new element too.
539 __guard_elts._M_first = __new_start;
540
541 __new_finish = std::__uninitialized_move_if_noexcept_a(
542 __position.base(), __old_finish,
543 __new_finish, _M_get_Tp_allocator());
544
545 // New storage has been fully initialized, destroy the old elements.
546 __guard_elts._M_first = __old_start;
547 __guard_elts._M_last = __old_finish;
548 }
549 __guard._M_storage = __old_start;
550 __guard._M_len = this->_M_impl._M_end_of_storage - __old_start;
551 }
552 // deallocate should be called before assignments to _M_impl,
553 // to avoid call-clobbering
554
555 this->_M_impl._M_start = __new_start;
556 this->_M_impl._M_finish = __new_finish;
557 this->_M_impl._M_end_of_storage = __new_start + __len;
558 }
559
560#if __cplusplus >= 201103L
561 template<typename _Tp, typename _Alloc>
562 template<typename... _Args>
563 _GLIBCXX20_CONSTEXPR
564 void
565 vector<_Tp, _Alloc>::
566 _M_realloc_append(_Args&&... __args)
567#else
568 template<typename _Tp, typename _Alloc>
569 void
570 vector<_Tp, _Alloc>::
571 _M_realloc_append(const _Tp& __x)
572#endif
573 {
574 const size_type __len = _M_check_len(1u, "vector::_M_realloc_append");
575 if (__len <= 0)
576 __builtin_unreachable();
577 pointer __old_start = this->_M_impl._M_start;
578 pointer __old_finish = this->_M_impl._M_finish;
579 const size_type __elems = size();
580 pointer __new_start(this->_M_allocate(__len));
581 pointer __new_finish(__new_start);
582
583 {
584 _Guard_alloc __guard(__new_start, __len, *this);
585
586 // The order of the three operations is dictated by the C++11
587 // case, where the moves could alter a new element belonging
588 // to the existing vector. This is an issue only for callers
589 // taking the element by lvalue ref (see last bullet of C++11
590 // [res.on.arguments]).
591
592 // If this throws, the existing elements are unchanged.
593#if __cplusplus >= 201103L
594 _Alloc_traits::construct(this->_M_impl,
595 std::__to_address(__new_start + __elems),
596 std::forward<_Args>(__args)...);
597#else
598 _Alloc_traits::construct(this->_M_impl,
599 __new_start + __elems,
600 __x);
601#endif
602
603#if __cplusplus >= 201103L
604 if constexpr (_S_use_relocate())
605 {
606 // Relocation cannot throw.
607 __new_finish = std::__relocate_a(__old_start, __old_finish,
608 __new_start,
609 _M_get_Tp_allocator());
610 ++__new_finish;
611 }
612 else
613#endif
614 {
615 // RAII type to destroy initialized elements.
616 struct _Guard_elts
617 {
618 pointer _M_first, _M_last; // Elements to destroy
619 _Tp_alloc_type& _M_alloc;
620
621 _GLIBCXX20_CONSTEXPR
622 _Guard_elts(pointer __elt, _Tp_alloc_type& __a)
623 : _M_first(__elt), _M_last(__elt + 1), _M_alloc(__a)
624 { }
625
626 _GLIBCXX20_CONSTEXPR
627 ~_Guard_elts()
628 { std::_Destroy(_M_first, _M_last, _M_alloc); }
629
630 private:
631 _Guard_elts(const _Guard_elts&);
632 };
633
634 // Guard the new element so it will be destroyed if anything throws.
635 _Guard_elts __guard_elts(__new_start + __elems, _M_impl);
636
637 __new_finish = std::__uninitialized_move_if_noexcept_a(
638 __old_start, __old_finish,
639 __new_start, _M_get_Tp_allocator());
640
641 ++__new_finish;
642
643 // New storage has been fully initialized, destroy the old elements.
644 __guard_elts._M_first = __old_start;
645 __guard_elts._M_last = __old_finish;
646 }
647 __guard._M_storage = __old_start;
648 __guard._M_len = this->_M_impl._M_end_of_storage - __old_start;
649 }
650 // deallocate should be called before assignments to _M_impl,
651 // to avoid call-clobbering
652
653 this->_M_impl._M_start = __new_start;
654 this->_M_impl._M_finish = __new_finish;
655 this->_M_impl._M_end_of_storage = __new_start + __len;
656 }
657#pragma GCC diagnostic pop
658
659 template<typename _Tp, typename _Alloc>
660 _GLIBCXX20_CONSTEXPR
661 void
662 vector<_Tp, _Alloc>::
663 _M_fill_insert(iterator __position, size_type __n, const value_type& __x)
664 {
665 if (__n != 0)
666 {
667 if (__position.base() == this->_M_impl._M_finish)
668 _M_fill_append(__n, __x);
669 else if (size_type(this->_M_impl._M_end_of_storage
670 - this->_M_impl._M_finish) >= __n)
671 {
672#if __cplusplus < 201103L
673 value_type __x_copy = __x;
674#else
675 _Temporary_value __tmp(this, __x);
676 value_type& __x_copy = __tmp._M_val();
677#endif
678 const size_type __elems_after = end() - __position;
679 pointer __old_finish(this->_M_impl._M_finish);
680 if (__elems_after > __n)
681 {
682 _GLIBCXX_ASAN_ANNOTATE_GROW(__n);
683 std::__uninitialized_move_a(__old_finish - __n,
684 __old_finish,
685 __old_finish,
686 _M_get_Tp_allocator());
687 this->_M_impl._M_finish += __n;
688 _GLIBCXX_ASAN_ANNOTATE_GREW(__n);
689 _GLIBCXX_MOVE_BACKWARD3(__position.base(),
690 __old_finish - __n, __old_finish);
691 std::fill(__position.base(), __position.base() + __n,
692 __x_copy);
693 }
694 else
695 {
696 _GLIBCXX_ASAN_ANNOTATE_GROW(__n);
697 this->_M_impl._M_finish =
698 std::__uninitialized_fill_n_a(__old_finish,
699 __n - __elems_after,
700 __x_copy,
701 _M_get_Tp_allocator());
702 _GLIBCXX_ASAN_ANNOTATE_GREW(__n - __elems_after);
703 std::__uninitialized_move_a(__position.base(), __old_finish,
704 this->_M_impl._M_finish,
705 _M_get_Tp_allocator());
706 this->_M_impl._M_finish += __elems_after;
707 _GLIBCXX_ASAN_ANNOTATE_GREW(__elems_after);
708 std::fill(__position.base(), __old_finish, __x_copy);
709 }
710 }
711 else
712 {
713 // Make local copies of these members because the compiler thinks
714 // the allocator can alter them if 'this' is globally reachable.
715 pointer __old_start = this->_M_impl._M_start;
716 pointer __old_finish = this->_M_impl._M_finish;
717 const pointer __pos = __position.base();
718
719 const size_type __len =
720 _M_check_len(__n, "vector::_M_fill_insert");
721 const size_type __elems_before = __pos - __old_start;
722 pointer __new_start(this->_M_allocate(__len));
723 pointer __new_finish(__new_start);
724 __try
725 {
726 // See _M_realloc_insert above.
727 std::__uninitialized_fill_n_a(__new_start + __elems_before,
728 __n, __x,
729 _M_get_Tp_allocator());
730 __new_finish = pointer();
731
732 __new_finish
733 = std::__uninitialized_move_if_noexcept_a
734 (__old_start, __pos, __new_start, _M_get_Tp_allocator());
735
736 __new_finish += __n;
737
738 __new_finish
739 = std::__uninitialized_move_if_noexcept_a
740 (__pos, __old_finish, __new_finish, _M_get_Tp_allocator());
741 }
742 __catch(...)
743 {
744 if (!__new_finish)
745 std::_Destroy(__new_start + __elems_before,
746 __new_start + __elems_before + __n,
747 _M_get_Tp_allocator());
748 else
749 std::_Destroy(__new_start, __new_finish,
750 _M_get_Tp_allocator());
751 _M_deallocate(__new_start, __len);
752 __throw_exception_again;
753 }
754 std::_Destroy(__old_start, __old_finish, _M_get_Tp_allocator());
755 _GLIBCXX_ASAN_ANNOTATE_REINIT;
756 _M_deallocate(__old_start,
757 this->_M_impl._M_end_of_storage - __old_start);
758 this->_M_impl._M_start = __new_start;
759 this->_M_impl._M_finish = __new_finish;
760 this->_M_impl._M_end_of_storage = __new_start + __len;
761 }
762 }
763 }
764
765 template<typename _Tp, typename _Alloc>
766 _GLIBCXX20_CONSTEXPR
767 void
768 vector<_Tp, _Alloc>::
769 _M_fill_append(size_type __n, const value_type& __x)
770 {
771 if (size_type(this->_M_impl._M_end_of_storage
772 - this->_M_impl._M_finish) >= __n)
773 {
774 _GLIBCXX_ASAN_ANNOTATE_GROW(__n);
775 this->_M_impl._M_finish =
776 std::__uninitialized_fill_n_a(this->_M_impl._M_finish, __n, __x,
777 _M_get_Tp_allocator());
778 _GLIBCXX_ASAN_ANNOTATE_GREW(__n);
779 }
780 else
781 {
782 // Make local copies of these members because the compiler thinks
783 // the allocator can alter them if 'this' is globally reachable.
784 pointer __old_start = this->_M_impl._M_start;
785 pointer __old_finish = this->_M_impl._M_finish;
786 const size_type __old_size = __old_finish - __old_start;
787
788 const size_type __len =
789 _M_check_len(__n, "vector::_M_fill_append");
790 pointer __new_start(this->_M_allocate(__len));
791 pointer __new_finish(__new_start + __old_size);
792 __try
793 {
794 // See _M_realloc_insert above.
795 __new_finish = std::__uninitialized_fill_n_a(
796 __new_finish, __n, __x,
797 _M_get_Tp_allocator());
798 std::__uninitialized_move_if_noexcept_a(
799 __old_start, __old_finish, __new_start,
800 _M_get_Tp_allocator());
801 }
802 __catch(...)
803 {
804 std::_Destroy(__new_start + __old_size, __new_finish,
805 _M_get_Tp_allocator());
806 _M_deallocate(__new_start, __len);
807 __throw_exception_again;
808 }
809 std::_Destroy(__old_start, __old_finish, _M_get_Tp_allocator());
810 _GLIBCXX_ASAN_ANNOTATE_REINIT;
811 _M_deallocate(__old_start,
812 this->_M_impl._M_end_of_storage - __old_start);
813 this->_M_impl._M_start = __new_start;
814 this->_M_impl._M_finish = __new_finish;
815 this->_M_impl._M_end_of_storage = __new_start + __len;
816 }
817 }
818
819#if __cplusplus >= 201103L
820#pragma GCC diagnostic push
821#pragma GCC diagnostic ignored "-Wc++17-extensions" // if constexpr
822 template<typename _Tp, typename _Alloc>
823 _GLIBCXX20_CONSTEXPR
824 void
825 vector<_Tp, _Alloc>::
826 _M_default_append(size_type __n)
827 {
828 if (__n != 0)
829 {
830 const size_type __size = size();
831 size_type __navail = size_type(this->_M_impl._M_end_of_storage
832 - this->_M_impl._M_finish);
833
834 if (__size > max_size() || __navail > max_size() - __size)
835 __builtin_unreachable();
836
837 if (__navail >= __n)
838 {
839 if (!this->_M_impl._M_finish)
840 __builtin_unreachable();
841
842 _GLIBCXX_ASAN_ANNOTATE_GROW(__n);
843 this->_M_impl._M_finish =
844 std::__uninitialized_default_n_a(this->_M_impl._M_finish,
845 __n, _M_get_Tp_allocator());
846 _GLIBCXX_ASAN_ANNOTATE_GREW(__n);
847 }
848 else
849 {
850 // Make local copies of these members because the compiler thinks
851 // the allocator can alter them if 'this' is globally reachable.
852 pointer __old_start = this->_M_impl._M_start;
853 pointer __old_finish = this->_M_impl._M_finish;
854
855 const size_type __len =
856 _M_check_len(__n, "vector::_M_default_append");
857 pointer __new_start(this->_M_allocate(__len));
858
859 {
860 _Guard_alloc __guard(__new_start, __len, *this);
861
862 std::__uninitialized_default_n_a(__new_start + __size, __n,
863 _M_get_Tp_allocator());
864
865 if constexpr (_S_use_relocate())
866 {
867 std::__relocate_a(__old_start, __old_finish,
868 __new_start, _M_get_Tp_allocator());
869 }
870 else
871 {
872 // RAII type to destroy initialized elements.
873 struct _Guard_elts
874 {
875 pointer _M_first, _M_last; // Elements to destroy
876 _Tp_alloc_type& _M_alloc;
877
878 _GLIBCXX20_CONSTEXPR
879 _Guard_elts(pointer __first, size_type __n,
880 _Tp_alloc_type& __a)
881 : _M_first(__first), _M_last(__first + __n), _M_alloc(__a)
882 { }
883
884 _GLIBCXX20_CONSTEXPR
885 ~_Guard_elts()
886 { std::_Destroy(_M_first, _M_last, _M_alloc); }
887
888 private:
889 _Guard_elts(const _Guard_elts&);
890 };
891 _Guard_elts __guard_elts(__new_start + __size, __n, _M_impl);
892
893 std::__uninitialized_move_if_noexcept_a(
894 __old_start, __old_finish, __new_start,
895 _M_get_Tp_allocator());
896
897 __guard_elts._M_first = __old_start;
898 __guard_elts._M_last = __old_finish;
899 }
900 _GLIBCXX_ASAN_ANNOTATE_REINIT;
901 __guard._M_storage = __old_start;
902 __guard._M_len = this->_M_impl._M_end_of_storage - __old_start;
903 }
904 // deallocate should be called before assignments to _M_impl,
905 // to avoid call-clobbering
906
907 this->_M_impl._M_start = __new_start;
908 this->_M_impl._M_finish = __new_start + __size + __n;
909 this->_M_impl._M_end_of_storage = __new_start + __len;
910 }
911 }
912 }
913#pragma GCC diagnostic pop
914
915 template<typename _Tp, typename _Alloc>
916 _GLIBCXX20_CONSTEXPR
917 bool
918 vector<_Tp, _Alloc>::
919 _M_shrink_to_fit()
920 {
921 if (capacity() == size())
922 return false;
923 _GLIBCXX_ASAN_ANNOTATE_REINIT;
924 return std::__shrink_to_fit_aux<vector>::_S_do_it(*this);
925 }
926#endif
927
928 template<typename _Tp, typename _Alloc>
929 template<typename _InputIterator>
930 _GLIBCXX20_CONSTEXPR
931 void
932 vector<_Tp, _Alloc>::
933 _M_range_insert(iterator __pos, _InputIterator __first,
934 _InputIterator __last, std::input_iterator_tag)
935 {
936 if (__pos == end())
937 {
938 for (; __first != __last; ++__first)
939 insert(end(), *__first);
940 }
941 else if (__first != __last)
942 {
943 vector __tmp(__first, __last, _M_get_Tp_allocator());
944 insert(__pos,
945 _GLIBCXX_MAKE_MOVE_ITERATOR(__tmp.begin()),
946 _GLIBCXX_MAKE_MOVE_ITERATOR(__tmp.end()));
947 }
948 }
949
950 template<typename _Tp, typename _Alloc>
951 template<typename _ForwardIterator>
952 _GLIBCXX20_CONSTEXPR
953 void
954 vector<_Tp, _Alloc>::
955 _M_range_insert(iterator __position, _ForwardIterator __first,
956 _ForwardIterator __last, std::forward_iterator_tag)
957 {
958 if (__first != __last)
959 {
960 const size_type __n = std::distance(__first, __last);
961 if (size_type(this->_M_impl._M_end_of_storage
962 - this->_M_impl._M_finish) >= __n)
963 {
964 const size_type __elems_after = end() - __position;
965 pointer __old_finish(this->_M_impl._M_finish);
966 if (__elems_after > __n)
967 {
968 _GLIBCXX_ASAN_ANNOTATE_GROW(__n);
969 std::__uninitialized_move_a(this->_M_impl._M_finish - __n,
970 this->_M_impl._M_finish,
971 this->_M_impl._M_finish,
972 _M_get_Tp_allocator());
973 this->_M_impl._M_finish += __n;
974 _GLIBCXX_ASAN_ANNOTATE_GREW(__n);
975 _GLIBCXX_MOVE_BACKWARD3(__position.base(),
976 __old_finish - __n, __old_finish);
977 std::copy(__first, __last, __position);
978 }
979 else
980 {
981 _ForwardIterator __mid = __first;
982 std::advance(__mid, __elems_after);
983 _GLIBCXX_ASAN_ANNOTATE_GROW(__n);
984 std::__uninitialized_copy_a(__mid, __last,
985 this->_M_impl._M_finish,
986 _M_get_Tp_allocator());
987 this->_M_impl._M_finish += __n - __elems_after;
988 _GLIBCXX_ASAN_ANNOTATE_GREW(__n - __elems_after);
989 std::__uninitialized_move_a(__position.base(),
990 __old_finish,
991 this->_M_impl._M_finish,
992 _M_get_Tp_allocator());
993 this->_M_impl._M_finish += __elems_after;
994 _GLIBCXX_ASAN_ANNOTATE_GREW(__elems_after);
995 std::copy(__first, __mid, __position);
996 }
997 }
998 else
999 {
1000 // Make local copies of these members because the compiler
1001 // thinks the allocator can alter them if 'this' is globally
1002 // reachable.
1003 pointer __old_start = this->_M_impl._M_start;
1004 pointer __old_finish = this->_M_impl._M_finish;
1005
1006 const size_type __len =
1007 _M_check_len(__n, "vector::_M_range_insert");
1008#if __cplusplus < 201103L
1009 if (__len < (__n + (__old_finish - __old_start)))
1010 __builtin_unreachable();
1011#endif
1012
1013 pointer __new_start(this->_M_allocate(__len));
1014 pointer __new_finish(__new_start);
1015 __try
1016 {
1017 __new_finish
1018 = std::__uninitialized_move_if_noexcept_a
1019 (__old_start, __position.base(),
1020 __new_start, _M_get_Tp_allocator());
1021 __new_finish
1022 = std::__uninitialized_copy_a(__first, __last,
1023 __new_finish,
1024 _M_get_Tp_allocator());
1025 __new_finish
1026 = std::__uninitialized_move_if_noexcept_a
1027 (__position.base(), __old_finish,
1028 __new_finish, _M_get_Tp_allocator());
1029 }
1030 __catch(...)
1031 {
1032 std::_Destroy(__new_start, __new_finish,
1033 _M_get_Tp_allocator());
1034 _M_deallocate(__new_start, __len);
1035 __throw_exception_again;
1036 }
1037 std::_Destroy(__old_start, __old_finish,
1038 _M_get_Tp_allocator());
1039 _GLIBCXX_ASAN_ANNOTATE_REINIT;
1040 _M_deallocate(__old_start,
1041 this->_M_impl._M_end_of_storage - __old_start);
1042 this->_M_impl._M_start = __new_start;
1043 this->_M_impl._M_finish = __new_finish;
1044 this->_M_impl._M_end_of_storage = __new_start + __len;
1045 }
1046 }
1047 }
1048
1049#if __glibcxx_containers_ranges // C++ >= 23
1050 template<typename _Tp, typename _Alloc>
1051 template<__detail::__container_compatible_range<_Tp> _Rg>
1052 constexpr auto
1053 vector<_Tp, _Alloc>::
1054 insert_range(const_iterator __pos, _Rg&& __rg)
1055 -> iterator
1056 {
1057 if (__pos == cend())
1058 {
1059 const auto __ins_idx = size();
1060 append_range(std::forward<_Rg>(__rg));
1061 return begin() + __ins_idx;
1062 }
1063
1064 if constexpr (ranges::forward_range<_Rg>)
1065 {
1066 const auto __ins_idx = __pos - cbegin();
1067 // Number of new elements to insert:
1068 const auto __n = size_type(ranges::distance(__rg));
1069 if (__n == 0)
1070 return begin() + __ins_idx;
1071
1072 // Start of existing elements:
1073 pointer __old_start = this->_M_impl._M_start;
1074 // End of existing elements:
1075 pointer __old_finish = this->_M_impl._M_finish;
1076 // Insertion point:
1077 pointer __ins = __old_start + __ins_idx;
1078 // Number of elements that can fit in unused capacity:
1079 const auto __cap = this->_M_impl._M_end_of_storage - __old_finish;
1080 if (__cap >= __n)
1081 {
1082 // Number of existing elements after insertion point:
1083 const size_type __elems_after = cend() - __pos;
1084 if (__elems_after > __n)
1085 {
1086 _GLIBCXX_ASAN_ANNOTATE_GROW(__n);
1087 std::__uninitialized_move_a(__old_finish - __n,
1088 __old_finish,
1089 __old_finish,
1090 _M_get_Tp_allocator());
1091 this->_M_impl._M_finish += __n;
1092 _GLIBCXX_ASAN_ANNOTATE_GREW(__n);
1093 std::move_backward(__ins, __old_finish - __n, __old_finish);
1094 ranges::copy(__rg, __ins);
1095 }
1096 else
1097 {
1098 auto __first = ranges::begin(__rg);
1099 const auto __last = ranges::end(__rg);
1100 auto __mid = ranges::next(__first, __elems_after);
1101 _GLIBCXX_ASAN_ANNOTATE_GROW(__n);
1102 _Base::_M_append_range(ranges::subrange(__mid, __last));
1103 _GLIBCXX_ASAN_ANNOTATE_GREW(__n - __elems_after);
1104 std::__uninitialized_move_a(__ins, __old_finish,
1105 this->_M_impl._M_finish,
1106 _M_get_Tp_allocator());
1107 this->_M_impl._M_finish += __elems_after;
1108 _GLIBCXX_ASAN_ANNOTATE_GREW(__elems_after);
1109 ranges::copy(__first, __mid, __ins);
1110 }
1111 }
1112 else // Reallocate
1113 {
1114 const size_type __len
1115 = _M_check_len(__n, "vector::insert_range");
1116
1117 struct _Guard : _Guard_alloc
1118 {
1119 // End of elements to destroy:
1120 pointer _M_finish = _Guard_alloc::_M_storage;
1121
1122 using _Guard_alloc::_Guard_alloc;
1123
1124 constexpr
1125 ~_Guard()
1126 {
1127 std::_Destroy(this->_M_storage, _M_finish,
1128 this->_M_vect._M_get_Tp_allocator());
1129 }
1130 };
1131
1132 // Allocate new storage:
1133 pointer __new_start(this->_M_allocate(__len));
1134 _Guard __guard(__new_start, __len, *this);
1135
1136 auto& __alloc = _M_get_Tp_allocator();
1137
1138 // Populate the new storage in three steps. After each step,
1139 // __guard owns the new storage and any elements that have
1140 // been constructed there.
1141
1142 // Move elements from before insertion point to new storage:
1143 __guard._M_finish
1144 = std::__uninitialized_move_if_noexcept_a(
1145 __old_start, __ins, __new_start, __alloc);
1146
1147 // Append new elements to new storage:
1148 _Base::_M_append_range_to(__rg, __guard._M_finish);
1149
1150 // Move elements from after insertion point to new storage:
1151 __guard._M_finish
1152 = std::__uninitialized_move_if_noexcept_a(
1153 __ins, __old_finish, __guard._M_finish, __alloc);
1154
1155 _GLIBCXX_ASAN_ANNOTATE_REINIT; // Creates _Asan::_Reinit.
1156
1157 // All elements are in the new storage, exchange ownership
1158 // with __guard so that it cleans up the old storage:
1159 this->_M_impl._M_start = __guard._M_storage;
1160 this->_M_impl._M_finish = __guard._M_finish;
1161 this->_M_impl._M_end_of_storage = __new_start + __len;
1162 __guard._M_storage = __old_start;
1163 __guard._M_finish = __old_finish;
1164 __guard._M_len = (__old_finish - __old_start) + __cap;
1165 // _Asan::_Reinit destructor marks unused capacity.
1166 // _Guard destructor destroys [old_start,old_finish).
1167 // _Guard_alloc destructor frees [old_start,old_start+len).
1168 }
1169 return begin() + __ins_idx;
1170 }
1171 else
1172 return insert_range(__pos, vector(from_range, std::forward<_Rg>(__rg),
1173 _M_get_Tp_allocator()));
1174 }
1175#endif // containers_ranges
1176
1177 // vector<bool>
1178 template<typename _Alloc>
1179 _GLIBCXX20_CONSTEXPR
1180 void
1181 vector<bool, _Alloc>::
1182 _M_reallocate(size_type __n)
1183 {
1184 const iterator __begin = begin(), __end = end();
1185 if (size_type(__end - __begin) > __n)
1186 __builtin_unreachable();
1187 _Bit_pointer __q = this->_M_allocate(__n);
1188 iterator __start(std::__addressof(*__q), 0);
1189 iterator __finish(_M_copy_aligned(__begin, __end, __start));
1190 this->_M_deallocate();
1191 this->_M_impl._M_start = __start;
1192 this->_M_impl._M_finish = __finish;
1193 this->_M_impl._M_end_of_storage = __q + _S_nword(__n);
1194 }
1195
1196 template<typename _Alloc>
1197 _GLIBCXX20_CONSTEXPR
1198 void
1199 vector<bool, _Alloc>::
1200 _M_fill_insert(iterator __position, size_type __n, bool __x)
1201 {
1202 if (__n == 0)
1203 return;
1204 if (capacity() - size() >= __n)
1205 {
1206 std::copy_backward(__position, end(),
1207 this->_M_impl._M_finish + difference_type(__n));
1208 std::fill(__position, __position + difference_type(__n), __x);
1209 this->_M_impl._M_finish += difference_type(__n);
1210 }
1211 else
1212 {
1213 const size_type __len =
1214 _M_check_len(__n, "vector<bool>::_M_fill_insert");
1215 iterator __begin = begin(), __end = end();
1216 _Bit_pointer __q = this->_M_allocate(__len);
1217 iterator __start(std::__addressof(*__q), 0);
1218 iterator __i = _M_copy_aligned(__begin, __position, __start);
1219 std::fill(__i, __i + difference_type(__n), __x);
1220 iterator __finish = std::copy(__position, __end,
1221 __i + difference_type(__n));
1222 this->_M_deallocate();
1223 this->_M_impl._M_end_of_storage = __q + _S_nword(__len);
1224 this->_M_impl._M_start = __start;
1225 this->_M_impl._M_finish = __finish;
1226 }
1227 }
1228
1229 template<typename _Alloc>
1230 template<typename _ForwardIterator>
1231 _GLIBCXX20_CONSTEXPR
1232 void
1233 vector<bool, _Alloc>::
1234 _M_insert_range(iterator __position, _ForwardIterator __first,
1235 _ForwardIterator __last, std::forward_iterator_tag)
1236 {
1237 if (__first != __last)
1238 {
1239 size_type __n = std::distance(__first, __last);
1240 if (capacity() - size() >= __n)
1241 {
1242 std::copy_backward(__position, end(),
1243 this->_M_impl._M_finish
1244 + difference_type(__n));
1245 std::copy(__first, __last, __position);
1246 this->_M_impl._M_finish += difference_type(__n);
1247 }
1248 else
1249 {
1250 const size_type __len =
1251 _M_check_len(__n, "vector<bool>::_M_insert_range");
1252 const iterator __begin = begin(), __end = end();
1253 _Bit_pointer __q = this->_M_allocate(__len);
1254 iterator __start(std::__addressof(*__q), 0);
1255 iterator __i = _M_copy_aligned(__begin, __position, __start);
1256 __i = std::copy(__first, __last, __i);
1257 iterator __finish = std::copy(__position, __end, __i);
1258 this->_M_deallocate();
1259 this->_M_impl._M_end_of_storage = __q + _S_nword(__len);
1260 this->_M_impl._M_start = __start;
1261 this->_M_impl._M_finish = __finish;
1262 }
1263 }
1264 }
1265
1266 template<typename _Alloc>
1267 _GLIBCXX20_CONSTEXPR
1268 void
1269 vector<bool, _Alloc>::
1270 _M_insert_aux(iterator __position, bool __x)
1271 {
1272 if (this->_M_impl._M_finish._M_p != this->_M_impl._M_end_addr())
1273 {
1274 std::copy_backward(__position, this->_M_impl._M_finish,
1275 this->_M_impl._M_finish + 1);
1276 *__position = __x;
1277 ++this->_M_impl._M_finish;
1278 }
1279 else
1280 {
1281 const size_type __len =
1282 _M_check_len(size_type(1), "vector<bool>::_M_insert_aux");
1283 _Bit_pointer __q = this->_M_allocate(__len);
1284 iterator __start(std::__addressof(*__q), 0);
1285 iterator __i = _M_copy_aligned(begin(), __position, __start);
1286 *__i++ = __x;
1287 iterator __finish = std::copy(__position, end(), __i);
1288 this->_M_deallocate();
1289 this->_M_impl._M_end_of_storage = __q + _S_nword(__len);
1290 this->_M_impl._M_start = __start;
1291 this->_M_impl._M_finish = __finish;
1292 }
1293 }
1294
1295 template<typename _Alloc>
1296 _GLIBCXX20_CONSTEXPR
1297 typename vector<bool, _Alloc>::iterator
1298 vector<bool, _Alloc>::
1299 _M_erase(iterator __position)
1300 {
1301 if (__position + 1 != end())
1302 std::copy(__position + 1, end(), __position);
1303 --this->_M_impl._M_finish;
1304 return __position;
1305 }
1306
1307 template<typename _Alloc>
1308 _GLIBCXX20_CONSTEXPR
1309 typename vector<bool, _Alloc>::iterator
1310 vector<bool, _Alloc>::
1311 _M_erase(iterator __first, iterator __last)
1312 {
1313 if (__first != __last)
1314 _M_erase_at_end(std::copy(__last, end(), __first));
1315 return __first;
1316 }
1317
1318#if __cplusplus >= 201103L
1319 template<typename _Alloc>
1320 _GLIBCXX20_CONSTEXPR
1321 bool
1322 vector<bool, _Alloc>::
1323 _M_shrink_to_fit()
1324 {
1325 if (capacity() - size() < int(_S_word_bit))
1326 return false;
1327 __try
1328 {
1329 if (size_type __n = size())
1330 _M_reallocate(__n);
1331 else
1332 {
1333 this->_M_deallocate();
1334 this->_M_impl._M_reset();
1335 }
1336 return true;
1337 }
1338 __catch(...)
1339 { return false; }
1340 }
1341#endif
1342
1343_GLIBCXX_END_NAMESPACE_CONTAINER
1344_GLIBCXX_END_NAMESPACE_VERSION
1345} // namespace std
1346
1347#if __cplusplus >= 201103L
1348
1349namespace std _GLIBCXX_VISIBILITY(default)
1350{
1351_GLIBCXX_BEGIN_NAMESPACE_VERSION
1352
1353 template<typename _Alloc>
1354 size_t
1355 hash<_GLIBCXX_STD_C::vector<bool, _Alloc>>::
1356 operator()(const _GLIBCXX_STD_C::vector<bool, _Alloc>& __b) const noexcept
1357 {
1358 size_t __hash = 0;
1359 const size_t __words = __b.size() / _S_word_bit;
1360 if (__words)
1361 {
1362 const size_t __clength = __words * sizeof(_Bit_type);
1363 __hash = std::_Hash_impl::hash(__b._M_impl._M_start._M_p, __clength);
1364 }
1365
1366 const size_t __extrabits = __b.size() % _S_word_bit;
1367 if (__extrabits)
1368 {
1369 _Bit_type __hiword = *__b._M_impl._M_finish._M_p;
1370 __hiword &= ~((~static_cast<_Bit_type>(0)) << __extrabits);
1371
1372 const size_t __clength
1373 = (__extrabits + __CHAR_BIT__ - 1) / __CHAR_BIT__;
1374 if (__words)
1375 __hash = std::_Hash_impl::hash(&__hiword, __clength, __hash);
1376 else
1377 __hash = std::_Hash_impl::hash(&__hiword, __clength);
1378 }
1379
1380 return __hash;
1381 }
1382
1383_GLIBCXX_END_NAMESPACE_VERSION
1384} // namespace std
1385
1386#endif // C++11
1387
1388#undef _GLIBCXX_ASAN_ANNOTATE_REINIT
1389#undef _GLIBCXX_ASAN_ANNOTATE_GROW
1390#undef _GLIBCXX_ASAN_ANNOTATE_GREW
1391#undef _GLIBCXX_ASAN_ANNOTATE_SHRINK
1392
1393#endif /* _VECTOR_TCC */
std::move
constexpr std::remove_reference< _Tp >::type && move(_Tp &&__t) noexcept
Convert a value to an rvalue.
Definition move.h:138
std::__addressof
constexpr _Tp * __addressof(_Tp &__r) noexcept
Same as C++11 std::addressof.
Definition move.h:52
std::forward
constexpr _Tp && forward(typename std::remove_reference< _Tp >::type &__t) noexcept
Forward an lvalue.
Definition move.h:72
std::end
_Tp * end(valarray< _Tp > &__va) noexcept
Return an iterator pointing to one past the last element of the valarray.
Definition valarray:1251
std::begin
_Tp * begin(valarray< _Tp > &__va) noexcept
Return an iterator pointing to the first element of the valarray.
Definition valarray:1229
std::move_backward
constexpr _BI2 move_backward(_BI1 __first, _BI1 __last, _BI2 __result)
Moves the range [first,last) into result.
Definition stl_algobase.h:873
std::__iterator_category
constexpr iterator_traits< _Iter >::iterator_category __iterator_category(const _Iter &)
Definition stl_iterator_base_types.h:241
std
ISO C++ entities toplevel namespace is std.
std::distance
constexpr iterator_traits< _InputIterator >::difference_type distance(_InputIterator __first, _InputIterator __last)
A generalization of pointer arithmetic.
Definition stl_iterator_base_funcs.h:172
std::cend
constexpr auto cend(const _Container &__cont) noexcept(noexcept(std::end(__cont))) -> decltype(std::end(__cont))
Return an iterator pointing to one past the last element of the const container.
Definition range_access.h:144
std::size
constexpr auto size(const _Container &__cont) noexcept(noexcept(__cont.size())) -> decltype(__cont.size())
Return the size of a container.
Definition range_access.h:274
std::advance
constexpr void advance(_InputIterator &__i, _Distance __n)
A generalization of pointer arithmetic.
Definition stl_iterator_base_funcs.h:262
std::cbegin
constexpr auto cbegin(const _Container &__cont) noexcept(noexcept(std::begin(__cont))) -> decltype(std::begin(__cont))
Return an iterator pointing to the first element of the const container.
Definition range_access.h:132
std::_Destroy
constexpr void _Destroy(_ForwardIterator __first, _ForwardIterator __last)
Definition stl_construct.h:219
std::hash
Primary class template hash.
Definition functional_hash.h:106
std::ranges::subrange
The ranges::subrange class template.
Definition ranges_util.h:270
std::forward_iterator_tag
Forward iterators support a superset of input iterator operations.
Definition stl_iterator_base_types.h:101
std::iterator
Common iterator class.
Definition stl_iterator_base_types.h:130
std::vector
A standard container which offers fixed time access to individual elements in any order.
Definition stl_vector.h:461
std::vector::insert
constexpr iterator insert(const_iterator __position, const value_type &__x)
Inserts given value into vector before specified iterator.
Definition vector.tcc:139
std::vector::end
constexpr iterator end() noexcept
Definition stl_vector.h:1008
std::vector::vector
vector()=default
Creates a vector with no elements.
std::vector::begin
constexpr iterator begin() noexcept
Definition stl_vector.h:988
std::vector::capacity
constexpr size_type capacity() const noexcept
Definition stl_vector.h:1198
std::vector::reserve
constexpr void reserve(size_type __n)
Attempt to preallocate enough memory for specified number of elements.
Definition vector.tcc:71
std::vector::_M_allocate_and_copy
constexpr pointer _M_allocate_and_copy(size_type __n, _ForwardIterator __first, _ForwardIterator __last)
Definition stl_vector.h:1897
std::vector::clear
constexpr void clear() noexcept
Definition stl_vector.h:1853
std::vector::size
constexpr size_type size() const noexcept
Definition stl_vector.h:1107
std::vector::operator=
constexpr vector & operator=(const vector &__x)
Vector assignment operator.
Definition vector.tcc:215
std::vector::max_size
constexpr size_type max_size() const noexcept
Definition stl_vector.h:1118