libstdc++-v3/include/debug/vector

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