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