C ++ - Äquivalent zu StringBuffer / StringBuilder?

184

Gibt es eine C ++ Standard Template Library - Klasse , die eine effiziente String - Verkettung Funktionalität, ähnlich wie C # 's bietet String oder Java String ?

An̲̳̳drew
quelle
3
Die kurze Antwort lautet: Ja, STL hat eine Klasse dafür und das ist es auch std::ostringstream.
CoffeDeveloper
Hey @andrew. Können Sie bitte die akzeptierte Antwort ändern? Es gibt eine klare Gewinnantwort und es ist nicht die aktuell akzeptierte Antwort.
null

Antworten:

53

HINWEIS Diese Antwort hat in letzter Zeit einige Aufmerksamkeit erhalten. Ich befürworte dies nicht als Lösung (es ist eine Lösung, die ich in der Vergangenheit vor der STL gesehen habe). Es ist ein interessanter Ansatz , und nur dann angewandt werden , über soll std::stringoder std::stringstreamwenn nach dem Code Profilieren Sie entdecken , dies macht eine Verbesserung.

Normalerweise benutze ich entweder std::stringoder std::stringstream. Ich hatte noch nie Probleme damit. Normalerweise würde ich zuerst etwas Platz reservieren, wenn ich die grobe Größe der Saite im Voraus kenne.

Ich habe in der fernen Vergangenheit gesehen, wie andere Leute ihren eigenen optimierten String-Builder hergestellt haben.

class StringBuilder {
private:
    std::string main;
    std::string scratch;

    const std::string::size_type ScratchSize = 1024;  // or some other arbitrary number

public:
    StringBuilder & append(const std::string & str) {
        scratch.append(str);
        if (scratch.size() > ScratchSize) {
            main.append(scratch);
            scratch.resize(0);
        }
        return *this;
    }

    const std::string & str() {
        if (scratch.size() > 0) {
            main.append(scratch);
            scratch.resize(0);
        }
        return main;
    }
};

Es werden zwei Zeichenfolgen verwendet, eine für den Großteil der Zeichenfolge und die andere als Arbeitsbereich zum Verketten kurzer Zeichenfolgen. Die Anhänge werden optimiert, indem die kurzen Anhängevorgänge in einer kleinen Zeichenfolge zusammengefasst und dann an die Hauptzeichenfolge angehängt werden, wodurch die Anzahl der erforderlichen Neuzuweisungen für die Hauptzeichenfolge verringert wird, wenn diese größer wird.

Ich habe diesen Trick mit std::stringoder nicht benötigt std::stringstream. Ich denke, es wurde mit einer String-Bibliothek eines Drittanbieters vor std :: string verwendet, es ist so lange her. Wenn Sie eine Strategie wie dieses Profil anwenden, verwenden Sie zuerst Ihre Bewerbung.

iain
quelle
13
Das Rad neu erfinden. std :: stringstream ist die richtige Antwort. Siehe gute Antworten unten.
Kobor42
12
@ Kobor42 Ich stimme Ihnen zu, wenn ich in der ersten und letzten Zeile meiner Antwort darauf hinweise.
iain
1
Ich glaube nicht, dass die scratchSaite hier wirklich etwas bewirkt. Die Anzahl der Neuzuweisungen des Hauptstrings hängt weitgehend von seiner endgültigen Größe ab, nicht von der Anzahl der Anhängeoperationen, es sei denn, die stringImplementierung ist wirklich schlecht (dh es wird kein exponentielles Wachstum verwendet). Das "Stapeln" appendhilft also nicht, denn sobald der Basiswert stringgroß ist, wächst er nur gelegentlich in beide Richtungen. Darüber hinaus werden eine Reihe redundanter Kopiervorgänge hinzugefügt und möglicherweise mehr Neuzuweisungen (daher Aufrufe von new/ delete), da Sie an eine kurze Zeichenfolge anhängen.
BeeOnRope
@BeeOnRope Ich stimme dir zu.
iain
Ich bin mir ziemlich sicher, str.reserve(1024);dass es schneller sein würde als dieses Ding
Hanshenrik
160

Der C ++ - Weg wäre, std :: stringstream oder einfach nur String-Verkettungen zu verwenden. C ++ - Zeichenfolgen sind veränderbar, sodass die Leistungsaspekte der Verkettung weniger wichtig sind.

In Bezug auf die Formatierung können Sie alle gleichen Formatierungen in einem Stream vornehmen, jedoch auf andere Weise, ähnlich wie beicout . oder Sie können einen stark typisierten Funktor verwenden, der dies kapselt und eine String.Format-ähnliche Schnittstelle bereitstellt, z. B. boost :: format

