Jakiej wydajności możemy się spodziewać po c_str () std :: string? Zawsze stały czas?

13

Ostatnio przeprowadzałem kilka potrzebnych optymalizacji. Jedną rzeczą, którą robiłem, jest zmiana niektórych ostringstreams -> sprintfs. Sprint do zestawu std :: strings do tablicy w stylu ac, ala

char foo[500];
sprintf(foo, "%s+%s", str1.c_str(), str2.c_str());

Okazuje się, że implementacja std :: string :: c_str () Microsoftu działa w stałym czasie (zwraca tylko wewnętrzny wskaźnik). Wygląda na to, że libstdc ++ robi to samo . Zdaję sobie sprawę, że std nie daje żadnych gwarancji dla c_str, ale trudno wyobrazić sobie inny sposób na zrobienie tego. Jeśli, na przykład, skopiowali do pamięci, musieliby albo przydzielić pamięć dla bufora (pozostawienie go wywołującemu, aby go zniszczył - NIE jest to część umowy STL) LUB musieliby skopiować do wewnętrznej pamięci statycznej bufor (prawdopodobnie nie jest wątkowo bezpieczny i nie masz żadnych gwarancji na jego żywotność). Tak więc proste zwrócenie wskaźnika do wewnętrznie utrzymywanego łańcucha zakończonego zerą wydaje się być jedynym realistycznym rozwiązaniem.

c++ performance strings Doug T.
źródło

Odpowiedzi:

9

O string::c_str()ile pamiętam, standard pozwala zwrócić prawie wszystko, co spełnia:

  • Pamięć, która jest wystarczająco duża dla zawartości ciągu i zakończenia NULL
  • Musi być ważny do momentu stringwywołania elementu non-const danego obiektu

W praktyce oznacza to wskaźnik do pamięci wewnętrznej; ponieważ nie ma sposobu, aby zewnętrznie śledzić żywotność zwróconego wskaźnika. Myślę, że twoja optymalizacja jest bezpieczna, zakładając, że jest to (mały) stały czas.

Na powiązaną uwagę, jeśli formatowanie łańcucha ogranicza wydajność; może okazać się, że szczęście odracza ocenę, dopóki nie będzie absolutnie potrzebne w przypadku czegoś takiego jak Boost.Phoenix .

Boost.Format Wierzę, że odracza formatowanie wewnętrznie, dopóki wynik nie będzie wymagany, i możesz wielokrotnie używać tego samego obiektu formatu bez ponownego analizowania ciągu formatu, co moim zdaniem ma znaczący wpływ na rejestrowanie wysokich częstotliwości.

wartość r
źródło
2
Możliwe, że implementacja utworzy nowy lub wtórny bufor wewnętrzny - wystarczająco duży, aby dodać terminator zerowy. Mimo że c_strjest to metoda const (lub przynajmniej ma przeciążenie const - nie pamiętam, które), nie zmienia to logicznej wartości, więc może być tego powodem mutable. Przerwałoby to wskaźniki od innych wywołań c_str, z wyjątkiem tego, że wszelkie takie wskaźniki muszą odnosić się do tego samego ciągu logicznego (więc nie ma nowego powodu do ponownego przydzielenia - musi być już terminator zerowy), w przeciwnym razie musiało już być wywołanie innego niż -stała metoda pomiędzy.
Steve314,
Jeśli to naprawdę jest poprawne, c_strwywołaniami może być O (n) czas na realokację i kopiowanie. Ale możliwe jest również, że istnieją dodatkowe zasady w standardzie, których nie jestem świadomy, aby temu zapobiec. Powodem Proponuję go - Rozmowy na c_strnie naprawdę miało być wspólne AFAIK, więc nie mogą być uznane za ważne, aby upewnić się one szybko - unikanie że dodatkowy bajt pamięci dla normalnie niepotrzebnego zerowy terminatora w stringprzypadkach, które nigdy stosowanie c_strmoże miały pierwszeństwo.
Steve314,
Boost.Formatwewnętrznie przechodzi przez strumienie, które wewnętrznie przechodzą, co sprintfkończy się dość dużym obciążeniem. Dokumentacja mówi, że jest około 8 razy wolniejsza niż zwykła sprintf. Jeśli chcesz wydajności i bezpieczeństwa typu, spróbuj Boost.Spirit.Karma.
Jan Hudec,
Boost.Spirit.Karmajest dobrą wskazówką dotyczącą wydajności, ale należy pamiętać, że ma ona zupełnie inną metodologię, która może być trudna w dostosowywaniu istniejącego printfkodu stylu (i koderów). W dużej mierze utknąłem, Boost.Formatponieważ nasze operacje we / wy są asynchroniczne; ale dużym czynnikiem jest to, że mogę przekonać moich kolegów, aby używali go konsekwentnie (wciąż pozwala na każdy typ z ostream<<przeciążeniem - co ładnie przesuwa.c_str() debatę) Liczby wyników Karmy .
rvalue
23

W standardzie c ++ 11 (czytam wersję N 3290) rozdział 21.4.7.1 mówi o metodzie c_str ():

const charT* c_str() const noexcept; const charT* data() const noexcept;

Zwraca: Wskaźnik p taki, że p + i == i operator dla każdego i w [0, size ()].
Złożoność: stały czas.
Wymaga: Program nie może zmieniać żadnych wartości przechowywanych w tablicy znaków.

Tak więc: stała złożoność czasowa jest gwarantowana przez standard.

Właśnie sprawdziłem standard c ++ 03 i nie ma on takich wymagań, ani nie mówi o złożoności.

BЈовић
źródło
8

Teoretycznie C ++ 03 tego nie wymaga, a zatem ciąg może być tablicą char, w której obecność terminatora zerowego jest dodawana w momencie wywołania c_str (). Może to wymagać ponownego przydziału (nie narusza to ciągłości, jeśli wewnętrzny prywatny wskaźnik jest zadeklarowany jako mutable).

C ++ 11 jest bardziej rygorystyczny: wymaga kosztowności czasowej, więc nie można dokonać relokacji, a tablica musi być zawsze wystarczająco szeroka, aby przechowywać wartość null na końcu. c_str () sam w sobie może nadal robić " ptr[size()]='\0'", aby upewnić się, że null jest naprawdę obecny. Nie narusza to trwałości tablicy, ponieważ zakres [0..size())nie jest zmieniany.

Emilio Garavaglia
źródło