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 bucket_count_, const Hash &hash = Hash(),
117 const KeyEqual &equal = KeyEqual(), const Allocator &alloc = Allocator())
118 : m_ht(bucket_count_, hash, equal, alloc, ht::DEFAULT_MAX_LOAD_FACTOR)
119 {
120 }
121
122 robin_set(size_type bucket_count_, const Allocator &alloc)
123 : robin_set(bucket_count_, Hash(), KeyEqual(), alloc)
124 {
125 }
126
127 robin_set(size_type bucket_count_, const Hash &hash, const Allocator &alloc)
128 : robin_set(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, size_type bucket_count_ = ht::DEFAULT_INIT_BUCKETS_SIZE,
136 const Hash &hash = Hash(), const KeyEqual &equal = KeyEqual(),
137 const Allocator &alloc = Allocator())
138 : robin_set(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 bucket_count_, const Allocator &alloc)
145 : robin_set(first, last, bucket_count_, Hash(), KeyEqual(), alloc)
146 {
147 }
148
149 template <class InputIt>
150 robin_set(InputIt first, InputIt last, size_type bucket_count_, const Hash &hash,
151 const Allocator &alloc)
152 : robin_set(first, last, bucket_count_, hash, KeyEqual(), alloc)
153 {
154 }
155
156 robin_set(std::initializer_list<value_type> init,
157 size_type 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(), bucket_count_, hash, equal, alloc)
160 {
161 }
162
163 robin_set(std::initializer_list<value_type> init, size_type bucket_count_,
164 const Allocator &alloc)
165 : robin_set(init.begin(), init.end(), bucket_count_, Hash(), KeyEqual(), alloc)
166 {
167 }
168
169 robin_set(std::initializer_list<value_type> init, size_type bucket_count_, const Hash &hash,
170 const Allocator &alloc)
171 : robin_set(init.begin(), init.end(), 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, value);
217 }
218
219 iterator insert(const_iterator hint, value_type &&value)
220 {
221 return m_ht.insert(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 float max_load_factor() const { return m_ht.max_load_factor(); }
489 void max_load_factor(float ml) { m_ht.max_load_factor(ml); }
490
491 void rehash(size_type count_) { m_ht.rehash(count_); }
492 void reserve(size_type count_) { m_ht.reserve(count_); }
493
494 /*
495 * Observers
496 */
497 hasher hash_function() const { return m_ht.hash_function(); }
498 key_equal key_eq() const { return m_ht.key_eq(); }
499
500 /*
501 * Other
502 */
503
504 /**
505 * Convert a const_iterator to an iterator.
506 */
507 iterator mutable_iterator(const_iterator pos) { return m_ht.mutable_iterator(pos); }
508
509 friend bool operator==(const robin_set &lhs, const robin_set &rhs)
510 {
511 if (lhs.size() != rhs.size()) {
512 return false;
513 }
514
515 for (const auto &element_lhs : lhs) {
516 const auto it_element_rhs = rhs.find(element_lhs);
517 if (it_element_rhs == rhs.cend()) {
518 return false;
519 }
520 }
521
522 return true;
523 }
524
525 friend bool operator!=(const robin_set &lhs, const robin_set &rhs)
526 {
527 return !operator==(lhs, rhs);
528 }
529
530 friend void swap(robin_set &lhs, robin_set &rhs) { lhs.swap(rhs); }
531
532 private:
533 ht m_ht;
534 };
535
536 /**
537 * Same as `tsl::robin_set<Key, Hash, KeyEqual, Allocator, StoreHash,
538 * tsl::rh::prime_growth_policy>`.
539 */
540 template <class Key, class Hash = std::hash<Key>, class KeyEqual = std::equal_to<Key>,
541 class Allocator = std::allocator<Key>, bool StoreHash = false>
542 using robin_pg_set =
543 robin_set<Key, Hash, KeyEqual, Allocator, StoreHash, tsl::rh::prime_growth_policy>;
544
545 } // end namespace tsl
546
547 #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:886
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:323
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:593
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::robin_set::robin_set
robin_set(InputIt first, InputIt last, size_type bucket_count_, const Allocator &alloc)
Definition: robin_set.h:144
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:318
tsl::robin_set::mutable_iterator
iterator mutable_iterator(const_iterator pos)
Definition: robin_set.h:507
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:912
tsl::detail_robin_hash::robin_hash::max_bucket_count
size_type max_bucket_count() const
Definition: robin_hash.h:914
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:324
tsl::detail_robin_hash::robin_hash::insert
std::pair< iterator, bool > insert(P &&value)
Definition: robin_hash.h:621
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:922
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:316
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::robin_set
robin_set(size_type bucket_count_, const Allocator &alloc)
Definition: robin_set.h:122
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:317
tsl::robin_set< Face, FaceHash, FaceEqual >::pointer
typename ht::pointer pointer
Definition: robin_set.h:106
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:571
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:857
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:497
tsl::robin_set::robin_set
robin_set(size_type bucket_count_, const Hash &hash, const Allocator &alloc)
Definition: robin_set.h:127
tsl::detail_robin_hash::robin_hash::clear
void clear() noexcept
Definition: robin_hash.h:611
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:326
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:707
tsl::robin_set::robin_set
robin_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: robin_set.h:135
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:583
tsl::detail_robin_hash::robin_hash::size
size_type size() const noexcept
Definition: robin_hash.h:604
tsl::robin_set::max_load_factor
void max_load_factor(float ml)
Definition: robin_set.h:489
tsl::robin_set::swap
friend void swap(robin_set &lhs, robin_set &rhs)
Definition: robin_set.h:530
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:597
tsl::detail_robin_hash::robin_hash< Key, KeySelect, void, Hash, KeyEqual, Allocator, StoreHash, GrowthPolicy >::key_equal
KeyEqual key_equal
Definition: robin_hash.h:321
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(std::initializer_list< value_type > init, size_type bucket_count_, const Allocator &alloc)
Definition: robin_set.h:163
tsl::detail_robin_hash::robin_hash::mutable_iterator
iterator mutable_iterator(const_iterator pos)
Definition: robin_hash.h:960
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:498
tsl::robin_set::rehash
void rehash(size_type count_)
Definition: robin_set.h:491
tsl::detail_robin_hash::robin_hash::emplace_hint
iterator emplace_hint(const_iterator hint, Args &&... args)
Definition: robin_hash.h:680
tsl::detail_robin_hash::robin_hash::max_size
size_type max_size() const noexcept
Definition: robin_hash.h:606
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:328
tsl::detail_robin_hash::robin_hash::swap
void swap(robin_hash &other)
Definition: robin_hash.h:796
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:322
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(size_type bucket_count_, const Hash &hash=Hash(), const KeyEqual &equal=KeyEqual(), const Allocator &alloc=Allocator())
Definition: robin_set.h:116
tsl::detail_robin_hash::robin_hash::find
iterator find(const K &key)
Definition: robin_hash.h:869
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::detail_robin_hash::robin_hash::rehash
void rehash(size_type count_)
Definition: robin_hash.h:939
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::reserve
void reserve(size_type count_)
Definition: robin_set.h:492
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:955
tsl::robin_set::equal_range
std::pair< iterator, iterator > equal_range(const Key &key)
Definition: robin_set.h:406
tsl::robin_set::robin_set
robin_set(InputIt first, InputIt last, size_type bucket_count_, const Hash &hash, const Allocator &alloc)
Definition: robin_set.h:150
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:1204
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:320
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:509
tsl::detail_robin_hash::robin_hash::reserve
void reserve(size_type count_)
Definition: robin_hash.h:945
tsl::detail_robin_hash::robin_hash::hash_function
hasher hash_function() const
Definition: robin_hash.h:953
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:327
tsl::robin_set::erase
size_type erase(const K &key, std::size_t precalculated_hash)
Definition: robin_set.h:288
tsl::detail_robin_hash::robin_hash::emplace
std::pair< iterator, bool > emplace(Args &&... args)
Definition: robin_hash.h:675
tsl::robin_set::robin_set
robin_set(std::initializer_list< value_type > init, size_type bucket_count_, const Hash &hash, const Allocator &alloc)
Definition: robin_set.h:169
tsl::detail_robin_hash::robin_hash
Definition: robin_hash.h:302
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:525
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:319
tsl::detail_robin_hash::robin_hash::max_load_factor
float max_load_factor() const
Definition: robin_hash.h:931
tsl::robin_set::robin_set
robin_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: robin_set.h:156
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::empty
bool empty() const noexcept
Definition: robin_hash.h:602
tsl::robin_set::swap
void swap(robin_set &other)
Definition: robin_set.h:293
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:325
tsl::robin_set::m_ht
ht m_ht
Definition: robin_set.h:533
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:566
tsl::robin_set::max_load_factor
float max_load_factor() const
Definition: robin_set.h:488