QStringList: use local storage in removeDuplicates()

If available, use a C++17 std::pmr::unordered_set with a monotonic
buffer resource and a 256-byte stack buffer to avoid the per-element
allocations of QSet.

Results on my machine:

 RESULT : tst_QStringList::removeDuplicates():"empty":
-     0.00014 msecs per iteration (total: 74, iterations: 524288)
+     0.000031 msecs per iteration (total: 66, iterations: 2097152)
 RESULT : tst_QStringList::removeDuplicates():"short-dup-0.00":
-     0.00043 msecs per iteration (total: 57, iterations: 131072)
+     0.00013 msecs per iteration (total: 69, iterations: 524288)
 RESULT : tst_QStringList::removeDuplicates():"short-dup-0.50":
-     0.00049 msecs per iteration (total: 65, iterations: 131072)
+     0.00032 msecs per iteration (total: 85, iterations: 262144)
 RESULT : tst_QStringList::removeDuplicates():"short-dup-0.66":
-     0.00057 msecs per iteration (total: 75, iterations: 131072)
+     0.00039 msecs per iteration (total: 52, iterations: 131072)
 RESULT : tst_QStringList::removeDuplicates():"short-dup-0.75":
-     0.00064 msecs per iteration (total: 85, iterations: 131072)
+     0.00048 msecs per iteration (total: 63, iterations: 131072)
 RESULT : tst_QStringList::removeDuplicates():"long-dup-0.00":
-     0.083 msecs per iteration (total: 85, iterations: 1024)
+     0.039 msecs per iteration (total: 80, iterations: 2048)
 RESULT : tst_QStringList::removeDuplicates():"long-dup-0.50":
-     0.11 msecs per iteration (total: 58, iterations: 512)
+     0.078 msecs per iteration (total: 80, iterations: 1024)
 RESULT : tst_QStringList::removeDuplicates():"long-dup-0.66":
-     0.13 msecs per iteration (total: 70, iterations: 512)
+     0.10 msecs per iteration (total: 53, iterations: 512)
 RESULT : tst_QStringList::removeDuplicates():"long-dup-0.75":
-     0.16 msecs per iteration (total: 86, iterations: 512)
+     0.13 msecs per iteration (total: 69, iterations: 512)

When interpreting the data, take into account that each iteration
contains _also_ a deep copy of the QStringList d/t the detach from
'input'.

The pattern is used elsewhere in Qt, so I've put the class that
implements the seen set into a private header file and used in some
other places I found.

Change-Id: I1f71a82008a16d5a3818f91f290ade21d837805e
Reviewed-by: Giuseppe D'Angelo <giuseppe.dangelo@kdab.com>

1 files changed, 4 insertions, 3 deletions

diff --git a/src/widgets/itemviews/qtreewidget.cpp b/src/widgets/itemviews/qtreewidget.cpp
index ddb31523fd..0d4c391e1c 100644
--- a/src/widgets/itemviews/qtreewidget.cpp
+++ b/src/widgets/itemviews/qtreewidget.cpp
@@ -48,6 +48,8 @@
 #include <private/qwidgetitemdata_p.h>
 #include <private/qtreewidgetitemiterator_p.h>
 
+#include <QtCore/private/qduplicatetracker_p.h>
+
 #include <algorithm>
 
 QT_BEGIN_NAMESPACE
@@ -3175,13 +3177,12 @@ QList<QTreeWidgetItem*> QTreeWidget::selectedItems() const
     const QModelIndexList indexes = selectionModel()->selectedIndexes();
     QList<QTreeWidgetItem*> items;
     items.reserve(indexes.count());
-    QSet<QTreeWidgetItem *> seen;
+    QDuplicateTracker<QTreeWidgetItem *> seen;
     seen.reserve(indexes.count());
     for (const auto &index : indexes) {
         QTreeWidgetItem *item = d->item(index);
-        if (item->isHidden() || seen.contains(item))
+        if (item->isHidden() || seen.hasSeen(item))
             continue;
-        seen.insert(item);
         items.append(item);
     }
     return items;