gpt4 book ai didi

c++ - 遍历任意深度树进行删除的最快方法?

转载 作者:行者123 更新时间:2023-11-30 04:35:43 25 4
gpt4 key购买 nike

为了我自己的练习,我正在编写一个 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();
}
}

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

最佳答案

不要特意去迭代地做递归可以轻松完成的事情,除非你能证明递归版本不够充分(例如堆栈溢出) 或更慢(这不会发生,除非你开始溢出你的堆栈,迫使操作系统扩展它或使你崩溃)。

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

Compared to recursion ,迭代方法在我的机器上慢了大约 3 倍。如果您可以确定您的 XML 深度不会超过几百个嵌套(我在真实世界的 XML 文档中从未见过),那么递归就不是问题。


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

关于c++ - 遍历任意深度树进行删除的最快方法?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/5012022/

25 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com