How to get this constant?

Question

I have a problem with const-correctness that I can't seem to solve. Here is the structure of my program:

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); (...) }; 

Now, if I call the function Graph::get_node_by_id() , I want to return a pointer to the given node (type Node ). But this cannot be done because std::set implicitly converts objects of type node to const Node objects, and I cannot extract non-const pointer from the const object.

However, I cannot set everything else to const Node (to solve the problem), because I want to call Node::add_neighbour() from Graph::add_edge() , but whenever I do this, my compiler says that I can violate const ness (you need to have a sorted set) of the elements in the node_list set, even if I defined a less operator< to only care about id .

Is there anything I can do to solve this dilemma (without giving up sorting)? Thank you for your responses!

Additional error information:

If I use inconsistent fields, the error 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; 

If I use constant fields, the error 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

Your problem is that you have two different “semantics of meanings” before Node .

One of them displays operator< , which is not affected by add_neighbour . This is one set need to streamline things and which it provides by making Node const .

Another is that the class API is displayed, where both set_id and add_neighbour will change the value.

To preserve the sorted set , you should not change the node identifier after setting it. But you can let the neighbors change.

So, I suggest you make the neighbours set mutable , make add_neighbour private and const and make Graph a friend from Node .

This is what mutable gives you, data members that are not part of the "value" of the type. Note that this means that you indicate that something containing const Node* can expect the result of is_neighbour change between calls.

So...

 class Node { private: // Trust Graph not to mess directly with these! int id; mutable std::set<Node*> neighbours; friend class Graph; // For Graph 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 set int get_id() const; void add_neighbour(Node* neighbour); // Callable when not in Graph 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); (...) }; 

You now have public, non-constant mutators for Node instances that are not in the Graph set , and an additional mutator for Graph used to change Node neighbors to set .

So only Graph can perform

 const Node b; b.add_neighbour(nullptr); 

If you really don't trust Graph , you can replace the private const add_neighbour with an inner class using the static add_neighbour(Node* node, Node* neighbour method static add_neighbour(Node* node, Node* neighbour , since the inner class implicit for accessing the personal data of the outer class.

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

Now only Graph can execute

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

In both cases, the following works for everyone:

 Node a; a.add_neighbour(nullptr); 

---

At this point, you should suffer from the smell of code ... The problem is the public get_node_by_id method in Graph. You will likely want to set some kind of iterator instead, not raw Node* and make Node private inner class of Graph.

Or just replace the whole Node concept with std::map<int,std::set<int>> ...

But it depends on your actual use.

Answer 2

Although TBBle analysis is correct, there is a much simpler solution: replace Graph std::set<Node> with std::map<int,Node> .

Your current Graph::get_node_by_id() uses a linear search because set does not actually provide the desired search. Creating a foreign key allows you to remove the operator< overload and get a faster and more natural search: map.find(id) .

The only ugly part is that now your Node has an internal identifier that must match the foreign key. If you never use an identifier other than looking for a node on a map, you can simply delete it completely. If you need to follow the graphs (neighbors) and then check the identifier, you can replace your set of pointers with a set of map iterators, for example:

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

Then your bypass has pair<const int,Node> .

---

NB. when reflected, changing from set to map gives almost the same difference as TBBle's answer: you break the node into const and mutable parts. Searching with this solution is cleaner (you can restore the logarithmic search of time by constructing a fake node as the key for set::find , but still a bit inelegant), and the object identifier is a little cleaner with another solution.