3. Baeume mit vector und das Speichern von Pfaden

Baeume mit vector und das Speichern von Pfaden

  • T

    Das koennte gehen, ich werde mal versuchen, es zu implementieren. Vielen Dank fuer den Tip!

    0
  • T

    Ich muss doch noch mal nachfragen, wie man korrekt einen vector aus Referenzen aufsetzt. Ich habe ein paar Sachen probiert, und ellenlange STL-Fehlermeldungen bekommen, weil ich versuchte, zeiger zuf referenzen oder referenzen auf referenzen zu erzeugen usw.

    std::vector<int&> refs;

    Das allein erzeugt schon Unmengen an Fehlermeldungen.
    Der zweite Versuch,

    std::vector<int> refs;
int i = 4;
int &r = i;

refs.push_back(r);

    Speichert (wie erwartet) eine Kopie von r, und nicht r selber, so dass Aenderungen an i oder r nicht in refs widergespiegelt werden.

    Koennte ich da noch einen Hinweis bekommen, bitte?

    Vielen Dank!

    0
  • K

    Referenzen können nicht in einem Vector gespeichert werden, da sie sich nicht kopieren lassen! Du musst da mit Zeigern arbeiten:
    vector<int *> Vector;

    Das funktioniert ohne Probleme!

    0
  • T

    Nein, das tut es nicht. Vielleicht illustriert folgendes Programm mein Problem ein wenig:

    #include <iostream>
#include <vector>

int main() {
    std::vector<int> vec;
    std::vector<int*> vptr;

    vec.reserve(3);

    for(int run = 0; run < 2; ++run) {
        std::cout << "Kapazitaet von vec: " << vec.capacity()
            << " Groesse: " << vec.size() << '\n';
        for(int i = 0; i < 3; ++i) {
            vec.push_back(i);
            vptr.push_back(& vec.back());
        }

        // Kontrolle:
        std::cout << "Adressenvergleich:\n";
        for (unsigned int i = 0; i < vec.size(); ++i) {
            std::cout << "vec[" << i << "]: " << &(vec[i])
                << " vptr[" << i << "]: " << vptr[i] << '\n';
        }
    }

    return 0;
}

    Ausgabe:

    Kapazitaet von vec: 3 Groesse: 0
Adressenvergleich:
vec[0]: 0x804c008 vptr[0]: 0x804c008
vec[1]: 0x804c00c vptr[1]: 0x804c00c
vec[2]: 0x804c010 vptr[2]: 0x804c010
Kapazitaet von vec: 3 Groesse: 3
Adressenvergleich:
vec[0]: 0x804c1e8 vptr[0]: 0x804c008
vec[1]: 0x804c1ec vptr[1]: 0x804c00c
vec[2]: 0x804c1f0 vptr[2]: 0x804c010
vec[3]: 0x804c1f4 vptr[3]: 0x804c1f4
vec[4]: 0x804c1f8 vptr[4]: 0x804c1f8
vec[5]: 0x804c1fc vptr[5]: 0x804c1fc

    Beim zweiten Durchlauf muss 'vec' vergroessert werden. Da er dadurch an einen nichtdefinierten, neuen Bereich im Speicher verschoben wird (damit er weiter zusammenhaengend bleiben kann), verlieren die gespeicherten Zeiger ihre Bedeutung.
    Ich muesste vor jeden 'vec.push_back' die Kapazitaet abfragen, und wenn sie die Groesse des vectors erreicht hat, vptr neu erstellen, nachdem vec reallokiert wurde.
    Das suchte ich zu vermeiden.

    0
  • C

    Das Problem kannst du mit vector'en nicht lösen - die Adresse der Elemente ändert sich, wenn der Vector mehr Speicherplatz anfordern muß.

    Als Lösung kannst du entweder verhindern, daß der Vector neuen Speicher anfordert (dazu sagst du ihm vorher per reserve(), wieviel er benötigen wird), oder einen anderen Container verwenden (wenn du nur mit push_back() Elemente einfügen willst, geht ein deque<>, ansonsten mußt du eine list<> verwenden).

    0
  • J

    Oder im vector nicht die Foos sondern Foo* speichern. Und als Pfad dann eben auch Foo* und nicht die Adressen der Foo* im vector.

    0
  • T

    CStoll schrieb:

    Das Problem kannst du mit vector'en nicht lösen - die Adresse der Elemente ändert sich, wenn der Vector mehr Speicherplatz anfordern muß.

    Das hatte ich ja auch schon erkannt und beschrieben.

    CStoll schrieb:

    Als Lösung kannst du entweder verhindern, daß der Vector neuen Speicher anfordert (dazu sagst du ihm vorher per reserve(), wieviel er benötigen wird),

    Mit reserve() kann ich nur die Mindest-Kapazitaet festlegen, nicht verhindern, dass der vector darueber hinaus waechst.

    CStoll schrieb:

    oder einen anderen Container verwenden (wenn du nur mit push_back() Elemente einfügen willst, geht ein deque<>, ansonsten mußt du eine list<> verwenden).

    deque scheint mein Problem zu loesen. Vielen Dank!

    0
  • C

    tim_g schrieb:

    CStoll schrieb:

    Als Lösung kannst du entweder verhindern, daß der Vector neuen Speicher anfordert (dazu sagst du ihm vorher per reserve(), wieviel er benötigen wird),

    Mit reserve() kann ich nur die Mindest-Kapazitaet festlegen, nicht verhindern, dass der vector darueber hinaus waechst.

    Nein, dafür mußt du selber sorgen. (Der Ansatz mit reserve() funktioniert nur, wenn du vorher die maximale Füllung deines Vector's kennst)

    CStoll schrieb:

    oder einen anderen Container verwenden (wenn du nur mit push_back() Elemente einfügen willst, geht ein deque<>, ansonsten mußt du eine list<> verwenden).

    deque scheint mein Problem zu loesen. Vielen Dank!

    Na dann ist es doch in Ordnung 😉

    (Aber Jesters Vorschlag hat auch etwas für sich, wenn du dich persönlich um die Speicherverwaltung kümmern willst)

    0
  • T

    Ueber Jesters Vorschlag habe ich auch ein wenig nachgedacht. Im Moment versuche ich es aber erst mit der deque - ist naeher an dem, was ich bisher implementiert habe und ich kann es mir besser vorstellen.

    Kann ich sicher davon ausgehen, dass die Elemente ihre Adresse waehrend der Laufzeit des Programmes / innerhalb des Scopes nicht aendern, oder koennte die Compiler-abhaengig sein?

    0
  • C

    Nach meinem Wissen ändern die vorhandenen Deque-Elemente ihre Position nur, wenn du neue Elemente dazwischenquetschst (per insert()) oder rauslöschst. Einfügen am Anfang oder Ende (push_Back(), push_front()) kann zwar auch neuen Speicher anfordern, aber die vorhandenen Elemente bleiben an ihrem Platz.

    0
Anmelden zum Antworten