Korrekte Elementreferenzierung bei std::vector

Hallo!

Folgendes scheint offensichtlich nicht korrekt zu sein:

std::vector<int> testVektor;
int* elementZeiger = NULL;

testVektor.push_back(1);
elementZeiger = &testVektor.back();
testVektor.push_back(2);     // elementZeiger zeigt nicht mehr auf das erste Element (1)

Ich schätze das ist in der dynamischen Speicherverwaltung von std::vector begründet.

Wie kann man aber dann zu einzelnen Elementen sicher referenzieren?
Geht dies nur über die Zugriffsmethoden wie z.B. testVektor[i]?
Das währe recht unbequem da ja die oft ohne vector-ownership zu einzelnen Elementen referenziert werden muß.

Danke für Eure Ratschläge!

Badestrand

Zeiger zu Elementen werden in der STL mit Iteratoren gelöst, dabei gibt es zwei Arten, den const_iterator (entspricht einem const int* und den normalen iterator, entspricht int* ).
Wenn du dann einen Zeiger auf das 10. Element im vector brauchst, sähe das so aus:

std::vector<int> vec;
std::vector<int>::iterator ptr = vec.begin() + 10;

vec.begin() gibt den Zeiger/Iterator auf das erste Element zurück.

Braucht man eine Funktion, die einen Zeiger bekommen soll und ab da über den Rest drüber-iterieren soll, kann man das so lösen:

void DoSomething( vector<int>::const_iterator beg, vector<int>::const_iterator end )
{
    int some_value = 0;
    for ( ; beg!=end; beg++ )
        some_value += 10 * (*beg);
    // Mit dereferenzieren des Iterators bekommst du den Wert dahinter, bzw kannst ihn auch zuweisen.
    // Zuweisen natürlich nur bei einem vector<int>::iterator, nicht bei einem const_iterator :)
}

...

vector<int> vec;
// füllen
DoSomething( vec.begin(), vec.end() );
// oder sowas
DoSomething( vec.begin()+5, vec.end()-5 );

Jester

Das ist zwar alles richtig, aber haarscharf an der Frage vorbei: Auch die Iteratoren werden ungültig, wenn sich der vector ändert.

Badestrand

mörks

Bashar

@KreuzQuer: Du kannst entweder durch entsprechende reserve-Aufrufe verhindern, dass der Vektor neu organisiert wird und dadurch Iteratoren ungültig werden. Das funktioniert natürlich nur, wenn du die maximale Zahl einzufügender Elemente kennst. Oder du kannst dich informieren, unter welchen Bedingungen bei den verschiedenen Containern Iteratoren ungültig werden und dementsprechend einen anderen Container wählen. std::list ist in der Hinsicht z.B. ziemlich robust.

Na dann verwalte ich im Vektor lieber Zeiger auf die Elemente.

Dabei muß ich mich zwar um die Speicherfreigabe kümmern, werde aber vom default-Ctor/-Dtor Gedöhnst entlastet.

Bashar

Das löst aber dein Problem nicht.

Nun doch - ich referenziere dann halt mittels den Elementen selbst, anstatt mit einem Zeiger auf die Referenz.

Also:

std::vector<Blah*> testVektor;
Blah* elementZeiger = NULL;

testVektor.push_back(new Blah(1));
elementZeiger = testVektor.back();
testVektor.push_back(new Blah(2));     // elementZeiger zeigt weiterhin auf das erste Element Blah(1)

MFK

Dann brauchst du aber den vector nicht mehr.

Sorry, ich habe meinen Verwendungszweck nicht beschrieben.

Es soll in mehreren Bereichen, die kein ownership des Vektors haben, auf die Elemente referenziert werden.
Ich brauche daher weiterhin einen Vektor für die Zeiger, da der Speicher für die Elemente ja zentral verwaltet werden muß.

*john 0

KreuzQuer schrieb:

std::vector<Blah*> testVektor;
Blah* elementZeiger = NULL;

testVektor.push_back(new Blah(1));
elementZeiger = testVektor.back();
testVektor.push_back(new Blah(2));     // elementZeiger zeigt weiterhin auf das erste Element Blah(1)

