CODEWITHSUNDEEP
c++vectorsegmentation-faultpush-back
a k
a k

Reputation: 561

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

Want to construct a Graph with adjacency list, but getting seg-fault when I add elements to vector<vector<int>>. adj.size() prints 5 which tells it has allocated memory, why the seg-fault in addEdge() method?

 #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;
    }

Upvotes: 0

Views: 249

Answers (2)

Peter
Peter

Reputation: 36597

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

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

is incorrect. The operator[]() for a vector ASSUMES the supplied index is valid. If u is not valid, the behaviour is undefined.

In your code, the vector passed has five elements, and the last edge in main()

vector<Edge> edges =

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

will cause addEdge() to be called with u having a value of 5. That is one past the end.

While #define V 6 will fix the problem, it doesn't protect addEdge() from being passed a bad value of u. Instead I would implement addEdge() so it protects itself from bad data as follows.

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);
}

An even better approach would be to avoid using supplied data - such as the data in edges in your main() - as array indices at all.

Upvotes: 3

a k
a k

Reputation: 561

Solved. Thanks for the guidance provided here, read up more on this and learnt that c++ language has protection built into it for these kinds of issues. Using .at() method protects the programmer from out-ob-bounds accesses.

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

if you use adj.at(u) instead of adj[u], program exits little gracefully

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)

Upvotes: 0

Related Questions