QFlatMap: add remove_if

The existing API of QFlatMap did not allow efficient removal of
elements:

- std::remove_if does not apply, because it works by moving elements
  back in the range onto those that need to be removed, which doesn't
  work in flat_map's case, because, like for all associative
  containers, the key in value_type is const.

- The node-based erase-loop (over it = cond ? c.erase(it) :
  std::next(it)) works, but, unlike in traditional associative
  containers, is quadratic, because flat_map::erase is a linear
  operation.

According to Stepanov's principle of Efficient Computational Basis
(Elements of Programming, Section 1.4), we're therefore missing API.

Add it.

I couldn't make up my mind about the calling convention for the
predicate and, despite having authored a merged paper about erase_if,
can never remember what the predicate is supposed to take, so be fancy
and accept all: (*it), (it.key(), it.value()), (it.key()). This means
that unary predicates can either not be generic or must be properly
constrained to distinguish between pair<const K, V> and K, but that's
not necessarily a bad thing.

There's no reason to supply a Qt-ified removeIf on top of the standard
name, because this is private API and doubling the names would do
nothing except double the testing overhead.

Fixes: QTBUG-100983
Change-Id: I12545058958fc5d620baa770f92193c8de8b2d26
Reviewed-by: Edward Welbourne <edward.welbourne@qt.io>
Reviewed-by: Ulf Hermann <ulf.hermann@qt.io>
Reviewed-by: Qt CI Bot <qt_ci_bot@qt-project.org>

1 files changed, 87 insertions, 0 deletions

diff --git a/tests/auto/corelib/tools/qflatmap/tst_qflatmap.cpp b/tests/auto/corelib/tools/qflatmap/tst_qflatmap.cpp
index 8674734a11..ae6fcd6cad 100644
--- a/tests/auto/corelib/tools/qflatmap/tst_qflatmap.cpp
+++ b/tests/auto/corelib/tools/qflatmap/tst_qflatmap.cpp
@@ -40,6 +40,20 @@
 #include <list>
 #include <tuple>
 
+static constexpr bool is_even(int n) { return n % 2 == 0; }
+static constexpr bool is_empty(QAnyStringView v) { return v.isEmpty(); }
+
+namespace {
+template <typename P>
+constexpr inline bool is_pair_impl_v = false;
+template <typename T, typename S>
+constexpr inline bool is_pair_impl_v<std::pair<T,S>> = true;
+template <typename P>
+constexpr inline bool is_pair_v = is_pair_impl_v<std::decay_t<P>>;
+template <typename P>
+using if_pair = std::enable_if_t<is_pair_v<P>, bool>;
+}
+
 class tst_QFlatMap : public QObject
 {
     Q_OBJECT
@@ -53,6 +67,9 @@ private slots:
     void removal();
     void extraction();
     void iterators();
+    void remove_if_pair() { remove_if_impl([](const auto &p) -> if_pair<decltype(p)> { return is_even(p.first) && is_empty(p.second); }); }
+    void remove_if_key_value() { remove_if_impl([](const auto &k, const auto &v) { return is_even(k) && is_empty(v); }); }
+    void remove_if_key() { remove_if_impl([](int k) { return is_even(k); }, true); }
     void statefulComparator();
     void transparency_using();
     void transparency_struct();
@@ -63,6 +80,8 @@ private slots:
 private:
     template <typename Compare>
     void transparency_impl();
+    template <typename Predicate>
+    void remove_if_impl(Predicate p, bool removeNonEmptyValues = false);
 };
 
 #ifdef QFLATMAP_TEMPORARILY_REMOVED
@@ -369,6 +388,74 @@ void tst_QFlatMap::iterators()
     }
 }
 
+template <typename Pred>
+void tst_QFlatMap::remove_if_impl(Pred p, bool removeNonEmptyValues)
+{
+    // empty stays empty:
+    {
+        QFlatMap<int, QString> m;
+        QCOMPARE(m.remove_if(p), 0);
+        QVERIFY(m.isEmpty());
+    }
+    // a matching element is removed:
+    {
+        {
+            QFlatMap<int, QString> m;
+            m.insert_or_assign(0, "");
+            QCOMPARE(m.remove_if(p), 1);
+            QVERIFY(m.isEmpty());
+        }
+        if (removeNonEmptyValues) {
+            QFlatMap<int, QString> m;
+            m.insert_or_assign(0, "x");
+            QCOMPARE(m.remove_if(p), 1);
+            QVERIFY(m.isEmpty());
+        }
+    }
+    // a non-matching element is not removed:
+    {
+        {
+            QFlatMap<int, QString> m;
+            m.insert_or_assign(1, "");
+            QCOMPARE(m.remove_if(p), 0);
+            QVERIFY(m.contains(1));
+            QVERIFY(m[1].isEmpty());
+        }
+        if (removeNonEmptyValues) {
+            QFlatMap<int, QString> m;
+            m.insert_or_assign(1, "x");
+            QCOMPARE(m.remove_if(p), 0);
+            QVERIFY(m.contains(1));
+            QCOMPARE(m[1], "x");
+        }
+    }
+    // of matching and non-matching elements, only matching ones are removed:
+    {
+        {
+            QFlatMap<int, QString> m;
+            m.insert_or_assign(0, "");
+            m.insert_or_assign(1, "");
+            const auto copy = m;
+            QCOMPARE(m.remove_if(p), 1);
+            QCOMPARE(copy.size(), 2);
+            QCOMPARE(copy[0], "");
+            QCOMPARE(copy[1], "");
+            QCOMPARE(m.size(), 1);
+            QVERIFY(m.contains(1));
+            QVERIFY(m[1].isEmpty());
+        }
+        {
+            QFlatMap<int, QString> m;
+            m.insert_or_assign(1, "");
+            m.insert_or_assign(2, "");
+            QCOMPARE(m.remove_if(p), 1);
+            QCOMPARE(m.size(), 1);
+            QVERIFY(m.contains(1));
+            QVERIFY(m[1].isEmpty());
+        }
+    }
+}
+
 void tst_QFlatMap::removal()
 {
 #ifdef QFLATMAP_TEMPORARILY_REMOVED