libstdc++
deque
Go to the documentation of this file.
00001 // Debugging deque implementation -*- C++ -*-
00002 
00003 // Copyright (C) 2003-2018 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/deque
00026  *  This file is a GNU debug extension to the Standard C++ Library.
00027  */
00028 
00029 #ifndef _GLIBCXX_DEBUG_DEQUE
00030 #define _GLIBCXX_DEBUG_DEQUE 1
00031 
00032 #pragma GCC system_header
00033 
00034 #include <deque>
00035 #include <debug/safe_sequence.h>
00036 #include <debug/safe_container.h>
00037 #include <debug/safe_iterator.h>
00038 
00039 namespace std _GLIBCXX_VISIBILITY(default)
00040 {
00041 namespace __debug
00042 {
00043   /// Class std::deque with safety/checking/debug instrumentation.
00044   template<typename _Tp, typename _Allocator = std::allocator<_Tp> >
00045     class deque
00046     : public __gnu_debug::_Safe_container<
00047         deque<_Tp, _Allocator>, _Allocator,
00048         __gnu_debug::_Safe_sequence>,
00049       public _GLIBCXX_STD_C::deque<_Tp, _Allocator>
00050     {
00051       typedef  _GLIBCXX_STD_C::deque<_Tp, _Allocator>           _Base;
00052       typedef __gnu_debug::_Safe_container<
00053         deque, _Allocator, __gnu_debug::_Safe_sequence> _Safe;
00054 
00055       typedef typename _Base::const_iterator    _Base_const_iterator;
00056       typedef typename _Base::iterator          _Base_iterator;
00057       typedef __gnu_debug::_Equal_to<_Base_const_iterator> _Equal;
00058 
00059     public:
00060       typedef typename _Base::reference                 reference;
00061       typedef typename _Base::const_reference           const_reference;
00062 
00063       typedef __gnu_debug::_Safe_iterator<_Base_iterator, deque>
00064                                                         iterator;
00065       typedef __gnu_debug::_Safe_iterator<_Base_const_iterator, deque>
00066                                                         const_iterator;
00067 
00068       typedef typename _Base::size_type                 size_type;
00069       typedef typename _Base::difference_type           difference_type;
00070 
00071       typedef _Tp                                       value_type;
00072       typedef _Allocator                                allocator_type;
00073       typedef typename _Base::pointer                   pointer;
00074       typedef typename _Base::const_pointer             const_pointer;
00075       typedef std::reverse_iterator<iterator>           reverse_iterator;
00076       typedef std::reverse_iterator<const_iterator>     const_reverse_iterator;
00077 
00078       // 23.2.1.1 construct/copy/destroy:
00079 
00080 #if __cplusplus < 201103L
00081       deque()
00082       : _Base() { }
00083 
00084       deque(const deque& __x)
00085       : _Base(__x) { }
00086 
00087       ~deque() { }
00088 #else
00089       deque() = default;
00090       deque(const deque&) = default;
00091       deque(deque&&) = default;
00092 
00093       deque(const deque& __d, const _Allocator& __a)
00094       : _Base(__d, __a) { }
00095 
00096       deque(deque&& __d, const _Allocator& __a)
00097       : _Safe(std::move(__d)), _Base(std::move(__d), __a) { }
00098 
00099       deque(initializer_list<value_type> __l,
00100             const allocator_type& __a = allocator_type())
00101       : _Base(__l, __a) { }
00102 
00103       ~deque() = default;
00104 #endif
00105 
00106       explicit
00107       deque(const _Allocator& __a)
00108       : _Base(__a) { }
00109 
00110 #if __cplusplus >= 201103L
00111       explicit
00112       deque(size_type __n, const _Allocator& __a = _Allocator())
00113       : _Base(__n, __a) { }
00114 
00115       deque(size_type __n, const _Tp& __value,
00116             const _Allocator& __a = _Allocator())
00117       : _Base(__n, __value, __a) { }
00118 #else
00119       explicit
00120       deque(size_type __n, const _Tp& __value = _Tp(),
00121             const _Allocator& __a = _Allocator())
00122       : _Base(__n, __value, __a) { }
00123 #endif
00124 
00125 #if __cplusplus >= 201103L
00126       template<class _InputIterator,
00127                typename = std::_RequireInputIter<_InputIterator>>
00128 #else
00129       template<class _InputIterator>
00130 #endif
00131         deque(_InputIterator __first, _InputIterator __last,
00132               const _Allocator& __a = _Allocator())
00133         : _Base(__gnu_debug::__base(__gnu_debug::__check_valid_range(__first,
00134                                                                      __last)),
00135                 __gnu_debug::__base(__last), __a)
00136         { }
00137 
00138       deque(const _Base& __x)
00139       : _Base(__x) { }
00140 
00141 #if __cplusplus < 201103L
00142       deque&
00143       operator=(const deque& __x)
00144       {
00145         this->_M_safe() = __x;
00146         _M_base() = __x;
00147         return *this;
00148       }
00149 #else
00150       deque&
00151       operator=(const deque&) = default;
00152 
00153       deque&
00154       operator=(deque&&) = default;
00155 
00156       deque&
00157       operator=(initializer_list<value_type> __l)
00158       {
00159         _M_base() = __l;
00160         this->_M_invalidate_all();
00161         return *this;
00162       }
00163 #endif
00164 
00165 #if __cplusplus >= 201103L
00166       template<class _InputIterator,
00167                typename = std::_RequireInputIter<_InputIterator>>
00168 #else
00169       template<class _InputIterator>
00170 #endif
00171         void
00172         assign(_InputIterator __first, _InputIterator __last)
00173         {
00174           typename __gnu_debug::_Distance_traits<_InputIterator>::__type __dist;
00175           __glibcxx_check_valid_range2(__first, __last, __dist);
00176           if (__dist.second >= __gnu_debug::__dp_sign)
00177             _Base::assign(__gnu_debug::__unsafe(__first),
00178                           __gnu_debug::__unsafe(__last));
00179           else
00180             _Base::assign(__first, __last);
00181 
00182           this->_M_invalidate_all();
00183         }
00184 
00185       void
00186       assign(size_type __n, const _Tp& __t)
00187       {
00188         _Base::assign(__n, __t);
00189         this->_M_invalidate_all();
00190       }
00191 
00192 #if __cplusplus >= 201103L
00193       void
00194       assign(initializer_list<value_type> __l)
00195       {
00196         _Base::assign(__l);
00197         this->_M_invalidate_all();
00198       }
00199 #endif
00200 
00201       using _Base::get_allocator;
00202 
00203       // iterators:
00204       iterator
00205       begin() _GLIBCXX_NOEXCEPT
00206       { return iterator(_Base::begin(), this); }
00207 
00208       const_iterator
00209       begin() const _GLIBCXX_NOEXCEPT
00210       { return const_iterator(_Base::begin(), this); }
00211 
00212       iterator
00213       end() _GLIBCXX_NOEXCEPT
00214       { return iterator(_Base::end(), this); }
00215 
00216       const_iterator
00217       end() const _GLIBCXX_NOEXCEPT
00218       { return const_iterator(_Base::end(), this); }
00219 
00220       reverse_iterator
00221       rbegin() _GLIBCXX_NOEXCEPT
00222       { return reverse_iterator(end()); }
00223 
00224       const_reverse_iterator
00225       rbegin() const _GLIBCXX_NOEXCEPT
00226       { return const_reverse_iterator(end()); }
00227 
00228       reverse_iterator
00229       rend() _GLIBCXX_NOEXCEPT
00230       { return reverse_iterator(begin()); }
00231 
00232       const_reverse_iterator
00233       rend() const _GLIBCXX_NOEXCEPT
00234       { return const_reverse_iterator(begin()); }
00235 
00236 #if __cplusplus >= 201103L
00237       const_iterator
00238       cbegin() const noexcept
00239       { return const_iterator(_Base::begin(), this); }
00240 
00241       const_iterator
00242       cend() const noexcept
00243       { return const_iterator(_Base::end(), this); }
00244 
00245       const_reverse_iterator
00246       crbegin() const noexcept
00247       { return const_reverse_iterator(end()); }
00248 
00249       const_reverse_iterator
00250       crend() const noexcept
00251       { return const_reverse_iterator(begin()); }
00252 #endif
00253 
00254     private:
00255       void
00256       _M_invalidate_after_nth(difference_type __n)
00257       {
00258         typedef __gnu_debug::_After_nth_from<_Base_const_iterator> _After_nth;
00259         this->_M_invalidate_if(_After_nth(__n, _Base::begin()));
00260       }
00261 
00262     public:
00263       // 23.2.1.2 capacity:
00264       using _Base::size;
00265       using _Base::max_size;
00266 
00267 #if __cplusplus >= 201103L
00268       void
00269       resize(size_type __sz)
00270       {
00271         bool __invalidate_all = __sz > this->size();
00272         if (__sz < this->size())
00273           this->_M_invalidate_after_nth(__sz);
00274 
00275         _Base::resize(__sz);
00276 
00277         if (__invalidate_all)
00278           this->_M_invalidate_all();
00279       }
00280 
00281       void
00282       resize(size_type __sz, const _Tp& __c)
00283       {
00284         bool __invalidate_all = __sz > this->size();
00285         if (__sz < this->size())
00286           this->_M_invalidate_after_nth(__sz);
00287 
00288         _Base::resize(__sz, __c);
00289 
00290         if (__invalidate_all)
00291           this->_M_invalidate_all();
00292       }
00293 #else
00294       void
00295       resize(size_type __sz, _Tp __c = _Tp())
00296       {
00297         bool __invalidate_all = __sz > this->size();
00298         if (__sz < this->size())
00299           this->_M_invalidate_after_nth(__sz);
00300 
00301         _Base::resize(__sz, __c);
00302 
00303         if (__invalidate_all)
00304           this->_M_invalidate_all();
00305       }
00306 #endif
00307 
00308 #if __cplusplus >= 201103L
00309       void
00310       shrink_to_fit() noexcept
00311       {
00312         if (_Base::_M_shrink_to_fit())
00313           this->_M_invalidate_all();
00314       }
00315 #endif
00316 
00317       using _Base::empty;
00318 
00319       // element access:
00320       reference
00321       operator[](size_type __n) _GLIBCXX_NOEXCEPT
00322       {
00323         __glibcxx_check_subscript(__n);
00324         return _M_base()[__n];
00325       }
00326 
00327       const_reference
00328       operator[](size_type __n) const _GLIBCXX_NOEXCEPT
00329       {
00330         __glibcxx_check_subscript(__n);
00331         return _M_base()[__n];
00332       }
00333 
00334       using _Base::at;
00335 
00336       reference
00337       front() _GLIBCXX_NOEXCEPT
00338       {
00339         __glibcxx_check_nonempty();
00340         return _Base::front();
00341       }
00342 
00343       const_reference
00344       front() const _GLIBCXX_NOEXCEPT
00345       {
00346         __glibcxx_check_nonempty();
00347         return _Base::front();
00348       }
00349 
00350       reference
00351       back() _GLIBCXX_NOEXCEPT
00352       {
00353         __glibcxx_check_nonempty();
00354         return _Base::back();
00355       }
00356 
00357       const_reference
00358       back() const _GLIBCXX_NOEXCEPT
00359       {
00360         __glibcxx_check_nonempty();
00361         return _Base::back();
00362       }
00363 
00364       // 23.2.1.3 modifiers:
00365       void
00366       push_front(const _Tp& __x)
00367       {
00368         _Base::push_front(__x);
00369         this->_M_invalidate_all();
00370       }
00371 
00372       void
00373       push_back(const _Tp& __x)
00374       {
00375         _Base::push_back(__x);
00376         this->_M_invalidate_all();
00377       }
00378 
00379 #if __cplusplus >= 201103L
00380       void
00381       push_front(_Tp&& __x)
00382       { emplace_front(std::move(__x)); }
00383 
00384       void
00385       push_back(_Tp&& __x)
00386       { emplace_back(std::move(__x)); }
00387 
00388       template<typename... _Args>
00389 #if __cplusplus > 201402L
00390         reference
00391 #else
00392         void
00393 #endif
00394         emplace_front(_Args&&... __args)
00395         {
00396           _Base::emplace_front(std::forward<_Args>(__args)...);
00397           this->_M_invalidate_all();
00398 #if __cplusplus > 201402L
00399           return front();
00400 #endif
00401         }
00402 
00403       template<typename... _Args>
00404 #if __cplusplus > 201402L
00405         reference
00406 #else
00407         void
00408 #endif
00409         emplace_back(_Args&&... __args)
00410         {
00411           _Base::emplace_back(std::forward<_Args>(__args)...);
00412           this->_M_invalidate_all();
00413 #if __cplusplus > 201402L
00414           return back();
00415 #endif
00416         }
00417 
00418       template<typename... _Args>
00419         iterator
00420         emplace(const_iterator __position, _Args&&... __args)
00421         {
00422           __glibcxx_check_insert(__position);
00423           _Base_iterator __res = _Base::emplace(__position.base(),
00424                                                 std::forward<_Args>(__args)...);
00425           this->_M_invalidate_all();
00426           return iterator(__res, this);
00427         }
00428 #endif
00429 
00430       iterator
00431 #if __cplusplus >= 201103L
00432       insert(const_iterator __position, const _Tp& __x)
00433 #else
00434       insert(iterator __position, const _Tp& __x)
00435 #endif
00436       {
00437         __glibcxx_check_insert(__position);
00438         _Base_iterator __res = _Base::insert(__position.base(), __x);
00439         this->_M_invalidate_all();
00440         return iterator(__res, this);
00441       }
00442 
00443 #if __cplusplus >= 201103L
00444       iterator
00445       insert(const_iterator __position, _Tp&& __x)
00446       { return emplace(__position, std::move(__x)); }
00447 
00448       iterator
00449       insert(const_iterator __position, initializer_list<value_type> __l)
00450       {
00451         __glibcxx_check_insert(__position);
00452         _Base_iterator __res = _Base::insert(__position.base(), __l);
00453         this->_M_invalidate_all();
00454         return iterator(__res, this);
00455       }
00456 #endif
00457 
00458 #if __cplusplus >= 201103L
00459       iterator
00460       insert(const_iterator __position, size_type __n, const _Tp& __x)
00461       {
00462         __glibcxx_check_insert(__position);
00463         _Base_iterator __res = _Base::insert(__position.base(), __n, __x);
00464         this->_M_invalidate_all();
00465         return iterator(__res, this);
00466       }
00467 #else
00468       void
00469       insert(iterator __position, size_type __n, const _Tp& __x)
00470       {
00471         __glibcxx_check_insert(__position);
00472         _Base::insert(__position.base(), __n, __x);
00473         this->_M_invalidate_all();
00474       }
00475 #endif
00476 
00477 #if __cplusplus >= 201103L
00478       template<class _InputIterator,
00479                typename = std::_RequireInputIter<_InputIterator>>
00480         iterator
00481         insert(const_iterator __position,
00482                _InputIterator __first, _InputIterator __last)
00483         {
00484           typename __gnu_debug::_Distance_traits<_InputIterator>::__type __dist;
00485           __glibcxx_check_insert_range(__position, __first, __last, __dist);
00486           _Base_iterator __res;
00487           if (__dist.second >= __gnu_debug::__dp_sign)
00488             __res = _Base::insert(__position.base(),
00489                                   __gnu_debug::__unsafe(__first),
00490                                   __gnu_debug::__unsafe(__last));
00491           else
00492             __res = _Base::insert(__position.base(), __first, __last);
00493 
00494           this->_M_invalidate_all();
00495           return iterator(__res, this);
00496         }
00497 #else
00498       template<class _InputIterator>
00499         void
00500         insert(iterator __position,
00501                _InputIterator __first, _InputIterator __last)
00502         {
00503           typename __gnu_debug::_Distance_traits<_InputIterator>::__type __dist;
00504           __glibcxx_check_insert_range(__position, __first, __last, __dist);
00505 
00506           if (__dist.second >= __gnu_debug::__dp_sign)
00507             _Base::insert(__position.base(),
00508                           __gnu_debug::__unsafe(__first),
00509                           __gnu_debug::__unsafe(__last));
00510           else
00511             _Base::insert(__position.base(), __first, __last);
00512 
00513           this->_M_invalidate_all();
00514         }
00515 #endif
00516 
00517       void
00518       pop_front() _GLIBCXX_NOEXCEPT
00519       {
00520         __glibcxx_check_nonempty();
00521         this->_M_invalidate_if(_Equal(_Base::begin()));
00522         _Base::pop_front();
00523       }
00524 
00525       void
00526       pop_back() _GLIBCXX_NOEXCEPT
00527       {
00528         __glibcxx_check_nonempty();
00529         this->_M_invalidate_if(_Equal(--_Base::end()));
00530         _Base::pop_back();
00531       }
00532 
00533       iterator
00534 #if __cplusplus >= 201103L
00535       erase(const_iterator __position)
00536 #else
00537       erase(iterator __position)        
00538 #endif
00539       {
00540         __glibcxx_check_erase(__position);
00541 #if __cplusplus >= 201103L
00542         _Base_const_iterator __victim = __position.base();
00543 #else
00544         _Base_iterator __victim = __position.base();
00545 #endif
00546         if (__victim == _Base::begin() || __victim == _Base::end() - 1)
00547           {
00548             this->_M_invalidate_if(_Equal(__victim));
00549             return iterator(_Base::erase(__victim), this);
00550           }
00551         else
00552           {
00553             _Base_iterator __res = _Base::erase(__victim);
00554             this->_M_invalidate_all();
00555             return iterator(__res, this);
00556           }
00557       }
00558 
00559       iterator
00560 #if __cplusplus >= 201103L
00561       erase(const_iterator __first, const_iterator __last)
00562 #else
00563       erase(iterator __first, iterator __last)
00564 #endif
00565       {
00566         // _GLIBCXX_RESOLVE_LIB_DEFECTS
00567         // 151. can't currently clear() empty container
00568         __glibcxx_check_erase_range(__first, __last);
00569 
00570         if (__first.base() == __last.base())
00571 #if __cplusplus >= 201103L
00572           return iterator(__first.base()._M_const_cast(), this);
00573 #else
00574           return __first;
00575 #endif
00576         else if (__first.base() == _Base::begin()
00577                  || __last.base() == _Base::end())
00578           {
00579             this->_M_detach_singular();
00580             for (_Base_const_iterator __position = __first.base();
00581                  __position != __last.base(); ++__position)
00582               {
00583                 this->_M_invalidate_if(_Equal(__position));
00584               }
00585             __try
00586               {
00587                 return iterator(_Base::erase(__first.base(), __last.base()),
00588                                 this);
00589               }
00590             __catch(...)
00591               {
00592                 this->_M_revalidate_singular();
00593                 __throw_exception_again;
00594               }
00595           }
00596         else
00597           {
00598             _Base_iterator __res = _Base::erase(__first.base(),
00599                                                 __last.base());
00600             this->_M_invalidate_all();
00601             return iterator(__res, this);
00602           }
00603       }
00604 
00605       void
00606       swap(deque& __x)
00607       _GLIBCXX_NOEXCEPT_IF( noexcept(declval<_Base&>().swap(__x)) )
00608       {
00609         _Safe::_M_swap(__x);
00610         _Base::swap(__x);
00611       }
00612 
00613       void
00614       clear() _GLIBCXX_NOEXCEPT
00615       {
00616         _Base::clear();
00617         this->_M_invalidate_all();
00618       }
00619 
00620       _Base&
00621       _M_base() _GLIBCXX_NOEXCEPT       { return *this; }
00622 
00623       const _Base&
00624       _M_base() const _GLIBCXX_NOEXCEPT { return *this; }
00625     };
00626 
00627 #if __cpp_deduction_guides >= 201606
00628   template<typename _InputIterator, typename _ValT
00629              = typename iterator_traits<_InputIterator>::value_type,
00630            typename _Allocator = allocator<_ValT>,
00631            typename = _RequireInputIter<_InputIterator>,
00632            typename = _RequireAllocator<_Allocator>>
00633     deque(_InputIterator, _InputIterator, _Allocator = _Allocator())
00634       -> deque<_ValT, _Allocator>;
00635 #endif
00636 
00637   template<typename _Tp, typename _Alloc>
00638     inline bool
00639     operator==(const deque<_Tp, _Alloc>& __lhs,
00640                const deque<_Tp, _Alloc>& __rhs)
00641     { return __lhs._M_base() == __rhs._M_base(); }
00642 
00643   template<typename _Tp, typename _Alloc>
00644     inline bool
00645     operator!=(const deque<_Tp, _Alloc>& __lhs,
00646                const deque<_Tp, _Alloc>& __rhs)
00647     { return __lhs._M_base() != __rhs._M_base(); }
00648 
00649   template<typename _Tp, typename _Alloc>
00650     inline bool
00651     operator<(const deque<_Tp, _Alloc>& __lhs,
00652               const deque<_Tp, _Alloc>& __rhs)
00653     { return __lhs._M_base() < __rhs._M_base(); }
00654 
00655   template<typename _Tp, typename _Alloc>
00656     inline bool
00657     operator<=(const deque<_Tp, _Alloc>& __lhs,
00658                const deque<_Tp, _Alloc>& __rhs)
00659     { return __lhs._M_base() <= __rhs._M_base(); }
00660 
00661   template<typename _Tp, typename _Alloc>
00662     inline bool
00663     operator>=(const deque<_Tp, _Alloc>& __lhs,
00664                const deque<_Tp, _Alloc>& __rhs)
00665     { return __lhs._M_base() >= __rhs._M_base(); }
00666 
00667   template<typename _Tp, typename _Alloc>
00668     inline bool
00669     operator>(const deque<_Tp, _Alloc>& __lhs,
00670               const deque<_Tp, _Alloc>& __rhs)
00671     { return __lhs._M_base() > __rhs._M_base(); }
00672 
00673   template<typename _Tp, typename _Alloc>
00674     inline void
00675     swap(deque<_Tp, _Alloc>& __lhs, deque<_Tp, _Alloc>& __rhs)
00676     _GLIBCXX_NOEXCEPT_IF(noexcept(__lhs.swap(__rhs)))
00677     { __lhs.swap(__rhs); }
00678 
00679 } // namespace __debug
00680 } // namespace std
00681 
00682 #endif