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
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
39 {
40 namespace __debug
41 {
42  template<typename _Tp,
43  typename _Allocator = std::allocator<_Tp> >
44  class vector
45  : public _GLIBCXX_STD_D::vector<_Tp, _Allocator>,
46  public __gnu_debug::_Safe_sequence<vector<_Tp, _Allocator> >
47  {
48  typedef _GLIBCXX_STD_D::vector<_Tp, _Allocator> _Base;
49  typedef __gnu_debug::_Safe_sequence<vector> _Safe_base;
50 
51  typedef typename _Base::const_iterator _Base_const_iterator;
53 
54  public:
55  typedef typename _Base::reference reference;
56  typedef typename _Base::const_reference const_reference;
57 
59  iterator;
61  const_iterator;
62 
63  typedef typename _Base::size_type size_type;
64  typedef typename _Base::difference_type difference_type;
65 
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;
72 
73  // 23.2.4.1 construct/copy/destroy:
74  explicit vector(const _Allocator& __a = _Allocator())
75  : _Base(__a), _M_guaranteed_capacity(0) { }
76 
77  explicit vector(size_type __n, const _Tp& __value = _Tp(),
78  const _Allocator& __a = _Allocator())
79  : _Base(__n, __value, __a), _M_guaranteed_capacity(__n) { }
80 
81  template<class _InputIterator>
82  vector(_InputIterator __first, _InputIterator __last,
83  const _Allocator& __a = _Allocator())
84  : _Base(__gnu_debug::__check_valid_range(__first, __last),
85  __last, __a),
86  _M_guaranteed_capacity(0)
87  { _M_update_guaranteed_capacity(); }
88 
89  vector(const vector& __x)
90  : _Base(__x), _Safe_base(), _M_guaranteed_capacity(__x.size()) { }
91 
92  /// Construction from a release-mode vector
93  vector(const _Base& __x)
94  : _Base(__x), _Safe_base(), _M_guaranteed_capacity(__x.size()) { }
95 
96 #ifdef __GXX_EXPERIMENTAL_CXX0X__
97  vector(vector&& __x)
98  : _Base(std::forward<vector>(__x)), _Safe_base(),
99  _M_guaranteed_capacity(this->size())
100  {
101  this->_M_swap(__x);
102  __x._M_guaranteed_capacity = 0;
103  }
104 
105  vector(initializer_list<value_type> __l,
106  const allocator_type& __a = allocator_type())
107  : _Base(__l, __a), _Safe_base(),
108  _M_guaranteed_capacity(__l.size()) { }
109 #endif
110 
111  ~vector() { }
112 
113  vector&
114  operator=(const vector& __x)
115  {
116  static_cast<_Base&>(*this) = __x;
117  this->_M_invalidate_all();
118  _M_update_guaranteed_capacity();
119  return *this;
120  }
121 
122 #ifdef __GXX_EXPERIMENTAL_CXX0X__
123  vector&
124  operator=(vector&& __x)
125  {
126  // NB: DR 675.
127  clear();
128  swap(__x);
129  return *this;
130  }
131 
132  vector&
133  operator=(initializer_list<value_type> __l)
134  {
135  static_cast<_Base&>(*this) = __l;
136  this->_M_invalidate_all();
137  _M_update_guaranteed_capacity();
138  return *this;
139  }
140 #endif
141 
142  template<typename _InputIterator>
143  void
144  assign(_InputIterator __first, _InputIterator __last)
145  {
146  __glibcxx_check_valid_range(__first, __last);
147  _Base::assign(__first, __last);
148  this->_M_invalidate_all();
149  _M_update_guaranteed_capacity();
150  }
151 
152  void
153  assign(size_type __n, const _Tp& __u)
154  {
155  _Base::assign(__n, __u);
156  this->_M_invalidate_all();
157  _M_update_guaranteed_capacity();
158  }
159 
160 #ifdef __GXX_EXPERIMENTAL_CXX0X__
161  void
162  assign(initializer_list<value_type> __l)
163  {
164  _Base::assign(__l);
165  this->_M_invalidate_all();
166  _M_update_guaranteed_capacity();
167  }
168 #endif
169 
170  using _Base::get_allocator;
171 
172  // iterators:
173  iterator
174  begin()
175  { return iterator(_Base::begin(), this); }
176 
177  const_iterator
178  begin() const
179  { return const_iterator(_Base::begin(), this); }
180 
181  iterator
182  end()
183  { return iterator(_Base::end(), this); }
184 
185  const_iterator
186  end() const
187  { return const_iterator(_Base::end(), this); }
188 
189  reverse_iterator
190  rbegin()
191  { return reverse_iterator(end()); }
192 
193  const_reverse_iterator
194  rbegin() const
195  { return const_reverse_iterator(end()); }
196 
197  reverse_iterator
198  rend()
199  { return reverse_iterator(begin()); }
200 
201  const_reverse_iterator
202  rend() const
203  { return const_reverse_iterator(begin()); }
204 
205 #ifdef __GXX_EXPERIMENTAL_CXX0X__
206  const_iterator
207  cbegin() const
208  { return const_iterator(_Base::begin(), this); }
209 
210  const_iterator
211  cend() const
212  { return const_iterator(_Base::end(), this); }
213 
214  const_reverse_iterator
215  crbegin() const
216  { return const_reverse_iterator(end()); }
217 
218  const_reverse_iterator
219  crend() const
220  { return const_reverse_iterator(begin()); }
221 #endif
222 
223  // 23.2.4.2 capacity:
224  using _Base::size;
225  using _Base::max_size;
226 
227  void
228  resize(size_type __sz, _Tp __c = _Tp())
229  {
230  bool __realloc = _M_requires_reallocation(__sz);
231  if (__sz < this->size())
232  this->_M_invalidate_if(_After_nth(__sz, _M_base().begin()));
233  _Base::resize(__sz, __c);
234  if (__realloc)
235  this->_M_invalidate_all();
236  }
237 
238  size_type
239  capacity() const
240  {
241 #ifdef _GLIBCXX_DEBUG_PEDANTIC
242  return _M_guaranteed_capacity;
243 #else
244  return _Base::capacity();
245 #endif
246  }
247 
248  using _Base::empty;
249 
250  void
251  reserve(size_type __n)
252  {
253  bool __realloc = _M_requires_reallocation(__n);
254  _Base::reserve(__n);
255  if (__n > _M_guaranteed_capacity)
256  _M_guaranteed_capacity = __n;
257  if (__realloc)
258  this->_M_invalidate_all();
259  }
260 
261  // element access:
262  reference
263  operator[](size_type __n)
264  {
265  __glibcxx_check_subscript(__n);
266  return _M_base()[__n];
267  }
268 
269  const_reference
270  operator[](size_type __n) const
271  {
272  __glibcxx_check_subscript(__n);
273  return _M_base()[__n];
274  }
275 
276  using _Base::at;
277 
278  reference
279  front()
280  {
281  __glibcxx_check_nonempty();
282  return _Base::front();
283  }
284 
285  const_reference
286  front() const
287  {
288  __glibcxx_check_nonempty();
289  return _Base::front();
290  }
291 
292  reference
293  back()
294  {
295  __glibcxx_check_nonempty();
296  return _Base::back();
297  }
298 
299  const_reference
300  back() const
301  {
302  __glibcxx_check_nonempty();
303  return _Base::back();
304  }
305 
306  // _GLIBCXX_RESOLVE_LIB_DEFECTS
307  // DR 464. Suggestion for new member functions in standard containers.
308  using _Base::data;
309 
310  // 23.2.4.3 modifiers:
311  void
312  push_back(const _Tp& __x)
313  {
314  bool __realloc = _M_requires_reallocation(this->size() + 1);
315  _Base::push_back(__x);
316  if (__realloc)
317  this->_M_invalidate_all();
318  _M_update_guaranteed_capacity();
319  }
320 
321 #ifdef __GXX_EXPERIMENTAL_CXX0X__
322  template<typename _Up = _Tp>
323  typename __gnu_cxx::__enable_if<!std::__are_same<_Up, bool>::__value,
324  void>::__type
325  push_back(_Tp&& __x)
326  { emplace_back(std::move(__x)); }
327 
328  template<typename... _Args>
329  void
330  emplace_back(_Args&&... __args)
331  {
332  bool __realloc = _M_requires_reallocation(this->size() + 1);
333  _Base::emplace_back(std::forward<_Args>(__args)...);
334  if (__realloc)
335  this->_M_invalidate_all();
336  _M_update_guaranteed_capacity();
337  }
338 #endif
339 
340  void
341  pop_back()
342  {
343  __glibcxx_check_nonempty();
344  iterator __victim = end() - 1;
345  __victim._M_invalidate();
346  _Base::pop_back();
347  }
348 
349 #ifdef __GXX_EXPERIMENTAL_CXX0X__
350  template<typename... _Args>
351  iterator
352  emplace(iterator __position, _Args&&... __args)
353  {
354  __glibcxx_check_insert(__position);
355  bool __realloc = _M_requires_reallocation(this->size() + 1);
356  difference_type __offset = __position - begin();
357  typename _Base::iterator __res = _Base::emplace(__position.base(),
358  std::forward<_Args>(__args)...);
359  if (__realloc)
360  this->_M_invalidate_all();
361  else
362  this->_M_invalidate_if(_After_nth(__offset, _M_base().begin()));
363  _M_update_guaranteed_capacity();
364  return iterator(__res, this);
365  }
366 #endif
367 
368  iterator
369  insert(iterator __position, const _Tp& __x)
370  {
371  __glibcxx_check_insert(__position);
372  bool __realloc = _M_requires_reallocation(this->size() + 1);
373  difference_type __offset = __position - begin();
374  typename _Base::iterator __res = _Base::insert(__position.base(),__x);
375  if (__realloc)
376  this->_M_invalidate_all();
377  else
378  this->_M_invalidate_if(_After_nth(__offset, _M_base().begin()));
379  _M_update_guaranteed_capacity();
380  return iterator(__res, this);
381  }
382 
383 #ifdef __GXX_EXPERIMENTAL_CXX0X__
384  template<typename _Up = _Tp>
385  typename __gnu_cxx::__enable_if<!std::__are_same<_Up, bool>::__value,
386  iterator>::__type
387  insert(iterator __position, _Tp&& __x)
388  { return emplace(__position, std::move(__x)); }
389 
390  void
391  insert(iterator __position, initializer_list<value_type> __l)
392  { this->insert(__position, __l.begin(), __l.end()); }
393 #endif
394 
395  void
396  insert(iterator __position, size_type __n, const _Tp& __x)
397  {
398  __glibcxx_check_insert(__position);
399  bool __realloc = _M_requires_reallocation(this->size() + __n);
400  difference_type __offset = __position - begin();
401  _Base::insert(__position.base(), __n, __x);
402  if (__realloc)
403  this->_M_invalidate_all();
404  else
405  this->_M_invalidate_if(_After_nth(__offset, _M_base().begin()));
406  _M_update_guaranteed_capacity();
407  }
408 
409  template<class _InputIterator>
410  void
411  insert(iterator __position,
412  _InputIterator __first, _InputIterator __last)
413  {
414  __glibcxx_check_insert_range(__position, __first, __last);
415 
416  /* Hard to guess if invalidation will occur, because __last
417  - __first can't be calculated in all cases, so we just
418  punt here by checking if it did occur. */
419  typename _Base::iterator __old_begin = _M_base().begin();
420  difference_type __offset = __position - begin();
421  _Base::insert(__position.base(), __first, __last);
422 
423  if (_M_base().begin() != __old_begin)
424  this->_M_invalidate_all();
425  else
426  this->_M_invalidate_if(_After_nth(__offset, _M_base().begin()));
427  _M_update_guaranteed_capacity();
428  }
429 
430  iterator
431  erase(iterator __position)
432  {
433  __glibcxx_check_erase(__position);
434  difference_type __offset = __position - begin();
435  typename _Base::iterator __res = _Base::erase(__position.base());
436  this->_M_invalidate_if(_After_nth(__offset, _M_base().begin()));
437  return iterator(__res, this);
438  }
439 
440  iterator
441  erase(iterator __first, iterator __last)
442  {
443  // _GLIBCXX_RESOLVE_LIB_DEFECTS
444  // 151. can't currently clear() empty container
445  __glibcxx_check_erase_range(__first, __last);
446 
447  difference_type __offset = __first - begin();
448  typename _Base::iterator __res = _Base::erase(__first.base(),
449  __last.base());
450  this->_M_invalidate_if(_After_nth(__offset, _M_base().begin()));
451  return iterator(__res, this);
452  }
453 
454  void
455 #ifdef __GXX_EXPERIMENTAL_CXX0X__
456  swap(vector&& __x)
457 #else
458  swap(vector& __x)
459 #endif
460  {
461  _Base::swap(__x);
462  this->_M_swap(__x);
463  std::swap(_M_guaranteed_capacity, __x._M_guaranteed_capacity);
464  }
465 
466  void
467  clear()
468  {
469  _Base::clear();
470  this->_M_invalidate_all();
471  _M_guaranteed_capacity = 0;
472  }
473 
474  _Base&
475  _M_base() { return *this; }
476 
477  const _Base&
478  _M_base() const { return *this; }
479 
480  private:
481  size_type _M_guaranteed_capacity;
482 
483  bool
484  _M_requires_reallocation(size_type __elements)
485  { return __elements > this->capacity(); }
486 
487  void
488  _M_update_guaranteed_capacity()
489  {
490  if (this->size() > _M_guaranteed_capacity)
491  _M_guaranteed_capacity = this->size();
492  }
493  };
494 
495  template<typename _Tp, typename _Alloc>
496  inline bool
497  operator==(const vector<_Tp, _Alloc>& __lhs,
498  const vector<_Tp, _Alloc>& __rhs)
499  { return __lhs._M_base() == __rhs._M_base(); }
500 
501  template<typename _Tp, typename _Alloc>
502  inline bool
503  operator!=(const vector<_Tp, _Alloc>& __lhs,
504  const vector<_Tp, _Alloc>& __rhs)
505  { return __lhs._M_base() != __rhs._M_base(); }
506 
507  template<typename _Tp, typename _Alloc>
508  inline bool
509  operator<(const vector<_Tp, _Alloc>& __lhs,
510  const vector<_Tp, _Alloc>& __rhs)
511  { return __lhs._M_base() < __rhs._M_base(); }
512 
513  template<typename _Tp, typename _Alloc>
514  inline bool
515  operator<=(const vector<_Tp, _Alloc>& __lhs,
516  const vector<_Tp, _Alloc>& __rhs)
517  { return __lhs._M_base() <= __rhs._M_base(); }
518 
519  template<typename _Tp, typename _Alloc>
520  inline bool
521  operator>=(const vector<_Tp, _Alloc>& __lhs,
522  const vector<_Tp, _Alloc>& __rhs)
523  { return __lhs._M_base() >= __rhs._M_base(); }
524 
525  template<typename _Tp, typename _Alloc>
526  inline bool
527  operator>(const vector<_Tp, _Alloc>& __lhs,
528  const vector<_Tp, _Alloc>& __rhs)
529  { return __lhs._M_base() > __rhs._M_base(); }
530 
531  template<typename _Tp, typename _Alloc>
532  inline void
533  swap(vector<_Tp, _Alloc>& __lhs, vector<_Tp, _Alloc>& __rhs)
534  { __lhs.swap(__rhs); }
535 
536 #ifdef __GXX_EXPERIMENTAL_CXX0X__
537  template<typename _Tp, typename _Alloc>
538  inline void
539  swap(vector<_Tp, _Alloc>&& __lhs, vector<_Tp, _Alloc>& __rhs)
540  { __lhs.swap(__rhs); }
541 
542  template<typename _Tp, typename _Alloc>
543  inline void
544  swap(vector<_Tp, _Alloc>& __lhs, vector<_Tp, _Alloc>&& __rhs)
545  { __lhs.swap(__rhs); }
546 #endif
547 
548 } // namespace __debug
549 } // namespace std
550 
551 #endif