3

我有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 <我应该如何实现它?即:比较的逻辑应该是什么?

注意:我太在乎性能了

4

4 回答 4

5

您似乎知道如何使其工作:定义一个operator<(const QSet<int>&)函数(我不相信 Qt 要求您将 QSet 子类化以使其工作,我知道 STL 不需要)。

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

但广泛地说:不要这样做。这是一种虐待。当然,您可以将某些东西用作集合的键,而不是可变数据结构。集合中的整数空间是否固定且很小(即始终在 0-1024 范围内或其他范围内)?然后尝试存储在 QByteArray 中的位掩码。ETC...

于 2012-04-19T21:10:50.697 回答
1

你可以像这样制作一个哈希方法

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% ,这取决于您的哈希函数。

于 2012-04-19T21:46:24.783 回答
0

假设您不担心性能(并且如果您使用容器作为密钥,我认为这是一个公平的假设),那么我会做这样的事情。

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';

这将是非常缓慢的添加,但查找应该(比较)快。

不过,我建议您想出一个更好的密钥。也许是一个具有固定数量整数的简单类,您只需定义必要的运算符即可将其放入映射/哈希中。

于 2012-04-19T21:21:55.640 回答
0

似乎您不需要值语义。为什么不使用:

QHash<QSet<int> *, char> charSet;
//then to insert a set
charSet.insert(& intSet, '6');

然而,对于每个集合,只有一个字符对应于一个集合,那么为什么不扩展 QSet 并添加额外的成员呢?

于 2012-04-19T21:39:56.580 回答