c++ - 使用 unordered_map 将对象映射为键

Question

我有一个简单的 Observable 类，实现了观察者模式。此类将模板类型 Event 映射到已注册的观察者。这一切都很好，尽管出于性能原因我想使用 std::unordered_map 而不是 std::map。

如果我将下面的成员变量更改为使用 unordered_map，我会得到一个相当普遍的错误:

std::map<Event, std::vector<std::function<void()>>> _observers;

Static_assert failed "the specified hash does not meet the Hash requirements"

我的期望是 std::map 和 std::unordered_map 应该可以互换。在这种情况下使用 unordered_map 的散列要求是什么，为什么不同？

这是我的代码:

#include <functional>
#include <unordered_map>
#include <map>
#include <vector>
#include <utility>

template <typename Event>
class Observable
{
public:
    Observable()=default;

    template <typename Observer>
    void registerObserver(const Event &event, Observer &&observer)
    {
        _observers[event].push_back(std::forward<Observer>(observer));
    }

    template <typename Observer>
    void registerObserver(Event &&event, Observer &&observer)
    {
        _observers[std::move(event)].push_back(std::forward<Observer>(observer));
    }

    void notify(const Event &event) const
    {
        for (const auto& obs : _observers.at(event)) obs();
    }

    /* disallow copying */
    Observable(const Observable&)=delete;
    Observable& operator=(const Observable&)=delete;

private:
    std::map<Event, std::vector<std::function<void()>>> _observers;
};

Answer 1

std::map和 std::unordered_map不可互换。它们根本不同。

std::map 是使用自平衡二叉搜索树实现的，要形成 BST，您需要定义要如何比较键(它们是有序的)。例如std::map中的默认比较函数是std::less或本质上 operator< .所以你的Event类型必须定义 operator< (成员函数或非成员函数)。但是，如果需要，您可以通过在第三个模板参数中指定比较函数来将比较函数更改为其他函数。

例如

std::map<Event, std::vector<std::function<void()>>, MyComp<Event>> _observers;

和myComp可以是具有有效签名的任何合适的函数对象(仿函数、自由函数、lambda 函数)。例如

template <typename Event>
struct MyComp{
    bool operator()(const Event& lhs, const Event& rhs) const {
        ...
    }
};

另一方面，std::unordered_map使用哈希表实现。顾名思义，它们是无序的，因此不需要比较函数即可工作。但他们需要知道如何将一个键(默认为 std::hash )散列为一个无符号整数值(即 size_t )，以及如何判断两个键是否相同(默认为 operator== )。

如果Event是一些用户定义的类型，std::hash<Event>不管用。结果，std::unordered_map无法创建。但是，您可以应用与上述 MyComp 相同的逻辑，并创建一个通用的事件哈希函数对象。例如

template <typename Event>
struct MyHash {
    std::size_t operator()(const Event& key) const {
        ...
    }
};

如果你还想定义一个广义相等函数(即不使用事件类型的 operator==)，你可以做同样的事情。

template <typename Event>
struct MyEqual {
    bool operator() (const Event& lhs, const Event& rhs) const {
        ...
    }
};

然后定义unordered_map作为

std::unordered_map<Event, std::vector<std::function<void()>>,
                   MyHash<Event>, MyEqual<Event>> _observers;

当然还有 MyHash 的正文和 MyEqual应该足够通用，以便它可以适用于所有或大部分 Event您要使用的类型。