vector sort just reversing input with custom comparator

Question

I get some strange behavior when sorting a c++ vector with at custom comparator class.

I want to sort a array of indexes based on some values in an other array. But as far as I can see the sort function just reverses my indexes. I've done some logging of the compare function, at it seems to be working just fine.

Is there anyone who can spot what I'm doing wrong?

My code:

template<class T>
class Comparator {
   vector<T> & data;
public:
  bool operator()(int a, int b) {
    return data.at(a) < data.at(b) ? -1 : (data.at(a) > data.at(b) ? 1 : 0);
  }

  Comparator(vector<T> & data) : data(data) {}
};

void sortTest2() {
  //SETUP
  int n = 5;
  vector<int> indexes(n);
  newIdAr(indexes, n); //init to {0,1,2,3,4}
  vector<double> data(n);
  randomData(data, n); //Init to radom data
  Comparator<double> comparator(data);

  //TEST
  print(indexes, data, n); // Prints [0.00125126, 0.563585, 0.193304, 0.808741]
  sort(indexes.begin(), indexes.end(),comparator);
  print(indexes, data, n); // Prints [0.808741, 0.193304, 0.563585, 0.00125126]
  sort(indexes.begin(), indexes.end(),comparator);
  print(indexes, data, n); // Prints [0.00125126, 0.563585, 0.193304, 0.808741]
  cout << "Shuffle" << endl;
  random_shuffle(indexes.begin(), indexes.end());
  print(indexes, data, n);
  sort(indexes.begin(), indexes.end(), comparator);
  print(indexes, data, n);
}

My output:

[0.00125126, 0.563585, 0.193304, 0.808741, 0.585009]
[0.585009, 0.808741, 0.193304, 0.563585, 0.00125126]
[0.00125126, 0.563585, 0.193304, 0.808741, 0.585009]
Shuffle
[0.193304, 0.00125126, 0.585009, 0.563585, 0.808741]
[0.808741, 0.563585, 0.585009, 0.00125126, 0.193304]

Code for the auxiliary functions:

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

void print(vector<int> & sort, vector<double> & data, int N) {
  cout << "[";
  for (int i = 0; i < N - 1; ++i) {
    cout << data[sort[i]] << ", ";
  }
  cout << data[sort[N - 1]] << "]" << endl;
}

void newIdAr(vector<int> & ar, int N) {
  for (int i = 0; i < N; ++i) {
    ar[i] = i;
  }
}

void randomData(vector<double> & data, int n) {
  for (int i = 0; i < n; ++i) {
    data[i] = ((double) rand()) / RAND_MAX;
  }
}

mfontanini · Accepted Answer · 2012-03-11 02:57:59Z

2

Comparators should return true if the first argument is lower than the second one, or false otherwise. Returning 0, -1 and 1 is invalid in your code.

You could realize this by analizing the comparator's operator() signature:

bool operator()(int a, int b)

I believe your implementation should be:

bool operator()(int a, int b) {
    return data.at(a) < data.at(b);
}

answered Mar 11, 2012 at 2:57

mfontanini

22k5 gold badges72 silver badges74 bronze badges

Sign up to request clarification or add additional context in comments.

Collectives™ on Stack Overflow

vector sort just reversing input with custom comparator

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related