Могу ли я использовать переменную-член в качестве ключа для hash_set / hash_map?

Question

У меня есть такой класс:

class Foo
{
   long long Id;
   string x;
   string y;
   // other member variables and functions
};

Я хотел бы сохранить это в hash_set (или hash_map), но использовать переменную-член Id в качестве ключа для вставки и поиска. Я не уверен, как я могу это сделать. Я думал о следующих способах, но ни один из них не очень хорош:

1) Я могу написать собственную хеш-функцию, которая будет хешировать объект с использованием идентификатора, но затем я не могу использовать метод find() в hash_set для поиска элемента по идентификатору (long long), поскольку потребует передачи объекта Foo.

2) Я могу продублировать Id и создать hash_map<long long, Foo> вместо hash_set<long long, Foo>, но у меня есть 100 миллионов экземпляров этих объектов, поэтому я бы не стал дублировать поле Id.

3) Я могу переместить поле Id за пределы Foo, а затем сделать hash_map<long long, Foo>, но это было бы немного грязно, поскольку Id используется внутренним классом, и было бы лучше оставить его с Foo.

Есть идеи? То, что я ищу, - это способ хранения Foo объектов, но возможность поиска их в hash_set с использованием long long (по идентификатору).

Спасибо!

Answer 1

Если вы не нашли реальное решение для контейнеров hash_set / hash_map, вы можете рассмотреть возможность использования реализации хеш-таблицы uthash , которая напрямую поддерживает ваш вариант использования. Хотя это C и он основан на макросах, но это одна из самых популярных реализаций хеш-таблиц, которые существуют.

Answer 2

У меня нет особого опыта в этом, но boost :: multiindex по умолчанию построен поверх boost :: hash и имеет явную поддержку для поиска объекта в хэше, используя только ключ, найденный в объекте..

Answer 3

1) Я могу написать собственную хеш-функцию, которая будет хешировать объект с помощью идентификатора, но затем я не могу использовать метод find () для hash_set для поиска элемента по Id (долго-долго), так как онпотребует передачи объекта Foo.

Это общая проблема со стандартной картой и установленными контейнерами.Добавьте конструктор или статический член, который создает объект сравнения, объект с действительным только ключевым элементом.

Answer 4

Вариант 2 - ваша лучшая ставка среди трех, которые вы дали.Если вы готовы, вы можете написать собственный hash_set (даже просто обертку вокруг обычного), чтобы предоставить то, что вы хотите.В этом случае я бы предпочел вариант 1. Вы можете легко добавить функцию поиска, которая принимает только значение ключа и адаптирует его для правильного использования внутренней функции поиска, предоставляя вам все преимущества.

Answer 5

Это может быть не очень элегантное решение, но оно работает: определите operator < (и operator ==, как и предложил CashCow) для вашего класса, который упорядочивает объекты на основе поля Id, а затемхотите сделать find, передать фиктивный объект, который содержит Id, который вы ищете.