libstdc++
|
00001 // Debugging vector implementation -*- C++ -*- 00002 00003 // Copyright (C) 2003, 2004, 2005, 2006, 2007, 2008, 2009 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 00039 { 00040 namespace __debug 00041 { 00042 template<typename _Tp, 00043 typename _Allocator = std::allocator<_Tp> > 00044 class vector 00045 : public _GLIBCXX_STD_D::vector<_Tp, _Allocator>, 00046 public __gnu_debug::_Safe_sequence<vector<_Tp, _Allocator> > 00047 { 00048 typedef _GLIBCXX_STD_D::vector<_Tp, _Allocator> _Base; 00049 typedef __gnu_debug::_Safe_sequence<vector> _Safe_base; 00050 00051 typedef typename _Base::const_iterator _Base_const_iterator; 00052 typedef __gnu_debug::_After_nth_from<_Base_const_iterator> _After_nth; 00053 00054 public: 00055 typedef typename _Base::reference reference; 00056 typedef typename _Base::const_reference const_reference; 00057 00058 typedef __gnu_debug::_Safe_iterator<typename _Base::iterator,vector> 00059 iterator; 00060 typedef __gnu_debug::_Safe_iterator<typename _Base::const_iterator,vector> 00061 const_iterator; 00062 00063 typedef typename _Base::size_type size_type; 00064 typedef typename _Base::difference_type difference_type; 00065 00066 typedef _Tp value_type; 00067 typedef _Allocator allocator_type; 00068 typedef typename _Base::pointer pointer; 00069 typedef typename _Base::const_pointer const_pointer; 00070 typedef std::reverse_iterator<iterator> reverse_iterator; 00071 typedef std::reverse_iterator<const_iterator> const_reverse_iterator; 00072 00073 // 23.2.4.1 construct/copy/destroy: 00074 explicit vector(const _Allocator& __a = _Allocator()) 00075 : _Base(__a), _M_guaranteed_capacity(0) { } 00076 00077 explicit vector(size_type __n, const _Tp& __value = _Tp(), 00078 const _Allocator& __a = _Allocator()) 00079 : _Base(__n, __value, __a), _M_guaranteed_capacity(__n) { } 00080 00081 template<class _InputIterator> 00082 vector(_InputIterator __first, _InputIterator __last, 00083 const _Allocator& __a = _Allocator()) 00084 : _Base(__gnu_debug::__check_valid_range(__first, __last), 00085 __last, __a), 00086 _M_guaranteed_capacity(0) 00087 { _M_update_guaranteed_capacity(); } 00088 00089 vector(const vector& __x) 00090 : _Base(__x), _Safe_base(), _M_guaranteed_capacity(__x.size()) { } 00091 00092 /// Construction from a release-mode vector 00093 vector(const _Base& __x) 00094 : _Base(__x), _Safe_base(), _M_guaranteed_capacity(__x.size()) { } 00095 00096 #ifdef __GXX_EXPERIMENTAL_CXX0X__ 00097 vector(vector&& __x) 00098 : _Base(std::forward<vector>(__x)), _Safe_base(), 00099 _M_guaranteed_capacity(this->size()) 00100 { 00101 this->_M_swap(__x); 00102 __x._M_guaranteed_capacity = 0; 00103 } 00104 00105 vector(initializer_list<value_type> __l, 00106 const allocator_type& __a = allocator_type()) 00107 : _Base(__l, __a), _Safe_base(), 00108 _M_guaranteed_capacity(__l.size()) { } 00109 #endif 00110 00111 ~vector() { } 00112 00113 vector& 00114 operator=(const vector& __x) 00115 { 00116 static_cast<_Base&>(*this) = __x; 00117 this->_M_invalidate_all(); 00118 _M_update_guaranteed_capacity(); 00119 return *this; 00120 } 00121 00122 #ifdef __GXX_EXPERIMENTAL_CXX0X__ 00123 vector& 00124 operator=(vector&& __x) 00125 { 00126 // NB: DR 675. 00127 clear(); 00128 swap(__x); 00129 return *this; 00130 } 00131 00132 vector& 00133 operator=(initializer_list<value_type> __l) 00134 { 00135 static_cast<_Base&>(*this) = __l; 00136 this->_M_invalidate_all(); 00137 _M_update_guaranteed_capacity(); 00138 return *this; 00139 } 00140 #endif 00141 00142 template<typename _InputIterator> 00143 void 00144 assign(_InputIterator __first, _InputIterator __last) 00145 { 00146 __glibcxx_check_valid_range(__first, __last); 00147 _Base::assign(__first, __last); 00148 this->_M_invalidate_all(); 00149 _M_update_guaranteed_capacity(); 00150 } 00151 00152 void 00153 assign(size_type __n, const _Tp& __u) 00154 { 00155 _Base::assign(__n, __u); 00156 this->_M_invalidate_all(); 00157 _M_update_guaranteed_capacity(); 00158 } 00159 00160 #ifdef __GXX_EXPERIMENTAL_CXX0X__ 00161 void 00162 assign(initializer_list<value_type> __l) 00163 { 00164 _Base::assign(__l); 00165 this->_M_invalidate_all(); 00166 _M_update_guaranteed_capacity(); 00167 } 00168 #endif 00169 00170 using _Base::get_allocator; 00171 00172 // iterators: 00173 iterator 00174 begin() 00175 { return iterator(_Base::begin(), this); } 00176 00177 const_iterator 00178 begin() const 00179 { return const_iterator(_Base::begin(), this); } 00180 00181 iterator 00182 end() 00183 { return iterator(_Base::end(), this); } 00184 00185 const_iterator 00186 end() const 00187 { return const_iterator(_Base::end(), this); } 00188 00189 reverse_iterator 00190 rbegin() 00191 { return reverse_iterator(end()); } 00192 00193 const_reverse_iterator 00194 rbegin() const 00195 { return const_reverse_iterator(end()); } 00196 00197 reverse_iterator 00198 rend() 00199 { return reverse_iterator(begin()); } 00200 00201 const_reverse_iterator 00202 rend() const 00203 { return const_reverse_iterator(begin()); } 00204 00205 #ifdef __GXX_EXPERIMENTAL_CXX0X__ 00206 const_iterator 00207 cbegin() const 00208 { return const_iterator(_Base::begin(), this); } 00209 00210 const_iterator 00211 cend() const 00212 { return const_iterator(_Base::end(), this); } 00213 00214 const_reverse_iterator 00215 crbegin() const 00216 { return const_reverse_iterator(end()); } 00217 00218 const_reverse_iterator 00219 crend() const 00220 { return const_reverse_iterator(begin()); } 00221 #endif 00222 00223 // 23.2.4.2 capacity: 00224 using _Base::size; 00225 using _Base::max_size; 00226 00227 void 00228 resize(size_type __sz, _Tp __c = _Tp()) 00229 { 00230 bool __realloc = _M_requires_reallocation(__sz); 00231 if (__sz < this->size()) 00232 this->_M_invalidate_if(_After_nth(__sz, _M_base().begin())); 00233 _Base::resize(__sz, __c); 00234 if (__realloc) 00235 this->_M_invalidate_all(); 00236 } 00237 00238 size_type 00239 capacity() const 00240 { 00241 #ifdef _GLIBCXX_DEBUG_PEDANTIC 00242 return _M_guaranteed_capacity; 00243 #else 00244 return _Base::capacity(); 00245 #endif 00246 } 00247 00248 using _Base::empty; 00249 00250 void 00251 reserve(size_type __n) 00252 { 00253 bool __realloc = _M_requires_reallocation(__n); 00254 _Base::reserve(__n); 00255 if (__n > _M_guaranteed_capacity) 00256 _M_guaranteed_capacity = __n; 00257 if (__realloc) 00258 this->_M_invalidate_all(); 00259 } 00260 00261 // element access: 00262 reference 00263 operator[](size_type __n) 00264 { 00265 __glibcxx_check_subscript(__n); 00266 return _M_base()[__n]; 00267 } 00268 00269 const_reference 00270 operator[](size_type __n) const 00271 { 00272 __glibcxx_check_subscript(__n); 00273 return _M_base()[__n]; 00274 } 00275 00276 using _Base::at; 00277 00278 reference 00279 front() 00280 { 00281 __glibcxx_check_nonempty(); 00282 return _Base::front(); 00283 } 00284 00285 const_reference 00286 front() const 00287 { 00288 __glibcxx_check_nonempty(); 00289 return _Base::front(); 00290 } 00291 00292 reference 00293 back() 00294 { 00295 __glibcxx_check_nonempty(); 00296 return _Base::back(); 00297 } 00298 00299 const_reference 00300 back() const 00301 { 00302 __glibcxx_check_nonempty(); 00303 return _Base::back(); 00304 } 00305 00306 // _GLIBCXX_RESOLVE_LIB_DEFECTS 00307 // DR 464. Suggestion for new member functions in standard containers. 00308 using _Base::data; 00309 00310 // 23.2.4.3 modifiers: 00311 void 00312 push_back(const _Tp& __x) 00313 { 00314 bool __realloc = _M_requires_reallocation(this->size() + 1); 00315 _Base::push_back(__x); 00316 if (__realloc) 00317 this->_M_invalidate_all(); 00318 _M_update_guaranteed_capacity(); 00319 } 00320 00321 #ifdef __GXX_EXPERIMENTAL_CXX0X__ 00322 template<typename _Up = _Tp> 00323 typename __gnu_cxx::__enable_if<!std::__are_same<_Up, bool>::__value, 00324 void>::__type 00325 push_back(_Tp&& __x) 00326 { emplace_back(std::move(__x)); } 00327 00328 template<typename... _Args> 00329 void 00330 emplace_back(_Args&&... __args) 00331 { 00332 bool __realloc = _M_requires_reallocation(this->size() + 1); 00333 _Base::emplace_back(std::forward<_Args>(__args)...); 00334 if (__realloc) 00335 this->_M_invalidate_all(); 00336 _M_update_guaranteed_capacity(); 00337 } 00338 #endif 00339 00340 void 00341 pop_back() 00342 { 00343 __glibcxx_check_nonempty(); 00344 iterator __victim = end() - 1; 00345 __victim._M_invalidate(); 00346 _Base::pop_back(); 00347 } 00348 00349 #ifdef __GXX_EXPERIMENTAL_CXX0X__ 00350 template<typename... _Args> 00351 iterator 00352 emplace(iterator __position, _Args&&... __args) 00353 { 00354 __glibcxx_check_insert(__position); 00355 bool __realloc = _M_requires_reallocation(this->size() + 1); 00356 difference_type __offset = __position - begin(); 00357 typename _Base::iterator __res = _Base::emplace(__position.base(), 00358 std::forward<_Args>(__args)...); 00359 if (__realloc) 00360 this->_M_invalidate_all(); 00361 else 00362 this->_M_invalidate_if(_After_nth(__offset, _M_base().begin())); 00363 _M_update_guaranteed_capacity(); 00364 return iterator(__res, this); 00365 } 00366 #endif 00367 00368 iterator 00369 insert(iterator __position, const _Tp& __x) 00370 { 00371 __glibcxx_check_insert(__position); 00372 bool __realloc = _M_requires_reallocation(this->size() + 1); 00373 difference_type __offset = __position - begin(); 00374 typename _Base::iterator __res = _Base::insert(__position.base(),__x); 00375 if (__realloc) 00376 this->_M_invalidate_all(); 00377 else 00378 this->_M_invalidate_if(_After_nth(__offset, _M_base().begin())); 00379 _M_update_guaranteed_capacity(); 00380 return iterator(__res, this); 00381 } 00382 00383 #ifdef __GXX_EXPERIMENTAL_CXX0X__ 00384 template<typename _Up = _Tp> 00385 typename __gnu_cxx::__enable_if<!std::__are_same<_Up, bool>::__value, 00386 iterator>::__type 00387 insert(iterator __position, _Tp&& __x) 00388 { return emplace(__position, std::move(__x)); } 00389 00390 void 00391 insert(iterator __position, initializer_list<value_type> __l) 00392 { this->insert(__position, __l.begin(), __l.end()); } 00393 #endif 00394 00395 void 00396 insert(iterator __position, size_type __n, const _Tp& __x) 00397 { 00398 __glibcxx_check_insert(__position); 00399 bool __realloc = _M_requires_reallocation(this->size() + __n); 00400 difference_type __offset = __position - begin(); 00401 _Base::insert(__position.base(), __n, __x); 00402 if (__realloc) 00403 this->_M_invalidate_all(); 00404 else 00405 this->_M_invalidate_if(_After_nth(__offset, _M_base().begin())); 00406 _M_update_guaranteed_capacity(); 00407 } 00408 00409 template<class _InputIterator> 00410 void 00411 insert(iterator __position, 00412 _InputIterator __first, _InputIterator __last) 00413 { 00414 __glibcxx_check_insert_range(__position, __first, __last); 00415 00416 /* Hard to guess if invalidation will occur, because __last 00417 - __first can't be calculated in all cases, so we just 00418 punt here by checking if it did occur. */ 00419 typename _Base::iterator __old_begin = _M_base().begin(); 00420 difference_type __offset = __position - begin(); 00421 _Base::insert(__position.base(), __first, __last); 00422 00423 if (_M_base().begin() != __old_begin) 00424 this->_M_invalidate_all(); 00425 else 00426 this->_M_invalidate_if(_After_nth(__offset, _M_base().begin())); 00427 _M_update_guaranteed_capacity(); 00428 } 00429 00430 iterator 00431 erase(iterator __position) 00432 { 00433 __glibcxx_check_erase(__position); 00434 difference_type __offset = __position - begin(); 00435 typename _Base::iterator __res = _Base::erase(__position.base()); 00436 this->_M_invalidate_if(_After_nth(__offset, _M_base().begin())); 00437 return iterator(__res, this); 00438 } 00439 00440 iterator 00441 erase(iterator __first, iterator __last) 00442 { 00443 // _GLIBCXX_RESOLVE_LIB_DEFECTS 00444 // 151. can't currently clear() empty container 00445 __glibcxx_check_erase_range(__first, __last); 00446 00447 difference_type __offset = __first - begin(); 00448 typename _Base::iterator __res = _Base::erase(__first.base(), 00449 __last.base()); 00450 this->_M_invalidate_if(_After_nth(__offset, _M_base().begin())); 00451 return iterator(__res, this); 00452 } 00453 00454 void 00455 #ifdef __GXX_EXPERIMENTAL_CXX0X__ 00456 swap(vector&& __x) 00457 #else 00458 swap(vector& __x) 00459 #endif 00460 { 00461 _Base::swap(__x); 00462 this->_M_swap(__x); 00463 std::swap(_M_guaranteed_capacity, __x._M_guaranteed_capacity); 00464 } 00465 00466 void 00467 clear() 00468 { 00469 _Base::clear(); 00470 this->_M_invalidate_all(); 00471 _M_guaranteed_capacity = 0; 00472 } 00473 00474 _Base& 00475 _M_base() { return *this; } 00476 00477 const _Base& 00478 _M_base() const { return *this; } 00479 00480 private: 00481 size_type _M_guaranteed_capacity; 00482 00483 bool 00484 _M_requires_reallocation(size_type __elements) 00485 { return __elements > this->capacity(); } 00486 00487 void 00488 _M_update_guaranteed_capacity() 00489 { 00490 if (this->size() > _M_guaranteed_capacity) 00491 _M_guaranteed_capacity = this->size(); 00492 } 00493 }; 00494 00495 template<typename _Tp, typename _Alloc> 00496 inline bool 00497 operator==(const vector<_Tp, _Alloc>& __lhs, 00498 const vector<_Tp, _Alloc>& __rhs) 00499 { return __lhs._M_base() == __rhs._M_base(); } 00500 00501 template<typename _Tp, typename _Alloc> 00502 inline bool 00503 operator!=(const vector<_Tp, _Alloc>& __lhs, 00504 const vector<_Tp, _Alloc>& __rhs) 00505 { return __lhs._M_base() != __rhs._M_base(); } 00506 00507 template<typename _Tp, typename _Alloc> 00508 inline bool 00509 operator<(const vector<_Tp, _Alloc>& __lhs, 00510 const vector<_Tp, _Alloc>& __rhs) 00511 { return __lhs._M_base() < __rhs._M_base(); } 00512 00513 template<typename _Tp, typename _Alloc> 00514 inline bool 00515 operator<=(const vector<_Tp, _Alloc>& __lhs, 00516 const vector<_Tp, _Alloc>& __rhs) 00517 { return __lhs._M_base() <= __rhs._M_base(); } 00518 00519 template<typename _Tp, typename _Alloc> 00520 inline bool 00521 operator>=(const vector<_Tp, _Alloc>& __lhs, 00522 const vector<_Tp, _Alloc>& __rhs) 00523 { return __lhs._M_base() >= __rhs._M_base(); } 00524 00525 template<typename _Tp, typename _Alloc> 00526 inline bool 00527 operator>(const vector<_Tp, _Alloc>& __lhs, 00528 const vector<_Tp, _Alloc>& __rhs) 00529 { return __lhs._M_base() > __rhs._M_base(); } 00530 00531 template<typename _Tp, typename _Alloc> 00532 inline void 00533 swap(vector<_Tp, _Alloc>& __lhs, vector<_Tp, _Alloc>& __rhs) 00534 { __lhs.swap(__rhs); } 00535 00536 #ifdef __GXX_EXPERIMENTAL_CXX0X__ 00537 template<typename _Tp, typename _Alloc> 00538 inline void 00539 swap(vector<_Tp, _Alloc>&& __lhs, vector<_Tp, _Alloc>& __rhs) 00540 { __lhs.swap(__rhs); } 00541 00542 template<typename _Tp, typename _Alloc> 00543 inline void 00544 swap(vector<_Tp, _Alloc>& __lhs, vector<_Tp, _Alloc>&& __rhs) 00545 { __lhs.swap(__rhs); } 00546 #endif 00547 00548 } // namespace __debug 00549 } // namespace std 00550 00551 #endif