0

I have a 2D vector, S, and a 1D vector, I. Both S and I contain integers. Here is an example:

vector<int> I={6,2,3,1,4,5,0};
vector<vector<int>> S;
S[0]={0,1,3};
S[1]={1,2,4};
S[2]={4,5,6};
S[3]={0,3,5};

I contains numbers 0..n and vectors S are all subsets of I. I want to sort items in vectors S, with respect to the order of items in I. So that:

S[0]={3,1,0};
S[1]={2,1,4};
S[2]={6,4,5};
S[3]={3,5,0};

My real vectors are large in size, so I need to do it in the most efficient way (in c++).

Anna
  • 13
  • 7

1 Answers1

0

You can populate a map of weights used for the sorting and then provide a custom comparator for sort:

#include <iostream>
#include <vector>
#include <algorithm>
#include <unordered_map>

int main() {
    std::vector<int> I={6,2,3,1,4,5,0};
    std::unordered_map<int,unsigned> weights;
    for (unsigned i = 0; i < I.size(); ++i) weights[I[i]] = i;

    std::vector<int> s{3,6,5};
    std::sort(s.begin(),s.end(), [&weights](int a,int b){
        return weights[a] < weights[b];
    });

    for (const auto& e : s) std::cout << e << " ";
}

To sort many vectors you just need to call sort in a loop. If the numbers in I are always consecutive with no holes in between then using an array as look up table would be more efficient.

463035818_is_not_an_ai
  • 109,796
  • 11
  • 89
  • 185