Effective STL理解你的排序操作[VC/C++编程]

排序一向是数据构造中的常用算法,STL供应的排序算法非常丰富,若何有效 利用就值得探究.在网上没有找到条款31的翻译,于是我自己翻译了.－－ Winter

若何举行排序?让我数数有几种办法.

一旦程序员需对容 器元素举行排序,sort算法即刻就会呈目前他的脑海(大概有些程序员会想到 qsort,但具体阅读条款46后,他们会放弃利用qsort的设法,转而利用sort算法 ).

sort是一个非常优异的算法,但并当你并不真正需求它的时刻,其实 就是一种浪费.有时你并不需求一个完好的排序（简称为全排序）.比方,你现 有一个包含Widget对象（Widget意为“小挂件”）的vector容器,并 且你想把此中质量最好的20个Widget送给你最好的客户,那么你需做的只是找出 这20个质量最好的Widget元素,剩下的并不需关心它们的次序.这时你需求的是 部份排序（相关于全排序）,恰好在算法中就有一个名副其实的部份排序函数函 数:partial_sort:

bool qualityCompare(const Widget& lhs, const Widget& rhs)
{
　　// lhs的质量不比rhs的质量差时返回true,不然返回false
}
…
partial_sort (widgets.begin(), 　　// 把质量最好的20元素
　　widgets.begin() + 20,　　　// 次序放入widgets容器中
　　widgets.end(),
　　qualityCompare);
… 　// 利用 widgets...

通过调用partial_sort,容器中开始的20个元素就是你需求的质量最好的20 个Widget,并按次序布列,质量排第一的就是widgets[0], 紧接着就是widgets [1],顺次类推.这样你便可以把质量第一的Widget送给你最好的顾客,质量第 二的Widget便可以送给下一个顾客,很便利吧,更便利的还在背面呢.

假如你只是想把这20个质量最好的Widget礼物送给你最好的20位顾客,而不需求 给他们一一对应,partial_sort在这里就有些显得大材小用了.因为在这里,你 只需求找出这20个元素,而不需求对它们本身举行排序.这时你需求的不是 partial_sort,而是nth_element.

nth_element排序算法只是对一个区 间举行排序,一向到你指定的第n个位置上放上精确的元素为止,也就是说,和 你举行全排序和nth_element排序相比,其共同点就是第n个位置是同一个元素. 当nth_element函数运行后,在全排序中应当在位置n之后的元素不会呈目前n的 前面,应当在位置n前面的元素也不会呈目前n的背面.听起来有些费解,主如果 我不得不谨严地利用我的语言来描写nth_element的功效.别焦急,呆会儿我会 给你注释为什么,目前先让我们来看看nth_element是若何让质量最好的20个 widget礼物排在vector容器的前面的:

nth_element (widgets.begin(),　// 把质量最好的20元素放在
　　widgets.begin() + 20,　　 // widgets容器的前面,
　　widgets.end(),　　// 但并不关心这20个元素
　　qualityCompare);　　//本身内部的次序

你可以看出,调用nth_element函数和调用partial_sort函数在本质上没有区 别,唯一的差别在于partial_sort把前20个元素还举行布列了,而nth_element 并不关系他们内部的次序.两个算法都实现了一样的功效:把质量最好的20个元 素放在vector容器的开始部份.

这样惹起了一个重要的问题:如果质量 一样的元素,排序算法将会若何处理呢?假定有12个元素的质量都为1（最好等 级）,15个元素的质量等级为2（质量次之）,假如要挑选20个最好的Widget, 则先选12个质量为1的元素,然后从15此中选出8个质量为2的元素.到底 nth_element和partial_sort若何从15此中选出8个,根据安在?换句话说,当多 个元素有一样的对比值时,排序算法若何决意谁先谁后?

关于 partial_sort和nth_element算法来说,你无法掌握它们,关于对比值相同的元 素它们想怎么排就怎么排（查看条款19,理解两个值相等的定义）.在我们上面 的例子中,面对需求从15个等级为2的元素选出8个增添到top 20中去,他们会任 意选取.这样做也有它的原理:假如你要求得到20个质量最好的Widget,同时有 些Widget的质量又一样,当你得到20个元素至少不比剩下的那些质量差,这已经 到达你的要求,你就不能抱怨什么了.

　　以上是“Effective STL理解你的排序操作[VC/C++编程]”的内容，如果你对以上该文章内容感兴趣，你可以看看七道奇为您推荐以下文章：