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
37namespace std _GLIBCXX_VISIBILITY(default)
38{
39namespace __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