How to check a multiset if a certain struct member exists, other than with a for loop?

Question

I am altering a relaxed A* program to use A* instead. As part of the A* algorithm there is the check:

if neighbor not in openSet
   openSet.add(neighbor)

The openSet is a:

multiset<cells> OPL;

With cells being:

struct cells {
    int currentCell;
    float fCost;
};  

So, I would like to add this check whether the neighbor already exists in the openSet to my code. However, a struct in a multiset is something I've not worked with before. The solution I've arrived at for now was inspired by this thread and works as such:

for (std::multiset<cells>::iterator it = OPL.begin(); it != OPL.end(); it++)
{
      cells const & f = *it;
      if(f.currentCell==neighborCell){
          return false;
      }
}
return true;

However, this seems inefficient. Originally I tried to see if I could use OPL.find() or something instead of having to run through the entire openSet each time, but I couldn't get it to work.

So I've come here to see whether some smart people have a better solution I can use and learn from ^^?

Answer 1

openSet should be a multimap from currentCell to fCost. Then your problem is easy.

What more, I'm not sure what multi earns you -- you usually don't care about sub-optimal paths when doing A*.

...

You can also use a cells with -INF and +INF in the fCost field and do a lower/upper bound on them (assuming that the fCost must be finite), forming a range of entries that match your currentCell.

Possibly easier is a lower bound, followed by a linear search until you are at the end of the list or find a currentCell that matches/doesn't match what you want.

cells tmp = neighborCell;
tmp.fCost = -std::numeric_limits<double>::infinity();
auto it = OPL.lower_bound(tmp);
if (it == OPL.end()) return false;
return it->currentCell == tmp.currentCell;

In addition, in later versions of C++ you can have what is known as a "transparent comparator". This one can intelligently know about "I just want the current cell", and do an equal_range directly.