Logo GNT
Actualités Tests & Guides Bons Plans
GTA 6 iPhone 17 Copilot Switch 2 Temu ChatGPT Tesla
OVH Cloud OVH Cloud
Entraide Développement Développement Langage C++ STL deque et stack

STL deque et stack

31 réponses
Avatar
heinquoi
Bjr,

j'ai une question con...je peux ?
voici
quel est intérêt de la stack lorsque les container on déjà des fonctions
pop_front,push_front ?
sachant que la stack peut etre adapté aux containers vector, list et deque,
et que ces containers ont des fonctions qui peuvent tout a fait faire une
stack si on les utilise.
--
Cordialement,
Heinquoi
Signaler un problème avec ce contenu

10 réponses

Supprimer
Cette action est irreversible, confirmez la suppression du commentaire ?
Signaler le commentaire

Veuillez sélectionner un problème

Nudité
Violence
Harcèlement
Fraude
Vente illégale
Discours haineux
Terrorisme
Autre
1 2 3 4
Avatar
Gabriel Dos Reis
Franck Branjonneau writes:

| Gabriel Dos Reis écrivait:
|
| > Franck Branjonneau writes:
| >
| > | Gabriel Dos Reis écrivait:
| > |
| > | > Plusieurs fois, j'ai abandonné std::stack pour utiliser le bon vieux
| > | > std::vector.
| > |
| > | Tu utilises des std::vector<> pour tes piles ? pas des std::deque<> ?
| >
| > Oui et non.
|
| Mon acception du français me permet de lire :

« Oui » pour la première question, « non » pour la seconde.

| 1/ Tantôt oui et tantôt non. OK.
|
| 2/ Oui j'utilise des std::vector<> pour mes piles ; non pas des
| std::deque<>. Et là je m'interroge. Le std::deque<> ne fait-il pas une
| meilleure gestion de la mémoire que le std::vector<> lors
| d'utilisations répétées de push()/pop() ?

