c++ - 排序相关算法(用排序集合中的索引替换每个项目)

Question

我需要做以下事情:

给定 int 的 std::vector 我需要将每个 int 替换为如果 vector 是排序。

我会尝试用一个例子更好地解释它。

输入:{22, 149,31}

输出:{2, 0, 1}

(请注意，在排序 vector {149, 31, 22} 中，22 在排序 vector 的 index 2 中，149 在 index 0，而 31 在 index 1)

我希望我把算法说清楚。

这是在 STL C++11 库中以某种方式实现的吗？这个算法有名字吗？您能提供任何想法来优雅地实现它吗？

Answer 1

我认为它没有名字，但它很容易实现。

首先，您创建一个目标 vector 并用索引 0...n 填充它。

vector<int> indices(input.size());
std::iota(indices.begin(), indices.end(), 0);

其次，您对该 vector 进行排序，但不是比较 vector 中的数字，而是比较输入 vector 中相关索引处的数字。

std::sort(indices.begin(), indices.end(),
          [&input](int l, int r) { return input[l] < input[r]; });

编辑 请注意，我按升序排序，而您正在查找降序。只需翻转 lambda 中的比较即可。