STL 矢量无故损坏，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 调试模式下构建。

下面描述了整个代码（抱歉评论少）

#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 并且您正在运行调试模式下，调试模式下的 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 的边界条件，您应该利用这一点并将所有数组声明为 std::vector 或 std::array ，这样您就可以轻松检测到这些错误，或者至少验证您没有越界。

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

现在如何解决这个问题？你需要调试你的代码，看看为什么 center and/or temp 给了你意想不到的值，或者增加你的 field vector/array 的大小以容纳索引值。

STL 矢量无故损坏，VC++ 2017

STL vector corrupted for no reason, VC++ 2017

c++

visual-studio

heap-corruption