d

-
Edité par Anonyme 23 septembre 2019 à 23:39:38

Ca vient du constructeur à la ligne 11: tu y déclares un tableau T local au lieu d'utiliser le membre T de ta classe. Du coup ton tableau de stockage n'existe plus lorsque tu sors du constructeur.

Salut,

Heu, je sais pas où tu as trouvé un tel code pour créer une file, mais ce n'est pas du tout comme cela que l'on est sensé s'y prendre...

Car, a priori, le principe d'une file, c'est de présenter un système FIFO (First In, First Out): on entre d'un côté, on sort de l'autre, sans présenter de taille pré définie, sans permettre l'accès  à ce qui suit le premier élément prêt à sortir, tout en garantissant une complexité en temps constant pour l'ajout et la suppression d'un élément.

L'un dans l'autre, le système d'une file est donc beaucoup plus proche d'un système de liste chainée que du système d'un tableau, à la différence notable que la liste chainée autorise l'ajout, la suppression et l'accès n'importe quel endroit de la liste.eau

En gros, cela devrait prendre une forme proche de

class File{
struct Node{
    int value;
    Node * next= nullptr;
};
public:
   void append(int value){
       Node * temp = new Node;
       temp->value = value;
       if(! first_)
           first_ = temp;
       if(last)
           last_->next= temp;
       last_ = temp;
       ++ size_;
   }
   bool empty() const{
       return first!= nullptr;
   }
   int get() const{
       assert(first && "nullptr detected");
       return first->value; 
   }
   int release(){
       int result = get();
       auto * temp = first_->next;
       delete first_;
       first_=temp;
       if(! first_)
           last_ = nullptr;
       -- size_;
   }
   size_t size() const{
   }
   ~File(){
       while(first_){
           auto * temp = first_->next;
           delete first_;
           first = temp;
       }
   }
private:
    Node * first_ = nullptr;
    Node * last_ = nullptr;
    size_t size_;
};

NOTA:

1- La différence entre les fonctions get() et release() tient uniquement dans le fait que la fonction get() permet d'accéder à l'élément "prêt à partir" sans le retirer effectivement de la liste.

2- j'ai ajouté -- bien qu'elle ne soit pas forcément nécessaire -- la notion de taille de manière à ce qu'elle soit également évaluable en temps constant, car, a priori, ce qui importe dans une file (et dans une pile aussi, d'ailleurs) c'est de savoir si elle est vide ou non

A vrai dire j'avais appris à faire les files et piles comme des "sortes" de liste chaînées mais mon professeur nous imposes le prototype des fonctions et le .h donc je dois m'y plier.

Attention, un prototype de fonction n'a absolument aucun incidence sur le fonctionnement interne de ta classe : les fonctions n'étant sensées représenter que les services que l'on est en droit d'attendre de la part de la classe, non la manière dont elle s'y prend pour les rendre

Ton code présente en effet un problème majeur: voici une petite mise en situation:

• je crée ma file de 10 éléments
• j'ajoute 5 éléments, ce qui donne 1, 2, 3, 4, 5, V, V, V, V, V
• j'en retire 2, restent les élément V, V, 3, 4, 5, V, V, V, V, V dans la pile
• j'en rajoute trois, ce qui donne V, V, 3, 4, 5,6,7,8, V, V
• j'en retire deux, ce qui donne V, V, V, V, 5, 6, 7, 8, V, V
• j'en rajoute 5, ce qui donne V, V, V, V, 5, 6, 7, 8, 9, 10, 11, 12. 

(les V représentant les cases vides ) Et c'est à partir de là que tu vas avoir un problème, car, tu remarqueras que je n'ai toujours que 9 éléments dans ma file, et qu'elle n'est donc sensément pas remplie.  Manque de bol, si j'ai bien suivi ton code, les éléments 11 et 12 sont hors des limites du tableau

Pour être honnête, il y a parfaitement moyen de s'en sortir avec un tableau, mais la logique n'est en tout cas pas correcte

Or, c'est justement le genre de fonctionnement typique auquel tu dois t'attendre avec une file...

Ceci dit, tu pourrais peut-être amener en douceur ton prof à se poser certaines questions, ne serait-ce que au niveau de la fonction affichage, qui, entre toutes est sans doute celle qui me choque le plus.

