c++ - set 元素的 const 引用不保留信息

Question

我有两个 friend 类:

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

我正在尝试创建一个可以首先在图中找到特定节点的函数 vertices_ ，说节点 v .然后我想更改 marked_ v 邻居的属性(property).寻找v , 我必须使用 std::find()方法。但是，此方法的返回迭代器不允许我更改邻居的成员变量。这是我尝试过的:

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

注意这里我必须使用const std::set<Node> & neighbors因为我想就地换邻居。但我无法更改 v 的邻居通过 const 迭代器 it ，所以这个方法是行不通的。我有办法更改 vertices_通过删除并通过迭代器复制回来，这不是问题。但是这里不一样，我是对顶点的元素进行操作，这是另外一个集合。有什么建议吗？

更新

根据@walnut 的建议，我刚刚更改了marked_可变，现在我可以编写以下代码

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

但是，这并没有解决问题，因为nbr在上面的代码中现在失去了它自己的信息 neighbors ，我仍然不能用它来遍历图形。

这太奇怪了因为nbr是原始图节点的引用？例如，我什至不能用它来打印我的图表!

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

上面的代码也不起作用，因为引用 node不保留它引用的对象的邻居信息。

Answer 1

walnut@ 在评论中链接了一些很棒的建议。其中，在您的特定情况下，我更喜欢使用 map 而不是 set ，因为映射键对应于节点之间的显式弧。下面的片段显示了这在您的示例中的样子(我将您的遍历代码放入 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);
  }
}

正如您在上面看到的，当您需要 id 时，您可以选择使用 it->second.id() 或 it->first，因为它们会两者具有相同的值。