Efficiently sort subset of the vector that defines the order

Question

I have the vector that defines the order of items (0..N-1), e.g. {5, 0, 4, 3, 2, 1, 7, 6}.

I have to sort subsets of that vector. So, for {0, 1, 2, 5} I should get {5, 0, 2, 1}.

I tested the following solutions:

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

The second solution seems much faster, although it needs subset to be sorted. Are there any better solutions? I am using C++/STL/Qt, but the problem is probably not language-dependent.

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

The code is copied from here