Wie lässt sich das korrigieren?

8

Ich habe ein const-Korrektheitsproblem, das ich anscheinend nicht lösen kann. Hier ist die Struktur meines Programms:

%Vor%

Nun ist die Sache, wenn ich die Funktion Graph::get_node_by_id() aufrufen möchte, möchte ich einen Zeiger auf einen gegebenen Knoten zurückgeben (Typ Node ). Aber das scheint unmöglich zu sein, weil std::set implizit meine Knotentypenobjekte in const Node -Objekte konvertiert, und ich kann keine non-const pointer von einem const -Objekt abrufen.

Ich kann jedoch nicht alles andere auf const Node setzen lassen (was das Problem lösen würde), weil ich Node::add_neighbour() von Graph::add_edge() aufrufen möchte, aber mein Compiler sagt immer, dass ich vielleicht verstoße Die const ness (erforderlich, um eine sortierte Menge zu haben) der Elemente in der node_list Menge, obwohl ich die less operator< so definiert habe, dass sie nur für id gilt.

Gibt es etwas, was ich tun kann, um dieses Dilemma zu lösen (ohne auf eine sortierte Menge zu verzichten)? Vielen Dank für Ihre Antworten!

Weitere Informationen zum Fehler:

Wenn ich nicht konstante Felder verwende, Fehler in Graph::get_node_by_id() :

%Vor%

Wenn ich konstante Felder verwende, Fehler in Graph::add_edge() :

%Vor%     
Adam Hunyadi 29.01.2016, 00:09
quelle

2 Antworten

3

Ihr Problem scheint zu sein, dass Sie zwei verschiedene 'Wertesemantiken' für Node haben.

Eins ist das, das von operator< verfügbar gemacht wird, das nicht von add_neighbour betroffen ist. Dies ist der eine set , der benötigt wird, um die Dinge geordnet zu halten, und den er erzwingt, indem er Node const macht.

Das andere ist das, was von der Klassen-API zur Verfügung gestellt wird, wobei sowohl set_id als auch add_neighbour den Wert ändern würden.

Um Ihre sortierte set beizubehalten, dürfen Sie nicht zulassen, dass die ID eines Knotens geändert wird, sobald sie in der Gruppe ist. Aber Sie können den Nachbarn das Ändern erlauben.

Ich schlage also vor, dass Sie neighbours set mutable , add_neighbour private und const machen und Graph a friend von Node machen.

Dies gibt mutable Ihnen, Datenmitglieder, die nicht Teil des 'Wertes' eines Typs sind. Beachten Sie, dass dies bedeutet, dass Sie angeben, dass etwas, das ein const Node* enthält, erwartet, dass sich das Ergebnis von is_neighbour zwischen den Aufrufen ändert.

Also ...

%Vor%

Nun haben Sie öffentliche, nicht-konstante Mutatoren für Node Instanzen, die nicht in Graph s set sind, und einen zusätzlichen Mutator für Graph , um die Nachbarn des% zu ändern. co_de% s in Node .

Also nur set kann

machen %Vor%

Wenn Sie Graph wirklich nicht vertrauen, können Sie die Graph private const durch eine innere add_neighbour ersetzen, mit einer class Methode, da eine innere static add_neighbour(Node* node, Node* neighbour implizit fähig ist um auf private Daten der äußeren Klasse zuzugreifen.

%Vor%

Jetzt kann nur class tun

%Vor%

In beiden Fällen funktioniert Folgendes für alle:

%Vor%

An diesem Punkt sollten Sie einen Code-Geruch erleiden ... Das Problem ist die Methode Graph public in Graph. Sie möchten wahrscheinlich lieber einen Iterator anstelle des rohen get_node_by_id und machen Node* eine private innere Klasse von Graph.

Oder ersetzen Sie einfach das gesamte Node -Konzept durch Node ...

Aber es hängt von Ihrem tatsächlichen Anwendungsfall ab.

    
TBBle 29.01.2016, 10:34
quelle
1

Obwohl die TBBle-Analyse korrekt ist, gibt es eine viel einfachere Lösung: Ersetzen Sie Graphs std::set<Node> durch std::map<int,Node> .

Ihr aktuelles Graph::get_node_by_id() verwendet eine lineare Suche, weil set nicht die von Ihnen gewünschte Suche liefert. Wenn Sie den Schlüssel external verwenden, können Sie die operator< -Überladung entfernen und dennoch eine schnellere und natürlichere Suche erhalten: map.find(id) .

Der einzige hässliche Teil ist, dass Ihr Node nun eine interne ID hat, die mit einem externen Schlüssel übereinstimmen muss. Wenn Sie die ID nie verwenden, außer einen Knoten in der Karte nachzuschlagen, können Sie dies ganz entfernen. Wenn Sie den Diagrammkanten (Nachbarn) folgen und dann die ID überprüfen müssen, können Sie Ihre Zeigergruppe durch eine Reihe von Map-Iteratoren ersetzen, wie:

%Vor%

Dann hat Ihr Traversal die pair<const int,Node> verfügbar.

NB. Wenn man von Spiegelung zu Karte wechselt, ergibt sich fast der gleiche Unterschied wie in TBBles Antwort: man zerlegt den Knoten in konstante und veränderliche Teile. Die Suche ist sauberer mit dieser Lösung (Sie können logarithmische Zeit suchen, indem Sie einen falschen Knoten als Schlüssel für set::find konstruieren, aber es ist immer noch ein wenig unelegant), und die Objektidentität ist mit der anderen Lösung etwas sauberer.

    
Useless 29.01.2016 10:49
quelle