在bimap的所有简单实现中，双重存储数据都存在一定的问题，如果可以从外部将其分解为指针的bimap，那么你可以忽略这一点，并简单地保持形式std::map<A*,B*>的两个Map，就像Arkaitz Jimenez已经建议的（尽管与他的回答相反，你必须关心来自外部的存储，以避免A->A*查找）。但是如果你无论如何都有指针，为什么不简单地将std::pair<A,B>存储在原本要分别存储A和B的位置上呢？
用std::map<A,B*>代替std::map<A*,B*>是很好的，因为这将允许例如通过新创建的具有相同内容的字符串而不是指向创建对的原始字符串的指针来查找与字符串相关联的元素。但是习惯上是在每个条目中存储键的完整副本，并且仅依赖于散列来找到正确的桶。这样，即使在哈希冲突的情况下，返回的项也将是正确的项...
如果你想速战速决的话，有这个

黑客解决方案：

创建两个Mapstd::map<size_t, A> mapA和std::map<size_t, B> mapB。插入时，散列两个要插入的元素，以获得相应Map的键。

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});
}

类似地实现查找。
使用multimap而不是map，并在其他Map中通过查找来验证每个元素（从mapA中获取候选b，散列b并在mapB中查找是否匹配所需的键，否则迭代到下一个候选B），这是一个有效的实现-但在我看来仍然是黑客式的...
你可以通过使用比较条目的元素的副本（见上文）作为存储空间来得到一个更好的解决方案，尽管这有点难以理解，详细说明一下：

更好的解决方案：

创建两组对std::set<pair<A, B*>>和std::set<pair<B, A*>>，并重载operator<和operator==以仅考虑对的第一个元素（或提供相应的比较类）。需要创建对集而不是Map（内部看起来很相似），因为我们需要保证A和B在内存中的位置不变，在插入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_cast s。
注意，元素对中的.second部分必须是可变的（所以我不确定std::pair是否可用），或者即使对于这个简单的插入也必须添加另一个抽象层（std::set<pair<B, A**>> mapA），在这两种解决方案中，都需要临时元素来返回对元素的非常数引用。

将所有元素存储在一个向量中并具有<T1*,T2*>和<T2*,T1*>的2个Map会更高效，这样就不会将所有内容复制两次。
在我看来，你试图存储两个东西，元素本身和它们之间的关系，如果你的目标是标量类型，你可以让它保持原样，但如果你的目标是处理复杂类型，它更有意义的是将存储与关系分开，并在存储之外处理关系。

Boost Bimap利用了Boost Mutant Idiom。
从链接的维基百科页面：
Boost变体使用reinterpret_cast，并在很大程度上依赖于两个具有相同数据成员（类型和顺序）的不同结构的内存布局是可互换的这一假设。尽管C++标准并不保证这一属性，但实际上所有编译器都满足这一属性。

template <class Pair>
struct Reverse
{
    typedef typename Pair::first_type  second_type;
    typedef typename Pair::second_type first_type;
    second_type second;
    first_type first;
};

template <class Pair>
Reverse<Pair> & mutate(Pair & p)
{
  return reinterpret_cast<Reverse<Pair> &>(p);
}

int main(void)
{
  std::pair<double, int> p(1.34, 5);

  std::cout << "p.first = " << p.first << ", p.second = "  << p.second << std::endl;
  std::cout << "mutate(p).first = " << mutate(p).first << ", mutate(p).second = "  << mutate(p).second << std::endl;
}

在升压源中的实现当然是相当多毛。

如果你为你的类型std::set<std::pair<X,Y>>创建了一组对，你就基本上实现了你的功能，并且关于可变性和恒定性的规则被预设了（好吧，也许这些设置不是你想要的，但是可以做一些调整）。

#ifndef MYBIMAP_HPP
#define MYBIMAP_HPP

#include <set>
#include <utility>
#include <algorithm>

using std::make_pair;

template<typename X, typename Y, typename Xless = std::less<X>, 
                     typename Yless = std::less<Y>>
class bimap
{
    typedef std::pair<X, Y>                             key_type;
    typedef std::pair<X, Y>                             value_type;
    typedef typename std::set<key_type>::iterator       iterator;
    typedef typename std::set<key_type>::const_iterator const_iterator;

