Quel conteneur ?

Version imprimable

22/03/2008, 21h48
matteli

Quel conteneur ?

Bonjour,

je n'ai utilisé que les vector pour l'instant.

Pour le problème suivant je pense qu'un set ou une list sera plus approprié.

Mes valeurs sont des ushort.
L'ordre n'a pas d'importance.
J'aurais juste besoin d'en ajouter, retirer de façon aléatoire et de vérifier si une valeur est présente.

Quel est le conteneur le plus approprié sachant que je recherche la rapidité pour les 3 opérations ci-dessus.

Merci
22/03/2008, 21h54
raptor70

Je pense qu'un vector sera très bien. Car la list et le set sont plus couteux mais plus approprié aux données à trier.
22/03/2008, 22h17
matteli

Citation:

Envoyé par raptor70

Je pense qu'un vector sera très bien. Car la list et le set sont plus couteux mais plus approprié aux données à trier.

est ce que ça ne risque pas d'être couteux quand je retirerai un élément qui peut être au milieu.
22/03/2008, 22h21
raptor70

Citation:

Envoyé par matteli

est ce que ça ne risque pas d'être couteux quand je retirerai un élément qui peut être au milieu.

http://artis.imag.fr/~Xavier.Decoret...urs_part4.html

Regarde le chapitre "Choisir ton conteneur", tu devrais trouver toutes tes réponses en fonction de tes besoins...

Merci :google2:
22/03/2008, 23h13
yan

Citation:

Envoyé par raptor70

Regarde le chapitre "Choisir ton conteneur", tu devrais trouver toutes tes réponses en fonction de tes besoins...

:faq:
http://cpp.developpez.com/faq/cpp/?p...hoix_conteneur
22/03/2008, 23h20
raptor70

Citation:

Envoyé par Mongaulois

:faq:
http://cpp.developpez.com/faq/cpp/?p...hoix_conteneur

Il me semblait bien qu'il y avait quelquechose come ça dans la FAQ .. mais je l'avais pas trouvé ...:oops:
23/03/2008, 09h40
matteli

Citation:

Envoyé par Mongaulois

:faq:
http://cpp.developpez.com/faq/cpp/?p...hoix_conteneur

Je connaissais mais malgré celà, j'avais du mal à me décider.

Tout compte fait, je vais prendre un vector et je ne supprimerai pas au milieu mais je mettrai une valeur particulière et lors de l'ajout d'un élément, je parcourrai le tableau pour voir s'il y a un emplacement de libre.

merci
23/03/2008, 16h19
HanLee

Si l'ordre ne t'importe pas, retirer un élément au milieu ne coute pas cher : un swap avec l'élément à la fin, et un pop_back.
24/03/2008, 20h51
matteli

Citation:

Envoyé par HanLee

Si l'ordre ne t'importe pas, retirer un élément au milieu ne coute pas cher : un swap avec l'élément à la fin, et un pop_back.

Ahhhh, en effet. merci. :king:
25/03/2008, 22h39
JolyLoic

Citation:

Envoyé par HanLee

Si l'ordre ne t'importe pas, retirer un élément au milieu ne coute pas cher : un swap avec l'élément à la fin, et un pop_back.

Sauf que là, la recherche d'un élément va devenir chère. Avoir des données triées permet d'économiser sur la recherche, au prix d'une perte sur l'ajout/suppression. Perso, je regarderais quand même du côté d'un std::set.

Si les valeurs sont bornées, avec une borne pas trop haute, une autre solution est d'avoir un tableau de booléens, chaque booléen indiquant si l'élément d'index correspondant est présent.
26/03/2008, 18h58
HanLee

Citation:

Envoyé par JolyLoic

Sauf que là, la recherche d'un élément va devenir chère. Avoir des données triées permet d'économiser sur la recherche, au prix d'une perte sur l'ajout/suppression. Perso, je regarderais quand même du côté d'un std::set.

Si les valeurs sont bornées, avec une borne pas trop haute, une autre solution est d'avoir un tableau de booléens, chaque booléen indiquant si l'élément d'index correspondant est présent.

Ah non mais tu as raison en fin de compte, j'ai mal lu : j'avais pas vu qu'il allait vérifier l'existence ou non d'une valeur en fait.