Da bist Du aber auf den besten Weg Speicherlöcher zu produzieren. In einen Container der Standard Library legt man niemals Zeiger rein, wenn über diese Zeiger die Ownership verwaltet werden muß. Also entweder so

#include <vector>

class A {};

int main () {
  std::size_t const size = 10
  A v[size];

  std::vector<A*> vec;

  for (std::size_t i = 0; i != size; ++i) {
    vec.push_back(&v[i]);
  }
}

oder so

#include <vector>
#include <boost/shared_pointer.hpp>

class A {};

int main () {
  std::size_t const size = 10;

  std::vector<boost::shared_pointer<A> > v;

  for (std::size_t i = 0; i != size; ++i) {
    v.push_back(boost::shared_pointer<A>(new A));
  }
}

Wenn Du Objekte in den Vektor einfügst und die Kapazität reicht nicht mehr aus, dann werden alle Iteratoren/Zeiger auf Objekte ungültig. Das ist so und kann nicht geändert werden. Da hilft nur dies zu vermeiden bzw. über einen eigenen Memory Allocator die Reallozierung gänzlich zu verhindern. Wenn das alles nicht gangbar ist, solltest Du über ein anderes Design nachdenken.

~john:

In deinem Beispiel verstehe ich dann aber wirklich nicht den Sinn des Vektors.

Meine Anwendung von dem Vektor von Zeigern sieht wie folgt aus:

class Typ;
class Klasse
{
   private:
     std:vector<Typ*> typVektor;

   public:

     Klasse() {};
     Klasse() {for(int i=0; i < typVektor.size(); i++) {delete typVektor[i];}

     const Typ* PushTypElement(Typ element) {typVektor.push_back(new Typ(element)); return typVektor.back()}
};

Ich verstehe nicht was daran zu anfällig für Speicherprobleme sein soll.
Danke für die Aufklärung.

camper

Wieso wird eigentlich immer gleich zu Pointern gegriffen?
Wenn std::vector ungeeignet ist, weil er ggf. keine stabilen Referenzen liefert, dann benutz einen anderen Container. std::deque dürfte für den skizzierten Fall geeignet sein.
achja:

KreuzQuer schrieb:

Das währe recht unbequem da ja die oft ohne vector-ownership zu einzelnen Elementen referenziert werden muß.

Die erste Satzhälfte verstehe ich ja noch, den Rest nicht...

camper schrieb:

Wieso wird eigentlich immer gleich zu Pointern gegriffen?
Wenn std::vector ungeeignet ist, weil er ggf. keine stabilen Referenzen liefert, dann benutz einen anderen Container. std::deque dürfte für den skizzierten Fall geeignet sein.

Ich verstehe nicht warum std::deque dafür geeigneter sein soll.

achja:

KreuzQuer schrieb:

Das währe recht unbequem da ja die oft ohne vector-ownership zu einzelnen Elementen referenziert werden muß.

Die erste Satzhälfte verstehe ich ja noch, den Rest nicht...

Gemeint war, dass es aufwändiger ist z.B. über den Indexwert eines Elementes auf ein Element zuzugreifen (Funktionsaufruf von außerhalb notwendig), als direkt eine Referenz (im Beispiel Zeiger auf konstantes Objekt) zum Element zu besitzen.

Bashar

Du könntest auch die eigentlichen Objekte in einem Container wie list (oder deque -- deque invalidiert Iteratoren glaub ich nur beim Einfügen in der Mitte, bin aber nicht sicher) lagern, und in einem vector Pointer darauf verwalten.

*john 0

KreuzQuer schrieb:

~john:

In deinem Beispiel verstehe ich dann aber wirklich nicht den Sinn des Vektors.

Das Array dient nur dazu Elemente für den Vektor bereitzustellen, es hätte auch irgend welche anderen Objekte sein können. So ist das nur kompakter zu schreiben.

Meine Anwendung von dem Vektor von Zeigern sieht wie folgt aus:
class Typ;
class Klasse
{
   private:
     std:vector<Typ*> typVektor;

   public:

