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