关联容器(STL)中的平等评估

Question

我知道STL关联容器(以及我猜的其他容器正在排序)使用排序标准来测试相等性.

容器的排序标准默认为st :: less,因此将对容器进行相等性测试:

if (! (lhs < rhs || rhs < lhs))

或类似的东西.我对此有几个问题......

首先,它似乎是比较平等的一种奇怪的低效方式 - 为什么STL会这样做？我原本期望STL容器只是为了相等而采用额外的默认参数.

我的第二个问题更多是关于对上述if语句的评估.在C++中,将评估该语句的多少(lhs> rhs)是真的？它会在评估失败的一方后停止尝试,从而节省一些效率吗？如果是这样,首先评估表达式的哪一部分？

Answer 1

在"有效STL"中,Scott Meyers在第19项中对此进行了广泛的讨论:

理解平等和等同之间的区别.

正如您所料,平等是基于operator==.

等价 "基于排序范围内对象值的相对排序...如果两个对象c在c排序顺序中都不在另一个之前,则它们在容器中具有等价值."

迈耶斯用这种方式表达出来:

!( w1 < w2 ) // it's not true that w1 < w2
&&           // and
!( w2 < w1 ) // it's not true that w2 < w1

迈耶斯随后重申:

这是有道理的:如果两个值都不在另一个之前(根据该标准),则两个值是等价的(相对于某些排序标准).

至于为什么STL这样做:

通过仅使用单个比较函数并使用等价作为"相同"的仲裁器,标准关联容器......避免了在标准关联中混合使用等同和等价的混淆容器.

阅读第19项(涵盖6页的较好部分),让自己获得完整的味道.

Answer 2

STL关联容器

您的意思是:标准C++排序的关联容器.

我原本期望STL容器只是为了相等而采用额外的默认参数.

会有什么成就？在你的教科书红黑树算法中,而不是

if (x < y)
    // ...
else if (y < x)
    // ...
else
    // equality

你有

if (x == y)
    // equality
else if (x < y)
    // ...
else
    // y < x

所以在最坏的情况下还是两个比较.

回应对这个答案的评论:只提供一个小于运算符使容器更容易使用,因为不需要保持小于和等于之间的一致性.让我们假设您有一个存储浮点数的程序.有一天,有人决定替换bitwise-equality float_equals函数,它恰好被一些容器使用,但也被它们的代码使用,通过近似的比较.如果那个人没有更新该float_less功能,因为他们的代码不使用该功能,那么你的容器代码会神秘地破坏.

(哦,在所示的示例代码中,一如既往地应用短路.)