libstdc++
debug/deque
Go to the documentation of this file.
1// Debugging deque implementation -*- C++ -*-
2
3// Copyright (C) 2003-2022 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#pragma GCC system_header
33
34#include <bits/c++config.h>
35namespace std _GLIBCXX_VISIBILITY(default) { namespace __debug {
36 template<typename _Tp, typename _Allocator> class deque;
37} } // namespace std::__debug
38
39#include <deque>
40#include <debug/safe_sequence.h>
41#include <debug/safe_container.h>
42#include <debug/safe_iterator.h>
43
44namespace std _GLIBCXX_VISIBILITY(default)
45{
46namespace __debug
47{
48 /// Class std::deque with safety/checking/debug instrumentation.
49 template<typename _Tp, typename _Allocator = std::allocator<_Tp> >
50 class deque
51 : public __gnu_debug::_Safe_container<
52 deque<_Tp, _Allocator>, _Allocator,
53 __gnu_debug::_Safe_sequence>,
54 public _GLIBCXX_STD_C::deque<_Tp, _Allocator>
55 {
56 typedef _GLIBCXX_STD_C::deque<_Tp, _Allocator> _Base;
57 typedef __gnu_debug::_Safe_container<
58 deque, _Allocator, __gnu_debug::_Safe_sequence> _Safe;
59
60 typedef typename _Base::const_iterator _Base_const_iterator;
61 typedef typename _Base::iterator _Base_iterator;
62 typedef __gnu_debug::_Equal_to<_Base_const_iterator> _Equal;
63
64 template<typename _ItT, typename _SeqT, typename _CatT>
65 friend class ::__gnu_debug::_Safe_iterator;
66
67 // Reference wrapper for base class. Disambiguates deque(const _Base&)
68 // from copy constructor by requiring a user-defined conversion.
69 // See PR libstdc++/90102.
70 struct _Base_ref
71 {
72 _Base_ref(const _Base& __r) : _M_ref(__r) { }
73
74 const _Base& _M_ref;
75 };
76
77 public:
78 typedef typename _Base::reference reference;
79 typedef typename _Base::const_reference const_reference;
80
81 typedef __gnu_debug::_Safe_iterator<_Base_iterator, deque>
82 iterator;
83 typedef __gnu_debug::_Safe_iterator<_Base_const_iterator, deque>
84 const_iterator;
85
86 typedef typename _Base::size_type size_type;
87 typedef typename _Base::difference_type difference_type;
88
89 typedef _Tp value_type;
90 typedef _Allocator allocator_type;
91 typedef typename _Base::pointer pointer;
92 typedef typename _Base::const_pointer const_pointer;
93 typedef std::reverse_iterator<iterator> reverse_iterator;
94 typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
95
96 // 23.2.1.1 construct/copy/destroy:
97
98#if __cplusplus < 201103L
99 deque()
100 : _Base() { }
101
102 deque(const deque& __x)
103 : _Base(__x) { }
104
105 ~deque() { }
106#else
107 deque() = default;
108 deque(const deque&) = default;
109 deque(deque&&) = default;
110
111 deque(const deque& __d, const __type_identity_t<_Allocator>& __a)
112 : _Base(__d, __a) { }
113
114 deque(deque&& __d, const __type_identity_t<_Allocator>& __a)
115 : _Safe(std::move(__d)), _Base(std::move(__d), __a) { }
116
117 deque(initializer_list<value_type> __l,
118 const allocator_type& __a = allocator_type())
119 : _Base(__l, __a) { }
120
121 ~deque() = default;
122#endif
123
124 explicit
125 deque(const _Allocator& __a)
126 : _Base(__a) { }
127
128#if __cplusplus >= 201103L
129 explicit
130 deque(size_type __n, const _Allocator& __a = _Allocator())
131 : _Base(__n, __a) { }
132
133 deque(size_type __n, const __type_identity_t<_Tp>& __value,
134 const _Allocator& __a = _Allocator())
135 : _Base(__n, __value, __a) { }
136#else
137 explicit
138 deque(size_type __n, const _Tp& __value = _Tp(),
139 const _Allocator& __a = _Allocator())
140 : _Base(__n, __value, __a) { }
141#endif
142
143#if __cplusplus >= 201103L
144 template<class _InputIterator,
145 typename = std::_RequireInputIter<_InputIterator>>
146#else
147 template<class _InputIterator>
148#endif
149 deque(_InputIterator __first, _InputIterator __last,
150 const _Allocator& __a = _Allocator())
151 : _Base(__gnu_debug::__base(
152 __glibcxx_check_valid_constructor_range(__first, __last)),
153 __gnu_debug::__base(__last), __a)
154 { }
155
156 deque(_Base_ref __x)
157 : _Base(__x._M_ref) { }
158
159#if __cplusplus >= 201103L
160 deque&
161 operator=(const deque&) = default;
162
163 deque&
164 operator=(deque&&) = default;
165
166 deque&
167 operator=(initializer_list<value_type> __l)
168 {
169 _Base::operator=(__l);
170 this->_M_invalidate_all();
171 return *this;
172 }
173#endif
174
175#if __cplusplus >= 201103L
176 template<class _InputIterator,
177 typename = std::_RequireInputIter<_InputIterator>>
178#else
179 template<class _InputIterator>
180#endif
181 void
182 assign(_InputIterator __first, _InputIterator __last)
183 {
184 typename __gnu_debug::_Distance_traits<_InputIterator>::__type __dist;
185 __glibcxx_check_valid_range2(__first, __last, __dist);
186 if (__dist.second >= __gnu_debug::__dp_sign)
187 _Base::assign(__gnu_debug::__unsafe(__first),
188 __gnu_debug::__unsafe(__last));
189 else
190 _Base::assign(__first, __last);
191
192 this->_M_invalidate_all();
193 }
194
195 void
196 assign(size_type __n, const _Tp& __t)
197 {
198 _Base::assign(__n, __t);
199 this->_M_invalidate_all();
200 }
201
202#if __cplusplus >= 201103L
203 void
204 assign(initializer_list<value_type> __l)
205 {
206 _Base::assign(__l);
207 this->_M_invalidate_all();
208 }
209#endif
210
211 using _Base::get_allocator;
212
213 // iterators:
214 _GLIBCXX_NODISCARD
215 iterator
216 begin() _GLIBCXX_NOEXCEPT
217 { return iterator(_Base::begin(), this); }
218
219 _GLIBCXX_NODISCARD
220 const_iterator
221 begin() const _GLIBCXX_NOEXCEPT
222 { return const_iterator(_Base::begin(), this); }
223
224 _GLIBCXX_NODISCARD
225 iterator
226 end() _GLIBCXX_NOEXCEPT
227 { return iterator(_Base::end(), this); }
228
229 _GLIBCXX_NODISCARD
230 const_iterator
231 end() const _GLIBCXX_NOEXCEPT
232 { return const_iterator(_Base::end(), this); }
233
234 _GLIBCXX_NODISCARD
235 reverse_iterator
236 rbegin() _GLIBCXX_NOEXCEPT
237 { return reverse_iterator(end()); }
238
239 _GLIBCXX_NODISCARD
240 const_reverse_iterator
241 rbegin() const _GLIBCXX_NOEXCEPT
242 { return const_reverse_iterator(end()); }
243
244 _GLIBCXX_NODISCARD
245 reverse_iterator
246 rend() _GLIBCXX_NOEXCEPT
247 { return reverse_iterator(begin()); }
248
249 _GLIBCXX_NODISCARD
250 const_reverse_iterator
251 rend() const _GLIBCXX_NOEXCEPT
252 { return const_reverse_iterator(begin()); }
253
254#if __cplusplus >= 201103L
255 [[__nodiscard__]]
256 const_iterator
257 cbegin() const noexcept
258 { return const_iterator(_Base::begin(), this); }
259
260 [[__nodiscard__]]
261 const_iterator
262 cend() const noexcept
263 { return const_iterator(_Base::end(), this); }
264
265 [[__nodiscard__]]
266 const_reverse_iterator
267 crbegin() const noexcept
268 { return const_reverse_iterator(end()); }
269
270 [[__nodiscard__]]
271 const_reverse_iterator
272 crend() const noexcept
273 { return const_reverse_iterator(begin()); }
274#endif
275
276 private:
277 void
278 _M_invalidate_after_nth(difference_type __n)
279 {
280 typedef __gnu_debug::_After_nth_from<_Base_const_iterator> _After_nth;
281 this->_M_invalidate_if(_After_nth(__n, _Base::begin()));
282 }
283
284 public:
285 // 23.2.1.2 capacity:
286 using _Base::size;
287 using _Base::max_size;
288
289#if __cplusplus >= 201103L
290 void
291 resize(size_type __sz)
292 {
293 bool __invalidate_all = __sz > this->size();
294 if (__sz < this->size())
295 this->_M_invalidate_after_nth(__sz);
296
297 _Base::resize(__sz);
298
299 if (__invalidate_all)
300 this->_M_invalidate_all();
301 }
302
303 void
304 resize(size_type __sz, const _Tp& __c)
305 {
306 bool __invalidate_all = __sz > this->size();
307 if (__sz < this->size())
308 this->_M_invalidate_after_nth(__sz);
309
310 _Base::resize(__sz, __c);
311
312 if (__invalidate_all)
313 this->_M_invalidate_all();
314 }
315#else
316 void
317 resize(size_type __sz, _Tp __c = _Tp())
318 {
319 bool __invalidate_all = __sz > this->size();
320 if (__sz < this->size())
321 this->_M_invalidate_after_nth(__sz);
322
323 _Base::resize(__sz, __c);
324
325 if (__invalidate_all)
326 this->_M_invalidate_all();
327 }
328#endif
329
330#if __cplusplus >= 201103L
331 void
332 shrink_to_fit() noexcept
333 {
334 if (_Base::_M_shrink_to_fit())
335 this->_M_invalidate_all();
336 }
337#endif
338
339 using _Base::empty;
340
341 // element access:
342 _GLIBCXX_NODISCARD
343 reference
344 operator[](size_type __n) _GLIBCXX_NOEXCEPT
345 {
346 __glibcxx_check_subscript(__n);
347 return _Base::operator[](__n);
348 }
349
350 _GLIBCXX_NODISCARD
351 const_reference
352 operator[](size_type __n) const _GLIBCXX_NOEXCEPT
353 {
354 __glibcxx_check_subscript(__n);
355 return _Base::operator[](__n);
356 }
357
358 using _Base::at;
359
360 _GLIBCXX_NODISCARD
361 reference
362 front() _GLIBCXX_NOEXCEPT
363 {
364 __glibcxx_check_nonempty();
365 return _Base::front();
366 }
367
368 _GLIBCXX_NODISCARD
369 const_reference
370 front() const _GLIBCXX_NOEXCEPT
371 {
372 __glibcxx_check_nonempty();
373 return _Base::front();
374 }
375
376 _GLIBCXX_NODISCARD
377 reference
378 back() _GLIBCXX_NOEXCEPT
379 {
380 __glibcxx_check_nonempty();
381 return _Base::back();
382 }
383
384 _GLIBCXX_NODISCARD
385 const_reference
386 back() const _GLIBCXX_NOEXCEPT
387 {
388 __glibcxx_check_nonempty();
389 return _Base::back();
390 }
391
392 // 23.2.1.3 modifiers:
393 void
394 push_front(const _Tp& __x)
395 {
396 _Base::push_front(__x);
397 this->_M_invalidate_all();
398 }
399
400 void
401 push_back(const _Tp& __x)
402 {
403 _Base::push_back(__x);
404 this->_M_invalidate_all();
405 }
406
407#if __cplusplus >= 201103L
408 void
409 push_front(_Tp&& __x)
410 { emplace_front(std::move(__x)); }
411
412 void
413 push_back(_Tp&& __x)
414 { emplace_back(std::move(__x)); }
415
416 template<typename... _Args>
417#if __cplusplus > 201402L
418 reference
419#else
420 void
421#endif
422 emplace_front(_Args&&... __args)
423 {
424 _Base::emplace_front(std::forward<_Args>(__args)...);
425 this->_M_invalidate_all();
426#if __cplusplus > 201402L
427 return front();
428#endif
429 }
430
431 template<typename... _Args>
432#if __cplusplus > 201402L
433 reference
434#else
435 void
436#endif
437 emplace_back(_Args&&... __args)
438 {
439 _Base::emplace_back(std::forward<_Args>(__args)...);
440 this->_M_invalidate_all();
441#if __cplusplus > 201402L
442 return back();
443#endif
444 }
445
446 template<typename... _Args>
447 iterator
448 emplace(const_iterator __position, _Args&&... __args)
449 {
450 __glibcxx_check_insert(__position);
451 _Base_iterator __res = _Base::emplace(__position.base(),
452 std::forward<_Args>(__args)...);
453 this->_M_invalidate_all();
454 return iterator(__res, this);
455 }
456#endif
457
458 iterator
459#if __cplusplus >= 201103L
460 insert(const_iterator __position, const _Tp& __x)
461#else
462 insert(iterator __position, const _Tp& __x)
463#endif
464 {
465 __glibcxx_check_insert(__position);
466 _Base_iterator __res = _Base::insert(__position.base(), __x);
467 this->_M_invalidate_all();
468 return iterator(__res, this);
469 }
470
471#if __cplusplus >= 201103L
472 iterator
473 insert(const_iterator __position, _Tp&& __x)
474 { return emplace(__position, std::move(__x)); }
475
476 iterator
477 insert(const_iterator __position, initializer_list<value_type> __l)
478 {
479 __glibcxx_check_insert(__position);
480 _Base_iterator __res = _Base::insert(__position.base(), __l);
481 this->_M_invalidate_all();
482 return iterator(__res, this);
483 }
484#endif
485
486#if __cplusplus >= 201103L
487 iterator
488 insert(const_iterator __position, size_type __n, const _Tp& __x)
489 {
490 __glibcxx_check_insert(__position);
491 _Base_iterator __res = _Base::insert(__position.base(), __n, __x);
492 this->_M_invalidate_all();
493 return iterator(__res, this);
494 }
495#else
496 void
497 insert(iterator __position, size_type __n, const _Tp& __x)
498 {
499 __glibcxx_check_insert(__position);
500 _Base::insert(__position.base(), __n, __x);
501 this->_M_invalidate_all();
502 }
503#endif
504
505#if __cplusplus >= 201103L
506 template<class _InputIterator,
507 typename = std::_RequireInputIter<_InputIterator>>
508 iterator
509 insert(const_iterator __position,
510 _InputIterator __first, _InputIterator __last)
511 {
512 typename __gnu_debug::_Distance_traits<_InputIterator>::__type __dist;
513 __glibcxx_check_insert_range(__position, __first, __last, __dist);
514 _Base_iterator __res;
515 if (__dist.second >= __gnu_debug::__dp_sign)
516 __res = _Base::insert(__position.base(),
517 __gnu_debug::__unsafe(__first),
518 __gnu_debug::__unsafe(__last));
519 else
520 __res = _Base::insert(__position.base(), __first, __last);
521
522 this->_M_invalidate_all();
523 return iterator(__res, this);
524 }
525#else
526 template<class _InputIterator>
527 void
528 insert(iterator __position,
529 _InputIterator __first, _InputIterator __last)
530 {
531 typename __gnu_debug::_Distance_traits<_InputIterator>::__type __dist;
532 __glibcxx_check_insert_range(__position, __first, __last, __dist);
533
534 if (__dist.second >= __gnu_debug::__dp_sign)
535 _Base::insert(__position.base(),
536 __gnu_debug::__unsafe(__first),
537 __gnu_debug::__unsafe(__last));
538 else
539 _Base::insert(__position.base(), __first, __last);
540
541 this->_M_invalidate_all();
542 }
543#endif
544
545 void
546 pop_front() _GLIBCXX_NOEXCEPT
547 {
548 __glibcxx_check_nonempty();
549 this->_M_invalidate_if(_Equal(_Base::begin()));
550 _Base::pop_front();
551 }
552
553 void
554 pop_back() _GLIBCXX_NOEXCEPT
555 {
556 __glibcxx_check_nonempty();
557 this->_M_invalidate_if(_Equal(--_Base::end()));
558 _Base::pop_back();
559 }
560
561 iterator
562#if __cplusplus >= 201103L
563 erase(const_iterator __position)
564#else
565 erase(iterator __position)
566#endif
567 {
568 __glibcxx_check_erase(__position);
569#if __cplusplus >= 201103L
570 _Base_const_iterator __victim = __position.base();
571#else
572 _Base_iterator __victim = __position.base();
573#endif
574 if (__victim == _Base::begin() || __victim == _Base::end() - 1)
575 {
576 this->_M_invalidate_if(_Equal(__victim));
577 return iterator(_Base::erase(__victim), this);
578 }
579 else
580 {
581 _Base_iterator __res = _Base::erase(__victim);
582 this->_M_invalidate_all();
583 return iterator(__res, this);
584 }
585 }
586
587 iterator
588#if __cplusplus >= 201103L
589 erase(const_iterator __first, const_iterator __last)
590#else
591 erase(iterator __first, iterator __last)
592#endif
593 {
594 // _GLIBCXX_RESOLVE_LIB_DEFECTS
595 // 151. can't currently clear() empty container
596 __glibcxx_check_erase_range(__first, __last);
597
598 if (__first.base() == __last.base())
599#if __cplusplus >= 201103L
600 return iterator(__first.base()._M_const_cast(), this);
601#else
602 return __first;
603#endif
604 else if (__first.base() == _Base::begin()
605 || __last.base() == _Base::end())
606 {
607 this->_M_detach_singular();
608 for (_Base_const_iterator __position = __first.base();
609 __position != __last.base(); ++__position)
610 {
611 this->_M_invalidate_if(_Equal(__position));
612 }
613 __try
614 {
615 return iterator(_Base::erase(__first.base(), __last.base()),
616 this);
617 }
618 __catch(...)
619 {
620 this->_M_revalidate_singular();
621 __throw_exception_again;
622 }
623 }
624 else
625 {
626 _Base_iterator __res = _Base::erase(__first.base(),
627 __last.base());
628 this->_M_invalidate_all();
629 return iterator(__res, this);
630 }
631 }
632
633 void
634 swap(deque& __x)
635 _GLIBCXX_NOEXCEPT_IF( noexcept(declval<_Base&>().swap(__x)) )
636 {
637 _Safe::_M_swap(__x);
638 _Base::swap(__x);
639 }
640
641 void
642 clear() _GLIBCXX_NOEXCEPT
643 {
644 _Base::clear();
645 this->_M_invalidate_all();
646 }
647
648 _Base&
649 _M_base() _GLIBCXX_NOEXCEPT { return *this; }
650
651 const _Base&
652 _M_base() const _GLIBCXX_NOEXCEPT { return *this; }
653 };
654
655#if __cpp_deduction_guides >= 201606
656 template<typename _InputIterator, typename _ValT
657 = typename iterator_traits<_InputIterator>::value_type,
658 typename _Allocator = allocator<_ValT>,
659 typename = _RequireInputIter<_InputIterator>,
660 typename = _RequireAllocator<_Allocator>>
661 deque(_InputIterator, _InputIterator, _Allocator = _Allocator())
662 -> deque<_ValT, _Allocator>;
663
664 template<typename _Tp, typename _Allocator = allocator<_Tp>,
665 typename = _RequireAllocator<_Allocator>>
666 deque(size_t, _Tp, _Allocator = _Allocator())
667 -> deque<_Tp, _Allocator>;
668#endif
669
670 template<typename _Tp, typename _Alloc>
671 inline bool
672 operator==(const deque<_Tp, _Alloc>& __lhs,
673 const deque<_Tp, _Alloc>& __rhs)
674 { return __lhs._M_base() == __rhs._M_base(); }
675
676#if __cpp_lib_three_way_comparison
677 template<typename _Tp, typename _Alloc>
678 constexpr __detail::__synth3way_t<_Tp>
679 operator<=>(const deque<_Tp, _Alloc>& __x, const deque<_Tp, _Alloc>& __y)
680 { return __x._M_base() <=> __y._M_base(); }
681#else
682 template<typename _Tp, typename _Alloc>
683 inline bool
684 operator!=(const deque<_Tp, _Alloc>& __lhs,
685 const deque<_Tp, _Alloc>& __rhs)
686 { return __lhs._M_base() != __rhs._M_base(); }
687
688 template<typename _Tp, typename _Alloc>
689 inline bool
690 operator<(const deque<_Tp, _Alloc>& __lhs,
691 const deque<_Tp, _Alloc>& __rhs)
692 { return __lhs._M_base() < __rhs._M_base(); }
693
694 template<typename _Tp, typename _Alloc>
695 inline bool
696 operator<=(const deque<_Tp, _Alloc>& __lhs,
697 const deque<_Tp, _Alloc>& __rhs)
698 { return __lhs._M_base() <= __rhs._M_base(); }
699
700 template<typename _Tp, typename _Alloc>
701 inline bool
702 operator>=(const deque<_Tp, _Alloc>& __lhs,
703 const deque<_Tp, _Alloc>& __rhs)
704 { return __lhs._M_base() >= __rhs._M_base(); }
705
706 template<typename _Tp, typename _Alloc>
707 inline bool
708 operator>(const deque<_Tp, _Alloc>& __lhs,
709 const deque<_Tp, _Alloc>& __rhs)
710 { return __lhs._M_base() > __rhs._M_base(); }
711#endif // three-way comparison
712
713 template<typename _Tp, typename _Alloc>
714 inline void
715 swap(deque<_Tp, _Alloc>& __lhs, deque<_Tp, _Alloc>& __rhs)
716 _GLIBCXX_NOEXCEPT_IF(noexcept(__lhs.swap(__rhs)))
717 { __lhs.swap(__rhs); }
718
719} // namespace __debug
720} // namespace std
721
722#endif