c++ - STL vector 无故损坏，VC++ 2017

Question

我正在制作一个搜索 T-spin 电梯的程序。 https://youtu.be/F3rhyJqusE4

但是我在处理 spin_env 变量时遇到问题，该变量定义如下:

struct spin_environment {
    vector< pair<int, int> > AND;
    vector< vector <pair<int, int> > > OR;
};
spin_environment spin_env[4][2][5];

特别是 spin_env[1][1][2].AND 在回溯期间被破坏。当我初始化它时，它的大小是1。但是在回溯的过程中，突然发现它的大小变成了536870911，里面所有内容的地址都找不到了。但是 spin_env 中的任何其他内容，例如 spin_env[3][0][1].AND，都没有改变。

所以我认为这应该是一个内存问题，所以我将预留内存量设置为堆上 1GB，堆栈上 200MB(默认均为 1MB)。但是同样的问题发生了，即使我拍摄了内存快照，我使用的内存量也没有变化。

我想知道为什么会发生这个错误以及如何解决它。请帮忙!我使用的 IDE 是 Visual Studio C++ 2017，在 x86 Debug模式下构建。

下面是整个代码的描述(不好意思评论少)

#include<stdio.h>
#include<stdlib.h>
#include<utility>
#include<vector>
using namespace std;
vector<pair<int, int>> offset[4][2] = {
    { { { -1, 0 },{ -1, 1 } },{ { 1, 0 },{ 1, 1 } } },
    { { { 1, 0 },{ 0, 2 },{ 0, 2 },{ 1, 2 },{ 1,2 } },{ { 1, 0 },{ 0, 2 },{ 1, 2 } } },
    { { { 1, 0 } },{ { -1, 0 } } },
    { { { -1, 0 },{ 0, 2 },{ -1,2 } },{ { -1, 0 },{ 0, 2 },{ 0, 2 },{ -1,2 },{ -1,2 } } }
};
pair<int, int> block[4][4] = {
    { { 0, 0 },{ 1, 0 },{ -1, 0 },{ 0, 1 } },
    { { 0, 0 },{ 1, 0 },{ 0, -1 },{ 0, 1 } },
    { { 0, 0 },{ 1, 0 },{ -1, 0 },{ 0, -1 } },
    { { 0, 0 },{ 0, -1 },{ -1, 0 },{ 0, 1 } }
};
struct spin_environment {
    vector< pair<int, int> > AND;
    vector< vector <pair<int, int> > > OR;
};
spin_environment spin_env[4][2][5];
vector<int> state_order = { 0, 1, 2, 1, 0}, spin_order = { 0, 0, 0, 0 };
vector<vector<int>> answer;

int field[10][20];
pair<int, int> center = { 5, 18 };
void simulation(int);

pair<int, int> operator+ (pair<int, int> a, pair<int, int> b) {
    return { a.first + b.first, a.second + b.second };
}

