c++ - 在有向邻接表图中存储不同大小的边

Question

假设我有以下设置:

class Vertex;

class Edge {
    Vertex *to;
};

class Teleport : public Edge {
    int teleportCost;
};

class Walk : public Edge {
    double distance;
};

class Vertex {
    vector<Edge> adjacencies; // can only store Edge and not Walk, Teleport etc!
};

问题当然是Vertex可以有许多不同类型的邻接，每一个都有不同的字节大小。那么，存储边缘的最佳方式是什么？我的图表永远不会删除顶点或边；一旦它完全建成，它就会保留在内存中，直到它被立即摧毁。也许这将允许在大内存池或足够大的内存池中“全局”存储字节 vector , 然后每个 Vertex有一个 vector<void*>或 vector<Edge*>或者指向内存缓冲区的东西。但是，我不确定该怎么做。任何人都可以帮助提供一些指导，说明在我的场景中什么可能最适合用作存储？

全部Edge s 将被多态使用，所以我永远不需要转换为 Teleport等等。

Answer 1

当一个类型要被子类型化时，这种类型的 vector 或对象数组几乎总是错误的。您需要存储一个 vector 或指针数组。

代替:

vector<Edge> adjacencies;

使用

vector<std::share_ptr<Edge>> adjacencies;