diff options
author | Ivan Komissarov <abbapoh@gmail.com> | 2021-04-21 14:03:58 +0200 |
---|---|---|
committer | Ivan Komissarov <ABBAPOH@gmail.com> | 2021-04-21 15:32:06 +0000 |
commit | d54d84a213041f9b84bc3061019f1d089ab74019 (patch) | |
tree | b889d5ab381ac5c45b9336f7ee42062566e8945a | |
parent | 18c97249f38af5492739f9215d702b918ad9132a (diff) | |
download | qbs-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.h | 4 | ||||
-rw-r--r-- | src/lib/corelib/tools/stlutils.h | 15 | ||||
-rw-r--r-- | tests/auto/tools/tst_tools.cpp | 24 | ||||
-rw-r--r-- | tests/auto/tools/tst_tools.h | 1 |
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(); |