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

Question

我需要执行以下操作：

std::vector给定一个我需要用如果对向量进行排序时它所在的索引int来替换每个。int

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

输入：{22, 149,31}

输出：{2, 0, 1}

（注意，在排序向量 {149, 31, 22} 中，22在排序向量的索引 2中，149在索引 0中，31在索引 1中）

我希望我把算法说清楚。

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

Answer 1

我不认为它有名字，但它很容易完成。

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

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

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

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

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