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