Piles et itérateur

Bonjour à tous,

Je souhaite créer une classe pile afin de stocker des données et d'effectuer des opérations sur ces données. Notamment celle ci :

SWAP : inversion de l'élément numéro x et l'élément numéro y de la pile (où
x et y sont les arguments entier de l'opérateur)

Il me faut donc mettre en place un itérateur afin d'accéder séquentiellement à tous les éléments de la pile. Mais je ne vois pas du tout comment l'implémenter et tout ça reste assez flou pour moi.

Pourriez vous m'éclairer sur ce point?:oops:

http://www.cplusplus.com/reference/stl/deque/

Hummm, je vois pas bien cob59, tu penses qu'il serait mieux d'utiliser un deque ou c'est juste pour la structure du SWAP ?

Désolé mais je suis un peu pommé :cry:

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

// Création d'une pile d'entiers std::deque<int> pile; pile.push_back(1); pile.push_back(2); pile.push_back(3); pile.push_back(4);   // Parcours de la pile via un itérateur for (auto it=pile.cbegin(), itEnd=pile.cend(); it!=itEnd; ++it) { cout << *it << endl; }   // Echange d'éléments std::swap( pile[0], pile[1] );

---

Pour échanger des éléments, utilise simplement la fonction std::swap (la fonction membre std::deque<T>::swap permet seulement d'intervertir des deque entre elles).
Note qu'il existe un type std::stack qui correspond plus exactement à une pile. Il s'agit seulement d'une deque "dégradée", dont l'interface est moins fournie (pas d'itérateurs).

Ah je commence à y voir un peu plus clair :D

Mais du coup quel est l'intérêt de l'itérateur içi si tu peux directement accéder aux élément de ta pile avec la fonction SWAP ?

ps : Quelle est la signification de "auto" dans ton for ?

Euh...
L'itérateur permet de parcourir les éléments de la deque. std::swap n'accède et ne parcourt rien du tout ; il permet seulement d'échanger les deux éléments qu'on lui fournit par référence.

Quant à auto, il permet de remplacer l'écriture d'un type là où le compilateur peut le déduire lui-même. Sans auto on aurait eu :

Code:

---

1 2 3 4

for (std::deque<int>::const_iterator it=pile.cbegin(), itEnd=pile.cend(); it!=itEnd; ++it) { cout << *it << endl; }

---

l'utilisation d'auto (C++11) dans ce cas là évite d'écrire

Code:

---

for (std::deque<int>::iterator it=pile.cbegin(), itEnd=pile.cend(); it!=itEnd; ++it)

---

l'utilisation du mot-clé auto permet de résoudre le type renvoyé par pile.cbegin() au moment de la compilation

edit : grillé

ok ok, donc je pense que ça va pouvoir m'aider tout ça :)

J'ai essayé de l'utiliser directement mais telle quel elle compile mais ne fait pas son travail... Vous avez une idée ?

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32

# include <windows.h> # include <deque> # include <iostream> using namespace std;     void SWAP(std::deque<int> p,int x,int y){std::swap(p[x], p[y]);}     int main (){   // Création d'une pile d'entiers std::deque<int> pile;   pile.push_back(1); pile.push_back(2); pile.push_back(3); pile.push_back(4);   cout<<pile[0]; cout<<pile[3]<<"\n";     // Echange d'éléments SWAP(pile,0,3);   cout<<pile[0]; cout<<pile[3]<<"\n";   system("pause");   }

---

Si ton exemple ne marche pas, c'est parce que tu fournis pile à SWAP par copie et pas par référence. Donc ce que SWAP modifie, c'est une copie locale de pile, pas pile elle-même.

Code:

---

void SWAP(std::deque<int>& p,int x,int y){std::swap(p[x], p[y]);}

---

Cela dit, pourquoi veux-tu absolument passer par une réécriture (SWAP) de la fonction std::swap ?

Ahlalala, j'ai encore beaucoup de choses à apprendre :cry:

Et bien pck dans ce projet certaines fonctions sont imposées, comme la fonction SWAP(int,int).

Le top serait donc de passer la pile par l'argument implicite, du genre :

pile.SWAP(x,y)

SWAP(int,int) en tant que fonction (libre) n'a pas beaucoup de sens, pour les raisons citées ci-dessus : les 2 entiers seront des copies locales, donc SWAP(a,b) n'agit pas sur a et b mais sur des copies locales de a et de b. Il faut utiliser des références : SWAP(int&,int&).

Par contre si SWAP appartient à une classe, ça peut se justifier :

Code:

---

1 2 3 4 5 6

class MyStackClass { public: void SWAP(int a, int b) { std::swap (stack[a], stack[b]); } private: std::deque<int> stack; }

---

Ouai je me suis un peu mal exprimé ^^

Je venais juste de l'écrire :mrgreen:

Je vais à présent compléter ma classe avec les fonction :


--SUM : somme des x premiers éléments de la pile (où x est l'argument)
(entier)
--MEAN : moyenne des x premiers éléments de la pile (où x est l'argument)
(entier)

Opérations sans arguments :
--CLEAR (ou Ctrl - C) : vider la pile
--DUP (ou Entrée sans aucune expression sur la ligne) : duplique le premier
élément de la pile
--DROP (ou Retour en arrière sans aucune expression sur la ligne) : supprime
le premier élément de la pile

décidément rien ne va ojd....

Pourquoi ai-je le droit d’initialiser et d'utiliser mon itérateur avec begin() :

Code:

---

1 2	std::deque<int>::const_iterator it=pile.begin(); cout<<*it;

---

et pas avec end() :

Code:

---

1 2	std::deque<int>::const_iterator itend=pile.end(); cout<<*itend;

---

Attention tu peux évidemment le faire avec end, mais tu ne peux pas déréférencer (avec '*') un iterator qui pointe sur la fin, car en réalité il pointe sur la fin + 1, donc "derrière la fin", et là, il ne se trouve rien.

Par contre, est-ce que le but de ton exercice est de recréer toi même une pile et toutes ses fonctions ou alors d'utiliser un container de la STL et d'ajouter des opérations sur ce container ?

D'ailleurs, il faut faire attention, car deque n'est pas une pile même si elle peut être utilisé comme (dans ce cas, un vector marche aussi). C'est une structure de donnée qui permet d'ajouter/supprimer vers l'avant et l'arrière tout en ne ré allouant pas à chaque ajout de la mémoire à la manière d'une liste.

Pour avoir une vraie pile et y être limité il faut utiliser std::stack<int>. Dans ce cas tu n'auras pas d'itérateur, car la définition même d'une pile et de ne pouvoir accéder qu'au premier élément.

Et bien le but de l'exercice est de créer une calculatrice, donc dans tous les cas j'ai besoin d'un conteneur.

J'étais donc parti sur une stack pusique c'est la traduction primaire de la pile mais en essayant de mettre en place un itérateur pour pouvoir accéder séquentiellement à ma pile et écrire la fonction SWAP. (je dois avoir au final push, drop, swap, mean, som,dupplique et clear)

Mais sur ce COB59 m'a orienté sur un deque qui ne necessite pas d'itérateur puisqu'il possède déjà un SWAP ainsi qu'un itérateur....

C'est une bonne idée non ?

Oui c'est une bonne idée, quoique pour l'usage que tu en fais, je pense qu'un std::vector serait suffisant, mais peut-être ai-je loupé une instruction qui nécessite d'ajouter/supprimer à l'avant ?

Sinon est-ce que c'est toi qui as choisi d'utiliser une pile et ces opérations ?

Parce que généralement la structure utilisée pour les calculatrices, c'est un arbre binaire (ou éventuellement n-aires).

Non la pile et ces opérations sont imposés.... Et je n'ai pas à ajouter/supprimer au début de la pile. Je dois tout faire sur "haut" de la pile.

Ça donne un truc comme ça : propre ? pas propre ? pourri ?

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36

# include <windows.h> # include <deque> # include <iostream> using namespace std;   class mypile {   public: std::deque<int> pile;   public: void SWAP(int a, int b) { std::swap (pile[a], pile[b]); }   };     int main (){   mypile p;   p.pile.push_back(1); p.pile.push_back(2); p.pile.push_back(3); p.pile.push_back(4);   cout<<p.pile[0]; cout<<p.pile[2]<<"\n";   p.SWAP(0,2);   cout<<p.pile[0]; cout<<p.pile[2]<<"\n";   system("pause");   }

---

Personnellement je n'aime pas le fait d'utiliser le deque, c'est un peu de la triche.

Pour swaper, tu devrais utiliser une pile temporaire... Je ne pense pas que ton professeur s'attende à ce que vous utilisiez autre chose qu'une pile.

Malgré tout, question performance, c'est quand même mieux d'utiliser un deque...

Et bien pour tout te dire, le prof est assez ouvert et je pense que si niveau performance c'est intéressant il ne devrait pas y avoir de soucis.

Je vais quand même demander :)

quelqu'un aurait une idée pourquoi cette fonction ne fait pas son boulot?

A savoir sommer les a derniers termes de la pile, les enlever de la pile et y insérer la valeur sommée...

Code:

---

1 2 3 4 5

void SUM(int a){ std::deque<int>::const_iterator itend=pile.end(); int s=0; for(int i=1;i=a;i++) s= s + *(itend-i); for(int j=1;j=a;j++) pile.pop_back(); pile.push_back(s);}

---

Tout d'abord pourquoi faire deux boucles ? Et sinon au lieu de commencer par la fin, tu peux simplement utiliser un reverse iterator, à savoir it = pile.rbegin(). Sinon je ne pense pas que c'est une bonne idée d'appeler ton deque pile, parce que ça n'en est pas une et ça prête à confusion.

Dans tes deux boucles tu dois quand même vérifier que tu n'as pas parcouru toute la structure au cas où a >= pile.size(). (Tu peux utiliser pile.rend() pour la fin reverse).

Et finalement pour répondre à ta question, hé bien oui c'est normal, car tu fais

Code:

---

for(int i=1;i=a;i++)

---

qui est une affectation..

D'ailleurs évite de faire *(itend-i) et incrémente plutôt ton itérateur à chaque itération.

Sinon tu pouvais passer un peu de temps à éplucher la STL et tomber là-dessus :
http://www.cplusplus.com/reference/s...ic/accumulate/

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

#include <cassert> #include <numeric>   void MyStackClass::SUM(int a) { // On vérifie qu'un a-ième élément existe dans la pile assert ( 0 < a && a <= pile.size() );   // On fait la somme des a premiers éléments int sum = std::accumulate(pile.begin(), pile.begin() + a);   // On vide la pile, on y ajoute sum pile.clear(); pile.push_back(sum); }

---

Ouai mais c'est une pile qui y est utilisé non ?:oops:

Trademark après modifs ça donne ça :

Code:

---

1 2 3 4 5 6

void SUM(int a){ std::deque<int>::reverse_iterator itend=pile.rbegin(); if (a <= pile.size()){ int s=0; for(int i=1;i==a;i++){ s+= *(itend++) ;pile.pop_back();} pile.push_back(s);} else cout<<"pile trop courte";}

---

Mais ça ne somme pas... peut être ai je mal compris le fonctionnement des reverse iterator... Il partent bien du dernier élément et lorsqu'on l'incrémente il se rapproche du premier :aie:

Citation:

---

Envoyé par cob59

Sinon tu pouvais passer un peu de temps à éplucher la STL et...

---

J'y ai pensé aussi mais en fait il faut qu'il somme les n valeurs du dessus de la pile, vider ces n valeurs (et pas toutes la pile) et ajouter la somme calculée.

Citation:

---

Mais ça ne somme pas... peut être ai je mal compris le fonctionnement des reverse iterator... Il partent bien du dernier élément et lorsqu'on l'incrémente il se rapproche du premier

---

Code:

---

for(int i=1;i==a;i++)

---

Tant que 1 est égale à 5 (si a vaut 5) faire ... Donc j'imagine que tu as compris le soucis.

Code:

---

1 2	if (a <= pile.size()){

---

Ce n'est pas spécialement une bonne idée d'afficher un message, je vois deux façons, soit tu fais :

Code:

---

a = std::min(a, pile.size());

---

Ou alors tu lance une exception. Mais faire une erreur silencieuse comme ça n'est probablement pas adéquat. Si tu utilises la première méthode, pense bien à le commenter.

OK. Dans ce cas ça fait faire une petite modif :

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

#include <cassert> #include <numeric>   void MyStackClass::SUM(int a) { // On vérifie qu'un a-ième élément existe dans la pile assert ( 0 < a && a <= pile.size() );   // On fait la somme des a derniers éléments int sum = std::accumulate(pile.end() - a, pile.end());   // On dépile, on ajoute sum pile.erase(pile.end() - a, pile.end()); pile.push_back(sum); }

---

Euh non, je ne comprends pas trademark...:cry:

Code:

---

for(int i=1;i==a;i++)

---

n'est pas "Tant que 1 est égale à 5 (si a vaut 5) faire..." mais plutôt "pour i=1 jusqu'à i=5 faire....(incrémenter i)"

Les boucles for sont pareils que les boucles while, c'est des "Tant que" et pas jusqu'à.

Donc ça donne :

Code:

---

1 2 3 4 5

for(int i=0;i < a; ++i, ++it) { sum += *it ; pile.pop_back(); }

---

Tu peux également utiliser la méthode présentée par cob59 mais tu auras du O(2a) au lieu de O(a), ce qui est parfois négligeable.

Aie aie aie des petites lacunes :aie:

Mais bonne nouvelle ma pile est finie :ccool: Merci à vous....:oops:

Salut je pense pouvoir t'aider ;)

Plusieurs erreurs :

Code:

---

1 2 3 4 5 6

void SUM(int a){ std::deque<int>::const_iterator itend=pile.end(); int s=0; for(int i=1;i!=a;i++) s= s + *(itend-i); for(int j=1;j!=a;j++) pile.pop_back(); pile.push_back(s);}

---

Après le code peut être un minimum optimisé :

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12 13

void SUM(int a) { double s=0; for(int i=(int)T.size()-1;i>=(int)T.size()-a&&i>=0;i--) s+=T[i];   if(a<A) T.erase(T.end()-a,T.end()); else T.erase(T.begin(),T.end()); T.push_back(s); }

---

Voila :D

Edit : je n'avais pas vu qu'il y avait une deuxième page sur ce forum donc je suis multi grillé :mouarf: