3

私はc ++で小さなquadedgeクラスを書こうとしています(ある種のグラフと考えてください)。すべてのノードは、近隣ノードを追跡する必要があります。出て行くアークだけを追跡する必要があります。

最初のアイデアは、ポインターを使用してそれを行うことです。

struct Node {
         //....
         Node * n1,n2,... nk;
};

ただし、このアプローチは、コピー コンストラクターを実装する必要がある場合に特に苦痛です* (最初にすべてのノードをコピーし、次に古いノードへのすべてのポインターを新しいノードへの相対ポインターにマップします)。

この場合、ポインターの代わりに整数インデックスを使用する方が良いと思います。

 struct Node {
        //....
        int n1,n2,...nk;
 };

このアプローチは一般的で正しいですか？もしそうなら、インデックスをノードにマッピングするのに適切なコンテナはどれですか?

std::vector<Node>おそらく最も効率的な方法です。ベクター内のインデックスを使用してノードを参照できますが、残念ながら、グラフからノードを削除するのは非常に複雑です (グラフ内のすべての参照をリベースする必要があります)。

を使用std::unordered_map<int,Node>する方が少し良いでしょうが、まだ自由な名前を追跡する必要があります (ノード 1、2、3 を挿入してから 2 を削除すると、名前 2 が使用可能であるという事実を追跡する必要があります)。

私が必要とするのは、ヒープの実装と非常に似ています。ベースからのオフセットをポインター型として使用するプール アロケーターを考えてみてください。

このような一般的なコンテナはありますか (Boost またはその他の一般的なライブラリ内)?

※その有用性はコピーコンストラクタに限らず、シリアライズなども考えてみてください

4

2 に答える 2

1

intすべてのインデックスを再シャッフルしない限り、コンテナーの途中でアイテムを削除または挿入できないため、コンテナーにインデックスを永続的に使用することは脆弱です。コピーまたはシリアル化操作中に一時的にインデックスを使用する方がはるかに優れています。ノードIDに依存しない操作の最初のアプローチで説明したようにポインターを使用し、ノードの一時的なID（たとえば、そのインデックス）のみを作成します必要な操作の期間。

たとえば、コピー コンストラクターでコピー操作を開始する前にvector<Node*>、 と を作成しますunordered_map<Node*,int>。2 つのパスでコピーを実行します。最初に、ベクトルへの参照を除いたノードのコピーを追加し、古いノードのアドレスをマップに追加します。次に、ノードをもう一度調べて、順序付けられていないマップからのインデックスを使用して、ベクター内の新しいノードのアドレスを検索することにより、参照を解決します。

于 2012-05-24T15:19:46.047 に答える
0

このノード ID の新しい概念を導入すると、作業が難しくなるだけだと思います。

シリアル化のために各ノードに一意の ID が必要な場合は、その時点で ID を作成するか、ノード アドレスを int にキャストします。

グラフをコピーする場合は、古いノードを新しいノードにマップする一時的な std::unordered_map を作成して、どのノードが既にコピーされているかを追跡できます。

ノードをディープ コピーする関数は再帰的になります。古いノードと新しいノードをマップに追加してから、まだマップにない隣接ノードをディープ コピーします。

于 2012-05-24T15:18:17.873 に答える