libstdc++
vector
Go to the documentation of this file.
00001 // Debugging vector implementation -*- C++ -*-
00002 
00003 // Copyright (C) 2003-2019 Free Software Foundation, Inc.
00004 //
00005 // This file is part of the GNU ISO C++ Library.  This library is free
00006 // software; you can redistribute it and/or modify it under the
00007 // terms of the GNU General Public License as published by the
00008 // Free Software Foundation; either version 3, or (at your option)
00009 // any later version.
00010 
00011 // This library is distributed in the hope that it will be useful,
00012 // but WITHOUT ANY WARRANTY; without even the implied warranty of
00013 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
00014 // GNU General Public License for more details.
00015 
00016 // Under Section 7 of GPL version 3, you are granted additional
00017 // permissions described in the GCC Runtime Library Exception, version
00018 // 3.1, as published by the Free Software Foundation.
00019 
00020 // You should have received a copy of the GNU General Public License and
00021 // a copy of the GCC Runtime Library Exception along with this program;
00022 // see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see
00023 // <http://www.gnu.org/licenses/>.
00024 
00025 /** @file debug/vector
00026  *  This file is a GNU debug extension to the Standard C++ Library.
00027  */
00028 
00029 #ifndef _GLIBCXX_DEBUG_VECTOR
00030 #define _GLIBCXX_DEBUG_VECTOR 1
00031 
00032 #pragma GCC system_header
00033 
00034 #include <bits/c++config.h>
00035 namespace std _GLIBCXX_VISIBILITY(default) { namespace __debug {
00036   template<typename _Tp, typename _Allocator> class vector;
00037 } } // namespace std::__debug
00038 
00039 #include <vector>
00040 #include <utility>
00041 #include <debug/safe_sequence.h>
00042 #include <debug/safe_container.h>
00043 #include <debug/safe_iterator.h>
00044 
00045 namespace __gnu_debug
00046 {
00047   /** @brief Base class for Debug Mode vector.
00048    *
00049    * Adds information about the guaranteed capacity, which is useful for
00050    * detecting code which relies on non-portable implementation details of
00051    * the libstdc++ reallocation policy.
00052    */
00053   template<typename _SafeSequence,
00054            typename _BaseSequence>
00055     class _Safe_vector
00056     {
00057       typedef typename _BaseSequence::size_type size_type;
00058 
00059       const _SafeSequence&
00060       _M_seq() const { return *static_cast<const _SafeSequence*>(this); }
00061 
00062     protected:
00063       _Safe_vector() _GLIBCXX_NOEXCEPT
00064         : _M_guaranteed_capacity(0)
00065       { _M_update_guaranteed_capacity(); }
00066 
00067       _Safe_vector(const _Safe_vector&) _GLIBCXX_NOEXCEPT
00068         : _M_guaranteed_capacity(0)
00069       { _M_update_guaranteed_capacity(); }
00070 
00071       _Safe_vector(size_type __n) _GLIBCXX_NOEXCEPT
00072         : _M_guaranteed_capacity(__n)
00073       { }
00074 
00075 #if __cplusplus >= 201103L
00076       _Safe_vector(_Safe_vector&& __x) noexcept
00077         : _Safe_vector()
00078       { __x._M_guaranteed_capacity = 0; }
00079 
00080       _Safe_vector&
00081       operator=(const _Safe_vector&) noexcept
00082       {
00083         _M_update_guaranteed_capacity();
00084         return *this;
00085       }
00086 
00087       _Safe_vector&
00088       operator=(_Safe_vector&& __x) noexcept
00089       {
00090         _M_update_guaranteed_capacity();
00091         __x._M_guaranteed_capacity = 0;
00092         return *this;
00093       }
00094 #endif
00095 
00096       size_type _M_guaranteed_capacity;
00097 
00098       bool
00099       _M_requires_reallocation(size_type __elements) const _GLIBCXX_NOEXCEPT
00100       { return __elements > _M_seq().capacity(); }
00101 
00102       void
00103       _M_update_guaranteed_capacity() _GLIBCXX_NOEXCEPT
00104       {
00105         if (_M_seq().size() > _M_guaranteed_capacity)
00106           _M_guaranteed_capacity = _M_seq().size();
00107       }
00108     };
00109 }
00110 
00111 namespace std _GLIBCXX_VISIBILITY(default)
00112 {
00113 namespace __debug
00114 {
00115   /// Class std::vector with safety/checking/debug instrumentation.
00116   template<typename _Tp,
00117            typename _Allocator = std::allocator<_Tp> >
00118     class vector
00119     : public __gnu_debug::_Safe_container<
00120         vector<_Tp, _Allocator>, _Allocator, __gnu_debug::_Safe_sequence>,
00121       public _GLIBCXX_STD_C::vector<_Tp, _Allocator>,
00122       public __gnu_debug::_Safe_vector<
00123         vector<_Tp, _Allocator>,
00124         _GLIBCXX_STD_C::vector<_Tp, _Allocator> >
00125     {
00126       typedef _GLIBCXX_STD_C::vector<_Tp, _Allocator>           _Base;
00127       typedef __gnu_debug::_Safe_container<
00128         vector, _Allocator, __gnu_debug::_Safe_sequence>        _Safe;
00129       typedef __gnu_debug::_Safe_vector<vector, _Base>          _Safe_vector;
00130 
00131       typedef typename _Base::iterator          _Base_iterator;
00132       typedef typename _Base::const_iterator    _Base_const_iterator;
00133       typedef __gnu_debug::_Equal_to<_Base_const_iterator> _Equal;
00134 
00135       template<typename _ItT, typename _SeqT, typename _CatT>
00136         friend class ::__gnu_debug::_Safe_iterator;
00137 
00138     public:
00139       typedef typename _Base::reference                 reference;
00140       typedef typename _Base::const_reference           const_reference;
00141 
00142       typedef __gnu_debug::_Safe_iterator<
00143         _Base_iterator, vector>                         iterator;
00144       typedef __gnu_debug::_Safe_iterator<
00145         _Base_const_iterator, vector>                   const_iterator;
00146 
00147       typedef typename _Base::size_type                 size_type;
00148       typedef typename _Base::difference_type           difference_type;
00149 
00150       typedef _Tp                                       value_type;
00151       typedef _Allocator                                allocator_type;
00152       typedef typename _Base::pointer                   pointer;
00153       typedef typename _Base::const_pointer             const_pointer;
00154       typedef std::reverse_iterator<iterator>           reverse_iterator;
00155       typedef std::reverse_iterator<const_iterator>     const_reverse_iterator;
00156 
00157       // 23.2.4.1 construct/copy/destroy:
00158 
00159 #if __cplusplus < 201103L
00160       vector() _GLIBCXX_NOEXCEPT
00161       : _Base() { }
00162 #else
00163       vector() = default;
00164 #endif
00165 
00166       explicit
00167       vector(const _Allocator& __a) _GLIBCXX_NOEXCEPT
00168       : _Base(__a) { }
00169 
00170 #if __cplusplus >= 201103L
00171       explicit
00172       vector(size_type __n, const _Allocator& __a = _Allocator())
00173       : _Base(__n, __a), _Safe_vector(__n) { }
00174 
00175       vector(size_type __n, const _Tp& __value,
00176              const _Allocator& __a = _Allocator())
00177       : _Base(__n, __value, __a) { }
00178 #else
00179       explicit
00180       vector(size_type __n, const _Tp& __value = _Tp(),
00181              const _Allocator& __a = _Allocator())
00182       : _Base(__n, __value, __a) { }
00183 #endif
00184 
00185 #if __cplusplus >= 201103L
00186       template<class _InputIterator,
00187                typename = std::_RequireInputIter<_InputIterator>>
00188 #else
00189       template<class _InputIterator>
00190 #endif
00191         vector(_InputIterator __first, _InputIterator __last,
00192                const _Allocator& __a = _Allocator())
00193         : _Base(__gnu_debug::__base(
00194                   __glibcxx_check_valid_constructor_range(__first, __last)),
00195                 __gnu_debug::__base(__last), __a) { }
00196 
00197 #if __cplusplus < 201103L
00198       vector(const vector& __x)
00199       : _Base(__x) { }
00200 
00201       ~vector() _GLIBCXX_NOEXCEPT { }
00202 #else
00203       vector(const vector&) = default;
00204       vector(vector&&) = default;
00205 
00206       vector(const vector& __x, const allocator_type& __a)
00207       : _Base(__x, __a) { }
00208 
00209       vector(vector&& __x, const allocator_type& __a)
00210         noexcept( noexcept(
00211           _Base(std::declval<_Base&&>()), std::declval<const allocator_type&>()) )
00212       : _Safe(std::move(__x._M_safe()), __a),
00213         _Base(std::move(__x._M_base()), __a),
00214         _Safe_vector(std::move(__x)) { }
00215 
00216       vector(initializer_list<value_type> __l,
00217              const allocator_type& __a = allocator_type())
00218       : _Base(__l, __a) { }
00219 
00220       ~vector() = default;
00221 #endif
00222 
00223       /// Construction from a normal-mode vector
00224       vector(const _Base& __x)
00225       : _Base(__x) { }
00226 
00227 #if __cplusplus < 201103L
00228       vector&
00229       operator=(const vector& __x)
00230       {
00231         this->_M_safe() = __x;
00232         _M_base() = __x;
00233         this->_M_update_guaranteed_capacity();
00234         return *this;
00235       }
00236 #else
00237       vector&
00238       operator=(const vector&) = default;
00239 
00240       vector&
00241       operator=(vector&&) = default;
00242 
00243       vector&
00244       operator=(initializer_list<value_type> __l)
00245       {
00246         _M_base() = __l;
00247         this->_M_invalidate_all();
00248         this->_M_update_guaranteed_capacity();
00249         return *this;
00250       }
00251 #endif
00252 
00253 #if __cplusplus >= 201103L
00254       template<typename _InputIterator,
00255                typename = std::_RequireInputIter<_InputIterator>>
00256 #else
00257       template<typename _InputIterator>
00258 #endif
00259         void
00260         assign(_InputIterator __first, _InputIterator __last)
00261         {
00262           typename __gnu_debug::_Distance_traits<_InputIterator>::__type __dist;
00263           __glibcxx_check_valid_range2(__first, __last, __dist);
00264 
00265           if (__dist.second >= __gnu_debug::__dp_sign)
00266             _Base::assign(__gnu_debug::__unsafe(__first),
00267                           __gnu_debug::__unsafe(__last));
00268           else
00269             _Base::assign(__first, __last);
00270 
00271           this->_M_invalidate_all();
00272           this->_M_update_guaranteed_capacity();
00273         }
00274 
00275       void
00276       assign(size_type __n, const _Tp& __u)
00277       {
00278         _Base::assign(__n, __u);
00279         this->_M_invalidate_all();
00280         this->_M_update_guaranteed_capacity();
00281       }
00282 
00283 #if __cplusplus >= 201103L
00284       void
00285       assign(initializer_list<value_type> __l)
00286       {
00287         _Base::assign(__l);
00288         this->_M_invalidate_all();
00289         this->_M_update_guaranteed_capacity();
00290       }
00291 #endif
00292 
00293       using _Base::get_allocator;
00294 
00295       // iterators:
00296       iterator
00297       begin() _GLIBCXX_NOEXCEPT
00298       { return iterator(_Base::begin(), this); }
00299 
00300       const_iterator
00301       begin() const _GLIBCXX_NOEXCEPT
00302       { return const_iterator(_Base::begin(), this); }
00303 
00304       iterator
00305       end() _GLIBCXX_NOEXCEPT
00306       { return iterator(_Base::end(), this); }
00307 
00308       const_iterator
00309       end() const _GLIBCXX_NOEXCEPT
00310       { return const_iterator(_Base::end(), this); }
00311 
00312       reverse_iterator
00313       rbegin() _GLIBCXX_NOEXCEPT
00314       { return reverse_iterator(end()); }
00315 
00316       const_reverse_iterator
00317       rbegin() const _GLIBCXX_NOEXCEPT
00318       { return const_reverse_iterator(end()); }
00319 
00320       reverse_iterator
00321       rend() _GLIBCXX_NOEXCEPT
00322       { return reverse_iterator(begin()); }
00323 
00324       const_reverse_iterator
00325       rend() const _GLIBCXX_NOEXCEPT
00326       { return const_reverse_iterator(begin()); }
00327 
00328 #if __cplusplus >= 201103L
00329       const_iterator
00330       cbegin() const noexcept
00331       { return const_iterator(_Base::begin(), this); }
00332 
00333       const_iterator
00334       cend() const noexcept
00335       { return const_iterator(_Base::end(), this); }
00336 
00337       const_reverse_iterator
00338       crbegin() const noexcept
00339       { return const_reverse_iterator(end()); }
00340 
00341       const_reverse_iterator
00342       crend() const noexcept
00343       { return const_reverse_iterator(begin()); }
00344 #endif
00345 
00346       // 23.2.4.2 capacity:
00347       using _Base::size;
00348       using _Base::max_size;
00349 
00350 #if __cplusplus >= 201103L
00351       void
00352       resize(size_type __sz)
00353       {
00354         bool __realloc = this->_M_requires_reallocation(__sz);
00355         if (__sz < this->size())
00356           this->_M_invalidate_after_nth(__sz);
00357         _Base::resize(__sz);
00358         if (__realloc)
00359           this->_M_invalidate_all();
00360         this->_M_update_guaranteed_capacity();
00361       }
00362 
00363       void
00364       resize(size_type __sz, const _Tp& __c)
00365       {
00366         bool __realloc = this->_M_requires_reallocation(__sz);
00367         if (__sz < this->size())
00368           this->_M_invalidate_after_nth(__sz);
00369         _Base::resize(__sz, __c);
00370         if (__realloc)
00371           this->_M_invalidate_all();
00372         this->_M_update_guaranteed_capacity();
00373       }
00374 #else
00375       void
00376       resize(size_type __sz, _Tp __c = _Tp())
00377       {
00378         bool __realloc = this->_M_requires_reallocation(__sz);
00379         if (__sz < this->size())
00380           this->_M_invalidate_after_nth(__sz);
00381         _Base::resize(__sz, __c);
00382         if (__realloc)
00383           this->_M_invalidate_all();
00384         this->_M_update_guaranteed_capacity();
00385       }
00386 #endif
00387 
00388 #if __cplusplus >= 201103L
00389       void
00390       shrink_to_fit()
00391       {
00392         if (_Base::_M_shrink_to_fit())
00393           {
00394             this->_M_guaranteed_capacity = _Base::capacity();
00395             this->_M_invalidate_all();
00396           }
00397       }
00398 #endif
00399 
00400       size_type
00401       capacity() const _GLIBCXX_NOEXCEPT
00402       {
00403 #ifdef _GLIBCXX_DEBUG_PEDANTIC
00404         return this->_M_guaranteed_capacity;
00405 #else
00406         return _Base::capacity();
00407 #endif
00408       }
00409 
00410       using _Base::empty;
00411 
00412       void
00413       reserve(size_type __n)
00414       {
00415         bool __realloc = this->_M_requires_reallocation(__n);
00416         _Base::reserve(__n);
00417         if (__n > this->_M_guaranteed_capacity)
00418           this->_M_guaranteed_capacity = __n;
00419         if (__realloc)
00420           this->_M_invalidate_all();
00421       }
00422 
00423       // element access:
00424       reference
00425       operator[](size_type __n) _GLIBCXX_NOEXCEPT
00426       {
00427         __glibcxx_check_subscript(__n);
00428         return _M_base()[__n];
00429       }
00430 
00431       const_reference
00432       operator[](size_type __n) const _GLIBCXX_NOEXCEPT
00433       {
00434         __glibcxx_check_subscript(__n);
00435         return _M_base()[__n];
00436       }
00437 
00438       using _Base::at;
00439 
00440       reference
00441       front() _GLIBCXX_NOEXCEPT
00442       {
00443         __glibcxx_check_nonempty();
00444         return _Base::front();
00445       }
00446 
00447       const_reference
00448       front() const _GLIBCXX_NOEXCEPT
00449       {
00450         __glibcxx_check_nonempty();
00451         return _Base::front();
00452       }
00453 
00454       reference
00455       back() _GLIBCXX_NOEXCEPT
00456       {
00457         __glibcxx_check_nonempty();
00458         return _Base::back();
00459       }
00460 
00461       const_reference
00462       back() const _GLIBCXX_NOEXCEPT
00463       {
00464         __glibcxx_check_nonempty();
00465         return _Base::back();
00466       }
00467 
00468       // _GLIBCXX_RESOLVE_LIB_DEFECTS
00469       // DR 464. Suggestion for new member functions in standard containers.
00470       using _Base::data;
00471 
00472       // 23.2.4.3 modifiers:
00473       void
00474       push_back(const _Tp& __x)
00475       {
00476         bool __realloc = this->_M_requires_reallocation(this->size() + 1);
00477         _Base::push_back(__x);
00478         if (__realloc)
00479           this->_M_invalidate_all();
00480         this->_M_update_guaranteed_capacity();
00481       }
00482 
00483 #if __cplusplus >= 201103L
00484       template<typename _Up = _Tp>
00485         typename __gnu_cxx::__enable_if<!std::__are_same<_Up, bool>::__value,
00486                                         void>::__type
00487         push_back(_Tp&& __x)
00488         { emplace_back(std::move(__x)); }
00489 
00490       template<typename... _Args>
00491 #if __cplusplus > 201402L
00492         reference
00493 #else
00494         void
00495 #endif
00496         emplace_back(_Args&&... __args)
00497         {
00498           bool __realloc = this->_M_requires_reallocation(this->size() + 1);
00499           _Base::emplace_back(std::forward<_Args>(__args)...);
00500           if (__realloc)
00501             this->_M_invalidate_all();
00502           this->_M_update_guaranteed_capacity();
00503 #if __cplusplus > 201402L
00504           return back();
00505 #endif
00506         }
00507 #endif
00508 
00509       void
00510       pop_back() _GLIBCXX_NOEXCEPT
00511       {
00512         __glibcxx_check_nonempty();
00513         this->_M_invalidate_if(_Equal(--_Base::end()));
00514         _Base::pop_back();
00515       }
00516 
00517 #if __cplusplus >= 201103L
00518       template<typename... _Args>
00519         iterator
00520         emplace(const_iterator __position, _Args&&... __args)
00521         {
00522           __glibcxx_check_insert(__position);
00523           bool __realloc = this->_M_requires_reallocation(this->size() + 1);
00524           difference_type __offset = __position.base() - _Base::cbegin();
00525           _Base_iterator __res = _Base::emplace(__position.base(),
00526                                                 std::forward<_Args>(__args)...);
00527           if (__realloc)
00528             this->_M_invalidate_all();
00529           else
00530             this->_M_invalidate_after_nth(__offset);
00531           this->_M_update_guaranteed_capacity();
00532           return { __res, this };
00533         }
00534 #endif
00535 
00536       iterator
00537 #if __cplusplus >= 201103L
00538       insert(const_iterator __position, const _Tp& __x)
00539 #else
00540       insert(iterator __position, const _Tp& __x)
00541 #endif
00542       {
00543         __glibcxx_check_insert(__position);
00544         bool __realloc = this->_M_requires_reallocation(this->size() + 1);
00545         difference_type __offset = __position.base() - _Base::begin();
00546         _Base_iterator __res = _Base::insert(__position.base(), __x);
00547         if (__realloc)
00548           this->_M_invalidate_all();
00549         else
00550           this->_M_invalidate_after_nth(__offset);
00551         this->_M_update_guaranteed_capacity();
00552         return iterator(__res, this);
00553       }
00554 
00555 #if __cplusplus >= 201103L
00556       template<typename _Up = _Tp>
00557         typename __gnu_cxx::__enable_if<!std::__are_same<_Up, bool>::__value,
00558                                         iterator>::__type
00559         insert(const_iterator __position, _Tp&& __x)
00560         { return emplace(__position, std::move(__x)); }
00561 
00562       iterator
00563       insert(const_iterator __position, initializer_list<value_type> __l)
00564       { return this->insert(__position, __l.begin(), __l.end()); }
00565 #endif
00566 
00567 #if __cplusplus >= 201103L
00568       iterator
00569       insert(const_iterator __position, size_type __n, const _Tp& __x)
00570       {
00571         __glibcxx_check_insert(__position);
00572         bool __realloc = this->_M_requires_reallocation(this->size() + __n);
00573         difference_type __offset = __position.base() - _Base::cbegin();
00574         _Base_iterator __res = _Base::insert(__position.base(), __n, __x);
00575         if (__realloc)
00576           this->_M_invalidate_all();
00577         else
00578           this->_M_invalidate_after_nth(__offset);
00579         this->_M_update_guaranteed_capacity();
00580         return { __res, this };
00581       }
00582 #else
00583       void
00584       insert(iterator __position, size_type __n, const _Tp& __x)
00585       {
00586         __glibcxx_check_insert(__position);
00587         bool __realloc = this->_M_requires_reallocation(this->size() + __n);
00588         difference_type __offset = __position.base() - _Base::begin();
00589         _Base::insert(__position.base(), __n, __x);
00590         if (__realloc)
00591           this->_M_invalidate_all();
00592         else
00593           this->_M_invalidate_after_nth(__offset);
00594         this->_M_update_guaranteed_capacity();
00595       }
00596 #endif
00597 
00598 #if __cplusplus >= 201103L
00599       template<class _InputIterator,
00600                typename = std::_RequireInputIter<_InputIterator>>
00601         iterator
00602         insert(const_iterator __position,
00603                _InputIterator __first, _InputIterator __last)
00604         {
00605           typename __gnu_debug::_Distance_traits<_InputIterator>::__type __dist;
00606           __glibcxx_check_insert_range(__position, __first, __last, __dist);
00607 
00608           /* Hard to guess if invalidation will occur, because __last
00609              - __first can't be calculated in all cases, so we just
00610              punt here by checking if it did occur. */
00611           _Base_iterator __old_begin = _M_base().begin();
00612           difference_type __offset = __position.base() - _Base::cbegin();
00613           _Base_iterator __res;
00614           if (__dist.second >= __gnu_debug::__dp_sign)
00615             __res = _Base::insert(__position.base(),
00616                                   __gnu_debug::__unsafe(__first),
00617                                   __gnu_debug::__unsafe(__last));
00618           else
00619             __res = _Base::insert(__position.base(), __first, __last);
00620 
00621           if (_M_base().begin() != __old_begin)
00622             this->_M_invalidate_all();
00623           else
00624             this->_M_invalidate_after_nth(__offset);
00625           this->_M_update_guaranteed_capacity();
00626           return { __res, this };
00627         }
00628 #else
00629       template<class _InputIterator>
00630         void
00631         insert(iterator __position,
00632                _InputIterator __first, _InputIterator __last)
00633         {
00634           typename __gnu_debug::_Distance_traits<_InputIterator>::__type __dist;
00635           __glibcxx_check_insert_range(__position, __first, __last, __dist);
00636 
00637           /* Hard to guess if invalidation will occur, because __last
00638              - __first can't be calculated in all cases, so we just
00639              punt here by checking if it did occur. */
00640           _Base_iterator __old_begin = _M_base().begin();
00641           difference_type __offset = __position.base() - _Base::begin();
00642           if (__dist.second >= __gnu_debug::__dp_sign)
00643             _Base::insert(__position.base(), __gnu_debug::__unsafe(__first),
00644                                              __gnu_debug::__unsafe(__last));
00645           else
00646             _Base::insert(__position.base(), __first, __last);
00647 
00648           if (_M_base().begin() != __old_begin)
00649             this->_M_invalidate_all();
00650           else
00651             this->_M_invalidate_after_nth(__offset);
00652           this->_M_update_guaranteed_capacity();
00653         }
00654 #endif
00655 
00656       iterator
00657 #if __cplusplus >= 201103L
00658       erase(const_iterator __position)
00659 #else
00660       erase(iterator __position)
00661 #endif
00662       {
00663         __glibcxx_check_erase(__position);
00664         difference_type __offset = __position.base() - _Base::begin();
00665         _Base_iterator __res = _Base::erase(__position.base());
00666         this->_M_invalidate_after_nth(__offset);
00667         return iterator(__res, this);
00668       }
00669 
00670       iterator
00671 #if __cplusplus >= 201103L
00672       erase(const_iterator __first, const_iterator __last)
00673 #else
00674       erase(iterator __first, iterator __last)
00675 #endif
00676       {
00677         // _GLIBCXX_RESOLVE_LIB_DEFECTS
00678         // 151. can't currently clear() empty container
00679         __glibcxx_check_erase_range(__first, __last);
00680 
00681         if (__first.base() != __last.base())
00682           {
00683             difference_type __offset = __first.base() - _Base::begin();
00684             _Base_iterator __res = _Base::erase(__first.base(),
00685                                                 __last.base());
00686             this->_M_invalidate_after_nth(__offset);
00687             return iterator(__res, this);
00688           }
00689         else
00690 #if __cplusplus >= 201103L
00691           return { _Base::begin() + (__first.base() - _Base::cbegin()), this };
00692 #else
00693           return __first;
00694 #endif
00695       }
00696 
00697       void
00698       swap(vector& __x)
00699       _GLIBCXX_NOEXCEPT_IF( noexcept(declval<_Base&>().swap(__x)) )
00700       {
00701         _Safe::_M_swap(__x);
00702         _Base::swap(__x);
00703         std::swap(this->_M_guaranteed_capacity, __x._M_guaranteed_capacity);
00704       }
00705 
00706       void
00707       clear() _GLIBCXX_NOEXCEPT
00708       {
00709         _Base::clear();
00710         this->_M_invalidate_all();
00711       }
00712 
00713       _Base&
00714       _M_base() _GLIBCXX_NOEXCEPT { return *this; }
00715 
00716       const _Base&
00717       _M_base() const _GLIBCXX_NOEXCEPT { return *this; }
00718 
00719     private:
00720       void
00721       _M_invalidate_after_nth(difference_type __n) _GLIBCXX_NOEXCEPT
00722       {
00723         typedef __gnu_debug::_After_nth_from<_Base_const_iterator> _After_nth;
00724         this->_M_invalidate_if(_After_nth(__n, _Base::begin()));
00725       }
00726     };
00727 
00728   template<typename _Tp, typename _Alloc>
00729     inline bool
00730     operator==(const vector<_Tp, _Alloc>& __lhs,
00731                const vector<_Tp, _Alloc>& __rhs)
00732     { return __lhs._M_base() == __rhs._M_base(); }
00733 
00734   template<typename _Tp, typename _Alloc>
00735     inline bool
00736     operator!=(const vector<_Tp, _Alloc>& __lhs,
00737                const vector<_Tp, _Alloc>& __rhs)
00738     { return __lhs._M_base() != __rhs._M_base(); }
00739 
00740   template<typename _Tp, typename _Alloc>
00741     inline bool
00742     operator<(const vector<_Tp, _Alloc>& __lhs,
00743               const vector<_Tp, _Alloc>& __rhs)
00744     { return __lhs._M_base() < __rhs._M_base(); }
00745 
00746   template<typename _Tp, typename _Alloc>
00747     inline bool
00748     operator<=(const vector<_Tp, _Alloc>& __lhs,
00749                const vector<_Tp, _Alloc>& __rhs)
00750     { return __lhs._M_base() <= __rhs._M_base(); }
00751 
00752   template<typename _Tp, typename _Alloc>
00753     inline bool
00754     operator>=(const vector<_Tp, _Alloc>& __lhs,
00755                const vector<_Tp, _Alloc>& __rhs)
00756     { return __lhs._M_base() >= __rhs._M_base(); }
00757 
00758   template<typename _Tp, typename _Alloc>
00759     inline bool
00760     operator>(const vector<_Tp, _Alloc>& __lhs,
00761               const vector<_Tp, _Alloc>& __rhs)
00762     { return __lhs._M_base() > __rhs._M_base(); }
00763 
00764   template<typename _Tp, typename _Alloc>
00765     inline void
00766     swap(vector<_Tp, _Alloc>& __lhs, vector<_Tp, _Alloc>& __rhs)
00767     _GLIBCXX_NOEXCEPT_IF(noexcept(__lhs.swap(__rhs)))
00768     { __lhs.swap(__rhs); }
00769 
00770 #if __cpp_deduction_guides >= 201606
00771   template<typename _InputIterator, typename _ValT
00772              = typename iterator_traits<_InputIterator>::value_type,
00773            typename _Allocator = allocator<_ValT>,
00774            typename = _RequireInputIter<_InputIterator>,
00775            typename = _RequireAllocator<_Allocator>>
00776     vector(_InputIterator, _InputIterator, _Allocator = _Allocator())
00777       -> vector<_ValT, _Allocator>;
00778 #endif
00779 
00780 } // namespace __debug
00781 
00782 _GLIBCXX_BEGIN_NAMESPACE_VERSION
00783 
00784 #if __cplusplus >= 201103L
00785   // DR 1182.
00786   /// std::hash specialization for vector<bool>.
00787   template<typename _Alloc>
00788     struct hash<__debug::vector<bool, _Alloc>>
00789     : public __hash_base<size_t, __debug::vector<bool, _Alloc>>
00790     {
00791       size_t
00792       operator()(const __debug::vector<bool, _Alloc>& __b) const noexcept
00793       { return std::hash<_GLIBCXX_STD_C::vector<bool, _Alloc>>()(__b); }
00794     };
00795 #endif
00796 
00797  template<typename _Iterator, typename _Container, typename _Sequence>
00798     _Iterator
00799     __niter_base(const __gnu_debug::_Safe_iterator<
00800                  __gnu_cxx::__normal_iterator<_Iterator, _Container>,
00801                  _Sequence, std::random_access_iterator_tag>& __it)
00802     { return std::__niter_base(__it.base()); }
00803 
00804 #if __cplusplus >= 201703L
00805   namespace __detail::__variant
00806   {
00807     template<typename> struct _Never_valueless_alt; // see <variant>
00808 
00809     // Provide the strong exception-safety guarantee when emplacing a
00810     // vector into a variant, but only if move assignment cannot throw.
00811     template<typename _Tp, typename _Alloc>
00812       struct _Never_valueless_alt<__debug::vector<_Tp, _Alloc>>
00813       : std::is_nothrow_move_assignable<__debug::vector<_Tp, _Alloc>>
00814       { };
00815   }  // namespace __detail::__variant
00816 #endif // C++17
00817 
00818 _GLIBCXX_END_NAMESPACE_VERSION
00819 } // namespace std
00820 
00821 namespace __gnu_debug
00822 {
00823   template<typename _Tp, typename _Alloc>
00824     struct _Is_contiguous_sequence<std::__debug::vector<_Tp, _Alloc> >
00825     : std::__true_type
00826     { };
00827 
00828   template<typename _Alloc>
00829     struct _Is_contiguous_sequence<std::__debug::vector<bool, _Alloc> >
00830     : std::__false_type
00831     { };
00832 }
00833 
00834 #endif