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 
00330       iterator
00331       erase(iterator __position)
00332       { return erase(const_iterator(__position)); }
00333 #else
00334       void
00335       erase(iterator __position)
00336       {
00337     _Base::erase(__position);
00338         __profcxx_map_to_unordered_map_erase(this, size(), 1);
00339       }
00340 #endif
00341 
00342       size_type
00343       erase(const key_type& __x)
00344       {
00345     iterator __victim = find(__x);
00346     if (__victim == end())
00347       return 0;
00348     else
00349     {
00350       _Base::erase(__victim);
00351       return 1;
00352     }
00353       }
00354 
00355 #ifdef __GXX_EXPERIMENTAL_CXX0X__
00356       iterator
00357       erase(const_iterator __first, const_iterator __last)
00358       { return iterator(_Base::erase(__first, __last)); }
00359 #else
00360       void
00361       erase(iterator __first, iterator __last)
00362       { _Base::erase(__first, __last); }
00363 #endif
00364 
00365       void
00366 
00367       swap(map& __x)
00368       { _Base::swap(__x); }
00369 
00370       void
00371       clear()
00372       { this->erase(begin(), end()); }
00373 
00374       // observers:
00375       using _Base::key_comp;
00376       using _Base::value_comp;
00377 
00378       // 23.3.1.3 map operations:
00379       iterator
00380       find(const key_type& __x)
00381       {
00382         __profcxx_map_to_unordered_map_find(this, size());
00383         return iterator(_Base::find(__x));
00384       }
00385 
00386       const_iterator
00387       find(const key_type& __x) const
00388       {
00389         __profcxx_map_to_unordered_map_find(this, size());
00390         return const_iterator(_Base::find(__x));
00391       }
00392 
00393       size_type
00394       count(const key_type& __x) const
00395       {
00396         __profcxx_map_to_unordered_map_find(this, size());
00397         return _Base::count(__x);
00398       }
00399 
00400       iterator
00401       lower_bound(const key_type& __x)
00402       { 
00403         __profcxx_map_to_unordered_map_invalidate(this);
00404         return iterator(_Base::lower_bound(__x)); 
00405       }
00406 
00407       const_iterator
00408       lower_bound(const key_type& __x) const
00409       { 
00410         __profcxx_map_to_unordered_map_invalidate(this);
00411         return const_iterator(_Base::lower_bound(__x)); 
00412       }
00413 
00414       iterator
00415       upper_bound(const key_type& __x)
00416       { 
00417         __profcxx_map_to_unordered_map_invalidate(this);
00418         return iterator(_Base::upper_bound(__x)); 
00419       }
00420 
00421       const_iterator
00422       upper_bound(const key_type& __x) const
00423       { 
00424         __profcxx_map_to_unordered_map_invalidate(this);
00425         return const_iterator(_Base::upper_bound(__x)); 
00426       }
00427 
00428       std::pair<iterator,iterator>
00429       equal_range(const key_type& __x)
00430       {
00431     typedef typename _Base::iterator _Base_iterator;
00432     std::pair<_Base_iterator, _Base_iterator> __res =
00433     _Base::equal_range(__x);
00434     return std::make_pair(iterator(__res.first),
00435                   iterator(__res.second));
00436       }
00437 
00438       std::pair<const_iterator,const_iterator>
00439       equal_range(const key_type& __x) const
00440       {
00441         __profcxx_map_to_unordered_map_find(this, size());
00442     typedef typename _Base::const_iterator _Base_const_iterator;
00443     std::pair<_Base_const_iterator, _Base_const_iterator> __res =
00444     _Base::equal_range(__x);
00445     return std::make_pair(const_iterator(__res.first),
00446                   const_iterator(__res.second));
00447       }
00448 
00449       _Base& 
00450       _M_base() { return *this; }
00451 
00452       const _Base&
00453       _M_base() const { return *this; }
00454 
00455     };
00456 
00457   template<typename _Key, typename _Tp,
00458        typename _Compare, typename _Allocator>
00459     inline bool
00460     operator==(const map<_Key, _Tp, _Compare, _Allocator>& __lhs,
00461            const map<_Key, _Tp, _Compare, _Allocator>& __rhs)
00462     { 
00463       __profcxx_map_to_unordered_map_invalidate(&__lhs);
00464       __profcxx_map_to_unordered_map_invalidate(&__rhs);
00465       return __lhs._M_base() == __rhs._M_base(); 
00466     }
00467 
00468   template<typename _Key, typename _Tp,
00469        typename _Compare, typename _Allocator>
00470     inline bool
00471     operator!=(const map<_Key, _Tp, _Compare, _Allocator>& __lhs,
00472            const map<_Key, _Tp, _Compare, _Allocator>& __rhs)
00473     { 
00474       __profcxx_map_to_unordered_map_invalidate(&__lhs);
00475       __profcxx_map_to_unordered_map_invalidate(&__rhs);
00476       return __lhs._M_base() != __rhs._M_base(); 
00477     }
00478 
00479   template<typename _Key, typename _Tp,
00480        typename _Compare, typename _Allocator>
00481     inline bool
00482     operator<(const map<_Key, _Tp, _Compare, _Allocator>& __lhs,
00483           const map<_Key, _Tp, _Compare, _Allocator>& __rhs)
00484     {
00485       __profcxx_map_to_unordered_map_invalidate(&__lhs);
00486       __profcxx_map_to_unordered_map_invalidate(&__rhs);
00487       return __lhs._M_base() < __rhs._M_base(); 
00488     }
00489 
00490   template<typename _Key, typename _Tp,
00491        typename _Compare, typename _Allocator>
00492     inline bool
00493     operator<=(const map<_Key, _Tp, _Compare, _Allocator>& __lhs,
00494            const map<_Key, _Tp, _Compare, _Allocator>& __rhs)
00495     {
00496       __profcxx_map_to_unordered_map_invalidate(&__lhs);
00497       __profcxx_map_to_unordered_map_invalidate(&__rhs);
00498       return __lhs._M_base() <= __rhs._M_base();
00499     }
00500 
00501   template<typename _Key, typename _Tp,
00502        typename _Compare, typename _Allocator>
00503     inline bool
00504     operator>=(const map<_Key, _Tp, _Compare, _Allocator>& __lhs,
00505            const map<_Key, _Tp, _Compare, _Allocator>& __rhs)
00506     {
00507       __profcxx_map_to_unordered_map_invalidate(&__lhs);
00508       __profcxx_map_to_unordered_map_invalidate(&__rhs);
00509       return __lhs._M_base() >= __rhs._M_base();
00510     }
00511 
00512   template<typename _Key, typename _Tp,
00513        typename _Compare, typename _Allocator>
00514     inline bool
00515     operator>(const map<_Key, _Tp, _Compare, _Allocator>& __lhs,
00516           const map<_Key, _Tp, _Compare, _Allocator>& __rhs)
00517     {
00518       __profcxx_map_to_unordered_map_invalidate(&__lhs);
00519       __profcxx_map_to_unordered_map_invalidate(&__rhs);
00520       return __lhs._M_base() > __rhs._M_base();
00521     }
00522 
00523   template<typename _Key, typename _Tp,
00524        typename _Compare, typename _Allocator>
00525     inline void
00526     swap(map<_Key, _Tp, _Compare, _Allocator>& __lhs,
00527      map<_Key, _Tp, _Compare, _Allocator>& __rhs)
00528     { __lhs.swap(__rhs); }
00529 
00530 } // namespace __profile
00531 } // namespace std
00532 
00533 #endif