IOSS 2.0

robin_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_ROBIN_SET_H
25 #define TSL_ROBIN_SET_H
26
27 #include "robin_hash.h"
28 #include <cstddef>
29 #include <functional>
30 #include <initializer_list>
31 #include <memory>
32 #include <type_traits>
33 #include <utility>
34
35 namespace tsl {
36
37 /**
38 * Implementation of a hash set using open-adressing and the robin hood hashing algorithm with
39 * backward shift deletion.
40 *
41 * For operations modifying the hash set (insert, erase, rehash, ...), the strong exception
42 * guarantee is only guaranteed when the expression `std::is_nothrow_swappable<Key>\:\:value &&
43 * std::is_nothrow_move_constructible<Key>\:\:value` is true, otherwise if an exception
44 * is thrown during the swap or the move, the hash set may end up in a undefined state. Per the
45 * standard a `Key` with a noexcept copy constructor and no move constructor also satisfies the
46 * `std::is_nothrow_move_constructible<Key>\:\:value` criterion (and will thus guarantee the
47 * strong exception for the set).
48 *
49 * When `StoreHash` is true, 32 bits of the hash are stored alongside the values. It can improve
50 * the performance during lookups if the `KeyEqual` function takes time (or engenders a cache-miss
51 * for example) as we then compare the stored hashes before comparing the keys. When
52 * `tsl::rh::power_of_two_growth_policy` is used as `GrowthPolicy`, it may also speed-up the
53 * rehash process as we can avoid to recalculate the hash. When it is detected that storing the
54 * hash will not incur any memory penality due to alignement (i.e.
55 * `sizeof(tsl::detail_robin_hash::bucket_entry<ValueType, true>) ==
56 * sizeof(tsl::detail_robin_hash::bucket_entry<ValueType, false>)`) and
57 * `tsl::rh::power_of_two_growth_policy` is used, the hash will be stored even if `StoreHash` is
58 * false so that we can speed-up the rehash (but it will not be used on lookups unless `StoreHash`
59 * is true).
60 *
61 * `GrowthPolicy` defines how the set grows and consequently how a hash value is mapped to a
62 * bucket. By default the set uses `tsl::rh::power_of_two_growth_policy`. This policy keeps the
63 * number of buckets to a power of two and uses a mask to set the hash to a bucket instead of the
64 * slow modulo. Other growth policies are available and you may define your own growth policy,
65 * check `tsl::rh::power_of_two_growth_policy` for the interface.
66 *
67 * If the destructor of `Key` throws an exception, the behaviour of the class is undefined.
68 *
69 * Iterators invalidation:
70 * - clear, operator=, reserve, rehash: always invalidate the iterators.
71 * - insert, emplace, emplace_hint, operator[]: if there is an effective insert, invalidate the
72 * iterators.
73 * - erase: always invalidate the iterators.
74 */
75 template <class Key, class Hash = std::hash<Key>, class KeyEqual = std::equal_to<Key>,
76 class Allocator = std::allocator<Key>, bool StoreHash = false,
77 class GrowthPolicy = tsl::rh::power_of_two_growth_policy<2>>
78 class robin_set
79 {
80 private:
81 template <typename U> using has_is_transparent = tsl::detail_robin_hash::has_is_transparent<U>;
82
83 class KeySelect
84 {
85 public:
86 using key_type = Key;
87
88 const key_type &operator()(const Key &key) const noexcept { return key; }
89
90 key_type &operator()(Key &key) noexcept { return key; }
91 };
92
93 using ht = detail_robin_hash::robin_hash<Key, KeySelect, void, Hash, KeyEqual, Allocator,
94 StoreHash, GrowthPolicy>;
95
96 public:
97 using key_type = typename ht::key_type;
98 using value_type = typename ht::value_type;
99 using size_type = typename ht::size_type;
100 using difference_type = typename ht::difference_type;
101 using hasher = typename ht::hasher;
102 using key_equal = typename ht::key_equal;
103 using allocator_type = typename ht::allocator_type;
104 using reference = typename ht::reference;
105 using const_reference = typename ht::const_reference;
106 using pointer = typename ht::pointer;
107 using const_pointer = typename ht::const_pointer;
108 using iterator = typename ht::iterator;
109 using const_iterator = typename ht::const_iterator;
110
111 /*
112 * Constructors
113 */
114 robin_set() : robin_set(ht::DEFAULT_INIT_BUCKETS_SIZE) {}
115
116 explicit robin_set(size_type my_bucket_count, const Hash &hash = Hash(),
117 const KeyEqual &equal = KeyEqual(), const Allocator &alloc = Allocator())
118 : m_ht(my_bucket_count, hash, equal, alloc)
119 {
120 }
121
122 robin_set(size_type my_bucket_count, const Allocator &alloc)
123 : robin_set(my_bucket_count, Hash(), KeyEqual(), alloc)
124 {
125 }
126
127 robin_set(size_type my_bucket_count, const Hash &hash, const Allocator &alloc)
128 : robin_set(my_bucket_count, hash, KeyEqual(), alloc)
129 {
130 }
131
132 explicit robin_set(const Allocator &alloc) : robin_set(ht::DEFAULT_INIT_BUCKETS_SIZE, alloc) {}
133
134 template <class InputIt>
135 robin_set(InputIt first, InputIt last,
136 size_type my_bucket_count = ht::DEFAULT_INIT_BUCKETS_SIZE, const Hash &hash = Hash(),
137 const KeyEqual &equal = KeyEqual(), const Allocator &alloc = Allocator())
138 : robin_set(my_bucket_count, hash, equal, alloc)
139 {
140 insert(first, last);
141 }
142
143 template <class InputIt>
144 robin_set(InputIt first, InputIt last, size_type my_bucket_count, const Allocator &alloc)
145 : robin_set(first, last, my_bucket_count, Hash(), KeyEqual(), alloc)
146 {
147 }
148
149 template <class InputIt>
150 robin_set(InputIt first, InputIt last, size_type my_bucket_count, const Hash &hash,
151 const Allocator &alloc)
152 : robin_set(first, last, my_bucket_count, hash, KeyEqual(), alloc)
153 {
154 }
155
156 robin_set(std::initializer_list<value_type> init,
157 size_type my_bucket_count = ht::DEFAULT_INIT_BUCKETS_SIZE, const Hash &hash = Hash(),
158 const KeyEqual &equal = KeyEqual(), const Allocator &alloc = Allocator())
159 : robin_set(init.begin(), init.end(), my_bucket_count, hash, equal, alloc)
160 {
161 }
162
163 robin_set(std::initializer_list<value_type> init, size_type my_bucket_count,
164 const Allocator &alloc)
165 : robin_set(init.begin(), init.end(), my_bucket_count, Hash(), KeyEqual(), alloc)
166 {
167 }
168
169 robin_set(std::initializer_list<value_type> init, size_type my_bucket_count, const Hash &hash,
170 const Allocator &alloc)
171 : robin_set(init.begin(), init.end(), my_bucket_count, hash, KeyEqual(), alloc)
172 {
173 }
174
175 robin_set &operator=(std::initializer_list<value_type> ilist)
176 {
177 m_ht.clear();
178
179 m_ht.reserve(ilist.size());
180 m_ht.insert(ilist.begin(), ilist.end());
181
182 return *this;
183 }
184
185 allocator_type get_allocator() const { return m_ht.get_allocator(); }
186
187 /*
188 * Iterators
189 */
190 iterator begin() noexcept { return m_ht.begin(); }
191 const_iterator begin() const noexcept { return m_ht.begin(); }
192 const_iterator cbegin() const noexcept { return m_ht.cbegin(); }
193
194 iterator end() noexcept { return m_ht.end(); }
195 const_iterator end() const noexcept { return m_ht.end(); }
196 const_iterator cend() const noexcept { return m_ht.cend(); }
197
198 /*
199 * Capacity
200 */
201 bool empty() const noexcept { return m_ht.empty(); }
202 size_type size() const noexcept { return m_ht.size(); }
203 size_type max_size() const noexcept { return m_ht.max_size(); }
204
205 /*
206 * Modifiers
207 */
208 void clear() noexcept { m_ht.clear(); }
209
210 std::pair<iterator, bool> insert(const value_type &value) { return m_ht.insert(value); }
211
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(hint, value);
217 }
218
219 iterator insert(const_iterator hint, value_type &&value)
220 {
221 return m_ht.insert_hint(hint, std::move(value));
222 }
223
224 template <class InputIt> void insert(InputIt first, InputIt last) { m_ht.insert(first, last); }
225
226 void insert(std::initializer_list<value_type> ilist)
227 {
228 m_ht.insert(ilist.begin(), ilist.end());
229 }
230
231 /**
232 * Due to the way elements are stored, emplace will need to move or copy the key-value once.
233 * The method is equivalent to insert(value_type(std::forward<Args>(args)...));
234 *
235 * Mainly here for compatibility with the std::unordered_map interface.
236 */
237 template <class... Args> std::pair<iterator, bool> emplace(Args &&... args)
238 {
239 return m_ht.emplace(std::forward<Args>(args)...);
240 }
241
242 /**
243 * Due to the way elements are stored, emplace_hint will need to move or copy the key-value
244 * once. The method is equivalent to insert(hint, value_type(std::forward<Args>(args)...));
245 *
246 * Mainly here for compatibility with the std::unordered_map interface.
247 */
248 template <class... Args> iterator emplace_hint(const_iterator hint, Args &&... args)
249 {
250 return m_ht.emplace_hint(hint, std::forward<Args>(args)...);
251 }
252
253 iterator erase(iterator pos) { return m_ht.erase(pos); }
254 iterator erase(const_iterator pos) { return m_ht.erase(pos); }
255 iterator erase(const_iterator first, const_iterator last) { return m_ht.erase(first, last); }
256 size_type erase(const key_type &key) { return m_ht.erase(key); }
257
258 /**
259 * Use the hash value 'precalculated_hash' instead of hashing the key. The hash value should be
260 * the same as hash_function()(key). Usefull to speed-up the lookup to the value if you already
261 * have the hash.
262 */
263 size_type erase(const key_type &key, std::size_t precalculated_hash)
264 {
265 return m_ht.erase(key, precalculated_hash);
266 }
267
268 /**
269 * This overload only participates in the overload resolution if the typedef
270 * KeyEqual::is_transparent exists. If so, K must be hashable and comparable to Key.
271 */
272 template <class K, class KE = KeyEqual,
273 typename std::enable_if<has_is_transparent<KE>::value>::type * = nullptr>
274 size_type erase(const K &key)
275 {
276 return m_ht.erase(key);
277 }
278
279 /**
280 * @copydoc erase(const K& key)
281 *
282 * Use the hash value 'precalculated_hash' instead of hashing the key. The hash value should be
283 * the same as hash_function()(key). Usefull to speed-up the lookup to the value if you already
284 * have the hash.
285 */
286 template <class K, class KE = KeyEqual,
287 typename std::enable_if<has_is_transparent<KE>::value>::type * = nullptr>
288 size_type erase(const K &key, std::size_t precalculated_hash)
289 {
290 return m_ht.erase(key, precalculated_hash);
291 }
292
293 void swap(robin_set &other) { other.m_ht.swap(m_ht); }
294
295 /*
296 * Lookup
297 */
298 size_type count(const Key &key) const { return m_ht.count(key); }
299
300 /**
301 * Use the hash value 'precalculated_hash' instead of hashing the key. The hash value should be
302 * the same as hash_function()(key). Usefull to speed-up the lookup if you already have the
303 * hash.
304 */
305 size_type count(const Key &key, std::size_t precalculated_hash) const
306 {
307 return m_ht.count(key, precalculated_hash);
308 }
309
310 /**
311 * This overload only participates in the overload resolution if the typedef
312 * KeyEqual::is_transparent exists. If so, K must be hashable and comparable to Key.
313 */
314 template <class K, class KE = KeyEqual,
315 typename std::enable_if<has_is_transparent<KE>::value>::type * = nullptr>
316 size_type count(const K &key) const
317 {
318 return m_ht.count(key);
319 }
320
321 /**
322 * @copydoc count(const K& key) const
323 *
324 * Use the hash value 'precalculated_hash' instead of hashing the key. The hash value should be
325 * the same as hash_function()(key). Usefull to speed-up the lookup if you already have the
326 * hash.
327 */
328 template <class K, class KE = KeyEqual,
329 typename std::enable_if<has_is_transparent<KE>::value>::type * = nullptr>
330 size_type count(const K &key, std::size_t precalculated_hash) const
331 {
332 return m_ht.count(key, precalculated_hash);
333 }
334
335 iterator find(const Key &key) { return m_ht.find(key); }
336
337 /**
338 * Use the hash value 'precalculated_hash' instead of hashing the key. The hash value should be
339 * the same as hash_function()(key). Usefull to speed-up the lookup if you already have the
340 * hash.
341 */
342 iterator find(const Key &key, std::size_t precalculated_hash)
343 {
344 return m_ht.find(key, precalculated_hash);
345 }
346
347 const_iterator find(const Key &key) const { return m_ht.find(key); }
348
349 /**
350 * @copydoc find(const Key& key, std::size_t precalculated_hash)
351 */
352 const_iterator find(const Key &key, std::size_t precalculated_hash) const
353 {
354 return m_ht.find(key, precalculated_hash);
355 }
356
357 /**
358 * This overload only participates in the overload resolution if the typedef
359 * KeyEqual::is_transparent exists. If so, K must be hashable and comparable to Key.
360 */
361 template <class K, class KE = KeyEqual,
362 typename std::enable_if<has_is_transparent<KE>::value>::type * = nullptr>
363 iterator find(const K &key)
364 {
365 return m_ht.find(key);
366 }
367
368 /**
369 * @copydoc find(const K& key)
370 *
371 * Use the hash value 'precalculated_hash' instead of hashing the key. The hash value should be
372 * the same as hash_function()(key). Usefull to speed-up the lookup if you already have the
373 * hash.
374 */
375 template <class K, class KE = KeyEqual,
376 typename std::enable_if<has_is_transparent<KE>::value>::type * = nullptr>
377 iterator find(const K &key, std::size_t precalculated_hash)
378 {
379 return m_ht.find(key, precalculated_hash);
380 }
381
382 /**
383 * @copydoc find(const K& key)
384 */
385 template <class K, class KE = KeyEqual,
386 typename std::enable_if<has_is_transparent<KE>::value>::type * = nullptr>
387 const_iterator find(const K &key) const
388 {
389 return m_ht.find(key);
390 }
391
392 /**
393 * @copydoc find(const K& key)
394 *
395 * Use the hash value 'precalculated_hash' instead of hashing the key. The hash value should be
396 * the same as hash_function()(key). Usefull to speed-up the lookup if you already have the
397 * hash.
398 */
399 template <class K, class KE = KeyEqual,
400 typename std::enable_if<has_is_transparent<KE>::value>::type * = nullptr>
401 const_iterator find(const K &key, std::size_t precalculated_hash) const
402 {
403 return m_ht.find(key, precalculated_hash);
404 }
405
406 std::pair<iterator, iterator> equal_range(const Key &key) { return m_ht.equal_range(key); }
407
408 /**
409 * Use the hash value 'precalculated_hash' instead of hashing the key. The hash value should be
410 * the same as hash_function()(key). Usefull to speed-up the lookup if you already have the
411 * hash.
412 */
413 std::pair<iterator, iterator> equal_range(const Key &key, std::size_t precalculated_hash)
414 {
415 return m_ht.equal_range(key, precalculated_hash);
416 }
417
418 std::pair<const_iterator, const_iterator> equal_range(const Key &key) const
419 {
420 return m_ht.equal_range(key);
421 }
422
423 /**
424 * @copydoc equal_range(const Key& key, std::size_t precalculated_hash)
425 */
426 std::pair<const_iterator, const_iterator> equal_range(const Key & key,
427 std::size_t precalculated_hash) const
428 {
429 return m_ht.equal_range(key, precalculated_hash);
430 }
431
432 /**
433 * This overload only participates in the overload resolution if the typedef
434 * KeyEqual::is_transparent exists. If so, K must be hashable and comparable to Key.
435 */
436 template <class K, class KE = KeyEqual,
437 typename std::enable_if<has_is_transparent<KE>::value>::type * = nullptr>
438 std::pair<iterator, iterator> equal_range(const K &key)
439 {
440 return m_ht.equal_range(key);
441 }
442
443 /**
444 * @copydoc equal_range(const K& key)
445 *
446 * Use the hash value 'precalculated_hash' instead of hashing the key. The hash value should be
447 * the same as hash_function()(key). Usefull to speed-up the lookup if you already have the
448 * hash.
449 */
450 template <class K, class KE = KeyEqual,
451 typename std::enable_if<has_is_transparent<KE>::value>::type * = nullptr>
452 std::pair<iterator, iterator> equal_range(const K &key, std::size_t precalculated_hash)
453 {
454 return m_ht.equal_range(key, precalculated_hash);
455 }
456
457 /**
458 * @copydoc equal_range(const K& key)
459 */
460 template <class K, class KE = KeyEqual,
461 typename std::enable_if<has_is_transparent<KE>::value>::type * = nullptr>
462 std::pair<const_iterator, const_iterator> equal_range(const K &key) const
463 {
464 return m_ht.equal_range(key);
465 }
466
467 /**
468 * @copydoc equal_range(const K& key, std::size_t precalculated_hash)
469 */
470 template <class K, class KE = KeyEqual,
471 typename std::enable_if<has_is_transparent<KE>::value>::type * = nullptr>
472 std::pair<const_iterator, const_iterator> equal_range(const K & key,
473 std::size_t precalculated_hash) const
474 {
475 return m_ht.equal_range(key, precalculated_hash);
476 }
477
478 /*
479 * Bucket interface
480 */
481 size_type bucket_count() const { return m_ht.bucket_count(); }
482 size_type max_bucket_count() const { return m_ht.max_bucket_count(); }
483
484 /*
485 * Hash policy
486 */
487 float load_factor() const { return m_ht.load_factor(); }
488
489 float min_load_factor() const { return m_ht.min_load_factor(); }
490 float max_load_factor() const { return m_ht.max_load_factor(); }
491
492 /**
493 * Set the `min_load_factor` to `ml`. When the `load_factor` of the set goes
494 * below `min_load_factor` after some erase operations, the set will be
495 * shrunk when an insertion occurs. The erase method itself never shrinks
496 * the set.
497 *
498 * The default value of `min_load_factor` is 0.0f, the set never shrinks by default.
499 */
500 void min_load_factor(float ml) { m_ht.min_load_factor(ml); }
501 void max_load_factor(float ml) { m_ht.max_load_factor(ml); }
502
503 void rehash(size_type my_count) { m_ht.rehash(my_count); }
504 void reserve(size_type my_count) { m_ht.reserve(my_count); }
505
506 /*
507 * Observers
508 */
509 hasher hash_function() const { return m_ht.hash_function(); }
510 key_equal key_eq() const { return m_ht.key_eq(); }
511
512 /*
513 * Other
514 */
515
516 /**
517 * Convert a const_iterator to an iterator.
518 */
519 iterator mutable_iterator(const_iterator pos) { return m_ht.mutable_iterator(pos); }
520
521 friend bool operator==(const robin_set &lhs, const robin_set &rhs)
522 {
523 if (lhs.size() != rhs.size()) {
524 return false;
525 }
526
527 for (const auto &element_lhs : lhs) {
528 const auto it_element_rhs = rhs.find(element_lhs);
529 if (it_element_rhs == rhs.cend()) {
530 return false;
531 }
532 }
533
534 return true;
535 }
536
537 friend bool operator!=(const robin_set &lhs, const robin_set &rhs)
538 {
539 return !operator==(lhs, rhs);
540 }
541
542 friend void swap(robin_set &lhs, robin_set &rhs) { lhs.swap(rhs); }
543
544 private:
545 ht m_ht;
546 };
547
548 /**
549 * Same as `tsl::robin_set<Key, Hash, KeyEqual, Allocator, StoreHash,
550 * tsl::rh::prime_growth_policy>`.
551 */
552 template <class Key, class Hash = std::hash<Key>, class KeyEqual = std::equal_to<Key>,
553 class Allocator = std::allocator<Key>, bool StoreHash = false>
554 using robin_pg_set =
555 robin_set<Key, Hash, KeyEqual, Allocator, StoreHash, tsl::rh::prime_growth_policy>;
556
557 } // end namespace tsl
558
559 #endif
tsl::robin_set< Face, FaceHash, FaceEqual >::reference
typename ht::reference reference
Definition: robin_set.h:104
tsl::detail_robin_hash::robin_hash::equal_range
std::pair< iterator, iterator > equal_range(const K &key)
Definition: robin_hash.h:936
tsl::robin_set::KeySelect
Definition: robin_set.h:83
tsl::robin_set::find
const_iterator find(const Key &key) const
Definition: robin_set.h:347
tsl::detail_robin_hash::robin_hash< Key, KeySelect, void, Hash, KeyEqual, Allocator, StoreHash, GrowthPolicy >::reference
value_type & reference
Definition: robin_hash.h:329
tsl::robin_set::erase
size_type erase(const key_type &key, std::size_t precalculated_hash)
Definition: robin_set.h:263
tsl::detail_robin_hash::robin_hash::end
iterator end() noexcept
Definition: robin_hash.h:637
tsl::robin_set::count
size_type count(const K &key, std::size_t precalculated_hash) const
Definition: robin_set.h:330
tsl::robin_set::insert
std::pair< iterator, bool > insert(value_type &&value)
Definition: robin_set.h:212
tsl::detail_robin_hash::robin_hash< Key, KeySelect, void, Hash, KeyEqual, Allocator, StoreHash, GrowthPolicy >::size_type
std::size_t size_type
Definition: robin_hash.h:324
tsl::robin_set::mutable_iterator
iterator mutable_iterator(const_iterator pos)
Definition: robin_set.h:519
tsl::robin_set::begin
const_iterator begin() const noexcept
Definition: robin_set.h:191
tsl::robin_set::find
const_iterator find(const K &key, std::size_t precalculated_hash) const
Definition: robin_set.h:401
tsl::robin_set::find
iterator find(const K &key, std::size_t precalculated_hash)
Definition: robin_set.h:377
tsl::robin_set::insert
iterator insert(const_iterator hint, value_type &&value)
Definition: robin_set.h:219
tsl::detail_robin_hash::robin_hash::bucket_count
size_type bucket_count() const
Definition: robin_hash.h:962
tsl::robin_set::reserve
void reserve(size_type my_count)
Definition: robin_set.h:504
tsl::detail_robin_hash::robin_hash::max_bucket_count
size_type max_bucket_count() const
Definition: robin_hash.h:964
tsl::robin_set::end
iterator end() noexcept
Definition: robin_set.h:194
tsl::robin_set< Face, FaceHash, FaceEqual >::const_pointer
typename ht::const_pointer const_pointer
Definition: robin_set.h:107
tsl::detail_robin_hash::robin_hash< Key, KeySelect, void, Hash, KeyEqual, Allocator, StoreHash, GrowthPolicy >::const_reference
const value_type & const_reference
Definition: robin_hash.h:330
tsl::detail_robin_hash::robin_hash::insert
std::pair< iterator, bool > insert(P &&value)
Definition: robin_hash.h:665
tsl::robin_set::equal_range
std::pair< iterator, iterator > equal_range(const Key &key, std::size_t precalculated_hash)
Definition: robin_set.h:413
tsl::detail_robin_hash::robin_hash::load_factor
float load_factor() const
Definition: robin_hash.h:972
tsl::detail_robin_hash::robin_hash< Key, KeySelect, void, Hash, KeyEqual, Allocator, StoreHash, GrowthPolicy >::key_type
typename KeySelect::key_type key_type
Definition: robin_hash.h:322
tsl::robin_set::erase
size_type erase(const key_type &key)
Definition: robin_set.h:256
tsl::robin_set::insert
iterator insert(const_iterator hint, const value_type &value)
Definition: robin_set.h:214
tsl
Definition: hopscotch_growth_policy.h:37
tsl::robin_set< Face, FaceHash, FaceEqual >::const_reference
typename ht::const_reference const_reference
Definition: robin_set.h:105
tsl::robin_set::size
size_type size() const noexcept
Definition: robin_set.h:202
tsl::robin_set::emplace
std::pair< iterator, bool > emplace(Args &&... args)
Definition: robin_set.h:237
tsl::robin_set::emplace_hint
iterator emplace_hint(const_iterator hint, Args &&... args)
Definition: robin_set.h:248
tsl::robin_set::insert
std::pair< iterator, bool > insert(const value_type &value)
Definition: robin_set.h:210
tsl::detail_robin_hash::robin_hash< Key, KeySelect, void, Hash, KeyEqual, Allocator, StoreHash, GrowthPolicy >::value_type
Key value_type
Definition: robin_hash.h:323
tsl::robin_set< Face, FaceHash, FaceEqual >::pointer
typename ht::pointer pointer
Definition: robin_set.h:106
tsl::detail_robin_hash::robin_hash::insert_hint
iterator insert_hint(const_iterator hint, P &&value)
Definition: robin_hash.h:670
tsl::robin_set::KeySelect::key_type
Key key_type
Definition: robin_set.h:86
tsl::detail_robin_hash::robin_hash::begin
iterator begin() noexcept
Definition: robin_hash.h:615
tsl::robin_set< Face, FaceHash, FaceEqual >::difference_type
typename ht::difference_type difference_type
Definition: robin_set.h:100
tsl::detail_robin_hash::robin_hash::count
size_type count(const K &key) const
Definition: robin_hash.h:907
tsl::robin_set< Face, FaceHash, FaceEqual >::iterator
typename ht::iterator iterator
Definition: robin_set.h:108
tsl::robin_set::hash_function
hasher hash_function() const
Definition: robin_set.h:509
tsl::detail_robin_hash::robin_hash::clear
void clear() noexcept
Definition: robin_hash.h:655
tsl::detail_robin_hash::robin_hash< Key, KeySelect, void, Hash, KeyEqual, Allocator, StoreHash, GrowthPolicy >::const_pointer
const value_type * const_pointer
Definition: robin_hash.h:332
tsl::robin_set::robin_set
robin_set(InputIt first, InputIt last, size_type my_bucket_count, const Allocator &alloc)
Definition: robin_set.h:144
tsl::robin_set::robin_set
robin_set(size_type my_bucket_count, const Allocator &alloc)
Definition: robin_set.h:122
tsl::robin_set::bucket_count
size_type bucket_count() const
Definition: robin_set.h:481
robin_hash.h
tsl::robin_set::erase
iterator erase(const_iterator first, const_iterator last)
Definition: robin_set.h:255
tsl::detail_robin_hash::robin_hash::erase
iterator erase(iterator pos)
Definition: robin_hash.h:751
tsl::robin_set::cend
const_iterator cend() const noexcept
Definition: robin_set.h:196
tsl::detail_robin_hash::robin_hash::cbegin
const_iterator cbegin() const noexcept
Definition: robin_hash.h:627
tsl::detail_robin_hash::robin_hash::size
size_type size() const noexcept
Definition: robin_hash.h:648
tsl::robin_set::max_load_factor
void max_load_factor(float ml)
Definition: robin_set.h:501
tsl::robin_set::robin_set
robin_set(std::initializer_list< value_type > init, size_type my_bucket_count, const Allocator &alloc)
Definition: robin_set.h:163
tsl::robin_set::swap
friend void swap(robin_set &lhs, robin_set &rhs)
Definition: robin_set.h:542
tsl::robin_set::equal_range
std::pair< const_iterator, const_iterator > equal_range(const Key &key, std::size_t precalculated_hash) const
Definition: robin_set.h:426
tsl::detail_robin_hash::robin_hash::cend
const_iterator cend() const noexcept
Definition: robin_hash.h:641
tsl::detail_robin_hash::robin_hash< Key, KeySelect, void, Hash, KeyEqual, Allocator, StoreHash, GrowthPolicy >::key_equal
KeyEqual key_equal
Definition: robin_hash.h:327
tsl::robin_set::min_load_factor
float min_load_factor() const
Definition: robin_set.h:489
tsl::robin_set::erase
size_type erase(const K &key)
Definition: robin_set.h:274
tsl::robin_set::find
iterator find(const K &key)
Definition: robin_set.h:363
tsl::robin_set::erase
iterator erase(const_iterator pos)
Definition: robin_set.h:254
tsl::robin_set::robin_set
robin_set(InputIt first, InputIt last, size_type my_bucket_count=ht::DEFAULT_INIT_BUCKETS_SIZE, const Hash &hash=Hash(), const KeyEqual &equal=KeyEqual(), const Allocator &alloc=Allocator())
Definition: robin_set.h:135
tsl::detail_robin_hash::robin_hash::mutable_iterator
iterator mutable_iterator(const_iterator pos)
Definition: robin_hash.h:1019
tsl::robin_set::empty
bool empty() const noexcept
Definition: robin_set.h:201
tsl::robin_set::equal_range
std::pair< const_iterator, const_iterator > equal_range(const K &key, std::size_t precalculated_hash) const
Definition: robin_set.h:472
tsl::robin_set::equal_range
std::pair< iterator, iterator > equal_range(const K &key, std::size_t precalculated_hash)
Definition: robin_set.h:452
tsl::robin_set::key_eq
key_equal key_eq() const
Definition: robin_set.h:510
tsl::detail_robin_hash::robin_hash::emplace_hint
iterator emplace_hint(const_iterator hint, Args &&... args)
Definition: robin_hash.h:724
tsl::detail_robin_hash::robin_hash::max_size
size_type max_size() const noexcept
Definition: robin_hash.h:650
tsl::robin_set::robin_set
robin_set()
Definition: robin_set.h:114
tsl::detail_robin_hash::robin_hash< Key, KeySelect, void, Hash, KeyEqual, Allocator, StoreHash, GrowthPolicy >::const_iterator
robin_iterator< true > const_iterator
Definition: robin_hash.h:334
tsl::detail_robin_hash::robin_hash::swap
void swap(robin_hash &other)
Definition: robin_hash.h:844
tsl::robin_set::find
const_iterator find(const Key &key, std::size_t precalculated_hash) const
Definition: robin_set.h:352
tsl::robin_set::erase
iterator erase(iterator pos)
Definition: robin_set.h:253
tsl::robin_set::KeySelect::operator()
key_type & operator()(Key &key) noexcept
Definition: robin_set.h:90
tsl::robin_set< Face, FaceHash, FaceEqual >::size_type
typename ht::size_type size_type
Definition: robin_set.h:99
tsl::robin_set::find
const_iterator find(const K &key) const
Definition: robin_set.h:387
tsl::detail_robin_hash::robin_hash< Key, KeySelect, void, Hash, KeyEqual, Allocator, StoreHash, GrowthPolicy >::allocator_type
Allocator allocator_type
Definition: robin_hash.h:328
tsl::robin_set::robin_set
robin_set(const Allocator &alloc)
Definition: robin_set.h:132
tsl::robin_set< Face, FaceHash, FaceEqual >::key_equal
typename ht::key_equal key_equal
Definition: robin_set.h:102
tsl::robin_set::count
size_type count(const Key &key) const
Definition: robin_set.h:298
tsl::robin_set< Face, FaceHash, FaceEqual >::key_type
typename ht::key_type key_type
Definition: robin_set.h:97
tsl::robin_set::equal_range
std::pair< const_iterator, const_iterator > equal_range(const Key &key) const
Definition: robin_set.h:418
tsl::robin_set::robin_set
robin_set(std::initializer_list< value_type > init, size_type my_bucket_count, const Hash &hash, const Allocator &alloc)
Definition: robin_set.h:169
tsl::detail_robin_hash::robin_hash::find
iterator find(const K &key)
Definition: robin_hash.h:919
tsl::robin_set::count
size_type count(const K &key) const
Definition: robin_set.h:316
tsl::detail_robin_hash::has_is_transparent
Definition: robin_hash.h:52
tsl::robin_set::get_allocator
allocator_type get_allocator() const
Definition: robin_set.h:185
tsl::robin_set< Face, FaceHash, FaceEqual >::allocator_type
typename ht::allocator_type allocator_type
Definition: robin_set.h:103
tsl::robin_set::cbegin
const_iterator cbegin() const noexcept
Definition: robin_set.h:192
tsl::robin_set
Definition: robin_set.h:78
tsl::robin_set::min_load_factor
void min_load_factor(float ml)
Definition: robin_set.h:500
tsl::robin_set< Face, FaceHash, FaceEqual >::value_type
typename ht::value_type value_type
Definition: robin_set.h:98
tsl::robin_set::equal_range
std::pair< const_iterator, const_iterator > equal_range(const K &key) const
Definition: robin_set.h:462
tsl::robin_set::KeySelect::operator()
const key_type & operator()(const Key &key) const noexcept
Definition: robin_set.h:88
tsl::robin_set::operator=
robin_set & operator=(std::initializer_list< value_type > ilist)
Definition: robin_set.h:175
tsl::detail_robin_hash::robin_hash::key_eq
key_equal key_eq() const
Definition: robin_hash.h:1014
tsl::robin_set::equal_range
std::pair< iterator, iterator > equal_range(const Key &key)
Definition: robin_set.h:406
tsl::detail_robin_hash::robin_hash< Key, KeySelect, void, Hash, KeyEqual, Allocator, StoreHash, GrowthPolicy >::DEFAULT_INIT_BUCKETS_SIZE
static const size_type DEFAULT_INIT_BUCKETS_SIZE
Definition: robin_hash.h:1282
anonymous_namespace{Ioss_SmartAssert.C}::init
struct anonymous_namespace{Ioss_SmartAssert.C}::assert_initializer init
tsl::robin_set< Face, FaceHash, FaceEqual >::hasher
typename ht::hasher hasher
Definition: robin_set.h:101
tsl::detail_robin_hash::robin_hash< Key, KeySelect, void, Hash, KeyEqual, Allocator, StoreHash, GrowthPolicy >::hasher
Hash hasher
Definition: robin_hash.h:326
tsl::robin_set::count
size_type count(const Key &key, std::size_t precalculated_hash) const
Definition: robin_set.h:305
tsl::robin_set::operator==
friend bool operator==(const robin_set &lhs, const robin_set &rhs)
Definition: robin_set.h:521
tsl::detail_robin_hash::robin_hash::hash_function
hasher hash_function() const
Definition: robin_hash.h:1012
tsl::robin_set::max_bucket_count
size_type max_bucket_count() const
Definition: robin_set.h:482
tsl::detail_robin_hash::robin_hash< Key, KeySelect, void, Hash, KeyEqual, Allocator, StoreHash, GrowthPolicy >::iterator
robin_iterator< false > iterator
Definition: robin_hash.h:333
tsl::robin_set::erase
size_type erase(const K &key, std::size_t precalculated_hash)
Definition: robin_set.h:288
tsl::robin_set::robin_set
robin_set(size_type my_bucket_count, const Hash &hash, const Allocator &alloc)
Definition: robin_set.h:127
tsl::robin_set::robin_set
robin_set(InputIt first, InputIt last, size_type my_bucket_count, const Hash &hash, const Allocator &alloc)
Definition: robin_set.h:150
tsl::detail_robin_hash::robin_hash::emplace
std::pair< iterator, bool > emplace(Args &&... args)
Definition: robin_hash.h:719
tsl::detail_robin_hash::robin_hash
Definition: robin_hash.h:308
tsl::robin_set::load_factor
float load_factor() const
Definition: robin_set.h:487
tsl::robin_set::find
iterator find(const Key &key)
Definition: robin_set.h:335
tsl::robin_set::operator!=
friend bool operator!=(const robin_set &lhs, const robin_set &rhs)
Definition: robin_set.h:537
tsl::robin_set::clear
void clear() noexcept
Definition: robin_set.h:208
tsl::robin_set::end
const_iterator end() const noexcept
Definition: robin_set.h:195
tsl::robin_set::insert
void insert(std::initializer_list< value_type > ilist)
Definition: robin_set.h:226
tsl::robin_set::equal_range
std::pair< iterator, iterator > equal_range(const K &key)
Definition: robin_set.h:438
tsl::robin_set::find
iterator find(const Key &key, std::size_t precalculated_hash)
Definition: robin_set.h:342
tsl::robin_set::insert
void insert(InputIt first, InputIt last)
Definition: robin_set.h:224
tsl::detail_robin_hash::robin_hash< Key, KeySelect, void, Hash, KeyEqual, Allocator, StoreHash, GrowthPolicy >::difference_type
std::ptrdiff_t difference_type
Definition: robin_hash.h:325
tsl::detail_robin_hash::robin_hash::max_load_factor
float max_load_factor() const
Definition: robin_hash.h:983
tsl::robin_set::ht
detail_robin_hash::robin_hash< Key, KeySelect, void, Hash, KeyEqual, Allocator, StoreHash, GrowthPolicy > ht
Definition: robin_set.h:94
tsl::robin_set::max_size
size_type max_size() const noexcept
Definition: robin_set.h:203
tsl::detail_robin_hash::robin_hash::reserve
void reserve(size_type my_count)
Definition: robin_hash.h:1004
tsl::robin_set::rehash
void rehash(size_type my_count)
Definition: robin_set.h:503
tsl::detail_robin_hash::robin_hash::min_load_factor
float min_load_factor() const
Definition: robin_hash.h:981
tsl::detail_robin_hash::robin_hash::empty
bool empty() const noexcept
Definition: robin_hash.h:646
tsl::robin_set::swap
void swap(robin_set &other)
Definition: robin_set.h:293
tsl::robin_set::robin_set
robin_set(size_type my_bucket_count, const Hash &hash=Hash(), const KeyEqual &equal=KeyEqual(), const Allocator &alloc=Allocator())
Definition: robin_set.h:116
tsl::robin_set::begin
iterator begin() noexcept
Definition: robin_set.h:190
tsl::detail_robin_hash::robin_hash< Key, KeySelect, void, Hash, KeyEqual, Allocator, StoreHash, GrowthPolicy >::pointer
value_type * pointer
Definition: robin_hash.h:331
tsl::robin_set::m_ht
ht m_ht
Definition: robin_set.h:545
tsl::robin_set< Face, FaceHash, FaceEqual >::const_iterator
typename ht::const_iterator const_iterator
Definition: robin_set.h:109
tsl::detail_robin_hash::robin_hash::get_allocator
allocator_type get_allocator() const
Definition: robin_hash.h:610
tsl::detail_robin_hash::robin_hash::rehash
void rehash(size_type my_count)
Definition: robin_hash.h:998
tsl::robin_set::robin_set
robin_set(std::initializer_list< value_type > init, size_type my_bucket_count=ht::DEFAULT_INIT_BUCKETS_SIZE, const Hash &hash=Hash(), const KeyEqual &equal=KeyEqual(), const Allocator &alloc=Allocator())
Definition: robin_set.h:156
tsl::robin_set::max_load_factor
float max_load_factor() const
Definition: robin_set.h:490