C++ und String-Ersetzung

von Hubert Schmid vom 2012-03-04

Vor kurzem gab es in einer deutschen Newsgroup zu C eine Diskussion über eine Funktion, die innerhalb einer langen Zeichenkette alle Vorkommen eines Teilausdrucks ersetzen sollte. Der Fragesteller hatte das Problem, dass seine Implementierung viel zu langsam war, was nicht weiter verwunderlich war, da der verwendete Algorithmus eine quadratische Laufzeit in der Länge der Zeichenkette aufwies.

Im Laufe der Diskussion wurden einige alternative und bessere Umsetzungen präsentiert – von durchaus erfahrenen C‑Entwicklern. Allerdings wirkten fast alle vorgeschlagenen Implementierungen auf mich recht komplex, schwer verständlich und zu spezialisiert.

Dieser Eindruck bestätigt meine Meinung zu den Unterschieden zwischen C und C++: In C sind häufig selbst einfache Aufgabenstellungen signifikante Herausforderungen. C++ bietet hingegen sinnvolle Abstraktionen – insbesondere für das Resourcenmanagement und die Fehlerbehandlung – um einfachen, sicheren und effizienten Code zu schreiben. Und wenn es darauf ankommt, erreicht man die gleiche Performance wie mit C.

Ich gehe auf die C‑Beispiele aus der erwähnten Diskussion nicht weiter ein. Stattdessen zeige ich, wie ich die Funktionalität in C++ realisieren würde. Dabei kommen immer wieder die beiden gleichen Parameter für die zu suchende Zeichenkette und den Ersetzungstext vor. Um die Beispiele im Folgenden einfacher zu halten, lagere ich diese beiden Parameter in eine separate Klasse aus.

struct substitution
{
    std::string target;
    std::string replacement;
};

Die Implementierung der Ersetzungsfunktion besteht nur aus ein paar Zeilen und ist nicht nur sehr verständlich und robust (Commit-or-Rollback Semantik) sondern auch sehr performant. Insbesondere ist die Laufzeit linear in der Größe der zu verarbeitenden Zeichenkette. Nach meiner Erfahrung ist das für die meisten Situationen hinreichend gut. Denn ich habe in produktiven Code vergleichbare Implementierungen eingesetzt, die Eingaben mit mehreren hundert Millionen Zeichen auf diese Weise verarbeitet haben, wobei das Laufzeitverhalten nie negativ aufgefallen ist.

void replace(std::string& value, const substitution& sub)
{
    std::string builder;
    std::string::size_type p;
    std::string::size_type q = 0;
    while ((p = value.find(sub.target, q)) != std::string::npos) {
        builder.append(value, q, p - q);
        builder.append(sub.replacement);
        q = p + sub.target.size();
    }
    builder.append(value, q, value.size() - q);
    value = std::move(builder);
}

Wenn doch für bestimmte Fälle die Laufzeit verbessert werden muss, kann man auf diesem Code aufbauen und muss nicht die komplette Funktion anders implementieren. Beispielsweise könnte es häufig vorkommen, dass die Funktion mit einer langen Zeichenkette aufgerufen wird, die den gesuchten Ausdruck überhaupt nicht enthält. Die obige Funktion würde in diesem Fall trotzdem die komplette Zeichenkette kopieren. Das lässt sich durch Ausrollen der ersten Schleifeniteration einfach wie folgt umgehen:

void replace(std::string& value, const substitution& sub)
{
    auto p = value.find(sub.target);
    if (p != std::string::npos) {
        std::string builder;
        builder.append(value, 0, p);
        builder.append(sub.replacement);
        auto q = p + sub.target.size();
        while ((p = value.find(sub.target, q)) != std::string::npos) {
            builder.append(value, q, p - q);
            builder.append(sub.replacement);
            q = p + sub.target.size();
        }
        builder.append(value, q, value.size() - q);
        value = std::move(builder);
    } // else: search string not found and nothing to do
}

Dadurch werden zwar Codeteile wiederholt, aber es hält sich noch hinreichend in Grenzen, und diese Optimierung ist gut vertretbar.

Eine weitere Verbesserung ergibt sich dadurch, dass Textersetzung grundsätzlich auf zwei unterschiedliche Arten genutzt werden kann: Entweder soll eine existierende Zeichenkette verändert werden, oder die Ersetzung soll auf einer Kopie erfolgen ohne die ursprüngliche Zeichenkette zu ändern. In C++ lässt sich beides relativ einfach mit nur einer Implementierung realisieren. Dafür muss ich die obige Funktion nur ein wenig refaktorisieren. Das Template wird dabei lediglich benötigt, um im Falle einer R‑Value-Referenz eine unnötige Kopie einsparen zu können.

// in private namespace ...
template <typename String>
auto replaced_aux(String&& value, const substitution& sub)
    -> std::string
{
    auto p = value.find(sub.target);
    if (p == std::string::npos) {
        /* Search string not found at all, i.e. nothing will be changed.
         * This makes it possible to avoid all copy operations - if the
         * input string is an r-value reference. */
        return std::forward<String>(value);
    } else {
        std::string builder;
        // possible optimization: estimate and reserve required capacity
        builder.append(value, 0, p);
        builder.append(sub.replacement);
        auto q = p + sub.target.size();
        while ((p = value.find(sub.target, q)) != std::string::npos) {
            builder.append(value, q, p - q);
            builder.append(sub.replacement);
            q = p + sub.target.size();
        }
        builder.append(value, q, value.size() - q);
        return std::move(builder);
    }
}

Die Umsetzung der Ersetzungsfunktionen mit Rückgabewert – also ohne die übergebene Zeichenkette zu ändern – ist damit offensichtlich. Die Überladung für eine R‑Value-Referenz ist nützlich, da sie eine unnötige und teure Kopie der Zeichenkette vermeidet, wenn die Funktion anwendbar ist und der gesuchte Ausdruck nicht gefunden werden kann.

auto replaced(const std::string& value, const substitution& sub)
    -> std::string
{
    return replaced_aux(value, sub);
}

// optional overload to optimize for r-values
auto replaced(std::string&& value, const substitution& sub)
    -> std::string
{
    return replaced_aux(std::move(value), sub);
}

Interessanterweise lässt sich die Funktion, die die Änderung in der übergebenen Zeichenkette durchführt, genauso einfach mit obigem Template realisieren. Und in diesem Fall lohnt sich ein genauerer Blick. Denn ganz offensichtlich ist diese Implementierung nicht – zumindest solange man mit der Move-Semantik noch nicht vertraut ist. Wichtig ist die Verwendung der R‑Value-Referenzen sowohl bei der Übergabe als auch bei der Zuweisung des Ergebnisses. Dadurch wird die gesamte Funktion so effizient wie bereits oben erarbeitet. Das gilt insbesondere auch für den Fall, bei dem der Suchausdruck nicht gefunden wird. Die Zeichenkette wird dabei zwar zweimal verschoben, jedoch kein einziges Mal kopiert.

void replace(std::string& value, const substitution& sub)
{
    // note usage of move assignment
    value = replaced_aux(std::move(value), sub);
}

Mir ist wichtig deutlich zu machen, dass C++ gegenüber C viele Mechanismen enthält, die die Entwicklung stark vereinfachen, ohne Performance einzubüßen. Das erfordert natürlich, dass die Sprache und die Auswirkungen der Abstraktionen von den Entwicklern hinreichend gut verstanden werden. Das gilt allerdings für praktisch alle Programmiersprachen: Ein ungenügend qualifizierter Entwickler wird in jeder Programmiersprache schlechten Code schreiben.