libstdc++
profile/map.h
Go to the documentation of this file.
00001 // Profiling map implementation -*- C++ -*-
00002 
00003 // Copyright (C) 2009, 2010, 2011 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 2, 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 // You should have received a copy of the GNU General Public License along
00017 // with this library; see the file COPYING.  If not, write to the Free
00018 // Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301,
00019 // USA.
00020 
00021 // As a special exception, you may use this file as part of a free software
00022 // library without restriction.  Specifically, if other files instantiate
00023 // templates or use macros or inline functions from this file, or you compile
00024 // this file and link it with other files to produce an executable, this
00025 // file does not by itself cause the resulting executable to be covered by
00026 // the GNU General Public License.  This exception does not however
00027 // invalidate any other reasons why the executable file might be covered by
00028 // the GNU General Public License.
00029 
00030 /** @file profile/map.h
00031  *  This file is a GNU profile extension to the Standard C++ Library.
00032  */
00033 
00034 #ifndef _GLIBCXX_PROFILE_MAP_H
00035 #define _GLIBCXX_PROFILE_MAP_H 1
00036 
00037 #include <utility>
00038 #include <profile/base.h>
00039 
00040 namespace std _GLIBCXX_VISIBILITY(default)
00041 {
00042 namespace __profile
00043 {
00044   /// Class std::map wrapper with performance instrumentation.
00045   template<typename _Key, typename _Tp, typename _Compare = std::less<_Key>,
00046        typename _Allocator = std::allocator<std::pair<const _Key, _Tp> > >
00047     class map
00048     : public _GLIBCXX_STD_C::map<_Key, _Tp, _Compare, _Allocator>
00049     {
00050       typedef _GLIBCXX_STD_C::map<_Key, _Tp, _Compare, _Allocator> _Base;
00051 
00052     public:
00053       // types:
00054       typedef _Key                                  key_type;
00055       typedef _Tp                                   mapped_type;
00056       typedef std::pair<const _Key, _Tp>            value_type;
00057       typedef _Compare                              key_compare;
00058       typedef _Allocator                            allocator_type;
00059       typedef typename _Base::reference             reference;
00060       typedef typename _Base::const_reference       const_reference;
00061 
00062       typedef typename _Base::iterator       iterator;
00063       typedef typename _Base::const_iterator       const_iterator;
00064       typedef typename _Base::size_type             size_type;
00065       typedef typename _Base::difference_type       difference_type;
00066       typedef typename _Base::pointer               pointer;
00067       typedef typename _Base::const_pointer         const_pointer;
00068       typedef std::reverse_iterator<iterator>       reverse_iterator;
00069       typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
00070 
00071       // 23.3.1.1 construct/copy/destroy:
00072       explicit
00073       map(const _Compare& __comp = _Compare(),
00074       const _Allocator& __a = _Allocator())
00075       : _Base(__comp, __a)
00076       { __profcxx_map_to_unordered_map_construct(this); }
00077 
00078       template<typename _InputIterator>
00079         map(_InputIterator __first, _InputIterator __last,
00080         const _Compare& __comp = _Compare(),
00081         const _Allocator& __a = _Allocator())
00082     : _Base(__first, __last, __comp, __a)
00083         { __profcxx_map_to_unordered_map_construct(this); }
00084 
00085       map(const map& __x)
00086       : _Base(__x)
00087       { __profcxx_map_to_unordered_map_construct(this); }
00088 
00089       map(const _Base& __x)
00090       : _Base(__x)
00091       { __profcxx_map_to_unordered_map_construct(this); }
00092 
00093 #ifdef __GXX_EXPERIMENTAL_CXX0X__
00094       map(map&& __x)
00095       : _Base(std::move(__x))
00096       { }
00097 
00098       map(initializer_list<value_type> __l,
00099       const _Compare& __c = _Compare(),
00100       const allocator_type& __a = allocator_type())
00101       : _Base(__l, __c, __a) { }
00102 #endif
00103 
00104       ~map()
00105       { __profcxx_map_to_unordered_map_destruct(this); }
00106 
00107       map&
00108       operator=(const map& __x)
00109       {
00110     *static_cast<_Base*>(this) = __x;
00111     return *this;
00112       }
00113 
00114 #ifdef __GXX_EXPERIMENTAL_CXX0X__
00115       map&
00116       operator=(map&& __x)
00117       {
00118     // NB: DR 1204.
00119     // NB: DR 675.
00120     this->clear();
00121     this->swap(__x);
00122     return *this;
00123       }
00124 
00125       map&
00126       operator=(initializer_list<value_type> __l)
00127       {
00128     this->clear();
00129     this->insert(__l);
00130     return *this;
00131       }
00132 #endif
00133 
00134       // _GLIBCXX_RESOLVE_LIB_DEFECTS
00135       // 133. map missing get_allocator()
00136       using _Base::get_allocator;
00137 
00138       // iterators:
00139       iterator 
00140       begin()
00141       { return _Base::begin(); }
00142 
00143       const_iterator
00144       begin() const
00145       { return _Base::begin(); }
00146 
00147       iterator
00148       end()
00149       { return _Base::end(); }
00150 
00151       const_iterator
00152       end() const
00153       { return _Base::end(); }
00154 
00155       reverse_iterator
00156       rbegin()
00157       { 
00158         __profcxx_map_to_unordered_map_invalidate(this);
00159         return reverse_iterator(end()); 
00160       }
00161 
00162       const_reverse_iterator
00163       rbegin() const
00164       {
00165         __profcxx_map_to_unordered_map_invalidate(this);
00166         return const_reverse_iterator(end());
00167       }
00168 
00169       reverse_iterator
00170       rend()
00171       {
00172         __profcxx_map_to_unordered_map_invalidate(this);
00173         return reverse_iterator(begin());
00174       }
00175 
00176       const_reverse_iterator
00177       rend() const
00178       {
00179         __profcxx_map_to_unordered_map_invalidate(this);
00180         return const_reverse_iterator(begin());
00181       }
00182 
00183 #ifdef __GXX_EXPERIMENTAL_CXX0X__
00184       const_iterator
00185       cbegin() const
00186       { return const_iterator(_Base::begin()); }
00187 
00188       const_iterator
00189       cend() const
00190       { return const_iterator(_Base::end()); }
00191 
00192       const_reverse_iterator
00193       crbegin() const
00194       {
00195         __profcxx_map_to_unordered_map_invalidate(this);
00196         return const_reverse_iterator(end());
00197       }
00198 
00199       const_reverse_iterator
00200       crend() const
00201       {
00202         __profcxx_map_to_unordered_map_invalidate(this);
00203         return const_reverse_iterator(begin());
00204       }
00205 #endif
00206 
00207       // capacity:
00208       using _Base::empty;
00209       using _Base::size;
00210       using _Base::max_size;
00211 
00212       // 23.3.1.2 element access:
00213       mapped_type&
00214       operator[](const key_type& __k)
00215       {
00216         __profcxx_map_to_unordered_map_find(this, size());
00217         return _Base::operator[](__k);
00218       }
00219 
00220 #ifdef __GXX_EXPERIMENTAL_CXX0X__
00221       mapped_type&
00222       operator[](key_type&& __k)
00223       {
00224         __profcxx_map_to_unordered_map_find(this, size());
00225         return _Base::operator[](std::move(__k));
00226       }
00227 #endif
00228 
00229       mapped_type&
00230       at(const key_type& __k)
00231       {
00232         __profcxx_map_to_unordered_map_find(this, size());
00233         return _Base::at(__k);
00234       }
00235 
00236       const mapped_type&
00237       at(const key_type& __k) const
00238       {
00239         __profcxx_map_to_unordered_map_find(this, size());
00240         return _Base::at(__k);
00241       }
00242 
00243       // modifiers:
00244       std::pair<iterator, bool>
00245       insert(const value_type& __x)
00246       {
00247         __profcxx_map_to_unordered_map_insert(this, size(), 1);
00248     typedef typename _Base::iterator _Base_iterator;
00249     std::pair<_Base_iterator, bool> __res = _Base::insert(__x);
00250     return std::pair<iterator, bool>(iterator(__res.first),
00251                      __res.second);
00252       }
00253 
00254 #ifdef __GXX_EXPERIMENTAL_CXX0X__
00255       template<typename _Pair, typename = typename
00256            std::enable_if<std::is_convertible<_Pair,
00257                           value_type>::value>::type>
00258         std::pair<iterator, bool>
00259         insert(_Pair&& __x)
00260         {
00261       __profcxx_map_to_unordered_map_insert(this, size(), 1);
00262       typedef typename _Base::iterator _Base_iterator;
00263       std::pair<_Base_iterator, bool> __res
00264         = _Base::insert(std::forward<_Pair>(__x));
00265       return std::pair<iterator, bool>(iterator(__res.first),
00266                        __res.second);
00267     }
00268 #endif
00269 
00270 #ifdef __GXX_EXPERIMENTAL_CXX0X__
00271       void
00272       insert(std::initializer_list<value_type> __list)
00273       { 
00274         size_type size_before = size();
00275         _Base::insert(__list); 
00276         __profcxx_map_to_unordered_map_insert(this, size_before, 
00277                           size() - size_before);
00278       }
00279 #endif
00280 
00281       iterator
00282 #ifdef __GXX_EXPERIMENTAL_CXX0X__
00283       insert(const_iterator __position, const value_type& __x)
00284 #else
00285       insert(iterator __position, const value_type& __x)
00286 #endif
00287       {
00288         size_type size_before = size();
00289     iterator __i = iterator(_Base::insert(__position, __x));
00290         __profcxx_map_to_unordered_map_insert(this, size_before, 
00291                           size() - size_before);
00292     return __i;
00293       }
00294 
00295 #ifdef __GXX_EXPERIMENTAL_CXX0X__
00296       template<typename _Pair, typename = typename
00297            std::enable_if<std::is_convertible<_Pair,
00298                           value_type>::value>::type>
00299         iterator
00300         insert(const_iterator __position, _Pair&& __x)
00301         {
00302       size_type size_before = size();
00303       iterator __i
00304         = iterator(_Base::insert(__position, std::forward<_Pair>(__x)));
00305       __profcxx_map_to_unordered_map_insert(this, size_before, 
00306                         size() - size_before);
00307       return __i;
00308       }
00309 #endif
00310 
00311       template<typename _InputIterator>
00312         void
00313         insert(_InputIterator __first, _InputIterator __last)
00314         {
00315           size_type size_before = size();
00316       _Base::insert(__first, __last);
00317           __profcxx_map_to_unordered_map_insert(this, size_before, 
00318                                                 size() - size_before);
00319     }
00320 
00321 #ifdef __GXX_EXPERIMENTAL_CXX0X__
00322       iterator
00323       erase(const_iterator __position)
00324       {
00325     iterator __i = _Base::erase(__position);
00326         __profcxx_map_to_unordered_map_erase(this, size(), 1);
00327         return __i;
00328       }
00329 #else
00330       void
00331       erase(iterator __position)
00332       {
00333     _Base::erase(__position);
00334         __profcxx_map_to_unordered_map_erase(this, size(), 1);
00335       }
00336 #endif
00337 
00338       size_type
00339       erase(const key_type& __x)
00340       {
00341     iterator __victim = find(__x);
00342     if (__victim == end())
00343       return 0;
00344     else
00345     {
00346       _Base::erase(__victim);
00347       return 1;
00348     }
00349       }
00350 
00351 #ifdef __GXX_EXPERIMENTAL_CXX0X__
00352       iterator
00353       erase(const_iterator __first, const_iterator __last)
00354       { return iterator(_Base::erase(__first, __last)); }
00355 #else
00356       void
00357       erase(iterator __first, iterator __last)
00358       { _Base::erase(__first, __last); }
00359 #endif
00360 
00361       void
00362 
00363       swap(map& __x)
00364       { _Base::swap(__x); }
00365 
00366       void
00367       clear()
00368       { this->erase(begin(), end()); }
00369 
00370       // observers:
00371       using _Base::key_comp;
00372       using _Base::value_comp;
00373 
00374       // 23.3.1.3 map operations:
00375       iterator
00376       find(const key_type& __x)
00377       {
00378         __profcxx_map_to_unordered_map_find(this, size());
00379         return iterator(_Base::find(__x));
00380       }
00381 
00382       const_iterator
00383       find(const key_type& __x) const
00384       {
00385         __profcxx_map_to_unordered_map_find(this, size());
00386         return const_iterator(_Base::find(__x));
00387       }
00388 
00389       size_type
00390       count(const key_type& __x) const
00391       {
00392         __profcxx_map_to_unordered_map_find(this, size());
00393         return _Base::count(__x);
00394       }
00395 
00396       iterator
00397       lower_bound(const key_type& __x)
00398       { 
00399         __profcxx_map_to_unordered_map_invalidate(this);
00400         return iterator(_Base::lower_bound(__x)); 
00401       }
00402 
00403       const_iterator
00404       lower_bound(const key_type& __x) const
00405       { 
00406         __profcxx_map_to_unordered_map_invalidate(this);
00407         return const_iterator(_Base::lower_bound(__x)); 
00408       }
00409 
00410       iterator
00411       upper_bound(const key_type& __x)
00412       { 
00413         __profcxx_map_to_unordered_map_invalidate(this);
00414         return iterator(_Base::upper_bound(__x)); 
00415       }
00416 
00417       const_iterator
00418       upper_bound(const key_type& __x) const
00419       { 
00420         __profcxx_map_to_unordered_map_invalidate(this);
00421         return const_iterator(_Base::upper_bound(__x)); 
00422       }
00423 
00424       std::pair<iterator,iterator>
00425       equal_range(const key_type& __x)
00426       {
00427     typedef typename _Base::iterator _Base_iterator;
00428     std::pair<_Base_iterator, _Base_iterator> __res =
00429     _Base::equal_range(__x);
00430     return std::make_pair(iterator(__res.first),
00431                   iterator(__res.second));
00432       }
00433 
00434       std::pair<const_iterator,const_iterator>
00435       equal_range(const key_type& __x) const
00436       {
00437         __profcxx_map_to_unordered_map_find(this, size());
00438     typedef typename _Base::const_iterator _Base_const_iterator;
00439     std::pair<_Base_const_iterator, _Base_const_iterator> __res =
00440     _Base::equal_range(__x);
00441     return std::make_pair(const_iterator(__res.first),
00442                   const_iterator(__res.second));
00443       }
00444 
00445       _Base& 
00446       _M_base() { return *this; }
00447 
00448       const _Base&
00449       _M_base() const { return *this; }
00450 
00451     };
00452 
00453   template<typename _Key, typename _Tp,
00454        typename _Compare, typename _Allocator>
00455     inline bool
00456     operator==(const map<_Key, _Tp, _Compare, _Allocator>& __lhs,
00457            const map<_Key, _Tp, _Compare, _Allocator>& __rhs)
00458     { 
00459       __profcxx_map_to_unordered_map_invalidate(&__lhs);
00460       __profcxx_map_to_unordered_map_invalidate(&__rhs);
00461       return __lhs._M_base() == __rhs._M_base(); 
00462     }
00463 
00464   template<typename _Key, typename _Tp,
00465        typename _Compare, typename _Allocator>
00466     inline bool
00467     operator!=(const map<_Key, _Tp, _Compare, _Allocator>& __lhs,
00468            const map<_Key, _Tp, _Compare, _Allocator>& __rhs)
00469     { 
00470       __profcxx_map_to_unordered_map_invalidate(&__lhs);
00471       __profcxx_map_to_unordered_map_invalidate(&__rhs);
00472       return __lhs._M_base() != __rhs._M_base(); 
00473     }
00474 
00475   template<typename _Key, typename _Tp,
00476        typename _Compare, typename _Allocator>
00477     inline bool
00478     operator<(const map<_Key, _Tp, _Compare, _Allocator>& __lhs,
00479           const map<_Key, _Tp, _Compare, _Allocator>& __rhs)
00480     {
00481       __profcxx_map_to_unordered_map_invalidate(&__lhs);
00482       __profcxx_map_to_unordered_map_invalidate(&__rhs);
00483       return __lhs._M_base() < __rhs._M_base(); 
00484     }
00485 
00486   template<typename _Key, typename _Tp,
00487        typename _Compare, typename _Allocator>
00488     inline bool
00489     operator<=(const map<_Key, _Tp, _Compare, _Allocator>& __lhs,
00490            const map<_Key, _Tp, _Compare, _Allocator>& __rhs)
00491     {
00492       __profcxx_map_to_unordered_map_invalidate(&__lhs);
00493       __profcxx_map_to_unordered_map_invalidate(&__rhs);
00494       return __lhs._M_base() <= __rhs._M_base();
00495     }
00496 
00497   template<typename _Key, typename _Tp,
00498        typename _Compare, typename _Allocator>
00499     inline bool
00500     operator>=(const map<_Key, _Tp, _Compare, _Allocator>& __lhs,
00501            const map<_Key, _Tp, _Compare, _Allocator>& __rhs)
00502     {
00503       __profcxx_map_to_unordered_map_invalidate(&__lhs);
00504       __profcxx_map_to_unordered_map_invalidate(&__rhs);
00505       return __lhs._M_base() >= __rhs._M_base();
00506     }
00507 
00508   template<typename _Key, typename _Tp,
00509        typename _Compare, typename _Allocator>
00510     inline bool
00511     operator>(const map<_Key, _Tp, _Compare, _Allocator>& __lhs,
00512           const map<_Key, _Tp, _Compare, _Allocator>& __rhs)
00513     {
00514       __profcxx_map_to_unordered_map_invalidate(&__lhs);
00515       __profcxx_map_to_unordered_map_invalidate(&__rhs);
00516       return __lhs._M_base() > __rhs._M_base();
00517     }
00518 
00519   template<typename _Key, typename _Tp,
00520        typename _Compare, typename _Allocator>
00521     inline void
00522     swap(map<_Key, _Tp, _Compare, _Allocator>& __lhs,
00523      map<_Key, _Tp, _Compare, _Allocator>& __rhs)
00524     { __lhs.swap(__rhs); }
00525 
00526 } // namespace __profile
00527 } // namespace std
00528 
00529 #endif