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