Was passiert wenn der Vector sich vergroessert

Nexus

Wenn Zeiger, Referenzen und Iteratoren auf die einzelnen Elemente gültig bleiben müssen, nimm std::list .

Hey, list funktioniert super.

Wofuer benutzt man dann ueberhaupt Vector ?

drakon

eicon111 schrieb:

Wofuer benutzt man dann ueberhaupt Vector ?

Dort wo die konstante Zugriffszeit auf ein Element eine Rolle spielt, respektive wichtig ist. (Du must nicht die Hälfte aller Elemente passieren, wenn du das in der Mitte willst. Bei einer Liste ist das aber so).

Ok, dann ist es gerade fuer mich sehr wichtig.
Ich habe mich schon gewundert warum ich nicht auf ein Element direkt zugreifen kann sondern alles mit einem Iterator machen muss.

Dann ist das doch keine Lösung

Nexus

Beschreib doch mal alle Operationen, die du auf dem Container ausführen möchtest (z.B. Zugriff, Löschen, Einfügen, Sortieren, ...) und Bedingungen, die du stellst (z.B. Zeiger auf Elemente müssen gültig bleiben). Dann können wir dir wahrscheinlich einen Containertypen empfehlen.

Ok,

also ich brauche schnellen Zugriff auf jedes Objekt und ob ein Objekt in der Liste enthalten ist muss ich auch gelegentlich wissen.

Ad aCTa

Eventuell std::set oder std::map? Die Zugriffszeit ist relativ schnell O(log n) und dank assoziativer Container einigermaßen random access.

Nexus

eicon111 schrieb:

also ich brauche schnellen Zugriff auf jedes Objekt

Sequentieller Container wie std::vector , std::deque : O(1)
Assoziativer Container wie std::set , std::map : O(log(n))

eicon111 schrieb:

und ob ein Objekt in der Liste enthalten ist muss ich auch gelegentlich wissen.

Sequentieller (unsortierter) Container: O(n)
Assoziativer Container: O(log(n))

Da du nur gelegentlich Elemente suchst, kannst du die lineare Zeitkomplexität dafür wahrscheinlich in Kauf nehmen. Ansonsten ausprobieren und Zeit messen...

Noch zum schnellen Zugriff auf jedes Objekt: Wirklich jedes beliebige? Sprichst du einzelne über den Index an?

Ja ich spreche sie eigentlich ueber einen index an, koennte das aber auch anders machen.

Aus Java kenne ich ein HashSet was mir einen Zugriff und Suche in O(1) gewaehrleistet hat.
Sowas waere eine tolle Sache, ich hab da auch schon was gefunden komme aber nicht klar damit weil man da so viel selber einstellen muss Hashfunktion usw.

sonst hilft vllt auch ein Konstrukt wie std::vector<shared_ptr<Node> > nodes;
dann kannste auch die Nachbarknoten als Vektor von shared_ptr auf Nodes verlinken... und hast trotzdem automatisches _aufräumen_ dabei

Zieh dir mal ein halbes Jahr C++ Grundlagen rein.

Th69

Sorry, hatte nicht gesehen, daß du einen Zeiger auf einen std::vector hast - warum eigentlich?

Also so war es gemeint:

vector<Node> allNodes;
size_t current;

//Zugriff dann über:
Node& node = allNodes[current];

Bei einem Zeiger müsstest du halt noch vorher dereferenzieren:

vector<Node> *allNodes;
size_t current;

//Zugriff dann über:
Node& node = (*allNodes)[current];

Gehört aber alles zu den Grundlagen der STL-Programmierung...

tipp schrieb:

Zieh dir mal ein halbes Jahr C++ Grundlagen rein.

Ok mach ich.

i-am-tired schrieb:

sonst hilft vllt auch ein Konstrukt wie std::vector<shared_ptr<Node> > nodes;
dann kannste auch die Nachbarknoten als Vektor von shared_ptr auf Nodes verlinken... und hast trotzdem automatisches _aufräumen_ dabei

Das hoert sich interessant an, aber was sind shared_ptr ? hab ich noch nichts von gehoert.

Ich hab mich mal mit der std::hash_map auseinander gesetzt und benutze die jetzt, ist fuer meine Anwendung wohl das beste.
Danke fuer die vielen hilfreichen Antworten!

Gruesse

Th69 schrieb:

Also so war es gemeint:
vector<Node> allNodes;
size_t current;

//Zugriff dann über:
Node& node = allNodes[current];
...
Gehört aber alles zu den Grundlagen der STL-Programmierung...

Darf man mal naiv fragen, was die Referenz hier dem Zeiger voraus hat, wenn der Vektor umkopiert wird?

Th69

Es ging um die Fehlermeldung http://www.c-plusplus.net/forum/viewtopic-var-p-is-1831417.html#1831417

OK, aber was ist mit der von dir vorgeschlagenen Konstruktion?

vector<Node> allNodes;
size_t current;

//Zugriff dann über:
Node& node = allNodes[current];

Ich meine hier besonders die Referenz. Hast du dir das gut überlegt?

Th69

Ja, habe ich!

Ok, etwas länger:
Die Referenz soll ja nur beim Zugriff temporär darauf benutzt werden - nicht als Member. Es ging ja darum, warum ein "Node-Zeiger" schlecht ist und darum besser ein Index als Variable benutzt werden soll.
Und ich habe nur gezeigt, wie man dann auf ein Element des std::vector mit Hilfe der Index-Variablen zugreift...

Daher ist auch ein Iterator nicht geeignet, ein aktuelles Element zu speichern (denn auch dieser wird beim internen Vergrößern (= Umkopieren) ungültig).

So, mehr habe ich hierzu nicht zu sagen -)

Nexus

Mitleid schrieb:

Ich meine hier besonders die Referenz. Hast du dir das gut überlegt?

Die Referenz wird ja nur gefährlich, wenn man während ihrer Lebensdauer den Container verändert und sie danach noch dereferenziert. Ich deklariere teilweise auch lokale Referenzen auf Containerelemente, z.B. wenn der Index komplexer berechnet wird.