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