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-09 11:43:23 +0000 |
commit | 4084f96052ea1568c847f8cfb52b6ae6d205ec4d (patch) | |
tree | c092c779d28e9c447f63701d73f0ff182c886625 /src | |
parent | 5c44032f2a30a7454317d8eca71ff03530d64ace (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>
(cherry picked from commit dbd55cdaf367bdc9d6774bcb9927cbe19f18065f)
Reviewed-by: Edward Welbourne <edward.welbourne@qt.io>
Diffstat (limited to 'src')
-rw-r--r-- | src/corelib/tools/qalgorithms.h | 29 | ||||
-rw-r--r-- | src/corelib/tools/qhash.h | 30 |
2 files changed, 49 insertions, 10 deletions
diff --git a/src/corelib/tools/qalgorithms.h b/src/corelib/tools/qalgorithms.h index b22c5e219c..503f98feee 100644 --- a/src/corelib/tools/qalgorithms.h +++ b/src/corelib/tools/qalgorithms.h @@ -40,6 +40,10 @@ #include <intrin.h> #endif +#include <iterator> +#include <utility> +#include <algorithm> + QT_BEGIN_NAMESPACE QT_WARNING_PUSH QT_WARNING_DISABLE_GCC("-Wdeprecated-declarations") @@ -70,6 +74,31 @@ template <typename RandomAccessIterator, typename T, typename LessThan> QT_DEPRECATED_X("Use std::binary_search") Q_OUTOFLINE_TEMPLATE RandomAccessIterator qBinaryFindHelper(RandomAccessIterator begin, RandomAccessIterator end, const T &value, LessThan lessThan); #endif // QT_DEPRECATED_SINCE(5, 2) +template <typename ForwardIterator1, typename ForwardIterator2> +bool qIsPermutation(ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2) +{ + // find and exclude a common prefix + const std::pair<ForwardIterator1, ForwardIterator2> commonPrefix = std::mismatch(first1, last1, first2); + + // unpack commonPrefix + first1 = commonPrefix.first; + first2 = commonPrefix.second; + + // is there anything else to check? if so, for each element left to check in the + // first range, count how many times it appears in both ranges; the counts must match + if (first1 != last1) { + ForwardIterator2 last2 = first2; + std::advance(last2, std::distance(first1, last1)); + + for (ForwardIterator1 it = first1; it != last1; ++it) { + if (std::count(first1, last1, *it) != std::count(first2, last2, *it)) + return false; + } + } + + return true; +} + } #if QT_DEPRECATED_SINCE(5, 2) diff --git a/src/corelib/tools/qhash.h b/src/corelib/tools/qhash.h index adb7782efc..c181de94bb 100644 --- a/src/corelib/tools/qhash.h +++ b/src/corelib/tools/qhash.h @@ -40,6 +40,7 @@ #include <QtCore/qlist.h> #include <QtCore/qrefcount.h> #include <QtCore/qhashfunctions.h> +#include <QtCore/qalgorithms.h> #ifdef Q_COMPILER_INITIALIZER_LISTS #include <initializer_list> @@ -916,18 +917,27 @@ 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 find, as we know the beginning of the range. + const_iterator 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 const_iterator otherEqualRangeBegin = other.find(it.key()); + const_iterator otherEqualRangeEnd = otherEqualRangeBegin; + while (otherEqualRangeEnd != other.end() && it.key() == otherEqualRangeEnd.key()) + ++otherEqualRangeEnd; + + if (std::distance(it, thisEqualRangeEnd) != std::distance(otherEqualRangeBegin, otherEqualRangeEnd)) + return false; + + // Keys in the ranges are equal by construction; this checks only the values. + if (!QAlgorithmsPrivate::qIsPermutation(it, thisEqualRangeEnd, otherEqualRangeBegin)) + return false; + + it = thisEqualRangeEnd; } + return true; } |