libstdc++
|
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