libstdc++
debug/deque
Go to the documentation of this file.
1 // Debugging deque implementation -*- C++ -*-
2 
3 // Copyright (C) 2003, 2004, 2005, 2006, 2007, 2008, 2009, 2010
4 // Free Software Foundation, Inc.
5 //
6 // This file is part of the GNU ISO C++ Library. This library is free
7 // software; you can redistribute it and/or modify it under the
8 // terms of the GNU General Public License as published by the
9 // Free Software Foundation; either version 3, or (at your option)
10 // any later version.
11 
12 // This library is distributed in the hope that it will be useful,
13 // but WITHOUT ANY WARRANTY; without even the implied warranty of
14 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15 // GNU General Public License for more details.
16 
17 // Under Section 7 of GPL version 3, you are granted additional
18 // permissions described in the GCC Runtime Library Exception, version
19 // 3.1, as published by the Free Software Foundation.
20 
21 // You should have received a copy of the GNU General Public License and
22 // a copy of the GCC Runtime Library Exception along with this program;
23 // see the files COPYING3 and COPYING.RUNTIME respectively. If not, see
24 // <http://www.gnu.org/licenses/>.
25 
26 /** @file debug/deque
27  * This file is a GNU debug extension to the Standard C++ Library.
28  */
29 
30 #ifndef _GLIBCXX_DEBUG_DEQUE
31 #define _GLIBCXX_DEBUG_DEQUE 1
32 
33 #include <deque>
34 #include <debug/safe_sequence.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 _GLIBCXX_STD_C::deque<_Tp, _Allocator>,
45  public __gnu_debug::_Safe_sequence<deque<_Tp, _Allocator> >
46  {
47  typedef _GLIBCXX_STD_C::deque<_Tp, _Allocator> _Base;
48  typedef __gnu_debug::_Safe_sequence<deque> _Safe_base;
49 
50  typedef typename _Base::const_iterator _Base_const_iterator;
51  typedef typename _Base::iterator _Base_iterator;
52  typedef __gnu_debug::_Equal_to<_Base_const_iterator> _Equal;
53  public:
54  typedef typename _Base::reference reference;
55  typedef typename _Base::const_reference const_reference;
56 
57  typedef __gnu_debug::_Safe_iterator<_Base_iterator,deque>
58  iterator;
59  typedef __gnu_debug::_Safe_iterator<_Base_const_iterator,deque>
60  const_iterator;
61 
62  typedef typename _Base::size_type size_type;
63  typedef typename _Base::difference_type difference_type;
64 
65  typedef _Tp value_type;
66  typedef _Allocator allocator_type;
67  typedef typename _Base::pointer pointer;
68  typedef typename _Base::const_pointer const_pointer;
69  typedef std::reverse_iterator<iterator> reverse_iterator;
70  typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
71 
72  // 23.2.1.1 construct/copy/destroy:
73  explicit
74  deque(const _Allocator& __a = _Allocator())
75  : _Base(__a) { }
76 
77 #ifdef __GXX_EXPERIMENTAL_CXX0X__
78  explicit
79  deque(size_type __n)
80  : _Base(__n) { }
81 
82  deque(size_type __n, const _Tp& __value,
83  const _Allocator& __a = _Allocator())
84  : _Base(__n, __value, __a) { }
85 #else
86  explicit
87  deque(size_type __n, const _Tp& __value = _Tp(),
88  const _Allocator& __a = _Allocator())
89  : _Base(__n, __value, __a) { }
90 #endif
91 
92  template<class _InputIterator>
93  deque(_InputIterator __first, _InputIterator __last,
94  const _Allocator& __a = _Allocator())
95  : _Base(__gnu_debug::__base(__gnu_debug::__check_valid_range(__first,
96  __last)),
97  __gnu_debug::__base(__last), __a)
98  { }
99 
100  deque(const deque& __x)
101  : _Base(__x), _Safe_base() { }
102 
103  deque(const _Base& __x)
104  : _Base(__x), _Safe_base() { }
105 
106 #ifdef __GXX_EXPERIMENTAL_CXX0X__
107  deque(deque&& __x)
108  : _Base(std::move(__x)), _Safe_base()
109  { this->_M_swap(__x); }
110 
111  deque(initializer_list<value_type> __l,
112  const allocator_type& __a = allocator_type())
113  : _Base(__l, __a), _Safe_base() { }
114 #endif
115 
116  ~deque() { }
117 
118  deque&
119  operator=(const deque& __x)
120  {
121  *static_cast<_Base*>(this) = __x;
122  this->_M_invalidate_all();
123  return *this;
124  }
125 
126 #ifdef __GXX_EXPERIMENTAL_CXX0X__
127  deque&
128  operator=(deque&& __x)
129  {
130  // NB: DR 1204.
131  // NB: DR 675.
132  clear();
133  swap(__x);
134  return *this;
135  }
136 
137  deque&
138  operator=(initializer_list<value_type> __l)
139  {
140  *static_cast<_Base*>(this) = __l;
141  this->_M_invalidate_all();
142  return *this;
143  }
144 #endif
145 
146  template<class _InputIterator>
147  void
148  assign(_InputIterator __first, _InputIterator __last)
149  {
150  __glibcxx_check_valid_range(__first, __last);
151  _Base::assign(__gnu_debug::__base(__first),
152  __gnu_debug::__base(__last));
153  this->_M_invalidate_all();
154  }
155 
156  void
157  assign(size_type __n, const _Tp& __t)
158  {
159  _Base::assign(__n, __t);
160  this->_M_invalidate_all();
161  }
162 
163 #ifdef __GXX_EXPERIMENTAL_CXX0X__
164  void
165  assign(initializer_list<value_type> __l)
166  {
167  _Base::assign(__l);
168  this->_M_invalidate_all();
169  }
170 #endif
171 
172  using _Base::get_allocator;
173 
174  // iterators:
175  iterator
176  begin()
177  { return iterator(_Base::begin(), this); }
178 
179  const_iterator
180  begin() const
181  { return const_iterator(_Base::begin(), this); }
182 
183  iterator
184  end()
185  { return iterator(_Base::end(), this); }
186 
187  const_iterator
188  end() const
189  { return const_iterator(_Base::end(), this); }
190 
191  reverse_iterator
192  rbegin()
193  { return reverse_iterator(end()); }
194 
195  const_reverse_iterator
196  rbegin() const
197  { return const_reverse_iterator(end()); }
198 
199  reverse_iterator
200  rend()
201  { return reverse_iterator(begin()); }
202 
203  const_reverse_iterator
204  rend() const
205  { return const_reverse_iterator(begin()); }
206 
207 #ifdef __GXX_EXPERIMENTAL_CXX0X__
208  const_iterator
209  cbegin() const
210  { return const_iterator(_Base::begin(), this); }
211 
212  const_iterator
213  cend() const
214  { return const_iterator(_Base::end(), this); }
215 
216  const_reverse_iterator
217  crbegin() const
218  { return const_reverse_iterator(end()); }
219 
220  const_reverse_iterator
221  crend() const
222  { return const_reverse_iterator(begin()); }
223 #endif
224 
225  private:
226  void
227  _M_invalidate_after_nth(difference_type __n)
228  {
229  typedef __gnu_debug::_After_nth_from<_Base_const_iterator> _After_nth;
230  this->_M_invalidate_if(_After_nth(__n, _Base::begin()));
231  }
232 
233  public:
234  // 23.2.1.2 capacity:
235  using _Base::size;
236  using _Base::max_size;
237 
238 #ifdef __GXX_EXPERIMENTAL_CXX0X__
239  void
240  resize(size_type __sz)
241  {
242  bool __invalidate_all = __sz > this->size();
243  if (__sz < this->size())
244  this->_M_invalidate_after_nth(__sz);
245 
246  _Base::resize(__sz);
247 
248  if (__invalidate_all)
249  this->_M_invalidate_all();
250  }
251 
252  void
253  resize(size_type __sz, const _Tp& __c)
254  {
255  bool __invalidate_all = __sz > this->size();
256  if (__sz < this->size())
257  this->_M_invalidate_after_nth(__sz);
258 
259  _Base::resize(__sz, __c);
260 
261  if (__invalidate_all)
262  this->_M_invalidate_all();
263  }
264 #else
265  void
266  resize(size_type __sz, _Tp __c = _Tp())
267  {
268  bool __invalidate_all = __sz > this->size();
269  if (__sz < this->size())
270  this->_M_invalidate_after_nth(__sz);
271 
272  _Base::resize(__sz, __c);
273 
274  if (__invalidate_all)
275  this->_M_invalidate_all();
276  }
277 #endif
278 
279 #ifdef __GXX_EXPERIMENTAL_CXX0X__
280  using _Base::shrink_to_fit;
281 #endif
282 
283  using _Base::empty;
284 
285  // element access:
286  reference
287  operator[](size_type __n)
288  {
289  __glibcxx_check_subscript(__n);
290  return _M_base()[__n];
291  }
292 
293  const_reference
294  operator[](size_type __n) const
295  {
296  __glibcxx_check_subscript(__n);
297  return _M_base()[__n];
298  }
299 
300  using _Base::at;
301 
302  reference
303  front()
304  {
305  __glibcxx_check_nonempty();
306  return _Base::front();
307  }
308 
309  const_reference
310  front() const
311  {
312  __glibcxx_check_nonempty();
313  return _Base::front();
314  }
315 
316  reference
317  back()
318  {
319  __glibcxx_check_nonempty();
320  return _Base::back();
321  }
322 
323  const_reference
324  back() const
325  {
326  __glibcxx_check_nonempty();
327  return _Base::back();
328  }
329 
330  // 23.2.1.3 modifiers:
331  void
332  push_front(const _Tp& __x)
333  {
334  _Base::push_front(__x);
335  this->_M_invalidate_all();
336  }
337 
338  void
339  push_back(const _Tp& __x)
340  {
341  _Base::push_back(__x);
342  this->_M_invalidate_all();
343  }
344 
345 #ifdef __GXX_EXPERIMENTAL_CXX0X__
346  void
347  push_front(_Tp&& __x)
348  { emplace_front(std::move(__x)); }
349 
350  void
351  push_back(_Tp&& __x)
352  { emplace_back(std::move(__x)); }
353 
354  template<typename... _Args>
355  void
356  emplace_front(_Args&&... __args)
357  {
358  _Base::emplace_front(std::forward<_Args>(__args)...);
359  this->_M_invalidate_all();
360  }
361 
362  template<typename... _Args>
363  void
364  emplace_back(_Args&&... __args)
365  {
366  _Base::emplace_back(std::forward<_Args>(__args)...);
367  this->_M_invalidate_all();
368  }
369 
370  template<typename... _Args>
371  iterator
372  emplace(iterator __position, _Args&&... __args)
373  {
374  __glibcxx_check_insert(__position);
375  _Base_iterator __res = _Base::emplace(__position.base(),
376  std::forward<_Args>(__args)...);
377  this->_M_invalidate_all();
378  return iterator(__res, this);
379  }
380 #endif
381 
382  iterator
383  insert(iterator __position, const _Tp& __x)
384  {
385  __glibcxx_check_insert(__position);
386  _Base_iterator __res = _Base::insert(__position.base(), __x);
387  this->_M_invalidate_all();
388  return iterator(__res, this);
389  }
390 
391 #ifdef __GXX_EXPERIMENTAL_CXX0X__
392  iterator
393  insert(iterator __position, _Tp&& __x)
394  { return emplace(__position, std::move(__x)); }
395 
396  void
397  insert(iterator __p, initializer_list<value_type> __l)
398  {
399  _Base::insert(__p, __l);
400  this->_M_invalidate_all();
401  }
402 #endif
403 
404  void
405  insert(iterator __position, size_type __n, const _Tp& __x)
406  {
407  __glibcxx_check_insert(__position);
408  _Base::insert(__position.base(), __n, __x);
409  this->_M_invalidate_all();
410  }
411 
412  template<class _InputIterator>
413  void
414  insert(iterator __position,
415  _InputIterator __first, _InputIterator __last)
416  {
417  __glibcxx_check_insert_range(__position, __first, __last);
418  _Base::insert(__position.base(), __gnu_debug::__base(__first),
419  __gnu_debug::__base(__last));
420  this->_M_invalidate_all();
421  }
422 
423  void
424  pop_front()
425  {
426  __glibcxx_check_nonempty();
427  this->_M_invalidate_if(_Equal(_Base::begin()));
428  _Base::pop_front();
429  }
430 
431  void
432  pop_back()
433  {
434  __glibcxx_check_nonempty();
435  this->_M_invalidate_if(_Equal(--_Base::end()));
436  _Base::pop_back();
437  }
438 
439  iterator
440  erase(iterator __position)
441  {
442  __glibcxx_check_erase(__position);
443  _Base_iterator __victim = __position.base();
444  if (__victim == _Base::begin() || __victim == _Base::end()-1)
445  {
446  this->_M_invalidate_if(_Equal(__victim));
447  return iterator(_Base::erase(__victim), this);
448  }
449  else
450  {
451  _Base_iterator __res = _Base::erase(__victim);
452  this->_M_invalidate_all();
453  return iterator(__res, this);
454  }
455  }
456 
457  iterator
458  erase(iterator __first, iterator __last)
459  {
460  // _GLIBCXX_RESOLVE_LIB_DEFECTS
461  // 151. can't currently clear() empty container
462  __glibcxx_check_erase_range(__first, __last);
463 
464  if (__first.base() == __last.base())
465  return __first;
466  else if (__first.base() == _Base::begin()
467  || __last.base() == _Base::end())
468  {
469  this->_M_detach_singular();
470  for (_Base_iterator __position = __first.base();
471  __position != __last.base(); ++__position)
472  {
473  this->_M_invalidate_if(_Equal(__position));
474  }
475  __try
476  {
477  return iterator(_Base::erase(__first.base(), __last.base()),
478  this);
479  }
480  __catch(...)
481  {
482  this->_M_revalidate_singular();
483  __throw_exception_again;
484  }
485  }
486  else
487  {
488  _Base_iterator __res = _Base::erase(__first.base(),
489  __last.base());
490  this->_M_invalidate_all();
491  return iterator(__res, this);
492  }
493  }
494 
495  void
496  swap(deque& __x)
497  {
498  _Base::swap(__x);
499  this->_M_swap(__x);
500  }
501 
502  void
503  clear()
504  {
505  _Base::clear();
506  this->_M_invalidate_all();
507  }
508 
509  _Base&
510  _M_base() { return *this; }
511 
512  const _Base&
513  _M_base() const { return *this; }
514  };
515 
516  template<typename _Tp, typename _Alloc>
517  inline bool
518  operator==(const deque<_Tp, _Alloc>& __lhs,
519  const deque<_Tp, _Alloc>& __rhs)
520  { return __lhs._M_base() == __rhs._M_base(); }
521 
522  template<typename _Tp, typename _Alloc>
523  inline bool
524  operator!=(const deque<_Tp, _Alloc>& __lhs,
525  const deque<_Tp, _Alloc>& __rhs)
526  { return __lhs._M_base() != __rhs._M_base(); }
527 
528  template<typename _Tp, typename _Alloc>
529  inline bool
530  operator<(const deque<_Tp, _Alloc>& __lhs,
531  const deque<_Tp, _Alloc>& __rhs)
532  { return __lhs._M_base() < __rhs._M_base(); }
533 
534  template<typename _Tp, typename _Alloc>
535  inline bool
536  operator<=(const deque<_Tp, _Alloc>& __lhs,
537  const deque<_Tp, _Alloc>& __rhs)
538  { return __lhs._M_base() <= __rhs._M_base(); }
539 
540  template<typename _Tp, typename _Alloc>
541  inline bool
542  operator>=(const deque<_Tp, _Alloc>& __lhs,
543  const deque<_Tp, _Alloc>& __rhs)
544  { return __lhs._M_base() >= __rhs._M_base(); }
545 
546  template<typename _Tp, typename _Alloc>
547  inline bool
548  operator>(const deque<_Tp, _Alloc>& __lhs,
549  const deque<_Tp, _Alloc>& __rhs)
550  { return __lhs._M_base() > __rhs._M_base(); }
551 
552  template<typename _Tp, typename _Alloc>
553  inline void
554  swap(deque<_Tp, _Alloc>& __lhs, deque<_Tp, _Alloc>& __rhs)
555  { __lhs.swap(__rhs); }
556 
557 } // namespace __debug
558 } // namespace std
559 
560 #endif