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 _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(noexcept(
221  _Base(std::declval<_Base&&>()), std::declval<const allocator_type&>()))
222  : _Safe(std::move(__x._M_safe()), __a),
223  _Base(std::move(__x._M_base()), __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& __x)
240  {
241  this->_M_safe() = __x;
242  _M_base() = __x;
243  this->_M_update_guaranteed_capacity();
244  return *this;
245  }
246 #else
247  vector&
248  operator=(const vector&) = default;
249 
250  vector&
251  operator=(vector&&) = default;
252 
253  vector&
254  operator=(initializer_list<value_type> __l)
255  {
256  _M_base() = __l;
257  this->_M_invalidate_all();
258  this->_M_update_guaranteed_capacity();
259  return *this;
260  }
261 #endif
262 
263 #if __cplusplus >= 201103L
264  template<typename _InputIterator,
265  typename = std::_RequireInputIter<_InputIterator>>
266 #else
267  template<typename _InputIterator>
268 #endif
269  void
270  assign(_InputIterator __first, _InputIterator __last)
271  {
272  typename __gnu_debug::_Distance_traits<_InputIterator>::__type __dist;
273  __glibcxx_check_valid_range2(__first, __last, __dist);
274 
275  if (__dist.second >= __gnu_debug::__dp_sign)
276  _Base::assign(__gnu_debug::__unsafe(__first),
277  __gnu_debug::__unsafe(__last));
278  else
279  _Base::assign(__first, __last);
280 
281  this->_M_invalidate_all();
282  this->_M_update_guaranteed_capacity();
283  }
284 
285  void
286  assign(size_type __n, const _Tp& __u)
287  {
288  _Base::assign(__n, __u);
289  this->_M_invalidate_all();
290  this->_M_update_guaranteed_capacity();
291  }
292 
293 #if __cplusplus >= 201103L
294  void
295  assign(initializer_list<value_type> __l)
296  {
297  _Base::assign(__l);
298  this->_M_invalidate_all();
299  this->_M_update_guaranteed_capacity();
300  }
301 #endif
302 
303  using _Base::get_allocator;
304 
305  // iterators:
306  iterator
307  begin() _GLIBCXX_NOEXCEPT
308  { return iterator(_Base::begin(), this); }
309 
310  const_iterator
311  begin() const _GLIBCXX_NOEXCEPT
312  { return const_iterator(_Base::begin(), this); }
313 
314  iterator
315  end() _GLIBCXX_NOEXCEPT
316  { return iterator(_Base::end(), this); }
317 
318  const_iterator
319  end() const _GLIBCXX_NOEXCEPT
320  { return const_iterator(_Base::end(), this); }
321 
322  reverse_iterator
323  rbegin() _GLIBCXX_NOEXCEPT
324  { return reverse_iterator(end()); }
325 
326  const_reverse_iterator
327  rbegin() const _GLIBCXX_NOEXCEPT
328  { return const_reverse_iterator(end()); }
329 
330  reverse_iterator
331  rend() _GLIBCXX_NOEXCEPT
332  { return reverse_iterator(begin()); }
333 
334  const_reverse_iterator
335  rend() const _GLIBCXX_NOEXCEPT
336  { return const_reverse_iterator(begin()); }
337 
338 #if __cplusplus >= 201103L
339  const_iterator
340  cbegin() const noexcept
341  { return const_iterator(_Base::begin(), this); }
342 
343  const_iterator
344  cend() const noexcept
345  { return const_iterator(_Base::end(), this); }
346 
347  const_reverse_iterator
348  crbegin() const noexcept
349  { return const_reverse_iterator(end()); }
350 
351  const_reverse_iterator
352  crend() const noexcept
353  { return const_reverse_iterator(begin()); }
354 #endif
355 
356  // 23.2.4.2 capacity:
357  using _Base::size;
358  using _Base::max_size;
359 
360 #if __cplusplus >= 201103L
361  void
362  resize(size_type __sz)
363  {
364  bool __realloc = this->_M_requires_reallocation(__sz);
365  if (__sz < this->size())
366  this->_M_invalidate_after_nth(__sz);
367  _Base::resize(__sz);
368  if (__realloc)
369  this->_M_invalidate_all();
370  this->_M_update_guaranteed_capacity();
371  }
372 
373  void
374  resize(size_type __sz, const _Tp& __c)
375  {
376  bool __realloc = this->_M_requires_reallocation(__sz);
377  if (__sz < this->size())
378  this->_M_invalidate_after_nth(__sz);
379  _Base::resize(__sz, __c);
380  if (__realloc)
381  this->_M_invalidate_all();
382  this->_M_update_guaranteed_capacity();
383  }
384 #else
385  void
386  resize(size_type __sz, _Tp __c = _Tp())
387  {
388  bool __realloc = this->_M_requires_reallocation(__sz);
389  if (__sz < this->size())
390  this->_M_invalidate_after_nth(__sz);
391  _Base::resize(__sz, __c);
392  if (__realloc)
393  this->_M_invalidate_all();
394  this->_M_update_guaranteed_capacity();
395  }
396 #endif
397 
398 #if __cplusplus >= 201103L
399  void
400  shrink_to_fit()
401  {
402  if (_Base::_M_shrink_to_fit())
403  {
404  this->_M_guaranteed_capacity = _Base::capacity();
405  this->_M_invalidate_all();
406  }
407  }
408 #endif
409 
410  size_type
411  capacity() const _GLIBCXX_NOEXCEPT
412  {
413 #ifdef _GLIBCXX_DEBUG_PEDANTIC
414  return this->_M_guaranteed_capacity;
415 #else
416  return _Base::capacity();
417 #endif
418  }
419 
420  using _Base::empty;
421 
422  void
423  reserve(size_type __n)
424  {
425  bool __realloc = this->_M_requires_reallocation(__n);
426  _Base::reserve(__n);
427  if (__n > this->_M_guaranteed_capacity)
428  this->_M_guaranteed_capacity = __n;
429  if (__realloc)
430  this->_M_invalidate_all();
431  }
432 
433  // element access:
434  reference
435  operator[](size_type __n) _GLIBCXX_NOEXCEPT
436  {
437  __glibcxx_check_subscript(__n);
438  return _M_base()[__n];
439  }
440 
441  const_reference
442  operator[](size_type __n) const _GLIBCXX_NOEXCEPT
443  {
444  __glibcxx_check_subscript(__n);
445  return _M_base()[__n];
446  }
447 
448  using _Base::at;
449 
450  reference
451  front() _GLIBCXX_NOEXCEPT
452  {
453  __glibcxx_check_nonempty();
454  return _Base::front();
455  }
456 
457  const_reference
458  front() const _GLIBCXX_NOEXCEPT
459  {
460  __glibcxx_check_nonempty();
461  return _Base::front();
462  }
463 
464  reference
465  back() _GLIBCXX_NOEXCEPT
466  {
467  __glibcxx_check_nonempty();
468  return _Base::back();
469  }
470 
471  const_reference
472  back() const _GLIBCXX_NOEXCEPT
473  {
474  __glibcxx_check_nonempty();
475  return _Base::back();
476  }
477 
478  // _GLIBCXX_RESOLVE_LIB_DEFECTS
479  // DR 464. Suggestion for new member functions in standard containers.
480  using _Base::data;
481 
482  // 23.2.4.3 modifiers:
483  void
484  push_back(const _Tp& __x)
485  {
486  bool __realloc = this->_M_requires_reallocation(this->size() + 1);
487  _Base::push_back(__x);
488  if (__realloc)
489  this->_M_invalidate_all();
490  this->_M_update_guaranteed_capacity();
491  }
492 
493 #if __cplusplus >= 201103L
494  template<typename _Up = _Tp>
495  typename __gnu_cxx::__enable_if<!std::__are_same<_Up, bool>::__value,
496  void>::__type
497  push_back(_Tp&& __x)
498  { emplace_back(std::move(__x)); }
499 
500  template<typename... _Args>
501 #if __cplusplus > 201402L
502  reference
503 #else
504  void
505 #endif
506  emplace_back(_Args&&... __args)
507  {
508  bool __realloc = this->_M_requires_reallocation(this->size() + 1);
509  _Base::emplace_back(std::forward<_Args>(__args)...);
510  if (__realloc)
511  this->_M_invalidate_all();
512  this->_M_update_guaranteed_capacity();
513 #if __cplusplus > 201402L
514  return back();
515 #endif
516  }
517 #endif
518 
519  void
520  pop_back() _GLIBCXX_NOEXCEPT
521  {
522  __glibcxx_check_nonempty();
523  this->_M_invalidate_if(_Equal(--_Base::end()));
524  _Base::pop_back();
525  }
526 
527 #if __cplusplus >= 201103L
528  template<typename... _Args>
529  iterator
530  emplace(const_iterator __position, _Args&&... __args)
531  {
532  __glibcxx_check_insert(__position);
533  bool __realloc = this->_M_requires_reallocation(this->size() + 1);
534  difference_type __offset = __position.base() - _Base::cbegin();
535  _Base_iterator __res = _Base::emplace(__position.base(),
536  std::forward<_Args>(__args)...);
537  if (__realloc)
538  this->_M_invalidate_all();
539  else
540  this->_M_invalidate_after_nth(__offset);
541  this->_M_update_guaranteed_capacity();
542  return { __res, this };
543  }
544 #endif
545 
546  iterator
547 #if __cplusplus >= 201103L
548  insert(const_iterator __position, const _Tp& __x)
549 #else
550  insert(iterator __position, const _Tp& __x)
551 #endif
552  {
553  __glibcxx_check_insert(__position);
554  bool __realloc = this->_M_requires_reallocation(this->size() + 1);
555  difference_type __offset = __position.base() - _Base::begin();
556  _Base_iterator __res = _Base::insert(__position.base(), __x);
557  if (__realloc)
558  this->_M_invalidate_all();
559  else
560  this->_M_invalidate_after_nth(__offset);
561  this->_M_update_guaranteed_capacity();
562  return iterator(__res, this);
563  }
564 
565 #if __cplusplus >= 201103L
566  template<typename _Up = _Tp>
567  typename __gnu_cxx::__enable_if<!std::__are_same<_Up, bool>::__value,
568  iterator>::__type
569  insert(const_iterator __position, _Tp&& __x)
570  { return emplace(__position, std::move(__x)); }
571 
572  iterator
573  insert(const_iterator __position, initializer_list<value_type> __l)
574  { return this->insert(__position, __l.begin(), __l.end()); }
575 #endif
576 
577 #if __cplusplus >= 201103L
578  iterator
579  insert(const_iterator __position, size_type __n, const _Tp& __x)
580  {
581  __glibcxx_check_insert(__position);
582  bool __realloc = this->_M_requires_reallocation(this->size() + __n);
583  difference_type __offset = __position.base() - _Base::cbegin();
584  _Base_iterator __res = _Base::insert(__position.base(), __n, __x);
585  if (__realloc)
586  this->_M_invalidate_all();
587  else
588  this->_M_invalidate_after_nth(__offset);
589  this->_M_update_guaranteed_capacity();
590  return { __res, this };
591  }
592 #else
593  void
594  insert(iterator __position, size_type __n, const _Tp& __x)
595  {
596  __glibcxx_check_insert(__position);
597  bool __realloc = this->_M_requires_reallocation(this->size() + __n);
598  difference_type __offset = __position.base() - _Base::begin();
599  _Base::insert(__position.base(), __n, __x);
600  if (__realloc)
601  this->_M_invalidate_all();
602  else
603  this->_M_invalidate_after_nth(__offset);
604  this->_M_update_guaranteed_capacity();
605  }
606 #endif
607 
608 #if __cplusplus >= 201103L
609  template<class _InputIterator,
610  typename = std::_RequireInputIter<_InputIterator>>
611  iterator
612  insert(const_iterator __position,
613  _InputIterator __first, _InputIterator __last)
614  {
615  typename __gnu_debug::_Distance_traits<_InputIterator>::__type __dist;
616  __glibcxx_check_insert_range(__position, __first, __last, __dist);
617 
618  /* Hard to guess if invalidation will occur, because __last
619  - __first can't be calculated in all cases, so we just
620  punt here by checking if it did occur. */
621  _Base_iterator __old_begin = _M_base().begin();
622  difference_type __offset = __position.base() - _Base::cbegin();
623  _Base_iterator __res;
624  if (__dist.second >= __gnu_debug::__dp_sign)
625  __res = _Base::insert(__position.base(),
626  __gnu_debug::__unsafe(__first),
627  __gnu_debug::__unsafe(__last));
628  else
629  __res = _Base::insert(__position.base(), __first, __last);
630 
631  if (_M_base().begin() != __old_begin)
632  this->_M_invalidate_all();
633  else
634  this->_M_invalidate_after_nth(__offset);
635  this->_M_update_guaranteed_capacity();
636  return { __res, this };
637  }
638 #else
639  template<class _InputIterator>
640  void
641  insert(iterator __position,
642  _InputIterator __first, _InputIterator __last)
643  {
644  typename __gnu_debug::_Distance_traits<_InputIterator>::__type __dist;
645  __glibcxx_check_insert_range(__position, __first, __last, __dist);
646 
647  /* Hard to guess if invalidation will occur, because __last
648  - __first can't be calculated in all cases, so we just
649  punt here by checking if it did occur. */
650  _Base_iterator __old_begin = _M_base().begin();
651  difference_type __offset = __position.base() - _Base::begin();
652  if (__dist.second >= __gnu_debug::__dp_sign)
653  _Base::insert(__position.base(), __gnu_debug::__unsafe(__first),
654  __gnu_debug::__unsafe(__last));
655  else
656  _Base::insert(__position.base(), __first, __last);
657 
658  if (_M_base().begin() != __old_begin)
659  this->_M_invalidate_all();
660  else
661  this->_M_invalidate_after_nth(__offset);
662  this->_M_update_guaranteed_capacity();
663  }
664 #endif
665 
666  iterator
667 #if __cplusplus >= 201103L
668  erase(const_iterator __position)
669 #else
670  erase(iterator __position)
671 #endif
672  {
673  __glibcxx_check_erase(__position);
674  difference_type __offset = __position.base() - _Base::begin();
675  _Base_iterator __res = _Base::erase(__position.base());
676  this->_M_invalidate_after_nth(__offset);
677  return iterator(__res, this);
678  }
679 
680  iterator
681 #if __cplusplus >= 201103L
682  erase(const_iterator __first, const_iterator __last)
683 #else
684  erase(iterator __first, iterator __last)
685 #endif
686  {
687  // _GLIBCXX_RESOLVE_LIB_DEFECTS
688  // 151. can't currently clear() empty container
689  __glibcxx_check_erase_range(__first, __last);
690 
691  if (__first.base() != __last.base())
692  {
693  difference_type __offset = __first.base() - _Base::begin();
694  _Base_iterator __res = _Base::erase(__first.base(),
695  __last.base());
696  this->_M_invalidate_after_nth(__offset);
697  return iterator(__res, this);
698  }
699  else
700 #if __cplusplus >= 201103L
701  return { _Base::begin() + (__first.base() - _Base::cbegin()), this };
702 #else
703  return __first;
704 #endif
705  }
706 
707  void
708  swap(vector& __x)
709  _GLIBCXX_NOEXCEPT_IF( noexcept(declval<_Base&>().swap(__x)) )
710  {
711  _Safe::_M_swap(__x);
712  _Base::swap(__x);
713  std::swap(this->_M_guaranteed_capacity, __x._M_guaranteed_capacity);
714  }
715 
716  void
717  clear() _GLIBCXX_NOEXCEPT
718  {
719  _Base::clear();
720  this->_M_invalidate_all();
721  }
722 
723  _Base&
724  _M_base() _GLIBCXX_NOEXCEPT { return *this; }
725 
726  const _Base&
727  _M_base() const _GLIBCXX_NOEXCEPT { return *this; }
728 
729  private:
730  void
731  _M_invalidate_after_nth(difference_type __n) _GLIBCXX_NOEXCEPT
732  {
733  typedef __gnu_debug::_After_nth_from<_Base_const_iterator> _After_nth;
734  this->_M_invalidate_if(_After_nth(__n, _Base::begin()));
735  }
736  };
737 
738  template<typename _Tp, typename _Alloc>
739  inline bool
740  operator==(const vector<_Tp, _Alloc>& __lhs,
741  const vector<_Tp, _Alloc>& __rhs)
742  { return __lhs._M_base() == __rhs._M_base(); }
743 
744 #if __cpp_lib_three_way_comparison
745  template<typename _Tp, typename _Alloc>
746  constexpr __detail::__synth3way_t<_Tp>
747  operator<=>(const vector<_Tp, _Alloc>& __x, const vector<_Tp, _Alloc>& __y)
748  { return __x._M_base() <=> __y._M_base(); }
749 #else
750  template<typename _Tp, typename _Alloc>
751  inline bool
752  operator!=(const vector<_Tp, _Alloc>& __lhs,
753  const vector<_Tp, _Alloc>& __rhs)
754  { return __lhs._M_base() != __rhs._M_base(); }
755 
756  template<typename _Tp, typename _Alloc>
757  inline bool
758  operator<(const vector<_Tp, _Alloc>& __lhs,
759  const vector<_Tp, _Alloc>& __rhs)
760  { return __lhs._M_base() < __rhs._M_base(); }
761 
762  template<typename _Tp, typename _Alloc>
763  inline bool
764  operator<=(const vector<_Tp, _Alloc>& __lhs,
765  const vector<_Tp, _Alloc>& __rhs)
766  { return __lhs._M_base() <= __rhs._M_base(); }
767 
768  template<typename _Tp, typename _Alloc>
769  inline bool
770  operator>=(const vector<_Tp, _Alloc>& __lhs,
771  const vector<_Tp, _Alloc>& __rhs)
772  { return __lhs._M_base() >= __rhs._M_base(); }
773 
774  template<typename _Tp, typename _Alloc>
775  inline bool
776  operator>(const vector<_Tp, _Alloc>& __lhs,
777  const vector<_Tp, _Alloc>& __rhs)
778  { return __lhs._M_base() > __rhs._M_base(); }
779 #endif // three-way comparison
780 
781  template<typename _Tp, typename _Alloc>
782  inline void
783  swap(vector<_Tp, _Alloc>& __lhs, vector<_Tp, _Alloc>& __rhs)
784  _GLIBCXX_NOEXCEPT_IF(noexcept(__lhs.swap(__rhs)))
785  { __lhs.swap(__rhs); }
786 
787 #if __cpp_deduction_guides >= 201606
788  template<typename _InputIterator, typename _ValT
789  = typename iterator_traits<_InputIterator>::value_type,
790  typename _Allocator = allocator<_ValT>,
791  typename = _RequireInputIter<_InputIterator>,
792  typename = _RequireAllocator<_Allocator>>
793  vector(_InputIterator, _InputIterator, _Allocator = _Allocator())
794  -> vector<_ValT, _Allocator>;
795 #endif
796 
797 } // namespace __debug
798 
799 _GLIBCXX_BEGIN_NAMESPACE_VERSION
800 
801 #if __cplusplus >= 201103L
802  // DR 1182.
803  /// std::hash specialization for vector<bool>.
804  template<typename _Alloc>
805  struct hash<__debug::vector<bool, _Alloc>>
806  : public __hash_base<size_t, __debug::vector<bool, _Alloc>>
807  {
808  size_t
809  operator()(const __debug::vector<bool, _Alloc>& __b) const noexcept
810  { return std::hash<_GLIBCXX_STD_C::vector<bool, _Alloc>>()(__b); }
811  };
812 #endif
813 
814 #if __cplusplus >= 201703L
815  namespace __detail::__variant
816  {
817  template<typename> struct _Never_valueless_alt; // see <variant>
818 
819  // Provide the strong exception-safety guarantee when emplacing a
820  // vector into a variant, but only if move assignment cannot throw.
821  template<typename _Tp, typename _Alloc>
822  struct _Never_valueless_alt<__debug::vector<_Tp, _Alloc>>
823  : std::is_nothrow_move_assignable<__debug::vector<_Tp, _Alloc>>
824  { };
825  } // namespace __detail::__variant
826 #endif // C++17
827 
828 _GLIBCXX_END_NAMESPACE_VERSION
829 } // namespace std
830 
831 namespace __gnu_debug
832 {
833  template<typename _Tp, typename _Alloc>
834  struct _Is_contiguous_sequence<std::__debug::vector<_Tp, _Alloc> >
835  : std::__true_type
836  { };
837 
838  template<typename _Alloc>
839  struct _Is_contiguous_sequence<std::__debug::vector<bool, _Alloc> >
840  : std::__false_type
841  { };
842 }
843 
844 #endif