Sequential general purpose containers: add erase/erase_if

This is refactor/revisit for Qt 6 of the original commit [1]
by Marc, limited to QList and QVLA.

[1] see 11aa9a2276ba5367adbbd96d0ba13111d58145f8

[ChangeLog][QtCore][QList] Added erase() and erase_if(),
for consistent container erasure. Added removeIf() as a
method, complementing removeOne() / removeAll().

[ChangeLog][QtCore][QVarLengthArray] Added erase() and erase_if(),
for consistent container erasure. Added removeIf() as a
method, complementing removeOne() / removeAll().

Change-Id: I2499504e221431ead754dd64cc8a4d4e9f116183
Done-by: Marc Mutz
Reviewed-by: Andrei Golubev <andrei.golubev@qt.io>
Reviewed-by: Lars Knoll <lars.knoll@qt.io>

5 files changed, 187 insertions, 22 deletions

diff --git a/src/corelib/tools/qcontainertools_impl.h b/src/corelib/tools/qcontainertools_impl.h
index f4dfecffce..79c41fee87 100644
--- a/src/corelib/tools/qcontainertools_impl.h
+++ b/src/corelib/tools/qcontainertools_impl.h
@@ -150,6 +150,54 @@ using IfIsNotSame =
 
 template<typename T, typename U>
 using IfIsNotConvertible = typename std::enable_if<!std::is_convertible<T, U>::value, bool>::type;
+
+template <typename Container, typename T>
+auto sequential_erase(Container &c, const T &t)
+{
+    // avoid a detach in case there is nothing to remove
+    const auto cbegin = c.cbegin();
+    const auto cend = c.cend();
+    const auto t_it = std::find(cbegin, cend, t);
+    auto result = std::distance(cbegin, t_it);
+    if (result == c.size())
+        return result - result; // `0` of the right type
+
+    const auto e = c.end();
+    const auto it = std::remove(std::next(c.begin(), result), e, t);
+    result = std::distance(it, e);
+    c.erase(it, e);
+    return result;
+}
+
+template <typename Container, typename T>
+auto sequential_erase_with_copy(Container &c, const T &t)
+{
+    using CopyProxy = std::conditional_t<std::is_copy_constructible_v<T>, T, const T &>;
+    const T &tCopy = CopyProxy(t);
+    return sequential_erase(c, tCopy);
+}
+
+template <typename Container, typename T>
+auto sequential_erase_one(Container &c, const T &t)
+{
+    const auto cend = c.cend();
+    const auto it = std::find(c.cbegin(), cend, t);
+    if (it == cend)
+        return false;
+    c.erase(it);
+    return true;
+}
+
+template <typename Container, typename Predicate>
+auto sequential_erase_if(Container &c, Predicate &pred)
+{
+    const auto e = c.end();
+    const auto it = std::remove_if(c.begin(), e, pred);
+    const auto result = std::distance(it, e);
+    c.erase(it, e);
+    return result;
+}
+
 } // namespace QtPrivate
 
 QT_END_NAMESPACE
diff --git a/src/corelib/tools/qlist.h b/src/corelib/tools/qlist.h
index 517ba10326..1626dd27ed 100644
--- a/src/corelib/tools/qlist.h
+++ b/src/corelib/tools/qlist.h
@@ -502,33 +502,21 @@ public:
     template <typename AT = T>
     qsizetype removeAll(const AT &t)
     {
-        const const_iterator ce = this->cend(), cit = std::find(this->cbegin(), ce, t);
-        if (cit == ce)
-            return 0;
-        qsizetype index = cit - this->cbegin();
-
-        // Next operation detaches, so ce, cit may become invalidated.
-        // Moreover -- unlike std::erase -- we do support the case where t
-        // belongs to this list, so we have to save it from invalidation
-        // by taking a copy. This is made slightly more complex by the fact
-        // that t might not be copiable (in which case it certainly does not
-        // belong to this list), in which case we just use the original.
-        using CopyProxy = std::conditional_t<std::is_copy_constructible_v<AT>, AT, const AT &>;
-        const AT &tCopy = CopyProxy(t);
-        const iterator e = end(), it = std::remove(begin() + index, e, tCopy);
-        const qsizetype result = std::distance(it, e);
-        d->truncate(d->size - result);
-        return result;
+        return QtPrivate::sequential_erase_with_copy(*this, t);
     }
