1// unordered_set implementation -*- C++ -*- 2 3// Copyright (C) 2010, 2011 Free Software Foundation, Inc. 4// 5// This file is part of the GNU ISO C++ Library. This library is free 6// software; you can redistribute it and/or modify it under the 7// terms of the GNU General Public License as published by the 8// Free Software Foundation; either version 3, or (at your option) 9// any later version. 10 11// This library is distributed in the hope that it will be useful, 12// but WITHOUT ANY WARRANTY; without even the implied warranty of 13// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 14// GNU General Public License for more details. 15 16// Under Section 7 of GPL version 3, you are granted additional 17// permissions described in the GCC Runtime Library Exception, version 18// 3.1, as published by the Free Software Foundation. 19 20// You should have received a copy of the GNU General Public License and 21// a copy of the GCC Runtime Library Exception along with this program; 22// see the files COPYING3 and COPYING.RUNTIME respectively. If not, see 23// <http://www.gnu.org/licenses/>. 24 25/** @file bits/unordered_set.h 26 * This is an internal header file, included by other library headers. 27 * Do not attempt to use it directly. @headername{unordered_set} 28 */ 29 30#ifndef _UNORDERED_SET_H 31#define _UNORDERED_SET_H 32 33namespace std _GLIBCXX_VISIBILITY(default) 34{ 35_GLIBCXX_BEGIN_NAMESPACE_CONTAINER 36 37 // NB: When we get typedef templates these class definitions 38 // will be unnecessary. 39 template<class _Value, 40 class _Hash = hash<_Value>, 41 class _Pred = std::equal_to<_Value>, 42 class _Alloc = std::allocator<_Value>, 43 bool __cache_hash_code = false> 44 class __unordered_set 45 : public _Hashtable<_Value, _Value, _Alloc, 46 std::_Identity<_Value>, _Pred, 47 _Hash, __detail::_Mod_range_hashing, 48 __detail::_Default_ranged_hash, 49 __detail::_Prime_rehash_policy, 50 __cache_hash_code, true, true> 51 { 52 typedef _Hashtable<_Value, _Value, _Alloc, 53 std::_Identity<_Value>, _Pred, 54 _Hash, __detail::_Mod_range_hashing, 55 __detail::_Default_ranged_hash, 56 __detail::_Prime_rehash_policy, 57 __cache_hash_code, true, true> 58 _Base; 59 60 public: 61 typedef typename _Base::value_type value_type; 62 typedef typename _Base::size_type size_type; 63 typedef typename _Base::hasher hasher; 64 typedef typename _Base::key_equal key_equal; 65 typedef typename _Base::allocator_type allocator_type; 66 67 explicit 68 __unordered_set(size_type __n = 10, 69 const hasher& __hf = hasher(), 70 const key_equal& __eql = key_equal(), 71 const allocator_type& __a = allocator_type()) 72 : _Base(__n, __hf, __detail::_Mod_range_hashing(), 73 __detail::_Default_ranged_hash(), __eql, 74 std::_Identity<value_type>(), __a) 75 { } 76 77 template<typename _InputIterator> 78 __unordered_set(_InputIterator __f, _InputIterator __l, 79 size_type __n = 0, 80 const hasher& __hf = hasher(), 81 const key_equal& __eql = key_equal(), 82 const allocator_type& __a = allocator_type()) 83 : _Base(__f, __l, __n, __hf, __detail::_Mod_range_hashing(), 84 __detail::_Default_ranged_hash(), __eql, 85 std::_Identity<value_type>(), __a) 86 { } 87 88 __unordered_set(initializer_list<value_type> __l, 89 size_type __n = 0, 90 const hasher& __hf = hasher(), 91 const key_equal& __eql = key_equal(), 92 const allocator_type& __a = allocator_type()) 93 : _Base(__l.begin(), __l.end(), __n, __hf, 94 __detail::_Mod_range_hashing(), 95 __detail::_Default_ranged_hash(), __eql, 96 std::_Identity<value_type>(), __a) 97 { } 98 99 __unordered_set& 100 operator=(initializer_list<value_type> __l) 101 { 102 this->clear(); 103 this->insert(__l.begin(), __l.end()); 104 return *this; 105 } 106 }; 107 108 template<class _Value, 109 class _Hash = hash<_Value>, 110 class _Pred = std::equal_to<_Value>, 111 class _Alloc = std::allocator<_Value>, 112 bool __cache_hash_code = false> 113 class __unordered_multiset 114 : public _Hashtable<_Value, _Value, _Alloc, 115 std::_Identity<_Value>, _Pred, 116 _Hash, __detail::_Mod_range_hashing, 117 __detail::_Default_ranged_hash, 118 __detail::_Prime_rehash_policy, 119 __cache_hash_code, true, false> 120 { 121 typedef _Hashtable<_Value, _Value, _Alloc, 122 std::_Identity<_Value>, _Pred, 123 _Hash, __detail::_Mod_range_hashing, 124 __detail::_Default_ranged_hash, 125 __detail::_Prime_rehash_policy, 126 __cache_hash_code, true, false> 127 _Base; 128 129 public: 130 typedef typename _Base::value_type value_type; 131 typedef typename _Base::size_type size_type; 132 typedef typename _Base::hasher hasher; 133 typedef typename _Base::key_equal key_equal; 134 typedef typename _Base::allocator_type allocator_type; 135 136 explicit 137 __unordered_multiset(size_type __n = 10, 138 const hasher& __hf = hasher(), 139 const key_equal& __eql = key_equal(), 140 const allocator_type& __a = allocator_type()) 141 : _Base(__n, __hf, __detail::_Mod_range_hashing(), 142 __detail::_Default_ranged_hash(), __eql, 143 std::_Identity<value_type>(), __a) 144 { } 145 146 147 template<typename _InputIterator> 148 __unordered_multiset(_InputIterator __f, _InputIterator __l, 149 size_type __n = 0, 150 const hasher& __hf = hasher(), 151 const key_equal& __eql = key_equal(), 152 const allocator_type& __a = allocator_type()) 153 : _Base(__f, __l, __n, __hf, __detail::_Mod_range_hashing(), 154 __detail::_Default_ranged_hash(), __eql, 155 std::_Identity<value_type>(), __a) 156 { } 157 158 __unordered_multiset(initializer_list<value_type> __l, 159 size_type __n = 0, 160 const hasher& __hf = hasher(), 161 const key_equal& __eql = key_equal(), 162 const allocator_type& __a = allocator_type()) 163 : _Base(__l.begin(), __l.end(), __n, __hf, 164 __detail::_Mod_range_hashing(), 165 __detail::_Default_ranged_hash(), __eql, 166 std::_Identity<value_type>(), __a) 167 { } 168 169 __unordered_multiset& 170 operator=(initializer_list<value_type> __l) 171 { 172 this->clear(); 173 this->insert(__l.begin(), __l.end()); 174 return *this; 175 } 176 }; 177 178 template<class _Value, class _Hash, class _Pred, class _Alloc, 179 bool __cache_hash_code> 180 inline void 181 swap(__unordered_set<_Value, _Hash, _Pred, _Alloc, __cache_hash_code>& __x, 182 __unordered_set<_Value, _Hash, _Pred, _Alloc, __cache_hash_code>& __y) 183 { __x.swap(__y); } 184 185 template<class _Value, class _Hash, class _Pred, class _Alloc, 186 bool __cache_hash_code> 187 inline void 188 swap(__unordered_multiset<_Value, _Hash, _Pred, 189 _Alloc, __cache_hash_code>& __x, 190 __unordered_multiset<_Value, _Hash, _Pred, 191 _Alloc, __cache_hash_code>& __y) 192 { __x.swap(__y); } 193 194 template<class _Value, class _Hash, class _Pred, class _Alloc, 195 bool __cache_hash_code> 196 inline bool 197 operator==(const __unordered_set<_Value, _Hash, _Pred, _Alloc, 198 __cache_hash_code>& __x, 199 const __unordered_set<_Value, _Hash, _Pred, _Alloc, 200 __cache_hash_code>& __y) 201 { return __x._M_equal(__y); } 202 203 template<class _Value, class _Hash, class _Pred, class _Alloc, 204 bool __cache_hash_code> 205 inline bool 206 operator!=(const __unordered_set<_Value, _Hash, _Pred, _Alloc, 207 __cache_hash_code>& __x, 208 const __unordered_set<_Value, _Hash, _Pred, _Alloc, 209 __cache_hash_code>& __y) 210 { return !(__x == __y); } 211 212 template<class _Value, class _Hash, class _Pred, class _Alloc, 213 bool __cache_hash_code> 214 inline bool 215 operator==(const __unordered_multiset<_Value, _Hash, _Pred, _Alloc, 216 __cache_hash_code>& __x, 217 const __unordered_multiset<_Value, _Hash, _Pred, _Alloc, 218 __cache_hash_code>& __y) 219 { return __x._M_equal(__y); } 220 221 template<class _Value, class _Hash, class _Pred, class _Alloc, 222 bool __cache_hash_code> 223 inline bool 224 operator!=(const __unordered_multiset<_Value, _Hash, _Pred, _Alloc, 225 __cache_hash_code>& __x, 226 const __unordered_multiset<_Value, _Hash, _Pred, _Alloc, 227 __cache_hash_code>& __y) 228 { return !(__x == __y); } 229 230 /** 231 * @brief A standard container composed of unique keys (containing 232 * at most one of each key value) in which the elements' keys are 233 * the elements themselves. 234 * 235 * @ingroup unordered_associative_containers 236 * 237 * Meets the requirements of a <a href="tables.html#65">container</a>, and 238 * <a href="tables.html#xx">unordered associative container</a> 239 * 240 * @param Value Type of key objects. 241 * @param Hash Hashing function object type, defaults to hash<Value>. 242 * @param Pred Predicate function object type, defaults to equal_to<Value>. 243 * @param Alloc Allocator type, defaults to allocator<Key>. 244 */ 245 template<class _Value, 246 class _Hash = hash<_Value>, 247 class _Pred = std::equal_to<_Value>, 248 class _Alloc = std::allocator<_Value> > 249 class unordered_set 250 : public __unordered_set<_Value, _Hash, _Pred, _Alloc> 251 { 252 typedef __unordered_set<_Value, _Hash, _Pred, _Alloc> _Base; 253 254 public: 255 typedef typename _Base::value_type value_type; 256 typedef typename _Base::size_type size_type; 257 typedef typename _Base::hasher hasher; 258 typedef typename _Base::key_equal key_equal; 259 typedef typename _Base::allocator_type allocator_type; 260 261 explicit 262 unordered_set(size_type __n = 10, 263 const hasher& __hf = hasher(), 264 const key_equal& __eql = key_equal(), 265 const allocator_type& __a = allocator_type()) 266 : _Base(__n, __hf, __eql, __a) 267 { } 268 269 template<typename _InputIterator> 270 unordered_set(_InputIterator __f, _InputIterator __l, 271 size_type __n = 0, 272 const hasher& __hf = hasher(), 273 const key_equal& __eql = key_equal(), 274 const allocator_type& __a = allocator_type()) 275 : _Base(__f, __l, __n, __hf, __eql, __a) 276 { } 277 278 unordered_set(initializer_list<value_type> __l, 279 size_type __n = 0, 280 const hasher& __hf = hasher(), 281 const key_equal& __eql = key_equal(), 282 const allocator_type& __a = allocator_type()) 283 : _Base(__l.begin(), __l.end(), __n, __hf, __eql, __a) 284 { } 285 286 unordered_set& 287 operator=(initializer_list<value_type> __l) 288 { 289 this->clear(); 290 this->insert(__l.begin(), __l.end()); 291 return *this; 292 } 293 }; 294 295 /** 296 * @brief A standard container composed of equivalent keys 297 * (possibly containing multiple of each key value) in which the 298 * elements' keys are the elements themselves. 299 * 300 * @ingroup unordered_associative_containers 301 * 302 * Meets the requirements of a <a href="tables.html#65">container</a>, and 303 * <a href="tables.html#xx">unordered associative container</a> 304 * 305 * @param Value Type of key objects. 306 * @param Hash Hashing function object type, defaults to hash<Value>. 307 * @param Pred Predicate function object type, defaults to equal_to<Value>. 308 * @param Alloc Allocator type, defaults to allocator<Key>. 309 */ 310 template<class _Value, 311 class _Hash = hash<_Value>, 312 class _Pred = std::equal_to<_Value>, 313 class _Alloc = std::allocator<_Value> > 314 class unordered_multiset 315 : public __unordered_multiset<_Value, _Hash, _Pred, _Alloc> 316 { 317 typedef __unordered_multiset<_Value, _Hash, _Pred, _Alloc> _Base; 318 319 public: 320 typedef typename _Base::value_type value_type; 321 typedef typename _Base::size_type size_type; 322 typedef typename _Base::hasher hasher; 323 typedef typename _Base::key_equal key_equal; 324 typedef typename _Base::allocator_type allocator_type; 325 326 explicit 327 unordered_multiset(size_type __n = 10, 328 const hasher& __hf = hasher(), 329 const key_equal& __eql = key_equal(), 330 const allocator_type& __a = allocator_type()) 331 : _Base(__n, __hf, __eql, __a) 332 { } 333 334 335 template<typename _InputIterator> 336 unordered_multiset(_InputIterator __f, _InputIterator __l, 337 size_type __n = 0, 338 const hasher& __hf = hasher(), 339 const key_equal& __eql = key_equal(), 340 const allocator_type& __a = allocator_type()) 341 : _Base(__f, __l, __n, __hf, __eql, __a) 342 { } 343 344 unordered_multiset(initializer_list<value_type> __l, 345 size_type __n = 0, 346 const hasher& __hf = hasher(), 347 const key_equal& __eql = key_equal(), 348 const allocator_type& __a = allocator_type()) 349 : _Base(__l.begin(), __l.end(), __n, __hf, __eql, __a) 350 { } 351 352 unordered_multiset& 353 operator=(initializer_list<value_type> __l) 354 { 355 this->clear(); 356 this->insert(__l.begin(), __l.end()); 357 return *this; 358 } 359 }; 360 361 template<class _Value, class _Hash, class _Pred, class _Alloc> 362 inline void 363 swap(unordered_set<_Value, _Hash, _Pred, _Alloc>& __x, 364 unordered_set<_Value, _Hash, _Pred, _Alloc>& __y) 365 { __x.swap(__y); } 366 367 template<class _Value, class _Hash, class _Pred, class _Alloc> 368 inline void 369 swap(unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x, 370 unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y) 371 { __x.swap(__y); } 372 373 template<class _Value, class _Hash, class _Pred, class _Alloc> 374 inline bool 375 operator==(const unordered_set<_Value, _Hash, _Pred, _Alloc>& __x, 376 const unordered_set<_Value, _Hash, _Pred, _Alloc>& __y) 377 { return __x._M_equal(__y); } 378 379 template<class _Value, class _Hash, class _Pred, class _Alloc> 380 inline bool 381 operator!=(const unordered_set<_Value, _Hash, _Pred, _Alloc>& __x, 382 const unordered_set<_Value, _Hash, _Pred, _Alloc>& __y) 383 { return !(__x == __y); } 384 385 template<class _Value, class _Hash, class _Pred, class _Alloc> 386 inline bool 387 operator==(const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x, 388 const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y) 389 { return __x._M_equal(__y); } 390 391 template<class _Value, class _Hash, class _Pred, class _Alloc> 392 inline bool 393 operator!=(const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x, 394 const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y) 395 { return !(__x == __y); } 396 397_GLIBCXX_END_NAMESPACE_CONTAINER 398} // namespace std 399 400#endif /* _UNORDERED_SET_H */ 401 402