使用unordered_map将对象映射为键

Question

我有一个简单的Observable类，实现了观察者模式。这个类将模板类型Event映射到已注册的观察者。虽然使用std::map是可以的，但出于性能原因，我想使用std::unordered_map。

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

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

静态断言失败，“指定的哈希不满足哈希要求”

我原以为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;
};

- benjist

---

对于std::unordered_map，您必须为键专门化std::hash。 - Some programmer dude

使用模板类型，这怎么可能实现呢？ - benjist

如果您查看现有的库类型的标准特化，您会发现许多类的模板特化。如果您仔细查看它们，我相信您会弄清楚如何做到这一点。 - Some programmer dude

@benjist 同样的方式，对于模板类型也可以实现 operator<：它需要针对最终用作模板参数的实际具体类型进行实现。 - aschepler

Answer 1

std::map和std::unordered_map是不可互换的，它们本质上是不同的。

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

例如：

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

而 myComp 可以是任何适当的函数对象（functor、自由函数、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 相同的逻辑，并创建一个通用的 Event 哈希函数对象。例如：

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类型。

- gchen

Answer 2

出于性能原因，我想使用std::unordered_map而不是std::map。

但这还不够好，std::unordered_map仍然很慢；请参阅我的答案和其中的链接。

但更重要的是：实际上，任何通用映射结构都不适合你，从根本上来说，在考虑实现质量之前。你看，由于每个事件可能有多个观察者，所以相关数据结构是一个std::multimap，或者对于无序情况，是一个std::unordered_multimap。我不能确定实现质量，但我敢打赌，对于你来说，使用std::unordered_multimap比使用std::unrodered_map-of-vectors更快。

PS - 所有评论者和@gchen的答案告诉您的基本上也适用于multimap-vs-unordered-multimap。 您需要专门化std :: hash，而这两个结构的内部非常不同。

- einpoklum