Effective STL领略你的排序操纵

副标题#e#

排序一直是数据布局中的常用算法，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个元素至少不比剩下的那些质量差，这已经 到达你的要求，你就不能诉苦什么了。

#p#副标题#e#

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

#p#分页标题#e#

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.begin(), 　　// 条件的放在widgets容器的前面，
　　widgets.end(), 　// 返回第一个不满意条件的
　　hasAcceptableQuality); 　//元素的位置

这样一来，所有在迭代器widgets.begin()和迭代器goodEnd之间的元素都是 满意需求的元素：其质量品级好于或便是2。而在 goodEnd 到 widgets.end() 之间的元素的质量品级城市低于质量品级2。假如你对证量品级沟通元素的相对 位置很体贴的话，你可以选择stable_partition算法来取代partition。

#p#副标题#e#

需要留意的是sort, stable_sort, partial_sort, 和nth_element算法都需要以 随机迭代器(random access

iterators)为参数，因此这些算法能只能用 于vector, string, deque, 和array等容器，对付尺度的关联容器map、set、 multmap、multset等，这些算法就有须要用了，这些容器自己的较量函数使得容 器内所有元素一直都是有序分列的。对付容器list，看似可以用这些排序算法， 其实也是不行用的（其iterator的范例并不是随机迭代器），不外在需要的时候 可以利用list自带的排序函数sort(有趣的是list::sort函数和一个“不变 ”排序函数的结果一样)。假如你想对一个list容器利用partial_sort或 nth_element，你只能间接利用。一个可选的要领是把list中的元素拷贝到带有 随机迭代器的容器中，然后再利用这些算法；另一种是生成一个包括 list::iterator的容器，直接对容器内的list::iterator举办排序，然后通过 list::iterator获得所指的元素；第三种要领，借助一个包括iterator的有序容 器，然后重复把list中的元素毗连到你想要链接的位置。瞥见了吧，你可以选择 的方法照旧较量多的。

#p#分页标题#e#

partition 和stable_partition函数与sort、 stable_sort、partial_sort、nth_element纷歧样，要求没有那么严格，输入参 数只需是双向迭代器(bidirectional iterator)。因此你可以对所有的尺度序列 容器利用partition和stable_partition算法。

让我们来总结一下你的排 序操纵：

若需对vector, string, deque, 或 array容器举办全排序，你 可选择sort或stable_sort；

若只需对vector, string, deque, 或 array容器中取得top n的元素，部门排序partial_sort是首选.

若对付 vector, string, deque, 或array容器，你需要找到第n个位置的元素可能你需 要获得top n且不干系top n中的内部顺序，nth_element是最抱负的；

若 你需要从尺度序列容器可能array中把满意某个条件可能不满意某个条件的元素 分隔，你最好利用partition或stable_partition；

若利用的list容器， 你可以直接利用partition和stable_partition算法，你可以利用list::sort代 替sort和stable_sort排序。若你需要获得partial_sort或nth_element的排序效 果，你必需间接利用。正如上面先容的有几种方法可以选择。

别的，你 可以利用尺度的关联容器来担保容器中所有元素在操纵进程中一直有序。你还可 思量非尺度的STL容器priority_queue，它同样可以担保其元素在所有操纵进程 中一直有序(priority_queue在传统意义上属于STL的一部门，但按照 “STL”界说，需要STL容器支持迭代器，而priority_queue并不支持 迭代器，故不能能称为尺度STL容器)。

这时你或者会问：“机能如 何？”很是好的问题。广义的讲，算法做的事情越多，花的时间越长， “不变”性排序算法比“非不变”性排序算法要耗时。我 们可以凭据其耗损的资源(时间和空间)的几多，对本文中接头的排序算法作个排 序，耗损资源越少的排在前面：

1. partition

2. stable_partition

3. nth_element

4. partial_sort

5. sort

6. stable_sort

选择这些算法的依据是你的需求而不是它们 的机能。若你能选择一个算法刚好满意你的需求(如用部门排序取代全排序)，不 仅会清晰表达你的意图，并且能高效的利用STL。