Odpowiednik C ++ StringBuffer / StringBuilder?

Czy istnieje klasa C ++ Standard Template Library, która zapewnia wydajne funkcje konkatenacji ciągów, podobny do C # 's StringBuilder lub Java StringBuffer ?

UWAGA, na tę odpowiedź ostatnio zwrócono uwagę. Nie zalecam tego jako rozwiązania (jest to rozwiązanie, które widziałem w przeszłości, przed STL). Jest to ciekawe podejście i powinien być stosowany wyłącznie przez std::stringlub std::stringstreamjeśli po profilowania kodu można odkryć to sprawia poprawę.

I normalnie używać albo std::stringalbo std::stringstream. Nigdy nie miałem z tym żadnych problemów. Zazwyczaj najpierw rezerwuję trochę miejsca, jeśli z góry znam przybliżony rozmiar struny.

W odległej przeszłości widziałem innych ludzi tworzących własny zoptymalizowany konstruktor strun.

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

Wykorzystuje dwa łańcuchy, jeden dla większości łańcucha, a drugi jako obszar rysowania do łączenia krótkich łańcuchów. Optymalizuje dołączanie przez grupowanie krótkich operacji dołączania w jednym małym ciągu, a następnie dołączanie go do łańcucha głównego, zmniejszając w ten sposób liczbę wymaganych przesunięć w łańcuchu głównym, gdy staje się on większy.

Nie wymagałem tej sztuczki z std::stringlub std::stringstream. Myślę, że był używany z zewnętrzną biblioteką ciągów przed std :: string, to było tak dawno temu. Jeśli zastosujesz strategię taką jak ten profil, najpierw zastosuj aplikację.

Sposobem C ++ byłoby użycie std :: stringstream lub po prostu zwykłego łączenia ciągów. Ciągi w języku C ++ są zmienne, więc względy wydajności dotyczące konkatenacji są mniej ważne.

jeśli chodzi o formatowanie, możesz wykonać to samo formatowanie w strumieniu, ale w inny sposób, podobny docout . lub możesz użyć silnie typowanego funktora, który to ujmuje i dostarcza String.Format podobny do interfejsu, np. boost :: format

Ta std::string.appendfunkcja nie jest dobrą opcją, ponieważ nie akceptuje wielu form danych. Bardziej użyteczną alternatywą jest użycie std::stringstream; tak:

#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();

std::string jest odpowiednikiem C ++: można go modyfikować.

Możesz użyć .append () do prostego łączenia łańcuchów.

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

Myślę, że możesz nawet zrobić:

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

Jeśli chodzi o operacje formatowania C # StringBuilder, uważam snprintf(lub sprintfjeśli chcesz zaryzykować zapisanie błędnego kodu ;-)) w tablicy znaków i przekonwertować z powrotem na ciąg znaków, jest jedyną opcją.

Ponieważ std::stringw C ++ można modyfikować, możesz tego użyć. Ma funkcję += operatori append.

Jeśli chcesz dołączyć dane liczbowe, skorzystaj z std::to_stringfunkcji.

Jeśli chcesz jeszcze większej elastyczności w postaci możliwości szeregowania dowolnego obiektu na łańcuch, skorzystaj z std::stringstreamklasy. Musisz jednak wdrożyć własne funkcje operatora przesyłania strumieniowego, aby działało ono z własnymi klasami niestandardowymi.

std :: string's + = nie działa z const char * (czymś takim jak „string to add” wydaje się być), więc zdecydowanie użycie stringstream jest najbliższe wymaganiom - wystarczy użyć << zamiast +

Wygodny konstruktor napisów dla c ++

Jak wiele osób odpowiedziało wcześniej, std :: stringstream jest metodą z wyboru. Działa dobrze i ma wiele opcji konwersji i formatowania. IMO ma jednak jedną niedogodną wadę: nie można jej używać jako jednej linijki ani jako wyrażenia. Zawsze musisz napisać:

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

co jest dość denerwujące, szczególnie gdy chcesz zainicjować ciągi znaków w konstruktorze.

Powodem jest to, że a) std :: stringstream nie ma operatora konwersji na std :: string oraz b) operator << () łańcucha string nie zwraca referencji stringstream, ale referencję std :: ostream - które nie mogą być dalej obliczane jako strumień ciągów.

Rozwiązaniem jest zastąpienie std :: stringstream i lepsze dopasowanie operatorów:

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

Dzięki temu możesz pisać takie rzeczy

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

nawet w konstruktorze.

Muszę wyznać, że nie zmierzyłem wydajności, ponieważ nie korzystałem z niej w środowisku, które często korzysta z budowania ciągów, ale zakładam, że nie będzie to znacznie gorsze niż std :: stringstream, ponieważ wszystko jest zrobione poprzez referencje (oprócz konwersji na ciąg, ale to także operacja kopiowania w std :: stringstream)

Rope pojemnik może być wart, jeśli trzeba wstawić / Usuń ciąg na losowym miejscu docelowym lub na ciąg długich sekwencji Char. Oto przykład z implementacji 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.

Chciałem dodać coś nowego z następujących powodów:

Za pierwszym razem nie udało mi się pokonać

std::ostringstream „s operator<<

wydajność, ale przy większej liczbie prób udało mi się stworzyć StringBuilder, który w niektórych przypadkach jest szybszy.

Za każdym razem, gdy dołączam ciąg, po prostu przechowuję gdzieś odniesienie i zwiększam licznik całkowitego rozmiaru.

Prawdziwym sposobem, w jaki w końcu go zaimplementowałem (Horror!) Jest użycie nieprzezroczystego bufora (std :: vector <char>):

• 1 bajt nagłówka (2 bity, aby stwierdzić, czy następujące dane to: przeniesiony ciąg, ciąg lub bajt [])
• 6 bitów do podania długości bajtu []

dla bajtu []

• Przechowuję bezpośrednio bajty krótkich ciągów (dla sekwencyjnego dostępu do pamięci)

dla przeniesionych ciągów (ciągi dołączone z std::move)

• Wskaźnik do std::stringobiektu (mamy własność)
• ustaw flagę w klasie, jeśli są tam nieużywane zarezerwowane bajty

na struny

• Wskaźnik do std::stringobiektu (bez prawa własności)

Jest jeszcze jedna drobna optymalizacja, jeśli ostatni wstawiony ciąg został przeniesiony, sprawdza wolne zarezerwowane, ale nieużywane bajty i zapisuje tam kolejne bajty zamiast używać nieprzezroczystego bufora (ma to na celu zaoszczędzenie pamięci, w rzeczywistości powoduje to, że jest nieco wolniejsza , może zależy również od procesora, a mimo to rzadko widuje się ciągi znaków z dodatkową zarezerwowaną przestrzenią)

To było w końcu nieco szybsze niż, std::ostringstreamale ma kilka wad:

• Przyjąłem stałe typy znaków (więc 1,2 lub 4 bajty, co nie jest dobre dla UTF8), nie mówię, że nie będzie działać dla UTF8, po prostu nie sprawdziłem lenistwa.
• Użyłem złej praktyki kodowania (nieprzezroczysty bufor, łatwy do uczynienia go nieprzenośnym, moim zdaniem mój jest przenośny)
• Brakuje wszystkich funkcji ostringstream
• Jeśli jakiś połączony ciąg zostanie usunięty przed połączeniem wszystkich ciągów: zachowanie niezdefiniowane.

wniosek? posługiwać się std::ostringstream

Naprawiono już największe wąskie gardło, a zdobywanie kilku procent punktów w szybszym tempie dzięki wdrożeniu kopalni nie jest warte wad.