C++の低速再帰デストラクタコール

Question

私はC++を使用していますが、参照カウントされたオブジェクトを使って大きなグラフを表現しています。ような何か：

// Public class 
class Pointer{ 
    public: 
    // Constructors 
    Pointer(...){ node = ...; node->counter++;} 

    // Copy constructor 
    Pointer(Pointer& const other){ node = other.node; node->counter++;} 

    // Destructor 
    ~Point(){ if(--node->counter==0) delete node;} 

    // Other methods 
    ... 

    Node* node; 
}; 

// Node base class 
class Node{ 
    // Constructor 
    Node():counter(0){} 

    // Destructor 
    virtual ~Node(){} 

    // public: 
    unsigned long counter; 
}; 

// Node derived class 
class NodeDerived : public Node{ 
    // Constructors and other methods 
    ... 

    // Destructor 
    virtual ~NodeDerived(){ ... } 

    // Children 
    Pointer children[2]; 
}; 

多型クラスのノードへのポインタを含むパブリッククラスPointerとされています。 Nodeから派生したクラスには、新しいPointerインスタンスが含まれます。いくつかのPointerインスタンスが同じNodeインスタンスを指している可能性があることに注意してください。

私はこのクラスを使用して、数百万のインスタンスを持つ非常に大きなグラフを構築しています。これはうまくいきます。この問題は、グラフを削除するときに発生します。デフォルトのデストラクタ実装では、スタック・オーバーフローが発生します。これは、ルート・ノードのデストラクタでは、子のデストラクタがコールされ、子のデストラクタでは、子の子のデストラクタがコールされるなどです。

上記のNodeDerivedクラスのデストラクタを実装することで、スタックを使用して再帰呼び出しを避けることでこれを解決しました。これは動作しますが、まだ非常に遅いですし、私はこれをスピードアップする方法を探しています。どうやらメモリリークを引き起こすことなくデストラクタ宣言を避けることが可能ですか？virtual？

Answer 1

破壊中に数百万のオブジェクトとスタックオーバーフローを処理する場合、重複する値を許可せず繰り返しをサポートするいくつかのタイプのコンテナ内のすべてのノードオブジェクトへのポインタを格納し、 std::setまたはstd::unordered_setのようになります。次に、グラフノード自体では、接続されたグラフノードへのポインタのみを格納します。グラフの削除時には、ノードを削除するために各グラフノードのポインタを再帰的に実行しないでください...代わりに、グラフ全体のノードセットへのポインタを含むコンテナに移動し、コンテナを反復処理します各ノードを1つずつ破棄します。グラフノードが接続されているすべてのノードを破壊するために、各グラフノードのポインタセットに「追従する」必要がないので、再帰は必要ありません。 std::shared_ptrのスペースと時間のオーバーヘッドについても心配する必要はありません。

Answer 2

ノードを個別に削除しない場合は、参照カウントの代わりにmemory poolを使用することを検討してください。メモリプールを使用すると、グラフ全体が急速に吹き飛ばされます（プールの種類によっては、グラフ全体が破棄されるまで個々の削除されたオブジェクトが使用するメモリを回復できない可能性があります）。

Answer 3

メモリリークを起こすことなくデストラクタを仮想宣言しないようにすることはできますか？

私は、ポインタの静的な型と一致しない指示先の動的な型とポインタにdelete pを呼び出すときに、より正確に、あなたは未定義の動作を避けることができないではない怖いです。

が、私はそれはそれは方法だ怖いまだ

非常に遅いです。数百万のオブジェクトを削除するのに時間がかかるでしょう。あなたはそれを回避することができます。例えば個々のオブジェクトの破壊を避けることによって、それらをすべてプールに入れて（そして、それを全体として）廃棄します。あなたの破壊的なニーズが何であるかによって異なります。