3

私は、2 つのユニークな要素セットを持つプロジェクトに取り組んでいます。1 つのセット内の要素のいずれかが、他のセット内の要素のいずれかと関連している可能性があります。

例：

セット 1: {A、B、C}

セット 2: {1、2、3、4}

許可される関係:

(ア、1) (ア、3)

(ロ、1) (ロ、4)

(C, 1) (C, 3) (C, 4)

1 つの関係は、1 対の括弧内の 2 つのセット要素として表されます。

私の特定のプロジェクトでは、両方のセットの要素がオブジェクトであり、格納されているすべてのオブジェクトへのすべての参照が 1 つのオブジェクトに解決されるようにします (たとえば、A を含むすべての関係はすべて同じオブジェクト A を参照し、同じことが関係の反対側にある他のセットへの参照)。

bimapこの問題を解決するためにブーストを使用することを考えていました。私は、bimap の左半分と右半分、および 2 つのセット間の関係に使用されるコレクションの潜在的なタイプを調べていて、どちらが正しいかを判断しようとしていました。

. _ bimap_ set_of CollectionType_bimap

ただし、実際にこれを試してみると、関係 (A, 1) を挿入した後に関係 (B, 1) を挿入できなくなります。これは、挿入が左の両方で有効でなければならないためです。そしてそれが起こるための正しい見方。この問題を修正するためにCollectionType、両方の半分の を に変更しましたmultiset_of。すべての値が適切に挿入されていますが、これbimapは、元のセットの要素のコピーが重複していることを意味しますか?

これを修正するために、bimap. リレーションシップ型のコレクション型はデフォルトで の左半分になっているので、それは間違いだとbimap思い、 と指定しました。ただし、これにより、元のセットからオブジェクトの複数のコピーが作成されるという元の問題が解決されるかどうかはわかりません。multiset_ofset_of

本当に必要なのは、セット 1 の要素に関連するセット 2 のすべてのオブジェクトを調べることだけです。ブーストbimapは私にとって正しいルートですか? 選択したコレクションと関係のタイプは正しいですか? 余談ですが、挿入時間を気にせずに、検索時間を短縮するようにマップをカスタマイズしようとしています (削除や変更は決して行われず、マップは初期化され、その後はルックアップにのみ使用されます)。代わりにカスタム データ構造を作成する必要がありますか?

4

2 に答える 2

2

これは、より直接的にモデル化されたグラフの問題であると私は思います:

struct nodeB;

struct nodeA {
    char label;
    std::vector<nodeB *> assocs;
};

struct nodeB { 
    int label;
    std::vector<nodeA *> assocs;
};

そこから、クラスで各タイプのコレクションを管理し、ノードの追加を処理して、不変条件が適切に維持されるようにする必要があると思います。

于 2015-12-23T23:37:06.017 に答える