libstdc++-v3/include/debug/vector

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