CODEWITHSUNDEEP
c++algorithmsortingvector
Michal
Michal

Reputation: 564

Efficiently sort subset of the vector that defines the order

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.

Upvotes: 7

Views: 696

Answers (1)

Naseef Chowdhury
Naseef Chowdhury

Reputation: 2464

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

Upvotes: 2

Related Questions