C++ vector sorting and mapping from unsorted to sorted elements

Question

I have to perform the following task. Take a std::vector<float>, sort the elements in descending order and have an indexing that maps the unsorted elements to the sorted ones. Please note that the order really matters: I need a map that, given the i-th element in the unsorted vector, tells me where this element is found in the sorted one. The vice-versa has been achieved already in a pretty smart way (through c++ lambdas) e.g., here: C++ sorting and keeping track of indexes. Nevertheless, I was not able to find an equally smart way to perform the "inverse" task. I would like to find a fast way, since this kind of mapping has to be performed many times and the vector has big size.
Please find in the following a simple example of what I need to achieve and my (probably suboptimal, since it relies on std::find) solution of the problem. Is it the most fast/efficient way to perform this task? If not, are there better solutions?

Example

Starting vector: v = {4.5, 1.2, 3.4, 2.3}

Sorted vector: v_s = {4.5, 3.4, 2.3, 1.2}

What I do want: map = {0, 3, 1, 2}

What I do not want: map = {0, 2, 3, 1}

My solution

template <typename A> std::vector<size_t> get_indices(std::vector<A> & v_unsorted, std::vector<A> & v_sorted) {
  std::vector<size_t> idx;
  for (auto const & element : v_unsorted) {
    typename std::vector<A>::iterator itr = std::find(v_sorted.begin(), v_sorted.end(), element);
      idx.push_back(std::distance(v_sorted.begin(), itr));
  }
  return idx;
}

Thanks a lot for your time, cheers!

Answer 1

You can use the code below.

My version of get_indices does the following:

1. Create a vector of indices mapping sorted -> unsorted, using code similar to the one in the link you mentioned in your post (C++ sorting and keeping track of indexes).

2. Then by traversing those indices once, create the sorted vector, and the final indices mapping unsorted -> sorted.

The complexity is O(n * log(n)), since the sort is done in O(n * log(n)), and the final traversal is linear.

The code:

#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>

template <typename T>
std::vector<size_t> get_indices(std::vector<T> const & v_unsorted, std::vector<T> & v_sorted) 
{
    std::vector<size_t> idx_sorted2unsorted(v_unsorted.size()); 
    std::iota(idx_sorted2unsorted.begin(), idx_sorted2unsorted.end(), 0);

    // Create indices mapping (sorted -> unsorted) sorting in descending order:
    std::stable_sort(idx_sorted2unsorted.begin(), idx_sorted2unsorted.end(),
        [&v_unsorted](size_t i1, size_t i2) 
            { return v_unsorted[i1] > v_unsorted[i2]; }); // You can use '<' for ascending order

    // Create final indices (unsorted -> sorted) and sorted array:
    std::vector<size_t> idx_unsorted2sorted(v_unsorted.size());
    v_sorted.resize(v_unsorted.size());
    for (size_t i = 0; i < v_unsorted.size(); ++i)
    {
        idx_unsorted2sorted[idx_sorted2unsorted[i]] = i;
        v_sorted[i] = v_unsorted[idx_sorted2unsorted[i]];
    }
    return idx_unsorted2sorted;
}

int main() 
{
    std::vector<double> v_unsorted{ 4.5, 1.2, 3.4, 2.3 };
    std::vector<double> v_sorted;
    std::vector<size_t> idx_unsorted2sorted = get_indices(v_unsorted, v_sorted);
    for (auto const & i : idx_unsorted2sorted)
    {
        std::cout << i << ", ";
    }
    return 0;
}

Output:

0, 3, 1, 2,

Answer 2

Once you have the mapping from sorted to unsorted indices, you only need a loop to invert it.

I am building on the code from this answer: https://stackoverflow.com/a/12399290/4117728. It provides a function to get the vector you do not want:

#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;
}

Sorting the vector is O(N logN) your code calls find N times resulting in O(N*N). On the other hand, adding a single loop is only linear, hence sorting plus the loop is still O(N log N).

int main() {
    std::vector<double> unsorted{4.5, 1.2, 3.4, 2.3};
    auto idx = sort_indexes(unsorted);
    for (auto i : idx) std::cout << unsorted[i] << "\n";
    
    // the vector you do not want
    for (auto i : idx) std::cout << i << "\n";
    
    // invert it
    std::vector<size_t> idx_inverse(idx.size());
    for (size_t i=0;i<idx.size();++i) idx_inverse[ idx[i] ] = i;
    
    // the vector you do want
    for (auto i : idx_inverse) std::cout << i << "\n";
}

Live Demo