From 633647334c14b263a0fcc7a5087bf1e2ea3e212a Mon Sep 17 00:00:00 2001 From: Dimitar Asenov Date: Tue, 2 Sep 2014 14:15:27 +0200 Subject: 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 --- .../graphicsview/qgraphicsscenelinearindex_p.h | 25 +++++++++++++++++++--- 1 file changed, 22 insertions(+), 3 deletions(-) (limited to 'src') 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 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::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 m_items; + int m_numSortedElements; }; #endif // QT_NO_GRAPHICSVIEW -- cgit v1.2.3