QTreeWidget::selectedItems() is very slow and inefficient when called on a large data set

QTreeWidget::selectedItems() loops over all indices in the data set, and each iteration of the loop can call QList<QTreeWidgetItem *>::contains(), which is itself an O(N) function call.

That means selectedItems() is a O(N^2) function call, which makes it very very slow when called on a large data set.

To reproduce, run the attached example program. Note that selectedItems() takes 45 seconds to return in the example program. (on a fast Mac... a slower computer would take even more time)

A simple change to QTreeWidget::selectedItems(), where the results list is collected into a QSet<QTreeWidgetItem *> and then copied over to a QList only at the end, reduces the running time of selectedItems() from 45 seconds to 2.5 seconds in the example.

/*!
Returns a list of all selected non-hidden items.

\sa itemSelectionChanged()
*/
QList<QTreeWidgetItem*> QTreeWidget::selectedItems() const
{
Q_D(const QTreeWidget);
QModelIndexList indexes = selectionModel()->selectedIndexes();
QList<QTreeWidgetItem*> items;

#ifdef ORIG_QT_CODE
// This is the code that was shipped with Qt-4.7.0-tp1
for (int i = 0; i < indexes.count(); ++i)

{ QTreeWidgetItem *item = d->item(indexes.at(i)); if (isItemHidden(item) || items.contains(item)) // ### slow, optimize later continue; items.append(item); }

#else
// This code I have changed to make it faster --jaf
QSet<QTreeWidgetItem *> resultSet;
for (int i = 0; i < indexes.count(); ++i)

{ QTreeWidgetItem *item = d->item(indexes.at(i)); if (isItemHidden(item) == false) resultSet.insert(item); // ### optimized now? }

// And now that we have our set, add it to the QList to return
QSetIterator<QTreeWidgetItem *> iter(resultSet);
while (iter.hasNext()) items.append(iter.next());
#endif

return items;
}

Here is my output from running the example program, both with and without ORIG_QT_CODE defined in the Qt build above:

[... Using Qt-4.7.0-tp1, as shipped...]
jeremy-friesners-mac-pro-3:tree_widget_slow jaf$ ./slow.app/Contents/MacOS/slow
Beginning test...
It took 4861 milliseconds to populate the QTreeWidget with 100000 QTreeWidgetItems.
It took 2101 milliseconds to call selectAll() on the QTreeWidget with 100000 QTreeWidgetItems.
It took 45917 milliseconds to call selectedItems() on the QTreeWidget with 100000 selected QTreeWidgetItems.
^C

[... using Qt-4.7.0-tp1, with the changes listed above to the selectedItems() source.... ]
jeremy-friesners-mac-pro-3:tree_widget_slow jaf$ ./slow.app/Contents/MacOS/slow
Beginning test...
It took 4820 milliseconds to populate the QTreeWidget with 100000 QTreeWidgetItems.
It took 2155 milliseconds to call selectAll() on the QTreeWidget with 100000 QTreeWidgetItems.
It took 2573 milliseconds to call selectedItems() on the QTreeWidget with 100000 selected QTreeWidgetItems.