jk.
quelle
59
C ++ - Zeichenfolgen sind veränderlich : genau. Der gesamte Grund StringBuilderbesteht darin, die Ineffizienz des unveränderlichen grundlegenden String-Typs von Java abzudecken . Mit anderen Worten, es StringBuilderhandelt sich um Patchwork, daher sollten wir froh sein, dass wir in C ++ keine solche Klasse benötigen.
Bobobobo
55
@bobobobo unveränderliche Saiten haben aber noch andere Vorteile, seine Pferde für Kurse
jk.
8
Erstellen einfache Zeichenfolgenverkettungen kein neues Objekt, also das gleiche Problem wie bei der Unveränderlichkeit in Java? Angenommen, alle Variablen sind im folgenden Beispiel Zeichenfolgen: a = b + c + d + e + f; Wird es nicht Operator + auf b und c, dann Operator + auf dem Ergebnis und d usw. aufrufen?
Serge Rogatch
9
Moment mal, die Standard-String-Klasse weiß, wie man sich selbst mutiert, aber das bedeutet nicht, dass die Ineffizienz nicht vorhanden ist. Soweit ich weiß, kann std :: string die Größe seines internen Zeichens * nicht einfach erweitern. Das bedeutet, dass eine Mutation auf eine Weise erforderlich ist, die mehr Zeichen erfordert, eine Neuzuweisung und ein Kopieren erfordert. Es ist nicht anders als ein Zeichenvektor und es ist sicherlich besser, den Platz zu reservieren, den Sie in diesem Fall benötigen.
Trygve Skogsholm
7
@TrygveSkogsholm - es unterscheidet sich nicht von einem Zeichenvektor, aber natürlich kann die "Kapazität" der Zeichenfolge größer als ihre Größe sein, sodass nicht alle Anhänge eine Neuzuweisung benötigen. Im Allgemeinen verwenden Strings eine exponentielle Wachstumsstrategie, sodass sich das Anhängen immer noch an einen linearen Kostenvorgang amortisiert. Dies unterscheidet sich von Javas unveränderlichen Strings, bei denen jeder Append-Vorgang alle Zeichen in beiden Strings in einen neuen kopieren muss, sodass eine Reihe von Appends wie O(n)im Allgemeinen endet .
BeeOnRope
93

Die std::string.appendFunktion ist keine gute Option, da sie nicht viele Arten von Daten akzeptiert. Eine nützlichere Alternative ist die Verwendung std::stringstream; wie so:

#include <sstream>
// ...

std::stringstream ss;

//put arbitrary formatted data into the stream
ss << 4.5 << ", " << 4 << " whatever";

//convert the stream buffer into a string
std::string str = ss.str();
Stu
quelle
43

std::string ist das C ++ - Äquivalent: Es ist veränderlich.

dan04
quelle
13

Sie können .append () verwenden, um Zeichenfolgen einfach zu verketten.

std::string s = "string1";
s.append("string2");

Ich denke, Sie könnten sogar in der Lage sein:

std::string s = "string1";
s += "string2";

Was die Formatierungsvorgänge von C # betrifft StringBuilder, glaube ich snprintf(oder sprintfwenn Sie das Risiko eingehen möchten, fehlerhaften Code zu schreiben ;-)), dass die Konvertierung in ein Zeichenarray und die Rückkonvertierung in eine Zeichenfolge die einzige Option ist.

Andy Shellam
quelle
Nicht auf die gleiche Weise wie printf oder .NETs String.Format, oder?
Andy Shellam
1
Es ist ein wenig unaufrichtig zu sagen, dass sie der einzige Weg sind
jk.
2
@jk - Sie sind die einzige Möglichkeit, die Formatierungsfähigkeit von .NETs StringBuilder zu vergleichen. Dies wurde in der ursprünglichen Frage speziell gestellt. Ich habe "Ich glaube" gesagt, damit ich mich irren kann, aber können Sie mir einen Weg zeigen, wie ich die Funktionalität von StringBuilder in C ++ ohne Verwendung von printf erhalten kann?
Andy Shellam
hat meine Antwort aktualisiert, um einige alternative Formatierungsoptionen einzuschließen
jk.
6

Da std::stringin C ++ veränderbar ist, können Sie das verwenden. Es hat eine += operatorund eine appendFunktion.

Wenn Sie numerische Daten anhängen müssen, verwenden Sie die std::to_stringFunktionen.

Wenn Sie noch mehr Flexibilität in Form der Serialisierung eines Objekts in eine Zeichenfolge wünschen, verwenden Sie die std::stringstreamKlasse. Sie müssen jedoch Ihre eigenen Streaming-Operator-Funktionen implementieren, damit sie mit Ihren eigenen benutzerdefinierten Klassen funktionieren.

