Welche Leistung können wir von std :: string's c_str () erwarten? Immer konstante Zeit?

13

Ich habe in letzter Zeit einige notwendige Optimierungen vorgenommen. Eine Sache, die ich getan habe, ist, einige Ostringströme zu verändern -> Sprintfs. Ich sprinte ein paar Standard-Strings zu einem Array im Stil von AC, ala

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

Es stellt sich heraus, dass die Implementierung von Microsoft std :: string :: c_str () in konstanter Zeit ausgeführt wird (es wird nur ein interner Zeiger zurückgegeben). Es scheint, dass libstdc ++ dasselbe tut . Ich verstehe, dass der Standard keine Garantie für c_str gibt, aber es ist schwer, sich eine andere Art und Weise vorzustellen, dies zu tun. Wenn sie zum Beispiel in den Speicher kopiert werden, müssen sie entweder Speicher für einen Puffer zuweisen (es bleibt dem Aufrufer überlassen, ihn zu zerstören - NICHT Teil des STL-Vertrags) ODER sie müssen in eine interne statische Datei kopieren Puffer (wahrscheinlich nicht threadsicher, und Sie haben keine Garantie für seine Lebensdauer). Es scheint also die einzig realistische Lösung zu sein, einfach einen Zeiger auf eine intern gepflegte nullterminierte Zeichenfolge zurückzugeben.

c++ performance strings Doug T.
quelle

Antworten:

9

Wenn ich mich string::c_str()recht erinnere, erlaubt der Standard so ziemlich alles zurückzugeben, was befriedigt:

  • Speicher, der groß genug für den Inhalt des Strings und den Abschluss ist NULL
  • Muss gültig sein, bis ein Nicht-Konstanten-Member des angegebenen stringObjekts aufgerufen wird

In der Praxis bedeutet dies also einen Zeiger auf den internen Speicher. da es keine Möglichkeit gibt, die Lebensdauer des zurückgegebenen Zeigers extern zu verfolgen. Ich denke, Ihre Optimierung ist sicher anzunehmen, dass dies eine (kleine) konstante Zeit ist.

In einem verwandten Hinweis, wenn die Formatierung von Zeichenfolgen die Leistung einschränkt; Mit etwas wie Boost.Phoenix kann es sein, dass Sie mehr Glück haben, wenn Sie die Bewertung aufschieben, bis sie unbedingt benötigt wird .

Boost.Format Ich glaube, die Formatierung wird intern verschoben, bis das Ergebnis erforderlich ist, und Sie können dasselbe Formatobjekt wiederholt verwenden, ohne die Formatzeichenfolge erneut zu analysieren, was für die Hochfrequenzprotokollierung einen signifikanten Unterschied darstellt.

rWert
quelle
2
Möglicherweise kann eine Implementierung einen neuen oder sekundären internen Puffer erstellen, der groß genug ist, um den Nullterminator hinzuzufügen. Auch wenn c_stres sich um eine const-Methode handelt (oder zumindest eine const-Überladung hat - ich vergesse welche), ändert dies den logischen Wert nicht und kann daher ein Grund dafür sein mutable. Es würde Zeiger von anderen Aufrufen auf unterbrechen c_str, mit der Ausnahme, dass sich solche Zeiger auf dieselbe logische Zeichenfolge beziehen müssen (es gibt also keinen neuen Grund für eine Neuzuweisung - es muss bereits ein Nullterminator vorhanden sein), oder es muss bereits ein Aufruf an einen Nicht-Benutzer stattgefunden haben -const Methode dazwischen.
Steve314
Wenn dies wirklich gültig ist, können c_strAnrufe O (n) Zeit für die Neuzuweisung und das Kopieren sein. Es ist aber auch möglich, dass der Standard zusätzliche Regeln enthält, von denen ich nicht weiß, dass sie dies verhindern würden. Der Grund , warum ich es vorschlagen - Anrufe c_strsind nicht wirklich gemeint AFAIK üblich sein, so ist es nicht wichtig , in Betracht gezogen werden kann sie schnell , um sicherzustellen , - dass zusätzliche Byte Speicherplatz für einen normalerweise unnötigen Nullabschluss bei der Vermeidung von stringFällen , die nie Gebrauch c_strkann Vorrang haben.
Steve314
Boost.FormatIntern durchläuft Streams, die intern einen sprintfziemlich hohen Overhead verursachen. Die Dokumentation sagt, es ist ungefähr 8-mal langsamer als normal sprintf. Wenn Sie Leistung und Typensicherheit wünschen, versuchen Sie es Boost.Spirit.Karma.
Jan Hudec
Boost.Spirit.KarmaDies ist ein guter Tipp für die Leistung, aber beachten Sie, dass es eine völlig andere Methodik gibt, die es schwierig machen kann, vorhandenen printfStyle-Code (und Codierer) anzupassen . Ich habe mich weitgehend daran gehalten, Boost.Formatweil unser I / O asynchron ist. Aber ein großer Faktor ist, dass ich meine Kollegen davon überzeugen kann, es konsequent zu verwenden (erlaubt immer noch jeden Typ mit einer ostream<<Überlastung - was die .c_str()Debatte angenehm umgeht ). Die Karma-Leistungszahlen .
rWert 13.12.11
23

Im c ++ 11-Standard (ich lese die Version N 3290) wird in Kapitel 21.4.7.1 die Methode c_str () beschrieben:

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

Rückgabe: Ein Zeiger p mit dem Operator p + i == & für jedes i in [0, size ()].
Komplexität: konstante Zeit.
Erforderlich: Das Programm darf keine der im Zeichenfeld gespeicherten Werte ändern.

Also ja: Die konstante zeitliche Komplexität wird durch den Standard garantiert.

Ich habe gerade den c ++ 03-Standard überprüft, und er hat weder solche Anforderungen noch zeigt er die Komplexität.

BЈовић
quelle
8

Theoretisch erfordert C ++ 03 dies nicht, und daher kann der String ein Array von Zeichen sein, bei dem das Vorhandensein des Nullterminators nur zum Zeitpunkt des Aufrufs von c_str () hinzugefügt wird. Dies kann eine Neuzuweisung erforderlich machen (verstößt nicht gegen die Konstanz, wenn der interne private Zeiger als deklariert ist mutable).

C ++ 11 ist strenger: Es erfordert Zeitaufwand, sodass keine Verlagerung durchgeführt werden kann und das Array immer breit genug sein muss, um die Null am Ende zu speichern. c_str () selbst kann immer noch " ptr[size()]='\0'" sicherstellen, dass die Null wirklich vorhanden ist. Dies verletzt nicht die Konstanz des Arrays, da der Bereich [0..size())nicht geändert wird.

Emilio Garavaglia
quelle