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