QItemSelection: fix (some) O(n²) behavior in merge()

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 <marten.nordheim@qt.io>

1 files changed, 7 insertions, 9 deletions

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