Sorting with indices using sort in C++

Question

In a previous question, an answer showed how to use lambdas to track original positions in an array and just sort the indices.

C++ sorting and keeping track of indexes

I want to sort the list but store the original indices. One approach is to sort the indices, then reorder the list. This would require two passes, and the second is O(n) so perhaps that is not too bad. But I wondered whether it would be possible to simultaneously reorder the values and swap the list. The problem is that the lambda for comparison only takes two parameters.

What is the best way to write:

template<typename T>
sortWithIndexes(v, indexes, n) {

}

so that v is reordered, and indexes contains the original position of each element of v?

@Logicstuff I want to jump into the array very frequently, and linearly scan through the data. it is very worth making this sequential in space. — Dov, Aug 17 '17 at 13:58
@tobi303 same reason as above, I want all the values sequential in memory — Dov, Aug 17 '17 at 13:58

Shravan40 · Answer 1 · 2017-08-17T13:16:00.100

0

You can use std::multimap for same. It will automatically sort w.r.t keys.

edited Aug 17 '17 at 13:16

answered Aug 17 '17 at 13:09

Shravan40

8,922
6
28
48

Sorting with indices using sort in C++

1 Answers1