libstdc++-v3/include/debug/vector

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