libstdc++
unordered_set
Go to the documentation of this file.
00001 // Profiling unordered_set/unordered_multiset implementation -*- C++ -*-
00002 
00003 // Copyright (C) 2009-2018 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     noexcept(noexcept(__x.swap(__y)))
00283     { __x.swap(__y); }
00284 
00285   template<typename _Key, typename _Hash, typename _Pred, typename _Alloc>
00286     inline bool
00287     operator==(const unordered_set<_Key, _Hash, _Pred, _Alloc>& __x,
00288                const unordered_set<_Key, _Hash, _Pred, _Alloc>& __y)
00289     { return static_cast<const _GLIBCXX_STD_BASE&>(__x) == __y; }
00290 
00291   template<typename _Key, typename _Hash, typename _Pred, typename _Alloc>
00292     inline bool
00293     operator!=(const unordered_set<_Key, _Hash, _Pred, _Alloc>& __x,
00294                const unordered_set<_Key, _Hash, _Pred, _Alloc>& __y)
00295     { return !(__x == __y); }
00296 
00297 #undef _GLIBCXX_BASE
00298 #undef _GLIBCXX_STD_BASE
00299 #define _GLIBCXX_STD_BASE _GLIBCXX_STD_C::_GLIBCXX_BASE
00300 #define _GLIBCXX_BASE unordered_multiset<_Value, _Hash, _Pred, _Alloc>
00301 
00302   /** @brief Unordered_multiset wrapper with performance instrumentation.  */
00303   template<typename _Value,
00304            typename _Hash = std::hash<_Value>,
00305            typename _Pred = std::equal_to<_Value>,
00306            typename _Alloc =  std::allocator<_Value> >
00307     class unordered_multiset
00308     : public _GLIBCXX_STD_BASE,
00309       public _Unordered_profile<unordered_multiset<_Value,
00310                                                    _Hash, _Pred, _Alloc>,
00311                                 false>
00312     {
00313       typedef _GLIBCXX_STD_BASE _Base;
00314 
00315       _Base&
00316       _M_base() noexcept       { return *this; }
00317 
00318       const _Base&
00319       _M_base() const noexcept { return *this; }
00320 
00321     public:
00322       typedef typename _Base::size_type       size_type;
00323       typedef typename _Base::hasher      hasher;
00324       typedef typename _Base::key_equal       key_equal;
00325       typedef typename _Base::allocator_type  allocator_type;
00326       typedef typename _Base::key_type  key_type;
00327       typedef typename _Base::value_type      value_type;
00328       typedef typename _Base::difference_type difference_type;
00329       typedef typename _Base::reference       reference;
00330       typedef typename _Base::const_reference const_reference;
00331 
00332       typedef typename _Base::iterator iterator;
00333       typedef typename _Base::const_iterator const_iterator;
00334 
00335       unordered_multiset() = default;
00336 
00337       explicit
00338       unordered_multiset(size_type __n,
00339                          const hasher& __hf = hasher(),
00340                          const key_equal& __eql = key_equal(),
00341                          const allocator_type& __a = allocator_type())
00342         : _Base(__n, __hf, __eql, __a)
00343       { }
00344 
00345       template<typename _InputIterator>
00346         unordered_multiset(_InputIterator __f, _InputIterator __l,
00347                            size_type __n = 0,
00348                            const hasher& __hf = hasher(),
00349                            const key_equal& __eql = key_equal(),
00350                            const allocator_type& __a = allocator_type())
00351           : _Base(__f, __l, __n, __hf, __eql, __a)
00352       { }
00353 
00354       unordered_multiset(const unordered_multiset&) = default;
00355 
00356       unordered_multiset(const _Base& __x)
00357         : _Base(__x)
00358       { }
00359 
00360       unordered_multiset(unordered_multiset&&) = default;
00361 
00362       explicit
00363       unordered_multiset(const allocator_type& __a)
00364         : _Base(__a)
00365       { }
00366 
00367       unordered_multiset(const unordered_multiset& __umset,
00368                          const allocator_type& __a)
00369         : _Base(__umset._M_base(), __a)
00370       { }
00371 
00372       unordered_multiset(unordered_multiset&& __umset,
00373                          const allocator_type& __a)
00374         : _Base(std::move(__umset._M_base()), __a)
00375       { }
00376 
00377       unordered_multiset(initializer_list<value_type> __l,
00378                          size_type __n = 0,
00379                          const hasher& __hf = hasher(),
00380                          const key_equal& __eql = key_equal(),
00381                          const allocator_type& __a = allocator_type())
00382         : _Base(__l, __n, __hf, __eql, __a)
00383       { }
00384 
00385       unordered_multiset(size_type __n, const allocator_type& __a)
00386         : unordered_multiset(__n, hasher(), key_equal(), __a)
00387       { }
00388 
00389       unordered_multiset(size_type __n, const hasher& __hf,
00390                          const allocator_type& __a)
00391         : unordered_multiset(__n, __hf, key_equal(), __a)
00392       { }
00393 
00394       template<typename _InputIterator>
00395         unordered_multiset(_InputIterator __first, _InputIterator __last,
00396                            size_type __n,
00397                            const allocator_type& __a)
00398           : unordered_multiset(__first, __last, __n, hasher(), key_equal(), __a)
00399         { }
00400 
00401       template<typename _InputIterator>
00402         unordered_multiset(_InputIterator __first, _InputIterator __last,
00403                            size_type __n, const hasher& __hf,
00404                            const allocator_type& __a)
00405           : unordered_multiset(__first, __last, __n, __hf, key_equal(), __a)
00406         { }
00407 
00408       unordered_multiset(initializer_list<value_type> __l,
00409                          size_type __n,
00410                          const allocator_type& __a)
00411         : unordered_multiset(__l, __n, hasher(), key_equal(), __a)
00412       { }
00413 
00414       unordered_multiset(initializer_list<value_type> __l,
00415                          size_type __n, const hasher& __hf,
00416                          const allocator_type& __a)
00417         : unordered_multiset(__l, __n, __hf, key_equal(), __a)
00418       { }
00419 
00420       unordered_multiset&
00421       operator=(const unordered_multiset&) = default;
00422 
00423       unordered_multiset&
00424       operator=(unordered_multiset&&) = default;
00425 
00426       unordered_multiset&
00427       operator=(initializer_list<value_type> __l)
00428       {
00429         this->_M_profile_destruct();
00430         _M_base() = __l;
00431         this->_M_profile_construct();
00432         return *this;
00433       }
00434 
00435       void
00436       swap(unordered_multiset& __x)
00437       noexcept( noexcept(__x._M_base().swap(__x)) )
00438       {
00439         _Base::swap(__x);
00440         this->_M_swap(__x);
00441       }
00442 
00443       void
00444       clear() noexcept
00445       {
00446         this->_M_profile_destruct();
00447         _Base::clear();
00448         this->_M_profile_construct();
00449       }
00450 
00451       template<typename... _Args>
00452         iterator
00453         emplace(_Args&&... __args)
00454         {
00455           size_type __old_size = _Base::bucket_count();
00456           iterator __res = _Base::emplace(std::forward<_Args>(__args)...);
00457           this->_M_profile_resize(__old_size);
00458           return __res;
00459         }
00460 
00461       template<typename... _Args>
00462         iterator
00463         emplace_hint(const_iterator __it, _Args&&... __args)
00464         {
00465           size_type __old_size = _Base::bucket_count();
00466           iterator __res
00467             = _Base::emplace_hint(__it, std::forward<_Args>(__args)...);
00468           this->_M_profile_resize(__old_size);
00469           return __res;
00470         }
00471 
00472       void
00473       insert(std::initializer_list<value_type> __l)
00474       {
00475         size_type __old_size = _Base::bucket_count();
00476         _Base::insert(__l);
00477         this->_M_profile_resize(__old_size);
00478       }
00479 
00480       iterator
00481       insert(const value_type& __obj)
00482       {
00483         size_type __old_size = _Base::bucket_count();
00484         iterator __res = _Base::insert(__obj);
00485         this->_M_profile_resize(__old_size);
00486         return __res;
00487       }
00488 
00489       iterator
00490       insert(const_iterator __iter, const value_type& __v)
00491       {
00492         size_type __old_size = _Base::bucket_count();
00493         iterator __res = _Base::insert(__iter, __v);
00494         this->_M_profile_resize(__old_size);
00495         return __res;
00496       }
00497 
00498       iterator
00499       insert(value_type&& __obj)
00500       {
00501         size_type __old_size = _Base::bucket_count();
00502         iterator __res = _Base::insert(std::move(__obj));
00503         this->_M_profile_resize(__old_size);
00504         return __res;
00505       }
00506 
00507       iterator
00508       insert(const_iterator __iter, value_type&& __v)
00509       {
00510         size_type __old_size = _Base::bucket_count();
00511         iterator __res = _Base::insert(__iter, std::move(__v));
00512         this->_M_profile_resize(__old_size);
00513         return __res;
00514       }
00515 
00516       template<typename _InputIter>
00517         void
00518         insert(_InputIter __first, _InputIter __last)
00519         {
00520           size_type __old_size = _Base::bucket_count();
00521           _Base::insert(__first, __last);
00522           this->_M_profile_resize(__old_size);
00523         }
00524 
00525       void
00526       rehash(size_type __n)
00527       {
00528         size_type __old_size = _Base::bucket_count();
00529         _Base::rehash(__n);
00530         this->_M_profile_resize(__old_size);
00531       }
00532    };
00533 
00534   template<typename _Value, typename _Hash, typename _Pred, typename _Alloc>
00535     inline void
00536     swap(unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x,
00537          unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y)
00538     noexcept(noexcept(__x.swap(__y)))
00539     { __x.swap(__y); }
00540 
00541   template<typename _Value, typename _Hash, typename _Pred, typename _Alloc>
00542     inline bool
00543     operator==(const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x,
00544                const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y)
00545     { return static_cast<const _GLIBCXX_STD_BASE&>(__x) == __y; }
00546 
00547   template<typename _Value, typename _Hash, typename _Pred, typename _Alloc>
00548     inline bool
00549     operator!=(const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x,
00550                const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y)
00551     { return !(__x == __y); }
00552 
00553 } // namespace __profile
00554 } // namespace std
00555 
00556 #undef _GLIBCXX_BASE
00557 #undef _GLIBCXX_STD_BASE
00558 
00559 #endif // C++11
00560 
00561 #endif