1

对于我自己的练习,我正在编写一个 XML 解析器。为了填充树,我使用法线std::stack并将当前节点设置为最后一个顶部节点的子节点(应该是深度优先?)。所以我现在对删除节点做同样的事情,我想知道是否有更快的方法。
当前删除代码:

struct XmlNode{
    // ignore the rest of the node implementation for now
    std::vector<XmlNode*> children_;
};
XmlNode* root_ = new XmlNode;

// fill root_ with child nodes...
// and then those nodes with child nodes and so fort...

std::stack<XmlNode*> nodes_;
nodes_.push(root_);
while(!nodes_.empty()){
    XmlNode* node = nodes_.top();
    if(node->children_.size() > 0){
        nodes_.push(node->children_.back());
        node->children_.pop_back();
    }else{
        delete nodes_.top();
        nodes_.pop();
    }
}

工作得很好,但看起来有点慢。那么有没有更快/更好/更常见的方法来做到这一点?

4

1 回答 1

2

除非您能证明递归版本不足(例如堆栈溢出)或较慢(除非您开始溢出堆栈,否则不会发生这种情况,否则不会发生这种情况除非您能证明递归版本不充分(例如堆栈溢出),否则不会发生这种情况。操作系统来扩展它或让你崩溃)。

换句话说,一般来说,对线性结构使用迭代,对树结构使用递归。

与递归相比,迭代方法在我的机器上慢了大约 3 倍。如果您可以确定您的 XML 深度不会超过几百个嵌套(我从未在现实世界的 XML 文档中看到过),那么递归就不会成为问题。


迭代是人;递归,神圣的。:)

于 2011-02-16T06:10:36.703 回答