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