双向地图是否有更有效的实现？

在bimap的所有简单实现中，将数据加倍存储存在一定的问题。如果您可以将其分解为外部的指针双图，则可以轻松地忽略它，只需保留std::map<A*,B*>Arkaitz Jimenez已经建议的两种形式的地图（尽管与他的回答相反，您必须从外部考虑存储以避免）一个A->A*查找）。但如果你有指针，无论如何，为什么不直接存储std::pair<A,B>在您原本存放点A，并B分别？

最好不要使用它std::map<A,B*>，std::map<A*,B*>因为这将允许例如通过具有相同内容的新创建的字符串（而不是指向创建该对的原始字符串的指针）查找与字符串关联的元素。但是习惯上是在每个条目中存储密钥的完整副本，并且仅依靠散列来找到正确的存储桶。这样，即使在哈希冲突的情况下，返回的项目也将是正确的...

如果您想让它又快又脏，那就有

破解解决方案：

创建两个地图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});
}

查找是类似实现的。

使用amultimap代替amap并通过在其他映射中进行查找来验证您获得的每个元素（从中获取候选，b从mapAhash中b查找，mapB如果匹配所需键，则查找，否则迭代到下一个候选b），这是有效的实现-但在我看来仍然有点黑...

通过使用用于比较条目（参见上文）的元素的副本（仅作为存储），您可以获得更好的解决方案。但是，要想解决这个问题比较困难。详细说明：

更好的解决方案：

创建两个对std::set<pair<A, B*>>和，std::set<pair<B, A*>>并重载operator<和，operator==以仅考虑对的第一个元素（或提供相应的比较类）。有必要创建成对的集合，而不是创建映射（内部看起来相似），因为我们需要保证A并将B位于内存中的恒定位置。插入a后，pair<A, B>我们将其分为适合上述集合的两个元素。

  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使用的解决方案-即使它们使用一些匿名的指针作为该对的第二个元素，因此必须使用reinterpret_casts。

请注意，这些.second对中的一部分需要是可变的（因此我不确定是否std::pair可以使用），或者std::set<pair<B, A**>> mapA即使是这种简单的插入，也必须添加另一层抽象（）。在这两种解决方案中，您都需要临时元素来返回对元素的非常量引用。