1 /** 2 * MIT License 3 * 4 * Copyright (c) 2017 Tessil 5 * 6 * Permission is hereby granted, free of charge, to any person obtaining a copy 7 * of this software and associated documentation files (the "Software"), to deal 8 * in the Software without restriction, including without limitation the rights 9 * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell 10 * copies of the Software, and to permit persons to whom the Software is 11 * furnished to do so, subject to the following conditions: 12 * 13 * The above copyright notice and this permission notice shall be included in all 14 * copies or substantial portions of the Software. 15 * 16 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR 17 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, 18 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE 19 * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER 20 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, 21 * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE 22 * SOFTWARE. 23 */ 24 #ifndef TSL_HOPSCOTCH_MAP_H 25 #define TSL_HOPSCOTCH_MAP_H 26 27 28 #include <algorithm> 29 #include <cstddef> 30 #include <functional> 31 #include <initializer_list> 32 #include <list> 33 #include <memory> 34 #include <type_traits> 35 #include <utility> 36 #include "hopscotch_hash.h" 37 38 39 namespace tsl { 40 41 /** 42 * Implementation of a hash map using the hopscotch hashing algorithm. 43 * 44 * The Key and the value T must be either nothrow move-constructible, copy-constuctible or both. 45 * 46 * The size of the neighborhood (NeighborhoodSize) must be > 0 and <= 62 if StoreHash is false. 47 * When StoreHash is true, 32-bits of the hash will be stored alongside the neighborhood limiting 48 * the NeighborhoodSize to <= 30. There is no memory usage difference between 49 * 'NeighborhoodSize 62; StoreHash false' and 'NeighborhoodSize 30; StoreHash true'. 50 * 51 * Storing the hash may improve performance on insert during the rehash process if the hash takes time 52 * to compute. It may also improve read performance if the KeyEqual function takes time (or incurs a cache-miss). 53 * If used with simple Hash and KeyEqual it may slow things down. 54 * 55 * StoreHash can only be set if the GrowthPolicy is set to tsl::power_of_two_growth_policy. 56 * 57 * GrowthPolicy defines how the map grows and consequently how a hash value is mapped to a bucket. 58 * By default the map uses tsl::power_of_two_growth_policy. This policy keeps the number of buckets 59 * to a power of two and uses a mask to map the hash to a bucket instead of the slow modulo. 60 * You may define your own growth policy, check tsl::power_of_two_growth_policy for the interface. 61 * 62 * If the destructors of Key or T throw an exception, behaviour of the class is undefined. 63 * 64 * Iterators invalidation: 65 * - clear, operator=, reserve, rehash: always invalidate the iterators. 66 * - insert, emplace, emplace_hint, operator[]: if there is an effective insert, invalidate the iterators 67 * if a displacement is needed to resolve a collision (which mean that most of the time, 68 * insert will invalidate the iterators). Or if there is a rehash. 69 * - erase: iterator on the erased element is the only one which become invalid. 70 */ 71 template<class Key, 72 class T, 73 class Hash = std::hash<Key>, 74 class KeyEqual = std::equal_to<Key>, 75 class Allocator = std::allocator<std::pair<Key, T>>, 76 unsigned int NeighborhoodSize = 62, 77 bool StoreHash = false, 78 class GrowthPolicy = tsl::hh::power_of_two_growth_policy<2>> 79 class hopscotch_map { 80 private: 81 template<typename U> 82 using has_is_transparent = tsl::detail_hopscotch_hash::has_is_transparent<U>; 83 84 class KeySelect { 85 public: 86 using key_type = Key; 87 operator()88 const key_type& operator()(const std::pair<Key, T>& key_value) const { 89 return key_value.first; 90 } 91 operator()92 key_type& operator()(std::pair<Key, T>& key_value) { 93 return key_value.first; 94 } 95 }; 96 97 class ValueSelect { 98 public: 99 using value_type = T; 100 operator()101 const value_type& operator()(const std::pair<Key, T>& key_value) const { 102 return key_value.second; 103 } 104 operator()105 value_type& operator()(std::pair<Key, T>& key_value) { 106 return key_value.second; 107 } 108 }; 109 110 111 using overflow_container_type = std::list<std::pair<Key, T>, Allocator>; 112 using ht = detail_hopscotch_hash::hopscotch_hash<std::pair<Key, T>, KeySelect, ValueSelect, 113 Hash, KeyEqual, 114 Allocator, NeighborhoodSize, 115 StoreHash, GrowthPolicy, 116 overflow_container_type>; 117 118 public: 119 using key_type = typename ht::key_type; 120 using mapped_type = T; 121 using value_type = typename ht::value_type; 122 using size_type = typename ht::size_type; 123 using difference_type = typename ht::difference_type; 124 using hasher = typename ht::hasher; 125 using key_equal = typename ht::key_equal; 126 using allocator_type = typename ht::allocator_type; 127 using reference = typename ht::reference; 128 using const_reference = typename ht::const_reference; 129 using pointer = typename ht::pointer; 130 using const_pointer = typename ht::const_pointer; 131 using iterator = typename ht::iterator; 132 using const_iterator = typename ht::const_iterator; 133 134 135 136 /* 137 * Constructors 138 */ hopscotch_map()139 hopscotch_map() : hopscotch_map(ht::DEFAULT_INIT_BUCKETS_SIZE) { 140 } 141 142 explicit hopscotch_map(size_type bucket_count, 143 const Hash& hash = Hash(), 144 const KeyEqual& equal = KeyEqual(), 145 const Allocator& alloc = Allocator()) : m_ht(bucket_count,hash,equal,alloc,ht::DEFAULT_MAX_LOAD_FACTOR)146 m_ht(bucket_count, hash, equal, alloc, ht::DEFAULT_MAX_LOAD_FACTOR) 147 { 148 } 149 hopscotch_map(size_type bucket_count,const Allocator & alloc)150 hopscotch_map(size_type bucket_count, 151 const Allocator& alloc) : hopscotch_map(bucket_count, Hash(), KeyEqual(), alloc) 152 { 153 } 154 hopscotch_map(size_type bucket_count,const Hash & hash,const Allocator & alloc)155 hopscotch_map(size_type bucket_count, 156 const Hash& hash, 157 const Allocator& alloc) : hopscotch_map(bucket_count, hash, KeyEqual(), alloc) 158 { 159 } 160 hopscotch_map(const Allocator & alloc)161 explicit hopscotch_map(const Allocator& alloc) : hopscotch_map(ht::DEFAULT_INIT_BUCKETS_SIZE, alloc) { 162 } 163 164 template<class InputIt> 165 hopscotch_map(InputIt first, InputIt last, 166 size_type bucket_count = ht::DEFAULT_INIT_BUCKETS_SIZE, 167 const Hash& hash = Hash(), 168 const KeyEqual& equal = KeyEqual(), hopscotch_map(bucket_count,hash,equal,alloc)169 const Allocator& alloc = Allocator()) : hopscotch_map(bucket_count, hash, equal, alloc) 170 { 171 insert(first, last); 172 } 173 174 template<class InputIt> hopscotch_map(InputIt first,InputIt last,size_type bucket_count,const Allocator & alloc)175 hopscotch_map(InputIt first, InputIt last, 176 size_type bucket_count, 177 const Allocator& alloc) : hopscotch_map(first, last, bucket_count, Hash(), KeyEqual(), alloc) 178 { 179 } 180 181 template<class InputIt> hopscotch_map(InputIt first,InputIt last,size_type bucket_count,const Hash & hash,const Allocator & alloc)182 hopscotch_map(InputIt first, InputIt last, 183 size_type bucket_count, 184 const Hash& hash, 185 const Allocator& alloc) : hopscotch_map(first, last, bucket_count, hash, KeyEqual(), alloc) 186 { 187 } 188 189 hopscotch_map(std::initializer_list<value_type> init, 190 size_type bucket_count = ht::DEFAULT_INIT_BUCKETS_SIZE, 191 const Hash& hash = Hash(), 192 const KeyEqual& equal = KeyEqual(), 193 const Allocator& alloc = Allocator()) : 194 hopscotch_map(init.begin(), init.end(), bucket_count, hash, equal, alloc) 195 { 196 } 197 hopscotch_map(std::initializer_list<value_type> init,size_type bucket_count,const Allocator & alloc)198 hopscotch_map(std::initializer_list<value_type> init, 199 size_type bucket_count, 200 const Allocator& alloc) : 201 hopscotch_map(init.begin(), init.end(), bucket_count, Hash(), KeyEqual(), alloc) 202 { 203 } 204 hopscotch_map(std::initializer_list<value_type> init,size_type bucket_count,const Hash & hash,const Allocator & alloc)205 hopscotch_map(std::initializer_list<value_type> init, 206 size_type bucket_count, 207 const Hash& hash, 208 const Allocator& alloc) : 209 hopscotch_map(init.begin(), init.end(), bucket_count, hash, KeyEqual(), alloc) 210 { 211 } 212 213 214 hopscotch_map& operator=(std::initializer_list<value_type> ilist) { 215 m_ht.clear(); 216 217 m_ht.reserve(ilist.size()); 218 m_ht.insert(ilist.begin(), ilist.end()); 219 220 return *this; 221 } 222 get_allocator()223 allocator_type get_allocator() const { return m_ht.get_allocator(); } 224 225 226 /* 227 * Iterators 228 */ begin()229 iterator begin() noexcept { return m_ht.begin(); } begin()230 const_iterator begin() const noexcept { return m_ht.begin(); } cbegin()231 const_iterator cbegin() const noexcept { return m_ht.cbegin(); } 232 end()233 iterator end() noexcept { return m_ht.end(); } end()234 const_iterator end() const noexcept { return m_ht.end(); } cend()235 const_iterator cend() const noexcept { return m_ht.cend(); } 236 237 238 /* 239 * Capacity 240 */ empty()241 bool empty() const noexcept { return m_ht.empty(); } size()242 size_type size() const noexcept { return m_ht.size(); } max_size()243 size_type max_size() const noexcept { return m_ht.max_size(); } 244 245 /* 246 * Modifiers 247 */ clear()248 void clear() noexcept { m_ht.clear(); } 249 250 251 252 insert(const value_type & value)253 std::pair<iterator, bool> insert(const value_type& value) { 254 return m_ht.insert(value); 255 } 256 257 template<class P, typename std::enable_if<std::is_constructible<value_type, P&&>::value>::type* = nullptr> insert(P && value)258 std::pair<iterator, bool> insert(P&& value) { 259 return m_ht.insert(std::forward<P>(value)); 260 } 261 insert(value_type && value)262 std::pair<iterator, bool> insert(value_type&& value) { 263 return m_ht.insert(std::move(value)); 264 } 265 266 insert(const_iterator hint,const value_type & value)267 iterator insert(const_iterator hint, const value_type& value) { 268 return m_ht.insert(hint, value); 269 } 270 271 template<class P, typename std::enable_if<std::is_constructible<value_type, P&&>::value>::type* = nullptr> insert(const_iterator hint,P && value)272 iterator insert(const_iterator hint, P&& value) { 273 return m_ht.insert(hint, std::forward<P>(value)); 274 } 275 insert(const_iterator hint,value_type && value)276 iterator insert(const_iterator hint, value_type&& value) { 277 return m_ht.insert(hint, std::move(value)); 278 } 279 280 281 template<class InputIt> insert(InputIt first,InputIt last)282 void insert(InputIt first, InputIt last) { 283 m_ht.insert(first, last); 284 } 285 insert(std::initializer_list<value_type> ilist)286 void insert(std::initializer_list<value_type> ilist) { 287 m_ht.insert(ilist.begin(), ilist.end()); 288 } 289 290 291 292 293 template<class M> insert_or_assign(const key_type & k,M && obj)294 std::pair<iterator, bool> insert_or_assign(const key_type& k, M&& obj) { 295 return m_ht.insert_or_assign(k, std::forward<M>(obj)); 296 } 297 298 template<class M> insert_or_assign(key_type && k,M && obj)299 std::pair<iterator, bool> insert_or_assign(key_type&& k, M&& obj) { 300 return m_ht.insert_or_assign(std::move(k), std::forward<M>(obj)); 301 } 302 303 template<class M> insert_or_assign(const_iterator hint,const key_type & k,M && obj)304 iterator insert_or_assign(const_iterator hint, const key_type& k, M&& obj) { 305 return m_ht.insert_or_assign(hint, k, std::forward<M>(obj)); 306 } 307 308 template<class M> insert_or_assign(const_iterator hint,key_type && k,M && obj)309 iterator insert_or_assign(const_iterator hint, key_type&& k, M&& obj) { 310 return m_ht.insert_or_assign(hint, std::move(k), std::forward<M>(obj)); 311 } 312 313 314 315 316 /** 317 * Due to the way elements are stored, emplace will need to move or copy the key-value once. 318 * The method is equivalent to insert(value_type(std::forward<Args>(args)...)); 319 * 320 * Mainly here for compatibility with the std::unordered_map interface. 321 */ 322 template<class... Args> emplace(Args &&...args)323 std::pair<iterator, bool> emplace(Args&&... args) { 324 return m_ht.emplace(std::forward<Args>(args)...); 325 } 326 327 328 329 330 /** 331 * Due to the way elements are stored, emplace_hint will need to move or copy the key-value once. 332 * The method is equivalent to insert(hint, value_type(std::forward<Args>(args)...)); 333 * 334 * Mainly here for compatibility with the std::unordered_map interface. 335 */ 336 template<class... Args> emplace_hint(const_iterator hint,Args &&...args)337 iterator emplace_hint(const_iterator hint, Args&&... args) { 338 return m_ht.emplace_hint(hint, std::forward<Args>(args)...); 339 } 340 341 342 343 344 template<class... Args> try_emplace(const key_type & k,Args &&...args)345 std::pair<iterator, bool> try_emplace(const key_type& k, Args&&... args) { 346 return m_ht.try_emplace(k, std::forward<Args>(args)...); 347 } 348 349 template<class... Args> try_emplace(key_type && k,Args &&...args)350 std::pair<iterator, bool> try_emplace(key_type&& k, Args&&... args) { 351 return m_ht.try_emplace(std::move(k), std::forward<Args>(args)...); 352 } 353 354 template<class... Args> try_emplace(const_iterator hint,const key_type & k,Args &&...args)355 iterator try_emplace(const_iterator hint, const key_type& k, Args&&... args) { 356 return m_ht.try_emplace(hint, k, std::forward<Args>(args)...); 357 } 358 359 template<class... Args> try_emplace(const_iterator hint,key_type && k,Args &&...args)360 iterator try_emplace(const_iterator hint, key_type&& k, Args&&... args) { 361 return m_ht.try_emplace(hint, std::move(k), std::forward<Args>(args)...); 362 } 363 364 365 366 erase(iterator pos)367 iterator erase(iterator pos) { return m_ht.erase(pos); } erase(const_iterator pos)368 iterator erase(const_iterator pos) { return m_ht.erase(pos); } erase(const_iterator first,const_iterator last)369 iterator erase(const_iterator first, const_iterator last) { return m_ht.erase(first, last); } erase(const key_type & key)370 size_type erase(const key_type& key) { return m_ht.erase(key); } 371 372 /** 373 * Use the hash value 'precalculated_hash' instead of hashing the key. The hash value should be the same 374 * as hash_function()(key). Usefull to speed-up the lookup to the value if you already have the hash. 375 */ erase(const key_type & key,std::size_t precalculated_hash)376 size_type erase(const key_type& key, std::size_t precalculated_hash) { 377 return m_ht.erase(key, precalculated_hash); 378 } 379 380 /** 381 * This overload only participates in the overload resolution if the typedef KeyEqual::is_transparent exists. 382 * If so, K must be hashable and comparable to Key. 383 */ 384 template<class K, class KE = KeyEqual, typename std::enable_if<has_is_transparent<KE>::value>::type* = nullptr> erase(const K & key)385 size_type erase(const K& key) { return m_ht.erase(key); } 386 387 /** 388 * @copydoc erase(const K& key) 389 * 390 * Use the hash value 'precalculated_hash' instead of hashing the key. The hash value should be the same 391 * as hash_function()(key). Usefull to speed-up the lookup to the value if you already have the hash. 392 */ 393 template<class K, class KE = KeyEqual, typename std::enable_if<has_is_transparent<KE>::value>::type* = nullptr> erase(const K & key,std::size_t precalculated_hash)394 size_type erase(const K& key, std::size_t precalculated_hash) { 395 return m_ht.erase(key, precalculated_hash); 396 } 397 398 399 400 swap(hopscotch_map & other)401 void swap(hopscotch_map& other) { other.m_ht.swap(m_ht); } 402 403 /* 404 * Lookup 405 */ at(const Key & key)406 T& at(const Key& key) { return m_ht.at(key); } 407 408 /** 409 * Use the hash value 'precalculated_hash' instead of hashing the key. The hash value should be the same 410 * as hash_function()(key). Usefull to speed-up the lookup if you already have the hash. 411 */ at(const Key & key,std::size_t precalculated_hash)412 T& at(const Key& key, std::size_t precalculated_hash) { return m_ht.at(key, precalculated_hash); } 413 414 at(const Key & key)415 const T& at(const Key& key) const { return m_ht.at(key); } 416 417 /** 418 * @copydoc at(const Key& key, std::size_t precalculated_hash) 419 */ at(const Key & key,std::size_t precalculated_hash)420 const T& at(const Key& key, std::size_t precalculated_hash) const { return m_ht.at(key, precalculated_hash); } 421 422 423 /** 424 * This overload only participates in the overload resolution if the typedef KeyEqual::is_transparent exists. 425 * If so, K must be hashable and comparable to Key. 426 */ 427 template<class K, class KE = KeyEqual, typename std::enable_if<has_is_transparent<KE>::value>::type* = nullptr> at(const K & key)428 T& at(const K& key) { return m_ht.at(key); } 429 430 /** 431 * @copydoc at(const K& key) 432 * 433 * Use the hash value 'precalculated_hash' instead of hashing the key. The hash value should be the same 434 * as hash_function()(key). Usefull to speed-up the lookup if you already have the hash. 435 */ 436 template<class K, class KE = KeyEqual, typename std::enable_if<has_is_transparent<KE>::value>::type* = nullptr> at(const K & key,std::size_t precalculated_hash)437 T& at(const K& key, std::size_t precalculated_hash) { return m_ht.at(key, precalculated_hash); } 438 439 440 /** 441 * @copydoc at(const K& key) 442 */ 443 template<class K, class KE = KeyEqual, typename std::enable_if<has_is_transparent<KE>::value>::type* = nullptr> at(const K & key)444 const T& at(const K& key) const { return m_ht.at(key); } 445 446 /** 447 * @copydoc at(const K& key, std::size_t precalculated_hash) 448 */ 449 template<class K, class KE = KeyEqual, typename std::enable_if<has_is_transparent<KE>::value>::type* = nullptr> at(const K & key,std::size_t precalculated_hash)450 const T& at(const K& key, std::size_t precalculated_hash) const { return m_ht.at(key, precalculated_hash); } 451 452 453 454 455 T& operator[](const Key& key) { return m_ht[key]; } 456 T& operator[](Key&& key) { return m_ht[std::move(key)]; } 457 458 459 460 count(const Key & key)461 size_type count(const Key& key) const { return m_ht.count(key); } 462 463 /** 464 * Use the hash value 'precalculated_hash' instead of hashing the key. The hash value should be the same 465 * as hash_function()(key). Usefull to speed-up the lookup if you already have the hash. 466 */ count(const Key & key,std::size_t precalculated_hash)467 size_type count(const Key& key, std::size_t precalculated_hash) const { 468 return m_ht.count(key, precalculated_hash); 469 } 470 471 /** 472 * This overload only participates in the overload resolution if the typedef KeyEqual::is_transparent exists. 473 * If so, K must be hashable and comparable to Key. 474 */ 475 template<class K, class KE = KeyEqual, typename std::enable_if<has_is_transparent<KE>::value>::type* = nullptr> count(const K & key)476 size_type count(const K& key) const { return m_ht.count(key); } 477 478 /** 479 * @copydoc count(const K& key) const 480 * 481 * Use the hash value 'precalculated_hash' instead of hashing the key. The hash value should be the same 482 * as hash_function()(key). Usefull to speed-up the lookup if you already have the hash. 483 */ 484 template<class K, class KE = KeyEqual, typename std::enable_if<has_is_transparent<KE>::value>::type* = nullptr> count(const K & key,std::size_t precalculated_hash)485 size_type count(const K& key, std::size_t precalculated_hash) const { return m_ht.count(key, precalculated_hash); } 486 487 488 489 find(const Key & key)490 iterator find(const Key& key) { return m_ht.find(key); } 491 492 /** 493 * Use the hash value 'precalculated_hash' instead of hashing the key. The hash value should be the same 494 * as hash_function()(key). Usefull to speed-up the lookup if you already have the hash. 495 */ find(const Key & key,std::size_t precalculated_hash)496 iterator find(const Key& key, std::size_t precalculated_hash) { return m_ht.find(key, precalculated_hash); } 497 find(const Key & key)498 const_iterator find(const Key& key) const { return m_ht.find(key); } 499 500 /** 501 * @copydoc find(const Key& key, std::size_t precalculated_hash) 502 */ find(const Key & key,std::size_t precalculated_hash)503 const_iterator find(const Key& key, std::size_t precalculated_hash) const { 504 return m_ht.find(key, precalculated_hash); 505 } 506 507 /** 508 * This overload only participates in the overload resolution if the typedef KeyEqual::is_transparent exists. 509 * If so, K must be hashable and comparable to Key. 510 */ 511 template<class K, class KE = KeyEqual, typename std::enable_if<has_is_transparent<KE>::value>::type* = nullptr> find(const K & key)512 iterator find(const K& key) { return m_ht.find(key); } 513 514 /** 515 * @copydoc find(const K& key) 516 * 517 * Use the hash value 'precalculated_hash' instead of hashing the key. The hash value should be the same 518 * as hash_function()(key). Usefull to speed-up the lookup if you already have the hash. 519 */ 520 template<class K, class KE = KeyEqual, typename std::enable_if<has_is_transparent<KE>::value>::type* = nullptr> find(const K & key,std::size_t precalculated_hash)521 iterator find(const K& key, std::size_t precalculated_hash) { return m_ht.find(key, precalculated_hash); } 522 523 /** 524 * @copydoc find(const K& key) 525 */ 526 template<class K, class KE = KeyEqual, typename std::enable_if<has_is_transparent<KE>::value>::type* = nullptr> find(const K & key)527 const_iterator find(const K& key) const { return m_ht.find(key); } 528 529 /** 530 * @copydoc find(const K& key) 531 * 532 * Use the hash value 'precalculated_hash' instead of hashing the key. The hash value should be the same 533 * as hash_function()(key). Usefull to speed-up the lookup if you already have the hash. 534 */ 535 template<class K, class KE = KeyEqual, typename std::enable_if<has_is_transparent<KE>::value>::type* = nullptr> find(const K & key,std::size_t precalculated_hash)536 const_iterator find(const K& key, std::size_t precalculated_hash) const { 537 return m_ht.find(key, precalculated_hash); 538 } 539 540 541 542 equal_range(const Key & key)543 std::pair<iterator, iterator> equal_range(const Key& key) { return m_ht.equal_range(key); } 544 545 /** 546 * Use the hash value 'precalculated_hash' instead of hashing the key. The hash value should be the same 547 * as hash_function()(key). Usefull to speed-up the lookup if you already have the hash. 548 */ equal_range(const Key & key,std::size_t precalculated_hash)549 std::pair<iterator, iterator> equal_range(const Key& key, std::size_t precalculated_hash) { 550 return m_ht.equal_range(key, precalculated_hash); 551 } 552 equal_range(const Key & key)553 std::pair<const_iterator, const_iterator> equal_range(const Key& key) const { return m_ht.equal_range(key); } 554 555 /** 556 * @copydoc equal_range(const Key& key, std::size_t precalculated_hash) 557 */ equal_range(const Key & key,std::size_t precalculated_hash)558 std::pair<const_iterator, const_iterator> equal_range(const Key& key, std::size_t precalculated_hash) const { 559 return m_ht.equal_range(key, precalculated_hash); 560 } 561 562 /** 563 * This overload only participates in the overload resolution if the typedef KeyEqual::is_transparent exists. 564 * If so, K must be hashable and comparable to Key. 565 */ 566 template<class K, class KE = KeyEqual, typename std::enable_if<has_is_transparent<KE>::value>::type* = nullptr> equal_range(const K & key)567 std::pair<iterator, iterator> equal_range(const K& key) { return m_ht.equal_range(key); } 568 569 570 /** 571 * @copydoc equal_range(const K& key) 572 * 573 * Use the hash value 'precalculated_hash' instead of hashing the key. The hash value should be the same 574 * as hash_function()(key). Usefull to speed-up the lookup if you already have the hash. 575 */ 576 template<class K, class KE = KeyEqual, typename std::enable_if<has_is_transparent<KE>::value>::type* = nullptr> equal_range(const K & key,std::size_t precalculated_hash)577 std::pair<iterator, iterator> equal_range(const K& key, std::size_t precalculated_hash) { 578 return m_ht.equal_range(key, precalculated_hash); 579 } 580 581 /** 582 * @copydoc equal_range(const K& key) 583 */ 584 template<class K, class KE = KeyEqual, typename std::enable_if<has_is_transparent<KE>::value>::type* = nullptr> equal_range(const K & key)585 std::pair<const_iterator, const_iterator> equal_range(const K& key) const { return m_ht.equal_range(key); } 586 587 /** 588 * @copydoc equal_range(const K& key, std::size_t precalculated_hash) 589 */ 590 template<class K, class KE = KeyEqual, typename std::enable_if<has_is_transparent<KE>::value>::type* = nullptr> equal_range(const K & key,std::size_t precalculated_hash)591 std::pair<const_iterator, const_iterator> equal_range(const K& key, std::size_t precalculated_hash) const { 592 return m_ht.equal_range(key, precalculated_hash); 593 } 594 595 596 597 598 /* 599 * Bucket interface 600 */ bucket_count()601 size_type bucket_count() const { return m_ht.bucket_count(); } max_bucket_count()602 size_type max_bucket_count() const { return m_ht.max_bucket_count(); } 603 604 605 /* 606 * Hash policy 607 */ load_factor()608 float load_factor() const { return m_ht.load_factor(); } max_load_factor()609 float max_load_factor() const { return m_ht.max_load_factor(); } max_load_factor(float ml)610 void max_load_factor(float ml) { m_ht.max_load_factor(ml); } 611 rehash(size_type count_)612 void rehash(size_type count_) { m_ht.rehash(count_); } reserve(size_type count_)613 void reserve(size_type count_) { m_ht.reserve(count_); } 614 615 616 /* 617 * Observers 618 */ hash_function()619 hasher hash_function() const { return m_ht.hash_function(); } key_eq()620 key_equal key_eq() const { return m_ht.key_eq(); } 621 622 /* 623 * Other 624 */ 625 626 /** 627 * Convert a const_iterator to an iterator. 628 */ mutable_iterator(const_iterator pos)629 iterator mutable_iterator(const_iterator pos) { 630 return m_ht.mutable_iterator(pos); 631 } 632 overflow_size()633 size_type overflow_size() const noexcept { return m_ht.overflow_size(); } 634 635 friend bool operator==(const hopscotch_map& lhs, const hopscotch_map& rhs) { 636 if(lhs.size() != rhs.size()) { 637 return false; 638 } 639 640 for(const auto& element_lhs : lhs) { 641 const auto it_element_rhs = rhs.find(element_lhs.first); 642 if(it_element_rhs == rhs.cend() || element_lhs.second != it_element_rhs->second) { 643 return false; 644 } 645 } 646 647 return true; 648 } 649 650 friend bool operator!=(const hopscotch_map& lhs, const hopscotch_map& rhs) { 651 return !operator==(lhs, rhs); 652 } 653 swap(hopscotch_map & lhs,hopscotch_map & rhs)654 friend void swap(hopscotch_map& lhs, hopscotch_map& rhs) { 655 lhs.swap(rhs); 656 } 657 658 659 660 private: 661 ht m_ht; 662 }; 663 664 665 /** 666 * Same as `tsl::hopscotch_map<Key, T, Hash, KeyEqual, Allocator, NeighborhoodSize, StoreHash, tsl::hh::prime_growth_policy>`. 667 */ 668 template<class Key, 669 class T, 670 class Hash = std::hash<Key>, 671 class KeyEqual = std::equal_to<Key>, 672 class Allocator = std::allocator<std::pair<Key, T>>, 673 unsigned int NeighborhoodSize = 62, 674 bool StoreHash = false> 675 using hopscotch_pg_map = hopscotch_map<Key, T, Hash, KeyEqual, Allocator, NeighborhoodSize, StoreHash, tsl::hh::prime_growth_policy>; 676 677 } // end namespace tsl 678 679 #endif 680