Speed up the removal of items from a QGraphicsScene

When using a linear index, all items in a scene are stored in a QList.
While adding new items is a constant operation, removal requires a
traversal through the entire list. This is especially problematic
when the scene contains millions of items and many of them are removed,
which requires a linear search for each item, resulting in a very slow
operation. Moreover, this behavior is actually inconsistent with the
current documentation which states for the linear index:
"Adding, moving and removing items, however, is done in constant time."

With this change, the list is sorted once an item needs to be removed.
The item to be removed is then found using binary search. To reduce
the overhead of sorting the list is not sorted from scratch. First the
newly inserted items are sorted and then the two parts of the list
are merged.

[ChangeLog][QtWidgets][QGraphicsScene] Speed up the removal of items
when using the linear index.

Change-Id: I28708622605d7fb0fac656df1f9b2f2fa3136759
Reviewed-by: Andreas Aardal Hanssen <andreas@hanssen.name>

1 files changed, 22 insertions, 3 deletions

diff --git a/src/widgets/graphicsview/qgraphicsscenelinearindex_p.h b/src/widgets/graphicsview/qgraphicsscenelinearindex_p.h
index 7debcfb501..5788818394 100644
--- a/src/widgets/graphicsview/qgraphicsscenelinearindex_p.h
+++ b/src/widgets/graphicsview/qgraphicsscenelinearindex_p.h
@@ -70,7 +70,7 @@ class Q_AUTOTEST_EXPORT QGraphicsSceneLinearIndex : public QGraphicsSceneIndex
     Q_OBJECT
 
 public:
-    QGraphicsSceneLinearIndex(QGraphicsScene *scene = 0) : QGraphicsSceneIndex(scene)
+    QGraphicsSceneLinearIndex(QGraphicsScene *scene = 0) : QGraphicsSceneIndex(scene), m_numSortedElements(0)
     { }
 
     QList<QGraphicsItem *> items(Qt::SortOrder order = Qt::DescendingOrder) const
@@ -85,16 +85,35 @@ public:
 
 protected :
     virtual void clear()
-    { m_items.clear(); }
+    {
+        m_items.clear();
+        m_numSortedElements = 0;
+    }
 
     virtual void addItem(QGraphicsItem *item)
     { m_items << item; }
 
     virtual void removeItem(QGraphicsItem *item)
-    { m_items.removeOne(item); }
+    {
+        // Sort m_items if needed
+        if (m_numSortedElements < m_items.size())
+        {
+            std::sort(m_items.begin() + m_numSortedElements, m_items.end() );
+            std::inplace_merge(m_items.begin(), m_items.begin() + m_numSortedElements, m_items.end());
+            m_numSortedElements = m_items.size();
+        }
+
+        QList<QGraphicsItem*>::iterator element = std::lower_bound(m_items.begin(), m_items.end(), item);
+        if (element != m_items.end() && *element == item)
+        {
+            m_items.erase(element);
+            --m_numSortedElements;
+        }
+    }
 
 private:
     QList<QGraphicsItem*> m_items;
+    int m_numSortedElements;
 };
 
 #endif // QT_NO_GRAPHICSVIEW