Daemin
quelle
4

std :: string's + = funktioniert nicht mit const char * (was für Dinge wie "string to add" zu sein scheinen), daher ist die Verwendung von stringstream definitiv die nächste, die erforderlich ist - Sie verwenden einfach << anstelle von +

sergeys
quelle
3

Ein praktischer String Builder für c ++

Wie viele Leute zuvor geantwortet haben, ist std :: stringstream die Methode der Wahl. Es funktioniert gut und hat viele Konvertierungs- und Formatierungsoptionen. IMO hat es jedoch einen ziemlich unangenehmen Fehler: Sie können es nicht als Einzeiler oder als Ausdruck verwenden. Sie müssen immer schreiben:

std::stringstream ss;
ss << "my data " << 42;
std::string myString( ss.str() );

Das ist ziemlich ärgerlich, besonders wenn Sie Strings im Konstruktor initialisieren möchten.

Der Grund ist, dass a) std :: stringstream keinen Konvertierungsoperator in std :: string hat und b) die Operatoren << () des Stringstreams keine Stringstream-Referenz zurückgeben, sondern stattdessen eine std :: ostream-Referenz - die nicht weiter als String-Stream berechnet werden kann.

Die Lösung besteht darin, std :: stringstream zu überschreiben und ihm bessere Übereinstimmungsoperatoren zu geben:

namespace NsStringBuilder {
template<typename T> class basic_stringstream : public std::basic_stringstream<T>
{
public:
    basic_stringstream() {}

    operator const std::basic_string<T> () const                                { return std::basic_stringstream<T>::str();                     }
    basic_stringstream<T>& operator<<   (bool _val)                             { std::basic_stringstream<T>::operator << (_val); return *this; }
    basic_stringstream<T>& operator<<   (char _val)                             { std::basic_stringstream<T>::operator << (_val); return *this; }
    basic_stringstream<T>& operator<<   (signed char _val)                      { std::basic_stringstream<T>::operator << (_val); return *this; }
    basic_stringstream<T>& operator<<   (unsigned char _val)                    { std::basic_stringstream<T>::operator << (_val); return *this; }
    basic_stringstream<T>& operator<<   (short _val)                            { std::basic_stringstream<T>::operator << (_val); return *this; }
    basic_stringstream<T>& operator<<   (unsigned short _val)                   { std::basic_stringstream<T>::operator << (_val); return *this; }
    basic_stringstream<T>& operator<<   (int _val)                              { std::basic_stringstream<T>::operator << (_val); return *this; }
    basic_stringstream<T>& operator<<   (unsigned int _val)                     { std::basic_stringstream<T>::operator << (_val); return *this; }
    basic_stringstream<T>& operator<<   (long _val)                             { std::basic_stringstream<T>::operator << (_val); return *this; }
    basic_stringstream<T>& operator<<   (unsigned long _val)                    { std::basic_stringstream<T>::operator << (_val); return *this; }
    basic_stringstream<T>& operator<<   (long long _val)                        { std::basic_stringstream<T>::operator << (_val); return *this; }
    basic_stringstream<T>& operator<<   (unsigned long long _val)               { std::basic_stringstream<T>::operator << (_val); return *this; }
    basic_stringstream<T>& operator<<   (float _val)                            { std::basic_stringstream<T>::operator << (_val); return *this; }
    basic_stringstream<T>& operator<<   (double _val)                           { std::basic_stringstream<T>::operator << (_val); return *this; }
    basic_stringstream<T>& operator<<   (long double _val)                      { std::basic_stringstream<T>::operator << (_val); return *this; }
    basic_stringstream<T>& operator<<   (void* _val)                            { std::basic_stringstream<T>::operator << (_val); return *this; }
    basic_stringstream<T>& operator<<   (std::streambuf* _val)                  { std::basic_stringstream<T>::operator << (_val); return *this; }
    basic_stringstream<T>& operator<<   (std::ostream& (*_val)(std::ostream&))  { std::basic_stringstream<T>::operator << (_val); return *this; }
    basic_stringstream<T>& operator<<   (std::ios& (*_val)(std::ios&))          { std::basic_stringstream<T>::operator << (_val); return *this; }
    basic_stringstream<T>& operator<<   (std::ios_base& (*_val)(std::ios_base&)){ std::basic_stringstream<T>::operator << (_val); return *this; }
    basic_stringstream<T>& operator<<   (const T* _val)                         { return static_cast<basic_stringstream<T>&>(std::operator << (*this,_val)); }
    basic_stringstream<T>& operator<<   (const std::basic_string<T>& _val)      { return static_cast<basic_stringstream<T>&>(std::operator << (*this,_val.c_str())); }
};

typedef basic_stringstream<char>        stringstream;
typedef basic_stringstream<wchar_t>     wstringstream;
}

