問題タブ [bimap]

最近、boost には bimap という名前の双方向マップ実装があることがわかりました。

私の最初の STL マップは、次の 2 つのタイプを使用していました。

• intキータイプとして
• std::weak_ptr<void>値の型として (と呼びましょうX)

シナリオ 1

これらのタイプで bimap を作成するには、宣言は次のようになります。

boost::bimap<int, boost::bimaps::set_of<X, std::owner_less<X>>>

std::weak_ptrより少ない演算子（ によって提供される）が必要であり、（私が正しく理解していれば）使用できるようstd::owner_lessに型にリンクされているためです。boost::bimaps::set_of

シナリオ 2

intマップの type キーが type の複数の値を指すようにしますX。

標準マップの場合、次のように値の型を からXに変更してstd::list<X>も問題ありません。 std::map<int, std::list<X>>

map<X,int>右のマップ​​ ビューが(のリストを平坦化X)として解釈され、右のマップ​​ ビューmap<int,list<X>>が

わかりましたので、boost::bimap を次のように宣言しました。

object と position は、それぞれクラスと構造体です。

Bimap に格納されている現在のオブジェクト内で、独自のエントリを見つけたいと考えています。

私は現在、次のようにしようとしています：

エラー出力の解析に問題がありますが、bimap の at 関数は、これの const 性および/または参照性が気に入らないようです (はい、これが右辺値であることはわかっています)。

この検索を行うための適切な/推奨される方法は何ですか?

エラーのスニペットを次に示します。

（seheのコメントに対処し、問題を指摘するために編集が追加されました）

私の投稿が悪いエチケットであった場合はお詫びします。私はSOに投稿するのが初めてで、すべてのコードをダンプするだけであると仮定していました（コードのこのセクションのカスタムオブジェクトとテンプレートを含めるだけで数百行になります）悪い形と見なされるので、問題を解決するために（私が思っていた）最小限に切り詰めました.

そして、テストケースのリンクに対処するために、私はテストケースを書きます. この場合、bimap のベクトルを位置コードに追加するために交換していましたが、これは実際にはコンパイルに失敗しました (スタック トレースではなく、コンパイル エラーであることを明確に述べていませんでしたが)。私はあなた (sehe) を想定していますが、ランタイム エラーについて話していると思っていました。

とにかく、エラーを再現するためにコードを実際の最小値までトリミングしていたので、ここに投稿して実際の問題に気付きました。上記のように、bimap は値<object*, position>を保持しますが、bimap に自分自身を挿入しようとしているクラスは順序クラスです: voidorder::do_thing() {

したがって、単純なタイプのエラーであることが判明しました。みなさん、本当にくだらない質問をしてすみません。午前 3 時にプロジェクトに取り組むことで得られるものだと思います。

アクティビティ用のカスタム ShowCase を実装しました

キャンバス マスクに描画しようとしています: http://i.stack.imgur.com/u23kQ.png

次のコード:

しかし、次のように表示されます。

http://i.stack.imgur.com/MhcOt.png

私は、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は私にとって正しいルートですか? 選択したコレクションと関係のタイプは正しいですか? 余談ですが、挿入時間を気にせずに、検索時間を短縮するようにマップをカスタマイズしようとしています (削除や変更は決して行われず、マップは初期化され、その後はルックアップにのみ使用されます)。代わりにカスタム データ構造を作成する必要がありますか?

複数のキーを同じ値にマップできるマップがあります。値を指定すると、この値にマップされるすべてのキーのリストを取得できるように、逆ルックアップを実行したいと思います。私のマップとは異なり Data.Bimap、1:1 ではなくn :1 であることに注意してください。

また、逆引きは、すべてのマップ エントリを実行する場合のようにO(n)を使用するのではなく、O(log n)または逆引きインデックスの場合のように使用する必要があります。マップには、追加/削除/検索操作の負荷が高い、何万ものエントリが含まれます。

そのようなデータ構造は関数形式で利用できますか (Haskell または Frege が推奨されます)?

Racket には双方向のハッシュマップがありますか?

つまり、キーを与えて値を調べるか、値を与えてキーを調べることができるハッシュ マップは一定時間でしょうか? 次のような API があれば幸いです。

記号keyと記号valは、val が与えられてキーを探していること、またはキーが与えられて val を探していることをハッシュ マップに伝えます。どちらの場合も、これを一定の O(1) 時間で実行したいと考えています。

互いに反転した 2 つのハッシュ テーブルを使用することでこれを実現できることはわかっていますが、Racket (または既存のライブラリ) に組み込まれた構造が必要です。

この質問は、ここで認める前に尋ねられましたが、今では4年前なので、あえて更新をお願いします。

タプル/ペアをコンテナーに追加し、左右の要素の両方を効率的に検索する方法が必要です。

ブーストにはbimap、multi_indexまさに私が望むことを行うものがありますが、(何らかの理由で) ブーストへの依存関係を導入したくない場合に備えて、プレーンな最新の C++-11/14 で推奨される代替手段は何だろうかと思います。

リンク先の 1 つの回答は、s.th の必要がないことを示唆しています。透明なコンパレーターにより、バイマップのようになります。受け入れられた答えは、 s を->と->std::mapの両方に組み合わせた実装を示唆しています。key1key2key2key1

ここで透過的なコンパレータがどのように役立つかはよくわかりません。これを行う方法とその理由-解決策があるかどうかに興味があります。ヒント/リンクを提供できますか?

プロジェクトに次のデータ構造を実装する必要があります。の関係があります

に

すべてのポインターに対して、それに接続されたカウンターを保存します。これは、時間の経過とともに変更できます (実際にはインクリメントのみ)。これは問題ありません。単純に std::map に格納できます。問題は、最も高い値を持つポインターにすばやくアクセスする必要があることです。

これが、boost::bimap を使用するという結論に達した理由です。私のプロジェクトでは次のように定義されています。

これは問題なく動作しますが、一度挿入されたペアの uint64_t を変更できないというのは正しいですか? ドキュメントによると、multiset_of は一定であるため、bimap でペアの値を変更することはできません。

私に何ができる？このバイマップの 1 つのキーの値を変更する正しい方法は何ですか? または、この問題に対して可能な単純なデータ構造はありますか?