STL deque et stack

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 ?

Parce que bettement quand je me suis mis à utiliser la STL je n'ai pas
gratté dans tous les sens pour voir ce qui permettait de faire tel ou tel
conteneur. J'avais une idée de ce que devait être un "vector", une "list",
une "string", une "map", et donc j'avais aussi une idée de ce que devait
être une "stack" générique, basé sur des expériences de ce qu'on est souvent
ammené à faire avec une pile.

Après être partit dans l'implémentation en utilisant std::stack, je me suis
rendu compte que ce conteneur ne disposait pas de ce que j'estimait qu'une
pile devrait avoir.

Rien de plus.

Pour plaggier une maxime de ce groupe "mauvais conteneur, changer de
conteneur" :)

Mike


PS: La pile d'assiette qui est posée sur le comptoir, dispose d'une
fonctionalité qui permet d'en prendre par groupe de "n" (en partant du haut)
pour les ranger dans les placard. std::stack permet de les déplacer une par
une :)

"Alain Naigeon" <anaigeon@free.fr> writes:

| "Mickael Pointier" <mpointier@edengames.moc> a écrit dans le message ne ws:
| ccgi8a$6c7$1@aphrodite.grec.isp.9tel.net...
|
| > > 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 su is
| > 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 suff isait,
| > 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,

Justement ! Je peux parcourir cette liste et voir cet ordre naturel en
action. Personne n'est venu dire que si on parcours une liste, ce
n'est plus une liste.

| est-ce si terrible d'écrire pop_front() au lieu de pop() ?

Mais la question n'est pas s'il est difficile d'écrire pop_front().
C'est une question de savoir si les abstractions qu'ont définies ont
une quelconque utilité. À l'évidence, une liste n'a pas les mêmes
contraintes de gestions de mémoire d'un vecteur ou comme une pile
utilisant une vecteur ou un foo_bar. Donc, je crois que ta question
n'a pas beaucoup de pertinence.

| La pile (qui tire son nom de la pile d'assiettes posée sur un comptoir,

C'est l'image conventionelle qu'on montre dans les bouquins pour
illustrer un point particulier, mais cela n'a jamais été qu'une
image. Quand tu as ta pile d'assiete devant toi, tu n'en vois que le
sommet ? Jamais celui juste en dessous, juste en dessous d'en dessous
?

| par exemple), est juste faite pour fournir une ressource, elle implémen te
| ce qui est nécessaire pour ce rôle.

Et c'est quoi une liste, un ensemble?

| 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 ?

Wrong question.

Cite-moi le nombre de fois que tu as utilisé std::stack<> de manià ¨re
utile sans ressentir de frustration.

-- Gaby

Ce message est le seul de ce fil que je retrouve après mes
vacances... Je réponds donc à plusieurs personnes ici...

Dans news:40ec7ed2$0$29375$626a14ce@news.free.fr, Alain

"Mickael Pointier" <mpointier@edengames.moc> a écrit dans le
message news: ccgi8a$6c7$1@aphrodite.grec.isp.9tel.net...

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.

Hum... Une vision des choses. Pas la seule... Je ne peux dire
quelle est la « bonne » ou la plus utile, mais je peux simplement
affirmer que des auteurs célèbres en ont une autre et que, même
si on peut leur reprocher, ils ont influencé la vision de plusieurs
personnes.

-- 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.

Alors il n'y a pas de problème. Si tu n'as pas besoin d'une
pile selon stack, i.e. selon un modèle classique tu peux prendre
autre chose.

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

Et ce que tu obtiens n'est plus une pile, du moins selon certaines
définitions classiques. Ça ne rend pas la chose moins bonne si
c'est ce dont tu as besoin :-)

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.

Dans ton problème spécifique. Je t'assure que std::stack peut être
utile tel quel.

J'avoue que je suis un peu perplexe en voyant ce débat, pourquoi
demander à un container ce que d'autres font parfaitement bien ?

En fait, je suis plus perplexe encore sur le fait qu'on dise
aujourd'hui que la définition d'une pile qui ne permet l'accès
qu'au seul élément du dessus, soit une erreur...

Cette définition permet, entre autres, des implémentations
efficaces (en rapidité et/ou en utilisation mémoire). Si les
seules opérations nécessaires sont comblées alors tout le
monde gagne. Si ce n'est pas le cas, on choisit autre chose
qu'une pile selon cette définition. On peut même décider de
l'appeler pile si on veut...

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

"Michel Michaud" <mm@gdzid.com> writes:

[...]

| >> 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.
|
| Alors il n'y a pas de problème. Si tu n'as pas besoin d'une
| pile selon stack, i.e. selon un modèle classique tu peux prendre
| autre chose.

Tu as tout à l'envers. Ce n'est pas qu'il n'a pas besoin de pile -- il
en a besoin. C'est juste que certains insistent à ne fournir que des
définitions inutiles -- sauf pour écrire des bouquins.

-- Gaby

Dans news:m33c3rwem9.fsf@merlin.cs.tamu.edu, Gabriel Dos

"Michel Michaud" <mm@gdzid.com> writes:

