Effectively sort a subset of an ordering vector

Question

I have a vector that defines the order of elements (0..N-1), for example. {5, 0, 4, 3, 2, 1, 7, 6} .

I need to sort the subsets of this vector. So, for {0, 1, 2, 5} I have to get {5, 0, 2, 1} .

I tested the following solutions:

• Create a set of elements in a subset, then clear the subset, go through the ordering vector, adding only the elements to the set.
• Create a new sorted vector by going through the ordering vector, adding only the elements found in a subset of std::lower_bound .

The second solution seems much faster, although it requires a subset to sort it. Are there any better solutions? I am using C ++ / STL / Qt, but the problem is probably language independent.

Answer 1

Check this code: -

 #include <iostream> #include <algorithm> #include <vector> struct cmp_subset { std::vector<int> vorder; cmp_subset(const std::vector<int>& order) { vorder.resize(order.size()); for (int i=0; i<order.size(); ++i) vorder.at(order[i]) = i; } bool operator()(int lhs, int rhs) const { return vorder[lhs] < vorder[rhs]; } }; int main() { std::vector<int> order = {5, 0, 4, 3, 2, 1, 7, 6}; std::vector<int> subset = {0, 1, 2, 5}; for (auto x : subset) std::cout << x << ' '; std::cout << '\n'; std::sort(subset.begin(), subset.end(), cmp_subset(order)); for (auto x : subset) std::cout << x << ' '; std::cout << '\n'; return 0; } 

Code copied from here