std::sort predicates.

[Gaminic]

Hello,

I'm trying to sort a vector of elements using the std::sort() algorithm, but the predicate I need isn't really straightforward, since it needs outside values.

The vector itself is just a list of ints, but they refer to other objects. These object id's have to be sorted by their relative distance to an external object.

The predicate should look something like this (but it obviously doesn't work):

bool distSort(int n, int i, int j) {
	return (distance[n][i] < distance[n][j]);
}

with "n" being the external element being compared to. A different external object is used depending on the situation, so hardcoding it isn't an option.

I was thinking of making a support class with simply a member "n" and a methods "getDistance(i)" and "setN()", so I could call a predicate "return (class.getDistance(i) < class.getDistance(j))" and set the N value between sort calls, but this seems very unelegant. Is there a more logical way to do it?

Coding my own sort algorithm would very likely be very inefficient compared to the <algorithm> one, and since it's probably going to be called a few hundred times, I'd prefer using the premade version.

Any help would be greatly appreciated!

[Albatross]

If they're just ints, then maybe non-type parameter templates are an option?

template <int n>
bool distSort(int i, int j) {
	return (distance[n][i] < distance[n][j]);
}

n would have to be relatively constant, though.

-Albatross

[ne555]

Or a functor

template<class T>
class dist_compare{
private:
  typedef std::vector< std::vector<T> > matrix;
  int n;
  const matrix &distance;
public:
  dist_compare(int n, const matrix &distance): n(n), distance(distance){}
  bool operator()(int i, int j){
    return (distance[n][i] < distance[n][j]);
  }
};

std::sort( /**/ dist_compare<int>(n, distance) );

A different external object is used depending on the situation

What is the situation? You mean that n could change in the middle of the algorithm, or just in another call?

Edit: I just realise that that was the algorithm you were thinking. The only change is that it uses a different object in every call, and avoids those evil getters and setters with the constructor and Demeter Tell, don't ask (responsibility) xP

[D80DSL3A]

@Albatross. A template which varies by value rather than by type? I would have never thought this possible! This language never ceases to amaze me.

@Gaminic.

I was thinking of making a support class with simply a member "n" and a methods "getDistance(i)" and "setN()", so I could call a predicate "return (class.getDistance(i) < class.getDistance(j))" and set the N value between sort calls, but this seems very unelegant. Is there a more logical way to do it?

There may be but I isn't this type of problem exactly what writing ones own predicate function is for?
I wish I knew how you are calculating the distance. I take it here to = abs(n*n-i*i).

I prepared 2 examples (good practice for me). A class based solution allows you to avoid using a global variable for the "external" object.

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

class compFunc
{
public:
	int N;
	bool operator()(int i, int j)const  // "distance" = | N*N-i*i |
	{
		return( abs(N*N-i*i) < abs(N*N-j*j) );
	}
};

int main()
{
	compFunc cf;
	vector<int> iv;
	iv.push_back(1);
	iv.push_back(3);
	iv.push_back(8);
	iv.push_back(6);	

	cf.N = 1;
	sort( iv.begin(), iv.end(), cf );// expecting 1 3 6 8
	for(vector<int>::iterator it = iv.begin(); it != iv.end(); ++it)
		cout << *it << " ";
        // repeat for a new N value
	cout << endl;
	cf.N = 4;// choosing a value which is a different "distance" from all 4 values in iv
	sort( iv.begin(), iv.end(), cf );// expecting 3 6 1 8
	for(vector<int>::iterator it = iv.begin(); it != iv.end(); ++it)
		cout << *it << " ";

	cout << endl;
	return 0;
}

I was curious to see if an ordinary global function would do as a predicate. It does, but then n is global (so it doesn't have to be passed to the function).

int n=0;
bool cF(int i, int j)
{
	return( abs(n*n-i*i) < abs(n*n-j*j) );
}

int main()
{
	compFunc cf;
	vector<int> iv;
	iv.push_back(1);
	iv.push_back(3);
	iv.push_back(8);
	iv.push_back(6);
	n = 1;
	sort( iv.begin(), iv.end(), cF );// expecting 1 3 6 8
	for(vector<int>::iterator it = iv.begin(); it != iv.end(); ++it)
		cout << *it << " ";

	cout << endl;
	n = 4;// choosing a value which is a different "distance" from all 4 values in iv
	sort( iv.begin(), iv.end(), cF );// expecting 3 6 1 8
	for(vector<int>::iterator it = iv.begin(); it != iv.end(); ++it)
		cout << *it << " ";
        cout << endl;
	return 0;
}

Either way the result of the sort is as expected. Program output:

1 3 6 8
3 1 6 8

[Gaminic]

Thanks for all the answers!

Albatross' method seems to be the one with the least overhead (no globals, no classes), so I've decided to go with that one. Wasn't aware that templates could be used that way!

[Gaminic]

Okay, apparently it's not as perfect as I hoped:

The line
sort(nr_temp.begin(), nr_temp.end(), nearSort<sNode>);
doesn't work; apparently I can't use a local variable as the argument. Is there a way around it or will I have to use one of the other methods?

[ne555]

I can't use a local variable as the argument.

That's because the template must be resolved at compile time. Don't know about a solution, but why you don't want to create an object? (which size is comparable to an int)

[Gaminic]

I'm not sure how time consuming creating and destructing an object is, but it seems like overkill to write an entire class (even one so small) for a simple sorting algorithm. Similarly, I didn't want to use a global variable, since the predicate is only used in very specific parts of the algorithm, but I guess the overhead of having a loose int lying around is negligible. I've just solved it that way, setting the global value locally when required (so basically fun2code's second suggestion).