libstdc++
|
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