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(
 186                   __glibcxx_check_valid_constructor_range(__first, __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         noexcept( noexcept(
 203           _Base(std::declval<_Base&&>()), std::declval<const allocator_type&>()) )
 204       : _Safe(std::move(__x._M_safe()), __a),
 205         _Base(std::move(__x._M_base()), __a),
 206         _Safe_vector(std::move(__x)) { }
 207
 208       vector(initializer_list<value_type> __l,
 209              const allocator_type& __a = allocator_type())
 210       : _Base(__l, __a) { }
 211
 212       ~vector() = default;
 213 #endif
 214
 215       /// Construction from a normal-mode vector
 216       vector(const _Base& __x)
 217       : _Base(__x) { }
 218
 219 #if __cplusplus < 201103L
 220       vector&
 221       operator=(const vector& __x)
 222       {
 223         this->_M_safe() = __x;
 224         _M_base() = __x;
 225         this->_M_update_guaranteed_capacity();
 226         return *this;
 227       }
 228 #else
 229       vector&
 230       operator=(const vector&) = default;
 231
 232       vector&
 233       operator=(vector&&) = default;
 234
 235       vector&
 236       operator=(initializer_list<value_type> __l)
 237       {
 238         _M_base() = __l;
 239         this->_M_invalidate_all();
 240         this->_M_update_guaranteed_capacity();
 241         return *this;
 242       }
 243 #endif
 244
 245 #if __cplusplus >= 201103L
 246       template<typename _InputIterator,
 247                typename = std::_RequireInputIter<_InputIterator>>
 248 #else
 249       template<typename _InputIterator>
 250 #endif
 251         void
 252         assign(_InputIterator __first, _InputIterator __last)
 253         {
 254           typename __gnu_debug::_Distance_traits<_InputIterator>::__type __dist;
 255           __glibcxx_check_valid_range2(__first, __last, __dist);
 256
 257           if (__dist.second >= __gnu_debug::__dp_sign)
 258             _Base::assign(__gnu_debug::__unsafe(__first),
 259                           __gnu_debug::__unsafe(__last));
 260           else
 261             _Base::assign(__first, __last);
 262
 263           this->_M_invalidate_all();
 264           this->_M_update_guaranteed_capacity();
 265         }
 266
 267       void
 268       assign(size_type __n, const _Tp& __u)
 269       {
 270         _Base::assign(__n, __u);
 271         this->_M_invalidate_all();
 272         this->_M_update_guaranteed_capacity();
 273       }
 274
 275 #if __cplusplus >= 201103L
 276       void
 277       assign(initializer_list<value_type> __l)
 278       {
 279         _Base::assign(__l);
 280         this->_M_invalidate_all();
 281         this->_M_update_guaranteed_capacity();
 282       }
 283 #endif
 284
 285       using _Base::get_allocator;
 286
 287       // iterators:
 288       iterator
 289       begin() _GLIBCXX_NOEXCEPT
 290       { return iterator(_Base::begin(), this); }
 291
 292       const_iterator
 293       begin() const _GLIBCXX_NOEXCEPT
 294       { return const_iterator(_Base::begin(), this); }
 295
 296       iterator
 297       end() _GLIBCXX_NOEXCEPT
 298       { return iterator(_Base::end(), this); }
 299
 300       const_iterator
 301       end() const _GLIBCXX_NOEXCEPT
 302       { return const_iterator(_Base::end(), this); }
 303
 304       reverse_iterator
 305       rbegin() _GLIBCXX_NOEXCEPT
 306       { return reverse_iterator(end()); }
 307
 308       const_reverse_iterator
 309       rbegin() const _GLIBCXX_NOEXCEPT
 310       { return const_reverse_iterator(end()); }
 311
 312       reverse_iterator
 313       rend() _GLIBCXX_NOEXCEPT
 314       { return reverse_iterator(begin()); }
 315
 316       const_reverse_iterator
 317       rend() const _GLIBCXX_NOEXCEPT
 318       { return const_reverse_iterator(begin()); }
 319
 320 #if __cplusplus >= 201103L
 321       const_iterator
 322       cbegin() const noexcept
 323       { return const_iterator(_Base::begin(), this); }
 324
 325       const_iterator
 326       cend() const noexcept
 327       { return const_iterator(_Base::end(), this); }
 328
 329       const_reverse_iterator
 330       crbegin() const noexcept
 331       { return const_reverse_iterator(end()); }
 332
 333       const_reverse_iterator
 334       crend() const noexcept
 335       { return const_reverse_iterator(begin()); }
 336 #endif
 337
 338       // 23.2.4.2 capacity:
 339       using _Base::size;
 340       using _Base::max_size;
 341
 342 #if __cplusplus >= 201103L
 343       void
 344       resize(size_type __sz)
 345       {
 346         bool __realloc = this->_M_requires_reallocation(__sz);
 347         if (__sz < this->size())
 348           this->_M_invalidate_after_nth(__sz);
 349         _Base::resize(__sz);
 350         if (__realloc)
 351           this->_M_invalidate_all();
 352         this->_M_update_guaranteed_capacity();
 353       }
 354
 355       void
 356       resize(size_type __sz, const _Tp& __c)
 357       {
 358         bool __realloc = this->_M_requires_reallocation(__sz);
 359         if (__sz < this->size())
 360           this->_M_invalidate_after_nth(__sz);
 361         _Base::resize(__sz, __c);
 362         if (__realloc)
 363           this->_M_invalidate_all();
 364         this->_M_update_guaranteed_capacity();
 365       }
 366 #else
 367       void
 368       resize(size_type __sz, _Tp __c = _Tp())
 369       {
 370         bool __realloc = this->_M_requires_reallocation(__sz);
 371         if (__sz < this->size())
 372           this->_M_invalidate_after_nth(__sz);
 373         _Base::resize(__sz, __c);
 374         if (__realloc)
 375           this->_M_invalidate_all();
 376         this->_M_update_guaranteed_capacity();
 377       }
 378 #endif
 379
 380 #if __cplusplus >= 201103L
 381       void
 382       shrink_to_fit()
 383       {
 384         if (_Base::_M_shrink_to_fit())
 385           {
 386             this->_M_guaranteed_capacity = _Base::capacity();
 387             this->_M_invalidate_all();
 388           }
 389       }
 390 #endif
 391
 392       size_type
 393       capacity() const _GLIBCXX_NOEXCEPT
 394       {
 395 #ifdef _GLIBCXX_DEBUG_PEDANTIC
 396         return this->_M_guaranteed_capacity;
 397 #else
 398         return _Base::capacity();
 399 #endif
 400       }
 401
 402       using _Base::empty;
 403
 404       void
 405       reserve(size_type __n)
 406       {
 407         bool __realloc = this->_M_requires_reallocation(__n);
 408         _Base::reserve(__n);
 409         if (__n > this->_M_guaranteed_capacity)
 410           this->_M_guaranteed_capacity = __n;
 411         if (__realloc)
 412           this->_M_invalidate_all();
 413       }
 414
 415       // element access:
 416       reference
 417       operator[](size_type __n) _GLIBCXX_NOEXCEPT
 418       {
 419         __glibcxx_check_subscript(__n);
 420         return _M_base()[__n];
 421       }
 422
 423       const_reference
 424       operator[](size_type __n) const _GLIBCXX_NOEXCEPT
 425       {
 426         __glibcxx_check_subscript(__n);
 427         return _M_base()[__n];
 428       }
 429
 430       using _Base::at;
 431
 432       reference
 433       front() _GLIBCXX_NOEXCEPT
 434       {
 435         __glibcxx_check_nonempty();
 436         return _Base::front();
 437       }
 438
 439       const_reference
 440       front() const _GLIBCXX_NOEXCEPT
 441       {
 442         __glibcxx_check_nonempty();
 443         return _Base::front();
 444       }
 445
 446       reference
 447       back() _GLIBCXX_NOEXCEPT
 448       {
 449         __glibcxx_check_nonempty();
 450         return _Base::back();
 451       }
 452
 453       const_reference
 454       back() const _GLIBCXX_NOEXCEPT
 455       {
 456         __glibcxx_check_nonempty();
 457         return _Base::back();
 458       }
 459
 460       // _GLIBCXX_RESOLVE_LIB_DEFECTS
 461       // DR 464. Suggestion for new member functions in standard containers.
 462       using _Base::data;
 463
 464       // 23.2.4.3 modifiers:
 465       void
 466       push_back(const _Tp& __x)
 467       {
 468         bool __realloc = this->_M_requires_reallocation(this->size() + 1);
 469         _Base::push_back(__x);
 470         if (__realloc)
 471           this->_M_invalidate_all();
 472         this->_M_update_guaranteed_capacity();
 473       }
 474
 475 #if __cplusplus >= 201103L
 476       template<typename _Up = _Tp>
 477         typename __gnu_cxx::__enable_if<!std::__are_same<_Up, bool>::__value,
 478                                         void>::__type
 479         push_back(_Tp&& __x)
 480         { emplace_back(std::move(__x)); }
 481
 482       template<typename... _Args>
 483 #if __cplusplus > 201402L
 484         reference
 485 #else
 486         void
 487 #endif
 488         emplace_back(_Args&&... __args)
 489         {
 490           bool __realloc = this->_M_requires_reallocation(this->size() + 1);
 491           _Base::emplace_back(std::forward<_Args>(__args)...);
 492           if (__realloc)
 493             this->_M_invalidate_all();
 494           this->_M_update_guaranteed_capacity();
 495 #if __cplusplus > 201402L
 496           return back();
 497 #endif
 498         }
 499 #endif
 500
 501       void
 502       pop_back() _GLIBCXX_NOEXCEPT
 503       {
 504         __glibcxx_check_nonempty();
 505         this->_M_invalidate_if(_Equal(--_Base::end()));
 506         _Base::pop_back();
 507       }
 508
 509 #if __cplusplus >= 201103L
 510       template<typename... _Args>
 511         iterator
 512         emplace(const_iterator __position, _Args&&... __args)
 513         {
 514           __glibcxx_check_insert(__position);
 515           bool __realloc = this->_M_requires_reallocation(this->size() + 1);
 516           difference_type __offset = __position.base() - _Base::begin();
 517           _Base_iterator __res = _Base::emplace(__position.base(),
 518                                                 std::forward<_Args>(__args)...);
 519           if (__realloc)
 520             this->_M_invalidate_all();
 521           else
 522             this->_M_invalidate_after_nth(__offset);
 523           this->_M_update_guaranteed_capacity();
 524           return iterator(__res, this);
 525         }
 526 #endif
 527
 528       iterator
 529 #if __cplusplus >= 201103L
 530       insert(const_iterator __position, const _Tp& __x)
 531 #else
 532       insert(iterator __position, const _Tp& __x)
 533 #endif
 534       {
 535         __glibcxx_check_insert(__position);
 536         bool __realloc = this->_M_requires_reallocation(this->size() + 1);
 537         difference_type __offset = __position.base() - _Base::begin();
 538         _Base_iterator __res = _Base::insert(__position.base(), __x);
 539         if (__realloc)
 540           this->_M_invalidate_all();
 541         else
 542           this->_M_invalidate_after_nth(__offset);
 543         this->_M_update_guaranteed_capacity();
 544         return iterator(__res, this);
 545       }
 546
 547 #if __cplusplus >= 201103L
 548       template<typename _Up = _Tp>
 549         typename __gnu_cxx::__enable_if<!std::__are_same<_Up, bool>::__value,
 550                                         iterator>::__type
 551         insert(const_iterator __position, _Tp&& __x)
 552         { return emplace(__position, std::move(__x)); }
 553
 554       iterator
 555       insert(const_iterator __position, initializer_list<value_type> __l)
 556       { return this->insert(__position, __l.begin(), __l.end()); }
 557 #endif
 558
 559 #if __cplusplus >= 201103L
 560       iterator
 561       insert(const_iterator __position, size_type __n, const _Tp& __x)
 562       {
 563         __glibcxx_check_insert(__position);
 564         bool __realloc = this->_M_requires_reallocation(this->size() + __n);
 565         difference_type __offset = __position.base() - _Base::cbegin();
 566         _Base_iterator __res = _Base::insert(__position.base(), __n, __x);
 567         if (__realloc)
 568           this->_M_invalidate_all();
 569         else
 570           this->_M_invalidate_after_nth(__offset);
 571         this->_M_update_guaranteed_capacity();
 572         return iterator(__res, this);
 573       }
 574 #else
 575       void
 576       insert(iterator __position, size_type __n, const _Tp& __x)
 577       {
 578         __glibcxx_check_insert(__position);
 579         bool __realloc = this->_M_requires_reallocation(this->size() + __n);
 580         difference_type __offset = __position.base() - _Base::begin();
 581         _Base::insert(__position.base(), __n, __x);
 582         if (__realloc)
 583           this->_M_invalidate_all();
 584         else
 585           this->_M_invalidate_after_nth(__offset);
 586         this->_M_update_guaranteed_capacity();
 587       }
 588 #endif
 589
 590 #if __cplusplus >= 201103L
 591       template<class _InputIterator,
 592                typename = std::_RequireInputIter<_InputIterator>>
 593         iterator
 594         insert(const_iterator __position,
 595                _InputIterator __first, _InputIterator __last)
 596         {
 597           typename __gnu_debug::_Distance_traits<_InputIterator>::__type __dist;
 598           __glibcxx_check_insert_range(__position, __first, __last, __dist);
 599
 600           /* Hard to guess if invalidation will occur, because __last
 601              - __first can't be calculated in all cases, so we just
 602              punt here by checking if it did occur. */
 603           _Base_iterator __old_begin = _M_base().begin();
 604           difference_type __offset = __position.base() - _Base::cbegin();
 605           _Base_iterator __res;
 606           if (__dist.second >= __gnu_debug::__dp_sign)
 607             __res = _Base::insert(__position.base(),
 608                                   __gnu_debug::__unsafe(__first),
 609                                   __gnu_debug::__unsafe(__last));
 610           else
 611             __res = _Base::insert(__position.base(), __first, __last);
 612
 613           if (_M_base().begin() != __old_begin)
 614             this->_M_invalidate_all();
 615           else
 616             this->_M_invalidate_after_nth(__offset);
 617           this->_M_update_guaranteed_capacity();
 618           return iterator(__res, this);
 619         }
 620 #else
 621       template<class _InputIterator>
 622         void
 623         insert(iterator __position,
 624                _InputIterator __first, _InputIterator __last)
 625         {
 626           typename __gnu_debug::_Distance_traits<_InputIterator>::__type __dist;
 627           __glibcxx_check_insert_range(__position, __first, __last, __dist);
 628
 629           /* Hard to guess if invalidation will occur, because __last
 630              - __first can't be calculated in all cases, so we just
 631              punt here by checking if it did occur. */
 632           _Base_iterator __old_begin = _M_base().begin();
 633           difference_type __offset = __position.base() - _Base::begin();
 634           if (__dist.second >= __gnu_debug::__dp_sign)
 635             _Base::insert(__position.base(), __gnu_debug::__unsafe(__first),
 636                                              __gnu_debug::__unsafe(__last));
 637           else
 638             _Base::insert(__position.base(), __first, __last);
 639
 640           if (_M_base().begin() != __old_begin)
 641             this->_M_invalidate_all();
 642           else
 643             this->_M_invalidate_after_nth(__offset);
 644           this->_M_update_guaranteed_capacity();
 645         }
 646 #endif
 647
 648       iterator
 649 #if __cplusplus >= 201103L
 650       erase(const_iterator __position)
 651 #else
 652       erase(iterator __position)
 653 #endif
 654       {
 655         __glibcxx_check_erase(__position);
 656         difference_type __offset = __position.base() - _Base::begin();
 657         _Base_iterator __res = _Base::erase(__position.base());
 658         this->_M_invalidate_after_nth(__offset);
 659         return iterator(__res, this);
 660       }
 661
 662       iterator
 663 #if __cplusplus >= 201103L
 664       erase(const_iterator __first, const_iterator __last)
 665 #else
 666       erase(iterator __first, iterator __last)
 667 #endif
 668       {
 669         // _GLIBCXX_RESOLVE_LIB_DEFECTS
 670         // 151. can't currently clear() empty container
 671         __glibcxx_check_erase_range(__first, __last);
 672
 673         if (__first.base() != __last.base())
 674           {
 675             difference_type __offset = __first.base() - _Base::begin();
 676             _Base_iterator __res = _Base::erase(__first.base(),
 677                                                 __last.base());
 678             this->_M_invalidate_after_nth(__offset);
 679             return iterator(__res, this);
 680           }
 681         else
 682 #if __cplusplus >= 201103L
 683           return begin() + (__first.base() - cbegin().base());
 684 #else
 685           return __first;
 686 #endif
 687       }
 688
 689       void
 690       swap(vector& __x)
 691       _GLIBCXX_NOEXCEPT_IF( noexcept(declval<_Base&>().swap(__x)) )
 692       {
 693         _Safe::_M_swap(__x);
 694         _Base::swap(__x);
 695         std::swap(this->_M_guaranteed_capacity, __x._M_guaranteed_capacity);
 696       }
 697
 698       void
 699       clear() _GLIBCXX_NOEXCEPT
 700       {
 701         _Base::clear();
 702         this->_M_invalidate_all();
 703       }
 704
 705       _Base&
 706       _M_base() _GLIBCXX_NOEXCEPT { return *this; }
 707
 708       const _Base&
 709       _M_base() const _GLIBCXX_NOEXCEPT { return *this; }
 710
 711     private:
 712       void
 713       _M_invalidate_after_nth(difference_type __n) _GLIBCXX_NOEXCEPT
 714       {
 715         typedef __gnu_debug::_After_nth_from<_Base_const_iterator> _After_nth;
 716         this->_M_invalidate_if(_After_nth(__n, _Base::begin()));
 717       }
 718     };
 719
 720   template<typename _Tp, typename _Alloc>
 721     inline bool
 722     operator==(const vector<_Tp, _Alloc>& __lhs,
 723                const vector<_Tp, _Alloc>& __rhs)
 724     { return __lhs._M_base() == __rhs._M_base(); }
 725
 726   template<typename _Tp, typename _Alloc>
 727     inline bool
 728     operator!=(const vector<_Tp, _Alloc>& __lhs,
 729                const vector<_Tp, _Alloc>& __rhs)
 730     { return __lhs._M_base() != __rhs._M_base(); }
 731
 732   template<typename _Tp, typename _Alloc>
 733     inline bool
 734     operator<(const vector<_Tp, _Alloc>& __lhs,
 735               const vector<_Tp, _Alloc>& __rhs)
 736     { return __lhs._M_base() < __rhs._M_base(); }
 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   template<typename _Tp, typename _Alloc>
 745     inline bool
 746     operator>=(const vector<_Tp, _Alloc>& __lhs,
 747                const vector<_Tp, _Alloc>& __rhs)
 748     { return __lhs._M_base() >= __rhs._M_base(); }
 749
 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 void
 758     swap(vector<_Tp, _Alloc>& __lhs, vector<_Tp, _Alloc>& __rhs)
 759     _GLIBCXX_NOEXCEPT_IF(noexcept(__lhs.swap(__rhs)))
 760     { __lhs.swap(__rhs); }
 761
 762 #if __cpp_deduction_guides >= 201606
 763   template<typename _InputIterator, typename _ValT
 764              = typename iterator_traits<_InputIterator>::value_type,
 765            typename _Allocator = allocator<_ValT>,
 766            typename = _RequireInputIter<_InputIterator>,
 767            typename = _RequireAllocator<_Allocator>>
 768     vector(_InputIterator, _InputIterator, _Allocator = _Allocator())
 769       -> vector<_ValT, _Allocator>;
 770 #endif
 771
 772 } // namespace __debug
 773
 774 #if __cplusplus >= 201103L
 775 _GLIBCXX_BEGIN_NAMESPACE_VERSION
 776
 777   // DR 1182.
 778   /// std::hash specialization for vector<bool>.
 779   template<typename _Alloc>
 780     struct hash<__debug::vector<bool, _Alloc>>
 781     : public __hash_base<size_t, __debug::vector<bool, _Alloc>>
 782     {
 783       size_t
 784       operator()(const __debug::vector<bool, _Alloc>& __b) const noexcept
 785       { return std::hash<_GLIBCXX_STD_C::vector<bool, _Alloc>>()(__b); }
 786     };
 787
 788  template<typename _Iterator, typename _Container, typename _Sequence>
 789     _Iterator
 790     __niter_base(const __gnu_debug::_Safe_iterator<
 791                  __gnu_cxx::__normal_iterator<_Iterator, _Container>,
 792                  _Sequence>& __it)
 793     { return std::__niter_base(__it.base()); }
 794
 795 _GLIBCXX_END_NAMESPACE_VERSION
 796 #endif
 797
 798 } // namespace std
 799
 800 namespace __gnu_debug
 801 {
 802   template<typename _Tp, typename _Alloc>
 803     struct _Is_contiguous_sequence<std::__debug::vector<_Tp, _Alloc> >
 804     : std::__true_type
 805     { };
 806
 807   template<typename _Alloc>
 808     struct _Is_contiguous_sequence<std::__debug::vector<bool, _Alloc> >
 809     : std::__false_type
 810     { };
 811 }
 812
 813 #endif