1

I'd like to have an unordered_map with a struct, that I'd like to use as the key, of multiple std::set< std::string >.

I see that a custom hash function is required and that a string can have std::hash applied; however, I cannot determine what should be returned to satisfy the purpose of the hash function of these sets for an unordered_map.

How should a custom hash function return?

4

2 回答 2

2

我认为这可能是Snps 答案的更好选择。这实现了std::hash用户定义类型的特殊化，并且它在不创建临时字符串的情况下对结构进行哈希处理。

我从 Boosthash_combine和复制了两个函数hash_range，以计算来自两个容器的单个哈希值。

#include <iostream>
#include <functional>
#include <set>
#include <unordered_map>

// user-defined type
struct myStruct {
    std::set<std::string> s1;
    std::set<std::string> s2;

    bool operator==(const myStruct &other) const {
        return (s1 == other.s1) && (s2 == other.s2);
    }
};

// hash helper functions plagiarized from Boost
template <typename T>
void hash_combine(size_t &seed, const T &v)
{
    using std::hash;
    seed ^= hash<T>()(v) + 0x9e3779b9 + (seed << 6) + (seed >> 2);
}

template <typename It>
void hash_range(size_t &seed, It first, It last)
{
    for (; first != last; ++first) {
        hash_combine(seed, *first);
    }
}

// std::hash specialization
namespace std
{
    template<> struct hash<myStruct> {
        size_t operator()(const myStruct &key) const {
            size_t seed = 0;
            hash_range(seed, key.s1.begin(), key.s1.end());
            hash_range(seed, key.s2.begin(), key.s2.end());
            return seed;
        }
    };
}

int main()
{
    std::unordered_map<myStruct, int> myMap;

    myStruct ms1{ { "apple", "pear", "orange" }, { "red", "green", "blue" } };
    myStruct ms2{ { "pear", "apple", "orange" }, { "red", "green", "blue" } };
    myStruct ms3{ { "apple", "banana", "orange" }, { "red", "green", "blue" } };

    myMap[ms1] = 1;
    myMap[ms2] = 2;
    myMap[ms3] = 3;

    std::cout << myMap.size() << '\n'; // output: 2
}
于 2014-07-18T00:30:31.747 回答
1

的要求std::hash如下：（http://en.cppreference.com/w/cpp/utility/hash）

散列模板定义了一个实现散列函数的函数对象。该函数对象的实例满足 Hash。特别是，他们定义了一个operator()：

  1. 接受一个类型的参数Key。
  2. 返回一个size_t表示参数哈希值的类型值。
  3. 调用时不抛出异常。
  4. 对于两个参数k1和k2相等，std::hash<Key>()(k1) == std::hash<Key>()(k2)。
  5. 对于不相等的两个不同参数k1，应该很小的概率，接近.k2std::hash<Key>()(k1) == std::hash<Key>()(k2)1.0 / std::numeric_limits<size_t>::max()

哈希模板既是CopyConstructible又是Destructible。

所以你需要的基本上是一个函数，它返回一个std::size_t对于每个myStruct对象都是唯一的，并且对于被认为是等效的对象返回相同的值。

编辑：以下可能不是生成哈希的最可靠的方法，但它将作为如何完成它的基本示例。

一种方法是使用标准特化 for ，通过使用分隔符序列std::hash<std::string>连接每个std::set成员中的所有字符串，然后将所有生成的合并字符串连接成一个，并使用标准哈希函数返回哈希值。

如果成员不同，则合并的“超级”字符串对于每个myStruct对象都是唯一的，并且当成员与有序容器std::set不同时仍然相同。std::set

struct myStruct {
    std::set<std::string> s1;
    std::set<std::string> s2;
};

std::string mergeAllStrings(const myStruct& ms) {
    static const std::string SEPARATOR = "#¤%&"; // Some uncommon sequence.
    std::string super;
    for (const auto& s : ms.s1) {
        super += s + SEPARATOR; // Append separator.
    }
    for (const auto& s : ms.s2) {
        super += s + SEPARATOR; // Append separator.
    }
    return super;
}

int main() {
    myStruct ms1{{"apple", "pear", "orange"}, {"red", "green", "blue"}};
    myStruct ms2{{"pear", "apple", "orange"}, {"red", "green", "blue"}};
    myStruct ms3{{"apple", "banana", "orange"}, {"red", "green", "blue"}};

    std::cout << std::hash<std::string>()(mergeAllStrings(ms1)) << std::endl;
    std::cout << std::hash<std::string>()(mergeAllStrings(ms2)) << std::endl;
    std::cout << std::hash<std::string>()(mergeAllStrings(ms3)) << std::endl;
}

输出：

2681724430859750844 // Same
2681724430859750844 // Same
2942368903851914580 // Different

您现在可以创建一个哈希函子，例如：

struct MyHash {
    std::size_t operator()(const myStruct& ms) const {
        return std::hash<std::string>()(mergeAllStrings(ms));
    }
};

并将其std::unordered_map用作：

std::unordered_map<myStruct, myValue, MyHash> m;

请注意，您还应该提供自定义equal_to函子。

于 2014-07-17T22:55:12.127 回答