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