35

我想知道为什么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);
     }
  }

假设 amap有两个对象，带有键key1和key2。现在我们要插入另一个带有 key 的对象key3。

使用std::less时，insert函数需要先std::less::operator()用key1and调用key3。假设std::less::operator()(key1, key3)返回假。它必须std::less::operator()在切换键的情况下再次调用std::less::operator()(key3, key1)，来决定key1是等于key3还是key3大于key1。如果第一个调用返回 false，则有两个调用来std::less::operator()做出决定。

如果std::map::insert使用compare，则只需一次调用即可获得足够的信息来做出正确的决定。

根据地图中键的类型，std::less::operator()(key1, key2)可能会很昂贵。

除非我遗漏了一些非常基本的东西，否则不应该使用类似的东西std::map而不是作为默认函子来比较键吗？std::setcomparestd::less

4

2 回答 2

24

我决定就此向 Alexander Stepanov（STL 的设计者）询问。我可以这样引用他的话：

最初，我提出了 3 路比较。标准委员会要求我改为标准比较运算符。我做了我被告知的事情。20 多年来，我一直提倡在标准中添加 3 路组件。

但请注意，也许不直观，2-way 并不是一个巨大的开销。您不必进行两倍的比较。在下降的过程中，每个节点只有一次比较（没有相等性检查）。代价是不能及早返回（当密钥在非叶子中时）和最后一次额外的比较（交换参数以检查相等性）。如果我没记错的话，那就是

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 次额外比较的开销更少，这是另一个问题。应该没多大关系吧。但我认为比较本身应该是 3 值的，因此可以改变是否使用所有 3 个结果的决定。

更新：请参阅下面的评论，了解为什么我认为 3 路比较在树中更好，但不一定在平面数组中。

于 2017-05-04T03:11:21.973 回答
17

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

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

  1. 写访问

    映射和集合的插入点完全由单个二进制搜索确定，例如lower_boundor upper_bound。二分查找的运行时复杂度为O(log n)

  2. 读取权限

    这同样适用于搜索：搜索比线性等式扫描更有效，正是因为大多数元素不需要比较。诀窍是容器是有序的。

结果是equality信息不需要存在。只是，那些项目可以有相同的 ordering。

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

于 2014-03-10T19:31:10.480 回答