Discussion :

[Core8]

Bonjour à tous,

Voilà j'aurais voulu savoir si en C++ il est possible avec des list (ou vector, queue, ...) de faire ce que les méthodes suivantes font en Java avec le type List :

Code :

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

1
2
3
E get(int index) // retourne l'élément à la position index 
et
E remove(int index) // enlève l'élément à la position index, rechaîne la liste et retourne l'élément supprimé

En C++, j'ai vu qu'il faut passer par des iterators mais je n'ai pas réussi à accéder directement à un élément de la liste (comme le fait la méthode get) sans la parcourir et de même pour supprimer un élément.

Merci d'avance pour vos réponses

[loacast]

Avec les vector tu y accèdes comme avec un tableau :

monVector[i] = ...;

[Core8]

Avec les vector tu y accèdes comme avec un tableau :

monVector[i] = ...;

Oui, j'avais vu ça mais j'ai toujours le problème pour retirer un élément à une position donnée et rechaîner le vector.

[Tijee]

Ca se fait tout seul via la méthode erase(iterator)...

Exemple :

Code :

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

1
2
3
4
5
for(vector<le_type_des_objets_de_ton_vector>::iterator it = ton_vector.begin() ; it != ton_vector.end() ; ++it) {
     if(ta_condition_pour_que_ton_objet_soit_supprimé) {
          ton_vector.erase(it);
     }
}

[Laurent Gomila]

Ce qu'il faut savoir c'est que tu pourras toujours obtenir un itérateur très facilement à partir d'un indice :

Code :

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

1
2
3
std::vector<xxx> v;
std::vector<xxx>::iterator it = v.begin() + 5;
v.erase(it);

Mais les suppressions aléatoires dans un vecteur ne sont pas ce qu'il y a de plus rapide, en général on préfère les listes pour ça. Enfin bon ça dépend du contexte.

[Luc Hermitte]

Et quand tu envisages des retraits, il ne faut pas réfléchir en termes d'indices -- surtout dans les listes (qui sont chaînées).

Identifies l'élément qui t'intéresse par son itérateur (d'autant que toutes les fonctions de recherche renvoient des itérateurs, et non des indices), et sévis.

[Core8]

Ce qu'il faut savoir c'est que tu pourras toujours obtenir un itérateur très facilement à partir d'un indice :

Code :

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

1
2
3
std::vector<xxx> v;
std::vector<xxx>::iterator it = v.begin() + 5;
v.erase(it);

Mais les suppressions aléatoires dans un vecteur ne sont pas ce qu'il y a de plus rapide, en général on préfère les listes pour ça. Enfin bon ça dépend du contexte.

Tout d'abord, merci à tous pour vos réponses.

Sinon, Laurent (Gomila) le code que tu m'as donné pour les vector ne marche pas pour les list. Est-ce qu'il est possible de faire la même chose avec des list ou pas.

[Laurent Gomila]

Non, il n'y a que les itérateurs de vector qui sont de type "accès aléatoire". Pour tous les autres, il faut utiliser std::advance :

Code :

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

1
2
3
std::list<xxx> v;
std::list<xxx>::iterator it = v.begin();
std::advance(it, 5);

Mais bon, si tu en arrives à manipuler des indices avec des listes... Il y a un problème quelque part. Normalement tu devrais toujours arriver avec un itérateur.

[Core8]

Ce que je veux faire c'est au départ avoir une liste (un vector ou autre chose) qui contient tous les nombres qu'il est possible de tirer.
Et ensuite, lorsque qu'un nombre est tiré (d'après son indice dans la liste) je l'enlève de cette liste afin de ne pas le retirer.
Comme mon application lance une "simulation" je ne peux pas me permettre de parcourir à chaque fois la liste à la recherche du nombre puisque mon programme lance 1 000 000 de simulations à chaque exécution afin d'obtenir des résultats exploitables.

[Luc Hermitte]

Et ensuite, lorsque qu'un nombre est tiré (d'après son indice dans la liste)

Pourquoi tu manipules une liste avec des indices ? Ce n'est pas fait pour.

[HanLee]

Ah mais tu veux en fait obtenir une sorte de permutation.

Au lieu de tirer un indice au pif, puis le retirer, tu peux stocker toutes tes valeurs possibles dans un tableau, et le réordonner de manière aléatoire.

Pour ça, tu peux créer une permutation en faisant plein de transpositions au pif (comprendre : des swaps de 2 valeurs), d'après le théorème qui dit que toute permutation de taille n peut s'exprimer comme produit de (n-1) transpositions au plus, un truc comme ça.

Ya un algorithme, où en gros tu parcours chaque élément, et tu échanges sa valeur avec celle d'un autre élément dont l'indice est tiré aléatoirement, mais je sais pas s'il est valide.

-----

Une fois fini, tu parcours ton vecteur dans l'ordre, sans retirer d'éléments.

[Core8]

Pourquoi tu manipules une liste avec des indices ? Ce n'est pas fait pour.

Bah je ne sais pas trop quoi utiliser d'autre parce que dans le cas d'un tableau j'aurais des cases vides contrairement à une liste chaînée.
Si t'as d'autre chose à me proposer c'est le bienvenue.
J'avais dans l'idée de faire ce que je veux avec une liste mais si ce n'est pas bon.
Je suis ouvert.

Sinon, HanLee nan je ne veux pas faire une permutation.
Ma liste (tableau, vector, vous l'appelez comme vous voulez) va contenir toutes les positions (struct) libres dans une matrice. Ensuite, je tire aléatoirement une position dans la liste (ou ...) d'après son indice (c'est le chiffre tiré aléatoirement). Puis, je l'enlève de la liste pour ne pas le retirer. Et ainsi de suite jusqu'à ce que j'ai tiré toutes mes positions dont j'ai besoin.

[HanLee]

Oui, et ça revient au même que de tout arranger aléatoirement, et de parcourir le vecteur séquentiellement regarde bien !

Le fait de parcourir ton vecteur dans séquentiellement, c'est comme si tu retirais l'élément de la liste. Une fois derrière, c'est derrière, et il ne sera plus devant.

Tirer un indice au pif, c'est la même chose que prendre une valeur au pif, vu de l'autre côté.

[Core8]

Oui, et ça revient au même que de tout arranger aléatoirement, et de parcourir le vecteur séquentiellement regarde bien !

Le fait de parcourir ton vecteur dans séquentiellement, c'est comme si tu retirais l'élément de la liste. Une fois derrière, c'est derrière, et il ne sera plus devant.

Tirer un indice au pif, c'est la même chose que prendre une valeur au pif, vu de l'autre côté.

Bah en fait nan, ça ne correspond pas tout à fait à ce que j'ai besoin. Puisque lors de chaque simulation lancée des cases de ma matrice peuvent être ocuppées puis libérées et re-occupées et ... Ma liste contient toutes les positions libres au départ (toute la matrice). Ensuite, dans ma liste il faut que je puisse supprimer les positions occupées et par contre ajouter les positions qui redeviennet libres.