libstdc++
debug/vector
Go to the documentation of this file.
1 // Debugging vector 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/vector
27  * This file is a GNU debug extension to the Standard C++ Library.
28  */
29 
30 #ifndef _GLIBCXX_DEBUG_VECTOR
31 #define _GLIBCXX_DEBUG_VECTOR 1
32 
33 #include <vector>
34 #include <utility>
35 #include <debug/safe_sequence.h>
36 #include <debug/safe_iterator.h>
37 
38 namespace std _GLIBCXX_VISIBILITY(default)
39 {
40 namespace __debug
41 {
42  /// Class std::vector with safety/checking/debug instrumentation.
43  template<typename _Tp,
44  typename _Allocator = std::allocator<_Tp> >
45  class vector
46  : public _GLIBCXX_STD_C::vector<_Tp, _Allocator>,
47  public __gnu_debug::_Safe_sequence<vector<_Tp, _Allocator> >
48  {
49  typedef _GLIBCXX_STD_C::vector<_Tp, _Allocator> _Base;
50 
51  typedef typename _Base::iterator _Base_iterator;
52  typedef typename _Base::const_iterator _Base_const_iterator;
53  typedef __gnu_debug::_Equal_to<_Base_const_iterator> _Equal;
54 
55 #ifdef __GXX_EXPERIMENTAL_CXX0X__
56  typedef __gnu_cxx::__alloc_traits<_Allocator> _Alloc_traits;
57 #endif
58 
59  public:
60  typedef typename _Base::reference reference;
61  typedef typename _Base::const_reference const_reference;
62 
63  typedef __gnu_debug::_Safe_iterator<_Base_iterator,vector>
64  iterator;
65  typedef __gnu_debug::_Safe_iterator<_Base_const_iterator,vector>
66  const_iterator;
67 
68  typedef typename _Base::size_type size_type;
69  typedef typename _Base::difference_type difference_type;
70 
71  typedef _Tp value_type;
72  typedef _Allocator allocator_type;
73  typedef typename _Base::pointer pointer;
74  typedef typename _Base::const_pointer const_pointer;
75  typedef std::reverse_iterator<iterator> reverse_iterator;
76  typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
77 
78  // 23.2.4.1 construct/copy/destroy:
79  explicit
80  vector(const _Allocator& __a = _Allocator())
81  : _Base(__a), _M_guaranteed_capacity(0) { }
82 
83 #ifdef __GXX_EXPERIMENTAL_CXX0X__
84  explicit
85  vector(size_type __n)
86  : _Base(__n), _M_guaranteed_capacity(__n) { }
87 
88  vector(size_type __n, const _Tp& __value,
89  const _Allocator& __a = _Allocator())
90  : _Base(__n, __value, __a), _M_guaranteed_capacity(__n) { }
91 #else
92  explicit
93  vector(size_type __n, const _Tp& __value = _Tp(),
94  const _Allocator& __a = _Allocator())
95  : _Base(__n, __value, __a), _M_guaranteed_capacity(__n) { }
96 #endif
97 
98  template<class _InputIterator>
99  vector(_InputIterator __first, _InputIterator __last,
100  const _Allocator& __a = _Allocator())
101  : _Base(__gnu_debug::__base(__gnu_debug::__check_valid_range(__first,
102  __last)),
103  __gnu_debug::__base(__last), __a),
104  _M_guaranteed_capacity(0)
105  { _M_update_guaranteed_capacity(); }
106 
107  vector(const vector& __x)
108  : _Base(__x), _M_guaranteed_capacity(__x.size()) { }
109 
110  /// Construction from a release-mode vector
111  vector(const _Base& __x)
112  : _Base(__x), _M_guaranteed_capacity(__x.size()) { }
113 
114 #ifdef __GXX_EXPERIMENTAL_CXX0X__
115  vector(vector&& __x) noexcept
116  : _Base(std::move(__x)),
117  _M_guaranteed_capacity(this->size())
118  {
119  this->_M_swap(__x);
120  __x._M_guaranteed_capacity = 0;
121  }
122 
123  vector(const vector& __x, const allocator_type& __a)
124  : _Base(__x, __a), _M_guaranteed_capacity(__x.size()) { }
125 
126  vector(vector&& __x, const allocator_type& __a)
127  : _Base(std::move(__x), __a),
128  _M_guaranteed_capacity(this->size())
129  {
130  __x._M_invalidate_all();
131  __x._M_guaranteed_capacity = 0;
132  }
133 
134  vector(initializer_list<value_type> __l,
135  const allocator_type& __a = allocator_type())
136  : _Base(__l, __a),
137  _M_guaranteed_capacity(__l.size()) { }
138 #endif
139 
140  ~vector() _GLIBCXX_NOEXCEPT { }
141 
142  vector&
143  operator=(const vector& __x)
144  {
145  static_cast<_Base&>(*this) = __x;
146  this->_M_invalidate_all();
147  _M_update_guaranteed_capacity();
148  return *this;
149  }
150 
151 #ifdef __GXX_EXPERIMENTAL_CXX0X__
152  vector&
153  operator=(vector&& __x) noexcept(_Alloc_traits::_S_nothrow_move())
154  {
155  _Base::operator=(std::move(__x));
156  this->_M_invalidate_all();
157  _M_update_guaranteed_capacity();
158  __x._M_invalidate_all();
159  __x._M_guaranteed_capacity = 0;
160  return *this;
161  }
162 
163  vector&
164  operator=(initializer_list<value_type> __l)
165  {
166  static_cast<_Base&>(*this) = __l;
167  this->_M_invalidate_all();
168  _M_update_guaranteed_capacity();
169  return *this;
170  }
171 #endif
172 
173  template<typename _InputIterator>
174  void
175  assign(_InputIterator __first, _InputIterator __last)
176  {
177  __glibcxx_check_valid_range(__first, __last);
178  _Base::assign(__gnu_debug::__base(__first),
179  __gnu_debug::__base(__last));
180  this->_M_invalidate_all();
181  _M_update_guaranteed_capacity();
182  }
183 
184  void
185  assign(size_type __n, const _Tp& __u)
186  {
187  _Base::assign(__n, __u);
188  this->_M_invalidate_all();
189  _M_update_guaranteed_capacity();
190  }
191 
192 #ifdef __GXX_EXPERIMENTAL_CXX0X__
193  void
194  assign(initializer_list<value_type> __l)
195  {
196  _Base::assign(__l);
197  this->_M_invalidate_all();
198  _M_update_guaranteed_capacity();
199  }
200 #endif
201 
202  using _Base::get_allocator;
203 
204  // iterators:
205  iterator
206  begin() _GLIBCXX_NOEXCEPT
207  { return iterator(_Base::begin(), this); }
208 
209  const_iterator
210  begin() const _GLIBCXX_NOEXCEPT
211  { return const_iterator(_Base::begin(), this); }
212 
213  iterator
214  end() _GLIBCXX_NOEXCEPT
215  { return iterator(_Base::end(), this); }
216 
217  const_iterator
218  end() const _GLIBCXX_NOEXCEPT
219  { return const_iterator(_Base::end(), this); }
220 
221  reverse_iterator
222  rbegin() _GLIBCXX_NOEXCEPT
223  { return reverse_iterator(end()); }
224 
225  const_reverse_iterator
226  rbegin() const _GLIBCXX_NOEXCEPT
227  { return const_reverse_iterator(end()); }
228 
229  reverse_iterator
230  rend() _GLIBCXX_NOEXCEPT
231  { return reverse_iterator(begin()); }
232 
233  const_reverse_iterator
234  rend() const _GLIBCXX_NOEXCEPT
235  { return const_reverse_iterator(begin()); }
236 
237 #ifdef __GXX_EXPERIMENTAL_CXX0X__
238  const_iterator
239  cbegin() const noexcept
240  { return const_iterator(_Base::begin(), this); }
241 
242  const_iterator
243  cend() const noexcept
244  { return const_iterator(_Base::end(), this); }
245 
246  const_reverse_iterator
247  crbegin() const noexcept
248  { return const_reverse_iterator(end()); }
249 
250  const_reverse_iterator
251  crend() const noexcept
252  { return const_reverse_iterator(begin()); }
253 #endif
254 
255  // 23.2.4.2 capacity:
256  using _Base::size;
257  using _Base::max_size;
258 
259 #ifdef __GXX_EXPERIMENTAL_CXX0X__
260  void
261  resize(size_type __sz)
262  {
263  bool __realloc = _M_requires_reallocation(__sz);
264  if (__sz < this->size())
265  this->_M_invalidate_after_nth(__sz);
266  _Base::resize(__sz);
267  if (__realloc)
268  this->_M_invalidate_all();
269  _M_update_guaranteed_capacity();
270  }
271 
272  void
273  resize(size_type __sz, const _Tp& __c)
274  {
275  bool __realloc = _M_requires_reallocation(__sz);
276  if (__sz < this->size())
277  this->_M_invalidate_after_nth(__sz);
278  _Base::resize(__sz, __c);
279  if (__realloc)
280  this->_M_invalidate_all();
281  _M_update_guaranteed_capacity();
282  }
283 #else
284  void
285  resize(size_type __sz, _Tp __c = _Tp())
286  {
287  bool __realloc = _M_requires_reallocation(__sz);
288  if (__sz < this->size())
289  this->_M_invalidate_after_nth(__sz);
290  _Base::resize(__sz, __c);
291  if (__realloc)
292  this->_M_invalidate_all();
293  _M_update_guaranteed_capacity();
294  }
295 #endif
296 
297 #ifdef __GXX_EXPERIMENTAL_CXX0X__
298  void
299  shrink_to_fit()
300  {
301  if (_Base::_M_shrink_to_fit())
302  {
303  _M_guaranteed_capacity = _Base::capacity();
304  this->_M_invalidate_all();
305  }
306  }
307 #endif
308 
309  size_type
310  capacity() const _GLIBCXX_NOEXCEPT
311  {
312 #ifdef _GLIBCXX_DEBUG_PEDANTIC
313  return _M_guaranteed_capacity;
314 #else
315  return _Base::capacity();
316 #endif
317  }
318 
319  using _Base::empty;
320 
321  void
322  reserve(size_type __n)
323  {
324  bool __realloc = _M_requires_reallocation(__n);
325  _Base::reserve(__n);
326  if (__n > _M_guaranteed_capacity)
327  _M_guaranteed_capacity = __n;
328  if (__realloc)
329  this->_M_invalidate_all();
330  }
331 
332  // element access:
333  reference
334  operator[](size_type __n)
335  {
336  __glibcxx_check_subscript(__n);
337  return _M_base()[__n];
338  }
339 
340  const_reference
341  operator[](size_type __n) const
342  {
343  __glibcxx_check_subscript(__n);
344  return _M_base()[__n];
345  }
346 
347  using _Base::at;
348 
349  reference
350  front()
351  {
352  __glibcxx_check_nonempty();
353  return _Base::front();
354  }
355 
356  const_reference
357  front() const
358  {
359  __glibcxx_check_nonempty();
360  return _Base::front();
361  }
362 
363  reference
364  back()
365  {
366  __glibcxx_check_nonempty();
367  return _Base::back();
368  }
369 
370  const_reference
371  back() const
372  {
373  __glibcxx_check_nonempty();
374  return _Base::back();
375  }
376 
377  // _GLIBCXX_RESOLVE_LIB_DEFECTS
378  // DR 464. Suggestion for new member functions in standard containers.
379  using _Base::data;
380 
381  // 23.2.4.3 modifiers:
382  void
383  push_back(const _Tp& __x)
384  {
385  bool __realloc = _M_requires_reallocation(this->size() + 1);
386  _Base::push_back(__x);
387  if (__realloc)
388  this->_M_invalidate_all();
389  _M_update_guaranteed_capacity();
390  }
391 
392 #ifdef __GXX_EXPERIMENTAL_CXX0X__
393  template<typename _Up = _Tp>
394  typename __gnu_cxx::__enable_if<!std::__are_same<_Up, bool>::__value,
395  void>::__type
396  push_back(_Tp&& __x)
397  { emplace_back(std::move(__x)); }
398 
399  template<typename... _Args>
400  void
401  emplace_back(_Args&&... __args)
402  {
403  bool __realloc = _M_requires_reallocation(this->size() + 1);
404  _Base::emplace_back(std::forward<_Args>(__args)...);
405  if (__realloc)
406  this->_M_invalidate_all();
407  _M_update_guaranteed_capacity();
408  }
409 #endif
410 
411  void
412  pop_back()
413  {
414  __glibcxx_check_nonempty();
415  this->_M_invalidate_if(_Equal(--_Base::end()));
416  _Base::pop_back();
417  }
418 
419 #ifdef __GXX_EXPERIMENTAL_CXX0X__
420  template<typename... _Args>
421  iterator
422  emplace(iterator __position, _Args&&... __args)
423  {
424  __glibcxx_check_insert(__position);
425  bool __realloc = _M_requires_reallocation(this->size() + 1);
426  difference_type __offset = __position.base() - _Base::begin();
427  _Base_iterator __res = _Base::emplace(__position.base(),
428  std::forward<_Args>(__args)...);
429  if (__realloc)
430  this->_M_invalidate_all();
431  else
432  this->_M_invalidate_after_nth(__offset);
433  _M_update_guaranteed_capacity();
434  return iterator(__res, this);
435  }
436 #endif
437 
438  iterator
439  insert(iterator __position, const _Tp& __x)
440  {
441  __glibcxx_check_insert(__position);
442  bool __realloc = _M_requires_reallocation(this->size() + 1);
443  difference_type __offset = __position.base() - _Base::begin();
444  _Base_iterator __res = _Base::insert(__position.base(), __x);
445  if (__realloc)
446  this->_M_invalidate_all();
447  else
448  this->_M_invalidate_after_nth(__offset);
449  _M_update_guaranteed_capacity();
450  return iterator(__res, this);
451  }
452 
453 #ifdef __GXX_EXPERIMENTAL_CXX0X__
454  template<typename _Up = _Tp>
455  typename __gnu_cxx::__enable_if<!std::__are_same<_Up, bool>::__value,
456  iterator>::__type
457  insert(iterator __position, _Tp&& __x)
458  { return emplace(__position, std::move(__x)); }
459 
460  void
461  insert(iterator __position, initializer_list<value_type> __l)
462  { this->insert(__position, __l.begin(), __l.end()); }
463 #endif
464 
465  void
466  insert(iterator __position, size_type __n, const _Tp& __x)
467  {
468  __glibcxx_check_insert(__position);
469  bool __realloc = _M_requires_reallocation(this->size() + __n);
470  difference_type __offset = __position.base() - _Base::begin();
471  _Base::insert(__position.base(), __n, __x);
472  if (__realloc)
473  this->_M_invalidate_all();
474  else
475  this->_M_invalidate_after_nth(__offset);
476  _M_update_guaranteed_capacity();
477  }
478 
479  template<class _InputIterator>
480  void
481  insert(iterator __position,
482  _InputIterator __first, _InputIterator __last)
483  {
484  __glibcxx_check_insert_range(__position, __first, __last);
485 
486  /* Hard to guess if invalidation will occur, because __last
487  - __first can't be calculated in all cases, so we just
488  punt here by checking if it did occur. */
489  _Base_iterator __old_begin = _M_base().begin();
490  difference_type __offset = __position.base() - _Base::begin();
491  _Base::insert(__position.base(), __gnu_debug::__base(__first),
492  __gnu_debug::__base(__last));
493 
494  if (_M_base().begin() != __old_begin)
495  this->_M_invalidate_all();
496  else
497  this->_M_invalidate_after_nth(__offset);
498  _M_update_guaranteed_capacity();
499  }
500 
501  iterator
502  erase(iterator __position)
503  {
504  __glibcxx_check_erase(__position);
505  difference_type __offset = __position.base() - _Base::begin();
506  _Base_iterator __res = _Base::erase(__position.base());
507  this->_M_invalidate_after_nth(__offset);
508  return iterator(__res, this);
509  }
510 
511  iterator
512  erase(iterator __first, iterator __last)
513  {
514  // _GLIBCXX_RESOLVE_LIB_DEFECTS
515  // 151. can't currently clear() empty container
516  __glibcxx_check_erase_range(__first, __last);
517 
518  if (__first.base() != __last.base())
519  {
520  difference_type __offset = __first.base() - _Base::begin();
521  _Base_iterator __res = _Base::erase(__first.base(),
522  __last.base());
523  this->_M_invalidate_after_nth(__offset);
524  return iterator(__res, this);
525  }
526  else
527  return __first;
528  }
529 
530  void
531  swap(vector& __x)
532 #ifdef __GXX_EXPERIMENTAL_CXX0X__
533  noexcept(_Alloc_traits::_S_nothrow_swap())
534 #endif
535  {
536  _Base::swap(__x);
537  this->_M_swap(__x);
538  std::swap(_M_guaranteed_capacity, __x._M_guaranteed_capacity);
539  }
540 
541  void
542  clear() _GLIBCXX_NOEXCEPT
543  {
544  _Base::clear();
545  this->_M_invalidate_all();
546  _M_guaranteed_capacity = 0;
547  }
548 
549  _Base&
550  _M_base() _GLIBCXX_NOEXCEPT { return *this; }
551 
552  const _Base&
553  _M_base() const _GLIBCXX_NOEXCEPT { return *this; }
554 
555  private:
556  size_type _M_guaranteed_capacity;
557 
558  bool
559  _M_requires_reallocation(size_type __elements)
560  { return __elements > this->capacity(); }
561 
562  void
563  _M_update_guaranteed_capacity()
564  {
565  if (this->size() > _M_guaranteed_capacity)
566  _M_guaranteed_capacity = this->size();
567  }
568 
569  void
570  _M_invalidate_after_nth(difference_type __n)
571  {
572  typedef __gnu_debug::_After_nth_from<_Base_const_iterator> _After_nth;
573  this->_M_invalidate_if(_After_nth(__n, _Base::begin()));
574  }
575  };
576 
577  template<typename _Tp, typename _Alloc>
578  inline bool
579  operator==(const vector<_Tp, _Alloc>& __lhs,
580  const vector<_Tp, _Alloc>& __rhs)
581  { return __lhs._M_base() == __rhs._M_base(); }
582 
583  template<typename _Tp, typename _Alloc>
584  inline bool
585  operator!=(const vector<_Tp, _Alloc>& __lhs,
586  const vector<_Tp, _Alloc>& __rhs)
587  { return __lhs._M_base() != __rhs._M_base(); }
588 
589  template<typename _Tp, typename _Alloc>
590  inline bool
591  operator<(const vector<_Tp, _Alloc>& __lhs,
592  const vector<_Tp, _Alloc>& __rhs)
593  { return __lhs._M_base() < __rhs._M_base(); }
594 
595  template<typename _Tp, typename _Alloc>
596  inline bool
597  operator<=(const vector<_Tp, _Alloc>& __lhs,
598  const vector<_Tp, _Alloc>& __rhs)
599  { return __lhs._M_base() <= __rhs._M_base(); }
600 
601  template<typename _Tp, typename _Alloc>
602  inline bool
603  operator>=(const vector<_Tp, _Alloc>& __lhs,
604  const vector<_Tp, _Alloc>& __rhs)
605  { return __lhs._M_base() >= __rhs._M_base(); }
606 
607  template<typename _Tp, typename _Alloc>
608  inline bool
609  operator>(const vector<_Tp, _Alloc>& __lhs,
610  const vector<_Tp, _Alloc>& __rhs)
611  { return __lhs._M_base() > __rhs._M_base(); }
612 
613  template<typename _Tp, typename _Alloc>
614  inline void
615  swap(vector<_Tp, _Alloc>& __lhs, vector<_Tp, _Alloc>& __rhs)
616  { __lhs.swap(__rhs); }
617 
618 } // namespace __debug
619 
620 #ifdef __GXX_EXPERIMENTAL_CXX0X__
621  // DR 1182.
622  /// std::hash specialization for vector<bool>.
623  template<typename _Alloc>
624  struct hash<__debug::vector<bool, _Alloc>>
625  : public __hash_base<size_t, __debug::vector<bool, _Alloc>>
626  {
627  size_t
628  operator()(const __debug::vector<bool, _Alloc>& __b) const noexcept
629  { return std::hash<_GLIBCXX_STD_C::vector<bool, _Alloc>>()
630  (__b._M_base()); }
631  };
632 #endif
633 
634 } // namespace std
635 
636 #endif
__gnu_debug::__base
_Siter_base< _Iterator >::iterator_type __base(_Iterator __it)
Definition: safe_iterator.h:743
std::__debug::vector
Class std::vector with safety/checking/debug instrumentation.
Definition: debug/vector:45
std::allocator
The standard allocator, as per [20.4].
Definition: bits/alloc_traits.h:43
__glibcxx_check_erase_range
#define __glibcxx_check_erase_range(_First, _Last)
Definition: macros.h:164
__gnu_debug::_Safe_sequence_base::_M_swap
void _M_swap(_Safe_sequence_base &__x)
__gnu_cxx::__alloc_traits
Uniform interface to C++98 and C++0x allocators.
Definition: ext/alloc_traits.h:110
__glibcxx_check_erase
#define __glibcxx_check_erase(_Position)
Definition: macros.h:136
__glibcxx_check_insert_range
#define __glibcxx_check_insert_range(_Position, _First, _Last)
Definition: macros.h:111
__glibcxx_check_insert
#define __glibcxx_check_insert(_Position)
Definition: macros.h:74
__gnu_debug::_Safe_sequence
Base class for constructing a safe sequence type that tracks iterators that reference it...
Definition: formatter.h:53
std::hash
Primary class template hash.
Definition: system_error:112
__gnu_debug::_Safe_iterator
Safe iterator wrapper.
Definition: formatter.h:47
std::size
constexpr size_t size() const _GLIBCXX_NOEXCEPT
Returns the total number of bits.
Definition: bitset:1284
std::__debug::vector::vector
vector(const _Base &__x)
Construction from a release-mode vector.
Definition: debug/vector:111
std::vector
A standard container which offers fixed time access to individual elements in any order...
Definition: stl_vector.h:208