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