Compile error with comparer function

Write here if you have problems with your C++ source code

Moderator: Board moderators

Post Reply
mamun
A great helper
Posts: 286
Joined: Mon Oct 03, 2005 1:54 pm
Location: Bangladesh
Contact:

Compile error with comparer function

Post by mamun »

My following code is getting compile error. Can anyone help me in this reagard?

Code: Select all

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

#define SIZE 100000

struct point{
	int x,y;
	point(){}
	point(int _x,int _y):x(_x),y(_y){}
	point operator-(point &p){point tmp(x-p.x,y-p.y);return tmp;}
	friend int operator^(point p1,point p2){return p1.x*p2.y-p1.y*p2.x;}
	bool operator<(point &p){return y<p.y || (y==p.y && x<p.x);}
};
vector<point> list;
point ref;

inline int cross_product(point &p0,point &p1,point &p2){
	return (p1-p0)^(p2-p0);
}

inline int sq_distance(point &p1,point &p2){
	return (p2.x-p1.x)*(p2.x-p1.x)+(p2.y-p1.y)*(p2.y-p1.y);
}

bool eqal(point &a,point &b){
	return cross_product(ref,a,b)==0;
}

bool comp(point &a,point &b){
	int cp=cross_product(ref,a,b);
	return cp<0 || (cp==0 && sq_distance(ref,a)>sq_distance(ref,b));
}

int convex_hull(vector<point> &points,int n){
	int i,top=0;
	static int stack[SIZE];
	for(i=1;i<n;i++)
		if(points[i]<points[top])
			top=i;
	swap(points[top],points[0]);
	ref=points[0];
	sort(points.begin(),points.end(),comp);
	points.erase(unique(points.begin()+1,points.end(),eqal),points.end());
	n=points.size();
	for(i=0;i<3;i++)	stack[i]=i;
	for(i=top=3;i<n;i++){
		while(cross_product(points[i],points[stack[top-1]],points[stack[top-2]])>0)
			top--;
		stack[top++]=i;
	}
	for(i=1;i<top;i++)
		points[i]=points[stack[i]];
	return top;
}

void main(){
	int p,i;
	while(scanf("%d",&p)==1){
		list.resize(p);
		for(i=0;i<p;i++)	scanf("%d%d",&list[i].x,&list[i].y);
		p=convex_hull(list,p);
		printf("%d\n",p);
	}
}
Here are the compile errors

Code: Select all

/usr/local/lib/gcc-lib/i686-pc-linux-gnu/2.95.3/../../../../include/g++-3/stl_algo.h: 
In function `const struct point & __median<point, bool (*)(point &, 
point &)>(const point &, const point &, const point &, bool (*)(point &, 
point &))':
/usr/local/lib/gcc-lib/i686-pc-linux-gnu/2.95.3/../../../../include/g++-3/stl_algo.h:1304:   
instantiated from `__introsort_loop<point *, point, int, bool (*)(point 
&, point &)>(point *, point *, point *, int, bool (*)(point &, point &))'
/usr/local/lib/gcc-lib/i686-pc-linux-gnu/2.95.3/../../../../include/g++-3/stl_algo.h:1332:   
instantiated from here
/usr/local/lib/gcc-lib/i686-pc-linux-gnu/2.95.3/../../../../include/g++-3/stl_algo.h:64: 
conversion from `const point' to `point &' discards qualifiers
/usr/local/lib/gcc-lib/i686-pc-linux-gnu/2.95.3/../../../../include/g++-3/stl_algo.h:64: 
conversion from `const point' to `point &' discards qualifiers
/usr/local/lib/gcc-lib/i686-pc-linux-gnu/2.95.3/../../../../include/g++-3/stl_algo.h:65: 
conversion from `const point' to `point &' discards qualifiers
/usr/local/lib/gcc-lib/i686-pc-linux-gnu/2.95.3/../../../../include/g++-3/stl_algo.h:65: 
conversion from `const point' to `point &' discards qualifiers
/usr/local/lib/gcc-lib/i686-pc-linux-gnu/2.95.3/../../../../include/g++-3/stl_algo.h:67: 
conversion from `const point' to `point &' discards qualifiers
/usr/local/lib/gcc-lib/i686-pc-linux-gnu/2.95.3/../../../../include/g++-3/stl_algo.h:67: 
conversion from `const point' to `point &' discards qualifiers
/usr/local/lib/gcc-lib/i686-pc-linux-gnu/2.95.3/../../../../include/g++-3/stl_algo.h:71: 
conversion from `const point' to `point &' discards qualifiers
/usr/local/lib/gcc-lib/i686-pc-linux-gnu/2.95.3/../../../../include/g++-3/stl_algo.h:71: 
conversion from `const point' to `point &' discards qualifiers
/usr/local/lib/gcc-lib/i686-pc-linux-gnu/2.95.3/../../../../include/g++-3/stl_algo.h:73: 
conversion from `const point' to `point &' discards qualifiers
/usr/local/lib/gcc-lib/i686-pc-linux-gnu/2.95.3/../../../../include/g++-3/stl_algo.h:73: 
conversion from `const point' to `point &' discards qualifiers

