diff options
author | Marc Mutz <marc.mutz@kdab.com> | 2015-12-03 13:47:27 +0100 |
---|---|---|
committer | Marc Mutz <marc.mutz@kdab.com> | 2015-12-03 22:35:19 +0000 |
commit | dc41ff5a84a743eae04cacf64274f653c4b1397e (patch) | |
tree | c05373c7218e2e5a3b529d315f4c35550e4c2b07 /src/widgets/widgets/qmdiarea.cpp | |
parent | 0d1024e0f147f033e481450e4b1cf918ddb7e735 (diff) |
QMdiArea: fix quadratic behavior
Repeatedly calling QVector::erase(it) (via QMutableVectorIterator::remove())
results in quadratic runtime.
Use std::stable_partition, which does exactly what the old code tried to do,
except in linear time.
Change-Id: I6e5911ee781071bbb84d72449c969e3b9907da51
Reviewed-by: Olivier Goffart (Woboq GmbH) <ogoffart@woboq.com>
Diffstat (limited to 'src/widgets/widgets/qmdiarea.cpp')
-rw-r--r-- | src/widgets/widgets/qmdiarea.cpp | 18 |
1 files changed, 8 insertions, 10 deletions
diff --git a/src/widgets/widgets/qmdiarea.cpp b/src/widgets/widgets/qmdiarea.cpp index 7ed790e40f..a0a6e08688 100644 --- a/src/widgets/widgets/qmdiarea.cpp +++ b/src/widgets/widgets/qmdiarea.cpp @@ -161,7 +161,6 @@ #include <QResizeEvent> #include <QScrollBar> #include <QtAlgorithms> -#include <QMutableVectorIterator> #include <QPainter> #include <QFontMetrics> #include <QStyleOption> @@ -480,17 +479,16 @@ QVector<QRect> MinOverlapPlacer::getCandidatePlacements(const QSize &size, const */ QVector<QRect> MinOverlapPlacer::findNonInsiders(const QRect &domain, QVector<QRect> &source) { + const auto containedInDomain = + [domain](const QRect &srcRect) { return domain.contains(srcRect); }; + + const auto firstOut = std::stable_partition(source.begin(), source.end(), containedInDomain); + QVector<QRect> result; - result.reserve(source.size()); + result.reserve(source.end() - firstOut); + std::copy(firstOut, source.end(), std::back_inserter(result)); - QMutableVectorIterator<QRect> it(source); - while (it.hasNext()) { - const QRect srcRect = it.next(); - if (!domain.contains(srcRect)) { - result << srcRect; - it.remove(); - } - } + source.erase(firstOut, source.end()); return result; } |