c++ - 我的 vector vector 有什么问题？

Question

class Graph {


public:

    std::vector<std::vector<int>> adj;

    Graph(int V) {
        std::vector<std::vector<int> > adj(V, std::vector<int>());
    }

    void insert_edge(int v, int u);
    void print_adjacencylist();


};


void Graph::insert_edge(int v, int u) {

adj[v].push_back(u);


}

我在打电话

Graph G(8);

G.insert_edge(4, 1);

我得到一个错误:

调试断言失败!表达式: vector 下标超出范围

我正在尝试创建一个有 V 个顶点的图。我正在使用 vector 的 vector 来表示图形(作为邻接列表)。我图中的节点从 0 到 V-1 编号，因此 adj vector 的索引代表节点的编号。除非我弄错了，否则 adj[u] 表示一个 vector ，所以我应该能够使用 adj[u].push_back(v) 将顶点 v 插入顶点 u 的邻接列表中。所以在我的示例中，adj[4] 应该得到与节点 4 相邻的顶点所在的 vector ，并且 .push_back(1)

这不会发生。我认为这与我没有正确初始化所有内容有关，但我已经尝试了一百万件事(甚至尝试使用 for 循环将 vector push_back 到 adj vector 的每个索引)并且我只是不断收到同样的错误。

Answer 1

您的数据成员 vector 为空，您正在越界访问它。这样做的原因是您默认在构造函数中初始化了它。您还初始化了一个不会在任何地方使用的局部变量:

Graph(int V) {
  // Oops! Local variable adj, nothing to do with member
  // of same name
  std::vector<std::vector<int> > adj(V, std::vector<int>());
}

您打算做的是初始化数据成员adj，您可以在构造函数初始化列表中执行此操作

Graph(int V) : adj(V, std::vector<int>()) {}

或者，用更少的输入，

Graph(int V) : adj(V) {}

请注意，可以通过在一些流行的编译器上使用合适的标志来避免这个问题。例如，在 clang 或 gcc 上使用 -Wshadow 标志会产生如下警告:

warning: declaration shadows a field of 'Graph' [-Wshadow]
std::vector > adj(V, std::vector());