libstdc++-v3/include/debug/vector

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