0

好的，所以我正在创建一个 Graph 类，我希望能够在今年夏天晚些时候有空闲时间的时候运行算法并添加一个 gui。现在我有一个 adjList，它被实现为一个向量数组（每个顶点一个），每个向量都是一个指针列表，表示从每个相关顶点到其他顶点的边。它被声明为我的 Graph 类的受保护成员，如下所示：

std::vector <Node*> *adjList;
adjList = new std::vector<Node*>[V];

我有一个附带问题。现在在这里我有一个包含指针的向量数组（通过指针）。相反，如果这不是一个数组，而是一个指向单个节点指针向量的指针，那么我可以像这样调用构造函数：

adjList = new std::vector<Node*>(10);

这将允许我为向量中的动态数组指定默认大小，但似乎我无法调用构造函数，或者至少在我有数组时无法正确获取语法。

现在是我主要关心的问题。对于指针数组中的每个向量，我在 addVertex 方法中调用 new 运算符，为每个向量添加多个节点指针。现在我需要确保我正确处理所有这些的释放。我相信我对这在 C++ 中应该如何工作有所了解，但我知道指针很棘手，所以在我继续向这个代码库添加大量内容之前，我想找人看看。通过几次搜索，我找不到任何与我所拥有的非常相似的东西。这是我的释放：

for(int i =0; i < V; i++)
    for (unsigned int j = 0; j < adjList[i].size(); j++)
        delete adjList[i][j];
delete adjList;

这会释放所有内存吗？还有一种简单的方法可以让我确定这一点，例如。在调试时计算使用 new 分配了多少内存？

[编辑：更新/更多信息]

这是一个指向 Google Books 的链接，显示了我想要在伪代码中实现的算法之一。此版本的广度优先搜索在邻接列表（指针列表数组）上运行。由于使用邻接列表分配给每个节点的属性，因此必须使用指针。

我想在运行后将这些属性从存储到每个节点的 BFS 算法中保留下来。我知道可以通过其他方式做到这一点，也许是索引节点和使用并行数组来存储属性。但我希望拥有与此伪代码类似的代码（用于链接中的 BFS）。

4

2 回答 2

2
  1. 为什么要使用向量数组？
  2. 为什么要维护指向向量的指针？
  3. 你为什么要维护一个指针向量？

所有这三个决定都会使您付出代价，并直接否定向量类的内存管理能力。向量不仅仅是一个可以在幕后增长的数组，它还通过称为RAII的模式为您管理内存。

当您创建一个指针向量时，该向量无法清理指针在销毁时引用的内存，因此您仍然需要调用delete该向量的每个元素。

当您创建指向向量的指针时，您无法利用向量释放在其析构函数中分配的任何内存这一事实。因此，您再次否定了向量为您管理内存的能力，因为您必须调用delete向量以防止内存泄漏。

当你维护一个向量数组时......好吧，你已经在使用向量了，为什么不直接使用 avector<vector<T>>呢？

矢量类型在幕后为您动态分配内存，专门用于避免您现在遇到的那种问题。当然，您可以管理自己的内存（您只需按照与分配相反的顺序解除分配，您似乎掌握了这一点），但是当有适当的机制为您执行此操作时，为什么还要麻烦呢？

我不明白这里的设计目标。为什么不简单地使用 avector<vector<Edge>>并完全摆脱这些问题呢？

class Edge {
    // whatever
}

class Graph {
private:
    // when instances of this class go out of scope, 
    // all of the memory allocated to these vectors is deallocated for you!
    vector<vector<Edge>> vertices;  
}
于 2012-05-02T04:54:35.560 回答
0

如果您正在构建一个通过指针对内部对象进行大量索引的类，那么确保仅在内存位置删除一次对象的一种方法是保留一个内存池。例如，您可以拥有一个std::vector<Node*> Graph::memPool成员。删除 . 时Graph，只需删除其中的所有内容，Graph::memPool而不是单个节点的adjList. 每当创建新节点时，只需将其添加到内存池即可。

在您当前的示例中，如果两个节点与同一个节点有一条边，您可能会删除一个无效的内存位置。

另一种选择是使用编号索引而不是指针。该图有一个节点的主向量，而每个节点中的邻接表保持向量索引。

class Graph
{
    std::vector<Node> all_nodes;
    ...
};

struct Node
{
    std::vector<size_t> adjList;
    SomeDataType nodeData;//e.g. node cost, weight, reward, etc
    ...
};

在这种情况下，不需要显式的 delocation。与使用指针类似，从图中删除节点将需要扫描邻接列表以更新索引。

于 2012-05-02T05:20:22.323 回答