Car, si on peut envisager de laisser l'utilisateur choisir une taille maximale pour sa file (*), il n'y a absolument aucun sens à envisager d'afficher autre chose que le seul élément sur le point de sortir d'en sortir.  Cela va -- purement et simplement -- à l'encontre du concept même de file

(*) et encore, j'ai bien parler d'envisager de permettre à l'utilisateur de choisir la taille maximale.  Ce ne devrait pas être une obligation, et il n'y a -- de mon point de vue -- aucun sens à imposer une limite arbitraire à ce niveau là au travers d'une valeur par défaut : soit l'utilisateur définit lui-même la limite, soit, la file est ... infinie, comme il se doit

On peut très bien représenter une file dans un tableau.

La représentation est un grand classique : "tampon circulaire" (circular buffer) avec des ajouts et retraits en temps constant.

Ref https://en.wikipedia.org/wiki/Circular_buffer

(l'article Wikipedia en français est indigent).

Beaucoup plus efficace que la représentation par des listes chaînes, avec les allocations qui prennent du temps, gaspillent de l'espace et dispersent les données en mémoire.

Le principe est simple : un indice qui indique la position du premier élément, et les autres sont après, avec retour au début du tableau quand on arrive à la fin. IMPORTANT : On ne décale jamais le contenu.

La tradition est d'utiliser un indice de début et un indice de fin. Dans les bouquins ça patine souvent sur le fait que ça empêcherait de distinguer le tableau plein du tableau vide. Et qu'il faut "donc" laisser une case vide. Ça serait vrai si on avait seulement ces 2 indices comme informations. Mais rien n'empêche de conserver aussi la taille.

PS en anglais, file ça veut dire fichier. Le bon nom est "queue".

Ps2 en fait c'est une EXCELLENTE IDEE, quand on essaie de réaliser une structure de données un peu complexe,  d'écrire des le début une fonction qui affiche les détails internes de cette structure.  Parce que chacun sait que ça ne marche pas du premier coup (a part des debutants qui croient que si ca compile c'est que ca marche) il va falloir chercher pourquoi, notamment en regardant se qui se passe dans la structure a chaque etape d'un scenario qui fait planter.

Ça ne fait évidemment pas partie de l'api destinée aux utilisateurs. #ifdef DEBUG_MON_MODULE

-
Edité par michelbillaud 22 septembre 2019 à 9:59:05

Autant je suis tout à fait disposé à envisager l'utilisation d'un tableau en interne -- à  condition d'avoir une logique cohérente et suffisante de gestion des éléments -- parce que cela correspond à un détail d'implémentation, et que l'on y trouve par ailleurs un tas de bonnes raisons technique, autant je suis désolé : vouloir accéder -- sous quelque forme que ce soit -- à autre chose qu'à l'élément qui se trouve à la tête de la file ou de la pile représente -- à mon sens -- la chose la plus illogique qui soit, parce que cela nie purement et simplement le concept même de pile ou de file.

j'admets, cependant, que mon point de vue s'appuie sur une expérience de gestion de stocks périssables, et que la notion sera sans doute bien plus facile à admettre avec les piles, tant le système FIFO peut rester "abstrait" dans de nombreux cas .

Mais, quand on y regarde de plus près, FIFO (First IN, First Out) et LIFO (Last In First Out) sont des concepts sommes toutes très similaires, dans le sens où l'on ne peut accéder à un élément bien particulier qu'après avoir retiré de la pile ou de la file les éléments qui le précèdent.

Or, si tu crées une pile de trois caisses et que tu essaye d'accéder à celle du bas sans avoir retiré les deux caisses qui sont au dessus, la pile se casse la gueule, purement et simplement.

Il en va malheureusement de même pour la file : ce qui rentre d'un coté sort de l'autre, et la file n'est pas prévue pour  permettre le parcours des éléments qui la composent.

Vouloir afficher le contenu d'une file revient, pour moi, exactement au même que de vouloir faire voler un sous-marin : c'est pas prévu pour

C'est comme une voiture, il y a qu'une personne qui a accès aux commande !

Sauf quand tu passe le permis ! il y a un double accès aux commandes !

De toutes façons, en vrai, personne ne devrait implémenter les types abstraits traditionnels pour les utiliser réellement, vu que ça fait partie des conteneurs de base de c++, java, etc.

C'est un EXERCICE.

Et il est aussi prévu que quand on fait un exercice, ça ne va pas marcher du premier coup.  Peut etre pas que dans les exercices, d'ailleurs.

-
Edité par michelbillaud 22 septembre 2019 à 16:22:03

rouloude a écrit:

C'est comme une voiture, il y a qu'une personne qui a accès aux commande !

Sauf quand tu passe le permis ! il y a un double accès aux commandes !

Bien qu'ayant passé mes différents permis en filière libre, à une époque où c'était (encore?) possible, je sais que les voitures que l'on met à ta disposition ne proposent généralement que les pédales en double commandes.  Cela ne représente qu'une toute petite partie des commandes utilisables depuis le siège du chauffeur

michelbillaud a écrit:

C'est un EXERCICE.

Même pour un exercice, ce n'est quand même pas les concepts entrant dans la catégorie des collections susceptibles de se satisfaire du parcours des éléments qui manquent!

A vrai dire, il n'y a que deux concepts de cette catégorie qui pour lesquels le parcours de tous les éléments est contre nature : ce sont, justement les piles et les files.  Et pourtant, parmi tous les concepts qui existent (les tableaux, les différentes sortes de liste, les arbres binaires), il faut  que le prof choisisse justement l'un de ceux qui ne donnent accès qu'à un seul élément à  la fois ????

Allons, je veux bien être coulant dans l'approche de l'enseignement, mais, quand même, il y a des limites

> Allons, je veux bien être coulant dans l'approche de l'enseignement,

Monseigneur est trop bon :-) 

Mais bon, je trouve suspect ce laxisme que tu as tout d'un coup avec les pointeurs bruts. Et du code même pas générique. Ca fait pas très  pro.

-
Edité par michelbillaud 22 septembre 2019 à 20:25:14

koala01 a écrit:

je sais que les voitures que l'on met à ta disposition ne proposent généralement que les pédales en double commandes.  Cela ne représente qu'une toute petite partie des commandes utilisables depuis le siège du chauffeur

Ça n'en fait pas pour autant une voiture ordinaire. C'est une voiture dédié à l'apprentissage de la conduite.

rouloude a écrit:

koala01 a écrit:

Ça n'en fait pas pour autant une voiture ordinaire. C'est une voiture dédié à l'apprentissage de la conduite.

Mais la modification ne dénature pas la voiture pour la cause : cela ne la transforme ni en avion, ni en sous-marin, ni en moto ou en camion !

Retire le lettrage de l'auto-école, et tu n'as aucune différence extérieure entre une voiture à double commande et sa soeur "normale".

Dans le cas présent, on demande la file d'adopter un comportement dont elle est conceptuellement incapable.  Un peu comme si on demandait à une voiture d'être capable de voler! ce n'est pas prévu pour

> blablablabla.

Une voiture volante, c'est prévu pour voler. Les analogies douteuses ne mènent à rien.

---

Bon, pour en revenir sur la représentation en tableaux, voila ce que ça donne en C (non, je ne fais pas les exercices en C++ si je ne suis pas payé très cher). Un tampon borné d'entiers, avec comportement FIFO.

#include <stdio.h>
#include <stdbool.h>

/**
 * Fifo Bounded Buffer of ints
 */

struct Buffer {
    unsigned size, capacity; 
    unsigned head, tail;    // head refers to the position of the next
    int *array;
};

void fb_init(struct Buffer *b, unsigned capacity) {
    b->size = 0;
    b->capacity = capacity;
    b->head = 0;
    b->tail = 0;
    b->array = malloc(capacity * sizeof(int)); // TODO : check
}

void fb_free(struct Buffer *b) {
    free(b->array);
    b->array = NULL;
}

void fb_put(struct Buffer *b, int value) {
    assert(b->size < b->capacity);
    b->array[b->head++] = value;
    if (b->head == b->capacity) {
        b->head = 0;
    }
    b->size++;
}

int fb_get(struct Buffer *b) {
    assert(b->size > 0);
    int value = b->array[b->tail++] = value;
    if (b->tail == b->capacity) {
        b->tail = 0;
    }
    b->size--;
    return value;
}

unsigned fb_size(const struct Buffer *b) {
    return b->size;
}

bool fb_is_full(const struct Buffer *b) {
    return b->size == b->capacity;
}

void fb_print_contents_for_debug(const struct Buffer *b) {
    printf("[");
    for (unsigned i = 0; i < b->size; i++) {
        println("%d ", b->array[i % b->capacity]);
    }
    printf("]");
}

Note : Dansla grande tradition des intervalles semi-ouverts, head est l'indice de la position où se fera le prochain ajout, les positions occupées (modulo la capacité) vont de tail à tail+size-1.

-
Edité par michelbillaud 23 septembre 2019 à 7:47:35

koala01 a écrit:

Retire le lettrage de l'auto-école, et tu n'as aucune différence extérieure entre une voiture à double commande et sa soeur "normale".

Retire l'affichage de la file (d'apprentissage) et tu n'as aucune différence extérieur avec une file.  

