Template-Iterator

penpen

Hallo!

Ich möchte gerne eine von list abgeleitete Template-Klasse ilist erstellen, die zusätzlichen einen passenden Iterator it enthält. Dazu verwende ich folgende Klassendefinition:

#include<list>
using namespace std;

template<class T>
class ilist: public list<T> {
  list<T>::iterator it;
};

Leider liefert mein Compilier (gcc) hierzu die wenig hilfreiche Fehlermeldung
ilist.cc:6: error: expected ‘;’ before ‘it’. Woran kann das liegen, bzw. wie mache ich es richtig?

THX 1138

#include<list>
using namespace std;

template<class T>
class ilist: public list<T> {
  typename list<T>::iterator it;
};

Der Typ von Iterator hängt vom Templateparameter T ab, darum musst du dem Compiler sagen, dass es ein Typ ist.
Aber grundsätzlich ist es keine gute Idee von STL Containern zu erben, weil die keine virtuellen Destruktoren haben.
Was brauchst du denn spezielles in der ilist, was std::list nicht hat?

penpen

Danke, so würde es also funktionieren!

Nun, die Idee dahinter ist folgende: Mein Programm verarbeitet eine DAG-Datenstruktur, wobei jeder node u.a. eine list<node>* von Nachfolgern hat, also in etwa so:

class node {
  irgendeintyp nutzdaten;
  list<node*> nachfolger;

Ich möchte nun der Reihe nach alle Pfade des DAGs erzeugen. Der zusätzliche iterator soll nun fürs explizite Backtracking jeweils den nächsten zu wählenden Nachfolger anzeigen. Da ich an der Wurzel des DAGs keinen einzelnen node, sondern eine list<node>* habe, möchte ich den iterator konsequenterweise in der list<node>* unterbringen (und nicht etwa in den nodes).

Du würdest mir aber eher davon abraten? Könntest Du mir bitte genauer erklären, welche Probleme durch das Fehlen der virtuellen Destruktoren entstehen?

schokomann

Das gibt Memory Leaks. Die Objekte der abgeleiteten Klassen werden
nicht zerstört.
Mach dir einfach 2 Klassen Base und Derive. Leite Derive von Base ab.
Beim ersten Test machst du die Destruktoren nicht virtuell, erzeugst
die Objekte und gibst den Speicher wieder frei. Beim zweiten Test
die Destruktoren virtuell machen. Mach eine Ausgabe in die Destruktoren
von Base und Derive oder setz einen Breakpoint rein, damit du siehst
ob und in welcher Reihenfolge die Destruktoren durchlaufen werden.

penpen

OK, danke für den Tipp!

Wenn ich nun also die fragliche Definition

template<class T>
class ilist: public list<T> {
  typename list<T>::iterator it;
};

verwende, und später z.B.

list<int>* x = new ilist<int>();

mache, dann wird bei Freigabe mit

delete x;

der Destruktor von list<int> aufgerufen, nicht aber der von ilist<int>.

Das ist nicht schön, in meinem Fall aber auch nicht wirklich schlimm, da ich für ilist<T> ohnehin keine zusätzlichen Aufräumaktionen benötigen werde.

Trotzdem gut zu wissen, was hier schiefgehen kann!

Konrad Rudolph

penpen schrieb:

dann wird bei Freigabe mit
delete x;
der Destruktor von list<int> aufgerufen, nicht aber der von ilist<int>.

Logisch, der Destruktor von 'list' ist nicht virtuell gemacht.

=> Standardcontainer eignen sich nicht für Vererbung!

(Oder zumindest nicht als Basis polymorpher Objekthierarchien.)

THX 1138

Das ist doch schonmal ein guter Ansatz. Ich würde nicht von Liste erben, sondern diese als Member anlegen.

template<typename T>
class node {
  irgendeintyp nutzdaten;
  typename list<node<T>*> nachfolger;
  typename list<node<T>*>::iterator nachfolge_iter;
  nachfolge_iter erster()
 {
    return nachfolger.begin();
  }
};

So mal als erste Idee, ist jetzt nicht getestet oder ausgereift.

Nun zu deinem Problem. Du möchtest Graphen abbilden richtig?
Schau dir die Boost Graph Library an, die ist sehr ähnlich aufgebaut wie die STL und bietet "Container" für Graphen (Adjazenz Liste und Matrix) sowie diverse Algorithmen und ...trrr...trommelwirbel... Iteratoren!

penpen

THX 1138 schrieb:

Das ist doch schonmal ein guter Ansatz. Ich würde nicht von Liste erben, sondern diese als Member anlegen.

Hätte ich auch getan, falls ich immer mit Knoten arbeiten würde. Nur ist der Einstiegspunkt in meine Datenstruktur eben kein einzelner Knoten, sondern eine Liste von Knoten. Es gibt in dem Graphen eben keine einzelne Wurzel, sondern mehrere Starknoten. Deshalb die Idee, den Iterator in den Listen unterzubringen.

Ein Workaround wäre natürlich, einen Wurzelknoten mit Dummy-Daten einzuführen. Den Vererbungs-Ansatz finde ich aber eleganter.

THX 1138 schrieb:

Nun zu deinem Problem. Du möchtest Graphen abbilden richtig?
Schau dir die Boost Graph Library an, die ist sehr ähnlich aufgebaut wie die STL und bietet "Container" für Graphen (Adjazenz Liste und Matrix) sowie diverse Algorithmen und ...trrr...trommelwirbel... Iteratoren!

Sieht sehr nützlich aus, vor allem eben für ganz allgemeine Graphen. Bis jetzt funktioniert mein Ansatz sehr gut, werde mir die Library aber auf jeden Fall merken.

hustbaer

template <class T> class dingsi
{
public:
    std::list<T> m_list;
    typename std::list<T>::iterator m_backTrackingIteratorDingsDongsLala;
};

Blubb?