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