迭代器nth用来指向一个全排序的情况下第n个元素的位置，然后根据这个值将[begin, end]区间内的元素分割成2部分，一部分都在元素n的全面，一部分在元素n的后面，但它并不关心分割后元素的排序情况。
事例:
nth_element的功能和partition有点类似，但又不完全相同。partition可以筛选出所有分数大于60分的人，现在需求变成需要筛选出分数最高的前5个人，这时就轮到nth_element出场了。
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <iterator> //ostream_iterator
#include <functional> //not2
using namespace std;
struct student
{
string name;
unsigned int score;
student(const string &n, unsigned int s) :
name(n),score(s)
{}
friend ostream & operator<<(ostream &os, const student &rhs)
{
return os << rhs.score << " : " << rhs.name << endl;
}
};
struct comp : public binary_function<student, student, bool>
{
bool operator()(const student &lhs, const student &rhs) const
{
return lhs.score > rhs.score;
}
};
int main()
{
student stu[] = {
student("aa", 100),
student("bb", 95),
student("cc", 50),
student("dd", 40),
student("ee", 52),
student("ff", 60),
student("gg", 86),
student("hh", 60),
student("ii", 83),
student("jj", 91),
};
vector<student> stuArray(stu, stu + sizeof(stu) / sizeof(student));
nth_element(stuArray.begin(), stuArray.begin() + 5, stuArray.end(), comp());
copy(stuArray.begin(), stuArray.begin() + 5, ostream_iterator<student>(cout, ""));
return 0;
}
[root@oracle ~]# ./a.out
100 : aa
95 : bb
91 : jj
83 : ii
86 : gg
6. partial_sort
原型:
template<typename iterator>
void partial_sort(iterator begin, iterator middle, iterator end)
template<typename iterator, typename compare>
void partial_sort(iterator begin, iterator middle, iterator end, compare comp)
事例:
partial_sort和nth_element的用法和功能基本相同。不同的是nth_element并不关心符合条件的元素具体的排序位置，只是把他们移到了容器的前面(上面的事例输出也很容易看出来)。而partial_sort则关心具体位置，将nth_element事例中的nth_element函数替换成partial_sort后，输出就变了。
#程序执行结果
[root@oracle ~]# ./a.out
100 : aa
95 : bb
91 : jj
86 : gg
83 : ii
三、总结
1. sort、stable_sort、partial_sort和nth_element算法都要求随机访问迭代器，所以这些算法只能被用于vector、string、deque和数组。
2. 如果需要对vector、string、deque或者数组中的元素执行一次完全排序，那么可以使用sort或者stable_sort。
3. 如果有一个vector、string、deque或者数组，并且只需要对等价性最前面的n个元素进行排序，那么可以使用partial_sort。