Help on std::sort on pair variables

This works fine, if i declare a pair of <double, int>

Code:

std::vector< pair<double,int> >test;
	test.push_back(pair<double,int>(0.1,3));
	test.push_back(pair<double,int>(0.3,6));
	test.push_back(pair<double,int>(0.2,75));
	sort(test.begin(),test.end());

However when i used a pair of <double, CvPoint>, where CvPoint is a opencv struct, the compiler complains of

Code:

error C2784: 'bool std::operator <(const std::vector<_Ty,_Alloc> &,const std::vector<_Ty,_Alloc> &)' : could not deduce template argument for 'const std::vector<_Ty,_Alloc> &' from 'const CvPoint'
1>        c:\program files\microsoft visual studio 9.0\vc\include\vector(1320) : see declaration of 'std::operator <'

Is it possible to use a structure in a vector pair?

Heres the code:

Code:

struct CvPoint{
 int x;
 int y;
}

std::vector< pair<double,CvPoint> >test;
	test.push_back(pair<double,CvPoint>(0.1,cvPoint(1,2)));
	test.push_back(pair<double,CvPoint>(0.3,cvPoint(2,4)));
	test.push_back(pair<double,CvPoint>(0.2,cvPoint(3,6)));
	sort(test.begin(),test.end());

Unless you're using "using std:: pair", don't forget to prepend "std::" to "pair"...

Also, you'll need an operator< implemented for CvPoint. You'll need it for sort (last edit I said I didn't see why it would be required, but obviously you're SORTING, which needs the operator<, obviously).
Damn. That took me about 10 edits to get right :P.

Hi EVOEx,

Thanks for replying.

May I how can i implement an operator for CvPoint, and where should i put it?

I am sorting the paired values on the basis of increasing double values, with the corresponding CvPoint structures.

I wouldn't implement an operator in this case. Instead do this;

Code:

bool mycompare(const std::pair<double, CvPoint> &x, const std::pair<double, CvPoint> &y)
{
    // compare x and y, return true if we deem x < y, otherwise false
}

int main()
{
        std::vector< pair<double,CvPoint> >test;
	test.push_back(pair<double,CvPoint>(0.1,cvPoint(1,2)));
	test.push_back(pair<double,CvPoint>(0.3,cvPoint(2,4)));
	test.push_back(pair<double,CvPoint>(0.2,cvPoint(3,6)));
	sort(test.begin(),test.end(), mycompare);
}

If you really want to, name "mycompare" as "operator<" but, given that sorting a pair of anything can have multiple possible meanings, better to be specific in your choice of functions.

I *would* implement the operator<, as it's also useful would you ever want to use those points in things like sets (damned useful!).

Like this:

Code:

bool operator<(const CvPoint &p1, const CvPoint &p2)
{
  /* Code to compare here. If p1 < p2, return true, otherwise false */
}

What you consider to be less doesn't matter, as long as it's a legal operation (eg. the points can legally be sorted). You could use something like: it's less if p1.x is less than p2.x OR if p1.x is equal to p2.x and p1.y is less than p2.y... That should work.

Originally Posted by EVOEx

I *would* implement the operator<, as it's also useful would you ever want to use those points in things like sets (damned useful!).

Since one of the template parameters when creating a set is a comparator (eg a function or functor that is used to compare relative order of two objects) it is not necessary to implement the function as operator<.

Where I'm coming from is that there is a difference between saying "A is ordered before B" and "A is less than B". With a std::pair<double, CVPoint> the first statement may make sense, but the second may not. Since the STL allows the programmer to express the first concept, no need to make code more cryptic by pretending an operator<() makes sense when it doesn't.

If you got rid of this silly CvPoint thing, and just used a std:: pair< int, int >, then you'd get it for free. Your data type would then be std:: pair< double, std:: pair< int, int > >.

Originally Posted by brewbuck

If you got rid of this silly CvPoint thing, and just used a std:: pair< int, int >, then you'd get it for free. Your data type would then be std:: pair< double, std:: pair< int, int > >.

That's actually a moot point, as the original question concerned how to do it with CvPoint, not the merits of CvPoint versus other approaches.

In any event, you would only "get it for free" if you don't consider loss of readability or extendability as a cost.

If - for sake of discussion - the purpose of CvPoint is to represent two-dimensional coordinates, then code using it will be more readily understandable if those coordinates are named x and y rather than first and second. The reader does not have to remember to do a mental mapping "first means x" and "second means y", and does not have to be reminded (eg using a comment in code). Code that is more understandable is easier to get right, and easier (less costly) to maintain.

Representing the coordinates using an std::pair<> will make it significantly more difficult should the code ever need to be extended to represent three-dimensional coordinates, say (x, y, z), or four-dimensional coordinates, say (x, y, z, t).

I don't believe brewbuck necessarily intended to suggest that one should use that apporach, but rather that one simply could. His post is rather useful in that it shows how convenient std::pair can be, and what is easily possible when using it. Of course the downside is that it might push someone into doing something evil like this:

Code:

#define x first
#define y second

I'd take grumpy's advice.

Originally Posted by iMalc

I don't believe brewbuck necessarily intended to suggest that one should use that apporach, but rather that one simply could.

Given that he described the alternative as silly, I did not interpret it that way.

Originally Posted by iMalc

His post is rather useful in that it shows how convenient std::pair can be, and what is easily possible when using it.

I agree.

Originally Posted by iMalc

Of course the downside is that it might push someone into doing something evil like this:

Code:

#define x first
#define y second

I will admit I had more benign cases than that in mind when I wrote my post. Clearly, I need to refresh my memory of Murphy's Law, to reduce such lapses of misplaced optimism about programmer conduct ;)

Originally Posted by plasma

Hi EVOEx,

Thanks for replying.

May I how can i implement an operator for CvPoint, and where should i put it?

I am sorting the paired values on the basis of increasing double values, with the corresponding CvPoint structures.

The problem is that the operator < for std::pair is defined as:

Code:

return lhs.first < rhs.first || lhs.second < rhs.second;

So it will compare both the members in the pair, and not necessarily sort after the first value. Beware.

Originally Posted by Elysia

The problem is that the operator < for std:air is defined as:

Code:

return lhs.first < rhs.first || lhs.second < rhs.second;

So it will compare both the members in the pair, and not necessarily sort after the first value. Beware.

That would contradict how the standard defines operator<, so I would be surprised to find that happen.

(The standard says it is

Code:

lhs.first < rhs.first || (!(rhs.first < lhs.first) && lhs.second < rhs.second);

so that the second elements are compared only if the first elements compare equal.)

Originally Posted by Elysia

The problem is that the operator < for std::pair is defined as:

Code:

return lhs.first < rhs.first || lhs.second < rhs.second;

So it will compare both the members in the pair, and not necessarily sort after the first value. Beware.

I have no idea where that came from. No admissable less-than operator can ever look like that really.

tabstop shows what it actually looks like in any compiler header files I've ever seen.

Probably too quick a glance at the code, I guess.
It seems that it's...

Code:

	return (_Left.first < _Right.first ||
		!(_Right.first < _Left.first) && _Left.second < _Right.second);

...what Tabstop said.