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

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

在 boost 源中的实现当然是相当复杂的。

---

如果您为您的类型创建一组对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 的替代品，而只是 < strong>自制 方法，通过值和键搜索关联容器。

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 的实例，那么：

在 mapA 中插入 (X, sz) --- O(lg sz) 在 mapB 中插入 (Y, sz) --- O(lg sz) 然后在寄存器中 push_back (IterX, IterY) --- O(1)。这里 IterX 和 IterY 是 mapA 和 mapB 中对应元素的迭代器，分别从 (1) 和 (2) 获得。

抬头

查找类型 A 的元素 X 的图像：

获取映射到 mapA 中 X 的 int。 --- O(lg n) 使用 int 索引到寄存器并得到对应的 IterY。 --- O(1) 一旦有了IterY，就可以通过IterY->first 得到Y。 --- O(1)

所以这两个操作都是在 O(lg n) 中实现的。

空间：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_;
};

---