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, 2011
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 
50  typedef typename _Base::iterator _Base_iterator;
52  public:
53  typedef typename _Base::reference reference;
54  typedef typename _Base::const_reference const_reference;
55 
57  iterator;
60 
61  typedef typename _Base::size_type size_type;
62  typedef typename _Base::difference_type difference_type;
63 
64  typedef _Tp value_type;
65  typedef _Allocator allocator_type;
66  typedef typename _Base::pointer pointer;
67  typedef typename _Base::const_pointer const_pointer;
70 
71  // 23.2.1.1 construct/copy/destroy:
72  explicit
73  deque(const _Allocator& __a = _Allocator())
74  : _Base(__a) { }
75 
76 #ifdef __GXX_EXPERIMENTAL_CXX0X__
77  explicit
78  deque(size_type __n)
79  : _Base(__n) { }
80 
81  deque(size_type __n, const _Tp& __value,
82  const _Allocator& __a = _Allocator())
83  : _Base(__n, __value, __a) { }
84 #else
85  explicit
86  deque(size_type __n, const _Tp& __value = _Tp(),
87  const _Allocator& __a = _Allocator())
88  : _Base(__n, __value, __a) { }
89 #endif
90 
91  template<class _InputIterator>
92  deque(_InputIterator __first, _InputIterator __last,
93  const _Allocator& __a = _Allocator())
94  : _Base(__gnu_debug::__base(__gnu_debug::__check_valid_range(__first,
95  __last)),
96  __gnu_debug::__base(__last), __a)
97  { }
98 
99  deque(const deque& __x)
100  : _Base(__x) { }
101 
102  deque(const _Base& __x)
103  : _Base(__x) { }
104 
105 #ifdef __GXX_EXPERIMENTAL_CXX0X__
106  deque(deque&& __x)
107  : _Base(std::move(__x))
108  { this->_M_swap(__x); }
109 
111  const allocator_type& __a = allocator_type())
112  : _Base(__l, __a) { }
113 #endif
114 
115  ~deque() _GLIBCXX_NOEXCEPT { }
116 
117  deque&
118  operator=(const deque& __x)
119  {
120  *static_cast<_Base*>(this) = __x;
121  this->_M_invalidate_all();
122  return *this;
123  }
124 
125 #ifdef __GXX_EXPERIMENTAL_CXX0X__
126  deque&
127  operator=(deque&& __x)
128  {
129  // NB: DR 1204.
130  // NB: DR 675.
131  clear();
132  swap(__x);
133  return *this;
134  }
135 
136  deque&
137  operator=(initializer_list<value_type> __l)
138  {
139  *static_cast<_Base*>(this) = __l;
140  this->_M_invalidate_all();
141  return *this;
142  }
143 #endif
144 
145  template<class _InputIterator>
146  void
147  assign(_InputIterator __first, _InputIterator __last)
148  {
149  __glibcxx_check_valid_range(__first, __last);
150  _Base::assign(__gnu_debug::__base(__first),
151  __gnu_debug::__base(__last));
152  this->_M_invalidate_all();
153  }
154 
155  void
156  assign(size_type __n, const _Tp& __t)
157  {
158  _Base::assign(__n, __t);
159  this->_M_invalidate_all();
160  }
161 
162 #ifdef __GXX_EXPERIMENTAL_CXX0X__
163  void
164  assign(initializer_list<value_type> __l)
165  {
166  _Base::assign(__l);
167  this->_M_invalidate_all();
168  }
169 #endif
170 
171  using _Base::get_allocator;
172 
173  // iterators:
174  iterator
175  begin() _GLIBCXX_NOEXCEPT
176  { return iterator(_Base::begin(), this); }
177 
179  begin() const _GLIBCXX_NOEXCEPT
180  { return const_iterator(_Base::begin(), this); }
181 
182  iterator
183  end() _GLIBCXX_NOEXCEPT
184  { return iterator(_Base::end(), this); }
185 
187  end() const _GLIBCXX_NOEXCEPT
188  { return const_iterator(_Base::end(), this); }
189 
191  rbegin() _GLIBCXX_NOEXCEPT
192  { return reverse_iterator(end()); }
193 
195  rbegin() const _GLIBCXX_NOEXCEPT
196  { return const_reverse_iterator(end()); }
197 
199  rend() _GLIBCXX_NOEXCEPT
200  { return reverse_iterator(begin()); }
201 
203  rend() const _GLIBCXX_NOEXCEPT
204  { return const_reverse_iterator(begin()); }
205 
206 #ifdef __GXX_EXPERIMENTAL_CXX0X__
208  cbegin() const noexcept
209  { return const_iterator(_Base::begin(), this); }
210 
212  cend() const noexcept
213  { return const_iterator(_Base::end(), this); }
214 
216  crbegin() const noexcept
217  { return const_reverse_iterator(end()); }
218 
220  crend() const noexcept
221  { return const_reverse_iterator(begin()); }
222 #endif
223 
224  private:
225  void
226  _M_invalidate_after_nth(difference_type __n)
227  {
229  this->_M_invalidate_if(_After_nth(__n, _Base::begin()));
230  }
231 
232  public:
233  // 23.2.1.2 capacity:
234  using _Base::size;
235  using _Base::max_size;
236 
237 #ifdef __GXX_EXPERIMENTAL_CXX0X__
238  void
239  resize(size_type __sz)
240  {
241  bool __invalidate_all = __sz > this->size();
242  if (__sz < this->size())
243  this->_M_invalidate_after_nth(__sz);
244 
245  _Base::resize(__sz);
246 
247  if (__invalidate_all)
248  this->_M_invalidate_all();
249  }
250 
251  void
252  resize(size_type __sz, const _Tp& __c)
253  {
254  bool __invalidate_all = __sz > this->size();
255  if (__sz < this->size())
256  this->_M_invalidate_after_nth(__sz);
257 
258  _Base::resize(__sz, __c);
259 
260  if (__invalidate_all)
261  this->_M_invalidate_all();
262  }
263 #else
264  void
265  resize(size_type __sz, _Tp __c = _Tp())
266  {
267  bool __invalidate_all = __sz > this->size();
268  if (__sz < this->size())
269  this->_M_invalidate_after_nth(__sz);
270 
271  _Base::resize(__sz, __c);
272 
273  if (__invalidate_all)
274  this->_M_invalidate_all();
275  }
276 #endif
277 
278 #ifdef __GXX_EXPERIMENTAL_CXX0X__
279  void
280  shrink_to_fit()
281  {
282  if (_Base::_M_shrink_to_fit())
283  this->_M_invalidate_all();
284  }
285 #endif
286 
287  using _Base::empty;
288 
289  // element access:
290  reference
291  operator[](size_type __n)
292  {
293  __glibcxx_check_subscript(__n);
294  return _M_base()[__n];
295  }
296 
297  const_reference
298  operator[](size_type __n) const
299  {
300  __glibcxx_check_subscript(__n);
301  return _M_base()[__n];
302  }
303 
304  using _Base::at;
305 
306  reference
307  front()
308  {
309  __glibcxx_check_nonempty();
310  return _Base::front();
311  }
312 
313  const_reference
314  front() const
315  {
316  __glibcxx_check_nonempty();
317  return _Base::front();
318  }
319 
320  reference
321  back()
322  {
323  __glibcxx_check_nonempty();
324  return _Base::back();
325  }
326 
327  const_reference
328  back() const
329  {
330  __glibcxx_check_nonempty();
331  return _Base::back();
332  }
333 
334  // 23.2.1.3 modifiers:
335  void
336  push_front(const _Tp& __x)
337  {
338  _Base::push_front(__x);
339  this->_M_invalidate_all();
340  }
341 
342  void
343  push_back(const _Tp& __x)
344  {
345  _Base::push_back(__x);
346  this->_M_invalidate_all();
347  }
348 
349 #ifdef __GXX_EXPERIMENTAL_CXX0X__
350  void
351  push_front(_Tp&& __x)
352  { emplace_front(std::move(__x)); }
353 
354  void
355  push_back(_Tp&& __x)
356  { emplace_back(std::move(__x)); }
357 
358  template<typename... _Args>
359  void
360  emplace_front(_Args&&... __args)
361  {
362  _Base::emplace_front(std::forward<_Args>(__args)...);
363  this->_M_invalidate_all();
364  }
365 
366  template<typename... _Args>
367  void
368  emplace_back(_Args&&... __args)
369  {
370  _Base::emplace_back(std::forward<_Args>(__args)...);
371  this->_M_invalidate_all();
372  }
373 
374  template<typename... _Args>
375  iterator
376  emplace(iterator __position, _Args&&... __args)
377  {
378  __glibcxx_check_insert(__position);
379  _Base_iterator __res = _Base::emplace(__position.base(),
380  std::forward<_Args>(__args)...);
381  this->_M_invalidate_all();
382  return iterator(__res, this);
383  }
384 #endif
385 
386  iterator
387  insert(iterator __position, const _Tp& __x)
388  {
389  __glibcxx_check_insert(__position);
390  _Base_iterator __res = _Base::insert(__position.base(), __x);
391  this->_M_invalidate_all();
392  return iterator(__res, this);
393  }
394 
395 #ifdef __GXX_EXPERIMENTAL_CXX0X__
396  iterator
397  insert(iterator __position, _Tp&& __x)
398  { return emplace(__position, std::move(__x)); }
399 
400  void
401  insert(iterator __p, initializer_list<value_type> __l)
402  {
403  _Base::insert(__p, __l);
404  this->_M_invalidate_all();
405  }
406 #endif
407 
408  void
409  insert(iterator __position, size_type __n, const _Tp& __x)
410  {
411  __glibcxx_check_insert(__position);
412  _Base::insert(__position.base(), __n, __x);
413  this->_M_invalidate_all();
414  }
415 
416  template<class _InputIterator>
417  void
418  insert(iterator __position,
419  _InputIterator __first, _InputIterator __last)
420  {
421  __glibcxx_check_insert_range(__position, __first, __last);
422  _Base::insert(__position.base(), __gnu_debug::__base(__first),
423  __gnu_debug::__base(__last));
424  this->_M_invalidate_all();
425  }
426 
427  void
428  pop_front()
429  {
430  __glibcxx_check_nonempty();
431  this->_M_invalidate_if(_Equal(_Base::begin()));
432  _Base::pop_front();
433  }
434 
435  void
436  pop_back()
437  {
438  __glibcxx_check_nonempty();
439  this->_M_invalidate_if(_Equal(--_Base::end()));
440  _Base::pop_back();
441  }
442 
443  iterator
444  erase(iterator __position)
445  {
446  __glibcxx_check_erase(__position);
447  _Base_iterator __victim = __position.base();
448  if (__victim == _Base::begin() || __victim == _Base::end()-1)
449  {
450  this->_M_invalidate_if(_Equal(__victim));
451  return iterator(_Base::erase(__victim), this);
452  }
453  else
454  {
455  _Base_iterator __res = _Base::erase(__victim);
456  this->_M_invalidate_all();
457  return iterator(__res, this);
458  }
459  }
460 
461  iterator
462  erase(iterator __first, iterator __last)
463  {
464  // _GLIBCXX_RESOLVE_LIB_DEFECTS
465  // 151. can't currently clear() empty container
466  __glibcxx_check_erase_range(__first, __last);
467 
468  if (__first.base() == __last.base())
469  return __first;
470  else if (__first.base() == _Base::begin()
471  || __last.base() == _Base::end())
472  {
473  this->_M_detach_singular();
474  for (_Base_iterator __position = __first.base();
475  __position != __last.base(); ++__position)
476  {
477  this->_M_invalidate_if(_Equal(__position));
478  }
479  __try
480  {
481  return iterator(_Base::erase(__first.base(), __last.base()),
482  this);
483  }
484  __catch(...)
485  {
486  this->_M_revalidate_singular();
487  __throw_exception_again;
488  }
489  }
490  else
491  {
492  _Base_iterator __res = _Base::erase(__first.base(),
493  __last.base());
494  this->_M_invalidate_all();
495  return iterator(__res, this);
496  }
497  }
498 
499  void
500  swap(deque& __x)
501  {
502  _Base::swap(__x);
503  this->_M_swap(__x);
504  }
505 
506  void
507  clear() _GLIBCXX_NOEXCEPT
508  {
509  _Base::clear();
510  this->_M_invalidate_all();
511  }
512 
513  _Base&
514  _M_base() _GLIBCXX_NOEXCEPT { return *this; }
515 
516  const _Base&
517  _M_base() const _GLIBCXX_NOEXCEPT { return *this; }
518  };
519 
520  template<typename _Tp, typename _Alloc>
521  inline bool
522  operator==(const deque<_Tp, _Alloc>& __lhs,
523  const deque<_Tp, _Alloc>& __rhs)
524  { return __lhs._M_base() == __rhs._M_base(); }
525 
526  template<typename _Tp, typename _Alloc>
527  inline bool
528  operator!=(const deque<_Tp, _Alloc>& __lhs,
529  const deque<_Tp, _Alloc>& __rhs)
530  { return __lhs._M_base() != __rhs._M_base(); }
531 
532  template<typename _Tp, typename _Alloc>
533  inline bool
534  operator<(const deque<_Tp, _Alloc>& __lhs,
535  const deque<_Tp, _Alloc>& __rhs)
536  { return __lhs._M_base() < __rhs._M_base(); }
537 
538  template<typename _Tp, typename _Alloc>
539  inline bool
540  operator<=(const deque<_Tp, _Alloc>& __lhs,
541  const deque<_Tp, _Alloc>& __rhs)
542  { return __lhs._M_base() <= __rhs._M_base(); }
543 
544  template<typename _Tp, typename _Alloc>
545  inline bool
546  operator>=(const deque<_Tp, _Alloc>& __lhs,
547  const deque<_Tp, _Alloc>& __rhs)
548  { return __lhs._M_base() >= __rhs._M_base(); }
549 
550  template<typename _Tp, typename _Alloc>
551  inline bool
552  operator>(const deque<_Tp, _Alloc>& __lhs,
553  const deque<_Tp, _Alloc>& __rhs)
554  { return __lhs._M_base() > __rhs._M_base(); }
555 
556  template<typename _Tp, typename _Alloc>
557  inline void
558  swap(deque<_Tp, _Alloc>& __lhs, deque<_Tp, _Alloc>& __rhs)
559  { __lhs.swap(__rhs); }
560 
561 } // namespace __debug
562 } // namespace std
563 
564 #endif