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>
35 namespace 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 
44 namespace std _GLIBCXX_VISIBILITY(default)
45 {
46 namespace __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