rouloude a écrit:

Retire l'affichage de la file (d'apprentissage) et tu n'as aucune différence extérieur avec une file.  

Ce que tu n'arrives pas à comprendre, c'est que la double commande n'est qu'un détail d'implémentation de la voiture : si le moniteur appuie sur une pédale, la voiture réagira exactement de la même manière que si c'était l'élève qui avait appuyé sur la pédale correspondante.

Si le moniteur appuie sur l'embrayage alors que l'élève appuie sur l'accélérateur, le moteur va s'emballer. Cela ne change rien aux services que peut rendre la voiture, qui est de transporter des biens et des personnes d'un endroit à l'autre en restant sur le plancher des vaches!

Ajouter une fonction publique à une classe, c'est ajouter un service qu'elle est capable de rendre à l'utilisateur. C'est ajouter la capacité de voler à une voiture.  Or, si une voiture savait voler, ce serait un avion, parce que, généralement, quand les roues d'une voiture quittent le plancher des vaches, c'est très mauvais signe pour ses occupants.

Du fait de sa nature même de système FIFO, une file ne peut accéder qu'au seul élément qui se trouve à sa tête (si tant est  qu'il y en ait un), tout comme une voiture est prévue pour ... rouler.

Peu importe de manière dont la file arrive à ce résultat en interne; peu importe que la voiture dispose de un, deux ou même dix jeux de pédales, cela ne change rien au fait que, par nature, une voiture ca roule, tout comme une file, par nature, ca ne fournit l'accès qu'à un seul élément à la fois.

