1 // unordered_set implementation -*- C++ -*- 2 3 // Copyright (C) 2010 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 * You should not attempt to use it directly. 28 */ 29 30 #ifndef _UNORDERED_SET_H 31 #define _UNORDERED_SET_H 32 33 _GLIBCXX_BEGIN_NESTED_NAMESPACE(std, _GLIBCXX_STD_D) 34 35 // XXX When we get typedef templates these class definitions 36 // will be unnecessary. 37 template<class _Value, 38 class _Hash = hash<_Value>, 39 class _Pred = std::equal_to<_Value>, 40 class _Alloc = std::allocator<_Value>, 41 bool __cache_hash_code = false> 42 class __unordered_set 43 : public _Hashtable<_Value, _Value, _Alloc, 44 std::_Identity<_Value>, _Pred, 45 _Hash, __detail::_Mod_range_hashing, 46 __detail::_Default_ranged_hash, 47 __detail::_Prime_rehash_policy, 48 __cache_hash_code, true, true> 49 { 50 typedef _Hashtable<_Value, _Value, _Alloc, 51 std::_Identity<_Value>, _Pred, 52 _Hash, __detail::_Mod_range_hashing, 53 __detail::_Default_ranged_hash, 54 __detail::_Prime_rehash_policy, 55 __cache_hash_code, true, true> 56 _Base; 57 58 public: 59 typedef typename _Base::size_type size_type; 60 typedef typename _Base::hasher hasher; 61 typedef typename _Base::key_equal key_equal; 62 typedef typename _Base::allocator_type allocator_type; 63 64 explicit 65 __unordered_set(size_type __n = 10, 66 const hasher& __hf = hasher(), 67 const key_equal& __eql = key_equal(), 68 const allocator_type& __a = allocator_type()) 69 : _Base(__n, __hf, __detail::_Mod_range_hashing(), 70 __detail::_Default_ranged_hash(), __eql, 71 std::_Identity<_Value>(), __a) 72 { } 73 74 template<typename _InputIterator> 75 __unordered_set(_InputIterator __f, _InputIterator __l, 76 size_type __n = 10, 77 const hasher& __hf = hasher(), 78 const key_equal& __eql = key_equal(), 79 const allocator_type& __a = allocator_type()) 80 : _Base(__f, __l, __n, __hf, __detail::_Mod_range_hashing(), 81 __detail::_Default_ranged_hash(), __eql, 82 std::_Identity<_Value>(), __a) 83 { } 84 85 __unordered_set(__unordered_set&& __x) 86 : _Base(std::forward<_Base>(__x)) { } 87 }; 88 89 template<class _Value, 90 class _Hash = hash<_Value>, 91 class _Pred = std::equal_to<_Value>, 92 class _Alloc = std::allocator<_Value>, 93 bool __cache_hash_code = false> 94 class __unordered_multiset 95 : public _Hashtable<_Value, _Value, _Alloc, 96 std::_Identity<_Value>, _Pred, 97 _Hash, __detail::_Mod_range_hashing, 98 __detail::_Default_ranged_hash, 99 __detail::_Prime_rehash_policy, 100 __cache_hash_code, true, false> 101 { 102 typedef _Hashtable<_Value, _Value, _Alloc, 103 std::_Identity<_Value>, _Pred, 104 _Hash, __detail::_Mod_range_hashing, 105 __detail::_Default_ranged_hash, 106 __detail::_Prime_rehash_policy, 107 __cache_hash_code, true, false> 108 _Base; 109 110 public: 111 typedef typename _Base::size_type size_type; 112 typedef typename _Base::hasher hasher; 113 typedef typename _Base::key_equal key_equal; 114 typedef typename _Base::allocator_type allocator_type; 115 116 explicit 117 __unordered_multiset(size_type __n = 10, 118 const hasher& __hf = hasher(), 119 const key_equal& __eql = key_equal(), 120 const allocator_type& __a = allocator_type()) 121 : _Base(__n, __hf, __detail::_Mod_range_hashing(), 122 __detail::_Default_ranged_hash(), __eql, 123 std::_Identity<_Value>(), __a) 124 { } 125 126 127 template<typename _InputIterator> 128 __unordered_multiset(_InputIterator __f, _InputIterator __l, 129 typename _Base::size_type __n = 0, 130 const hasher& __hf = hasher(), 131 const key_equal& __eql = key_equal(), 132 const allocator_type& __a = allocator_type()) 133 : _Base(__f, __l, __n, __hf, __detail::_Mod_range_hashing(), 134 __detail::_Default_ranged_hash(), __eql, 135 std::_Identity<_Value>(), __a) 136 { } 137 138 __unordered_multiset(__unordered_multiset&& __x) 139 : _Base(std::forward<_Base>(__x)) { } 140 }; 141 142 template<class _Value, class _Hash, class _Pred, class _Alloc, 143 bool __cache_hash_code> 144 inline void 145 swap(__unordered_set<_Value, _Hash, _Pred, _Alloc, __cache_hash_code>& __x, 146 __unordered_set<_Value, _Hash, _Pred, _Alloc, __cache_hash_code>& __y) 147 { __x.swap(__y); } 148 149 template<class _Value, class _Hash, class _Pred, class _Alloc, 150 bool __cache_hash_code> 151 inline void 152 swap(__unordered_multiset<_Value, _Hash, _Pred, 153 _Alloc, __cache_hash_code>& __x, 154 __unordered_multiset<_Value, _Hash, _Pred, 155 _Alloc, __cache_hash_code>& __y) 156 { __x.swap(__y); } 157 158 template<class _Value, class _Hash, class _Pred, class _Alloc, 159 bool __cache_hash_code> 160 inline bool 161 operator==(const __unordered_set<_Value, _Hash, _Pred, _Alloc, 162 __cache_hash_code>& __x, 163 const __unordered_set<_Value, _Hash, _Pred, _Alloc, 164 __cache_hash_code>& __y) 165 { return __x._M_equal(__y); } 166 167 template<class _Value, class _Hash, class _Pred, class _Alloc, 168 bool __cache_hash_code> 169 inline bool 170 operator!=(const __unordered_set<_Value, _Hash, _Pred, _Alloc, 171 __cache_hash_code>& __x, 172 const __unordered_set<_Value, _Hash, _Pred, _Alloc, 173 __cache_hash_code>& __y) 174 { return !(__x == __y); } 175 176 template<class _Value, class _Hash, class _Pred, class _Alloc, 177 bool __cache_hash_code> 178 inline bool 179 operator==(const __unordered_multiset<_Value, _Hash, _Pred, _Alloc, 180 __cache_hash_code>& __x, 181 const __unordered_multiset<_Value, _Hash, _Pred, _Alloc, 182 __cache_hash_code>& __y) 183 { return __x._M_equal(__y); } 184 185 template<class _Value, class _Hash, class _Pred, class _Alloc, 186 bool __cache_hash_code> 187 inline bool 188 operator!=(const __unordered_multiset<_Value, _Hash, _Pred, _Alloc, 189 __cache_hash_code>& __x, 190 const __unordered_multiset<_Value, _Hash, _Pred, _Alloc, 191 __cache_hash_code>& __y) 192 { return !(__x == __y); } 193 194 /** 195 * @brief A standard container composed of unique keys (containing 196 * at most one of each key value) in which the elements' keys are 197 * the elements themselves. 198 * 199 * @ingroup unordered_associative_containers 200 * 201 * Meets the requirements of a <a href="tables.html#65">container</a>, and 202 * <a href="tables.html#xx">unordered associative container</a> 203 * 204 * @param Value Type of key objects. 205 * @param Hash Hashing function object type, defaults to hash<Value>. 206 * @param Pred Predicate function object type, defaults to equal_to<Value>. 207 * @param Alloc Allocator type, defaults to allocator<Key>. 208 */ 209 template<class _Value, 210 class _Hash = hash<_Value>, 211 class _Pred = std::equal_to<_Value>, 212 class _Alloc = std::allocator<_Value> > 213 class unordered_set 214 : public __unordered_set<_Value, _Hash, _Pred, _Alloc> 215 { 216 typedef __unordered_set<_Value, _Hash, _Pred, _Alloc> _Base; 217 218 public: 219 typedef typename _Base::value_type value_type; 220 typedef typename _Base::size_type size_type; 221 typedef typename _Base::hasher hasher; 222 typedef typename _Base::key_equal key_equal; 223 typedef typename _Base::allocator_type allocator_type; 224 225 explicit 226 unordered_set(size_type __n = 10, 227 const hasher& __hf = hasher(), 228 const key_equal& __eql = key_equal(), 229 const allocator_type& __a = allocator_type()) 230 : _Base(__n, __hf, __eql, __a) 231 { } 232 233 template<typename _InputIterator> 234 unordered_set(_InputIterator __f, _InputIterator __l, 235 size_type __n = 10, 236 const hasher& __hf = hasher(), 237 const key_equal& __eql = key_equal(), 238 const allocator_type& __a = allocator_type()) 239 : _Base(__f, __l, __n, __hf, __eql, __a) 240 { } 241 242 unordered_set(unordered_set&& __x) 243 : _Base(std::forward<_Base>(__x)) { } 244 245 unordered_set(initializer_list<value_type> __l, 246 size_type __n = 10, 247 const hasher& __hf = hasher(), 248 const key_equal& __eql = key_equal(), 249 const allocator_type& __a = allocator_type()) 250 : _Base(__l.begin(), __l.end(), __n, __hf, __eql, __a) 251 { } 252 253 unordered_set& 254 operator=(unordered_set&& __x) 255 { 256 // NB: DR 1204. 257 // NB: DR 675. 258 this->clear(); 259 this->swap(__x); 260 return *this; 261 } 262 263 unordered_set& 264 operator=(initializer_list<value_type> __l) 265 { 266 this->clear(); 267 this->insert(__l.begin(), __l.end()); 268 return *this; 269 } 270 }; 271 272 /** 273 * @brief A standard container composed of equivalent keys 274 * (possibly containing multiple of each key value) in which the 275 * elements' keys are the elements themselves. 276 * 277 * @ingroup unordered_associative_containers 278 * 279 * Meets the requirements of a <a href="tables.html#65">container</a>, and 280 * <a href="tables.html#xx">unordered associative container</a> 281 * 282 * @param Value Type of key objects. 283 * @param Hash Hashing function object type, defaults to hash<Value>. 284 * @param Pred Predicate function object type, defaults to equal_to<Value>. 285 * @param Alloc Allocator type, defaults to allocator<Key>. 286 */ 287 template<class _Value, 288 class _Hash = hash<_Value>, 289 class _Pred = std::equal_to<_Value>, 290 class _Alloc = std::allocator<_Value> > 291 class unordered_multiset 292 : public __unordered_multiset<_Value, _Hash, _Pred, _Alloc> 293 { 294 typedef __unordered_multiset<_Value, _Hash, _Pred, _Alloc> _Base; 295 296 public: 297 typedef typename _Base::value_type value_type; 298 typedef typename _Base::size_type size_type; 299 typedef typename _Base::hasher hasher; 300 typedef typename _Base::key_equal key_equal; 301 typedef typename _Base::allocator_type allocator_type; 302 303 explicit 304 unordered_multiset(size_type __n = 10, 305 const hasher& __hf = hasher(), 306 const key_equal& __eql = key_equal(), 307 const allocator_type& __a = allocator_type()) 308 : _Base(__n, __hf, __eql, __a) 309 { } 310 311 312 template<typename _InputIterator> 313 unordered_multiset(_InputIterator __f, _InputIterator __l, 314 typename _Base::size_type __n = 0, 315 const hasher& __hf = hasher(), 316 const key_equal& __eql = key_equal(), 317 const allocator_type& __a = allocator_type()) 318 : _Base(__f, __l, __n, __hf, __eql, __a) 319 { } 320 321 unordered_multiset(unordered_multiset&& __x) 322 : _Base(std::forward<_Base>(__x)) { } 323 324 unordered_multiset(initializer_list<value_type> __l, 325 size_type __n = 10, 326 const hasher& __hf = hasher(), 327 const key_equal& __eql = key_equal(), 328 const allocator_type& __a = allocator_type()) 329 : _Base(__l.begin(), __l.end(), __n, __hf, __eql, __a) 330 { } 331 332 unordered_multiset& 333 operator=(unordered_multiset&& __x) 334 { 335 // NB: DR 1204. 336 // NB: DR 675. 337 this->clear(); 338 this->swap(__x); 339 return *this; 340 } 341 342 unordered_multiset& 343 operator=(initializer_list<value_type> __l) 344 { 345 this->clear(); 346 this->insert(__l.begin(), __l.end()); 347 return *this; 348 } 349 }; 350 351 template<class _Value, class _Hash, class _Pred, class _Alloc> 352 inline void 353 swap(unordered_set<_Value, _Hash, _Pred, _Alloc>& __x, 354 unordered_set<_Value, _Hash, _Pred, _Alloc>& __y) 355 { __x.swap(__y); } 356 357 template<class _Value, class _Hash, class _Pred, class _Alloc> 358 inline void 359 swap(unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x, 360 unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y) 361 { __x.swap(__y); } 362 363 template<class _Value, class _Hash, class _Pred, class _Alloc> 364 inline bool 365 operator==(const unordered_set<_Value, _Hash, _Pred, _Alloc>& __x, 366 const unordered_set<_Value, _Hash, _Pred, _Alloc>& __y) 367 { return __x._M_equal(__y); } 368 369 template<class _Value, class _Hash, class _Pred, class _Alloc> 370 inline bool 371 operator!=(const unordered_set<_Value, _Hash, _Pred, _Alloc>& __x, 372 const unordered_set<_Value, _Hash, _Pred, _Alloc>& __y) 373 { return !(__x == __y); } 374 375 template<class _Value, class _Hash, class _Pred, class _Alloc> 376 inline bool 377 operator==(const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x, 378 const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y) 379 { return __x._M_equal(__y); } 380 381 template<class _Value, class _Hash, class _Pred, class _Alloc> 382 inline bool 383 operator!=(const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x, 384 const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y) 385 { return !(__x == __y); } 386 387 _GLIBCXX_END_NESTED_NAMESPACE 388 389 #endif /* _UNORDERED_SET_H */ 390 391