c++ - 我怎么知道双重释放或损坏(出)错误是从哪里来的？

Question

#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>
using namespace std;
#define MAX_WEIGHT 1000000
class Set
{
public:
    int * parent;
    int * height;

    Set(int _n)
    {
        parent = new int[_n+1];
        height = new int[_n+1];
        for(int i=0; i<_n+1; i++)
        {
            parent[i] = i;
            height[i] = 0;
        }
    }
    ~Set()
    {
        delete[] parent;
        delete[] height;
    }

    int Find_Set(int _x)
    {
        while(parent[_x]!=_x)
        {
            _x = parent[_x];
        }
        return _x;
    }

    void Union_Set(int _x, int _y)
    {
        _x = Find_Set(_x);
        _y = Find_Set(_y);
        if(_x!=_y)
        {
            if(height[_x]>height[_y])
                parent[_y] = _x;
            else if(height[_x]<height[_y])
                parent[_x] = _y;
            else
            {
                parent[_y] = _x;
                height[_x]++;
            }
        }
    }
};
template<typename WEIGHT_TYPE>
class Graph
{
public:
    int vNum; // num of vertices
    int eNum; // num of edges
    vector<pair<int, WEIGHT_TYPE>> * edges;

    Graph(const char * _fileName)
    {
        FILE * input = fopen(_fileName, "r");
        fscanf(input, "%d %d", &vNum, &eNum);
        edges = new vector<pair<int, WEIGHT_TYPE>>[vNum];

        for(int i=0; i<eNum; i++)
        {
            int idx1, idx2;
            double weight;
            fscanf(input, "%d %d %lf", &idx1, &idx2, &weight);
            idx1--;
            idx2--;

            edges[idx1].push_back(make_pair(idx2, weight));
            edges[idx2].push_back(make_pair(idx1, weight));
        }
    }

    ~Graph()
    {
        delete[] edges;
    }
};
template<typename WEIGHT_TYPE>
WEIGHT_TYPE Kruskal(Graph<WEIGHT_TYPE> &_graph)
{
    vector<pair<WEIGHT_TYPE, pair<int, int>>> k;
    for(int i=0; i<_graph.vNum; i++)
    {
        for(int j=0; j<_graph.edges[i].size(); j++)
        {
            if(_graph.edges[i][j].second==-1)
                continue;
            if(i<_graph.edges[i][j].first)
                k.push_back(make_pair(_graph.edges[i][j].second, make_pair(i, _graph.edges[i][j].first)));
        }
    }
    sort(k.begin(), k.end());
    WEIGHT_TYPE cost = (WEIGHT_TYPE)0;
    Set s(_graph.vNum);

    for(int i=0; i<k.size(); i++)
    {
        int idx1 = k[i].second.first;
        int idx2 = k[i].second.second;
        WEIGHT_TYPE weight = k[i].first;

        if(s.Find_Set(idx1) != s.Find_Set(idx2))
        {
            s.Union_Set(idx1, idx2);
            cost += weight;
        }
    }
    return cost;
}
template<typename WEIGHT_TYPE>
WEIGHT_TYPE Second(Graph<WEIGHT_TYPE> _graph)
{
    WEIGHT_TYPE cost = (WEIGHT_TYPE)INT_MAX;
    WEIGHT_TYPE cost2 = (WEIGHT_TYPE)INT_MAX;
    WEIGHT_TYPE result = (WEIGHT_TYPE)INT_MAX;
    for(int from=0; from<_graph.eNum; from++)
    {
        for(int i=0; i<_graph.edges[from].size(); i++)
        {
            int to = _graph.edges[from][i].first;
            for(int j=0; j<_graph.edges[to].size(); j++)
            {
                if(_graph.edges[to][j].first==from)
                {
                    int tmp1 = _graph.edges[from][to].second;
                    int tmp2 = _graph.edges[to][j].second;
                    _graph.edges[from][to].second = -1;
                    _graph.edges[to][j].second = -1;
                    result = Kruskal(_graph);
                    printf("RESULT : %d\n", result);
                    if(result<cost)
                    {
                        cost2 = cost;
                        cost = result;
                    }
                    else if(result>cost && result<cost2)
                    {
                        cost2 = result;
                    }
                    _graph.edges[from][to].second = tmp1;
                    _graph.edges[to][j].second = tmp2;
                    printf("SECOND : %d\n", cost2);
                }
            }
        }
    }
    return cost2;
}
int main(int argc, char **argv)
{
    Graph<int> g(argv[1]);
    //int cost = Kruskal<int>(g);
    int cost2 = Second<int>(g);
    printf("cost2: %d\n", cost2);   
    FILE * output = fopen(argv[2], "w");
    fprintf(output, "%d", cost2);
}

好吧，我有这段代码和我的输入文件

7 12
1 2 8
1 3 5
2 3 10
2 4 2
2 5 18
3 4 3
3 6 16
4 5 12
4 6 30
4 7 14
5 7 4
6 7 26

我在网上搜索了这个错误，发现它是在你删除一个从未分配的、已经删除或从内存中释放的内存时引起的。但是我没有看到我的代码的任何部分可以释放或删除那些空内存。我也尝试使用 GDB 但由于我的知识不足，我只是发现它是由 Second 中的 Kruskal() 引起的( ) 在 main() 中....没有别的..所以我想知道我的代码中的哪个导致错误以及我如何跟踪它？

Answer 1

您没有遵守规则 5:如果您手动定义五个特殊成员函数(析构函数、复制构造函数、移动构造函数、复制赋值、移动赋值)中的任何一个，您应该显式定义所有五个，因为自动生成的那些很可能是错误的。

这里就是这种情况:

您的类有一个隐式定义的复制构造函数(它复制指针成员)。当您调用 WEIGHT_TYPE Second(Graph<WEIGHT_TYPE> _graph) 时调用此复制构造函数- 参数被复制。现在你有相同的两个拷贝 Graph , 都带有指向同一数组的指针 vector 。第一个超出范围的(在 Second 的末尾)将 delete[]那个指针......但最终程序结束了，Graph在 main将超出范围并将 delete[]又是指针!这是双重免费。

这就是为什么您应该以遵循零规则为目标:永远不要进行显式资源管理。不要使用 new和 delete ，使用智能指针或容器类。编译器将自动生成正确的操作(并禁止那些没有意义的操作 - 如果您的类具有指针的明确所有权，即 std::unique_ptr，则无法复制它)。

进一步阅读:https://en.cppreference.com/w/cpp/language/rule_of_three