Fonction de comparaison STL polymorphe (classe classe cmp, classe cmp int) pour le tri

Question

Je suis en train d'implémenter un jeu. J'ai une arborescence d'états et une file d'attente de priorité basée sur <> qui règle les états sur leurs coûts. Pour cela, je dois l'opérateur < mis en œuvre:

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(); 
    } 

}; 

Maintenant, je veux éliminer les états qui ont un coût plus élevé que certains nombre, mais pour cela, je dois créer un état factice avec le coût que je veux et faire un upper_bound sur l'ensemble. Existe-t-il un moyen de définir un opérateur qui travaille sur les comparaisons entre états et entiers en ajoutant par exemple à la structure ci-dessus? Merci

Answer 1

Vous pouvez facilement ajouter une capacité de comparaison plus flexible à struct DereferenceCompareState en surchargeant operator() plus, mais cela ne va pas aider avec ce que vous essayez. Le vrai problème que vous avez rencontré est que std::set<T,Cmp>::upper_bound() prend seulement un type clé/valeur (T) comme argument. Donc, peu importe ce que vous faites pour votre type de comparaison, vous ne serez pas en mesure d'appeler s.upper_bound(5); La meilleure chose à faire est probablement d'utiliser simplement un objet Etat temporaire comme vous l'avez décrit.

Answer 2

Le problème est que set, par définition, est un conteneur associatif dans lequel les éléments eux-mêmes sont des clés. Ce que vous semblez vouloir, cependant, est un conteneur où la clé est plutôt une expression dérivée de l'élément, mais pas l'élément lui-même. Donc, si vous ne faites que des recherches sur le coût de votre état, faites-en un map<int, State*> avec le coût étant la clé. Si vous voulez faire des recherches sur l'état lui-même et sur le coût (et éventuellement d'autres propriétés), alors je suggère que vous utilisez Boost MultiIndex, ce qui vous permet d'avoir plusieurs indices (y compris l'identité, comme ensemble) sur un seul conteneur. Si vous utilisez un index ordonné sur getCost(), vous obtiendrez également upper_bound() pour cet index qui fera exactement ce que vous voulez.