4

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?

José D.
  • 4,175
  • 7
  • 28
  • 47
  • I don't know that it has a name, but it's very similar to [this question](http://stackoverflow.com/q/19260078/752320). It looks like you're sorting descending, but other than that it's basically the same problem. – Geobits Oct 17 '13 at 16:32
  • It's called "sorting with a compare function". You sort the indexes, using the indexed values in the comparison function. – Has QUIT--Anony-Mousse Oct 17 '13 at 16:36
  • If your input was `{22, 149, 31, 149}` what would you expect the output to be? – Marshall Clow Oct 17 '13 at 16:48

1 Answers1

13

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.

Sebastian Redl
  • 69,373
  • 8
  • 123
  • 157
  • +1 but one minor nitpick: `vector indices; indices.reserve(input.size()); iota_n(std::back_inserter(indices), input.size(), 0);` would be slightly more efficient in generating the indices. For `iota_n` see e.g. [this Q&A](http://stackoverflow.com/q/11767512/819272) – TemplateRex Nov 27 '13 at 11:33