vector

00001 // Debugging vector implementation -*- C++ -*- 00002 00003 // Copyright (C) 2003, 2004 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 2, 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 // You should have received a copy of the GNU General Public License along 00018 // with this library; see the file COPYING. If not, write to the Free 00019 // Software Foundation, 59 Temple Place - Suite 330, Boston, MA 02111-1307, 00020 // USA. 00021 00022 // As a special exception, you may use this file as part of a free software 00023 // library without restriction. Specifically, if other files instantiate 00024 // templates or use macros or inline functions from this file, or you compile 00025 // this file and link it with other files to produce an executable, this 00026 // file does not by itself cause the resulting executable to be covered by 00027 // the GNU General Public License. This exception does not however 00028 // invalidate any other reasons why the executable file might be covered by 00029 // the GNU General Public License. 00030 00031 #ifndef _GLIBCXX_DEBUG_VECTOR 00032 #define _GLIBCXX_DEBUG_VECTOR 1 00033 00034 #include <vector> 00035 #include <debug/safe_sequence.h> 00036 #include <debug/safe_iterator.h> 00037 #include <utility> 00038 00039 namespace __gnu_debug_def 00040 { 00041 template<typename _Tp, 00042 typename _Allocator = std::allocator<_Tp> > 00043 class vector 00044 : public _GLIBCXX_STD::vector<_Tp, _Allocator>, 00045 public __gnu_debug::_Safe_sequence<vector<_Tp, _Allocator> > 00046 { 00047 typedef _GLIBCXX_STD::vector<_Tp, _Allocator> _Base; 00048 typedef __gnu_debug::_Safe_sequence<vector> _Safe_base; 00049 00050 typedef typename _Base::const_iterator _Base_const_iterator; 00051 typedef __gnu_debug::_After_nth_from<_Base_const_iterator> _After_nth; 00052 00053 public: 00054 typedef typename _Base::reference reference; 00055 typedef typename _Base::const_reference const_reference; 00056 00057 typedef __gnu_debug::_Safe_iterator<typename _Base::iterator,vector> 00058 iterator; 00059 typedef __gnu_debug::_Safe_iterator<typename _Base::const_iterator,vector> 00060 const_iterator; 00061 00062 typedef typename _Base::size_type size_type; 00063 typedef typename _Base::difference_type difference_type; 00064 00065 typedef _Tp value_type; 00066 typedef _Allocator allocator_type; 00067 typedef typename _Allocator::pointer pointer; 00068 typedef typename _Allocator::const_pointer const_pointer; 00069 typedef std::reverse_iterator<iterator> reverse_iterator; 00070 typedef std::reverse_iterator<const_iterator> const_reverse_iterator; 00071 00072 // 23.2.4.1 construct/copy/destroy: 00073 explicit vector(const _Allocator& __a = _Allocator()) 00074 : _Base(__a), _M_guaranteed_capacity(0) { } 00075 00076 explicit vector(size_type __n, const _Tp& __value = _Tp(), 00077 const _Allocator& __a = _Allocator()) 00078 : _Base(__n, __value, __a), _M_guaranteed_capacity(__n) { } 00079 00080 template<class _InputIterator> 00081 vector(_InputIterator __first, _InputIterator __last, 00082 const _Allocator& __a = _Allocator()) 00083 : _Base(__gnu_debug::__check_valid_range(__first, __last), 00084 __last, __a), 00085 _M_guaranteed_capacity(0) 00086 { _M_update_guaranteed_capacity(); } 00087 00088 vector(const vector<_Tp,_Allocator>& __x) 00089 : _Base(__x), _Safe_base(), _M_guaranteed_capacity(__x.size()) { } 00090 00091 /// Construction from a release-mode vector 00092 vector(const _Base& __x) 00093 : _Base(__x), _Safe_base(), _M_guaranteed_capacity(__x.size()) { } 00094 00095 ~vector() { } 00096 00097 vector<_Tp,_Allocator>& 00098 operator=(const vector<_Tp,_Allocator>& __x) 00099 { 00100 static_cast<_Base&>(*this) = __x; 00101 this->_M_invalidate_all(); 00102 _M_update_guaranteed_capacity(); 00103 return *this; 00104 } 00105 00106 template<typename _InputIterator> 00107 void 00108 assign(_InputIterator __first, _InputIterator __last) 00109 { 00110 __glibcxx_check_valid_range(__first, __last); 00111 _Base::assign(__first, __last); 00112 this->_M_invalidate_all(); 00113 _M_update_guaranteed_capacity(); 00114 } 00115 00116 void 00117 assign(size_type __n, const _Tp& __u) 00118 { 00119 _Base::assign(__n, __u); 00120 this->_M_invalidate_all(); 00121 _M_update_guaranteed_capacity(); 00122 } 00123 00124 using _Base::get_allocator; 00125 00126 // iterators: 00127 iterator 00128 begin() 00129 { return iterator(_Base::begin(), this); } 00130 00131 const_iterator 00132 begin() const 00133 { return const_iterator(_Base::begin(), this); } 00134 00135 iterator 00136 end() 00137 { return iterator(_Base::end(), this); } 00138 00139 const_iterator 00140 end() const 00141 { return const_iterator(_Base::end(), this); } 00142 00143 reverse_iterator 00144 rbegin() 00145 { return reverse_iterator(end()); } 00146 00147 const_reverse_iterator 00148 rbegin() const 00149 { return const_reverse_iterator(end()); } 00150 00151 reverse_iterator 00152 rend() 00153 { return reverse_iterator(begin()); } 00154 00155 const_reverse_iterator 00156 rend() const 00157 { return const_reverse_iterator(begin()); } 00158 00159 // 23.2.4.2 capacity: 00160 using _Base::size; 00161 using _Base::max_size; 00162 00163 void 00164 resize(size_type __sz, _Tp __c = _Tp()) 00165 { 00166 bool __realloc = _M_requires_reallocation(__sz); 00167 if (__sz < this->size()) 00168 this->_M_invalidate_if(_After_nth(__sz, _M_base().begin())); 00169 _Base::resize(__sz, __c); 00170 if (__realloc) 00171 this->_M_invalidate_all(); 00172 } 00173 00174 using _Base::capacity; 00175 using _Base::empty; 00176 00177 void 00178 reserve(size_type __n) 00179 { 00180 bool __realloc = _M_requires_reallocation(__n); 00181 _Base::reserve(__n); 00182 if (__n > _M_guaranteed_capacity) 00183 _M_guaranteed_capacity = __n; 00184 if (__realloc) 00185 this->_M_invalidate_all(); 00186 } 00187 00188 // element access: 00189 reference 00190 operator[](size_type __n) 00191 { 00192 __glibcxx_check_subscript(__n); 00193 return _M_base()[__n]; 00194 } 00195 00196 const_reference 00197 operator[](size_type __n) const 00198 { 00199 __glibcxx_check_subscript(__n); 00200 return _M_base()[__n]; 00201 } 00202 00203 using _Base::at; 00204 00205 reference 00206 front() 00207 { 00208 __glibcxx_check_nonempty(); 00209 return _Base::front(); 00210 } 00211 00212 const_reference 00213 front() const 00214 { 00215 __glibcxx_check_nonempty(); 00216 return _Base::front(); 00217 } 00218 00219 reference 00220 back() 00221 { 00222 __glibcxx_check_nonempty(); 00223 return _Base::back(); 00224 } 00225 00226 const_reference 00227 back() const 00228 { 00229 __glibcxx_check_nonempty(); 00230 return _Base::back(); 00231 } 00232 00233 // 23.2.4.3 modifiers: 00234 void 00235 push_back(const _Tp& __x) 00236 { 00237 bool __realloc = _M_requires_reallocation(this->size() + 1); 00238 _Base::push_back(__x); 00239 if (__realloc) 00240 this->_M_invalidate_all(); 00241 _M_update_guaranteed_capacity(); 00242 } 00243 00244 void 00245 pop_back() 00246 { 00247 __glibcxx_check_nonempty(); 00248 iterator __victim = end() - 1; 00249 __victim._M_invalidate(); 00250 _Base::pop_back(); 00251 } 00252 00253 iterator 00254 insert(iterator __position, const _Tp& __x) 00255 { 00256 __glibcxx_check_insert(__position); 00257 bool __realloc = _M_requires_reallocation(this->size() + 1); 00258 difference_type __offset = __position - begin(); 00259 typename _Base::iterator __res = _Base::insert(__position.base(),__x); 00260 if (__realloc) 00261 this->_M_invalidate_all(); 00262 else 00263 this->_M_invalidate_if(_After_nth(__offset, _M_base().begin())); 00264 _M_update_guaranteed_capacity(); 00265 return iterator(__res, this); 00266 } 00267 00268 void 00269 insert(iterator __position, size_type __n, const _Tp& __x) 00270 { 00271 __glibcxx_check_insert(__position); 00272 bool __realloc = _M_requires_reallocation(this->size() + __n); 00273 difference_type __offset = __position - begin(); 00274 _Base::insert(__position.base(), __n, __x); 00275 if (__realloc) 00276 this->_M_invalidate_all(); 00277 else 00278 this->_M_invalidate_if(_After_nth(__offset, _M_base().begin())); 00279 _M_update_guaranteed_capacity(); 00280 } 00281 00282 template<class _InputIterator> 00283 void 00284 insert(iterator __position, 00285 _InputIterator __first, _InputIterator __last) 00286 { 00287 __glibcxx_check_insert_range(__position, __first, __last); 00288 00289 /* Hard to guess if invalidation will occur, because __last 00290 - __first can't be calculated in all cases, so we just 00291 punt here by checking if it did occur. */ 00292 typename _Base::iterator __old_begin = _M_base().begin(); 00293 difference_type __offset = __position - begin(); 00294 _Base::insert(__position.base(), __first, __last); 00295 00296 if (_M_base().begin() != __old_begin) 00297 this->_M_invalidate_all(); 00298 else 00299 this->_M_invalidate_if(_After_nth(__offset, _M_base().begin())); 00300 _M_update_guaranteed_capacity(); 00301 } 00302 00303 iterator 00304 erase(iterator __position) 00305 { 00306 __glibcxx_check_erase(__position); 00307 difference_type __offset = __position - begin(); 00308 typename _Base::iterator __res = _Base::erase(__position.base()); 00309 this->_M_invalidate_if(_After_nth(__offset, _M_base().begin())); 00310 return iterator(__res, this); 00311 } 00312 00313 iterator 00314 erase(iterator __first, iterator __last) 00315 { 00316 // _GLIBCXX_RESOLVE_LIB_DEFECTS 00317 // 151. can't currently clear() empty container 00318 __glibcxx_check_erase_range(__first, __last); 00319 00320 difference_type __offset = __first - begin(); 00321 typename _Base::iterator __res = _Base::erase(__first.base(), 00322 __last.base()); 00323 this->_M_invalidate_if(_After_nth(__offset, _M_base().begin())); 00324 return iterator(__res, this); 00325 } 00326 00327 void 00328 swap(vector<_Tp,_Allocator>& __x) 00329 { 00330 _Base::swap(__x); 00331 this->_M_swap(__x); 00332 std::swap(_M_guaranteed_capacity, __x._M_guaranteed_capacity); 00333 } 00334 00335 void 00336 clear() 00337 { 00338 _Base::clear(); 00339 this->_M_invalidate_all(); 00340 _M_guaranteed_capacity = 0; 00341 } 00342 00343 _Base& 00344 _M_base() { return *this; } 00345 00346 const _Base& 00347 _M_base() const { return *this; } 00348 00349 private: 00350 size_type _M_guaranteed_capacity; 00351 00352 bool 00353 _M_requires_reallocation(size_type __elements) 00354 { 00355 #ifdef _GLIBCXX_DEBUG_PEDANTIC 00356 return __elements > this->capacity(); 00357 #else 00358 return __elements > _M_guaranteed_capacity; 00359 #endif 00360 } 00361 00362 void 00363 _M_update_guaranteed_capacity() 00364 { 00365 if (this->size() > _M_guaranteed_capacity) 00366 _M_guaranteed_capacity = this->size(); 00367 } 00368 }; 00369 00370 template<typename _Tp, typename _Alloc> 00371 inline bool 00372 operator==(const vector<_Tp, _Alloc>& __lhs, 00373 const vector<_Tp, _Alloc>& __rhs) 00374 { return __lhs._M_base() == __rhs._M_base(); } 00375 00376 template<typename _Tp, typename _Alloc> 00377 inline bool 00378 operator!=(const vector<_Tp, _Alloc>& __lhs, 00379 const vector<_Tp, _Alloc>& __rhs) 00380 { return __lhs._M_base() != __rhs._M_base(); } 00381 00382 template<typename _Tp, typename _Alloc> 00383 inline bool 00384 operator<(const vector<_Tp, _Alloc>& __lhs, 00385 const vector<_Tp, _Alloc>& __rhs) 00386 { return __lhs._M_base() < __rhs._M_base(); } 00387 00388 template<typename _Tp, typename _Alloc> 00389 inline bool 00390 operator<=(const vector<_Tp, _Alloc>& __lhs, 00391 const vector<_Tp, _Alloc>& __rhs) 00392 { return __lhs._M_base() <= __rhs._M_base(); } 00393 00394 template<typename _Tp, typename _Alloc> 00395 inline bool 00396 operator>=(const vector<_Tp, _Alloc>& __lhs, 00397 const vector<_Tp, _Alloc>& __rhs) 00398 { return __lhs._M_base() >= __rhs._M_base(); } 00399 00400 template<typename _Tp, typename _Alloc> 00401 inline bool 00402 operator>(const vector<_Tp, _Alloc>& __lhs, 00403 const vector<_Tp, _Alloc>& __rhs) 00404 { return __lhs._M_base() > __rhs._M_base(); } 00405 00406 template<typename _Tp, typename _Alloc> 00407 inline void 00408 swap(vector<_Tp, _Alloc>& __lhs, vector<_Tp, _Alloc>& __rhs) 00409 { __lhs.swap(__rhs); } 00410 } // namespace __gnu_debug_def 00411 00412 #endif

Generated on Wed Jun 9 11:19:23 2004 for libstdc++-v3 Source by doxygen 1.3.7