Mais std::deque<> ne me donne pas les garanties de std::vector<> que
j'utilise aussi -- il est rare que je traite une pile juste comme une
pile. En général, cela arrive uniquement dans une petite portion de
mes programmes. En fait, std::stack<> est un adapteur pour ces
onsidérations -- c'est un peu curieux que cela ce soit arrêter en
mi-chemin :-(

-- Gaby
Avatar
Michel Michaud
Dans news:cbcj6n$6r4$, Loïc
Franck Branjonneau wrote:


2/ Oui j'utilise des std::vector<> pour mes piles ; non pas des
std::deque<>. Et là je m'interroge. Le std::deque<> ne fait-il
pas une meilleure gestion de la mémoire que le std::vector<>
lors d'utilisations répétées de push()/pop() ?


Tu parlerais de queues, je serais d'accord, mais pour des
piles, vector me semble meilleur avec les cas d'utilisation
classiques.


Tu peux expliquer ? Parce que d'après moi, la norme ne choisit pas
std::deque pour rien, par défaut, dans std::stack. La gestion de
mémoire sera plus efficace avec deque. Son seul défaut général par
rapport à vector est l'accès aux éléments qui est un peu moins
direct que pour vector, mais pour une pile, il n'y a d'accès qu'à
un élément qui est facile si on garde l'itérateur...

--
Michel Michaud
http://www.gdzid.com
FAQ de fr.comp.lang.c++ :
http://www.cmla.ens-cachan.fr/~dosreis/C++/FAQ/


Avatar
Loïc Joly
Michel Michaud wrote:

Dans news:cbcj6n$6r4$, Loïc

Franck Branjonneau wrote:


2/ Oui j'utilise des std::vector<> pour mes piles ; non pas des
std::deque<>. Et là je m'interroge. Le std::deque<> ne fait-il
pas une meilleure gestion de la mémoire que le std::vector<>
lors d'utilisations répétées de push()/pop() ?


Tu parlerais de queues, je serais d'accord, mais pour des
piles, vector me semble meilleur avec les cas d'utilisation
classiques.



Tu peux expliquer ? Parce que d'après moi, la norme ne choisit pas
std::deque pour rien, par défaut, dans std::stack. La gestion de
mémoire sera plus efficace avec deque. Son seul défaut général par
rapport à vector est l'accès aux éléments qui est un peu moins
direct que pour vector, mais pour une pile, il n'y a d'accès qu'à
un élément qui est facile si on garde l'itérateur...


Je me suis mal exprimé. Je voulais dire que dans le cas d'un stack,
deque ou vector étaient AMA très proches l'un de l'autre, et donc
dépendent du profil d'utilisation, alors que dans le cas d'une queue, le
choix de deque s'imposait clairement.

Par exemple, si la taille d'un bloc de deque est de 100(*), que l'on ne
supprime un bloc que quand il y a deux blocs vides, et que le profil
d'utilisation est d'ajouter n éléments puis d'en enlever n, (n>100)
alors il y aura sans cesse des allocations mémoires, alors qu'avec
vector, il n'y aura des allocations que la première fois.

Réciproquement, si une fois, la pile contient 10000000 membres, mais par
la suite, elle en contient 3 au plus, deque briellera devant vector.

(*) D'ailleurs, le fait que dans un soucis de généricité et
d'encapsulation la norme de parle pas de la taille d'un bloc et ne
permettre pas de la fixer me semble un peu dommage.

--
Loïc



Avatar
Gabriel Dos Reis
"Michel Michaud" writes:

| Dans news:cbcj6n$6r4$, Loïc
| > Franck Branjonneau wrote:
| >
| >>
| >> 2/ Oui j'utilise des std::vector<> pour mes piles ; non pas des
| >> std::deque<>. Et là je m'interroge. Le std::deque<> ne fait-il
| >> pas une meilleure gestion de la mémoire que le std::vector<>
| >> lors d'utilisations répétées de push()/pop() ?
| >
| > Tu parlerais de queues, je serais d'accord, mais pour des
| > piles, vector me semble meilleur avec les cas d'utilisation
| > classiques.
|
| Tu peux expliquer ? Parce que d'après moi, la norme ne choisit pas
| std::deque pour rien, par défaut, dans std::stack. La gestion de
| mémoire sera plus efficace avec deque. Son seul défaut général par
| rapport à vector est l'accès aux éléments qui est un peu moins
| direct que pour vector,

C'est simple, j'ai implémenté un interpréteur de mini-PostScript en
forme de bibliothèque. PostScript est un langage qui utilise
abondamment la pile -- presque tout se passe sur la pile. J'ai besoin
d'indexer arbitrairement dans la pile. Il n'y a aucune raison pour que
cela coûte plus cher que d'indexer dans un tableau.

Si j'écris un compilateur C++, la recherche de noms est quelque choses
de fréquent. En première approximation, les portées s'emboîtent -- et
se comportent comme une pile. L'accès aux portées englobantes ne doit
pas coûter plus cher que d'indexer un tableau. Si c'est pas possible,
c'est que std::stack<> ne convient pas.


| mais pour une pile, il n'y a d'accès qu'à
| un élément qui est facile si on garde l'itérateur...

Bah *non*. C'est une erreur.

-- Gaby
Avatar
Michel Michaud
Dans news:, Gabriel Dos
"Michel Michaud" writes:

Dans news:cbcj6n$6r4$, Loïc
Franck Branjonneau wrote:


2/ Oui j'utilise des std::vector<> pour mes piles ; non pas
des std::deque<>. Et là je m'interroge. Le std::deque<> ne
fait-il pas une meilleure gestion de la mémoire que le
std::vector<> lors d'utilisations répétées de push()/pop() ?


Tu parlerais de queues, je serais d'accord, mais pour des
piles, vector me semble meilleur avec les cas d'utilisation
classiques.


Tu peux expliquer ? Parce que d'après moi, la norme ne choisit
pas std::deque pour rien, par défaut, dans std::stack. La
gestion de mémoire sera plus efficace avec deque. Son seul
défaut général par rapport à vector est l'accès aux éléments
qui est un peu moins direct que pour vector,


C'est simple, j'ai implémenté un interpréteur de
mini-PostScript en forme de bibliothèque. PostScript est un
langage qui utilise abondamment la pile -- presque tout se
passe sur la pile. J'ai besoin d'indexer arbitrairement dans la
pile. Il n'y a aucune raison pour que cela coûte plus cher que
d'indexer dans un tableau.


S'il faut « indexer » des éléments, alors pour moi ce n'est plus
une pile¹, même si tu peux aussi faire des opérations de type
pile. Alors oui, tu pourras utiliser vector directement pour ça.
Ce n'est pas une pile, mais c'est ce dont tu as besoin.

¹ Je suppose qu'il n'y a pas de définition officielle de ce qu'est
une pile : j'insiste pour dire que je parle de ma définition, que
je peux facilement faire confirmer par des auteurs connus dans le
domaine. J'imagine cependant qu'on pourrait en trouver d'autres...
Si tu veux continuer à appeler ça une pile, c'est ton choix, mais
ça change le sujet réel de la discussion : si c'est un vector qu'il
faut, je suis parfaitement d'accord pour dire qu'il faut prendre un
vector :-)

