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