//initialize spin_env
void initialization() {
    spin_env[0][0][0].AND = { { 0, -1 } };
    spin_env[0][0][1].AND = { { 0, -1 },{ -1, -1 } };
    spin_env[0][1][0].AND = { { 0, -1 } };
    spin_env[0][1][1].AND = { { 0, -1 },{ 1, -1 } };

    spin_env[1][0][0].AND = { { -1, 0 } };

    spin_env[1][0][1].AND = { { -1, 0 },{ 1, -1 } };
    spin_env[1][0][2].AND = { { -1, 0 },{ 2,0 } };
    spin_env[1][0][2].OR = { { { 1, -1 },{ 2, -1 },{ 1, -2 } } };

    spin_env[1][0][3].AND = { { -1, 0 },{ 1, -1 },{ -1, 2 } };
    spin_env[1][0][4].AND = { { -1, 0 },{ 2,0 },{ -1, 2 } };
    spin_env[1][0][4].OR = { { { 1, -1 },{ 2, -1 },{ 1, -2 } } };

    spin_env[1][1][0].AND = { { -1, 0 } };

    spin_env[1][1][1].AND = { { -1, 0 } };
    spin_env[1][1][1].OR = { { { 1, -1 },{ 2, -1 } },{ { 2, 0 },{ 1, 1 } } };

    spin_env[1][1][2].AND = { { -1, 0 } };
    spin_env[1][1][2].OR = { { { 1, -1 },{ 2, -1 } },{ { 2, 0 },{ 1, 1 } },{ { -1, 2 },{ 0, 3 } } };

    spin_env[2][0][0].AND = { { 0, 1 } };

    spin_env[2][1][0].AND = { { 0, 1 } };

    spin_env[3][0][0].AND = { { 1, 0 } };

    spin_env[3][0][1].AND = { { 1, 0 } };
    spin_env[3][0][1].OR = { { { -1, -1 },{ -2, -1 } },{ { -2, 0 },{ -1, 1 } } };

    spin_env[3][0][2].AND = { { 1, 0 } };
    spin_env[3][0][2].OR = { { { -1, -1 },{ -2, -1 } },{ { -2, 0 },{ -1, 1 } },{ { 1, 2 },{ 0, 3 } } };

    spin_env[3][1][0].AND = { { 1, 0 } };

    spin_env[3][1][1].AND = { { 1, 0 },{ -1, -1 } };
    spin_env[3][1][2].AND = { { 1, 0 },{ -2,0 } };
    spin_env[3][1][2].OR = { { { -1, -1 },{ -2, -1 },{ -1, -2 } } };

    spin_env[3][1][3].AND = { { 1, 0 },{ -1, -1 },{ 1, 2 } };
    spin_env[3][1][4].AND = { { 1, 0 },{ -2,0 },{ 1, 2 } };
    spin_env[3][1][4].OR = { { { -1, -1 },{ -2, -1 },{ -1, -2 } } };
}

//subroutine function of simulation()
void subroutine(int index, int s, int c, int t, int sub_index) {
    if (sub_index == spin_env[s][c][t].OR.size()) {
        center.first += offset[s][c][t].first;
        center.second -= offset[s][c][t].second;
        simulation(index + 1);
        center.first -= offset[s][c][t].first;
        center.second += offset[s][c][t].second;
        return;
    }
    int pass = 0;
    for (int i = 0; i < spin_env[s][c][t].OR[sub_index].size(); i++) {
        pair<int, int> temp = spin_env[s][c][t].OR[sub_index][i];
        if (field[center.second - temp.second][center.first + temp.first] == 1) 
{
            pass = 1;
            break;
        }
    }
    if (pass) {
        subroutine(index, s, c, t, sub_index + 1);
        return;
    }
    for (int i = 0; i < spin_env[s][c][t].OR[sub_index].size(); i++) {
        pair<int, int> temp = spin_env[s][c][t].OR[sub_index][i];
        if (field[center.second - temp.second][center.first + temp.first] == -1) 
continue;
        field[center.second - temp.second][center.first + temp.first] = 1;
        subroutine(index, s, c, t, sub_index + 1);
        field[center.second - temp.second][center.first + temp.first] = 0;
    }
}

