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 * `Key` must be swappable.
68 *
69 * `Key` must be copy and/or move constructible.
70 *
71 * If the destructor of `Key` throws an exception, the behaviour of the class is undefined.
72 *
73 * Iterators invalidation:
74 * - clear, operator=, reserve, rehash: always invalidate the iterators.
75 * - insert, emplace, emplace_hint, operator[]: if there is an effective insert, invalidate the
76 * iterators.
77 * - erase: always invalidate the iterators.
78 */
79 template <class Key, class Hash = std::hash<Key>, class KeyEqual = std::equal_to<Key>,
80 class Allocator = std::allocator<Key>, bool StoreHash = false,
81 class GrowthPolicy = tsl::rh::power_of_two_growth_policy<2>>
82 class robin_set
83 {
84 private:
85 template <typename U> using has_is_transparent = tsl::detail_robin_hash::has_is_transparent<U>;
86
87 class KeySelect
88 {
89 public:
90 using key_type = Key;
91
92 const key_type &operator()(const Key &key) const noexcept { return key; }
93
94 key_type &operator()(Key &key) noexcept { return key; }
95 };
96
97 using ht = detail_robin_hash::robin_hash<Key, KeySelect, void, Hash, KeyEqual, Allocator,
98 StoreHash, GrowthPolicy>;
99
100 public:
101 using key_type = typename ht::key_type;
102 using value_type = typename ht::value_type;
103 using size_type = typename ht::size_type;
104 using difference_type = typename ht::difference_type;
105 using hasher = typename ht::hasher;
106 using key_equal = typename ht::key_equal;
107 using allocator_type = typename ht::allocator_type;
108 using reference = typename ht::reference;
109 using const_reference = typename ht::const_reference;
110 using pointer = typename ht::pointer;
111 using const_pointer = typename ht::const_pointer;
112 using iterator = typename ht::iterator;
113 using const_iterator = typename ht::const_iterator;
114
115 /*
116 * Constructors
117 */
118 robin_set() : robin_set(ht::DEFAULT_INIT_BUCKETS_SIZE) {}
119
120 explicit robin_set(size_type my_bucket_count, const Hash &hash = Hash(),
121 const KeyEqual &equal = KeyEqual(), const Allocator &alloc = Allocator())
122 : m_ht(my_bucket_count, hash, equal, alloc)
123 {
124 }
125
126 robin_set(size_type my_bucket_count, const Allocator &alloc)
127 : robin_set(my_bucket_count, Hash(), KeyEqual(), alloc)
128 {
129 }
130
131 robin_set(size_type my_bucket_count, const Hash &hash, const Allocator &alloc)
132 : robin_set(my_bucket_count, hash, KeyEqual(), alloc)
133 {
134 }
135
136 explicit robin_set(const Allocator &alloc) : robin_set(ht::DEFAULT_INIT_BUCKETS_SIZE, alloc) {}
137
138 template <class InputIt>
139 robin_set(InputIt first, InputIt last, size_type my_bucket_count = ht::DEFAULT_INIT_BUCKETS_SIZE,
140 const Hash &hash = Hash(), const KeyEqual &equal = KeyEqual(),
141 const Allocator &alloc = Allocator())
142 : robin_set(my_bucket_count, hash, equal, alloc)
143 {
144 insert(first, last);
145 }
146
147 template <class InputIt>
148 robin_set(InputIt first, InputIt last, size_type my_bucket_count, const Allocator &alloc)
149 : robin_set(first, last, my_bucket_count, Hash(), KeyEqual(), alloc)
150 {
151 }
152
153 template <class InputIt>
154 robin_set(InputIt first, InputIt last, size_type my_bucket_count, const Hash &hash,
155 const Allocator &alloc)
156 : robin_set(first, last, my_bucket_count, hash, KeyEqual(), alloc)
157 {
158 }
159
160 robin_set(std::initializer_list<value_type> init,
161 size_type my_bucket_count = ht::DEFAULT_INIT_BUCKETS_SIZE, const Hash &hash = Hash(),
162 const KeyEqual &equal = KeyEqual(), const Allocator &alloc = Allocator())
163 : robin_set(init.begin(), init.end(), my_bucket_count, hash, equal, alloc)
164 {
165 }
166
167 robin_set(std::initializer_list<value_type> init, size_type my_bucket_count,
168 const Allocator &alloc)
169 : robin_set(init.begin(), init.end(), my_bucket_count, Hash(), KeyEqual(), alloc)
170 {
171 }
172
173 robin_set(std::initializer_list<value_type> init, size_type my_bucket_count, const Hash &hash,
174 const Allocator &alloc)
175 : robin_set(init.begin(), init.end(), my_bucket_count, hash, KeyEqual(), alloc)
176 {
177 }
178
179 robin_set &operator=(std::initializer_list<value_type> ilist)
180 {
181 m_ht.clear();
182
183 m_ht.reserve(ilist.size());
184 m_ht.insert(ilist.begin(), ilist.end());
185
186 return *this;
187 }
188
189 allocator_type get_allocator() const { return m_ht.get_allocator(); }
190
191 /*
192 * Iterators
193 */
194 iterator begin() noexcept { return m_ht.begin(); }
195 const_iterator begin() const noexcept { return m_ht.begin(); }
196 const_iterator cbegin() const noexcept { return m_ht.cbegin(); }
197
198 iterator end() noexcept { return m_ht.end(); }
199 const_iterator end() const noexcept { return m_ht.end(); }
200 const_iterator cend() const noexcept { return m_ht.cend(); }
201
202 /*
203 * Capacity
204 */
205 bool empty() const noexcept { return m_ht.empty(); }
206 size_type size() const noexcept { return m_ht.size(); }
207 size_type max_size() const noexcept { return m_ht.max_size(); }
208
209 /*
210 * Modifiers
211 */
212 void clear() noexcept { m_ht.clear(); }
213
214 std::pair<iterator, bool> insert(const value_type &value) { return m_ht.insert(value); }
215
216 std::pair<iterator, bool> insert(value_type &&value) { return m_ht.insert(std::move(value)); }
217
218 iterator insert(const_iterator hint, const value_type &value)
219 {
220 return m_ht.insert_hint(hint, value);
221 }
222
223 iterator insert(const_iterator hint, value_type &&value)
224 {
225 return m_ht.insert_hint(hint, std::move(value));
226 }
227
228 template <class InputIt> void insert(InputIt first, InputIt last) { m_ht.insert(first, last); }
229
230 void insert(std::initializer_list<value_type> ilist)
231 {
232 m_ht.insert(ilist.begin(), ilist.end());
233 }
234
235 /**
236 * Due to the way elements are stored, emplace will need to move or copy the key-value once.
237 * The method is equivalent to insert(value_type(std::forward<Args>(args)...));
238 *
239 * Mainly here for compatibility with the std::unordered_map interface.
240 */
241 template <class... Args> std::pair<iterator, bool> emplace(Args &&... args)
242 {
243 return m_ht.emplace(std::forward<Args>(args)...);
244 }
245
246 /**
247 * Due to the way elements are stored, emplace_hint will need to move or copy the key-value
248 * once. The method is equivalent to insert(hint, value_type(std::forward<Args>(args)...));
249 *
250 * Mainly here for compatibility with the std::unordered_map interface.
251 */
252 template <class... Args> iterator emplace_hint(const_iterator hint, Args &&... args)
253 {
254 return m_ht.emplace_hint(hint, std::forward<Args>(args)...);
255 }
256
257 iterator erase(iterator pos) { return m_ht.erase(pos); }
258 iterator erase(const_iterator pos) { return m_ht.erase(pos); }
259 iterator erase(const_iterator first, const_iterator last) { return m_ht.erase(first, last); }
260 size_type erase(const key_type &key) { return m_ht.erase(key); }
261
262 /**
263 * Use the hash value 'precalculated_hash' instead of hashing the key. The hash value should be
264 * the same as hash_function()(key). Usefull to speed-up the lookup to the value if you already
265 * have the hash.
266 */
267 size_type erase(const key_type &key, std::size_t precalculated_hash)
268 {
269 return m_ht.erase(key, precalculated_hash);
270 }
271
272 /**
273 * This overload only participates in the overload resolution if the typedef
274 * KeyEqual::is_transparent exists. If so, K must be hashable and comparable to Key.
275 */
276 template <class K, class KE = KeyEqual,
277 typename std::enable_if<has_is_transparent<KE>::value>::type * = nullptr>
278 size_type erase(const K &key)
279 {
280 return m_ht.erase(key);
281 }
282
283 /**
284 * @copydoc erase(const K& key)
285 *
286 * Use the hash value 'precalculated_hash' instead of hashing the key. The hash value should be
287 * the same as hash_function()(key). Usefull to speed-up the lookup to the value if you already
288 * have the hash.
289 */
290 template <class K, class KE = KeyEqual,
291 typename std::enable_if<has_is_transparent<KE>::value>::type * = nullptr>
292 size_type erase(const K &key, std::size_t precalculated_hash)
293 {
294 return m_ht.erase(key, precalculated_hash);
295 }
296
297 void swap(robin_set &other) { other.m_ht.swap(m_ht); }
298
299 /*
300 * Lookup
301 */
302 size_type count(const Key &key) const { return m_ht.count(key); }
303
304 /**
305 * Use the hash value 'precalculated_hash' instead of hashing the key. The hash value should be
306 * the same as hash_function()(key). Usefull to speed-up the lookup if you already have the
307 * hash.
308 */
309 size_type count(const Key &key, std::size_t precalculated_hash) const
310 {
311 return m_ht.count(key, precalculated_hash);
312 }
313
314 /**
315 * This overload only participates in the overload resolution if the typedef
316 * KeyEqual::is_transparent exists. If so, K must be hashable and comparable to Key.
317 */
318 template <class K, class KE = KeyEqual,
319 typename std::enable_if<has_is_transparent<KE>::value>::type * = nullptr>
320 size_type count(const K &key) const
321 {
322 return m_ht.count(key);
323 }
324
325 /**
326 * @copydoc count(const K& key) const
327 *
328 * Use the hash value 'precalculated_hash' instead of hashing the key. The hash value should be
329 * the same as hash_function()(key). Usefull to speed-up the lookup if you already have the
330 * hash.
331 */
332 template <class K, class KE = KeyEqual,
333 typename std::enable_if<has_is_transparent<KE>::value>::type * = nullptr>
334 size_type count(const K &key, std::size_t precalculated_hash) const
335 {
336 return m_ht.count(key, precalculated_hash);
337 }
338
339 iterator find(const Key &key) { return m_ht.find(key); }
340
341 /**
342 * Use the hash value 'precalculated_hash' instead of hashing the key. The hash value should be
343 * the same as hash_function()(key). Usefull to speed-up the lookup if you already have the
344 * hash.
345 */
346 iterator find(const Key &key, std::size_t precalculated_hash)
347 {
348 return m_ht.find(key, precalculated_hash);
349 }
350
351 const_iterator find(const Key &key) const { return m_ht.find(key); }
352
353 /**
354 * @copydoc find(const Key& key, std::size_t precalculated_hash)
355 */
356 const_iterator find(const Key &key, std::size_t precalculated_hash) const
357 {
358 return m_ht.find(key, precalculated_hash);
359 }
360
361 /**
362 * This overload only participates in the overload resolution if the typedef
363 * KeyEqual::is_transparent exists. If so, K must be hashable and comparable to Key.
364 */
365 template <class K, class KE = KeyEqual,
366 typename std::enable_if<has_is_transparent<KE>::value>::type * = nullptr>
367 iterator find(const K &key)
368 {
369 return m_ht.find(key);
370 }
371
372 /**
373 * @copydoc find(const K& key)
374 *
375 * Use the hash value 'precalculated_hash' instead of hashing the key. The hash value should be
376 * the same as hash_function()(key). Usefull to speed-up the lookup if you already have the
377 * hash.
378 */
379 template <class K, class KE = KeyEqual,
380 typename std::enable_if<has_is_transparent<KE>::value>::type * = nullptr>
381 iterator find(const K &key, std::size_t precalculated_hash)
382 {
383 return m_ht.find(key, precalculated_hash);
384 }
385
386 /**
387 * @copydoc find(const K& key)
388 */
389 template <class K, class KE = KeyEqual,
390 typename std::enable_if<has_is_transparent<KE>::value>::type * = nullptr>
391 const_iterator find(const K &key) const
392 {
393 return m_ht.find(key);
394 }
395
396 /**
397 * @copydoc find(const K& key)
398 *
399 * Use the hash value 'precalculated_hash' instead of hashing the key. The hash value should be
400 * the same as hash_function()(key). Usefull to speed-up the lookup if you already have the
401 * hash.
402 */
403 template <class K, class KE = KeyEqual,
404 typename std::enable_if<has_is_transparent<KE>::value>::type * = nullptr>
405 const_iterator find(const K &key, std::size_t precalculated_hash) const
406 {
407 return m_ht.find(key, precalculated_hash);
408 }
409
410 std::pair<iterator, iterator> equal_range(const Key &key) { return m_ht.equal_range(key); }
411
412 /**
413 * Use the hash value 'precalculated_hash' instead of hashing the key. The hash value should be
414 * the same as hash_function()(key). Usefull to speed-up the lookup if you already have the
415 * hash.
416 */
417 std::pair<iterator, iterator> equal_range(const Key &key, std::size_t precalculated_hash)
418 {
419 return m_ht.equal_range(key, precalculated_hash);
420 }
421
422 std::pair<const_iterator, const_iterator> equal_range(const Key &key) const
423 {
424 return m_ht.equal_range(key);
425 }
426
427 /**
428 * @copydoc equal_range(const Key& key, std::size_t precalculated_hash)
429 */
430 std::pair<const_iterator, const_iterator> equal_range(const Key & key,
431 std::size_t precalculated_hash) const
432 {
433 return m_ht.equal_range(key, precalculated_hash);
434 }
435
436 /**
437 * This overload only participates in the overload resolution if the typedef
438 * KeyEqual::is_transparent exists. If so, K must be hashable and comparable to Key.
439 */
440 template <class K, class KE = KeyEqual,
441 typename std::enable_if<has_is_transparent<KE>::value>::type * = nullptr>
442 std::pair<iterator, iterator> equal_range(const K &key)
443 {
444 return m_ht.equal_range(key);
445 }
446
447 /**
448 * @copydoc equal_range(const K& key)
449 *
450 * Use the hash value 'precalculated_hash' instead of hashing the key. The hash value should be
451 * the same as hash_function()(key). Usefull to speed-up the lookup if you already have the
452 * hash.
453 */
454 template <class K, class KE = KeyEqual,
455 typename std::enable_if<has_is_transparent<KE>::value>::type * = nullptr>
456 std::pair<iterator, iterator> equal_range(const K &key, std::size_t precalculated_hash)
457 {
458 return m_ht.equal_range(key, precalculated_hash);
459 }
460
461 /**
462 * @copydoc equal_range(const K& key)
463 */
464 template <class K, class KE = KeyEqual,
465 typename std::enable_if<has_is_transparent<KE>::value>::type * = nullptr>
466 std::pair<const_iterator, const_iterator> equal_range(const K &key) const
467 {
468 return m_ht.equal_range(key);
469 }
470
471 /**
472 * @copydoc equal_range(const K& key, std::size_t precalculated_hash)
473 */
474 template <class K, class KE = KeyEqual,
475 typename std::enable_if<has_is_transparent<KE>::value>::type * = nullptr>
476 std::pair<const_iterator, const_iterator> equal_range(const K & key,
477 std::size_t precalculated_hash) const
478 {
479 return m_ht.equal_range(key, precalculated_hash);
480 }
481
482 /*
483 * Bucket interface
484 */
485 size_type bucket_count() const { return m_ht.bucket_count(); }
486 size_type max_bucket_count() const { return m_ht.max_bucket_count(); }
487
488 /*
489 * Hash policy
490 */
491 float load_factor() const { return m_ht.load_factor(); }
492
493 float min_load_factor() const { return m_ht.min_load_factor(); }
494 float max_load_factor() const { return m_ht.max_load_factor(); }
495
496 /**
497 * Set the `min_load_factor` to `ml`. When the `load_factor` of the set goes
498 * below `min_load_factor` after some erase operations, the set will be
499 * shrunk when an insertion occurs. The erase method itself never shrinks
500 * the set.
501 *
502 * The default value of `min_load_factor` is 0.0f, the set never shrinks by default.
503 */
504 void min_load_factor(float ml) { m_ht.min_load_factor(ml); }
505 void max_load_factor(float ml) { m_ht.max_load_factor(ml); }
506
507 void rehash(size_type new_count) { m_ht.rehash(new_count); }
508 void reserve(size_type new_count) { m_ht.reserve(new_count); }
509
510 /*
511 * Observers
512 */
513 hasher hash_function() const { return m_ht.hash_function(); }
514 key_equal key_eq() const { return m_ht.key_eq(); }
515
516 /*
517 * Other
518 */
519
520 /**
521 * Convert a const_iterator to an iterator.
522 */
523 iterator mutable_iterator(const_iterator pos) { return m_ht.mutable_iterator(pos); }
524
525 friend bool operator==(const robin_set &lhs, const robin_set &rhs)
526 {
527 if (lhs.size() != rhs.size()) {
528 return false;
529 }
530
531 for (const auto &element_lhs : lhs) {
532 const auto it_element_rhs = rhs.find(element_lhs);
533 if (it_element_rhs == rhs.cend()) {
534 return false;
535 }
536 }
537
538 return true;
539 }
540
541 friend bool operator!=(const robin_set &lhs, const robin_set &rhs)
542 {
543 return !operator==(lhs, rhs);
544 }
545
546 friend void swap(robin_set &lhs, robin_set &rhs) { lhs.swap(rhs); }
547
548 private:
549 ht m_ht;
550 };
551
552 /**
553 * Same as `tsl::robin_set<Key, Hash, KeyEqual, Allocator, StoreHash,
554 * tsl::rh::prime_growth_policy>`.
555 */
556 template <class Key, class Hash = std::hash<Key>, class KeyEqual = std::equal_to<Key>,
557 class Allocator = std::allocator<Key>, bool StoreHash = false>
558 using robin_pg_set =
559 robin_set<Key, Hash, KeyEqual, Allocator, StoreHash, tsl::rh::prime_growth_policy>;
560
561 } // end namespace tsl
562
563 #endif
tsl::robin_set::begin
iterator begin() noexcept
Definition: robin_set.h:194
tsl::robin_set::m_ht
ht m_ht
Definition: robin_set.h:549
tsl::robin_set::const_iterator
typename ht::const_iterator const_iterator
Definition: robin_set.h:113
tsl::robin_set::find
iterator find(const K &key, std::size_t precalculated_hash)
Definition: robin_set.h:381
tsl
Definition: bhopscotch_map.h:37
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:160
tsl::robin_set::max_load_factor
float max_load_factor() const
Definition: robin_set.h:494
tsl::detail_robin_hash::robin_hash::hash_function
hasher hash_function() const
Definition: robin_hash.h:1034
tsl::robin_set::reference
typename ht::reference reference
Definition: robin_set.h:108
tsl::detail_robin_hash::robin_hash::size
size_type size() const noexcept
Definition: robin_hash.h:669
tsl::robin_set::find
const_iterator find(const Key &key) const
Definition: robin_set.h:351
tsl::robin_set::const_pointer
typename ht::const_pointer const_pointer
Definition: robin_set.h:111
tsl::robin_set::reserve
void reserve(size_type new_count)
Definition: robin_set.h:508
tsl::robin_set::erase
size_type erase(const key_type &key, std::size_t precalculated_hash)
Definition: robin_set.h:267
tsl::detail_robin_hash::robin_hash::max_load_factor
float max_load_factor() const
Definition: robin_hash.h:1005
tsl::robin_set::end
iterator end() noexcept
Definition: robin_set.h:198
tsl::robin_set::rehash
void rehash(size_type new_count)
Definition: robin_set.h:507
tsl::detail_robin_hash::robin_hash::emplace
std::pair< iterator, bool > emplace(Args &&... args)
Definition: robin_hash.h:740
tsl::robin_set::equal_range
std::pair< iterator, iterator > equal_range(const Key &key, std::size_t precalculated_hash)
Definition: robin_set.h:417
tsl::detail_robin_hash::robin_hash< Key, KeySelect, void, Hash, KeyEqual, Allocator, StoreHash, GrowthPolicy >::pointer
value_type * pointer
Definition: robin_hash.h:348
tsl::robin_set::insert
iterator insert(const_iterator hint, const value_type &value)
Definition: robin_set.h:218
tsl::robin_set::find
const_iterator find(const K &key, std::size_t precalculated_hash) const
Definition: robin_set.h:405
tsl::robin_set::insert
iterator insert(const_iterator hint, value_type &&value)
Definition: robin_set.h:223
tsl::robin_set::const_reference
typename ht::const_reference const_reference
Definition: robin_set.h:109
tsl::robin_set::insert
std::pair< iterator, bool > insert(const value_type &value)
Definition: robin_set.h:214
tsl::robin_set::emplace
std::pair< iterator, bool > emplace(Args &&... args)
Definition: robin_set.h:241
tsl::robin_set
Definition: robin_set.h:82
tsl::robin_set::pointer
typename ht::pointer pointer
Definition: robin_set.h:110
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:342
anonymous_namespace{Ioss_SmartAssert.C}::init
struct anonymous_namespace{Ioss_SmartAssert.C}::assert_initializer init
tsl::detail_robin_hash::robin_hash::empty
bool empty() const noexcept
Definition: robin_hash.h:667
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:341
tsl::robin_set::erase
size_type erase(const key_type &key)
Definition: robin_set.h:260
tsl::robin_set::erase
iterator erase(const_iterator first, const_iterator last)
Definition: robin_set.h:259
tsl::robin_set::size
size_type size() const noexcept
Definition: robin_set.h:206
tsl::robin_set::emplace_hint
iterator emplace_hint(const_iterator hint, Args &&... args)
Definition: robin_set.h:252
tsl::robin_set::cend
const_iterator cend() const noexcept
Definition: robin_set.h:200
tsl::robin_set::KeySelect::operator()
const key_type & operator()(const Key &key) const noexcept
Definition: robin_set.h:92
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:167
tsl::robin_set::difference_type
typename ht::difference_type difference_type
Definition: robin_set.h:104
tsl::robin_set::hash_function
hasher hash_function() const
Definition: robin_set.h:513
tsl::robin_set::iterator
typename ht::iterator iterator
Definition: robin_set.h:112
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:430
tsl::robin_set::min_load_factor
float min_load_factor() const
Definition: robin_set.h:493
tsl::robin_set::erase
size_type erase(const K &key)
Definition: robin_set.h:278
tsl::robin_set::robin_set
robin_set(InputIt first, InputIt last, size_type my_bucket_count, const Allocator &alloc)
Definition: robin_set.h:148
tsl::robin_set::erase
iterator erase(const_iterator pos)
Definition: robin_set.h:258
tsl::robin_set::find
iterator find(const K &key)
Definition: robin_set.h:367
tsl::detail_robin_hash::robin_hash::max_size
size_type max_size() const noexcept
Definition: robin_hash.h:671
tsl::robin_set::bucket_count
size_type bucket_count() const
Definition: robin_set.h:485
tsl::robin_set::robin_set
robin_set(size_type my_bucket_count, const Allocator &alloc)
Definition: robin_set.h:126
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:139
tsl::detail_robin_hash::robin_hash::rehash
void rehash(size_type new_count)
Definition: robin_hash.h:1020
tsl::detail_robin_hash::robin_hash::insert_hint
iterator insert_hint(const_iterator hint, P &&value)
Definition: robin_hash.h:691
tsl::robin_set::max_load_factor
void max_load_factor(float ml)
Definition: robin_set.h:505
tsl::robin_set::empty
bool empty() const noexcept
Definition: robin_set.h:205
tsl::robin_set::equal_range
std::pair< iterator, iterator > equal_range(const K &key, std::size_t precalculated_hash)
Definition: robin_set.h:456
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:347
tsl::robin_set::KeySelect::operator()
key_type & operator()(Key &key) noexcept
Definition: robin_set.h:94
tsl::detail_robin_hash::robin_hash::clear
void clear() noexcept
Definition: robin_hash.h:676
tsl::robin_set::key_eq
key_equal key_eq() const
Definition: robin_set.h:514
tsl::robin_set::swap
friend void swap(robin_set &lhs, robin_set &rhs)
Definition: robin_set.h:546
tsl::detail_robin_hash::robin_hash::reserve
void reserve(size_type new_count)
Definition: robin_hash.h:1026
robin_hash.h
tsl::detail_robin_hash::robin_hash< Key, KeySelect, void, Hash, KeyEqual, Allocator, StoreHash, GrowthPolicy >::value_type
Key value_type
Definition: robin_hash.h:340
tsl::detail_robin_hash::robin_hash::find
iterator find(const K &key)
Definition: robin_hash.h:940
tsl::robin_set::robin_set
robin_set()
Definition: robin_set.h:118
tsl::detail_robin_hash::robin_hash::cbegin
const_iterator cbegin() const noexcept
Definition: robin_hash.h:648
tsl::robin_set::find
const_iterator find(const Key &key, std::size_t precalculated_hash) const
Definition: robin_set.h:356
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:476
tsl::robin_set::size_type
typename ht::size_type size_type
Definition: robin_set.h:103
tsl::detail_robin_hash::robin_hash::count
size_type count(const K &key) const
Definition: robin_hash.h:928
tsl::robin_set::find
const_iterator find(const K &key) const
Definition: robin_set.h:391
tsl::detail_robin_hash::has_is_transparent
Definition: robin_hash.h:52
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:1304
tsl::robin_set::robin_set
robin_set(const Allocator &alloc)
Definition: robin_set.h:136
tsl::detail_robin_hash::robin_hash::cend
const_iterator cend() const noexcept
Definition: robin_hash.h:662
tsl::detail_robin_hash::robin_hash< Key, KeySelect, void, Hash, KeyEqual, Allocator, StoreHash, GrowthPolicy >::key_equal
KeyEqual key_equal
Definition: robin_hash.h:344
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:349
tsl::robin_set::key_equal
typename ht::key_equal key_equal
Definition: robin_set.h:106
tsl::robin_set::count
size_type count(const Key &key) const
Definition: robin_set.h:302
tsl::detail_robin_hash::robin_hash< Key, KeySelect, void, Hash, KeyEqual, Allocator, StoreHash, GrowthPolicy >::hasher
Hash hasher
Definition: robin_hash.h:343
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:173
tsl::detail_robin_hash::robin_hash::erase
iterator erase(iterator pos)
Definition: robin_hash.h:772
tsl::detail_robin_hash::robin_hash
Definition: robin_hash.h:325
tsl::detail_robin_hash::robin_hash::mutable_iterator
iterator mutable_iterator(const_iterator pos)
Definition: robin_hash.h:1041
tsl::robin_set::get_allocator
allocator_type get_allocator() const
Definition: robin_set.h:189
tsl::robin_set::count
size_type count(const K &key) const
Definition: robin_set.h:320
tsl::robin_set::erase
iterator erase(iterator pos)
Definition: robin_set.h:257
tsl::detail_robin_hash::robin_hash::emplace_hint
iterator emplace_hint(const_iterator hint, Args &&... args)
Definition: robin_hash.h:745
tsl::robin_set::min_load_factor
void min_load_factor(float ml)
Definition: robin_set.h:504
tsl::robin_set::key_type
typename ht::key_type key_type
Definition: robin_set.h:101
tsl::robin_set::equal_range
std::pair< const_iterator, const_iterator > equal_range(const Key &key) const
Definition: robin_set.h:422
tsl::robin_set::value_type
typename ht::value_type value_type
Definition: robin_set.h:102
tsl::robin_set::equal_range
std::pair< const_iterator, const_iterator > equal_range(const K &key) const
Definition: robin_set.h:466
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:351
tsl::robin_set::KeySelect::key_type
Key key_type
Definition: robin_set.h:90
tsl::detail_robin_hash::robin_hash::swap
void swap(robin_hash &other)
Definition: robin_hash.h:865
tsl::detail_robin_hash::robin_hash::min_load_factor
float min_load_factor() const
Definition: robin_hash.h:1003
tsl::robin_set::allocator_type
typename ht::allocator_type allocator_type
Definition: robin_set.h:107
tsl::robin_set::cbegin
const_iterator cbegin() const noexcept
Definition: robin_set.h:196
tsl::robin_set::equal_range
std::pair< iterator, iterator > equal_range(const Key &key)
Definition: robin_set.h:410
tsl::detail_robin_hash::robin_hash< Key, KeySelect, void, Hash, KeyEqual, Allocator, StoreHash, GrowthPolicy >::allocator_type
Allocator allocator_type
Definition: robin_hash.h:345
tsl::robin_set::hasher
typename ht::hasher hasher
Definition: robin_set.h:105
tsl::robin_set::max_bucket_count
size_type max_bucket_count() const
Definition: robin_set.h:486
tsl::robin_set::operator=
robin_set & operator=(std::initializer_list< value_type > ilist)
Definition: robin_set.h:179
tsl::detail_robin_hash::robin_hash::end
iterator end() noexcept
Definition: robin_hash.h:658
tsl::robin_set::robin_set
robin_set(size_type my_bucket_count, const Hash &hash, const Allocator &alloc)
Definition: robin_set.h:131
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:154
tsl::robin_set::find
iterator find(const Key &key)
Definition: robin_set.h:339
tsl::robin_set::operator!=
friend bool operator!=(const robin_set &lhs, const robin_set &rhs)
Definition: robin_set.h:541
tsl::detail_robin_hash::robin_hash::get_allocator
allocator_type get_allocator() const
Definition: robin_hash.h:631
tsl::robin_set::insert
void insert(std::initializer_list< value_type > ilist)
Definition: robin_set.h:230
tsl::robin_set::find
iterator find(const Key &key, std::size_t precalculated_hash)
Definition: robin_set.h:346
tsl::robin_set::equal_range
std::pair< iterator, iterator > equal_range(const K &key)
Definition: robin_set.h:442
tsl::robin_set::KeySelect
Definition: robin_set.h:87
tsl::detail_robin_hash::robin_hash::max_bucket_count
size_type max_bucket_count() const
Definition: robin_hash.h:986
tsl::robin_set::count
size_type count(const Key &key, std::size_t precalculated_hash) const
Definition: robin_set.h:309
tsl::robin_set::operator==
friend bool operator==(const robin_set &lhs, const robin_set &rhs)
Definition: robin_set.h:525
tsl::robin_set::insert
void insert(InputIt first, InputIt last)
Definition: robin_set.h:228
tsl::detail_robin_hash::robin_hash::equal_range
std::pair< iterator, iterator > equal_range(const K &key)
Definition: robin_hash.h:957
tsl::detail_robin_hash::robin_hash< Key, KeySelect, void, Hash, KeyEqual, Allocator, StoreHash, GrowthPolicy >::reference
value_type & reference
Definition: robin_hash.h:346
tsl::robin_set::ht
detail_robin_hash::robin_hash< Key, KeySelect, void, Hash, KeyEqual, Allocator, StoreHash, GrowthPolicy > ht
Definition: robin_set.h:98
tsl::robin_set::erase
size_type erase(const K &key, std::size_t precalculated_hash)
Definition: robin_set.h:292
tsl::robin_set::max_size
size_type max_size() const noexcept
Definition: robin_set.h:207
tsl::robin_set::load_factor
float load_factor() const
Definition: robin_set.h:491
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:339
tsl::robin_set::end
const_iterator end() const noexcept
Definition: robin_set.h:199
tsl::robin_set::clear
void clear() noexcept
Definition: robin_set.h:212
tsl::detail_robin_hash::robin_hash::bucket_count
size_type bucket_count() const
Definition: robin_hash.h:984
tsl::detail_robin_hash::robin_hash::begin
iterator begin() noexcept
Definition: robin_hash.h:636
tsl::detail_robin_hash::robin_hash< Key, KeySelect, void, Hash, KeyEqual, Allocator, StoreHash, GrowthPolicy >::iterator
robin_iterator< false > iterator
Definition: robin_hash.h:350
tsl::robin_set::count
size_type count(const K &key, std::size_t precalculated_hash) const
Definition: robin_set.h:334
tsl::robin_set::swap
void swap(robin_set &other)
Definition: robin_set.h:297
tsl::detail_robin_hash::robin_hash::key_eq
key_equal key_eq() const
Definition: robin_hash.h:1036
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:120
tsl::robin_set::insert
std::pair< iterator, bool > insert(value_type &&value)
Definition: robin_set.h:216
tsl::robin_set::mutable_iterator
iterator mutable_iterator(const_iterator pos)
Definition: robin_set.h:523
tsl::detail_robin_hash::robin_hash::insert
std::pair< iterator, bool > insert(P &&value)
Definition: robin_hash.h:686
tsl::detail_robin_hash::robin_hash::load_factor
float load_factor() const
Definition: robin_hash.h:994
tsl::robin_set::begin
const_iterator begin() const noexcept
Definition: robin_set.h:195