开发者

Fastest way to traverse arbitary depth tree for deletion?

For my own exercises I'm writing an XML-parser. To fill the tree I use a normal std::stack and push the current node on top after making it a child of the last top-node (should be depth-first?). So I now do the same for deletion of the nodes, and I want to know if there's a faster way.

Current code for deletion:

struct XmlNode{
    // ignore the rest of the node implementation for now
    std::vector<XmlNode*> children_;
};
XmlNode* root_ = new开发者_Go百科 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();
    }
}

Works totally fine but it kinda looks slow. So is there any faster / better / more common way to do this?


Don't go out of your way to do iteratively what can be easily done recursively, unless you can prove that the recursive version is either insufficient (e.g. stack overflows) or slower (which won't happen unless you start overflowing your stack, forcing the OS to either expand it or crash you).

In other words, in general, use iteration for linear structures, and recursion for tree structures.

Compared to recursion, an iterative method was around 3 times slower on my machine. If you can be sure that your XML depth won't exceed a few hundred nestings (which I've never seen inside real-world XML documents), then recursion won't be a problem.


To iterate is human; to recurse, divine. :)

0

上一篇:

下一篇:

精彩评论

暂无评论...
验证码 换一张
取 消

最新问答

问答排行榜