unordered_set.h

Go to the documentation of this file.
00001 // unordered_set implementation -*- C++ -*-
00002 
00003 // Copyright (C) 2010 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 and
00021 // a copy of the GCC Runtime Library Exception along with this program;
00022 // see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see
00023 // <http://www.gnu.org/licenses/>.
00024 
00025 /** @file bits/unordered_set.h
00026  *  This is an internal header file, included by other library headers.
00027  *  You should not attempt to use it directly.
00028  */
00029 
00030 #ifndef _UNORDERED_SET_H
00031 #define _UNORDERED_SET_H
00032 
00033 _GLIBCXX_BEGIN_NESTED_NAMESPACE(std, _GLIBCXX_STD_D)
00034 
00035   // XXX When we get typedef templates these class definitions
00036   // will be unnecessary.
00037   template<class _Value,
00038        class _Hash = hash<_Value>,
00039        class _Pred = std::equal_to<_Value>,
00040        class _Alloc = std::allocator<_Value>,
00041        bool __cache_hash_code = false>
00042     class __unordered_set
00043     : public _Hashtable<_Value, _Value, _Alloc,
00044             std::_Identity<_Value>, _Pred,
00045             _Hash, __detail::_Mod_range_hashing,
00046             __detail::_Default_ranged_hash,
00047             __detail::_Prime_rehash_policy,
00048             __cache_hash_code, true, true>
00049     {
00050       typedef _Hashtable<_Value, _Value, _Alloc,
00051              std::_Identity<_Value>, _Pred,
00052              _Hash, __detail::_Mod_range_hashing,
00053              __detail::_Default_ranged_hash,
00054              __detail::_Prime_rehash_policy,
00055              __cache_hash_code, true, true>
00056         _Base;
00057 
00058     public:
00059       typedef typename _Base::size_type       size_type;
00060       typedef typename _Base::hasher          hasher;
00061       typedef typename _Base::key_equal       key_equal;
00062       typedef typename _Base::allocator_type  allocator_type;
00063       
00064       explicit
00065       __unordered_set(size_type __n = 10,
00066               const hasher& __hf = hasher(),
00067               const key_equal& __eql = key_equal(),
00068               const allocator_type& __a = allocator_type())
00069       : _Base(__n, __hf, __detail::_Mod_range_hashing(),
00070           __detail::_Default_ranged_hash(), __eql,
00071           std::_Identity<_Value>(), __a)
00072       { }
00073 
00074       template<typename _InputIterator>
00075         __unordered_set(_InputIterator __f, _InputIterator __l, 
00076             size_type __n = 10,
00077             const hasher& __hf = hasher(), 
00078             const key_equal& __eql = key_equal(), 
00079             const allocator_type& __a = allocator_type())
00080     : _Base(__f, __l, __n, __hf, __detail::_Mod_range_hashing(),
00081         __detail::_Default_ranged_hash(), __eql,
00082         std::_Identity<_Value>(), __a)
00083         { }
00084 
00085       __unordered_set(__unordered_set&& __x)
00086       : _Base(std::forward<_Base>(__x)) { }
00087     };
00088 
00089   template<class _Value,
00090        class _Hash = hash<_Value>,
00091        class _Pred = std::equal_to<_Value>,
00092        class _Alloc = std::allocator<_Value>,
00093        bool __cache_hash_code = false>
00094     class __unordered_multiset
00095     : public _Hashtable<_Value, _Value, _Alloc,
00096             std::_Identity<_Value>, _Pred,
00097             _Hash, __detail::_Mod_range_hashing,
00098             __detail::_Default_ranged_hash,
00099             __detail::_Prime_rehash_policy,
00100             __cache_hash_code, true, false>
00101     {
00102       typedef _Hashtable<_Value, _Value, _Alloc,
00103              std::_Identity<_Value>, _Pred,
00104              _Hash, __detail::_Mod_range_hashing,
00105              __detail::_Default_ranged_hash,
00106              __detail::_Prime_rehash_policy,
00107              __cache_hash_code, true, false>
00108         _Base;
00109 
00110     public:
00111       typedef typename _Base::size_type       size_type;
00112       typedef typename _Base::hasher          hasher;
00113       typedef typename _Base::key_equal       key_equal;
00114       typedef typename _Base::allocator_type  allocator_type;
00115       
00116       explicit
00117       __unordered_multiset(size_type __n = 10,
00118                const hasher& __hf = hasher(),
00119                const key_equal& __eql = key_equal(),
00120                const allocator_type& __a = allocator_type())
00121       : _Base(__n, __hf, __detail::_Mod_range_hashing(),
00122           __detail::_Default_ranged_hash(), __eql,
00123           std::_Identity<_Value>(), __a)
00124       { }
00125 
00126 
00127       template<typename _InputIterator>
00128         __unordered_multiset(_InputIterator __f, _InputIterator __l, 
00129                  typename _Base::size_type __n = 0,
00130                  const hasher& __hf = hasher(), 
00131                  const key_equal& __eql = key_equal(), 
00132                  const allocator_type& __a = allocator_type())
00133     : _Base(__f, __l, __n, __hf, __detail::_Mod_range_hashing(),
00134         __detail::_Default_ranged_hash(), __eql,
00135         std::_Identity<_Value>(), __a)
00136         { }
00137 
00138       __unordered_multiset(__unordered_multiset&& __x)
00139       : _Base(std::forward<_Base>(__x)) { }
00140     };
00141 
00142   template<class _Value, class _Hash, class _Pred, class _Alloc,
00143        bool __cache_hash_code>
00144     inline void
00145     swap(__unordered_set<_Value, _Hash, _Pred, _Alloc, __cache_hash_code>& __x,
00146      __unordered_set<_Value, _Hash, _Pred, _Alloc, __cache_hash_code>& __y)
00147     { __x.swap(__y); }
00148 
00149   template<class _Value, class _Hash, class _Pred, class _Alloc,
00150        bool __cache_hash_code>
00151     inline void
00152     swap(__unordered_multiset<_Value, _Hash, _Pred,
00153      _Alloc, __cache_hash_code>& __x,
00154      __unordered_multiset<_Value, _Hash, _Pred,
00155      _Alloc, __cache_hash_code>& __y)
00156     { __x.swap(__y); }
00157 
00158   template<class _Value, class _Hash, class _Pred, class _Alloc,
00159        bool __cache_hash_code>
00160     inline bool
00161     operator==(const __unordered_set<_Value, _Hash, _Pred, _Alloc,
00162            __cache_hash_code>& __x,
00163            const __unordered_set<_Value, _Hash, _Pred, _Alloc,
00164            __cache_hash_code>& __y)
00165     { return __x._M_equal(__y); }
00166 
00167   template<class _Value, class _Hash, class _Pred, class _Alloc,
00168        bool __cache_hash_code>
00169     inline bool
00170     operator!=(const __unordered_set<_Value, _Hash, _Pred, _Alloc,
00171            __cache_hash_code>& __x,
00172            const __unordered_set<_Value, _Hash, _Pred, _Alloc,
00173            __cache_hash_code>& __y)
00174     { return !(__x == __y); }
00175 
00176   template<class _Value, class _Hash, class _Pred, class _Alloc,
00177        bool __cache_hash_code>
00178     inline bool
00179     operator==(const __unordered_multiset<_Value, _Hash, _Pred, _Alloc,
00180            __cache_hash_code>& __x,
00181            const __unordered_multiset<_Value, _Hash, _Pred, _Alloc,
00182            __cache_hash_code>& __y)
00183     { return __x._M_equal(__y); }
00184 
00185   template<class _Value, class _Hash, class _Pred, class _Alloc,
00186        bool __cache_hash_code>
00187     inline bool
00188     operator!=(const __unordered_multiset<_Value, _Hash, _Pred, _Alloc,
00189            __cache_hash_code>& __x,
00190            const __unordered_multiset<_Value, _Hash, _Pred, _Alloc,
00191            __cache_hash_code>& __y)
00192     { return !(__x == __y); }
00193 
00194   /**
00195    *  @brief A standard container composed of unique keys (containing
00196    *  at most one of each key value) in which the elements' keys are
00197    *  the elements themselves.
00198    *
00199    *  @ingroup unordered_associative_containers
00200    *
00201    *  Meets the requirements of a <a href="tables.html#65">container</a>, and
00202    *  <a href="tables.html#xx">unordered associative container</a>
00203    *
00204    *  @param  Value  Type of key objects.
00205    *  @param  Hash  Hashing function object type, defaults to hash<Value>.
00206    *  @param  Pred  Predicate function object type, defaults to equal_to<Value>.
00207    *  @param  Alloc  Allocator type, defaults to allocator<Key>.
00208    */
00209   template<class _Value,
00210        class _Hash = hash<_Value>,
00211        class _Pred = std::equal_to<_Value>,
00212        class _Alloc = std::allocator<_Value> >
00213     class unordered_set
00214     : public __unordered_set<_Value, _Hash, _Pred, _Alloc>
00215     {
00216       typedef __unordered_set<_Value, _Hash, _Pred, _Alloc>  _Base;
00217 
00218     public:
00219       typedef typename _Base::value_type      value_type;
00220       typedef typename _Base::size_type       size_type;
00221       typedef typename _Base::hasher          hasher;
00222       typedef typename _Base::key_equal       key_equal;
00223       typedef typename _Base::allocator_type  allocator_type;
00224       
00225       explicit
00226       unordered_set(size_type __n = 10,
00227             const hasher& __hf = hasher(),
00228             const key_equal& __eql = key_equal(),
00229             const allocator_type& __a = allocator_type())
00230       : _Base(__n, __hf, __eql, __a)
00231       { }
00232 
00233       template<typename _InputIterator>
00234         unordered_set(_InputIterator __f, _InputIterator __l, 
00235               size_type __n = 10,
00236               const hasher& __hf = hasher(), 
00237               const key_equal& __eql = key_equal(), 
00238               const allocator_type& __a = allocator_type())
00239     : _Base(__f, __l, __n, __hf, __eql, __a)
00240         { }
00241 
00242       unordered_set(unordered_set&& __x)
00243       : _Base(std::forward<_Base>(__x)) { }
00244 
00245       unordered_set(initializer_list<value_type> __l,
00246             size_type __n = 10,
00247             const hasher& __hf = hasher(),
00248             const key_equal& __eql = key_equal(),
00249             const allocator_type& __a = allocator_type())
00250     : _Base(__l.begin(), __l.end(), __n, __hf, __eql, __a)
00251       { }
00252 
00253       unordered_set&
00254       operator=(unordered_set&& __x)
00255       {
00256     // NB: DR 1204.
00257     // NB: DR 675.
00258     this->clear();
00259     this->swap(__x);
00260     return *this;   
00261       }
00262 
00263       unordered_set&
00264       operator=(initializer_list<value_type> __l)
00265       {
00266     this->clear();
00267     this->insert(__l.begin(), __l.end());
00268     return *this;
00269       }
00270     };
00271 
00272   /**
00273    *  @brief A standard container composed of equivalent keys
00274    *  (possibly containing multiple of each key value) in which the
00275    *  elements' keys are the elements themselves.
00276    *
00277    *  @ingroup unordered_associative_containers
00278    *
00279    *  Meets the requirements of a <a href="tables.html#65">container</a>, and
00280    *  <a href="tables.html#xx">unordered associative container</a>
00281    *
00282    *  @param  Value  Type of key objects.
00283    *  @param  Hash  Hashing function object type, defaults to hash<Value>.
00284    *  @param  Pred  Predicate function object type, defaults to equal_to<Value>.
00285    *  @param  Alloc  Allocator type, defaults to allocator<Key>.
00286    */
00287   template<class _Value,
00288        class _Hash = hash<_Value>,
00289        class _Pred = std::equal_to<_Value>,
00290        class _Alloc = std::allocator<_Value> >
00291     class unordered_multiset
00292     : public __unordered_multiset<_Value, _Hash, _Pred, _Alloc>
00293     {
00294       typedef __unordered_multiset<_Value, _Hash, _Pred, _Alloc>  _Base;
00295 
00296     public:
00297       typedef typename _Base::value_type      value_type;
00298       typedef typename _Base::size_type       size_type;
00299       typedef typename _Base::hasher          hasher;
00300       typedef typename _Base::key_equal       key_equal;
00301       typedef typename _Base::allocator_type  allocator_type;
00302       
00303       explicit
00304       unordered_multiset(size_type __n = 10,
00305              const hasher& __hf = hasher(),
00306              const key_equal& __eql = key_equal(),
00307              const allocator_type& __a = allocator_type())
00308       : _Base(__n, __hf, __eql, __a)
00309       { }
00310 
00311 
00312       template<typename _InputIterator>
00313         unordered_multiset(_InputIterator __f, _InputIterator __l, 
00314                typename _Base::size_type __n = 0,
00315                const hasher& __hf = hasher(), 
00316                const key_equal& __eql = key_equal(), 
00317                const allocator_type& __a = allocator_type())
00318     : _Base(__f, __l, __n, __hf, __eql, __a)
00319         { }
00320 
00321       unordered_multiset(unordered_multiset&& __x)
00322       : _Base(std::forward<_Base>(__x)) { }
00323 
00324       unordered_multiset(initializer_list<value_type> __l,
00325              size_type __n = 10,
00326              const hasher& __hf = hasher(),
00327              const key_equal& __eql = key_equal(),
00328              const allocator_type& __a = allocator_type())
00329     : _Base(__l.begin(), __l.end(), __n, __hf, __eql, __a)
00330       { }
00331 
00332       unordered_multiset&
00333       operator=(unordered_multiset&& __x)
00334       {
00335     // NB: DR 1204.
00336     // NB: DR 675.
00337     this->clear();
00338     this->swap(__x);
00339     return *this;   
00340       }
00341 
00342       unordered_multiset&
00343       operator=(initializer_list<value_type> __l)
00344       {
00345     this->clear();
00346     this->insert(__l.begin(), __l.end());
00347     return *this;
00348       }
00349     };
00350 
00351   template<class _Value, class _Hash, class _Pred, class _Alloc>
00352     inline void
00353     swap(unordered_set<_Value, _Hash, _Pred, _Alloc>& __x,
00354      unordered_set<_Value, _Hash, _Pred, _Alloc>& __y)
00355     { __x.swap(__y); }
00356 
00357   template<class _Value, class _Hash, class _Pred, class _Alloc>
00358     inline void
00359     swap(unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x,
00360      unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y)
00361     { __x.swap(__y); }
00362 
00363   template<class _Value, class _Hash, class _Pred, class _Alloc>
00364     inline bool
00365     operator==(const unordered_set<_Value, _Hash, _Pred, _Alloc>& __x,
00366            const unordered_set<_Value, _Hash, _Pred, _Alloc>& __y)
00367     { return __x._M_equal(__y); }
00368 
00369   template<class _Value, class _Hash, class _Pred, class _Alloc>
00370     inline bool
00371     operator!=(const unordered_set<_Value, _Hash, _Pred, _Alloc>& __x,
00372            const unordered_set<_Value, _Hash, _Pred, _Alloc>& __y)
00373     { return !(__x == __y); }
00374 
00375   template<class _Value, class _Hash, class _Pred, class _Alloc>
00376     inline bool
00377     operator==(const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x,
00378            const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y)
00379     { return __x._M_equal(__y); }
00380 
00381   template<class _Value, class _Hash, class _Pred, class _Alloc>
00382     inline bool
00383     operator!=(const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x,
00384            const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y)
00385     { return !(__x == __y); }
00386 
00387 _GLIBCXX_END_NESTED_NAMESPACE
00388 
00389 #endif /* _UNORDERED_SET_H */
00390