IOSS 2.0

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