libstdc++-v3/include/debug/vector

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