vector verketten
-
wenn ich
#include <slist>schreibe, bekomm ich aber einen Fehler, da er die Datei nicht kennt... Naja, ich bleib sowieso beim vector...
das mit dem reserve hab ich jetzt gemacht, scheint auch ein wenig zu helfen...
Vielen Dank erstmal für die Antworten
-
@FireFlow: kann es denn sein, dass ne Liste etwas langsamer als ein vector ist?? Im Prinzip könnte ich ja auch ne Liste nehmen, da ich ja nicht auf spezielle Elemente per Index zugreifen muss, aber irgendwie war mein Programm immer ein ganzes Stück langsamer, wenn ich list benutzt habe
-
Was machst du denn sonst so mit dem Ding?
Der Vektor ist eigentlich immer schneller, es sei denn, er muss neuen Speicher alloziieren (was du ja mit reserve machst).
-
eigentlich häng ich immer nur was an der vector dran und er wird ziemlich oft durchlaufen, um zu gucken, ob sich ein bestimmtes Element in der Liste befindet.
Deshalb hab ich ja auch überlegt, mir selber schnell ne verkette Liste zu programmieren, da sie ja nicht wirklich viele Funktionen braucht...
-
Vielleicht ein bisschen genauer? Es gibt noch einige Container mehr in der STL ;), da ist bestimmt ein passender dabei. Ich glaube nicht, dass es Sinn macht, selber eine Liste zu bauen (die mögliche Performance rechtfertigt die zusätzliche Arbeit nicht). Und wie gesagt, vector ist (wenn du seine Endgröße weißt) deutlich schneller als alles andere.
-
Autor unbekannt, ich finds aber ganz praktisch: http://quicix.de/A5.img Sry für den Referrer check...
An welchen Stellen genau ist der Code denn langsam?
Gruß
-
ich denke vector ist schon richtig, wahrscheinlich muss ich mir nur noch ein bischen Gedanken über die Speicherverwaltung machen.
In den Vektoren sind eigentlich nur Zeiger gespeichert. Ich hab einen Baum, in dem jeder Knoten beliebig viele Kinder haben kann, deshalb der Vektor...
Für die Knoten selber muss ich aber trotzdem immer einzeln Speicher anfordern. Ich hab mir jetzt überlegt, hier auch ziemlich viele Objekte auf einmal zu erstellen und dann bei Bedarf einfach nen Zeiger auf noch "freie" Objekte zu übergeben. Das müsste doch auch einen Geschwindigkeitsvorteil bringen, oder??
-
@FireFlow: Bisher hab ich immer gedacht, dass das Durchsuchen der Listen soviel Zeit beansprucht, vielleicht ist es aber auch das Reservieren von Speicher...
-
Also wenn ich das richtig verstehe, werden in deinem vector die Zeiger auf Unterknoten gespeichert. Wenn dem so ist, solltest du auf jeden Fall ptr_vector verwenden, sonst geht das mit den Pointern irgendwann schief. Dann könntest du noch soetwas wie den SmallObjectAllocator aus der Loki lib bauen oder verwenden.
Möglicherweise ist es auch sinnvoll, ein ptr_set statt eines vectors zu benutzen, da du ja sicherlich durch diesen Baum durchgehst und dann ist ein sortierter Container angebrachter (du sagtest ja, dass Indexzugriff unwichtig ist).
-
Erstmal vielen Dank für die Hilfe.
Ich hab vorhin mal versucht, so eine kleine "Speicherverwaltung" zu bauen:
In der Funktion, die neue Knoten erstellt, hab ich ein statisches Array und einen Zähler erstellt. Dann hab ich immer noch freie Adressen aus dem Array an die neuen Zeiger übergeben. Allerdings wurde das Programm dann immer mit der Fehlermeldung "_CrtIsValidHeapPointer(pUserData)" abgebrochen.
Wie ich inzwischen rausgefunden hab, ist das Problem wohl das Freigeben vom Speicher...Ich werd mir mal diesen SmallObjectAllocator angucken, der scheint ja genau das zu regeln