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