I was not aware of the following basic thing. See the code segment bellow:
struct T
{
int a, b;
T(){}
T(int _a, int _b){a=_a;b=_b;}
bool operator < (T obj) const
{
return a < obj.a;
}
};
int main()
{
set<T> S;
S.insert(T(0,0));
S.insert(T(0,1));
cout<<S.size()<<"\n";
return 0;
}
The overloaded operator '<' can not distinguish between T(0,0) and T(0,1) (pretty basic.. huh!)
I learnt this when writing the State class for a Dijkstra's code. I was using STL set as the priority queue. Some nodes were "mysteriously" vanishing!
The overloaded operator should look like this:
bool operator < (T obj) const
{
if(a!=obj.a)
return a < obj.a;
else
return b < obj.b;
}
Yeah , It's a common bug.
ReplyDeletebtw, for time efficient reasons sometimes it's better to pass by reference.
bool operator < (const T &obj) const
ah yes.. somehow I keep ignoring this simple but important optimization.
DeleteThanks for pointing out! :)
nice..i will do it
ReplyDelete