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

Question

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

У меня есть простой класс Observable, реализующий шаблон наблюдателя. Этот класс отображает тип шаблона Event для зарегистрированных наблюдателей. Это все хорошо, хотя вместо std :: map я бы хотел использовать std :: unordered_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;
};

5

c++c++11 observable

Решение

Другие решения

Вместо 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и внутренние структуры двух структур очень разные.

2

Источник

Accepted Answer

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

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

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

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 Тип, который вы хотите использовать.

2