Pages

Saturday, January 28, 2012

A probable mistake while overloading the '<' operator

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 output of the given code is: 1 (I was surprised!)
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;
    }
Although this doesn't matter if you use a STL priority_queue. It can store more than one copy of the 'same' thing. But sometimes you need to use set, specially when deleting-nodes from the priority queue is important.

3 comments:

  1. Yeah , It's a common bug.
    btw, for time efficient reasons sometimes it's better to pass by reference.
    bool operator < (const T &obj) const

    ReplyDelete
    Replies
    1. ah yes.. somehow I keep ignoring this simple but important optimization.
      Thanks for pointing out! :)

      Delete