wake-up-neo.com

Effiziente String-Verkettung in C++

Ich hörte ein paar Leute, die sich Sorgen um "+" - Operator in std :: string machten und verschiedene Problemumgehungen, um die Verkettung zu beschleunigen. Ist eines davon wirklich notwendig? Wenn ja, wie kann man Strings in C++ am besten verketten?

89
sneg

Die zusätzliche Arbeit lohnt sich wahrscheinlich nicht, es sei denn, Sie benötigen wirklich Effizienz. Sie werden wahrscheinlich viel bessere Effizienz erreichen, wenn Sie stattdessen Operator + = verwenden. 

Nach diesem Haftungsausschluss beantworte ich Ihre eigentliche Frage ...

Die Effizienz der STL-Stringklasse hängt von der verwendeten STL-Implementierung ab.

Sie können sich Effizienz garantieren und besser steuern durch manuelles Verketten über die integrierten Funktionen von c durchführen. 

Warum operator + nicht effizient ist:

Schauen Sie sich diese Schnittstelle an:

template <class charT, class traits, class Alloc>
basic_string<charT, traits, Alloc>
operator+(const basic_string<charT, traits, Alloc>& s1,
          const basic_string<charT, traits, Alloc>& s2)

Sie können sehen, dass nach jedem + ein neues Objekt zurückgegeben wird. Das bedeutet, dass jedes Mal ein neuer Puffer verwendet wird. Wenn Sie eine Menge zusätzlicher Operationen ausführen, ist dies nicht effizient. 

Warum können Sie es effizienter machen:

  • Sie garantieren Effizienz, anstatt einem Delegierten zu vertrauen, dass er dies effizient für Sie erledigt
  • die Klasse std :: string weiß nichts über die maximale Größe Ihrer Zeichenfolge und auch nicht, wie oft Sie daran verkettet werden. Sie verfügen möglicherweise über dieses Wissen und können auf der Grundlage dieser Informationen etwas tun. Dies führt zu weniger Neuzuweisungen. 
  • Sie steuern die Puffer manuell, sodass Sie sicher sein können, dass Sie die gesamte Zeichenfolge nicht in neue Puffer kopieren, wenn Sie dies nicht wünschen. 
  • Sie können den Stapel für Ihre Puffer anstelle des Heap verwenden, der wesentlich effizienter ist. 
  • string + Operator erstellt ein neues String-Objekt und gibt es mit einem neuen Puffer zurück. 

Überlegungen zur Implementierung:

  • Verfolgen Sie die Saitenlänge.
  • Halten Sie einen Zeiger auf das Ende der Zeichenfolge und den Anfang oder nur den Anfang und verwenden Sie den Anfang + die Länge als Versatz, um das Ende der Zeichenfolge zu finden. 
  • Stellen Sie sicher, dass der Puffer, in dem Sie Ihre Zeichenfolge speichern, groß genug ist, sodass Sie keine Daten neu zuordnen müssen
  • Verwenden Sie strcpy anstelle von strcat, sodass Sie nicht über die Länge der Zeichenfolge iterieren müssen, um das Ende der Zeichenfolge zu finden.

Seildatenstruktur:

Wenn Sie wirklich schnelle Verkettungen benötigen, sollten Sie eine Seildatenstruktur verwenden.

78
Brian R. Bondy

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);
}
68

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.

11
Pesto

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.

7
James Curran

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. 

5
Tim

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.

4
Luc Hermitte

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).

3
timmerov

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.

2
Mykola Golubyev

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.

2
Pete Kirkham

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!");
0
LanDenLabs

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  |  
0
Pedro Vicente