Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Find a pointer T* in std::unordered_set<std::unique_ptr> (C++20)

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.

like image 267
Mikhail Avatar asked Oct 07 '20 11:10

Mikhail


People also ask

How to use unordered_set find () function in C++ STL?

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)

What is the use of value_type in unordered_set?

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.

What is unordered_set in C++?

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.

What is unordered set in Java?

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.


Video Answer


1 Answers

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>{}();
    }
}
like image 65
lubgr Avatar answered Oct 20 '22 11:10

lubgr