为什么使用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,将有足够的信息来做出只用一个电话一个正确的决定.

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

除非我失去了一些东西很基本的,不应std::map与std::set使用类似compare,而不是std::less作为默认仿函数对键进行比较？

Answer 1

我决定问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个额外比较的开销更少是另一个问题.可能并不重要.但我认为比较本身应该是3值的,因此可以改变是否使用所有3种结果的决定.

更新:请参阅下面的评论,了解为什么我认为3-way比较在树中更好,但不一定在平面阵列中.

Answer 2

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

请参阅https://www.sgi.com/tech/stl/StrictWeakOrdering.html

1. 写入权限

   地图和集合的插入点完全由单个二进制搜索确定,例如lower_bound或upper_bound.二进制搜索的运行时复杂性是O(log n)

2. 读取权限

   这同样适用于搜索:搜索是远远大于线性平等扫描更高效,正是因为大多数元素并不需要进行比较.诀窍在于订购了容器.

结果是equality信息不需要存在.只是,这些项目可以有相同的顺序.

实际上,这只是意味着对元素类型的约束更少,实现需求的工作量减少以及在常见使用场景中的最佳性能.总会有权衡取舍.(例如,对于大型集合,散列表(无序集和映射)通常更有效.请注意,这些确实需要equatable元素,并且它们采用散列方案进行快速查找)