Effective STL理解你的排序操作

假如对于全排序，你倒是可以得 到更多的控制权。一些排序算法是“稳定的”(stable)，在一个 “稳定”的排序算法中，如果两个元素有相同的值，它们的相对位置 在排序后也会保持不变。例如：如果在未排序时Widget A在Widget B之前，而且 都有相同的质量等级，那么“稳定”排序算法就可以保证在排序之后 ，Widget A仍然在Widget B之前。而非“稳定”排序算法就不能保证 这一点。

partial_sort和nth_element都不是“稳定”排序算 法，真正的“稳定”排序算法是stable_sort，从名字上看就知道它 是“稳定”的。如果你在排序的时候需要保证相同元素的相对位置， 你最好使用stable_sort，在STL中没有为partial_sort和nth_element算法提供 对应的“稳定”版本。

说到nth_element，名字确实很怪，但 是功能却是不少，除了让你找到无关顺序的top n个元素外，它还能找到某个范 围的中值，或者找到在某个特定百分点的值。

vector<Widget>::iterator begin(widgets.begin()); 　 　// widgets的第一个
　　vector<Widget>::iterator end (widgets.end()); 　//和最后一个迭代器
　　//
　　vector<Widget>::iterator goalPosition; 　// 需 要定位的那个迭代器

　　　//以下代码用来得到质量排在中间的那个元素的迭代器
　　goalPosition = begin + widgets.size() / 2; 　// 要找的那个元素应该
　　　　　　　　　　　　　　　　　　　　　　　　//在vector的中部。
　　 nth_element(begin, goalPosition, end, 　　　　// 找到容器widgets元素的 中值
　　　　　　　　　qualityCompare);　　//
　　 … // goalPosition现在指向中值元素

　　//以下代码用来得到质量排在75%的元素
　　 vector<Widget>::size_type goalOffset = 　// 计算出要找的值
　　　　0.25 * widgets.size(); 　　//离begin迭代器的距离。
　　　　//
　　 nth_element( begin, begin + goalOffset, end, 　// 得到质量排在75％的元 素
　　　　　　　　　　　　　　 qualityCompare); 　　//

　　… 　// goalPosition 现在指向质量排在75％的元素。

当你需要把一个集合由无序变成有序时，可选用sort, stable_sort或 partial_sort，当你只需得到top n或者在某个特定位置的元素，你就可以使用 nth_element。或许有时你的需求比nth_element提供的还要少，例如：你并不需 要得到质量最好的前20个Widget，而只需要识别那些质量等级为1或者等级为2的 Widget。当然，你可以对整个vector按照Widget的质量等级进行全排序，然后查 找到第一个质量等级低于等级2的元素。

问题就在于全排序太耗费资源， 而且大部分工作都是无用功。这种情况下最好选择partition算法，partition只 是给你确定一个区间，把符合特定条件的元素放到这个区间中。举例来说，要把 质量等级好于等于等级2的Widget的元素放在widget容器的前端，我们可以定义 一个用于识别Widget质量等级的函数：

bool hasAcceptableQuality(const Widget& w)
　　{
　　　　//如 果w的质量等于或好于2，返回true，否则返回false
　　}

然后把这个判断函数传递给partion算法：

vector<Widget>::iterator goodEnd = 　// 把所有满足 hasAcceptableQuality
　　partition(widgets.

凌众科技专业提供服务器租用、服务器托管、企业邮局、虚拟主机等服务，公司网站：http://www.lingzhong.cn 为了给广大客户了解更多的技术信息，本技术文章收集来源于网络,凌众科技尊重文章作者的版权，如果有涉及你的版权有必要删除你的文章，请和我们联系。以上信息与文章正文是不可分割的一部分,如果您要转载本文章,请保留以上信息，谢谢!