1// Debugging deque implementation -*- C++ -*-
3// Copyright (C) 2003-2024 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/>.
26 * This file is a GNU debug extension to the Standard C++ Library.
29#ifndef _GLIBCXX_DEBUG_DEQUE
30#define _GLIBCXX_DEBUG_DEQUE 1
33#pragma GCC system_header
36#include <bits/c++config.h>
37namespace std _GLIBCXX_VISIBILITY(default) { namespace __debug {
38 template<typename _Tp, typename _Allocator> class deque;
39} } // namespace std::__debug
42#include <debug/safe_sequence.h>
43#include <debug/safe_container.h>
44#include <debug/safe_iterator.h>
46namespace std _GLIBCXX_VISIBILITY(default)
50 /// Class std::deque with safety/checking/debug instrumentation.
51 template<typename _Tp, typename _Allocator = std::allocator<_Tp> >
53 : public __gnu_debug::_Safe_container<
54 deque<_Tp, _Allocator>, _Allocator,
55 __gnu_debug::_Safe_sequence>,
56 public _GLIBCXX_STD_C::deque<_Tp, _Allocator>
58 typedef _GLIBCXX_STD_C::deque<_Tp, _Allocator> _Base;
59 typedef __gnu_debug::_Safe_container<
60 deque, _Allocator, __gnu_debug::_Safe_sequence> _Safe;
62 typedef typename _Base::const_iterator _Base_const_iterator;
63 typedef typename _Base::iterator _Base_iterator;
64 typedef __gnu_debug::_Equal_to<_Base_const_iterator> _Equal;
66 template<typename _ItT, typename _SeqT, typename _CatT>
67 friend class ::__gnu_debug::_Safe_iterator;
69 // Reference wrapper for base class. Disambiguates deque(const _Base&)
70 // from copy constructor by requiring a user-defined conversion.
71 // See PR libstdc++/90102.
74 _Base_ref(const _Base& __r) : _M_ref(__r) { }
80 typedef typename _Base::reference reference;
81 typedef typename _Base::const_reference const_reference;
83 typedef __gnu_debug::_Safe_iterator<_Base_iterator, deque>
85 typedef __gnu_debug::_Safe_iterator<_Base_const_iterator, deque>
88 typedef typename _Base::size_type size_type;
89 typedef typename _Base::difference_type difference_type;
91 typedef _Tp value_type;
92 typedef _Allocator allocator_type;
93 typedef typename _Base::pointer pointer;
94 typedef typename _Base::const_pointer const_pointer;
95 typedef std::reverse_iterator<iterator> reverse_iterator;
96 typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
98 // 23.2.1.1 construct/copy/destroy:
100#if __cplusplus < 201103L
104 deque(const deque& __x)
110 deque(const deque&) = default;
111 deque(deque&&) = default;
113 deque(const deque& __d, const __type_identity_t<_Allocator>& __a)
114 : _Base(__d, __a) { }
116 deque(deque&& __d, const __type_identity_t<_Allocator>& __a)
117 : _Safe(std::move(__d)), _Base(std::move(__d), __a) { }
119 deque(initializer_list<value_type> __l,
120 const allocator_type& __a = allocator_type())
121 : _Base(__l, __a) { }
127 deque(const _Allocator& __a)
130#if __cplusplus >= 201103L
132 deque(size_type __n, const _Allocator& __a = _Allocator())
133 : _Base(__n, __a) { }
135 deque(size_type __n, const __type_identity_t<_Tp>& __value,
136 const _Allocator& __a = _Allocator())
137 : _Base(__n, __value, __a) { }
140 deque(size_type __n, const _Tp& __value = _Tp(),
141 const _Allocator& __a = _Allocator())
142 : _Base(__n, __value, __a) { }
145#if __cplusplus >= 201103L
146 template<class _InputIterator,
147 typename = std::_RequireInputIter<_InputIterator>>
149 template<class _InputIterator>
151 deque(_InputIterator __first, _InputIterator __last,
152 const _Allocator& __a = _Allocator())
153 : _Base(__gnu_debug::__base(
154 __glibcxx_check_valid_constructor_range(__first, __last)),
155 __gnu_debug::__base(__last), __a)
159 : _Base(__x._M_ref) { }
161#if __cplusplus >= 201103L
163 operator=(const deque&) = default;
166 operator=(deque&&) = default;
169 operator=(initializer_list<value_type> __l)
171 _Base::operator=(__l);
172 this->_M_invalidate_all();
177#if __cplusplus >= 201103L
178 template<class _InputIterator,
179 typename = std::_RequireInputIter<_InputIterator>>
181 template<class _InputIterator>
184 assign(_InputIterator __first, _InputIterator __last)
186 typename __gnu_debug::_Distance_traits<_InputIterator>::__type __dist;
187 __glibcxx_check_valid_range2(__first, __last, __dist);
188 if (__dist.second >= __gnu_debug::__dp_sign)
189 _Base::assign(__gnu_debug::__unsafe(__first),
190 __gnu_debug::__unsafe(__last));
192 _Base::assign(__first, __last);
194 this->_M_invalidate_all();
198 assign(size_type __n, const _Tp& __t)
200 _Base::assign(__n, __t);
201 this->_M_invalidate_all();
204#if __cplusplus >= 201103L
206 assign(initializer_list<value_type> __l)
209 this->_M_invalidate_all();
213 using _Base::get_allocator;
218 begin() _GLIBCXX_NOEXCEPT
219 { return iterator(_Base::begin(), this); }
223 begin() const _GLIBCXX_NOEXCEPT
224 { return const_iterator(_Base::begin(), this); }
228 end() _GLIBCXX_NOEXCEPT
229 { return iterator(_Base::end(), this); }
233 end() const _GLIBCXX_NOEXCEPT
234 { return const_iterator(_Base::end(), this); }
238 rbegin() _GLIBCXX_NOEXCEPT
239 { return reverse_iterator(end()); }
242 const_reverse_iterator
243 rbegin() const _GLIBCXX_NOEXCEPT
244 { return const_reverse_iterator(end()); }
248 rend() _GLIBCXX_NOEXCEPT
249 { return reverse_iterator(begin()); }
252 const_reverse_iterator
253 rend() const _GLIBCXX_NOEXCEPT
254 { return const_reverse_iterator(begin()); }
256#if __cplusplus >= 201103L
259 cbegin() const noexcept
260 { return const_iterator(_Base::begin(), this); }
264 cend() const noexcept
265 { return const_iterator(_Base::end(), this); }
268 const_reverse_iterator
269 crbegin() const noexcept
270 { return const_reverse_iterator(end()); }
273 const_reverse_iterator
274 crend() const noexcept
275 { return const_reverse_iterator(begin()); }
280 _M_invalidate_after_nth(difference_type __n)
282 typedef __gnu_debug::_After_nth_from<_Base_const_iterator> _After_nth;
283 this->_M_invalidate_if(_After_nth(__n, _Base::begin()));
287 // 23.2.1.2 capacity:
289 using _Base::max_size;
291#if __cplusplus >= 201103L
293 resize(size_type __sz)
295 bool __invalidate_all = __sz > this->size();
296 if (__sz < this->size())
297 this->_M_invalidate_after_nth(__sz);
301 if (__invalidate_all)
302 this->_M_invalidate_all();
306 resize(size_type __sz, const _Tp& __c)
308 bool __invalidate_all = __sz > this->size();
309 if (__sz < this->size())
310 this->_M_invalidate_after_nth(__sz);
312 _Base::resize(__sz, __c);
314 if (__invalidate_all)
315 this->_M_invalidate_all();
319 resize(size_type __sz, _Tp __c = _Tp())
321 bool __invalidate_all = __sz > this->size();
322 if (__sz < this->size())
323 this->_M_invalidate_after_nth(__sz);
325 _Base::resize(__sz, __c);
327 if (__invalidate_all)
328 this->_M_invalidate_all();
332#if __cplusplus >= 201103L
334 shrink_to_fit() noexcept
336 if (_Base::_M_shrink_to_fit())
337 this->_M_invalidate_all();
346 operator[](size_type __n) _GLIBCXX_NOEXCEPT
348 __glibcxx_check_subscript(__n);
349 return _Base::operator[](__n);
354 operator[](size_type __n) const _GLIBCXX_NOEXCEPT
356 __glibcxx_check_subscript(__n);
357 return _Base::operator[](__n);
364 front() _GLIBCXX_NOEXCEPT
366 __glibcxx_check_nonempty();
367 return _Base::front();
372 front() const _GLIBCXX_NOEXCEPT
374 __glibcxx_check_nonempty();
375 return _Base::front();
380 back() _GLIBCXX_NOEXCEPT
382 __glibcxx_check_nonempty();
383 return _Base::back();
388 back() const _GLIBCXX_NOEXCEPT
390 __glibcxx_check_nonempty();
391 return _Base::back();
394 // 23.2.1.3 modifiers:
396 push_front(const _Tp& __x)
398 _Base::push_front(__x);
399 this->_M_invalidate_all();
403 push_back(const _Tp& __x)
405 _Base::push_back(__x);
406 this->_M_invalidate_all();
409#if __cplusplus >= 201103L
411 push_front(_Tp&& __x)
412 { emplace_front(std::move(__x)); }
416 { emplace_back(std::move(__x)); }
418 template<typename... _Args>
419#if __cplusplus > 201402L
424 emplace_front(_Args&&... __args)
426 _Base::emplace_front(std::forward<_Args>(__args)...);
427 this->_M_invalidate_all();
428#if __cplusplus > 201402L
433 template<typename... _Args>
434#if __cplusplus > 201402L
439 emplace_back(_Args&&... __args)
441 _Base::emplace_back(std::forward<_Args>(__args)...);
442 this->_M_invalidate_all();
443#if __cplusplus > 201402L
448 template<typename... _Args>
450 emplace(const_iterator __position, _Args&&... __args)
452 __glibcxx_check_insert(__position);
453 _Base_iterator __res = _Base::emplace(__position.base(),
454 std::forward<_Args>(__args)...);
455 this->_M_invalidate_all();
456 return iterator(__res, this);
461#if __cplusplus >= 201103L
462 insert(const_iterator __position, const _Tp& __x)
464 insert(iterator __position, const _Tp& __x)
467 __glibcxx_check_insert(__position);
468 _Base_iterator __res = _Base::insert(__position.base(), __x);
469 this->_M_invalidate_all();
470 return iterator(__res, this);
473#if __cplusplus >= 201103L
475 insert(const_iterator __position, _Tp&& __x)
476 { return emplace(__position, std::move(__x)); }
479 insert(const_iterator __position, initializer_list<value_type> __l)
481 __glibcxx_check_insert(__position);
482 _Base_iterator __res = _Base::insert(__position.base(), __l);
483 this->_M_invalidate_all();
484 return iterator(__res, this);
488#if __cplusplus >= 201103L
490 insert(const_iterator __position, size_type __n, const _Tp& __x)
492 __glibcxx_check_insert(__position);
493 _Base_iterator __res = _Base::insert(__position.base(), __n, __x);
494 this->_M_invalidate_all();
495 return iterator(__res, this);
499 insert(iterator __position, size_type __n, const _Tp& __x)
501 __glibcxx_check_insert(__position);
502 _Base::insert(__position.base(), __n, __x);
503 this->_M_invalidate_all();
507#if __cplusplus >= 201103L
508 template<class _InputIterator,
509 typename = std::_RequireInputIter<_InputIterator>>
511 insert(const_iterator __position,
512 _InputIterator __first, _InputIterator __last)
514 typename __gnu_debug::_Distance_traits<_InputIterator>::__type __dist;
515 __glibcxx_check_insert_range(__position, __first, __last, __dist);
516 _Base_iterator __res;
517 if (__dist.second >= __gnu_debug::__dp_sign)
518 __res = _Base::insert(__position.base(),
519 __gnu_debug::__unsafe(__first),
520 __gnu_debug::__unsafe(__last));
522 __res = _Base::insert(__position.base(), __first, __last);
524 this->_M_invalidate_all();
525 return iterator(__res, this);
528 template<class _InputIterator>
530 insert(iterator __position,
531 _InputIterator __first, _InputIterator __last)
533 typename __gnu_debug::_Distance_traits<_InputIterator>::__type __dist;
534 __glibcxx_check_insert_range(__position, __first, __last, __dist);
536 if (__dist.second >= __gnu_debug::__dp_sign)
537 _Base::insert(__position.base(),
538 __gnu_debug::__unsafe(__first),
539 __gnu_debug::__unsafe(__last));
541 _Base::insert(__position.base(), __first, __last);
543 this->_M_invalidate_all();
548 pop_front() _GLIBCXX_NOEXCEPT
550 __glibcxx_check_nonempty();
551 this->_M_invalidate_if(_Equal(_Base::begin()));
556 pop_back() _GLIBCXX_NOEXCEPT
558 __glibcxx_check_nonempty();
559 this->_M_invalidate_if(_Equal(--_Base::end()));
564#if __cplusplus >= 201103L
565 erase(const_iterator __position)
567 erase(iterator __position)
570 __glibcxx_check_erase(__position);
571#if __cplusplus >= 201103L
572 _Base_const_iterator __victim = __position.base();
574 _Base_iterator __victim = __position.base();
576 if (__victim == _Base::begin() || __victim == _Base::end() - 1)
578 this->_M_invalidate_if(_Equal(__victim));
579 return iterator(_Base::erase(__victim), this);
583 _Base_iterator __res = _Base::erase(__victim);
584 this->_M_invalidate_all();
585 return iterator(__res, this);
590#if __cplusplus >= 201103L
591 erase(const_iterator __first, const_iterator __last)
593 erase(iterator __first, iterator __last)
596 // _GLIBCXX_RESOLVE_LIB_DEFECTS
597 // 151. can't currently clear() empty container
598 __glibcxx_check_erase_range(__first, __last);
600 if (__first.base() == __last.base())
601#if __cplusplus >= 201103L
602 return iterator(__first.base()._M_const_cast(), this);
606 else if (__first.base() == _Base::begin()
607 || __last.base() == _Base::end())
609 this->_M_detach_singular();
610 for (_Base_const_iterator __position = __first.base();
611 __position != __last.base(); ++__position)
613 this->_M_invalidate_if(_Equal(__position));
617 return iterator(_Base::erase(__first.base(), __last.base()),
622 this->_M_revalidate_singular();
623 __throw_exception_again;
628 _Base_iterator __res = _Base::erase(__first.base(),
630 this->_M_invalidate_all();
631 return iterator(__res, this);
637 _GLIBCXX_NOEXCEPT_IF( noexcept(declval<_Base&>().swap(__x)) )
644 clear() _GLIBCXX_NOEXCEPT
647 this->_M_invalidate_all();
651 _M_base() _GLIBCXX_NOEXCEPT { return *this; }
654 _M_base() const _GLIBCXX_NOEXCEPT { return *this; }
657#if __cpp_deduction_guides >= 201606
658 template<typename _InputIterator, typename _ValT
659 = typename iterator_traits<_InputIterator>::value_type,
660 typename _Allocator = allocator<_ValT>,
661 typename = _RequireInputIter<_InputIterator>,
662 typename = _RequireAllocator<_Allocator>>
663 deque(_InputIterator, _InputIterator, _Allocator = _Allocator())
664 -> deque<_ValT, _Allocator>;
666 template<typename _Tp, typename _Allocator = allocator<_Tp>,
667 typename = _RequireAllocator<_Allocator>>
668 deque(size_t, _Tp, _Allocator = _Allocator())
669 -> deque<_Tp, _Allocator>;
672 template<typename _Tp, typename _Alloc>
674 operator==(const deque<_Tp, _Alloc>& __lhs,
675 const deque<_Tp, _Alloc>& __rhs)
676 { return __lhs._M_base() == __rhs._M_base(); }
678#if __cpp_lib_three_way_comparison
679 template<typename _Tp, typename _Alloc>
680 constexpr __detail::__synth3way_t<_Tp>
681 operator<=>(const deque<_Tp, _Alloc>& __x, const deque<_Tp, _Alloc>& __y)
682 { return __x._M_base() <=> __y._M_base(); }
684 template<typename _Tp, typename _Alloc>
686 operator!=(const deque<_Tp, _Alloc>& __lhs,
687 const deque<_Tp, _Alloc>& __rhs)
688 { return __lhs._M_base() != __rhs._M_base(); }
690 template<typename _Tp, typename _Alloc>
692 operator<(const deque<_Tp, _Alloc>& __lhs,
693 const deque<_Tp, _Alloc>& __rhs)
694 { return __lhs._M_base() < __rhs._M_base(); }
696 template<typename _Tp, typename _Alloc>
698 operator<=(const deque<_Tp, _Alloc>& __lhs,
699 const deque<_Tp, _Alloc>& __rhs)
700 { return __lhs._M_base() <= __rhs._M_base(); }
702 template<typename _Tp, typename _Alloc>
704 operator>=(const deque<_Tp, _Alloc>& __lhs,
705 const deque<_Tp, _Alloc>& __rhs)
706 { return __lhs._M_base() >= __rhs._M_base(); }
708 template<typename _Tp, typename _Alloc>
710 operator>(const deque<_Tp, _Alloc>& __lhs,
711 const deque<_Tp, _Alloc>& __rhs)
712 { return __lhs._M_base() > __rhs._M_base(); }
713#endif // three-way comparison
715 template<typename _Tp, typename _Alloc>
717 swap(deque<_Tp, _Alloc>& __lhs, deque<_Tp, _Alloc>& __rhs)
718 _GLIBCXX_NOEXCEPT_IF(noexcept(__lhs.swap(__rhs)))
719 { __lhs.swap(__rhs); }
721} // namespace __debug