C++ sorting and keeping track of indexes

Question

Using c++, and hopefully the STL, I want to sort a sequence of samples in ascending order, but I also want to remember the original indexes of the newly samples. For example I have a set, or vector, or matrix of samples A : [5, 2, 1, 4, 3] I want to sort these to be B : [1,2,3,4,5], but I also want to remember the original indexes of the values, so i can get another set which would be: C : [2, 1, 4, 3, 0 ] - which corresponds to the index of the each element in 'B', in the original 'A'.

For example, in matlab you can do: [a,b]=sort([5, 8, 7])

a = 5 7 8

b = 1 3 2

Can anyone see a good way to do this?

Answer 1

If it's possible, you can build the position array using find function, and then sort the array.

Or maybe you can use a map where the key would be the element, and the values a list of its position in the upcoming arrays (A, B and C)

It depends on later uses of that arrays.

Answer 2

Are the items in the vector unique? If so, copy the vector, sort one of the copies with STL Sort then you can find which index each item had in the original vector.

If the vector is supposed to handle duplicate items, I think youre better of implementing your own sort routine.

Answer 3

You could sort std::pair instead of just ints - first int is original data, second int is original index. Then supply a comparator that only sorts on the first int. Example:

Your problem instance: v = [5 7 8]
New problem instance: v_prime = [<5,0>, <8,1>, <7,2>]

Sort the new problem instance using a comparator like:

typedef std::pair<int,int> mypair;
bool comparator ( const mypair& l, const mypair& r)
   { return l.first < r.first; }
// forgetting the syntax here but intent is clear enough

The result of std::sort on v_prime, using that comparator, should be:

v_prime = [<5,0>, <7,2>, <8,1>]

You can peel out the indices by walking the vector, grabbing .second from each std::pair.

Answer 4

I have had had this problem before but I'm not sure there is an elegant solution. At the time I simply stored two containers - one with sorted pointers to my data, and one with the original sort. I would be curious as to whether there is a cleaner implementation.

Answer 5

When dealing with multiple views on a container, always consider boost::multi_index_container. It might be a bit overkill, but it also might be just what you needed. You just insert and access and take a sorted view.