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