Structure de données STL avec tri

Question

J'ai besoin d'une structure de données pouvant être triée automatiquement en fonction d'une structure.

struct{ 
    int key; 
    int comparisonValue(size of the vector); 
} 

J'ai besoin sous la forme suivante:

datastructure<struct, vector<int>> 

Lorsque la structure de données sont triées automatiquement en fonction de la comparisonValue et basée sur la valeur minimale de la valeur de comparaison, je voudrais obtenir le vecteur et ajouter des données à ce sujet.

Quelle structure de données pourrais-je utiliser? Puis-je utiliser la carte et y a-t-il un trieur personnalisé pour la carte?

Que faire si j'ai besoin de modifier la clé, dans ce cas la valeur de comparaison et de garder l'ordre trié?

Merci

Answer 1

std::map de la STL.

Par défaut, cette fonction trie les valeurs clés en les comparant à l'aide de std::less<Key>, qui appelle par défaut operator< sur les valeurs de clé. Par conséquent, vous pouvez définir une surcharge de operator< pour votre type de struct ::

bool operator<(const Key &a, const Key &b) 
{ 
    return (a.someField < b.someField); 
} 

Answer 2

» ... et en fonction de la valeur minimale de la valeur de comparaison, je voudrais obtenir le vecteur et ajouter des données à ce "

Si vous souhaitez obtenir le plus petit élément de toute la collection, vous pouvez préférer un std::priority_queue, en supposant que vous ne mettez à jour que le plus petit élément.

Sinon, c'est probablement ce dont vous avez besoin, comme le suggère Oli Charlesworth. Vous devriez probablement jeter un oeil à map méthodes lower_bound() et upper_bound().

Vous devez également savoir que les conteneurs STL conservent copies des objets. Par conséquent, si vous souhaitez que vos modifications soient répercutées ailleurs, vous devez stocker des pointeurs sur les objets. Ensuite, vous utiliserez un Functor séparé pour comparer les pointeurs en fonction de ce qu'ils pointent.