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);}

---