1 // Debugging deque implementation -*- C++ -*-
3 // Copyright (C) 2003, 2004, 2005
4 // Free Software Foundation, Inc.
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 2, or (at your option)
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.
17 // You should have received a copy of the GNU General Public License along
18 // with this library; see the file COPYING. If not, write to the Free
19 // Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301,
22 // As a special exception, you may use this file as part of a free software
23 // library without restriction. Specifically, if other files instantiate
24 // templates or use macros or inline functions from this file, or you compile
25 // this file and link it with other files to produce an executable, this
26 // file does not by itself cause the resulting executable to be covered by
27 // the GNU General Public License. This exception does not however
28 // invalidate any other reasons why the executable file might be covered by
29 // the GNU General Public License.
32 * This file is a GNU debug extension to the Standard C++ Library.
35 #ifndef _GLIBCXX_DEBUG_DEQUE
36 #define _GLIBCXX_DEBUG_DEQUE 1
39 #include <debug/safe_sequence.h>
40 #include <debug/safe_iterator.h>
46 template<typename _Tp, typename _Allocator = std::allocator<_Tp> >
48 : public _GLIBCXX_STD::deque<_Tp, _Allocator>,
49 public __gnu_debug::_Safe_sequence<deque<_Tp, _Allocator> >
51 typedef _GLIBCXX_STD::deque<_Tp, _Allocator> _Base;
52 typedef __gnu_debug::_Safe_sequence<deque> _Safe_base;
55 typedef typename _Base::reference reference;
56 typedef typename _Base::const_reference const_reference;
58 typedef __gnu_debug::_Safe_iterator<typename _Base::iterator,deque>
60 typedef __gnu_debug::_Safe_iterator<typename _Base::const_iterator,deque>
63 typedef typename _Base::size_type size_type;
64 typedef typename _Base::difference_type difference_type;
66 typedef _Tp value_type;
67 typedef _Allocator allocator_type;
68 typedef typename _Base::pointer pointer;
69 typedef typename _Base::const_pointer const_pointer;
70 typedef std::reverse_iterator<iterator> reverse_iterator;
71 typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
73 // 23.2.1.1 construct/copy/destroy:
74 explicit deque(const _Allocator& __a = _Allocator())
77 explicit deque(size_type __n, const _Tp& __value = _Tp(),
78 const _Allocator& __a = _Allocator())
79 : _Base(__n, __value, __a) { }
81 template<class _InputIterator>
82 deque(_InputIterator __first, _InputIterator __last,
83 const _Allocator& __a = _Allocator())
84 : _Base(__gnu_debug::__check_valid_range(__first, __last), __last, __a)
87 deque(const deque<_Tp,_Allocator>& __x) : _Base(__x), _Safe_base() { }
89 deque(const _Base& __x) : _Base(__x), _Safe_base() { }
93 deque<_Tp,_Allocator>&
94 operator=(const deque<_Tp,_Allocator>& __x)
96 *static_cast<_Base*>(this) = __x;
97 this->_M_invalidate_all();
101 template<class _InputIterator>
103 assign(_InputIterator __first, _InputIterator __last)
105 __glibcxx_check_valid_range(__first, __last);
106 _Base::assign(__first, __last);
107 this->_M_invalidate_all();
111 assign(size_type __n, const _Tp& __t)
113 _Base::assign(__n, __t);
114 this->_M_invalidate_all();
117 using _Base::get_allocator;
122 { return iterator(_Base::begin(), this); }
126 { return const_iterator(_Base::begin(), this); }
130 { return iterator(_Base::end(), this); }
134 { return const_iterator(_Base::end(), this); }
138 { return reverse_iterator(end()); }
140 const_reverse_iterator
142 { return const_reverse_iterator(end()); }
146 { return reverse_iterator(begin()); }
148 const_reverse_iterator
150 { return const_reverse_iterator(begin()); }
152 // 23.2.1.2 capacity:
154 using _Base::max_size;
157 resize(size_type __sz, _Tp __c = _Tp())
159 typedef typename _Base::const_iterator _Base_const_iterator;
160 typedef __gnu_debug::_After_nth_from<_Base_const_iterator> _After_nth;
162 bool __invalidate_all = __sz > this->size();
163 if (__sz < this->size())
164 this->_M_invalidate_if(_After_nth(__sz, _M_base().begin()));
166 _Base::resize(__sz, __c);
168 if (__invalidate_all)
169 this->_M_invalidate_all();
176 operator[](size_type __n)
178 __glibcxx_check_subscript(__n);
179 return _M_base()[__n];
183 operator[](size_type __n) const
185 __glibcxx_check_subscript(__n);
186 return _M_base()[__n];
194 __glibcxx_check_nonempty();
195 return _Base::front();
201 __glibcxx_check_nonempty();
202 return _Base::front();
208 __glibcxx_check_nonempty();
209 return _Base::back();
215 __glibcxx_check_nonempty();
216 return _Base::back();
219 // 23.2.1.3 modifiers:
221 push_front(const _Tp& __x)
223 _Base::push_front(__x);
224 this->_M_invalidate_all();
228 push_back(const _Tp& __x)
230 _Base::push_back(__x);
231 this->_M_invalidate_all();
235 insert(iterator __position, const _Tp& __x)
237 __glibcxx_check_insert(__position);
238 typename _Base::iterator __res = _Base::insert(__position.base(), __x);
239 this->_M_invalidate_all();
240 return iterator(__res, this);
244 insert(iterator __position, size_type __n, const _Tp& __x)
246 __glibcxx_check_insert(__position);
247 _Base::insert(__position.base(), __n, __x);
248 this->_M_invalidate_all();
251 template<class _InputIterator>
253 insert(iterator __position,
254 _InputIterator __first, _InputIterator __last)
256 __glibcxx_check_insert_range(__position, __first, __last);
257 _Base::insert(__position.base(), __first, __last);
258 this->_M_invalidate_all();
264 __glibcxx_check_nonempty();
265 iterator __victim = begin();
266 __victim._M_invalidate();
273 __glibcxx_check_nonempty();
274 iterator __victim = end();
276 __victim._M_invalidate();
281 erase(iterator __position)
283 __glibcxx_check_erase(__position);
284 if (__position == begin() || __position == end()-1)
286 __position._M_invalidate();
287 return iterator(_Base::erase(__position.base()), this);
291 typename _Base::iterator __res = _Base::erase(__position.base());
292 this->_M_invalidate_all();
293 return iterator(__res, this);
298 erase(iterator __first, iterator __last)
300 // _GLIBCXX_RESOLVE_LIB_DEFECTS
301 // 151. can't currently clear() empty container
302 __glibcxx_check_erase_range(__first, __last);
303 if (__first == begin() || __last == end())
305 this->_M_detach_singular();
306 for (iterator __position = __first; __position != __last; )
308 iterator __victim = __position++;
309 __victim._M_invalidate();
313 return iterator(_Base::erase(__first.base(), __last.base()),
318 this->_M_revalidate_singular();
319 __throw_exception_again;
324 typename _Base::iterator __res = _Base::erase(__first.base(),
326 this->_M_invalidate_all();
327 return iterator(__res, this);
332 swap(deque<_Tp,_Allocator>& __x)
342 this->_M_invalidate_all();
346 _M_base() { return *this; }
349 _M_base() const { return *this; }
352 template<typename _Tp, typename _Alloc>
354 operator==(const deque<_Tp, _Alloc>& __lhs,
355 const deque<_Tp, _Alloc>& __rhs)
356 { return __lhs._M_base() == __rhs._M_base(); }
358 template<typename _Tp, typename _Alloc>
360 operator!=(const deque<_Tp, _Alloc>& __lhs,
361 const deque<_Tp, _Alloc>& __rhs)
362 { return __lhs._M_base() != __rhs._M_base(); }
364 template<typename _Tp, typename _Alloc>
366 operator<(const deque<_Tp, _Alloc>& __lhs, const deque<_Tp, _Alloc>& __rhs)
367 { return __lhs._M_base() < __rhs._M_base(); }
369 template<typename _Tp, typename _Alloc>
371 operator<=(const deque<_Tp, _Alloc>& __lhs,
372 const deque<_Tp, _Alloc>& __rhs)
373 { return __lhs._M_base() <= __rhs._M_base(); }
375 template<typename _Tp, typename _Alloc>
377 operator>=(const deque<_Tp, _Alloc>& __lhs,
378 const deque<_Tp, _Alloc>& __rhs)
379 { return __lhs._M_base() >= __rhs._M_base(); }
381 template<typename _Tp, typename _Alloc>
383 operator>(const deque<_Tp, _Alloc>& __lhs, const deque<_Tp, _Alloc>& __rhs)
384 { return __lhs._M_base() > __rhs._M_base(); }
386 template<typename _Tp, typename _Alloc>
388 swap(deque<_Tp, _Alloc>& __lhs, deque<_Tp, _Alloc>& __rhs)
389 { __lhs.swap(__rhs); }
390 } // namespace __debug