1 // Debugging vector implementation -*- C++ -*-
3 // Copyright (C) 2003-2021 Free Software Foundation, Inc.
5 // This file is part of the GNU ISO C++ Library. This library is free
6 // software; you can redistribute it and/or modify it under the
7 // terms of the GNU General Public License as published by the
8 // Free Software Foundation; either version 3, or (at your option)
11 // This library is distributed in the hope that it will be useful,
12 // but WITHOUT ANY WARRANTY; without even the implied warranty of
13 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 // GNU General Public License for more details.
16 // Under Section 7 of GPL version 3, you are granted additional
17 // permissions described in the GCC Runtime Library Exception, version
18 // 3.1, as published by the Free Software Foundation.
20 // You should have received a copy of the GNU General Public License and
21 // a copy of the GCC Runtime Library Exception along with this program;
22 // see the files COPYING3 and COPYING.RUNTIME respectively. If not, see
23 // <http://www.gnu.org/licenses/>.
25 /** @file debug/vector
26 * This file is a GNU debug extension to the Standard C++ Library.
29 #ifndef _GLIBCXX_DEBUG_VECTOR
30 #define _GLIBCXX_DEBUG_VECTOR 1
32 #pragma GCC system_header
34 #include <bits/c++config.h>
35 namespace std _GLIBCXX_VISIBILITY(default) { namespace __debug {
36 template<typename _Tp, typename _Allocator> class vector;
37 } } // namespace std::__debug
41 #include <debug/safe_sequence.h>
42 #include <debug/safe_container.h>
43 #include <debug/safe_iterator.h>
47 /** @brief Base class for Debug Mode vector.
49 * Adds information about the guaranteed capacity, which is useful for
50 * detecting code which relies on non-portable implementation details of
51 * the libstdc++ reallocation policy.
53 template<typename _SafeSequence,
54 typename _BaseSequence>
57 typedef typename _BaseSequence::size_type size_type;
60 _M_seq() const { return *static_cast<const _SafeSequence*>(this); }
63 _Safe_vector() _GLIBCXX_NOEXCEPT
64 : _M_guaranteed_capacity(0)
65 { _M_update_guaranteed_capacity(); }
67 _Safe_vector(const _Safe_vector&) _GLIBCXX_NOEXCEPT
68 : _M_guaranteed_capacity(0)
69 { _M_update_guaranteed_capacity(); }
71 _Safe_vector(size_type __n) _GLIBCXX_NOEXCEPT
72 : _M_guaranteed_capacity(__n)
75 #if __cplusplus >= 201103L
76 _Safe_vector(_Safe_vector&& __x) noexcept
78 { __x._M_guaranteed_capacity = 0; }
81 operator=(const _Safe_vector&) noexcept
83 _M_update_guaranteed_capacity();
88 operator=(_Safe_vector&& __x) noexcept
90 _M_update_guaranteed_capacity();
91 __x._M_guaranteed_capacity = 0;
96 size_type _M_guaranteed_capacity;
99 _M_requires_reallocation(size_type __elements) const _GLIBCXX_NOEXCEPT
100 { return __elements > _M_seq().capacity(); }
103 _M_update_guaranteed_capacity() _GLIBCXX_NOEXCEPT
105 if (_M_seq().size() > _M_guaranteed_capacity)
106 _M_guaranteed_capacity = _M_seq().size();
111 namespace std _GLIBCXX_VISIBILITY(default)
115 /// Class std::vector with safety/checking/debug instrumentation.
116 template<typename _Tp,
117 typename _Allocator = std::allocator<_Tp> >
119 : public __gnu_debug::_Safe_container<
120 vector<_Tp, _Allocator>, _Allocator, __gnu_debug::_Safe_sequence>,
121 public _GLIBCXX_STD_C::vector<_Tp, _Allocator>,
122 public __gnu_debug::_Safe_vector<
123 vector<_Tp, _Allocator>,
124 _GLIBCXX_STD_C::vector<_Tp, _Allocator> >
126 typedef _GLIBCXX_STD_C::vector<_Tp, _Allocator> _Base;
127 typedef __gnu_debug::_Safe_container<
128 vector, _Allocator, __gnu_debug::_Safe_sequence> _Safe;
129 typedef __gnu_debug::_Safe_vector<vector, _Base> _Safe_vector;
131 typedef typename _Base::iterator _Base_iterator;
132 typedef typename _Base::const_iterator _Base_const_iterator;
133 typedef __gnu_debug::_Equal_to<_Base_const_iterator> _Equal;
135 template<typename _ItT, typename _SeqT, typename _CatT>
136 friend class ::__gnu_debug::_Safe_iterator;
138 // Reference wrapper for base class. Disambiguates vector(const _Base&)
139 // from copy constructor by requiring a user-defined conversion.
140 // See PR libstdc++/90102.
143 _Base_ref(const _Base& __r) : _M_ref(__r) { }
149 typedef typename _Base::reference reference;
150 typedef typename _Base::const_reference const_reference;
152 typedef __gnu_debug::_Safe_iterator<
153 _Base_iterator, vector> iterator;
154 typedef __gnu_debug::_Safe_iterator<
155 _Base_const_iterator, vector> const_iterator;
157 typedef typename _Base::size_type size_type;
158 typedef typename _Base::difference_type difference_type;
160 typedef _Tp value_type;
161 typedef _Allocator allocator_type;
162 typedef typename _Base::pointer pointer;
163 typedef typename _Base::const_pointer const_pointer;
164 typedef std::reverse_iterator<iterator> reverse_iterator;
165 typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
167 // 23.2.4.1 construct/copy/destroy:
169 #if __cplusplus < 201103L
170 vector() _GLIBCXX_NOEXCEPT
177 vector(const _Allocator& __a) _GLIBCXX_NOEXCEPT
180 #if __cplusplus >= 201103L
182 vector(size_type __n, const _Allocator& __a = _Allocator())
183 : _Base(__n, __a), _Safe_vector(__n) { }
185 vector(size_type __n, const _Tp& __value,
186 const _Allocator& __a = _Allocator())
187 : _Base(__n, __value, __a) { }
190 vector(size_type __n, const _Tp& __value = _Tp(),
191 const _Allocator& __a = _Allocator())
192 : _Base(__n, __value, __a) { }
195 #if __cplusplus >= 201103L
196 template<class _InputIterator,
197 typename = std::_RequireInputIter<_InputIterator>>
199 template<class _InputIterator>
201 vector(_InputIterator __first, _InputIterator __last,
202 const _Allocator& __a = _Allocator())
203 : _Base(__gnu_debug::__base(
204 __glibcxx_check_valid_constructor_range(__first, __last)),
205 __gnu_debug::__base(__last), __a) { }
207 #if __cplusplus < 201103L
208 vector(const vector& __x)
211 ~vector() _GLIBCXX_NOEXCEPT { }
213 vector(const vector&) = default;
214 vector(vector&&) = default;
216 vector(const vector& __x, const allocator_type& __a)
217 : _Base(__x, __a) { }
219 vector(vector&& __x, const allocator_type& __a)
221 _Base(std::declval<_Base&&>()), std::declval<const allocator_type&>()))
222 : _Safe(std::move(__x._M_safe()), __a),
223 _Base(std::move(__x._M_base()), __a),
224 _Safe_vector(std::move(__x)) { }
226 vector(initializer_list<value_type> __l,
227 const allocator_type& __a = allocator_type())
228 : _Base(__l, __a) { }
233 /// Construction from a normal-mode vector
234 vector(_Base_ref __x)
235 : _Base(__x._M_ref) { }
237 #if __cplusplus < 201103L
239 operator=(const vector& __x)
241 this->_M_safe() = __x;
243 this->_M_update_guaranteed_capacity();
248 operator=(const vector&) = default;
251 operator=(vector&&) = default;
254 operator=(initializer_list<value_type> __l)
257 this->_M_invalidate_all();
258 this->_M_update_guaranteed_capacity();
263 #if __cplusplus >= 201103L
264 template<typename _InputIterator,
265 typename = std::_RequireInputIter<_InputIterator>>
267 template<typename _InputIterator>
270 assign(_InputIterator __first, _InputIterator __last)
272 typename __gnu_debug::_Distance_traits<_InputIterator>::__type __dist;
273 __glibcxx_check_valid_range2(__first, __last, __dist);
275 if (__dist.second >= __gnu_debug::__dp_sign)
276 _Base::assign(__gnu_debug::__unsafe(__first),
277 __gnu_debug::__unsafe(__last));
279 _Base::assign(__first, __last);
281 this->_M_invalidate_all();
282 this->_M_update_guaranteed_capacity();
286 assign(size_type __n, const _Tp& __u)
288 _Base::assign(__n, __u);
289 this->_M_invalidate_all();
290 this->_M_update_guaranteed_capacity();
293 #if __cplusplus >= 201103L
295 assign(initializer_list<value_type> __l)
298 this->_M_invalidate_all();
299 this->_M_update_guaranteed_capacity();
303 using _Base::get_allocator;
307 begin() _GLIBCXX_NOEXCEPT
308 { return iterator(_Base::begin(), this); }
311 begin() const _GLIBCXX_NOEXCEPT
312 { return const_iterator(_Base::begin(), this); }
315 end() _GLIBCXX_NOEXCEPT
316 { return iterator(_Base::end(), this); }
319 end() const _GLIBCXX_NOEXCEPT
320 { return const_iterator(_Base::end(), this); }
323 rbegin() _GLIBCXX_NOEXCEPT
324 { return reverse_iterator(end()); }
326 const_reverse_iterator
327 rbegin() const _GLIBCXX_NOEXCEPT
328 { return const_reverse_iterator(end()); }
331 rend() _GLIBCXX_NOEXCEPT
332 { return reverse_iterator(begin()); }
334 const_reverse_iterator
335 rend() const _GLIBCXX_NOEXCEPT
336 { return const_reverse_iterator(begin()); }
338 #if __cplusplus >= 201103L
340 cbegin() const noexcept
341 { return const_iterator(_Base::begin(), this); }
344 cend() const noexcept
345 { return const_iterator(_Base::end(), this); }
347 const_reverse_iterator
348 crbegin() const noexcept
349 { return const_reverse_iterator(end()); }
351 const_reverse_iterator
352 crend() const noexcept
353 { return const_reverse_iterator(begin()); }
356 // 23.2.4.2 capacity:
358 using _Base::max_size;
360 #if __cplusplus >= 201103L
362 resize(size_type __sz)
364 bool __realloc = this->_M_requires_reallocation(__sz);
365 if (__sz < this->size())
366 this->_M_invalidate_after_nth(__sz);
369 this->_M_invalidate_all();
370 this->_M_update_guaranteed_capacity();
374 resize(size_type __sz, const _Tp& __c)
376 bool __realloc = this->_M_requires_reallocation(__sz);
377 if (__sz < this->size())
378 this->_M_invalidate_after_nth(__sz);
379 _Base::resize(__sz, __c);
381 this->_M_invalidate_all();
382 this->_M_update_guaranteed_capacity();
386 resize(size_type __sz, _Tp __c = _Tp())
388 bool __realloc = this->_M_requires_reallocation(__sz);
389 if (__sz < this->size())
390 this->_M_invalidate_after_nth(__sz);
391 _Base::resize(__sz, __c);
393 this->_M_invalidate_all();
394 this->_M_update_guaranteed_capacity();
398 #if __cplusplus >= 201103L
402 if (_Base::_M_shrink_to_fit())
404 this->_M_guaranteed_capacity = _Base::capacity();
405 this->_M_invalidate_all();
411 capacity() const _GLIBCXX_NOEXCEPT
413 #ifdef _GLIBCXX_DEBUG_PEDANTIC
414 return this->_M_guaranteed_capacity;
416 return _Base::capacity();
423 reserve(size_type __n)
425 bool __realloc = this->_M_requires_reallocation(__n);
427 if (__n > this->_M_guaranteed_capacity)
428 this->_M_guaranteed_capacity = __n;
430 this->_M_invalidate_all();
435 operator[](size_type __n) _GLIBCXX_NOEXCEPT
437 __glibcxx_check_subscript(__n);
438 return _M_base()[__n];
442 operator[](size_type __n) const _GLIBCXX_NOEXCEPT
444 __glibcxx_check_subscript(__n);
445 return _M_base()[__n];
451 front() _GLIBCXX_NOEXCEPT
453 __glibcxx_check_nonempty();
454 return _Base::front();
458 front() const _GLIBCXX_NOEXCEPT
460 __glibcxx_check_nonempty();
461 return _Base::front();
465 back() _GLIBCXX_NOEXCEPT
467 __glibcxx_check_nonempty();
468 return _Base::back();
472 back() const _GLIBCXX_NOEXCEPT
474 __glibcxx_check_nonempty();
475 return _Base::back();
478 // _GLIBCXX_RESOLVE_LIB_DEFECTS
479 // DR 464. Suggestion for new member functions in standard containers.
482 // 23.2.4.3 modifiers:
484 push_back(const _Tp& __x)
486 bool __realloc = this->_M_requires_reallocation(this->size() + 1);
487 _Base::push_back(__x);
489 this->_M_invalidate_all();
490 this->_M_update_guaranteed_capacity();
493 #if __cplusplus >= 201103L
494 template<typename _Up = _Tp>
495 typename __gnu_cxx::__enable_if<!std::__are_same<_Up, bool>::__value,
498 { emplace_back(std::move(__x)); }
500 template<typename... _Args>
501 #if __cplusplus > 201402L
506 emplace_back(_Args&&... __args)
508 bool __realloc = this->_M_requires_reallocation(this->size() + 1);
509 _Base::emplace_back(std::forward<_Args>(__args)...);
511 this->_M_invalidate_all();
512 this->_M_update_guaranteed_capacity();
513 #if __cplusplus > 201402L
520 pop_back() _GLIBCXX_NOEXCEPT
522 __glibcxx_check_nonempty();
523 this->_M_invalidate_if(_Equal(--_Base::end()));
527 #if __cplusplus >= 201103L
528 template<typename... _Args>
530 emplace(const_iterator __position, _Args&&... __args)
532 __glibcxx_check_insert(__position);
533 bool __realloc = this->_M_requires_reallocation(this->size() + 1);
534 difference_type __offset = __position.base() - _Base::cbegin();
535 _Base_iterator __res = _Base::emplace(__position.base(),
536 std::forward<_Args>(__args)...);
538 this->_M_invalidate_all();
540 this->_M_invalidate_after_nth(__offset);
541 this->_M_update_guaranteed_capacity();
542 return { __res, this };
547 #if __cplusplus >= 201103L
548 insert(const_iterator __position, const _Tp& __x)
550 insert(iterator __position, const _Tp& __x)
553 __glibcxx_check_insert(__position);
554 bool __realloc = this->_M_requires_reallocation(this->size() + 1);
555 difference_type __offset = __position.base() - _Base::begin();
556 _Base_iterator __res = _Base::insert(__position.base(), __x);
558 this->_M_invalidate_all();
560 this->_M_invalidate_after_nth(__offset);
561 this->_M_update_guaranteed_capacity();
562 return iterator(__res, this);
565 #if __cplusplus >= 201103L
566 template<typename _Up = _Tp>
567 typename __gnu_cxx::__enable_if<!std::__are_same<_Up, bool>::__value,
569 insert(const_iterator __position, _Tp&& __x)
570 { return emplace(__position, std::move(__x)); }
573 insert(const_iterator __position, initializer_list<value_type> __l)
574 { return this->insert(__position, __l.begin(), __l.end()); }
577 #if __cplusplus >= 201103L
579 insert(const_iterator __position, size_type __n, const _Tp& __x)
581 __glibcxx_check_insert(__position);
582 bool __realloc = this->_M_requires_reallocation(this->size() + __n);
583 difference_type __offset = __position.base() - _Base::cbegin();
584 _Base_iterator __res = _Base::insert(__position.base(), __n, __x);
586 this->_M_invalidate_all();
588 this->_M_invalidate_after_nth(__offset);
589 this->_M_update_guaranteed_capacity();
590 return { __res, this };
594 insert(iterator __position, size_type __n, const _Tp& __x)
596 __glibcxx_check_insert(__position);
597 bool __realloc = this->_M_requires_reallocation(this->size() + __n);
598 difference_type __offset = __position.base() - _Base::begin();
599 _Base::insert(__position.base(), __n, __x);
601 this->_M_invalidate_all();
603 this->_M_invalidate_after_nth(__offset);
604 this->_M_update_guaranteed_capacity();
608 #if __cplusplus >= 201103L
609 template<class _InputIterator,
610 typename = std::_RequireInputIter<_InputIterator>>
612 insert(const_iterator __position,
613 _InputIterator __first, _InputIterator __last)
615 typename __gnu_debug::_Distance_traits<_InputIterator>::__type __dist;
616 __glibcxx_check_insert_range(__position, __first, __last, __dist);
618 /* Hard to guess if invalidation will occur, because __last
619 - __first can't be calculated in all cases, so we just
620 punt here by checking if it did occur. */
621 _Base_iterator __old_begin = _M_base().begin();
622 difference_type __offset = __position.base() - _Base::cbegin();
623 _Base_iterator __res;
624 if (__dist.second >= __gnu_debug::__dp_sign)
625 __res = _Base::insert(__position.base(),
626 __gnu_debug::__unsafe(__first),
627 __gnu_debug::__unsafe(__last));
629 __res = _Base::insert(__position.base(), __first, __last);
631 if (_M_base().begin() != __old_begin)
632 this->_M_invalidate_all();
634 this->_M_invalidate_after_nth(__offset);
635 this->_M_update_guaranteed_capacity();
636 return { __res, this };
639 template<class _InputIterator>
641 insert(iterator __position,
642 _InputIterator __first, _InputIterator __last)
644 typename __gnu_debug::_Distance_traits<_InputIterator>::__type __dist;
645 __glibcxx_check_insert_range(__position, __first, __last, __dist);
647 /* Hard to guess if invalidation will occur, because __last
648 - __first can't be calculated in all cases, so we just
649 punt here by checking if it did occur. */
650 _Base_iterator __old_begin = _M_base().begin();
651 difference_type __offset = __position.base() - _Base::begin();
652 if (__dist.second >= __gnu_debug::__dp_sign)
653 _Base::insert(__position.base(), __gnu_debug::__unsafe(__first),
654 __gnu_debug::__unsafe(__last));
656 _Base::insert(__position.base(), __first, __last);
658 if (_M_base().begin() != __old_begin)
659 this->_M_invalidate_all();
661 this->_M_invalidate_after_nth(__offset);
662 this->_M_update_guaranteed_capacity();
667 #if __cplusplus >= 201103L
668 erase(const_iterator __position)
670 erase(iterator __position)
673 __glibcxx_check_erase(__position);
674 difference_type __offset = __position.base() - _Base::begin();
675 _Base_iterator __res = _Base::erase(__position.base());
676 this->_M_invalidate_after_nth(__offset);
677 return iterator(__res, this);
681 #if __cplusplus >= 201103L
682 erase(const_iterator __first, const_iterator __last)
684 erase(iterator __first, iterator __last)
687 // _GLIBCXX_RESOLVE_LIB_DEFECTS
688 // 151. can't currently clear() empty container
689 __glibcxx_check_erase_range(__first, __last);
691 if (__first.base() != __last.base())
693 difference_type __offset = __first.base() - _Base::begin();
694 _Base_iterator __res = _Base::erase(__first.base(),
696 this->_M_invalidate_after_nth(__offset);
697 return iterator(__res, this);
700 #if __cplusplus >= 201103L
701 return { _Base::begin() + (__first.base() - _Base::cbegin()), this };
709 _GLIBCXX_NOEXCEPT_IF( noexcept(declval<_Base&>().swap(__x)) )
713 std::swap(this->_M_guaranteed_capacity, __x._M_guaranteed_capacity);
717 clear() _GLIBCXX_NOEXCEPT
720 this->_M_invalidate_all();
724 _M_base() _GLIBCXX_NOEXCEPT { return *this; }
727 _M_base() const _GLIBCXX_NOEXCEPT { return *this; }
731 _M_invalidate_after_nth(difference_type __n) _GLIBCXX_NOEXCEPT
733 typedef __gnu_debug::_After_nth_from<_Base_const_iterator> _After_nth;
734 this->_M_invalidate_if(_After_nth(__n, _Base::begin()));
738 template<typename _Tp, typename _Alloc>
740 operator==(const vector<_Tp, _Alloc>& __lhs,
741 const vector<_Tp, _Alloc>& __rhs)
742 { return __lhs._M_base() == __rhs._M_base(); }
744 #if __cpp_lib_three_way_comparison
745 template<typename _Tp, typename _Alloc>
746 constexpr __detail::__synth3way_t<_Tp>
747 operator<=>(const vector<_Tp, _Alloc>& __x, const vector<_Tp, _Alloc>& __y)
748 { return __x._M_base() <=> __y._M_base(); }
750 template<typename _Tp, typename _Alloc>
752 operator!=(const vector<_Tp, _Alloc>& __lhs,
753 const vector<_Tp, _Alloc>& __rhs)
754 { return __lhs._M_base() != __rhs._M_base(); }
756 template<typename _Tp, typename _Alloc>
758 operator<(const vector<_Tp, _Alloc>& __lhs,
759 const vector<_Tp, _Alloc>& __rhs)
760 { return __lhs._M_base() < __rhs._M_base(); }
762 template<typename _Tp, typename _Alloc>
764 operator<=(const vector<_Tp, _Alloc>& __lhs,
765 const vector<_Tp, _Alloc>& __rhs)
766 { return __lhs._M_base() <= __rhs._M_base(); }
768 template<typename _Tp, typename _Alloc>
770 operator>=(const vector<_Tp, _Alloc>& __lhs,
771 const vector<_Tp, _Alloc>& __rhs)
772 { return __lhs._M_base() >= __rhs._M_base(); }
774 template<typename _Tp, typename _Alloc>
776 operator>(const vector<_Tp, _Alloc>& __lhs,
777 const vector<_Tp, _Alloc>& __rhs)
778 { return __lhs._M_base() > __rhs._M_base(); }
779 #endif // three-way comparison
781 template<typename _Tp, typename _Alloc>
783 swap(vector<_Tp, _Alloc>& __lhs, vector<_Tp, _Alloc>& __rhs)
784 _GLIBCXX_NOEXCEPT_IF(noexcept(__lhs.swap(__rhs)))
785 { __lhs.swap(__rhs); }
787 #if __cpp_deduction_guides >= 201606
788 template<typename _InputIterator, typename _ValT
789 = typename iterator_traits<_InputIterator>::value_type,
790 typename _Allocator = allocator<_ValT>,
791 typename = _RequireInputIter<_InputIterator>,
792 typename = _RequireAllocator<_Allocator>>
793 vector(_InputIterator, _InputIterator, _Allocator = _Allocator())
794 -> vector<_ValT, _Allocator>;
797 } // namespace __debug
799 _GLIBCXX_BEGIN_NAMESPACE_VERSION
801 #if __cplusplus >= 201103L
803 /// std::hash specialization for vector<bool>.
804 template<typename _Alloc>
805 struct hash<__debug::vector<bool, _Alloc>>
806 : public __hash_base<size_t, __debug::vector<bool, _Alloc>>
809 operator()(const __debug::vector<bool, _Alloc>& __b) const noexcept
810 { return std::hash<_GLIBCXX_STD_C::vector<bool, _Alloc>>()(__b); }
814 #if __cplusplus >= 201703L
815 namespace __detail::__variant
817 template<typename> struct _Never_valueless_alt; // see <variant>
819 // Provide the strong exception-safety guarantee when emplacing a
820 // vector into a variant, but only if move assignment cannot throw.
821 template<typename _Tp, typename _Alloc>
822 struct _Never_valueless_alt<__debug::vector<_Tp, _Alloc>>
823 : std::is_nothrow_move_assignable<__debug::vector<_Tp, _Alloc>>
825 } // namespace __detail::__variant
828 _GLIBCXX_END_NAMESPACE_VERSION
831 namespace __gnu_debug
833 template<typename _Tp, typename _Alloc>
834 struct _Is_contiguous_sequence<std::__debug::vector<_Tp, _Alloc> >
838 template<typename _Alloc>
839 struct _Is_contiguous_sequence<std::__debug::vector<bool, _Alloc> >