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