Discussion :

[Josiane22]

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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!

[foetus]

Une idée

Tu gardes, une matrice pour ton maillage afin de stocker les propriétés d'un nœud (à toi de voir quel conteneur pour cela)
Ainsi, tu gardes l'accès maillage [i, j].

Et à côté, tu as un arbre AVL pour trier tes altitudes. (chaque nœud contient une altitude et un pointeur vers ton maillage [i, j]).
Éventuellement, chaque nœud de ton maillage a un pointeur vers un nœud de ton arbre AVL (lien bidirectionnel) : à tester si c'est utile

Parce qu'avec un arbre AVL, la recherche, la suppression et l'ajout sont optimisés (en O(log(n)))

Reste le chargement de ton arbre AVL, la place mémoire qu'il prend et si c'est compliqué de synchroniser ton maillage et l'arbre.

[Kaamui]

Ne serait-il pas envisageable pour toi de maintenir à jour les propriétés communes qui t'intéressent dans un objet global à toutes les mailles, une sorte de objMailleHandler, responsable de l'insertion/suppression des mailles ?

Si tu garantis dans ton code qu'on ne peut insérer/supprimer/opérer sur ta liste de maille autrement que par cet objet, alors il te suffit de maintenir par exemple un vector contenant l'historique des valeurs attribuées à Zmax, et à chaque ajout tu push si la ZMax de la maille insérée est plus grande que l'actuelle, puis tu pop à la suppression de la maille pour avoir la précédente qui redevient l'actuelle. Peut-être même qu'un historique de pointeurs des mailles concernées te donnerait accès à plus d'infos si besoin ensuite.

Egalement, juste au cas où :
https://cpp.developpez.com/faq/cpp/?...ker-mes-objets

Tu peux voir dans ce graphe qu'il existe des conteneurs de type priority_queue par exemple, potentiellement intéressant pour toi. Toutefois, il me semble que d'avoir à effectuer une recherche à posteriori est le signe ici qu'on a raté le moment où on avait l'information dans les mains (ici quand une opération d'insertion ou de suppression modifie potentiellement la valeur "statistique" lowestZMax, que tu souhaite connaitre à tout moment sans coût de recherche)

Attention toutefois, si tu pars sur l'idée d'un objectHandler, de ne pas lui donner trop de responsabilité. S'il est responsable des entrées/sorties pour tes mailles, il devrait être associé à un autre type d'objet, responsable de maintenir à jour le données statistiques de ta map de mailles.

[Bousk]

IMO pour l'accès rapide à [i,j] il te faut un tableau https://cpp.developpez.com/faq/cpp/?...au-de-tableaux
Si tu accèdes plus souvent à la maille la moins élevée que tu ne retires/ajoutes de maille, tu maintiens un pointeur vers la moins élevée que tu mets à jour quand tu ajoutes une maille si nécessaire, ou retires la maille la moins élevée
Éventuellement on pourrait imaginer un set pour stocker les altitudes si chaque maille en a une unique