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