Сортировать структурный вектор как подгруппы

Question

У меня есть вектор структуры, который выглядит следующим образом:

struct table{

int k;
int r;
int c;

}

std::vector<table> myvector;

Я хочу отсортировать объект вектора на основе следующих критериев:

• Объект с тем же значением r должны быть помещены вместе (я назвал накопление того же r как «группа»).
• Объекты внутри одной группы должны располагаться в порядке возрастания на основе значения c.
• Группы должны быть отсортированы в порядке возрастания на основе значения c первого объекта.

Например, если myvector такой (каждый столбец представляет объект):

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

После сортировки вектор должен выглядеть так:

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

Мое решение состоит в том, чтобы сначала отсортировать векторную базу по значению r, чтобы мы соединили одно и то же значение r:

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

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

Мы сортируем внутри каждой группы:

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

Прямо сейчас myvector становится:

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

Последний шаг - поместить объекты с k = 5 и 6 в конец вектора, потому что 1-ая группа * 1 c = 3 больше, чем 1 c = 1 2-й группы (третий критерий). Я могу скопировать k = 5 & 6 и стереть их, а затем вставить их в конце myvector. Но это кажется не очень эффективным. У кого-нибудь есть идея получше?

Answer 1

Вот возможная реализация идеи, предложенной @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];
} );

Я не пытался скомпилировать код, поскольку вы не предоставили MCVE, но он должен работать после исправления синтаксических ошибок, если таковые имеются.