Effiziente QString-Verkettung mit Folding C++ 17 Template-Parametern

qt, QString, expression

In C++ ist es üblich, mit operator+ eine Zeichenfolgenverkettung durchzuführen, unabhängig davon, ob Sie die Standardbibliothek (oder STL) oder Qt verwenden. Dadurch können Sie Dinge wie den folgenden Ausschnitt schreiben:

QString statement{"I'm not"};
QString number{"a number"};
QString space{" "};
QString period{". "};
QString result = statement + space + number + period;

Das hat aber einen großen Nachteil – unnötiges Erzeugen von temporären Zwischenergebnissen. Im vorherigen Beispiel gibt es nämlich einen temporären String, um das Ergebnis des +-Operators und den leeren Teil des Ausdrucks zu speichern, dann wird dieser String mit einer Zahl verkettet, die einen anderen temporären String zurückgibt. Dann wird die zweite temporäre Linie mit dem Punkt verbunden, der das Endergebnis liefert, wonach die temporären Linien zerstört werden.

Das bedeutet, dass es fast so viele unnötige Zuweisungen und Trennungen wie Aufrufe an operator+ gibt. Außerdem werden dieselben Daten mehrfach kopiert. Beispielsweise wird der Inhalt einer Anweisungszeichenfolge zuerst in das erste temporäre Objekt kopiert, dann vom ersten temporären Objekt zum zweiten und dann vom zweiten temporären Objekt zum Endergebnis.

Temporäre Variablen

Dies kann auf viel effizientere Weise erfolgen, indem eine Zeichenfolgeninstanz erstellt wird, die den zum Speichern des Endergebnisses erforderlichen Speicher vorab zuweist und dann die QString::appendmember-Funktion nacheinander aufruft, um alle Zeichenfolgen hinzuzufügen, die wir verketten möchten einzeln:

