STL container und abstrakte Datentypen - praktische tips

Hallo,
Entschuldigung, mir ist erst am schluss engefallen, dass das hier ja ein deutsches forum ist
hab aus versehen alles in englisch geschrieben. Antworten koennt ihr aber natuerlich in deutsch.

I am currently struggling with STL containers and abstract types. I am lacking rules of when to use pointers references or values in containers.

class Manager {
public:
	map<IA, IB> GetAssoc() { return assoc; }
	void InsertAssoc(IA a, IB b) { assoc[a] = b; }

private:
	map<IA, IB> assoc;
}

A and B are both abstract types (having pure virtual functions) and we have CA and CB which are the non abstract implementations of IA and IB.
My code example will not work, as InsertAssoc(IA a, IB b) requires copy constructors for IA and IB, which, as much as i know, are not possible to do for abstract types. or is it possible to call the copy constructor of CA within the copy constructor of IA?
So my next try was to use pointers and references, but i did not seem to find a good combination.
What i want is:
* the user of Manager shall only have to know about IA and IB, not about CA and CB
* on GetAssoc(), the user shall receive a map of IA and IB which he can not change, and he shall not be able to change IA or IB either.
* if i have to use IA* in the map, i need the IAs to be compared with each other through IA::operator==, and not through comparing the pointer adresses with each other
* i want as little copying of objects as possible

i am not able to find a good solution. whatever way i try, i always end up getting problems cause the compiler tries to call the copy constructor of one of IA or IB, which do not exist, or i end up with too much copying or an other problem.
Take the following example:

class Manager {
public:
	const map<const IA&, const IB*>* GetAssoc() { return &assoc; }
	void InsertAssoc(const IA& a, const IB& b) { assoc[CA(a)] = new CB(b); }

private:
	map<const CA&, const IB*> assoc;
}

Besides that is pretty ugly in my eyes, i also have the problem that i can not return assoc in GetAssoc(), because assoc doeas not match the return type.

I am initially a Java guy, now somewhat familiar with C aswell, but .. as you see, still having problems with C++ in practise; I am confused!
Could you please help me getting some rules of how to handle this and possibly similar situations?
thank you!

hoijui

asc

hoijui schrieb:

...

Ich vermute einfach (nicht böse gemeint) das du die Java-Brille aufhast.

Grundsätzlich musst du hierzu eines bedenken: Java-Referenzen entsprechen eher den C++ Zeigern (von der internen Abbildung) als irgend etwas anderes. Wenn du nur eine Typangabe in C++ machst so sind typen von exakt dieser Klasse gemeint, für die Verwendung von Abstrakten Klassen müßt du Zeiger und Referenzen verwenden, letzteres geht aber bei Containern wiederum auch nicht, da die Container der Standardbibliothek mit Kopieren arbeiten.

So, verlassen wir wieder die reine Theorie und wenden uns der Praxis zu. Tatsächlich bleibt dir auf den ersten Blick nur der Weg über Zeiger. Du könntest dir alternativ aber mal den TR1 oder Boost anschauen (ersteres wird teilweise von einzelnen Standardbibliotheken schon abgebildet, letzteres findest du unter www.boost.org, die auch eine TR1 Implementierung mitbringen).
In beiden Fällen heißt die Alternative shared_ptr, ein sogenannter Smartpointer (In diesen Fall einer mit Refernzzählung der auch in Containern verwendet werden kann). Für ausführliche Erklärungen bitte die Suchfunktion des Forums...

cu André

pumuckl

Du kannst froh sein dass du das gleich mit abstrakten Typen ausprobiert hast. (denen du durchaus auch den Copy-Ctor implementieren kannst und sogar solltest, wenn sie kompliziertere Innereien haben)
Was du sonst nämlich hättest beobachten können nennt sich Slicing:
du übergibst dem Insertoperator des Containers ein abgeleitetes Objekt. Da der Container aber für die Basisklasse instantiiert ist wird deren Copy-Ctor aufgerufen ,dem man durchaus auch abgeleitete Objekte übergeen kann. Der Copy-Ctor kopiert dann einfach nur den Basis-Teil in das Objket im COntainer und lässt den Rest unbeachtet, schöner Informationsverlust!
Du solltest stattdessen am Besten Smartpointer auf die Basisklasse in den Container stopfen, dann entfällt am Ende lästiges Aufräumen.

hustbaer

For stuff like that you can use boost::shared_ptr<IA>, boost::shared_ptr<IB>.
Like so:

class IA {
public:
    virtual bool Compare(IA const& other) = 0;
};

class IB {
public:
    virtual void Foo() = 0;
};

