Creating a vector of indices of a sorted vector [duplicate]

Question

Variable x is a vector of n ints, and I want to sort the vector in ascending order. However, for reasons outside the scope of this question, I want to vector to remain untouched. Therefore, rather than actually sorting the contents of x, I want to create another vector of n indices, where each index refers to the respective value in x, if x were to have been sorted.

For example:

std::vector<int> x = {15, 3, 0, 20};
std::vector<int> y;
// Put the sorted indices of x into the vector y
for (int i = 0; i < 4; i++)
{
    std::cout << y[i];
}

Should give the output:

2
1
0
3

Corresponding to values in x:

0
3
15
20

I can think of plenty of timely ways of implementing this, but I'm wondering whether the STL has something build-in to perform this efficiently for me?

Answer 1

1) Create y as a vector of index (an integer range)

2) Sort this range with a comparator that returns the indexes elements from x Using the Standard Library, that gives :

#include <iostream>
#include <vector>
#include <algorithm>

int main() {

    std::vector<int> x = {15, 3, 0, 20};

    std::vector<int> y;

    std::vector<int> y(x.size());
    std::size_t n(0);
    std::generate(std::begin(y), std::end(y), [&]{ return n++; });

    std::sort(  std::begin(y), 
                std::end(y),
                [&](int i1, int i2) { return x[i1] < x[i2]; } );

    for (auto v : y)
        std::cout << v << ' ';

    return 0;
}

Live demo.

Answer 2

Fill y with all the indices of x then use std::sort on y but provide a comparator that compares the corresponding elements in x:

  std::vector<int> y(x.size());
  std::iota(y.begin(), y.end(), 0);
  auto comparator = [&x](int a, int b){ return x[a] < x[b]; };
  std::sort(y.begin(), y.end(), comparator);