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