std :: sort来排序数组和索引列表？

Question

我有一个函数,它接受两个与参数大小相同的向量:

void mysort(std::vector<double>& data, std::vector<unsigned int>& index)
{
   // For example :
   // The data vector contains : 9.8 1.2 10.5 -4.3
   // The index vector contains : 0 1 2 3
   // The goal is to obtain for the data : -4.3 1.2 9.8 10.5
   // The goal is to obtain for the index : 3 1 0 2
   // Using std::sort and minimizing copies
}

如何解决最小化所需副本数量的问题？

一种显而易见的方法是制作单个矢量std::pair<double, unsigned int>并指定比较器[](std::pair<double, unsigned int> x, std::pair<double, unsigned int> y){return x.first < y.first;},然后将结果复制到两个原始矢量中,但效率不高.

注意:函数的签名是固定的,我不能传递单个向量std::pair.

Answer 1

在函数内部,positions = [0,1,2,3...] 使用比较器创建矢量排序位置(int x, int y){return data[x]<data[y];}.

然后迭代位置,做 result.push_back(index[*it]);

这假设值index可以是任意的.如果保证已经[0,1,2..]像你的例子一样,那么你不要制作positions数组,只需index在它的位置使用并跳过最后一个副本.