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

问题描述

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

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?

    通常如何实现bimap？

    How is a bimap usually implemented?

    编辑：

    
    bimap元素应该是可变的还是不可变的？ （更改 map1 中的一个元素应该更改 map2 中的键，但是键是const，这是不可能的 - 什么是解决方案？）

    • 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?)

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

    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?

    编辑2：

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

    推荐答案

    有一个问题在双折扣的所有简单实现中双重存储您的数据。如果你可以把它分解成外部的指针，那么你可以很容易地忽略这一点，只需保留两种形式的地图： std :: map< A *，B *> 像Arkaitz Jimenez已经建议（尽管与他的答案相反，你必须关心从外面的存储，以避免一个 A-&A; a * 查找）。但是，如果你有指针，为什么不把 std :: pair< A，B> 存储在你另外存储的位置。 和 B 分开？

    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?

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

    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

    
    

    黑客解决方案：

    创建两个地图 std :: map< size_t，A> mapA 和 std :: map< size_t，B> mapB 。插入时将要插入的两个元素都填入相应地图的键。

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

    查找是类似的。

    使用 multimap 而不是映射并验证每个元素在相应的其他地图中查找（从 mapA 获得候选 b ，哈希 b ，并且查找 mapB 如果匹配所需的密钥，则迭代到下一个候选者b否则）这是一个有效的实现 - 但仍然在我的意见...

    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:

    
    

    更好的解决方案：

    创建两组对 std :: set< pair< A，B *>> 和 std :: set< pair< B ，A *> ，并将运算符< 和 operator == 只考虑对的第一个元素（或提供相应的比较类）。有必要创建一组对而不是地图（内部看起来类似），因为我们需要保证 A 和 B 将永远在内存中相同的位置。在插入对< A，B> 之后，我们将其拆分成两个适合上述集合的元素。

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

    
    
    

    
    

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

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

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

    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.

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

    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屋！