为什么 std::unordered_map 的 KeyEqual 不被其运算符==使用?

Why is the KeyEqual of std::unordered_map not used by its operator==?

提问人:Trams 提问时间:9/16/2023 最后编辑:Jan SchultkeTrams 更新时间:9/21/2023 访问量:92

问:

在下面的代码中,我定义了模板参数和 for .我希望输出是,但实际上是.为什么会这样?是因为不用于比较地图吗?HashKeyEqualunordered_map1 1 1 11 1 0 1std::equal_to<Base*>==

#include <iostream>
#include <unordered_map>

using std::cout;
using std::endl;

class Base {
public:
    int x;
    Base(int _x) : x(_x) {}

    bool operator==(const Base& another) const {
        return x == another.x;
    }
    size_t hash() const {return x;}
};

template <>
struct std::hash<Base> {
    size_t operator()(const Base& r) const {
        return r.hash();
    }
};

template <>
struct std::hash<Base*> {
    size_t operator()(const Base *r) const {
        return r->hash();
    }
};

template <>
struct std::equal_to<Base*> {
    bool operator()(const Base *r1, const Base *r2) const {
        return (*r1) == (*r2);
    }
};

int main(int, char**){
    Base b1(1);
    Base b2(2);
    Base bb1(1);
    Base bb2(2);
    cout << (b1 == bb1) << endl;

    std::unordered_map<Base, int> map1;
    map1.emplace(b1, 1);
    map1.emplace(b2, 2);
    std::unordered_map<Base, int> map2;
    map2.emplace(bb1, 1);
    map2.emplace(bb2, 2);
    cout << (map1 == map2) << endl;

    std::unordered_map<Base*, int, std::hash<Base*>, std::equal_to<Base*>> map11;
    map11.emplace(&b1, 1);
    map11.emplace(&b2, 2);
    std::unordered_map<Base*, int, std::hash<Base*>, std::equal_to<Base*>> map22;
    map22.emplace(&bb1, 1);
    map22.emplace(&bb2, 2);
    cout << (map11 == map22) << endl;

    std::unordered_map<Base*, int, std::hash<Base*>, std::equal_to<Base*>> map33;
    map33.emplace(&b1, 1);
    map33.emplace(&b2, 2);
    cout << (map11 == map33) << endl;
}
C++ STL 无序映射 语言设计

评论


答:

3赞 Jan Schultke 9/16/2023 #1

operator==绕过他们KeyEqualstd::unordered_map

与直觉相反,操作者不关心或不关心;它依赖于类型的内置运算符。==std::unordered_mapstd::hashstd::key_equal==

两个无序容器 a 和 b 比较相等,如果 和 对于从 中获取的每个等效键组,存在一个从 获得的等效键组,使得返回 。a.size() == b.size()[Ea1, Ea2)a.equal_range(Ea1)[Eb1, Eb2)b.equal_range(Ea1)is_permutation(Ea1, Ea2, Eb1, Eb2)true

- [unord.req.general] 第242页

请注意,测试相等性的范围(在您的例子中,它们将只包含一个指针)不使用它们提供给容器。它是根据 with no 来定义的,它只是使用内置运算符。KeyEqualis_permutationKeyEqual==

这样做的理由是什么?!

容器通常不考虑您提供给它们的 、(在 的情况下为 )等。所有比较运算符都简单地转发到包含的元素,这种设计是一致的,即使它有悖常理。KeyEqualLessstd::set

对于具有两个(有状态)的 2 个 s,还有另一个动机:std::unordered_mapKeyEqual

通常,计算排列是二次运算。但是,给定两个无序 使用相同哈希和键等效函数的容器,元素将被划分为 键等价组,使比较更加高效。

- N2986:无序容器的相等性比较


另请参阅 无法将 std::unorded_set 与自定义 KeyEqual 进行比较

评论

0赞 Trams 9/16/2023
我通过比较映射的大小和比较键值对来自定义比较,这工作正常。
0赞 Chris Dodd 9/16/2023
似乎在这个例子中,相等性比较函数是对KeyEqual生成的分区的细化。这意味着所有可能的键。a == bKeyEqual(a, b)
0赞 Jan Schultke 9/16/2023
@ChrisDodd你是对的,所以它是明确的。只是定义明确,以获得令人惊讶的结果。