libstdc++
vector
Go to the documentation of this file.
00001 // Profiling vector implementation -*- C++ -*-
00002 
00003 // Copyright (C) 2009-2015 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 _Vector>
00041     class _Vector_profile_pre
00042     {
00043       _Vector&
00044       _M_conjure()
00045       { return *static_cast<_Vector*>(this); }
00046 
00047     public:
00048 #if __cplusplus >= 201103L
00049       _Vector_profile_pre() = default;
00050       _Vector_profile_pre(const _Vector_profile_pre&) = default;
00051       _Vector_profile_pre(_Vector_profile_pre&&) = default;
00052 
00053       _Vector_profile_pre&
00054       operator=(const _Vector_profile_pre&)
00055       { _M_conjure()._M_profile_destruct(); }
00056 
00057       _Vector_profile_pre&
00058       operator=(_Vector_profile_pre&&) noexcept
00059       { _M_conjure()._M_profile_destruct(); }
00060 #endif
00061     };
00062 
00063   template<typename _Vector>
00064     class _Vector_profile_post
00065     {
00066       _Vector&
00067       _M_conjure()
00068       { return *static_cast<_Vector*>(this); }
00069 
00070     protected:
00071       __gnu_profile::__container_size_info* _M_size_info;
00072       __gnu_profile::__vector2list_info* _M_vect2list_info;
00073 
00074       _Vector_profile_post() _GLIBCXX_NOEXCEPT
00075       { _M_profile_construct(); }
00076 
00077 #if __cplusplus >= 201103L
00078       _Vector_profile_post(const _Vector_profile_post&) noexcept
00079       : _Vector_profile_post() { }
00080       _Vector_profile_post(_Vector_profile_post&& __other) noexcept
00081       : _Vector_profile_post()
00082       { _M_swap(__other); }
00083 
00084       _Vector_profile_post&
00085       operator=(const _Vector_profile_post&) noexcept
00086       { _M_profile_construct(); }
00087 
00088       _Vector_profile_post&
00089       operator=(_Vector_profile_post&& __other) noexcept
00090       {
00091         _M_swap(__other);
00092         __other._M_profile_construct();
00093       }
00094 #endif
00095 
00096       ~_Vector_profile_post()
00097       { _M_conjure()._M_profile_destruct(); }
00098 
00099     public:
00100       void
00101       _M_profile_construct() _GLIBCXX_NOEXCEPT
00102       {
00103         _M_size_info =
00104           __profcxx_vector_size_construct(_M_conjure().capacity());
00105         _M_vect2list_info = __profcxx_vector2list_construct();  
00106       }
00107 
00108       void
00109       _M_profile_destruct() _GLIBCXX_NOEXCEPT
00110       {
00111         __profcxx_vector2list_destruct(_M_vect2list_info);
00112         _M_vect2list_info = 0;
00113         __profcxx_vector_size_destruct(_M_size_info,
00114                                        _M_conjure().capacity(),
00115                                        _M_conjure().size());
00116         _M_size_info = 0;
00117       }
00118 
00119       void
00120       _M_swap(_Vector_profile_post& __other) _GLIBCXX_NOEXCEPT
00121       {
00122         std::swap(_M_size_info, __other._M_size_info);
00123         std::swap(_M_vect2list_info, __other._M_vect2list_info);
00124       }
00125     };
00126 
00127   template<typename _Tp,
00128            typename _Allocator = std::allocator<_Tp> >
00129     class vector
00130     : public _Vector_profile_pre<vector<_Tp, _Allocator> >,
00131       public _GLIBCXX_STD_C::vector<_Tp, _Allocator>,
00132       public _Vector_profile_post<vector<_Tp, _Allocator> >
00133     {
00134       typedef _GLIBCXX_STD_C::vector<_Tp, _Allocator>   _Base;
00135 
00136       typedef typename _Base::iterator                  _Base_iterator;
00137       typedef typename _Base::const_iterator            _Base_const_iterator;
00138 
00139     public:
00140       typedef typename _Base::reference                 reference;
00141       typedef typename _Base::const_reference           const_reference;
00142 
00143       typedef __iterator_tracker<_Base_iterator, vector>
00144                                                         iterator;
00145       typedef __iterator_tracker<_Base_const_iterator, vector>
00146                                                         const_iterator;
00147 
00148       typedef typename _Base::size_type                 size_type;
00149       typedef typename _Base::difference_type           difference_type;
00150 
00151       typedef _Tp                                       value_type;
00152       typedef _Allocator                                allocator_type;
00153       typedef typename _Base::pointer                   pointer;
00154       typedef typename _Base::const_pointer             const_pointer;
00155       typedef std::reverse_iterator<iterator>           reverse_iterator;
00156       typedef std::reverse_iterator<const_iterator>     const_reverse_iterator;
00157 
00158       _Base&
00159       _M_base() _GLIBCXX_NOEXCEPT       { return *this; }
00160 
00161       const _Base&
00162       _M_base() const _GLIBCXX_NOEXCEPT { return *this; }
00163 
00164       // 23.2.4.1 construct/copy/destroy:
00165 
00166 #if __cplusplus < 201103L
00167       vector()
00168       { }
00169 
00170       vector(const vector& __x)
00171       : _Base(__x) { }
00172 #else
00173       vector() = default;
00174       vector(const vector&) = default;
00175       vector(vector&&) = default;
00176 #endif
00177 
00178       explicit
00179       vector(const _Allocator& __a) _GLIBCXX_NOEXCEPT
00180       : _Base(__a) { }
00181 
00182 #if __cplusplus >= 201103L
00183       explicit
00184       vector(size_type __n, const _Allocator& __a = _Allocator())
00185       : _Base(__n, __a) { }
00186 
00187       vector(size_type __n, const _Tp& __value,
00188              const _Allocator& __a = _Allocator())
00189       : _Base(__n, __value, __a) { }
00190 #else
00191       explicit
00192       vector(size_type __n, const _Tp& __value = _Tp(),
00193              const _Allocator& __a = _Allocator())
00194       : _Base(__n, __value, __a) { }
00195 #endif
00196 
00197 #if __cplusplus >= 201103L
00198       template<typename _InputIterator,
00199                typename = std::_RequireInputIter<_InputIterator>>
00200 #else
00201       template<typename _InputIterator>
00202 #endif
00203         vector(_InputIterator __first, _InputIterator __last,
00204                const _Allocator& __a = _Allocator())
00205         : _Base(__first, __last, __a) { }
00206 
00207       /// Construction from a normal-mode vector
00208       vector(const _Base& __x)
00209       : _Base(__x) { }
00210 
00211 #if __cplusplus >= 201103L
00212       vector(const _Base& __x, const _Allocator& __a)
00213       : _Base(__x, __a) { }
00214 
00215       vector(vector&& __x, const _Allocator& __a)
00216       : _Base(std::move(__x), __a) { }
00217 
00218       vector(initializer_list<value_type> __l,
00219              const allocator_type& __a = allocator_type())
00220       : _Base(__l, __a) { }
00221 #endif
00222 
00223 #if __cplusplus < 201103L
00224       vector&
00225       operator=(const vector& __x)
00226       {
00227         this->_M_profile_destruct();
00228         _M_base() = __x;
00229         this->_M_profile_construct();
00230         return *this;
00231       }
00232 #else
00233       vector&
00234       operator=(const vector&) = default;
00235 
00236       vector&
00237       operator=(vector&&) = default;
00238 
00239       vector&
00240       operator=(initializer_list<value_type> __l)
00241       {
00242         this->_M_profile_destruct();
00243         _M_base() = __l;
00244         this->_M_profile_construct();
00245         return *this;
00246       }
00247 #endif
00248 
00249       // iterators:
00250       iterator
00251       begin() _GLIBCXX_NOEXCEPT
00252       { return iterator(_Base::begin(), this); }
00253 
00254       const_iterator
00255       begin() const _GLIBCXX_NOEXCEPT
00256       { return const_iterator(_Base::begin(), this); }
00257 
00258       iterator
00259       end() _GLIBCXX_NOEXCEPT
00260       { return iterator(_Base::end(), this); }
00261 
00262       const_iterator
00263       end() const _GLIBCXX_NOEXCEPT
00264       { return const_iterator(_Base::end(), this); }
00265 
00266       reverse_iterator
00267       rbegin() _GLIBCXX_NOEXCEPT
00268       { return reverse_iterator(end()); }
00269 
00270       const_reverse_iterator
00271       rbegin() const _GLIBCXX_NOEXCEPT
00272       { return const_reverse_iterator(end()); }
00273 
00274       reverse_iterator
00275       rend() _GLIBCXX_NOEXCEPT
00276       { return reverse_iterator(begin()); }
00277 
00278       const_reverse_iterator
00279       rend() const _GLIBCXX_NOEXCEPT
00280       { return const_reverse_iterator(begin()); }
00281 
00282 #if __cplusplus >= 201103L
00283       const_iterator
00284       cbegin() const noexcept
00285       { return const_iterator(_Base::begin(), this); }
00286 
00287       const_iterator
00288       cend() const noexcept
00289       { return const_iterator(_Base::end(), this); }
00290 
00291       const_reverse_iterator
00292       crbegin() const noexcept
00293       { return const_reverse_iterator(end()); }
00294 
00295       const_reverse_iterator
00296       crend() const noexcept
00297       { return const_reverse_iterator(begin()); }
00298 #endif
00299 
00300       // 23.2.4.2 capacity:
00301 
00302 #if __cplusplus >= 201103L
00303       void
00304       resize(size_type __sz)
00305       {
00306         __profcxx_vector2list_invalid_operator(this->_M_vect2list_info);
00307         _M_profile_resize(this->capacity(), __sz);
00308         _Base::resize(__sz);
00309       }
00310 
00311       void
00312       resize(size_type __sz, const _Tp& __c)
00313       {
00314         __profcxx_vector2list_invalid_operator(this->_M_vect2list_info);
00315         _M_profile_resize(this->capacity(), __sz);
00316         _Base::resize(__sz, __c);
00317       }
00318 #else
00319       void
00320       resize(size_type __sz, _Tp __c = _Tp())
00321       {
00322         __profcxx_vector2list_invalid_operator(this->_M_vect2list_info);
00323         _M_profile_resize(this->capacity(), __sz);
00324         _Base::resize(__sz, __c);
00325       }
00326 #endif
00327 
00328       // element access:
00329       reference
00330       operator[](size_type __n) _GLIBCXX_NOEXCEPT
00331       {
00332         __profcxx_vector2list_invalid_operator(this->_M_vect2list_info);
00333         return _M_base()[__n];
00334       }
00335       const_reference
00336       operator[](size_type __n) const _GLIBCXX_NOEXCEPT
00337       {
00338         __profcxx_vector2list_invalid_operator(this->_M_vect2list_info);
00339         return _M_base()[__n];
00340       }
00341 
00342       // 23.2.4.3 modifiers:
00343       void
00344       push_back(const _Tp& __x)
00345       {
00346         size_type __old_size = this->capacity();
00347         _Base::push_back(__x);
00348         _M_profile_resize(__old_size, this->capacity());
00349       }
00350 
00351 #if __cplusplus >= 201103L
00352       void
00353       push_back(_Tp&& __x)
00354       {
00355         size_type __old_size = this->capacity();
00356         _Base::push_back(std::move(__x));
00357         _M_profile_resize(__old_size, this->capacity());
00358       }
00359 
00360 #endif
00361 
00362       iterator
00363 #if __cplusplus >= 201103L
00364       insert(const_iterator __pos, const _Tp& __x)
00365 #else
00366       insert(iterator __pos, const _Tp& __x)
00367 #endif
00368       {
00369         __profcxx_vector2list_insert(this->_M_vect2list_info,
00370                                      __pos.base() - _Base::begin(),
00371                                      this->size());
00372         size_type __old_size = this->capacity();
00373         _Base_iterator __res = _Base::insert(__pos.base(), __x);
00374         _M_profile_resize(__old_size, this->capacity());
00375         return iterator(__res, this);
00376       }
00377 
00378 #if __cplusplus >= 201103L
00379       iterator
00380       insert(const_iterator __pos, _Tp&& __x)
00381       {
00382         __profcxx_vector2list_insert(this->_M_vect2list_info,
00383                                      __pos.base() - _Base::cbegin(),
00384                                      this->size());
00385         size_type __old_size = this->capacity();
00386         _Base_iterator __res = _Base::insert(__pos.base(), __x);
00387         _M_profile_resize(__old_size, this->capacity());
00388         return iterator(__res, this);
00389       }
00390 
00391       template<typename... _Args>
00392         iterator
00393         emplace(const_iterator __pos, _Args&&... __args)
00394         {
00395           _Base_iterator __res = _Base::emplace(__pos.base(),
00396                                                 std::forward<_Args>(__args)...);
00397           return iterator(__res, this);
00398         }
00399 
00400       iterator
00401       insert(const_iterator __pos, initializer_list<value_type> __l)
00402       { return this->insert(__pos, __l.begin(), __l.end()); }
00403 #endif
00404 
00405       void
00406       swap(vector& __x)
00407 #if __cplusplus >= 201103L
00408         noexcept( noexcept(declval<_Base>().swap(__x)) )
00409 #endif
00410       {
00411         _Base::swap(__x);
00412         this->_M_swap(__x);
00413       }
00414 
00415 #if __cplusplus >= 201103L
00416       iterator
00417       insert(const_iterator __pos, size_type __n, const _Tp& __x)
00418       {
00419         __profcxx_vector2list_insert(this->_M_vect2list_info,
00420                                      __pos.base() - _Base::cbegin(),
00421                                      this->size());
00422         size_type __old_size = this->capacity();
00423         _Base_iterator __res = _Base::insert(__pos, __n, __x);
00424         _M_profile_resize(__old_size, this->capacity());
00425         return iterator(__res, this);
00426       }
00427 #else
00428       void
00429       insert(iterator __pos, size_type __n, const _Tp& __x)
00430       {
00431         __profcxx_vector2list_insert(this->_M_vect2list_info,
00432                                      __pos.base() - _Base::begin(),
00433                                      this->size());
00434         size_type __old_size = this->capacity();
00435         _Base::insert(__pos, __n, __x);
00436         _M_profile_resize(__old_size, this->capacity());
00437       }
00438 #endif
00439 
00440 #if __cplusplus >= 201103L
00441       template<typename _InputIterator,
00442                typename = std::_RequireInputIter<_InputIterator>>
00443         iterator
00444         insert(const_iterator __pos,
00445                _InputIterator __first, _InputIterator __last)
00446         {
00447           __profcxx_vector2list_insert(this->_M_vect2list_info,
00448                                        __pos.base() - _Base::cbegin(),
00449                                        this->size());
00450           size_type __old_size = this->capacity();
00451           _Base_iterator __res = _Base::insert(__pos, __first, __last);
00452           _M_profile_resize(__old_size, this->capacity());
00453           return iterator(__res, this);
00454         }
00455 #else
00456       template<typename _InputIterator>
00457         void
00458         insert(iterator __pos,
00459                _InputIterator __first, _InputIterator __last)
00460         {
00461           __profcxx_vector2list_insert(this->_M_vect2list_info,
00462                                        __pos.base() - _Base::begin(),
00463                                        this->size());
00464           size_type __old_size = this->capacity();
00465           _Base::insert(__pos, __first, __last);
00466           _M_profile_resize(__old_size, this->capacity());
00467         }
00468 #endif
00469 
00470       iterator
00471 #if __cplusplus >= 201103L
00472       erase(const_iterator __pos)
00473 #else
00474       erase(iterator __pos)     
00475 #endif
00476       { return iterator(_Base::erase(__pos.base()), this); }
00477 
00478       iterator
00479 #if __cplusplus >= 201103L
00480       erase(const_iterator __first, const_iterator __last)
00481 #else
00482       erase(iterator __first, iterator __last)
00483 #endif
00484       { return iterator(_Base::erase(__first.base(), __last.base()), this); }
00485 
00486       void
00487       clear() _GLIBCXX_NOEXCEPT
00488       {
00489         this->_M_profile_destruct();
00490         _Base::clear();
00491         this->_M_profile_construct();
00492       }
00493 
00494       inline void
00495       _M_profile_iterate(int __rewind = 0) const
00496       { __profcxx_vector2list_iterate(this->_M_vect2list_info, __rewind); }
00497 
00498     private:
00499       void _M_profile_resize(size_type __old_size, size_type __new_size)
00500       {
00501         if (__old_size < __new_size)
00502           {
00503             __profcxx_vector_size_resize(this->_M_size_info,
00504                                          this->size(), __new_size);
00505             __profcxx_vector2list_resize(this->_M_vect2list_info,
00506                                          this->size(), __new_size);
00507           }
00508       }
00509     };
00510 
00511   template<typename _Tp, typename _Alloc>
00512     inline bool
00513     operator==(const vector<_Tp, _Alloc>& __lhs,
00514                const vector<_Tp, _Alloc>& __rhs)
00515     { return __lhs._M_base() == __rhs._M_base(); }
00516 
00517   template<typename _Tp, typename _Alloc>
00518     inline bool
00519     operator!=(const vector<_Tp, _Alloc>& __lhs,
00520                const vector<_Tp, _Alloc>& __rhs)
00521     { return __lhs._M_base() != __rhs._M_base(); }
00522 
00523   template<typename _Tp, typename _Alloc>
00524     inline bool
00525     operator<(const vector<_Tp, _Alloc>& __lhs,
00526               const vector<_Tp, _Alloc>& __rhs)
00527     { return __lhs._M_base() < __rhs._M_base(); }
00528 
00529   template<typename _Tp, typename _Alloc>
00530     inline bool
00531     operator<=(const vector<_Tp, _Alloc>& __lhs,
00532                const vector<_Tp, _Alloc>& __rhs)
00533     { return __lhs._M_base() <= __rhs._M_base(); }
00534 
00535   template<typename _Tp, typename _Alloc>
00536     inline bool
00537     operator>=(const vector<_Tp, _Alloc>& __lhs,
00538                const vector<_Tp, _Alloc>& __rhs)
00539     { return __lhs._M_base() >= __rhs._M_base(); }
00540 
00541   template<typename _Tp, typename _Alloc>
00542     inline bool
00543     operator>(const vector<_Tp, _Alloc>& __lhs,
00544               const vector<_Tp, _Alloc>& __rhs)
00545     { return __lhs._M_base() > __rhs._M_base(); }
00546 
00547   template<typename _Tp, typename _Alloc>
00548     inline void
00549     swap(vector<_Tp, _Alloc>& __lhs, vector<_Tp, _Alloc>& __rhs)
00550     { __lhs.swap(__rhs); }
00551 
00552 #if __cplusplus >= 201103L
00553   template<typename _Tp, typename _Alloc>
00554     inline void
00555     swap(vector<_Tp, _Alloc>&& __lhs, vector<_Tp, _Alloc>& __rhs)
00556     { __lhs.swap(__rhs); }
00557 
00558   template<typename _Tp, typename _Alloc>
00559     inline void
00560     swap(vector<_Tp, _Alloc>& __lhs, vector<_Tp, _Alloc>&& __rhs)
00561     { __lhs.swap(__rhs); }
00562 #endif
00563 
00564 } // namespace __profile
00565 
00566 #if __cplusplus >= 201103L
00567   // DR 1182.
00568   /// std::hash specialization for vector<bool>.
00569   template<typename _Alloc>
00570     struct hash<__profile::vector<bool, _Alloc>>
00571     : public __hash_base<size_t, __profile::vector<bool, _Alloc>>
00572     {
00573       size_t
00574       operator()(const __profile::vector<bool, _Alloc>& __b) const noexcept
00575       {
00576         return std::hash<_GLIBCXX_STD_C::vector<bool, _Alloc>>()(__b._M_base());
00577       }
00578     };
00579 #endif
00580 
00581 } // namespace std
00582 
00583 #endif