libstdc++
unordered_set
Go to the documentation of this file.
00001 // Profiling unordered_set/unordered_multiset implementation -*- C++ -*-
00002 
00003 // Copyright (C) 2009-2015 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       unordered_set() = default;
00079 
00080       explicit
00081       unordered_set(size_type __n,
00082                     const hasher& __hf = hasher(),
00083                     const key_equal& __eql = key_equal(),
00084                     const allocator_type& __a = allocator_type())
00085         : _Base(__n, __hf, __eql, __a)
00086       { }
00087 
00088       template<typename _InputIterator>
00089         unordered_set(_InputIterator __f, _InputIterator __l,
00090                       size_type __n = 0,
00091                       const hasher& __hf = hasher(),
00092                       const key_equal& __eql = key_equal(),
00093                       const allocator_type& __a = allocator_type())
00094           : _Base(__f, __l, __n, __hf, __eql, __a)
00095       { }
00096 
00097       unordered_set(const unordered_set&) = default;
00098 
00099       unordered_set(const _Base& __x)
00100         : _Base(__x)
00101       { }
00102 
00103       unordered_set(unordered_set&&) = default;
00104 
00105       explicit
00106       unordered_set(const allocator_type& __a)
00107         : _Base(__a)
00108       { }
00109 
00110       unordered_set(const unordered_set& __uset,
00111                     const allocator_type& __a)
00112         : _Base(__uset._M_base(), __a)
00113       { }
00114 
00115       unordered_set(unordered_set&& __uset,
00116                     const allocator_type& __a)
00117         : _Base(std::move(__uset._M_base()), __a)
00118       { }
00119 
00120       unordered_set(initializer_list<value_type> __l,
00121                     size_type __n = 0,
00122                     const hasher& __hf = hasher(),
00123                     const key_equal& __eql = key_equal(),
00124                     const allocator_type& __a = allocator_type())
00125       : _Base(__l, __n, __hf, __eql, __a)
00126       { }
00127 
00128       unordered_set(size_type __n, const allocator_type& __a)
00129         : unordered_set(__n, hasher(), key_equal(), __a)
00130       { }
00131 
00132       unordered_set(size_type __n, const hasher& __hf,
00133                     const allocator_type& __a)
00134         : unordered_set(__n, __hf, key_equal(), __a)
00135       { }
00136 
00137       template<typename _InputIterator>
00138         unordered_set(_InputIterator __first, _InputIterator __last,
00139                       size_type __n,
00140                       const allocator_type& __a)
00141           : unordered_set(__first, __last, __n, hasher(), key_equal(), __a)
00142         { }
00143 
00144       template<typename _InputIterator>
00145         unordered_set(_InputIterator __first, _InputIterator __last,
00146                       size_type __n, const hasher& __hf,
00147                       const allocator_type& __a)
00148           : unordered_set(__first, __last, __n, __hf, key_equal(), __a)
00149         { }
00150 
00151       unordered_set(initializer_list<value_type> __l,
00152                     size_type __n,
00153                     const allocator_type& __a)
00154         : unordered_set(__l, __n, hasher(), key_equal(), __a)
00155       { }
00156 
00157       unordered_set(initializer_list<value_type> __l,
00158                     size_type __n, const hasher& __hf,
00159                     const allocator_type& __a)
00160         : unordered_set(__l, __n, __hf, key_equal(), __a)
00161       { }
00162 
00163       unordered_set&
00164       operator=(const unordered_set&) = default;
00165 
00166       unordered_set&
00167       operator=(unordered_set&&) = default;
00168 
00169       unordered_set&
00170       operator=(initializer_list<value_type> __l)
00171       {
00172         this->_M_profile_destruct();
00173         _M_base() = __l;
00174         this->_M_profile_construct();
00175         return *this;
00176       }
00177 
00178       void
00179       swap(unordered_set& __x)
00180       noexcept( noexcept(__x._M_base().swap(__x)) )
00181       {
00182         _Base::swap(__x);
00183         this->_M_swap(__x);
00184       }
00185 
00186       void
00187       clear() noexcept
00188       {
00189         this->_M_profile_destruct();
00190         _Base::clear();
00191         this->_M_profile_construct();
00192       }
00193 
00194       template<typename... _Args>
00195         std::pair<iterator, bool>
00196         emplace(_Args&&... __args)
00197         {
00198           size_type __old_size = _Base::bucket_count();
00199           std::pair<iterator, bool> __res
00200             = _Base::emplace(std::forward<_Args>(__args)...);
00201           this->_M_profile_resize(__old_size);
00202           return __res;
00203         }
00204 
00205       template<typename... _Args>
00206         iterator
00207         emplace_hint(const_iterator __it, _Args&&... __args)
00208         {
00209           size_type __old_size = _Base::bucket_count();
00210           iterator __res
00211             = _Base::emplace_hint(__it, std::forward<_Args>(__args)...);
00212           this->_M_profile_resize(__old_size);
00213           return __res;
00214         }
00215 
00216       void
00217       insert(std::initializer_list<value_type> __l)
00218       {
00219         size_type __old_size = _Base::bucket_count();
00220         _Base::insert(__l);
00221         this->_M_profile_resize(__old_size);
00222       }
00223 
00224       std::pair<iterator, bool>
00225       insert(const value_type& __obj)
00226       {
00227         size_type __old_size = _Base::bucket_count();
00228         std::pair<iterator, bool> __res = _Base::insert(__obj);
00229         this->_M_profile_resize(__old_size);
00230         return __res;
00231       }
00232 
00233       iterator
00234       insert(const_iterator __iter, const value_type& __v)
00235       {
00236         size_type __old_size = _Base::bucket_count();
00237         iterator __res = _Base::insert(__iter, __v);
00238         this->_M_profile_resize(__old_size);
00239         return __res;
00240       }
00241 
00242       std::pair<iterator, bool>
00243       insert(value_type&& __obj)
00244       {
00245         size_type __old_size = _Base::bucket_count();
00246         std::pair<iterator, bool> __res = _Base::insert(std::move(__obj));
00247         this->_M_profile_resize(__old_size);
00248         return __res;
00249       }
00250 
00251       iterator
00252       insert(const_iterator __iter, value_type&& __v)
00253       {
00254         size_type __old_size = _Base::bucket_count();
00255         iterator __res = _Base::insert(__iter, std::move(__v));
00256         this->_M_profile_resize(__old_size);
00257         return __res;
00258       }
00259 
00260       template<typename _InputIter>
00261         void
00262         insert(_InputIter __first, _InputIter __last)
00263         {
00264           size_type __old_size = _Base::bucket_count();
00265           _Base::insert(__first, __last);
00266           this->_M_profile_resize(__old_size);
00267         }
00268 
00269       void
00270       rehash(size_type __n)
00271       {
00272         size_type __old_size = _Base::bucket_count();
00273         _Base::rehash(__n);
00274         this->_M_profile_resize(__old_size);
00275       }
00276   };
00277 
00278   template<typename _Key, typename _Hash, typename _Pred, typename _Alloc>
00279     inline void
00280     swap(unordered_set<_Key, _Hash, _Pred, _Alloc>& __x,
00281          unordered_set<_Key, _Hash, _Pred, _Alloc>& __y)
00282     { __x.swap(__y); }
00283 
00284   template<typename _Key, typename _Hash, typename _Pred, typename _Alloc>
00285     inline bool
00286     operator==(const unordered_set<_Key, _Hash, _Pred, _Alloc>& __x,
00287                const unordered_set<_Key, _Hash, _Pred, _Alloc>& __y)
00288     { return static_cast<const _GLIBCXX_STD_BASE&>(__x) == __y; }
00289 
00290   template<typename _Key, typename _Hash, typename _Pred, typename _Alloc>
00291     inline bool
00292     operator!=(const unordered_set<_Key, _Hash, _Pred, _Alloc>& __x,
00293                const unordered_set<_Key, _Hash, _Pred, _Alloc>& __y)
00294     { return !(__x == __y); }
00295 
00296 #undef _GLIBCXX_BASE
00297 #undef _GLIBCXX_STD_BASE
00298 #define _GLIBCXX_STD_BASE _GLIBCXX_STD_C::_GLIBCXX_BASE
00299 #define _GLIBCXX_BASE unordered_multiset<_Value, _Hash, _Pred, _Alloc>
00300 
00301   /** @brief Unordered_multiset wrapper with performance instrumentation.  */
00302   template<typename _Value,
00303            typename _Hash = std::hash<_Value>,
00304            typename _Pred = std::equal_to<_Value>,
00305            typename _Alloc =  std::allocator<_Value> >
00306     class unordered_multiset
00307     : public _GLIBCXX_STD_BASE,
00308       public _Unordered_profile<unordered_multiset<_Value,
00309                                                    _Hash, _Pred, _Alloc>,
00310                                 false>
00311     {
00312       typedef _GLIBCXX_STD_BASE _Base;
00313 
00314       _Base&
00315       _M_base() noexcept       { return *this; }
00316 
00317       const _Base&
00318       _M_base() const noexcept { return *this; }
00319 
00320     public:
00321       typedef typename _Base::size_type       size_type;
00322       typedef typename _Base::hasher      hasher;
00323       typedef typename _Base::key_equal       key_equal;
00324       typedef typename _Base::allocator_type  allocator_type;
00325       typedef typename _Base::key_type  key_type;
00326       typedef typename _Base::value_type      value_type;
00327       typedef typename _Base::difference_type difference_type;
00328       typedef typename _Base::reference       reference;
00329       typedef typename _Base::const_reference const_reference;
00330 
00331       typedef typename _Base::iterator iterator;
00332       typedef typename _Base::const_iterator const_iterator;
00333 
00334       unordered_multiset() = default;
00335 
00336       explicit
00337       unordered_multiset(size_type __n,
00338                          const hasher& __hf = hasher(),
00339                          const key_equal& __eql = key_equal(),
00340                          const allocator_type& __a = allocator_type())
00341         : _Base(__n, __hf, __eql, __a)
00342       { }
00343 
00344       template<typename _InputIterator>
00345         unordered_multiset(_InputIterator __f, _InputIterator __l,
00346                            size_type __n = 0,
00347                            const hasher& __hf = hasher(),
00348                            const key_equal& __eql = key_equal(),
00349                            const allocator_type& __a = allocator_type())
00350           : _Base(__f, __l, __n, __hf, __eql, __a)
00351       { }
00352 
00353       unordered_multiset(const unordered_multiset&) = default;
00354 
00355       unordered_multiset(const _Base& __x)
00356         : _Base(__x)
00357       { }
00358 
00359       unordered_multiset(unordered_multiset&&) = default;
00360 
00361       explicit
00362       unordered_multiset(const allocator_type& __a)
00363         : _Base(__a)
00364       { }
00365 
00366       unordered_multiset(const unordered_multiset& __umset,
00367                          const allocator_type& __a)
00368         : _Base(__umset._M_base(), __a)
00369       { }
00370 
00371       unordered_multiset(unordered_multiset&& __umset,
00372                          const allocator_type& __a)
00373         : _Base(std::move(__umset._M_base()), __a)
00374       { }
00375 
00376       unordered_multiset(initializer_list<value_type> __l,
00377                          size_type __n = 0,
00378                          const hasher& __hf = hasher(),
00379                          const key_equal& __eql = key_equal(),
00380                          const allocator_type& __a = allocator_type())
00381         : _Base(__l, __n, __hf, __eql, __a)
00382       { }
00383 
00384       unordered_multiset(size_type __n, const allocator_type& __a)
00385         : unordered_multiset(__n, hasher(), key_equal(), __a)
00386       { }
00387 
00388       unordered_multiset(size_type __n, const hasher& __hf,
00389                          const allocator_type& __a)
00390         : unordered_multiset(__n, __hf, key_equal(), __a)
00391       { }
00392 
00393       template<typename _InputIterator>
00394         unordered_multiset(_InputIterator __first, _InputIterator __last,
00395                            size_type __n,
00396                            const allocator_type& __a)
00397           : unordered_multiset(__first, __last, __n, hasher(), key_equal(), __a)
00398         { }
00399 
00400       template<typename _InputIterator>
00401         unordered_multiset(_InputIterator __first, _InputIterator __last,
00402                            size_type __n, const hasher& __hf,
00403                            const allocator_type& __a)
00404           : unordered_multiset(__first, __last, __n, __hf, key_equal(), __a)
00405         { }
00406 
00407       unordered_multiset(initializer_list<value_type> __l,
00408                          size_type __n,
00409                          const allocator_type& __a)
00410         : unordered_multiset(__l, __n, hasher(), key_equal(), __a)
00411       { }
00412 
00413       unordered_multiset(initializer_list<value_type> __l,
00414                          size_type __n, const hasher& __hf,
00415                          const allocator_type& __a)
00416         : unordered_multiset(__l, __n, __hf, key_equal(), __a)
00417       { }
00418 
00419       unordered_multiset&
00420       operator=(const unordered_multiset&) = default;
00421 
00422       unordered_multiset&
00423       operator=(unordered_multiset&&) = default;
00424 
00425       unordered_multiset&
00426       operator=(initializer_list<value_type> __l)
00427       {
00428         this->_M_profile_destruct();
00429         _M_base() = __l;
00430         this->_M_profile_construct();
00431         return *this;
00432       }
00433 
00434       void
00435       swap(unordered_multiset& __x)
00436       noexcept( noexcept(__x._M_base().swap(__x)) )
00437       {
00438         _Base::swap(__x);
00439         this->_M_swap(__x);
00440       }
00441 
00442       void
00443       clear() noexcept
00444       {
00445         this->_M_profile_destruct();
00446         _Base::clear();
00447         this->_M_profile_construct();
00448       }
00449 
00450       template<typename... _Args>
00451         iterator
00452         emplace(_Args&&... __args)
00453         {
00454           size_type __old_size = _Base::bucket_count();
00455           iterator __res = _Base::emplace(std::forward<_Args>(__args)...);
00456           this->_M_profile_resize(__old_size);
00457           return __res;
00458         }
00459 
00460       template<typename... _Args>
00461         iterator
00462         emplace_hint(const_iterator __it, _Args&&... __args)
00463         {
00464           size_type __old_size = _Base::bucket_count();
00465           iterator __res
00466             = _Base::emplace_hint(__it, std::forward<_Args>(__args)...);
00467           this->_M_profile_resize(__old_size);
00468           return __res;
00469         }
00470 
00471       void
00472       insert(std::initializer_list<value_type> __l)
00473       {
00474         size_type __old_size = _Base::bucket_count();
00475         _Base::insert(__l);
00476         this->_M_profile_resize(__old_size);
00477       }
00478 
00479       iterator
00480       insert(const value_type& __obj)
00481       {
00482         size_type __old_size = _Base::bucket_count();
00483         iterator __res = _Base::insert(__obj);
00484         this->_M_profile_resize(__old_size);
00485         return __res;
00486       }
00487 
00488       iterator
00489       insert(const_iterator __iter, const value_type& __v)
00490       {
00491         size_type __old_size = _Base::bucket_count();
00492         iterator __res = _Base::insert(__iter, __v);
00493         this->_M_profile_resize(__old_size);
00494         return __res;
00495       }
00496 
00497       iterator
00498       insert(value_type&& __obj)
00499       {
00500         size_type __old_size = _Base::bucket_count();
00501         iterator __res = _Base::insert(std::move(__obj));
00502         this->_M_profile_resize(__old_size);
00503         return __res;
00504       }
00505 
00506       iterator
00507       insert(const_iterator __iter, value_type&& __v)
00508       {
00509         size_type __old_size = _Base::bucket_count();
00510         iterator __res = _Base::insert(__iter, std::move(__v));
00511         this->_M_profile_resize(__old_size);
00512         return __res;
00513       }
00514 
00515       template<typename _InputIter>
00516         void
00517         insert(_InputIter __first, _InputIter __last)
00518         {
00519           size_type __old_size = _Base::bucket_count();
00520           _Base::insert(__first, __last);
00521           this->_M_profile_resize(__old_size);
00522         }
00523 
00524       void
00525       rehash(size_type __n)
00526       {
00527         size_type __old_size = _Base::bucket_count();
00528         _Base::rehash(__n);
00529         this->_M_profile_resize(__old_size);
00530       }
00531    };
00532 
00533   template<typename _Value, typename _Hash, typename _Pred, typename _Alloc>
00534     inline void
00535     swap(unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x,
00536          unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y)
00537     { __x.swap(__y); }
00538 
00539   template<typename _Value, typename _Hash, typename _Pred, typename _Alloc>
00540     inline bool
00541     operator==(const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x,
00542                const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y)
00543     { return static_cast<const _GLIBCXX_STD_BASE&>(__x) == __y; }
00544 
00545   template<typename _Value, typename _Hash, typename _Pred, typename _Alloc>
00546     inline bool
00547     operator!=(const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x,
00548                const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y)
00549     { return !(__x == __y); }
00550 
00551 } // namespace __profile
00552 } // namespace std
00553 
00554 #undef _GLIBCXX_BASE
00555 #undef _GLIBCXX_STD_BASE
00556 
00557 #endif // C++11
00558 
00559 #endif