1

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 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?

4

1 に答える 1

2

再帰バージョンが不十分（スタックオーバーフローなど）または低速（スタックオーバーフローを開始しない限り発生しない）であることが証明できない限り、簡単に再帰的に実行できることを繰り返し実行しないでください。 OSを拡張するか、クラッシュさせます）。

つまり、一般に、線形構造には反復を使用し、ツリー構造には再帰を使用します。

再帰と比較して、反復法は私のマシンでは約3倍遅くなりました。XMLの深さが数百のネスト（実際のXMLドキュメント内では見たことがない）を超えないことが確実であれば、再帰は問題になりません。

繰り返すのは人間です。再帰する、神。:)

于 2011-02-16T06:10:36.703 に答える