比较运算符, Min, Max, Sort 和 Order

惭愧,突然发现又是没有blog的一年。这一年不断在尝试搞大新闻,写点大东西,到现在也没憋出来。倒是又在学习新东西的过程中看到了一些零碎的小知识,很有意思.

很巧,这个也是和比较运算符相关的,和一年前的blog竟然有所重合。

还是先上结论:
1. min 和 max 一般应当基于 rhs < lhs 实现,以便于和升序排序配合使用.
2. 逻辑运算符应当尽可能保证语义整体一致,例如 !(a < b) && !(b < a) <=> b==a

template <class T> T &min(T &lhs, T &rhs) { 
  return rhs < lhs ? rhs : lhs; 
}

template <class T> T &max(T &lhs, T &rhs) { 
  return rhs < lhs ? lhs : rhs; 
}

这个结论第一眼看上去。。。 总感觉有点毫无卵用? 一般情况下,确实如此,这样实现的主要优势是能保证在一些极端场合代码的一致性。

考虑下面的代码.

template <class T> 
T &min(T &lhs, T &rhs) { 
  return lhs < rhs ? lhs : rhs; 
}

template <class T> 
T &max(T &lhs, T &rhs) { 
  return lhs < rhs ? rhs : lhs; 
}

template <class T>
void SortSwap(T &a, T &b){
   if (b < a) swap(a,b);
   assert(a == min(a,b));
   assert(b == max(a,b))
}

在一些极端场合下,上面的assert会fail。

例如, operator<operator= 语义全局上不一致时就会这样(也就是 a<b == falseb<a == falsea!=b时), 读者可以自己推理验证。

举个例子,我们实现了某种优先级结构(允许相同优先级),所以有了

sturct PrirorityNode{
 int prio;
 Data* data;
}

很自然的,我们用成员prio来确定优先级,并基于此进行排序,就会触发上面的assert.

解决方案则就是开头的结论, 背后的理论也很有意思, 可以参考Notes on Programming

拓展

对于下面的代码, 就是另外一种场景了, 这也是为什么标准库提供的所有工具默认都是升序排序. 降序排序最好是通过 reverse iterate 来达成.

template <class T>
void ReverseSortSwap(T &a, T &b){
   if (a < b) swap(a,b);
   assert(a == max(a,b));
   assert(b == min(a,b))
}

发表评论

邮箱地址不会被公开。 必填项已用*标注