//recursive function for backtracking
void simulation(int index) {

    if (index == spin_order.size()) {
        for (int y = 0; y < 10; y++) {
            for (int x = 0; x < 20; x++) {
                switch (field[y][x]) {
                case 1:
                    printf("1 ");
                    break;
                case -1:
                    printf("X ");
                    break;
                default:
                    printf("  ");
                    break;
                }
            }
            printf("\n");
        }
        return;
    }

    int s, c, t;
    pair<int, int> temp;
    s = state_order[index];
    t = spin_order[index];

    switch (state_order[index + 1] - s) {
    case 1:
    case -3:
        c = 0;
        break;
    case -1:
    case 3:
        c = 1;
        break;
    }

    for (int j = 0; j < spin_env[s][c][t].AND.size(); j++) {
        temp = spin_env[s][c][t].AND[j];
        if (field[center.second - temp.second][center.first + temp.first] == -1) 
{
            return;
        }
    }
    for (int j = 0; j < 4; j++) {
        temp = block[state_order[index + 1]][j] + offset[s][c][t];
        if (field[center.second - temp.second][center.first + temp.first] == 1) 
        {
            return;
        }
    }
    for (int j = 0; j < spin_env[s][c][t].AND.size(); j++) {
        temp = spin_env[s][c][t].AND[j];
        field[center.second - temp.second][center.first + temp.first] = 1;
    }
    for (int j = 0; j < 4; j++) {
        temp = block[state_order[index + 1]][j] + offset[s][c][t];
        field[center.second - temp.second][center.first + temp.first] = -1;
    }
    subroutine(index, s, c, t, 0);
    for (int j = 0; j < spin_env[s][c][t].AND.size(); j++) {
        temp = spin_env[s][c][t].AND[j];
        field[center.second - temp.second][center.first + temp.first] = 0;
    }
    for (int j = 0; j < 4; j++) {
        temp = block[state_order[index + 1]][j] + offset[s][c][t];
        field[center.second - temp.second][center.first + temp.first] = 0;
    }
}

//recursive fuction for generate permutation
void permutation(int index) {
    if (index == spin_order.size()) {
        for (int j = 0; j < 4; j++) {
            pair<int, int> temp = block[state_order[0]][j];
            field[center.second - temp.second][center.first + temp.first] = -1;
        }
        simulation(0);
        for (int j = 0; j < 4; j++) {
            pair<int, int> temp = block[state_order[0]][j];
            field[center.second - temp.second][center.first + temp.first] = 0;
        }
        return;
    }

    int k;

    switch (state_order[index]) {
    case 0:
        k = 2;
        break;
    case 1:
        if (state_order[index + 1] == 2) k = 5;
        else k = 3;
        break;
    case 2:
        k = 1;
        break;
    case 3:
        if (state_order[index + 1] == 2) k = 5;
        else k = 3;
        break;
    }
    for (int i = 0; i < k; i++) {
        spin_order[index] = i;
        permutation(index + 1);
    }
}
int main() {
    initialization();
    permutation(0);
}

Answer 1

按原样使用您的代码，只需更改 field 的声明即可这会检测到您在 field 中越界了:

std::vector<std::vector<int>> field(10, std::vector<int>(20));

由于您使用的是 Visual Studio 并且在 Debug模式下运行， Debug模式下的 Visual C++ 会检测 std::vector 的越界错误情况。 .错误发生在 permutation功能:

    if (index == spin_order.size()) {
        for (int j = 0; j < 4; j++) {
            pair<int, int> temp = block[state_order[0]][j];
            field[center.second - temp.second][center.first + temp.first] = -1; // <-- Out of bounds here

当我运行这个程序时，std::pair<int, int> 的值变量 center和 temp如下:

center = {5,18}
temp = {0,0}

center.second - temp.second 的值远远超过最高行索引，即 9，因此您正在访问 vector出界。由于您正在调用未定义的行为，因此该行之后的任何内容都成为讨论点。

请注意，这是通过更改 field 检测到的从使用原始数组到 std::vector 的声明.由于 Visual Studio 检查 std::vector 的边界条件和 std::array在 Debug模式下，您应该利用这一点并将所有数组声明为 std::vector或 std::array ，这样您就可以轻松检测到这些错误，或者至少验证您没有越界。

另外，vector和 array有一个at()可用于检测边界条件和洒水的成员函数 at()调用而不是使用 [ ]访问您的元素也是调试应用程序的另一种方式，或者至少验证您没有边界访问问题。

---

现在如何解决这个问题？您需要调试代码并查看原因 center和/或 temp给你意想不到的值(value)，或者增加你的 field 的大小 vector/数组以容纳索引值。