libstdc++
unordered_set
Go to the documentation of this file.
00001 // Profiling unordered_set/unordered_multiset 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/unordered_set
00025  *  This file is a GNU profile extension to the Standard C++ Library.
00026  */
00027 
00028 #ifndef _GLIBCXX_PROFILE_UNORDERED_SET
00029 #define _GLIBCXX_PROFILE_UNORDERED_SET 1
00030 
00031 #if __cplusplus < 201103L
00032 # include <bits/c++0x_warning.h>
00033 #else
00034 # include <unordered_set>
00035 
00036 #include <profile/base.h>
00037 #include <profile/unordered_base.h>
00038 
00039 #define _GLIBCXX_BASE unordered_set<_Key, _Hash, _Pred, _Alloc>
00040 #define _GLIBCXX_STD_BASE _GLIBCXX_STD_C::_GLIBCXX_BASE
00041 
00042 namespace std _GLIBCXX_VISIBILITY(default)
00043 {
00044 namespace __profile
00045 {
00046   /** @brief Unordered_set wrapper with performance instrumentation.  */
00047   template<typename _Key, 
00048        typename _Hash = std::hash<_Key>,
00049        typename _Pred = std::equal_to<_Key>,
00050        typename _Alloc =  std::allocator<_Key> >
00051     class unordered_set
00052     : public _GLIBCXX_STD_BASE,
00053       public _Unordered_profile<unordered_set<_Key, _Hash, _Pred, _Alloc>,
00054                 true>
00055     {
00056       typedef _GLIBCXX_STD_BASE _Base;
00057 
00058       _Base&
00059       _M_base() noexcept       { return *this; }
00060 
00061       const _Base&
00062       _M_base() const noexcept { return *this; }
00063 
00064     public:
00065       typedef typename _Base::size_type       size_type;
00066       typedef typename _Base::hasher          hasher;
00067       typedef typename _Base::key_equal       key_equal;
00068       typedef typename _Base::allocator_type  allocator_type;
00069       typedef typename _Base::key_type        key_type;
00070       typedef typename _Base::value_type      value_type;
00071       typedef typename _Base::difference_type difference_type;
00072       typedef typename _Base::reference       reference;
00073       typedef typename _Base::const_reference const_reference;
00074 
00075       typedef typename _Base::iterator iterator;
00076       typedef typename _Base::const_iterator const_iterator;
00077 
00078       explicit
00079       unordered_set(size_type __n = 10,
00080             const hasher& __hf = hasher(),
00081             const key_equal& __eql = key_equal(),
00082             const allocator_type& __a = allocator_type())
00083     : _Base(__n, __hf, __eql, __a)
00084       { }
00085 
00086       template<typename _InputIterator>
00087         unordered_set(_InputIterator __f, _InputIterator __l,
00088               size_type __n = 0,
00089               const hasher& __hf = hasher(),
00090               const key_equal& __eql = key_equal(),
00091               const allocator_type& __a = allocator_type())
00092       : _Base(__f, __l, __n, __hf, __eql, __a)
00093       { }
00094 
00095       unordered_set(const unordered_set&) = default;
00096 
00097       unordered_set(const _Base& __x)
00098     : _Base(__x)
00099       { }
00100 
00101       unordered_set(unordered_set&&) = default;
00102 
00103       explicit
00104       unordered_set(const allocator_type& __a)
00105     : _Base(__a)
00106       { }
00107 
00108       unordered_set(const unordered_set& __uset,
00109             const allocator_type& __a)
00110     : _Base(__uset._M_base(), __a)
00111       { }
00112 
00113       unordered_set(unordered_set&& __uset,
00114             const allocator_type& __a)
00115     : _Base(std::move(__uset._M_base()), __a)
00116       { }
00117 
00118       unordered_set(initializer_list<value_type> __l,
00119             size_type __n = 0,
00120             const hasher& __hf = hasher(),
00121             const key_equal& __eql = key_equal(),
00122             const allocator_type& __a = allocator_type())
00123       : _Base(__l, __n, __hf, __eql, __a)
00124       { }
00125 
00126       unordered_set&
00127       operator=(const unordered_set&) = default;
00128 
00129       unordered_set&
00130       operator=(unordered_set&&) = default;
00131 
00132       unordered_set&
00133       operator=(initializer_list<value_type> __l)
00134       {
00135     _M_base() = __l;
00136     return *this;
00137       }
00138 
00139       void
00140       swap(unordered_set& __x)
00141       noexcept( noexcept(__x._M_base().swap(__x)) )
00142       { _Base::swap(__x); }
00143 
00144       void
00145       clear() noexcept
00146       {
00147         __profcxx_hashtable_destruct(this, _Base::bucket_count(), 
00148                                      _Base::size());
00149         this->_M_profile_destruct();
00150         _Base::clear();
00151       }
00152 
00153       template<typename... _Args>
00154     std::pair<iterator, bool>
00155     emplace(_Args&&... __args)
00156     {
00157       size_type __old_size = _Base::bucket_count();
00158       std::pair<iterator, bool> __res
00159         = _Base::emplace(std::forward<_Args>(__args)...);
00160       _M_profile_resize(__old_size);
00161       return __res;
00162     }
00163 
00164       template<typename... _Args>
00165     iterator
00166     emplace_hint(const_iterator __it, _Args&&... __args)
00167     {
00168       size_type __old_size = _Base::bucket_count();
00169       iterator __res
00170         = _Base::emplace_hint(__it, std::forward<_Args>(__args)...);
00171       _M_profile_resize(__old_size);
00172       return __res;
00173     }
00174 
00175       void
00176       insert(std::initializer_list<value_type> __l)
00177       { 
00178         size_type __old_size = _Base::bucket_count();
00179         _Base::insert(__l); 
00180         _M_profile_resize(__old_size); 
00181       }
00182 
00183       std::pair<iterator, bool>
00184       insert(const value_type& __obj)
00185       {
00186         size_type __old_size = _Base::bucket_count();
00187         std::pair<iterator, bool> __res = _Base::insert(__obj);
00188         _M_profile_resize(__old_size); 
00189         return __res;
00190       }
00191 
00192       iterator
00193       insert(const_iterator __iter, const value_type& __v)
00194       { 
00195         size_type __old_size = _Base::bucket_count(); 
00196         iterator __res = _Base::insert(__iter, __v);
00197         _M_profile_resize(__old_size); 
00198         return __res;
00199       }
00200 
00201       std::pair<iterator, bool>
00202       insert(value_type&& __obj)
00203       {
00204         size_type __old_size = _Base::bucket_count();
00205         std::pair<iterator, bool> __res = _Base::insert(std::move(__obj));
00206         _M_profile_resize(__old_size); 
00207         return __res;
00208       }
00209 
00210       iterator
00211       insert(const_iterator __iter, value_type&& __v)
00212       { 
00213         size_type __old_size = _Base::bucket_count();
00214         iterator __res = _Base::insert(__iter, std::move(__v));
00215         _M_profile_resize(__old_size); 
00216         return __res;
00217       }
00218 
00219       template<typename _InputIter>
00220         void
00221         insert(_InputIter __first, _InputIter __last)
00222         {
00223       size_type __old_size = _Base::bucket_count(); 
00224       _Base::insert(__first, __last);
00225       _M_profile_resize(__old_size); 
00226     }
00227 
00228       void
00229       rehash(size_type __n)
00230       {
00231         size_type __old_size = _Base::bucket_count();
00232         _Base::rehash(__n);
00233         _M_profile_resize(__old_size); 
00234       }
00235 
00236     private:
00237       void
00238       _M_profile_resize(size_type __old_size)
00239       {
00240     size_type __new_size = _Base::bucket_count();
00241     if (__old_size != __new_size)
00242       __profcxx_hashtable_resize(this, __old_size, __new_size);
00243       }
00244   };
00245 
00246   template<typename _Key, typename _Hash, typename _Pred, typename _Alloc>
00247     inline void
00248     swap(unordered_set<_Key, _Hash, _Pred, _Alloc>& __x,
00249      unordered_set<_Key, _Hash, _Pred, _Alloc>& __y)
00250     { __x.swap(__y); }
00251 
00252   template<typename _Key, typename _Hash, typename _Pred, typename _Alloc>
00253     inline bool
00254     operator==(const unordered_set<_Key, _Hash, _Pred, _Alloc>& __x,
00255            const unordered_set<_Key, _Hash, _Pred, _Alloc>& __y)
00256     { return static_cast<const _GLIBCXX_STD_BASE&>(__x) == __y; }
00257 
00258   template<typename _Key, typename _Hash, typename _Pred, typename _Alloc>
00259     inline bool
00260     operator!=(const unordered_set<_Key, _Hash, _Pred, _Alloc>& __x,
00261            const unordered_set<_Key, _Hash, _Pred, _Alloc>& __y)
00262     { return !(__x == __y); }
00263 
00264 #undef _GLIBCXX_BASE
00265 #undef _GLIBCXX_STD_BASE
00266 #define _GLIBCXX_STD_BASE _GLIBCXX_STD_C::_GLIBCXX_BASE
00267 #define _GLIBCXX_BASE unordered_multiset<_Value, _Hash, _Pred, _Alloc>
00268 
00269   /** @brief Unordered_multiset wrapper with performance instrumentation.  */
00270   template<typename _Value,
00271        typename _Hash = std::hash<_Value>,
00272        typename _Pred = std::equal_to<_Value>,
00273        typename _Alloc =  std::allocator<_Value> >
00274     class unordered_multiset
00275     : public _GLIBCXX_STD_BASE,
00276       public _Unordered_profile<unordered_multiset<_Value,
00277                            _Hash, _Pred, _Alloc>,
00278                 false>
00279     {
00280       typedef _GLIBCXX_STD_BASE _Base;
00281 
00282       _Base&
00283       _M_base() noexcept       { return *this; }
00284 
00285       const _Base&
00286       _M_base() const noexcept { return *this; }
00287 
00288     public:
00289       typedef typename _Base::size_type       size_type;
00290       typedef typename _Base::hasher          hasher;
00291       typedef typename _Base::key_equal       key_equal;
00292       typedef typename _Base::allocator_type  allocator_type;
00293       typedef typename _Base::key_type        key_type;
00294       typedef typename _Base::value_type      value_type;
00295       typedef typename _Base::difference_type difference_type;
00296       typedef typename _Base::reference       reference;
00297       typedef typename _Base::const_reference const_reference;
00298 
00299       typedef typename _Base::iterator iterator;
00300       typedef typename _Base::const_iterator const_iterator;
00301 
00302       explicit
00303       unordered_multiset(size_type __n = 10,
00304              const hasher& __hf = hasher(),
00305              const key_equal& __eql = key_equal(),
00306              const allocator_type& __a = allocator_type())
00307     : _Base(__n, __hf, __eql, __a)
00308       { }
00309 
00310       template<typename _InputIterator>
00311         unordered_multiset(_InputIterator __f, _InputIterator __l,
00312                size_type __n = 0,
00313                const hasher& __hf = hasher(),
00314                const key_equal& __eql = key_equal(),
00315                const allocator_type& __a = allocator_type())
00316       : _Base(__f, __l, __n, __hf, __eql, __a)
00317       { }
00318 
00319       unordered_multiset(const unordered_multiset&) = default;
00320 
00321       unordered_multiset(const _Base& __x)
00322     : _Base(__x)
00323       { }
00324 
00325       unordered_multiset(unordered_multiset&&) = default;
00326 
00327       explicit
00328       unordered_multiset(const allocator_type& __a)
00329     : _Base(__a)
00330       { }
00331 
00332       unordered_multiset(const unordered_multiset& __umset,
00333              const allocator_type& __a)
00334     : _Base(__umset._M_base(), __a)
00335       { }
00336 
00337       unordered_multiset(unordered_multiset&& __umset,
00338              const allocator_type& __a)
00339     : _Base(std::move(__umset._M_base()), __a)
00340       { }
00341 
00342       unordered_multiset(initializer_list<value_type> __l,
00343              size_type __n = 0,
00344              const hasher& __hf = hasher(),
00345              const key_equal& __eql = key_equal(),
00346              const allocator_type& __a = allocator_type())
00347     : _Base(__l, __n, __hf, __eql, __a)
00348       { }
00349 
00350       unordered_multiset&
00351       operator=(const unordered_multiset&) = default;
00352 
00353       unordered_multiset&
00354       operator=(unordered_multiset&&) = default;
00355 
00356       unordered_multiset&
00357       operator=(initializer_list<value_type> __l)
00358       {
00359     _M_base() = __l;
00360     return *this;
00361       }
00362 
00363       void
00364       swap(unordered_multiset& __x)
00365       noexcept( noexcept(__x._M_base().swap(__x)) )
00366       { _Base::swap(__x); }
00367 
00368       void
00369       clear() noexcept
00370       {
00371         __profcxx_hashtable_destruct(this, _Base::bucket_count(), 
00372                                      _Base::size());
00373         this->_M_profile_destruct();
00374         _Base::clear();
00375       }
00376 
00377       template<typename... _Args>
00378     iterator
00379     emplace(_Args&&... __args)
00380     {
00381       size_type __old_size = _Base::bucket_count();
00382       iterator __res = _Base::emplace(std::forward<_Args>(__args)...);
00383       _M_profile_resize(__old_size);
00384       return __res;
00385     }
00386 
00387       template<typename... _Args>
00388     iterator
00389     emplace_hint(const_iterator __it, _Args&&... __args)
00390     {
00391       size_type __old_size = _Base::bucket_count();
00392       iterator __res
00393         = _Base::emplace_hint(__it, std::forward<_Args>(__args)...);
00394       _M_profile_resize(__old_size);
00395       return __res;
00396     }
00397 
00398       void
00399       insert(std::initializer_list<value_type> __l)
00400       { 
00401         size_type __old_size = _Base::bucket_count();
00402         _Base::insert(__l); 
00403         _M_profile_resize(__old_size); 
00404       }
00405 
00406       iterator
00407       insert(const value_type& __obj)
00408       {
00409         size_type __old_size = _Base::bucket_count();
00410         iterator __res = _Base::insert(__obj);
00411         _M_profile_resize(__old_size); 
00412         return __res;
00413       }
00414 
00415       iterator
00416       insert(const_iterator __iter, const value_type& __v)
00417       {
00418         size_type __old_size = _Base::bucket_count(); 
00419         iterator __res = _Base::insert(__iter, __v);
00420         _M_profile_resize(__old_size); 
00421         return __res;
00422       }
00423 
00424       iterator
00425       insert(value_type&& __obj)
00426       {
00427     size_type __old_size = _Base::bucket_count();
00428         iterator __res = _Base::insert(std::move(__obj));
00429         _M_profile_resize(__old_size); 
00430         return __res;
00431       }
00432 
00433       iterator
00434       insert(const_iterator __iter, value_type&& __v)
00435       {
00436         size_type __old_size = _Base::bucket_count(); 
00437         iterator __res = _Base::insert(__iter, std::move(__v));
00438         _M_profile_resize(__old_size); 
00439         return __res;
00440       }
00441 
00442       template<typename _InputIter>
00443         void
00444         insert(_InputIter __first, _InputIter __last)
00445         {
00446       size_type __old_size = _Base::bucket_count(); 
00447       _Base::insert(__first, __last);
00448       _M_profile_resize(__old_size); 
00449     }
00450 
00451       void
00452       rehash(size_type __n)
00453       {
00454         size_type __old_size = _Base::bucket_count();
00455         _Base::rehash(__n);
00456         _M_profile_resize(__old_size); 
00457       }
00458 
00459     private:
00460       void
00461       _M_profile_resize(size_type __old_size)
00462       {
00463     size_type __new_size = _Base::bucket_count();
00464         if (__old_size != __new_size)
00465           __profcxx_hashtable_resize(this, __old_size, __new_size);
00466       }
00467    };
00468 
00469   template<typename _Value, typename _Hash, typename _Pred, typename _Alloc>
00470     inline void
00471     swap(unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x,
00472      unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y)
00473     { __x.swap(__y); }
00474 
00475   template<typename _Value, typename _Hash, typename _Pred, typename _Alloc>
00476     inline bool
00477     operator==(const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x,
00478            const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y)
00479     { return static_cast<const _GLIBCXX_STD_BASE&>(__x) == __y; }
00480 
00481   template<typename _Value, typename _Hash, typename _Pred, typename _Alloc>
00482     inline bool
00483     operator!=(const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x,
00484            const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y)
00485     { return !(__x == __y); }
00486 
00487 } // namespace __profile
00488 } // namespace std
00489 
00490 #undef _GLIBCXX_BASE
00491 #undef _GLIBCXX_STD_BASE
00492 
00493 #endif // C++11
00494 
00495 #endif