为什么 map.find 使用 < 运算符而不是 == 运算符？

Question

当试图找出我的程序有问题的原因时，我发现：

In a std::map, the keys are compared using the less-than operator < when performing a search.

（来自）。

有人知道为什么地图在执行搜索时使用 < 运算符而不是 == 运算符吗？

Answer 1

因为std::map是排序的，可以利用所有小于x的元素都位于x之前，所有大于x的元素都位于在 x 之后。这意味着你可以 binary search 来找到一个元素，这比线性搜索（即只按顺序查找每个元素）更有效。

例如，有效地查找集合中的数字 55 可能看起来像这样：

 1 1 2 3 5 8 13 21 34 55 89 144
[          ^                   ]  8 is too low

 1 1 2 3 5 8 13 21 34 55 89 144
            [      ^           ]  34 is too low

 1 1 2 3 5 8 13 21 34 55 89 144
                     [   ^     ]  89 is too high

 1 1 2 3 5 8 13 21 34 55 89 144
                     [^ ]         55 is a match!

这具有复杂性 O(log n)，而仅与 == 相比具有复杂性 O(n)。换句话说，在一百万个元素的映射中找到一个元素只需要大约 log₂(10⁶) ≈ 20 次比较，而如果我们与 == 进行比较，则需要大约 10⁶ 次比较，对于大型集合而言，巨大差异。

Answer 2

最让你困惑的可能是你提到的link中的这句话：

I have created a hash map

但是，这是不正确的。 std::map是树状图，一般用红黑树实现。

现在你的问题基本上变成了数据结构问题

红黑树是一种二叉搜索树，其中的每个节点都有以下属性：

节点的左儿子小于当前节点
节点的右儿子大于当前节点

注意，我用"less"或"greater"只是为了让你明白。更精确地，给定一个二元谓词p用于组织满足严格弱排序要求的树，我们假设当前节点为N，则：

p(N, N->left) 为真
p(N, N->right) 为假

所以现在你在树的顶端，要找到正确的节点，你需要不断比较你和当前节点的值，并决定你应该往哪个方向走。

而你可能会问为什么==不是必须的，那是因为当一个谓词p满足严格弱序的要求时，下面两个表达式是等价的（不准确，但至少是我们关心的部分about 是等价的):

一个。 !(p(A, B) || p(B, A))

乙。 A == B

你可以问问自己，当A不小于B且B不小于A时，A和B之间是什么关系？

为什么 map.find 使用 < 运算符而不是 == 运算符？

Why does map.find use < operator and not == operator?

c++

stdmap