C++ 循环依赖与邻接表表示的混淆

Question

抱歉我对 C++ 缺乏经验，但我花了一些时间解决循环依赖问题，因此提出了这个问题。

我正在尝试用 C++ 表示邻接表。

我有结构 Node,

struct Node{

    int data;
    unordered_set<Node, Hash> links;

    bool operator == (Node const& other) const{
        return (data == other.data);
    }

    Node(){
    }

    Node(int data){
        this->data = data;
    }
};

我有我的 Hash 函子

struct Hash {
    size_t operator()(const Node &node) const {
        return node.data;
    };
};

我注意到 Hash 使用 Node 而 Node 使用 Hash
如果出于本练习的目的，我想在一个文件中声明所有内容，我应该先声明哪个文件。

我尝试过先定义 Hash 和 Node 中的任何一个，但编译了其中的 none。

PS: 这不是作业，我正在尝试在线解决图算法难题

Answer 1

延迟定义 Hash::operator() 直到定义 Node 并在 Hash 之前声明 Node。您可以引用不完整的类型，只要您不对其进行任何操作即可。

class Node;

class Hash{
    public:
        size_t operator()(const Node &node) const;
};

class Node{
    public:
        int data;
        unordered_set<Node, Hash> links;
};

inline size_t Hash::operator()(const Node &node) const{
    return node.data;
}

Answer 2

在完全定义 Node 之后通过将散列的实现移动到某个点来解析语法是不够的。无论顺序是什么，您都无法编译它，因为 Node 的 unordered_set 期望 Node 是 完整类型 ，即需要完全定义类型。

除了拆分出Hash::operator()的定义还需要把unordered_set的第一个类型参数改成指针，最好是智能指针：

unordered_set<shared_ptr<Node>, Hash> links;
...
size_t Hash::operator()(const shared_ptr<Node> &node) const{
    return node->data;
}

常规指针也可以，但是您必须单独管理节点的内存 - 例如通过将所有节点放在一个向量中。

C++ 循环依赖与邻接表表示的混淆

C++ cyclic dependency confusion with adjacency list representation

c++

adjacency-list

cyclic-reference