libstdc++-v3/include/debug/vector

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