libstdc++
debug/vector
Go to the documentation of this file.
1 // Debugging vector implementation -*- C++ -*-
2 
3 // Copyright (C) 2003-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 /** @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>
37 namespace 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 
46 namespace __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 
120 namespace std _GLIBCXX_VISIBILITY(default)
121 {
122 namespace __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(__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(__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(__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(__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(__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(__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(__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(__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 _GLIBCXX_END_NAMESPACE_VERSION
1042 } // namespace std
1043 
1044 namespace __gnu_debug
1045 {
1046  template<typename _Tp, typename _Alloc>
1047  struct _Is_contiguous_sequence<std::__debug::vector<_Tp, _Alloc> >
1048  : std::__true_type
1049  { };
1050 
1051  template<typename _Alloc>
1052  struct _Is_contiguous_sequence<std::__debug::vector<bool, _Alloc> >
1053  : std::__false_type
1054  { };
1055 }
1056 
1057 #endif