1

ツリーノードの子を反復処理しています。子はptr_vectorに格納され、反復中のある時点で無限再帰に陥りますが、その理由はわかりません。

無限再帰が発生するメソッドは次のとおりです(このメソッドは、ツリー構造をに出力するために使用されますcout)。

std::ostream& operator<<(std::ostream &strm, const node &n) {
    if (n.children_.empty())
        return strm << "[]";

    for (boost::ptr_vector<node::edge>::const_iterator iter = n.children_.begin(); iter != n.children_.end(); ++iter)
    {
        if (iter != n.children_.begin())
            strm << ", ";
        strm << "-" << iter->distance << "->[ " << *(iter->dest) << "]";
    }

    return strm;
}

そして、これが私がナビゲートしているツリー構造です(ネストされた目的はedge親ノードと子ノードの間の距離を表すことであることに注意してください):

class node
{
public:
    node(void);
    ~node(void);

    node* add_child(unsigned int d);
    node* get_closest(void);

    friend std::ostream& operator<<(std::ostream&, const node&);

private:
    class edge
    {
    public:
        edge(node* n, unsigned int d);
        ~edge(void);

        unsigned int distance;
        node* dest;
    };

    boost::ptr_vector<edge> children_;
};

さらに、この無限再帰は、次のメソッドが呼び出された後にのみ発生することに気付きました。

node* node::get_closest(void) const
{
    if (children_.empty())
        return NULL;

    boost::ptr_vector<node::edge>::const_iterator iter = children_.begin();
    node::edge closest = *iter;
    ++iter;

    if (iter != children_.end())
    {
        for (; iter != children_.end(); ++iter)
        {
            if (iter->distance < closest.distance)
                closest = *iter;
        }
    }

    return closest.dest;
}

この方法で無限再帰が発生するのはなぜですか?ありがとう!

4

1 に答える 1

0

@RobIの提案によると、生のポインターと共有ポインターが混在していることが問題の原因となっています。に変更node::edge closest = *iter;しましたconst node::edge* closest = &(*iter);。メソッドの新しい(そして機能している)バージョンは次のとおりです。

node* node::get_closest(void) const
{
    if (children_.empty())
        return NULL;

    boost::ptr_vector<node::edge>::const_iterator iter = children_.begin();
    const node::edge* closest = &(*iter);
    ++iter;

    if (iter != children_.end())
    {
        for (; iter != children_.end(); ++iter)
        {
            if (iter->distance < closest->distance)
                closest = &(*iter);
        }
    }

    return closest->dest;
}
于 2012-08-15T19:14:04.573 に答える