--
Michel Michaud
http://www.gdzid.com
FAQ de fr.comp.lang.c++ :
http://www.cmla.ens-cachan.fr/~dosreis/C++/FAQ/




Avatar
kanze
"Michel Michaud" wrote in message
news:<dPeGc.8653$...
Dans news:, Gabriel Dos
"Michel Michaud" writes:

Dans news:cbcj6n$6r4$, Loïc
Franck Branjonneau wrote:

2/ Oui j'utilise des std::vector<> pour mes piles ; non pas des
std::deque<>. Et là je m'interroge. Le std::deque<> ne fait-il
pas une meilleure gestion de la mémoire que le std::vector<> lors
d'utilisations répétées de push()/pop() ?


Tu parlerais de queues, je serais d'accord, mais pour des piles,
vector me semble meilleur avec les cas d'utilisation classiques.


Tu peux expliquer ? Parce que d'après moi, la norme ne choisit pas
std::deque pour rien, par défaut, dans std::stack. La gestion de
mémoire sera plus efficace avec deque. Son seul défaut général par
rapport à vector est l'accès aux éléments qui est un peu moins
direct que pour vector,


C'est simple, j'ai implémenté un interpréteur de mini-PostScript en
forme de bibliothèque. PostScript est un langage qui utilise
abondamment la pile -- presque tout se passe sur la pile. J'ai
besoin d'indexer arbitrairement dans la pile. Il n'y a aucune raison
pour que cela coûte plus cher que d'indexer dans un tableau.


S'il faut « indexer » des éléments, alors pour moi ce n'est plus une
pile¹, même si tu peux aussi faire des opérations de type pile. Alors
oui, tu pourras utiliser vector directement pour ça. Ce n'est pas une
pile, mais c'est ce dont tu as besoin.


Formellement, je crois que tu as raison. Mais pratiquement...

Si je me souviens bien, Gabi a cité Postscript en exemple. C'est un
langage postfixé, qui se sert logiquement d'une pile pour ces
opérateurs. Formellement, la définition de l'opérateur d'addition serait
quelque chose du genre, popper deux éléments du haut de la pile, puis en
pusher leur somme, c-à-d :

int tmp1 = pile.top() ;
pile.pop() ;
int tmp2 = pile.top() ;
pile.pop() ;
pile.push( tmp1, tmp2 ) ;

Pratiquement, je crois que je préfèrerais une implémentation qui
faisait :

pile[ 1 ] = pile[ 0 ] + pile[ 1 ] ;
pile.pop() ;

si la pile le supportait. Mais ce n'est pas pour autant que je dirais
que la structure en question n'est pas une pile.

--
James Kanze GABI Software http://www.gabi-soft.fr
Conseils en informatique orientée objet/
Beratung in objektorientierter Datenverarbeitung
9 place Sémard, 78210 St.-Cyr-l'École, France, +33 (0)1 30 23 00 34





Avatar
Gabriel Dos Reis
"Michel Michaud" writes:

