std::sort using indices but maintaining index order

Question

I have a vector of values. I want to get a sorted list of indices out based on these values.

I have got this working reasonably well except where the same value occurs. When the same value occurs I'd like the indices to stay in order.

For example I have this test case:

std::vector< size_t >   idx;
std::vector< int >      val;
for( int i = 0; i < 40; i++ )
{
    idx.push_back( i );
    val.push_back( i % 10 );
}

std::sort( idx.begin(), idx.end(), [&]( size_t a, size_t b )
    {
        return val[a] < val[b];
    } );

This sorts the index array to the following:

(0,10,30,20,1,31,21,11,2,22,12,32,3,13,23,33,4,14,24,34,5,15,25,35,6,16,26,36,7,17,27,37,8,28,18,38,9,29,19,39)

But I want the array to be in the following order:

(0,10,20,30,1,11,21,31,2,12,22,32,3,13,23,33,4,14,24,34,5,15,25,35,6,16,26,36,7,17,27,37,8,18,28,38,9,19,29,39)

Is there an easy way I can modify my lambda to get these values in the order specified by the last?

Cheers in advance!

You could use stable sort: http://en.cppreference.com/w/cpp/algorithm/stable_sort — Maksim Solovjov, Sep 10 '15 at 15:29
@MaksimSolovjov: Knew there'd be an easy solution :D Put that as an answer and I'lll accept it :) — Goz, Sep 10 '15 at 15:32

Maksim Solovjov · Accepted Answer · 2015-09-10T15:42:44.677

7

You should use std::stable_sort.

In your specific case, you could tweak the lambda to compare a with b when val[a] == val[b] but that would make your intention obscure to any future future developers that might stumble upon this code.

edited Sep 10 '15 at 15:42

answered Sep 10 '15 at 15:35

Maksim Solovjov

3,147
18
28

shivam mitra · Answer 2 · 2015-09-10T16:07:42.057

1

When val[a] == val[b], return the smaller of the two indexes.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
vector<int> val;
int compare(int a,int b)
{
    if(val[a] == val[b]) {
        return a < b;
    }
    return val[a] < val[b];
}
int main()
{
    vector<int> idx;
    int i;
    for(i = 0; i < 40; i++) {
        idx.push_back(i);
        val.push_back(i%10);
    }
    sort(idx.begin(),idx.end(),compare);
    for(i = 0; i < 40; i++) {
        cout<<idx[i]<<' ';
    }
}

edited Sep 10 '15 at 16:07

answered Sep 10 '15 at 15:39

shivam mitra

232
1
5
12

3

wtf is doing there? – Slava Sep 10 '15 at 15:50
It includes all the header files required. So, I don't have to write #include and #include in this case. Read more http://stackoverflow.com/questions/25311011/how-does-include-bits-stdc-h-work-in-c – shivam mitra Sep 10 '15 at 15:54
2

It includes many files that are not required. And it is not standard, so I think you should avoid it in examples. – Slava Sep 10 '15 at 16:00
Yes, I know that but in competitive programming, it takes a lot of time to include all the header files. – shivam mitra Sep 10 '15 at 16:03
1

Abusing implementation details of your compiler / standard library implementation is not a good idea because it a) is not portable between compilers and b) might break at any time. Just include the standard headers, it is not that hard but a whole lot safer. – Baum mit Augen Sep 10 '15 at 16:04
@shivammitra: What does that have to do with this question? Stop being lazy. – Blastfurnace Sep 10 '15 at 16:05
@shivammitra This is not "competitive programming", but a high quality Q/A repository. Stop confusing readers with this nonsense. – Baum mit Augen Sep 10 '15 at 16:06
Edited :) I won't repeat it here from now on :) – shivam mitra Sep 10 '15 at 16:10

std::sort using indices but maintaining index order

2 Answers2