QHash intersection

Volebab

I have two QHash<int, QString>, the first one is a list of fruits, the second is a list of selected fruits. I want to intersect them preserving the key of the fruits. For example:

QHash<int, QString> fruits = {
    { 0, "banana" },
    { 1, "mango" },
    { 2, "tomato" },
    { 8, "apple" },
    { 9, "orange" },
    { 12, "grape" },
    { 13, "melon" },
    { 14, "lemon" }
};

QHash<int, QString> selected = {
    { 0, "banana" },
    { 1, "mango" },
    { 2, "tomato" },
    { 3, "melon" },
    { 4, "lemon" }
};

it would return:

QHash<int, QString> intersection = {
    { 0, "banana" },
    { 1, "mango" },
    { 2, "tomato" },
    { 13, "melon" },
    { 14, "lemon" }
};

As you can see, it preserverd the key of banana, mango, tomato, melon and lemon from the fruits.

How can I do that? As far as I know, the only list that has intersection is QSet but it's not suitable in this case.

Paul Colby

Not necessarily the best solution (depends on what you're optimising for), but how about something like:

const QSet<QString> selectedValues = QSet<QString>::fromList(selected.values());
QHash<int, QString> intersection;
for (auto iter = fruits.constBegin(); iter != fruits.constEnd(); ++iter) {
    if (selectedValues.contains(iter.value())) {
        intersection.insert(iter.key(), iter.value());
    }
}

Cheers.

kshegunov

@Paul-Colby

Not necessarily the best solution

It is the best solution, with one tiny remark: To maximize performance the resulting hash should be sized before inserting. However, I really doubt it much matters here.

Volebab

@kshegunov - I can't size QHash as I don't know how many items is going to be inserted on it. - but the answer is great. I will accept as the right answer, but if anyone else knows how to do that using other algorithm, please, share.

Paul Colby

@kshegunov said:

To maximize performance the resulting hash should be sized before inserting.

You're probably right, but given the lack of information we have about the use case, I'd say that's really a premature optimisation ;)

For example:

what if fruits and selected both typically contain 100's of thousands of items, while the intersection is typically only a couple of items? Then a QHash::reserve would probably be more expensive than not; or
if all three are really large (ie there are more items in common than distinct), then it might make more sense to construct intersection as a copy of fruits, then make the loop remove items, rather than insert (might depend on the implementation / efficiency of QHash's copy constructor).

But yeah, an intersection.reserve(qMin(fruits.size(), selected.size()); might be a performance improvement, depending on the details of the use case :)

Cheers.

kshegunov

@Paul-Colby said:

You're probably right, but given the lack of information we have about the use case, I'd say that's really a premature optimisation

Agreed.

Volebab

@Paul-Colby - The size will vary, the items change according to the user record.
That's why I said I can't put a size in QHash, but the only thing I can assure is: The size isn't always big, I mean, the example I gave is pretty much the same size as others - the selected items, but the fruits can be big.
I described for you how it will be. The fruit list will be big - most of the cases, but the selected items won't, most of the time it will have a few. The approach you presented is the best for that? I mean, inserted instead of deleting?

Paul Colby

@Volebab said:

The fruit list will be big - most of the cases, but the selected items won't, most of the time it will have a few. The approach you presented is the best for that? I mean, inserted instead of deleting?

Yeah, in that case inserts would probably be more efficient (both CPU and memory utilization) than deletes. If it really matters, then I'd recommend benchmarking a few alternatives after establishing where the bottlenecks really are :)

https://en.wikipedia.org/wiki/Program_optimization#When_to_optimize

Cheers.

Volebab

@Paul-Colby I will be reading, and I was reading things about optimization related to Qt. Thank you.