| Dans news:, Gabriel Dos
| > "Michel Michaud" writes:
| >
| >> Dans news:cbcj6n$6r4$, Loïc
| >>> Franck Branjonneau wrote:
| >>>
| >>>>
| >>>> 2/ Oui j'utilise des std::vector<> pour mes piles ; non pas
| >>>> des std::deque<>. Et là je m'interroge. Le std::deque<> ne
| >>>> fait-il pas une meilleure gestion de la mémoire que le
| >>>> std::vector<> lors d'utilisations répétées de push()/pop() ?
| >>>
| >>> Tu parlerais de queues, je serais d'accord, mais pour des
| >>> piles, vector me semble meilleur avec les cas d'utilisation
| >>> classiques.
| >>
| >> Tu peux expliquer ? Parce que d'après moi, la norme ne choisit
| >> pas std::deque pour rien, par défaut, dans std::stack. La
| >> gestion de mémoire sera plus efficace avec deque. Son seul
| >> défaut général par rapport à vector est l'accès aux éléments
| >> qui est un peu moins direct que pour vector,
| >
| > C'est simple, j'ai implémenté un interpréteur de
| > mini-PostScript en forme de bibliothèque. PostScript est un
| > langage qui utilise abondamment la pile -- presque tout se
| > passe sur la pile. J'ai besoin d'indexer arbitrairement dans la
| > pile. Il n'y a aucune raison pour que cela coûte plus cher que
| > d'indexer dans un tableau.
|
| S'il faut « indexer » des éléments, alors pour moi ce n'est plus
| une pile¹,

Uniquement pour une définition restreinte et inutile de pile.

| même si tu peux aussi faire des opérations de type
| pile. Alors oui, tu pourras utiliser vector directement pour ça.
| Ce n'est pas une pile, mais c'est ce dont tu as besoin.
|
| ¹ Je suppose qu'il n'y a pas de définition officielle de ce qu'est
| une pile : j'insiste pour dire que je parle de ma définition, que
| je peux facilement faire confirmer par des auteurs connus dans le
| domaine. J'imagine cependant qu'on pourrait en trouver d'autres...

Bof. Une définition de pile qui exclut qu'on puisse la parcourir
dans l'ordre naturel des choses n'est utile que pour ces
experts/auteurs là. Et comme il y a autant d'avis que d'experts, je
laisse ces experts/auteurs avec leurs piles inutiles.

Il y a un ordre naturel sur la position des éléments d'une pile.
Si on a une définition de pile qui refuse cet ordre, elle est à mettre
à la poubelle.

| Si tu veux continuer à appeler ça une pile, c'est ton choix, mais
| ça change le sujet réel de la discussion : si c'est un vector qu'il
| faut, je suis parfaitement d'accord pour dire qu'il faut prendre un
| vector :-)


-- Gaby
Avatar
Gabriel Dos Reis
writes:

[...]

| > > C'est simple, j'ai implémenté un interpréteur de mini-PostScript en
| > > forme de bibliothèque. PostScript est un langage qui utilise
| > > abondamment la pile -- presque tout se passe sur la pile. J'ai
| > > besoin d'indexer arbitrairement dans la pile. Il n'y a aucune raison
| > > pour que cela coûte plus cher que d'indexer dans un tableau.
|
| > S'il faut « indexer » des éléments, alors pour moi ce n'est plus une
| > pile¹, même si tu peux aussi faire des opérations de type pile. Alors
| > oui, tu pourras utiliser vector directement pour ça. Ce n'est pas une
| > pile, mais c'est ce dont tu as besoin.
|
| Formellement, je crois que tu as raison. Mais pratiquement...
|
| Si je me souviens bien, Gabi a cité Postscript en exemple. C'est un
| langage postfixé, qui se sert logiquement d'une pile pour ces
| opérateurs. Formellement, la définition de l'opérateur d'addition serait
| quelque chose du genre, popper deux éléments du haut de la pile, puis en
| pusher leur somme, c-à-d :
|
| int tmp1 = pile.top() ;
| pile.pop() ;
| int tmp2 = pile.top() ;
| pile.pop() ;
| pile.push( tmp1, tmp2 ) ;
|
| Pratiquement, je crois que je préfèrerais une implémentation qui
| faisait :
|
| pile[ 1 ] = pile[ 0 ] + pile[ 1 ] ;
| pile.pop() ;
|
| si la pile le supportait. Mais ce n'est pas pour autant que je dirais
| que la structure en question n'est pas une pile.

