QSet in QMap or QHash

Question

I have QMap and I want to make QSet the key of it, I couldn't do that because QSet is not comparable. for example:

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

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

charSet.insert(intSet, '6');

Is there any way to make it work? and if I inherit from QSet and define operator < how should I implement it? i.e: What should be the logic of the comparison?

Note: I care too much about performance

Answer 1

You seem to know how to make it work: define an operator<(const QSet<int>&) function (I don't believe Qt requires that you subclass QSet to make this work, I know STL does not).

Obviously, implementing a comparator on an unordered set is going to be difficult. And doing it such that it runs in constant time is, I believe, impossible. You might try something like checking the size first, and then sorting and comparing the two contents as lists.

But broadly: don't do this. It's an abuse. Surely there is something you can use for the key of your set that is not a mutable data structure. Is the space of integers in the sets fixed and small (i.e. always in the range 0-1024 or whatnot)? Then try a bitmask stored in a QByteArray. etc...

Answer 2

you can make a hash method like this

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

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

then your QMap will be like this

QMap<uint, char> charSet;

where uint is the result of previous method .

actually this way isn't stable 100% , it depends on your hash function.

Answer 3

It seems like you don't need a value semantics. Wo why not use:

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

However for each set there is only one character that corresponds with a set, so why don't you extend QSet and add additional member?

Answer 4

Assuming you're not worried about performance (and if you're using a container as a key I think that's a fair assumption to make) then I would do something like this.

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

This will be very slow to add, but the lookups should be (comparatively) fast.

I would suggest you come up with a better key though. Perhaps a simple class with a fixed number of ints which you just define the necessary operators for it to go in a map/hash.