struct IACompare {
    bool operator ()(boost::shared_ptr<IA> const& left, boost::shared_ptr<IA> const& right) {
        return left->Compare(*right);
    }
};

std::map<boost::shared_ptr<IA>, boost::shared_ptr<IB>, IACompare> my_map;

// ---

void foo()
{
    boost::shared_ptr<IA> a1(new CA("bar"));
    boost::shared_ptr<IA> a2(new CA2("bar"));

    boost::shared_ptr<IA> b(new CB("baz"));

    my_map[a1] = b;
    my_map[a2]->Foo();
}

However most of the time one doesn't use things like that, because there are usually more elegant solutions available in C++.

danke vielmal ihr zwei, super antworten, danke!

Durch die Java brille sieht das ganze viel schoener aus.
Aber.. naja, zur praktishcen loesung kommt man mit der anscheinend nicht, wenns um C++ geht.

Das projekt fuer das ich schreibe, benutzt schon boost, allerdings erst threads und regex. aber so wie ichs verstanden habe, sind die smart pointer ja nicht notwendig, sondern nur eine erleichterung. grundsaetzlich kann ich mit pointern schon recht gut umgehen, da ich schon eine wiele C gecoded habe fuer das projekt bis jetzt; da mach ich mir nicht so sorgen drumm, dass ich da viel falsch machen wuerde.

Nach euren beitraegen, wuerd ichs jetzt etwa so machen:

class Manager {
public:
	~Manager() { /* delete all pointers in assoc */ }
	const map<const IA*, const IB*>* GetAssoc() { return &assoc; }

private:
	map<const IA*, const IB*> assoc;

	void InsertAssoc(const IA& a, const IB& b) { assoc[new CA(a)] = new CB(b); }
}

Der Manager wird beim erstellen initialisiert (InsertAssoc() wird ein paar mal aufgerufen), und danach wird veraendert sich assoc nicht mehr, ich kann also eigentlich die map direkt als const zurueckgeben in GetAssoc().
Was meint ihr zu dem entwurf?

Einige fragen:
1. wenn ich eine "const map" oder "const map*" habe, ist dann nur das hinzufuegen und loeschen von elementen zu der map verboten, oder bekommt man auch nur const elemente aus der map, die man dann nicht aendern kann?
oder anderst gesagt:
wenn nichts veraendert werden darf (weder die map noch deren keys und values), was muss ich zurueck geben:
a) const map<const IA*, const IB*>*
b) const map<IA*, IB*>*
2. Ich habe IA als abstrakt, und CA als implementation, die auch einen copy construktor hat. Was ich nun moechte, ist ca. dies hier:

IA::IA(const IA& ia) {
	this = new CA(ia);
}

ich glaube aber das hab ich probiert, und der compiler wollte es nicht. Wie sollte ich denn den copy konstruktor von IA implementieren?
3. Wenn ich den key wert der map als pointer habe (map<IA*, IB*>), wie werden die keys miteinander verglichen? werden die adressen verglichen, oder wird der operator== oder operator< oder sonst einer benutzt? Ich haette gern, dass operatoren benutzt werden, nicht die adressen. Mus ich da einen speziellen comparator mitgeben, damit das so funktioniert?

danke hustbaer
nach deinem beispiel nehm ich an, dass ich so oder so einen eigenen comparator benoetigen werde. mich wuerde es aber sehr interessieren wie es elleganter moeglich waere in C++! wenn es eleganter ist, muss es doch auch recht einfach sein, nicht?

ich hab mal nachgeschaut, und an anderen orten im projekt verwenden sie schon boost::shared_ptr, das ist also schon voll integriert, koennt ich ohne probleme verwenden. werde das auch mal tun, aber waere an einer eleganteren loesung schon auch interessiert

Simon2

hoijui schrieb:

...
Einige fragen:
1. wenn ich eine "const map" oder "const map*" habe, ist ...

... nur die Anwendung von const-Funktion (Member- oder freie) erlaubt.
Damit ist z.B. der operator[]() (der nicht const ist) verboten.

hoijui schrieb:

...
a) const map<const IA*, const IB*>*
b) const map<IA*, IB*>*

map<const IA*, const IB*> und map<IA*, IB*> sind unterschiedliche Klassen - die kannst Du sowieso nicht miteinander "verwursten" (müsstest umkopieren).

hoijui schrieb:

...
2. Ich habe IA als abstrakt, und CA als implementation, die auch einen copy construktor hat. Was ich nun moechte, ist ca. dies hier:
IA::IA(const IA& ia) {
	this = new CA(ia);
}
...

