C++ Container - Welche Datenstruktur wofür (Vertiefung)

[Tockra]

Hallo Leute,

ich versuche mir gerade mit hilfe eines Buches C++ anzueignen. Da ich aus der Java Ecke komme und recht viel mit Informatik zu tun habe, sind die Datenstrukturen der Container mir nicht gerade Fremd. Allerdings erschließen sich einige Dinge für mich noch nicht so richtig.

Ich weiß, dass es folgende Container gibt:
vector, deque, map, stack, list, set, array, queue , ...

Folgende wurden in dem Buch das ich gelesen habe etwas angeschnitten:
array, vector, list, deque, map.


Leider wurde der Anwendungsbereich und die Implementierung der Container gar nicht wirklich angesprochen. Ja gut ich würde mal Map und Set aus dieser Aussage raus nehmen, da da ja klar ist, was die machen sollen und mir persönlich die Implementierung nicht so wichtig ist, wobei es da ja auch verschiedene Varianten gibt (Stichwort Hash, ...).

Ich würde gerne verstehen, was ein deque sein soll (wurde nur verwendet in meinem Buch, aber nicht erläutert) und wo ich eine Liste benutze und wo einen vector.

Soviel hab ich verstanden: (Vector)
Ein vector ist ein Array, dass eine unbeschränkte größe hat. Mit [x] kann ich auf die reservierten/belegten Indizis zugreifen und mit push_back am Ende neue Element außerhalb des reservierten Bereichs anhängen bzw. mit reserve den Platz vergrößern.


Was mich an dieser Datenstruktur interessiert, wäre zu wissen wie das umgesetzt ist, dass ich alle Elemente dieses Containers hintereinander im Heap finde.
Außerdem interessiert mich, ob beim benutzen von insert der reservierte Bereich vergrößert (muss ja eigentlich).
Ist das das Äquivalent zu einer Arraylist in Java? (Liste mit konstanter Zugriffszeit)


Desweiteren würde mich interessieren wie list implementiert ist ? Ist das das LinkedList Äquivalent und wie teuer ist dort das Einfügen/Löschen/Zugreifen!?


Außerdem interessiert mich wozu der Stack denn nötig ist. Wozu er genutzt wird ist klar, aber ich kann doch einfach einen Vector nehmen, mit der Memberfunktion end() den Iterator vom letzten Element holen und so die Funktion top() ersetzen und push_end() wäre dann das Äquivalent zu push .
Wieso sollte man soetwas nicht einfach machen?



Ich hoffe ich habe euch jetzt nicht mit diesen Fragen erschlagen, aber die Dinger hängen so stark zusammen, dass ich mich gar nicht traue danach zu suchen, da ich da eh nichts finde (schon teilweise probiert).

Gruß
T

 

[VikingGe]

Ich kann zwar die meisten deiner Fragen nicht beantworten, weil ich normalerweise einen riesigen Bogen um die Standardbibliothek mache, aber generell kann man bei solchen Sachen gut hier nachschauen.

Da sieht man dann auch, dass std::stack nur ein spezielles Interface für andere Container ist - wo man unter anderem eben auch einen std::vector angeben könnte. Dann passiert praktisch genau das, was du beschreibst (standardmäßig wird aber wohl std::deque benutzt).

 

[Tockra]

weil ich normalerweise einen riesigen Bogen um die Standardbibliothek mache,

Aus einen bestimmten Grund ? Gibt es für diese Container Datentypen besser/leistungsfähigere Datenstrukturen oder wieso nutzt du die nicht?

 

[Hellsfoul]

Ich glaub, ich hab mal auf CodeProject.com mal einen Artikel darüber gelesen. Quintessenz nicht alle Standardcontainer sind langsam. Manche sind sogar richtig schnell. Ich schau mal, ob ich ihn finde.

 

[Tockra]

Also auf Wikipedia hab ich auch grad was gelesen, da wurde aber auch nicht wirklich gesagt wie die einfügezeit von vector zustande kommt und ob die genau so groß ist wie die vom array oder wie die konstante Einfügezeit von O(1) für Listen zustande kommt. Das ist ja eigentlich nicht der Fall (außer am Anfang oder am Ende).



Desweiteren würde ich gerne zu meinen Fragen oben hinzufügen, ob die Sortieralgorithmen über die Container immer "optimal" sind. Sprich der schnellste ist ja afaik Merge sort oder Quicksort (je nach Anwendungsfall).

Außerdem würde mich interessieren, ob AVL Bäume auch irgendwo in der Standartbib benutzt werden. Sind ja afaik das Non-Plus-Ultra wenn man schnell einfügen, suchen und zugreifen möchte (log n)

 

[VikingGe]

Aus einen bestimmten Grund?

Der Grund ist, dass ich einfach die Schnittstellen überhaupt nicht mag - spätestens bei Strings mit unterschiedlichen Char-Typen wird es richtig furchtbar.
Ich meine, die Klassen sind alle extrem flexibel und alles, aber die Benutzung macht keinen Spaß. Da schreibe ich den Kram lieber selbst, und ja, wenn man sich 10 Minuten lang Gedanken über das Design macht, dann kann auch das flexibel und sehr effizient sein.

oder wie die konstante Einfügezeit von O(1) für Listen zustande kommt

Die gilt natürlich nur, wenn die Position, an der eingefügt wird bekannt ist. Wie das in der STL genau geht, weiß ich nicht, aber irgendwas in Richtung Iterator wird das wohl sein.

cppreference sagt nebenbei:

