OSDN Git Service

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