c++ - 理解第 nth_element

Question

我很难掌握应该如何使用 std::nth_element ，因为我有点生疏。

裁判说:

Rearranges the elements in the range [first,last), in such a way that the element at the nth position is the element that would be in that position in a sorted sequence.

我想获取 vector 子集的第 n 个元素，所以我想做这样的事情:

std::nth_element (v.begin()+start-0, v.begin()+nTh-1, v.begin()+end);

表示获取 vector v 的子集，从 start 到 end(不包括)，然后想象此子集已排序，定位 nTh 元素。

看来我的理解是错误的，因为这个玩具示例:

#include <iostream>
#include <algorithm>
#include <vector>

int main () {
  std::vector<int> myvector;

  // set some values:
  for (int i=1; i<10; i++) myvector.push_back(i);   // 1 2 3 4 5 6 7 8 9

  std::random_shuffle (myvector.begin(), myvector.end());


  std::nth_element (myvector.begin() + 1 - 0, myvector.begin()+5-1, myvector.begin() + 5);
  std::cout <<  *(myvector.begin()+5-1) << std::endl;

  for (std::vector<int>::iterator it=myvector.begin(); it!=myvector.end(); ++it)
    std::cout << ' ' << *it;
  std::cout << '\n';

  return 0;
}

打印 9 作为请求的元素，而我期望的是 5。请问我缺少什么？

Answer 1

尝试:

std::nth_element (myvector.begin(), myvector.begin()+ 4, myvector.end());

代替:

std::nth_element (myvector.begin() + 1, 
                  myvector.begin() + 4, 
                  myvector.begin() + 5);

你正在洗牌，然后只为一个子序列调用 nth_element。这样你就不能返回的元素应该是什么。如果你对整个序列都这样做，那么答案是 5。