Sequential erase/_if: don't apply predicate twice to element

The code was trying to avoid a detach in the case no element needed to
be removed, by first running find_if() on const_iterators, and then,
after converting its result to (mutable) iterators, start the
remove_if() algorithm where find_if() left off.

But this applies the predicate to the element found by find_if() (if
any) _twice_: first just before we exit the first find_if() and then
just as we enter remove_if(), which will start by running find_if()
again, with the result of the initial find_if as 'first'.

Apart from being needlessly inefficient, this violates the
specification of Uniform Erasure, which defines sequential erase_if()
as being equivalent to remove_if() + container erase(), with the
former being specified to apply the predicate exactly once per
element.

Fix by writing the remove_if() part by hand.

Instead of doing the dance with the loop invariant documentation
twice, simply implement erase() via erase_if() (complicated a bit by
the weird passing of predicates by lvalue reference instead of by
value, as would be idiomatic). This exposes users to:

[ChangeLog][QtCore][Potentially Source-Incompatible Changes] A fix in
the implementation of the erase-like algorithms of sequential Qt
container may re-enable signed/unsigned comparison warnings previously
suppressed by having occurred in std library code. To fix, cast the
value to look for such that it has the same signedness as the
container's elements.

... but the issue would be the same had we inlined std::remove()
instead of passing a lambda to sequential_erase_if(), so it's nothing
we can, nor should, work around.

[ChangeLog][QtCore][Containers] Fixed a bug in the implementation of
most sequential Qt container's erase-like algorithms (member
removeAll()/removeIf() and free erase()/erase_if()) where the equality
operator or the predicate, respectively, was applied to the first
matching element twice. Each element is now tested exactly once.

Pick-to: 6.3 6.2
Change-Id: Ib6d24b01b40866c125406f1cd6042d4cd083ea0d
Reviewed-by: Giuseppe D'Angelo <giuseppe.dangelo@kdab.com>

1 files changed, 18 insertions, 4 deletions

diff --git a/tests/auto/corelib/tools/containerapisymmetry/tst_containerapisymmetry.cpp b/tests/auto/corelib/tools/containerapisymmetry/tst_containerapisymmetry.cpp
index 7fe1dd9b4d..95d2076b6e 100644
--- a/tests/auto/corelib/tools/containerapisymmetry/tst_containerapisymmetry.cpp
+++ b/tests/auto/corelib/tools/containerapisymmetry/tst_containerapisymmetry.cpp
@@ -771,21 +771,35 @@ void tst_ContainerApiSymmetry::erase_if_impl() const
     auto c = make<Container>(7); // {1, 2, 3, 4, 5, 6, 7}
     QCOMPARE(c.size(), S(7));
 
-    auto result = erase_if(c, [](V i) { return Conv::toInt(i) % 2 == 0; });
+    decltype(c.size()) oldSize, count;
+
+    oldSize = c.size();
+    count = 0;
+    auto result = erase_if(c, [&](V i) { ++count; return Conv::toInt(i) % 2 == 0; });
     QCOMPARE(result, S(3));
     QCOMPARE(c.size(), S(4));
+    QCOMPARE(count, oldSize);
 
-    result = erase_if(c, [](V i) { return Conv::toInt(i) % 123 == 0; });
+    oldSize = c.size();
+    count = 0;
+    result = erase_if(c, [&](V i) { ++count; return Conv::toInt(i) % 123 == 0; });
     QCOMPARE(result, S(0));
     QCOMPARE(c.size(), S(4));
+    QCOMPARE(count, oldSize);
 
-    result = erase_if(c, [](V i) { return Conv::toInt(i) % 3 == 0; });
+    oldSize = c.size();
+    count = 0;
+    result = erase_if(c, [&](V i) { ++count; return Conv::toInt(i) % 3 == 0; });
     QCOMPARE(result, S(1));
     QCOMPARE(c.size(), S(3));
+    QCOMPARE(count, oldSize);
 
-    result = erase_if(c, [](V i) { return Conv::toInt(i) % 2 == 1; });
+    oldSize = c.size();
+    count = 0;
+    result = erase_if(c, [&](V i) { ++count; return Conv::toInt(i) % 2 == 1; });
     QCOMPARE(result, S(3));
     QCOMPARE(c.size(), S(0));
+    QCOMPARE(count, oldSize);
 }
 
 template <typename Container>