Come avere questa correzione corretta?

Question

Ho un problema di const-correctness che non riesco a risolvere. Ecco la struttura del mio programma:

class Node 
{ 
    private: 
     int   id; 
     std::set<Node*> neighbours; 
    public: 
     Node(); 
     Node(int id_p); 

     void set_id(const int& id_p); 
     int get_id() const; 
     void add_neighbour(Node* neighbour); 
     bool is_neighbour(Node* neighbour) const; 

     friend bool operator <(const Node& lhs, const Node& rhs); 
}; 

class Graph 
{ 
    private: 
     std::set<Node> node_list; 
    public: 
     Graph(); 

     void  add_node(int id); 
     const Node* get_node_by_id(int id) const; 
     bool  has_node(int id) const; 
     void  check_add_node(int id); 
     void  add_edge(int id_1, int id_2); 
     bool  has_edge(int id_1, int id_2) const; 
     void  check_add_edge(int id_1, int id_2); 

     (...) 
}; 

Ora la cosa è, se chiamo la funzione Graph::get_node_by_id(), voglio restituire un puntatore ad un dato nodo (tipo Node). Ma sembra impossibile, perché std::set converte implicitamente gli oggetti di tipo Node in oggetti const Node e non riesco a recuperare uno non-const pointer da un oggetto const.

Tuttavia, non posso avere tutto il resto insieme a const Node (che sarebbe risolvere il problema), perché voglio chiamare Node::add_neighbour() da Graph::add_edge(), ma ogni volta che lo faccio, il mio compilatore dice che potrei essere violare la const ness (richiesto per avere un insieme ordinato) degli elementi nel set node_list, anche se ho definito lo less operator< per preoccuparmi solo dello id.

C'è qualcosa che posso fare per risolvere questo dilemma (senza rinunciare ad avere un set ordinato)? Grazie per le tue risposte!

Maggiori informazioni sull'errore:

Se uso i campi non costanti, di errore in Graph::get_node_by_id():

for(Node& element : this->node_list) // Error: element should be const Node& 
{ 
    if(element->get_id() == id) 
    { 
     return element; 
    } 
} 
return nullptr; 

Se uso i campi costanti, di errore in Graph::add_edge():

(...) 
const Node* node_1 = this->get_node_by_id(id_1); 
const Node* node_2 = this->get_node_by_id(id_2); 
node_1->add_neighbour(node_2); // Error for disregarding constness 
node_2->add_neighbour(node_1); 

Answer 1

Sembra che il tuo problema sia che hai due "semantica del valore" diverse a Node.

Uno è quello esposto da operator< che non è interessato da add_neighbour. Questo è il tipo di esigenza di set, per mantenere le cose ordinate e quali impone rendendo Nodeconst.

L'altro è quello esposto dalla classe API, dove sia set_id che add_neighbour cambierebbero il valore.

Per mantenere ordinato il numero set, non è consentito modificare l'ID di un nodo una volta entrato nel set. Ma tu puoi consentire ai vicini di cambiare.

quindi consiglio a fare la neighbourssetmutable, fanno add_neighbourprivate e const, e fare un Graphfriend di Node.

Questo è ciò che fornisce mutable membri dati che non fanno parte del "valore" di un tipo. Tieni presente che ciò significa che stai indicando che qualcosa che detiene uno const Node* potrebbe aspettarsi che il risultato di is_neighbour cambi tra le chiamate.

Quindi ...

class Node 
{ 
    private: 
     // Trust Graph not to mess directly with these! 
     int   id; 
     mutable std::set<Node*> neighbours; 

     friend class Graph; 
     // For Graph's exclusive use 
     void add_neighbour(Node* neighbour) const; 


    public: 
     Node(); 
     Node(int id_p); 

     void set_id(const int& id_p); // Callable when not in Graph's set 
     int get_id() const; 
     void add_neighbour(Node* neighbour); // Callable when not in Graph's set 
     bool is_neighbour(Node* neighbour) const; 

     friend bool operator <(const Node& lhs, const Node& rhs); 
}; 

class Graph 
{ 
    private: 
     std::set<Node> node_list; 
    public: 
     Graph(); 

     void  add_node(int id); 
     const Node* get_node_by_id(int id) const; 
     bool  has_node(int id) const; 
     void  check_add_node(int id); 
     void  add_edge(int id_1, int id_2); 
     bool  has_edge(int id_1, int id_2) const; 
     void  check_add_edge(int id_1, int id_2); 

     (...) 
}; 

Ora quello che hai è, mutatori pubbliche non const per Node istanze che non sono in Graph s' set, e un mutatore in più per Graph da utilizzare per cambiare i vicini dei Node s nella sua set .

Quindi solo Graph può fare

const Node b; 
b.add_neighbour(nullptr); 

Se davvero non ti fidi Graph, è possibile sostituire il privateconstadd_neighbour con un interno class, con un metodo static add_neighbour(Node* node, Node* neighbour, dal momento che un interno class è implicitamente in grado di accedere ai dati privati ​​della classe esterna.

class NeighbourHelper { 
    friend class Graph; 
    static void add(const Node* node, Node* neighbour) { 
     node->add_neighbour(neighbour); 
    } 

Ora solo Graph può fare

const Node b; 
Node::NeighbourHelper::add(&b, nullptr); 

In entrambi i casi, i seguenti lavori per tutti:

Node a; 
a.add_neighbour(nullptr); 

---

A questo punto, si dovrebbe essere affetti un code- annusare ... Il problema è il metodo publicget_node_by_id in Graph. In realtà probabilmente vuoi esporre un iteratore di qualche tipo invece che il grezzo e rendere Node una classe interna privata di Graph.

O anche solo sostituire l'intero Node concetto con std::map<int,std::set<int>> ...

Ma dipende dal vostro caso applicativo concreto.

Answer 2

Sebbene l'analisi di TBBle sia corretta, c'è una soluzione molto più semplice: sostituire Graph std::set<Node> con std::map<int,Node>.

L'attuale Graph::get_node_by_id() utilizza una ricerca lineare poiché set non fornisce realmente la ricerca desiderata. Rendere la chiave esterna consente di rimuovere il sovraccarico di operator< e ottenere comunque una ricerca più rapida e naturale: map.find(id).

L'unica parte brutta è che ora il tuo Node ha un ID interno che deve corrispondere a una chiave esterna. Se non usi mai l'id tranne per cercare un nodo nella mappa, puoi semplicemente rimuoverlo completamente. Se è necessario seguire i bordi del grafico (vicini) e quindi controllare l'ID, è possibile sostituire il set di puntatori con una serie di mappa iteratori, come:

typedef std::map<int, Node> NodeMap; 
typedef std::set<NodeMap::iterator> NeighbourMap; 

Allora la vostra traversata ha la pair<const int,Node> disponibili.

---

NB. Riflettendoci, il passaggio dalla serie alla mappa produce quasi la stessa distinzione della risposta di TBBle: dividi il nodo in parti const e mutabili. La ricerca è più pulita con questa soluzione (è possibile riottenere la ricerca logaritmica in tempo costruendo un nodo falso come chiave per set::find, ma è ancora un po 'poco elegante) e l'identità dell'oggetto è leggermente più pulita con l'altra soluzione.