Fast random access is not supported. It is usually implemented as double-linked list.

 

[antred]

Also auf Wikipedia hab ich auch grad was gelesen, da wurde aber auch nicht wirklich gesagt wie die einfügezeit von vector zustande kommt und ob die genau so groß ist wie die vom array oder wie die konstante Einfügezeit von O(1) für Listen zustande kommt. Das ist ja eigentlich nicht der Fall (außer am Anfang oder am Ende).

Na ist doch logisch. Fügst du was in einer Liste dein, müssen nur ein paar next/prev-Zeigerpaare umgehängt werden. Fügst du mitten in einem vector was ein, müssen erst mal alle Elemente, die nach dem Einfüge-Index liegen, um eine Position nach rechts geschoben werden. Da kann also viel Aufwand entstehen. Bei vector/array ist Einfügen generell nur am Ende des Containers effizient, wobei man da ja eigentlich eher vom Anfügen reden kann.

Eine deque ist eine double-ended queue. Hier ist das Einfügen an beiden Enden effizient.

Im Zweifelsfall immer erst mal zum vector, dem einfachsten Container greifen. Wenn du merkst, daß du viel in der Mitte oder vorne Einfügen kannst und per Profiler nachweisen kannst, daß das auch tatsächlich einen meßbaren Performanceverlust bringt, kannst du immer noch auf einen anderen, spezielleren Container umsteigen.

 

[wayne_757]

Der Vector wird intern als normales array abgebildet. Es wird aber mehr Speicher allokiert als benötigt.
Sobald die Reserve aufgebraucht ist wird ein neues Array angelegt und umkopiert. Deshalb ist die Performance bei großen Vectoren schlechter als bei z.B. der Deque.
std::list ist als doppelt verkette Liste implementiert.

Ergänzung (12. Februar 2015)

Der Grund ist, dass ich einfach die Schnittstellen überhaupt nicht mag - spätestens bei Strings mit unterschiedlichen Char-Typen wird es richtig furchtbar.
Ich meine, die Klassen sind alle extrem flexibel und alles, aber die Benutzung macht keinen Spaß. Da schreibe ich den Kram lieber selbst, und ja, wenn man sich 10 Minuten lang Gedanken über das Design macht, dann kann auch das flexibel und sehr effizient sein.

Ganz ehrlich? Für die händische Implementierung einer Map die Referenzgezählte Pointer beinhalted benötigst du 10 Tage inklusive 3 gravierender Bugs und grottenschlechter Performance. Gibs zu, über Segfaults ärgerst du dich am meisten

 

[Hellsfoul]

Der Vector wird intern als normales array abgebildet. Es wird aber mehr Speicher allokiert als benötigt.
Sobald die Reserve aufgebraucht ist wird ein neues Array angelegt und umkopiert.

Hier ein schöner Artikel dazu: http://www.codeproject.com/Articles/5425/An-In-Depth-Study-of-the-STL-Deque-Container

 

[Tockra]

Na ist doch logisch. Fügst du was in einer Liste dein, müssen nur ein paar next/prev-Zeigerpaare umgehängt werden.

Das ist mir wohl bekannt, allerdings gehört zum Einfügen an Index I ja nicht nur die Einfügeoperation sondern auch die Suchoperation, um den entsprechenden Knoten zu finden und bei einer doppelt verketteten Liste wird da die schlechteste Suchzeit ja O(n) sein.

 

[antred]

Das ist mir wohl bekannt, allerdings gehört zum Einfügen an Index I ja nicht nur die Einfügeoperation sondern auch die Suchoperation, um den entsprechenden Knoten zu finden und bei einer doppelt verketteten Liste wird da die schlechteste Suchzeit ja O(n) sein.

Schau dir mal die insert()-Methoden-Überladungen von std::list an. Jede einzelne von denen erwartet unter anderem einen Iterator, der auf die Einfügeposition zeigt.

 

[Miuwa]

Hi,

Eine deque ist äußerlich erstmal recht ähnlich wie ein std::vektor, der sowohl vorne als auch hinten effizient wachsen kann. Intern ist sie meines Wissens als Vektor von Pointern auf (relativ kurze) Arrays implementiert. Sie speichert ihre Elemente also nicht in einem zusammenhängenden Datenblock ab. Das hat den Vorteil, dass die einzelnen Elemente nicht umkopiert werden müssen, wenn der reservierte Bereich voll ist (es wird einfach ein neues array alloziert).

Die Einfügezeit von std::list bezieht sich nur auf das Einfügen eines Elements an einem bekannten ort (sprich wenn man bereits einen itarator darauf hat) das Suchen dieser Stelle hat natürlich erstmal O(n) Komplexität.
Beim Vektor ist es umgekehrt: Das finden der i-ten Stelle hat Komplexität O(1) während das Einfügen lineare Komplexität aufweißt.

Generell sollte man aber beachten, dass das kontinuierliche Speicherlayout von Arrays und Vektoren sehr cachefreundlich ist. In den meisten Fällen ist das wesentlich wichtiger als die asymptotische Komplexität der verschiedenen Operationen. Sofern du z.B. nicht für Google oder Facebook arbeitest würde ich grundsätzlich - wenn möglich - erstmal einen std::vektor nutzen. Egal was du machst, die Chanchen stehen gut, dass das die performanteste stl Datenstruktur für deine Anwendung ist (vielleicht abgesehen von std::unordered_map).

Ergänzung (13. Februar 2015)

Aber wie immer gilt natürllich, wenn Performance wichtig ist: MESSEN