Jak to naprawić?

Question

Mam problem z poprawnością const, którego nie potrafię rozwiązać. Oto struktura mojego programu:

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); 

     (...) 
}; 

Teraz rzeczą jest, jeśli wywołanie funkcji Graph::get_node_by_id() chcę zwracają wskaźnik do danego węzła (typ Node). Ale wydaje się to niemożliwe, ponieważ std::set niejawnie konwertuje obiekty typu węzła na obiekty const Node i nie mogę pobrać obiektu non-const pointer z obiektu const.

Jednakże, nie można mieć wszystkiego innego zestawu do const Node (która rozwiąże ten problem), bo chcę zadzwonić Node::add_neighbour() z Graph::add_edge(), ale gdy robię tak, mój kompilator mówi, że może być naruszenie const Ness (wymagane mieć posortowany zestaw) elementów w zestawie node_list, mimo że zdefiniowałem less operator<, aby dbać tylko o id.

Czy jest coś, co mogę zrobić, aby rozwiązać ten dylemat (bez rezygnacji z sortowania)? Dziękuję za odpowiedzi!

Więcej informacji na temat błędu:

Jeśli używam non-stałych pól, błąd w 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; 

Jeśli używam stałych pól, błąd w 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

Wygląda na to, że masz dwie różne semantyki wartości do Node.

Jednym z nich jest to naświetlone przez operator<, na które nie ma wpływu add_neighbour. Jest to jedna z tych potrzeb, aby zachować porządek i którą wymusza, tworząc Nodeconst.

Druga metoda jest ujawniona przez interfejs API klasy, w którym zarówno wartości set_id, jak i add_neighbour zmienią wartość.

Aby zachować posortowane set, nie wolno zezwalać na zmianę identyfikatora węzła, gdy jest on w zestawie. Ale możesz może pozwolić sąsiadom się zmienić.

Więc ja proponuję zrobić neighbourssetmutable, upewnij add_neighbourprivate i const i dokonać Graphfriend z Node.

To, co daje mutable, elementy danych, które nie są częścią "wartości" typu. Zauważ, że oznacza to, że wskazujesz, że coś trzymającego const Node* może oczekiwać, że wynik is_neighbour zmieni się między połączeniami.

Więc ...

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); 

     (...) 
}; 

Teraz co masz jest publiczna, non-const mutatorów dla Node przypadkach, które nie są w Graph „s set oraz dodatkowe modyfikujące dla Graph użyć, aby zmienić sąsiadów Node s w jego set .

Więc tylko Graph może zrobić

const Node b; 
b.add_neighbour(nullptr); 

Jeśli naprawdę nie ufa Graph, można wymienić privateconstadd_neighbour z wewnętrznym class, z metody static add_neighbour(Node* node, Node* neighbour, ponieważ wewnętrzna class jest w stanie w sposób dorozumiany uzyskać dostęp do prywatnych danych klasy zewnętrznej.

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

Teraz tylko Graph może zrobić

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

W obu przypadkach, następujące prace dla wszystkich:

Node a; 
a.add_neighbour(nullptr); 

---

W tym momencie należy cierpienie Code zapach ... Problemem jest metoda publicget_node_by_id na wykresie. Prawdopodobnie chcesz zamiast tego odsłonić iterator, a nie surową Node* i uczynić Node prywatną wewnętrzną klasą wykresu.

lub nawet tylko wymienić cały Node pojęcia z std::map<int,std::set<int>> ...

Ale to zależy od rzeczywistego przypadku użycia.

Answer 2

Chociaż analiza TBBle jest prawidłowa, istnieje znacznie prostsze rozwiązanie: zastąpienie wykresu std::set<Node> przez std::map<int,Node>.

Twój bieżący Graph::get_node_by_id() używa wyszukiwania liniowego, ponieważ set tak naprawdę nie zapewnia poszukiwań, które chcesz. Utworzenie klucza zewnętrznego umożliwia usunięcie przeciążenia operator<, a mimo to uzyskanie szybszego i bardziej naturalnego wyszukiwania: map.find(id).

Jedyną brzydką częścią jest to, że teraz twój Node ma wewnętrzny identyfikator, który musi być zgodny z kluczem zewnętrznym. Jeśli nigdy nie użyjesz identyfikatora, z wyjątkiem wyszukiwania węzła na mapie, możesz go całkowicie usunąć. Jeśli trzeba wykonać krawędzie wykresu (sąsiadów), a następnie sprawdzić identyfikator, można wymienić zestaw wskaźników z zestawem map iteratorów, jak:

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

Wtedy twój przejścia ma pair<const int,Node> dostępny.

---

NB. po odbiciu zmiana z zestawu na mapę daje prawie takie samo rozróżnienie, jak odpowiedź TBBle: podzielisz węzeł na części stałe i zmienne. Wyszukiwanie jest czystsze dzięki temu rozwiązaniu (możesz odzyskać logarytmiczno-czasowe wyszukiwanie poprzez skonstruowanie fałszywego węzła jako klucza dla set::find, ale wciąż jest trochę nieelegancki), a tożsamość obiektu jest nieco czystsza w przypadku innego rozwiązania.