Sort and keep track of elements

Question

Just to know, I'm talking C++ now. Suppose I have an array `A = {4, 1, 5, 2, 3}` and sort it in `A_sorted = {1, 2, 3, 4, 5}`. I would like to keep the following information: where is now element `e` (from array A) in the sorted array A_sorted? e.g.: element with index 2 in A (`5`) has now index 4 in A_sorted. The question is more like: can one use STL to achieve this?

Accepted Answer

There's no off-the-shelf functionality to achieve this, but there are work-arounds. You can, for example, keep an array of user-defined structs that also contain the original position:

```
A = { {4,0}, {1,1}, {5,2}, {2,3}, {3,4}}
```

And then sort this using a custom comparator function that sorts by the value and not the original index.

```
A_sorted = {{1,1}, {2,3}, {3,4}, {4,0}, {5,2}}
```

Sort and keep track of elements

Solution

Problem