双方向の地図について、より効率的な実装はありますか？

質問

私は簡単な 双方向マップ クラスを作成しました。 std::map インスタンスを内部的に保存し、ユーザーフレンドリーなインタフェースを提供します。

template<class T1, class T2> class Bimap
{
    std::map<T1, T2> map1;
    std::map<T2, T1> map2;
    // ...
};

• 2 倍のメモリを必要としない、より効率的な双方向マップの実装方法はありますか？

• バイマップは通常どのように実装されるのですか？

EDITです。

• bimap要素はmutableとimmutableのどちらであるべきですか？ (の要素を変更することはできません。 map1 のキーを変更する必要があります。 map2 のキーを変更する必要がありますが、キーは const であり、それは不可能です - 解決策は？）

• ユーザーがバイマップにキーと値のペアを挿入すると、バイマップはそのキーと値のペアのコピーを作成して保存し、その後内部の2番目のマップ（キーと値が反転している）はコピーせず、元のペアを指すようにすべきなのです。これはどのように実現できるのでしょうか？

EDIT 2:

Code Reviewに私が作った実装候補を掲載しました。

どのように解決するのですか？

バイマップのすべての単純な実装において、データを二重に保存することには一定の問題があります。もし、外部からのポインタのバイマップに分解することができれば、これを容易に無視することができ、単に両方のマップをフォームの std::map<A*,B*> という形式にしておけばよいのです。 A->A* のルックアップを避けるために、外部からのストレージを気にする必要があります)。しかし、どうせポインタがあるのなら、単純に std::pair<A,B> を格納する場所に A と B を別々にするのですか？

があると良いですね。 std::map<A,B*> の代わりに std::map<A*,B*> に変更することで、例えば、文字列に関連付けられた要素を、ペアを作成した元の文字列へのポインタの代わりに、同じ内容を持つ新しく作成された文字列で検索することができるようになるからです。しかし、各エントリーにキーの完全なコピーを保存し、正しいバケットを見つけるためにハッシュにのみ依存することが通例です。こうすれば、ハッシュが衝突した場合でも、返される項目は正しいものになります...。

しかし、もしあなたが素早く、そして汚くしたいのであれば、次のような方法があります。

ハキハキとした解決策です。

2つのマップを作成する std::map<size_t, A> mapA と std::map<size_t, B> mapB . 挿入時に、挿入される両方の要素をハッシュ化し、それぞれのマップのキーを取得します。

void insert(const A &a, const B &b) {
    size_t hashA = std::hash<A>(a);
    size_t hashB = std::hash<B>(b);

    mapA.insert({hashB, a});
    mapB.insert({hashA, b});
}

Lookupも同様に実装されています。

を使うことで multimap の代わりに map を使うようにし、取得したすべての要素をそれぞれ他のマップのルックアップで確認します（取得候補の b から mapA ハッシュ b を検索し mapB を探し、それが目的のキーと一致すれば、次の候補に反復する b そうでなければ、これは有効な実装です。

エントリーを比較するために使用される要素のコピー (上記参照) をストレージとしてのみ使用することで、より優れたソリューションが得られます。しかし、それを理解するのは少し難しいです。詳しく説明すると

より良い解決策です。

として2組のペアを作成します。 std::set<pair<A, B*>> と std::set<pair<B, A*>> をオーバーロードし operator< と operator== のように、ペアの最初の要素だけを考慮に入れるようにします（または、対応する比較クラスを提供します）。マップの代わりにペアのセットを作成する必要があります（内部的には同じように見えますが）。 A と B はメモリ上で一定の位置にある。を挿入すると pair<A, B> が挿入されると、それを上記のセットに適合する2つの要素に分割する。

  std::set<pair<B, A*>> mapA;
  std::set<pair<A, B*>> mapB;

  void insert(const A &a, const B &b) {
      auto aitr = mapA.insert({b, nullptr}).first; // creates first pair
      B *bp = &(aitr->first);  // get pointer of our stored copy of b
      auto bitr = mapB.insert({a, bp}).first; 
      // insert second pair {a, pointer_to_b}
      A *ap = &(bitr->first);  // update pointer in mapA to point to a
      aitr->second = ap;
  }

ルックアップがシンプルに行えるようになりました。 std::set のルックアップとポインタのデリファレンスで行えるようになりました。

このより良い解決策は、boostが使用する解決策に似ています - 彼らはペアの2番目の要素としていくつかの匿名化されたポインタを使用し、したがって reinterpret_cast s.

なお、この .second の部分のペアはmutableである必要があることに注意してください（だから、私は std::pair が使えるかどうかはわかりません）、あるいは別の抽象化されたレイヤーを追加する必要があります ( std::set<pair<B, A**>> mapA ) を追加しなければなりません。どちらの解決策でも、要素への非恒等式の参照を返すために一時的な要素が必要です。