Vektorelemente als Pointer...

Athar

also std::vector<Element*>

Wenn schon, dann ptr_vector<Element>. Ansonsten siehe oben, womit aber Punkt 2 wegfällt.

Blue-Tiger

kruemelkacker hat ja schon alles gesagt (und wie gesagt, ptr_vector<foo> ist die bessere Wahl fuer vector<foo*>).

Du musst nur noch entscheiden was fuer dich guenstiger ist.

* Wenns nicht performancekritisch ist, nimm vector<> und gut ist
* Wenn du oft einfuegst (und nicht nur z. B. hautsaechlich 1x am Anfang) so dass das umkopieren ein problem wird, nimm ptr_vector<>

Osbios

Wenn du große Elemente benutzt, kann es sehr viel länger dauern Operationen wie push_back (wenn er keine Reserven mehr hat und ein realloc ausführen muss, was offt alles kopiert), swap und besonders insert und erase auszuführen.
Dann würden sich Pointer anbieten, da sie auf den meisten Systemen nur 4 oder 8 Byte verbrauchen.

Bei Zugriffen auf die Elemente musst du dann jedoch immer über die Pointer gehen, was etwas langsamer ist.

Viele kleine Elemente -> keine pointer benutzen
Wenige aber große Elemente -> pointer benutzen

Aber wie krümelkacker auch durchsickern lässt, lohnt der extraaufwand meist nicht. Also Pointer nur benutzen wenn es um Performanceverbesserungen geht.

Osbios

Wenn ich das nach kurzem googeln richtig sehe ist ptr_vector nicht in der std enthalten sondern seperat z.B. über boost zu benutzen?

Eisflamme

Ja, die ptr_*-Klassen sind boost.

Und "Nachteil" an vector<T> ist ja auch einfach, dass T copyable sein muss, andernfalls müssen wir also zwangsläufig ptr_vector oder vector<T*> benutzen.

antialias

Bei vector auch immer schaun obs wirklich unbedingt ein vector sein muss oder obs nicht auch eine list (oder ähnliches) tut. Das erspart dann einige der Performanceprobleme die vector beim einfügen von neuen Objekten hat (zu Lasten einer schlechteren Zugriffszeit auf Element n des containers)..siehe Punkt 4 auf krümelkackers Liste.

Wenns also nur ums durchiterieren geht und um insert/remove von Elementen (was bei 500 Elementen wahrscheinlich ist), dann nimm was anderes als vector.

Osbios

Denn größten Nutzen von Vector sehe ich darin, dass die Daten immer wie ein array angeordnet sind und man diese daher direkt mit Funktionen benutzen kann die arrays erwarten.

Athar

Fragt sich dann nur, warum du Funktionen hast, die Arrays erwarten und keinen Vektor bzw. ein einfaches Iteratorpaar.

Nexus

antialias schrieb:

Wenns also nur ums durchiterieren geht und um insert/remove von Elementen (was bei 500 Elementen wahrscheinlich ist), dann nimm was anderes als vector.

Nein, kehre nicht zu schnell von std::vector ab. Dieser bleibt nämlich für die meisten Fälle der am besten geeignete Container. Ohne Beachtung der Reihenfolge kann er auch in O(1) löschen und einfügen. Wenn die Grössenordnung der Elemente zuvor bekannt ist, kann man mit reserve() nachhelfen.

std::list hat einige Nachteile (eine Auswahl der von mir aus gesehen wichtigen Punkte):

Overhead einer dynamischen Allokation und Deallokation pro Element statt pro Container. Das benötigt zusätzliche Zeit und Speicher.
Schlechte Cache-Lokalität, was sich beim Durchiterieren negativ auswirken kann.
Kein Random-Access, folglich auch keine darauf basierenden Algorithmen

Hingegen schneidet std::list vor allem in folgenden Punkten besser ab als std::vector :

Einfügungen und Löschungen dauern immer gleich lang, zudem kann mit O(1) die Reihenfolge behalten werden
Sämtliche Iteratoren, Referenzen und Zeiger auf Elemente bleiben gültig, solange das Element existiert

Osbios

Athar schrieb:

Fragt sich dann nur, warum du Funktionen hast, die Arrays erwarten und keinen Vektor bzw. ein einfaches Iteratorpaar.

Man muss das ja nicht mit eigenen Funktionen so handhaben, aber z.B. ältere Bibliotheken die keine Vector benutzen oder noch garnicht kannten, können damit gefüttert werden.