使用unordered_map将对象映射为键

Question

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

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

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

Static_assert失败"指定的哈希不符合哈希要求"

我的期望是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无法创建 a。但是，您可以应用与上面 MyComp 相同的逻辑，并创建一个通用的 Event 哈希函数对象。例如

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

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

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;

当然，MyHashand的主体MyEqual应该足够通用，以便它可以适用于Event您要使用的所有或大部分类型。