是否有更高效的双向映射实现？

Question

我创建了一个简单的双向映射类,它通过内部存储两个std::map具有相反键/值类型的实例,并提供用户友好的界面:

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

• 是否有更有效的方法来实现不需要两倍内存的双向映射？

• 通常如何实施bimap？

---

编辑:

• bimap元素应该是可变的还是不可变的？(更改一个元素map1应该更改键map2,但键是常量,这是不可能的 - 解决方案是什么？)

• 元素的所有权也是另一个问题:当用户在bimap中插入键值对时,bimap应该复制该键值对并存储它,然后内部第二个映射(具有反转的键/值)应该不复制,但指向原始对.怎么能实现这一目标？

---

编辑2:

我发布了一个关于Code Review的可能实现.

Answer 1

在bimap的所有简单实现中双重存储数据存在一定的问题.如果你可以把它分解成外面的指针bimap,那么你可以很容易地忽略这一点并简单地保留std::map<A*,B*>像Arkaitz Jimenez这样的形式的两张地图(虽然与他的回答相反,你必须关心外面的存储以避免一个A->A*查找).但是,如果你有指针,为什么不简单地存储一个std::pair<A,B>你将以其他方式存储A和B单独存储的点？

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

如果你想快速和肮脏,有这个

hackish解决方案:

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

查找是类似地实现的.

使用multimap的,而不是一个map数据,验证你的respectivly其他地图查找得到元素(获得候选人b从mapA散列b并查看mapB它是否有用密钥相匹配,迭代到下一个候选b以其他方式),这是一个有效的实现-但在我看来仍然是hackish ...

通过使用用于比较条目(见上文)的元素副本作为唯一存储,您可以获得更好的解决方案.尽管如此,还是有点难以理解.详细说明:

一个更好的解决方案:

创建两组对std::set<pair<A, B*>>和,std::set<pair<B, A*>>并重载operator<和operator==仅考虑对的第一个元素(或提供相应的比较类).有必要创建成对的集合而不是映射(内部看起来类似),因为我们需要保证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_casts.

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

Answer 2

将所有元素存储在向量中并且具有2个映射会更有效,<T1*,T2*>并且<T2*,T1*>不会将所有内容复制两次.

我看到它的方式你试图存储2个东西,元素本身以及它们之间的关系,如果你的目标是标量类型,你可以将其保留为2个地图,但如果你的目标是处理复杂类型,那么它更有意义将存储与关系分开,并处理存储之外的关系.

Answer 3

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

增强源中的实现当然相当多.

Answer 4

如果你为你的类型创建了一组对,std::set<std::pair<X,Y>>你几乎已经实现了你的功能和关于mutabillity和constness预设的规则(好的可能设置不是你想要的,但可以进行调整).所以这是代码:

#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而只是一种自制方式,可以通过两种方式搜索关联容器.价值和关键.

实例

Answer 5

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

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. 将（X，sz）插入mapA--- O（lg sz）
2. 将（Y，sz）插入mapB--- O（lg sz）
3. 然后push_back在register --- O（1）中输入（IterX，IterY ）。这里IterX和IterY是迭代器到相应的元件中mapA和mapB和分别从（1）和（2）获得的。

抬头

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

1. 获得映射到X整型mapA。-O（lg n）
2. 使用int索引register并获得相应的IterY。-O（1）
3. 一旦有了IterY，就可以使Y通过IterY->first。-O（1）

因此，两个操作都在O（lg n）中实现。

Space: All the copies of the objects of A and B are required to be stored only once. There is, however, a lot of bookkeeping stuff. But when you have large objects, that would also be not much significant.

Note: This implementation relies on the fact that the iterators of a map are never invalidated. Hence, the contents of register are always valid.

A more elaborate version of this implementation can be found here