libstdc++-v3/include/debug/vector

   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