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;
};

For [`std::unordered_map`](http://en.cppreference.com/w/cpp/container/unordered_map) you must specialize [`std::hash`](http://en.cppreference.com/w/cpp/utility/hash) for the key. — Some programmer dude, Apr 27 '18 at 15:32
If you look at the existing [standard specializations for library types](http://en.cppreference.com/w/cpp/utility/hash#Standard_specializations_for_library_types) you will see many specialization for classes that are templates. If you look closer at them I'm sure you will figure out how to do it. — Some programmer dude, Apr 27 '18 at 15:38
@benjist Same way `operator<` is possible for a template type: it needs to be implemented for the actual concrete type that eventually gets used as a template argument. — aschepler, Apr 27 '18 at 22:43

gchen · Answer 1 · 2018-04-27T22:33:20.867

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.

score 3 · Answer 2 · answered Apr 27 '18 at 22:57

Instead of std::map I'd like to use std::unordered_map for performance reasons.

That's not good enough, std::unordered_map is still slow; see this answer of mine and the links there.

But there's more: Actually, any general-purpose map structure is wrong for you, fundamentally and before having considered implementation quality. You see, since you may have multiple observers per event, the relevant data structure is a std::multimap, or for the unordered case, an std::unordered_multimap. I can't speak to the implementation quality, but I would bet it would be faster for you to use std::unordered_multimap over an std::unrodered_map-of-vectors.

PS - Everything the commenters and @gchen's answer have told you is basically valid for multimap-vs-unordered-multimap as well. You need to specialize std::hash, and the two structures' internals are very different.

Mapping objects as key with unordered_map

2 Answers2