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