c++ - map<A, set<A*>> 与 set<A> 其中 A 包含 A* 的集合

Question

我想用 C++ 表示一个图。

我正在解析我的输入数据，这些数据是 (1) 节点和 (2) 节点之间的连接。

我的问题是关于保存节点和连接的数据结构:

我的第一种方法是我从 C 中了解到的一种链表，但使用的是 STL 容器: class A持有节点的名称和一个 std::set<A*>存储指向连接节点的指针。 像这样的东西(不可编译，只是想法的草稿):

class A
{
    private:
        std::string name;
        std::set<A*> links;

    public:
        // constr., destr., getter, setter, ...
};

我的第二个想法是 std::map<A, std::set<A*> >甚至 std::map<A, std::vector<A*> >在我看来，在这种情况下这是更好的方法。

当然是 class A在这种情况下将只包含名称:

class A
{
    private:
        std::string name;

    public:
        // constr., destr., getter, setter, ...
};

我的图表用数据填充一次，初始化后不会应用删除/插入/更新操作。

如果有更好的数据结构方法我没有提到，欢迎赐教:)

Answer 1

这种方法看起来更经济:

class A
{
    std::string name;
    std::vector<A*> links;
}

原因:

1. map< A, vector > 必须保存 A 的拷贝(作为键)，因此会增加内存需求，尤其是当名称很长且具有描述性时。

2. 在遍历节点时，您在任何给定时间都知道当前 A，并且可以直接访问链接集/vector ；使用 map ，您必须查找链接的集合/vector ，这会浪费时间。