From d54d84a213041f9b84bc3061019f1d089ab74019 Mon Sep 17 00:00:00 2001
From: Ivan Komissarov <abbapoh@gmail.com>
Date: Wed, 21 Apr 2021 14:03:58 +0200
Subject: Use binary search in Set::find()

Change-Id: I5ed154633233dfeedf6b69b52fc5339fef3a956a
Reviewed-by: Christian Kandeler <christian.kandeler@qt.io>
---
 tests/auto/tools/tst_tools.cpp | 24 ++++++++++++++++++++++++
 tests/auto/tools/tst_tools.h   |  1 +
 2 files changed, 25 insertions(+)

(limited to 'tests')

diff --git a/tests/auto/tools/tst_tools.cpp b/tests/auto/tools/tst_tools.cpp
index edf5a1308..92e0978b5 100644
--- a/tests/auto/tools/tst_tools.cpp
+++ b/tests/auto/tools/tst_tools.cpp
@@ -673,6 +673,30 @@ void TestTools::set_containsSet()
     QVERIFY(set3.contains(set4));
 }
 
+void TestTools::set_find()
+{
+    Set<QString> set1;
+
+    for (int i = 0; i < 500; ++i) {
+        QVERIFY(set1.find(QString::number(i)) == set1.end());
+        set1.insert(QString::number(i));
+        const auto it = set1.find(QString::number(i));
+        QVERIFY(it != set1.end());
+        QVERIFY(*it == QString::number(i));
+    }
+
+    QCOMPARE(set1.size(), size_t { 500 });
+
+    for (int j = 0; j < 500; ++j) {
+        int i = (j * 17) % 500;
+        const auto it = set1.find(QString::number(i));
+        QVERIFY(it != set1.end());
+        QVERIFY(*it == QString::number(i));
+        set1.remove(QString::number(i));
+        QVERIFY(set1.find(QString::number(i)) == set1.end());
+    }
+}
+
 void TestTools::set_begin()
 {
     Set<int> set1;
diff --git a/tests/auto/tools/tst_tools.h b/tests/auto/tools/tst_tools.h
index bd8538be2..d1ba0a57b 100644
--- a/tests/auto/tools/tst_tools.h
+++ b/tests/auto/tools/tst_tools.h
@@ -79,6 +79,7 @@ private slots:
     void set_remove();
     void set_contains();
     void set_containsSet();
+    void set_find();
     void set_begin();
     void set_end();
     void set_insert();
-- 
cgit v1.2.3