libstdc++
debug/deque
Go to the documentation of this file.
1// Debugging deque implementation -*- C++ -*-
2
3// Copyright (C) 2003-2024 Free Software Foundation, Inc.
4//
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)
9// any later version.
10
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.
15
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.
19
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/>.
24
25/** @file debug/deque
26 * This file is a GNU debug extension to the Standard C++ Library.
27 */
28
29#ifndef _GLIBCXX_DEBUG_DEQUE
30#define _GLIBCXX_DEBUG_DEQUE 1
31
32#ifdef _GLIBCXX_SYSHDR
33#pragma GCC system_header
34#endif
35
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
40
41#include <deque>
42#include <debug/safe_sequence.h>
44#include <debug/safe_iterator.h>
45
46namespace std _GLIBCXX_VISIBILITY(default)
47{
48namespace __debug
49{
50 /// Class std::deque with safety/checking/debug instrumentation.
51 template<typename _Tp, typename _Allocator = std::allocator<_Tp> >
52 class deque
54 deque<_Tp, _Allocator>, _Allocator,
55 __gnu_debug::_Safe_sequence>,
56 public _GLIBCXX_STD_C::deque<_Tp, _Allocator>
57 {
58 typedef _GLIBCXX_STD_C::deque<_Tp, _Allocator> _Base;
61
63 typedef typename _Base::iterator _Base_iterator;
65
66 template<typename _ItT, typename _SeqT, typename _CatT>
67 friend class ::__gnu_debug::_Safe_iterator;
68
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.
72 struct _Base_ref
73 {
74 _Base_ref(const _Base& __r) : _M_ref(__r) { }
75
76 const _Base& _M_ref;
77 };
78
79 public:
80 typedef typename _Base::reference reference;
81 typedef typename _Base::const_reference const_reference;
82
87
88 typedef typename _Base::size_type size_type;
89 typedef typename _Base::difference_type difference_type;
90
91 typedef _Tp value_type;
92 typedef _Allocator allocator_type;
93 typedef typename _Base::pointer pointer;
94 typedef typename _Base::const_pointer const_pointer;
97
98 // 23.2.1.1 construct/copy/destroy:
99
100#if __cplusplus < 201103L
101 deque()
102 : _Base() { }
103
104 deque(const deque& __x)
105 : _Base(__x) { }
106
107 ~deque() { }
108#else
109 deque() = default;
110 deque(const deque&) = default;
111 deque(deque&&) = default;
112
113 deque(const deque& __d, const __type_identity_t<_Allocator>& __a)
114 : _Base(__d, __a) { }
115
116 deque(deque&& __d, const __type_identity_t<_Allocator>& __a)
117 : _Safe(std::move(__d)), _Base(std::move(__d), __a) { }
118
120 const allocator_type& __a = allocator_type())
121 : _Base(__l, __a) { }
122
123 ~deque() = default;
124#endif
125
126 explicit
127 deque(const _Allocator& __a)
128 : _Base(__a) { }
129
130#if __cplusplus >= 201103L
131 explicit
132 deque(size_type __n, const _Allocator& __a = _Allocator())
133 : _Base(__n, __a) { }
134
135 deque(size_type __n, const __type_identity_t<_Tp>& __value,
136 const _Allocator& __a = _Allocator())
137 : _Base(__n, __value, __a) { }
138#else
139 explicit
140 deque(size_type __n, const _Tp& __value = _Tp(),
141 const _Allocator& __a = _Allocator())
142 : _Base(__n, __value, __a) { }
143#endif
144
145#if __cplusplus >= 201103L
146 template<class _InputIterator,
147 typename = std::_RequireInputIter<_InputIterator>>
148#else
149 template<class _InputIterator>
150#endif
151 deque(_InputIterator __first, _InputIterator __last,
152 const _Allocator& __a = _Allocator())
154 __glibcxx_check_valid_constructor_range(__first, __last)),
155 __gnu_debug::__base(__last), __a)
156 { }
157
158 deque(_Base_ref __x)
159 : _Base(__x._M_ref) { }
160
161#if __cplusplus >= 201103L
162 deque&
163 operator=(const deque&) = default;
164
165 deque&
166 operator=(deque&&) = default;
167
168 deque&
169 operator=(initializer_list<value_type> __l)
170 {
171 _Base::operator=(__l);
172 this->_M_invalidate_all();
173 return *this;
174 }
175#endif
176
177#if __cplusplus >= 201103L
178 template<class _InputIterator,
179 typename = std::_RequireInputIter<_InputIterator>>
180#else
181 template<class _InputIterator>
182#endif
183 void
184 assign(_InputIterator __first, _InputIterator __last)
185 {
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));
191 else
192 _Base::assign(__first, __last);
193
194 this->_M_invalidate_all();
195 }
196
197 void
198 assign(size_type __n, const _Tp& __t)
199 {
200 _Base::assign(__n, __t);
201 this->_M_invalidate_all();
202 }
203
204#if __cplusplus >= 201103L
205 void
207 {
208 _Base::assign(__l);
209 this->_M_invalidate_all();
210 }
211#endif
212
213 using _Base::get_allocator;
214
215 // iterators:
216 _GLIBCXX_NODISCARD
218 begin() _GLIBCXX_NOEXCEPT
219 { return iterator(_Base::begin(), this); }
220
221 _GLIBCXX_NODISCARD
223 begin() const _GLIBCXX_NOEXCEPT
224 { return const_iterator(_Base::begin(), this); }
225
226 _GLIBCXX_NODISCARD
228 end() _GLIBCXX_NOEXCEPT
229 { return iterator(_Base::end(), this); }
230
231 _GLIBCXX_NODISCARD
233 end() const _GLIBCXX_NOEXCEPT
234 { return const_iterator(_Base::end(), this); }
235
236 _GLIBCXX_NODISCARD
238 rbegin() _GLIBCXX_NOEXCEPT
239 { return reverse_iterator(end()); }
240
241 _GLIBCXX_NODISCARD
243 rbegin() const _GLIBCXX_NOEXCEPT
244 { return const_reverse_iterator(end()); }
245
246 _GLIBCXX_NODISCARD
248 rend() _GLIBCXX_NOEXCEPT
249 { return reverse_iterator(begin()); }
250
251 _GLIBCXX_NODISCARD
253 rend() const _GLIBCXX_NOEXCEPT
254 { return const_reverse_iterator(begin()); }
255
256#if __cplusplus >= 201103L
257 [[__nodiscard__]]
259 cbegin() const noexcept
260 { return const_iterator(_Base::begin(), this); }
261
262 [[__nodiscard__]]
264 cend() const noexcept
265 { return const_iterator(_Base::end(), this); }
266
267 [[__nodiscard__]]
269 crbegin() const noexcept
270 { return const_reverse_iterator(end()); }
271
272 [[__nodiscard__]]
274 crend() const noexcept
275 { return const_reverse_iterator(begin()); }
276#endif
277
278 private:
279 void
280 _M_invalidate_after_nth(difference_type __n)
281 {
283 this->_M_invalidate_if(_After_nth(__n, _Base::begin()));
284 }
285
286 public:
287 // 23.2.1.2 capacity:
288 using _Base::size;
289 using _Base::max_size;
290
291#if __cplusplus >= 201103L
292 void
293 resize(size_type __sz)
294 {
295 bool __invalidate_all = __sz > this->size();
296 if (__sz < this->size())
297 this->_M_invalidate_after_nth(__sz);
298
299 _Base::resize(__sz);
300
301 if (__invalidate_all)
302 this->_M_invalidate_all();
303 }
304
305 void
306 resize(size_type __sz, const _Tp& __c)
307 {
308 bool __invalidate_all = __sz > this->size();
309 if (__sz < this->size())
310 this->_M_invalidate_after_nth(__sz);
311
312 _Base::resize(__sz, __c);
313
314 if (__invalidate_all)
315 this->_M_invalidate_all();
316 }
317#else
318 void
319 resize(size_type __sz, _Tp __c = _Tp())
320 {
321 bool __invalidate_all = __sz > this->size();
322 if (__sz < this->size())
323 this->_M_invalidate_after_nth(__sz);
324
325 _Base::resize(__sz, __c);
326
327 if (__invalidate_all)
328 this->_M_invalidate_all();
329 }
330#endif
331
332#if __cplusplus >= 201103L
333 void
334 shrink_to_fit() noexcept
335 {
336 if (_Base::_M_shrink_to_fit())
337 this->_M_invalidate_all();
338 }
339#endif
340
341 using _Base::empty;
342
343 // element access:
344 _GLIBCXX_NODISCARD
345 reference
346 operator[](size_type __n) _GLIBCXX_NOEXCEPT
347 {
348 __glibcxx_check_subscript(__n);
349 return _Base::operator[](__n);
350 }
351
352 _GLIBCXX_NODISCARD
353 const_reference
354 operator[](size_type __n) const _GLIBCXX_NOEXCEPT
355 {
356 __glibcxx_check_subscript(__n);
357 return _Base::operator[](__n);
358 }
359
360 using _Base::at;
361
362 _GLIBCXX_NODISCARD
363 reference
364 front() _GLIBCXX_NOEXCEPT
365 {
366 __glibcxx_check_nonempty();
367 return _Base::front();
368 }
369
370 _GLIBCXX_NODISCARD
371 const_reference
372 front() const _GLIBCXX_NOEXCEPT
373 {
374 __glibcxx_check_nonempty();
375 return _Base::front();
376 }
377
378 _GLIBCXX_NODISCARD
379 reference
380 back() _GLIBCXX_NOEXCEPT
381 {
382 __glibcxx_check_nonempty();
383 return _Base::back();
384 }
385
386 _GLIBCXX_NODISCARD
387 const_reference
388 back() const _GLIBCXX_NOEXCEPT
389 {
390 __glibcxx_check_nonempty();
391 return _Base::back();
392 }
393
394 // 23.2.1.3 modifiers:
395 void
396 push_front(const _Tp& __x)
397 {
398 _Base::push_front(__x);
399 this->_M_invalidate_all();
400 }
401
402 void
403 push_back(const _Tp& __x)
404 {
405 _Base::push_back(__x);
406 this->_M_invalidate_all();
407 }
408
409#if __cplusplus >= 201103L
410 void
411 push_front(_Tp&& __x)
412 { emplace_front(std::move(__x)); }
413
414 void
415 push_back(_Tp&& __x)
416 { emplace_back(std::move(__x)); }
417
418 template<typename... _Args>
419#if __cplusplus > 201402L
420 reference
421#else
422 void
423#endif
424 emplace_front(_Args&&... __args)
425 {
426 _Base::emplace_front(std::forward<_Args>(__args)...);
427 this->_M_invalidate_all();
428#if __cplusplus > 201402L
429 return front();
430#endif
431 }
432
433 template<typename... _Args>
434#if __cplusplus > 201402L
435 reference
436#else
437 void
438#endif
439 emplace_back(_Args&&... __args)
440 {
441 _Base::emplace_back(std::forward<_Args>(__args)...);
442 this->_M_invalidate_all();
443#if __cplusplus > 201402L
444 return back();
445#endif
446 }
447
448 template<typename... _Args>
450 emplace(const_iterator __position, _Args&&... __args)
451 {
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);
457 }
458#endif
459
461#if __cplusplus >= 201103L
462 insert(const_iterator __position, const _Tp& __x)
463#else
464 insert(iterator __position, const _Tp& __x)
465#endif
466 {
467 __glibcxx_check_insert(__position);
468 _Base_iterator __res = _Base::insert(__position.base(), __x);
469 this->_M_invalidate_all();
470 return iterator(__res, this);
471 }
472
473#if __cplusplus >= 201103L
475 insert(const_iterator __position, _Tp&& __x)
476 { return emplace(__position, std::move(__x)); }
477
479 insert(const_iterator __position, initializer_list<value_type> __l)
480 {
481 __glibcxx_check_insert(__position);
482 _Base_iterator __res = _Base::insert(__position.base(), __l);
483 this->_M_invalidate_all();
484 return iterator(__res, this);
485 }
486#endif
487
488#if __cplusplus >= 201103L
490 insert(const_iterator __position, size_type __n, const _Tp& __x)
491 {
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);
496 }
497#else
498 void
499 insert(iterator __position, size_type __n, const _Tp& __x)
500 {
501 __glibcxx_check_insert(__position);
502 _Base::insert(__position.base(), __n, __x);
503 this->_M_invalidate_all();
504 }
505#endif
506
507#if __cplusplus >= 201103L
508 template<class _InputIterator,
509 typename = std::_RequireInputIter<_InputIterator>>
511 insert(const_iterator __position,
512 _InputIterator __first, _InputIterator __last)
513 {
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));
521 else
522 __res = _Base::insert(__position.base(), __first, __last);
523
524 this->_M_invalidate_all();
525 return iterator(__res, this);
526 }
527#else
528 template<class _InputIterator>
529 void
530 insert(iterator __position,
531 _InputIterator __first, _InputIterator __last)
532 {
534 __glibcxx_check_insert_range(__position, __first, __last, __dist);
535
536 if (__dist.second >= __gnu_debug::__dp_sign)
537 _Base::insert(__position.base(),
538 __gnu_debug::__unsafe(__first),
539 __gnu_debug::__unsafe(__last));
540 else
541 _Base::insert(__position.base(), __first, __last);
542
543 this->_M_invalidate_all();
544 }
545#endif
546
547 void
548 pop_front() _GLIBCXX_NOEXCEPT
549 {
550 __glibcxx_check_nonempty();
551 this->_M_invalidate_if(_Equal(_Base::begin()));
552 _Base::pop_front();
553 }
554
555 void
556 pop_back() _GLIBCXX_NOEXCEPT
557 {
558 __glibcxx_check_nonempty();
559 this->_M_invalidate_if(_Equal(--_Base::end()));
560 _Base::pop_back();
561 }
562
564#if __cplusplus >= 201103L
565 erase(const_iterator __position)
566#else
567 erase(iterator __position)
568#endif
569 {
570 __glibcxx_check_erase(__position);
571#if __cplusplus >= 201103L
572 _Base_const_iterator __victim = __position.base();
573#else
574 _Base_iterator __victim = __position.base();
575#endif
576 if (__victim == _Base::begin() || __victim == _Base::end() - 1)
577 {
578 this->_M_invalidate_if(_Equal(__victim));
579 return iterator(_Base::erase(__victim), this);
580 }
581 else
582 {
583 _Base_iterator __res = _Base::erase(__victim);
584 this->_M_invalidate_all();
585 return iterator(__res, this);
586 }
587 }
588
590#if __cplusplus >= 201103L
591 erase(const_iterator __first, const_iterator __last)
592#else
593 erase(iterator __first, iterator __last)
594#endif
595 {
596 // _GLIBCXX_RESOLVE_LIB_DEFECTS
597 // 151. can't currently clear() empty container
598 __glibcxx_check_erase_range(__first, __last);
599
600 if (__first.base() == __last.base())
601#if __cplusplus >= 201103L
602 return iterator(__first.base()._M_const_cast(), this);
603#else
604 return __first;
605#endif
606 else if (__first.base() == _Base::begin()
607 || __last.base() == _Base::end())
608 {
609 this->_M_detach_singular();
610 for (_Base_const_iterator __position = __first.base();
611 __position != __last.base(); ++__position)
612 {
613 this->_M_invalidate_if(_Equal(__position));
614 }
615 __try
616 {
617 return iterator(_Base::erase(__first.base(), __last.base()),
618 this);
619 }
620 __catch(...)
621 {
622 this->_M_revalidate_singular();
623 __throw_exception_again;
624 }
625 }
626 else
627 {
628 _Base_iterator __res = _Base::erase(__first.base(),
629 __last.base());
630 this->_M_invalidate_all();
631 return iterator(__res, this);
632 }
633 }
634
635 void
636 swap(deque& __x)
637 _GLIBCXX_NOEXCEPT_IF( noexcept(declval<_Base&>().swap(__x)) )
638 {
639 _Safe::_M_swap(__x);
640 _Base::swap(__x);
641 }
642
643 void
644 clear() _GLIBCXX_NOEXCEPT
645 {
646 _Base::clear();
647 this->_M_invalidate_all();
648 }
649
650 _Base&
651 _M_base() _GLIBCXX_NOEXCEPT { return *this; }
652
653 const _Base&
654 _M_base() const _GLIBCXX_NOEXCEPT { return *this; }
655 };
656
657#if __cpp_deduction_guides >= 201606
658 template<typename _InputIterator, typename _ValT
660 typename _Allocator = allocator<_ValT>,
661 typename = _RequireInputIter<_InputIterator>,
662 typename = _RequireAllocator<_Allocator>>
663 deque(_InputIterator, _InputIterator, _Allocator = _Allocator())
665
666 template<typename _Tp, typename _Allocator = allocator<_Tp>,
667 typename = _RequireAllocator<_Allocator>>
668 deque(size_t, _Tp, _Allocator = _Allocator())
670#endif
671
672 template<typename _Tp, typename _Alloc>
673 inline bool
674 operator==(const deque<_Tp, _Alloc>& __lhs,
675 const deque<_Tp, _Alloc>& __rhs)
676 { return __lhs._M_base() == __rhs._M_base(); }
677
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(); }
683#else
684 template<typename _Tp, typename _Alloc>
685 inline bool
686 operator!=(const deque<_Tp, _Alloc>& __lhs,
687 const deque<_Tp, _Alloc>& __rhs)
688 { return __lhs._M_base() != __rhs._M_base(); }
689
690 template<typename _Tp, typename _Alloc>
691 inline bool
692 operator<(const deque<_Tp, _Alloc>& __lhs,
693 const deque<_Tp, _Alloc>& __rhs)
694 { return __lhs._M_base() < __rhs._M_base(); }
695
696 template<typename _Tp, typename _Alloc>
697 inline bool
698 operator<=(const deque<_Tp, _Alloc>& __lhs,
699 const deque<_Tp, _Alloc>& __rhs)
700 { return __lhs._M_base() <= __rhs._M_base(); }
701
702 template<typename _Tp, typename _Alloc>
703 inline bool
704 operator>=(const deque<_Tp, _Alloc>& __lhs,
705 const deque<_Tp, _Alloc>& __rhs)
706 { return __lhs._M_base() >= __rhs._M_base(); }
707
708 template<typename _Tp, typename _Alloc>
709 inline bool
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
714
715 template<typename _Tp, typename _Alloc>
716 inline void
717 swap(deque<_Tp, _Alloc>& __lhs, deque<_Tp, _Alloc>& __rhs)
718 _GLIBCXX_NOEXCEPT_IF(noexcept(__lhs.swap(__rhs)))
719 { __lhs.swap(__rhs); }
720
721} // namespace __debug
722} // namespace std
723
724#endif
#define __glibcxx_check_insert(_Position)
Definition macros.h:143
#define __glibcxx_check_erase_range(_First, _Last)
Definition macros.h:245
#define __glibcxx_check_erase(_Position)
Definition macros.h:209
#define __glibcxx_check_insert_range(_Position, _First, _Last, _Dist)
Definition macros.h:177
constexpr bool operator<=(const duration< _Rep1, _Period1 > &__lhs, const duration< _Rep2, _Period2 > &__rhs)
Definition chrono.h:859
constexpr bool operator>=(const duration< _Rep1, _Period1 > &__lhs, const duration< _Rep2, _Period2 > &__rhs)
Definition chrono.h:873
constexpr bool operator<(const duration< _Rep1, _Period1 > &__lhs, const duration< _Rep2, _Period2 > &__rhs)
Definition chrono.h:826
constexpr bool operator>(const duration< _Rep1, _Period1 > &__lhs, const duration< _Rep2, _Period2 > &__rhs)
Definition chrono.h:866
constexpr std::remove_reference< _Tp >::type && move(_Tp &&__t) noexcept
Convert a value to an rvalue.
Definition move.h:127
ISO C++ entities toplevel namespace is std.
constexpr auto size(const _Container &__cont) noexcept(noexcept(__cont.size())) -> decltype(__cont.size())
Return the size of a container.
constexpr _Iterator __base(_Iterator __it)
initializer_list
The standard allocator, as per C++03 [20.4.1].
Definition allocator.h:134
Safe iterator wrapper.
constexpr _Iterator & base() noexcept
Return the underlying iterator.
A standard container using fixed-size memory allocation and constant-time manipulation of elements at...
Definition stl_deque.h:789
Struct holding two objects of arbitrary type.
Definition stl_pair.h:286
_T2 second
The second member.
Definition stl_pair.h:291
Traits class for iterators.
Base class for constructing a safe sequence type that tracks iterators that reference it.
Safe class dealing with some allocator dependent operations.
Class std::deque with safety/checking/debug instrumentation.
Definition debug/deque:57