共有ポインタは再帰的なデータ構造を再帰的に削除し、スタックがオーバーフローします

Question

私は長いリンクリストを持っています（最大20,000アイテムあります）。彼らは異なる始まりを持っていますが、最終的にはあるノードから同じノードに向かうことができます。私はそのようなリンクされたリストを一緒に成長させ、それらの間の記憶を共有させることを決めました。

#include <memory> 
struct SharedLinkedList { 
    int someData; 
    std::shared_ptr<SharedLinkedList> next; 
}; 

この方法で、すべてが正常に動作します：私は共有ポインタとリンクリストを実装することを決定しまし理由です

。不要になったリンクリストは削除されます。それらが他のリンクされたリストとある部分を共有する場合、その非共有部分のみが削除されます。

共有パーツのない長いリンクリストを削除しようとすると問題が発生します。削除は最初の要素から始まります。これにより、削除することができる次の要素への参照数が減少し、スタックがオーバーフローするまで再帰的に繰り返されます。

ここでは、長いリンクリストを作成して削除に失敗するコードの例を示します。

SharedLinkedList* beginningOfList; 
SharedLinkedList* actualElement = new SharedLinkedList(); 
SharedLinkedList* nextElement; 

beginningOfList = actualElement; 
for (int i = 0; i < 1000; i++) { // 100 is OK, 1000 is KO 
    nextElement = new SharedLinkedList(); 
    actualElement->next = std::shared_ptr<SharedLinkedList>(nextElement); 
    actualElement = nextElement; 
} 
delete beginningOfList; 

私は、次のいずれかのために、事前に感謝：shared_pointersのと、私が行方不明です何の

1. 説明。どうすれば使えますか？そして、それを使ってもできますか？そのような記憶の共有は、共有ポインタが発明されたものではないか？
2. アドバイスコードを再実装する方法
3. このコードは、コンピュータで実行される科学計算に使用されます。スタックのサイズを大きくするために何か何かを微調整することはできますか？

この質問は、C++ 11固有のものではありません。共有ポイントの実装が使用されているかどうかは気にしません。私は自分の共有ポインタを実装しました。これにより、リンクリストを少し長くすることができましたが、デストラクタやスタックオーバーフローの再帰も出現しました。デストラクタで再帰せずに共有ポインタを実装する方法はありません。

EDIT：

ただ、混乱をaviodする：私は、全体のリストを共有することができることを繰り返したいです。だから、それを木と呼ぶことができます。

LIST1が含まれています：1,2,3,4,5,6,7をここ

は一例です。

リスト2は含まれています6,6,6,1,2,3,4,5,6,7

LIST3は含まれています10,11,12,1,2,3,4,5,6 、7

1,2,3,4,5,6,7を数回記憶することでモーモリーを浪費しない3つのSharedLinkedListでこれを表現したいのですが、それらは同じ場所を指しています。そのため、参照カウントが必要です。

delete list3;は、共有されていない部分、すなわち要素10,11,12のみを削除することになっています。

Answer 1

あなたがshared_ptrを使用する場合は、所有権を管理しますあなたのために。参照カウントが0になると、pointeeのデストラクタを呼び出します。今度はオブジェクトへのポインタが破棄され、その要素として次の共有ポインタが次のポインタを破棄します。これにより、メモリの再割り当て方法が再帰的に発生します。今度は、メモリの反復を解除しようとする可能性があります。あなただけの破壊を回避し、後でそれを手動で削除するには、次の要素への参照を保持する必要があります。

void destroy(SharedLinkedList* l) { 
    auto next=l->next; // take 2nd element 
    delete l;   // delete first 

    while (next) 
    next=next->next; // move next forward, deleting old next 
    } 

Answer 2

一般に、shared_ptrはおそらくではありません。リンクリストの良いアイデアです。あなたが指摘している理由からです。この場合、おそらく は手作業で行う必要があり、各ノードの親カウントは にしてください。 （これはshared_ptrとスタックオーバーフローを回避 ループのいくつかの並べ替えを動作するように、おそらく可能ですが、 結果はおそらく手でメモリ を管理するよりも複雑になります。）