Ajouter une fonction publique qui permet d'accéder -- quelle qu'en soit la raison -- à d'autres éléments de la file, c'est dénaturer le concept de file; c'est transformer notre file en liste aussi surement que le fait de rajouter "ce qu'il faut" (des ailes et une hélice, sans doute) à une voiture pour qu'elle puisse voler, revient à dénaturer la voiture pour la transformer en avion.

Le problème contre lequel je m'insurge, c'est le choix d'un mauvais terme pour désigner la chose représentée. 

Tu veux une fonction d'affichage? soit!  Mais, dans ce cas, parle de liste et non de file, et tant pis si il manque une ou deux fonctions capable de rendre quelques services qui vont avec la notion.

Exactement comme tu parlerais d'avion, et non de voiture, si tu voulais avoir un véhicule capable de voler.

-
Edité par koala01 23 septembre 2019 à 10:04:57

koala01 a écrit:

Du fait de sa nature même de système FIFO, une file ne peut accéder qu'au seul élément qui se trouve à sa tête (si tant est  qu'il y en ait un), tout comme une voiture est prévue pour ... rouler.

Non, c'est pas la file qui n'accède qu'à ceci cela. L'objet file, il accède à tous ses constituants.

C'est les opérations qui font partie de son interface publique. Et se comporter comme une file, ça veut dire que ça possède _au moins_ les opérations de base d'une file.

---

Et puis ce qui est écrit, ce n'est pas une file. C'est une -classe- qui a pour but de se comporter grosso-modo comme ce qu'on appelle file dans une vision idéalisée.

Et concrètement, c'est des objets qui n'ont pas une capacité illimitée. Du coup, ta classe file, avec ou sans affichage, elle ne respecte pas les invariants qui décrivent le comportement du type abstrait. Exemple

get(put(v, q))                   pour chaque file q et valeur v
  =    v    si empty(q)
  =  get(q) sinon

parce que, put(v, q),  ça peut être indéfini.

