diff options
author | Marc Mutz <marc.mutz@kdab.com> | 2020-05-13 20:18:46 +0200 |
---|---|---|
committer | Marc Mutz <marc.mutz@kdab.com> | 2020-05-14 20:30:22 +0000 |
commit | 49e69827d2be045751ded48645904b4349115212 (patch) | |
tree | 75edfd13fb2069c486d228dfba0818e69a99612e /src/corelib/text/qstring.cpp | |
parent | 7ea6cee52533009799e025e6f66c5ff2cb907b23 (diff) |
QString: fix quadratic behavior in QString::remove(QString)
Calling linear-complexity remove(int, int) in a loop is O(N²).
Fix by implementing a remove_if()-like algorithm which ensures each
character is written at most once, which is linear.
[ChangeLog][QtCore][QString] Fixed quadratic worst-case complexity of
remove(QString). The function now has linear complexity in all cases.
Pick-to: 5.15
Change-Id: I12f70fbc83fb5da4a9aae4bd02f525d7657cc940
Reviewed-by: Lars Knoll <lars.knoll@qt.io>
Reviewed-by: Edward Welbourne <edward.welbourne@qt.io>
Diffstat (limited to 'src/corelib/text/qstring.cpp')
-rw-r--r-- | src/corelib/text/qstring.cpp | 34 |
1 files changed, 24 insertions, 10 deletions
diff --git a/src/corelib/text/qstring.cpp b/src/corelib/text/qstring.cpp index 1e227a09ba..fc1a9f2a83 100644 --- a/src/corelib/text/qstring.cpp +++ b/src/corelib/text/qstring.cpp @@ -2844,16 +2844,30 @@ QString &QString::remove(int pos, int len) template<typename T> static void removeStringImpl(QString &s, const T &needle, Qt::CaseSensitivity cs) { - const int needleSize = needle.size(); - if (needleSize) { - if (needleSize == 1) { - s.remove(needle.front(), cs); - } else { - int i = 0; - while ((i = s.indexOf(needle, i, cs)) != -1) - s.remove(i, needleSize); - } - } + const auto needleSize = needle.size(); + if (!needleSize) + return; + + // avoid detach if nothing to do: + int i = s.indexOf(needle, 0, cs); + if (i < 0) + return; + + const auto beg = s.begin(); // detaches + auto dst = beg + i; + auto src = beg + i + needleSize; + const auto end = s.end(); + // loop invariant: [beg, dst[ is partial result + // [src, end[ still to be checked for needles + while (src < end) { + const auto i = s.indexOf(needle, src - beg, cs); + const auto hit = i == -1 ? end : beg + i; + const auto skipped = hit - src; + memmove(dst, src, skipped * sizeof(QChar)); + dst += skipped; + src = hit + needleSize; + } + s.truncate(dst - beg); } /*! |