std::string als dynamischer Array?

[mekakic]

Ich frage mich gerade wie gut sich eigentlich die typischen std::string Implementierungen als dynamischer Byte-Array eignen?

Dabei geht es im Prinzip um einen Speicher [etwa 8k], an den von hinten immer Daten angehängt werden und von Vorne Daten gelöscht werden. Die Daten kommen als "unsigned char *" rein und werden auch so wieder weiterversendet. Der String hat ja wohl intern seine eigene Speicherverwaltung und würde sowas auf dem Heap ablegen?

std::string bietet mir da alle Funktionen, inkl. std::string::data() und std::string::c_str(), was ich bei vector & Co. als Operation vermißt habe.

Nimmt man besser was anderes aus der STL oder spricht was gegen die Verwendung von string als Array?

[Mond]

Ich kann Dir nichts dazu sagen, ob das ganze Sinn macht und effizient ist, aber vielleicht bietet dir folgendes (http://doc.trolltech.com/latest/qbytearray.html) folgendes (http://doc.trolltech.com/latest/qstring.html) ein paar Vorteile?

[Nighthawk13]

Vorsicht falls NULL Werte im string abgespeichert werden sollen.
Ansonsten sollte es gehen, fände aber std::vector<unsigned char> stilistisch besser.

Die Speicherverwaltung von string und vector fast gleich in den meisten Implementierungen(ein grosser Buffer auf dem Heap der vergrössert wird wenn zu klein).
string hat manchmal einen kleinen internen Buffer(~16 Bytes) um kurze String zu speichern ohne den Heap zu bemühen.

[Gnafoo]

Ein vector muss im zusammenhängenden Speicher abgelegt werden.
Das heißt du kommst mit &vec[0] an einen C-String, sofern vec ein vector<char> ist und eine terminierende Null enthält.

Edit:

Strings verwenden häufig noch Reference Counting unter der Haube und der Standard erlaubt mehr Freiheiten bei der Speicherverwaltung. Ich würde einen vector nehmen, wenn keine weiteren String-Funktionen notwendig sind.

Das du vorne wieder Zeichen entfernst klingt übrigens eher nach einem Ringbuffer. Bei vector/string musst du immer alle Elemente verschieben beim Entfernen. Man könnte mit vector problemlos einen Ringbuffer implementieren, allerdings wird es dann schwieriger, einen C-String zu bekommen. Da muss man dann ggf. zwei Fragmente aus dem Puffer kopieren und verketten. Wenn die Performance unwichtig ist, lohnt sich der Aufwand vermutlich nicht.

[ShadowXX]

Wie wäre es mit einem deque anstatt einem vector...das würde auch mit dem Daten löschen vorne besser passen.

[Coda]

std::deque oder ein Ringbuffer (http://www.boost.org/doc/libs/1_45_0/libs/circular_buffer/doc/circular_buffer.html) ist wohl die bessere Lösung. Je nachdem was du wirklich tun willst.

[Brillus]

Ein vector muss im zusammenhängenden Speicher abgelegt werden.
Das heißt du kommst mit &vec[0] an einen C-String, sofern vec ein vector<char> ist und eine terminierende Null enthält.

Edit:

Strings verwenden häufig noch Reference Counting unter der Haube und der Standard erlaubt mehr Freiheiten bei der Speicherverwaltung. Ich würde einen vector nehmen, wenn keine weiteren String-Funktionen notwendig sind.

Das du vorne wieder Zeichen entfernst klingt übrigens eher nach einem Ringbuffer. Bei vector/string musst du immer alle Elemente verschieben beim Entfernen. Man könnte mit vector problemlos einen Ringbuffer implementieren, allerdings wird es dann schwieriger, einen C-String zu bekommen. Da muss man dann ggf. zwei Fragmente aus dem Puffer kopieren und verketten. Wenn die Performance unwichtig ist, lohnt sich der Aufwand vermutlich nicht.


std:vector müsste ein dynamisches array sein wenn mich jetzt nicht alles täuscht, daher eher unpassend

[Gnafoo]

Unpassend wofür? Für die Implementation eines Ringbuffers oder das Problem im allgemeinen? Rein prinzipiell macht es ja keinen wirklichen Unterschied, ob ich ein Array oder einen vector mit fester Größe verwende (der vector lässt sich ja direkt über den Konstruktor mit einer Allokation und der passenden Größe erstellen). Vector hat halt ein STL-Interface.

Der Ringbuffer ist imho auch nur dann sinnvoll, wenn der Code performancekritisch ist. Außerdem muss man dann den String aus dem Puffer kopieren um ihn weiterzugeben (C-Strings benötigen ja einen fortlaufenden Speicherbereich). Das ist dann genauso O(n), wie remove beim vector. Ob sich das lohnt hängt also davon ab, wie häufig man remove braucht und wie häufig man einen C-String extrahieren muss. Deque ist sicher eine Alternative, aber hier muss man die Daten genauso mit std::copy heraus kopieren. Vom Prinzip her ist es dasselbe wie der Ringbuffer (könnte aber auch eine verkette Liste sein, keine Ahnung, wie das üblicherweise implementiert wird).

Im Endeffekt heißt das:
vector: remove() in O(n), c_str() in O(1)
deque/rb: remove() in O(1), c_str() in O(n)

Wenn man den C-String ohnehin kopieren muss (weil man ihn z. B. länger aufheben muss oder modifizieren will), dann haben deque/rb einen leichten Vorteil. Wenn man nur send(str) damit aufruft, ist es wohl egal. Aber das ist es im Grunde genommen so oder so, wenn der Code nicht gerade performancekritisch ist und einen Hotspot darstellt. Es geht ja auch nur um 8 kb.