Effective STL理解你的排序操作

这样一来，所有在迭代器widgets.begin()和迭代器goodEnd之间的元素都是 满足需求的元素：其质量等级好于或等于2。而在 goodEnd 到 widgets.end() 之间的元素的质量等级都会低于质量等级2。如果你对质量等级相同元素的相对 位置很关心的话，你可以选择stable_partition算法来代替partition。

需要注意的是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中的元素连接到你想要链接的位置。看见了吧，你可以选择 的方式还是比较多的。

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

选择这些算法的依据是你的需求而不是它们 的性能。若你能选择一个算法恰好满足你的需求(如用部分排序代替

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