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