IOSS 2.0
Loading...
Searching...
No Matches
robin_set.h
Go to the documentation of this file.
1/**
2 * MIT License
3 *
4 * Copyright (c) 2017 Thibaut Goetghebuer-Planchon <tessil@gmx.com>
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
14 * all 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 <cstddef>
28#include <functional>
29#include <initializer_list>
30#include <memory>
31#include <type_traits>
32#include <utility>
33
34#include "robin_hash.h"
35
36namespace tsl {
37
38 /**
39 * Implementation of a hash set using open-addressing and the robin hood hashing
40 * algorithm with backward shift deletion.
41 *
42 * For operations modifying the hash set (insert, erase, rehash, ...), the
43 * strong exception guarantee is only guaranteed when the expression
44 * `std::is_nothrow_swappable<Key>\:\:value &&
45 * std::is_nothrow_move_constructible<Key>\:\:value` is true, otherwise if an
46 * exception is thrown during the swap or the move, the hash set may end up in a
47 * undefined state. Per the standard a `Key` with a noexcept copy constructor
48 * and no move constructor also satisfies the
49 * `std::is_nothrow_move_constructible<Key>\:\:value` criterion (and will thus
50 * guarantee the strong exception for the set).
51 *
52 * When `StoreHash` is true, 32 bits of the hash are stored alongside the
53 * values. It can improve the performance during lookups if the `KeyEqual`
54 * function takes time (or engenders a cache-miss for example) as we then
55 * compare the stored hashes before comparing the keys. When
56 * `tsl::rh::power_of_two_growth_policy` is used as `GrowthPolicy`, it may also
57 * speed-up the rehash process as we can avoid to recalculate the hash. When it
58 * is detected that storing the hash will not incur any memory penalty due to
59 * alignment (i.e. `sizeof(tsl::detail_robin_hash::bucket_entry<ValueType,
60 * true>) == sizeof(tsl::detail_robin_hash::bucket_entry<ValueType, false>)`)
61 * and `tsl::rh::power_of_two_growth_policy` is used, the hash will be stored
62 * even if `StoreHash` is false so that we can speed-up the rehash (but it will
63 * not be used on lookups unless `StoreHash` is true).
64 *
65 * `GrowthPolicy` defines how the set grows and consequently how a hash value is
66 * mapped to a bucket. By default the set uses
67 * `tsl::rh::power_of_two_growth_policy`. This policy keeps the number of
68 * buckets to a power of two and uses a mask to set the hash to a bucket instead
69 * of the slow modulo. Other growth policies are available and you may define
70 * your own growth policy, check `tsl::rh::power_of_two_growth_policy` for the
71 * interface.
72 *
73 * `Key` must be swappable.
74 *
75 * `Key` must be copy and/or move constructible.
76 *
77 * If the destructor of `Key` throws an exception, the behaviour of the class is
78 * undefined.
79 *
80 * Iterators invalidation:
81 * - clear, operator=, reserve, rehash: always invalidate the iterators.
82 * - insert, emplace, emplace_hint, operator[]: if there is an effective
83 * insert, invalidate the iterators.
84 * - erase: always invalidate the iterators.
85 */
86 template <class Key, class Hash = std::hash<Key>, class KeyEqual = std::equal_to<Key>,
87 class Allocator = std::allocator<Key>, bool StoreHash = false,
88 class GrowthPolicy = tsl::rh::power_of_two_growth_policy<2>>
90 {
91 private:
93
95 {
96 public:
97 using key_type = Key;
98
99 const key_type &operator()(const Key &key) const noexcept { return key; }
100
101 key_type &operator()(Key &key) noexcept { return key; }
102 };
103
104 using ht = detail_robin_hash::robin_hash<Key, KeySelect, void, Hash, KeyEqual, Allocator,
105 StoreHash, GrowthPolicy>;
106
107 public:
108 using key_type = typename ht::key_type;
109 using value_type = typename ht::value_type;
110 using size_type = typename ht::size_type;
112 using hasher = typename ht::hasher;
113 using key_equal = typename ht::key_equal;
115 using reference = typename ht::reference;
117 using pointer = typename ht::pointer;
119 using iterator = typename ht::iterator;
121
122 /*
123 * Constructors
124 */
125 robin_set() : robin_set(ht::DEFAULT_INIT_BUCKETS_SIZE) {}
126
127 explicit robin_set(size_type bucket_count, const Hash &hash = Hash(),
128 const KeyEqual &equal = KeyEqual(), const Allocator &alloc = Allocator())
129 : m_ht(bucket_count, hash, equal, alloc)
130 {
131 }
132
133 robin_set(size_type bucket_count, const Allocator &alloc)
134 : robin_set(bucket_count, Hash(), KeyEqual(), alloc)
135 {
136 }
137
138 robin_set(size_type bucket_count, const Hash &hash, const Allocator &alloc)
139 : robin_set(bucket_count, hash, KeyEqual(), alloc)
140 {
141 }
142
143 explicit robin_set(const Allocator &alloc) : robin_set(ht::DEFAULT_INIT_BUCKETS_SIZE, alloc) {}
144
145 template <class InputIt>
147 const Hash &hash = Hash(), const KeyEqual &equal = KeyEqual(),
148 const Allocator &alloc = Allocator())
149 : robin_set(bucket_count, hash, equal, alloc)
150 {
151 insert(first, last);
152 }
153
154 template <class InputIt>
155 robin_set(InputIt first, InputIt last, size_type bucket_count, const Allocator &alloc)
156 : robin_set(first, last, bucket_count, Hash(), KeyEqual(), alloc)
157 {
158 }
159
160 template <class InputIt>
161 robin_set(InputIt first, InputIt last, size_type bucket_count, const Hash &hash,
162 const Allocator &alloc)
163 : robin_set(first, last, bucket_count, hash, KeyEqual(), alloc)
164 {
165 }
166
167 robin_set(std::initializer_list<value_type> init,
168 size_type bucket_count = ht::DEFAULT_INIT_BUCKETS_SIZE, const Hash &hash = Hash(),
169 const KeyEqual &equal = KeyEqual(), const Allocator &alloc = Allocator())
170 : robin_set(init.begin(), init.end(), bucket_count, hash, equal, alloc)
171 {
172 }
173
174 robin_set(std::initializer_list<value_type> init, size_type bucket_count,
175 const Allocator &alloc)
176 : robin_set(init.begin(), init.end(), bucket_count, Hash(), KeyEqual(), alloc)
177 {
178 }
179
180 robin_set(std::initializer_list<value_type> init, size_type bucket_count, const Hash &hash,
181 const Allocator &alloc)
182 : robin_set(init.begin(), init.end(), bucket_count, hash, KeyEqual(), alloc)
183 {
184 }
185
186 robin_set &operator=(std::initializer_list<value_type> ilist)
187 {
188 m_ht.clear();
189
190 m_ht.reserve(ilist.size());
191 m_ht.insert(ilist.begin(), ilist.end());
192
193 return *this;
194 }
195
197
198 /*
199 * Iterators
200 */
201 iterator begin() noexcept { return m_ht.begin(); }
202 const_iterator begin() const noexcept { return m_ht.begin(); }
203 const_iterator cbegin() const noexcept { return m_ht.cbegin(); }
204
205 iterator end() noexcept { return m_ht.end(); }
206 const_iterator end() const noexcept { return m_ht.end(); }
207 const_iterator cend() const noexcept { return m_ht.cend(); }
208
209 /*
210 * Capacity
211 */
212 bool empty() const noexcept { return m_ht.empty(); }
213 size_type size() const noexcept { return m_ht.size(); }
214 size_type max_size() const noexcept { return m_ht.max_size(); }
215
216 /*
217 * Modifiers
218 */
219 void clear() noexcept { m_ht.clear(); }
220
221 std::pair<iterator, bool> insert(const value_type &value) { return m_ht.insert(value); }
222
223 std::pair<iterator, bool> insert(value_type &&value) { return m_ht.insert(std::move(value)); }
224
226 {
227 return m_ht.insert_hint(hint, value);
228 }
229
231 {
232 return m_ht.insert_hint(hint, std::move(value));
233 }
234
235 template <class InputIt> void insert(InputIt first, InputIt last) { m_ht.insert(first, last); }
236
237 void insert(std::initializer_list<value_type> ilist)
238 {
239 m_ht.insert(ilist.begin(), ilist.end());
240 }
241
242 /**
243 * Due to the way elements are stored, emplace will need to move or copy the
244 * key-value once. The method is equivalent to
245 * insert(value_type(std::forward<Args>(args)...));
246 *
247 * Mainly here for compatibility with the std::unordered_map interface.
248 */
249 template <class... Args> std::pair<iterator, bool> emplace(Args &&...args)
250 {
251 return m_ht.emplace(std::forward<Args>(args)...);
252 }
253
254 /**
255 * Due to the way elements are stored, emplace_hint will need to move or copy
256 * the key-value once. The method is equivalent to insert(hint,
257 * value_type(std::forward<Args>(args)...));
258 *
259 * Mainly here for compatibility with the std::unordered_map interface.
260 */
261 template <class... Args> iterator emplace_hint(const_iterator hint, Args &&...args)
262 {
263 return m_ht.emplace_hint(hint, std::forward<Args>(args)...);
264 }
265
266 iterator erase(iterator pos) { return m_ht.erase(pos); }
267 iterator erase(const_iterator pos) { return m_ht.erase(pos); }
268 iterator erase(const_iterator first, const_iterator last) { return m_ht.erase(first, last); }
269 size_type erase(const key_type &key) { return m_ht.erase(key); }
270
271 /**
272 * Use the hash value 'precalculated_hash' instead of hashing the key. The
273 * hash value should be the same as hash_function()(key). Useful to speed-up
274 * the lookup to the value if you already have the hash.
275 */
276 size_type erase(const key_type &key, std::size_t precalculated_hash)
277 {
278 return m_ht.erase(key, precalculated_hash);
279 }
280
281 /**
282 * This overload only participates in the overload resolution if the typedef
283 * KeyEqual::is_transparent exists. If so, K must be hashable and comparable
284 * to Key.
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)
289 {
290 return m_ht.erase(key);
291 }
292
293 /**
294 * @copydoc erase(const K& key)
295 *
296 * Use the hash value 'precalculated_hash' instead of hashing the key. The
297 * hash value should be the same as hash_function()(key). Useful to speed-up
298 * the lookup to the value if you already have the hash.
299 */
300 template <class K, class KE = KeyEqual,
301 typename std::enable_if<has_is_transparent<KE>::value>::type * = nullptr>
302 size_type erase(const K &key, std::size_t precalculated_hash)
303 {
304 return m_ht.erase(key, precalculated_hash);
305 }
306
307 void swap(robin_set &other) { other.m_ht.swap(m_ht); }
308
309 /*
310 * Lookup
311 */
312 size_type count(const Key &key) const { return m_ht.count(key); }
313
314 /**
315 * Use the hash value 'precalculated_hash' instead of hashing the key. The
316 * hash value should be the same as hash_function()(key). Useful to speed-up
317 * the lookup if you already have the hash.
318 */
319 size_type count(const Key &key, std::size_t precalculated_hash) const
320 {
321 return m_ht.count(key, precalculated_hash);
322 }
323
324 /**
325 * This overload only participates in the overload resolution if the typedef
326 * KeyEqual::is_transparent exists. If so, K must be hashable and comparable
327 * to Key.
328 */
329 template <class K, class KE = KeyEqual,
330 typename std::enable_if<has_is_transparent<KE>::value>::type * = nullptr>
331 size_type count(const K &key) const
332 {
333 return m_ht.count(key);
334 }
335
336 /**
337 * @copydoc count(const K& key) const
338 *
339 * Use the hash value 'precalculated_hash' instead of hashing the key. The
340 * hash value should be the same as hash_function()(key). Useful to speed-up
341 * the lookup if you already have the hash.
342 */
343 template <class K, class KE = KeyEqual,
344 typename std::enable_if<has_is_transparent<KE>::value>::type * = nullptr>
345 size_type count(const K &key, std::size_t precalculated_hash) const
346 {
347 return m_ht.count(key, precalculated_hash);
348 }
349
350 iterator find(const Key &key) { return m_ht.find(key); }
351
352 /**
353 * Use the hash value 'precalculated_hash' instead of hashing the key. The
354 * hash value should be the same as hash_function()(key). Useful to speed-up
355 * the lookup if you already have the hash.
356 */
357 iterator find(const Key &key, std::size_t precalculated_hash)
358 {
359 return m_ht.find(key, precalculated_hash);
360 }
361
362 const_iterator find(const Key &key) const { return m_ht.find(key); }
363
364 /**
365 * @copydoc find(const Key& key, std::size_t precalculated_hash)
366 */
367 const_iterator find(const Key &key, std::size_t precalculated_hash) const
368 {
369 return m_ht.find(key, precalculated_hash);
370 }
371
372 /**
373 * This overload only participates in the overload resolution if the typedef
374 * KeyEqual::is_transparent exists. If so, K must be hashable and comparable
375 * to Key.
376 */
377 template <class K, class KE = KeyEqual,
378 typename std::enable_if<has_is_transparent<KE>::value>::type * = nullptr>
379 iterator find(const K &key)
380 {
381 return m_ht.find(key);
382 }
383
384 /**
385 * @copydoc find(const K& key)
386 *
387 * Use the hash value 'precalculated_hash' instead of hashing the key. The
388 * hash value should be the same as hash_function()(key). Useful to speed-up
389 * the lookup if you already have the hash.
390 */
391 template <class K, class KE = KeyEqual,
392 typename std::enable_if<has_is_transparent<KE>::value>::type * = nullptr>
393 iterator find(const K &key, std::size_t precalculated_hash)
394 {
395 return m_ht.find(key, precalculated_hash);
396 }
397
398 /**
399 * @copydoc find(const K& key)
400 */
401 template <class K, class KE = KeyEqual,
402 typename std::enable_if<has_is_transparent<KE>::value>::type * = nullptr>
403 const_iterator find(const K &key) const
404 {
405 return m_ht.find(key);
406 }
407
408 /**
409 * @copydoc find(const K& key)
410 *
411 * Use the hash value 'precalculated_hash' instead of hashing the key. The
412 * hash value should be the same as hash_function()(key). Useful to speed-up
413 * the lookup if you already have the hash.
414 */
415 template <class K, class KE = KeyEqual,
416 typename std::enable_if<has_is_transparent<KE>::value>::type * = nullptr>
417 const_iterator find(const K &key, std::size_t precalculated_hash) const
418 {
419 return m_ht.find(key, precalculated_hash);
420 }
421
422 bool contains(const Key &key) const { return m_ht.contains(key); }
423
424 /**
425 * Use the hash value 'precalculated_hash' instead of hashing the key. The
426 * hash value should be the same as hash_function()(key). Useful to speed-up
427 * the lookup if you already have the hash.
428 */
429 bool contains(const Key &key, std::size_t precalculated_hash) const
430 {
431 return m_ht.contains(key, precalculated_hash);
432 }
433
434 /**
435 * This overload only participates in the overload resolution if the typedef
436 * KeyEqual::is_transparent exists. If so, K must be hashable and comparable
437 * to Key.
438 */
439 template <class K, class KE = KeyEqual,
440 typename std::enable_if<has_is_transparent<KE>::value>::type * = nullptr>
441 bool contains(const K &key) const
442 {
443 return m_ht.contains(key);
444 }
445
446 /**
447 * @copydoc contains(const K& key) const
448 *
449 * Use the hash value 'precalculated_hash' instead of hashing the key. The
450 * hash value should be the same as hash_function()(key). Useful to speed-up
451 * the lookup if you already have the hash.
452 */
453 template <class K, class KE = KeyEqual,
454 typename std::enable_if<has_is_transparent<KE>::value>::type * = nullptr>
455 bool contains(const K &key, std::size_t precalculated_hash) const
456 {
457 return m_ht.contains(key, precalculated_hash);
458 }
459
460 std::pair<iterator, iterator> equal_range(const Key &key) { return m_ht.equal_range(key); }
461
462 /**
463 * Use the hash value 'precalculated_hash' instead of hashing the key. The
464 * hash value should be the same as hash_function()(key). Useful to speed-up
465 * the lookup if you already have the hash.
466 */
467 std::pair<iterator, iterator> equal_range(const Key &key, std::size_t precalculated_hash)
468 {
469 return m_ht.equal_range(key, precalculated_hash);
470 }
471
472 std::pair<const_iterator, const_iterator> equal_range(const Key &key) const
473 {
474 return m_ht.equal_range(key);
475 }
476
477 /**
478 * @copydoc equal_range(const Key& key, std::size_t precalculated_hash)
479 */
480 std::pair<const_iterator, const_iterator> equal_range(const Key &key,
481 std::size_t precalculated_hash) const
482 {
483 return m_ht.equal_range(key, precalculated_hash);
484 }
485
486 /**
487 * This overload only participates in the overload resolution if the typedef
488 * KeyEqual::is_transparent exists. If so, K must be hashable and comparable
489 * to Key.
490 */
491 template <class K, class KE = KeyEqual,
492 typename std::enable_if<has_is_transparent<KE>::value>::type * = nullptr>
493 std::pair<iterator, iterator> equal_range(const K &key)
494 {
495 return m_ht.equal_range(key);
496 }
497
498 /**
499 * @copydoc equal_range(const K& key)
500 *
501 * Use the hash value 'precalculated_hash' instead of hashing the key. The
502 * hash value should be the same as hash_function()(key). Useful to speed-up
503 * the lookup if you already have the hash.
504 */
505 template <class K, class KE = KeyEqual,
506 typename std::enable_if<has_is_transparent<KE>::value>::type * = nullptr>
507 std::pair<iterator, iterator> equal_range(const K &key, std::size_t precalculated_hash)
508 {
509 return m_ht.equal_range(key, precalculated_hash);
510 }
511
512 /**
513 * @copydoc equal_range(const K& key)
514 */
515 template <class K, class KE = KeyEqual,
516 typename std::enable_if<has_is_transparent<KE>::value>::type * = nullptr>
517 std::pair<const_iterator, const_iterator> equal_range(const K &key) const
518 {
519 return m_ht.equal_range(key);
520 }
521
522 /**
523 * @copydoc equal_range(const K& key, std::size_t precalculated_hash)
524 */
525 template <class K, class KE = KeyEqual,
526 typename std::enable_if<has_is_transparent<KE>::value>::type * = nullptr>
527 std::pair<const_iterator, const_iterator> equal_range(const K &key,
528 std::size_t precalculated_hash) const
529 {
530 return m_ht.equal_range(key, precalculated_hash);
531 }
532
533 /*
534 * Bucket interface
535 */
538
539 /*
540 * Hash policy
541 */
542 float load_factor() const { return m_ht.load_factor(); }
543
544 float min_load_factor() const { return m_ht.min_load_factor(); }
545 float max_load_factor() const { return m_ht.max_load_factor(); }
546
547 /**
548 * Set the `min_load_factor` to `ml`. When the `load_factor` of the set goes
549 * below `min_load_factor` after some erase operations, the set will be
550 * shrunk when an insertion occurs. The erase method itself never shrinks
551 * the set.
552 *
553 * The default value of `min_load_factor` is 0.0f, the set never shrinks by
554 * default.
555 */
556 void min_load_factor(float ml) { m_ht.min_load_factor(ml); }
557 void max_load_factor(float ml) { m_ht.max_load_factor(ml); }
558
559 void rehash(size_type my_count) { m_ht.rehash(my_count); }
560 void reserve(size_type my_count) { m_ht.reserve(my_count); }
561
562 /*
563 * Observers
564 */
566 key_equal key_eq() const { return m_ht.key_eq(); }
567
568 /*
569 * Other
570 */
571
572 /**
573 * Convert a const_iterator to an iterator.
574 */
576
577 friend bool operator==(const robin_set &lhs, const robin_set &rhs)
578 {
579 if (lhs.size() != rhs.size()) {
580 return false;
581 }
582
583 for (const auto &element_lhs : lhs) {
584 const auto it_element_rhs = rhs.find(element_lhs);
585 if (it_element_rhs == rhs.cend()) {
586 return false;
587 }
588 }
589
590 return true;
591 }
592
593 /**
594 * Serialize the set through the `serializer` parameter.
595 *
596 * The `serializer` parameter must be a function object that supports the
597 * following call:
598 * - `template<typename U> void operator()(const U& value);` where the types
599 * `std::int16_t`, `std::uint32_t`, `std::uint64_t`, `float` and `Key` must be
600 * supported for U.
601 *
602 * The implementation leaves binary compatibility (endianness, IEEE 754 for
603 * floats, ...) of the types it serializes in the hands of the `Serializer`
604 * function object if compatibility is required.
605 */
606 template <class Serializer> void serialize(Serializer &serializer) const
607 {
608 m_ht.serialize(serializer);
609 }
610
611 /**
612 * Deserialize a previously serialized set through the `deserializer`
613 * parameter.
614 *
615 * The `deserializer` parameter must be a function object that supports the
616 * following call:
617 * - `template<typename U> U operator()();` where the types `std::int16_t`,
618 * `std::uint32_t`, `std::uint64_t`, `float` and `Key` must be supported for
619 * U.
620 *
621 * If the deserialized hash set type is hash compatible with the serialized
622 * set, the deserialization process can be sped up by setting
623 * `hash_compatible` to true. To be hash compatible, the Hash, KeyEqual and
624 * GrowthPolicy must behave the same way than the ones used on the serialized
625 * set and the StoreHash must have the same value. The `std::size_t` must also
626 * be of the same size as the one on the platform used to serialize the set.
627 * If these criteria are not met, the behaviour is undefined with
628 * `hash_compatible` sets to true.
629 *
630 * The behaviour is undefined if the type `Key` of the `robin_set` is not the
631 * same as the type used during serialization.
632 *
633 * The implementation leaves binary compatibility (endianness, IEEE 754 for
634 * floats, size of int, ...) of the types it deserializes in the hands of the
635 * `Deserializer` function object if compatibility is required.
636 */
637 template <class Deserializer>
638 static robin_set deserialize(Deserializer &deserializer, bool hash_compatible = false)
639 {
640 robin_set set(0);
641 set.m_ht.deserialize(deserializer, hash_compatible);
642
643 return set;
644 }
645
646 friend bool operator!=(const robin_set &lhs, const robin_set &rhs)
647 {
648 return !operator==(lhs, rhs);
649 }
650
651 friend void swap(robin_set &lhs, robin_set &rhs) { lhs.swap(rhs); }
652
653 private:
655 };
656
657 /**
658 * Same as `tsl::robin_set<Key, Hash, KeyEqual, Allocator, StoreHash,
659 * tsl::rh::prime_growth_policy>`.
660 */
661 template <class Key, class Hash = std::hash<Key>, class KeyEqual = std::equal_to<Key>,
662 class Allocator = std::allocator<Key>, bool StoreHash = false>
665
666} // end namespace tsl
667
668#endif
Definition robin_hash.h:365
key_equal key_eq() const
Definition robin_hash.h:1073
static const size_type DEFAULT_INIT_BUCKETS_SIZE
Definition robin_hash.h:1508
iterator find(const K &key)
Definition robin_hash.h:972
Hash hasher
Definition robin_hash.h:382
const value_type * const_pointer
Definition robin_hash.h:388
iterator begin() noexcept
Definition robin_hash.h:664
bool empty() const noexcept
Definition robin_hash.h:695
typename KeySelect::key_type key_type
Definition robin_hash.h:378
float min_load_factor() const
Definition robin_hash.h:1041
KeyEqual key_equal
Definition robin_hash.h:383
std::pair< iterator, bool > insert(P &&value)
Definition robin_hash.h:719
hasher hash_function() const
Definition robin_hash.h:1071
value_type * pointer
Definition robin_hash.h:387
value_type & reference
Definition robin_hash.h:385
void rehash(size_type my_count)
Definition robin_hash.h:1057
void serialize(Serializer &serializer) const
Definition robin_hash.h:1083
bool contains(const K &key) const
Definition robin_hash.h:989
std::ptrdiff_t difference_type
Definition robin_hash.h:381
std::pair< iterator, bool > emplace(Args &&...args)
Definition robin_hash.h:773
iterator insert_hint(const_iterator hint, P &&value)
Definition robin_hash.h:724
size_type max_size() const noexcept
Definition robin_hash.h:699
const_iterator cbegin() const noexcept
Definition robin_hash.h:676
allocator_type get_allocator() const
Definition robin_hash.h:659
ValueType value_type
Definition robin_hash.h:379
robin_iterator< false > iterator
Definition robin_hash.h:389
float load_factor() const
Definition robin_hash.h:1032
const value_type & const_reference
Definition robin_hash.h:386
iterator erase(iterator pos)
Definition robin_hash.h:803
size_type bucket_count() const
Definition robin_hash.h:1022
void deserialize(Deserializer &deserializer, bool hash_compatible)
Definition robin_hash.h:1088
void swap(robin_hash &other)
Definition robin_hash.h:897
size_type count(const K &key) const
Definition robin_hash.h:960
const_iterator cend() const noexcept
Definition robin_hash.h:690
iterator end() noexcept
Definition robin_hash.h:686
float max_load_factor() const
Definition robin_hash.h:1043
size_type size() const noexcept
Definition robin_hash.h:697
std::pair< iterator, iterator > equal_range(const K &key)
Definition robin_hash.h:996
robin_iterator< true > const_iterator
Definition robin_hash.h:390
std::size_t size_type
Definition robin_hash.h:380
void reserve(size_type my_count)
Definition robin_hash.h:1063
iterator mutable_iterator(const_iterator pos)
Definition robin_hash.h:1078
Allocator allocator_type
Definition robin_hash.h:384
size_type max_bucket_count() const
Definition robin_hash.h:1024
iterator emplace_hint(const_iterator hint, Args &&...args)
Definition robin_hash.h:778
void clear() noexcept
Definition robin_hash.h:704
Definition robin_set.h:95
key_type & operator()(Key &key) noexcept
Definition robin_set.h:101
Key key_type
Definition robin_set.h:97
const key_type & operator()(const Key &key) const noexcept
Definition robin_set.h:99
Definition robin_set.h:90
std::pair< iterator, bool > insert(const value_type &value)
Definition robin_set.h:221
std::pair< const_iterator, const_iterator > equal_range(const Key &key, std::size_t precalculated_hash) const
Definition robin_set.h:480
robin_set(InputIt first, InputIt last, size_type bucket_count, const Allocator &alloc)
Definition robin_set.h:155
ht m_ht
Definition robin_set.h:654
size_type count(const Key &key) const
Definition robin_set.h:312
iterator erase(iterator pos)
Definition robin_set.h:266
typename ht::pointer pointer
Definition robin_set.h:117
const_iterator find(const K &key) const
Definition robin_set.h:403
robin_set(size_type bucket_count, const Hash &hash=Hash(), const KeyEqual &equal=KeyEqual(), const Allocator &alloc=Allocator())
Definition robin_set.h:127
const_iterator find(const K &key, std::size_t precalculated_hash) const
Definition robin_set.h:417
const_iterator find(const Key &key) const
Definition robin_set.h:362
robin_set(std::initializer_list< value_type > init, size_type bucket_count, const Allocator &alloc)
Definition robin_set.h:174
iterator erase(const_iterator first, const_iterator last)
Definition robin_set.h:268
bool empty() const noexcept
Definition robin_set.h:212
void reserve(size_type my_count)
Definition robin_set.h:560
typename ht::hasher hasher
Definition robin_set.h:112
typename ht::const_reference const_reference
Definition robin_set.h:116
const_iterator cbegin() const noexcept
Definition robin_set.h:203
iterator insert(const_iterator hint, const value_type &value)
Definition robin_set.h:225
robin_set()
Definition robin_set.h:125
size_type max_size() const noexcept
Definition robin_set.h:214
void max_load_factor(float ml)
Definition robin_set.h:557
iterator insert(const_iterator hint, value_type &&value)
Definition robin_set.h:230
void serialize(Serializer &serializer) const
Definition robin_set.h:606
size_type erase(const key_type &key, std::size_t precalculated_hash)
Definition robin_set.h:276
iterator begin() noexcept
Definition robin_set.h:201
float load_factor() const
Definition robin_set.h:542
typename ht::size_type size_type
Definition robin_set.h:110
friend bool operator==(const robin_set &lhs, const robin_set &rhs)
Definition robin_set.h:577
std::pair< const_iterator, const_iterator > equal_range(const K &key, std::size_t precalculated_hash) const
Definition robin_set.h:527
std::pair< iterator, bool > emplace(Args &&...args)
Definition robin_set.h:249
robin_set(InputIt first, InputIt last, size_type bucket_count, const Hash &hash, const Allocator &alloc)
Definition robin_set.h:161
typename ht::const_iterator const_iterator
Definition robin_set.h:120
iterator find(const K &key, std::size_t precalculated_hash)
Definition robin_set.h:393
robin_set(size_type bucket_count, const Hash &hash, const Allocator &alloc)
Definition robin_set.h:138
size_type erase(const key_type &key)
Definition robin_set.h:269
iterator find(const Key &key)
Definition robin_set.h:350
void rehash(size_type my_count)
Definition robin_set.h:559
typename ht::value_type value_type
Definition robin_set.h:109
size_type erase(const K &key)
Definition robin_set.h:288
typename ht::reference reference
Definition robin_set.h:115
const_iterator find(const Key &key, std::size_t precalculated_hash) const
Definition robin_set.h:367
iterator find(const Key &key, std::size_t precalculated_hash)
Definition robin_set.h:357
friend bool operator!=(const robin_set &lhs, const robin_set &rhs)
Definition robin_set.h:646
key_equal key_eq() const
Definition robin_set.h:566
std::pair< const_iterator, const_iterator > equal_range(const K &key) const
Definition robin_set.h:517
typename ht::iterator iterator
Definition robin_set.h:119
iterator end() noexcept
Definition robin_set.h:205
typename ht::key_equal key_equal
Definition robin_set.h:113
void swap(robin_set &other)
Definition robin_set.h:307
std::pair< iterator, iterator > equal_range(const K &key, std::size_t precalculated_hash)
Definition robin_set.h:507
robin_set & operator=(std::initializer_list< value_type > ilist)
Definition robin_set.h:186
void min_load_factor(float ml)
Definition robin_set.h:556
typename ht::key_type key_type
Definition robin_set.h:108
size_type count(const K &key) const
Definition robin_set.h:331
size_type bucket_count() const
Definition robin_set.h:536
iterator erase(const_iterator pos)
Definition robin_set.h:267
std::pair< const_iterator, const_iterator > equal_range(const Key &key) const
Definition robin_set.h:472
size_type count(const K &key, std::size_t precalculated_hash) const
Definition robin_set.h:345
const_iterator cend() const noexcept
Definition robin_set.h:207
iterator emplace_hint(const_iterator hint, Args &&...args)
Definition robin_set.h:261
std::pair< iterator, iterator > equal_range(const Key &key)
Definition robin_set.h:460
bool contains(const K &key) const
Definition robin_set.h:441
const_iterator begin() const noexcept
Definition robin_set.h:202
const_iterator end() const noexcept
Definition robin_set.h:206
friend void swap(robin_set &lhs, robin_set &rhs)
Definition robin_set.h:651
robin_set(size_type bucket_count, const Allocator &alloc)
Definition robin_set.h:133
allocator_type get_allocator() const
Definition robin_set.h:196
std::pair< iterator, iterator > equal_range(const K &key)
Definition robin_set.h:493
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:167
iterator find(const K &key)
Definition robin_set.h:379
typename ht::const_pointer const_pointer
Definition robin_set.h:118
size_type erase(const K &key, std::size_t precalculated_hash)
Definition robin_set.h:302
typename ht::allocator_type allocator_type
Definition robin_set.h:114
std::pair< iterator, iterator > equal_range(const Key &key, std::size_t precalculated_hash)
Definition robin_set.h:467
float min_load_factor() const
Definition robin_set.h:544
robin_set(const Allocator &alloc)
Definition robin_set.h:143
typename ht::difference_type difference_type
Definition robin_set.h:111
void insert(std::initializer_list< value_type > ilist)
Definition robin_set.h:237
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:146
bool contains(const Key &key, std::size_t precalculated_hash) const
Definition robin_set.h:429
void insert(InputIt first, InputIt last)
Definition robin_set.h:235
bool contains(const Key &key) const
Definition robin_set.h:422
iterator mutable_iterator(const_iterator pos)
Definition robin_set.h:575
robin_set(std::initializer_list< value_type > init, size_type bucket_count, const Hash &hash, const Allocator &alloc)
Definition robin_set.h:180
bool contains(const K &key, std::size_t precalculated_hash) const
Definition robin_set.h:455
void clear() noexcept
Definition robin_set.h:219
size_type count(const Key &key, std::size_t precalculated_hash) const
Definition robin_set.h:319
size_type max_bucket_count() const
Definition robin_set.h:537
size_type size() const noexcept
Definition robin_set.h:213
hasher hash_function() const
Definition robin_set.h:565
float max_load_factor() const
Definition robin_set.h:545
std::pair< iterator, bool > insert(value_type &&value)
Definition robin_set.h:223
static robin_set deserialize(Deserializer &deserializer, bool hash_compatible=false)
Definition robin_set.h:638
Definition bhopscotch_map.h:38