Problem mit Templateinstantiierung

ypnos

Hallo,

ich habe im Prinzip den folgenden Code:

class MultiGraph : public SocialMemory {
    struct Mapping {
        double bestObj;
    };

    struct minsol
    {
        minsol(const std::vector<Mapping>* m) : mappings(m) {}
        bool operator()(int s1, int s2) const
        {
            return (*mappings)[s1].bestObj < (*mappings)[s2].bestObj;
        }
    private:
        const std::vector<Mapping>* mappings;
    };

    struct SubGraph {

// Das hier klappt erwartungsgemäß nicht:

        std::set<int, minsol(members)> candidates;

// Wie macht man es dann?
    };

    public:
    private:
        std::vector<Mapping> members;
    };

Hier nochmal eine kurze Umschreibung:

Ich möchte bestimmte Objekte, die nur indirekt greifbar sind, anhand einer ihrer Eigenschaften sortiert vorrätig haben, in erwähntem set namens candidates.

Damit nun anhand des Indizes der Vergleich stattfinden kann, brauche ich das entspr. Mapping (ein Vektor); dieser muss dazu der Vergleichsfunktion zur Verfügung stehen.

Glücklicherweise kann man nun bei Anlegen von so einem Set ein Funktionsobjekt übergeben, bei dem man den Konstruktor mit Parametern aufruft. Allerdings geht das nur im Code selbst, und nicht wie hier, in der Klassendefinition.

Doch wie stelle ich das nun an? Oder welche Möglichkeiten habe ich sonst?

Vielen Dank für Eure Hilfe!

mfg,
Ypnos

CStoll

Der Template-Parameter der Set gibt nur den Typ des Vergleichsfuktors an - wenn es innerhalb des Typs mehrere Variationen gibt, mußt du das konkrete Objekt an den Ctor übergeben:

struct SubGraph
{
  set<int,minsol> candidates;

  SubGraph(const vector<Mapping>* sorter) : candidates(minsol(sorter)) {}
};

Übrigens exisitieren die Unterklassen von MultiGraph relativ unabhängig von ihrer Mutterklasse - d.h. ein SubGraph-Objekt weiß nicht automatisch, zu welchem MultiGraph (wenn überhaupt) es gehört.

PS: Und mit deinem Sortierkriterium könntest du dir noch einige Probleme einhandeln - wenn du 'members' nach dem Anlegen der set<> noch veränderst, zerstörst du damit deren Sortierung.

schokomann

und der Operator müsste so

operator()(const int& s1, const int& s2) const

aussehen.

CStoll

schokomann schrieb:

und der Operator müsste so

operator()(const int& s1, const int& s2) const

aussehen.

Nicht unbedingt - int's sind klein genug, um per Wert übergeben zu werden (und set<> ist es egal, WIE es seine Parameter übergeben kann - wichtig ist nur, daß der Compiler den Elementtyp der set<> konvertieren kann in den Parametertyp der Comparators).

schokomann

ja, richtig int's sind klein.

Aber die Memberfunktion für die Klasse sieht so
bool operator()(const T& x, const T& y) const;
aus.

Das Schlüsselwort const hat nicht nur für Entwickler,
sondern auch für Compiler (z.B. Unix Maschinen) eine Information.
Je nach Compiler und Optimierungsstufe kann besser optimiert werden,
für Entwickler ist klar, dass der Parameter sich nicht ändert und
man gewöhnt es sich erst gar nicht an, dass const wegzulassen
(das Referenzzeichen natürlich auch nicht).
Nacher wird bei größeren Objekten das const auch weggelassen und
dann macht es sich schon bemerkbar.

Bei den internen Datentypen würde es bei sehr sehr vielen Aufrufen,
bzw. wenn die ganze Software voll davon ist auch bemerkbar machen.

In Büchern werden zur Veranschaulichung eines Sachverhaltes die
Parameter auch als Kopie übergeben. Vielleicht machen sich daher viele
keinen Kopf darum.

Ansonsten
viel Spaß noch

LordJaxom

schokomann schrieb:

Aber die Memberfunktion für die Klasse sieht so
bool operator()(const T& x, const T& y) const;
aus.

Was ist das für eine Aussage? Wenn ich die Definition ändere sieht die Memberfunktion nicht mehr so aus :p

Das Schlüsselwort const hat nicht nur für Entwickler,
sondern auch für Compiler (z.B. Unix Maschinen) eine Information.

Was hat jetzt UNIX damit zu tun? Kann unter Windows nicht optimiert werden? Gibt es unter Windows keine schreibgeschützten Speicherbereiche?

Je nach Compiler und Optimierungsstufe kann besser optimiert werden,
für Entwickler ist klar, dass der Parameter sich nicht ändert und
man gewöhnt es sich erst gar nicht an, dass const wegzulassen
(das Referenzzeichen natürlich auch nicht).

Und genau hier liegt imo ein Denkfehler: Wenn ich sowohl const als auch & weglasse, ist mir als Aufrufer egal, ob in der Funktion die Parameter geändert werden, da sich die Änderung nach aussen garnicht auswirkt.

