c++ - cpp unordered_set 只使用比较器而不是散列

Question

#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) 正如我提供的在结构比较中。但是当我测试时。哈希函数似乎也可以改变比较。有人说我定义散列和比较器的方式会导致未定义的行为。真的吗？为什么？如果是真的，如何解决这个问题？我只希望比较器决定将哪个插入到 unordered_set 中而不重复。并且真的不关心哈希。

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

Answer 1

如果你想处理edge.a1和 edge.a2可互换地，您必须实现一个哈希函数，即使它们被交换也能返回相同的值。我建议不要使用加法，因为 addition may not be commutative for 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)
  };
};

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

引用旧答案:

Objects with the same hash are not considered equal in unordered_set. They are just stored in the same bucket. There is a KeyEqual template parameter for the comparison, which by default uses the operator== of your Key. So your main problem is, that comp should implement e1 == e2 and not e1 < e2 (and should probably be called equal).

The hash is just used to speed up the search, insertion, and removal of elements.

On another note, you may want to use the hashes of the member variables instead of the values themselves to compute the hash of 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)
  };
};

This way, you won't get the same hash for two edges with swapped coordinates. This way of combining hashes is suggested here (but is not a good way to combine more than two).