18

次のコードは正常にコンパイルおよび実行されます。

#include <memory>
struct MyTree {
    std::shared_ptr <MyTree> left;
    std::shared_ptr <MyTree> right;
    int val;
    MyTree(
        std::shared_ptr <MyTree> left_,
        std::shared_ptr <MyTree> right_,
        int val_
    ) : left(left_), right(right_), val(val_) {};
};
int main() {
    std::shared_ptr <MyTree> t(
        new MyTree( std::shared_ptr <MyTree>(),
                    std::shared_ptr <MyTree>(),
                    0)
    );  
    for(int i=0;i<10000;i++) {
        t.reset(new MyTree(t,t,0));
    }
}

ただし、for ループを 10000 から 100000 に変更すると、segfault が発生します。gdb の結果を見ると、std::shared_ptr のガベージ コレクションの結果としてデストラクタが呼び出され、数千の深さのバックトレースが作成されているようです。そのため、セグメンテーション違反は、関数呼び出しからスタック上のスペースが不足しているためだと思います。2つ質問があります。まず、これはセグメンテーション違反の正しい評価ですか? 第二に、もしそうなら、ガベージコレクションが必要であるが非常に大きくなる可能性があるツリーなどのカスタムデータ構造を管理する良い方法はありますか. ありがとう。

4

4 に答える 4

8

通常、ツリーのバランスを保ち、深さがO（lg N）であるため、これは通常問題にはなりません。

代わりに、すべてのポインタの複製コピーを含む、奇妙な単一リンクリストがあります。それは変です。

実際の単一リンクリストは非常に深い再帰ですが、末尾呼び出しの最適化の恩恵を受け、スタックを使い果たすことはありません。

あなたが抱えている問題は、2つのデータ構造の混合に非常に独特です。これには私が見ることができる利点はありません。

于 2012-12-27T16:10:39.753 に答える
4

あなたの評価は私には完全に正しいように見えます。子サブツリーを削除するための再帰呼び出しが、スタック サイズを超えているようです。shared_ptrただし、データ構造の再帰アルゴリズムも同じように失敗すると予想されるため、これは関係ありません。

プラットフォームで可能であれば、そのような大きな構造体の必要性に対処する最も簡単な方法は、単純にスタックのサイズ (たとえばulimit) を増やして、自然な再帰アルゴリズムが機能できるようにすることです。

それが不可能な場合は、ノードを自分でトラバースし、トラバースの結果を何らかのコンテナーに格納して、サブノードを切り刻み、ツリー構造の完全な深さのトラバーサルを必要としないようにする必要があります。

于 2012-12-27T15:58:58.203 に答える
1

これは の誤用のように私には見えますstd::shared_ptr。そして、いくつかの非常に貧弱な命名: クラスMyTreeはツリーではなく、単なるノードです。ツリーは別のクラスである必要があり、そのデストラクタ内のすべてのノードを削除する必要があります。

そうは言っても、目前の問題に関しては、これはあまり変わりません。ツリーのノードを再帰的に (唯一の方法で) 訪問しており、ツリーを深くしすぎると、訪問が暗黙的 ( のデストラクタ呼び出しによるstd::shared_ptr)であるかどうかに関係なく、スタックがオーバーフローします。明示的。このようなツリーを最初から作成しても意味がありません。破壊を開始する前にノードにアクセスできないツリーを作成しても意味がないからです。

編集：

コメントでのガベージ コレクションの議論を考慮に入れる。Boehm コレクターまたはその他のガベージ コレクターを使用すると、要素の割り当て解除の問題を解決できます。しかし、それでも割り当てを解除する前にアクセスすることはできないため、そのようなツリーは役に立たないままです。(C++ でのガベージ コレクションを支持する非常に強力な議論があると思いますが、これはその 1 つではありません。)

于 2012-12-27T17:10:00.477 に答える
0

このタイプのエラーは、shared_ptr がなくても再現できると思います。これは基本的に長い再帰呼び出しです。わかりました、ツリーの半分を作成して削除しましたが...

struct MyTree {
    MyTree *left;
    int val;
    MyTree()
    {
      left = 0;
    }
    MyTree(MyTree *left_)
     : left(left_) {};

    ~MyTree()
    {
      delete left;
    }
};
int main() {
    MyTree *t = new MyTree();
    for(int i=0;i<100000;i++) {
      t = new MyTree(t);
    }
    delete t;
}

100000 の後にゼロをもう 1 つ追加すると、同じエラー メッセージが表示されます。

于 2012-12-27T21:12:58.250 に答える