libstdc++
deque
Go to the documentation of this file.
00001 // Debugging deque implementation -*- C++ -*-
00002 
00003 // Copyright (C) 2003-2016 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           typename __gnu_debug::_Distance_traits<_InputIterator>::__type __dist;
00173           __glibcxx_check_valid_range2(__first, __last, __dist);
00174           if (__dist.second >= __gnu_debug::__dp_sign)
00175             _Base::assign(__gnu_debug::__unsafe(__first),
00176                           __gnu_debug::__unsafe(__last));
00177           else
00178             _Base::assign(__first, __last);
00179 
00180           this->_M_invalidate_all();
00181         }
00182 
00183       void
00184       assign(size_type __n, const _Tp& __t)
00185       {
00186         _Base::assign(__n, __t);
00187         this->_M_invalidate_all();
00188       }
00189 
00190 #if __cplusplus >= 201103L
00191       void
00192       assign(initializer_list<value_type> __l)
00193       {
00194         _Base::assign(__l);
00195         this->_M_invalidate_all();
00196       }
00197 #endif
00198 
00199       using _Base::get_allocator;
00200 
00201       // iterators:
00202       iterator
00203       begin() _GLIBCXX_NOEXCEPT
00204       { return iterator(_Base::begin(), this); }
00205 
00206       const_iterator
00207       begin() const _GLIBCXX_NOEXCEPT
00208       { return const_iterator(_Base::begin(), this); }
00209 
00210       iterator
00211       end() _GLIBCXX_NOEXCEPT
00212       { return iterator(_Base::end(), this); }
00213 
00214       const_iterator
00215       end() const _GLIBCXX_NOEXCEPT
00216       { return const_iterator(_Base::end(), this); }
00217 
00218       reverse_iterator
00219       rbegin() _GLIBCXX_NOEXCEPT
00220       { return reverse_iterator(end()); }
00221 
00222       const_reverse_iterator
00223       rbegin() const _GLIBCXX_NOEXCEPT
00224       { return const_reverse_iterator(end()); }
00225 
00226       reverse_iterator
00227       rend() _GLIBCXX_NOEXCEPT
00228       { return reverse_iterator(begin()); }
00229 
00230       const_reverse_iterator
00231       rend() const _GLIBCXX_NOEXCEPT
00232       { return const_reverse_iterator(begin()); }
00233 
00234 #if __cplusplus >= 201103L
00235       const_iterator
00236       cbegin() const noexcept
00237       { return const_iterator(_Base::begin(), this); }
00238 
00239       const_iterator
00240       cend() const noexcept
00241       { return const_iterator(_Base::end(), this); }
00242 
00243       const_reverse_iterator
00244       crbegin() const noexcept
00245       { return const_reverse_iterator(end()); }
00246 
00247       const_reverse_iterator
00248       crend() const noexcept
00249       { return const_reverse_iterator(begin()); }
00250 #endif
00251 
00252     private:
00253       void
00254       _M_invalidate_after_nth(difference_type __n)
00255       {
00256         typedef __gnu_debug::_After_nth_from<_Base_const_iterator> _After_nth;
00257         this->_M_invalidate_if(_After_nth(__n, _Base::begin()));
00258       }
00259 
00260     public:
00261       // 23.2.1.2 capacity:
00262       using _Base::size;
00263       using _Base::max_size;
00264 
00265 #if __cplusplus >= 201103L
00266       void
00267       resize(size_type __sz)
00268       {
00269         bool __invalidate_all = __sz > this->size();
00270         if (__sz < this->size())
00271           this->_M_invalidate_after_nth(__sz);
00272 
00273         _Base::resize(__sz);
00274 
00275         if (__invalidate_all)
00276           this->_M_invalidate_all();
00277       }
00278 
00279       void
00280       resize(size_type __sz, const _Tp& __c)
00281       {
00282         bool __invalidate_all = __sz > this->size();
00283         if (__sz < this->size())
00284           this->_M_invalidate_after_nth(__sz);
00285 
00286         _Base::resize(__sz, __c);
00287 
00288         if (__invalidate_all)
00289           this->_M_invalidate_all();
00290       }
00291 #else
00292       void
00293       resize(size_type __sz, _Tp __c = _Tp())
00294       {
00295         bool __invalidate_all = __sz > this->size();
00296         if (__sz < this->size())
00297           this->_M_invalidate_after_nth(__sz);
00298 
00299         _Base::resize(__sz, __c);
00300 
00301         if (__invalidate_all)
00302           this->_M_invalidate_all();
00303       }
00304 #endif
00305 
00306 #if __cplusplus >= 201103L
00307       void
00308       shrink_to_fit() noexcept
00309       {
00310         if (_Base::_M_shrink_to_fit())
00311           this->_M_invalidate_all();
00312       }
00313 #endif
00314 
00315       using _Base::empty;
00316 
00317       // element access:
00318       reference
00319       operator[](size_type __n) _GLIBCXX_NOEXCEPT
00320       {
00321         __glibcxx_check_subscript(__n);
00322         return _M_base()[__n];
00323       }
00324 
00325       const_reference
00326       operator[](size_type __n) const _GLIBCXX_NOEXCEPT
00327       {
00328         __glibcxx_check_subscript(__n);
00329         return _M_base()[__n];
00330       }
00331 
00332       using _Base::at;
00333 
00334       reference
00335       front() _GLIBCXX_NOEXCEPT
00336       {
00337         __glibcxx_check_nonempty();
00338         return _Base::front();
00339       }
00340 
00341       const_reference
00342       front() const _GLIBCXX_NOEXCEPT
00343       {
00344         __glibcxx_check_nonempty();
00345         return _Base::front();
00346       }
00347 
00348       reference
00349       back() _GLIBCXX_NOEXCEPT
00350       {
00351         __glibcxx_check_nonempty();
00352         return _Base::back();
00353       }
00354 
00355       const_reference
00356       back() const _GLIBCXX_NOEXCEPT
00357       {
00358         __glibcxx_check_nonempty();
00359         return _Base::back();
00360       }
00361 
00362       // 23.2.1.3 modifiers:
00363       void
00364       push_front(const _Tp& __x)
00365       {
00366         _Base::push_front(__x);
00367         this->_M_invalidate_all();
00368       }
00369 
00370       void
00371       push_back(const _Tp& __x)
00372       {
00373         _Base::push_back(__x);
00374         this->_M_invalidate_all();
00375       }
00376 
00377 #if __cplusplus >= 201103L
00378       void
00379       push_front(_Tp&& __x)
00380       { emplace_front(std::move(__x)); }
00381 
00382       void
00383       push_back(_Tp&& __x)
00384       { emplace_back(std::move(__x)); }
00385 
00386       template<typename... _Args>
00387         void
00388         emplace_front(_Args&&... __args)
00389         {
00390           _Base::emplace_front(std::forward<_Args>(__args)...);
00391           this->_M_invalidate_all();
00392         }
00393 
00394       template<typename... _Args>
00395         void
00396         emplace_back(_Args&&... __args)
00397         {
00398           _Base::emplace_back(std::forward<_Args>(__args)...);
00399           this->_M_invalidate_all();
00400         }
00401 
00402       template<typename... _Args>
00403         iterator
00404         emplace(const_iterator __position, _Args&&... __args)
00405         {
00406           __glibcxx_check_insert(__position);
00407           _Base_iterator __res = _Base::emplace(__position.base(),
00408                                                 std::forward<_Args>(__args)...);
00409           this->_M_invalidate_all();
00410           return iterator(__res, this);
00411         }
00412 #endif
00413 
00414       iterator
00415 #if __cplusplus >= 201103L
00416       insert(const_iterator __position, const _Tp& __x)
00417 #else
00418       insert(iterator __position, const _Tp& __x)
00419 #endif
00420       {
00421         __glibcxx_check_insert(__position);
00422         _Base_iterator __res = _Base::insert(__position.base(), __x);
00423         this->_M_invalidate_all();
00424         return iterator(__res, this);
00425       }
00426 
00427 #if __cplusplus >= 201103L
00428       iterator
00429       insert(const_iterator __position, _Tp&& __x)
00430       { return emplace(__position, std::move(__x)); }
00431 
00432       iterator
00433       insert(const_iterator __position, initializer_list<value_type> __l)
00434       {
00435         __glibcxx_check_insert(__position);
00436         _Base_iterator __res = _Base::insert(__position.base(), __l);
00437         this->_M_invalidate_all();
00438         return iterator(__res, this);
00439       }
00440 #endif
00441 
00442 #if __cplusplus >= 201103L
00443       iterator
00444       insert(const_iterator __position, size_type __n, const _Tp& __x)
00445       {
00446         __glibcxx_check_insert(__position);
00447         _Base_iterator __res = _Base::insert(__position.base(), __n, __x);
00448         this->_M_invalidate_all();
00449         return iterator(__res, this);
00450       }
00451 #else
00452       void
00453       insert(iterator __position, size_type __n, const _Tp& __x)
00454       {
00455         __glibcxx_check_insert(__position);
00456         _Base::insert(__position.base(), __n, __x);
00457         this->_M_invalidate_all();
00458       }
00459 #endif
00460 
00461 #if __cplusplus >= 201103L
00462       template<class _InputIterator,
00463                typename = std::_RequireInputIter<_InputIterator>>
00464         iterator
00465         insert(const_iterator __position,
00466                _InputIterator __first, _InputIterator __last)
00467         {
00468           typename __gnu_debug::_Distance_traits<_InputIterator>::__type __dist;
00469           __glibcxx_check_insert_range(__position, __first, __last, __dist);
00470           _Base_iterator __res;
00471           if (__dist.second >= __gnu_debug::__dp_sign)
00472             __res = _Base::insert(__position.base(),
00473                                   __gnu_debug::__unsafe(__first),
00474                                   __gnu_debug::__unsafe(__last));
00475           else
00476             __res = _Base::insert(__position.base(), __first, __last);
00477 
00478           this->_M_invalidate_all();
00479           return iterator(__res, this);
00480         }
00481 #else
00482       template<class _InputIterator>
00483         void
00484         insert(iterator __position,
00485                _InputIterator __first, _InputIterator __last)
00486         {
00487           typename __gnu_debug::_Distance_traits<_InputIterator>::__type __dist;
00488           __glibcxx_check_insert_range(__position, __first, __last, __dist);
00489 
00490           if (__dist.second >= __gnu_debug::__dp_sign)
00491             _Base::insert(__position.base(),
00492                           __gnu_debug::__unsafe(__first),
00493                           __gnu_debug::__unsafe(__last));
00494           else
00495             _Base::insert(__position.base(), __first, __last);
00496 
00497           this->_M_invalidate_all();
00498         }
00499 #endif
00500 
00501       void
00502       pop_front() _GLIBCXX_NOEXCEPT
00503       {
00504         __glibcxx_check_nonempty();
00505         this->_M_invalidate_if(_Equal(_Base::begin()));
00506         _Base::pop_front();
00507       }
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       iterator
00518 #if __cplusplus >= 201103L
00519       erase(const_iterator __position)
00520 #else
00521       erase(iterator __position)        
00522 #endif
00523       {
00524         __glibcxx_check_erase(__position);
00525 #if __cplusplus >= 201103L
00526         _Base_const_iterator __victim = __position.base();
00527 #else
00528         _Base_iterator __victim = __position.base();
00529 #endif
00530         if (__victim == _Base::begin() || __victim == _Base::end() - 1)
00531           {
00532             this->_M_invalidate_if(_Equal(__victim));
00533             return iterator(_Base::erase(__victim), this);
00534           }
00535         else
00536           {
00537             _Base_iterator __res = _Base::erase(__victim);
00538             this->_M_invalidate_all();
00539             return iterator(__res, this);
00540           }
00541       }
00542 
00543       iterator
00544 #if __cplusplus >= 201103L
00545       erase(const_iterator __first, const_iterator __last)
00546 #else
00547       erase(iterator __first, iterator __last)
00548 #endif
00549       {
00550         // _GLIBCXX_RESOLVE_LIB_DEFECTS
00551         // 151. can't currently clear() empty container
00552         __glibcxx_check_erase_range(__first, __last);
00553 
00554         if (__first.base() == __last.base())
00555 #if __cplusplus >= 201103L
00556           return iterator(__first.base()._M_const_cast(), this);
00557 #else
00558           return __first;
00559 #endif
00560         else if (__first.base() == _Base::begin()
00561                  || __last.base() == _Base::end())
00562           {
00563             this->_M_detach_singular();
00564             for (_Base_const_iterator __position = __first.base();
00565                  __position != __last.base(); ++__position)
00566               {
00567                 this->_M_invalidate_if(_Equal(__position));
00568               }
00569             __try
00570               {
00571                 return iterator(_Base::erase(__first.base(), __last.base()),
00572                                 this);
00573               }
00574             __catch(...)
00575               {
00576                 this->_M_revalidate_singular();
00577                 __throw_exception_again;
00578               }
00579           }
00580         else
00581           {
00582             _Base_iterator __res = _Base::erase(__first.base(),
00583                                                 __last.base());
00584             this->_M_invalidate_all();
00585             return iterator(__res, this);
00586           }
00587       }
00588 
00589       void
00590       swap(deque& __x)
00591       _GLIBCXX_NOEXCEPT_IF( noexcept(declval<_Base&>().swap(__x)) )
00592       {
00593         _Safe::_M_swap(__x);
00594         _Base::swap(__x);
00595       }
00596 
00597       void
00598       clear() _GLIBCXX_NOEXCEPT
00599       {
00600         _Base::clear();
00601         this->_M_invalidate_all();
00602       }
00603 
00604       _Base&
00605       _M_base() _GLIBCXX_NOEXCEPT       { return *this; }
00606 
00607       const _Base&
00608       _M_base() const _GLIBCXX_NOEXCEPT { return *this; }
00609     };
00610 
00611   template<typename _Tp, typename _Alloc>
00612     inline bool
00613     operator==(const deque<_Tp, _Alloc>& __lhs,
00614                const deque<_Tp, _Alloc>& __rhs)
00615     { return __lhs._M_base() == __rhs._M_base(); }
00616 
00617   template<typename _Tp, typename _Alloc>
00618     inline bool
00619     operator!=(const deque<_Tp, _Alloc>& __lhs,
00620                const deque<_Tp, _Alloc>& __rhs)
00621     { return __lhs._M_base() != __rhs._M_base(); }
00622 
00623   template<typename _Tp, typename _Alloc>
00624     inline bool
00625     operator<(const deque<_Tp, _Alloc>& __lhs,
00626               const deque<_Tp, _Alloc>& __rhs)
00627     { return __lhs._M_base() < __rhs._M_base(); }
00628 
00629   template<typename _Tp, typename _Alloc>
00630     inline bool
00631     operator<=(const deque<_Tp, _Alloc>& __lhs,
00632                const deque<_Tp, _Alloc>& __rhs)
00633     { return __lhs._M_base() <= __rhs._M_base(); }
00634 
00635   template<typename _Tp, typename _Alloc>
00636     inline bool
00637     operator>=(const deque<_Tp, _Alloc>& __lhs,
00638                const deque<_Tp, _Alloc>& __rhs)
00639     { return __lhs._M_base() >= __rhs._M_base(); }
00640 
00641   template<typename _Tp, typename _Alloc>
00642     inline bool
00643     operator>(const deque<_Tp, _Alloc>& __lhs,
00644               const deque<_Tp, _Alloc>& __rhs)
00645     { return __lhs._M_base() > __rhs._M_base(); }
00646 
00647   template<typename _Tp, typename _Alloc>
00648     inline void
00649     swap(deque<_Tp, _Alloc>& __lhs, deque<_Tp, _Alloc>& __rhs)
00650     _GLIBCXX_NOEXCEPT_IF(noexcept(__lhs.swap(__rhs)))
00651     { __lhs.swap(__rhs); }
00652 
00653 } // namespace __debug
00654 } // namespace std
00655 
00656 #endif