c++ - 用 unordered_map 制作树

Question

我想使用 Node 类作为 unordered_map 中的值，但是当我尝试编译时，我遇到了与Using unordered_map with custom value object in C++相同的问题 在上述问题的回答中，只提到了如何使用指向Node的指针。

有趣的是map<Key,Node>编译没有错误。但我不想使用 map因为map使用时间复杂度为 O(log(n)) 的红黑树，另一方面，unordered_map似乎需要恒定的时间。

下面是 Node 类和相关结构。

struct Bundle{
    double prob;
    vector<int> type;
};

typedef struct Bundle Bundle;
class Node {
    public:
        unordered_map<unsigned, Bundle> bundle;
        unordered_map<unsigned, Node> childs;
    private:
        //private method here
};

Answer 1

class Node {
    public:
        unordered_map<unsigned, Bundle> bundle;
        unordered_map<unsigned, Node> childs;

此时 Node类型尚未完成，因为您仍在定义它。

用不完整的类型实例化大多数标准库模板(例如 unordered_map)是未定义的行为。它可能适用于某些编译器，但也可能不适用。原因是模板可能需要知道类似 sizeof(Node) 的信息。以及是否Node不可抛出复制构造，并且对于不完整的类型，它无法知道这些事情。

我猜您正在使用 GCC，它支持 std::map 中的不完整类型(作为非标准扩展名)但不是 std::unordered_map .您的选择是使用不同的容器，或使用不同类型的容器(例如 unordered_map<unsigned, unique_ptr<Node>> )