CODEWITHSUNDEEP
c++vector
John Lui
John Lui

Reputation: 1464

How can I check if a vector is pointing to null vector in a 2d-vector in c++?

So, I have the following case:

I declared a vector of vector of integers as vector < vector<int> > edges. Basically, I am trying to implement a graph using the above where graph is defined as follows: 

class graph
{
    public:
    int vertices;
    vector < vector<int> > edges;
};

Now, during the insertion of an edge, I take input as the starting vertex and ending vertex. Now, I want to do something like this: 

void insert(int a, int b, graph *mygraph) // a is starting vertex and b is ending vertex
{ 
    auto it = mygraph->edges.begin();
    //int v = 1;
    vector<int> foo;
    foo.push_back(b);
    if (mygraph->edges[a].size() != 0) // Question here?
        mygraph->edges[a].push_back(b);
    else
        mygraph->edges.push_back(foo);

    return;
}

Now, in the line marked with Question here, basically, I want to check if the vector for that particular entry exists or not? size is actually wrong because I am trying to call size operation on a vector which doesn't exists. In other words, I want to check, if there is a vector which exists at a particular location in vector of vectors. How can I do it? Something like, mygraph->edges[a] != NULL?

Upvotes: 0

Views: 362

Answers (3)

Blito
Blito

Reputation: 328

You can approach your problem in two different ways:

  1. Initialize edges to the number of vertices, and don't allow other vertices to be inserted after that. Why is that?

    std::vector< std::vector<int> > v = { {1}, {2} };
// now you need to add an edge between vertex 4 and vertex 5
std::vector<int> edges3;
v.push_back(edges3); // v = { {1}, {2}, {} }
std::vector<int> edges4 = {5};
v.push_back(edges4); // v = { {1}, {2}, {}, {5} }

    If you don't want to do it like that, you'd have to do something like this first:

    std::vector< std::vector<int> > v;
for (int i = 0; i < maxVertices; i++)
{
    std::vector<int> w;
    v.push_back(w);
}
// now you need to add an edge between vertex 4 and vertex 5
v[4].push_back(5);

  2. Change the structure used for edges, probably to something better suited for sparse matrices (which looks like your case here, since probably not every vertex is connected to every other vertex). Try:

    std::map< int, std::vector<int> > edges;

    That way you can match a single vertex with a list of other vertices without the need to initialize edges to the maximum possible number of vertices.

    std::vector<int> vertices = {5};
edges[4] = vertices;

Upvotes: 1

Paagalpan
Paagalpan

Reputation: 1311

Edges is a vector of vectors. Vectors are stored contiguously in memory. You insert elements into a vector from the end. If the size of vector is 10, all 10 members are contiguous and their indexes are going to range from 0-9. If you delete a middle vector, say 5th, all vectors from index 6-9 get shifted up by 1.

The point of saying all this is that you can't have a situation where edges would have an index that doesn't hold a vector. To answer your question, a vector for index a would exist if

a < mygraph->edges.size ();

Upvotes: 0

stgatilov
stgatilov

Reputation: 5533

Simply check that a does not exceed size of the vector. If it does, then resize the outer vector.

void insert(int a, int b, graph &mygraph) { // a is starting vertex and b is ending vertex
    if (a >= mygraph.edges.size())
        mygraph.edges.resize(a+1);
    mygraph.edges[a].push_back(b);
}

Upvotes: 2

Related Questions