libstdc++
vector
Go to the documentation of this file.
00001 // Debugging vector implementation -*- C++ -*-
00002 
00003 // Copyright (C) 2003-2015 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 #include <vector>
00033 #include <utility>
00034 #include <debug/safe_sequence.h>
00035 #include <debug/safe_container.h>
00036 #include <debug/safe_iterator.h>
00037 
00038 namespace __gnu_debug
00039 {
00040   /// Special vector safe base class to add a guaranteed capacity information
00041   /// useful to detect code relying on the libstdc++ reallocation management
00042   /// implementation detail.
00043   template<typename _SafeSequence,
00044            typename _BaseSequence>
00045     class _Safe_vector
00046     {
00047       typedef typename _BaseSequence::size_type size_type;
00048 
00049       const _SafeSequence&
00050       _M_seq() const { return *static_cast<const _SafeSequence*>(this); }
00051 
00052     protected:
00053       _Safe_vector() _GLIBCXX_NOEXCEPT
00054         : _M_guaranteed_capacity(0)
00055       { _M_update_guaranteed_capacity(); }
00056 
00057       _Safe_vector(const _Safe_vector&) _GLIBCXX_NOEXCEPT
00058         : _M_guaranteed_capacity(0)
00059       { _M_update_guaranteed_capacity(); }
00060 
00061       _Safe_vector(size_type __n) _GLIBCXX_NOEXCEPT
00062         : _M_guaranteed_capacity(__n)
00063       { }
00064 
00065 #if __cplusplus >= 201103L
00066       _Safe_vector(_Safe_vector&& __x) noexcept
00067         : _Safe_vector()
00068       { __x._M_guaranteed_capacity = 0; }
00069 
00070       _Safe_vector&
00071       operator=(const _Safe_vector&) noexcept
00072       {
00073         _M_update_guaranteed_capacity();
00074         return *this;
00075       }
00076 
00077       _Safe_vector&
00078       operator=(_Safe_vector&& __x) noexcept
00079       {
00080         _M_update_guaranteed_capacity();
00081         __x._M_guaranteed_capacity = 0;
00082         return *this;
00083       }
00084 #endif
00085 
00086       size_type _M_guaranteed_capacity;
00087 
00088       bool
00089       _M_requires_reallocation(size_type __elements) const _GLIBCXX_NOEXCEPT
00090       { return __elements > _M_seq().capacity(); }
00091 
00092       void
00093       _M_update_guaranteed_capacity() _GLIBCXX_NOEXCEPT
00094       {
00095         if (_M_seq().size() > _M_guaranteed_capacity)
00096           _M_guaranteed_capacity = _M_seq().size();
00097       }
00098     };
00099 }
00100 
00101 namespace std _GLIBCXX_VISIBILITY(default)
00102 {
00103 namespace __debug
00104 {
00105   /// Class std::vector with safety/checking/debug instrumentation.
00106   template<typename _Tp,
00107            typename _Allocator = std::allocator<_Tp> >
00108     class vector
00109     : public __gnu_debug::_Safe_container<
00110         vector<_Tp, _Allocator>, _Allocator, __gnu_debug::_Safe_sequence>,
00111       public _GLIBCXX_STD_C::vector<_Tp, _Allocator>,
00112       public __gnu_debug::_Safe_vector<
00113         vector<_Tp, _Allocator>,
00114         _GLIBCXX_STD_C::vector<_Tp, _Allocator> >
00115     {
00116       typedef _GLIBCXX_STD_C::vector<_Tp, _Allocator>           _Base;
00117       typedef __gnu_debug::_Safe_container<
00118         vector, _Allocator, __gnu_debug::_Safe_sequence>        _Safe;
00119       typedef __gnu_debug::_Safe_vector<vector, _Base>          _Safe_vector;
00120 
00121       typedef typename _Base::iterator          _Base_iterator;
00122       typedef typename _Base::const_iterator    _Base_const_iterator;
00123       typedef __gnu_debug::_Equal_to<_Base_const_iterator> _Equal;
00124 
00125     public:
00126       typedef typename _Base::reference                 reference;
00127       typedef typename _Base::const_reference           const_reference;
00128 
00129       typedef __gnu_debug::_Safe_iterator<
00130         _Base_iterator, vector>                         iterator;
00131       typedef __gnu_debug::_Safe_iterator<
00132         _Base_const_iterator, vector>                   const_iterator;
00133 
00134       typedef typename _Base::size_type                 size_type;
00135       typedef typename _Base::difference_type           difference_type;
00136 
00137       typedef _Tp                                       value_type;
00138       typedef _Allocator                                allocator_type;
00139       typedef typename _Base::pointer                   pointer;
00140       typedef typename _Base::const_pointer             const_pointer;
00141       typedef std::reverse_iterator<iterator>           reverse_iterator;
00142       typedef std::reverse_iterator<const_iterator>     const_reverse_iterator;
00143 
00144       // 23.2.4.1 construct/copy/destroy:
00145 
00146 #if __cplusplus < 201103L
00147       vector() _GLIBCXX_NOEXCEPT
00148       : _Base() { }
00149 #else
00150       vector() = default;
00151 #endif
00152 
00153       explicit
00154       vector(const _Allocator& __a) _GLIBCXX_NOEXCEPT
00155       : _Base(__a) { }
00156 
00157 #if __cplusplus >= 201103L
00158       explicit
00159       vector(size_type __n, const _Allocator& __a = _Allocator())
00160       : _Base(__n, __a), _Safe_vector(__n) { }
00161 
00162       vector(size_type __n, const _Tp& __value,
00163              const _Allocator& __a = _Allocator())
00164       : _Base(__n, __value, __a) { }
00165 #else
00166       explicit
00167       vector(size_type __n, const _Tp& __value = _Tp(),
00168              const _Allocator& __a = _Allocator())
00169       : _Base(__n, __value, __a) { }
00170 #endif
00171 
00172 #if __cplusplus >= 201103L
00173       template<class _InputIterator,
00174                typename = std::_RequireInputIter<_InputIterator>>
00175 #else
00176       template<class _InputIterator>
00177 #endif
00178         vector(_InputIterator __first, _InputIterator __last,
00179                const _Allocator& __a = _Allocator())
00180         : _Base(__gnu_debug::__base(__gnu_debug::__check_valid_range(__first,
00181                                                                      __last)),
00182                 __gnu_debug::__base(__last), __a) { }
00183 
00184 #if __cplusplus < 201103L
00185       vector(const vector& __x)
00186       : _Base(__x) { }
00187 
00188       ~vector() _GLIBCXX_NOEXCEPT { }
00189 #else
00190       vector(const vector&) = default;
00191       vector(vector&&) = default;
00192 
00193       vector(const vector& __x, const allocator_type& __a)
00194       : _Base(__x, __a) { }
00195 
00196       vector(vector&& __x, const allocator_type& __a)
00197       : _Safe(std::move(__x._M_safe()), __a),
00198         _Base(std::move(__x._M_base()), __a),
00199         _Safe_vector(std::move(__x)) { }
00200 
00201       vector(initializer_list<value_type> __l,
00202              const allocator_type& __a = allocator_type())
00203       : _Base(__l, __a) { }
00204 
00205       ~vector() = default;
00206 #endif
00207 
00208       /// Construction from a normal-mode vector
00209       vector(const _Base& __x)
00210       : _Base(__x) { }
00211 
00212 #if __cplusplus < 201103L
00213       vector&
00214       operator=(const vector& __x)
00215       {
00216         this->_M_safe() = __x;
00217         _M_base() = __x;
00218         this->_M_update_guaranteed_capacity();
00219         return *this;
00220       }
00221 #else
00222       vector&
00223       operator=(const vector&) = default;
00224 
00225       vector&
00226       operator=(vector&&) = default;
00227 
00228       vector&
00229       operator=(initializer_list<value_type> __l)
00230       {
00231         _M_base() = __l;
00232         this->_M_invalidate_all();
00233         this->_M_update_guaranteed_capacity();
00234         return *this;
00235       }
00236 #endif
00237 
00238 #if __cplusplus >= 201103L
00239       template<typename _InputIterator,
00240                typename = std::_RequireInputIter<_InputIterator>>
00241 #else
00242       template<typename _InputIterator>
00243 #endif
00244         void
00245         assign(_InputIterator __first, _InputIterator __last)
00246         {
00247           __glibcxx_check_valid_range(__first, __last);
00248           _Base::assign(__gnu_debug::__base(__first),
00249                         __gnu_debug::__base(__last));
00250           this->_M_invalidate_all();
00251           this->_M_update_guaranteed_capacity();
00252         }
00253 
00254       void
00255       assign(size_type __n, const _Tp& __u)
00256       {
00257         _Base::assign(__n, __u);
00258         this->_M_invalidate_all();
00259         this->_M_update_guaranteed_capacity();
00260       }
00261 
00262 #if __cplusplus >= 201103L
00263       void
00264       assign(initializer_list<value_type> __l)
00265       {
00266         _Base::assign(__l);
00267         this->_M_invalidate_all();
00268         this->_M_update_guaranteed_capacity();
00269       }
00270 #endif
00271 
00272       using _Base::get_allocator;
00273 
00274       // iterators:
00275       iterator
00276       begin() _GLIBCXX_NOEXCEPT
00277       { return iterator(_Base::begin(), this); }
00278 
00279       const_iterator
00280       begin() const _GLIBCXX_NOEXCEPT
00281       { return const_iterator(_Base::begin(), this); }
00282 
00283       iterator
00284       end() _GLIBCXX_NOEXCEPT
00285       { return iterator(_Base::end(), this); }
00286 
00287       const_iterator
00288       end() const _GLIBCXX_NOEXCEPT
00289       { return const_iterator(_Base::end(), this); }
00290 
00291       reverse_iterator
00292       rbegin() _GLIBCXX_NOEXCEPT
00293       { return reverse_iterator(end()); }
00294 
00295       const_reverse_iterator
00296       rbegin() const _GLIBCXX_NOEXCEPT
00297       { return const_reverse_iterator(end()); }
00298 
00299       reverse_iterator
00300       rend() _GLIBCXX_NOEXCEPT
00301       { return reverse_iterator(begin()); }
00302 
00303       const_reverse_iterator
00304       rend() const _GLIBCXX_NOEXCEPT
00305       { return const_reverse_iterator(begin()); }
00306 
00307 #if __cplusplus >= 201103L
00308       const_iterator
00309       cbegin() const noexcept
00310       { return const_iterator(_Base::begin(), this); }
00311 
00312       const_iterator
00313       cend() const noexcept
00314       { return const_iterator(_Base::end(), this); }
00315 
00316       const_reverse_iterator
00317       crbegin() const noexcept
00318       { return const_reverse_iterator(end()); }
00319 
00320       const_reverse_iterator
00321       crend() const noexcept
00322       { return const_reverse_iterator(begin()); }
00323 #endif
00324 
00325       // 23.2.4.2 capacity:
00326       using _Base::size;
00327       using _Base::max_size;
00328 
00329 #if __cplusplus >= 201103L
00330       void
00331       resize(size_type __sz)
00332       {
00333         bool __realloc = this->_M_requires_reallocation(__sz);
00334         if (__sz < this->size())
00335           this->_M_invalidate_after_nth(__sz);
00336         _Base::resize(__sz);
00337         if (__realloc)
00338           this->_M_invalidate_all();
00339         this->_M_update_guaranteed_capacity();
00340       }
00341 
00342       void
00343       resize(size_type __sz, const _Tp& __c)
00344       {
00345         bool __realloc = this->_M_requires_reallocation(__sz);
00346         if (__sz < this->size())
00347           this->_M_invalidate_after_nth(__sz);
00348         _Base::resize(__sz, __c);
00349         if (__realloc)
00350           this->_M_invalidate_all();
00351         this->_M_update_guaranteed_capacity();
00352       }
00353 #else
00354       void
00355       resize(size_type __sz, _Tp __c = _Tp())
00356       {
00357         bool __realloc = this->_M_requires_reallocation(__sz);
00358         if (__sz < this->size())
00359           this->_M_invalidate_after_nth(__sz);
00360         _Base::resize(__sz, __c);
00361         if (__realloc)
00362           this->_M_invalidate_all();
00363         this->_M_update_guaranteed_capacity();
00364       }
00365 #endif
00366 
00367 #if __cplusplus >= 201103L
00368       void
00369       shrink_to_fit()
00370       {
00371         if (_Base::_M_shrink_to_fit())
00372           {
00373             this->_M_guaranteed_capacity = _Base::capacity();
00374             this->_M_invalidate_all();
00375           }
00376       }
00377 #endif
00378 
00379       size_type
00380       capacity() const _GLIBCXX_NOEXCEPT
00381       {
00382 #ifdef _GLIBCXX_DEBUG_PEDANTIC
00383         return this->_M_guaranteed_capacity;
00384 #else
00385         return _Base::capacity();
00386 #endif
00387       }
00388 
00389       using _Base::empty;
00390 
00391       void
00392       reserve(size_type __n)
00393       {
00394         bool __realloc = this->_M_requires_reallocation(__n);
00395         _Base::reserve(__n);
00396         if (__n > this->_M_guaranteed_capacity)
00397           this->_M_guaranteed_capacity = __n;
00398         if (__realloc)
00399           this->_M_invalidate_all();
00400       }
00401 
00402       // element access:
00403       reference
00404       operator[](size_type __n) _GLIBCXX_NOEXCEPT
00405       {
00406         __glibcxx_check_subscript(__n);
00407         return _M_base()[__n];
00408       }
00409 
00410       const_reference
00411       operator[](size_type __n) const _GLIBCXX_NOEXCEPT
00412       {
00413         __glibcxx_check_subscript(__n);
00414         return _M_base()[__n];
00415       }
00416 
00417       using _Base::at;
00418 
00419       reference
00420       front() _GLIBCXX_NOEXCEPT
00421       {
00422         __glibcxx_check_nonempty();
00423         return _Base::front();
00424       }
00425 
00426       const_reference
00427       front() const _GLIBCXX_NOEXCEPT
00428       {
00429         __glibcxx_check_nonempty();
00430         return _Base::front();
00431       }
00432 
00433       reference
00434       back() _GLIBCXX_NOEXCEPT
00435       {
00436         __glibcxx_check_nonempty();
00437         return _Base::back();
00438       }
00439 
00440       const_reference
00441       back() const _GLIBCXX_NOEXCEPT
00442       {
00443         __glibcxx_check_nonempty();
00444         return _Base::back();
00445       }
00446 
00447       // _GLIBCXX_RESOLVE_LIB_DEFECTS
00448       // DR 464. Suggestion for new member functions in standard containers.
00449       using _Base::data;
00450 
00451       // 23.2.4.3 modifiers:
00452       void
00453       push_back(const _Tp& __x)
00454       {
00455         bool __realloc = this->_M_requires_reallocation(this->size() + 1);
00456         _Base::push_back(__x);
00457         if (__realloc)
00458           this->_M_invalidate_all();
00459         this->_M_update_guaranteed_capacity();
00460       }
00461 
00462 #if __cplusplus >= 201103L
00463       template<typename _Up = _Tp>
00464         typename __gnu_cxx::__enable_if<!std::__are_same<_Up, bool>::__value,
00465                                         void>::__type
00466         push_back(_Tp&& __x)
00467         { emplace_back(std::move(__x)); }
00468 
00469       template<typename... _Args>
00470         void
00471         emplace_back(_Args&&... __args)
00472         {
00473           bool __realloc = this->_M_requires_reallocation(this->size() + 1);
00474           _Base::emplace_back(std::forward<_Args>(__args)...);
00475           if (__realloc)
00476             this->_M_invalidate_all();
00477           this->_M_update_guaranteed_capacity();
00478         }
00479 #endif
00480 
00481       void
00482       pop_back() _GLIBCXX_NOEXCEPT
00483       {
00484         __glibcxx_check_nonempty();
00485         this->_M_invalidate_if(_Equal(--_Base::end()));
00486         _Base::pop_back();
00487       }
00488 
00489 #if __cplusplus >= 201103L
00490       template<typename... _Args>
00491         iterator
00492         emplace(const_iterator __position, _Args&&... __args)
00493         {
00494           __glibcxx_check_insert(__position);
00495           bool __realloc = this->_M_requires_reallocation(this->size() + 1);
00496           difference_type __offset = __position.base() - _Base::begin();
00497           _Base_iterator __res = _Base::emplace(__position.base(),
00498                                                 std::forward<_Args>(__args)...);
00499           if (__realloc)
00500             this->_M_invalidate_all();
00501           else
00502             this->_M_invalidate_after_nth(__offset);
00503           this->_M_update_guaranteed_capacity();
00504           return iterator(__res, this);
00505         }
00506 #endif
00507 
00508       iterator
00509 #if __cplusplus >= 201103L
00510       insert(const_iterator __position, const _Tp& __x)
00511 #else
00512       insert(iterator __position, const _Tp& __x)
00513 #endif
00514       {
00515         __glibcxx_check_insert(__position);
00516         bool __realloc = this->_M_requires_reallocation(this->size() + 1);
00517         difference_type __offset = __position.base() - _Base::begin();
00518         _Base_iterator __res = _Base::insert(__position.base(), __x);
00519         if (__realloc)
00520           this->_M_invalidate_all();
00521         else
00522           this->_M_invalidate_after_nth(__offset);
00523         this->_M_update_guaranteed_capacity();
00524         return iterator(__res, this);
00525       }
00526 
00527 #if __cplusplus >= 201103L
00528       template<typename _Up = _Tp>
00529         typename __gnu_cxx::__enable_if<!std::__are_same<_Up, bool>::__value,
00530                                         iterator>::__type
00531         insert(const_iterator __position, _Tp&& __x)
00532         { return emplace(__position, std::move(__x)); }
00533 
00534       iterator
00535       insert(const_iterator __position, initializer_list<value_type> __l)
00536       { return this->insert(__position, __l.begin(), __l.end()); }
00537 #endif
00538 
00539 #if __cplusplus >= 201103L
00540       iterator
00541       insert(const_iterator __position, size_type __n, const _Tp& __x)
00542       {
00543         __glibcxx_check_insert(__position);
00544         bool __realloc = this->_M_requires_reallocation(this->size() + __n);
00545         difference_type __offset = __position.base() - _Base::cbegin();
00546         _Base_iterator __res = _Base::insert(__position.base(), __n, __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 #else
00555       void
00556       insert(iterator __position, size_type __n, const _Tp& __x)
00557       {
00558         __glibcxx_check_insert(__position);
00559         bool __realloc = this->_M_requires_reallocation(this->size() + __n);
00560         difference_type __offset = __position.base() - _Base::begin();
00561         _Base::insert(__position.base(), __n, __x);
00562         if (__realloc)
00563           this->_M_invalidate_all();
00564         else
00565           this->_M_invalidate_after_nth(__offset);
00566         this->_M_update_guaranteed_capacity();
00567       }
00568 #endif
00569 
00570 #if __cplusplus >= 201103L
00571       template<class _InputIterator,
00572                typename = std::_RequireInputIter<_InputIterator>>
00573         iterator
00574         insert(const_iterator __position,
00575                _InputIterator __first, _InputIterator __last)
00576         {
00577           __glibcxx_check_insert_range(__position, __first, __last);
00578 
00579           /* Hard to guess if invalidation will occur, because __last
00580              - __first can't be calculated in all cases, so we just
00581              punt here by checking if it did occur. */
00582           _Base_iterator __old_begin = _M_base().begin();
00583           difference_type __offset = __position.base() - _Base::cbegin();
00584           _Base_iterator __res = _Base::insert(__position.base(),
00585                                                __gnu_debug::__base(__first),
00586                                                __gnu_debug::__base(__last));
00587 
00588           if (_M_base().begin() != __old_begin)
00589             this->_M_invalidate_all();
00590           else
00591             this->_M_invalidate_after_nth(__offset);
00592           this->_M_update_guaranteed_capacity();
00593           return iterator(__res, this);
00594         }
00595 #else
00596       template<class _InputIterator>
00597         void
00598         insert(iterator __position,
00599                _InputIterator __first, _InputIterator __last)
00600         {
00601           __glibcxx_check_insert_range(__position, __first, __last);
00602 
00603           /* Hard to guess if invalidation will occur, because __last
00604              - __first can't be calculated in all cases, so we just
00605              punt here by checking if it did occur. */
00606           _Base_iterator __old_begin = _M_base().begin();
00607           difference_type __offset = __position.base() - _Base::begin();
00608           _Base::insert(__position.base(), __gnu_debug::__base(__first),
00609                                            __gnu_debug::__base(__last));
00610 
00611           if (_M_base().begin() != __old_begin)
00612             this->_M_invalidate_all();
00613           else
00614             this->_M_invalidate_after_nth(__offset);
00615           this->_M_update_guaranteed_capacity();
00616         }
00617 #endif
00618 
00619       iterator
00620 #if __cplusplus >= 201103L
00621       erase(const_iterator __position)
00622 #else
00623       erase(iterator __position)
00624 #endif
00625       {
00626         __glibcxx_check_erase(__position);
00627         difference_type __offset = __position.base() - _Base::begin();
00628         _Base_iterator __res = _Base::erase(__position.base());
00629         this->_M_invalidate_after_nth(__offset);
00630         return iterator(__res, this);
00631       }
00632 
00633       iterator
00634 #if __cplusplus >= 201103L
00635       erase(const_iterator __first, const_iterator __last)
00636 #else
00637       erase(iterator __first, iterator __last)
00638 #endif
00639       {
00640         // _GLIBCXX_RESOLVE_LIB_DEFECTS
00641         // 151. can't currently clear() empty container
00642         __glibcxx_check_erase_range(__first, __last);
00643 
00644         if (__first.base() != __last.base())
00645           {
00646             difference_type __offset = __first.base() - _Base::begin();
00647             _Base_iterator __res = _Base::erase(__first.base(),
00648                                                 __last.base());
00649             this->_M_invalidate_after_nth(__offset);
00650             return iterator(__res, this);
00651           }
00652         else
00653 #if __cplusplus >= 201103L
00654           return begin() + (__first.base() - cbegin().base());
00655 #else
00656           return __first;
00657 #endif
00658       }
00659 
00660       void
00661       swap(vector& __x)
00662 #if __cplusplus >= 201103L
00663         noexcept( noexcept(declval<_Base>().swap(__x)) )
00664 #endif
00665       {
00666         _Safe::_M_swap(__x);
00667         _Base::swap(__x);
00668         std::swap(this->_M_guaranteed_capacity, __x._M_guaranteed_capacity);
00669       }
00670 
00671       void
00672       clear() _GLIBCXX_NOEXCEPT
00673       {
00674         _Base::clear();
00675         this->_M_invalidate_all();
00676       }
00677 
00678       _Base&
00679       _M_base() _GLIBCXX_NOEXCEPT { return *this; }
00680 
00681       const _Base&
00682       _M_base() const _GLIBCXX_NOEXCEPT { return *this; }
00683 
00684     private:
00685       void
00686       _M_invalidate_after_nth(difference_type __n) _GLIBCXX_NOEXCEPT
00687       {
00688         typedef __gnu_debug::_After_nth_from<_Base_const_iterator> _After_nth;
00689         this->_M_invalidate_if(_After_nth(__n, _Base::begin()));
00690       }
00691     };
00692 
00693   template<typename _Tp, typename _Alloc>
00694     inline bool
00695     operator==(const vector<_Tp, _Alloc>& __lhs,
00696                const vector<_Tp, _Alloc>& __rhs)
00697     { return __lhs._M_base() == __rhs._M_base(); }
00698 
00699   template<typename _Tp, typename _Alloc>
00700     inline bool
00701     operator!=(const vector<_Tp, _Alloc>& __lhs,
00702                const vector<_Tp, _Alloc>& __rhs)
00703     { return __lhs._M_base() != __rhs._M_base(); }
00704 
00705   template<typename _Tp, typename _Alloc>
00706     inline bool
00707     operator<(const vector<_Tp, _Alloc>& __lhs,
00708               const vector<_Tp, _Alloc>& __rhs)
00709     { return __lhs._M_base() < __rhs._M_base(); }
00710 
00711   template<typename _Tp, typename _Alloc>
00712     inline bool
00713     operator<=(const vector<_Tp, _Alloc>& __lhs,
00714                const vector<_Tp, _Alloc>& __rhs)
00715     { return __lhs._M_base() <= __rhs._M_base(); }
00716 
00717   template<typename _Tp, typename _Alloc>
00718     inline bool
00719     operator>=(const vector<_Tp, _Alloc>& __lhs,
00720                const vector<_Tp, _Alloc>& __rhs)
00721     { return __lhs._M_base() >= __rhs._M_base(); }
00722 
00723   template<typename _Tp, typename _Alloc>
00724     inline bool
00725     operator>(const vector<_Tp, _Alloc>& __lhs,
00726               const vector<_Tp, _Alloc>& __rhs)
00727     { return __lhs._M_base() > __rhs._M_base(); }
00728 
00729   template<typename _Tp, typename _Alloc>
00730     inline void
00731     swap(vector<_Tp, _Alloc>& __lhs, vector<_Tp, _Alloc>& __rhs)
00732     { __lhs.swap(__rhs); }
00733 
00734 } // namespace __debug
00735 
00736 #if __cplusplus >= 201103L
00737   // DR 1182.
00738   /// std::hash specialization for vector<bool>.
00739   template<typename _Alloc>
00740     struct hash<__debug::vector<bool, _Alloc>>
00741     : public __hash_base<size_t, __debug::vector<bool, _Alloc>>
00742     {
00743       size_t
00744       operator()(const __debug::vector<bool, _Alloc>& __b) const noexcept
00745       { return std::hash<_GLIBCXX_STD_C::vector<bool, _Alloc>>()
00746           (__b._M_base()); }
00747     };
00748 #endif
00749 
00750 } // namespace std
00751 
00752 namespace __gnu_debug
00753 {
00754   template<typename _Tp, typename _Alloc>
00755     struct _Is_contiguous_sequence<std::__debug::vector<_Tp, _Alloc> >
00756     : std::__true_type
00757     { };
00758 
00759   template<typename _Alloc>
00760     struct _Is_contiguous_sequence<std::__debug::vector<bool, _Alloc> >
00761     : std::__false_type
00762     { };
00763 }
00764 
00765 #endif