Listenelemente wissen nicht zu welcher Liste sie gehören!

Pigeon

Hallo!

Ich habe eine Liste nach folgendem Prinzip realisiert. (sämtliche listeneinträge müssen von listLink abgeleitet sein.)

class listLink
{
  listLink* prev; //Vorgänger
  listLink* next; //Nachfolger
};

template<class T>
class list_t
{
   T* vFirst;
   T* vLast;

   unsigned vCount;

public:
   void append(T* what, T* where);
   void remove(T* what);
   ...
   ...
   ...
};

Nun das Problem:

list_t<eineTolleKlasse_t> eineListe;
   eineListe.remove(einZeiger);

Die liste arbeitet natürlich mit den zeigern vPrev und vNext. Wenn einZeiger in wirklichkeit gar nicht in list drinnen ist, dann gibt es natürlich Probleme. Bekommt nun jedes Element einen Zeiger auf seine Liste ist der Speicherverbrauch wohl zu groß(?). (Ich habe sehr sehr große und viele Listen).

Kann man vielleicht eine art statische Elementvariable für eine bestimmte Gruppe von Instanzen realisieren?

Dankesehr

funky cat

Pigeon schrieb:

Die liste arbeitet natürlich mit den zeigern vPrev und vNext. Wenn einZeiger in wirklichkeit gar nicht in list drinnen ist, dann gibt es natürlich Probleme.

Du musst eindeutig festlegen, wie die Zeiger eines Elements gesetzt sind, das sich in einer Liste oder nicht in einer Liste befindet. Dann sollte es keine Probleme geben. Aber vielleicht habe ich deine Frage auch nicht richtig verstanden.

Pigeon

Naja ich habe mehrere Listen. Sagen wir ListA und ListB. Zusätzlich habe ich das Element e23. Ich möchte jetzt irgendwie wissen zu welcher Liste das Element e23 gehört.

ohne in jeder Liste nachzusehn (zu aufwändig)
ohne den Elementen einen Zeiger auf die jeweilige Liste zu verpassen (zu großer speicherbedarf)

Jester

Pigeon schrieb:

ohne in jeder Liste nachzusehn (zu aufwändig)
ohne den Elementen einen Zeiger auf die jeweilige Liste zu verpassen (zu großer speicherbedarf)

tut mir leid, aber geschenkt gibt's nichts. du wirst dir diese information entweder abspeichern müssen oder mit laufzeit dafür bezahlen es nachzuschaun.

funky cat

Wenn dir ein Zeiger zu viel Speicher verbraucht, dann benutz eine ID, z.B ein 16 Bit Wert, für die Listenzugehörigkeit. Ohne eine zusätzliche Information in den Listenelementen selber, wirst du in den Listen suchen müssen. Und das ist bei vielen, großen Listen wohl der schlechteste Weg.

Pigeon

aber mit eine ID muss ich doch auch mehr oder weniger lang "suchen" ?! Wie verwende ich die ID dann am besten?

funky cat

Am besten du nimmst ein Array, das allen Pointer auf alle Listenköpfe speichert. Dann ist die ID einfach ein Index in das Array. Hast du z.B. weniger als 257 Listen, dann reicht für die ID ein einzelnes Byte.

Shade Of Mine

Ich sehe den Sinn nicht wirklich das abzuspeichern. Es waere ein Logikfehler ein Element aus einer Liste zu loeschen in dem das Element nicht drinnen ist und Logikfehler schreibt immer nach assert.

Also einfach:

void remove(Node* node) {
  assert(contains(node));
  //...
}

contains kann dann ja jedesmal die komplette liste durchgehen und schauen ob node enthalten ist. stoert ja niemanden, da es nur in der debug version stattfindet.

Pigeon

Shade Of Mine schrieb:

Ich sehe den Sinn nicht wirklich das abzuspeichern. Es waere ein Logikfehler ein Element aus einer Liste zu loeschen in dem das Element nicht drinnen ist und Logikfehler schreibt immer nach assert.

Also einfach:
void remove(Node* node) {
  assert(contains(node));
  //...
}
contains kann dann ja jedesmal die komplette liste durchgehen und schauen ob node enthalten ist. stoert ja niemanden, da es nur in der debug version stattfindet.

das ist um einiges besser als mein print-debug dass ich auskommentiere, lösche, wieder hinschreibe ... danke

phlox81

Shade Of Mine schrieb:

Ich sehe den Sinn nicht wirklich das abzuspeichern. Es waere ein Logikfehler ein Element aus einer Liste zu loeschen in dem das Element nicht drinnen ist und Logikfehler schreibt immer nach assert.

Sehe ich genauso.

Btw. wieso benutzt du nicht einfach die STL Container oder boost::ptr_container?

Jester

phlox81 schrieb:

Btw. wieso benutzt du nicht einfach die STL Container oder boost::ptr_container?

möglicherweise weil std::list absolut unbrauchbar ist? Die angegebenen Garantien und das Interface schränken die Anwendbarkeit dermaßen ein, dass man oft gezwungen ist was eigenes zu machen.
Um nur ein Beispiel zu nennen: Wozu muß man denn überhaupt wissen in welcher Liste ein Element ist um es zu löschen, wenn man schon einen iterator darauf hat?