如何使映射键具有两种不同的数据类型？

Question

我有一个 std::unordered_map 容器，其中 Key 可以是两种数据类型：

64 位无符号整数
具有（8 位无符号整数、8 位无符号整数、16 位无符号整数、32 位无符号整数）的元组

但值是一个对象类型，与两种键类型相同。

我尝试过的一件事是将密钥设为 std::variant，这样它就可以容纳这两种类型。基于某些条件检查，密钥被设置为以下类型之一：

void A::a() {
    std::varaint<type1, type2> Id; //key

    if (condition) {
        Id = 64 bit unsigned value;
    }
    else {
        Id = tuple<.....>;
    }
}

unorderedmap[Id] = obj1;
// ^-- gives compile-time error
// (expecting Id specialized to either of the variant types)

此外，与此函数类似，我们在 unordered_map.

上执行 find() 的多个函数

unorderedmap.find(Id);
// ^-- Here also, compiler is throwing similar error

有没有办法修复 std::variant，或者我应该使用其他方法？

Answer 1

这似乎工作得很好：

#include <iostream>
#include <unordered_map>
#include <string>
#include <variant>

typedef std::variant<int, std::string> mytype;

std::unordered_map<mytype, int> m;

int main()
{
    m[5] = 20;
    std::cout << m[5];
    m["hey"] = 10;
    std::cout << m["hey"];
    mytype tmp = "hey";
    std::cout << m[tmp];
}

所以答案基本上是：如果您尝试使用变体索引地图，请确保地图的索引具有相同的变体类型。如果您使用 get 或 this，您甚至可以在 map 是您要使用的变体的超集时使用它 - 密切模拟动态语言。

编辑：

如果你想支持std::tuple，你有几个选择。

选项 1

只需使用 std::map 而不是 std::unordered_map。你不太可能永远能够看到 logN，并且根据经验 std::map 实际上会更快（你也不会被需要一个世纪的重新哈希所谋杀，这种情况每次都会发生 std::unordered_map 必须成长）。

选项 2

继续使用 std::unordered_map，但实施散列。一个示例是 here，具有以下改编代码：

#include <iostream>
#include <string>
#include <variant>
#include <unordered_map>
// #include "custom_tuple.h"

// CUSTOM_TUPLE.h
#include <tuple>

namespace std{
    namespace
    {

        // Code from boost
        // Reciprocal of the golden ratio helps spread entropy
        //     and handles duplicates.
        // See Mike Seymour in magic-numbers-in-boosthash-combine:
        //     https://whosebug.com/questions/4948780

        template <class T>
        inline void hash_combine(std::size_t& seed, T const& v)
        {
            seed ^= hash<T>()(v) + 0x9e3779b9 + (seed<<6) + (seed>>2);
        }

        // Recursive template code derived from Matthieu M.
        template <class Tuple, size_t Index = std::tuple_size<Tuple>::value - 1>
        struct HashValueImpl
        {
          static void apply(size_t& seed, Tuple const& tuple)
          {
            HashValueImpl<Tuple, Index-1>::apply(seed, tuple);
            hash_combine(seed, get<Index>(tuple));
          }
        };

        template <class Tuple>
        struct HashValueImpl<Tuple,0>
        {
          static void apply(size_t& seed, Tuple const& tuple)
          {
            hash_combine(seed, get<0>(tuple));
          }
        };
    }

    template <typename ... TT>
    struct hash<std::tuple<TT...>> 
    {
        size_t
        operator()(std::tuple<TT...> const& tt) const
        {                                              
            size_t seed = 0;                             
            HashValueImpl<std::tuple<TT...> >::apply(seed, tt);    
            return seed;                                 
        }                                              

    };
}
// END CUSTOM_TUPLE.h

typedef std::variant<std::string, std::tuple<int, bool>> mytype;

std::unordered_map<mytype, int> m;

int main()
{
    m[std::tuple{5, false}] = 20;
    std::cout << m[std::tuple{5, false}];
    m["hey"] = 10;
    std::cout << m["hey"];
    mytype tmp = "hey";
    std::cout << m[tmp];
}

您可以将 namespace std{} 部分内的所有内容都放在 header 内，然后在任何您想要的地方包含 header （我省略了包含守卫，所以 ofc 添加照常）。如果标准赶上并实现元组散列，只需删除 header 文件。

如何使映射键具有两种不同的数据类型？

How to make a map key to be of two different data types?

c++

stdtuple

std-variant

编辑：

选项 1

选项 2