为什么 push_back 进入 vector<vector<int>> 导致段错误？

Question

想要构建一个带有邻接表的图，但是当我向 vector<vector<int>> 添加元素时出现段错误。 adj.size() 打印 5 告诉它已分配内存，为什么 addEdge() 方法中出现段错误？

 #define V 5

    struct Edge {
        int src, dst;
    };

    void addEdge(vector<vector<int>> &adj, int u, int v)
    {
        adj[u].push_back(v);
    }

    void constructGraph(vector<vector<int>> &adj, vector<Edge> &edges)
    {

        for(Edge e : edges)
        {
            addEdge(adj, e.src, e.dst);
        }
    }

    int main()
    {
       vector<vector<int>> adj(V);

       vector<Edge> edges =
        {
            { 0, 1 }, { 1, 2 }, { 2, 0 }, { 2, 1 },
            { 3, 2 }, { 4, 5 }, { 5, 4 }
        };

        constructGraph(adj, edges);

       return 0;
    }

Answer 1

void addEdge(vector<vector<int>> &adj, int u, int v)

{
    adj[u].push_back(v);
}

不正确。向量的 operator[]() 假定提供的索引有效。如果 u 无效，则行为未定义。

在您的代码中，传递的向量有五个元素，main()

中的最后一条边

vector<Edge> edges =

    {
        { 0, 1 }, { 1, 2 }, { 2, 0 }, { 2, 1 },
        { 3, 2 }, { 4, 5 }, { 5, 4 }               // note the last pair here
    };

将导致 addEdge() 被调用时 u 的值为 5。那是一个过去了。

虽然 #define V 6 可以解决问题，但它不能防止 addEdge() 被传递错误的值 u。相反，我会实现 addEdge()，这样它就可以保护自己免受错误数据的影响，如下所示。

void addEdge(vector<vector<int>> &adj, int u, int v)
{
    if (u < 0) return;                   // handle negative u
    if (u >= adj.size()) adj.resize(u+1);  //   resize if needed
    adj[u].push_back(v);
}

更好的方法是完全避免使用提供的数据——例如 main() 中 edges 中的数据——作为数组索引。

Answer 2

已解决。感谢此处提供的指导，阅读更多相关内容，了解到 C++ 语言内置了针对此类问题的保护。使用 .at() 方法保护程序员免受越界访问。

void addEdge(vector<vector<int>> &adj, int u, int v)
{
    adj.at(u).push_back(v);
}

如果您使用 adj.at(u) 而不是 adj[u]，程序会稍微优雅地退出

terminate called after throwing an instance of 'std::out_of_range'
  what():  vector::_M_range_check: __n (which is 5) >= this->size() (which is 5)
Aborted (core dumped)

为什么 push_back 进入 vector<vector<int>> 导致段错误？

Why does push_back into vector<vector<int>> causing seg fault?

c++

vector

segmentation-fault

push-back