Double Ended Vector

[Nexus]

Hallo,

Ist ein dynamisches Array, das auf beiden Seiten einen Puffer mit rohem Speicher hat und somit beidseitig Lösch-/Einfügeoperationen in konstanter Zeit erlaubt, wirklich eine so seltene Datenstruktur oder hab ich da was übersehen?

Im Gegensatz zu einer Double Ended Queue ( std::deque ) wäre der Speicherbereich trotzdem an einem Stück, was die Vorteile eines dynamischen Arrays ( std::vector ) beibehalten würde. Ausserdem hätte man mit relativ wenig Overhead (einer "linksseitigen Kapazität") die Möglichkeit, auch am Containeranfang effizient zu operieren. Gleichzeitig wären die Operationen zwischen Anfang und Mitte nicht mehr dramatischer als diejenigen zwischen Mitte und Ende - beim normalen Vector nimmt der Kopieraufwand ja linear mit der Distanz zum Ende zu. Hier wäre es dann die kleinere der beiden Distanzen zum Anfang/Ende.

Was denkt ihr darüber? Wird sowas nie benötigt, nimmt man für solche Fälle die eher teure std::deque ?

[volkard]

Nexus schrieb:

Ist ein dynamisches Array, das auf beiden Seiten einen Puffer mit rohem Speicher hat und somit beidseitig Lösch-/Einfügeoperationen in konstanter Zeit erlaubt, wirklich eine so seltene Datenstruktur oder hab ich da was übersehen?

ja.
ich hab 1999 mal so ein double ended array gebraucht, um netzwerkpakete zusammenzubasteln, ohne dauernd zu kopieren, denn der envelope der tieferen schicht steckt ja mal vorne, mal vorn&hinten.
hab sowas aber seitdem nicht mehr gebraucht und auch beo keinem anderen gesehen.

Im Gegensatz zu einer Double Ended Queue ( std::deque ) wäre der Speicherbereich trotzdem an einem Stück, was die Vorteile eines dynamischen Arrays ( std::vector ) beibehalten würde.

der vorteil scheint selten genug gebraucht zu werden.

Was denkt ihr darüber? Wird sowas nie benötigt, nimmt man für solche Fälle die eher teure std::deque ?

naja, so teuer ist die auch wieder nicht. zumal sie keine wachstumsschmerzen hat wie der vector.

ein double ended vector braucht eine sinnvolle abschätzung, wieviel speicher am anfang auf vorrat genommen wird. davor scheut man sich. man will ja nicht innen 100k nutzdaten, dahinter 100k leer und davor 100k leer. bei meinen netzwerkpaketen konnte ich sinnvolle annahmen machen.

[Nexus]

volkard schrieb:

ich hab 1999 mal so ein double ended array gebraucht, [...] hab sowas aber seitdem nicht mehr gebraucht und auch beo keinem anderen gesehen.

Hmm... Dann sind Double Ended Vectors in unserem Jahrtausend wohl nicht mehr zeitgemäss.
Ich habe eben selber auch noch nie sowas Ähnliches gesehen. Ich hab mir nur überlegt, dass es vielleicht einige nützliche Anwendungsfälle geben könnte, aber scheinbar nicht allzu viele.

volkard schrieb:

der vorteil scheint selten genug gebraucht zu werden.

Stimmt. Die lineare Anordnung selber wird am ehesten im Zusammenhang mit C-Interfaces zu Arrays benötigt. Allerdings wäre der Random Access möglicherweise leicht schneller.

volkard schrieb:

naja, so teuer ist die auch wieder nicht. zumal sie keine wachstumsschmerzen hat wie der vector.

Gut, das ist der Vorteil. Ich hatte jetzt nur an die zusätzliche Indirektion und den Zeiger-Overhead gedacht, aber meistens sollten die verkraftbar sein...

volkard schrieb:

ein double ended vector braucht eine sinnvolle abschätzung, wieviel speicher am anfang auf vorrat genommen wird. davor scheut man sich. man will ja nicht innen 100k nutzdaten, dahinter 100k leer und davor 100k leer. bei meinen netzwerkpaketen konnte ich sinnvolle annahmen machen.

Da hast du Recht, das scheint mir ein sehr wichtiger Punkt zu sein. std::vector ist teilweise schon nicht ganz ideal, da er in gewissen Implementierungen bis zu doppelt so viel Platz belegt wie er nutzt. Meist kann man den verlorenen Speicher für bessere Performance in Kauf nehmen. Aber grundsätzlich muss man sich schon etwas ausdenken, damit auch kleine Container nicht allzu viel Platz verschwenden. Vielleicht in beide Richtungen 1.5 Mal vorallokieren oder so. Eventuell auch dem User die Möglichkeit geben, darauf Einfluss zu haben...

Nun ja, ich werde sowas vorerst wohl nicht benötigen. Sollte der Zeitpunkt kommen, kann ich mir dann immer noch was basteln, das dürfte nicht allzu schwer sein. Vielen Dank für die Hinweise.

[volkard]

Nexus schrieb:

Gut, das ist der Vorteil. Ich hatte jetzt nur an die zusätzliche Indirektion und den Zeiger-Overhead gedacht, aber meistens sollten die verkraftbar sein...

die queue<T> darf gerne redundante zusatzzeiger haben, und ein pushback ist dann

if(writePos==endOfAllocatedMemoryOfLastPage)
  tuwasTollesMachen()
new(writePos)T(t);
++writePos;

zum vergleich der vector:

if(writePos==endOfAllocatedMemory)
  tuwasTollesMachen()
new(writePos)T(t);
++writePos;

wäre manchmal fein, wenn sowas in der doku stehen würde.

will damit sagen, daß die queue schon verflixt schnell sein kann.
mir schwant sogar, daß beim umstieg auf ranges das durchiterieren so schnell wie beim vector ist. (ausgenommen prefetch-zaubereien des prozessors und kleinigkeiten wie 25 verwaltungstakte pro 8k durchlaufene daten.)

[Nexus]

volkard schrieb:

will damit sagen, daß die queue schon verflixt schnell sein kann.

Das glaube ich gerne, gerade bei Operationen in der Mitte oder gegen den Anfang ist eine std::deque meist schneller. Wie gesagt wäre auch der Overhead dafür vertretbar.

Naja, im Moment betrifft mich die Thematik nicht besonders. Falls ich mal so einen Container brauche, schreibe ich mir den und untersuche wenn möglich ein wenig dessen Laufzeitverhalten... Aber vorerst ist das unnötig.