Skip to content
TheChatArchiveThe Chat Archive
gpt-3.5-turbo-0301· openaiHugging Face Suzhen/CodeChat

拥有2个string 类型变量的自定义 struct,作为std::unordered_map的key

  1. User

    拥有2个string 类型变量的自定义 struct,作为std::unordered_map的key

  2. Assistant

    可以这样定义自定义 struct:

    struct MyKey {
        std::string str1;
        std::string str2;
    
        bool operator==(const MyKey& other) const {
            return (str1 == other.str1 && str2 == other.str2);
        }
    };
    

    在这里我们重载了 == 运算符,以便在 std::unordered_map 中使用自定义 struct 作为 key 时进行比较。假设我们已经定义了这个自定义 struct,则可以这样使用 std::unordered_map:

    std::unordered_map<MyKey, int> myMap;
    

    其中泛型类型 <MyKey, int> 分别代表 key 的类型和 value 的类型。我们可以通过下面的方式向这个 map 中添加 key 和 value:

    MyKey key = {"hello", "world"};
    int value = 42;
    
    myMap.insert(std::make_pair(key, value));
    

    或者,我们也可以这样访问和修改 map 中的值:

    MyKey key = {"hello", "world"};
    
    if (myMap.find(key) != myMap.end()) {
        myMap[key] = 66;
    }
    

    在这里我们使用了 std::map::find 函数来查找这个自定义 struct;如果找到了,则可以通过访问 myMap[key] 来获取或修改对应的 value。

  3. User

    拥有2个string 类型变量的自定义 struct,作为std::unordered_map的key,生成hash函数

  4. Assistant

    在使用自定义 struct 作为 std::unordered_map 的 key 时,需要提供一个 hash 函数将 key 转换成一个整数以便于快速查找。我们可以通过重载 std::hash 模板的 operator() 函数来自定义 hash 函数。下面是一个例子:

    #include <unordered_map>
    #include <string>
    
    struct MyKey {
        std::string str1;
        std::string str2;
    
        bool operator==(const MyKey& other) const {
            return (str1 == other.str1 && str2 == other.str2);
        }
    };
    
    struct MyKeyHash {
        std::size_t operator()(const MyKey& k) const {
            return std::hash<std::string>{}(k.str1) ^ (std::hash<std::string>{}(k.str2) << 1);
        }
    };
    
    int main() {
        std::unordered_map<MyKey, int, MyKeyHash> myMap;
    
        // Add some key-value pairs
        myMap.emplace(MyKey{"hello", "world"}, 42);
        myMap.emplace(MyKey{"foo", "bar"}, 123);
    
        // Access the values
        std::cout << myMap[MyKey{"hello", "world"}] << std::endl;  // should print "42"
        std::cout << myMap[MyKey{"foo", "bar"}] << std::endl;  // should print "123"
    
        return 0;
    }
    

    在这个例子中,我们定义了一个叫做 MyKeyHash 的结构体,该结构体重载了 std::hash 模板的 operator() 函数,用于生成 MyKey 对象的 hash 值。在 MyKeyHash 的 operator() 函数中,我们分别对 str1 和 str2 的 hash 值进行按位异或和移位操作,并将它们结合起来生成最终的 hash 值。

    注意,在定义 std::unordered_map 时,我们要指定第三个模板参数为 MyKeyHash,告诉编译器使用我们自定义的 hash 函数。

  5. User

    上面的问答中,std::hash的结果为什么要左移1位

  6. Assistant

    在 MyKeyHash 中,我们将 std::hash<std::string>{}(k.str2) 的结果左移了 1 位。这是因为我们想尽可能利用 str1 和 str2 的信息来生成 hash 值,而不是将它们拼在一起直接做 hash。因此我们将 str2 的 hash 值左移了一位,使得它在 str1 的 hash 值基础上能够带来额外的影响,增加 hash 的随机性。

    当然,这个左移的幅度是可以调整的,根据实际情况可以适度增加或减小。需要注意的是,如果左移的幅度过大,可能会导致产生的 hash 值越来越接近偶数,失去了 hash 的随机性。因此在实际应用中需要慎重选择合适的偏移量。

  7. User

    有没有用于hash table 的通用的自定义结构体的hash实现

  8. Assistant

    对于一些通用的自定义结构体,可以参考以下的 hash 函数实现:

    #include <algorithm>
    #include <functional>
    #include <string>
    
    struct MyStruct {
        int intField;
        std::string strField;
    
        bool operator==(const MyStruct& other) const {
            return (intField == other.intField && strField == other.strField);
        }
    };
    
    struct MyStructHash {
    private:
        std::size_t hash_combine(std::size_t h1, std::size_t h2) const {
            return h1 ^ (h2 + 0x9e3779b9 + (h1 << 6) + (h1 >> 2));
        }
    
    public:
        std::size_t operator()(const MyStruct& s) const {
            std::size_t h1 = std::hash<int>{}(s.intField);
            std::size_t h2 = std::hash<std::string>{}(s.strField);
            return hash_combine(h1, h2);
        }
    };
    

    在这个例子中,我们定义了一个叫做 MyStruct 的结构体,里面包含一个 int 类型和一个 string 类型的成员变量。我们还定义了一个叫做 MyStructHash 的结构体,该结构体重载了 std::hash 模板的 operator() 函数,用于生成 MyStruct 对象的 hash 值。

    这个 MyStructHash 是经过优化过的通用 hash 函数的实现,其中包含了基于 hash_combine 函数的简单散列函数,该函数将 h1 和 h2 的 hash 值结合起来生成最终的 hash 值。在实现中,我们使用了一种叫做 MurmurHash 的算法,以提高 hash 的质量和性能。

    需要注意的是,这个 hash 函数的实现是通用的,也就是说它适用于比较通用的自定义结构体,但是在实际应用中,需要根据自定义结构体的具体情况进行调整。比如,可以根据自定义结构体的成员变量数目和类型的不同,选择不同的 hash 算法和结合方式。

Responses were produced in different, uncontrolled contexts (system prompts, settings, prior turns). This is not a benchmark.