是否有更有效的实现双向地图？ [英] Is there a more efficient implementation for a bidirectional map?

问题描述

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

 模板< class T1，class T2> class Bimap 
 {
 std :: map< T1，T2> map1; 
 std :: map< T2，T1> map2; 
 // ... 
}; 
  

• 是否有更有效的方法来实现双向地图




• 通常如何实现bimap？

---

编辑：

• bimap元素应该是可变的还是不可变的？ （更改 map1 中的一个元素应该更改 map2 中的键，但键是常量，




• 元素所有权也是另一个问题：当用户在bimap中插入键值对时，bimap应该制作该键值对的副本并存储，然后内部第二个映射（具有反向键/值）不应该复制，而是指向原始对。

---

我发布了一个可能的实现我对代码审查。

解决方案

在bimap的所有简单实现中双重存储您的数据。如果你可以把它分解为从外部指针的一个指针，那么你可以很容易地忽略这一点，只需保留形式 std :: map 像Arkaitz Jimenez已经建议的（虽然与他的回答相反，你必须关心从外部的存储，以避免 A-> A * 查找）。但是如果你有指针，为什么不直接存储 std :: pair< A，B> ，否则会存储 A 和和 B ？





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

如果你想要它快速和脏，

创建两个maps 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 而不是映射在相应的其他映射中获取查找（从 mapA 获取候选 b ，hash b 如果它匹配所需的键，迭代到下一个候选b）。这是一个有效的实现 - 但仍然在我的意见...

您可以通过使用用于将条目（见上文）仅作为存储进行比较的元素的副本来获得更好的解决方案。这是一个有点难以让你的头，虽然。详细说明：

更好的解决方案：

创建两组对 std :: set< pair< A，B *> 和 std :: set< pair< B ，A *> 并且重载运算符和运算符== 仅考虑对的第一元素（或提供相应的比较类）。有必要创建一组对而不是地图（内部看起来类似），因为我们需要保证 A 和 B 将始终在内存中的相同位置。在插入对< 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}）。 //创建第一个对
 B * bp =&（aitr-> first）; //获取我们的存储副本的指针b 
 auto bitr = mapB.insert（{a，bp}）。 
 //插入第二对{a，pointer_to_b} 
 A * ap =&（bitr-> first）; // update pointer in mapA to point to a 
 aitr-> second = ap; 
} 
  





Lookup现在可以通过简单的 std :: set 查找和指针取消引用。

类似于boost使用的解决方案 - 即使他们使用一些匿名的指针作为对的第二个元素，因此必须使用 reinterpret_cast s。

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

I created a simple bidirectional map class that works by internally storing two std::map instances, with opposite key/value types, and providing an user-friendly interface:

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

• Is there a more efficient method of implementing a bidirectional map that doesn't require twice the memory?

• How is a bimap usually implemented?

---

EDIT:

• Should bimap element be mutable or immutable? (Changing one element in map1 should change the key in map2, but keys are const and that's impossible - what's the solution?)

• Ownership of elements is also another problem: when an user inserts a key-value pair in the bimap, the bimap should make a copy of that key-value pair and store it, then the internal second map (with inverted key/value) should not copy but point to the original pair. How can this be achieved?

---

EDIT 2:

I've posted a possible implementation I made on Code Review.

解决方案

There is a certain problem with double-storing your data in all simple implementations of a bimap. If you can break it down to a bimap of pointers from outside, then you can readily ignore this and simply keep both maps of the form std::map<A*,B*> like Arkaitz Jimenez already suggested (though contrary to his answer you have to care about the storage from outside to avoid a A->A* lookup). But if you have the pointers anyway, why not simply store a std::pair<A,B> at the point where you would otherwise store A and B separately?

It would be nice to have std::map<A,B*> instead of std::map<A*,B*> as this would allow for example the lookup of an element associated to an string by a newly created string with the same content instead of the pointer to the original string that created the pair. But it is customary to store a full copy of the key with every entry and only rely on the hash to find the right bucket. This way the returned item will be the correct one even in the case of a hash-collision...

If you want to have it quick and dirty though, there is this

hackish solution:

Create two maps std::map<size_t, A> mapA and std::map<size_t, B> mapB. Upon insertion hash both elements that are to be inserted to get the keys to the respective maps.

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 is implemented analogously.

Using a multimap instead of a map and verifying every element you get with a lookup in the respectivly other map (get candidate b from mapA, hash b and look in mapB if it matches the wanted key, iterate to the next candidate b otherwise) this is a valid implementation - but still hackish in my opinion...

You can get a much nicer solution by using the copies of the elements that are used to compare the entries (see above) as only storage. It is a bit harder to get your head around that though. To elaborate:

a nicer solution:

Create two sets of pairs as std::set<pair<A, B*>> and std::set<pair<B, A*>> and overload the operator< and operator== to only take the first element of the pairs into account (or provide an corresponding comparion class). It is necessary to create sets of pairs instead of maps (which internally look similarly) because we need a guarantee that A and B will always be in the same positions in memory. Upon insertion of an pair<A,B> we split it into two elements that fit into the above sets.

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

Lookup can now simply be done by a simple std::set lookup and a pointer dereference.

This nicer solution is similar to the solution that boost uses - even though they use some annonymized pointers as second elements of the pairs and thus have to use reinterpret_casts.

Note that the .second part of the pairs need to be mutable (so I'm not sure std::pair can be used), or you have to add another layer of abstraction (std::set<pair<B, A**>> mapA) even for this simple insertion. In both solutions you need temporary elements to return non-const references to elements.

这篇关于是否有更有效的实现双向地图？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！