     Klasse() {};
     Klasse() {for(int i=0; i < typVektor.size(); i++) {delete typVektor[i];}

     const Typ* PushTypElement(Typ element) {typVektor.push_back(new Typ(element)); return typVektor.back()}
};
Ich verstehe nicht was daran zu anfällig für Speicherprobleme sein soll.
Danke für die Aufklärung.

Denk mal darüber nach was passiert, wenn ein Objekt der Klasse "Klasse" destruiert wird? Wie sieht es mit dem Kopierzuweisungsoperator aus? ...

Alle Elemente im Vektor typVektor werden destruiert, da es sich um PODs (einfache Zeiger auf Typ) handelt wird gar nichts gemacht, und der Speicher für die referenzierte Objekte vom Typ "Typ" wird nicht freigegeben und die Destruktoren für die Objekte werden nicht aufgerufen.

*john 0

Um das Problem zu verdeutlichen

class Typ;
class Klasse
{
   private:
     std:vector<Typ*> typVektor;

   public:

     Klasse() {};
     ~Klasse() {for(int i=0; i < typVektor.size(); i++) {delete typVektor[i];}

     const Typ* PushTypElement(Typ element) {typVektor.push_back(new Typ(element)); return typVektor.back()}
};

int main () {
  Klasse A;
  // Code zum Füllen von A;
  {
    Klasse B = A;
  } // ab hier enthält A nur noch Zeiger auf Datenmüll!
} // hier versucht der Destruktor bereits freigegeben Objekte freizugeben!

~john schrieb:

Denk mal darüber nach was passiert, wenn ein Objekt der Klasse "Klasse" destruiert wird?
Alle Elemente im Vektor typVektor werden destruiert, da es sich um PODs (einfache Zeiger auf Typ) handelt wird gar nichts gemacht, und der Speicher für die referenzierte Objekte vom Typ "Typ" wird nicht freigegeben und die Destruktoren für die Objekte werden nicht aufgerufen.

Ich hatte mich lediglich vertippt - der Destruktur ist natürlich definiert:

class Typ;
class Klasse
{
   private:
     std:vector<Typ*> typVektor;

   public:

      Klasse() {};
     ~Klasse() {for(int i=0; i < typVektor.size(); i++) {delete typVektor[i]};}

     const Typ* PushTypElement(Typ element) {typVektor.push_back(new Typ(element)); return typVektor.back();}
};

Da wird der Speicher korrekt freigegen, und niemand als das Objekt selbst hat schreibenden Zugriff auf die Elemente hinter dem Zeiger.
Die Objekte, die eine Referenz zu den Elementen besitzen, werden stets vor dem Objekt mit dem Vektor selbst vernichtet.

*john 0

KreuzQuer schrieb:

Da wird der Speicher korrekt freigegen, und niemand als das Objekt selbst hat schreibenden Zugriff auf die Elemente hinter dem Zeiger.

Schau Dir das Posting vorher an.

~john schrieb:

Um das Problem zu verdeutlichen

int main () {
  Klasse A;
  // Code zum Füllen von A;
  {
    Klasse B = A;
  } // ab hier enthält A nur noch Zeiger auf Datenmüll!
} // hier versucht der Destruktor bereits freigegeben Objekte freizugeben!

Das ist doch Sache des Copy-Ctor, der natürlich korrekt definiert sein muß wenn man ihn verwenden will.
Nach dieser Argumentation dürfte man ja gar keine Zeiger als Objektvariablen verwenden.

*john 0

Es geht um Kontrakte. Alle Container der Standard Library sind auf Speicherung von Werten und nicht von Zeiger auf Objekte ausgelegt. Daher empfiehlt es sich nur Objekte direkt oder SmartPointer auf Objekte in einem Container der Standard Library abzulegen, da man so weniger Arbeit hat und nichts übersieht.

class Typ;
class Klasse {
  std:vector<boost::shared_ptr<Typ> > typVektor;
public:
  Typ const* PushTypElement(Typ element) {
    boost::shared_ptr<Typ> sp (new Typ(element));
    typVektor.push_back(sp);
    return sp.get();
  }
};

Alternativ kann man sich natürlich auch direkt die SmartPointer zurückliefern lassen.