libstdc++
vector
Go to the documentation of this file.
00001 // Profiling vector implementation -*- C++ -*-
00002 
00003 // Copyright (C) 2009-2014 Free Software Foundation, Inc.
00004 //
00005 // This file is part of the GNU ISO C++ Library.  This library is free
00006 // software; you can redistribute it and/or modify it under the
00007 // terms of the GNU General Public License as published by the
00008 // Free Software Foundation; either version 3, or (at your option)
00009 // any later version.
00010 //
00011 // This library is distributed in the hope that it will be useful,
00012 // but WITHOUT ANY WARRANTY; without even the implied warranty of
00013 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
00014 // GNU General Public License for more details.
00015 
00016 // Under Section 7 of GPL version 3, you are granted additional
00017 // permissions described in the GCC Runtime Library Exception, version
00018 // 3.1, as published by the Free Software Foundation.
00019 
00020 // You should have received a copy of the GNU General Public License along
00021 // with this library; see the file COPYING3.  If not see
00022 // <http://www.gnu.org/licenses/>.
00023 
00024 /** @file profile/vector
00025  *  This file is a GNU profile extension to the Standard C++ Library.
00026  */
00027 
00028 #ifndef _GLIBCXX_PROFILE_VECTOR
00029 #define _GLIBCXX_PROFILE_VECTOR 1
00030 
00031 #include <vector>
00032 #include <utility>
00033 #include <profile/base.h>
00034 #include <profile/iterator_tracker.h>
00035 
00036 namespace std _GLIBCXX_VISIBILITY(default)
00037 {
00038 namespace __profile
00039 {
00040   template<typename _Tp,
00041        typename _Allocator = std::allocator<_Tp> >
00042     class vector
00043     : public _GLIBCXX_STD_C::vector<_Tp, _Allocator>
00044     {
00045       typedef _GLIBCXX_STD_C::vector<_Tp, _Allocator> _Base;
00046 
00047       typedef typename _Base::iterator _Base_iterator;
00048       typedef typename _Base::const_iterator _Base_const_iterator;
00049 
00050 #if __cplusplus >= 201103L
00051       typedef __gnu_cxx::__alloc_traits<_Allocator>  _Alloc_traits;
00052 #endif
00053 
00054     public:
00055       typedef typename _Base::reference             reference;
00056       typedef typename _Base::const_reference       const_reference;
00057 
00058       typedef __iterator_tracker<_Base_iterator, vector>
00059                                                     iterator;
00060       typedef __iterator_tracker<_Base_const_iterator, vector>
00061                                     const_iterator;
00062 
00063       typedef typename _Base::size_type             size_type;
00064       typedef typename _Base::difference_type       difference_type;
00065 
00066       typedef _Tp                   value_type;
00067       typedef _Allocator                allocator_type;
00068       typedef typename _Base::pointer               pointer;
00069       typedef typename _Base::const_pointer         const_pointer;
00070       typedef std::reverse_iterator<iterator>       reverse_iterator;
00071       typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
00072       
00073       _Base&
00074       _M_base() _GLIBCXX_NOEXCEPT { return *this; }
00075 
00076       const _Base&
00077       _M_base() const _GLIBCXX_NOEXCEPT { return *this; }
00078 
00079       // 23.2.4.1 construct/copy/destroy:
00080 
00081       vector() _GLIBCXX_NOEXCEPT
00082       : _Base()
00083       {
00084         __profcxx_vector_construct(this, this->capacity());
00085         __profcxx_vector_construct2(this);
00086       }
00087 
00088       explicit
00089       vector(const _Allocator& __a) _GLIBCXX_NOEXCEPT
00090       : _Base(__a)
00091       {
00092         __profcxx_vector_construct(this, this->capacity());
00093         __profcxx_vector_construct2(this);
00094       }
00095 
00096 #if __cplusplus >= 201103L
00097       explicit
00098       vector(size_type __n, const _Allocator& __a = _Allocator())
00099       : _Base(__n, __a)
00100       {
00101         __profcxx_vector_construct(this, this->capacity());
00102         __profcxx_vector_construct2(this);
00103       }
00104 
00105       vector(size_type __n, const _Tp& __value,
00106          const _Allocator& __a = _Allocator())
00107       :  _Base(__n, __value, __a)
00108       {
00109         __profcxx_vector_construct(this, this->capacity());
00110         __profcxx_vector_construct2(this);
00111       }
00112 #else
00113       explicit
00114       vector(size_type __n, const _Tp& __value = _Tp(),
00115          const _Allocator& __a = _Allocator())
00116       : _Base(__n, __value, __a)
00117       {
00118         __profcxx_vector_construct(this, this->capacity());
00119         __profcxx_vector_construct2(this);
00120       }
00121 #endif
00122 
00123 #if __cplusplus >= 201103L
00124       template<typename _InputIterator,
00125            typename = std::_RequireInputIter<_InputIterator>>
00126 #else
00127       template<typename _InputIterator>
00128 #endif
00129         vector(_InputIterator __first, _InputIterator __last,
00130            const _Allocator& __a = _Allocator())
00131     : _Base(__first, __last, __a)
00132         {
00133       __profcxx_vector_construct(this, this->capacity());
00134       __profcxx_vector_construct2(this);
00135     }
00136 
00137       vector(const vector& __x)
00138       : _Base(__x) 
00139       {
00140         __profcxx_vector_construct(this, this->capacity());
00141         __profcxx_vector_construct2(this);
00142       }
00143 
00144       /// Construction from a release-mode vector
00145       vector(const _Base& __x)
00146       : _Base(__x) 
00147       { 
00148         __profcxx_vector_construct(this, this->capacity());
00149         __profcxx_vector_construct2(this);
00150       }
00151 
00152 #if __cplusplus >= 201103L
00153       vector(vector&& __x) noexcept
00154       : _Base(std::move(__x))
00155       {
00156         __profcxx_vector_construct(this, this->capacity());
00157         __profcxx_vector_construct2(this);
00158       }
00159 
00160       vector(const _Base& __x, const _Allocator& __a)
00161       : _Base(__x, __a)
00162       { 
00163         __profcxx_vector_construct(this, this->capacity());
00164         __profcxx_vector_construct2(this);
00165       }
00166 
00167       vector(vector&& __x, const _Allocator& __a)
00168       : _Base(std::move(__x), __a)
00169       {
00170         __profcxx_vector_construct(this, this->capacity());
00171         __profcxx_vector_construct2(this);
00172       }
00173 
00174       vector(initializer_list<value_type> __l,
00175          const allocator_type& __a = allocator_type())
00176       : _Base(__l, __a) { }
00177 #endif
00178 
00179       ~vector() _GLIBCXX_NOEXCEPT
00180       {
00181         __profcxx_vector_destruct(this, this->capacity(), this->size());
00182         __profcxx_vector_destruct2(this);
00183       }
00184 
00185       vector&
00186       operator=(const vector& __x)
00187       {
00188         static_cast<_Base&>(*this) = __x;
00189         return *this;
00190       }
00191 
00192 #if __cplusplus >= 201103L
00193       vector&
00194       operator=(vector&& __x) noexcept(_Alloc_traits::_S_nothrow_move())
00195       {
00196     __profcxx_vector_destruct(this, this->capacity(), this->size());
00197     __profcxx_vector_destruct2(this);
00198     static_cast<_Base&>(*this) = std::move(__x);
00199     return *this;
00200       }
00201 
00202       vector&
00203       operator=(initializer_list<value_type> __l)
00204       {
00205     static_cast<_Base&>(*this) = __l;
00206     return *this;
00207       }
00208 #endif
00209 
00210       using _Base::assign;
00211       using _Base::get_allocator;
00212 
00213 
00214       // iterators:
00215       iterator
00216       begin() _GLIBCXX_NOEXCEPT
00217       { return iterator(_Base::begin(), this); }
00218 
00219       const_iterator
00220       begin() const _GLIBCXX_NOEXCEPT
00221       { return const_iterator(_Base::begin(), this); }
00222 
00223       iterator
00224       end() _GLIBCXX_NOEXCEPT
00225       { return iterator(_Base::end(), this); }
00226 
00227       const_iterator
00228       end() const _GLIBCXX_NOEXCEPT
00229       { return const_iterator(_Base::end(), this); }
00230 
00231       reverse_iterator
00232       rbegin() _GLIBCXX_NOEXCEPT
00233       { return reverse_iterator(end()); }
00234 
00235       const_reverse_iterator
00236       rbegin() const _GLIBCXX_NOEXCEPT
00237       { return const_reverse_iterator(end()); }
00238 
00239       reverse_iterator
00240       rend() _GLIBCXX_NOEXCEPT
00241       { return reverse_iterator(begin()); }
00242 
00243       const_reverse_iterator
00244       rend() const _GLIBCXX_NOEXCEPT
00245       { return const_reverse_iterator(begin()); }
00246 
00247 #if __cplusplus >= 201103L
00248       const_iterator
00249       cbegin() const noexcept
00250       { return const_iterator(_Base::begin(), this); }
00251 
00252       const_iterator
00253       cend() const noexcept
00254       { return const_iterator(_Base::end(), this); }
00255 
00256       const_reverse_iterator
00257       crbegin() const noexcept
00258       { return const_reverse_iterator(end()); }
00259 
00260       const_reverse_iterator
00261       crend() const noexcept
00262       { return const_reverse_iterator(begin()); }
00263 #endif
00264 
00265       // 23.2.4.2 capacity:
00266       using _Base::size;
00267       using _Base::max_size;
00268 
00269 #if __cplusplus >= 201103L
00270       void
00271       resize(size_type __sz)
00272       {
00273         __profcxx_vector_invalid_operator(this);
00274         _M_profile_resize(this, this->capacity(), __sz);
00275         _Base::resize(__sz);
00276       }
00277 
00278       void
00279       resize(size_type __sz, const _Tp& __c)
00280       {
00281         __profcxx_vector_invalid_operator(this);
00282         _M_profile_resize(this, this->capacity(), __sz);
00283         _Base::resize(__sz, __c);
00284       }
00285 #else
00286       void
00287       resize(size_type __sz, _Tp __c = _Tp())
00288       {
00289         __profcxx_vector_invalid_operator(this);
00290         _M_profile_resize(this, this->capacity(), __sz);
00291         _Base::resize(__sz, __c);
00292       }
00293 #endif
00294 
00295 #if __cplusplus >= 201103L
00296       using _Base::shrink_to_fit;
00297 #endif
00298 
00299       using _Base::empty;
00300 
00301       // element access:
00302       reference
00303       operator[](size_type __n) _GLIBCXX_NOEXCEPT
00304       {
00305         __profcxx_vector_invalid_operator(this);
00306         return _M_base()[__n];
00307       }
00308       const_reference
00309       operator[](size_type __n) const _GLIBCXX_NOEXCEPT
00310       {
00311         __profcxx_vector_invalid_operator(this);
00312         return _M_base()[__n];
00313       }
00314 
00315       using _Base::at;
00316 
00317       reference
00318       front() _GLIBCXX_NOEXCEPT
00319       { 
00320         return _Base::front();
00321       }
00322 
00323       const_reference
00324       front() const _GLIBCXX_NOEXCEPT
00325       {
00326     return _Base::front();
00327       }
00328 
00329       reference
00330       back() _GLIBCXX_NOEXCEPT
00331       {
00332     return _Base::back();
00333       }
00334 
00335       const_reference
00336       back() const _GLIBCXX_NOEXCEPT
00337       {
00338     return _Base::back();
00339       }
00340 
00341       // _GLIBCXX_RESOLVE_LIB_DEFECTS
00342       // DR 464. Suggestion for new member functions in standard containers.
00343       using _Base::data;
00344 
00345       // 23.2.4.3 modifiers:
00346       void
00347       push_back(const _Tp& __x)
00348       {
00349         size_type __old_size = this->capacity();
00350     _Base::push_back(__x);
00351         _M_profile_resize(this, __old_size, this->capacity());
00352       }
00353 
00354 #if __cplusplus >= 201103L
00355       void
00356       push_back(_Tp&& __x)
00357       {
00358         size_type __old_size = this->capacity();
00359         _Base::push_back(std::move(__x));
00360         _M_profile_resize(this, __old_size, this->capacity());
00361       }
00362 
00363 #endif
00364 
00365       iterator
00366 #if __cplusplus >= 201103L
00367       insert(const_iterator __position, const _Tp& __x)
00368 #else
00369       insert(iterator __position, const _Tp& __x)
00370 #endif
00371       {
00372         __profcxx_vector_insert(this, __position.base() - _Base::begin(),
00373                                 this->size());
00374         size_type __old_size = this->capacity();
00375     _Base_iterator __res = _Base::insert(__position.base(), __x);
00376         _M_profile_resize(this, __old_size, this->capacity());
00377     return iterator(__res, this);
00378       }
00379 
00380 #if __cplusplus >= 201103L
00381       iterator
00382       insert(const_iterator __position, _Tp&& __x)
00383       {
00384         __profcxx_vector_insert(this, __position.base() - _Base::cbegin(),
00385                                 this->size());
00386         size_type __old_size = this->capacity();
00387     _Base_iterator __res = _Base::insert(__position.base(), __x);
00388         _M_profile_resize(this, __old_size, this->capacity());
00389     return iterator(__res, this);
00390       }
00391 
00392       template<typename... _Args>
00393         iterator
00394         emplace(const_iterator __position, _Args&&... __args)
00395         {
00396       _Base_iterator __res = _Base::emplace(__position.base(),
00397                         std::forward<_Args>(__args)...);
00398       return iterator(__res, this);
00399     }
00400 
00401       iterator
00402       insert(const_iterator __position, initializer_list<value_type> __l)
00403       { return this->insert(__position, __l.begin(), __l.end()); }
00404 #endif
00405 
00406 #if __cplusplus >= 201103L
00407       void
00408       swap(vector&& __x)
00409       {
00410         _Base::swap(__x);
00411       }
00412 #endif
00413 
00414       void
00415       swap(vector& __x)
00416 #if __cplusplus >= 201103L
00417       noexcept(_Alloc_traits::_S_nothrow_swap())
00418 #endif
00419       {
00420         _Base::swap(__x);
00421       }
00422 
00423 #if __cplusplus >= 201103L
00424       iterator
00425       insert(const_iterator __position, size_type __n, const _Tp& __x)
00426       {
00427         __profcxx_vector_insert(this, __position.base() - _Base::cbegin(),
00428                                 this->size());
00429         size_type __old_size = this->capacity();
00430         _Base_iterator __res = _Base::insert(__position, __n, __x);
00431         _M_profile_resize(this, __old_size, this->capacity());
00432     return iterator(__res, this);
00433       }
00434 #else
00435       void
00436       insert(iterator __position, size_type __n, const _Tp& __x)
00437       {
00438         __profcxx_vector_insert(this, __position.base() - _Base::begin(),
00439                                 this->size());
00440         size_type __old_size = this->capacity();
00441         _Base::insert(__position, __n, __x);
00442         _M_profile_resize(this, __old_size, this->capacity());
00443       }
00444 #endif
00445 
00446 #if __cplusplus >= 201103L
00447       template<typename _InputIterator,
00448            typename = std::_RequireInputIter<_InputIterator>>
00449     iterator
00450     insert(const_iterator __position,
00451            _InputIterator __first, _InputIterator __last)
00452         {
00453       __profcxx_vector_insert(this, __position.base() - _Base::cbegin(),
00454                   this->size());
00455       size_type __old_size = this->capacity();
00456       _Base_iterator __res = _Base::insert(__position, __first, __last);
00457       _M_profile_resize(this, __old_size, this->capacity());
00458       return iterator(__res, this);
00459     }
00460 #else
00461       template<typename _InputIterator>
00462     void
00463     insert(iterator __position,
00464            _InputIterator __first, _InputIterator __last)
00465         {
00466       __profcxx_vector_insert(this, __position.base() - _Base::begin(),
00467                   this->size());
00468       size_type __old_size = this->capacity();
00469       _Base::insert(__position, __first, __last);
00470       _M_profile_resize(this, __old_size, this->capacity());
00471     }
00472 #endif
00473 
00474       iterator
00475 #if __cplusplus >= 201103L
00476       erase(const_iterator __position)
00477 #else
00478       erase(iterator __position)    
00479 #endif
00480       {
00481     _Base_iterator __res = _Base::erase(__position.base());
00482     return iterator(__res, this);
00483       }
00484 
00485       iterator
00486 #if __cplusplus >= 201103L
00487       erase(const_iterator __first, const_iterator __last)
00488 #else
00489       erase(iterator __first, iterator __last)
00490 #endif
00491       {
00492     // _GLIBCXX_RESOLVE_LIB_DEFECTS
00493     // 151. can't currently clear() empty container
00494     _Base_iterator __res = _Base::erase(__first.base(), __last.base());
00495     return iterator(__res, this);
00496       }
00497 
00498       void
00499       clear() _GLIBCXX_NOEXCEPT
00500       {
00501         __profcxx_vector_destruct(this, this->capacity(), this->size());
00502         __profcxx_vector_destruct2(this);
00503         _Base::clear();
00504       }
00505 
00506       inline void _M_profile_find() const 
00507       { 
00508         __profcxx_vector_find(this, size()); 
00509       }
00510 
00511       inline void _M_profile_iterate(int __rewind = 0) const 
00512       { 
00513         __profcxx_vector_iterate(this); 
00514       }
00515 
00516     private:
00517       void _M_profile_resize(void* obj, size_type __old_size, 
00518                              size_type __new_size)
00519       {
00520         if (__old_size < __new_size) {
00521           __profcxx_vector_resize(this, this->size(), __new_size);
00522           __profcxx_vector_resize2(this, this->size(), __new_size);
00523         }
00524       }
00525     };
00526 
00527   template<typename _Tp, typename _Alloc>
00528     inline bool
00529     operator==(const vector<_Tp, _Alloc>& __lhs,
00530            const vector<_Tp, _Alloc>& __rhs)
00531     { return __lhs._M_base() == __rhs._M_base(); }
00532 
00533   template<typename _Tp, typename _Alloc>
00534     inline bool
00535     operator!=(const vector<_Tp, _Alloc>& __lhs,
00536            const vector<_Tp, _Alloc>& __rhs)
00537     { return __lhs._M_base() != __rhs._M_base(); }
00538 
00539   template<typename _Tp, typename _Alloc>
00540     inline bool
00541     operator<(const vector<_Tp, _Alloc>& __lhs,
00542           const vector<_Tp, _Alloc>& __rhs)
00543     { return __lhs._M_base() < __rhs._M_base(); }
00544 
00545   template<typename _Tp, typename _Alloc>
00546     inline bool
00547     operator<=(const vector<_Tp, _Alloc>& __lhs,
00548            const vector<_Tp, _Alloc>& __rhs)
00549     { return __lhs._M_base() <= __rhs._M_base(); }
00550 
00551   template<typename _Tp, typename _Alloc>
00552     inline bool
00553     operator>=(const vector<_Tp, _Alloc>& __lhs,
00554            const vector<_Tp, _Alloc>& __rhs)
00555     { return __lhs._M_base() >= __rhs._M_base(); }
00556 
00557   template<typename _Tp, typename _Alloc>
00558     inline bool
00559     operator>(const vector<_Tp, _Alloc>& __lhs,
00560           const vector<_Tp, _Alloc>& __rhs)
00561     { return __lhs._M_base() > __rhs._M_base(); }
00562 
00563   template<typename _Tp, typename _Alloc>
00564     inline void
00565     swap(vector<_Tp, _Alloc>& __lhs, vector<_Tp, _Alloc>& __rhs)
00566     { __lhs.swap(__rhs); }
00567 
00568 #if __cplusplus >= 201103L
00569   template<typename _Tp, typename _Alloc>
00570     inline void
00571     swap(vector<_Tp, _Alloc>&& __lhs, vector<_Tp, _Alloc>& __rhs)
00572     { __lhs.swap(__rhs); }
00573 
00574   template<typename _Tp, typename _Alloc>
00575     inline void
00576     swap(vector<_Tp, _Alloc>& __lhs, vector<_Tp, _Alloc>&& __rhs)
00577     { __lhs.swap(__rhs); }
00578 #endif
00579 
00580 } // namespace __profile
00581 
00582 #if __cplusplus >= 201103L
00583   // DR 1182.
00584   /// std::hash specialization for vector<bool>.
00585   template<typename _Alloc>
00586     struct hash<__profile::vector<bool, _Alloc>>
00587     : public __hash_base<size_t, __profile::vector<bool, _Alloc>>
00588     {
00589       size_t
00590       operator()(const __profile::vector<bool, _Alloc>& __b) const noexcept
00591       { return std::hash<_GLIBCXX_STD_C::vector<bool, _Alloc>>()
00592       (__b._M_base()); }
00593     };
00594 #endif
00595 
00596 } // namespace std
00597 
00598 #endif