+
     template <typename AT = T>
     bool removeOne(const AT &t)
     {
-        const qsizetype i = indexOf(t);
-        if (i < 0)
-            return false;
-        remove(i);
-        return true;
+        return QtPrivate::sequential_erase_one(*this, t);
+    }
+
+    template <typename Predicate>
+    qsizetype removeIf(Predicate pred)
+    {
+        return QtPrivate::sequential_erase_if(*this, pred);
     }
+
     T takeAt(qsizetype i) { T t = std::move((*this)[i]); remove(i); return t; }
     void move(qsizetype from, qsizetype to)
     {
@@ -932,6 +920,18 @@ size_t qHash(const QList<T> &key, size_t seed = 0)
     return qHashRange(key.cbegin(), key.cend(), seed);
 }
 
+template <typename T, typename AT>
+qsizetype erase(QList<T> &list, const AT &t)
+{
+    return QtPrivate::sequential_erase(list, t);
+}
+
+template <typename T, typename Predicate>
+qsizetype erase_if(QList<T> &list, Predicate pred)
+{
+    return QtPrivate::sequential_erase_if(list, pred);
+}
+
 QList<uint> QStringView::toUcs4() const { return QtPrivate::convertToUcs4(*this); }
 
 QT_END_NAMESPACE
diff --git a/src/corelib/tools/qlist.qdoc b/src/corelib/tools/qlist.qdoc
index 4f78f75dc0..6469d52eed 100644
--- a/src/corelib/tools/qlist.qdoc
+++ b/src/corelib/tools/qlist.qdoc
@@ -844,6 +844,15 @@
     \sa removeAll()
 */
 
+/*! \fn template <typename T> template <typename Predicate> qsizetype QList<T>::removeIf(Predicate pred)
+    \since 6.1
+
+    Removes all elements for which the predicate \a pred returns true
+    from the list. Returns the number of elements removed, if any.
+
+    \sa removeAll()
+*/
+
 /*! \fn template <typename T> qsizetype QList<T>::length() const
     \since 5.2
 
@@ -1528,3 +1537,29 @@
 
     \sa{Serializing Qt Data Types}{Format of the QDataStream operators}
 */
+
+/*! \fn template <typename T, typename AT> qsizetype erase(QList<T> &list, const AT &t)
+    \relates QList
+    \since 6.1
+
+    Removes all elements that compare equal to \a t from the
+    list \a list. Returns the number of elements removed, if any.
+
+    \note Unlike QList::removeAll, \a t is not allowed to be a
+    reference to an element inside \a list. If you cannot be sure that
+    this is not the case, take a copy of \a t and call this function
+    with the copy.
+
+    \sa QList::removeAll(), erase_if
+*/
+
+/*! \fn template <typename T, typename Predicate> qsizetype erase_if(QList<T> &list, Predicate pred)
+    \relates QList
+    \since 6.1
+
+    Removes all elements for which the predicate \a pred returns true
+    from the list \a list. Returns the number of elements removed, if
+    any.
+
+    \sa erase
+*/
diff --git a/src/corelib/tools/qvarlengtharray.h b/src/corelib/tools/qvarlengtharray.h
index 06a4b66125..2a0818d176 100644
--- a/src/corelib/tools/qvarlengtharray.h
+++ b/src/corelib/tools/qvarlengtharray.h
@@ -250,6 +250,12 @@ public:
     void replace(qsizetype i, const T &t);
     void remove(qsizetype i);
     void remove(qsizetype i, qsizetype n);
+    template <typename AT = T>
+    qsizetype removeAll(const AT &t);
+    template <typename AT = T>
+    bool removeOne(const AT &t);
+    template <typename Predicate>
+    qsizetype removeIf(Predicate pred);
 
     inline T *data() { return ptr; }
     inline const T *data() const { return ptr; }
@@ -578,6 +584,18 @@ inline void QVarLengthArray<T, Prealloc>::remove(qsizetype i)
 { Q_ASSERT_X(i >= 0 && i < s, "QVarLengthArray::remove", "index out of range");
   erase(begin() + i, begin() + i + 1); }
 template <class T, qsizetype Prealloc>
