1// Debugging vector implementation -*- C++ -*-
2
3// Copyright (C) 2003-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/** @file debug/vector
26 * This file is a GNU debug extension to the Standard C++ Library.
27 */
28
29#ifndef _GLIBCXX_DEBUG_VECTOR
30#define _GLIBCXX_DEBUG_VECTOR 1
31
32#ifdef _GLIBCXX_SYSHDR
33#pragma GCC system_header
34#endif
35
36#include <bits/c++config.h>
37namespace std _GLIBCXX_VISIBILITY(default) { namespace __debug {
38 template<typename _Tp, typename _Allocator> class vector;
39} } // namespace std::__debug
40
41#include <vector>
42#include <debug/safe_sequence.h>
43#include <debug/safe_container.h>
44#include <debug/safe_iterator.h>
45
46namespace __gnu_debug
47{
48 /** @brief Base class for Debug Mode vector.
49 *
50 * Adds information about the guaranteed capacity, which is useful for
51 * detecting code which relies on non-portable implementation details of
52 * the libstdc++ reallocation policy.
53 */
54 template<typename _SafeSequence,
55 typename _BaseSequence>
56 class _Safe_vector
57 {
58 typedef typename _BaseSequence::size_type size_type;
59
60 _GLIBCXX20_CONSTEXPR
61 const _SafeSequence&
62 _M_seq() const { return *static_cast<const _SafeSequence*>(this); }
63
64 protected:
65 _GLIBCXX20_CONSTEXPR
66 _Safe_vector() _GLIBCXX_NOEXCEPT
67 : _M_guaranteed_capacity(0)
68 { _M_update_guaranteed_capacity(); }
69
70 _GLIBCXX20_CONSTEXPR
71 _Safe_vector(const _Safe_vector&) _GLIBCXX_NOEXCEPT
72 : _M_guaranteed_capacity(0)
73 { _M_update_guaranteed_capacity(); }
74
75 _GLIBCXX20_CONSTEXPR
76 _Safe_vector(size_type __n) _GLIBCXX_NOEXCEPT
77 : _M_guaranteed_capacity(__n)
78 { }
79
80 _GLIBCXX20_CONSTEXPR
81 _Safe_vector&
82 operator=(const _Safe_vector&) _GLIBCXX_NOEXCEPT
83 {
84 _M_update_guaranteed_capacity();
85 return *this;
86 }
87
88#if __cplusplus >= 201103L
89 _GLIBCXX20_CONSTEXPR
90 _Safe_vector(_Safe_vector&& __x) noexcept
91 : _Safe_vector()
92 { __x._M_guaranteed_capacity = 0; }
93
94 _GLIBCXX20_CONSTEXPR
95 _Safe_vector&
96 operator=(_Safe_vector&& __x) noexcept
97 {
98 _M_update_guaranteed_capacity();
99 __x._M_guaranteed_capacity = 0;
100 return *this;
101 }
102#endif
103
104 size_type _M_guaranteed_capacity;
105
106 bool
107 _M_requires_reallocation(size_type __elements) const _GLIBCXX_NOEXCEPT
108 { return __elements > _M_seq().capacity(); }
109
110 _GLIBCXX20_CONSTEXPR
111 void
112 _M_update_guaranteed_capacity() _GLIBCXX_NOEXCEPT
113 {
114 if (_M_seq().size() > _M_guaranteed_capacity)
115 _M_guaranteed_capacity = _M_seq().size();
116 }
117 };
118}
119
120namespace std _GLIBCXX_VISIBILITY(default)
121{
122namespace __debug
123{
124 /// Class std::vector with safety/checking/debug instrumentation.
125 template<typename _Tp,
126 typename _Allocator = std::allocator<_Tp> >
127 class vector
128 : public __gnu_debug::_Safe_container<
129 vector<_Tp, _Allocator>, _Allocator, __gnu_debug::_Safe_sequence>,
130 public _GLIBCXX_STD_C::vector<_Tp, _Allocator>,
131 public __gnu_debug::_Safe_vector<
132 vector<_Tp, _Allocator>,
133 _GLIBCXX_STD_C::vector<_Tp, _Allocator> >
134 {
135 typedef _GLIBCXX_STD_C::vector<_Tp, _Allocator> _Base;
136 typedef __gnu_debug::_Safe_container<
137 vector, _Allocator, __gnu_debug::_Safe_sequence> _Safe;
138 typedef __gnu_debug::_Safe_vector<vector, _Base> _Safe_vector;
139
140 typedef typename _Base::iterator _Base_iterator;
141 typedef typename _Base::const_iterator _Base_const_iterator;
142 typedef __gnu_debug::_Equal_to<_Base_const_iterator> _Equal;
143
144 template<typename _ItT, typename _SeqT, typename _CatT>
145 friend class ::__gnu_debug::_Safe_iterator;
146
147 // Reference wrapper for base class. Disambiguates vector(const _Base&)
148 // from copy constructor by requiring a user-defined conversion.
149 // See PR libstdc++/90102.
150 struct _Base_ref
151 {
152 _Base_ref(const _Base& __r) : _M_ref(__r) { }
153
154 const _Base& _M_ref;
155 };
156
157 public:
158 typedef typename _Base::reference reference;
159 typedef typename _Base::const_reference const_reference;
160
161 typedef __gnu_debug::_Safe_iterator<
162 _Base_iterator, vector> iterator;
163 typedef __gnu_debug::_Safe_iterator<
164 _Base_const_iterator, vector> const_iterator;
165
166 typedef typename _Base::size_type size_type;
167 typedef typename _Base::difference_type difference_type;
168
169 typedef _Tp value_type;
170 typedef _Allocator allocator_type;
171 typedef typename _Base::pointer pointer;
172 typedef typename _Base::const_pointer const_pointer;
173 typedef std::reverse_iterator<iterator> reverse_iterator;
174 typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
175
176 // 23.2.4.1 construct/copy/destroy:
177
178#if __cplusplus < 201103L
179 vector() _GLIBCXX_NOEXCEPT
180 : _Base() { }
181#else
182 vector() = default;
183#endif
184
185 _GLIBCXX20_CONSTEXPR
186 explicit
187 vector(const _Allocator& __a) _GLIBCXX_NOEXCEPT
188 : _Base(__a) { }
189
190#if __cplusplus >= 201103L
191 _GLIBCXX20_CONSTEXPR
192 explicit
193 vector(size_type __n, const _Allocator& __a = _Allocator())
194 : _Base(__n, __a), _Safe_vector(__n) { }
195
196 _GLIBCXX20_CONSTEXPR
197 vector(size_type __n, const __type_identity_t<_Tp>& __value,
198 const _Allocator& __a = _Allocator())
199 : _Base(__n, __value, __a) { }
200#else
201 explicit
202 vector(size_type __n, const _Tp& __value = _Tp(),
203 const _Allocator& __a = _Allocator())
204 : _Base(__n, __value, __a) { }
205#endif
206
207#if __cplusplus >= 201103L
208 template<class _InputIterator,
209 typename = std::_RequireInputIter<_InputIterator>>
210#else
211 template<class _InputIterator>
212#endif
213 _GLIBCXX20_CONSTEXPR
214 vector(_InputIterator __first, _InputIterator __last,
215 const _Allocator& __a = _Allocator())
216 : _Base(__gnu_debug::__base(std::__is_constant_evaluated() ? __first
217 : __glibcxx_check_valid_constructor_range(__first, __last)),
218 __gnu_debug::__base(__last), __a) { }
219
220#if __cplusplus < 201103L
221 vector(const vector& __x)
222 : _Base(__x) { }
223
224 ~vector() _GLIBCXX_NOEXCEPT { }
225#else
226 vector(const vector&) = default;
227 vector(vector&&) = default;
228
229 _GLIBCXX20_CONSTEXPR
230 vector(const vector& __x, const __type_identity_t<allocator_type>& __a)
231 : _Base(__x, __a) { }
232
233 _GLIBCXX20_CONSTEXPR
234 vector(vector&& __x, const __type_identity_t<allocator_type>& __a)
235 noexcept(
236 std::is_nothrow_constructible<_Base,
237 _Base, const allocator_type&>::value )
238 : _Safe(std::move(__x), __a),
239 _Base(std::move(__x), __a),
240 _Safe_vector(std::move(__x)) { }
241
242 _GLIBCXX20_CONSTEXPR
243 vector(initializer_list<value_type> __l,
244 const allocator_type& __a = allocator_type())
245 : _Base(__l, __a) { }
246
247#if __glibcxx_containers_ranges // C++ >= 23
248 /**
249 * @brief Construct a vector from a range.
250 * @since C++23
251 */
252 template<std::__detail::__container_compatible_range<_Tp> _Rg>
253 constexpr
254 vector(std::from_range_t __t, _Rg&& __rg,
255 const allocator_type& __a = allocator_type())
256 : _Base(__t, std::forward<_Rg>(__rg), __a)
257 { }
258#endif
259
260 ~vector() = default;
261#endif
262
263 /// Construction from a normal-mode vector
264 _GLIBCXX20_CONSTEXPR
265 vector(_Base_ref __x)
266 : _Base(__x._M_ref) { }
267
268#if __cplusplus >= 201103L
269 vector&
270 operator=(const vector&) = default;
271
272 vector&
273 operator=(vector&&) = default;
274
275 _GLIBCXX20_CONSTEXPR
276 vector&
277 operator=(initializer_list<value_type> __l)
278 {
279 _Base::operator=(__l);
280 if (!std::__is_constant_evaluated())
281 {
282 this->_M_invalidate_all();
283 this->_M_update_guaranteed_capacity();
284 }
285 return *this;
286 }
287#endif
288
289#if __cplusplus >= 201103L
290 template<typename _InputIterator,
291 typename = std::_RequireInputIter<_InputIterator>>
292#else
293 template<typename _InputIterator>
294#endif
295 _GLIBCXX20_CONSTEXPR
296 void
297 assign(_InputIterator __first, _InputIterator __last)
298 {
299 if (std::__is_constant_evaluated())
300 return _Base::assign(__gnu_debug::__unsafe(__first),
301 __gnu_debug::__unsafe(__last));
302
303 typename __gnu_debug::_Distance_traits<_InputIterator>::__type __dist;
304 __glibcxx_check_valid_range2(__first, __last, __dist);
305
306 if (__dist.second >= __gnu_debug::__dp_sign)
307 _Base::assign(__gnu_debug::__unsafe(__first),
308 __gnu_debug::__unsafe(__last));
309 else
310 _Base::assign(__first, __last);
311
312 this->_M_invalidate_all();
313 this->_M_update_guaranteed_capacity();
314 }
315
316 _GLIBCXX20_CONSTEXPR
317 void
318 assign(size_type __n, const _Tp& __u)
319 {
320 _Base::assign(__n, __u);
321 if (!std::__is_constant_evaluated())
322 {
323 this->_M_invalidate_all();
324 this->_M_update_guaranteed_capacity();
325 }
326 }
327
328#if __cplusplus >= 201103L
329 _GLIBCXX20_CONSTEXPR
330 void
331 assign(initializer_list<value_type> __l)
332 {
333 _Base::assign(__l);
334 if (!std::__is_constant_evaluated())
335 {
336 this->_M_invalidate_all();
337 this->_M_update_guaranteed_capacity();
338 }
339 }
340#endif
341
342 using _Base::get_allocator;
343
344 // iterators:
345 _GLIBCXX_NODISCARD
346 _GLIBCXX20_CONSTEXPR
347 iterator
348 begin() _GLIBCXX_NOEXCEPT
349 { return iterator(_Base::begin(), this); }
350
351 _GLIBCXX_NODISCARD
352 _GLIBCXX20_CONSTEXPR
353 const_iterator
354 begin() const _GLIBCXX_NOEXCEPT
355 { return const_iterator(_Base::begin(), this); }
356
357 _GLIBCXX_NODISCARD
358 _GLIBCXX20_CONSTEXPR
359 iterator
360 end() _GLIBCXX_NOEXCEPT
361 { return iterator(_Base::end(), this); }
362
363 _GLIBCXX_NODISCARD
364 _GLIBCXX20_CONSTEXPR
365 const_iterator
366 end() const _GLIBCXX_NOEXCEPT
367 { return const_iterator(_Base::end(), this); }
368
369 _GLIBCXX_NODISCARD
370 _GLIBCXX20_CONSTEXPR
371 reverse_iterator
372 rbegin() _GLIBCXX_NOEXCEPT
373 { return reverse_iterator(end()); }
374
375 _GLIBCXX_NODISCARD
376 _GLIBCXX20_CONSTEXPR
377 const_reverse_iterator
378 rbegin() const _GLIBCXX_NOEXCEPT
379 { return const_reverse_iterator(end()); }
380
381 _GLIBCXX_NODISCARD
382 _GLIBCXX20_CONSTEXPR
383 reverse_iterator
384 rend() _GLIBCXX_NOEXCEPT
385 { return reverse_iterator(begin()); }
386
387 _GLIBCXX_NODISCARD
388 _GLIBCXX20_CONSTEXPR
389 const_reverse_iterator
390 rend() const _GLIBCXX_NOEXCEPT
391 { return const_reverse_iterator(begin()); }
392
393#if __cplusplus >= 201103L
394 [[__nodiscard__]]
395 _GLIBCXX20_CONSTEXPR
396 const_iterator
397 cbegin() const noexcept
398 { return const_iterator(_Base::begin(), this); }
399
400 [[__nodiscard__]]
401 _GLIBCXX20_CONSTEXPR
402 const_iterator
403 cend() const noexcept
404 { return const_iterator(_Base::end(), this); }
405
406 [[__nodiscard__]]
407 _GLIBCXX20_CONSTEXPR
408 const_reverse_iterator
409 crbegin() const noexcept
410 { return const_reverse_iterator(end()); }
411
412 [[__nodiscard__]]
413 _GLIBCXX20_CONSTEXPR
414 const_reverse_iterator
415 crend() const noexcept
416 { return const_reverse_iterator(begin()); }
417#endif
418
419 // 23.2.4.2 capacity:
420 using _Base::size;
421 using _Base::max_size;
422
423#if __cplusplus >= 201103L
424 _GLIBCXX20_CONSTEXPR
425 void
426 resize(size_type __sz)
427 {
428 if (std::__is_constant_evaluated())
429 return _Base::resize(__sz);
430
431 bool __realloc = this->_M_requires_reallocation(__sz);
432 if (__sz < this->size())
433 this->_M_invalidate_after_nth(n: __sz);
434 _Base::resize(__sz);
435 if (__realloc)
436 this->_M_invalidate_all();
437 this->_M_update_guaranteed_capacity();
438 }
439
440 _GLIBCXX20_CONSTEXPR
441 void
442 resize(size_type __sz, const _Tp& __c)
443 {
444 if (std::__is_constant_evaluated())
445 return _Base::resize(__sz, __c);
446
447 bool __realloc = this->_M_requires_reallocation(__sz);
448 if (__sz < this->size())
449 this->_M_invalidate_after_nth(n: __sz);
450 _Base::resize(__sz, __c);
451 if (__realloc)
452 this->_M_invalidate_all();
453 this->_M_update_guaranteed_capacity();
454 }
455#else
456 void
457 resize(size_type __sz, _Tp __c = _Tp())
458 {
459 bool __realloc = this->_M_requires_reallocation(__sz);
460 if (__sz < this->size())
461 this->_M_invalidate_after_nth(__sz);
462 _Base::resize(__sz, __c);
463 if (__realloc)
464 this->_M_invalidate_all();
465 this->_M_update_guaranteed_capacity();
466 }
467#endif
468
469#if __cplusplus >= 201103L
470 _GLIBCXX20_CONSTEXPR
471 void
472 shrink_to_fit()
473 {
474 if (std::__is_constant_evaluated())
475 return _Base::shrink_to_fit();
476
477 if (_Base::_M_shrink_to_fit())
478 {
479 this->_M_guaranteed_capacity = _Base::capacity();
480 this->_M_invalidate_all();
481 }
482 }
483#endif
484
485 _GLIBCXX_NODISCARD
486 _GLIBCXX20_CONSTEXPR
487 size_type
488 capacity() const _GLIBCXX_NOEXCEPT
489 {
490 if (std::__is_constant_evaluated())
491 return _Base::capacity();
492
493#ifdef _GLIBCXX_DEBUG_PEDANTIC
494 return this->_M_guaranteed_capacity;
495#else
496 return _Base::capacity();
497#endif
498 }
499
500 using _Base::empty;
501
502 _GLIBCXX20_CONSTEXPR
503 void
504 reserve(size_type __n)
505 {
506 if (std::__is_constant_evaluated())
507 return _Base::reserve(__n);
508
509 bool __realloc = this->_M_requires_reallocation(__n);
510 _Base::reserve(__n);
511 if (__n > this->_M_guaranteed_capacity)
512 this->_M_guaranteed_capacity = __n;
513 if (__realloc)
514 this->_M_invalidate_all();
515 }
516
517 // element access:
518 _GLIBCXX_NODISCARD
519 _GLIBCXX20_CONSTEXPR
520 reference
521 operator[](size_type __n) _GLIBCXX_NOEXCEPT
522 {
523 __glibcxx_check_subscript(__n);
524 return _Base::operator[](__n);
525 }
526
527 _GLIBCXX_NODISCARD
528 _GLIBCXX20_CONSTEXPR
529 const_reference
530 operator[](size_type __n) const _GLIBCXX_NOEXCEPT
531 {
532 __glibcxx_check_subscript(__n);
533 return _Base::operator[](__n);
534 }
535
536 using _Base::at;
537
538 _GLIBCXX_NODISCARD
539 _GLIBCXX20_CONSTEXPR
540 reference
541 front() _GLIBCXX_NOEXCEPT
542 {
543 __glibcxx_check_nonempty();
544 return _Base::front();
545 }
546
547 _GLIBCXX_NODISCARD
548 _GLIBCXX20_CONSTEXPR
549 const_reference
550 front() const _GLIBCXX_NOEXCEPT
551 {
552 __glibcxx_check_nonempty();
553 return _Base::front();
554 }
555
556 _GLIBCXX_NODISCARD
557 _GLIBCXX20_CONSTEXPR
558 reference
559 back() _GLIBCXX_NOEXCEPT
560 {
561 __glibcxx_check_nonempty();
562 return _Base::back();
563 }
564
565 _GLIBCXX_NODISCARD
566 _GLIBCXX20_CONSTEXPR
567 const_reference
568 back() const _GLIBCXX_NOEXCEPT
569 {
570 __glibcxx_check_nonempty();
571 return _Base::back();
572 }
573
574 // _GLIBCXX_RESOLVE_LIB_DEFECTS
575 // DR 464. Suggestion for new member functions in standard containers.
576 using _Base::data;
577
578 // 23.2.4.3 modifiers:
579 _GLIBCXX20_CONSTEXPR
580 void
581 push_back(const _Tp& __x)
582 {
583 if (std::__is_constant_evaluated())
584 return _Base::push_back(__x);
585
586 bool __realloc = this->_M_requires_reallocation(this->size() + 1);
587 _Base::push_back(__x);
588 if (__realloc)
589 this->_M_invalidate_all();
590 this->_M_update_guaranteed_capacity();
591 }
592
593#if __cplusplus >= 201103L
594 template<typename _Up = _Tp>
595 _GLIBCXX20_CONSTEXPR
596 typename __gnu_cxx::__enable_if<!std::__are_same<_Up, bool>::__value,
597 void>::__type
598 push_back(_Tp&& __x)
599 { emplace_back(std::move(__x)); }
600
601 template<typename... _Args>
602 _GLIBCXX20_CONSTEXPR
603#if __cplusplus > 201402L
604 reference
605#else
606 void
607#endif
608 emplace_back(_Args&&... __args)
609 {
610 if (std::__is_constant_evaluated())
611 return _Base::emplace_back(std::forward<_Args>(__args)...);
612
613 bool __realloc = this->_M_requires_reallocation(this->size() + 1);
614 _Base::emplace_back(std::forward<_Args>(__args)...);
615 if (__realloc)
616 this->_M_invalidate_all();
617 this->_M_update_guaranteed_capacity();
618#if __cplusplus > 201402L
619 return back();
620#endif
621 }
622#endif
623
624 _GLIBCXX20_CONSTEXPR
625 void
626 pop_back() _GLIBCXX_NOEXCEPT
627 {
628 if (!std::__is_constant_evaluated())
629 {
630 __glibcxx_check_nonempty();
631 this->_M_invalidate_if(_Equal(--_Base::end()));
632 }
633 _Base::pop_back();
634 }
635
636#if __cplusplus >= 201103L
637 template<typename... _Args>
638 _GLIBCXX20_CONSTEXPR
639 iterator
640 emplace(const_iterator __position, _Args&&... __args)
641 {
642 if (std::__is_constant_evaluated())
643 return iterator(_Base::emplace(__position.base(),
644 std::forward<_Args>(__args)...),
645 this);
646
647 __glibcxx_check_insert(__position);
648 bool __realloc = this->_M_requires_reallocation(this->size() + 1);
649 difference_type __offset = __position.base() - _Base::cbegin();
650 _Base_iterator __res = _Base::emplace(__position.base(),
651 std::forward<_Args>(__args)...);
652 if (__realloc)
653 this->_M_invalidate_all();
654 else
655 this->_M_invalidate_after_nth(n: __offset);
656 this->_M_update_guaranteed_capacity();
657 return { __res, this };
658 }
659#endif
660
661 _GLIBCXX20_CONSTEXPR
662 iterator
663#if __cplusplus >= 201103L
664 insert(const_iterator __position, const _Tp& __x)
665#else
666 insert(iterator __position, const _Tp& __x)
667#endif
668 {
669 if (std::__is_constant_evaluated())
670 return iterator(_Base::insert(__position.base(), __x), this);
671
672 __glibcxx_check_insert(__position);
673 bool __realloc = this->_M_requires_reallocation(this->size() + 1);
674 difference_type __offset = __position.base() - _Base::begin();
675 _Base_iterator __res = _Base::insert(__position.base(), __x);
676 if (__realloc)
677 this->_M_invalidate_all();
678 else
679 this->_M_invalidate_after_nth(n: __offset);
680 this->_M_update_guaranteed_capacity();
681 return iterator(__res, this);
682 }
683
684#if __cplusplus >= 201103L
685 template<typename _Up = _Tp>
686 _GLIBCXX20_CONSTEXPR
687 typename __gnu_cxx::__enable_if<!std::__are_same<_Up, bool>::__value,
688 iterator>::__type
689 insert(const_iterator __position, _Tp&& __x)
690 { return emplace(__position, std::move(__x)); }
691
692 _GLIBCXX20_CONSTEXPR
693 iterator
694 insert(const_iterator __position, initializer_list<value_type> __l)
695 { return this->insert(__position, __l.begin(), __l.end()); }
696#endif
697
698#if __cplusplus >= 201103L
699 _GLIBCXX20_CONSTEXPR
700 iterator
701 insert(const_iterator __position, size_type __n, const _Tp& __x)
702 {
703 if (std::__is_constant_evaluated())
704 return iterator(_Base::insert(__position.base(), __n, __x), this);
705
706 __glibcxx_check_insert(__position);
707 bool __realloc = this->_M_requires_reallocation(this->size() + __n);
708 difference_type __offset = __position.base() - _Base::cbegin();
709 _Base_iterator __res = _Base::insert(__position.base(), __n, __x);
710 if (__realloc)
711 this->_M_invalidate_all();
712 else
713 this->_M_invalidate_after_nth(n: __offset);
714 this->_M_update_guaranteed_capacity();
715 return { __res, this };
716 }
717#else
718 void
719 insert(iterator __position, size_type __n, const _Tp& __x)
720 {
721 __glibcxx_check_insert(__position);
722 bool __realloc = this->_M_requires_reallocation(this->size() + __n);
723 difference_type __offset = __position.base() - _Base::begin();
724 _Base::insert(__position.base(), __n, __x);
725 if (__realloc)
726 this->_M_invalidate_all();
727 else
728 this->_M_invalidate_after_nth(__offset);
729 this->_M_update_guaranteed_capacity();
730 }
731#endif
732
733#if __cplusplus >= 201103L
734 template<class _InputIterator,
735 typename = std::_RequireInputIter<_InputIterator>>
736 _GLIBCXX20_CONSTEXPR
737 iterator
738 insert(const_iterator __position,
739 _InputIterator __first, _InputIterator __last)
740 {
741 if (std::__is_constant_evaluated())
742 return iterator(_Base::insert(__position.base(),
743 __gnu_debug::__unsafe(__first),
744 __gnu_debug::__unsafe(__last)), this);
745
746 typename __gnu_debug::_Distance_traits<_InputIterator>::__type __dist;
747 __glibcxx_check_insert_range(__position, __first, __last, __dist);
748
749 /* Hard to guess if invalidation will occur, because __last
750 - __first can't be calculated in all cases, so we just
751 punt here by checking if it did occur. */
752 _Base_iterator __old_begin = _M_base().begin();
753 difference_type __offset = __position.base() - _Base::cbegin();
754 _Base_iterator __res;
755 if (__dist.second >= __gnu_debug::__dp_sign)
756 __res = _Base::insert(__position.base(),
757 __gnu_debug::__unsafe(__first),
758 __gnu_debug::__unsafe(__last));
759 else
760 __res = _Base::insert(__position.base(), __first, __last);
761
762 if (_M_base().begin() != __old_begin)
763 this->_M_invalidate_all();
764 else
765 this->_M_invalidate_after_nth(n: __offset);
766 this->_M_update_guaranteed_capacity();
767 return { __res, this };
768 }
769#else
770 template<class _InputIterator>
771 void
772 insert(iterator __position,
773 _InputIterator __first, _InputIterator __last)
774 {
775 typename __gnu_debug::_Distance_traits<_InputIterator>::__type __dist;
776 __glibcxx_check_insert_range(__position, __first, __last, __dist);
777
778 /* Hard to guess if invalidation will occur, because __last
779 - __first can't be calculated in all cases, so we just
780 punt here by checking if it did occur. */
781 _Base_iterator __old_begin = _M_base().begin();
782 difference_type __offset = __position.base() - _Base::begin();
783 if (__dist.second >= __gnu_debug::__dp_sign)
784 _Base::insert(__position.base(), __gnu_debug::__unsafe(__first),
785 __gnu_debug::__unsafe(__last));
786 else
787 _Base::insert(__position.base(), __first, __last);
788
789 if (_M_base().begin() != __old_begin)
790 this->_M_invalidate_all();
791 else
792 this->_M_invalidate_after_nth(__offset);
793 this->_M_update_guaranteed_capacity();
794 }
795#endif
796
797 _GLIBCXX20_CONSTEXPR
798 iterator
799#if __cplusplus >= 201103L
800 erase(const_iterator __position)
801#else
802 erase(iterator __position)
803#endif
804 {
805 if (std::__is_constant_evaluated())
806 return iterator(_Base::erase(__position.base()), this);
807
808 __glibcxx_check_erase(__position);
809 difference_type __offset = __position.base() - _Base::begin();
810 _Base_iterator __res = _Base::erase(__position.base());
811 this->_M_invalidate_after_nth(n: __offset);
812 return iterator(__res, this);
813 }
814
815 _GLIBCXX20_CONSTEXPR
816 iterator
817#if __cplusplus >= 201103L
818 erase(const_iterator __first, const_iterator __last)
819#else
820 erase(iterator __first, iterator __last)
821#endif
822 {
823 if (std::__is_constant_evaluated())
824 return iterator(_Base::erase(__first.base(), __last.base()), this);
825
826 // _GLIBCXX_RESOLVE_LIB_DEFECTS
827 // 151. can't currently clear() empty container
828 __glibcxx_check_erase_range(__first, __last);
829
830 if (__first.base() != __last.base())
831 {
832 difference_type __offset = __first.base() - _Base::begin();
833 _Base_iterator __res = _Base::erase(__first.base(),
834 __last.base());
835 this->_M_invalidate_after_nth(n: __offset);
836 return iterator(__res, this);
837 }
838 else
839#if __cplusplus >= 201103L
840 return { _Base::begin() + (__first.base() - _Base::cbegin()), this };
841#else
842 return __first;
843#endif
844 }
845
846 _GLIBCXX20_CONSTEXPR
847 void
848 swap(vector& __x)
849 _GLIBCXX_NOEXCEPT_IF( noexcept(declval<_Base&>().swap(__x)) )
850 {
851 if (!std::__is_constant_evaluated())
852 _Safe::_M_swap(__x);
853 _Base::swap(__x);
854 std::swap(this->_M_guaranteed_capacity, __x._M_guaranteed_capacity);
855 }
856
857 _GLIBCXX20_CONSTEXPR
858 void
859 clear() _GLIBCXX_NOEXCEPT
860 {
861 _Base::clear();
862 if (!std::__is_constant_evaluated())
863 this->_M_invalidate_all();
864 }
865
866 _GLIBCXX20_CONSTEXPR
867 _Base&
868 _M_base() _GLIBCXX_NOEXCEPT { return *this; }
869
870 _GLIBCXX20_CONSTEXPR
871 const _Base&
872 _M_base() const _GLIBCXX_NOEXCEPT { return *this; }
873
874#if __glibcxx_containers_ranges // C++ >= 23
875 template<std::__detail::__container_compatible_range<_Tp> _Rg>
876 constexpr void
877 assign_range(_Rg&& __rg)
878 {
879 auto __old_capacity = _Base::capacity();
880 auto __old_size = _Base::size();
881 _Base::assign_range(__rg);
882 if (!std::__is_constant_evaluated())
883 {
884 if (_Base::capacity() != __old_capacity)
885 this->_M_invalidate_all();
886 else if (_Base::size() < __old_size)
887 this->_M_invalidate_after_nth(_Base::size());
888 this->_M_update_guaranteed_capacity();
889 }
890 }
891
892 template<__detail::__container_compatible_range<_Tp> _Rg>
893 constexpr iterator
894 insert_range(const_iterator __pos, _Rg&& __rg)
895 {
896 auto __old_capacity = _Base::capacity();
897 auto __res = _Base::insert_range(__pos.base(), __rg);
898 if (!std::__is_constant_evaluated())
899 {
900 if (_Base::capacity() != __old_capacity)
901 this->_M_invalidate_all();
902 this->_M_update_guaranteed_capacity();
903 }
904 return iterator(__res, this);
905 }
906
907 template<__detail::__container_compatible_range<_Tp> _Rg>
908 constexpr void
909 append_range(_Rg&& __rg)
910 {
911 auto __old_capacity = _Base::capacity();
912 _Base::append_range(__rg);
913 if (!std::__is_constant_evaluated())
914 {
915 if (_Base::capacity() != __old_capacity)
916 this->_M_invalidate_all();
917 this->_M_update_guaranteed_capacity();
918 }
919 }
920#endif
921
922 private:
923 void
924 _M_invalidate_after_nth(difference_type __n) _GLIBCXX_NOEXCEPT
925 {
926 typedef __gnu_debug::_After_nth_from<_Base_const_iterator> _After_nth;
927 this->_M_invalidate_if(_After_nth(__n, _Base::begin()));
928 }
929 };
930
931 template<typename _Tp, typename _Alloc>
932 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
933 inline bool
934 operator==(const vector<_Tp, _Alloc>& __lhs,
935 const vector<_Tp, _Alloc>& __rhs)
936 { return __lhs._M_base() == __rhs._M_base(); }
937
938#if __cpp_lib_three_way_comparison
939 template<typename _Tp, typename _Alloc>
940 [[nodiscard]]
941 constexpr __detail::__synth3way_t<_Tp>
942 operator<=>(const vector<_Tp, _Alloc>& __x, const vector<_Tp, _Alloc>& __y)
943 { return __x._M_base() <=> __y._M_base(); }
944#else
945 template<typename _Tp, typename _Alloc>
946 _GLIBCXX_NODISCARD
947 inline bool
948 operator!=(const vector<_Tp, _Alloc>& __lhs,
949 const vector<_Tp, _Alloc>& __rhs)
950 { return __lhs._M_base() != __rhs._M_base(); }
951
952 template<typename _Tp, typename _Alloc>
953 _GLIBCXX_NODISCARD
954 inline bool
955 operator<(const vector<_Tp, _Alloc>& __lhs,
956 const vector<_Tp, _Alloc>& __rhs)
957 { return __lhs._M_base() < __rhs._M_base(); }
958
959 template<typename _Tp, typename _Alloc>
960 _GLIBCXX_NODISCARD
961 inline bool
962 operator<=(const vector<_Tp, _Alloc>& __lhs,
963 const vector<_Tp, _Alloc>& __rhs)
964 { return __lhs._M_base() <= __rhs._M_base(); }
965
966 template<typename _Tp, typename _Alloc>
967 _GLIBCXX_NODISCARD
968 inline bool
969 operator>=(const vector<_Tp, _Alloc>& __lhs,
970 const vector<_Tp, _Alloc>& __rhs)
971 { return __lhs._M_base() >= __rhs._M_base(); }
972
973 template<typename _Tp, typename _Alloc>
974 _GLIBCXX_NODISCARD
975 inline bool
976 operator>(const vector<_Tp, _Alloc>& __lhs,
977 const vector<_Tp, _Alloc>& __rhs)
978 { return __lhs._M_base() > __rhs._M_base(); }
979#endif // three-way comparison
980
981 template<typename _Tp, typename _Alloc>
982 _GLIBCXX20_CONSTEXPR
983 inline void
984 swap(vector<_Tp, _Alloc>& __lhs, vector<_Tp, _Alloc>& __rhs)
985 _GLIBCXX_NOEXCEPT_IF(noexcept(__lhs.swap(__rhs)))
986 { __lhs.swap(__rhs); }
987
988#if __cpp_deduction_guides >= 201606
989 template<typename _InputIterator, typename _ValT
990 = typename iterator_traits<_InputIterator>::value_type,
991 typename _Allocator = allocator<_ValT>,
992 typename = _RequireInputIter<_InputIterator>,
993 typename = _RequireAllocator<_Allocator>>
994 vector(_InputIterator, _InputIterator, _Allocator = _Allocator())
995 -> vector<_ValT, _Allocator>;
996
997 template<typename _Tp, typename _Allocator = allocator<_Tp>,
998 typename = _RequireAllocator<_Allocator>>
999 vector(size_t, _Tp, _Allocator = _Allocator())
1000 -> vector<_Tp, _Allocator>;
1001
1002#if __glibcxx_containers_ranges // C++ >= 23
1003 template<ranges::input_range _Rg,
1004 typename _Alloc = allocator<ranges::range_value_t<_Rg>>>
1005 vector(from_range_t, _Rg&&, _Alloc = _Alloc())
1006 -> vector<ranges::range_value_t<_Rg>, _Alloc>;
1007#endif
1008#endif
1009
1010} // namespace __debug
1011
1012_GLIBCXX_BEGIN_NAMESPACE_VERSION
1013
1014#if __cplusplus >= 201103L
1015 // DR 1182.
1016 /// std::hash specialization for vector<bool>.
1017 template<typename _Alloc>
1018 struct hash<__debug::vector<bool, _Alloc>>
1019 : public __hash_base<size_t, __debug::vector<bool, _Alloc>>
1020 {
1021 size_t
1022 operator()(const __debug::vector<bool, _Alloc>& __b) const noexcept
1023 { return std::hash<_GLIBCXX_STD_C::vector<bool, _Alloc>>()(__b); }
1024 };
1025#endif
1026
1027#if __cplusplus >= 201703L
1028 namespace __detail::__variant
1029 {
1030 template<typename> struct _Never_valueless_alt; // see <variant>
1031
1032 // Provide the strong exception-safety guarantee when emplacing a
1033 // vector into a variant, but only if move assignment cannot throw.
1034 template<typename _Tp, typename _Alloc>
1035 struct _Never_valueless_alt<__debug::vector<_Tp, _Alloc>>
1036 : std::is_nothrow_move_assignable<__debug::vector<_Tp, _Alloc>>
1037 { };
1038 } // namespace __detail::__variant
1039#endif // C++17
1040
1041#ifdef __glibcxx_erase_if // C++ >= 20 && HOSTED
1042 template<typename _Tp, typename _Alloc, typename _Predicate>
1043 constexpr typename __debug::vector<_Tp, _Alloc>::size_type
1044 erase_if(__debug::vector<_Tp, _Alloc>& __cont, _Predicate __pred)
1045 {
1046 return __detail::__erase_if(__cont, __cont._M_base(), std::move(__pred));
1047 }
1048
1049 template<typename _Tp, typename _Alloc, typename _Up = _Tp>
1050 constexpr typename __debug::vector<_Tp, _Alloc>::size_type
1051 erase(__debug::vector<_Tp, _Alloc>& __cont, const _Up& __value)
1052 { return std::erase_if(__cont, __gnu_cxx::__ops::__equal_to(__value)); }
1053#endif // __glibcxx_erase_if
1054
1055_GLIBCXX_END_NAMESPACE_VERSION
1056} // namespace std
1057
1058namespace __gnu_debug
1059{
1060 template<typename _Tp, typename _Alloc>
1061 struct _Is_contiguous_sequence<std::__debug::vector<_Tp, _Alloc> >
1062 : std::__true_type
1063 { };
1064
1065 template<typename _Alloc>
1066 struct _Is_contiguous_sequence<std::__debug::vector<bool, _Alloc> >
1067 : std::__false_type
1068 { };
1069}
1070
1071#endif
1072