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

Question

当试图找出为什么我的程序存在错误时，我发现:

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

(来自 std::map find not working in C++)。

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

Answer 1

由于std::map已排序，因此您可以利用以下事实:所有小于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)。换句话说，在一百万个元素的映射中找到一个元素仅需要log2(106)≈20个比较，而如果我们与 ==比较，则需要约106个比较，对于大型集合而言，这是一个巨大的差异。