Project not showing/crashing when adding a simple line of code

[FBF_Luis]

Hello all, I'm trying to make a project which includes a square matrix of objects and for each entry I want to add a list of neighbours which are the 8 surrounding cells (cells on the edge of the matrix will connect to the other side, so each cell should have 8 neighbours). I have this piece of code:


int i;
int j;

for (i = 0; i<NCOL; i++) {
for (j = 0; j<NCOL; j++) {
mat[i][j].neigh.push_back(mat[(i-1+NCOL)%NCOL][(j-1+NCOL)%NCOL]);
//mat[i][j].neigh.push_back(mat[i][(j-1+NCOL)%NCOL]);
mat[i][j].neigh.push_back(mat[(i+1)%NCOL][(j-1+NCOL)%NCOL]);
mat[i][j].neigh.push_back(mat[(i-1+NCOL)%NCOL][j]);
mat[i][j].neigh.push_back(mat[(i+1)%NCOL][j]);
mat[i][j].neigh.push_back(mat[(i-1+NCOL)%NCOL][(j+1)%NCOL]);
mat[i][j].neigh.push_back(mat[i][(j+1)%NCOL]);
mat[i][j].neigh.push_back(mat[(i+1)%NCOL][(j+1)%NCOL]);
}
}


Now, with this piece of code the project runs fine, however when I uncomment the second line of the loop, the project won't run...
Sometimes, it crashes imediately, sometimes it says in the application output that the app is starting and it just stays that way until I force quit it, I had both error 1 and error 3 and for twice now I had my pc restarting while waiting for the mainwindow to show up. I even had those errors claiming I don't have permission.
I really do not understand what is going on here :(

I realized that when trying to run the app with the uncommented line, qt takes about 90% of my computer memory, but I don't know if this is part of the problem since a little line of code should not be such a problem.

I would really appreciate if anyone knows what is happening as I cannot advance in my project until I solve this problem.

[d_stranz]

It is difficult to understand what you intend with this code. Apparently you have a two dimensional array data structure (mat), and each of the elements of mat contains a QList / std list of mat entries.

So think about what is happening each time through the loop. The first time, mat is empty. So for i = 0, j = 0, you are pushing onto mat[0][0]'s list eight empty copies of mat. The next time through, i = 0, j = 1, and you push eight more copies of mat onto mat[0][1], one of which (mat[0][0]) already contains eight copies of mat. I don't know how big NCOL is and it is too early in the morning for me to do the math, but by the end of the double loop, you have a gazillion copies of mat sitting around. None of them represent the actual state of mat, since each of the copies was made at a different time in the building of mat.

The solution is to not make copies of mat. You don't need them. All you need to do to keep track of the neighbors of mat[i][j] is a list of pairs of [i][j] indexes of those neighbors:



mat[i][j].neigh.push_back( std::make_pair( index_i, index_j ) );


where index_i and index_j are the indexes of whichever neighbor you are pushing.

[FBF_Luis]

I ran my code in VSC and after some seconds it return the bad_alloc error, which means it was indeed an absurd amount of objects. Each entry of my matrix is an object I called "Cell" and my goal was for each cell to have 8 other cells as neighbours. Since NCOL is 40, I thought I would have 40*8 obejcts in the neighbours lists. Seeing your explanation, I realize I had the math all wrong and although I don't think it is as bad as you mentioned, it is still an exponential amount of objects which is not good.

Anyways, I followed your suggestion of making a list of pairs and the app is now running fine, so thank you :D

[d_stranz]

Since NCOL is 40, I thought I would have 40*8 objects

Actually 40 * 40 * 8 if your math had been correct. But I am not sure if I can calculate the true number.

So let's see:

For the first row:

mat[0][0] contains 8 copies of mat, none of which have copies of mat.
mat[0][1] contains 8 more copies, one of which (mat[0][0]) also has 8 copies
mat[0][2] - mat[0][38] also each contain 8 copies, one of which (mat[0][n-1]) has 8 more
mat[0][39] has 8 copies plus 16 more (mat[0][0] and mat[0][38]) (I think your grid wraps)

For the second row:

mat[1][0] has 8 copies, plus mat[0][0] and mat[0][1] for 16 more. But mat[0][1] also has mat[0][0] for 8 more.
mat[1][2] has 8, plus mat[0][0], mat[0][1] and mat[0][2] for 24 more. The last two have [0][n-1] for another 16
same for 3 - 38.
mat[1][39] has 8 plus 24 plus 16 plus the 32 from mat[1][0] because of wrapping

and it just gets worse. By the time you get to [39][39] the total is somewhere near a gazillion. :-)

Glad the simpler solution worked for you.