C++ sorting and keeping track of indexes

user_62791 0
Viewed 168503

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?

indexing sorting stl c++
16 Answers

Suppose Given vector is

A=[2,4,3]

Create a new vector

V=[0,1,2] // indicating positions

Sort V and while sorting instead of comparing elements of V , compare corresponding elements of A

 //Assume A is a given vector with N elements
 vector<int> V(N);
 std::iota(V.begin(),V.end(),0); //Initializing
 sort( V.begin(),V.end(), [&](int i,int j){return A[i]<A[j];} );
user_63544420

Consider using std::multimap as suggested by @Ulrich Eckhardt. Just that the code could be made even simpler.

Given

std::vector<int> a = {5, 2, 1, 4, 3};  // a: 5 2 1 4 3

To sort in the mean time of insertion

std::multimap<int, std::size_t> mm;
for (std::size_t i = 0; i != a.size(); ++i)
    mm.insert({a[i], i});

To retrieve values and original indices

std::vector<int> b;
std::vector<std::size_t> c;
for (const auto & kv : mm) {
    b.push_back(kv.first);             // b: 1 2 3 4 5
    c.push_back(kv.second);            // c: 2 1 4 3 0
}

The reason to prefer a std::multimap to a std::map is to allow equal values in original vectors. Also please note that, unlike for std::map, operator[] is not defined for std::multimap.

user_93735090

I recently stepped upon the elegant projection feature of C++20 <ranges> and it allows to write shorter/clearer code:

std::vector<std::size_t> B(std::size(A));
std::iota(begin(B), end(B), 0);
std::ranges::sort(B, {}, [&](std::size_t i){ return A[i]; });

{} refers to the usual std::less<std::size_t>. So as you can see we define a function to call on each element before any comparaison. This projection feature is actually quite powerful since this function can be, as here, a lambda or it can even be a method, or a member value. For instance:

struct Item {
    float price;
    float weight;
    float efficiency() const { return price / weight; }
};

int main() {
    std::vector<Item> items{{7, 9}, {3, 4}, {5, 3}, {9, 7}};
    std::ranges::sort(items, std::greater<>(), &Item::efficiency);
    // now items are sorted by their efficiency in decreasing order:
    // items = {{5, 3}, {9, 7}, {7, 9}, {3, 4}}
}

If we wanted to sort by increasing price:

std::ranges::sort(items, {}, &Item::price);

Don't define operator< or use lambdas, use a projection!

user_29482480

One solution is to use a 2D vector.

#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;

int main() {
 vector<vector<double>> val_and_id;
 val_and_id.resize(5);
 for (int i = 0; i < 5; i++) {
   val_and_id[i].resize(2); // one to store value, the other for index.
 }
 // Store value in dimension 1, and index in the other:
 // say values are 5,4,7,1,3.
 val_and_id[0][0] = 5.0;
 val_and_id[1][0] = 4.0;
 val_and_id[2][0] = 7.0;
 val_and_id[3][0] = 1.0;
 val_and_id[4][0] = 3.0;

 val_and_id[0][1] = 0.0;
 val_and_id[1][1] = 1.0;
 val_and_id[2][1] = 2.0;
 val_and_id[3][1] = 3.0;
 val_and_id[4][1] = 4.0;

 sort(val_and_id.begin(), val_and_id.end());
 // display them:
 cout << "Index \t" << "Value \n";
 for (int i = 0; i < 5; i++) {
  cout << val_and_id[i][1] << "\t" << val_and_id[i][0] << "\n";
 }
 return 0;
}

Here is the output:

   Index   Value
   3       1
   4       3
   1       4
   0       5
   2       7
user_38677390
Related