contrib/gcc-8.0/libstdc++-v3/include/debug/vector

   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
  40 namespace __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
 106 namespace std _GLIBCXX_VISIBILITY(default)
 107 {
 108 namespace __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
 791 namespace __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