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