technisch: Soweit ich weiß, kann man "this" nichts zuweisen ....
inhaltlich: IA als abstrakte Basis ist nicht besonders sinnvoll, wenn jedes Objekt (egal von welcher Blattklasse) beim Kopieren sowieso auf ein CA-Objekt "verbogen" wird.

Copy-Konstruktoren werden üblicherweise in den Blattklassen implementiert.

Gruß,

Simon2.

danke auch dir simon

1. hier will ich eigentlich nur wissen ob ich a) oder b) verwenden soll, ich will die nicht mischen. falls b) fuer meine zwecke ausreichend ist, werde ich b) verwenden, sonst halt a).
In Java ist es so, dass bei einer final Map zwar keine objekte geloescht oder hinzugefuegt werden koennen, aber die objekte selber koennen veraendert werden. Ich dachte in C++ sei das anderst, bei einer const map (so stell ichs mir jedenfalls vor, wie ich die funktionsweise von map verstanden habe). da ich mir aber nicht sicher bin, hab ich gefragt.
tschuldigung, aber nach deiner antwort bin ich mir immer noch nicht sicher.

Simon2 schrieb:

hoijui schrieb:
2. Ich habe IA als abstrakt, und CA als implementation, die auch einen copy construktor hat. Was ich nun moechte, ist ca. dies hier:
IA::IA(const IA& ia) {
	this = new CA(ia);
}
...
technisch: Soweit ich weiß, kann man "this" nichts zuweisen ....
inhaltlich: IA als abstrakte Basis ist nicht besonders sinnvoll, wenn jedes Objekt (egal von welcher Blattklasse) beim Kopieren sowieso auf ein CA-Objekt "verbogen" wird.

Das verbiegen waehre eigentlich ok, so wie ichs brauche. das was mir wichtig ist, was ich behalten moechte, ist nur das was in IA und IB drinn steht. die verschiedenen implementationen so wie CA, DA, EA z.B., werden nur dazu benoetigt die informationen von verschiedenen quellen zu laden oder zu speichern. wen das mit dem copy konstruktor in IA irgendwie funktionieren wuerde, waere das gut. Du hast aber recht damit, das das mit an this zuweisen nicht funktioniert. wie wuerd ich das denn technisch machen?

Am besten waere natuerlich, wenn ich virtuelle copy konstruktoren haben koennte, aber das gibts ja nicht (bzw nur sowas selbstgebasteltes).

pumuckl

der Copy-Ctor von IA ist nur dazu da, um den IA-Teil der bageleiteten KLassen zu kopieren. Des weiteren ist ein Konstruktor einer Klasse dazu da, genau diese Klasse aufzubauen, also ein Objekt der Klasse zu initialisieren, und nicht ein Objekt irgendeiner abgeleiteten Klasse.

Blödes Beispiel: Ich habe ein Brötchen (Basisklasse), belegt mit Salat, Käse, Schinken und Gurkenscheiben (belegtesBrötchen = abgeleitete Klasse).
Um noch so ein Brötchen zu kriegen sag ich dem belegten Brötchen "verdoppel dich" (schön wärs ja...), und standardmäßig wird ein neues Belegtes Brötchen erstellt indem sich zuerst das Brötchen verdoppelt, danach dann Salat, Käse, Schinken udn Gruke verdoppelt werden und in das eigentliche Brötchen gelegt werden. Was du jetzt versuchst ist, bei jeder Brötchen-Kopie sofort Salat & Co mitzuliefern, so dass spätestens beim Versuch, ein Fischbrötchen zu kopieren das Ganze sehr komisch schmecken würde. Gut also, dass das nicht geht.

Jetzt hab ich Hunger....

Simon2

hoijui schrieb:

...
1. hier will ich eigentlich nur wissen ob ich a) oder b) verwenden soll, ...

Ich will darauf hinaus, dass diese Entscheidung nicht nur den Rückgabetypen dieser Funktion betrifft. Wenn Deine Klasse eine map<IA*, IA*> als Member enthält, kannst Du diese gar nicht als map<IA const*, IA const*> rausgeben !

hoijui schrieb:

...
In Java ist es so, dass bei einer final Map zwar keine objekte geloescht oder hinzugefuegt werden koennen, aber die objekte selber koennen veraendert werden....

Die Frage ist nicht so einfach zu beantworten, wie Du denkst.

Laut Standard ("23.3.1.3") gibt's von find() 2 overloads:

iterator      find(const key_type& __x);
      const_iterator   find(const key_type& __x) const;

von der die const-Variante für eine "map const" genommen werden kann.
operator[] gibt's dagegen nur einmal ("23.3.1.2"):

