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