C++中二维矢量初始化问题

Question

我正在为这个问题实现一个解决方案，以获得对该语言的感觉。我的理由如下：

1. 注意，对角线上的模式是2*n+1。
2. 左边和上面的元素是从对角线到边界的元素的交替算术累进或加/减。
3. 创建一个2D向量并实例化所有对角线元素。然后创建一个虚拟变量，通过添加/减去对角线元素来填充其余部分。

我的代码如下：

#include <vector>

using namespace std;

const long value = 1e9;

vector<vector<long>> spiral(value, vector<long> (value));
long temp;

void build(){
    spiral[0][0] = 1;
    for(int i = 1; i < 5e8; i++){
        spiral[i][i]= 2*i+1;
        temp = i;
        long counter = temp;
        while(counter){
            if(temp % 2 ==0){
                spiral[i][counter]++;
                spiral[counter][i]--;
                counter--;
                temp--;
            }else{
                spiral[i][counter]--;
                spiral[counter][i]++;
                counter--;
                temp--;
            }
        }
    }
}

int main(){
    spiral[0][0] = 1;
    build();
    int y, x;
    cin >> y >> x;
    cout << spiral[y][x] << endl;
}

问题是这个程序没有输出任何东西。我不明白为什么我的向量不打印任何元素。我已经用spiral[1][1]对它进行了测试，在等待5或10分钟之后，我得到的只是一些晦涩的汇编程序消息。我的推理怎么了？

编辑:完整输出如下：

​

​

和

​

​

Answer 1

对于您来说，long可能是4或8个字节(例如，Windows上通常是4个字节，x86 Linux上通常是4个字节，x64 Linux上是8个字节)，所以让我们假设4G的1e9 * 4是每个vector<long> (value)的4G连续内存。

然后，外部向量创建另一个1e9副本，它是4艾字节(或4百万兆字节)，给定32位长或64位加倍，忽略了每个std::vector的开销大小。您不太可能拥有那么多内存和swapfile，并且在调用main()之前尝试使用它作为全局文件。

因此，您将无法直接存储所有这些数据，您需要考虑实际需要存储哪些数据才能获得您想要的结果。

如果您在设置为停止异常的调试器下运行，您可能会看到一个std::bad_alloc被抛出，调用堆栈指示原因(例如，Visual将在调用堆栈中显示类似于“‘螺旋’的动态初始化器”之类的内容)，但是在Linux上操作系统可能会首先关闭它，因为Linux可以过提交内存(因此new等)，然后当某些程序使用内存(实际的读或写)时，它会失败(过度提交，没有任何空闲)，并且SIGKILL会释放内存(这似乎不是完全可以预测的)，我将您的代码复制到Ubuntu 18上，并在命令行上得到“在抛出‘std：：bad_alloc’实例后终止调用”)。

Answer 2

这个问题实际上要求你为解决方案找到一个解析公式，而不是模拟模式。您所需要做的就是仔细分析模式：

unsigned int get_n(unsigned int row, unsigned int col) {
    assert(row >= 1 && col >= 1);

    const auto n = std::max(row, col);
    if (n % 2 == 0)
        std::swap(row, col);
    if (col == n)
        return n * n + 1 - row;
    else
        return (n - 1) * (n - 1) + col;
}