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