现在的位置: 首页 > 综合 > 正文

关于c++中strict weak ordering的一些笔记

2013年10月01日 ⁄ 综合 ⁄ 共 811字 ⁄ 字号 评论关闭

STL中某些算法,比如sort,binary_search等,都要求对象有一个良好定义的strict weak ordering。严格弱序是一种严格偏序,但是满足一个额外的条件,即对于集合中的两个元素x,
y,满足以下条件,

即若x, y之间没有可比性,那么x和y等价。若还存在元素z,使得 x ~ z 或者 y ~ z,那么x ~ y ~ z,这是传递性。

显然,对于任意一个元素x,x与x自身是等价的(根据严格弱序的定义)。

c++中使用严格弱序来定义等价,而不是利用==来定义,这样我们只需要保证一个良好定义的<,就能够保证sort的正确性。

有时候我们的对象拥有多个可以比较的成员时(多个主键),我们该如何定义呢?我们知道如何比较string,string是根据逐个字符的比较来确定之间的顺序。比如对于abc, abd,我们先比较前两个字符,发现相等,于是我们比较最后一个字符发现c < d,于是abc < abd,这就是字典序(lexicographical order)。我们也可以采用类似的思路来对多个主键进行比较,但是需要注意相等这个概念,在严格弱序中,这个被称为等价,而用
< 来表示这个等价关系,即有

所以,假设有两个对象a, b,并且有主键

如果我们能够找到一个j,使得j满足

并且有q,满足

那么

参考:

[1] http://en.wikipedia.org/wiki/Weak_ordering

[2] http://en.wikipedia.org/wiki/Equivalence_class

[3] http://www.sgi.com/tech/stl/StrictWeakOrdering.html (注意,这里对于严格弱序的定义中使用了antisymmetric,这个是不对的,应该是非对称,即asymmetric)。

[4] http://www.drdobbs.com/author/Andrew-Koenig(这里有关于ordering的好几篇文章)

抱歉!评论已关闭.