[...]

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.

Alors il n'y a pas de problme. Si tu n'as pas besoin d'une
pile selon stack, i.e. selon un mod le classique tu peux
prendre autre chose.

Tu as tout à l'envers. Ce n'est pas qu'il n'a pas besoin de
pile -- il en a besoin. C'est juste que certains insistent à ne

Relis donc le passage. Il n'a pas besoin d'une pile selon stack,
car stack ne lui convient pas. Je n'ai rien à l'envers, c'est lui
qui l'a dit.

fournir que des définitions inutiles -- sauf pour écrire des
bouquins.

C'est ton point de vue. Je t'ai accordé qu'il pouvait avoir son
intérêt et que tu pouvais l'affirmer. Mais tu ne sembles pas avoir
lu attentivement (et tu sembles avoir posté dans un drôle de
mode qui a perdu les accents... j'espère avoir rétabli les choses).

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

"Michel Michaud" <mm@gdzid.com> writes:

| Dans news:m33c3rwem9.fsf@merlin.cs.tamu.edu, Gabriel Dos
| > "Michel Michaud" <mm@gdzid.com> writes:
| >
| > [...]
| >
| >>>> 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.
| >>
| >> Alors il n'y a pas de problme. Si tu n'as pas besoin d'une
| >> pile selon stack, i.e. selon un mod le classique tu peux
| >> prendre autre chose.
| >
| > Tu as tout à l'envers. Ce n'est pas qu'il n'a pas besoin de
| > pile -- il en a besoin. C'est juste que certains insistent à ne
|
| Relis donc le passage.

Je l'ai fait mille fois pendant que tu étais en vacances ;-/

| Il n'a pas besoin d'une pile selon stack,
| car stack ne lui convient pas. Je n'ai rien à l'envers, c'est lui
| qui l'a dit.

Si. Il dit que std::stack ne lui convient pas, principalement parce
que c'est une sur-abstraction inutilisable. Cela ne veut pas dire
qu'il n'a pas besoin de pile -- de fait, c'était cela qui l'avait
amené à vouloir utiliser std::stack.

-- Gaby

Dans news:m3r7rad8gl.fsf@merlin.cs.tamu.edu, Gabriel Dos

"Michel Michaud" <mm@gdzid.com> writes:

Dans news:m33c3rwem9.fsf@merlin.cs.tamu.edu, Gabriel Dos

"Michel Michaud" <mm@gdzid.com> writes:

Alors il n'y a pas de problme. Si tu n'as pas besoin d'une
pile selon stack, i.e. selon un mod le classique tu peux
prendre autre chose.

Tu as tout à l'envers. Ce n'est pas qu'il n'a pas besoin de
pile -- il en a besoin. C'est juste que certains insistent à
ne

Relis donc le passage.

Je l'ai fait mille fois pendant que tu étais en vacances ;-/

Tu as mon message avant que je l'écrive ? Wow :-)

Il n'a pas besoin d'une pile selon stack,
car stack ne lui convient pas. Je n'ai rien à l'envers, c'est
lui qui l'a dit.

Si. Il dit que std::stack ne lui convient pas, principalement
parce que c'est une sur-abstraction inutilisable. Cela ne veut
pas dire qu'il n'a pas besoin de pile -- de fait, c'était cela
qui l'avait amené à vouloir utiliser std::stack.

Encore une fois, lis et relis. Je suis d'accord : il dit qu'il
a besoin d'une pile. Il dit que std::stack ne lui convient pas.

En d'autres mots, std::stack n'est pas le type de pile dont il
a besoin. En d'autres mots, il n'a pas besoin d'une pile du modèle
std::stack. C'est exactement ce que j'ai dit. Tu répètes la même
chose comme si ce n'est pas ce que j'ai dit !

Là où nous ne sommes pas d'accord, c'est que tu crois que
std::stack est un sur-abstraction inutilisable alors que je
crois qu'il y a des cas où elle suffit.

Qu'on puisse vouloir autre chose, parfois, pour résoudre des
problèmes, je n'ai jamais dit le contraire. Par contre, si tu
n'as jamais eu besoin de std::stack, ça ne prouve pas son
inutilité, si tu veux des exemples où elle est utilisable,
ouvre n'importe quel livre sur les structures de données. Je
suis certain que tu verras quelques exemples.

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

"Michel Michaud" <mm@gdzid.com> writes:

| Dans news:m3r7rad8gl.fsf@merlin.cs.tamu.edu, Gabriel Dos
| > "Michel Michaud" <mm@gdzid.com> writes:
| >
| >> Dans news:m33c3rwem9.fsf@merlin.cs.tamu.edu, Gabriel Dos
| >>> "Michel Michaud" <mm@gdzid.com> writes:
| >>>> Alors il n'y a pas de problme. Si tu n'as pas besoin d'une
| >>>> pile selon stack, i.e. selon un mod le classique tu peux
| >>>> prendre autre chose.
| >>>
| >>> Tu as tout à l'envers. Ce n'est pas qu'il n'a pas besoin de
| >>> pile -- il en a besoin. C'est juste que certains insistent à
| >>> ne
| >>
| >> Relis donc le passage.

deja-lu-mille-fois:

| > Je l'ai fait mille fois pendant que tu étais en vacances ;-/
|
| Tu as mon message avant que je l'écrive ? Wow :-)

Pardon ?

| >> Il n'a pas besoin d'une pile selon stack,
| >> car stack ne lui convient pas. Je n'ai rien à l'envers, c'est
| >> lui qui l'a dit.
| >
| > Si. Il dit que std::stack ne lui convient pas, principalement
| > parce que c'est une sur-abstraction inutilisable. Cela ne veut
| > pas dire qu'il n'a pas besoin de pile -- de fait, c'était cela
| > qui l'avait amené à vouloir utiliser std::stack.
|
| Encore une fois, lis et relis.

goto deja-lu-mille-fois;


| Je suis d'accord : il dit qu'il
| a besoin d'une pile. Il dit que std::stack ne lui convient pas.
|
| En d'autres mots, std::stack n'est pas le type de pile dont il
| a besoin. En d'autres mots, il n'a pas besoin d'une pile du modèle
| std::stack. C'est exactement ce que j'ai dit. Tu répètes la même
| chose comme si ce n'est pas ce que j'ai dit !
|
| Là où nous ne sommes pas d'accord, c'est que tu crois que
| std::stack est un sur-abstraction inutilisable alors que je
| crois qu'il y a des cas où elle suffit.

Exemples ! (non-académiques). J'ai déjà posé la question. Aucune
réponse. Si, elle ci-dessus que tu contestes et ne contestes pas.

-- Gaby

Dans news:m3vfgmas3h.fsf@merlin.cs.tamu.edu, Gabriel Dos

"Michel Michaud" <mm@gdzid.com> writes:

Tu as mon message avant que je l'écrive ? Wow :-)

Pardon ?

Pardon :
Tu as lu mon message avant que je l'écrive ? Wow :-)

Encore une fois, lis et relis.

goto deja-lu-mille-fois;

Je te crois maintenant, car sur ceci :

Je suis d'accord : il dit qu'il
a besoin d'une pile. Il dit que std::stack ne lui convient pas.

Tu ne contestes pas que c'est bien ce que je dis. goto la-suite.

Là où nous ne sommes pas d'accord, c'est que tu crois que
std::stack est un sur-abstraction inutilisable alors que je
crois qu'il y a des cas où elle suffit.

Exemples ! (non-académiques). J'ai déjà posé la question.

Ah ok. Pour toi, si c'est dans un livre c'est académique.
J'imagine que tout cas où on se sert d'une pile pour éliminer
une récursivité est académique. Que tout exemple d'implémentation
d'un « undo » ou d'une historique est académique. Que tout exemple
assez petit pour être posté ici serait académique. Que tout code
écrit avec une pile similaire à std::stack mais dans d'autres
langages ou sans std::stack serait sans pertinence.

En fait, comme je suis enseignant, tout exemple que je te donnerai
sera académique aussi, même s'il n'a rien à voir avec mon
enseignement. You win.

Aucune réponse. Si, elle ci-dessus que tu contestes et ne
contestes pas.

Je ne comprends pas exactement cette partie de ton message, mais
je t'ai donné une réponse, mais elle ne t'a pas satisfaite. C'est
normal, aucune ne te satisfera puisque tu n'es pas d'accord.

Je préfère revenir à la discussion de départ sur ce qu'est une
pile.

Comme on parle de C++ et std::stack, il serait utile de voir ce
que disent Josuttis et Austern, mais comme ils ont écrit des
livres, c'est académique et ça ne t'intéressera pas. Pour les
autres, je dirai simplement que Josuttis donne sa propre classe
de pile, qu'il dit préférer, et qui offre une interface encore
plus restrictive que stack (!). Pour sa part, Austern indique
que l'emploi de std::stack permet de « rendre clair qu'on fait
seulement des opérations de pile ».

Citons aussi notre ami BS, dans TC++PL3 : « All stack does is to
eliminate all the non-stack operations on its container from the
interface and give back(), push_back(), and pop_back() their
conventional names ». Mais bon, lui aussi a écrit des livres.

En conclusion, il semble qu'il y a encore des auteurs modernes
qui font « l'erreur » de penser que std::stack est en fait une
abstraction qui correspond assez bien à leur idée d'une pile.
Ils ne voient pas ce qui apparaît évident à d'autres : que ça
devient une sur-abstraction inutilisable.

Voilà. I rest my case.

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

Michel Michaud wrote:

Ah ok. Pour toi, si c'est dans un livre c'est académique.
J'imagine que tout cas où on se sert d'une pile pour éliminer
une récursivité est académique. Que tout exemple d'implémentation
d'un « undo » ou d'une historique est académique.

C'est pas forcément un super exemple. Pas mal de logiciels modernes font
une utilisation de "undo" autrement que par pile. Si l'on ne peut
annuler que le dernier élément, il est possible de visualiser tous les
éléments et d'en annuler les n derniers d'un coup. ;)

--
Loïc