24#ifndef PXR_TSL_ROBIN_MAP_H
25#define PXR_TSL_ROBIN_MAP_H
29#include <initializer_list>
34#include "robin_hash.h"
39PXR_NAMESPACE_OPEN_SCOPE
91template <
class Key,
class T,
class Hash = std::hash<Key>,
92 class KeyEqual = std::equal_to<Key>,
93 class Allocator = std::allocator<std::pair<Key, T>>,
94 bool StoreHash = false,
95 class GrowthPolicy = pxr_tsl::rh::power_of_two_growth_policy<2>>
99 using has_is_transparent = pxr_tsl::detail_robin_hash::has_is_transparent<U>;
103 using key_type = Key;
105 const key_type& operator()(
const std::pair<Key, T>& key_value)
const
107 return key_value.first;
110 key_type& operator()(std::pair<Key, T>& key_value)
noexcept {
111 return key_value.first;
117 using value_type = T;
119 const value_type& operator()(
const std::pair<Key, T>& key_value)
const
121 return key_value.second;
124 value_type& operator()(std::pair<Key, T>& key_value)
noexcept {
125 return key_value.second;
130 ValueSelect, Hash, KeyEqual,
131 Allocator, StoreHash, GrowthPolicy>;
134 using key_type =
typename ht::key_type;
135 using mapped_type = T;
136 using value_type =
typename ht::value_type;
137 using size_type =
typename ht::size_type;
138 using difference_type =
typename ht::difference_type;
139 using hasher =
typename ht::hasher;
140 using key_equal =
typename ht::key_equal;
141 using allocator_type =
typename ht::allocator_type;
142 using reference =
typename ht::reference;
143 using const_reference =
typename ht::const_reference;
144 using pointer =
typename ht::pointer;
145 using const_pointer =
typename ht::const_pointer;
155 explicit robin_map(size_type bucket_count,
const Hash& hash = Hash(),
156 const KeyEqual& equal = KeyEqual(),
157 const Allocator& alloc = Allocator())
158 : m_ht(bucket_count, hash, equal, alloc) {}
160 robin_map(size_type bucket_count,
const Allocator& alloc)
161 :
robin_map(bucket_count, Hash(), KeyEqual(), alloc) {}
163 robin_map(size_type bucket_count,
const Hash& hash,
const Allocator& alloc)
164 :
robin_map(bucket_count, hash, KeyEqual(), alloc) {}
166 explicit robin_map(
const Allocator& alloc)
167 :
robin_map(ht::DEFAULT_INIT_BUCKETS_SIZE, alloc) {}
169 template <
class InputIt>
171 size_type bucket_count = ht::DEFAULT_INIT_BUCKETS_SIZE,
172 const Hash& hash = Hash(),
const KeyEqual& equal = KeyEqual(),
173 const Allocator& alloc = Allocator())
174 :
robin_map(bucket_count, hash, equal, alloc) {
178 template <
class InputIt>
179 robin_map(InputIt first, InputIt last, size_type bucket_count,
180 const Allocator& alloc)
181 :
robin_map(first, last, bucket_count, Hash(), KeyEqual(), alloc) {}
183 template <
class InputIt>
184 robin_map(InputIt first, InputIt last, size_type bucket_count,
185 const Hash& hash,
const Allocator& alloc)
186 :
robin_map(first, last, bucket_count, hash, KeyEqual(), alloc) {}
188 robin_map(std::initializer_list<value_type> init,
189 size_type bucket_count = ht::DEFAULT_INIT_BUCKETS_SIZE,
190 const Hash& hash = Hash(),
const KeyEqual& equal = KeyEqual(),
191 const Allocator& alloc = Allocator())
192 :
robin_map(init.begin(), init.end(), bucket_count, hash, equal, alloc) {}
194 robin_map(std::initializer_list<value_type> init, size_type bucket_count,
195 const Allocator& alloc)
196 :
robin_map(init.begin(), init.end(), bucket_count, Hash(), KeyEqual(),
199 robin_map(std::initializer_list<value_type> init, size_type bucket_count,
200 const Hash& hash,
const Allocator& alloc)
201 :
robin_map(init.begin(), init.end(), bucket_count, hash, KeyEqual(),
204 robin_map& operator=(std::initializer_list<value_type> ilist) {
207 m_ht.reserve(ilist.size());
208 m_ht.insert(ilist.begin(), ilist.end());
213 allocator_type get_allocator()
const {
return m_ht.get_allocator(); }
218 iterator begin()
noexcept {
return m_ht.begin(); }
219 const_iterator begin()
const noexcept {
return m_ht.begin(); }
220 const_iterator cbegin()
const noexcept {
return m_ht.cbegin(); }
222 iterator end()
noexcept {
return m_ht.end(); }
223 const_iterator end()
const noexcept {
return m_ht.end(); }
224 const_iterator cend()
const noexcept {
return m_ht.cend(); }
229 bool empty()
const noexcept {
return m_ht.empty(); }
230 size_type size()
const noexcept {
return m_ht.size(); }
231 size_type max_size()
const noexcept {
return m_ht.max_size(); }
236 void clear()
noexcept { m_ht.clear(); }
238 std::pair<iterator, bool> insert(
const value_type& value) {
239 return m_ht.insert(value);
242 template <
class P,
typename std::enable_if<std::is_constructible<
243 value_type, P&&>::value>::type* =
nullptr>
244 std::pair<iterator, bool> insert(P&& value) {
245 return m_ht.emplace(std::forward<P>(value));
248 std::pair<iterator, bool> insert(value_type&& value) {
249 return m_ht.insert(std::move(value));
252 iterator insert(const_iterator hint,
const value_type& value) {
253 return m_ht.insert_hint(hint, value);
256 template <
class P,
typename std::enable_if<std::is_constructible<
257 value_type, P&&>::value>::type* =
nullptr>
258 iterator insert(const_iterator hint, P&& value) {
259 return m_ht.emplace_hint(hint, std::forward<P>(value));
262 iterator insert(const_iterator hint, value_type&& value) {
263 return m_ht.insert_hint(hint, std::move(value));
266 template <
class InputIt>
267 void insert(InputIt first, InputIt last) {
268 m_ht.insert(first, last);
271 void insert(std::initializer_list<value_type> ilist) {
272 m_ht.insert(ilist.begin(), ilist.end());
276 std::pair<iterator, bool> insert_or_assign(
const key_type& k, M&& obj) {
277 return m_ht.insert_or_assign(k, std::forward<M>(obj));
281 std::pair<iterator, bool> insert_or_assign(key_type&& k, M&& obj) {
282 return m_ht.insert_or_assign(std::move(k), std::forward<M>(obj));
286 iterator insert_or_assign(const_iterator hint,
const key_type& k, M&& obj) {
287 return m_ht.insert_or_assign(hint, k, std::forward<M>(obj));
291 iterator insert_or_assign(const_iterator hint, key_type&& k, M&& obj) {
292 return m_ht.insert_or_assign(hint, std::move(k), std::forward<M>(obj));
302 template <
class... Args>
303 std::pair<iterator, bool>
emplace(Args&&... args) {
304 return m_ht.emplace(std::forward<Args>(args)...);
314 template <
class... Args>
316 return m_ht.emplace_hint(hint, std::forward<Args>(args)...);
319 template <
class... Args>
320 std::pair<iterator, bool> try_emplace(
const key_type& k, Args&&... args) {
321 return m_ht.try_emplace(k, std::forward<Args>(args)...);
324 template <
class... Args>
325 std::pair<iterator, bool> try_emplace(key_type&& k, Args&&... args) {
326 return m_ht.try_emplace(std::move(k), std::forward<Args>(args)...);
329 template <
class... Args>
330 iterator try_emplace(const_iterator hint,
const key_type& k, Args&&... args) {
331 return m_ht.try_emplace_hint(hint, k, std::forward<Args>(args)...);
334 template <
class... Args>
335 iterator try_emplace(const_iterator hint, key_type&& k, Args&&... args) {
336 return m_ht.try_emplace_hint(hint, std::move(k),
337 std::forward<Args>(args)...);
340 iterator erase(iterator pos) {
return m_ht.
erase(pos); }
341 iterator erase(const_iterator pos) {
return m_ht.
erase(pos); }
342 iterator erase(const_iterator first, const_iterator last) {
343 return m_ht.
erase(first, last);
345 size_type erase(
const key_type& key) {
return m_ht.
erase(key); }
352 size_type
erase(
const key_type& key, std::size_t precalculated_hash) {
353 return m_ht.
erase(key, precalculated_hash);
362 class K,
class KE = KeyEqual,
363 typename std::enable_if<has_is_transparent<KE>::value>::type* =
nullptr>
365 return m_ht.
erase(key);
376 class K,
class KE = KeyEqual,
377 typename std::enable_if<has_is_transparent<KE>::value>::type* =
nullptr>
378 size_type
erase(
const K& key, std::size_t precalculated_hash) {
379 return m_ht.
erase(key, precalculated_hash);
382 void swap(
robin_map& other) { other.m_ht.swap(m_ht); }
387 T& at(
const Key& key) {
return m_ht.at(key); }
394 T&
at(
const Key& key, std::size_t precalculated_hash) {
395 return m_ht.at(key, precalculated_hash);
398 const T& at(
const Key& key)
const {
return m_ht.at(key); }
403 const T&
at(
const Key& key, std::size_t precalculated_hash)
const {
404 return m_ht.at(key, precalculated_hash);
413 class K,
class KE = KeyEqual,
414 typename std::enable_if<has_is_transparent<KE>::value>::type* =
nullptr>
415 T&
at(
const K& key) {
427 class K,
class KE = KeyEqual,
428 typename std::enable_if<has_is_transparent<KE>::value>::type* =
nullptr>
429 T&
at(
const K& key, std::size_t precalculated_hash) {
430 return m_ht.at(key, precalculated_hash);
437 class K,
class KE = KeyEqual,
438 typename std::enable_if<has_is_transparent<KE>::value>::type* =
nullptr>
439 const T&
at(
const K& key)
const {
447 class K,
class KE = KeyEqual,
448 typename std::enable_if<has_is_transparent<KE>::value>::type* =
nullptr>
449 const T&
at(
const K& key, std::size_t precalculated_hash)
const {
450 return m_ht.at(key, precalculated_hash);
453 T& operator[](
const Key& key) {
return m_ht[key]; }
454 T& operator[](Key&& key) {
return m_ht[std::move(key)]; }
456 size_type count(
const Key& key)
const {
return m_ht.count(key); }
463 size_type
count(
const Key& key, std::size_t precalculated_hash)
const {
464 return m_ht.count(key, precalculated_hash);
473 class K,
class KE = KeyEqual,
474 typename std::enable_if<has_is_transparent<KE>::value>::type* =
nullptr>
475 size_type
count(
const K& key)
const {
476 return m_ht.count(key);
487 class K,
class KE = KeyEqual,
488 typename std::enable_if<has_is_transparent<KE>::value>::type* =
nullptr>
489 size_type
count(
const K& key, std::size_t precalculated_hash)
const {
490 return m_ht.count(key, precalculated_hash);
493 iterator find(
const Key& key) {
return m_ht.find(key); }
500 iterator
find(
const Key& key, std::size_t precalculated_hash) {
501 return m_ht.find(key, precalculated_hash);
504 const_iterator find(
const Key& key)
const {
return m_ht.find(key); }
509 const_iterator
find(
const Key& key, std::size_t precalculated_hash)
const {
510 return m_ht.find(key, precalculated_hash);
519 class K,
class KE = KeyEqual,
520 typename std::enable_if<has_is_transparent<KE>::value>::type* =
nullptr>
522 return m_ht.find(key);
533 class K,
class KE = KeyEqual,
534 typename std::enable_if<has_is_transparent<KE>::value>::type* =
nullptr>
535 iterator
find(
const K& key, std::size_t precalculated_hash) {
536 return m_ht.find(key, precalculated_hash);
543 class K,
class KE = KeyEqual,
544 typename std::enable_if<has_is_transparent<KE>::value>::type* =
nullptr>
545 const_iterator
find(
const K& key)
const {
546 return m_ht.find(key);
557 class K,
class KE = KeyEqual,
558 typename std::enable_if<has_is_transparent<KE>::value>::type* =
nullptr>
559 const_iterator
find(
const K& key, std::size_t precalculated_hash)
const {
560 return m_ht.find(key, precalculated_hash);
563 bool contains(
const Key& key)
const {
return m_ht.contains(key); }
570 bool contains(
const Key& key, std::size_t precalculated_hash)
const {
571 return m_ht.contains(key, precalculated_hash);
580 class K,
class KE = KeyEqual,
581 typename std::enable_if<has_is_transparent<KE>::value>::type* =
nullptr>
583 return m_ht.contains(key);
594 class K,
class KE = KeyEqual,
595 typename std::enable_if<has_is_transparent<KE>::value>::type* =
nullptr>
596 bool contains(
const K& key, std::size_t precalculated_hash)
const {
597 return m_ht.contains(key, precalculated_hash);
600 std::pair<iterator, iterator> equal_range(
const Key& key) {
601 return m_ht.equal_range(key);
610 std::size_t precalculated_hash) {
611 return m_ht.equal_range(key, precalculated_hash);
614 std::pair<const_iterator, const_iterator> equal_range(
const Key& key)
const {
615 return m_ht.equal_range(key);
622 const Key& key, std::size_t precalculated_hash)
const {
623 return m_ht.equal_range(key, precalculated_hash);
632 class K,
class KE = KeyEqual,
633 typename std::enable_if<has_is_transparent<KE>::value>::type* =
nullptr>
635 return m_ht.equal_range(key);
646 class K,
class KE = KeyEqual,
647 typename std::enable_if<has_is_transparent<KE>::value>::type* =
nullptr>
649 std::size_t precalculated_hash) {
650 return m_ht.equal_range(key, precalculated_hash);
657 class K,
class KE = KeyEqual,
658 typename std::enable_if<has_is_transparent<KE>::value>::type* =
nullptr>
659 std::pair<const_iterator, const_iterator>
equal_range(
const K& key)
const {
660 return m_ht.equal_range(key);
667 class K,
class KE = KeyEqual,
668 typename std::enable_if<has_is_transparent<KE>::value>::type* =
nullptr>
670 const K& key, std::size_t precalculated_hash)
const {
671 return m_ht.equal_range(key, precalculated_hash);
677 size_type bucket_count()
const {
return m_ht.bucket_count(); }
678 size_type max_bucket_count()
const {
return m_ht.max_bucket_count(); }
683 float load_factor()
const {
return m_ht.load_factor(); }
685 float min_load_factor()
const {
return m_ht.min_load_factor(); }
686 float max_load_factor()
const {
return m_ht.max_load_factor(); }
698 void max_load_factor(
float ml) { m_ht.max_load_factor(ml); }
700 void rehash(size_type count_) { m_ht.rehash(count_); }
701 void reserve(size_type count_) { m_ht.reserve(count_); }
706 hasher hash_function()
const {
return m_ht.hash_function(); }
707 key_equal key_eq()
const {
return m_ht.key_eq(); }
717 return m_ht.mutable_iterator(pos);
733 template <
class Serializer>
735 m_ht.serialize(serializer);
764 template <
class Deserializer>
766 bool hash_compatible =
false) {
768 map.m_ht.deserialize(deserializer, hash_compatible);
774 if (lhs.size() != rhs.size()) {
778 for (
const auto& element_lhs : lhs) {
779 const auto it_element_rhs = rhs.find(element_lhs.first);
780 if (it_element_rhs == rhs.cend() ||
781 element_lhs.second != it_element_rhs->second) {
789 friend bool operator!=(
const robin_map& lhs,
const robin_map& rhs) {
790 return !operator==(lhs, rhs);
793 friend void swap(robin_map& lhs, robin_map& rhs) { lhs.swap(rhs); }
803template <
class Key,
class T,
class Hash = std::hash<Key>,
804 class KeyEqual = std::equal_to<Key>,
805 class Allocator = std::allocator<std::pair<Key, T>>,
806 bool StoreHash = false>
812PXR_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 map 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.
static robin_map deserialize(Deserializer &deserializer, bool hash_compatible=false)
Deserialize a previously serialized map through the deserializer parameter.
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...
const T & at(const K &key, std::size_t precalculated_hash) 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 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.
T & at(const K &key)
This overload only participates in the overload resolution if the typedef KeyEqual::is_transparent ex...
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.
T & at(const K &key, std::size_t precalculated_hash)
This overload only participates in the overload resolution if the typedef KeyEqual::is_transparent ex...
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...
const T & at(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.
size_type erase(const K &key)
This overload only participates in the overload resolution if the typedef KeyEqual::is_transparent ex...
const T & at(const Key &key, std::size_t precalculated_hash) const
Use the hash value 'precalculated_hash' instead of hashing the key.
T & at(const Key &key, std::size_t precalculated_hash)
Use the hash value 'precalculated_hash' instead of hashing the key.
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 map through the serializer parameter.