如何使用二叉搜索树指针纠正 C++ 内存泄漏？

Question

我正在对 C++ 上的某些数据结构应用一些操作。我从 CSV 文件中读取操作，计算 CPU 时间，并将其写入另一个 CSV 文件。

我正在为数百组操作执行此操作，但是，在多次应用 make_experiment() 之后，我收到以下错误：

在抛出 'St9bad_alloc' what(): std::bad_alloc

实例后调用终止

显然可能是因为某些原因我运行内存不足。可能出了什么问题？ ABB 是 BST。

代码如下：

#include <iostream>
#include <string>
#include <fstream>
using namespace std;
typedef unsigned int uint;

string PATH_IN = "ops/";

struct node{
    uint data;
    node* left;
    node* right;
};

class ABB{
    private:
        node* root;
        node* insert(uint x, node* t);
        int find(node* t, uint x);

    public:
        ABB();
        void insert(uint x);
        int search(uint x);
};

node* ABB::insert(uint x, node* t){
    if (t == NULL){
        t = new node;
        t->data = x;
        t->left = t->right = NULL;
    }
    else if(x < t->data)
        t->left = insert(x, t->left);
    else if(x > t->data)
        t->right = insert(x, t->right);
    return t;
}

int ABB::find(node* t, uint x){
    if(t == NULL)
        return 0;
    else if(x < t->data)
        return find(t->left, x);
    else if(x > t->data)
        return find(t->right, x);
    else
        return 1;
}

ABB::ABB() {
    root = NULL;
}

void ABB::insert(uint x) {
    root = insert(x, root);
}

int ABB::search(uint x) {
    return find(root, x);
}

void make_experiment(string tree_type, string exp_type, int n){

    // Declaration of variables
    ABB abb;
    ifstream file_in;
    ofstream file_out;
    string line;
    string op;
    string sval;
    uint val;
    int found;

    // Opening input and output files
    if(exp_type == "r"){
        file_in.open(PATH_IN + "random/random_" + to_string(n+1) +  ".csv");
    }
    file_out.open(tree_type + "_" + exp_type + "_" + to_string(n+1) + ".csv");

    // Dealing with headers
    getline(file_in, line);
    file_out << "op,time_ms" << endl;

    // Applying operations and writing elapsed time to output CSV
    while(getline(file_in, op, ',')) {
        file_out << op << ","; 
        getline(file_in, sval);
        val = (uint)stoul(sval);
        if(op == "i"){
            if(tree_type == "abb"){
                abb.insert(val);
            }
        }
        else if(op == "be"){
            if(tree_type == "abb"){
                found = abb.search(val);
            }    
        }
        else{
            if(tree_type == "abb"){
                found = abb.search(val);
            }
        }
        file_out << "time_elapsed" << endl; 
    }
    file_in.close();
    file_out.close();
}

int main(){
    for(int i=0; i<1000; i++){
        make_experiment("abb", "r", i);
        cout << "ww" << endl;
    }
    return 0;
}

输入的 CSV 文件看起来像这样，有一百万行：

operation,value
i,771383893
be,4071986422
i,2493790208
bi,297183474

一般一直运行到i≈250，正确创建对应的输出文件，然后错误就来了。

Answer 1

最可能的原因是您在私有 insert 函数中创建并分配了原始指针：

node* ABB::insert(uint x, node* t){
    if (t == NULL){
        t = new node; //< new pointer created
        //...
    }
    //...
}

然后将其传递给 insert 的 public 版本中的根数据成员：

void ABB::insert(uint x) {
    root = insert(x, root);
}

但是当你完成时永远不要 destroy/deallocate root 成员指针（即当 ABB 对象被销毁时）。

更正此问题的最简单方法是删除 ABB 的析构函数（您将显式声明和定义）中的根指针：

ABB::~ABB(){
   delete root;
}

同样，你需要一个node的析构函数，这样每个节点的左右指针都会递归释放，否则所有的BST叶子仍然会出现内存泄漏（注意有多种实现方式，我的是一个非常基本的示例实现；您应该研究最适合您需要的实现）：

node::~node() {
    delete left;
    delete right;
}

您可以使用 std::couts 或您的调试器来直观地查看这些析构函数是如何工作的

我还会考虑完全重新设计（特别是私有 insert 函数，甚至可能是私有 find 函数），以便不必在单独的函数中分配和传递原始指针，因为，尽管 不太可能 ，如果在 root 仍在分配时发生类似异常的情况，内存可能会泄漏：

node* ABB::insert(uint x, node* t){
    if (t == NULL){
        t = new node;
        t->data = x;
        t->left = t->right = NULL;
    }
    else if(x < t->data)
        t->left = insert(x, t->left);
    else if(x > t->data)
        t->right = insert(x, t->right);
    return t; //< exception occurs somewhere in the function before this line
}
void ABB::insert(uint x) {
    root = insert(x, root); //< root is never assigned; t is still allocated but not freed
}

更重要的是，如果您以某种方式最终在程序的其他地方使用了私有 insert 函数，您可能会忘记删除该特定指针 并拥有相同的指针问题又来了。如果您的 insert 不是 return 原始指针，这将不是问题。

更好的解决方案（如果您有 C++11 或更新版本） 是重新设计以使用 std::unique_ptr instead of raw pointers, since smart pointers have built in RAII 等智能指针并将管理为您解除指针分配：

struct node{
    uint data;
    std::unqiue_ptr<node> left;
    std::unqiue_ptr<node> right;
    //Destructor no longer needed in this minimal example
};

class ABB{
    private:
        std::unqiue_ptr<node> root;
        std::unqiue_ptr<node> insert(uint x, node& t);
        int find(node& t, uint x);
    public:
        //No destructor or contructor needed in the minimal example
        void insert(uint x);
        int search(uint x);
};

如何使用二叉搜索树指针纠正 C++ 内存泄漏？

How do I correct c++ memory leaks with my binary search tree pointers?

c++

data-structures

memory-management

binary-search-tree