summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorIvan Komissarov <abbapoh@gmail.com>2021-04-21 14:03:58 +0200
committerIvan Komissarov <ABBAPOH@gmail.com>2021-04-21 15:32:06 +0000
commitd54d84a213041f9b84bc3061019f1d089ab74019 (patch)
treeb889d5ab381ac5c45b9336f7ee42062566e8945a
parent18c97249f38af5492739f9215d702b918ad9132a (diff)
downloadqbs-d54d84a213041f9b84bc3061019f1d089ab74019.tar.gz
Use binary search in Set::find()
Change-Id: I5ed154633233dfeedf6b69b52fc5339fef3a956a Reviewed-by: Christian Kandeler <christian.kandeler@qt.io>
-rw-r--r--src/lib/corelib/tools/set.h4
-rw-r--r--src/lib/corelib/tools/stlutils.h15
-rw-r--r--tests/auto/tools/tst_tools.cpp24
-rw-r--r--tests/auto/tools/tst_tools.h1
4 files changed, 42 insertions, 2 deletions
diff --git a/src/lib/corelib/tools/set.h b/src/lib/corelib/tools/set.h
index 75db0528b..463d3beb6 100644
--- a/src/lib/corelib/tools/set.h
+++ b/src/lib/corelib/tools/set.h
@@ -112,8 +112,8 @@ public:
Set &operator&=(const Set &other) { return intersect(other); }
Set &operator&=(const T &v) { return intersect(Set{ v }); }
- iterator find(const T &v) { return std::find(m_data.begin(), m_data.end(), v); }
- const_iterator find(const T &v) const { return std::find(m_data.cbegin(), m_data.cend(), v); }
+ iterator find(const T &v) { return binaryFind(m_data.begin(), m_data.end(), v); }
+ const_iterator find(const T &v) const { return binaryFind(m_data.cbegin(), m_data.cend(), v); }
std::pair<iterator, bool> insert(const T &v);
Set &operator+=(const T &v) { insert(v); return *this; }
Set &operator|=(const T &v) { return operator+=(v); }
diff --git a/src/lib/corelib/tools/stlutils.h b/src/lib/corelib/tools/stlutils.h
index 1b6d7278f..d4c569a95 100644
--- a/src/lib/corelib/tools/stlutils.h
+++ b/src/lib/corelib/tools/stlutils.h
@@ -123,6 +123,21 @@ bool none_of(const Container &container, const UnaryPredicate &predicate)
return std::none_of(std::begin(container), std::end(container), predicate);
}
+template <class It, class T, class Compare>
+It binaryFind(It begin, It end, const T &value, Compare comp)
+{
+ const auto it = std::lower_bound(begin, end, value, comp);
+ if (it == end || comp(value, *it))
+ return end;
+ return it;
+}
+
+template <class It, class T>
+It binaryFind(It begin, It end, const T &value)
+{
+ return binaryFind(begin, end, value, std::less<T>());
+}
+
template <class C>
C &operator<<(C &container, const typename C::value_type &v)
{
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();