CODEWITHSUNDEEP
c++vector
Ashton Wiens
Ashton Wiens

Reputation: 61

vector out of range/ range check

new user here. I have been writing this code which creates a network with nodes and uses a random number to create edges between them. I keep track of the whole graph as a vector, each entry being a vector representing a node whose elements are its neighbors. It then uses a depth-first search to find the number of components, which are seperated parts of the graph (my count variable). Then I output the node and the number of neighbors it is connected to into a txt file. The code compiles, but the command prompt gives me an error:

terminate called after throwing an instance of 'std::out_of_range' what(): vector::_M_range_check

This application has requested the Runtime to terminate it in an unusual way. Please contact support...

So... what does this mean and how can I fix it?

Also, I need to keep track of how many nodes are in each component, any ideas?

Thanks in advance, here is my code:

#include <iostream>
#include <fstream>
#include <stdlib.h>
#include <vector>
using namespace std;

void gengraph(int v, float p, vector <vector <int> >& G);
void DFS(vector <vector <int> > G, int v, vector<int>& M);

int main()
{
    int a = 1000;
    float b = 0.004;
    vector <vector <int> > G;
    gengraph(a,b,G);
    vector <int> M (1000);
    int count = 0;
    int i;
    for (i = 0; i < a; i++)
    {
        if (M[i]==0)
        {
            DFS(G, i, M);
            count += 1;
        }
    }
    ofstream myfile;
    myfile.open ("data.txt");
    for (int l=0; l<1000; l++)
    {
        myfile << "v   len(G[v])\n";
    }
    myfile.close();
}
void gengraph(int v, float p, vector <vector <int> >& G)
{
    for (int i = 0; i<1000; i++)
    {  
        for (int j = 0; j<1000; j++)
        {
            int y = rand();
            bool Prob = (y <= p);
            if (i == j)
                continue;
            else
            {
                if(Prob == true)
                {
                    G.at(i).push_back (j);
                    G.at(j).push_back (i);
                }
            }
        }
    }
}
void DFS(vector <vector <int> >& G, int v, vector<int>& M)
{
    M[v]=1;
    for(unsigned int j = 0; j < G[v].size(); j++)
    {
        if (M[j]==0)
        {
            DFS(G, j, M);
        }
    }
}

Upvotes: 6

Views: 33283

Answers (4)

Tony Delroy
Tony Delroy

Reputation: 106106

vector <vector <int> > G;

This creates a vector of vectors-of-ints, but initially there are no vectors-of-int elements. Despite that, you call G.at(i)... which - for any value of i, immediately accesses a non-existant element.

Separately, rand() returns a random 32-bit integer, so will almost always be more than your 0.004 float. You may want to use something like (rand() % 1000000 / 1000000.0). The random number subsystem should be initialised with a call ala srand(time(NULL));

More generally, you're best off using a few std::cerr << "x is now " << x << '\n'; - printing variables, vector sizes etc. - scattered through your code so you can see what it's doing and where it goes wrong. Alternatively, see if you can get an interactive debugger and step through your code line by line.

Upvotes: 2

Moataz Elmasry
Moataz Elmasry

Reputation: 2519

You created the vector > but it has initial size 0.

Now when you access it using M.at() it checks whether this index is out of bound and throws an exception if this is case.

defining the vector as:

vector<vector<int> > M(1000);

should solve your problem.

You should also use gdb or other debugger. it will make life much easier on you

Upvotes: 2

Slava
Slava

Reputation: 44258

First error: in function gengraph() you use empty vector:

G.at(i) ...
G.at(j) ...

Yes you call push_back, but you call it of what method at() returned. But at() cannot return anything whatever value i and j have there as your vector is empty. One of the solution put this line in the begining of gengraph()

G.resize( 1000 );

Second advice: avoid to use magic numbers as much as possible. Put something like:

const int size = 1000;

In the begining of your file and use size instead of magic number 1000. Especially this:

int a = 1000;
float b = 0.004;
vector <vector <int> > G;
gengraph(a,b,G);
vector <int> M (1000); // use a here and better call it something more meaningfulness than a
int count = 0;
int i;
for (i = 0; i < a; i++) { // or use M.size() here or both
}

Upvotes: 0

StoryTeller - Unslander Monica
StoryTeller - Unslander Monica

Reputation: 170084

It means you indexed a vector outside of it's range.

vector::at() performs range checks. So it's probably because you don't pre-allocate enough elements to G.

Upvotes: 0

Related Questions