const references of set elements do not preserve information

Question

I have two friend classes:

class Node {
private:
    unsigned id_;
    bool marked_;
    std::set<Node> neighbors_;

    friend class Graph;
    ......

public:
bool operator == (const Node & other) const { return id_ == other.id(); }
bool operator < (const Node & other) const { return id_ < other.id(); }
......
};

class Graph {
private:
    std::set<Node> vertices_{};
    void reach_set_helper(unsigned id, std::vector<unsigned> &reach_set);
    ......
};

I am trying to create a function that can first find a specific node in the graph vertices_, say node v. And then I want to change the marked_ property of the neighbors of v. To find v, I have to use std::find() method. However, the return iterator of this method does not allow me to change member variables of neighbors. This is what I have tried:

Node & s = v;
std::set<Node>::iterator pos = vertices_.find(s);
const std::set<Node> & neighbors = (pos->neighbors_);
for (std::set<Node>::iterator it = neighbors.begin(); it != neighbors.end(); it++) {
    if (!it->is_marked()) {
        reach_set.push_back(it->id());
        it->set_marked(true);
        this->reach_set_helper(it->id(), reach_set);
    }
}

Notice here that I have to use const std::set<Node> & neighbors because I want to change neighbors in place. But I can't change neighbors of v through const iterator it, so this method does not work. I have a way to make changes to vertices_ by erase and copy back through iterator, that's not a problem. But here it is different, I am doing operations on elements of vertices, which is another set. Any suggestions?

UPDATE

Following suggestions by @walnut, I just changed marked_ to mutable, and now I'm able to write the following code

std::set<Node>::iterator pos = vertices_.find(s);
const std::set<Node> & neighbors = (pos->neighbors_);
for (const Node & nbr : neighbors) {
    if (!nbr.is_marked()) {
        reach_set.push_back(nbr.id());
        Stack.push(nbr);
        nbr.marked_ = true;
    }
}

However, this does not solve the problem, as nbr in the above code now lose the information of its own neighbors, I still can not use this to traverse the graph.

This is so weird because nbr is a reference of the original graph node? For example, I cannot even use this to print out my graph!

void MtxGraph::print_graph() const {
    const Node & start = *vertices_.begin();
    print_graph_helper(start);
}

void MtxGraph::print_graph_helper(const Node & v) const {
    std::set<Node> neighbors = v.neighbors_;
    for (const Node & node : neighbors) {
        std::cout << v.id() << " => " << node.id() << " => ";
        print_graph_helper(node);
        std::cout << std::endl;
    }
}

The above code also doesn't work because the reference node doesn't preserve neighbors information of the object it refers to.

I am using `std::set`. My `operator==` is defined by their `id` number. If `id` are the same, then they are equal. Oh I don't have C++ 17 available, it seems too fancy for me right now. Just wondering if there is a way to get around this in the current version. — user123, Jan 01 '20 at 05:09
Thanks @walnut, `operator<` is also define using their `id`, smaller `id` has smaller value. — user123, Jan 01 '20 at 05:13
In that case, does this answer your question? (`std::set` and `std::map` behave the same way) [Modify key of std::map](https://stackoverflow.com/questions/51785099/modify-key-of-stdmap) or [How to update an existing element of std::set?](https://stackoverflow.com/questions/7340434/how-to-update-an-existing-element-of-stdset) or [C++ std::set update is tedious: I can't change an element in place](https://stackoverflow.com/questions/2217878/c-stdset-update-is-tedious-i-cant-change-an-element-in-place). Also see https://stackoverflow.com/questions/6068167 — walnut, Jan 01 '20 at 05:17
Are you suggesting to change `Node` from `std::set` to `std::map`? If so, how am I going to have `marked` property in the Node? — user123, Jan 01 '20 at 05:23
Not necessarily. I am suggesting either one of the methods used in the linked questions' answers (they apply to `std::set` and `std::map` in the same manner): Either make `marked_` `mutable` *or* remove/modify/insert the `Node` *or* separate the class into key-relevant and key-unrelated state in a `std::map` *or* (in C++17) use `.extract`. — walnut, Jan 01 '20 at 05:25
I've seen that method for `std::set` in the link, they use erase and copy back, which helped me in the other function but is not applicable in this case though — user123, Jan 01 '20 at 05:28
Making `marked_` `mutable` is the simplest solution to your problem, given that `marked_` does not participate in the key comparator (i.e. `operator<`). — walnut, Jan 01 '20 at 05:30
Yes I saw these links! But `mutable` seems like a great solution, let me try that out!! Thanks a lot!! — user123, Jan 01 '20 at 05:33
Also read the answers [here](https://stackoverflow.com/questions/52285161/using-mutable-to-allow-modification-of-object-in-unordered-set) for concerns about the `mutable` approach. (Question is about `std::unordered_set`, but applies analogously for `std::set`.) — walnut, Jan 01 '20 at 05:38
Thank you @walnut, you saved my night! You can post your comments below and I'll take it as an answer. Your method is different from everyone else's. — user123, Jan 01 '20 at 05:44
You should be able to accept my duplicate suggestion. I did intentionally not write an answer, because there are sufficient answers in the linked questions. The `mutable` method is mentioned in all of them. — walnut, Jan 01 '20 at 05:47
Hi @walnut, it still seems to have some problems, could you please be so nice to have another look at my update? Thank you so much! — user123, Jan 01 '20 at 08:55
I don't really see from the snippets what exactly is wrong with your code now. You need to provide a [repro] and the output it generates. You have a complete working example using the `std::map` approach in the answer section. This is certainly the cleaner implementation. — walnut, Jan 01 '20 at 12:21

Derek T. Jones · Answer 1 · 2020-01-04T17:51:46.293

walnut@ linked some great suggestions in the comments. Of them, I would prefer the use of map over set in your particular case, because the map key corresponds to an explicit arc between nodes. The below fragment shows how this would look in your example (I put your traversal code into Graph::f):

#include <set>
#include <map>

class Node {
private:
    unsigned id_;
    bool marked_;
    std::map<unsigned, Node> neighbors_;

    bool is_marked() const;
    void set_marked(bool val);
    unsigned id() const { return id_; }

    friend class Graph;
public:
    bool operator== (const Node& other) const { return id_ == other.id_; }
    bool operator< (const Node& other) const { return id_ < other.id_; }
};


class Graph {
private:
    std::map<unsigned, Node> vertices_;
    void reach_set_helper(unsigned id, std::vector<unsigned> &reach_set);
    void f(Node& s);
};

void Graph::f(Node& s)
{
  auto neighbors = vertices_.find(s.id())->second.neighbors_;
  for (auto it = neighbors.begin(); it != neighbors.end(); ++it) {
    if (!it->second.is_marked()) {
        reach_set.push_back(it->first);
        it->second.set_marked(true);
    }
    this->reach_set_helper(it->first, reach_set);
  }
}

As you can see above, you can choose to use it->second.id() or it->first when you need the id, since they will both have the same value.

const references of set elements do not preserve information

1 Answers1