Exactement. Et une définition de pile qui refuse l'ordre naturelle des
choses est inutile. Une pile a une histoire ; et c'est justement cette
histoire qui est intéressante.

-- Gaby
Avatar
Mickael Pointier
| Si je me souviens bien, Gabi a cité Postscript en exemple. C'est un
| langage postfixé, qui se sert logiquement d'une pile pour ces
| opérateurs. Formellement, la définition de l'opérateur d'addition serait
| quelque chose du genre, popper deux éléments du haut de la pile, puis en
| pusher leur somme, c-à-d :
|
| int tmp1 = pile.top() ;
| pile.pop() ;
| int tmp2 = pile.top() ;
| pile.pop() ;
| pile.push( tmp1, tmp2 ) ;
|
| Pratiquement, je crois que je préfèrerais une implémentation qui
| faisait :
|
| pile[ 1 ] = pile[ 0 ] + pile[ 1 ] ;
| pile.pop() ;
|
| si la pile le supportait. Mais ce n'est pas pour autant que je dirais
| que la structure en question n'est pas une pile.

Exactement. Et une définition de pile qui refuse l'ordre naturelle des
choses est inutile. Une pile a une histoire ; et c'est justement cette
histoire qui est intéressante.

-- Gaby


Parfaitement avec tout ça.

Je n'utilise d'ailleur plus du tout std:stack, à chaque fois je me suis
retrouvé coincé en voulant faire une manip que ne supportait pas ce
conteneur.

Donc en général je me réimplémente ma propre pile en utilisant un autre
conteneur plus générique.

Je crois qu'une pile qui me permettrait d'accéder aux "n" derniers éléments
(une sorte d'indexation spécialisée partant de la fin quoi) me suffisait,
mais ne pouvoir accéder qu'au "top" ca je ne peux pas m'en servir.

Mike

Avatar
Alain Naigeon
"Mickael Pointier" a écrit dans le message news:
ccgi8a$6c7$

Exactement. Et une définition de pile qui refuse l'ordre naturelle des
choses est inutile. Une pile a une histoire ; et c'est justement cette
histoire qui est intéressante.

-- Gaby


Parfaitement avec tout ça.

Je n'utilise d'ailleur plus du tout std:stack, à chaque fois je me suis
retrouvé coincé en voulant faire une manip que ne supportait pas ce
conteneur.

Donc en général je me réimplémente ma propre pile en utilisant un autre
conteneur plus générique.

Je crois qu'une pile qui me permettrait d'accéder aux "n" derniers
éléments

(une sorte d'indexation spécialisée partant de la fin quoi) me suffisait,
mais ne pouvoir accéder qu'au "top" ca je ne peux pas m'en servir.


J'avoue que je suis un peu perplexe en voyant ce débat, pourquoi
demander à un container ce que d'autres font parfaitement bien ?
Une liste non ordonnée a aussi un ordre naturel basée sur l'histoire
des insertions, est-ce si terrible d'écrire pop_front() au lieu de pop() ?

La pile (qui tire son nom de la pile d'assiettes posée sur un comptoir,
par exemple), est juste faite pour fournir une ressource, elle implémente
ce qui est nécessaire pour ce rôle. Chacun a des des tas de trucs qu'il
n'utilise pas dans la stl, est-ce une raison pour que d'autres n'en
disposent
pas si leurs besoins sont différents ?

--

Français *==> "Musique renaissance" <==* English
midi - facsimiles - ligatures - mensuration
http://anaigeon.free.fr | http://www.medieval.org/emfaq/anaigeon/
Alain Naigeon - - Strasbourg, France


1 2 3 4