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