1 // Debugging deque implementation -*- C++ -*-
3 // Copyright (C) 2003, 2004, 2005, 2006, 2007, 2008, 2009, 2010, 2011
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 3, 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 // 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.
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/>.
27 * This file is a GNU debug extension to the Standard C++ Library.
30 #ifndef _GLIBCXX_DEBUG_DEQUE
31 #define _GLIBCXX_DEBUG_DEQUE 1
34 #include <debug/safe_sequence.h>
35 #include <debug/safe_iterator.h>
37 namespace std _GLIBCXX_VISIBILITY(default)
41 /// Class std::deque with safety/checking/debug instrumentation.
42 template<typename _Tp, typename _Allocator = std::allocator<_Tp> >
44 : public _GLIBCXX_STD_C::deque<_Tp, _Allocator>,
45 public __gnu_debug::_Safe_sequence<deque<_Tp, _Allocator> >
47 typedef _GLIBCXX_STD_C::deque<_Tp, _Allocator> _Base;
49 typedef typename _Base::const_iterator _Base_const_iterator;
50 typedef typename _Base::iterator _Base_iterator;
51 typedef __gnu_debug::_Equal_to<_Base_const_iterator> _Equal;
53 typedef typename _Base::reference reference;
54 typedef typename _Base::const_reference const_reference;
56 typedef __gnu_debug::_Safe_iterator<_Base_iterator,deque>
58 typedef __gnu_debug::_Safe_iterator<_Base_const_iterator,deque>
61 typedef typename _Base::size_type size_type;
62 typedef typename _Base::difference_type difference_type;
64 typedef _Tp value_type;
65 typedef _Allocator allocator_type;
66 typedef typename _Base::pointer pointer;
67 typedef typename _Base::const_pointer const_pointer;
68 typedef std::reverse_iterator<iterator> reverse_iterator;
69 typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
71 // 23.2.1.1 construct/copy/destroy:
73 deque(const _Allocator& __a = _Allocator())
76 #ifdef __GXX_EXPERIMENTAL_CXX0X__
81 deque(size_type __n, const _Tp& __value,
82 const _Allocator& __a = _Allocator())
83 : _Base(__n, __value, __a) { }
86 deque(size_type __n, const _Tp& __value = _Tp(),
87 const _Allocator& __a = _Allocator())
88 : _Base(__n, __value, __a) { }
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,
96 __gnu_debug::__base(__last), __a)
99 deque(const deque& __x)
102 deque(const _Base& __x)
105 #ifdef __GXX_EXPERIMENTAL_CXX0X__
107 : _Base(std::move(__x))
108 { this->_M_swap(__x); }
110 deque(initializer_list<value_type> __l,
111 const allocator_type& __a = allocator_type())
112 : _Base(__l, __a) { }
115 ~deque() _GLIBCXX_NOEXCEPT { }
118 operator=(const deque& __x)
120 *static_cast<_Base*>(this) = __x;
121 this->_M_invalidate_all();
125 #ifdef __GXX_EXPERIMENTAL_CXX0X__
127 operator=(deque&& __x)
137 operator=(initializer_list<value_type> __l)
139 *static_cast<_Base*>(this) = __l;
140 this->_M_invalidate_all();
145 template<class _InputIterator>
147 assign(_InputIterator __first, _InputIterator __last)
149 __glibcxx_check_valid_range(__first, __last);
150 _Base::assign(__gnu_debug::__base(__first),
151 __gnu_debug::__base(__last));
152 this->_M_invalidate_all();
156 assign(size_type __n, const _Tp& __t)
158 _Base::assign(__n, __t);
159 this->_M_invalidate_all();
162 #ifdef __GXX_EXPERIMENTAL_CXX0X__
164 assign(initializer_list<value_type> __l)
167 this->_M_invalidate_all();
171 using _Base::get_allocator;
175 begin() _GLIBCXX_NOEXCEPT
176 { return iterator(_Base::begin(), this); }
179 begin() const _GLIBCXX_NOEXCEPT
180 { return const_iterator(_Base::begin(), this); }
183 end() _GLIBCXX_NOEXCEPT
184 { return iterator(_Base::end(), this); }
187 end() const _GLIBCXX_NOEXCEPT
188 { return const_iterator(_Base::end(), this); }
191 rbegin() _GLIBCXX_NOEXCEPT
192 { return reverse_iterator(end()); }
194 const_reverse_iterator
195 rbegin() const _GLIBCXX_NOEXCEPT
196 { return const_reverse_iterator(end()); }
199 rend() _GLIBCXX_NOEXCEPT
200 { return reverse_iterator(begin()); }
202 const_reverse_iterator
203 rend() const _GLIBCXX_NOEXCEPT
204 { return const_reverse_iterator(begin()); }
206 #ifdef __GXX_EXPERIMENTAL_CXX0X__
208 cbegin() const noexcept
209 { return const_iterator(_Base::begin(), this); }
212 cend() const noexcept
213 { return const_iterator(_Base::end(), this); }
215 const_reverse_iterator
216 crbegin() const noexcept
217 { return const_reverse_iterator(end()); }
219 const_reverse_iterator
220 crend() const noexcept
221 { return const_reverse_iterator(begin()); }
226 _M_invalidate_after_nth(difference_type __n)
228 typedef __gnu_debug::_After_nth_from<_Base_const_iterator> _After_nth;
229 this->_M_invalidate_if(_After_nth(__n, _Base::begin()));
233 // 23.2.1.2 capacity:
235 using _Base::max_size;
237 #ifdef __GXX_EXPERIMENTAL_CXX0X__
239 resize(size_type __sz)
241 bool __invalidate_all = __sz > this->size();
242 if (__sz < this->size())
243 this->_M_invalidate_after_nth(__sz);
247 if (__invalidate_all)
248 this->_M_invalidate_all();
252 resize(size_type __sz, const _Tp& __c)
254 bool __invalidate_all = __sz > this->size();
255 if (__sz < this->size())
256 this->_M_invalidate_after_nth(__sz);
258 _Base::resize(__sz, __c);
260 if (__invalidate_all)
261 this->_M_invalidate_all();
265 resize(size_type __sz, _Tp __c = _Tp())
267 bool __invalidate_all = __sz > this->size();
268 if (__sz < this->size())
269 this->_M_invalidate_after_nth(__sz);
271 _Base::resize(__sz, __c);
273 if (__invalidate_all)
274 this->_M_invalidate_all();
278 #ifdef __GXX_EXPERIMENTAL_CXX0X__
282 if (_Base::_M_shrink_to_fit())
283 this->_M_invalidate_all();
291 operator[](size_type __n)
293 __glibcxx_check_subscript(__n);
294 return _M_base()[__n];
298 operator[](size_type __n) const
300 __glibcxx_check_subscript(__n);
301 return _M_base()[__n];
309 __glibcxx_check_nonempty();
310 return _Base::front();
316 __glibcxx_check_nonempty();
317 return _Base::front();
323 __glibcxx_check_nonempty();
324 return _Base::back();
330 __glibcxx_check_nonempty();
331 return _Base::back();
334 // 23.2.1.3 modifiers:
336 push_front(const _Tp& __x)
338 _Base::push_front(__x);
339 this->_M_invalidate_all();
343 push_back(const _Tp& __x)
345 _Base::push_back(__x);
346 this->_M_invalidate_all();
349 #ifdef __GXX_EXPERIMENTAL_CXX0X__
351 push_front(_Tp&& __x)
352 { emplace_front(std::move(__x)); }
356 { emplace_back(std::move(__x)); }
358 template<typename... _Args>
360 emplace_front(_Args&&... __args)
362 _Base::emplace_front(std::forward<_Args>(__args)...);
363 this->_M_invalidate_all();
366 template<typename... _Args>
368 emplace_back(_Args&&... __args)
370 _Base::emplace_back(std::forward<_Args>(__args)...);
371 this->_M_invalidate_all();
374 template<typename... _Args>
376 emplace(iterator __position, _Args&&... __args)
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);
387 insert(iterator __position, const _Tp& __x)
389 __glibcxx_check_insert(__position);
390 _Base_iterator __res = _Base::insert(__position.base(), __x);
391 this->_M_invalidate_all();
392 return iterator(__res, this);
395 #ifdef __GXX_EXPERIMENTAL_CXX0X__
397 insert(iterator __position, _Tp&& __x)
398 { return emplace(__position, std::move(__x)); }
401 insert(iterator __p, initializer_list<value_type> __l)
403 _Base::insert(__p, __l);
404 this->_M_invalidate_all();
409 insert(iterator __position, size_type __n, const _Tp& __x)
411 __glibcxx_check_insert(__position);
412 _Base::insert(__position.base(), __n, __x);
413 this->_M_invalidate_all();
416 template<class _InputIterator>
418 insert(iterator __position,
419 _InputIterator __first, _InputIterator __last)
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();
430 __glibcxx_check_nonempty();
431 this->_M_invalidate_if(_Equal(_Base::begin()));
438 __glibcxx_check_nonempty();
439 this->_M_invalidate_if(_Equal(--_Base::end()));
444 erase(iterator __position)
446 __glibcxx_check_erase(__position);
447 _Base_iterator __victim = __position.base();
448 if (__victim == _Base::begin() || __victim == _Base::end()-1)
450 this->_M_invalidate_if(_Equal(__victim));
451 return iterator(_Base::erase(__victim), this);
455 _Base_iterator __res = _Base::erase(__victim);
456 this->_M_invalidate_all();
457 return iterator(__res, this);
462 erase(iterator __first, iterator __last)
464 // _GLIBCXX_RESOLVE_LIB_DEFECTS
465 // 151. can't currently clear() empty container
466 __glibcxx_check_erase_range(__first, __last);
468 if (__first.base() == __last.base())
470 else if (__first.base() == _Base::begin()
471 || __last.base() == _Base::end())
473 this->_M_detach_singular();
474 for (_Base_iterator __position = __first.base();
475 __position != __last.base(); ++__position)
477 this->_M_invalidate_if(_Equal(__position));
481 return iterator(_Base::erase(__first.base(), __last.base()),
486 this->_M_revalidate_singular();
487 __throw_exception_again;
492 _Base_iterator __res = _Base::erase(__first.base(),
494 this->_M_invalidate_all();
495 return iterator(__res, this);
507 clear() _GLIBCXX_NOEXCEPT
510 this->_M_invalidate_all();
514 _M_base() _GLIBCXX_NOEXCEPT { return *this; }
517 _M_base() const _GLIBCXX_NOEXCEPT { return *this; }
520 template<typename _Tp, typename _Alloc>
522 operator==(const deque<_Tp, _Alloc>& __lhs,
523 const deque<_Tp, _Alloc>& __rhs)
524 { return __lhs._M_base() == __rhs._M_base(); }
526 template<typename _Tp, typename _Alloc>
528 operator!=(const deque<_Tp, _Alloc>& __lhs,
529 const deque<_Tp, _Alloc>& __rhs)
530 { return __lhs._M_base() != __rhs._M_base(); }
532 template<typename _Tp, typename _Alloc>
534 operator<(const deque<_Tp, _Alloc>& __lhs,
535 const deque<_Tp, _Alloc>& __rhs)
536 { return __lhs._M_base() < __rhs._M_base(); }
538 template<typename _Tp, typename _Alloc>
540 operator<=(const deque<_Tp, _Alloc>& __lhs,
541 const deque<_Tp, _Alloc>& __rhs)
542 { return __lhs._M_base() <= __rhs._M_base(); }
544 template<typename _Tp, typename _Alloc>
546 operator>=(const deque<_Tp, _Alloc>& __lhs,
547 const deque<_Tp, _Alloc>& __rhs)
548 { return __lhs._M_base() >= __rhs._M_base(); }
550 template<typename _Tp, typename _Alloc>
552 operator>(const deque<_Tp, _Alloc>& __lhs,
553 const deque<_Tp, _Alloc>& __rhs)
554 { return __lhs._M_base() > __rhs._M_base(); }
556 template<typename _Tp, typename _Alloc>
558 swap(deque<_Tp, _Alloc>& __lhs, deque<_Tp, _Alloc>& __rhs)
559 { __lhs.swap(__rhs); }
561 } // namespace __debug