From dbd55cdaf367bdc9d6774bcb9927cbe19f18065f Mon Sep 17 00:00:00 2001 From: Giuseppe D'Angelo Date: Tue, 25 Apr 2017 15:58:57 +0100 Subject: QHash/QMultiHash: fix operator== The existing QHash::operator== does not work when the same keys appear in different order between the two hashes being compared. However, relying on iteration order on a QHash is (as usual) a bad idea and one should never do it. Task-number: QTBUG-60395 Change-Id: Ifb39a6779230e26bbd6fdba82ccc0247b9cdc6ed Reviewed-by: Lars Knoll --- src/corelib/tools/qhash.h | 28 ++++++++++++++++++---------- 1 file changed, 18 insertions(+), 10 deletions(-) (limited to 'src/corelib/tools/qhash.h') diff --git a/src/corelib/tools/qhash.h b/src/corelib/tools/qhash.h index c59f789cb2..b2c3cf574d 100644 --- a/src/corelib/tools/qhash.h +++ b/src/corelib/tools/qhash.h @@ -51,6 +51,8 @@ #include #endif +#include + #if defined(Q_CC_MSVC) #pragma warning( push ) #pragma warning( disable : 4311 ) // disable pointer truncation warning @@ -936,18 +938,24 @@ Q_OUTOFLINE_TEMPLATE bool QHash::operator==(const QHash &other) const const_iterator it = begin(); while (it != end()) { - const Key &akey = it.key(); + // Build two equal ranges for i.key(); one for *this and one for other. + // For *this we can avoid a lookup via equal_range, as we know the beginning of the range. + auto thisEqualRangeEnd = it; + while (thisEqualRangeEnd != end() && it.key() == thisEqualRangeEnd.key()) + ++thisEqualRangeEnd; - const_iterator it2 = other.find(akey); - do { - if (it2 == other.end() || !(it2.key() == akey)) - return false; - if (!(it.value() == it2.value())) - return false; - ++it; - ++it2; - } while (it != end() && it.key() == akey); + const auto otherEqualRange = other.equal_range(it.key()); + + if (std::distance(it, thisEqualRangeEnd) != std::distance(otherEqualRange.first, otherEqualRange.second)) + return false; + + // Keys in the ranges are equal by construction; this checks only the values. + if (!std::is_permutation(it, thisEqualRangeEnd, otherEqualRange.first)) + return false; + + it = thisEqualRangeEnd; } + return true; } -- cgit v1.2.3