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 = 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