QString, QByteArray: don't detach in removeIf/erase/eraseif()

If the object is shared, instead of detaching, copy characters from
"this" to a new object except for the chacters that would be erased,
this is more efficient than detaching (which would copy the whole data
then erase).

- Extend tst_QString::removeIf() to catch a corner-case (that I saw
  with tst_QByteArray::removeIf()).

- Add q_uninitialized_remove_copy_if, which works like
  std::remove_copy_if but for uninitialized memory like
  q_uninitialized_relocate_n (but copies rather than relocates/moves).
  With the same static_assert from q_relocate_overlap_n that the type
  destructor is non-throwing.

Added q_uninitialized_remove_copy_if in this commit rather than a
separate one so that it's unittested by its usage in eraseIf().

[ChangeLog][QtCore][QString, QByteArray] Removing characters from a
currently shared string or byte array is now done more efficiently

Task-number: QTBUG-106181
Task-number: QTBUG-106183
Change-Id: Icc0ed31633cef71d482b97e0d2d20d763163d383
Reviewed-by: Thiago Macieira <thiago.macieira@intel.com>

1 files changed, 35 insertions, 0 deletions

diff --git a/src/corelib/tools/qcontainertools_impl.h b/src/corelib/tools/qcontainertools_impl.h
index adaa254a04..da35c511f9 100644
--- a/src/corelib/tools/qcontainertools_impl.h
+++ b/src/corelib/tools/qcontainertools_impl.h
@@ -86,6 +86,41 @@ void q_uninitialized_relocate_n(T* first, N n, T* out)
 
 QT_WARNING_POP
 
+/*!
+    \internal
+    Copies all elements, except the ones for which \a pred returns \c true, from
+    range [first, last), to the uninitialized memory buffer starting at \a out.
+
+    It's undefined behavior if \a out points into [first, last).
+
+    Returns a pointer one past the last copied element.
+
+    If an exception is thrown, all the already copied elements in the destination
+    buffer are destroyed.
+*/
+template <typename T, typename Predicate>
+T *q_uninitialized_remove_copy_if(T *first, T *last, T *out, Predicate &pred)
+{
+    static_assert(std::is_nothrow_destructible_v<T>,
+                  "This algorithm requires that T has a non-throwing destructor");
+    Q_ASSERT(!q_points_into_range(out, first, last));
+
+    T *dest_begin = out;
+    QT_TRY {
+        while (first != last) {
+            if (!pred(*first)) {
+                new (std::addressof(*out)) T(*first);
+                ++out;
+            }
+            ++first;
+        }
+    } QT_CATCH (...) {
+        std::destroy(std::reverse_iterator(out), std::reverse_iterator(dest_begin));
+        QT_RETHROW;
+    }
+    return out;
+}
+
 template<typename iterator, typename N>
 void q_relocate_overlap_n_left_move(iterator first, N n, iterator d_first)
 {