Structure which contains a vector of itself

Question

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.

I'm not sure what your error is yet, but I'm fairly sure that your `near` index would work better as a vector of pointers. — , Aug 07 '17 at 19:01
My bad, read too fast. Have you tried going through with the debugger ? — Hannes Hauptmann, Aug 07 '17 at 19:02
When I run this it slows down a lot with each iteration of the last loop. You're probably having performance problems. — Alex, Aug 07 '17 at 19:03
You cannot have an incomplete type in an `std::vector`. See https://stackoverflow.com/q/18672135/3002139 The answers in the question you link are incorrect. — Baum mit Augen, Aug 07 '17 at 19:04
@user0042 Except that is is undefined behaviour if the container is a standard library container. — juanchopanza, Aug 07 '17 at 20:56

score 3 · Accepted Answer · answered Aug 07 '17 at 19:03

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

Structure which contains a vector of itself

1 Answers1