1 // Debugging vector implementation -*- C++ -*- 2 3 // Copyright (C) 2003, 2004, 2005, 2006, 2007, 2008, 2009 4 // Free Software Foundation, Inc. 5 // 6 // This file is part of the GNU ISO C++ Library. This library is free 7 // software; you can redistribute it and/or modify it under the 8 // terms of the GNU General Public License as published by the 9 // Free Software Foundation; either version 3, or (at your option) 10 // any later version. 11 12 // This library is distributed in the hope that it will be useful, 13 // but WITHOUT ANY WARRANTY; without even the implied warranty of 14 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 15 // GNU General Public License for more details. 16 17 // Under Section 7 of GPL version 3, you are granted additional 18 // permissions described in the GCC Runtime Library Exception, version 19 // 3.1, as published by the Free Software Foundation. 20 21 // You should have received a copy of the GNU General Public License and 22 // a copy of the GCC Runtime Library Exception along with this program; 23 // see the files COPYING3 and COPYING.RUNTIME respectively. If not, see 24 // <http://www.gnu.org/licenses/>. 25 26 /** @file debug/vector 27 * This file is a GNU debug extension to the Standard C++ Library. 28 */ 29 30 #ifndef _GLIBCXX_DEBUG_VECTOR 31 #define _GLIBCXX_DEBUG_VECTOR 1 32 33 #include <vector> 34 #include <utility> 35 #include <debug/safe_sequence.h> 36 #include <debug/safe_iterator.h> 37 38 namespace std 39 { 40 namespace __debug 41 { 42 template<typename _Tp, 43 typename _Allocator = std::allocator<_Tp> > 44 class vector 45 : public _GLIBCXX_STD_D::vector<_Tp, _Allocator>, 46 public __gnu_debug::_Safe_sequence<vector<_Tp, _Allocator> > 47 { 48 typedef _GLIBCXX_STD_D::vector<_Tp, _Allocator> _Base; 49 typedef __gnu_debug::_Safe_sequence<vector> _Safe_base; 50 51 typedef typename _Base::const_iterator _Base_const_iterator; 52 typedef __gnu_debug::_After_nth_from<_Base_const_iterator> _After_nth; 53 54 public: 55 typedef typename _Base::reference reference; 56 typedef typename _Base::const_reference const_reference; 57 58 typedef __gnu_debug::_Safe_iterator<typename _Base::iterator,vector> 59 iterator; 60 typedef __gnu_debug::_Safe_iterator<typename _Base::const_iterator,vector> 61 const_iterator; 62 63 typedef typename _Base::size_type size_type; 64 typedef typename _Base::difference_type difference_type; 65 66 typedef _Tp value_type; 67 typedef _Allocator allocator_type; 68 typedef typename _Base::pointer pointer; 69 typedef typename _Base::const_pointer const_pointer; 70 typedef std::reverse_iterator<iterator> reverse_iterator; 71 typedef std::reverse_iterator<const_iterator> const_reverse_iterator; 72 73 // 23.2.4.1 construct/copy/destroy: 74 explicit vector(const _Allocator& __a = _Allocator()) 75 : _Base(__a), _M_guaranteed_capacity(0) { } 76 77 explicit vector(size_type __n, const _Tp& __value = _Tp(), 78 const _Allocator& __a = _Allocator()) 79 : _Base(__n, __value, __a), _M_guaranteed_capacity(__n) { } 80 81 template<class _InputIterator> 82 vector(_InputIterator __first, _InputIterator __last, 83 const _Allocator& __a = _Allocator()) 84 : _Base(__gnu_debug::__check_valid_range(__first, __last), 85 __last, __a), 86 _M_guaranteed_capacity(0) 87 { _M_update_guaranteed_capacity(); } 88 89 vector(const vector& __x) 90 : _Base(__x), _Safe_base(), _M_guaranteed_capacity(__x.size()) { } 91 92 /// Construction from a release-mode vector 93 vector(const _Base& __x) 94 : _Base(__x), _Safe_base(), _M_guaranteed_capacity(__x.size()) { } 95 96 #ifdef __GXX_EXPERIMENTAL_CXX0X__ 97 vector(vector&& __x) 98 : _Base(std::forward<vector>(__x)), _Safe_base(), 99 _M_guaranteed_capacity(this->size()) 100 { 101 this->_M_swap(__x); 102 __x._M_guaranteed_capacity = 0; 103 } 104 105 vector(initializer_list<value_type> __l, 106 const allocator_type& __a = allocator_type()) 107 : _Base(__l, __a), _Safe_base(), 108 _M_guaranteed_capacity(__l.size()) { } 109 #endif 110 111 ~vector() { } 112 113 vector& 114 operator=(const vector& __x) 115 { 116 static_cast<_Base&>(*this) = __x; 117 this->_M_invalidate_all(); 118 _M_update_guaranteed_capacity(); 119 return *this; 120 } 121 122 #ifdef __GXX_EXPERIMENTAL_CXX0X__ 123 vector& 124 operator=(vector&& __x) 125 { 126 // NB: DR 675. 127 clear(); 128 swap(__x); 129 return *this; 130 } 131 132 vector& 133 operator=(initializer_list<value_type> __l) 134 { 135 static_cast<_Base&>(*this) = __l; 136 this->_M_invalidate_all(); 137 _M_update_guaranteed_capacity(); 138 return *this; 139 } 140 #endif 141 142 template<typename _InputIterator> 143 void 144 assign(_InputIterator __first, _InputIterator __last) 145 { 146 __glibcxx_check_valid_range(__first, __last); 147 _Base::assign(__first, __last); 148 this->_M_invalidate_all(); 149 _M_update_guaranteed_capacity(); 150 } 151 152 void 153 assign(size_type __n, const _Tp& __u) 154 { 155 _Base::assign(__n, __u); 156 this->_M_invalidate_all(); 157 _M_update_guaranteed_capacity(); 158 } 159 160 #ifdef __GXX_EXPERIMENTAL_CXX0X__ 161 void 162 assign(initializer_list<value_type> __l) 163 { 164 _Base::assign(__l); 165 this->_M_invalidate_all(); 166 _M_update_guaranteed_capacity(); 167 } 168 #endif 169 170 using _Base::get_allocator; 171 172 // iterators: 173 iterator 174 begin() 175 { return iterator(_Base::begin(), this); } 176 177 const_iterator 178 begin() const 179 { return const_iterator(_Base::begin(), this); } 180 181 iterator 182 end() 183 { return iterator(_Base::end(), this); } 184 185 const_iterator 186 end() const 187 { return const_iterator(_Base::end(), this); } 188 189 reverse_iterator 190 rbegin() 191 { return reverse_iterator(end()); } 192 193 const_reverse_iterator 194 rbegin() const 195 { return const_reverse_iterator(end()); } 196 197 reverse_iterator 198 rend() 199 { return reverse_iterator(begin()); } 200 201 const_reverse_iterator 202 rend() const 203 { return const_reverse_iterator(begin()); } 204 205 #ifdef __GXX_EXPERIMENTAL_CXX0X__ 206 const_iterator 207 cbegin() const 208 { return const_iterator(_Base::begin(), this); } 209 210 const_iterator 211 cend() const 212 { return const_iterator(_Base::end(), this); } 213 214 const_reverse_iterator 215 crbegin() const 216 { return const_reverse_iterator(end()); } 217 218 const_reverse_iterator 219 crend() const 220 { return const_reverse_iterator(begin()); } 221 #endif 222 223 // 23.2.4.2 capacity: 224 using _Base::size; 225 using _Base::max_size; 226 227 void 228 resize(size_type __sz, _Tp __c = _Tp()) 229 { 230 bool __realloc = _M_requires_reallocation(__sz); 231 if (__sz < this->size()) 232 this->_M_invalidate_if(_After_nth(__sz, _M_base().begin())); 233 _Base::resize(__sz, __c); 234 if (__realloc) 235 this->_M_invalidate_all(); 236 } 237 238 size_type 239 capacity() const 240 { 241 #ifdef _GLIBCXX_DEBUG_PEDANTIC 242 return _M_guaranteed_capacity; 243 #else 244 return _Base::capacity(); 245 #endif 246 } 247 248 using _Base::empty; 249 250 void 251 reserve(size_type __n) 252 { 253 bool __realloc = _M_requires_reallocation(__n); 254 _Base::reserve(__n); 255 if (__n > _M_guaranteed_capacity) 256 _M_guaranteed_capacity = __n; 257 if (__realloc) 258 this->_M_invalidate_all(); 259 } 260 261 // element access: 262 reference 263 operator[](size_type __n) 264 { 265 __glibcxx_check_subscript(__n); 266 return _M_base()[__n]; 267 } 268 269 const_reference 270 operator[](size_type __n) const 271 { 272 __glibcxx_check_subscript(__n); 273 return _M_base()[__n]; 274 } 275 276 using _Base::at; 277 278 reference 279 front() 280 { 281 __glibcxx_check_nonempty(); 282 return _Base::front(); 283 } 284 285 const_reference 286 front() const 287 { 288 __glibcxx_check_nonempty(); 289 return _Base::front(); 290 } 291 292 reference 293 back() 294 { 295 __glibcxx_check_nonempty(); 296 return _Base::back(); 297 } 298 299 const_reference 300 back() const 301 { 302 __glibcxx_check_nonempty(); 303 return _Base::back(); 304 } 305 306 // _GLIBCXX_RESOLVE_LIB_DEFECTS 307 // DR 464. Suggestion for new member functions in standard containers. 308 using _Base::data; 309 310 // 23.2.4.3 modifiers: 311 void 312 push_back(const _Tp& __x) 313 { 314 bool __realloc = _M_requires_reallocation(this->size() + 1); 315 _Base::push_back(__x); 316 if (__realloc) 317 this->_M_invalidate_all(); 318 _M_update_guaranteed_capacity(); 319 } 320 321 #ifdef __GXX_EXPERIMENTAL_CXX0X__ 322 template<typename _Up = _Tp> 323 typename __gnu_cxx::__enable_if<!std::__are_same<_Up, bool>::__value, 324 void>::__type 325 push_back(_Tp&& __x) 326 { emplace_back(std::move(__x)); } 327 328 template<typename... _Args> 329 void 330 emplace_back(_Args&&... __args) 331 { 332 bool __realloc = _M_requires_reallocation(this->size() + 1); 333 _Base::emplace_back(std::forward<_Args>(__args)...); 334 if (__realloc) 335 this->_M_invalidate_all(); 336 _M_update_guaranteed_capacity(); 337 } 338 #endif 339 340 void 341 pop_back() 342 { 343 __glibcxx_check_nonempty(); 344 iterator __victim = end() - 1; 345 __victim._M_invalidate(); 346 _Base::pop_back(); 347 } 348 349 #ifdef __GXX_EXPERIMENTAL_CXX0X__ 350 template<typename... _Args> 351 iterator 352 emplace(iterator __position, _Args&&... __args) 353 { 354 __glibcxx_check_insert(__position); 355 bool __realloc = _M_requires_reallocation(this->size() + 1); 356 difference_type __offset = __position - begin(); 357 typename _Base::iterator __res = _Base::emplace(__position.base(), 358 std::forward<_Args>(__args)...); 359 if (__realloc) 360 this->_M_invalidate_all(); 361 else 362 this->_M_invalidate_if(_After_nth(__offset, _M_base().begin())); 363 _M_update_guaranteed_capacity(); 364 return iterator(__res, this); 365 } 366 #endif 367 368 iterator 369 insert(iterator __position, const _Tp& __x) 370 { 371 __glibcxx_check_insert(__position); 372 bool __realloc = _M_requires_reallocation(this->size() + 1); 373 difference_type __offset = __position - begin(); 374 typename _Base::iterator __res = _Base::insert(__position.base(),__x); 375 if (__realloc) 376 this->_M_invalidate_all(); 377 else 378 this->_M_invalidate_if(_After_nth(__offset, _M_base().begin())); 379 _M_update_guaranteed_capacity(); 380 return iterator(__res, this); 381 } 382 383 #ifdef __GXX_EXPERIMENTAL_CXX0X__ 384 template<typename _Up = _Tp> 385 typename __gnu_cxx::__enable_if<!std::__are_same<_Up, bool>::__value, 386 iterator>::__type 387 insert(iterator __position, _Tp&& __x) 388 { return emplace(__position, std::move(__x)); } 389 390 void 391 insert(iterator __position, initializer_list<value_type> __l) 392 { this->insert(__position, __l.begin(), __l.end()); } 393 #endif 394 395 void 396 insert(iterator __position, size_type __n, const _Tp& __x) 397 { 398 __glibcxx_check_insert(__position); 399 bool __realloc = _M_requires_reallocation(this->size() + __n); 400 difference_type __offset = __position - begin(); 401 _Base::insert(__position.base(), __n, __x); 402 if (__realloc) 403 this->_M_invalidate_all(); 404 else 405 this->_M_invalidate_if(_After_nth(__offset, _M_base().begin())); 406 _M_update_guaranteed_capacity(); 407 } 408 409 template<class _InputIterator> 410 void 411 insert(iterator __position, 412 _InputIterator __first, _InputIterator __last) 413 { 414 __glibcxx_check_insert_range(__position, __first, __last); 415 416 /* Hard to guess if invalidation will occur, because __last 417 - __first can't be calculated in all cases, so we just 418 punt here by checking if it did occur. */ 419 typename _Base::iterator __old_begin = _M_base().begin(); 420 difference_type __offset = __position - begin(); 421 _Base::insert(__position.base(), __first, __last); 422 423 if (_M_base().begin() != __old_begin) 424 this->_M_invalidate_all(); 425 else 426 this->_M_invalidate_if(_After_nth(__offset, _M_base().begin())); 427 _M_update_guaranteed_capacity(); 428 } 429 430 iterator 431 erase(iterator __position) 432 { 433 __glibcxx_check_erase(__position); 434 difference_type __offset = __position - begin(); 435 typename _Base::iterator __res = _Base::erase(__position.base()); 436 this->_M_invalidate_if(_After_nth(__offset, _M_base().begin())); 437 return iterator(__res, this); 438 } 439 440 iterator 441 erase(iterator __first, iterator __last) 442 { 443 // _GLIBCXX_RESOLVE_LIB_DEFECTS 444 // 151. can't currently clear() empty container 445 __glibcxx_check_erase_range(__first, __last); 446 447 difference_type __offset = __first - begin(); 448 typename _Base::iterator __res = _Base::erase(__first.base(), 449 __last.base()); 450 this->_M_invalidate_if(_After_nth(__offset, _M_base().begin())); 451 return iterator(__res, this); 452 } 453 454 void 455 #ifdef __GXX_EXPERIMENTAL_CXX0X__ 456 swap(vector&& __x) 457 #else 458 swap(vector& __x) 459 #endif 460 { 461 _Base::swap(__x); 462 this->_M_swap(__x); 463 std::swap(_M_guaranteed_capacity, __x._M_guaranteed_capacity); 464 } 465 466 void 467 clear() 468 { 469 _Base::clear(); 470 this->_M_invalidate_all(); 471 _M_guaranteed_capacity = 0; 472 } 473 474 _Base& 475 _M_base() { return *this; } 476 477 const _Base& 478 _M_base() const { return *this; } 479 480 private: 481 size_type _M_guaranteed_capacity; 482 483 bool 484 _M_requires_reallocation(size_type __elements) 485 { return __elements > this->capacity(); } 486 487 void 488 _M_update_guaranteed_capacity() 489 { 490 if (this->size() > _M_guaranteed_capacity) 491 _M_guaranteed_capacity = this->size(); 492 } 493 }; 494 495 template<typename _Tp, typename _Alloc> 496 inline bool 497 operator==(const vector<_Tp, _Alloc>& __lhs, 498 const vector<_Tp, _Alloc>& __rhs) 499 { return __lhs._M_base() == __rhs._M_base(); } 500 501 template<typename _Tp, typename _Alloc> 502 inline bool 503 operator!=(const vector<_Tp, _Alloc>& __lhs, 504 const vector<_Tp, _Alloc>& __rhs) 505 { return __lhs._M_base() != __rhs._M_base(); } 506 507 template<typename _Tp, typename _Alloc> 508 inline bool 509 operator<(const vector<_Tp, _Alloc>& __lhs, 510 const vector<_Tp, _Alloc>& __rhs) 511 { return __lhs._M_base() < __rhs._M_base(); } 512 513 template<typename _Tp, typename _Alloc> 514 inline bool 515 operator<=(const vector<_Tp, _Alloc>& __lhs, 516 const vector<_Tp, _Alloc>& __rhs) 517 { return __lhs._M_base() <= __rhs._M_base(); } 518 519 template<typename _Tp, typename _Alloc> 520 inline bool 521 operator>=(const vector<_Tp, _Alloc>& __lhs, 522 const vector<_Tp, _Alloc>& __rhs) 523 { return __lhs._M_base() >= __rhs._M_base(); } 524 525 template<typename _Tp, typename _Alloc> 526 inline bool 527 operator>(const vector<_Tp, _Alloc>& __lhs, 528 const vector<_Tp, _Alloc>& __rhs) 529 { return __lhs._M_base() > __rhs._M_base(); } 530 531 template<typename _Tp, typename _Alloc> 532 inline void 533 swap(vector<_Tp, _Alloc>& __lhs, vector<_Tp, _Alloc>& __rhs) 534 { __lhs.swap(__rhs); } 535 536 #ifdef __GXX_EXPERIMENTAL_CXX0X__ 537 template<typename _Tp, typename _Alloc> 538 inline void 539 swap(vector<_Tp, _Alloc>&& __lhs, vector<_Tp, _Alloc>& __rhs) 540 { __lhs.swap(__rhs); } 541 542 template<typename _Tp, typename _Alloc> 543 inline void 544 swap(vector<_Tp, _Alloc>& __lhs, vector<_Tp, _Alloc>&& __rhs) 545 { __lhs.swap(__rhs); } 546 #endif 547 548 } // namespace __debug 549 } // namespace std 550 551 #endif 552
