6

I have two vectors with same sizes

vector<float> predictions;      //say {1.22, 3.22, 2.22, 4.22}
vector<int> indices;            //say {0, 1, 2, 3}

I sorted the values in predictions in descending order using

std::sort(predictions.rbegin(), predictions.rend());     //gives {4.22, 3.22, 2.22, 1.22}

Now I want to sort indices simultaneously with the predictions.

//to get {3, 1, 2, 0}

How do I do it without using boost and custom templates?

Sujit
  • 143
  • 2
  • 13
  • 10
    Why not boost? **Why not templates?** – Vittorio Romeo Jan 19 '16 at 13:42
  • 1
    Write your own sort function that takes both and whenever you swap an element in one do the same swap in the other. – NathanOliver Jan 19 '16 at 13:42
  • 3
    I don't get why people keep wanting to not use convenient C++ features. – Hatted Rooster Jan 19 '16 at 13:43
  • 2
    Create a class containing a prediction and an index, and sort a vector of those instead – dreamlax Jan 19 '16 at 13:43
  • @Hacketo It's weird though, templates are a core feature of C++. If your professor teaches you C++ and disallows templates he's doing it wrong. – Hatted Rooster Jan 19 '16 at 13:46
  • @JameyD Speaking from what I have seen and what I went through in collage most beginning C++ classes start of as C using C++ syntax and they do not introduce "C++" until the end or the next level class. – NathanOliver Jan 19 '16 at 13:48
  • @SuJit Not understanding them is not an excuses not to use them. You should learn how templates work as they are a core principal of C++. – NathanOliver Jan 19 '16 at 13:48
  • 3
    Your requirements are impossible. `std::vector` is a template and you cannot use a template without using a template. – eerorika Jan 19 '16 at 13:49
  • 1
    As is `std::sort`; it's templated on the iterator type, which is itself templated on the `vector` type. – ShadowRanger Jan 19 '16 at 13:50
  • @NathanOliver and Vittorio Please see the Answer I added. If the things can be so simple, why should I use heavy boost or create my own templates? – Sujit Jan 20 '16 at 06:54
  • I have edited the question header. I wanted the solution where I won't have to 'use' boost or 'create' my own template. – Sujit Jan 20 '16 at 07:02
  • An alternative solution to the problem might be to only sort indices (using predictions as key, as rgcldr suggested) and leave predictions unsorted. Then you can look up predictions via the indices as needed. – M.M Jan 21 '16 at 04:22

5 Answers5

8

You can combine these two vectors into one with type like std::vector<std::pair<int, float>> and sort it instead. The compare function can be like this:

bool compareFunc(std::pair<int, float> &a, std::pair<int, float> &b)
{
    return a.second > b.second;
}

And sort the combined data like this:

std::sort(data.begin(), data.end(), compareFunc);

After this, you can get the sorted parts, i.e. its first component.

herohuyongtao
  • 49,413
  • 29
  • 133
  • 174
  • Sorry, but I am still not getting. How do I use compare function? – Sujit Jan 19 '16 at 14:12
  • I did this: std::vector> predictions; std::pair p = {j, pixel[j]}; predictions.push_back(p); – Sujit Jan 19 '16 at 14:13
  • Thanks for help! I did it without compareFunc; std::vector> predictions; sort(predictions.rbegin(), predictions.rend()); – Sujit Jan 20 '16 at 06:22
  • It's actually vector> predictions; sort function sorts vector by it's first component. – Sujit Jan 20 '16 at 06:46
4

This is slower, but it doesn't require pairing the data and doesn't require allocating a temp vector:

    std::sort(indices.begin(), indices.end(),
          [&predictions](size_t i, size_t j)
          {return predictions[i] > predictions[j];});
    std::sort(predictions.begin(), predictions.end(),
          std::greater<float>());
rcgldr
  • 27,407
  • 3
  • 36
  • 61
3

@herohuyongtao 's answer is good, but uses templates. You should learn templates. If you don't want to do this though, just create your own struct

struct MyPair
{
    float prediction;
    int index;
};

and your own compare function

bool compare(MyPair &a, MyPair &b) { return a.prediction > b.prediction; }

Then bundle your vectors into a single vector<MyPair> and use std::sort on that and your compare.

Of course, vector<MyPair> is a template. So was vector<int>. You should learn templates!

Sideshow Bob
  • 4,566
  • 5
  • 42
  • 79
0

This is what I finally used, suggested by @herohuyongtao and it's working as expected.

std::vector<std::pair<float, int>> predictions;
float * pixel = output.ptr<float>( 0 );
for ( int j = 0; j < output.cols; ++j ) {
    predictions.push_back({pixel[j], j});
}
std::sort(predictions.rbegin(), predictions.rend());
Sujit
  • 143
  • 2
  • 13
0

Sort the indices (assuming it is 0 to N sequentially) like:

std::sort(indices.begin(), indices.end(), compareFunc);

using a compare function like:

bool compareFunc(int &a, int &b)
{
    return predictions[a] > predictions[b];
}

This will sort only indices but predictions can be accessed in sorted order using index values from indices!

Complete Code:

#include <vector>
#include <algorithm>
#include <iostream>

using namespace std;

vector<double> predictions{ 1.22, 3.22, 2.22, 4.22 };
vector<int> indices{ 0, 1, 2, 3 };

bool compareFunc(int &a, int &b) {
    return predictions[a] > predictions[b];
}

int main()
{
    std::sort(indices.begin(), indices.end(), compareFunc);
    for (auto i: indices) {
        cout << i << "\t" << predictions[i] << endl;
    }

    return 0;
}
mahendra230668
  • 105
  • 1
  • 5