QString result;
result.reserve(statement.length() + number.length() + space.length() + period.length();
result.append(statement);
result.append(number);
result.append(space);
result.append(period);

Temporäre Variablen

Alternativ könnte man QString::resizeanstelle von QString::reserve verwenden und dann std::copy(oder std::memcpy) verwenden, um die Daten hinein zu kopieren (später werden wir sehen, wie man std::copy zur String-Verkettung verwendet). . Dies wird wahrscheinlich die Leistung ein wenig verbessern (abhängig von Compiler-Optimierungen), da QString::append prüfen muss, ob die Kapazität des Strings groß genug ist, um den resultierenden String aufzunehmen. std::copyalgorithm hat keine unnötige zusätzliche Prüfung, die ihm einen kleinen Vorteil verschaffen könnte.

Beide Ansätze sind wesentlich effizienter als die Verwendung von operator+ , aber es wäre lästig, solchen Code jedes Mal zu schreiben, wenn Sie mehrere Zeilen verketten möchten.

Algorithmus std::akkumulieren

Bevor wir fortfahren, wie Qt dieses Problem jetzt löst und wie es in Qt 6 mit den großartigen Funktionen von C++17 verbessert werden kann, schauen wir uns einen der wichtigsten und leistungsfähigsten Algorithmen aus der Standardbibliothek an, den Standardalgorithmus: :accumulate .

Stellen Sie sich eine Sequenz (z. B. einen QVector) von Strings vor, die wir verketten möchten, anstatt sie in separaten Variablen zu haben.

Mit std::accumulate würde die String-Verkettung so aussehen:

QVector<QString> strings{ . . . };
std::accumulate(strings.cbegin(), strings.cend(), QString{});

Der Algorithmus tut das, was Sie in diesem Beispiel erwarten würden – er beginnt mit einem leeren QString und fügt ihm jeden String aus dem Vektor hinzu, wodurch ein verketteter String entsteht.

Dies wäre genauso ineffizient wie das ursprüngliche Beispiel der Verwendung von operator+ für die Verkettung, da std::accumulate standardmäßig operator+ intern verwendet.

Um diese Implementierung zu optimieren, können Sie wie im vorherigen Abschnitt einfach std::accumulate verwenden, um die Größe der resultierenden Zeichenfolge zu berechnen, anstatt eine vollständige Verkettung damit durchzuführen:

QVector<QString> strings{ . . . };
QString result;
result.resize(
    std::accumulate(strings.cbegin(), strings.cend(),
                    0, [] (int acc, const QString& s) {
                        return s.length();
                    }));

Dieses Mal beginnt std::accumulate bei einem Anfangswert von 0 und addiert für jede Zeichenfolge im Vektor der Zeichenfolgen die Länge zu diesem Anfangswert und gibt schließlich die Summe der Längen aller Zeichenfolgen im Vektor zurück.

Das ist es, was std::accumulate für die meisten Leute bedeutet - eine Art Akkumulation . Aber das ist eine ziemlich vereinfachende Ansicht.

Im ersten Beispiel wurden tatsächlich alle Strings im Vektor aufsummiert . Aber das zweite Beispiel ist ein wenig anders. Tatsächlich werden die Elemente eines Vektors nicht summiert. Der Vektor enthält QStrings und ganze Zahlen werden hinzugefügt.

Die Stärke von std::accumulate besteht darin, dass Sie ihm eine benutzerdefinierte Operation übergeben können. Die Operation nimmt einen zuvor akkumulierten Wert und ein Element aus der ursprünglichen Sammlung und generiert einen neuen akkumulierten Wert. Wenn std::accumulate diese Operation zum ersten Mal aufruft, wird ihr der Anfangswert als Akkumulator und das erste Element der Quellsammlung übergeben. Es nimmt das Ergebnis und übergibt es zusammen mit dem zweiten Element der ursprünglichen Sammlung an den nächsten Aufruf der Operation. Dies wird wiederholt, bis die gesamte ursprüngliche Sammlung verarbeitet wurde und der Algorithmus das Ergebnis des letzten Aufrufs an die Operation zurückgibt.

Wie Sie dem vorherigen Codeausschnitt entnehmen können, muss der Akkumulator nicht vom gleichen Typ sein wie die Werte im Vektor. Es gab einen Vektor von Zeichenketten, und der Akkumulator war eine Ganzzahl.

Der obige std::copy-Algorithmus nimmt eine Sequenz von zu kopierenden Elementen (als Eingabe-Iterator-Paar) und ein Ziel (als Ausgabe-Iterator), wo die Elemente kopiert werden sollen. Es gibt einen Iterator zurück, der auf das Element nach dem letzten kopierten Element in der Zielsammlung zeigt.

Das heißt, wenn wir die Daten einer Quellzeile mit std::copy in die Zielzeile kopieren, erhalten wir einen Iterator, der genau auf die Stelle zeigt, an der wir die Daten der zweiten Zeile kopieren möchten.

Es gibt also eine Funktion, die einen String (als Paar Iteratoren) und einen Ausgabe-Iterator nimmt und anschließend einen neuen Ausgabe-Iterator liefert. Dies ähnelt dem, was als Operation für std::accumulate verwendet werden kann, um eine effiziente Zeichenfolgenverkettung zu implementieren:

QVector<QString> strings{ . . . };
QString result;
result.resize( . . . );

std::accumulate(strings.cbegin(), strings.cend(), result.begin(),
                [] (const auto& dest, const QString& s) {
                    return std::copy(s.cbegin(), s.cend(), dest);
                });

Der erste Aufruf von std::copy kopiert die erste Zeile an das in result.begin() angegebene Ziel. Es wird direkt nach dem letzten kopierten Zeichen einen Iterator an die Ergebniszeichenfolge zurückgeben, und dort wird die zweite Zeichenfolge aus dem Vektor kopiert. Danach wird die dritte Zeile kopiert und so weiter.

Temporäre Variablen

Am Ende erhalten wir den verketteten String.

Vorlagen für rekursive Ausdrücke

Jetzt können wir mit operator+ in Qt zur effizienten String-Verkettung zurückkehren.

QString result = statement + space + number + period;

Sie können sehen, dass das Problem mit der String-Verkettung darauf zurückzuführen ist, dass C++ den vorherigen Ausdruck schrittweise auswertet und dabei operator+ mehrmals aufruft, wobei jeder Aufruf eine neue QString-Instanz zurückgibt.

Obwohl es nicht möglich ist, die Art und Weise zu ändern, wie dies in C++ ausgewertet wird, kann eine Technik namens Ausdrucksvorlagen verwendet werden, um die tatsächliche Auswertung der resultierenden Zeichenfolge zu verzögern, bis der gesamte Ausdruck definiert wurde. Dies kann erreicht werden, indem der Rückgabetyp von operator+ nicht in QString geändert wird, sondern in einen benutzerdefinierten Typ, der einfach die zu verkettenden Zeichenfolgen speichert, ohne die Verkettung tatsächlich durchzuführen.

Genau das macht Qt mit 4.6, wenn Sie die schnelle String-Verkettung aktivieren. Anstatt einen QString zurückzugeben, gibt operator+ eine Instanz einer verborgenen Klassenvorlage namens QStringBuilder zurück. Die Vorlage QStringBuilderclass ist nur ein Dummy-Typ, der Verweise auf die Argumente enthält, die an operator+ übergeben werden.

Eine komplexere Version des Folgenden:

template <typename Left, typename Right>
class QStringBuilder {
    const Left& _left;
    const Right& _right;
};

Wenn Sie mehrere Strings verketten, erhalten Sie am Ende einen komplexeren Typ, bei dem mehrere QStringBuilder ineinander verschachtelt sind. Sowas in der Art:

QStringBuilder<QString, QStringBuilder<QString, QStringBuilder<QString, QString>>>

Dieser Typ ist nur eine komplizierte Art zu sagen: "Ich halte vier Zeilen, die verkettet werden müssen".

Wenn Sie aufgefordert werden, einen QStringBuilder in einen QString umzuwandeln (z. B. durch Zuweisung an das Ergebnis eines QString), berechnet er zuerst die Gesamtgröße aller enthaltenen Strings, weist dann eine QString-Instanz dieser Größe zu und kopiert schließlich die Strings einzeln eins in die resultierende Zeichenfolge.

Im Wesentlichen wird es dasselbe tun, was zuvor getan wurde, aber es wird automatisch ausgeführt, ohne dass Sie "einen Finger heben" müssen.

Vorlagen mit einer variablen Anzahl von Argumenten

Das Problem bei der aktuellen Implementierung von QStringBuilder ist, dass sie einen Container mit einer beliebigen Anzahl von Strings durch Verschachtelung implementiert. Jede QStringBuilder-Instanz kann genau zwei Elemente enthalten, unabhängig davon, ob es sich um Zeichenfolgen oder andere QStringBuilder-Instanzen handelt.

Das bedeutet, dass alle QStringBuilder-Instanzen eine Art binärer Baum mit QStrings als Blattknoten sind. Wann immer es etwas mit den enthaltenen Strings tun muss, muss QStringBuilder seinen linken Teilbaum und dann seinen rechten Teilbaum rekursiv verarbeiten.

Anstatt Binärbäume zu erstellen, können Sie variadische Vorlagen verwenden (verfügbar seit C++11, das bei der Erstellung von QStringBuilder nicht verfügbar war). Vorlagen mit Variablenargumenten ermöglichen es Ihnen, Klassen und Funktionen mit einer beliebigen Anzahl von Vorlagenargumenten zu erstellen.

Das bedeutet, dass Sie mit std::tuplewe ein QStringBuilder-Klassen-Template erstellen können, das beliebig viele Strings enthält:

template <typename... Strings>
class QStringBuilder {
    std::tuple<Strings...> _strings;
};

Wenn wir einen neuen String zum QStringBuilder hinzufügen müssen, können wir ihn einfach mit std::tuple_cat an das Tupel anhängen, das die beiden Tupel verkettet (wir verwenden operator% anstelle von operator+, da dieser Operator auch von QString und QStringBuilder unterstützt wird). :

template <typename... Strings>
class QStringBuilder {
    std::tuple<Strings...> _strings;

    template <typename String>
    auto operator%(String&& newString) &&
    {
        return QStringBuilder<Strings..., String>(
            std::tuple_cat(_strings, std::make_tuple(newString)));
    }
};

Parameter der Vertragsvorlage

Das ist alles schön und gut, aber die Frage ist, wie der fold-Ausdruck (der Strings-Teil) mit Paketen umgeht.

C++17 hat ein neues Konstrukt für die Handhabung von Parameterpaketen eingeführt, das als Vorlagenparameterfaltung bezeichnet wird.

Die allgemeine Form der Vorlagenparameterfaltung ist wie folgt (operator+ kann durch einen anderen binären Operator wie *, %... ersetzt werden):

(init + ... + pack)

oder:

(pack + ... + init)

Die erste Option heißt linker Ausdruck der Vorlagenparameter (linker Ausdruck) , behandelt die Operation als linksassoziativ (linksassoziativ), und die zweite Option heißt *rechte Faltung der Vorlagenparameter (rechter Ausdruck) * weil es die Operation als rechtsassoziativ behandelt (assoziativ rechts).

Wenn man Strings in einem Template-Parameterpaket mit Template-Parameterfaltung verketten möchte, könnte man das so machen:

template <typename... Strings>
auto concatenate(Strings... strings)
{
    return (QString{} + ... + strings);
}

Zuerst wird operator+ für den Anfangswert von QString{} und das erste Element des Parameterpakets aufgerufen. Anschließend wird operator+ für das Ergebnis des vorherigen Aufrufs und das zweite Element des Parameterpakets aufgerufen. Und so weiter, bis alle Elemente verarbeitet wurden.

Klingt vertraut, nicht wahr?

Dasselbe Verhalten wurde bei std::accumulate beobachtet. Der einzige Unterschied besteht darin, dass der Algorithmus std::accumulate zur Laufzeit mit Datenfolgen (Vektoren, Arrays, Listen usw.) arbeitet. Wohingegen Template-Parameter-Folds mit Sequenzen zur Kompilierzeit arbeiten, d. h. Paketen von Template-Parametern mit einer variablen Anzahl von Argumenten.

Sie können dieselben Schritte ausführen, um die vorherige Verkettungsimplementierung zu optimieren, die für std::accumulate verwendet wurde. Zuerst müssen Sie die Summe aller Saitenlängen berechnen. Es ist ziemlich einfach mit Template-Parameterfaltungen:

template <typename... Strings>
auto concatenate(Strings... strings)
{
    const auto totalSize = (0 + ... + strings.length());
    . . .
}

Wenn ein Vorlagenparameter fold das Parameterpaket erweitert, erhält es den folgenden Ausdruck:

0 + string1.length() + string2.length() + string3.length()

Wir haben also die Größe der resultierenden Zeichenfolge erhalten. Jetzt können wir damit fortfahren, eine Zeichenfolge zu extrahieren, die groß genug für das Ergebnis ist, und die ursprünglichen Zeichenfolgen nacheinander hinzuzufügen.

Wie bereits erwähnt, funktioniert die Vorlagenparameterfaltung mit binären C++-Operatoren. Wenn wir eine Funktion für jedes Element in einem Parameterpaket ausführen möchten, können wir einen der seltsamsten Operatoren in C und C++ verwenden, den Kommaoperator.

template <typename... Strings>
auto concatenate(Strings... strings)
{
    const auto totalSize = (0 + ... + strings.length());
    QString result;
    result.reserve(totalSize);

    (result.append(strings), ...);

    return result;
}

Dadurch wird jede Zeile im Parameterpaket angehängt, was zu einer verketteten Zeile führt.

Benutzerdefinierte Operatoren mit Vorlagenparameterfalten

Der zweite Ansatz, der mit std::accumulate verwendet wurde, war etwas komplexer. Es war notwendig, einen benutzerdefinierten Vorgang für die Akkumulation bereitzustellen. Der Akkumulator (Akkumulator) war ein Iterator in der Zielsammlung, der angab, wohin die nächste Zeile kopiert werden sollte.

Wenn wir eine benutzerdefinierte Operation mit Vorlagenparameterfaltungen haben möchten, müssen wir einen binären Operator erstellen. Ein Operator wie das Lambda, das an std::accumulate übergeben wurde, muss einen Ausgabe-Iterator und einen String annehmen, er muss std::copy aufrufen, um die String-Daten in diesen Iterator zu kopieren, und er muss einen neuen Iterator zurückgeben, der to angibt das Element nach dem letzten kopierten Zeichen.

Dazu können Sie den Operator << neu definieren:

template <typename Dest, typename String>
auto operator<< (Dest dest, const String& string)
{
    return std::copy(string.cbegin(), string.cend(), dest);
}

Mit dieser implementierten Vorlagenparameterfaltung, die alle Zeilen in den Zielpuffer kopiert, wird dies ziemlich einfach. Der Startwert ist der Start-Iterator des Zielpuffers und << jede der Zeichenfolgen im Parameterpaket dazu:

template <typename... Strings>
auto concatenate(Strings... strings)
{
    const auto totalSize = (0 + ... + strings.length());
    QString result;
    result.resize(totalSize);

    (result.begin() << ... << strings);

    return result;
}

Folding-Template-Parameter und Tupel

Jetzt wissen wir, wie man eine Sammlung von Strings effektiv verkettet – sei es ein Vektor oder ein variadischer Satz von Parametern.

Das Problem ist, dass QStringBuilder das auch nicht hat. Es speichert Strings in einem std::tuple, das weder eine iterierbare Sammlung noch ein Parameterpaket ist.

Um mit Rollup für Vorlagenparameter arbeiten zu können, benötigen Sie Parameterpakete. Anstelle eines Parameterpakets, das Strings enthält, können Sie ein Paket erstellen, das eine Liste von Indizes von 0 bis n-1 enthält, die später mit std::getto verwendet werden können, um auf Werte innerhalb eines Tupels zuzugreifen.

Dieses Paket wird einfach mit der std::index_sequence erstellt, die eine Liste von Ganzzahlen zur Kompilierzeit darstellt. Sie können eine Hilfsfunktion erstellen, die std::index_sequence akzeptiert als Argument und verwenden Sie dann std::get (_strings), um nacheinander auf Zeichenfolgen aus einem Tupel aus Vorlagenparameterfaltungen zuzugreifen.

template <typename... Strings>
class QStringBuilder {
    using Tuple = std::tuple<Strings...>;
    Tuple _strings;

    template <std::size_t... Idx>
    auto concatenateHelper(std::index_sequence<Idx...>) const
    {
        const auto totalSize = (std::get<Idx>(_strings).size() + ... + 0);

        QString result;
        result.resize(totalSize);

        (result.begin() << ... << std::get<Idx>(_strings));

        return result;
    }
};

Sie müssen eine Wrapper-Funktion erstellen, die eine Indexsequenz für das Tupel erstellt, und die concatenateHelper-Funktion aufrufen:

template <typename... Strings>
class QStringBuilder {
    . . .

    auto concatenate() const
    {
        return concatenateHelper(
            std::index_sequence_for<Strings...>{});
    }
};

Fazit

In diesem Artikel geht es nur um die eigentliche Zeichenfolgenverkettung. Um dies auf einen echten QStringBuilder anzuwenden, sind einige weitere Dinge erforderlich, und die Implementierung wird ein wenig überwältigend, um sie als Blogartikel zu lesen.

Sie müssen bei der Überladung von Operatoren vorsichtig sein. Man müsste std::enable_iflike als aktuelle Implementierung von QStringBuilder verwenden, damit es mit allen verkettbaren Qt-Typen funktioniert und den globalen Raum nicht mit diesen Operatoren durcheinander bringt.

Es wäre auch nützlich, temporäre Werte, die an die String-Verkettung übergeben werden, sicherer handhaben zu können, da QStringBuilder nur String-Referenzen speichert, die im Fall von temporären Strings leicht zu baumelnden Referenzen werden können.