+template <typename AT>
+inline qsizetype QVarLengthArray<T, Prealloc>::removeAll(const AT &t)
+{ return QtPrivate::sequential_erase_with_copy(*this, t); }
+template <class T, qsizetype Prealloc>
+template <typename AT>
+inline bool QVarLengthArray<T, Prealloc>::removeOne(const AT &t)
+{ return QtPrivate::sequential_erase_one(*this, t); }
+template <class T, qsizetype Prealloc>
+template <typename Predicate>
+inline qsizetype QVarLengthArray<T, Prealloc>::removeIf(Predicate pred)
+{ return QtPrivate::sequential_erase_if(*this, pred); }
+template <class T, qsizetype Prealloc>
 inline void QVarLengthArray<T, Prealloc>::prepend(T &&t)
 { insert(cbegin(), std::move(t)); }
 template <class T, qsizetype Prealloc>
@@ -699,6 +717,18 @@ size_t qHash(const QVarLengthArray<T, Prealloc> &key, size_t seed = 0)
     return qHashRange(key.cbegin(), key.cend(), seed);
 }
 
+template <typename T, qsizetype Prealloc, typename AT>
+qsizetype erase(QVarLengthArray<T, Prealloc> &array, const AT &t)
+{
+    return QtPrivate::sequential_erase(array, t);
+}
+
+template <typename T, qsizetype Prealloc, typename Predicate>
+qsizetype erase_if(QVarLengthArray<T, Prealloc> &array, Predicate pred)
+{
+    return QtPrivate::sequential_erase_if(array, pred);
+}
+
 QT_END_NAMESPACE
 
 #endif // QVARLENGTHARRAY_H
diff --git a/src/corelib/tools/qvarlengtharray.qdoc b/src/corelib/tools/qvarlengtharray.qdoc
index e1abebc3f9..52261de4c6 100644
--- a/src/corelib/tools/qvarlengtharray.qdoc
+++ b/src/corelib/tools/qvarlengtharray.qdoc
@@ -921,3 +921,55 @@
     Returns the hash value for \a key, using \a seed to seed the
     calculation.
 */
+
+/*! \fn template <typename T, qsizetype Prealloc> template <typename AT = T> qsizetype QVarLengthArray<T, Prealloc>::removeAll(const AT &t)
+    \since 6.1
+
+    Removes all elements that compare equal to \a t from the
+    array. Returns the number of elements removed, if any.
+
+    \sa removeOne()
+*/
+
+/*! \fn template <typename T, qsizetype Prealloc> template <typename AT = T> bool QVarLengthArray<T, Prealloc>::removeOne(const AT &t)
+    \since 6.1
+
+    Removes the first element that compares equal to \a t from the
+    array. Returns whether an element was, in fact, removed.
+
+    \sa removeAll()
+*/
+
+/*! \fn template <typename T, qsizetype Prealloc> template <typename Predicate> qsizetype QVarLengthArray<T, Prealloc>::removeIf(Predicate pred)
+    \since 6.1
+
+    Removes all elements for which the predicate \a pred returns true
+    from the array. Returns the number of elements removed, if any.
+
+    \sa removeAll()
+*/
+
+/*! \fn template <typename T, qsizetype Prealloc, typename AT> qsizetype erase(QVarLengthArray<T, Prealloc> &array, const AT &t)
+    \relates QVarLengthArray
+    \since 6.1
+
+    Removes all elements that compare equal to \a t from the
+    array \a array. Returns the number of elements removed, if any.
+
+    \note \a t is not allowed to be a reference to an element inside \a
+    array. If you cannot be sure that this is not the case, take a copy
+    of \a t and call this function with the copy.
+
+    \sa erase_if()
+*/
+
+/*! \fn template <typename T, qsizetype Prealloc, typename Predicate> qsizetype erase_if(QVarLengthArray<T, Prealloc> &array, Predicate pred)
+    \relates QVarLengthArray
+    \since 6.1
+
+    Removes all elements for which the predicate \a pred returns true
+    from the list \a array. Returns the number of elements removed, if
+    any.
+
+    \sa erase()
+*/