CODEWITHSUNDEEP
c++vectorstruct
Fra
Fra

Reputation: 79

Structure which contains a vector of itself

I have a problem with this code. I try to create a struct "point" in which there is a vector of the same struct. If N is small (1,2,3) there aren't problems and the program is correctly execute, while if N is enough big (10..100) the compiler return this error:

terminate called after throwing an instance of 'std::bad_alloc'
what(): std::bad_alloc

I have seen this topic How to create a structure which contains a list of itself? and it says that is legal put inside a struct a vector that refers to that struct. Help is greatly appreciated. Thanks!

#include <iostream>
#include <vector>

using namespace std;

struct point{

    int a;
    int b;
    vector<point> near;

};

int main()
{

    int N = 100;
    vector<vector<point>> a;

    a.resize(N);
    for ( int i = 0; i<N; i++){
        a[i].resize(N);
    }

    for ( int i = 0; i<N; i++){
        for ( int j=0; j<N; j++){

                a[i][j].near.reserve(4);
                if ( i+1< N) {a[i][j].near.push_back(a[i+1][j]);}
                if ( i-1>=0) {a[i][j].near.push_back(a[i-1][j]);}
                if ( j+1< N) {a[i][j].near.push_back(a[i][j+1]);}
                if ( j-1>=0) {a[i][j].near.push_back(a[i][j-1]);}

        }
    }

    return 0;
}

Windows 10 - Code::blocks 16.01.

Upvotes: 2

Views: 652

Answers (1)

user4442671
user4442671

Reputation:

You are running out of memory.

When you do the following:

if ( i+1< N) {a[i][j].near.push_back(a[i+1][j]);}

You are copying a[i+1][j], including the content of its near vector, recursively!

So by the time you hit your 10000th node, you are copying a LOT of vectors around.

You may want to store neighbourhood as pointers instead:

struct point{
    int a;
    int b;
    vector<point *> near;
};

...
if ( i+1< N) {a[i][j].near.push_back(&a[i+1][j]);}
...

Upvotes: 3

Related Questions