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