diff options
author | Giuseppe D'Angelo <giuseppe.dangelo@kdab.com> | 2017-04-25 15:58:57 +0100 |
---|---|---|
committer | Giuseppe D'Angelo <giuseppe.dangelo@kdab.com> | 2017-05-05 12:18:25 +0000 |
commit | dbd55cdaf367bdc9d6774bcb9927cbe19f18065f (patch) | |
tree | 5bc5298d51911ff7ef3bfaae6f27699697e1264e | |
parent | 18d49808db46add078d9d4bcffaac5361d5c7269 (diff) |
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>
-rw-r--r-- | src/corelib/tools/qhash.h | 28 | ||||
-rw-r--r-- | tests/auto/corelib/tools/qhash/tst_qhash.cpp | 69 |
2 files changed, 85 insertions, 12 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; } diff --git a/tests/auto/corelib/tools/qhash/tst_qhash.cpp b/tests/auto/corelib/tools/qhash/tst_qhash.cpp index 0c5f1a7afb..943b4316ff 100644 --- a/tests/auto/corelib/tools/qhash/tst_qhash.cpp +++ b/tests/auto/corelib/tools/qhash/tst_qhash.cpp @@ -51,7 +51,7 @@ private slots: void contains(); // copied from tst_QMap void qhash(); void take(); // copied from tst_QMap - void operator_eq(); // copied from tst_QMap + void operator_eq(); // slightly modified from tst_QMap void rehash_isnt_quadratic(); void dont_need_default_constructor(); void qmultihash_specific(); @@ -771,7 +771,7 @@ void tst_QHash::take() QVERIFY(!map.contains(3)); } -//copied from tst_QMap +// slightly modified from tst_QMap void tst_QHash::operator_eq() { { @@ -848,6 +848,71 @@ void tst_QHash::operator_eq() QVERIFY(a != b); QVERIFY(!(a == b)); } + + // unlike multi-maps, multi-hashes should be equal iff their contents are equal, + // regardless of insertion or iteration order + + { + QHash<int, int> a; + QHash<int, int> b; + + a.insertMulti(0, 0); + a.insertMulti(0, 1); + + b.insertMulti(0, 1); + b.insertMulti(0, 0); + + QVERIFY(a == b); + QVERIFY(!(a != b)); + } + + { + QHash<int, int> a; + QHash<int, int> b; + + enum { Count = 100 }; + + for (int key = 0; key < Count; ++key) { + for (int value = 0; value < Count; ++value) + a.insertMulti(key, value); + } + + for (int key = Count - 1; key >= 0; --key) { + for (int value = 0; value < Count; ++value) + b.insertMulti(key, value); + } + + QVERIFY(a == b); + QVERIFY(!(a != b)); + } + + { + QHash<int, int> a; + QHash<int, int> b; + + enum { + Count = 100, + KeyStep = 17, // coprime with Count + ValueStep = 23, // coprime with Count + }; + + for (int key = 0; key < Count; ++key) { + for (int value = 0; value < Count; ++value) + a.insertMulti(key, value); + } + + // Generates two permutations of [0, Count) for the keys and values, + // so that b will be identical to a, just built in a very different order. + + for (int k = 0; k < Count; ++k) { + const int key = (k * KeyStep) % Count; + for (int v = 0; v < Count; ++v) + b.insertMulti(key, (v * ValueStep) % Count); + } + + QVERIFY(a == b); + QVERIFY(!(a != b)); + } } void tst_QHash::compare() |