c++ - 包含自身 vector 的结构

Question

我对这段代码有疑问。我尝试创建一个结构“点”，其中有一个相同结构的 vector 。如果 N 很小 (1,2,3)，则没有问题，程序可以正确执行，而如果 N 足够大 (10..100)，编译器将返回此错误:

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

我看过这个题目How to create a structure which contains a list of itself?它说在结构中放入一个引用该结构的 vector 是合法的。非常感谢帮助。谢谢!

#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。

Answer 1

内存不足。

当您执行以下操作时:

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

您正在以递归方式复制 a[i+1][j]，包括其 near vector 的内容!

因此，当您到达第 10000 个节点时，您正在复制大量 vector 。

您可能希望将邻域存储为指针:

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

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