C++实现的B树出现内存泄漏，是否为析构函数逻辑错误导致？

问题原因 #

你遇到的bad_alloc确实是析构逻辑错误导致的内存泄漏：
当前BNode的析构函数仅释放了当前节点的keys数组、存储子节点指针的C数组本身，但C数组中存储的所有子节点实例没有被释放，整个B树除根节点外的所有节点都会残留内存，多次迭代后内存耗尽就会抛出分配错误。

修复方案 #

修改BNode的析构函数，递归释放所有子节点即可：

BNode::~BNode(){
    delete[] keys;
    // 遍历释放所有子节点，n个关键字对应n+1个子节点
    for (int i = 0; i < n + 1; ++i) {
        // C++中delete空指针为合法操作，无需额外判断非空
        delete C[i];
    }
    delete[] C;
}

原理说明 #

修改后：

1. 每次function执行结束触发BTree析构，调用delete root触发根节点的析构函数
2. 根节点析构时会先逐个delete所有子节点，每个子节点又会递归释放自己的子节点
3. 最终整个B树的所有节点资源都会被完全回收，不会再出现内存泄漏。

修改后重新运行测试即可解决迭代多次后抛出bad_alloc的问题。

内容的提问来源于stack exchange，提问作者vdaiep