(les types abstraits algébriques, c'était à la mode dans les années 70-80, et après ça a tourné aux catégories :-()

-
Edité par michelbillaud 23 septembre 2019 à 11:18:11

Une file qui a un affichage (pour l'enseignement) n'est pas une pile, (on pourrait mettre un affichage sur une pile aussi) comme une voiture n'est pas un avion. Les deux peuvent avoir un afficheur de température intérieur alors que ce n'est pas indispensable.

Dans une discussion parallèle, il y a quelqu'un qui cause des tours de hanoi.

Des disques sont empilés. Il s'agit de bouger des disques du sommet d'une pile à une autre.

Et il n'aurait pas le droit de faire afficher le contenu de ses piles ?

-
Edité par michelbillaud 23 septembre 2019 à 11:19:03

Ah non, c'est absolument interdit ! il n'y a que dans les casses que l'on fait des piles de voitures.

michelbillaud a écrit:

Dans une discussion parallèle, il y a quelqu'un qui cause des tours de hanoi.

Ah, ben, je m'attendais à cette réflexion

michelbillaud a écrit:

Des disques sont empilés. Il s'agit de bouger des disques du sommet d'une pile à une autre.

Mais, dis moi ... Quelle est la classe que l'on  a mis en avant pour être en mesure de dresser la liste de chacune des tour ? n'est ce pas std::vector ?

Tiens, donc, pourquoi n'a-t-on, à ton avis, pas mis std::stack en avant, vu que std::vector est l'implémentation d'un tableau et que std::stack correspond à l'implémentation d'une pile?

Crois tu que ce n'est que pour un vulgaire soucis de performances?

Que nenni!!!  C'est parce que std::stack respecte le concept LIFO, et qu'il n'y a pas moyen de parcourir les éléments qui la composent autrement qu'en supprimant de la pile l'élément qui se trouve le plus "au dessus".

michelbillaud a écrit:

Et il n'aurait pas le droit de faire afficher le contenu de ses piles ?

Ben, non ... Sinon nous aurions utilisé std::stack

S'il n'y a rien qui nous empêche de manipuler une collection adaptée au parcours des éléments qui la composent "comme s'il s'agissait" d'une pile ou d'une file, l'inverse n'est absolument pas vrai.

rouloude a écrit:

Une file qui a un affichage (pour l'enseignement) n'est pas une pile, (on pourrait mettre un affichage sur une pile aussi) comme une voiture n'est pas un avion. Les deux peuvent avoir un afficheur de température intérieur alors que ce n'est pas indispensable.

Je suis vraiment désolé, mais non, ca casse l'invariant spécifique à ce genre de concept!

Les termes pile, file, stack et queue ne sont que d'autres termes représentant les concepts de FIFO et de LIFO, qui, par nature, ne donnent accès qu'à un seul élément à la fois.  C'est leur principal (et leur seul) invariant!

Si tu décide de permettre d'accéder -- sous quelle que forme que ce soit -- aux autres éléments, tu casse purement et simplement cet invariant. Tu exprimes donc un concept qui est tout, sauf pile ou file (LIFO ou FIFO).  Tu peux l'appeler comme tu veux (liste, par exemple), mais tu ne peux en aucun cas prétendre que c'est une pile ou une file.

L'idée d'une voiture à double pédale pour les auto école ne modifie pas la nature même du véhicule pour la cause, ne brise absolument pas l'invariant propre à une voiture qui est de se déplacer sur terre.  Pour changer l'invariant d'une voiture similaire, il faudrait faire en sorte qu'elle puisse se déplacer "ailleurs" que sur la terre ferme; c'est à dire, soit sur l'eau soit dans les airs.

Sauf que, si on admet une telle modification, nous n'avons plus affaire à une voiture, mais bien soit à un bateau, soit à un avion (voir un ULM quelconque).

> Les termes pile, file, stack et queue ne sont que d'autres termes représentant les concepts de FIFO et de LIFO, qui, par nature, ne donnent accès qu'à un seul élément à la fois.

Donc pour toi, la pile d'exécution d'un programme, c'est pas une pile, en fait.

-
Edité par michelbillaud 23 septembre 2019 à 20:17:28

michelbillaud a écrit:

Donc pour toi, la pile d'exécution d'un programme, c'est pas une pile, en fait.

-
Edité par michelbillaud il y a environ 5 heures

Je ne vais quand même pas te faire l'affront de te rappeler que

1. une fois que l'on a commencé à y placer les informations requises par la fonction appelée, on n'a plus accès aux informations mises en pile par la fonction appelante
2. toutes les données créées sur la pile par une fonction sont automatiquement détruites (dans l'ordre inverse de leur déclaration, qui plus est) lorsque la fonction est quittée
3. que l'on n'a plus accès à la moindre information issue d'une fonction appelée une fois que l'on est de retour au niveau de la fonction appelante

 C'est une pile particulière, adaptée à un usage bien particulier, mais c'est le système LIFO dans toute sa splendeur, vu qu'elle ne fourni les informations relatives qu'à une fonction à la fois

Même le système d'exceptions n'arrive pas à déroger à la règle !

Et pendant l'exécution, les variables automatiques sont logées quelque part en haut de la pile,

Fort heureusement, on peut accéder à autre chose qu'au dernier machin en haut.

Au passage ton point 1 est faux

Exemple les langages (pascal etc) où une fonction peut contenir des définitions de fonctions. La fonction interne a accès à  tout le contexte englobant. Qui peut se trouver loin en dessous.

Autre exemple. Tu appelles la fonction f en lui passant des paramètres. Ça empile les paramètres, et l'adresse de retour. La fonction à des variables locales, hop au dessus dans la pile aussi. Et alors le code de la fonction, comment il fait pour accéder aux paramètres reçus, qui ne sont plus en sommet de pile ? :-)

Au passage aussi ce n'est pas une question de système d'exploitation, mais d'implémentation du langage.

Bref, il y a bien une notion formelle de pile file etc, avec accès à un seul élément etc, mais ce sont des notions idéalisées.

Ça n'empêche pas de parler de pile pour des trucs dont l'idée générale est d'entasser dans un sens ou dans l'autre, mais ça n'empêche pas d'avoir d'autres actions en pratique. Par exemple dans les langages basés sur les piles (Postscript, forth), il y a des opérations pour dupliquer/retirer le n ieme élément sous le sommet. Parce que c'est pratique. Ça ne fait pas partie du type abstrait pile, but who cares ?

Bref, le code de départ, c'est un tampon circulaire _utilisé_ comme une fifo. Improprement appelé file vu que c'est queue en anglais.

C'est comme si on disait qu'un triporteur vespa est une voiture. C'est un genre. Un genre de velomoteur aussi. Et de brouette, pourquoi pas.

-
Edité par michelbillaud 24 septembre 2019 à 9:02:03

michelbillaud a écrit:

Et pendant l'exécution, les variables automatiques sont logées quelque part en haut de la pile,

Fort heureusement, on peut accéder à autre chose qu'au dernier machin en haut.

Pour moi, il n'y a rien à faire, ce que l'on place dans la pile d'appel est un concept que l'on pourrait appeler "ensemble dee données (d'une fonction)", et c'est ce concept que l'on empile, fut-il de taille variable, au même titre que nous pourrions empiler une structure 3D, qui nous permettrait "bien sur" d'accéder aux trois données représentant les différents axes

michelbillaud a écrit:

Exemple les langages (pascal etc) où une fonction peut contenir des définitions de fonctions. La fonction interne a accès à  tout le contexte englobant. Qui peut se trouver loin en dessous.

Ca reste une boite (plus petite) dans une boite (plus grande), ce sont les boites les plus grandes que tu empile

michelbillaud a écrit:

Autre exemple. Tu appelles la fonction f en lui passant des paramètres. Ça empile les paramètres, et l'adresse de retour. La fonction à des variables locales, hop au dessus dans la pile aussi. Et alors le code de la fonction, comment il fait pour accéder aux paramètres reçus, qui ne sont plus en sommet de pile ? :-)

Cela accède au contenu de la dernière boite mise dans la pile, j'ai toujours utilisé le terme générique d'élément, je n'ai jamais imposé la moindre restriction sur le genre d'élément que l'on pouvait empilé, que je sache

Tu réagis comme si j'avais imposé qu'on ne puisse empiler que des types primitifs, mais l'élément peut être aussi complexe qu'on le veut, c'est juste "une boite"

michelbillaud a écrit:

Au passage aussi ce n'est pas une question de système d'exploitation, mais d'implémentation du langage.

Ca, je suis tout à fait d'accord

michelbillaud a écrit:

C'est comme si on disait qu'un triporteur vespa est une voiture. C'est un genre. Un genre de velomoteur aussi. Et de brouette, pourquoi pas.

Du point de vue légal, c'est considéré comme une mobylette, même si elle n'est pas considérée comme "un véhicule étroit" à cause de ses trois roues

koala01 a écrit:

michelbillaud a écrit:

Exemple les langages (pascal etc) où une fonction peut contenir des définitions de fonctions. La fonction interne a accès à  tout le contexte englobant. Qui peut se trouver loin en dessous.

Ca reste une boite (plus petite) dans une boite (plus grande), ce sont les boites les plus grandes que tu empile

Faux. Les "boites" comme tu les appelles ne sont pas emboitées. Les élements du contexte peuvent être arbitrairement loin dans la pile. exemple

fonction f (a, b) {
    fonction g(n) {
        si n = 0  h()
        sinon g(n-1);
    }
    fonction h() {
       affiche(b);
    }

    g(a);
}

la fonction h va chercher son b  de nombreux étages en dessous (dépend de la valeur de a).

Et je passe les subtilités liés au passage de fonctionnelles en parametres.

-
Edité par michelbillaud 24 septembre 2019 à 16:12:01

non, parce que tu confond l'élément de la pile avec le contenu de l'élément en question!

Même si la pile ne donne accès qu'à un seul élément, elle n'en demeure pas moins un container, dont le but principal est, justement, de fournir l'accès à cet élément:

Ta pile d'appel va donc fonctionner sous une forme proche de

stack.push(Function{return_address, params});
/* lors de la déclaration d'une nouvelle variable dans la fonction */
stack.top().add(Data{/* ...*/});
/* on pourrait très bien envisager quelque chose comme */
auto * caller = stack.top().caller(); /* accède à l'élément de la pile correspondant 
                                       * à la fonction appelante 
                                       */
/* mais ce n'est pas le problème de la pile */
/* au moment du retour */
nextAddress = stack.top().return_address; /* le compteur d'adresse du processeur */
stack.pop();

L'élément que tu place dans la pile, c'est une boite!  Elle contient ce qu'elle veut!

On ne sait pas dire à quoi l'élément que tu place dans la pile donnera accès; Si cela se trouve, il contiendra effectivement l'adresse dans la pile de la fonction qui l'a appelé.  Mais ca, ca sort du cadre de compétences la pile en elle-même : c'est le problème de l'élément.

La pile, elle, elle ne fait que ce pour quoi elle a été prévue : contenir "un nombre a priori inconnu"  d'éléments, et fournir l'accès au dernier élément qui a été ajouté.

-
Edité par koala01 25 septembre 2019 à 10:14:59

> L'élément que tu place dans la pile, c'est une boite!  Elle contient ce qu'elle veut!

Ah parce que les boites veulent quelque chose maintenant.

Bon, faudrait être sérieux. Il y a un vocabulaire technique précis pour parle de ces choses.  Parce que là, ce que tu racontes est (désolé) complètement vaseux.

Ton exemple à base de /* on pourrait très bien envisager */, ça reste complètement à démontrer. J'y croirai quand je verrai l'idée développée et du code qui fait quelque chose.

Ce qu'il y a sur la pile d'exécution, c'est des _cadres de piles_ (stack frames).

Ce que j'expliquais, c'est que le code qui s'exécute dans un cadre de pile (le code de la fonction en cours d'exécution) a accès à des données situées dans d'autres cadres de pile. C'est évident par exemple quand on reçoit des paramètres par référence. Derrière ça se matérialise par des adresses de trucs situés dans un autre élément de la pile.

Alors, oui, les cadres de piles sont empilés, et non, on n'a pas accès qu'au seul contenu du dernier cadre de pile. Un autre exemple : lors d'un appel de fonction, l'évaluation des paramètres à transmettre se fait dans un cadre de pile (la fonction courante) en remplissant sur la pile le cadre suivant (pour la fonction qui va être appelée).

Pourtant c'est bien une pile.

Donc, il ne faut pas avoir une vision trop étroite de ce qu'est une pile. Il y a une définition usuelle, stricte, en terme de type abstrait, et  des usages usuels du mot pour désigner des trucs où l'idée est d'avoir un accès LIFO, mais pas que.

-
Edité par michelbillaud 25 septembre 2019 à 11:01:19

Hé bien, parlons technique :

une pile, c'est un conteneur qui contient des éléments, mais qui présente la particularité de n'autoriser l'accès qu'à un seul élément à la fois, à savoir : le dernier élément qui a été ajouté.

A partir de là, l'élément en question, tu le développe strictement comme tu veux: si tu souhaites contourner la restriction imposée par la notion de pile, et pouvoir accéder à l'élément qui a été introduit dans la pile juste avant, libre à toi.

Par exemple, tu pourrais parfaitement avoir un code proche de

struct Element{
    Element * previous = nullptr;
    /* toutes les autres données qui t'intéressent
     * dans ton cas particulier
     */
};

using MyStack = std::stack<Element>;
void add(MyStack & stack,/* other parameters */){
    Element temp;
    if(! stack.empty)
        temp.previous = &stack.top();
    stack.push(temp);
}

et cela te permettra n'importe quelle logique proche de

void doSomething(MyStack /* const*/ & stack){
   /* on accède au seul élément auquel la pile donne
    * accès
    */
   auto /* const*/ & temp = stack.top(); 
   auto * first = temp.previous;
   /* on peut même remonter jusqu'au premier élément
    * si on le souhaite
    */
   while(first->previous){
       first = first->previous;
   }
   /* on s'assure quand même que l'élément obtenu
    * de la pile n'était pas le premier élément
    */
   if(first){
        /* on a récupéré le premier élément ajouté à la pile
         */
   }else{
       /* l'élément obtenu était le premier ajouté */
   }
}

Personnellement, cela ne me dérange absolument pas.  Tu remarquera que l'usage que l'on fait de la pile en elle-même respecte strictement le concept LIFO.  C'est l'usage de l'élément que l'on place dans la pile qui contourne les restrictions de celle-ci

michelbillaud a écrit:

Ce que j'expliquais, c'est que le code qui s'exécute dans un cadre de pile (le code de la fonction en cours d'exécution) a accès à des données situées dans d'autres cadres de pile. C'est évident par exemple quand on reçoit des paramètres par référence. Derrière ça se matérialise par des adresses de trucs situés dans un autre élément de la pile.

Et cela ne me pose aucun problème, vu que c'est le cadre de la pile qui répond aux besoins spécifiques pour lesquels il a été développé.

C'est bien pour cela qu'il ne faut pas confondre le contenu de la pile, les éléments que l'on place dans la pile, avec le contenu des éléments en lui-même.  Ce sont deux champs de responsabilités tout à fait différents

michelbillaud a écrit:

Alors, oui, les cadres de piles sont empilés, et non, on n'a pas accès qu'au seul contenu du dernier cadre de pile

Et, pourtant, si : à partir de la pile en elle-même, tu n'as accès qu'au dernier cadre de pile ajouté.  C'est à partir du dernier cadre de pileajouté que tu peux éventuellement avoir accès aux cadres de pile ajouté précédemment!  La nuance est de taille

michelbillaud a écrit:

Donc, il ne faut pas avoir une vision trop étroite de ce qu'est une pile.

Je n'ai pas une vision étroite de ce qu'est une pile, j'en ai une vision rigoureuse, en accord avec le SRP : la seule responsabilité de la pile, c'est de contenir des éléments et de donner accès au dernier élément ajouté.

Si les éléments veulent contourner les restrictions imposées par la notion de pile, il en va de leur responsabilité propre, mais la pile n'a rien à voir dans l'histoire (en dehors de permettre d'accéder à un et un seul élément à la fois et de maintenir en mémoire l'ensemble des éléments ajoutés depuis le début, bien sur)

-
Edité par koala01 25 septembre 2019 à 12:31:21

Revenons au dictionnaire  https://www.larousse.fr/dictionnaires/francais/pile/60903

• Amas de choses disposées ou rangées les unes sur les autres : Une pile de livres, de linge.

..

• En informatique, structure ordonnée d'informations que l'on ne peut normalement remplir ou vider que par une seule et même extrémité.

Indices

• normalement
• remplir ou vidér par une même extrémité.

Ne pouvoir remplir ou vider que par une extrémité, ça n'exclut pas d'une part d'autres opérations que remplir ou vider,

Exemple les opérations de Forth, langage à pile si il en est http://wiki.laptop.org/go/Forth_stack_operators

dup   ( a -- a a )
?dup  ( a -- a a | 0 ) dup if dup then ;
drop  ( a -- )
swap  ( a b -- b a )
over  ( a b -- a b a )
rot   ( a b c -- b c a )
-rot  ( a b c -- c a b ) rot rot ;
nip   ( a b -- b ) swap drop ;
tuck  ( a b -- b a b ) swap over ;

ni même, d'autre part,  de pouvoir remplir ou vider de plusieurs éléments d'un coup !

2drop ( a b -- ) drop drop ;

-
Edité par michelbillaud 25 septembre 2019 à 13:55:15