libstdc++
debug/list
Go to the documentation of this file.
1 // Debugging list 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/list
27  * This file is a GNU debug extension to the Standard C++ Library.
28  */
29 
30 #ifndef _GLIBCXX_DEBUG_LIST
31 #define _GLIBCXX_DEBUG_LIST 1
32 
33 #include <list>
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::list with safety/checking/debug instrumentation.
42  template<typename _Tp, typename _Allocator = std::allocator<_Tp> >
43  class list
44  : public _GLIBCXX_STD_C::list<_Tp, _Allocator>,
45  public __gnu_debug::_Safe_sequence<list<_Tp, _Allocator> >
46  {
47  typedef _GLIBCXX_STD_C::list<_Tp, _Allocator> _Base;
48 
49  typedef typename _Base::iterator _Base_iterator;
50  typedef typename _Base::const_iterator _Base_const_iterator;
51  typedef __gnu_debug::_Equal_to<_Base_const_iterator> _Equal;
52  typedef __gnu_debug::_Not_equal_to<_Base_const_iterator> _Not_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, list>
58  iterator;
59  typedef __gnu_debug::_Safe_iterator<_Base_const_iterator, list>
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.2.1 construct/copy/destroy:
73  explicit
74  list(const _Allocator& __a = _Allocator())
75  : _Base(__a) { }
76 
77 #ifdef __GXX_EXPERIMENTAL_CXX0X__
78  explicit
79  list(size_type __n)
80  : _Base(__n) { }
81 
82  list(size_type __n, const _Tp& __value,
83  const _Allocator& __a = _Allocator())
84  : _Base(__n, __value, __a) { }
85 #else
86  explicit
87  list(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  list(_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 
101  list(const list& __x)
102  : _Base(__x) { }
103 
104  list(const _Base& __x)
105  : _Base(__x) { }
106 
107 #ifdef __GXX_EXPERIMENTAL_CXX0X__
108  list(list&& __x) noexcept
109  : _Base(std::move(__x))
110  { this->_M_swap(__x); }
111 
112  list(initializer_list<value_type> __l,
113  const allocator_type& __a = allocator_type())
114  : _Base(__l, __a) { }
115 #endif
116 
117  ~list() _GLIBCXX_NOEXCEPT { }
118 
119  list&
120  operator=(const list& __x)
121  {
122  static_cast<_Base&>(*this) = __x;
123  this->_M_invalidate_all();
124  return *this;
125  }
126 
127 #ifdef __GXX_EXPERIMENTAL_CXX0X__
128  list&
129  operator=(list&& __x)
130  {
131  // NB: DR 1204.
132  // NB: DR 675.
133  clear();
134  swap(__x);
135  return *this;
136  }
137 
138  list&
139  operator=(initializer_list<value_type> __l)
140  {
141  static_cast<_Base&>(*this) = __l;
142  this->_M_invalidate_all();
143  return *this;
144  }
145 
146  void
147  assign(initializer_list<value_type> __l)
148  {
149  _Base::assign(__l);
150  this->_M_invalidate_all();
151  }
152 #endif
153 
154  template<class _InputIterator>
155  void
156  assign(_InputIterator __first, _InputIterator __last)
157  {
158  __glibcxx_check_valid_range(__first, __last);
159  _Base::assign(__gnu_debug::__base(__first),
160  __gnu_debug::__base(__last));
161  this->_M_invalidate_all();
162  }
163 
164  void
165  assign(size_type __n, const _Tp& __t)
166  {
167  _Base::assign(__n, __t);
168  this->_M_invalidate_all();
169  }
170 
171  using _Base::get_allocator;
172 
173  // iterators:
174  iterator
175  begin() _GLIBCXX_NOEXCEPT
176  { return iterator(_Base::begin(), this); }
177 
178  const_iterator
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 
186  const_iterator
187  end() const _GLIBCXX_NOEXCEPT
188  { return const_iterator(_Base::end(), this); }
189 
190  reverse_iterator
191  rbegin() _GLIBCXX_NOEXCEPT
192  { return reverse_iterator(end()); }
193 
194  const_reverse_iterator
195  rbegin() const _GLIBCXX_NOEXCEPT
196  { return const_reverse_iterator(end()); }
197 
198  reverse_iterator
199  rend() _GLIBCXX_NOEXCEPT
200  { return reverse_iterator(begin()); }
201 
202  const_reverse_iterator
203  rend() const _GLIBCXX_NOEXCEPT
204  { return const_reverse_iterator(begin()); }
205 
206 #ifdef __GXX_EXPERIMENTAL_CXX0X__
207  const_iterator
208  cbegin() const noexcept
209  { return const_iterator(_Base::begin(), this); }
210 
211  const_iterator
212  cend() const noexcept
213  { return const_iterator(_Base::end(), this); }
214 
215  const_reverse_iterator
216  crbegin() const noexcept
217  { return const_reverse_iterator(end()); }
218 
219  const_reverse_iterator
220  crend() const noexcept
221  { return const_reverse_iterator(begin()); }
222 #endif
223 
224  // 23.2.2.2 capacity:
225  using _Base::empty;
226  using _Base::size;
227  using _Base::max_size;
228 
229 #ifdef __GXX_EXPERIMENTAL_CXX0X__
230  void
231  resize(size_type __sz)
232  {
233  this->_M_detach_singular();
234 
235  // if __sz < size(), invalidate all iterators in [begin+__sz, end())
236  _Base_iterator __victim = _Base::begin();
237  _Base_iterator __end = _Base::end();
238  for (size_type __i = __sz; __victim != __end && __i > 0; --__i)
239  ++__victim;
240 
241  for (; __victim != __end; ++__victim)
242  {
243  this->_M_invalidate_if(_Equal(__victim));
244  }
245 
246  __try
247  {
248  _Base::resize(__sz);
249  }
250  __catch(...)
251  {
252  this->_M_revalidate_singular();
253  __throw_exception_again;
254  }
255  }
256 
257  void
258  resize(size_type __sz, const _Tp& __c)
259  {
260  this->_M_detach_singular();
261 
262  // if __sz < size(), invalidate all iterators in [begin+__sz, end())
263  _Base_iterator __victim = _Base::begin();
264  _Base_iterator __end = _Base::end();
265  for (size_type __i = __sz; __victim != __end && __i > 0; --__i)
266  ++__victim;
267 
268  for (; __victim != __end; ++__victim)
269  {
270  this->_M_invalidate_if(_Equal(__victim));
271  }
272 
273  __try
274  {
275  _Base::resize(__sz, __c);
276  }
277  __catch(...)
278  {
279  this->_M_revalidate_singular();
280  __throw_exception_again;
281  }
282  }
283 #else
284  void
285  resize(size_type __sz, _Tp __c = _Tp())
286  {
287  this->_M_detach_singular();
288 
289  // if __sz < size(), invalidate all iterators in [begin+__sz, end())
290  _Base_iterator __victim = _Base::begin();
291  _Base_iterator __end = _Base::end();
292  for (size_type __i = __sz; __victim != __end && __i > 0; --__i)
293  ++__victim;
294 
295  for (; __victim != __end; ++__victim)
296  {
297  this->_M_invalidate_if(_Equal(__victim));
298  }
299 
300  __try
301  {
302  _Base::resize(__sz, __c);
303  }
304  __catch(...)
305  {
306  this->_M_revalidate_singular();
307  __throw_exception_again;
308  }
309  }
310 #endif
311 
312  // element access:
313  reference
314  front()
315  {
316  __glibcxx_check_nonempty();
317  return _Base::front();
318  }
319 
320  const_reference
321  front() const
322  {
323  __glibcxx_check_nonempty();
324  return _Base::front();
325  }
326 
327  reference
328  back()
329  {
330  __glibcxx_check_nonempty();
331  return _Base::back();
332  }
333 
334  const_reference
335  back() const
336  {
337  __glibcxx_check_nonempty();
338  return _Base::back();
339  }
340 
341  // 23.2.2.3 modifiers:
342  using _Base::push_front;
343 
344 #ifdef __GXX_EXPERIMENTAL_CXX0X__
345  using _Base::emplace_front;
346 #endif
347 
348  void
349  pop_front()
350  {
351  __glibcxx_check_nonempty();
352  this->_M_invalidate_if(_Equal(_Base::begin()));
353  _Base::pop_front();
354  }
355 
356  using _Base::push_back;
357 
358 #ifdef __GXX_EXPERIMENTAL_CXX0X__
359  using _Base::emplace_back;
360 #endif
361 
362  void
363  pop_back()
364  {
365  __glibcxx_check_nonempty();
366  this->_M_invalidate_if(_Equal(--_Base::end()));
367  _Base::pop_back();
368  }
369 
370 #ifdef __GXX_EXPERIMENTAL_CXX0X__
371  template<typename... _Args>
372  iterator
373  emplace(iterator __position, _Args&&... __args)
374  {
375  __glibcxx_check_insert(__position);
376  return iterator(_Base::emplace(__position.base(),
377  std::forward<_Args>(__args)...), this);
378  }
379 #endif
380 
381  iterator
382  insert(iterator __position, const _Tp& __x)
383  {
384  __glibcxx_check_insert(__position);
385  return iterator(_Base::insert(__position.base(), __x), this);
386  }
387 
388 #ifdef __GXX_EXPERIMENTAL_CXX0X__
389  iterator
390  insert(iterator __position, _Tp&& __x)
391  { return emplace(__position, std::move(__x)); }
392 
393  void
394  insert(iterator __p, initializer_list<value_type> __l)
395  {
396  __glibcxx_check_insert(__p);
397  _Base::insert(__p.base(), __l);
398  }
399 #endif
400 
401  void
402  insert(iterator __position, size_type __n, const _Tp& __x)
403  {
404  __glibcxx_check_insert(__position);
405  _Base::insert(__position.base(), __n, __x);
406  }
407 
408  template<class _InputIterator>
409  void
410  insert(iterator __position, _InputIterator __first,
411  _InputIterator __last)
412  {
413  __glibcxx_check_insert_range(__position, __first, __last);
414  _Base::insert(__position.base(), __gnu_debug::__base(__first),
415  __gnu_debug::__base(__last));
416  }
417 
418  private:
419  _Base_iterator
420  _M_erase(_Base_iterator __position)
421  {
422  this->_M_invalidate_if(_Equal(__position));
423  return _Base::erase(__position);
424  }
425  public:
426  iterator
427  erase(iterator __position)
428  {
429  __glibcxx_check_erase(__position);
430  return iterator(_M_erase(__position.base()), this);
431  }
432 
433  iterator
434  erase(iterator __position, iterator __last)
435  {
436  // _GLIBCXX_RESOLVE_LIB_DEFECTS
437  // 151. can't currently clear() empty container
438  __glibcxx_check_erase_range(__position, __last);
439  for (_Base_iterator __victim = __position.base();
440  __victim != __last.base(); ++__victim)
441  {
442  _GLIBCXX_DEBUG_VERIFY(__victim != _Base::end(),
443  _M_message(__gnu_debug::__msg_valid_range)
444  ._M_iterator(__position, "position")
445  ._M_iterator(__last, "last"));
446  this->_M_invalidate_if(_Equal(__victim));
447  }
448  return iterator(_Base::erase(__position.base(), __last.base()), this);
449  }
450 
451  void
452  swap(list& __x)
453  {
454  _Base::swap(__x);
455  this->_M_swap(__x);
456  }
457 
458  void
459  clear() _GLIBCXX_NOEXCEPT
460  {
461  _Base::clear();
462  this->_M_invalidate_all();
463  }
464 
465  // 23.2.2.4 list operations:
466  void
467 #ifdef __GXX_EXPERIMENTAL_CXX0X__
468  splice(iterator __position, list&& __x)
469 #else
470  splice(iterator __position, list& __x)
471 #endif
472  {
473  _GLIBCXX_DEBUG_VERIFY(&__x != this,
474  _M_message(__gnu_debug::__msg_self_splice)
475  ._M_sequence(*this, "this"));
476  this->_M_transfer_from_if(__x, _Not_equal(__x._M_base().end()));
477  _Base::splice(__position.base(), _GLIBCXX_MOVE(__x._M_base()));
478  }
479 
480 #ifdef __GXX_EXPERIMENTAL_CXX0X__
481  void
482  splice(iterator __position, list& __x)
483  { splice(__position, std::move(__x)); }
484 #endif
485 
486  void
487 #ifdef __GXX_EXPERIMENTAL_CXX0X__
488  splice(iterator __position, list&& __x, iterator __i)
489 #else
490  splice(iterator __position, list& __x, iterator __i)
491 #endif
492  {
493  __glibcxx_check_insert(__position);
494 
495  // We used to perform the splice_alloc check: not anymore, redundant
496  // after implementing the relevant bits of N1599.
497 
498  _GLIBCXX_DEBUG_VERIFY(__i._M_dereferenceable(),
499  _M_message(__gnu_debug::__msg_splice_bad)
500  ._M_iterator(__i, "__i"));
501  _GLIBCXX_DEBUG_VERIFY(__i._M_attached_to(&__x),
502  _M_message(__gnu_debug::__msg_splice_other)
503  ._M_iterator(__i, "__i")._M_sequence(__x, "__x"));
504 
505  // _GLIBCXX_RESOLVE_LIB_DEFECTS
506  // 250. splicing invalidates iterators
507  this->_M_transfer_from_if(__x, _Equal(__i.base()));
508  _Base::splice(__position.base(), _GLIBCXX_MOVE(__x._M_base()),
509  __i.base());
510  }
511 
512 #ifdef __GXX_EXPERIMENTAL_CXX0X__
513  void
514  splice(iterator __position, list& __x, iterator __i)
515  { splice(__position, std::move(__x), __i); }
516 #endif
517 
518  void
519 #ifdef __GXX_EXPERIMENTAL_CXX0X__
520  splice(iterator __position, list&& __x, iterator __first,
521  iterator __last)
522 #else
523  splice(iterator __position, list& __x, iterator __first,
524  iterator __last)
525 #endif
526  {
527  __glibcxx_check_insert(__position);
528  __glibcxx_check_valid_range(__first, __last);
529  _GLIBCXX_DEBUG_VERIFY(__first._M_attached_to(&__x),
530  _M_message(__gnu_debug::__msg_splice_other)
531  ._M_sequence(__x, "x")
532  ._M_iterator(__first, "first"));
533 
534  // We used to perform the splice_alloc check: not anymore, redundant
535  // after implementing the relevant bits of N1599.
536 
537  for (_Base_iterator __tmp = __first.base();
538  __tmp != __last.base(); ++__tmp)
539  {
540  _GLIBCXX_DEBUG_VERIFY(__tmp != _Base::end(),
541  _M_message(__gnu_debug::__msg_valid_range)
542  ._M_iterator(__first, "first")
543  ._M_iterator(__last, "last"));
544  _GLIBCXX_DEBUG_VERIFY(&__x != this || __tmp != __position,
545  _M_message(__gnu_debug::__msg_splice_overlap)
546  ._M_iterator(__tmp, "position")
547  ._M_iterator(__first, "first")
548  ._M_iterator(__last, "last"));
549  // _GLIBCXX_RESOLVE_LIB_DEFECTS
550  // 250. splicing invalidates iterators
551  this->_M_transfer_from_if(__x, _Equal(__tmp));
552  }
553 
554  _Base::splice(__position.base(), _GLIBCXX_MOVE(__x._M_base()),
555  __first.base(), __last.base());
556  }
557 
558 #ifdef __GXX_EXPERIMENTAL_CXX0X__
559  void
560  splice(iterator __position, list& __x, iterator __first, iterator __last)
561  { splice(__position, std::move(__x), __first, __last); }
562 #endif
563 
564  void
565  remove(const _Tp& __value)
566  {
567  for (_Base_iterator __x = _Base::begin(); __x != _Base::end(); )
568  {
569  if (*__x == __value)
570  __x = _M_erase(__x);
571  else
572  ++__x;
573  }
574  }
575 
576  template<class _Predicate>
577  void
578  remove_if(_Predicate __pred)
579  {
580  for (_Base_iterator __x = _Base::begin(); __x != _Base::end(); )
581  {
582  if (__pred(*__x))
583  __x = _M_erase(__x);
584  else
585  ++__x;
586  }
587  }
588 
589  void
590  unique()
591  {
592  _Base_iterator __first = _Base::begin();
593  _Base_iterator __last = _Base::end();
594  if (__first == __last)
595  return;
596  _Base_iterator __next = __first; ++__next;
597  while (__next != __last)
598  {
599  if (*__first == *__next)
600  __next = _M_erase(__next);
601  else
602  __first = __next++;
603  }
604  }
605 
606  template<class _BinaryPredicate>
607  void
608  unique(_BinaryPredicate __binary_pred)
609  {
610  _Base_iterator __first = _Base::begin();
611  _Base_iterator __last = _Base::end();
612  if (__first == __last)
613  return;
614  _Base_iterator __next = __first; ++__next;
615  while (__next != __last)
616  {
617  if (__binary_pred(*__first, *__next))
618  __next = _M_erase(__next);
619  else
620  __first = __next++;
621  }
622  }
623 
624  void
625 #ifdef __GXX_EXPERIMENTAL_CXX0X__
626  merge(list&& __x)
627 #else
628  merge(list& __x)
629 #endif
630  {
631  // _GLIBCXX_RESOLVE_LIB_DEFECTS
632  // 300. list::merge() specification incomplete
633  if (this != &__x)
634  {
635  __glibcxx_check_sorted(_Base::begin(), _Base::end());
636  __glibcxx_check_sorted(__x.begin().base(), __x.end().base());
637  this->_M_transfer_from_if(__x, _Not_equal(__x._M_base().end()));
638  _Base::merge(_GLIBCXX_MOVE(__x._M_base()));
639  }
640  }
641 
642 #ifdef __GXX_EXPERIMENTAL_CXX0X__
643  void
644  merge(list& __x)
645  { merge(std::move(__x)); }
646 #endif
647 
648  template<class _Compare>
649  void
650 #ifdef __GXX_EXPERIMENTAL_CXX0X__
651  merge(list&& __x, _Compare __comp)
652 #else
653  merge(list& __x, _Compare __comp)
654 #endif
655  {
656  // _GLIBCXX_RESOLVE_LIB_DEFECTS
657  // 300. list::merge() specification incomplete
658  if (this != &__x)
659  {
660  __glibcxx_check_sorted_pred(_Base::begin(), _Base::end(),
661  __comp);
662  __glibcxx_check_sorted_pred(__x.begin().base(), __x.end().base(),
663  __comp);
664  this->_M_transfer_from_if(__x, _Not_equal(__x._M_base().end()));
665  _Base::merge(_GLIBCXX_MOVE(__x._M_base()), __comp);
666  }
667  }
668 
669 #ifdef __GXX_EXPERIMENTAL_CXX0X__
670  template<typename _Compare>
671  void
672  merge(list& __x, _Compare __comp)
673  { merge(std::move(__x), __comp); }
674 #endif
675 
676  void
677  sort() { _Base::sort(); }
678 
679  template<typename _StrictWeakOrdering>
680  void
681  sort(_StrictWeakOrdering __pred) { _Base::sort(__pred); }
682 
683  using _Base::reverse;
684 
685  _Base&
686  _M_base() _GLIBCXX_NOEXCEPT { return *this; }
687 
688  const _Base&
689  _M_base() const _GLIBCXX_NOEXCEPT { return *this; }
690 
691  private:
692  void
693  _M_invalidate_all()
694  {
695  this->_M_invalidate_if(_Not_equal(_Base::end()));
696  }
697  };
698 
699  template<typename _Tp, typename _Alloc>
700  inline bool
701  operator==(const list<_Tp, _Alloc>& __lhs,
702  const list<_Tp, _Alloc>& __rhs)
703  { return __lhs._M_base() == __rhs._M_base(); }
704 
705  template<typename _Tp, typename _Alloc>
706  inline bool
707  operator!=(const list<_Tp, _Alloc>& __lhs,
708  const list<_Tp, _Alloc>& __rhs)
709  { return __lhs._M_base() != __rhs._M_base(); }
710 
711  template<typename _Tp, typename _Alloc>
712  inline bool
713  operator<(const list<_Tp, _Alloc>& __lhs,
714  const list<_Tp, _Alloc>& __rhs)
715  { return __lhs._M_base() < __rhs._M_base(); }
716 
717  template<typename _Tp, typename _Alloc>
718  inline bool
719  operator<=(const list<_Tp, _Alloc>& __lhs,
720  const list<_Tp, _Alloc>& __rhs)
721  { return __lhs._M_base() <= __rhs._M_base(); }
722 
723  template<typename _Tp, typename _Alloc>
724  inline bool
725  operator>=(const list<_Tp, _Alloc>& __lhs,
726  const list<_Tp, _Alloc>& __rhs)
727  { return __lhs._M_base() >= __rhs._M_base(); }
728 
729  template<typename _Tp, typename _Alloc>
730  inline bool
731  operator>(const list<_Tp, _Alloc>& __lhs,
732  const list<_Tp, _Alloc>& __rhs)
733  { return __lhs._M_base() > __rhs._M_base(); }
734 
735  template<typename _Tp, typename _Alloc>
736  inline void
737  swap(list<_Tp, _Alloc>& __lhs, list<_Tp, _Alloc>& __rhs)
738  { __lhs.swap(__rhs); }
739 
740 } // namespace __debug
741 } // namespace std
742 
743 #endif