Sort-related algorithm (replace each item by its index in the sorted colletion)

Question

I need to do the following:

Given an std::vector of int I need to replace each int by the index that it would be in if the vector were sorted.

I will try to explain it better with an example.

Input: {22, 149,31}

Output: {2, 0, 1}

(Note that in the sorted vector {149, 31, 22} the 22 is in the index 2 of the sorted vector, the 149 is in index 0, and the 31 is in index 1)

I hope I make the algorithm clear.

Is this implemented somehow in the STL C++11 library? Has this algorithm a name? Can you offer any ideas to implement it elegantly?

Answer 1

I don't think it has a name, but it's pretty easy to accomplish.

First, you create a target vector and fill it with the indices 0...n.

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

Second, you sort that vector, but instead of comparing the numbers in the vector, you compare the numbers at the relevant index in the input vector.

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

Edit Note that I'm sorting in ascending order, whereas you're looking for descending order. Just flip the comparison in the lambda.