Damit können Sie Dinge wie schreiben

std::string myString( NsStringBuilder::stringstream() << "my data " << 42 )

sogar im Konstruktor.

Ich muss gestehen, dass ich die Leistung nicht gemessen habe, da ich sie noch nicht in einer Umgebung verwendet habe, in der der Stringaufbau noch stark genutzt wird, aber ich gehe davon aus, dass sie nicht viel schlimmer sein wird als std :: stringstream, da alles erledigt ist über Referenzen (außer der Konvertierung in einen String, aber das ist auch eine Kopieroperation in std :: stringstream)

user2328447
quelle
Das ist ordentlich. Ich verstehe nicht, warum ich mich nicht std::stringstreamso verhalte.
Einpoklum
1

Der Seilcontainer kann sich lohnen, wenn eine Zeichenfolge in die zufällige Stelle der Zielzeichenfolge oder für lange Zeichenfolgen eingefügt / gelöscht werden muss. Hier ist ein Beispiel aus der Implementierung von SGI:

crope r(1000000, 'x');          // crope is rope<char>. wrope is rope<wchar_t>
                                // Builds a rope containing a million 'x's.
                                // Takes much less than a MB, since the
                                // different pieces are shared.
crope r2 = r + "abc" + r;       // concatenation; takes on the order of 100s
                                // of machine instructions; fast
crope r3 = r2.substr(1000000, 3);       // yields "abc"; fast.
crope r4 = r2.substr(1000000, 1000000); // also fast.
reverse(r2.mutable_begin(), r2.mutable_end());
                                // correct, but slow; may take a
                                // minute or more.
Igor
quelle
0

Ich wollte aus folgenden Gründen etwas Neues hinzufügen:

Bei einem ersten Versuch konnte ich nicht schlagen

std::ostringstream 's operator<<

Effizienz, aber mit mehr Versuchen konnte ich einen StringBuilder erstellen, der in einigen Fällen schneller ist.

Jedes Mal, wenn ich eine Zeichenfolge anhänge, speichere ich irgendwo einen Verweis darauf und erhöhe den Zähler der Gesamtgröße.

Die wirkliche Art, wie ich es endlich implementiert habe (Horror!), Ist die Verwendung eines undurchsichtigen Puffers (std :: vector <char>):

  • 1-Byte-Header (2 Bits, um festzustellen, ob folgende Daten vorliegen: Verschobene Zeichenfolge, Zeichenfolge oder Byte [])
  • 6 Bits, um die Länge des Bytes anzuzeigen []

für Byte []

  • Ich speichere direkt Bytes von kurzen Zeichenfolgen (für sequentiellen Speicherzugriff)

für verschobene Zeichenfolgen (Zeichenfolgen mit angehängt std::move)

  • Der Zeiger auf ein std::stringObjekt (wir haben Eigentum)
  • Setzen Sie ein Flag in der Klasse, wenn dort nicht verwendete reservierte Bytes vorhanden sind

für Saiten

  • Der Zeiger auf ein std::stringObjekt (kein Besitz)

Es gibt auch eine kleine Optimierung: Wenn die zuletzt eingefügte Zeichenfolge verschoben wurde, sucht sie nach frei reservierten, aber nicht verwendeten Bytes und speichert dort weitere Bytes, anstatt den undurchsichtigen Puffer zu verwenden (um Speicherplatz zu sparen, wird sie tatsächlich etwas langsamer , hängt vielleicht auch von der CPU ab, und es kommt sowieso selten vor, dass Zeichenfolgen mit zusätzlichem reserviertem Speicherplatz angezeigt werden.)

Dies war schließlich etwas schneller als std::ostringstream, hat aber einige Nachteile:

  • Ich habe Char-Typen mit fester Länge angenommen (also 1,2 oder 4 Bytes, nicht gut für UTF8). Ich sage nicht, dass es für UTF8 nicht funktioniert. Ich habe es nur nicht auf Faulheit überprüft.
  • Ich habe schlechte Codierungspraktiken angewendet (undurchsichtiger Puffer, leicht zu machen, nicht portierbar, ich glaube, meiner ist übrigens portabel)
  • Fehlt alle Funktionen von ostringstream
  • Wenn eine Zeichenfolge, auf die verwiesen wird, vor dem Zusammenführen aller Zeichenfolgen gelöscht wird: undefiniertes Verhalten.

Fazit? verwenden std::ostringstream

Es behebt bereits den größten Engpass, während es sich nicht lohnt, mit der Minenimplementierung einige Prozentpunkte Geschwindigkeit zu erreichen.

Kaffeeentwickler
quelle