1 
#include <unordered_set>
#include <iostream>

class edge{
    public:
        float a1;
        float a2;

};

struct comp{
    bool operator()(const edge& e1, const edge& e2) const {
        return true;
        return (
            (e1.a1==e2.a1 && e1.a2==e2.a2) ||
            (e1.a1==e2.a2 && e1.a2==e2.a1)
        );
    };
};
struct hash{
    size_t operator()(const edge& e1) const {
        // return std::hash<float>()(e1.a1+e1.a2);
        return std::hash<float>()(e1.a1+e1.a2*2);
    };
};


int main() {
    std::unordered_set<edge,hash,comp> s1;
    s1.insert(edge{1.1,2.2});
    s1.insert(edge{2.2,1.1});
    for( auto& it : s1 ) {
        std::cout << it.a1 << " " << it.a2 << "\n";
    }
    std::cout << "s1.size " << s1.size() << "\n";
}

我意识到如果不同的元素具有相同的哈希值，那么它们被认为是相等的，但我只希望这个 unordered_set 使用我定义的比较器，只是忽略哈希？

如何做到这一点？

我知道我可以使用set，但是使用set需要考虑顺序，如果a < b 为真，b < a 也为真，那么这个元素不会插入成功，有时，很难提供顺序。

如果有人可以提供帮助，不胜感激

编辑：我的意图是让两条边称为 e1，e2，如果(e1.a1==e2.a1&&e1.a2==e2.a2)或(e1.a1==e2.a2 && e1.a2==e2.a1)与我在 struct comp 中提供的一样，它们是相同的。但是当我测试时。似乎哈希函数也可以改变比较。有人说我定义哈希和比较器的方式会导致未定义的行为。真的吗？为什么？如果是真的，如何解决这个问题？我只想让比较器决定将哪一个满足插入 unordered_set 而不重复。而且真的不关心哈希。

顺便说一句，感谢很多人回复

4

2 回答 2

3

如果你想处理edge.a1和edge.a2互换，你必须实现一个散列函数，即使它们被交换也返回相同的值。我建议不要使用加法，因为加法对于 floats 可能不是可交换的，但是您可以按大小对它们进行排序并在之后组合散列：

struct hash {
  size_t operator()(const edge& e1) const {
    auto h1 = std::hash<float>{}(std::min(e1.a1, e1.a2));
    auto h2 = std::hash<float>{}(std::max(e1.a1, e1.a2));
    return h1 ^ (h2 << 1)
  };
};

这仅对相当大的浮点数集有意义，因为否则散列开销可能超过首先使用散列数据结构的好处。

旧答案供参考：

具有相同散列的对象在 unordered_set. 它们只是存储在同一个存储桶中。有一个 用于比较的KeyEqual模板参数，默认情况下使用operator==您的Key. 所以你的主要问题是，comp应该实现e1 == e2而不是e1 < e2（并且可能应该被称为equal）。

哈希只是用来加速元素的搜索、插入和删除。

另一方面，您可能希望使用成员变量的散列而不是值本身来计算 的散列 edge：

struct hash {
  size_t operator()(const edge& e1) const {
    auto h1 = std::hash<float>{}(e1.a1);
    auto h2 = std::hash<float>{}(e1.a2);
    return h1 ^ (h2 << 1)
  };
};

这样，对于交换坐标的两条边，您将不会获得相同的哈希值。这里建议使用这种组合哈希的方法（但不是组合两个以上的好方法）。

于 2019-12-03T11:43:08.747 回答
1

您不必使用 的成员edge来提供哈希。只要求相等的值具有相等的散列。“始终有效”的哈希是

struct hash{
    size_t operator()(const edge& e1) const {
        return 0;
    };
};

但似乎你最初的尝试更好

struct hash{
    size_t operator()(const edge& e1) const {
        return std::hash<float>{}(e1.a1 + e1.a2); // + is commutative
    };
};
于 2019-12-03T11:58:06.773 回答