Search code examples
c++c++11setcomparison-operatorsmultiset

Custom comparison operator for custom struct in multiset C++


I have the following structure

 struct Node                                                         
{
    int x0,y0,g,h,f;
    int *Grid[N][N];
    Node* parent=NULL;
    Node(int x=0,int y=0,int G=0,Node* node=NULL)
    {
        x0=x;
        y0=y;
        g=G;
        parent=node;
    }
}

and the multiset definition as follows

multiset<Node*,GridLess>open_list;

Gridless is the initial structure for comparison operator.

struct GridLess                                                                     
{
    bool operator()(const Node *a,const Node *b) const
    {
        for(i=0;i<N;i++)
        {
           for(j=0;j<N;j++)
           {
               if(*a->Grid[i][j]!=*b->Grid[i][j])
               {
                   return *a->Grid[i][j]<*b->Grid[i][j];
               }
           }
        }
        return false;
    }
};

My basic need was to find the Node in the open_list which has the same elements at same positions in grid using multiset::count or multiset::find which is completed by the above comparison operator.

Now I want to the Node in the open_list which has the same elements at same positions in grid as well as the same Node::g and Node::f

This is what I tried to use and failed

struct GridLess                                                                    
{
    bool operator()(const Node *a,const Node *b) const
    {
        for(i=0;i<N;i++)
        {
           for(j=0;j<N;j++)
           {
               if(*a->Grid[i][j]!=*b->Grid[i][j])
               {
                   return *a->Grid[i][j]<*b->Grid[i][j]||(*a->Grid[i][j]==*b->Grid[i][j]&&a->g<b->g)||((*a->Grid[i][j] == *b->Grid[i][j])&&(a->g==b->g)&&a->f<b->f);
               }
           }
        }
        return false;
    }
};

Introducing two Nodes in the open_list with same grid but different g or f still results in count=2.

I tried checking for just the Grid and Node::g with the following

return *a->Grid[i][j]<*b->Grid[i][j]||(*a->Grid[i][j]==*b->Grid[i][j]&&a->g<b->g);

Even that doesn't work.

I need a comparison operator for this problem and explanation of how it works.

EDIT

I figured I am not clear with the bool operator() function as in when we write return a<b I understand it will return true if a<b but what will it return if a==b or a>b if this could be explained together with the question it would be really helpful.


Solution

  • You comparison of the g and f members has to be outside of the loop. As long as it is inside the loop, you do not compare the g and f members in case the Grid members are equal.

    struct GridLess                                                                     
    {
        bool operator()(const Node *a,const Node *b) const
        {
            for(i=0;i<N;i++)
            {
               for(j=0;j<N;j++)
               {
                   if(*a->Grid[i][j]!=*b->Grid[i][j])
                   {
                       return *a->Grid[i][j]<*b->Grid[i][j];
                   }
               }
            }
            return std::tie(a->g, a->f) < std::tie(b->g, b->f);
        }
    };