Как написать qHash для контейнера QSet <SomeClass *>?

Question

Мне нужно реализовать набор наборов в моем приложении. Использование QSet с пользовательским классом требует предоставления функции qHash() и operator==.

Код выглядит следующим образом:

    class Custom{
        int x;
        int y;
        //some other irrelevant here
    }
    inline uint qHash(Custom* c){
        return (qHash(c->x) ^ qHash(c->y));
    }
    bool operator==(Custom &c1, Custom &c2){
        return ((c1.x==c2.x) && (c1.y == c2.y));
    }

    //now I can use: QSet<Custom*>

Как мне реализовать qHash(QSet<Custom*>), чтобы можно было использовать QSet< QSet<SomeClass*> >?

Редактировать:

Дополнительный вопрос: В моем приложении «набор наборов» может содержать до 15000 наборов. В каждом подмножестве до 25 пользовательских указателей классов. Как гарантировать, что qHash(QSet<Custom*>) будет достаточно уникальным?

Answer 1

Вы не можете реализовать qHash с помощью boost::hash_range / boost::hash_combine (что фактически делает ответ pmr), потому что QSet является эквивалентом Qt std::unordered_set, и, так как Название STL предполагает, что эти контейнеры неупорядочены , тогда как Boost Documentation утверждает, что hash_combine зависит от порядка, то есть. он будет хешировать перестановки в различных хеш-значениях.

Это проблема, потому что если вы наивно хешируете элементы в сохраненном порядке Вы не можете гарантировать, что два набора, которые сравнивают равные, действительно равны, что является одним из требований хеш-функции:

For all x, y:   x == y => qHash(x) == qHash(y)

Таким образом, если вашей функции объединения хэшей необходимо произвести одинаковые выходные данные для любой перестановки входных значений, она должна быть коммутативной . К счастью, как (без знака) добавление, так и операция xor просто отвечают всем требованиям:

template <typename T>
inline uint qHash(const QSet<T> &set, uint seed=0) {
    return std::accumulate(set.begin(), set.end(), seed,
                           [](uint seed, const T&value) {
                               return seed + qHash(value); // or ^
                           });
}

Answer 2

Обычный способ хэширования контейнеров - это объединение хэшей всех элементов.Boost предоставляет hash_combine и hash_range для этой цели.Это должно дать вам представление о том, как реализовать это для результатов вашего qHash.

Итак, учитывая ваше qHash для Custom:

uint qHash(const QSet<Custom*>& c) {
  uint seed = 0;

  for(auto x : c) {
    seed ^= qHash(x) + 0x9e3779b9 + (seed << 6) + (seed >> 2);
  }

  return seed;
}