mapped_type& operator[](const key_type& __k);

Deswegen ergibt sich Folgendes:

#include <iostream>
using std::cout;

#include <map>
using std::map;

struct A {
	A() { m[0] = 10; m[1] = 11; m[2] = 12; }
	map<int, int> m;
	map<int, int> const * getM() { return &m; }
};

int main() {
   A a;
   map<int, int> const * p = a.getM();

   cout << (*p)[1]; // geht nicht: operator[] nicht const	
   cout << p->find(1)->second; // geht: find() ist const
   p->find(1)->second = 22; // geht nicht: const-find() gibt const_iterator raus

   return 0;
}

pumuckl schrieb:

Du kannst froh sein dass du das gleich mit abstrakten Typen ausprobiert hast. (denen du durchaus auch den Copy-Ctor implementieren kannst und sogar solltest, wenn sie kompliziertere Innereien haben)

class IA {
public:
   IA(const IA& ia);
   virtual int GetX() const = 0;
};

class CA : public IA {
public:
   CA(const IA& ia) { x = ia.GetX(); }
   virtual int GetX() const { return x; }
   virtual void SetX(int newX) { x = newX; }
private:
   int x;
};

Hier kann ich doch gar keinen copy konstruktor von IA implementieren, der den x wert mitkopiert, obwohl dieser zu IA gehoert. in CA geht das aber, darum wollte ich den CA copy konstruktor aufrufen. ich weiss schon, dass das nicht ganz sauber ist. ganz sauber waehre meiner meinung nach mit einem virtuellen kopy konstruktor, nicht?
oder muss ich die SetX() methode schon in IA drinn haben? das will ich eigentlich nicht.

Simon2

hoijui schrieb:

...

Simon2 schrieb:

...
inhaltlich: IA als abstrakte Basis ist nicht besonders sinnvoll, wenn jedes Objekt (egal von welcher Blattklasse) beim Kopieren sowieso auf ein CA-Objekt "verbogen" wird.

Das verbiegen waehre eigentlich ok, so wie ichs brauche. ...

Ehrlich gesagt: Das glaube ich nicht.
Du machst Dir vermutlich gar nicht bewusst, wie oft Copy-Konstruktoren verwendet werden ... und in wie vielen Fällen Dein "Sonderverhalten" in die Hose gehen kann, gerade weil es total dem "Usus" widerspricht. in Java würdest Du doch vermutlich auch nicht

clone() { Festplatte_formatieren(); }

implementieren...

Gruß,

Simon2.

Simon2 schrieb:

hoijui schrieb:

...
1. hier will ich eigentlich nur wissen ob ich a) oder b) verwenden soll, ...

Ich will darauf hinaus, dass diese Entscheidung nicht nur den Rückgabetypen dieser Funktion betrifft. Wenn Deine Klasse eine map<IA*, IA*> als Member enthält, kannst Du diese gar nicht als map<IA const*, IA const*> rausgeben !

Ihr unterschaetzt meine Macht, junger Sternen-Geher! Ich bin der Herrscher ueber Manager, IA und alles andere! ich kann sowohl den rueckgabewert der funktion sowie den type all meiner membervariablen nach belieben waehlen! ich werde sie gleich waehlen. nur wie ich sie waehlen werde ist noch die frage.

... Aber diese frage hast du mit dem zweiten teil beantwortet, danke!!
map<IA*, IB*> ist ausreichend, sehr gut! das gefaellt mir besser als in Java.

werde wohl auch die shared_ptr benutzten.

Simon2

hoijui schrieb:

...
Ihr unterschaetzt meine Macht, junger Sternen-Geher! ...

Mitnichten, junger C++-Padawan.

hoijui schrieb:

...ich kann sowohl den rueckgabewert der funktion sowie den type all meiner membervariablen nach belieben waehlen! ich werde sie gleich waehlen....

Ja schon, aber bei einer "map<const IA*, const IB*>" als Member kannst Du ja auch innerhalb der Klasse nicht schreibend auf die Elemente zugreifen ... vielleicht willst Du das ja auch nicht, aber darauf wollte ich nur hinweisen.

Gruß,

Simon2.

Simon2 schrieb:

Du machst Dir vermutlich gar nicht bewusst, wie oft Copy-Konstruktoren verwendet werden ... und in wie vielen Fällen Dein "Sonderverhalten" in die Hose gehen kann, gerade weil es total dem "Usus" widerspricht. in Java würdest Du doch vermutlich auch nicht
clone() { Festplatte_formatieren(); }
implementieren...

hmm.. ich hab keine ahnung was du damit meinst

