c++ - 在一棵很深的树上删除

Question

我正在为 10 个字符集构建后缀树(不幸的是，没有时间正确实现后缀树)。我希望解析的字符串会相当长(最多 1M 个字符)。树的构造没有任何问题，但是，当我在完成后尝试释放内存时遇到了一些问题。

特别是，如果我这样设置我的构造函数和析构函数(其中 CNode.child 是一个指向由 10 个指向其他 CNode 的指针组成的数组的指针，而 count 是一个简单的无符号整数):

CNode::CNode(){
    count = 0;
    child = new CNode* [10];
    memset(child, 0, sizeof(CNode*) * 10);
}

CNode::~CNode(){
    for (int i=0; i<10; i++)
        delete child[i];
}

尝试删除根节点时发生堆栈溢出。我可能是错的，但我相当肯定这是由于太多的析构函数调用(每个析构函数最多调用 10 个其他析构函数)。我知道这在空间和时间方面都不是最理想的，但是，这应该是对重复子串问题的快速解决方案。

tl;dr:如何释放一棵非常深的树占用的内存？

感谢您的宝贵时间。

Answer 1

一种选择是从一个大缓冲区分配，然后一次性释放该缓冲区。

例如(未经测试):

class CNodeBuffer {
    private:
        std::vector<CNode *> nodes;

    public:
        ~CNodeBuffer() {
            empty();
        }

        CNode *get(...) {
            CNode *node = new CNode(...);
            nodes.push_back(node);
            return node;
        }

        void empty() {
            for(std::vector<CNode *>::iterator *i = nodes.begin(); i != nodes.end(); ++i) {
                delete *i;
            }

            nodes = std::vector<CNode *>();
        }
};

如果指针指向 std::vector的元素是稳定的，你可以让事情更简单一点，只需要使用 std::vector<CNode> .这需要测试。