IOSS 2.0

hopscotch_set.h
Go to the documentation of this file.
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_SET_H
25 #define TSL_HOPSCOTCH_SET_H
26
27 #include "hopscotch_hash.h"
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
37 namespace tsl {
38
39 /**
40 * Implementation of a hash set using the hopscotch hashing algorithm.
41 *
42 * The Key must be either nothrow move-constructible, copy-constuctible or both.
43 *
44 * The size of the neighborhood (NeighborhoodSize) must be > 0 and <= 62 if StoreHash is false.
45 * When StoreHash is true, 32-bits of the hash will be stored alongside the neighborhood limiting
46 * the NeighborhoodSize to <= 30. There is no memory usage difference between
47 * 'NeighborhoodSize 62; StoreHash false' and 'NeighborhoodSize 30; StoreHash true'.
48 *
49 * Storing the hash may improve performance on insert during the rehash process if the hash takes
50 * time to compute. It may also improve read performance if the KeyEqual function takes time (or
51 * incurs a cache-miss). If used with simple Hash and KeyEqual it may slow things down.
52 *
53 * StoreHash can only be set if the GrowthPolicy is set to tsl::power_of_two_growth_policy.
54 *
55 * GrowthPolicy defines how the set grows and consequently how a hash value is mapped to a bucket.
56 * By default the set uses tsl::power_of_two_growth_policy. This policy keeps the number of
57 * buckets to a power of two and uses a mask to set the hash to a bucket instead of the slow
58 * modulo. You may define your own growth policy, check tsl::power_of_two_growth_policy for the
59 * interface.
60 *
61 * If the destructor of Key throws an exception, behaviour of the class is undefined.
62 *
63 * Iterators invalidation:
64 * - clear, operator=, reserve, rehash: always invalidate the iterators.
65 * - insert, emplace, emplace_hint, operator[]: if there is an effective insert, invalidate the
66 * iterators if a displacement is needed to resolve a collision (which mean that most of the time,
67 * insert will invalidate the iterators). Or if there is a rehash.
68 * - erase: iterator on the erased element is the only one which become invalid.
69 */
70 template <class Key, class Hash = std::hash<Key>, class KeyEqual = std::equal_to<Key>,
71 class Allocator = std::allocator<Key>, unsigned int NeighborhoodSize = 62,
72 bool StoreHash = false, class GrowthPolicy = tsl::hh::power_of_two_growth_policy<2>>
73 class hopscotch_set
74 {
75 private:
76 template <typename U>
77 using has_is_transparent = tsl::detail_hopscotch_hash::has_is_transparent<U>;
78
79 class KeySelect
80 {
81 public:
82 using key_type = Key;
83
84 const key_type &operator()(const Key &key) const { return key; }
85
86 key_type &operator()(Key &key) { return key; }
87 };
88
89 using overflow_container_type = std::list<Key, Allocator>;
90 using ht = detail_hopscotch_hash::hopscotch_hash<Key, KeySelect, void, Hash, KeyEqual,
91 Allocator, NeighborhoodSize, StoreHash,
92 GrowthPolicy, overflow_container_type>;
93
94 public:
95 using key_type = typename ht::key_type;
96 using value_type = typename ht::value_type;
97 using size_type = typename ht::size_type;
98 using difference_type = typename ht::difference_type;
99 using hasher = typename ht::hasher;
100 using key_equal = typename ht::key_equal;
101 using allocator_type = typename ht::allocator_type;
102 using reference = typename ht::reference;
103 using const_reference = typename ht::const_reference;
104 using pointer = typename ht::pointer;
105 using const_pointer = typename ht::const_pointer;
106 using iterator = typename ht::iterator;
107 using const_iterator = typename ht::const_iterator;
108
109 /*
110 * Constructors
111 */
112 hopscotch_set() : hopscotch_set(ht::DEFAULT_INIT_BUCKETS_SIZE) {}
113
114 explicit hopscotch_set(size_type bucket_count, const Hash &hash = Hash(),
115 const KeyEqual &equal = KeyEqual(), const Allocator &alloc = Allocator())
116 : m_ht(bucket_count, hash, equal, alloc, ht::DEFAULT_MAX_LOAD_FACTOR)
117 {
118 }
119
120 hopscotch_set(size_type bucket_count, const Allocator &alloc)
121 : hopscotch_set(bucket_count, Hash(), KeyEqual(), alloc)
122 {
123 }
124
125 hopscotch_set(size_type bucket_count, const Hash &hash, const Allocator &alloc)
126 : hopscotch_set(bucket_count, hash, KeyEqual(), alloc)
127 {
128 }
129
130 explicit hopscotch_set(const Allocator &alloc)
131 : hopscotch_set(ht::DEFAULT_INIT_BUCKETS_SIZE, alloc)
132 {
133 }
134
135 template <class InputIt>
136 hopscotch_set(InputIt first, InputIt last,
137 size_type bucket_count = ht::DEFAULT_INIT_BUCKETS_SIZE, const Hash &hash = Hash(),
138 const KeyEqual &equal = KeyEqual(), const Allocator &alloc = Allocator())
139 : hopscotch_set(bucket_count, hash, equal, alloc)
140 {
141 insert(first, last);
142 }
143
144 template <class InputIt>
145 hopscotch_set(InputIt first, InputIt last, size_type bucket_count, const Allocator &alloc)
146 : hopscotch_set(first, last, bucket_count, Hash(), KeyEqual(), alloc)
147 {
148 }
149
150 template <class InputIt>
151 hopscotch_set(InputIt first, InputIt last, size_type bucket_count, const Hash &hash,
152 const Allocator &alloc)
153 : hopscotch_set(first, last, bucket_count, hash, KeyEqual(), alloc)
154 {
155 }
156
157 hopscotch_set(std::initializer_list<value_type> init,
158 size_type bucket_count = ht::DEFAULT_INIT_BUCKETS_SIZE, const Hash &hash = Hash(),
159 const KeyEqual &equal = KeyEqual(), const Allocator &alloc = Allocator())
160 : hopscotch_set(init.begin(), init.end(), bucket_count, hash, equal, alloc)
161 {
162 }
163
164 hopscotch_set(std::initializer_list<value_type> init, size_type bucket_count,
165 const Allocator &alloc)
166 : hopscotch_set(init.begin(), init.end(), bucket_count, Hash(), KeyEqual(), alloc)
167 {
168 }
169
170 hopscotch_set(std::initializer_list<value_type> init, size_type bucket_count, const Hash &hash,
171 const Allocator &alloc)
172 : hopscotch_set(init.begin(), init.end(), bucket_count, hash, KeyEqual(), alloc)
173 {
174 }
175
176 hopscotch_set &operator=(std::initializer_list<value_type> ilist)
177 {
178 m_ht.clear();
179
180 m_ht.reserve(ilist.size());
181 m_ht.insert(ilist.begin(), ilist.end());
182
183 return *this;
184 }
185
186 allocator_type get_allocator() const { return m_ht.get_allocator(); }
187
188 /*
189 * Iterators
190 */
191 iterator begin() noexcept { return m_ht.begin(); }
192 const_iterator begin() const noexcept { return m_ht.begin(); }
193 const_iterator cbegin() const noexcept { return m_ht.cbegin(); }
194
195 iterator end() noexcept { return m_ht.end(); }
196 const_iterator end() const noexcept { return m_ht.end(); }
197 const_iterator cend() const noexcept { return m_ht.cend(); }
198
199 /*
200 * Capacity
201 */
202 bool empty() const noexcept { return m_ht.empty(); }
203 size_type size() const noexcept { return m_ht.size(); }
204 size_type max_size() const noexcept { return m_ht.max_size(); }
205
206 /*
207 * Modifiers
208 */
209 void clear() noexcept { m_ht.clear(); }
210
211 std::pair<iterator, bool> insert(const value_type &value) { return m_ht.insert(value); }
212 std::pair<iterator, bool> insert(value_type &&value) { return m_ht.insert(std::move(value)); }
213
214 iterator insert(const_iterator hint, const value_type &value)
215 {
216 return m_ht.insert(hint, value);
217 }
218 iterator insert(const_iterator hint, value_type &&value)
219 {
220 return m_ht.insert(hint, std::move(value));
221 }
222
223 template <class InputIt> void insert(InputIt first, InputIt last) { m_ht.insert(first, last); }
224 void insert(std::initializer_list<value_type> ilist)
225 {
226 m_ht.insert(ilist.begin(), ilist.end());
227 }
228
229 /**
230 * Due to the way elements are stored, emplace will need to move or copy the key-value once.
231 * The method is equivalent to insert(value_type(std::forward<Args>(args)...));
232 *
233 * Mainly here for compatibility with the std::unordered_map interface.
234 */
235 template <class... Args> std::pair<iterator, bool> emplace(Args &&... args)
236 {
237 return m_ht.emplace(std::forward<Args>(args)...);
238 }
239
240 /**
241 * Due to the way elements are stored, emplace_hint will need to move or copy the key-value
242 * once. The method is equivalent to insert(hint, value_type(std::forward<Args>(args)...));
243 *
244 * Mainly here for compatibility with the std::unordered_map interface.
245 */
246 template <class... Args> iterator emplace_hint(const_iterator hint, Args &&... args)
247 {
248 return m_ht.emplace_hint(hint, std::forward<Args>(args)...);
249 }
250
251 iterator erase(iterator pos) { return m_ht.erase(pos); }
252 iterator erase(const_iterator pos) { return m_ht.erase(pos); }
253 iterator erase(const_iterator first, const_iterator last) { return m_ht.erase(first, last); }
254 size_type erase(const key_type &key) { return m_ht.erase(key); }
255
256 /**
257 * Use the hash value 'precalculated_hash' instead of hashing the key. The hash value should be
258 * the same as hash_function()(key). Usefull to speed-up the lookup to the value if you already
259 * have the hash.
260 */
261 size_type erase(const key_type &key, std::size_t precalculated_hash)
262 {
263 return m_ht.erase(key, precalculated_hash);
264 }
265
266 /**
267 * This overload only participates in the overload resolution if the typedef
268 * KeyEqual::is_transparent exists. If so, K must be hashable and comparable to Key.
269 */
270 template <class K, class KE = KeyEqual,
271 typename std::enable_if<has_is_transparent<KE>::value>::type * = nullptr>
272 size_type erase(const K &key)
273 {
274 return m_ht.erase(key);
275 }
276
277 /**
278 * @copydoc erase(const K& key)
279 *
280 * Use the hash value 'precalculated_hash' instead of hashing the key. The hash value should be
281 * the same as hash_function()(key). Usefull to speed-up the lookup to the value if you already
282 * have the hash.
283 */
284 template <class K, class KE = KeyEqual,
285 typename std::enable_if<has_is_transparent<KE>::value>::type * = nullptr>
286 size_type erase(const K &key, std::size_t precalculated_hash)
287 {
288 return m_ht.erase(key, precalculated_hash);
289 }
290
291 void swap(hopscotch_set &other) { other.m_ht.swap(m_ht); }
292
293 /*
294 * Lookup
295 */
296 size_type count(const Key &key) const { return m_ht.count(key); }
297
298 /**
299 * Use the hash value 'precalculated_hash' instead of hashing the key. The hash value should be
300 * the same as hash_function()(key). Usefull to speed-up the lookup if you already have the
301 * hash.
302 */
303 size_type count(const Key &key, std::size_t precalculated_hash) const
304 {
305 return m_ht.count(key, precalculated_hash);
306 }
307
308 /**
309 * This overload only participates in the overload resolution if the typedef
310 * KeyEqual::is_transparent exists. If so, K must be hashable and comparable to Key.
311 */
312 template <class K, class KE = KeyEqual,
313 typename std::enable_if<has_is_transparent<KE>::value>::type * = nullptr>
314 size_type count(const K &key) const
315 {
316 return m_ht.count(key);
317 }
318
319 /**
320 * @copydoc count(const K& key) const
321 *
322 * Use the hash value 'precalculated_hash' instead of hashing the key. The hash value should be
323 * the same as hash_function()(key). Usefull to speed-up the lookup if you already have the
324 * hash.
325 */
326 template <class K, class KE = KeyEqual,
327 typename std::enable_if<has_is_transparent<KE>::value>::type * = nullptr>
328 size_type count(const K &key, std::size_t precalculated_hash) const
329 {
330 return m_ht.count(key, precalculated_hash);
331 }
332
333 iterator find(const Key &key) { return m_ht.find(key); }
334
335 /**
336 * Use the hash value 'precalculated_hash' instead of hashing the key. The hash value should be
337 * the same as hash_function()(key). Usefull to speed-up the lookup if you already have the
338 * hash.
339 */
340 iterator find(const Key &key, std::size_t precalculated_hash)
341 {
342 return m_ht.find(key, precalculated_hash);
343 }
344
345 const_iterator find(const Key &key) const { return m_ht.find(key); }
346
347 /**
348 * @copydoc find(const Key& key, std::size_t precalculated_hash)
349 */
350 const_iterator find(const Key &key, std::size_t precalculated_hash) const
351 {
352 return m_ht.find(key, precalculated_hash);
353 }
354
355 /**
356 * This overload only participates in the overload resolution if the typedef
357 * KeyEqual::is_transparent exists. If so, K must be hashable and comparable to Key.
358 */
359 template <class K, class KE = KeyEqual,
360 typename std::enable_if<has_is_transparent<KE>::value>::type * = nullptr>
361 iterator find(const K &key)
362 {
363 return m_ht.find(key);
364 }
365
366 /**
367 * @copydoc find(const K& key)
368 *
369 * Use the hash value 'precalculated_hash' instead of hashing the key. The hash value should be
370 * the same as hash_function()(key). Usefull to speed-up the lookup if you already have the
371 * hash.
372 */
373 template <class K, class KE = KeyEqual,
374 typename std::enable_if<has_is_transparent<KE>::value>::type * = nullptr>
375 iterator find(const K &key, std::size_t precalculated_hash)
376 {
377 return m_ht.find(key, precalculated_hash);
378 }
379
380 /**
381 * @copydoc find(const K& key)
382 */
383 template <class K, class KE = KeyEqual,
384 typename std::enable_if<has_is_transparent<KE>::value>::type * = nullptr>
385 const_iterator find(const K &key) const
386 {
387 return m_ht.find(key);
388 }
389
390 /**
391 * @copydoc find(const K& key)
392 *
393 * Use the hash value 'precalculated_hash' instead of hashing the key. The hash value should be
394 * the same as hash_function()(key). Usefull to speed-up the lookup if you already have the
395 * hash.
396 */
397 template <class K, class KE = KeyEqual,
398 typename std::enable_if<has_is_transparent<KE>::value>::type * = nullptr>
399 const_iterator find(const K &key, std::size_t precalculated_hash) const
400 {
401 return m_ht.find(key, precalculated_hash);
402 }
403
404 bool contains(const Key &key) const { return m_ht.contains(key); }
405
406 /**
407 * Use the hash value 'precalculated_hash' instead of hashing the key. The hash value should be
408 * the same as hash_function()(key). Usefull to speed-up the lookup if you already have the
409 * hash.
410 */
411 bool contains(const Key &key, std::size_t precalculated_hash) const
412 {
413 return m_ht.contains(key, precalculated_hash);
414 }
415
416 /**
417 * This overload only participates in the overload resolution if the typedef
418 * KeyEqual::is_transparent exists. If so, K must be hashable and comparable to Key.
419 */
420 template <class K, class KE = KeyEqual,
421 typename std::enable_if<has_is_transparent<KE>::value>::type * = nullptr>
422 bool contains(const K &key) const
423 {
424 return m_ht.contains(key);
425 }
426
427 /**
428 * @copydoc contains(const K& key) const
429 *
430 * Use the hash value 'precalculated_hash' instead of hashing the key. The hash value should be
431 * the same as hash_function()(key). Usefull to speed-up the lookup if you already have the
432 * hash.
433 */
434 template <class K, class KE = KeyEqual,
435 typename std::enable_if<has_is_transparent<KE>::value>::type * = nullptr>
436 bool contains(const K &key, std::size_t precalculated_hash) const
437 {
438 return m_ht.contains(key, precalculated_hash);
439 }
440
441 std::pair<iterator, iterator> equal_range(const Key &key) { return m_ht.equal_range(key); }
442
443 /**
444 * Use the hash value 'precalculated_hash' instead of hashing the key. The hash value should be
445 * the same as hash_function()(key). Usefull to speed-up the lookup if you already have the
446 * hash.
447 */
448 std::pair<iterator, iterator> equal_range(const Key &key, std::size_t precalculated_hash)
449 {
450 return m_ht.equal_range(key, precalculated_hash);
451 }
452
453 std::pair<const_iterator, const_iterator> equal_range(const Key &key) const
454 {
455 return m_ht.equal_range(key);
456 }
457
458 /**
459 * @copydoc equal_range(const Key& key, std::size_t precalculated_hash)
460 */
461 std::pair<const_iterator, const_iterator> equal_range(const Key & key,
462 std::size_t precalculated_hash) const
463 {
464 return m_ht.equal_range(key, precalculated_hash);
465 }
466
467 /**
468 * This overload only participates in the overload resolution if the typedef
469 * KeyEqual::is_transparent exists. If so, K must be hashable and comparable to Key.
470 */
471 template <class K, class KE = KeyEqual,
472 typename std::enable_if<has_is_transparent<KE>::value>::type * = nullptr>
473 std::pair<iterator, iterator> equal_range(const K &key)
474 {
475 return m_ht.equal_range(key);
476 }
477
478 /**
479 * @copydoc equal_range(const K& key)
480 *
481 * Use the hash value 'precalculated_hash' instead of hashing the key. The hash value should be
482 * the same as hash_function()(key). Usefull to speed-up the lookup if you already have the
483 * hash.
484 */
485 template <class K, class KE = KeyEqual,
486 typename std::enable_if<has_is_transparent<KE>::value>::type * = nullptr>
487 std::pair<iterator, iterator> equal_range(const K &key, std::size_t precalculated_hash)
488 {
489 return m_ht.equal_range(key, precalculated_hash);
490 }
491
492 /**
493 * @copydoc equal_range(const K& key)
494 */
495 template <class K, class KE = KeyEqual,
496 typename std::enable_if<has_is_transparent<KE>::value>::type * = nullptr>
497 std::pair<const_iterator, const_iterator> equal_range(const K &key) const
498 {
499 return m_ht.equal_range(key);
500 }
501
502 /**
503 * @copydoc equal_range(const K& key, std::size_t precalculated_hash)
504 */
505 template <class K, class KE = KeyEqual,
506 typename std::enable_if<has_is_transparent<KE>::value>::type * = nullptr>
507 std::pair<const_iterator, const_iterator> equal_range(const K & key,
508 std::size_t precalculated_hash) const
509 {
510 return m_ht.equal_range(key, precalculated_hash);
511 }
512
513 /*
514 * Bucket interface
515 */
516 size_type bucket_count() const { return m_ht.bucket_count(); }
517 size_type max_bucket_count() const { return m_ht.max_bucket_count(); }
518
519 /*
520 * Hash policy
521 */
522 float load_factor() const { return m_ht.load_factor(); }
523 float max_load_factor() const { return m_ht.max_load_factor(); }
524 void max_load_factor(float ml) { m_ht.max_load_factor(ml); }
525
526 void rehash(size_type count_) { m_ht.rehash(count_); }
527 void reserve(size_type count_) { m_ht.reserve(count_); }
528
529 /*
530 * Observers
531 */
532 hasher hash_function() const { return m_ht.hash_function(); }
533 key_equal key_eq() const { return m_ht.key_eq(); }
534
535 /*
536 * Other
537 */
538
539 /**
540 * Convert a const_iterator to an iterator.
541 */
542 iterator mutable_iterator(const_iterator pos) { return m_ht.mutable_iterator(pos); }
543
544 size_type overflow_size() const noexcept { return m_ht.overflow_size(); }
545
546 friend bool operator==(const hopscotch_set &lhs, const hopscotch_set &rhs)
547 {
548 if (lhs.size() != rhs.size()) {
549 return false;
550 }
551
552 for (const auto &element_lhs : lhs) {
553 const auto it_element_rhs = rhs.find(element_lhs);
554 if (it_element_rhs == rhs.cend()) {
555 return false;
556 }
557 }
558
559 return true;
560 }
561
562 friend bool operator!=(const hopscotch_set &lhs, const hopscotch_set &rhs)
563 {
564 return !operator==(lhs, rhs);
565 }
566
567 friend void swap(hopscotch_set &lhs, hopscotch_set &rhs) { lhs.swap(rhs); }
568
569 private:
570 ht m_ht;
571 };
572
573 /**
574 * Same as `tsl::hopscotch_set<Key, Hash, KeyEqual, Allocator, NeighborhoodSize, StoreHash,
575 * tsl::hh::prime_growth_policy>`.
576 */
577 template <class Key, class Hash = std::hash<Key>, class KeyEqual = std::equal_to<Key>,
578 class Allocator = std::allocator<Key>, unsigned int NeighborhoodSize = 62,
579 bool StoreHash = false>
580 using hopscotch_pg_set = hopscotch_set<Key, Hash, KeyEqual, Allocator, NeighborhoodSize,
581 StoreHash, tsl::hh::prime_growth_policy>;
582
583 } // end namespace tsl
584
585 #endif
tsl::detail_hopscotch_hash::hopscotch_hash::equal_range
std::pair< iterator, iterator > equal_range(const K &key)
Definition: hopscotch_hash.h:1087
tsl::hopscotch_set::KeySelect
Definition: hopscotch_set.h:79
tsl::detail_hopscotch_hash::hopscotch_hash::max_load_factor
float max_load_factor() const
Definition: hopscotch_hash.h:1147
tsl::hopscotch_set::erase
iterator erase(iterator pos)
Definition: hopscotch_set.h:251
tsl
Definition: bhopscotch_map.h:37
tsl::hopscotch_set::find
const_iterator find(const Key &key) const
Definition: hopscotch_set.h:345
tsl::hopscotch_set::operator=
hopscotch_set & operator=(std::initializer_list< value_type > ilist)
Definition: hopscotch_set.h:176
tsl::hopscotch_set::insert
void insert(std::initializer_list< value_type > ilist)
Definition: hopscotch_set.h:224
tsl::hopscotch_set::const_reference
typename ht::const_reference const_reference
Definition: hopscotch_set.h:103
tsl::hopscotch_set::difference_type
typename ht::difference_type difference_type
Definition: hopscotch_set.h:98
tsl::detail_hopscotch_hash::hopscotch_hash< Key, KeySelect, void, Hash, KeyEqual, Allocator, NeighborhoodSize, StoreHash, GrowthPolicy, overflow_container_type >::reference
value_type & reference
Definition: hopscotch_hash.h:440
tsl::hopscotch_set::size
size_type size() const noexcept
Definition: hopscotch_set.h:203
tsl::hopscotch_set::hopscotch_set
hopscotch_set(std::initializer_list< value_type > init, size_type bucket_count, const Allocator &alloc)
Definition: hopscotch_set.h:164
tsl::hopscotch_set::equal_range
std::pair< iterator, iterator > equal_range(const Key &key, std::size_t precalculated_hash)
Definition: hopscotch_set.h:448
tsl::hopscotch_set::hasher
typename ht::hasher hasher
Definition: hopscotch_set.h:99
tsl::hopscotch_set::insert
iterator insert(const_iterator hint, value_type &&value)
Definition: hopscotch_set.h:218
tsl::hopscotch_set::contains
bool contains(const K &key) const
Definition: hopscotch_set.h:422
tsl::hopscotch_set::cbegin
const_iterator cbegin() const noexcept
Definition: hopscotch_set.h:193
tsl::detail_hopscotch_hash::hopscotch_hash::insert
std::pair< iterator, bool > insert(const value_type &value)
Definition: hopscotch_hash.h:786
tsl::detail_hopscotch_hash::hopscotch_hash::clear
void clear() noexcept
Definition: hopscotch_hash.h:776
tsl::detail_hopscotch_hash::hopscotch_hash::rehash
void rehash(size_type count_)
Definition: hopscotch_hash.h:1156
tsl::detail_hopscotch_hash::hopscotch_hash< Key, KeySelect, void, Hash, KeyEqual, Allocator, NeighborhoodSize, StoreHash, GrowthPolicy, overflow_container_type >::allocator_type
Allocator allocator_type
Definition: hopscotch_hash.h:439
anonymous_namespace{Ioss_SmartAssert.C}::init
struct anonymous_namespace{Ioss_SmartAssert.C}::assert_initializer init
tsl::hopscotch_set::KeySelect::operator()
const key_type & operator()(const Key &key) const
Definition: hopscotch_set.h:84
tsl::hopscotch_set::hopscotch_set
hopscotch_set(size_type bucket_count, const Hash &hash, const Allocator &alloc)
Definition: hopscotch_set.h:125
tsl::hopscotch_set::end
const_iterator end() const noexcept
Definition: hopscotch_set.h:196
tsl::hopscotch_set::equal_range
std::pair< const_iterator, const_iterator > equal_range(const K &key, std::size_t precalculated_hash) const
Definition: hopscotch_set.h:507
tsl::hopscotch_set::reference
typename ht::reference reference
Definition: hopscotch_set.h:102
tsl::hopscotch_set::overflow_size
size_type overflow_size() const noexcept
Definition: hopscotch_set.h:544
tsl::detail_hopscotch_hash::hopscotch_hash::get_allocator
allocator_type get_allocator() const
Definition: hopscotch_hash.h:724
tsl::detail_hopscotch_hash::hopscotch_hash< Key, KeySelect, void, Hash, KeyEqual, Allocator, NeighborhoodSize, StoreHash, GrowthPolicy, overflow_container_type >::const_reference
const value_type & const_reference
Definition: hopscotch_hash.h:441
tsl::detail_hopscotch_hash::hopscotch_hash< Key, KeySelect, void, Hash, KeyEqual, Allocator, NeighborhoodSize, StoreHash, GrowthPolicy, overflow_container_type >::hasher
Hash hasher
Definition: hopscotch_hash.h:437
tsl::hopscotch_set::find
iterator find(const K &key)
Definition: hopscotch_set.h:361
tsl::detail_hopscotch_hash::hopscotch_hash::overflow_size
size_type overflow_size() const noexcept
Definition: hopscotch_hash.h:1192
tsl::hopscotch_set::hopscotch_set
hopscotch_set(std::initializer_list< value_type > init, size_type bucket_count, const Hash &hash, const Allocator &alloc)
Definition: hopscotch_set.h:170
tsl::hopscotch_set::bucket_count
size_type bucket_count() const
Definition: hopscotch_set.h:516
tsl::hopscotch_set::count
size_type count(const K &key, std::size_t precalculated_hash) const
Definition: hopscotch_set.h:328
tsl::detail_hopscotch_hash::hopscotch_hash::contains
bool contains(const K &key) const
Definition: hopscotch_hash.h:1080
tsl::hopscotch_set::erase
size_type erase(const key_type &key)
Definition: hopscotch_set.h:254
tsl::detail_hopscotch_hash::hopscotch_hash< Key, KeySelect, void, Hash, KeyEqual, Allocator, NeighborhoodSize, StoreHash, GrowthPolicy, overflow_container_type >::key_type
typename KeySelect::key_type key_type
Definition: hopscotch_hash.h:433
tsl::hopscotch_set::max_size
size_type max_size() const noexcept
Definition: hopscotch_set.h:204
tsl::hopscotch_set::begin
const_iterator begin() const noexcept
Definition: hopscotch_set.h:192
tsl::hopscotch_set::max_bucket_count
size_type max_bucket_count() const
Definition: hopscotch_set.h:517
tsl::hopscotch_set::m_ht
ht m_ht
Definition: hopscotch_set.h:570
tsl::hopscotch_set::emplace_hint
iterator emplace_hint(const_iterator hint, Args &&... args)
Definition: hopscotch_set.h:246
tsl::hopscotch_set::mutable_iterator
iterator mutable_iterator(const_iterator pos)
Definition: hopscotch_set.h:542
tsl::detail_hopscotch_hash::hopscotch_hash::hash_function
hasher hash_function() const
Definition: hopscotch_hash.h:1170
tsl::detail_hopscotch_hash::hopscotch_hash::load_factor
float load_factor() const
Definition: hopscotch_hash.h:1138
tsl::detail_hopscotch_hash::hopscotch_hash::emplace
std::pair< iterator, bool > emplace(Args &&... args)
Definition: hopscotch_hash.h:876
tsl::hopscotch_set::insert
iterator insert(const_iterator hint, const value_type &value)
Definition: hopscotch_set.h:214
tsl::detail_hopscotch_hash::hopscotch_hash< Key, KeySelect, void, Hash, KeyEqual, Allocator, NeighborhoodSize, StoreHash, GrowthPolicy, overflow_container_type >::difference_type
std::ptrdiff_t difference_type
Definition: hopscotch_hash.h:436
tsl::detail_hopscotch_hash::hopscotch_hash< Key, KeySelect, void, Hash, KeyEqual, Allocator, NeighborhoodSize, StoreHash, GrowthPolicy, overflow_container_type >::DEFAULT_INIT_BUCKETS_SIZE
static const size_type DEFAULT_INIT_BUCKETS_SIZE
Definition: hopscotch_hash.h:1763
tsl::hopscotch_set::insert
std::pair< iterator, bool > insert(value_type &&value)
Definition: hopscotch_set.h:212
tsl::detail_hopscotch_hash::hopscotch_hash::max_size
size_type max_size() const noexcept
Definition: hopscotch_hash.h:771
tsl::detail_hopscotch_hash::hopscotch_hash< Key, KeySelect, void, Hash, KeyEqual, Allocator, NeighborhoodSize, StoreHash, GrowthPolicy, overflow_container_type >::value_type
Key value_type
Definition: hopscotch_hash.h:434
tsl::hopscotch_set::erase
size_type erase(const key_type &key, std::size_t precalculated_hash)
Definition: hopscotch_set.h:261
tsl::hopscotch_set::equal_range
std::pair< iterator, iterator > equal_range(const K &key, std::size_t precalculated_hash)
Definition: hopscotch_set.h:487
tsl::hopscotch_set::hopscotch_set
hopscotch_set(std::initializer_list< value_type > init, size_type bucket_count=ht::DEFAULT_INIT_BUCKETS_SIZE, const Hash &hash=Hash(), const KeyEqual &equal=KeyEqual(), const Allocator &alloc=Allocator())
Definition: hopscotch_set.h:157
tsl::hopscotch_set::max_load_factor
void max_load_factor(float ml)
Definition: hopscotch_set.h:524
tsl::hopscotch_set::hopscotch_set
hopscotch_set(const Allocator &alloc)
Definition: hopscotch_set.h:130
tsl::detail_hopscotch_hash::hopscotch_hash::end
iterator end() noexcept
Definition: hopscotch_hash.h:751
tsl::detail_hopscotch_hash::hopscotch_hash::size
size_type size() const noexcept
Definition: hopscotch_hash.h:769
tsl::hopscotch_set::const_pointer
typename ht::const_pointer const_pointer
Definition: hopscotch_set.h:105
tsl::hopscotch_set::allocator_type
typename ht::allocator_type allocator_type
Definition: hopscotch_set.h:101
tsl::detail_hopscotch_hash::hopscotch_hash< Key, KeySelect, void, Hash, KeyEqual, Allocator, NeighborhoodSize, StoreHash, GrowthPolicy, overflow_container_type >::key_equal
KeyEqual key_equal
Definition: hopscotch_hash.h:438
tsl::detail_hopscotch_hash::hopscotch_hash::reserve
void reserve(size_type count_)
Definition: hopscotch_hash.h:1162
tsl::detail_hopscotch_hash::hopscotch_hash< Key, KeySelect, void, Hash, KeyEqual, Allocator, NeighborhoodSize, StoreHash, GrowthPolicy, overflow_container_type >::size_type
std::size_t size_type
Definition: hopscotch_hash.h:435
tsl::hopscotch_set::find
const_iterator find(const K &key) const
Definition: hopscotch_set.h:385
tsl::hopscotch_set::contains
bool contains(const Key &key, std::size_t precalculated_hash) const
Definition: hopscotch_set.h:411
tsl::hopscotch_set::insert
std::pair< iterator, bool > insert(const value_type &value)
Definition: hopscotch_set.h:211
tsl::hopscotch_set::hash_function
hasher hash_function() const
Definition: hopscotch_set.h:532
tsl::hopscotch_set::swap
friend void swap(hopscotch_set &lhs, hopscotch_set &rhs)
Definition: hopscotch_set.h:567
tsl::detail_hopscotch_hash::hopscotch_hash< Key, KeySelect, void, Hash, KeyEqual, Allocator, NeighborhoodSize, StoreHash, GrowthPolicy, overflow_container_type >::const_iterator
hopscotch_iterator< true > const_iterator
Definition: hopscotch_hash.h:445
tsl::detail_hopscotch_hash::hopscotch_hash::begin
iterator begin() noexcept
Definition: hopscotch_hash.h:729
tsl::hopscotch_set::find
iterator find(const K &key, std::size_t precalculated_hash)
Definition: hopscotch_set.h:375
tsl::hopscotch_set::count
size_type count(const K &key) const
Definition: hopscotch_set.h:314
tsl::hopscotch_set::find
const_iterator find(const Key &key, std::size_t precalculated_hash) const
Definition: hopscotch_set.h:350
tsl::hopscotch_set::equal_range
std::pair< const_iterator, const_iterator > equal_range(const Key &key) const
Definition: hopscotch_set.h:453
tsl::hopscotch_set::find
iterator find(const Key &key, std::size_t precalculated_hash)
Definition: hopscotch_set.h:340
tsl::detail_hopscotch_hash::hopscotch_hash::erase
iterator erase(iterator pos)
Definition: hopscotch_hash.h:921
tsl::detail_hopscotch_hash::hopscotch_hash::find
iterator find(const K &key)
Definition: hopscotch_hash.h:1063
tsl::hopscotch_set
Definition: hopscotch_set.h:73
tsl::hopscotch_set::end
iterator end() noexcept
Definition: hopscotch_set.h:195
tsl::hopscotch_set::equal_range
std::pair< iterator, iterator > equal_range(const Key &key)
Definition: hopscotch_set.h:441
tsl::detail_hopscotch_hash::hopscotch_hash< Key, KeySelect, void, Hash, KeyEqual, Allocator, NeighborhoodSize, StoreHash, GrowthPolicy, overflow_container_type >::const_pointer
const value_type * const_pointer
Definition: hopscotch_hash.h:443
tsl::hopscotch_set::erase
iterator erase(const_iterator first, const_iterator last)
Definition: hopscotch_set.h:253
tsl::detail_hopscotch_hash::hopscotch_hash< Key, KeySelect, void, Hash, KeyEqual, Allocator, NeighborhoodSize, StoreHash, GrowthPolicy, overflow_container_type >::pointer
value_type * pointer
Definition: hopscotch_hash.h:442
tsl::hopscotch_set::erase
iterator erase(const_iterator pos)
Definition: hopscotch_set.h:252
tsl::hopscotch_set::count
size_type count(const Key &key) const
Definition: hopscotch_set.h:296
tsl::detail_hopscotch_hash::hopscotch_hash::emplace_hint
iterator emplace_hint(const_iterator hint, Args &&... args)
Definition: hopscotch_hash.h:881
tsl::detail_hopscotch_hash::hopscotch_hash::cbegin
const_iterator cbegin() const noexcept
Definition: hopscotch_hash.h:741
tsl::detail_hopscotch_hash::hopscotch_hash::key_eq
key_equal key_eq() const
Definition: hopscotch_hash.h:1172
tsl::hopscotch_set::operator==
friend bool operator==(const hopscotch_set &lhs, const hopscotch_set &rhs)
Definition: hopscotch_set.h:546
tsl::detail_hopscotch_hash::has_is_transparent
Definition: hopscotch_hash.h:69
tsl::detail_hopscotch_hash::hopscotch_hash< Key, KeySelect, void, Hash, KeyEqual, Allocator, NeighborhoodSize, StoreHash, GrowthPolicy, overflow_container_type >::iterator
hopscotch_iterator< false > iterator
Definition: hopscotch_hash.h:444
tsl::hopscotch_set::find
const_iterator find(const K &key, std::size_t precalculated_hash) const
Definition: hopscotch_set.h:399
tsl::hopscotch_set::erase
size_type erase(const K &key, std::size_t precalculated_hash)
Definition: hopscotch_set.h:286
tsl::hopscotch_set::get_allocator
allocator_type get_allocator() const
Definition: hopscotch_set.h:186
tsl::hopscotch_set::clear
void clear() noexcept
Definition: hopscotch_set.h:209
tsl::detail_hopscotch_hash::hopscotch_hash::swap
void swap(hopscotch_hash &other)
Definition: hopscotch_hash.h:980
tsl::hopscotch_set::KeySelect::operator()
key_type & operator()(Key &key)
Definition: hopscotch_set.h:86
tsl::hopscotch_set::hopscotch_set
hopscotch_set(size_type bucket_count, const Hash &hash=Hash(), const KeyEqual &equal=KeyEqual(), const Allocator &alloc=Allocator())
Definition: hopscotch_set.h:114
tsl::hopscotch_set::begin
iterator begin() noexcept
Definition: hopscotch_set.h:191
tsl::detail_hopscotch_hash::hopscotch_hash::empty
bool empty() const noexcept
Definition: hopscotch_hash.h:767
tsl::hopscotch_set::equal_range
std::pair< const_iterator, const_iterator > equal_range(const Key &key, std::size_t precalculated_hash) const
Definition: hopscotch_set.h:461
tsl::hopscotch_set::key_type
typename ht::key_type key_type
Definition: hopscotch_set.h:95
tsl::hopscotch_set::KeySelect::key_type
Key key_type
Definition: hopscotch_set.h:82
tsl::hopscotch_set::max_load_factor
float max_load_factor() const
Definition: hopscotch_set.h:523
tsl::detail_hopscotch_hash::hopscotch_hash::count
size_type count(const K &key) const
Definition: hopscotch_hash.h:1056
tsl::hopscotch_set::operator!=
friend bool operator!=(const hopscotch_set &lhs, const hopscotch_set &rhs)
Definition: hopscotch_set.h:562
tsl::hopscotch_set::equal_range
std::pair< const_iterator, const_iterator > equal_range(const K &key) const
Definition: hopscotch_set.h:497
tsl::hopscotch_set::erase
size_type erase(const K &key)
Definition: hopscotch_set.h:272
tsl::hopscotch_set::reserve
void reserve(size_type count_)
Definition: hopscotch_set.h:527
tsl::hopscotch_set::contains
bool contains(const K &key, std::size_t precalculated_hash) const
Definition: hopscotch_set.h:436
tsl::detail_hopscotch_hash::hopscotch_hash< Key, KeySelect, void, Hash, KeyEqual, Allocator, NeighborhoodSize, StoreHash, GrowthPolicy, overflow_container_type >
tsl::hopscotch_set::cend
const_iterator cend() const noexcept
Definition: hopscotch_set.h:197
tsl::hopscotch_set::hopscotch_set
hopscotch_set(InputIt first, InputIt last, size_type bucket_count=ht::DEFAULT_INIT_BUCKETS_SIZE, const Hash &hash=Hash(), const KeyEqual &equal=KeyEqual(), const Allocator &alloc=Allocator())
Definition: hopscotch_set.h:136
tsl::hopscotch_set::iterator
typename ht::iterator iterator
Definition: hopscotch_set.h:106
tsl::hopscotch_set::empty
bool empty() const noexcept
Definition: hopscotch_set.h:202
tsl::hopscotch_set::hopscotch_set
hopscotch_set()
Definition: hopscotch_set.h:112
tsl::hopscotch_set::key_eq
key_equal key_eq() const
Definition: hopscotch_set.h:533
tsl::hopscotch_set::count
size_type count(const Key &key, std::size_t precalculated_hash) const
Definition: hopscotch_set.h:303
tsl::detail_hopscotch_hash::hopscotch_hash::cend
const_iterator cend() const noexcept
Definition: hopscotch_hash.h:758
tsl::detail_hopscotch_hash::hopscotch_hash::max_bucket_count
size_type max_bucket_count() const
Definition: hopscotch_hash.h:1128
tsl::hopscotch_set::find
iterator find(const Key &key)
Definition: hopscotch_set.h:333
tsl::hopscotch_set::overflow_container_type
std::list< Key, Allocator > overflow_container_type
Definition: hopscotch_set.h:89
tsl::hopscotch_set::const_iterator
typename ht::const_iterator const_iterator
Definition: hopscotch_set.h:107
tsl::hopscotch_set::load_factor
float load_factor() const
Definition: hopscotch_set.h:522
hopscotch_hash.h
tsl::hopscotch_set::emplace
std::pair< iterator, bool > emplace(Args &&... args)
Definition: hopscotch_set.h:235
tsl::hopscotch_set::equal_range
std::pair< iterator, iterator > equal_range(const K &key)
Definition: hopscotch_set.h:473
tsl::hopscotch_set::hopscotch_set
hopscotch_set(InputIt first, InputIt last, size_type bucket_count, const Hash &hash, const Allocator &alloc)
Definition: hopscotch_set.h:151
tsl::hopscotch_set::insert
void insert(InputIt first, InputIt last)
Definition: hopscotch_set.h:223
tsl::hopscotch_set::pointer
typename ht::pointer pointer
Definition: hopscotch_set.h:104
tsl::hopscotch_set::contains
bool contains(const Key &key) const
Definition: hopscotch_set.h:404
tsl::hopscotch_set::value_type
typename ht::value_type value_type
Definition: hopscotch_set.h:96
tsl::hopscotch_set::rehash
void rehash(size_type count_)
Definition: hopscotch_set.h:526
tsl::hopscotch_set::hopscotch_set
hopscotch_set(size_type bucket_count, const Allocator &alloc)
Definition: hopscotch_set.h:120
tsl::detail_hopscotch_hash::hopscotch_hash::bucket_count
size_type bucket_count() const
Definition: hopscotch_hash.h:1114
tsl::detail_hopscotch_hash::hopscotch_hash::mutable_iterator
iterator mutable_iterator(const_iterator pos)
Definition: hopscotch_hash.h:1177
tsl::hopscotch_set::hopscotch_set
hopscotch_set(InputIt first, InputIt last, size_type bucket_count, const Allocator &alloc)
Definition: hopscotch_set.h:145
tsl::hopscotch_set::swap
void swap(hopscotch_set &other)
Definition: hopscotch_set.h:291
tsl::hopscotch_set::size_type
typename ht::size_type size_type
Definition: hopscotch_set.h:97
tsl::hh::prime_growth_policy
Definition: hopscotch_growth_policy.h:250
tsl::hopscotch_set::key_equal
typename ht::key_equal key_equal
Definition: hopscotch_set.h:100