Donc oui je préfèrerais en fait considerer std::set.

Je vais donner un peu plus d'explication car mon problème a un peu évolué.
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 struct structProvince { std::list<unsigned int> army; ... }; std::vector<structProvince> province; struct structArmy { unsigned short province; unsigned short country; ... }; std::vector<structArmy> army; struct structCountry { std::list<unsigned int> army; ... }; std::vector<structCountry> country;
Le nombre de pays et de provinces est défini au début du jeu. J'ai donc mis un vector.
C'est le conteneur "army" qui pose problème.

Les armées peuvent être crée pendant le jeu ou au lancement. Elles disparaissent pendant le jeu. (Je précise pendant le jeu car c'est un jeu temps réel donc nécessité de ne pas trop tarder à créer détruire l'armée).

Quand je crée une armée dans une province X avec mon pays Y :
- je crée une entrée dans le conteneur army (push_back) en entrant le pays Y et la province X (qui détermine dans quelle province se situe l'armée)
- je récupère le numéro d'entrée de l'armée (avec un army.size())
- j'ajoute ce numéro dans une liste pour la province X et pour le pays Y

Lorsque j'affiche mes sprites :
- en fonction de l'endroit où je me trouve sur la carte, je récupère une liste de provinces à "afficher".
- pour chaque province, je parcoure la liste d'armée présente. Je récupère un numéro d'armée si une est présente (en priorité une armée du joueur si le joueur est présent dans cette province sinon la première armée AI)
- je consulte l'armée en question dans le conteneur "army" et récupère le numéro de pays
- avec ce numéro de pays, je récupère le numéro du sprite à afficher

Quand une armée disparait :
- je fais un swap, pop_back dans le conteneur "army"
- je supprimer l'entrée dans le country et le province
- je change le numéro d'entrée de l'armée dans le country et le province de l'armée "swappé".

J'aurais aussi besoin de "voir" si tel armée d'un pays est présent dans tel province très souvent (un peu à la façon dont j'affiche mes sprites)

Voilà, voilà avec plus de précision, pensez-vous qu'un set ou un map soit plus approprié pour mon conteneur "army" ?

A noter que le nombre d'armée dans une province sera généralement faible (compris entre 0 et 5) mais qu'il peut monter occasionnellement. Idem pour le nombre d'armée pour un pays (en-dessous de la vingtaine sauf occasionnellement). Le nombre d'armée totale quant à lui est de l'ordre du millier.

27/03/2008, 21h48
JolyLoic

En gros, si j'ai bien compris, pour le conteneur d'army, tu veux pouvoir ajouter, enlever, et accéder rapidement à un élément. Cet élément est identifié par un numéro. Il y a un millier d'éléments à prendre en compte.

Déjà, avec ce genre de chiffre, je ne suis pas certain qu'une méthode se différencie pratiquement d'une autre. Pour l'insertion ou la suppression, une list battra un set/map (O(1) par rapport à O(log n)). Pour la recherche, l'inverse (O(n par rapport à O(log n)). Donc, tel quel, vu que le nombre de recherche est plus important, et qu'il y a bien plus à perdre entre log n et n qu'entre 1 et log n, je dirais donc d'utiliser un set/map.

Sauf qu'il y a une autre possibilité : Ne pas mettre dans les provinces des identifiant d'armée, mais directement des itérateurs sur le conteneur d'armée (ou des pointeurs sur les armées) (il faut s'assurer d'une stabilité des itérateurs, c'est bon pour list et set/map, mais attention alors à ne surtout pas utiliser un vector qui invalide les itérateurs/pointeurs pour un oui ou pour un non). Du coup l'accès depuis une province devient en O(1) lui aussi.

Je sais qu'à la base, je n'aime pas trop stocker des itérateurs/pointeurs vers une autre structure car en cas d'erreur (on a effacé une armée, on ne l'a pas retiré de la province), on a un truc qui pointe sur rien du tout et va faire planter, alors qu'un numéro, on peut toujours se rentre compte qu'il n'est plus présent, mais si c'est bien encapsulé, et que le gain le justifie...
04/04/2008, 15h55
matteli

Au fait, merci pour vos réponses.