Krzysztof Duleba
Guru
Posts: 584
Joined: Thu Jun 19, 2003 3:48 am
Location: Sanok, Poland
Contact:

Post by Krzysztof Duleba »

The compiler is telling you everything, just read the error message and fix the code.

Hint: why are you using references when you should be using const-references? In particular using references in comp breaks the interface of comparators.
For millions of years, mankind lived just like the animals. Then something happened which unleashed the power of our imagination. We learned to talk and we learned to listen...

mamun
A great helper
Posts: 286
Joined: Mon Oct 03, 2005 1:54 pm
Location: Bangladesh
Contact:

Post by mamun »

Thanks. :)
Changing

Code: Select all

bool comp(point &a,point &b)
bool eqal(point &a,point &b)
inline int sq_distance(point &p1,point &p2)
inline int cross_product(point &p0,point &p1,point &p2)
to

Code: Select all

bool comp(const point &a,const point &b)
bool eqal(const point &a,const point &b)
inline int sq_distance(point p1,point p2)
inline int cross_product(point &p0,point p1,point p2)
resolved the problem. I'd come with such because I'm trying to use a global variable in the comparators.

Krzysztof Duleba
Guru
Posts: 584
Joined: Thu Jun 19, 2003 3:48 am
Location: Sanok, Poland
Contact:

Post by Krzysztof Duleba »

The use of reference in cross product is still incorrect - you're not changing p0 inside cross_product, are you? Also in most cases functions like sq_distance and cross_product should pass their arguments by const references instead of values (the only exceptions are primitive types and very small classes that are cheaper to copy than to reference).
For millions of years, mankind lived just like the animals. Then something happened which unleashed the power of our imagination. We learned to talk and we learned to listen...

mamun
A great helper
Posts: 286
Joined: Mon Oct 03, 2005 1:54 pm
Location: Bangladesh
Contact:

Post by mamun »

Thank you Krzysztof Duleba. I've rewritten sq_distance() as

Code: Select all

inline int sq_distance(const point &p1,const point &p2)
But if I try to pass the arguments by const references to cross_product() as well then I come with new compile errors which seems to be related to the operator-().

Krzysztof Duleba
Guru
Posts: 584
Joined: Thu Jun 19, 2003 3:48 am
Location: Sanok, Poland
Contact:

Post by Krzysztof Duleba »

Oh, that's right. operator- should use const references, other operators too. And most of the time they should be const as well, to promise not to modify the objects they are operating on (as in bool operator-(const point &p)const{...} - note the second const that applies to the implied argument).

BTW: main should return int, not void.

Another hint: turn on the highest level of warnings in your compiler (I usually use -Wall -W -Wshadow and even -Werror). You will avoid many silly mistakes this way (I know I have).
For millions of years, mankind lived just like the animals. Then something happened which unleashed the power of our imagination. We learned to talk and we learned to listen...

mamun
A great helper
Posts: 286
Joined: Mon Oct 03, 2005 1:54 pm
Location: Bangladesh
Contact:

Post by mamun »

Thank you so much Krzysztof Duleba. You're damn expert in C++.

Post Reply

Return to “C++”