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 <lars.knoll@qt.io>

1 files changed, 18 insertions, 10 deletions

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 <initializer_list>
 #endif
 
+#include <algorithm>
+
 #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<Key, T>::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;
 }