Fix QGraphicsScene::update() performance

A previous fix has caused a performance degradation while adding a
check for avoiding adding duplicated rectangles to the update list.
This patch fixes it by using a std::set instead of a QList, avoiding
duplication while using an O(log N) operation, instead of the O(N)
used before.

Fixes: QTBUG-77952
Change-Id: Ifa9fbf110e0bad60ee02a42d91281981fd98ceab
Reviewed-by: Volker Hilsheimer <volker.hilsheimer@qt.io>

1 files changed, 16 insertions, 1 deletions

diff --git a/src/widgets/graphicsview/qgraphicsscene_p.h b/src/widgets/graphicsview/qgraphicsscene_p.h
index a2d13436fc..14bafe6678 100644
--- a/src/widgets/graphicsview/qgraphicsscene_p.h
+++ b/src/widgets/graphicsview/qgraphicsscene_p.h
@@ -69,6 +69,9 @@
 #include <QtWidgets/qstyle.h>
 #include <QtWidgets/qstyleoption.h>
 
+#include <set>
+#include <tuple>
+
 QT_REQUIRE_CONFIG(graphicsview);
 
 QT_BEGIN_NAMESPACE
@@ -122,7 +125,19 @@ public:
     QRectF growingItemsBoundingRect;
 
     void _q_emitUpdated();
-    QList<QRectF> updatedRects;
+
+    struct UpdatedRectsCmp
+    {
+        bool operator() (const QRectF &a, const QRectF &b) const noexcept
+        {
+            return std::make_tuple(a.y(), a.x(), a.height(), a.width())
+                    < std::make_tuple(b.y(), b.x(), b.height(), b.width());
+        }
+    };
+
+    // std::set was used here instead of std::unordered_set due to requiring only a comparator and
+    // showing equivalent performance in empirical measurements within the ranges of interest...
+    std::set<QRectF, UpdatedRectsCmp> updatedRects;
 
     QPainterPath selectionArea;
     int selectionChanging;