libstdc++
unordered_set
Go to the documentation of this file.
00001 // Profiling unordered_set/unordered_multiset implementation -*- C++ -*-
00002 
00003 // Copyright (C) 2009-2013 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       unordered_set(initializer_list<value_type> __l,
00104             size_type __n = 0,
00105             const hasher& __hf = hasher(),
00106             const key_equal& __eql = key_equal(),
00107             const allocator_type& __a = allocator_type())
00108       : _Base(__l, __n, __hf, __eql, __a)
00109       { }
00110 
00111       unordered_set&
00112       operator=(const unordered_set&) = default;
00113 
00114       unordered_set&
00115       operator=(unordered_set&&) = default;
00116 
00117       unordered_set&
00118       operator=(initializer_list<value_type> __l)
00119       {
00120     _M_base() = __l;
00121     return *this;
00122       }
00123 
00124       void
00125       swap(unordered_set& __x)
00126       { _Base::swap(__x); }
00127 
00128       void
00129       clear() noexcept
00130       {
00131         __profcxx_hashtable_destruct(this, _Base::bucket_count(), 
00132                                      _Base::size());
00133         this->_M_profile_destruct();
00134         _Base::clear();
00135       }
00136 
00137       template<typename... _Args>
00138     std::pair<iterator, bool>
00139     emplace(_Args&&... __args)
00140     {
00141       size_type __old_size = _Base::bucket_count();
00142       std::pair<iterator, bool> __res
00143         = _Base::emplace(std::forward<_Args>(__args)...);
00144       _M_profile_resize(__old_size);
00145       return __res;
00146     }
00147 
00148       template<typename... _Args>
00149     iterator
00150     emplace_hint(const_iterator __it, _Args&&... __args)
00151     {
00152       size_type __old_size = _Base::bucket_count();
00153       iterator __res
00154         = _Base::emplace_hint(__it, std::forward<_Args>(__args)...);
00155       _M_profile_resize(__old_size);
00156       return __res;
00157     }
00158 
00159       void
00160       insert(std::initializer_list<value_type> __l)
00161       { 
00162         size_type __old_size = _Base::bucket_count();
00163         _Base::insert(__l); 
00164         _M_profile_resize(__old_size); 
00165       }
00166 
00167       std::pair<iterator, bool>
00168       insert(const value_type& __obj)
00169       {
00170         size_type __old_size = _Base::bucket_count();
00171         std::pair<iterator, bool> __res = _Base::insert(__obj);
00172         _M_profile_resize(__old_size); 
00173         return __res;
00174       }
00175 
00176       iterator
00177       insert(const_iterator __iter, const value_type& __v)
00178       { 
00179         size_type __old_size = _Base::bucket_count(); 
00180         iterator __res = _Base::insert(__iter, __v);
00181         _M_profile_resize(__old_size); 
00182         return __res;
00183       }
00184 
00185       std::pair<iterator, bool>
00186       insert(value_type&& __obj)
00187       {
00188         size_type __old_size = _Base::bucket_count();
00189         std::pair<iterator, bool> __res = _Base::insert(std::move(__obj));
00190         _M_profile_resize(__old_size); 
00191         return __res;
00192       }
00193 
00194       iterator
00195       insert(const_iterator __iter, value_type&& __v)
00196       { 
00197         size_type __old_size = _Base::bucket_count();
00198         iterator __res = _Base::insert(__iter, std::move(__v));
00199         _M_profile_resize(__old_size); 
00200         return __res;
00201       }
00202 
00203       template<typename _InputIter>
00204         void
00205         insert(_InputIter __first, _InputIter __last)
00206         {
00207       size_type __old_size = _Base::bucket_count(); 
00208       _Base::insert(__first, __last);
00209       _M_profile_resize(__old_size); 
00210     }
00211 
00212       void
00213       rehash(size_type __n)
00214       {
00215         size_type __old_size = _Base::bucket_count();
00216         _Base::rehash(__n);
00217         _M_profile_resize(__old_size); 
00218       }
00219 
00220     private:
00221       void
00222       _M_profile_resize(size_type __old_size)
00223       {
00224     size_type __new_size = _Base::bucket_count();
00225     if (__old_size != __new_size)
00226       __profcxx_hashtable_resize(this, __old_size, __new_size);
00227       }
00228   };
00229 
00230   template<typename _Key, typename _Hash, typename _Pred, typename _Alloc>
00231     inline void
00232     swap(unordered_set<_Key, _Hash, _Pred, _Alloc>& __x,
00233      unordered_set<_Key, _Hash, _Pred, _Alloc>& __y)
00234     { __x.swap(__y); }
00235 
00236   template<typename _Key, typename _Hash, typename _Pred, typename _Alloc>
00237     inline bool
00238     operator==(const unordered_set<_Key, _Hash, _Pred, _Alloc>& __x,
00239            const unordered_set<_Key, _Hash, _Pred, _Alloc>& __y)
00240     { return static_cast<const _GLIBCXX_STD_BASE&>(__x) == __y; }
00241 
00242   template<typename _Key, typename _Hash, typename _Pred, typename _Alloc>
00243     inline bool
00244     operator!=(const unordered_set<_Key, _Hash, _Pred, _Alloc>& __x,
00245            const unordered_set<_Key, _Hash, _Pred, _Alloc>& __y)
00246     { return !(__x == __y); }
00247 
00248 #undef _GLIBCXX_BASE
00249 #undef _GLIBCXX_STD_BASE
00250 #define _GLIBCXX_STD_BASE _GLIBCXX_STD_C::_GLIBCXX_BASE
00251 #define _GLIBCXX_BASE unordered_multiset<_Value, _Hash, _Pred, _Alloc>
00252 
00253   /** @brief Unordered_multiset wrapper with performance instrumentation.  */
00254   template<typename _Value,
00255        typename _Hash = std::hash<_Value>,
00256        typename _Pred = std::equal_to<_Value>,
00257        typename _Alloc =  std::allocator<_Value> >
00258     class unordered_multiset
00259     : public _GLIBCXX_STD_BASE,
00260       public _Unordered_profile<unordered_multiset<_Value,
00261                            _Hash, _Pred, _Alloc>,
00262                 false>
00263     {
00264       typedef _GLIBCXX_STD_BASE _Base;
00265 
00266       _Base&
00267       _M_base() noexcept       { return *this; }
00268 
00269       const _Base&
00270       _M_base() const noexcept { return *this; }
00271 
00272     public:
00273       typedef typename _Base::size_type       size_type;
00274       typedef typename _Base::hasher          hasher;
00275       typedef typename _Base::key_equal       key_equal;
00276       typedef typename _Base::allocator_type  allocator_type;
00277       typedef typename _Base::key_type        key_type;
00278       typedef typename _Base::value_type      value_type;
00279       typedef typename _Base::difference_type difference_type;
00280       typedef typename _Base::reference       reference;
00281       typedef typename _Base::const_reference const_reference;
00282 
00283       typedef typename _Base::iterator iterator;
00284       typedef typename _Base::const_iterator const_iterator;
00285 
00286       explicit
00287       unordered_multiset(size_type __n = 10,
00288              const hasher& __hf = hasher(),
00289              const key_equal& __eql = key_equal(),
00290              const allocator_type& __a = allocator_type())
00291     : _Base(__n, __hf, __eql, __a)
00292       { }
00293 
00294       template<typename _InputIterator>
00295         unordered_multiset(_InputIterator __f, _InputIterator __l,
00296                size_type __n = 0,
00297                const hasher& __hf = hasher(),
00298                const key_equal& __eql = key_equal(),
00299                const allocator_type& __a = allocator_type())
00300       : _Base(__f, __l, __n, __hf, __eql, __a)
00301       { }
00302 
00303       unordered_multiset(const unordered_multiset&) = default;
00304 
00305       unordered_multiset(const _Base& __x)
00306     : _Base(__x)
00307       { }
00308 
00309       unordered_multiset(unordered_multiset&&) = default;
00310 
00311       unordered_multiset(initializer_list<value_type> __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(__l, __n, __hf, __eql, __a)
00317       { }
00318 
00319       unordered_multiset&
00320       operator=(const unordered_multiset&) = default;
00321 
00322       unordered_multiset&
00323       operator=(unordered_multiset&&) = default;
00324 
00325       unordered_multiset&
00326       operator=(initializer_list<value_type> __l)
00327       {
00328     _M_base() = __l;
00329     return *this;
00330       }
00331 
00332       void
00333       swap(unordered_multiset& __x)
00334       { _Base::swap(__x); }
00335 
00336       void
00337       clear() noexcept
00338       {
00339         __profcxx_hashtable_destruct(this, _Base::bucket_count(), 
00340                                      _Base::size());
00341         this->_M_profile_destruct();
00342         _Base::clear();
00343       }
00344 
00345       template<typename... _Args>
00346     iterator
00347     emplace(_Args&&... __args)
00348     {
00349       size_type __old_size = _Base::bucket_count();
00350       iterator __res = _Base::emplace(std::forward<_Args>(__args)...);
00351       _M_profile_resize(__old_size);
00352       return __res;
00353     }
00354 
00355       template<typename... _Args>
00356     iterator
00357     emplace_hint(const_iterator __it, _Args&&... __args)
00358     {
00359       size_type __old_size = _Base::bucket_count();
00360       iterator __res
00361         = _Base::emplace_hint(__it, std::forward<_Args>(__args)...);
00362       _M_profile_resize(__old_size);
00363       return __res;
00364     }
00365 
00366       void
00367       insert(std::initializer_list<value_type> __l)
00368       { 
00369         size_type __old_size = _Base::bucket_count();
00370         _Base::insert(__l); 
00371         _M_profile_resize(__old_size); 
00372       }
00373 
00374       iterator
00375       insert(const value_type& __obj)
00376       {
00377         size_type __old_size = _Base::bucket_count();
00378         iterator __res = _Base::insert(__obj);
00379         _M_profile_resize(__old_size); 
00380         return __res;
00381       }
00382 
00383       iterator
00384       insert(const_iterator __iter, const value_type& __v)
00385       {
00386         size_type __old_size = _Base::bucket_count(); 
00387         iterator __res = _Base::insert(__iter, __v);
00388         _M_profile_resize(__old_size); 
00389         return __res;
00390       }
00391 
00392       iterator
00393       insert(value_type&& __obj)
00394       {
00395     size_type __old_size = _Base::bucket_count();
00396         iterator __res = _Base::insert(std::move(__obj));
00397         _M_profile_resize(__old_size); 
00398         return __res;
00399       }
00400 
00401       iterator
00402       insert(const_iterator __iter, value_type&& __v)
00403       {
00404         size_type __old_size = _Base::bucket_count(); 
00405         iterator __res = _Base::insert(__iter, std::move(__v));
00406         _M_profile_resize(__old_size); 
00407         return __res;
00408       }
00409 
00410       template<typename _InputIter>
00411         void
00412         insert(_InputIter __first, _InputIter __last)
00413         {
00414       size_type __old_size = _Base::bucket_count(); 
00415       _Base::insert(__first, __last);
00416       _M_profile_resize(__old_size); 
00417     }
00418 
00419       void
00420       rehash(size_type __n)
00421       {
00422         size_type __old_size = _Base::bucket_count();
00423         _Base::rehash(__n);
00424         _M_profile_resize(__old_size); 
00425       }
00426 
00427     private:
00428       void
00429       _M_profile_resize(size_type __old_size)
00430       {
00431     size_type __new_size = _Base::bucket_count();
00432         if (__old_size != __new_size)
00433           __profcxx_hashtable_resize(this, __old_size, __new_size);
00434       }
00435    };
00436 
00437   template<typename _Value, typename _Hash, typename _Pred, typename _Alloc>
00438     inline void
00439     swap(unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x,
00440      unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y)
00441     { __x.swap(__y); }
00442 
00443   template<typename _Value, typename _Hash, typename _Pred, typename _Alloc>
00444     inline bool
00445     operator==(const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x,
00446            const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y)
00447     { return static_cast<const _GLIBCXX_STD_BASE&>(__x) == __y; }
00448 
00449   template<typename _Value, typename _Hash, typename _Pred, typename _Alloc>
00450     inline bool
00451     operator!=(const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x,
00452            const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y)
00453     { return !(__x == __y); }
00454 
00455 } // namespace __profile
00456 } // namespace std
00457 
00458 #undef _GLIBCXX_BASE
00459 #undef _GLIBCXX_STD_BASE
00460 
00461 #endif // C++11
00462 
00463 #endif