为什么使用std::less作为默认仿函数来比较std::map和std::集中的键？

Question

我想知道为什么std：：map和std：：set使用std：：less作为比较键的默认函子。为什么不使用一个类似strcmp的函子呢？类似于：

  template <typename T> struct compare
  {
     // Return less than 0 if lhs < rhs
     // Return 0 if lhs == rhs
     // Return greater than 0 if lhs > rhs
     int operator()(T const& lhs, T const& rhs)
     {
        return (lhs-rhs);
     }
  }

假设地图中有两个对象，分别是键1和键2。现在，我们要插入另一个具有键3的对象。

如果std::map::插入使用比较，那么只需一个调用就有足够的信息来做出正确的决定。

根据映射中键的类型，std：：less：：operator（）（键1，键2）可能很昂贵。

除非我缺少一些非常基本的东西，否则不应该使用类似于比较的东西，而不是作为比较键的默认函子？

Answer 1

基于树的容器只需要严格的弱总排序。

看https://www.sgi.com/tech/stl/StrictWeakOrdering.html

>

写访问

映射和集合的插入点完全由单个二进制搜索确定，例如lower_bound或upper_bound。二进制搜索的运行时复杂性为O（log n）

读取访问权限

这同样适用于搜索：搜索比线性等式扫描效率要高得多，因为大多数元素不需要进行比较。诀窍在于容器是订购的。

结果是，不需要存在平等信息。只是，这些项目可以具有同等的顺序。

实际上，这只意味着对元素类型的约束更少，在常见使用场景中实现需求和最佳性能的工作更少。总会有取舍。（例如，对于大型集合，哈希表（无序集和映射）通常更有效。请注意，它们确实需要相等的元素，并且使用哈希方案进行快速查找）

Answer 2

我决定向Alexander Stepanov（STL的设计师）询问这件事。我可以引用他的话如下：

最初，我提出了三方比较。标准委员会要求我改为标准比较运算符。我做了别人告诉我的事。20多年来，我一直主张在标准中添加3路组件。

但请注意，也许不太直观，双向并不是一个巨大的开销。你不必做两倍的比较。在向下的过程中，每个节点只有一个比较（没有等式检查）。代价是不能提前返回（当键位于非叶中时）和在最后进行一次额外的比较（交换参数以检查相等性）。如果我没记错的话

1 + 1/2*1 + 1/4*2 + 1/8*3 + ...
= 1 + 1/2+1/4+1/8+... + 1/4+1/8+... + ...
-> 3  (depth -> infty)

在包含查询元素的平衡树上平均进行额外比较。

另一方面，3路比较没有可怕的开销：无分支3路整数比较。现在，另一个问题是，在每个节点上用一个额外的分支来检查与0（相等）的比较结果，其开销是否比在最后额外进行3次比较要小。可能没什么大不了的。但我认为比较本身应该是三值的，这样就可以改变是否使用所有三种结果的决定。

更新：请参阅下面的评论，了解为什么我认为三向比较在树中更好，但在平面阵列中不一定更好。