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