libstdc++
map.h
Go to the documentation of this file.
00001 // Profiling map 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/map.h
00025  *  This file is a GNU profile extension to the Standard C++ Library.
00026  */
00027 
00028 #ifndef _GLIBCXX_PROFILE_MAP_H
00029 #define _GLIBCXX_PROFILE_MAP_H 1
00030 
00031 #include <utility>
00032 #include <profile/base.h>
00033 
00034 namespace std _GLIBCXX_VISIBILITY(default)
00035 {
00036 namespace __profile
00037 {
00038   /// Class std::map wrapper with performance instrumentation.
00039   template<typename _Key, typename _Tp, typename _Compare = std::less<_Key>,
00040        typename _Allocator = std::allocator<std::pair<const _Key, _Tp> > >
00041     class map
00042     : public _GLIBCXX_STD_C::map<_Key, _Tp, _Compare, _Allocator>
00043     {
00044       typedef _GLIBCXX_STD_C::map<_Key, _Tp, _Compare, _Allocator> _Base;
00045 
00046 #if __cplusplus >= 201103L
00047       typedef __gnu_cxx::__alloc_traits<_Allocator> _Alloc_traits;
00048 #endif
00049 
00050     public:
00051       // types:
00052       typedef _Key                                  key_type;
00053       typedef _Tp                                   mapped_type;
00054       typedef std::pair<const _Key, _Tp>            value_type;
00055       typedef _Compare                              key_compare;
00056       typedef _Allocator                            allocator_type;
00057       typedef typename _Base::reference             reference;
00058       typedef typename _Base::const_reference       const_reference;
00059 
00060       typedef typename _Base::iterator       iterator;
00061       typedef typename _Base::const_iterator       const_iterator;
00062       typedef typename _Base::size_type             size_type;
00063       typedef typename _Base::difference_type       difference_type;
00064       typedef typename _Base::pointer               pointer;
00065       typedef typename _Base::const_pointer         const_pointer;
00066       typedef std::reverse_iterator<iterator>       reverse_iterator;
00067       typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
00068 
00069       // 23.3.1.1 construct/copy/destroy:
00070 
00071       map()
00072       : _Base()
00073       { __profcxx_map_to_unordered_map_construct(this); }
00074 
00075       explicit
00076       map(const _Compare& __comp,
00077       const _Allocator& __a = _Allocator())
00078       : _Base(__comp, __a)
00079       { __profcxx_map_to_unordered_map_construct(this); }
00080 
00081 #if __cplusplus >= 201103L
00082       template<typename _InputIterator,
00083            typename = std::_RequireInputIter<_InputIterator>>
00084 #else
00085       template<typename _InputIterator>
00086 #endif
00087         map(_InputIterator __first, _InputIterator __last,
00088         const _Compare& __comp = _Compare(),
00089         const _Allocator& __a = _Allocator())
00090     : _Base(__first, __last, __comp, __a)
00091         { __profcxx_map_to_unordered_map_construct(this); }
00092 
00093       map(const map& __x)
00094       : _Base(__x)
00095       { __profcxx_map_to_unordered_map_construct(this); }
00096 
00097       map(const _Base& __x)
00098       : _Base(__x)
00099       { __profcxx_map_to_unordered_map_construct(this); }
00100 
00101 #if __cplusplus >= 201103L
00102       map(map&& __x)
00103       noexcept(is_nothrow_copy_constructible<_Compare>::value)
00104       : _Base(std::move(__x))
00105       { __profcxx_map_to_unordered_map_construct(this); }
00106 
00107       map(initializer_list<value_type> __l,
00108       const _Compare& __c = _Compare(),
00109       const allocator_type& __a = allocator_type())
00110       : _Base(__l, __c, __a)
00111       { __profcxx_map_to_unordered_map_construct(this); }
00112 
00113       explicit
00114       map(const allocator_type& __a)
00115     : _Base(__a)
00116       { __profcxx_map_to_unordered_map_construct(this); }
00117 
00118       map(const map& __x, const allocator_type& __a)
00119       : _Base(__x, __a)
00120       { __profcxx_map_to_unordered_map_construct(this); }
00121 
00122       map(map&& __x, const allocator_type& __a)
00123       noexcept(is_nothrow_copy_constructible<_Compare>::value
00124            && _Alloc_traits::_S_always_equal())
00125       : _Base(std::move(__x), __a)
00126       { __profcxx_map_to_unordered_map_construct(this); }
00127 
00128       map(initializer_list<value_type> __l, const allocator_type& __a)
00129       : _Base(__l, __a)
00130       { __profcxx_map_to_unordered_map_construct(this); }
00131 
00132       template<typename _InputIterator>
00133         map(_InputIterator __first, _InputIterator __last,
00134         const allocator_type& __a)
00135       : _Base(__first, __last, __a)
00136       { __profcxx_map_to_unordered_map_construct(this); }
00137 #endif
00138 
00139       ~map() _GLIBCXX_NOEXCEPT
00140       { __profcxx_map_to_unordered_map_destruct(this); }
00141 
00142 #if __cplusplus < 201103L
00143       map&
00144       operator=(const map& __x)
00145       {
00146     _M_base() = __x;
00147     return *this;
00148       }
00149 #else
00150       map&
00151       operator=(const map&) = default;
00152 
00153       map&
00154       operator=(map&&) = default;
00155 
00156       map&
00157       operator=(initializer_list<value_type> __l)
00158       {
00159     _M_base() = __l;
00160     return *this;
00161       }
00162 #endif
00163 
00164       // _GLIBCXX_RESOLVE_LIB_DEFECTS
00165       // 133. map missing get_allocator()
00166       using _Base::get_allocator;
00167 
00168       // iterators:
00169       iterator 
00170       begin() _GLIBCXX_NOEXCEPT
00171       { return _Base::begin(); }
00172 
00173       const_iterator
00174       begin() const _GLIBCXX_NOEXCEPT
00175       { return _Base::begin(); }
00176 
00177       iterator
00178       end() _GLIBCXX_NOEXCEPT
00179       { return _Base::end(); }
00180 
00181       const_iterator
00182       end() const _GLIBCXX_NOEXCEPT
00183       { return _Base::end(); }
00184 
00185       reverse_iterator
00186       rbegin() _GLIBCXX_NOEXCEPT
00187       { 
00188         __profcxx_map_to_unordered_map_invalidate(this);
00189         return reverse_iterator(end()); 
00190       }
00191 
00192       const_reverse_iterator
00193       rbegin() const _GLIBCXX_NOEXCEPT
00194       {
00195         __profcxx_map_to_unordered_map_invalidate(this);
00196         return const_reverse_iterator(end());
00197       }
00198 
00199       reverse_iterator
00200       rend() _GLIBCXX_NOEXCEPT
00201       {
00202         __profcxx_map_to_unordered_map_invalidate(this);
00203         return reverse_iterator(begin());
00204       }
00205 
00206       const_reverse_iterator
00207       rend() const _GLIBCXX_NOEXCEPT
00208       {
00209         __profcxx_map_to_unordered_map_invalidate(this);
00210         return const_reverse_iterator(begin());
00211       }
00212 
00213 #if __cplusplus >= 201103L
00214       const_iterator
00215       cbegin() const noexcept
00216       { return const_iterator(_Base::begin()); }
00217 
00218       const_iterator
00219       cend() const noexcept
00220       { return const_iterator(_Base::end()); }
00221 
00222       const_reverse_iterator
00223       crbegin() const noexcept
00224       {
00225         __profcxx_map_to_unordered_map_invalidate(this);
00226         return const_reverse_iterator(end());
00227       }
00228 
00229       const_reverse_iterator
00230       crend() const noexcept
00231       {
00232         __profcxx_map_to_unordered_map_invalidate(this);
00233         return const_reverse_iterator(begin());
00234       }
00235 #endif
00236 
00237       // capacity:
00238       using _Base::empty;
00239       using _Base::size;
00240       using _Base::max_size;
00241 
00242       // 23.3.1.2 element access:
00243       mapped_type&
00244       operator[](const key_type& __k)
00245       {
00246         __profcxx_map_to_unordered_map_find(this, size());
00247         return _Base::operator[](__k);
00248       }
00249 
00250 #if __cplusplus >= 201103L
00251       mapped_type&
00252       operator[](key_type&& __k)
00253       {
00254         __profcxx_map_to_unordered_map_find(this, size());
00255         return _Base::operator[](std::move(__k));
00256       }
00257 #endif
00258 
00259       mapped_type&
00260       at(const key_type& __k)
00261       {
00262         __profcxx_map_to_unordered_map_find(this, size());
00263         return _Base::at(__k);
00264       }
00265 
00266       const mapped_type&
00267       at(const key_type& __k) const
00268       {
00269         __profcxx_map_to_unordered_map_find(this, size());
00270         return _Base::at(__k);
00271       }
00272 
00273       // modifiers:
00274 #if __cplusplus >= 201103L
00275       template<typename... _Args>
00276     std::pair<iterator, bool>
00277     emplace(_Args&&... __args)
00278     {
00279       __profcxx_map_to_unordered_map_insert(this, size(), 1);
00280       auto __res = _Base::emplace(std::forward<_Args>(__args)...);
00281       return std::pair<iterator, bool>(iterator(__res.first),
00282                        __res.second);
00283     }
00284 
00285       template<typename... _Args>
00286     iterator
00287     emplace_hint(const_iterator __pos, _Args&&... __args)
00288     {
00289       size_type size_before = size();
00290       auto __res = _Base::emplace_hint(__pos,
00291                        std::forward<_Args>(__args)...);
00292       __profcxx_map_to_unordered_map_insert(this, size_before,
00293                         size() - size_before);
00294       return __res;
00295     }
00296 #endif
00297 
00298       std::pair<iterator, bool>
00299       insert(const value_type& __x)
00300       {
00301         __profcxx_map_to_unordered_map_insert(this, size(), 1);
00302     typedef typename _Base::iterator _Base_iterator;
00303     std::pair<_Base_iterator, bool> __res = _Base::insert(__x);
00304     return std::pair<iterator, bool>(iterator(__res.first),
00305                      __res.second);
00306       }
00307 
00308 #if __cplusplus >= 201103L
00309       template<typename _Pair, typename = typename
00310            std::enable_if<std::is_constructible<value_type,
00311                             _Pair&&>::value>::type>
00312         std::pair<iterator, bool>
00313         insert(_Pair&& __x)
00314         {
00315       __profcxx_map_to_unordered_map_insert(this, size(), 1);
00316       typedef typename _Base::iterator _Base_iterator;
00317       std::pair<_Base_iterator, bool> __res
00318         = _Base::insert(std::forward<_Pair>(__x));
00319       return std::pair<iterator, bool>(iterator(__res.first),
00320                        __res.second);
00321     }
00322 #endif
00323 
00324 #if __cplusplus >= 201103L
00325       void
00326       insert(std::initializer_list<value_type> __list)
00327       { 
00328         size_type size_before = size();
00329         _Base::insert(__list); 
00330         __profcxx_map_to_unordered_map_insert(this, size_before, 
00331                           size() - size_before);
00332       }
00333 #endif
00334 
00335       iterator
00336 #if __cplusplus >= 201103L
00337       insert(const_iterator __position, const value_type& __x)
00338 #else
00339       insert(iterator __position, const value_type& __x)
00340 #endif
00341       {
00342         size_type size_before = size();
00343     iterator __i = iterator(_Base::insert(__position, __x));
00344         __profcxx_map_to_unordered_map_insert(this, size_before,
00345                           size() - size_before);
00346     return __i;
00347       }
00348 
00349 #if __cplusplus >= 201103L
00350       template<typename _Pair, typename = typename
00351            std::enable_if<std::is_constructible<value_type,
00352                             _Pair&&>::value>::type>
00353         iterator
00354         insert(const_iterator __position, _Pair&& __x)
00355         {
00356       size_type size_before = size();
00357       iterator __i
00358         = iterator(_Base::insert(__position, std::forward<_Pair>(__x)));
00359       __profcxx_map_to_unordered_map_insert(this, size_before, 
00360                         size() - size_before);
00361       return __i;
00362       }
00363 #endif
00364 
00365 #if __cplusplus >= 201103L
00366       template<typename _InputIterator,
00367            typename = std::_RequireInputIter<_InputIterator>>
00368 #else
00369       template<typename _InputIterator>
00370 #endif
00371         void
00372         insert(_InputIterator __first, _InputIterator __last)
00373         {
00374           size_type size_before = size();
00375       _Base::insert(__first, __last);
00376           __profcxx_map_to_unordered_map_insert(this, size_before, 
00377                                                 size() - size_before);
00378     }
00379 
00380 #if __cplusplus >= 201103L
00381       iterator
00382       erase(const_iterator __position)
00383       {
00384     iterator __i = _Base::erase(__position);
00385         __profcxx_map_to_unordered_map_erase(this, size(), 1);
00386         return __i;
00387       }
00388 
00389       iterator
00390       erase(iterator __position)
00391       { return erase(const_iterator(__position)); }
00392 #else
00393       void
00394       erase(iterator __position)
00395       {
00396     _Base::erase(__position);
00397         __profcxx_map_to_unordered_map_erase(this, size(), 1);
00398       }
00399 #endif
00400 
00401       size_type
00402       erase(const key_type& __x)
00403       {
00404     iterator __victim = find(__x);
00405     if (__victim == end())
00406       return 0;
00407     else
00408     {
00409       _Base::erase(__victim);
00410       return 1;
00411     }
00412       }
00413 
00414 #if __cplusplus >= 201103L
00415       iterator
00416       erase(const_iterator __first, const_iterator __last)
00417       { return iterator(_Base::erase(__first, __last)); }
00418 #else
00419       void
00420       erase(iterator __first, iterator __last)
00421       { _Base::erase(__first, __last); }
00422 #endif
00423 
00424       void
00425       swap(map& __x)
00426 #if __cplusplus >= 201103L
00427       noexcept(_Alloc_traits::_S_nothrow_swap())
00428 #endif
00429       { _Base::swap(__x); }
00430 
00431       void
00432       clear() _GLIBCXX_NOEXCEPT
00433       { this->erase(begin(), end()); }
00434 
00435       // observers:
00436       using _Base::key_comp;
00437       using _Base::value_comp;
00438 
00439       // 23.3.1.3 map operations:
00440       iterator
00441       find(const key_type& __x)
00442       {
00443         __profcxx_map_to_unordered_map_find(this, size());
00444         return iterator(_Base::find(__x));
00445       }
00446 
00447       const_iterator
00448       find(const key_type& __x) const
00449       {
00450         __profcxx_map_to_unordered_map_find(this, size());
00451         return const_iterator(_Base::find(__x));
00452       }
00453 
00454       size_type
00455       count(const key_type& __x) const
00456       {
00457         __profcxx_map_to_unordered_map_find(this, size());
00458         return _Base::count(__x);
00459       }
00460 
00461       iterator
00462       lower_bound(const key_type& __x)
00463       { 
00464         __profcxx_map_to_unordered_map_invalidate(this);
00465         return iterator(_Base::lower_bound(__x)); 
00466       }
00467 
00468       const_iterator
00469       lower_bound(const key_type& __x) const
00470       { 
00471         __profcxx_map_to_unordered_map_invalidate(this);
00472         return const_iterator(_Base::lower_bound(__x)); 
00473       }
00474 
00475       iterator
00476       upper_bound(const key_type& __x)
00477       { 
00478         __profcxx_map_to_unordered_map_invalidate(this);
00479         return iterator(_Base::upper_bound(__x)); 
00480       }
00481 
00482       const_iterator
00483       upper_bound(const key_type& __x) const
00484       { 
00485         __profcxx_map_to_unordered_map_invalidate(this);
00486         return const_iterator(_Base::upper_bound(__x)); 
00487       }
00488 
00489       std::pair<iterator,iterator>
00490       equal_range(const key_type& __x)
00491       {
00492     typedef typename _Base::iterator _Base_iterator;
00493     std::pair<_Base_iterator, _Base_iterator> __res =
00494     _Base::equal_range(__x);
00495     return std::make_pair(iterator(__res.first),
00496                   iterator(__res.second));
00497       }
00498 
00499       std::pair<const_iterator,const_iterator>
00500       equal_range(const key_type& __x) const
00501       {
00502         __profcxx_map_to_unordered_map_find(this, size());
00503     typedef typename _Base::const_iterator _Base_const_iterator;
00504     std::pair<_Base_const_iterator, _Base_const_iterator> __res =
00505     _Base::equal_range(__x);
00506     return std::make_pair(const_iterator(__res.first),
00507                   const_iterator(__res.second));
00508       }
00509 
00510       _Base& 
00511       _M_base() _GLIBCXX_NOEXCEPT       { return *this; }
00512 
00513       const _Base&
00514       _M_base() const _GLIBCXX_NOEXCEPT { return *this; }
00515 
00516     };
00517 
00518   template<typename _Key, typename _Tp,
00519        typename _Compare, typename _Allocator>
00520     inline bool
00521     operator==(const map<_Key, _Tp, _Compare, _Allocator>& __lhs,
00522            const map<_Key, _Tp, _Compare, _Allocator>& __rhs)
00523     { 
00524       __profcxx_map_to_unordered_map_invalidate(&__lhs);
00525       __profcxx_map_to_unordered_map_invalidate(&__rhs);
00526       return __lhs._M_base() == __rhs._M_base(); 
00527     }
00528 
00529   template<typename _Key, typename _Tp,
00530        typename _Compare, typename _Allocator>
00531     inline bool
00532     operator!=(const map<_Key, _Tp, _Compare, _Allocator>& __lhs,
00533            const map<_Key, _Tp, _Compare, _Allocator>& __rhs)
00534     { 
00535       __profcxx_map_to_unordered_map_invalidate(&__lhs);
00536       __profcxx_map_to_unordered_map_invalidate(&__rhs);
00537       return __lhs._M_base() != __rhs._M_base(); 
00538     }
00539 
00540   template<typename _Key, typename _Tp,
00541        typename _Compare, typename _Allocator>
00542     inline bool
00543     operator<(const map<_Key, _Tp, _Compare, _Allocator>& __lhs,
00544           const map<_Key, _Tp, _Compare, _Allocator>& __rhs)
00545     {
00546       __profcxx_map_to_unordered_map_invalidate(&__lhs);
00547       __profcxx_map_to_unordered_map_invalidate(&__rhs);
00548       return __lhs._M_base() < __rhs._M_base(); 
00549     }
00550 
00551   template<typename _Key, typename _Tp,
00552        typename _Compare, typename _Allocator>
00553     inline bool
00554     operator<=(const map<_Key, _Tp, _Compare, _Allocator>& __lhs,
00555            const map<_Key, _Tp, _Compare, _Allocator>& __rhs)
00556     {
00557       __profcxx_map_to_unordered_map_invalidate(&__lhs);
00558       __profcxx_map_to_unordered_map_invalidate(&__rhs);
00559       return __lhs._M_base() <= __rhs._M_base();
00560     }
00561 
00562   template<typename _Key, typename _Tp,
00563        typename _Compare, typename _Allocator>
00564     inline bool
00565     operator>=(const map<_Key, _Tp, _Compare, _Allocator>& __lhs,
00566            const map<_Key, _Tp, _Compare, _Allocator>& __rhs)
00567     {
00568       __profcxx_map_to_unordered_map_invalidate(&__lhs);
00569       __profcxx_map_to_unordered_map_invalidate(&__rhs);
00570       return __lhs._M_base() >= __rhs._M_base();
00571     }
00572 
00573   template<typename _Key, typename _Tp,
00574        typename _Compare, typename _Allocator>
00575     inline bool
00576     operator>(const map<_Key, _Tp, _Compare, _Allocator>& __lhs,
00577           const map<_Key, _Tp, _Compare, _Allocator>& __rhs)
00578     {
00579       __profcxx_map_to_unordered_map_invalidate(&__lhs);
00580       __profcxx_map_to_unordered_map_invalidate(&__rhs);
00581       return __lhs._M_base() > __rhs._M_base();
00582     }
00583 
00584   template<typename _Key, typename _Tp,
00585        typename _Compare, typename _Allocator>
00586     inline void
00587     swap(map<_Key, _Tp, _Compare, _Allocator>& __lhs,
00588      map<_Key, _Tp, _Compare, _Allocator>& __rhs)
00589     { __lhs.swap(__rhs); }
00590 
00591 } // namespace __profile
00592 } // namespace std
00593 
00594 #endif