As pointed out in Using a std::unordered_set of std::unique_ptr, it is not easy to find a pointer T*
in std::unordered_set<std::unique_ptr<T>>
. Prior to C++20 we were forced to construct an instance of std::unique_ptr<T>
.
Thanks to the Heterogeneous lookup for unordered containers proposals (http://wg21.link/P0919r3 and http://wg21.link/p1690r1), this problem is solved in C++20. But the available solution looks quite clumsy to me (even by C++ standards). It seems like I need to implement from scratch not one, but two functors (for transparent hashing and for transparent comparison):
template<class T>
struct Equal {
using is_transparent = void;
bool operator()(const std::unique_ptr<T>& lhs, const std::unique_ptr<T>& rhs) const {
return lhs == rhs;
}
bool operator()(const std::unique_ptr<T>& lhs, const T* rhs) const {
return lhs.get() == rhs;
}
bool operator()(const T* lhs, const std::unique_ptr<T>& rhs) const {
return lhs == rhs.get();
}
};
template<class T>
struct Hash {
using is_transparent = void;
size_t operator()(const std::unique_ptr<T>& ptr) const {
return std::hash<const T*>()(ptr.get());
}
size_t operator()(const T* ptr) const {
return std::hash<const T*>()(ptr);
}
};
template<class T>
using UnorderedSetOfUniquePtrs = std::unordered_set<std::unique_ptr<T>, Hash<T>, Equal<T>>;
Demo: https://gcc.godbolt.org/z/bqx714 (the proposal is currently implemented only in MSVC).
This works but looks like A LOT of boilerplate. Am I missing something? Is there a way to use IDK maybe some standard transparent hasher or equality comparator? I see that std::equal_to<void>
is transparent, but I cannot use it directly. Maybe there is a sneaky way to define unique_ptr<T> -> T*
implicit conversion "just for this UnorderedSetOfUniquePtrs
class"? Your ideas are welcomed.
The unordered_set::find () function is a built-in function in C++ STL which is used to search for an element in the container. It returns an iterator to the element, if found else, it returns an iterator pointing to unordered_set::end (). Syntax : unordered_set_name .find (key)
In unordered_set containers it is the same as value_type, defined as an alias of the class's first template parameter ( Key ). An iterator to the element, if the specified value is found, or unordered_set::end if it is not found in the container.
Unordered Sets in C++ Standard Template Library. An unordered_set is implemented using a hash table where keys are hashed into indices of a hash table so that the insertion is always randomized.
Unordered set is an associative container that contains a set of unique objects of type Key. Search, insertion, and removal have average constant-time complexity. Internally, the elements are not sorted in any particular order, but organized into buckets. Which bucket an element is placed into depends entirely on the hash of its value.
You can shift the verbosity into std::to_address (thanks to @Caleth for pointing that out) and the existing std::hash
, which is specialized for std::unique_ptr
to return a hash based on the raw address (thanks to @Mikhail for the hint). Then, implement hash and equality types with member function templates (note how you no longer need the types themselves be templates):
struct Equal {
using is_transparent = void;
template<class U, class S>
bool operator()(const U& lhs, const S& rhs) const {
return std::to_address(lhs) == std::to_address(rhs);
}
};
struct Hash {
using is_transparent = void;
template<class U>
size_t operator()(const U& ptr) const {
return std::hash<U>{}();
}
}
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With