Using C++, and hopefully the standard library, I want to sort a sequence of samples in ascending order, but I also want to remember the original indexes of the new 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 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?
ベストアンサー1
Using C++ 11 lambdas:
#include <iostream>
#include <vector>
#include <numeric> // std::iota
#include <algorithm> // std::sort, std::stable_sort
using namespace std;
template <typename T>
vector<size_t> sort_indexes(const vector<T> &v) {
// initialize original index locations
vector<size_t> idx(v.size());
iota(idx.begin(), idx.end(), 0);
// sort indexes based on comparing values in v
// using std::stable_sort instead of std::sort
// to avoid unnecessary index re-orderings
// when v contains elements of equal values
stable_sort(idx.begin(), idx.end(),
[&v](size_t i1, size_t i2) {return v[i1] < v[i2];});
return idx;
}
Now you can use the returned index vector in iterations such as
for (auto i: sort_indexes(v)) {
cout << v[i] << endl;
}
You can also choose to supply your original index vector, sort function, comparator, or automatically reorder v in the sort_indexes function using an extra vector.