From 06dfbdf081facf8b8d4e3c289886012376222d9d Mon Sep 17 00:00:00 2001 From: Marc Mutz Date: Wed, 10 Nov 2021 11:07:50 +0100 Subject: =?UTF-8?q?QItemSelection:=20fix=20(some)=20O(n=C2=B2)=20behavior?= =?UTF-8?q?=20in=20merge()?= MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit Instead of taking a copy of the incoming data, followed by a quadratic modifying algorithm (single-element erase loop), guaranteeing a deep-copy detach of the original, just iterate over the incoming data, building the new dataset by appending only valid items. Also port to ranged for loop. There's more quadratic behavior in that function, later on, but that's for another patch. Change-Id: I284f3b7c9694c8eb226a198f6f97538765113b19 Reviewed-by: Mårten Nordheim --- src/corelib/itemmodels/qitemselectionmodel.cpp | 16 +++++++--------- 1 file changed, 7 insertions(+), 9 deletions(-) (limited to 'src/corelib/itemmodels') diff --git a/src/corelib/itemmodels/qitemselectionmodel.cpp b/src/corelib/itemmodels/qitemselectionmodel.cpp index 6e1fbabd9d..f144bf9357 100644 --- a/src/corelib/itemmodels/qitemselectionmodel.cpp +++ b/src/corelib/itemmodels/qitemselectionmodel.cpp @@ -490,20 +490,18 @@ void QItemSelection::merge(const QItemSelection &other, QItemSelectionModel::Sel command & QItemSelectionModel::Toggle)) return; - QItemSelection newSelection = other; + QItemSelection newSelection; + newSelection.reserve(other.size()); // Collect intersections QItemSelection intersections; - QItemSelection::iterator it = newSelection.begin(); - while (it != newSelection.end()) { - if (!(*it).isValid()) { - it = newSelection.erase(it); + for (const auto &range : other) { + if (!range.isValid()) continue; - } + newSelection.push_back(range); for (int t = 0; t < count(); ++t) { - if ((*it).intersects(at(t))) - intersections.append(at(t).intersected(*it)); + if (range.intersects(at(t))) + intersections.append(at(t).intersected(range)); } - ++it; } // Split the old (and new) ranges using the intersections -- cgit v1.2.3