libstdc++
debug/deque
Go to the documentation of this file.
1 // Debugging deque implementation -*- C++ -*-
2 
3 // Copyright (C) 2003-2021 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 _Allocator& __a)
112  : _Base(__d, __a) { }
113 
114  deque(deque&& __d, const _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& __x)
162  {
163  this->_M_safe() = __x;
164  _M_base() = __x;
165  return *this;
166  }
167 #else
168  deque&
169  operator=(const deque&) = default;
170 
171  deque&
172  operator=(deque&&) = default;
173 
174  deque&
175  operator=(initializer_list<value_type> __l)
176  {
177  _M_base() = __l;
178  this->_M_invalidate_all();
179  return *this;
180  }
181 #endif
182 
183 #if __cplusplus >= 201103L
184  template<class _InputIterator,
185  typename = std::_RequireInputIter<_InputIterator>>
186 #else
187  template<class _InputIterator>
188 #endif
189  void
190  assign(_InputIterator __first, _InputIterator __last)
191  {
192  typename __gnu_debug::_Distance_traits<_InputIterator>::__type __dist;
193  __glibcxx_check_valid_range2(__first, __last, __dist);
194  if (__dist.second >= __gnu_debug::__dp_sign)
195  _Base::assign(__gnu_debug::__unsafe(__first),
196  __gnu_debug::__unsafe(__last));
197  else
198  _Base::assign(__first, __last);
199 
200  this->_M_invalidate_all();
201  }
202 
203  void
204  assign(size_type __n, const _Tp& __t)
205  {
206  _Base::assign(__n, __t);
207  this->_M_invalidate_all();
208  }
209 
210 #if __cplusplus >= 201103L
211  void
212  assign(initializer_list<value_type> __l)
213  {
214  _Base::assign(__l);
215  this->_M_invalidate_all();
216  }
217 #endif
218 
219  using _Base::get_allocator;
220 
221  // iterators:
222  iterator
223  begin() _GLIBCXX_NOEXCEPT
224  { return iterator(_Base::begin(), this); }
225 
226  const_iterator
227  begin() const _GLIBCXX_NOEXCEPT
228  { return const_iterator(_Base::begin(), this); }
229 
230  iterator
231  end() _GLIBCXX_NOEXCEPT
232  { return iterator(_Base::end(), this); }
233 
234  const_iterator
235  end() const _GLIBCXX_NOEXCEPT
236  { return const_iterator(_Base::end(), this); }
237 
238  reverse_iterator
239  rbegin() _GLIBCXX_NOEXCEPT
240  { return reverse_iterator(end()); }
241 
242  const_reverse_iterator
243  rbegin() const _GLIBCXX_NOEXCEPT
244  { return const_reverse_iterator(end()); }
245 
246  reverse_iterator
247  rend() _GLIBCXX_NOEXCEPT
248  { return reverse_iterator(begin()); }
249 
250  const_reverse_iterator
251  rend() const _GLIBCXX_NOEXCEPT
252  { return const_reverse_iterator(begin()); }
253 
254 #if __cplusplus >= 201103L
255  const_iterator
256  cbegin() const noexcept
257  { return const_iterator(_Base::begin(), this); }
258 
259  const_iterator
260  cend() const noexcept
261  { return const_iterator(_Base::end(), this); }
262 
263  const_reverse_iterator
264  crbegin() const noexcept
265  { return const_reverse_iterator(end()); }
266 
267  const_reverse_iterator
268  crend() const noexcept
269  { return const_reverse_iterator(begin()); }
270 #endif
271 
272  private:
273  void
274  _M_invalidate_after_nth(difference_type __n)
275  {
276  typedef __gnu_debug::_After_nth_from<_Base_const_iterator> _After_nth;
277  this->_M_invalidate_if(_After_nth(__n, _Base::begin()));
278  }
279 
280  public:
281  // 23.2.1.2 capacity:
282  using _Base::size;
283  using _Base::max_size;
284 
285 #if __cplusplus >= 201103L
286  void
287  resize(size_type __sz)
288  {
289  bool __invalidate_all = __sz > this->size();
290  if (__sz < this->size())
291  this->_M_invalidate_after_nth(__sz);
292 
293  _Base::resize(__sz);
294 
295  if (__invalidate_all)
296  this->_M_invalidate_all();
297  }
298 
299  void
300  resize(size_type __sz, const _Tp& __c)
301  {
302  bool __invalidate_all = __sz > this->size();
303  if (__sz < this->size())
304  this->_M_invalidate_after_nth(__sz);
305 
306  _Base::resize(__sz, __c);
307 
308  if (__invalidate_all)
309  this->_M_invalidate_all();
310  }
311 #else
312  void
313  resize(size_type __sz, _Tp __c = _Tp())
314  {
315  bool __invalidate_all = __sz > this->size();
316  if (__sz < this->size())
317  this->_M_invalidate_after_nth(__sz);
318 
319  _Base::resize(__sz, __c);
320 
321  if (__invalidate_all)
322  this->_M_invalidate_all();
323  }
324 #endif
325 
326 #if __cplusplus >= 201103L
327  void
328  shrink_to_fit() noexcept
329  {
330  if (_Base::_M_shrink_to_fit())
331  this->_M_invalidate_all();
332  }
333 #endif
334 
335  using _Base::empty;
336 
337  // element access:
338  reference
339  operator[](size_type __n) _GLIBCXX_NOEXCEPT
340  {
341  __glibcxx_check_subscript(__n);
342  return _M_base()[__n];
343  }
344 
345  const_reference
346  operator[](size_type __n) const _GLIBCXX_NOEXCEPT
347  {
348  __glibcxx_check_subscript(__n);
349  return _M_base()[__n];
350  }
351 
352  using _Base::at;
353 
354  reference
355  front() _GLIBCXX_NOEXCEPT
356  {
357  __glibcxx_check_nonempty();
358  return _Base::front();
359  }
360 
361  const_reference
362  front() const _GLIBCXX_NOEXCEPT
363  {
364  __glibcxx_check_nonempty();
365  return _Base::front();
366  }
367 
368  reference
369  back() _GLIBCXX_NOEXCEPT
370  {
371  __glibcxx_check_nonempty();
372  return _Base::back();
373  }
374 
375  const_reference
376  back() const _GLIBCXX_NOEXCEPT
377  {
378  __glibcxx_check_nonempty();
379  return _Base::back();
380  }
381 
382  // 23.2.1.3 modifiers:
383  void
384  push_front(const _Tp& __x)
385  {
386  _Base::push_front(__x);
387  this->_M_invalidate_all();
388  }
389 
390  void
391  push_back(const _Tp& __x)
392  {
393  _Base::push_back(__x);
394  this->_M_invalidate_all();
395  }
396 
397 #if __cplusplus >= 201103L
398  void
399  push_front(_Tp&& __x)
400  { emplace_front(std::move(__x)); }
401 
402  void
403  push_back(_Tp&& __x)
404  { emplace_back(std::move(__x)); }
405 
406  template<typename... _Args>
407 #if __cplusplus > 201402L
408  reference
409 #else
410  void
411 #endif
412  emplace_front(_Args&&... __args)
413  {
414  _Base::emplace_front(std::forward<_Args>(__args)...);
415  this->_M_invalidate_all();
416 #if __cplusplus > 201402L
417  return front();
418 #endif
419  }
420 
421  template<typename... _Args>
422 #if __cplusplus > 201402L
423  reference
424 #else
425  void
426 #endif
427  emplace_back(_Args&&... __args)
428  {
429  _Base::emplace_back(std::forward<_Args>(__args)...);
430  this->_M_invalidate_all();
431 #if __cplusplus > 201402L
432  return back();
433 #endif
434  }
435 
436  template<typename... _Args>
437  iterator
438  emplace(const_iterator __position, _Args&&... __args)
439  {
440  __glibcxx_check_insert(__position);
441  _Base_iterator __res = _Base::emplace(__position.base(),
442  std::forward<_Args>(__args)...);
443  this->_M_invalidate_all();
444  return iterator(__res, this);
445  }
446 #endif
447 
448  iterator
449 #if __cplusplus >= 201103L
450  insert(const_iterator __position, const _Tp& __x)
451 #else
452  insert(iterator __position, const _Tp& __x)
453 #endif
454  {
455  __glibcxx_check_insert(__position);
456  _Base_iterator __res = _Base::insert(__position.base(), __x);
457  this->_M_invalidate_all();
458  return iterator(__res, this);
459  }
460 
461 #if __cplusplus >= 201103L
462  iterator
463  insert(const_iterator __position, _Tp&& __x)
464  { return emplace(__position, std::move(__x)); }
465 
466  iterator
467  insert(const_iterator __position, initializer_list<value_type> __l)
468  {
469  __glibcxx_check_insert(__position);
470  _Base_iterator __res = _Base::insert(__position.base(), __l);
471  this->_M_invalidate_all();
472  return iterator(__res, this);
473  }
474 #endif
475 
476 #if __cplusplus >= 201103L
477  iterator
478  insert(const_iterator __position, size_type __n, const _Tp& __x)
479  {
480  __glibcxx_check_insert(__position);
481  _Base_iterator __res = _Base::insert(__position.base(), __n, __x);
482  this->_M_invalidate_all();
483  return iterator(__res, this);
484  }
485 #else
486  void
487  insert(iterator __position, size_type __n, const _Tp& __x)
488  {
489  __glibcxx_check_insert(__position);
490  _Base::insert(__position.base(), __n, __x);
491  this->_M_invalidate_all();
492  }
493 #endif
494 
495 #if __cplusplus >= 201103L
496  template<class _InputIterator,
497  typename = std::_RequireInputIter<_InputIterator>>
498  iterator
499  insert(const_iterator __position,
500  _InputIterator __first, _InputIterator __last)
501  {
502  typename __gnu_debug::_Distance_traits<_InputIterator>::__type __dist;
503  __glibcxx_check_insert_range(__position, __first, __last, __dist);
504  _Base_iterator __res;
505  if (__dist.second >= __gnu_debug::__dp_sign)
506  __res = _Base::insert(__position.base(),
507  __gnu_debug::__unsafe(__first),
508  __gnu_debug::__unsafe(__last));
509  else
510  __res = _Base::insert(__position.base(), __first, __last);
511 
512  this->_M_invalidate_all();
513  return iterator(__res, this);
514  }
515 #else
516  template<class _InputIterator>
517  void
518  insert(iterator __position,
519  _InputIterator __first, _InputIterator __last)
520  {
521  typename __gnu_debug::_Distance_traits<_InputIterator>::__type __dist;
522  __glibcxx_check_insert_range(__position, __first, __last, __dist);
523 
524  if (__dist.second >= __gnu_debug::__dp_sign)
525  _Base::insert(__position.base(),
526  __gnu_debug::__unsafe(__first),
527  __gnu_debug::__unsafe(__last));
528  else
529  _Base::insert(__position.base(), __first, __last);
530 
531  this->_M_invalidate_all();
532  }
533 #endif
534 
535  void
536  pop_front() _GLIBCXX_NOEXCEPT
537  {
538  __glibcxx_check_nonempty();
539  this->_M_invalidate_if(_Equal(_Base::begin()));
540  _Base::pop_front();
541  }
542 
543  void
544  pop_back() _GLIBCXX_NOEXCEPT
545  {
546  __glibcxx_check_nonempty();
547  this->_M_invalidate_if(_Equal(--_Base::end()));
548  _Base::pop_back();
549  }
550 
551  iterator
552 #if __cplusplus >= 201103L
553  erase(const_iterator __position)
554 #else
555  erase(iterator __position)
556 #endif
557  {
558  __glibcxx_check_erase(__position);
559 #if __cplusplus >= 201103L
560  _Base_const_iterator __victim = __position.base();
561 #else
562  _Base_iterator __victim = __position.base();
563 #endif
564  if (__victim == _Base::begin() || __victim == _Base::end() - 1)
565  {
566  this->_M_invalidate_if(_Equal(__victim));
567  return iterator(_Base::erase(__victim), this);
568  }
569  else
570  {
571  _Base_iterator __res = _Base::erase(__victim);
572  this->_M_invalidate_all();
573  return iterator(__res, this);
574  }
575  }
576 
577  iterator
578 #if __cplusplus >= 201103L
579  erase(const_iterator __first, const_iterator __last)
580 #else
581  erase(iterator __first, iterator __last)
582 #endif
583  {
584  // _GLIBCXX_RESOLVE_LIB_DEFECTS
585  // 151. can't currently clear() empty container
586  __glibcxx_check_erase_range(__first, __last);
587 
588  if (__first.base() == __last.base())
589 #if __cplusplus >= 201103L
590  return iterator(__first.base()._M_const_cast(), this);
591 #else
592  return __first;
593 #endif
594  else if (__first.base() == _Base::begin()
595  || __last.base() == _Base::end())
596  {
597  this->_M_detach_singular();
598  for (_Base_const_iterator __position = __first.base();
599  __position != __last.base(); ++__position)
600  {
601  this->_M_invalidate_if(_Equal(__position));
602  }
603  __try
604  {
605  return iterator(_Base::erase(__first.base(), __last.base()),
606  this);
607  }
608  __catch(...)
609  {
610  this->_M_revalidate_singular();
611  __throw_exception_again;
612  }
613  }
614  else
615  {
616  _Base_iterator __res = _Base::erase(__first.base(),
617  __last.base());
618  this->_M_invalidate_all();
619  return iterator(__res, this);
620  }
621  }
622 
623  void
624  swap(deque& __x)
625  _GLIBCXX_NOEXCEPT_IF( noexcept(declval<_Base&>().swap(__x)) )
626  {
627  _Safe::_M_swap(__x);
628  _Base::swap(__x);
629  }
630 
631  void
632  clear() _GLIBCXX_NOEXCEPT
633  {
634  _Base::clear();
635  this->_M_invalidate_all();
636  }
637 
638  _Base&
639  _M_base() _GLIBCXX_NOEXCEPT { return *this; }
640 
641  const _Base&
642  _M_base() const _GLIBCXX_NOEXCEPT { return *this; }
643  };
644 
645 #if __cpp_deduction_guides >= 201606
646  template<typename _InputIterator, typename _ValT
647  = typename iterator_traits<_InputIterator>::value_type,
648  typename _Allocator = allocator<_ValT>,
649  typename = _RequireInputIter<_InputIterator>,
650  typename = _RequireAllocator<_Allocator>>
651  deque(_InputIterator, _InputIterator, _Allocator = _Allocator())
652  -> deque<_ValT, _Allocator>;
653 
654  template<typename _Tp, typename _Allocator = allocator<_Tp>,
655  typename = _RequireAllocator<_Allocator>>
656  deque(size_t, _Tp, _Allocator = _Allocator())
657  -> deque<_Tp, _Allocator>;
658 #endif
659 
660  template<typename _Tp, typename _Alloc>
661  inline bool
662  operator==(const deque<_Tp, _Alloc>& __lhs,
663  const deque<_Tp, _Alloc>& __rhs)
664  { return __lhs._M_base() == __rhs._M_base(); }
665 
666 #if __cpp_lib_three_way_comparison
667  template<typename _Tp, typename _Alloc>
668  constexpr __detail::__synth3way_t<_Tp>
669  operator<=>(const deque<_Tp, _Alloc>& __x, const deque<_Tp, _Alloc>& __y)
670  { return __x._M_base() <=> __y._M_base(); }
671 #else
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  template<typename _Tp, typename _Alloc>
679  inline bool
680  operator<(const deque<_Tp, _Alloc>& __lhs,
681  const deque<_Tp, _Alloc>& __rhs)
682  { return __lhs._M_base() < __rhs._M_base(); }
683 
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 #endif // three-way comparison
702 
703  template<typename _Tp, typename _Alloc>
704  inline void
705  swap(deque<_Tp, _Alloc>& __lhs, deque<_Tp, _Alloc>& __rhs)
706  _GLIBCXX_NOEXCEPT_IF(noexcept(__lhs.swap(__rhs)))
707  { __lhs.swap(__rhs); }
708 
709 } // namespace __debug
710 } // namespace std
711 
712 #endif