Discussion :

[pixelou]

Bonjour,
Je débute encore un peu en programmmation et j'aurais besoin de réaliser un programme fonctionnant ainsi :
avec la donnée de n listes, on peut calculer une n+1 ème liste.
On veux ensuite attacher cette liste à la suite des n précédentes et comme on a plus besoin de la première, on l'oublie
Il y a par conséquent beaucoup d'itérations, mais aucune copie de listes.

J'ai pensé dans un premier temps créer n+1 vector<l'objet des listes>
n+1 pointeurs vers ces vector
on calcul le vecteur n+1
on décale les pointeurs d'un cran
on recommence

Seulement ce principe apparement simple implique de travailler avec un tableau de pointeurs vers des vectors , et j'ai un peu de mal à m'y retrouver.

Existe-t-il une méthode plus simple?
merci d'avance

[pixelou]

sinon je pourrais peut-être accéder directement à la liste de vectors sans passer par les pointeurs, et en utilisant, par exemple un modulo dans mes appels au tableau

à la ième itération, le dernier tableau calculé est le .... i mod(n) ème il me semble. On accède assez facilement au n états précédents.

Que pensez-vous de cette solution?

[autre mickael]

Salut,

Je suis pas beaucoup plus avancé que toi donc "à prendre avec des pincettes" :

Tu peux utiliser des listes plutôt que des vecteurs :

Code :

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

1
2
3
4
5
 
std::list<std::vector<objet>> ma_liste;
//pour rouler :
ma_liste.push_back(un_nouveau_vecteur); //ajout à la fin
ma_liste.pop_front(); //suppression du premier

Après c'est à toi d'initialiser la liste avec

Code :

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

1
2
3
4
5
 
for(int i = 0; i< n; i++)
{
   ma_list.push_back(un_vecteur);
}

à moins que tu sois obligé d'utilisé des vecteurs...

[Xtrem_Voyageur]

Bonjour,

Tu ne souhaites donc que conserver N listes dans ta structure de données en supprimant la plus ancienne qui devient inutile.
Une bonne solution est donc d'utiliser un conteneur qui respecte le principe
FIFO (first in, first out). Une file correspond donc parfaitement à ta situation.
Tu peux donc utiliser queue basé par défaut sur un deque.

Code :

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

1
2
 
std::queue<T>

Ce conteneur est parfait pour insérer des éléments en fin, et en extraire au début (FIFO)

Tu peux ne stocker qu'un pointeur de tes listes.

Code :

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

1
2
 
std::queue<std::list<ton_type>*>

Tu peux alors ajouter des éléments en fin avec

Code :

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

1
2
3
 
void push(const value_type& v);
//push(ptr_list); où ptr_list est un pointeur de liste std::list<ton_type>* ptr_list

et en retirer au début avec

Code :

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

1
2
 
void pop();

P.S : tu parles tout d'abord de vecteurs de liste, puis de liste de vecteurs.
Quel est l'objet avec lequel tu travailles vraiment.
Quand tu dis calculer un (n+1)ème élément à partir des n premiers. Quels sont ces éléments, des listes ou des vecteurs?

[pixelou]

désolé pour la réponse tardive,
Xtrem_Voyageur : ta réponse est tout à fait pertinente par rapport à mon problème, j'utilise une liste de n vectors<voiture>, voiture étant un classe de mon programme avec un id, une position, un vitesse etc...
Le calcul donne les voitures à l'étape n+1 en fonction des n précédents états.
Je peux en effet remplacer la liste de vectors par un queue, car c'est bien "premier arrivé premier sorti" (j'ai vu ça sur le diagramme qui aide à choisir les conteneurs de la stl ).
J' hésite quand même à utiliser le queue, car il faut une copie entière du vector<voiture> calculé à chaque boucle lors du push, non? à moins de travailler avec des pointeurs, mais c'est très lourd dans l' écriture du code avec beaucoup de déréférencements. D'autre part, le queue est assez facile à réimplémenter dans mon code, je pense que je vais rester sur une méthode simple pour l'instant, puis l'élaborer ensuite lorsque les bases seront posées.

[Xtrem_Voyageur]

Salut, je ne suis toujours pas sûr de bien saisir ta structure de données.
Ce que je crois comprendre :
Tu as en tout et pour tout N vector<voiture> et tu souhaites pourvoir produire un nouveau vector<voiture> à partir des N autres. Et tu cherches dans quel conteneur tu pourrais stocker ces N vector<voiture>
Si tel est le cas, oui la queue peut représenter une solution acceptable.

Tu implémentes donc une queue<vector<voiture>>
Maintenant, le problème de copie. Je sais pas quelles sont les opérations que tu souhaites réaliser par la suite. Mais dans l'immédiat tu me sembles juste faire les opérations suivantes:
1. Créer un vector<voiture>
2. Le placer dans ta queue par référence et donc il n'y a pas copie.

Pour tes calculs tu disposes donc d'une queue de N vector<voiture> de taille N. Tu crées un nouveau vector<voiture> x. En parcourant ta queue, tu peux calculer et donner les bonnes valeurs que tu souhaites donner à ce vecteur. Tu l'ajoutes à ta queue, tu retires le premier vecteur dont tu n'as plus besoin avec pop.
L'élément 'vecteur' qui était le numéro 1 devient donc l'élément 0. Ton nouveau vecteur ajouté x devient l'élément N-1 une fois le pop effectué.
Cela t'évites à devoir jouer a déplacer des éléments comme tu aurais dû faire avec d'autres structures, par exemple un vector<vector<voiture>>. Avec la queue, l'ordre est conservé naturellement, tu n'as pas besoin d'effectuer de roulement, ou de mémoriser un index et jouer avec des modulos.

Maintenant si tu dois effectuer d'autres opérations qui nécessitent des échanges dans ta structure alors oui les des pointeurs vers des vector<voiture> seraient plus appropriés. Les pointeurs agissent comme des descripteurs, il suffit de swap les adresses et hop les éléments sont tels qu'on le souhaite sans ce besoin de copier tout l'objet.