24#ifndef PXR_TSL_ROBIN_SET_H
25#define PXR_TSL_ROBIN_SET_H
29#include <initializer_list>
34#include "robin_hash.h"
39PXR_NAMESPACE_OPEN_SCOPE
91template <
class Key,
class Hash = std::hash<Key>,
92 class KeyEqual = std::equal_to<Key>,
93 class Allocator = std::allocator<Key>,
bool StoreHash = false,
94 class GrowthPolicy = pxr_tsl::rh::power_of_two_growth_policy<2>>
98 using has_is_transparent = pxr_tsl::detail_robin_hash::has_is_transparent<U>;
102 using key_type = Key;
104 const key_type& operator()(
const Key& key)
const noexcept {
return key; }
106 key_type& operator()(Key& key)
noexcept {
return key; }
110 Allocator, StoreHash, GrowthPolicy>;
113 using key_type =
typename ht::key_type;
114 using value_type =
typename ht::value_type;
115 using size_type =
typename ht::size_type;
116 using difference_type =
typename ht::difference_type;
117 using hasher =
typename ht::hasher;
118 using key_equal =
typename ht::key_equal;
119 using allocator_type =
typename ht::allocator_type;
120 using reference =
typename ht::reference;
121 using const_reference =
typename ht::const_reference;
122 using pointer =
typename ht::pointer;
123 using const_pointer =
typename ht::const_pointer;
132 explicit robin_set(size_type bucket_count,
const Hash& hash = Hash(),
133 const KeyEqual& equal = KeyEqual(),
134 const Allocator& alloc = Allocator())
135 : m_ht(bucket_count, hash, equal, alloc) {}
137 robin_set(size_type bucket_count,
const Allocator& alloc)
138 :
robin_set(bucket_count, Hash(), KeyEqual(), alloc) {}
140 robin_set(size_type bucket_count,
const Hash& hash,
const Allocator& alloc)
141 :
robin_set(bucket_count, hash, KeyEqual(), alloc) {}
143 explicit robin_set(
const Allocator& alloc)
144 :
robin_set(ht::DEFAULT_INIT_BUCKETS_SIZE, alloc) {}
146 template <
class InputIt>
148 size_type bucket_count = ht::DEFAULT_INIT_BUCKETS_SIZE,
149 const Hash& hash = Hash(),
const KeyEqual& equal = KeyEqual(),
150 const Allocator& alloc = Allocator())
151 :
robin_set(bucket_count, hash, equal, alloc) {
155 template <
class InputIt>
156 robin_set(InputIt first, InputIt last, size_type bucket_count,
157 const Allocator& alloc)
158 :
robin_set(first, last, bucket_count, Hash(), KeyEqual(), alloc) {}
160 template <
class InputIt>
161 robin_set(InputIt first, InputIt last, size_type bucket_count,
162 const Hash& hash,
const Allocator& alloc)
163 :
robin_set(first, last, bucket_count, hash, KeyEqual(), alloc) {}
165 robin_set(std::initializer_list<value_type> init,
166 size_type bucket_count = ht::DEFAULT_INIT_BUCKETS_SIZE,
167 const Hash& hash = Hash(),
const KeyEqual& equal = KeyEqual(),
168 const Allocator& alloc = Allocator())
169 :
robin_set(init.begin(), init.end(), bucket_count, hash, equal, alloc) {}
171 robin_set(std::initializer_list<value_type> init, size_type bucket_count,
172 const Allocator& alloc)
173 :
robin_set(init.begin(), init.end(), bucket_count, Hash(), KeyEqual(),
176 robin_set(std::initializer_list<value_type> init, size_type bucket_count,
177 const Hash& hash,
const Allocator& alloc)
178 :
robin_set(init.begin(), init.end(), bucket_count, hash, KeyEqual(),
181 robin_set& operator=(std::initializer_list<value_type> ilist) {
184 m_ht.reserve(ilist.size());
185 m_ht.insert(ilist.begin(), ilist.end());
190 allocator_type get_allocator()
const {
return m_ht.get_allocator(); }
195 iterator begin()
noexcept {
return m_ht.begin(); }
196 const_iterator begin()
const noexcept {
return m_ht.begin(); }
197 const_iterator cbegin()
const noexcept {
return m_ht.cbegin(); }
199 iterator end()
noexcept {
return m_ht.end(); }
200 const_iterator end()
const noexcept {
return m_ht.end(); }
201 const_iterator cend()
const noexcept {
return m_ht.cend(); }
206 bool empty()
const noexcept {
return m_ht.empty(); }
207 size_type size()
const noexcept {
return m_ht.size(); }
208 size_type max_size()
const noexcept {
return m_ht.max_size(); }
213 void clear()
noexcept { m_ht.clear(); }
215 std::pair<iterator, bool> insert(
const value_type& value) {
216 return m_ht.insert(value);
219 std::pair<iterator, bool> insert(value_type&& value) {
220 return m_ht.insert(std::move(value));
223 iterator insert(const_iterator hint,
const value_type& value) {
224 return m_ht.insert_hint(hint, value);
227 iterator insert(const_iterator hint, value_type&& value) {
228 return m_ht.insert_hint(hint, std::move(value));
231 template <
class InputIt>
232 void insert(InputIt first, InputIt last) {
233 m_ht.insert(first, last);
236 void insert(std::initializer_list<value_type> ilist) {
237 m_ht.insert(ilist.begin(), ilist.end());
247 template <
class... Args>
248 std::pair<iterator, bool>
emplace(Args&&... args) {
249 return m_ht.emplace(std::forward<Args>(args)...);
259 template <
class... Args>
261 return m_ht.emplace_hint(hint, std::forward<Args>(args)...);
264 iterator erase(iterator pos) {
return m_ht.
erase(pos); }
265 iterator erase(const_iterator pos) {
return m_ht.
erase(pos); }
266 iterator erase(const_iterator first, const_iterator last) {
267 return m_ht.
erase(first, last);
269 size_type erase(
const key_type& key) {
return m_ht.
erase(key); }
277 void erase_fast(iterator pos) {
return m_ht.erase_fast(pos); }
284 size_type
erase(
const key_type& key, std::size_t precalculated_hash) {
285 return m_ht.
erase(key, precalculated_hash);
294 class K,
class KE = KeyEqual,
295 typename std::enable_if<has_is_transparent<KE>::value>::type* =
nullptr>
297 return m_ht.
erase(key);
308 class K,
class KE = KeyEqual,
309 typename std::enable_if<has_is_transparent<KE>::value>::type* =
nullptr>
310 size_type
erase(
const K& key, std::size_t precalculated_hash) {
311 return m_ht.
erase(key, precalculated_hash);
314 void swap(
robin_set& other) { other.m_ht.swap(m_ht); }
319 size_type count(
const Key& key)
const {
return m_ht.count(key); }
326 size_type
count(
const Key& key, std::size_t precalculated_hash)
const {
327 return m_ht.count(key, precalculated_hash);
336 class K,
class KE = KeyEqual,
337 typename std::enable_if<has_is_transparent<KE>::value>::type* =
nullptr>
338 size_type
count(
const K& key)
const {
339 return m_ht.count(key);
350 class K,
class KE = KeyEqual,
351 typename std::enable_if<has_is_transparent<KE>::value>::type* =
nullptr>
352 size_type
count(
const K& key, std::size_t precalculated_hash)
const {
353 return m_ht.count(key, precalculated_hash);
356 iterator find(
const Key& key) {
return m_ht.find(key); }
363 iterator
find(
const Key& key, std::size_t precalculated_hash) {
364 return m_ht.find(key, precalculated_hash);
367 const_iterator find(
const Key& key)
const {
return m_ht.find(key); }
372 const_iterator
find(
const Key& key, std::size_t precalculated_hash)
const {
373 return m_ht.find(key, precalculated_hash);
382 class K,
class KE = KeyEqual,
383 typename std::enable_if<has_is_transparent<KE>::value>::type* =
nullptr>
385 return m_ht.find(key);
396 class K,
class KE = KeyEqual,
397 typename std::enable_if<has_is_transparent<KE>::value>::type* =
nullptr>
398 iterator
find(
const K& key, std::size_t precalculated_hash) {
399 return m_ht.find(key, precalculated_hash);
406 class K,
class KE = KeyEqual,
407 typename std::enable_if<has_is_transparent<KE>::value>::type* =
nullptr>
408 const_iterator
find(
const K& key)
const {
409 return m_ht.find(key);
420 class K,
class KE = KeyEqual,
421 typename std::enable_if<has_is_transparent<KE>::value>::type* =
nullptr>
422 const_iterator
find(
const K& key, std::size_t precalculated_hash)
const {
423 return m_ht.find(key, precalculated_hash);
426 bool contains(
const Key& key)
const {
return m_ht.contains(key); }
433 bool contains(
const Key& key, std::size_t precalculated_hash)
const {
434 return m_ht.contains(key, precalculated_hash);
443 class K,
class KE = KeyEqual,
444 typename std::enable_if<has_is_transparent<KE>::value>::type* =
nullptr>
446 return m_ht.contains(key);
457 class K,
class KE = KeyEqual,
458 typename std::enable_if<has_is_transparent<KE>::value>::type* =
nullptr>
459 bool contains(
const K& key, std::size_t precalculated_hash)
const {
460 return m_ht.contains(key, precalculated_hash);
463 std::pair<iterator, iterator> equal_range(
const Key& key) {
464 return m_ht.equal_range(key);
473 std::size_t precalculated_hash) {
474 return m_ht.equal_range(key, precalculated_hash);
477 std::pair<const_iterator, const_iterator> equal_range(
const Key& key)
const {
478 return m_ht.equal_range(key);
485 const Key& key, std::size_t precalculated_hash)
const {
486 return m_ht.equal_range(key, precalculated_hash);
495 class K,
class KE = KeyEqual,
496 typename std::enable_if<has_is_transparent<KE>::value>::type* =
nullptr>
498 return m_ht.equal_range(key);
509 class K,
class KE = KeyEqual,
510 typename std::enable_if<has_is_transparent<KE>::value>::type* =
nullptr>
512 std::size_t precalculated_hash) {
513 return m_ht.equal_range(key, precalculated_hash);
520 class K,
class KE = KeyEqual,
521 typename std::enable_if<has_is_transparent<KE>::value>::type* =
nullptr>
522 std::pair<const_iterator, const_iterator>
equal_range(
const K& key)
const {
523 return m_ht.equal_range(key);
530 class K,
class KE = KeyEqual,
531 typename std::enable_if<has_is_transparent<KE>::value>::type* =
nullptr>
533 const K& key, std::size_t precalculated_hash)
const {
534 return m_ht.equal_range(key, precalculated_hash);
540 size_type bucket_count()
const {
return m_ht.bucket_count(); }
541 size_type max_bucket_count()
const {
return m_ht.max_bucket_count(); }
546 float load_factor()
const {
return m_ht.load_factor(); }
548 float min_load_factor()
const {
return m_ht.min_load_factor(); }
549 float max_load_factor()
const {
return m_ht.max_load_factor(); }
561 void max_load_factor(
float ml) { m_ht.max_load_factor(ml); }
563 void rehash(size_type count_) { m_ht.rehash(count_); }
564 void reserve(size_type count_) { m_ht.reserve(count_); }
569 hasher hash_function()
const {
return m_ht.hash_function(); }
570 key_equal key_eq()
const {
return m_ht.key_eq(); }
580 return m_ht.mutable_iterator(pos);
584 if (lhs.size() != rhs.size()) {
588 for (
const auto& element_lhs : lhs) {
589 const auto it_element_rhs = rhs.find(element_lhs);
590 if (it_element_rhs == rhs.cend()) {
611 template <
class Serializer>
613 m_ht.serialize(serializer);
642 template <
class Deserializer>
644 bool hash_compatible =
false) {
646 set.m_ht.deserialize(deserializer, hash_compatible);
652 return !operator==(lhs, rhs);
655 friend void swap(robin_set& lhs, robin_set& rhs) { lhs.swap(rhs); }
665template <
class Key,
class Hash = std::hash<Key>,
666 class KeyEqual = std::equal_to<Key>,
667 class Allocator = std::allocator<Key>,
bool StoreHash = false>
673PXR_NAMESPACE_CLOSE_SCOPE
The 'operator*()' and 'operator->()' methods return a const reference and const pointer respectively ...
Internal common class used by robin_map and robin_set.
iterator erase(iterator pos)
Here to avoid template<class K> size_type erase(const K& key) being used when we use an iterator inst...
Grow the hash table by using prime numbers as bucket count.
Implementation of a hash set using open-addressing and the robin hood hashing algorithm with backward...
std::pair< iterator, iterator > equal_range(const Key &key, std::size_t precalculated_hash)
Use the hash value 'precalculated_hash' instead of hashing the key.
bool contains(const Key &key, std::size_t precalculated_hash) const
Use the hash value 'precalculated_hash' instead of hashing the key.
const_iterator find(const K &key, std::size_t precalculated_hash) const
This overload only participates in the overload resolution if the typedef KeyEqual::is_transparent ex...
const_iterator find(const Key &key, std::size_t precalculated_hash) const
Use the hash value 'precalculated_hash' instead of hashing the key.
std::pair< const_iterator, const_iterator > equal_range(const K &key) const
This overload only participates in the overload resolution if the typedef KeyEqual::is_transparent ex...
void erase_fast(iterator pos)
Erase the element at position 'pos'.
std::pair< const_iterator, const_iterator > equal_range(const Key &key, std::size_t precalculated_hash) const
Use the hash value 'precalculated_hash' instead of hashing the key.
std::pair< iterator, iterator > equal_range(const K &key)
This overload only participates in the overload resolution if the typedef KeyEqual::is_transparent ex...
bool contains(const K &key, std::size_t precalculated_hash) const
This overload only participates in the overload resolution if the typedef KeyEqual::is_transparent ex...
void min_load_factor(float ml)
Set the min_load_factor to ml.
size_type count(const Key &key, std::size_t precalculated_hash) const
Use the hash value 'precalculated_hash' instead of hashing the key.
const_iterator find(const K &key) const
This overload only participates in the overload resolution if the typedef KeyEqual::is_transparent ex...
std::pair< const_iterator, const_iterator > equal_range(const K &key, std::size_t precalculated_hash) const
This overload only participates in the overload resolution if the typedef KeyEqual::is_transparent ex...
size_type erase(const key_type &key, std::size_t precalculated_hash)
Use the hash value 'precalculated_hash' instead of hashing the key.
iterator find(const Key &key, std::size_t precalculated_hash)
Use the hash value 'precalculated_hash' instead of hashing the key.
iterator mutable_iterator(const_iterator pos)
Convert a const_iterator to an iterator.
iterator emplace_hint(const_iterator hint, Args &&... args)
Due to the way elements are stored, emplace_hint will need to move or copy the key-value once.
iterator find(const K &key, std::size_t precalculated_hash)
This overload only participates in the overload resolution if the typedef KeyEqual::is_transparent ex...
bool contains(const K &key) const
This overload only participates in the overload resolution if the typedef KeyEqual::is_transparent ex...
size_type count(const K &key) const
This overload only participates in the overload resolution if the typedef KeyEqual::is_transparent ex...
std::pair< iterator, bool > emplace(Args &&... args)
Due to the way elements are stored, emplace will need to move or copy the key-value once.
static robin_set deserialize(Deserializer &deserializer, bool hash_compatible=false)
Deserialize a previously serialized set through the deserializer parameter.
size_type erase(const K &key)
This overload only participates in the overload resolution if the typedef KeyEqual::is_transparent ex...
iterator find(const K &key)
This overload only participates in the overload resolution if the typedef KeyEqual::is_transparent ex...
size_type erase(const K &key, std::size_t precalculated_hash)
This overload only participates in the overload resolution if the typedef KeyEqual::is_transparent ex...
std::pair< iterator, iterator > equal_range(const K &key, std::size_t precalculated_hash)
This overload only participates in the overload resolution if the typedef KeyEqual::is_transparent ex...
size_type count(const K &key, std::size_t precalculated_hash) const
This overload only participates in the overload resolution if the typedef KeyEqual::is_transparent ex...
void serialize(Serializer &serializer) const
Serialize the set through the serializer parameter.