c++ - 使用 unordered_map 实现图表示的邻接表

Question

我想使用 unordered_map 实现图的邻接表。选择 unordered_map 是因为它可以给我 O(1) 时间来访问给定顶点的相邻顶点。所以我的想法是定义 unordered_map 如下:

using namespace std;

class node {};
class edge {};  
typedef vector<edge*> edges_t;
typedef unordered_map<node*, edges_t*> graph_t;

我使用 node 类的指针作为 unordered_map 的键，因为直接使用 node 对象需要定制的 std::hash 实现。使用指针的主要问题是内存管理。我需要显式释放分配的内存。

这里可以使用 unique_ptr 来简化内存管理吗？或任何更好的建议解决方案？

谢谢!

Answer 1

所有权政策确实是个问题，您有几种可能性:

• 如果存在明确的所有者，std::unique_ptr是最佳选择(参见 this example )
• 如果有多个可能的所有者，您可以打破对称性并引入一个或遵从 std::shared_ptr (注意循环)

打破对称性就像引入一个 std::deque<node> 一样简单它将包含节点并在该容器内获取指针。同样，一个 std::deque<edge>将解决边缘的所有权问题。