Suppose we have two std::vectors v1 and v2 and we dont want to combine these in a struct. How to transform v2 the same way v1 was transformed by sort?

Question

This is a followup of this question. The only difference is the constrain that the two vectors cannot be combined in a struct.

Suppose we have a vector

std::vector<double> v1 = {9.0,5.0,3.0,2.0,1.0};

Now we sort the vector v1. Let v2 be given by

std::vector<std::string> v2 = {"you?","are","how","there","hello"};

How to transform v2 the same way v1 was transformed by sort?

Answer 1

Based on this answer, you can use an array of indices to "sort" the vector of doubles, and just use the resulting index array to index the vector of strings.

#include <algorithm>
#include <iostream>
#include <string>
#include <numeric>

int main()
{
    std::vector<double> v1 = {5.0,9.0,3.0,2.0,1.0};
    std::vector<std::string> v2 = {"are", "you?","how","there","hello"};

    // Create an array of indices, starting from 0
    std::vector<int> index(v1.size());
    std::iota(index.begin(), index.end(), 0);

    // "Sort" the index array according to the value in the vector of doubles
    std::sort(index.begin(), index.end(), 
              [&](int n1, int n2){ return v1[n1] < v1[n2]; });

    // Output results
    for (auto i : index )
      std::cout << v2[i] << " " << v1[i] << ", index is " << i << "\n";
}

Output:

hello 1, index is 4
there 2, index is 3
how 3, index is 2
are 5, index is 0
you? 9, index is 1

---

Note:

I changed the original data to illustrate how the index array works.

Answer 2

The abstraction you are missing is the ability to view the vectors as one item. That's the role that a vector of indices is a proxy for in another answer.

I think it is worth mentioning that there are libraries that provide such a concept (often under the name "zip"). For example, with range-v3:

std::vector<double> v1 = {5, 9, 3, 2, 1};
std::vector<std::string> v2 = {"are", "you?", "how", "there", "hello"};

// Sort the vectors
ranges::actions::sort(ranges::views::zip(v1, v2));

// Output results
for (std::size_t i = 0; i < v1.size(); ++i)
  std::cout << v2[i] << " " << v1[i] << ", index is " << i << "\n";

Answer 3

A possible solution uses a helper std::vector<int>:

#include <iostream>
#include <vector>
#include <algorithm>
#include <stdexcept>

template<typename T>
void MySort(std::vector<T> t, std::vector<int>& helper)
{
    struct StructHelper
    {
        T t1;
        int num;
        StructHelper(T t, int i): t1{t}, num{i} {};
        bool operator<(const StructHelper& other) const
        { return t1 < other.t1; }
    };

    std::vector<StructHelper> shVector;

    for(int i=0; i<t.size(); ++i)
    {
        shVector.emplace_back(t[i], i);
    }

    std::sort(shVector.begin(), shVector.end());
    helper = std::vector<int>(t.size());

    for(int i=0; i<t.size(); ++i)
    {
        helper[i] = shVector[i].num;
    }

}

template<typename T>
void MySortUsingHelper(std::vector<T>& t1, const std::vector<int>& helper)
{
    if(t1.size() != helper.size()) throw std::out_of_range("not same size");
    std::vector<T> t2(t1.size());

    for(int i=0; i<helper.size(); ++i)
    {
        t2[i] = t1[helper[i]];
    }

    t1 = t2;
}

int main() {

    std::vector<double> v1 = {9.0,5.0,3.0,2.0,1.0};
    std::vector<int> helper;

    MySort(v1, helper);

    std::vector<std::string> v2 = {"you?","are","how","there","hello"};

    MySortUsingHelper(v2, helper);

    for(auto elem : v2)
    {
        std::cout << elem << " ";
    }

    return 0;
} 

You can run the above code online to see the following output:

hello there how are you?