CODEWITHSUNDEEP
c++algorithmsortingvector
shushi_piggy
shushi_piggy

Reputation: 115

Sort struct vector as sub-groups

I have a struct vector looks like this:

struct table{

int k;
int r;
int c;

}

std::vector<table> myvector;

I want to sort the vector's object based on the following criteria:

For instance, if myvector is like this (each column represents a object):

k:  1   2   3   5   4   6
r:  3   3   3   2   3   2
c:  3   4   2   3   1   4

After sorting the vector should be like this:

k:  4   3   1   2   5   6
r:  3   3   3   3   2   2
c:  1   2   3   4   3   4

My solution is that first sort the vector base on r value so that we put the same r value together:

std::sort(myvector.begin(), myvector.end(), compare_r);

bool compare_r(table left, table right){return left.r < right.r;}

The we sort inside each group:

bool compare_c(table left, table right){return left.c < right.c;}

std::vector<table>::iterator it1, it2;
it1 = myvector.begin();
it2 = it1;

int r_now = it1 -> r;

for(; it2 != myvector.end(); ++it2){

    if(it2 -> r != r_now){
        std::sort(it1, it2, compare_c);
        r_now = it2 -> r;
        it1 = it2;
    }

}

std::sort(it1, it2, compare_c);

Right now myvector becomes:

k:  5   6   4   3   1   2   
r:  2   2   3   3   3   3   
c:  3   4   1   2   3   4

The final step is to put objects with k = 5 & 6 to the back of the vector because 1st group's 1st c = 3 is larger than the 1st c = 1 of the 2nd group (third criteria). I can copy k = 5 & 6 and erase them, then insert them at the end of myvector. But that seems like not very efficient. Does anyone has a better idea?

Upvotes: 0

Views: 170

Answers (1)

Slava
Slava

Reputation: 44238

Here is possible implementation of idea suggested by @IgorTandetnik:

std::vector<table> myvector;
// sort based by c
std::sort( myvector.begin(), myvector.end(), []( const auto &l, const auto &r ) {
     return l.c < r.c;
} );
std::unordered_map<int,int> ranks;
// populate ranks based on smallest (first) c
std::transform( myvector.begin(), myvector.end(), std::inserter( ranks ), []( const auto &t ) { return std::make_pair( t.r, t.c ); } );
// stable sort by ranks of r
std::stable_sort( myvector.begin(), myvector.end(), [&ranks]( const auto &l, const auto &r ) {
     return ranks[l.r] < ranks[r.r];
} );

I did not try to compile the code, as you did not provide MCVE, but it should work after fixing syntax errors if any.

Upvotes: 1

Related Questions