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

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);
     }
  }

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

使用std::less时，insert函数需要先用调用std::less::operator() >key1 和 key3。假设 std::less::operator()(key1, key3) 返回 false。它必须再次调用 std::less::operator() 并切换键，std::less::operator()(key3, key1) 来决定key1 是否等于 key3 或 key3 是否大于 key1。有两次调用 std::less::operator() 来判断第一次调用是否返回 false。

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

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

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

Answer 1

我决定就此询问 Alexander Stepanov(STL 的设计师)。我可以这样引用他的话:

Originally, I proposed 3-way comparisons. The standard committee asked me to change to standard comparison operators. I did what I was told. I have been advocating adding 3-way components to the standard for over 20 years.

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

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 路比较没有可怕的开销:Branchless 3-way integer comparison .现在，在每个节点上检查比较结果与 0(相等)的额外分支是否比最后支付约 3 次额外比较的开销更少，这是另一个问题。应该没多大关系吧。但我认为比较本身应该是 3 值的，因此可以改变是否使用所有 3 个结果的决定。

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