Отображение объектов в качестве ключа с помощью unordered_map

Question

У меня есть простой класс Observable, реализующий шаблон наблюдателя. Этот класс отображает тип шаблона Event для зарегистрированных наблюдателей. Это все хорошо, хотя вместо std :: map я бы хотел использовать std :: unordered_map из соображений производительности.

Если я изменю переменную-член ниже, чтобы использовать unordered_map, я получу довольно общую ошибку:

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

Static_assert fail "указанный хеш не соответствует хешу требования "

Я ожидал, что 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::unordered_map все еще медленно; см этот ответ мой и ссылки там.

Но есть еще кое-что: на самом деле, любая структура карты общего назначения не подходит для вас , в принципе и до рассмотрения качества реализации. Видите ли, поскольку у вас может быть несколько наблюдателей на событие, соответствующей структурой данных является std::multimap, или для неупорядоченного случая - std::unordered_multimap. Я не могу говорить о качестве реализации, но могу поспорить, что для вас будет быстрее использовать std::unordered_multimap вместо std::unrodered_map -векторов.

PS - Все, что сказали вам комментаторы и ответ @ gchen, в основном относится и к multimap-vs-unordered-multimap. Вы должны специализироваться std::hash, и внутренние структуры двух структур очень разные.

Answer 2

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 могут быть любыми подходящими объектами функции (функтор, свободная функция, лямбда-функция) с действительными сигнатурами. * например 1016 *

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

С другой стороны, std::unordered_map реализован с использованием хеш-таблицы. Как и предполагает его название, они неупорядочены, поэтому им не нужны функции сравнения для работы. Но они должны знать, как хэшировать ключ (по умолчанию std::hash) в значение типа unsigned int (то есть 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== типа 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;

И, конечно, тело MyHash и MyEqual должно быть достаточно общим, чтобы оно могло работать для всех или большинства типов Event, которые вы хотите использовать.