ich hab aber schon eine ahnung wie oft copy konstruktoren verwendet werden. Weill miene IA klasse naehmlich keinen hat, kriege ich eine compiler fehlermeldung an jedem ort wo dieser den copy-ctor aufrufen will

ist die idee eigentlich, dass der IA copy-ctor gar nie benutzt werden muss? soll ich desshalb alles mit pointern machen?

hehe simon!
ich bin der uebermuetige, ueberhebliche lehrling.. jaja.. hast ja recht ;-D

Was ich aus der diskussion um map gelernt habe, ist, dass map<const IA*, const IB*> eigentlich keinen sinn gibt. weill man den gleichen effekt mit const map<IA*, IB*> bekommt, und da braucht man dann eben nicht umzukopieren. ich kann mich auch nicht erinnern, schonmal eine map mit const key oder value gesehen zu haben (aussert bei const char*). es waehre eigentlich noch sinnwoll, wenn das in tutorials fuer C++ STL containers erwaehnt wuerde, hab ich aber bis jetzt noch nie gelesen. klar, man kann es aus dem code ableiten... aber da muss man zuerst mal auf die idee kommen das es so sein koennte, und dann alle methoden durch gehen, um zu schauen ob die bei const auch wirklich keine moeglichkeit zum veraendern der keys und values erlauben.

pumuckl

hoijui schrieb:

Was ich aus der diskussion um map gelernt habe, ist, dass map<const IA*, const IB*> eigentlich keinen sinn gibt. weill man den gleichen effekt mit const map<IA*, IB*> bekommt

ähm nein.
- bei einer map<const IA*, const IB*> hast du eine Map mit zeigern auf konstante Objekte. Du kannst der map sowoghl zeiger auf weitere Konstante Objkete hinzufügen und entfernen, als auch die Zeiger, die schon in der map sind, umbiegen auf andere konstante Objkete
- const map<IA*, IB*> heißt, dass du weder neue Zeiger hinzufügen kannst noch die Zeiger umbiegen kannst (weil ein Zugriff auf eine const map nur const values, also konstante Zeiger liefert) was du sehr wohl kannst ist die Objekte zu verändern, auf die die Zeiger verweisen, denn die Objkete selbst sind nicht const. Somit sind die bieden das genaue gegenteil, const-bezüglich
- der vollständigkeit halber: map<IA * const, IB * const> wäre eine weitere Alternative. Hier kannst du die Zeiger nicht umbiegen (sind ja const), kannst aber sehr wohl weitere konstante zeiger einfügen und entnehmen (die map selbst ist nicht const), und auch die Objkete sind veränderbar.

Simon2

pumuckl schrieb:

...
- const map<IA*, IB*> ... was du sehr wohl kannst ist die Objekte zu verändern, auf die die Zeiger verweisen, denn die Objkete selbst sind nicht const. Somit sind die bieden das genaue gegenteil, const-bezüglich
...

Hmmm also ich glaube nicht.
In der "Container-Theorie" schon (bei einem Array geht das vermutlich) ... aber Du bekommst bei einer const-map keine veränderbaren Referenzen auf die Elemente.
Oder habe ich da was übersehen ?

Gruß,

Simon2.

ja, hab das eben auch so verstanden wie simon. von einer const map bekommt man nur const_iterators, keine iterators, und auch operator[] kann man nicht verwenden, weill der nicht const ist (hat simon schon erklaehrt). wie soll man also die elemente veraendern koennen?
die einzige weise die ich sehe ist, wenn man pointer drinn hat, dass dann nur die pointer konstant sind, nicht aber die daten selber, auf die sie zeigen, wenn man sie ueber den const_iterator aus der map holt. ist das so?

pumuckl

Simon2 schrieb:

In der "Container-Theorie" schon (bei einem Array geht das vermutlich) ... aber Du bekommst bei einer const-map keine veränderbaren Referenzen auf die Elemente.
Oder habe ich da was übersehen

Ja, hast du. Die Elemente der Map sind Pointer, nicht die Daten selbst. Die Pointer sind wie geschrieben nicht veränderbar, aber dereferenzierung ändert den Pointer ja auch nicht. Worauf diese Pointer zeigen ist aber durchaus veränderbar. Das ist der unterschied zwischen

const T*; //pointer auf ein const objekt
T* const; //const pointer auf ein durchaus veraenderbares Objekt

nehmen wir einen konstanten Container<T> wie im Beispiel, dann ist T in dem Fall ein IA*. Ein zugriff auf den konstanten Container liefert mir ein const T&, also ein IA *const& - eine Referenz auf einen Konstanten zeiger auf ein (nicht-konstantes) IA