Effiziente String-Verkettung in C++

Reservieren Sie Ihr letztes Leerzeichen vorher und verwenden Sie dann die Append-Methode mit einem Puffer. Angenommen, Sie erwarten, dass Ihre endgültige Zeichenfolgenlänge 1 Million Zeichen beträgt:

std::string s;
s.reserve(1000000);

while (whatever)
{
  s.append(buf,len);
}

Ich würde mir keine Sorgen machen. Wenn Sie dies in einer Schleife tun, werden die Speicher immer von Strings vorab zugewiesen, um die Neuzuordnung zu minimieren. Verwenden Sie in diesem Fall einfach operator+=. Und wenn Sie es manuell tun, so oder länger

a + " : " + c

Dann werden temporäre Dateien erstellt - selbst wenn der Compiler einige Rückgabewertkopien entfernen könnte. Das liegt daran, dass in einem nacheinander aufgerufenen operator+ nicht bekannt ist, ob der Referenzparameter auf ein benanntes Objekt oder ein temporäres Objekt verweist, das von einem untergeordneten operator+-Aufruf zurückgegeben wird. Ich möchte mir keine Sorgen darüber machen, bevor ich nicht zuerst ein Profil erstellt habe. Aber nehmen wir ein Beispiel dafür. Wir führen zuerst Klammern ein, um die Bindung deutlich zu machen. Ich stelle die Argumente direkt nach der Funktionsdeklaration, die der Klarheit halber verwendet wird. Darunter zeige ich, was der resultierende Ausdruck dann ist:

((a + " : ") + c) 
calls string operator+(string const&, char const*)(a, " : ")
  => (tmp1 + c)

In diesem Zusatz wurde tmp1 beim ersten Aufruf von operator + mit den angezeigten Argumenten zurückgegeben. Wir gehen davon aus, dass der Compiler wirklich klug ist und die Rückgabewertkopie optimiert. So erhalten wir einen neuen String, der die Verkettung von a und " : " enthält. Nun passiert das:

(tmp1 + c)
calls string operator+(string const&, string const&)(tmp1, c)
  => tmp2 == <end result>

Vergleichen Sie das mit dem folgenden:

std::string f = "hello";
(f + c)
calls string operator+(string const&, string const&)(f, c)
  => tmp1 == <end result>

Es verwendet dieselbe Funktion für eine temporäre und für eine benannte Zeichenfolge! Also muss der Compiler has das Argument in einen neuen String kopieren und an diesen anhängen und es aus dem Hauptteil von operator+ zurückgeben. Es kann nicht die Erinnerung eines temporären nehmen und an das anhängen. Je größer der Ausdruck ist, desto mehr Kopien müssen gemacht werden. 

Next Visual Studio und GCC werden die Semantik von c ++ 1x move (ergänzende copy-Semantik ) und rvalue-Referenzen als experimentelle Ergänzung unterstützen. So können Sie herausfinden, ob der Parameter auf einen temporären Wert verweist. Dadurch werden solche Zusätze erstaunlich schnell, da alle oben genannten Punkte in einer "Add-Pipeline" ohne Kopien landen.

Wenn sich herausstellt, dass es einen Engpass gibt, können Sie dies trotzdem tun

 std::string(a).append(" : ").append(c) ...

Die append-Aufrufe fügen das Argument an *this an und geben dann einen Verweis auf sich selbst zurück. Daher wird dort kein Kopieren von Provisorien durchgeführt. Alternativ kann der operator+= verwendet werden, aber Sie benötigen hässliche Klammern, um die Rangfolge festzulegen.

Für die meisten Anwendungen spielt es keine Rolle. Schreiben Sie einfach Ihren Code, wissen Sie nicht genau, wie der Operator + genau funktioniert, und nehmen Sie die Sache nur in die eigenen Hände, wenn es zu einem offensichtlichen Engpass wird.

Im Gegensatz zu .NET System.String sind C++ - std :: stringsmutable und können daher durch einfache Verkettung genauso schnell erstellt werden wie durch andere Methoden.

vielleicht stattdessen std :: stringstream?

Aber ich stimme mit dem Gefühl überein, dass Sie es wahrscheinlich nur pflegbar und verständlich halten sollten und dann ein Profil erstellen, um zu sehen, ob Sie wirklich Probleme haben. 

In Imperfect C++ präsentiert Matthew Wilson einen dynamic - String-Verkettener, der die Länge des letzten Strings vorberechnet, um nur eine Zuweisung zu erhalten, bevor alle Teile verkettet werden. Wir können auch einen statischen Verkettener implementieren, indem wir mit expression-Vorlagen spielen.

Diese Art von Idee wurde in STLport std :: string implementiert - die Konformität mit dem Standard ist aufgrund dieses präzisen Hacks nicht gegeben.

std::stringoperator+ weist einen neuen String zu und kopiert jedes Mal die beiden Operanden-Strings. mehrmals wiederholen und es wird teuer, O (n).

Andererseits erhöhen std::stringappend und operator+= die Kapazität jedes Mal um 50%, wenn die Zeichenfolge erhöht werden muss. Dadurch wird die Anzahl der Speicherzuordnungen und Kopiervorgänge erheblich reduziert, O (log n).

Für kleine Zeichenfolgen spielt es keine Rolle .. Wenn Sie große Zeichenfolgen haben, sollten Sie sie besser als Vektor oder in einer anderen Sammlung als Teile speichern. Und fügen Sie Ihren Algorithmus hinzu, um mit solchen Daten anstelle der einen großen Zeichenkette zu arbeiten.

Ich bevorzuge std :: ostringstream für komplexe Verkettungen.

Wie bei den meisten Dingen ist es einfacher, nichts zu tun, als es zu tun. 

Wenn Sie große Zeichenfolgen an eine grafische Benutzeroberfläche ausgeben möchten, kann es sein, dass das, was Sie ausgeben, die Zeichenfolgen in Teilen besser verarbeiten kann als große Zeichenfolgen (z. B. Verketten von Text in einem Texteditor) Strukturen).

Wenn Sie in eine Datei ausgeben möchten, streamen Sie die Daten, anstatt einen großen String zu erstellen und diesen auszugeben.

Ich habe nie die Notwendigkeit gefunden, die Verkettung schneller zu machen, wenn ich unnötige Verkettung aus langsamem Code entfernt habe.

Wahrscheinlich beste Leistung, wenn Sie Platz in der resultierenden Zeichenfolge im Voraus reservieren (reservieren). 

template<typename... Args>
std::string concat(Args const&... args)
{
    size_t len = 0;
    for (auto s : {args...})  len += strlen(s);

    std::string result;
    result.reserve(len);    // <--- preallocate result
    for (auto s : {args...})  result += s;
    return result;
}

Verwendungszweck:

std::string merged = concat("This ", "is ", "a ", "test!");

Ein einfaches Array von Zeichen, gekapselt in einer Klasse, die die Array-Größe und die Anzahl der zugewiesenen Bytes verfolgt, ist das schnellste.

Der Trick besteht darin, beim Start nur eine große Zuweisung vorzunehmen.

beim

https://github.com/pedro-vicente/table-string

Benchmarks

X86 Debug Build für Visual Studio 2015, erhebliche Verbesserung gegenüber C++ std :: string.

| API                   | Seconds           
| ----------------------|----| 
| SDS                   | 19 |  
| std::string           | 11 |  
| std::string (reserve) | 9  |  
| table_str_t           | 1  |