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?

Viewed 127

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?

3 Answers

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.

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";

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? 
Related