c++ - 调整大小时出现 std::vector 和内存错误

Question

我有一个这样定义的结构:

struct Edge
{
    int u, v;   // vertices

    Edge() { }
    Edge(int u, int v)
    {
        this->u = u;
        this->v = v;
    }
};

和类字段定义如下

vector<Edge> solution;

在其中一种方法中，我正在创建新的 Edge 并像这样将它们插入 vector (对我的实际代码进行了极大的简化，但问题仍然存在):

solution.push_back(Edge(1, 2));
solution.push_back(Edge(3, 4));
solution.push_back(Edge(5, 6));
solution.push_back(Edge(7, 8));
solution.push_back(Edge(9, 10));
solution.push_back(Edge(11, 12));
solution.push_back(Edge(13, 14)); // adding 7th element; the problem occurs here

当执行最后一个 push_back 时，我在 Visual Studio 的 Debug模式下得到一个错误窗口

[AppName] has triggered a breakpoint.

然后调试器转到 malloc.c，到 _heap_alloc 函数的末尾。在第 7 行之前， vector 似乎可以正常工作。我可以在调试器中看到所有元素。似乎 vector 在重新分配自身(扩展其大小)时遇到了问题。

有趣的是，如果我把它放在所有推回之前:

solution.reserve(7);

，第 7 条边添加正确。更有趣的是，尝试为超过 22 个元素保留空间也会导致上述错误。

我做错了什么？我该如何调试它？应用程序的其余部分没有使用那么多内存，所以我无法相信堆已满。

---

更多代码，应要求提供。这是公制旅行商问题的 2 近似算法的一个相当草率的实现。它首先创建一个最小生成树，然后以 DFS 顺序将顶点(只是索引)添加到 partialSolution vector 。

void ApproxTSPSolver::Solve()
{
    // creating a incidence matrix
    SquareMatrix<float> graph(noOfPoints);

    for (int r=0; r<noOfPoints; r++)
    {
        for (int c=0; c<noOfPoints; c++)
        {
            if (r == c)
                graph.SetValue(r, c, MAX);
            else
                graph.SetValue(r, c, points[r].distance(points[c]));
        }
    }

    // finding a minimum spanning tree
    spanningTree = SquareMatrix<bool>(noOfPoints);

    // zeroeing the matrix
    for (int r=0; r<noOfPoints; r++)
        for (int c=0; c<noOfPoints; c++)
            spanningTree.SetValue(r, c, false);

    bool* selected = new bool[noOfPoints];
    memset(selected, 0, noOfPoints*sizeof(bool));
    selected[0] = true; // the first point is initially selected

    float min;
    int minR, minC;

    for (int i=0; i<noOfPoints - 1; i++)
    {
        min = MAX;

        for (int r=0; r<noOfPoints; r++)
        {
            if (selected[r] == false)
                continue;

            for (int c=0; c<noOfPoints; c++)
            {
                if (selected[c] == false && graph.GetValue(r, c) < min)
                {
                    min = graph.GetValue(r, c);
                    minR = r;
                    minC = c;
                }
            }
        }

        selected[minC] = true;
        spanningTree.SetValue(minR, minC, true);
    }

    delete[] selected;

    // traversing the tree
    DFS(0);

    minSol = 0.0f;

    // rewriting the solution to the solver's solution field
    for (int i=0; i<noOfPoints - 1; i++)
    {
        solution.push_back(Edge(partialSolution[i], partialSolution[i + 1]));
        minSol += points[partialSolution[i]].distance(points[partialSolution[i + 1]]);
    }

    solution.push_back(Edge(partialSolution[noOfPoints - 1], partialSolution[0]));
    minSol += points[partialSolution[noOfPoints - 1]].distance(points[partialSolution[0]]);

    cout << endl << minSol << endl;

    solved = true;
}

void ApproxTSPSolver::DFS(int vertex)
{
    bool isPresent = std::find(partialSolution.begin(), partialSolution.end(), vertex)
        != partialSolution.end();

    if (isPresent == false)
        partialSolution.push_back(vertex); // if I comment out this line, the error doesn't occur

    for (int i=0; i<spanningTree.GetSize(); i++)
    {
        if (spanningTree.GetValue(vertex, i) == true)
            DFS(i);
    }
}


class ApproxTSPSolver : public TSPSolver
{
    vector<int> partialSolution;
    SquareMatrix<bool> spanningTree;
    void DFS(int vertex);

public:
    void Solve() override;
};

---

来自main.cpp:

TSPSolver* solver;
    string inputFilePath, outputFilePath;

    // parsing arguments
    if (ArgParser::CmdOptionExists(argv, argv + argc, "/a"))
    {
        solver = new ApproxTSPSolver();
    }
    else if (ArgParser::CmdOptionExists(argv, argv + argc, "/b"))
    {
        solver = new BruteForceTSPSolver();
    }
    else
    {
        solver = new BranchAndBoundTSPSolver();
    }

    inputFilePath = ArgParser::GetCmdOption(argv, argv + argc, "/i");
    outputFilePath = ArgParser::GetCmdOption(argv, argv + argc, "/s");

    solver->LoadFromFile(inputFilePath);

    Timer timer;
    timer.start();
    solver->Solve();
    timer.stop();

    cout << timer.getElapsedTime();

TSPSolver.c 的一部分:

TSPSolver::TSPSolver()
{
    points = NULL;
    solved = false;
}

TSPSolver::~TSPSolver()
{
    if (points)
        delete[] points;
}

void TSPSolver::LoadFromFile(string path)
{
    ifstream input(path);
    string line;
    int nodeID;
    float coordX, coordY;
    bool coords = false;

    minX = numeric_limits<float>::max();
    maxX = numeric_limits<float>::min();
    minY = numeric_limits<float>::max();
    maxY = numeric_limits<float>::min();

    while (input.good())
    {
        if (coords == false)
        {
            getline(input, line);

            if (line == "NODE_COORD_SECTION")
            {
                coords = true;
            }
            else if (line.find("DIMENSION") != string::npos)
            {
                int colonPos = line.find_last_of(":");
                noOfPoints = stoi(line.substr(colonPos + 1));
#ifdef _DEBUG
                cout << noOfPoints << " points" << endl;
#endif

                // allocating memory for this amount of points
                points = new Point[noOfPoints];
            }
        }
        else
        {
            input >> nodeID >> coordX >> coordY;

            points[nodeID - 1].X = coordX;
            points[nodeID - 1].Y = coordY;

            minX = min(minX, coordX);
            maxX = max(maxX, coordX);
            minY = min(minY, coordY);
            maxY = max(maxY, coordY);

            if (nodeID == noOfPoints)
            {
                break;
            }
        }
    }

    input.close();
}

Answer 1

这是一个评论而不是一个答案，但是空间太有限了。

如果您使用的是 Windows，请尝试 Microsoft Application Verifier .它可能会检测到错误的内存访问。

另一种检测此类访问的方法是保留初始化为 0 的空字符数组。

打开声明 vector 的类，并在 vector 前后声明一个 char 数组，比方说 64 个字符，并将它们初始化为 0!。然后进入你的 vector 代码，在那里产生错误并检查那些填充数组的内容。如果他们被填满，有人会写更多它应该写的。

定位“恶意”访问(至少在 VC++ 中)的一种方法是在填充数组中设置数据断点，然后检查调用堆栈。