走向理解 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.

我想取向量子集的第 n 个元素，所以我想这样做：

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

表示取向量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.

Answer 2

I want to take the n-th element of a subset of a vector, so I thought doing something like this:

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

would mean to take the subset of the vector v, from the start, until the end (exclusive), and then imagining that this subset is sorted, position the nTh element.

是的，确实如此。但是在这样做时，位置 v[0] 到 v[start-1] 和 v[end] 到 v[v.size() - 1] 中的任何元素都不会成为 nth_element 的一部分重新安排，他们将留在原地。作为 nth_element() 一部分的开始和结束已将这些元素排除在重新排列之外。

我想你想要

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

考虑整个向量（nth_element 的第一个和第三个参数）。

这意味着无论 random_shuffle 在哪里洗牌了元素

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

因为 nth_element 正在考虑整个向量，nth_element 的第二个参数，myvector 中的第 5 个项目如果排序，应该是 5。注意，因为 nth_element 的方式有效，前面的项目将少于 5（并且以任何顺序）并且接下来的项目将超过 5（并且以任何顺序）。

走向理解 nth_element

Towards understanding nth_element

c++

algorithm

vector

nth-element