未排序长度 n 数组中 k 个最大元素的索引

我需要找到 C++ 中未排序、长度为 n 的数组/向量的 k 个最大元素的索引，其中 k

在没有 nth_element() 的情况下实现它似乎我必须迭代整个数组一次，在每一步填充最大元素的索引列表。

标准 C++ 库中是否有任何内容可以使其成为一句简单的话，或者有什么巧妙的方法可以让我自己在几行内实现这一点？在我的特定情况下，k = 3，n = 6，因此效率并不是一个大问题，但最好找到一种干净且有效的方法来对任意 k 和 n 执行此操作。

看起来像标记未排序数组的前 N ​​个元素 https://stackoverflow.com/questions/1885591/mark-the-top-n-elements-of-an-unsorted-array这可能是我能在 SO 上找到的最接近的帖子，那里的帖子是用 Python 和 PHP 编写的。

这应该是 @hazelnusse 的改进版本，在O(nlogk)代替O(nlogn)

#include <queue>
#include <iostream>
#include <vector>
// maxindices.cc
// compile with:
// g++ -std=c++11 maxindices.cc -o maxindices
int main()
{
  std::vector<double> test = {2, 8, 7, 5, 9, 3, 6, 1, 10, 4};
  std::priority_queue< std::pair<double, int>, std::vector< std::pair<double, int> >, std::greater <std::pair<double, int> > > q;
    int k = 5; // number of indices we need
  for (int i = 0; i < test.size(); ++i) {
    if(q.size()<k)
        q.push(std::pair<double, int>(test[i], i));
    else if(q.top().first < test[i]){
        q.pop();
        q.push(std::pair<double, int>(test[i], i));
    }
  }
  k = q.size();
  std::vector<int> res(k);
  for (int i = 0; i < k; ++i) {
    res[k - i - 1] = q.top().second;
    q.pop();
  }
  for (int i = 0; i < k; ++i) {
    std::cout<< res[i] <<std::endl;
  }
}

8 4 1 2 6