Quel conteneur pour recherche rapide ?
Bonjour tout le monde,
Je dispose d'un espace maillé.
Chaque maille est:
- définie par un couple <i,j> (indices de la maille dans la carte)
- dispose de plusieurs propriétés, dont celle qui nous intéresse aujourd'hui, l'altitude maximum sur la maille (Zmax).
L'un de mes besoins est de pouvoir rapidement accéder à la maille d'indice (i,j).
J'ai donc mis en place un std::pair<int,int> pour représenter la position de ma maille, ainsi qu'un objet "objMaille" regroupant toutes ses propriétés.
Toutes ces mailles sont ensuite regroupées dans une std::map, dont la clé est le std::pair. On a donc:
Code:
1
2
|
liste = std::map<std::pair<int,int>,objMaille> |
Il est donc facile d'accéder à une maille (i,j). Ca tombe bien, je dois le faire assez souvent.
Code:
1
2
3
4
| std::pair<int,int> pair;
pair.first = i;
pair.second = j;
auto maille = liste.find(pair); |
Le soucis, c'est qu'à un autre moment du code, j'ai besoin de trouver la maille de la liste qui a l'altitude la plus faible.
Je n'ai pas trouvé mieux pour le moment que de balayer toutes les mailles de la map à la recherche de la bonne. C'est assez coûteux.
Le problème, c'est que je dois faire ça assez souvent aussi (des mailles sont supprimées, puis remplacées par de nouvelles constamment).
J'essaye de trouver mieux, mais je ne m'en sors pas...
J'ai pensé à stocker les mailles dans un std::vector, puis les trier (avec sort()) sur l'altitude.
Mais ce que je gagne sur la recherche de la maille ayant la plus faible altitude (c'est la première du vector), je le perd sur la recherche de la maille d'indices i,j (je suis obligé de balayer le vector). On ne gagne rien.
J'ai pensé à créé à la fois la map et le vector (pour utiliser l'un ou l'autre en fonction du besoin), mais ça ne résoud rien:
à chaque fois que je dois ajouter/supprimer une maille dans la map, je dois aussi l'ajouter/supprimer dans le vector.
Et dans le cas d'une suppression, il faut la retrouver dans le vector ce qui nous ramène au problème précédent.
Auriez-vous une idée pour mon problème?
Existerait-il un conteneur tout fait adapté à mon besoin?
Merci d'avance pour vos réponses!
