QMap或QHash中的QSet

Question

我有QMap，我想让QSet成为它的关键，我不能这样做，因为QSet是不可比较的。例如：

QSet<int> intSet;
QMap<QSet<int>, char> charSet;

intSet.insert(1);
intSet.insert(2);
intSet.insert(3);

charSet.insert(intSet, '6');

有没有办法让它工作呢？如果我继承了QSet并定义了operator <，我应该如何实现它？即:比较的逻辑应该是什么？

注意:我太关心性能了

Answer 1

你似乎知道如何让它工作:定义一个operator<(const QSet<int>&)函数(我不相信Qt需要你对QSet进行子类化才能使它工作，我知道STL不需要)。

显然，在无序集上实现比较器将是困难的。而让它在恒定的时间内运行，我认为是不可能的。您可能会尝试先检查大小，然后以列表的形式对两个内容进行排序和比较。

但总的来说:不要这样做。这是虐待。当然，有一些东西可以用于集合的键，而不是可变的数据结构。集合中整数的空间是固定的和小的吗(例如，总是在0-1024或诸如此类的范围内)？然后尝试存储在QByteArray中的位掩码。等等。

Answer 2

您可以像这样创建一个散列方法

uint qHash(const QSet<int>& set) {
  uint seed = 0;

  for(int x : set) {
     seed ^= qHash(x) + 0x9e1559a9 + (seed << 6) + (seed >> 2);
  }
  return seed;
}

那么你的QMap会是这样的

QMap<uint, char> charSet;

其中uint是前一个方法的结果。

实际上，这种方式并不是100%稳定的，它取决于你的散列函数。

Answer 3

假设您不担心性能(如果您使用容器作为键，我认为这是一个合理的假设)，那么我会这样做。

QSet<int> intSet;
intSet << 1 << 2 << 3 << 3 << 4;

QVector<int> intVector;
intVector.reserve(intSet.size());
qCopy(intSet.begin(), intSet.end(), std::back_inserter(intVector)); // QVector doesn't have a std::vector range constructor atm
qSort(intVector);

QHash<QVector<int>, char> charHash;
charHash[intVector] = '6';

这将是非常慢的添加，但查找应该(相对)快。

不过，我建议你想出一个更好的密钥。也许是一个具有固定数量的int的简单类，您只需定义必要的操作符就可以将其放入map/hash中。