Nacher wird bei größeren Objekten das const auch weggelassen und
dann macht es sich schon bemerkbar.

Stimmt, dann ist es aber IMO entweder Unwissenheit oder Vergesslichkeit
...oder volle Absicht (z.B. wenn sowieso eine Kopie benötigt wird)

Bei den internen Datentypen würde es bei sehr sehr vielen Aufrufen,
bzw. wenn die ganze Software voll davon ist auch bemerkbar machen.

Heisst? Schneidet bei sehr vielen Aufrufen mit internen Datentypen die konstante Referenz besser oder schlechter ab als die Kopie? Ich behaupte in bestimmten Konstellationen kann hier die Kopie sogar besser abschneiden (oder beides ist identisch).

Ansonsten
viel Spaß noch

Jo, werd ich haben

CStoll

schokomann schrieb:

ja, richtig int's sind klein.

Und genau das ist der Punkt - bei der Größe macht es keinen Unterschied, ob du die Adresse des int's übergibst (Referenzen sind auch nur Zeiger, die bei Verwendung implizit dereferenziert werden) oder seinen Wert.

Aber die Memberfunktion für die Klasse sieht so
bool operator()(const T& x, const T& y) const;
aus.

Die Memberfunktion KANN so aussehen, aber niemand zwingt dich, sie so zu definieren (Template-Programmierung benötigt keine vorgegebenen Interfaces, sondern stellt nur bestimmte Vorbedingungen an die beteiligten Klassen - und ein set<T,irgendwas> erwartet, daß es einem 'irgendwas'-Objekt zwei T's übergeben und den Rückgabewert in einem bool speichern kann).

Das Schlüsselwort const hat nicht nur für Entwickler,
sondern auch für Compiler (z.B. Unix Maschinen) eine Information.
Je nach Compiler und Optimierungsstufe kann besser optimiert werden,
für Entwickler ist klar, dass der Parameter sich nicht ändert und
man gewöhnt es sich erst gar nicht an, dass const wegzulassen
(das Referenzzeichen natürlich auch nicht).

OK, das ist ein Argument.

Nacher wird bei größeren Objekten das const auch weggelassen und
dann macht es sich schon bemerkbar.

Dir ist doch sicher klar, daß sich dadurch dann die gesamte Semantik der Funktion ändert? Bei Übergabe per T val (Kopie) und const T& val (konstante Referenz) sind sich alle Beteiligten sicher, daß das übergebene Objekt sich nicht ändern wird - bei Übergabe als T& val gehen sie davon aus, daß es sich ändern kann.

ypnos

Hallo miteinander,

CStoll schrieb:

Der Template-Parameter der Set gibt nur den Typ des Vergleichsfuktors an - wenn es innerhalb des Typs mehrere Variationen gibt, mußt du das konkrete Objekt an den Ctor übergeben:
struct SubGraph
{
  set<int,minsol> candidates;

  SubGraph(const vector<Mapping>* sorter) : candidates(minsol(sorter)) {}
};

Danke für die Information! Das hätte ich mir so nie gedacht, da wenn man innerhalb einer Methode eine Objektinstanz übergeben will, das tatsächlich in der Template-Notation, also innerhalb der <> gemacht wird (so sind auch die Beispiele in der SGI STL Doku). Gut zu wissen, dass es so geht, danke - hätte ich eigentlich auch in der besagten Doku selbst finden müssen!

Übrigens exisitieren die Unterklassen von MultiGraph relativ unabhängig von ihrer Mutterklasse - d.h. ein SubGraph-Objekt weiß nicht automatisch, zu welchem MultiGraph (wenn überhaupt) es gehört.

Genau! Ich müsste also auch dem SubGraph beim Anlegen den Pointer auf den Vector mitgeben.

PS: Und mit deinem Sortierkriterium könntest du dir noch einige Probleme einhandeln - wenn du 'members' nach dem Anlegen der set<> noch veränderst, zerstörst du damit deren Sortierung.

Ja, hier muss ich bei jeder Änderung des Sortierkriteriums die Elemente aus dem Set entfernen (vorher) und dann wieder einfügen. Ist vom Aufwand her vergleichbar/besser, als bei jedem Bedarf komplett neu zu sortieren...

Was die Sache mit der const int& angeht: Ich glaube nicht, dass es Sinn macht, eine Referenz auf einen primitiven Datentyp zu verwenden. Ob nun eine Speicheradresse auf einen Int auf den Stack gelegt wird oder eine Kopie des Int selbst ist kein großer Unterschied - beim Zugriff darauf allerdings kann ich mir eine Indirektion sparen (bei der Referenz muss 2x gelesen werden). Von const int& wird implizit auch auf int gecastet, also entstehen hier auch keine Probleme. const ...& hilft nur bei großen Objekten, weil dann die sonst notwendige Kopie zum Vergleich entfallen kann.

mfg
Ypnos

CStoll

ypnos schrieb:

Hallo miteinander,

CStoll schrieb:
Der Template-Parameter der Set gibt nur den Typ des Vergleichsfuktors an - wenn es innerhalb des Typs mehrere Variationen gibt, mußt du das konkrete Objekt an den Ctor übergeben:
struct SubGraph
{
  set<int,minsol> candidates;

  SubGraph(const vector<Mapping>* sorter) : candidates(minsol(sorter)) {}
};
Danke für die Information! Das hätte ich mir so nie gedacht, da wenn man innerhalb einer Methode eine Objektinstanz übergeben will, das tatsächlich in der Template-Notation, also innerhalb der <> gemacht wird (so sind auch die Beispiele in der SGI STL Doku). Gut zu wissen, dass es so geht, danke - hätte ich eigentlich auch in der besagten Doku selbst finden müssen!

Bei den meisten typischen Vergleichs-Funktoren gibt es ja auch nur einen möglichen Grundzustand - d.h. du übergibst der set<> den Typ und sie verwendet ein Default-konstruiertes Objekt dieses Typs.

(wenn ich dich falsch verstanden habe, solltest du diese Aussage genauer erklären)

PS: Und mit deinem Sortierkriterium könntest du dir noch einige Probleme einhandeln - wenn du 'members' nach dem Anlegen der set<> noch veränderst, zerstörst du damit deren Sortierung.

Ja, hier muss ich bei jeder Änderung des Sortierkriteriums die Elemente aus dem Set entfernen (vorher) und dann wieder einfügen. Ist vom Aufwand her vergleichbar/besser, als bei jedem Bedarf komplett neu zu sortieren...

Bist du sicher, daß das besser ist? Aus meiner Sicht ist dieser Ansatz nur unnötig fehleranfällig (und du hast keine automatischen Möglichkeiten, eine Änderung des Sortierkriteriums zu entdecken).

ypnos

Hallo,

was die Objektinstantiierung angeht, meine ich, dass in einem anderen Kontext (innerhalb des Codes) das hier möglich wäre:

std::set<int, minsol(members)> candidates;

...was eigentlich auch etwas verwunderlich ist. Ich muss aber zugeben, dass das nur vage Erinnerungen sind und ich es damals vielleicht ja doch mit dem Konstruktur gemacht habe!

Was die Methodik an sich angeht: Du hast recht dabei, das in Frage zu stellen. Man muss genau bescheid wissen, wann sich das Kriterium ändert und man muss auch abwägen zwischen der Anzahl der Updates versus der Anzahl der Abfragen (also wie oft ich die sortierte Liste brauche).

Ich habe hier mal ein Beispiel, das etwas nachvollziehbarer ist, als das was ich hier mache:

Ich habe Knoten in einem Graphen und ich möchte nun den Graphen "vervollständigen", d.h. dass ich beliebig neue Kanten zwischen den Konten hinzufüge. Dabei will ich aber auch, dass der Grad der einzelnen Knoten möglichst wenig variiert, d. h. ich füge Kanten bevorzugt zwischen Konten ein, deren Grad gering ist; diese dürfen aber auch nicht schon miteinander verbunden sein.

Meine Lösung dazu ist wie hier ein entspr. Set. Der Vorteil ist hier klar ersichtlich: Wenn ich Kanten hinzufüge, d.h. der Grad sich ändert, dann ist das ohnehin genau an der Stelle, an der ich mit dem Set arbeite. Fehleranfälligkeit quasi 0, solange ich nicht anfange, den Graph auch an anderen Stellen zu modifizieren. Aufwandstechnisch natürlich viel besser: Anstelle jedes Mal komplett neu zu sortieren (und hier ist, da ja große Teile schon sortiert sind, qsort sehr schlecht), müssen nur jew. 2 Elemente neu einsortiert werden.

mfg
Ypnos

CStoll

ypnos schrieb:

Hallo,

was die Objektinstantiierung angeht, meine ich, dass in einem anderen Kontext (innerhalb des Codes) das hier möglich wäre:
std::set<int, minsol(members)> candidates;
...was eigentlich auch etwas verwunderlich ist. Ich muss aber zugeben, dass das nur vage Erinnerungen sind und ich es damals vielleicht ja doch mit dem Konstruktur gemacht habe!

Dann vermute ich eher, daß deine Erinnerungen zu ungenau waren.

Anstelle jedes Mal komplett neu zu sortieren (und hier ist, da ja große Teile schon sortiert sind, qsort sehr schlecht), müssen nur jew. 2 Elemente neu einsortiert werden.

Es gibt auch noch andere Sortierverfahren als QuickSort - und bei "fast komplett" sortierten Daten ist afaik InsertionSort recht gut verwendbar.

ypnos

Ja, insertionsort ist spitze dafür. Verkettete Liste dann quasi, wäre perfekt für meinen Einsatzzweck..

So oder so müsste ich mir die Datenstruktur dann selbst schreiben. Das Set liefert mir hier aber einen vernünftigen Aufwand zu einem sehr gutem Preis (was die Codezeilen angeht ;)).

Wobei ich mich hier gerade frage, ob ich nicht in eine Falle tappe. vllt. sollte ich statt einem set hier eine list verwenden