libstdc++-v3/include/debug/vector

   1 // Debugging vector implementation -*- C++ -*-
   2
   3 // Copyright (C) 2003-2024 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 <debug/safe_sequence.h>
  41 #include <debug/safe_container.h>
  42 #include <debug/safe_iterator.h>
  43
  44 namespace __gnu_debug
  45 {
  46   /** @brief Base class for Debug Mode vector.
  47    *
  48    * Adds information about the guaranteed capacity, which is useful for
  49    * detecting code which relies on non-portable implementation details of
  50    * the libstdc++ reallocation policy.
  51    */
  52   template<typename _SafeSequence,
  53            typename _BaseSequence>
  54     class _Safe_vector
  55     {
  56       typedef typename _BaseSequence::size_type size_type;
  57
  58       _GLIBCXX20_CONSTEXPR
  59       const _SafeSequence&
  60       _M_seq() const { return *static_cast<const _SafeSequence*>(this); }
  61
  62     protected:
  63       _GLIBCXX20_CONSTEXPR
  64       _Safe_vector() _GLIBCXX_NOEXCEPT
  65         : _M_guaranteed_capacity(0)
  66       { _M_update_guaranteed_capacity(); }
  67
  68       _GLIBCXX20_CONSTEXPR
  69       _Safe_vector(const _Safe_vector&) _GLIBCXX_NOEXCEPT
  70         : _M_guaranteed_capacity(0)
  71       { _M_update_guaranteed_capacity(); }
  72
  73       _GLIBCXX20_CONSTEXPR
  74       _Safe_vector(size_type __n) _GLIBCXX_NOEXCEPT
  75         : _M_guaranteed_capacity(__n)
  76       { }
  77
  78       _GLIBCXX20_CONSTEXPR
  79       _Safe_vector&
  80       operator=(const _Safe_vector&) _GLIBCXX_NOEXCEPT
  81       {
  82         _M_update_guaranteed_capacity();
  83         return *this;
  84       }
  85
  86 #if __cplusplus >= 201103L
  87       _GLIBCXX20_CONSTEXPR
  88       _Safe_vector(_Safe_vector&& __x) noexcept
  89         : _Safe_vector()
  90       { __x._M_guaranteed_capacity = 0; }
  91
  92       _GLIBCXX20_CONSTEXPR
  93       _Safe_vector&
  94       operator=(_Safe_vector&& __x) noexcept
  95       {
  96         _M_update_guaranteed_capacity();
  97         __x._M_guaranteed_capacity = 0;
  98         return *this;
  99       }
 100 #endif
 101
 102       size_type _M_guaranteed_capacity;
 103
 104       bool
 105       _M_requires_reallocation(size_type __elements) const _GLIBCXX_NOEXCEPT
 106       { return __elements > _M_seq().capacity(); }
 107
 108       _GLIBCXX20_CONSTEXPR
 109       void
 110       _M_update_guaranteed_capacity() _GLIBCXX_NOEXCEPT
 111       {
 112         if (_M_seq().size() > _M_guaranteed_capacity)
 113           _M_guaranteed_capacity = _M_seq().size();
 114       }
 115     };
 116 }
 117
 118 namespace std _GLIBCXX_VISIBILITY(default)
 119 {
 120 namespace __debug
 121 {
 122   /// Class std::vector with safety/checking/debug instrumentation.
 123   template<typename _Tp,
 124            typename _Allocator = std::allocator<_Tp> >
 125     class vector
 126     : public __gnu_debug::_Safe_container<
 127         vector<_Tp, _Allocator>, _Allocator, __gnu_debug::_Safe_sequence>,
 128       public _GLIBCXX_STD_C::vector<_Tp, _Allocator>,
 129       public __gnu_debug::_Safe_vector<
 130         vector<_Tp, _Allocator>,
 131         _GLIBCXX_STD_C::vector<_Tp, _Allocator> >
 132     {
 133       typedef _GLIBCXX_STD_C::vector<_Tp, _Allocator>           _Base;
 134       typedef __gnu_debug::_Safe_container<
 135         vector, _Allocator, __gnu_debug::_Safe_sequence>        _Safe;
 136       typedef __gnu_debug::_Safe_vector<vector, _Base>          _Safe_vector;
 137
 138       typedef typename _Base::iterator          _Base_iterator;
 139       typedef typename _Base::const_iterator    _Base_const_iterator;
 140       typedef __gnu_debug::_Equal_to<_Base_const_iterator> _Equal;
 141
 142       template<typename _ItT, typename _SeqT, typename _CatT>
 143         friend class ::__gnu_debug::_Safe_iterator;
 144
 145       // Reference wrapper for base class. Disambiguates vector(const _Base&)
 146       // from copy constructor by requiring a user-defined conversion.
 147       // See PR libstdc++/90102.
 148       struct _Base_ref
 149       {
 150         _Base_ref(const _Base& __r) : _M_ref(__r) { }
 151
 152         const _Base& _M_ref;
 153       };
 154
 155     public:
 156       typedef typename _Base::reference                 reference;
 157       typedef typename _Base::const_reference           const_reference;
 158
 159       typedef __gnu_debug::_Safe_iterator<
 160         _Base_iterator, vector>                         iterator;
 161       typedef __gnu_debug::_Safe_iterator<
 162         _Base_const_iterator, vector>                   const_iterator;
 163
 164       typedef typename _Base::size_type                 size_type;
 165       typedef typename _Base::difference_type           difference_type;
 166
 167       typedef _Tp                                       value_type;
 168       typedef _Allocator                                allocator_type;
 169       typedef typename _Base::pointer                   pointer;
 170       typedef typename _Base::const_pointer             const_pointer;
 171       typedef std::reverse_iterator<iterator>           reverse_iterator;
 172       typedef std::reverse_iterator<const_iterator>     const_reverse_iterator;
 173
 174       // 23.2.4.1 construct/copy/destroy:
 175
 176 #if __cplusplus < 201103L
 177       vector() _GLIBCXX_NOEXCEPT
 178       : _Base() { }
 179 #else
 180       vector() = default;
 181 #endif
 182
 183       _GLIBCXX20_CONSTEXPR
 184       explicit
 185       vector(const _Allocator& __a) _GLIBCXX_NOEXCEPT
 186       : _Base(__a) { }
 187
 188 #if __cplusplus >= 201103L
 189       _GLIBCXX20_CONSTEXPR
 190       explicit
 191       vector(size_type __n, const _Allocator& __a = _Allocator())
 192       : _Base(__n, __a), _Safe_vector(__n) { }
 193
 194       _GLIBCXX20_CONSTEXPR
 195       vector(size_type __n, const __type_identity_t<_Tp>& __value,
 196              const _Allocator& __a = _Allocator())
 197       : _Base(__n, __value, __a) { }
 198 #else
 199       explicit
 200       vector(size_type __n, const _Tp& __value = _Tp(),
 201              const _Allocator& __a = _Allocator())
 202       : _Base(__n, __value, __a) { }
 203 #endif
 204
 205 #if __cplusplus >= 201103L
 206       template<class _InputIterator,
 207                typename = std::_RequireInputIter<_InputIterator>>
 208 #else
 209       template<class _InputIterator>
 210 #endif
 211         _GLIBCXX20_CONSTEXPR
 212         vector(_InputIterator __first, _InputIterator __last,
 213                const _Allocator& __a = _Allocator())
 214         : _Base(__gnu_debug::__base(std::__is_constant_evaluated() ? __first
 215                   : __glibcxx_check_valid_constructor_range(__first, __last)),
 216                 __gnu_debug::__base(__last), __a) { }
 217
 218 #if __cplusplus < 201103L
 219       vector(const vector& __x)
 220       : _Base(__x) { }
 221
 222       ~vector() _GLIBCXX_NOEXCEPT { }
 223 #else
 224       vector(const vector&) = default;
 225       vector(vector&&) = default;
 226
 227       _GLIBCXX20_CONSTEXPR
 228       vector(const vector& __x, const __type_identity_t<allocator_type>& __a)
 229       : _Base(__x, __a) { }
 230
 231       _GLIBCXX20_CONSTEXPR
 232       vector(vector&& __x, const __type_identity_t<allocator_type>& __a)
 233       noexcept(
 234         std::is_nothrow_constructible<_Base,
 235           _Base, const allocator_type&>::value )
 236       : _Safe(std::move(__x), __a),
 237         _Base(std::move(__x), __a),
 238         _Safe_vector(std::move(__x)) { }
 239
 240       _GLIBCXX20_CONSTEXPR
 241       vector(initializer_list<value_type> __l,
 242              const allocator_type& __a = allocator_type())
 243       : _Base(__l, __a) { }
 244
 245       ~vector() = default;
 246 #endif
 247
 248       /// Construction from a normal-mode vector
 249       _GLIBCXX20_CONSTEXPR
 250       vector(_Base_ref __x)
 251       : _Base(__x._M_ref) { }
 252
 253 #if __cplusplus >= 201103L
 254       vector&
 255       operator=(const vector&) = default;
 256
 257       vector&
 258       operator=(vector&&) = default;
 259
 260       _GLIBCXX20_CONSTEXPR
 261       vector&
 262       operator=(initializer_list<value_type> __l)
 263       {
 264         _Base::operator=(__l);
 265         if (!std::__is_constant_evaluated())
 266           {
 267             this->_M_invalidate_all();
 268             this->_M_update_guaranteed_capacity();
 269           }
 270         return *this;
 271       }
 272 #endif
 273
 274 #if __cplusplus >= 201103L
 275       template<typename _InputIterator,
 276                typename = std::_RequireInputIter<_InputIterator>>
 277 #else
 278       template<typename _InputIterator>
 279 #endif
 280         _GLIBCXX20_CONSTEXPR
 281         void
 282         assign(_InputIterator __first, _InputIterator __last)
 283         {
 284           if (std::__is_constant_evaluated())
 285             return _Base::assign(__gnu_debug::__unsafe(__first),
 286                                  __gnu_debug::__unsafe(__last));
 287
 288           typename __gnu_debug::_Distance_traits<_InputIterator>::__type __dist;
 289           __glibcxx_check_valid_range2(__first, __last, __dist);
 290
 291           if (__dist.second >= __gnu_debug::__dp_sign)
 292             _Base::assign(__gnu_debug::__unsafe(__first),
 293                           __gnu_debug::__unsafe(__last));
 294           else
 295             _Base::assign(__first, __last);
 296
 297           this->_M_invalidate_all();
 298           this->_M_update_guaranteed_capacity();
 299         }
 300
 301       _GLIBCXX20_CONSTEXPR
 302       void
 303       assign(size_type __n, const _Tp& __u)
 304       {
 305         _Base::assign(__n, __u);
 306         if (!std::__is_constant_evaluated())
 307           {
 308             this->_M_invalidate_all();
 309             this->_M_update_guaranteed_capacity();
 310           }
 311       }
 312
 313 #if __cplusplus >= 201103L
 314       _GLIBCXX20_CONSTEXPR
 315       void
 316       assign(initializer_list<value_type> __l)
 317       {
 318         _Base::assign(__l);
 319         if (!std::__is_constant_evaluated())
 320           {
 321             this->_M_invalidate_all();
 322             this->_M_update_guaranteed_capacity();
 323           }
 324       }
 325 #endif
 326
 327       using _Base::get_allocator;
 328
 329       // iterators:
 330       _GLIBCXX_NODISCARD
 331       _GLIBCXX20_CONSTEXPR
 332       iterator
 333       begin() _GLIBCXX_NOEXCEPT
 334       { return iterator(_Base::begin(), this); }
 335
 336       _GLIBCXX_NODISCARD
 337       _GLIBCXX20_CONSTEXPR
 338       const_iterator
 339       begin() const _GLIBCXX_NOEXCEPT
 340       { return const_iterator(_Base::begin(), this); }
 341
 342       _GLIBCXX_NODISCARD
 343       _GLIBCXX20_CONSTEXPR
 344       iterator
 345       end() _GLIBCXX_NOEXCEPT
 346       { return iterator(_Base::end(), this); }
 347
 348       _GLIBCXX_NODISCARD
 349       _GLIBCXX20_CONSTEXPR
 350       const_iterator
 351       end() const _GLIBCXX_NOEXCEPT
 352       { return const_iterator(_Base::end(), this); }
 353
 354       _GLIBCXX_NODISCARD
 355       _GLIBCXX20_CONSTEXPR
 356       reverse_iterator
 357       rbegin() _GLIBCXX_NOEXCEPT
 358       { return reverse_iterator(end()); }
 359
 360       _GLIBCXX_NODISCARD
 361       _GLIBCXX20_CONSTEXPR
 362       const_reverse_iterator
 363       rbegin() const _GLIBCXX_NOEXCEPT
 364       { return const_reverse_iterator(end()); }
 365
 366       _GLIBCXX_NODISCARD
 367       _GLIBCXX20_CONSTEXPR
 368       reverse_iterator
 369       rend() _GLIBCXX_NOEXCEPT
 370       { return reverse_iterator(begin()); }
 371
 372       _GLIBCXX_NODISCARD
 373       _GLIBCXX20_CONSTEXPR
 374       const_reverse_iterator
 375       rend() const _GLIBCXX_NOEXCEPT
 376       { return const_reverse_iterator(begin()); }
 377
 378 #if __cplusplus >= 201103L
 379       [[__nodiscard__]]
 380       _GLIBCXX20_CONSTEXPR
 381       const_iterator
 382       cbegin() const noexcept
 383       { return const_iterator(_Base::begin(), this); }
 384
 385       [[__nodiscard__]]
 386       _GLIBCXX20_CONSTEXPR
 387       const_iterator
 388       cend() const noexcept
 389       { return const_iterator(_Base::end(), this); }
 390
 391       [[__nodiscard__]]
 392       _GLIBCXX20_CONSTEXPR
 393       const_reverse_iterator
 394       crbegin() const noexcept
 395       { return const_reverse_iterator(end()); }
 396
 397       [[__nodiscard__]]
 398       _GLIBCXX20_CONSTEXPR
 399       const_reverse_iterator
 400       crend() const noexcept
 401       { return const_reverse_iterator(begin()); }
 402 #endif
 403
 404       // 23.2.4.2 capacity:
 405       using _Base::size;
 406       using _Base::max_size;
 407
 408 #if __cplusplus >= 201103L
 409       _GLIBCXX20_CONSTEXPR
 410       void
 411       resize(size_type __sz)
 412       {
 413         if (std::__is_constant_evaluated())
 414           return _Base::resize(__sz);
 415
 416         bool __realloc = this->_M_requires_reallocation(__sz);
 417         if (__sz < this->size())
 418           this->_M_invalidate_after_nth(__sz);
 419         _Base::resize(__sz);
 420         if (__realloc)
 421           this->_M_invalidate_all();
 422         this->_M_update_guaranteed_capacity();
 423       }
 424
 425       _GLIBCXX20_CONSTEXPR
 426       void
 427       resize(size_type __sz, const _Tp& __c)
 428       {
 429         if (std::__is_constant_evaluated())
 430           return _Base::resize(__sz, __c);
 431
 432         bool __realloc = this->_M_requires_reallocation(__sz);
 433         if (__sz < this->size())
 434           this->_M_invalidate_after_nth(__sz);
 435         _Base::resize(__sz, __c);
 436         if (__realloc)
 437           this->_M_invalidate_all();
 438         this->_M_update_guaranteed_capacity();
 439       }
 440 #else
 441       void
 442       resize(size_type __sz, _Tp __c = _Tp())
 443       {
 444         bool __realloc = this->_M_requires_reallocation(__sz);
 445         if (__sz < this->size())
 446           this->_M_invalidate_after_nth(__sz);
 447         _Base::resize(__sz, __c);
 448         if (__realloc)
 449           this->_M_invalidate_all();
 450         this->_M_update_guaranteed_capacity();
 451       }
 452 #endif
 453
 454 #if __cplusplus >= 201103L
 455       _GLIBCXX20_CONSTEXPR
 456       void
 457       shrink_to_fit()
 458       {
 459         if (std::__is_constant_evaluated())
 460           return _Base::shrink_to_fit();
 461
 462         if (_Base::_M_shrink_to_fit())
 463           {
 464             this->_M_guaranteed_capacity = _Base::capacity();
 465             this->_M_invalidate_all();
 466           }
 467       }
 468 #endif
 469
 470       _GLIBCXX_NODISCARD
 471       _GLIBCXX20_CONSTEXPR
 472       size_type
 473       capacity() const _GLIBCXX_NOEXCEPT
 474       {
 475         if (std::__is_constant_evaluated())
 476           return _Base::capacity();
 477
 478 #ifdef _GLIBCXX_DEBUG_PEDANTIC
 479         return this->_M_guaranteed_capacity;
 480 #else
 481         return _Base::capacity();
 482 #endif
 483       }
 484
 485       using _Base::empty;
 486
 487       _GLIBCXX20_CONSTEXPR
 488       void
 489       reserve(size_type __n)
 490       {
 491         if (std::__is_constant_evaluated())
 492           return _Base::reserve(__n);
 493
 494         bool __realloc = this->_M_requires_reallocation(__n);
 495         _Base::reserve(__n);
 496         if (__n > this->_M_guaranteed_capacity)
 497           this->_M_guaranteed_capacity = __n;
 498         if (__realloc)
 499           this->_M_invalidate_all();
 500       }
 501
 502       // element access:
 503       _GLIBCXX_NODISCARD
 504       _GLIBCXX20_CONSTEXPR
 505       reference
 506       operator[](size_type __n) _GLIBCXX_NOEXCEPT
 507       {
 508         __glibcxx_check_subscript(__n);
 509         return _Base::operator[](__n);
 510       }
 511
 512       _GLIBCXX_NODISCARD
 513       _GLIBCXX20_CONSTEXPR
 514       const_reference
 515       operator[](size_type __n) const _GLIBCXX_NOEXCEPT
 516       {
 517         __glibcxx_check_subscript(__n);
 518         return _Base::operator[](__n);
 519       }
 520
 521       using _Base::at;
 522
 523       _GLIBCXX_NODISCARD
 524       _GLIBCXX20_CONSTEXPR
 525       reference
 526       front() _GLIBCXX_NOEXCEPT
 527       {
 528         __glibcxx_check_nonempty();
 529         return _Base::front();
 530       }
 531
 532       _GLIBCXX_NODISCARD
 533       _GLIBCXX20_CONSTEXPR
 534       const_reference
 535       front() const _GLIBCXX_NOEXCEPT
 536       {
 537         __glibcxx_check_nonempty();
 538         return _Base::front();
 539       }
 540
 541       _GLIBCXX_NODISCARD
 542       _GLIBCXX20_CONSTEXPR
 543       reference
 544       back() _GLIBCXX_NOEXCEPT
 545       {
 546         __glibcxx_check_nonempty();
 547         return _Base::back();
 548       }
 549
 550       _GLIBCXX_NODISCARD
 551       _GLIBCXX20_CONSTEXPR
 552       const_reference
 553       back() const _GLIBCXX_NOEXCEPT
 554       {
 555         __glibcxx_check_nonempty();
 556         return _Base::back();
 557       }
 558
 559       // _GLIBCXX_RESOLVE_LIB_DEFECTS
 560       // DR 464. Suggestion for new member functions in standard containers.
 561       using _Base::data;
 562
 563       // 23.2.4.3 modifiers:
 564       _GLIBCXX20_CONSTEXPR
 565       void
 566       push_back(const _Tp& __x)
 567       {
 568         if (std::__is_constant_evaluated())
 569           return _Base::push_back(__x);
 570
 571         bool __realloc = this->_M_requires_reallocation(this->size() + 1);
 572         _Base::push_back(__x);
 573         if (__realloc)
 574           this->_M_invalidate_all();
 575         this->_M_update_guaranteed_capacity();
 576       }
 577
 578 #if __cplusplus >= 201103L
 579       template<typename _Up = _Tp>
 580         _GLIBCXX20_CONSTEXPR
 581         typename __gnu_cxx::__enable_if<!std::__are_same<_Up, bool>::__value,
 582                                         void>::__type
 583         push_back(_Tp&& __x)
 584         { emplace_back(std::move(__x)); }
 585
 586       template<typename... _Args>
 587         _GLIBCXX20_CONSTEXPR
 588 #if __cplusplus > 201402L
 589         reference
 590 #else
 591         void
 592 #endif
 593         emplace_back(_Args&&... __args)
 594         {
 595           if (std::__is_constant_evaluated())
 596             return _Base::emplace_back(std::forward<_Args>(__args)...);
 597
 598           bool __realloc = this->_M_requires_reallocation(this->size() + 1);
 599           _Base::emplace_back(std::forward<_Args>(__args)...);
 600           if (__realloc)
 601             this->_M_invalidate_all();
 602           this->_M_update_guaranteed_capacity();
 603 #if __cplusplus > 201402L
 604           return back();
 605 #endif
 606         }
 607 #endif
 608
 609       _GLIBCXX20_CONSTEXPR
 610       void
 611       pop_back() _GLIBCXX_NOEXCEPT
 612       {
 613         if (!std::__is_constant_evaluated())
 614           {
 615             __glibcxx_check_nonempty();
 616             this->_M_invalidate_if(_Equal(--_Base::end()));
 617           }
 618         _Base::pop_back();
 619       }
 620
 621 #if __cplusplus >= 201103L
 622       template<typename... _Args>
 623         _GLIBCXX20_CONSTEXPR
 624         iterator
 625         emplace(const_iterator __position, _Args&&... __args)
 626         {
 627           if (std::__is_constant_evaluated())
 628             return iterator(_Base::emplace(__position.base(),
 629                                            std::forward<_Args>(__args)...),
 630                             this);
 631
 632           __glibcxx_check_insert(__position);
 633           bool __realloc = this->_M_requires_reallocation(this->size() + 1);
 634           difference_type __offset = __position.base() - _Base::cbegin();
 635           _Base_iterator __res = _Base::emplace(__position.base(),
 636                                                 std::forward<_Args>(__args)...);
 637           if (__realloc)
 638             this->_M_invalidate_all();
 639           else
 640             this->_M_invalidate_after_nth(__offset);
 641           this->_M_update_guaranteed_capacity();
 642           return { __res, this };
 643         }
 644 #endif
 645
 646       _GLIBCXX20_CONSTEXPR
 647       iterator
 648 #if __cplusplus >= 201103L
 649       insert(const_iterator __position, const _Tp& __x)
 650 #else
 651       insert(iterator __position, const _Tp& __x)
 652 #endif
 653       {
 654         if (std::__is_constant_evaluated())
 655           return iterator(_Base::insert(__position.base(), __x), this);
 656
 657         __glibcxx_check_insert(__position);
 658         bool __realloc = this->_M_requires_reallocation(this->size() + 1);
 659         difference_type __offset = __position.base() - _Base::begin();
 660         _Base_iterator __res = _Base::insert(__position.base(), __x);
 661         if (__realloc)
 662           this->_M_invalidate_all();
 663         else
 664           this->_M_invalidate_after_nth(__offset);
 665         this->_M_update_guaranteed_capacity();
 666         return iterator(__res, this);
 667       }
 668
 669 #if __cplusplus >= 201103L
 670       template<typename _Up = _Tp>
 671         _GLIBCXX20_CONSTEXPR
 672         typename __gnu_cxx::__enable_if<!std::__are_same<_Up, bool>::__value,
 673                                         iterator>::__type
 674         insert(const_iterator __position, _Tp&& __x)
 675         { return emplace(__position, std::move(__x)); }
 676
 677       _GLIBCXX20_CONSTEXPR
 678       iterator
 679       insert(const_iterator __position, initializer_list<value_type> __l)
 680       { return this->insert(__position, __l.begin(), __l.end()); }
 681 #endif
 682
 683 #if __cplusplus >= 201103L
 684       _GLIBCXX20_CONSTEXPR
 685       iterator
 686       insert(const_iterator __position, size_type __n, const _Tp& __x)
 687       {
 688         if (std::__is_constant_evaluated())
 689           return iterator(_Base::insert(__position.base(), __n, __x), this);
 690
 691         __glibcxx_check_insert(__position);
 692         bool __realloc = this->_M_requires_reallocation(this->size() + __n);
 693         difference_type __offset = __position.base() - _Base::cbegin();
 694         _Base_iterator __res = _Base::insert(__position.base(), __n, __x);
 695         if (__realloc)
 696           this->_M_invalidate_all();
 697         else
 698           this->_M_invalidate_after_nth(__offset);
 699         this->_M_update_guaranteed_capacity();
 700         return { __res, this };
 701       }
 702 #else
 703       void
 704       insert(iterator __position, size_type __n, const _Tp& __x)
 705       {
 706         __glibcxx_check_insert(__position);
 707         bool __realloc = this->_M_requires_reallocation(this->size() + __n);
 708         difference_type __offset = __position.base() - _Base::begin();
 709         _Base::insert(__position.base(), __n, __x);
 710         if (__realloc)
 711           this->_M_invalidate_all();
 712         else
 713           this->_M_invalidate_after_nth(__offset);
 714         this->_M_update_guaranteed_capacity();
 715       }
 716 #endif
 717
 718 #if __cplusplus >= 201103L
 719       template<class _InputIterator,
 720                typename = std::_RequireInputIter<_InputIterator>>
 721         _GLIBCXX20_CONSTEXPR
 722         iterator
 723         insert(const_iterator __position,
 724                _InputIterator __first, _InputIterator __last)
 725         {
 726           if (std::__is_constant_evaluated())
 727             return iterator(_Base::insert(__position.base(),
 728                                           __gnu_debug::__unsafe(__first),
 729                                           __gnu_debug::__unsafe(__last)), this);
 730
 731           typename __gnu_debug::_Distance_traits<_InputIterator>::__type __dist;
 732           __glibcxx_check_insert_range(__position, __first, __last, __dist);
 733
 734           /* Hard to guess if invalidation will occur, because __last
 735              - __first can't be calculated in all cases, so we just
 736              punt here by checking if it did occur. */
 737           _Base_iterator __old_begin = _M_base().begin();
 738           difference_type __offset = __position.base() - _Base::cbegin();
 739           _Base_iterator __res;
 740           if (__dist.second >= __gnu_debug::__dp_sign)
 741             __res = _Base::insert(__position.base(),
 742                                   __gnu_debug::__unsafe(__first),
 743                                   __gnu_debug::__unsafe(__last));
 744           else
 745             __res = _Base::insert(__position.base(), __first, __last);
 746
 747           if (_M_base().begin() != __old_begin)
 748             this->_M_invalidate_all();
 749           else
 750             this->_M_invalidate_after_nth(__offset);
 751           this->_M_update_guaranteed_capacity();
 752           return { __res, this };
 753         }
 754 #else
 755       template<class _InputIterator>
 756         void
 757         insert(iterator __position,
 758                _InputIterator __first, _InputIterator __last)
 759         {
 760           typename __gnu_debug::_Distance_traits<_InputIterator>::__type __dist;
 761           __glibcxx_check_insert_range(__position, __first, __last, __dist);
 762
 763           /* Hard to guess if invalidation will occur, because __last
 764              - __first can't be calculated in all cases, so we just
 765              punt here by checking if it did occur. */
 766           _Base_iterator __old_begin = _M_base().begin();
 767           difference_type __offset = __position.base() - _Base::begin();
 768           if (__dist.second >= __gnu_debug::__dp_sign)
 769             _Base::insert(__position.base(), __gnu_debug::__unsafe(__first),
 770                                              __gnu_debug::__unsafe(__last));
 771           else
 772             _Base::insert(__position.base(), __first, __last);
 773
 774           if (_M_base().begin() != __old_begin)
 775             this->_M_invalidate_all();
 776           else
 777             this->_M_invalidate_after_nth(__offset);
 778           this->_M_update_guaranteed_capacity();
 779         }
 780 #endif
 781
 782       _GLIBCXX20_CONSTEXPR
 783       iterator
 784 #if __cplusplus >= 201103L
 785       erase(const_iterator __position)
 786 #else
 787       erase(iterator __position)
 788 #endif
 789       {
 790         if (std::__is_constant_evaluated())
 791           return iterator(_Base::erase(__position.base()), this);
 792
 793         __glibcxx_check_erase(__position);
 794         difference_type __offset = __position.base() - _Base::begin();
 795         _Base_iterator __res = _Base::erase(__position.base());
 796         this->_M_invalidate_after_nth(__offset);
 797         return iterator(__res, this);
 798       }
 799
 800       _GLIBCXX20_CONSTEXPR
 801       iterator
 802 #if __cplusplus >= 201103L
 803       erase(const_iterator __first, const_iterator __last)
 804 #else
 805       erase(iterator __first, iterator __last)
 806 #endif
 807       {
 808         if (std::__is_constant_evaluated())
 809           return iterator(_Base::erase(__first.base(), __last.base()), this);
 810
 811         // _GLIBCXX_RESOLVE_LIB_DEFECTS
 812         // 151. can't currently clear() empty container
 813         __glibcxx_check_erase_range(__first, __last);
 814
 815         if (__first.base() != __last.base())
 816           {
 817             difference_type __offset = __first.base() - _Base::begin();
 818             _Base_iterator __res = _Base::erase(__first.base(),
 819                                                 __last.base());
 820             this->_M_invalidate_after_nth(__offset);
 821             return iterator(__res, this);
 822           }
 823         else
 824 #if __cplusplus >= 201103L
 825           return { _Base::begin() + (__first.base() - _Base::cbegin()), this };
 826 #else
 827           return __first;
 828 #endif
 829       }
 830
 831       _GLIBCXX20_CONSTEXPR
 832       void
 833       swap(vector& __x)
 834       _GLIBCXX_NOEXCEPT_IF( noexcept(declval<_Base&>().swap(__x)) )
 835       {
 836         if (!std::__is_constant_evaluated())
 837           _Safe::_M_swap(__x);
 838         _Base::swap(__x);
 839         std::swap(this->_M_guaranteed_capacity, __x._M_guaranteed_capacity);
 840       }
 841
 842       _GLIBCXX20_CONSTEXPR
 843       void
 844       clear() _GLIBCXX_NOEXCEPT
 845       {
 846         _Base::clear();
 847         if (!std::__is_constant_evaluated())
 848           this->_M_invalidate_all();
 849       }
 850
 851       _GLIBCXX20_CONSTEXPR
 852       _Base&
 853       _M_base() _GLIBCXX_NOEXCEPT { return *this; }
 854
 855       _GLIBCXX20_CONSTEXPR
 856       const _Base&
 857       _M_base() const _GLIBCXX_NOEXCEPT { return *this; }
 858
 859     private:
 860       void
 861       _M_invalidate_after_nth(difference_type __n) _GLIBCXX_NOEXCEPT
 862       {
 863         typedef __gnu_debug::_After_nth_from<_Base_const_iterator> _After_nth;
 864         this->_M_invalidate_if(_After_nth(__n, _Base::begin()));
 865       }
 866     };
 867
 868   template<typename _Tp, typename _Alloc>
 869     _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
 870     inline bool
 871     operator==(const vector<_Tp, _Alloc>& __lhs,
 872                const vector<_Tp, _Alloc>& __rhs)
 873     { return __lhs._M_base() == __rhs._M_base(); }
 874
 875 #if __cpp_lib_three_way_comparison
 876   template<typename _Tp, typename _Alloc>
 877     [[nodiscard]]
 878     constexpr __detail::__synth3way_t<_Tp>
 879     operator<=>(const vector<_Tp, _Alloc>& __x, const vector<_Tp, _Alloc>& __y)
 880     { return __x._M_base() <=> __y._M_base(); }
 881 #else
 882   template<typename _Tp, typename _Alloc>
 883     _GLIBCXX_NODISCARD
 884     inline bool
 885     operator!=(const vector<_Tp, _Alloc>& __lhs,
 886                const vector<_Tp, _Alloc>& __rhs)
 887     { return __lhs._M_base() != __rhs._M_base(); }
 888
 889   template<typename _Tp, typename _Alloc>
 890     _GLIBCXX_NODISCARD
 891     inline bool
 892     operator<(const vector<_Tp, _Alloc>& __lhs,
 893               const vector<_Tp, _Alloc>& __rhs)
 894     { return __lhs._M_base() < __rhs._M_base(); }
 895
 896   template<typename _Tp, typename _Alloc>
 897     _GLIBCXX_NODISCARD
 898     inline bool
 899     operator<=(const vector<_Tp, _Alloc>& __lhs,
 900                const vector<_Tp, _Alloc>& __rhs)
 901     { return __lhs._M_base() <= __rhs._M_base(); }
 902
 903   template<typename _Tp, typename _Alloc>
 904     _GLIBCXX_NODISCARD
 905     inline bool
 906     operator>=(const vector<_Tp, _Alloc>& __lhs,
 907                const vector<_Tp, _Alloc>& __rhs)
 908     { return __lhs._M_base() >= __rhs._M_base(); }
 909
 910   template<typename _Tp, typename _Alloc>
 911     _GLIBCXX_NODISCARD
 912     inline bool
 913     operator>(const vector<_Tp, _Alloc>& __lhs,
 914               const vector<_Tp, _Alloc>& __rhs)
 915     { return __lhs._M_base() > __rhs._M_base(); }
 916 #endif // three-way comparison
 917
 918   template<typename _Tp, typename _Alloc>
 919     _GLIBCXX20_CONSTEXPR
 920     inline void
 921     swap(vector<_Tp, _Alloc>& __lhs, vector<_Tp, _Alloc>& __rhs)
 922     _GLIBCXX_NOEXCEPT_IF(noexcept(__lhs.swap(__rhs)))
 923     { __lhs.swap(__rhs); }
 924
 925 #if __cpp_deduction_guides >= 201606
 926   template<typename _InputIterator, typename _ValT
 927              = typename iterator_traits<_InputIterator>::value_type,
 928            typename _Allocator = allocator<_ValT>,
 929            typename = _RequireInputIter<_InputIterator>,
 930            typename = _RequireAllocator<_Allocator>>
 931     vector(_InputIterator, _InputIterator, _Allocator = _Allocator())
 932       -> vector<_ValT, _Allocator>;
 933
 934   template<typename _Tp, typename _Allocator = allocator<_Tp>,
 935            typename = _RequireAllocator<_Allocator>>
 936     vector(size_t, _Tp, _Allocator = _Allocator())
 937       -> vector<_Tp, _Allocator>;
 938 #endif
 939
 940 } // namespace __debug
 941
 942 _GLIBCXX_BEGIN_NAMESPACE_VERSION
 943
 944 #if __cplusplus >= 201103L
 945   // DR 1182.
 946   /// std::hash specialization for vector<bool>.
 947   template<typename _Alloc>
 948     struct hash<__debug::vector<bool, _Alloc>>
 949     : public __hash_base<size_t, __debug::vector<bool, _Alloc>>
 950     {
 951       size_t
 952       operator()(const __debug::vector<bool, _Alloc>& __b) const noexcept
 953       { return std::hash<_GLIBCXX_STD_C::vector<bool, _Alloc>>()(__b); }
 954     };
 955 #endif
 956
 957 #if __cplusplus >= 201703L
 958   namespace __detail::__variant
 959   {
 960     template<typename> struct _Never_valueless_alt; // see <variant>
 961
 962     // Provide the strong exception-safety guarantee when emplacing a
 963     // vector into a variant, but only if move assignment cannot throw.
 964     template<typename _Tp, typename _Alloc>
 965       struct _Never_valueless_alt<__debug::vector<_Tp, _Alloc>>
 966       : std::is_nothrow_move_assignable<__debug::vector<_Tp, _Alloc>>
 967       { };
 968   }  // namespace __detail::__variant
 969 #endif // C++17
 970
 971 _GLIBCXX_END_NAMESPACE_VERSION
 972 } // namespace std
 973
 974 namespace __gnu_debug
 975 {
 976   template<typename _Tp, typename _Alloc>
 977     struct _Is_contiguous_sequence<std::__debug::vector<_Tp, _Alloc> >
 978     : std::__true_type
 979     { };
 980
 981   template<typename _Alloc>
 982     struct _Is_contiguous_sequence<std::__debug::vector<bool, _Alloc> >
 983     : std::__false_type
 984     { };
 985 }
 986
 987 #endif