Polymorphic STL compare function (class cmp class, class cmp int) for sorting

Question

I'm implementing a game. I have a state tree and a set<> based priority queue that sorts the states on their costs. For this I have the < operator implemented as:

struct DereferenceCompareState : 
public std::binary_function<State*, State*, bool>
{

  bool operator()(const State* lhs, const State* rhs) const
  {
    verbose6("comparing " << lhs->getCost() << " with " << rhs->getCost());
    return lhs->getCost() < rhs->getCost();
  }

};

Now, I want to eliminate states that have higher cost than some number, but for this, I have to create a dummy state with the cost I want and do an upper_bound on the set. Is there a way to define an operator that works on state vs integer comparisons by for example adding to the struct above? Thanks

Answer 1

You can easily add more flexible comparison ability to struct DereferenceCompareState by overloading operator() more, but it won't help with what you're trying. The real problem you've come across is that std::set<T,Cmp>::upper_bound() only takes a key/value type (T) as argument. So no matter what you do to your comparison type, you won't be able to call s.upper_bound(5); The best thing to do is probably to just use a temporary State object like you described.

Answer 2

The problem is that set, by definition, is an associative container in which elements themselves are keys. What you seem to want, however, is a container where the key is rather an expression derived from the element, but not the element itself.

So, if you only ever do lookups on the cost of your state, then make it a map<int, State*> with cost being the key. If you want to do lookups on the state itself and on cost (and possibly other properties), then I would suggest that you use Boost MultiIndex, which lets you have multiple indices (including identity, like set) over a single container. If you use an ordered index on getCost(), you'll also get upper_bound() for that index which will do precisely what you want.