Mapping objects as key with unordered_map

Question

I have a simple Observable class, implementing the observer pattern. This class maps a template type Event to registered observers. This is all fine, though instead of std::map I'd like to use std::unordered_map for performance reasons.

If I change the member variable below to use an unordered_map I get a rather generic error:

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

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

My expectation was that std::map and std::unordered_map should be interchangeable. What are the hashing requirements to use unordered_map in this case, and why is it different?

This is my code:

#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 and std::unordered_map are not interchangeable. They are fundamentally different.

std::map is implemented using a self-balanced binary search tree, and to form a BST, you need to define how you want the keys to be compared (They are ordered). For example, the default comparison function in std::map is std::less or essentially operator<. so Your Event type must define operator< (either a member function or a non-member function). However, You can change the comparison function to others if you want, by specifying the comparison function in the third template argument.

e.g.

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

And myComp can be any suitable function objects(functor, free function, lambda function) with valid signatures. e.g

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

On the other hand, std::unordered_map is implemented using a hash table. Just like its name suggested, they are unordered, so they do not need comparison functions to work. But they need to know how to hash a key (the default is std::hash) into an unsigned int value(i.e. size_t), and how to tell if two keys are the same(the default is operator==).

If Event is some user defined types, std::hash<Event> will not work. As the result, a std::unordered_map cannot be created. However, You can apply the same logic as MyComp above, and create a generalized Event hash function object. e.g.

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

And if you also want to define a generalized equal function(i.e. not using operator== of the Event type), You can do the same thing.

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

Then define the unordered_map as

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

And of course, the body of MyHash and MyEqual should be general enough so that it can work for all or most of the Event type you want to use.