    struct Xcomp
    {
        bool operator()(X const &x1, X const &x2)
        {
            return !Xless()(x1, x2) && !Xless()(x2, x1);
        }
    };
    struct Ycomp
    {
        bool operator()(Y const &y1, Y const &y2)
        {
            return !Yless()(y1, y2) && !Yless()(y2, y1);
        }
    };
    struct Fless 
    { // prevents lexicographical comparison for std::pair, so that 
        // every .first value is unique as if it was in its own map
        bool operator()(key_type const &lhs, key_type const &rhs)
        {
            return Xless()(lhs.first, rhs.first);
        }
    };
    /// key and value type are interchangeable
    std::set<std::pair<X, Y>, Fless> _data;

public:
    std::pair<iterator, bool> insert(X const &x, Y const &y)
    {
        auto it = find_right(y);
        if (it == end()) { // every .second value is unique
            return _data.insert(make_pair(x, y));
        }
        return make_pair(it, false);
    }
    iterator find_left(X const &val)
    {
        return _data.find(make_pair(val,Y()));
    }
    iterator find_right(Y const &val)
    {
        return std::find_if(_data.begin(), _data.end(), 
            [&val](key_type const &kt)
        {
            return Ycomp()(kt.second, val);
        });
    }
    iterator end()   { return _data.end();   }
    iterator begin() { return _data.begin(); }
};

#endif

用法示例

template<typename X, typename Y, typename In>
void PrintBimapInsertion(X const &x, Y const &y, In const &in)
{
    if (in.second) {
        std::cout << "Inserted element (" 
              << in.first->first << ", " << in.first->second << ")\n";
    }
    else {
        std::cout << "Could not insert (" << x << ", " << y 
                      << ") because (" <<  in.first->first << ", " 
                      << in.first->second << ") already exists\n";
    }
}

int _tmain(int argc, _TCHAR* argv[])
{
    bimap<std::string, int> mb;
    PrintBimapInsertion("A", 1, mb.insert("A", 1) );
    PrintBimapInsertion("A", 2, mb.insert("A", 2) );
    PrintBimapInsertion("b", 2, mb.insert("b", 2));
    PrintBimapInsertion("z", 2, mb.insert("z", 2));

    auto it1 = mb.find_left("A");
    if (it1 != mb.end()) {
        std::cout << std::endl << it1->first << ", " 
                      << it1->second << std::endl;
    }

    auto it2 = mb.find_right(2);
    if (it2 != mb.end()) {
        std::cout << std::endl << it2->first << ", " 
                      << it2->second << std::endl;
    }

    return 0;
}

注意：所有这些都是完整实现的粗略代码草图，即使在完善和扩展代码之后，我也不是暗示这将是boost::bimap的替代品，而仅仅是一种自制的方法，可以通过值和键搜索关联容器。

Live example

使用中间数据结构和间接寻址的一个可能的实现是：

int sz;  // total elements in the bimap

std::map<A, int> mapA;
std::map<B, int> mapB;

typedef typename std::map<A, int>::iterator iterA;
typedef typename std::map<B, int>::iterator iterB;

std::vector<pair<iterA, iterB>> register;  
// All the operations on bimap are indirected through it.

插入

假设必须插入（X，Y），其中X、Y分别是A和B的示例，则：
1.在mapA--- O（长尺寸）中插入（X，尺寸）
1.将（Y，尺寸）插入mapB--- O（长度尺寸）
1.那么register中的push_back（IterX，IterY）--- O（1），这里IterX和IterY是mapA和mapB中对应元素的迭代器，分别由（1）和（2）获得。

查找

查找类型A的元素X的图像：
1.在mapA中获取Map到X的整数。--- O（lg n）
1.使用int来索引register并获得相应的IterY。--- O（1）
1.一旦你有了IterY，你就可以通过IterY->first得到Y。--- O（1）
所以这两个操作都是在O（lgn）中实现的。

空间：A和B的对象的所有副本只需要存储一次，但是有很多簿记的东西，但是当你有大的对象时，那也没有多大意义。
注意：这个实现依赖于Map的迭代器永远不会失效的事实。因此，register的内容总是有效的。

可以在here中找到此实现的更详细版本

这个怎么样？
这里，我们避免了一种类型（T1）的双重存储，另一种类型（T2）仍然是双重存储。

// Assume T1 is relatively heavier (e.g. string) than T2 (e.g. int family).
// If not, client should instantiate this the other way.
template <typename T1, typename T2>
class UnorderedBimap {

  typedef std::unordered_map<T1, T2> Map1;
  Map1 map1_;

  std::unordered_map<T2, Map1::iterator> map2_;
};