Question sur les listes chainées.

Bonjour

J'ai dans un livre un exemple de listes chainées, dont je reproduis la classe:

Code:

---

1 2 3 4 5 6 7

class Node{ public: int data; Node *next; Node(int, Node*); //déclarations de fonction.. };

---

J'ai voulu optimisé les fonctions push et pull.
La fonction push ajoute un objet à la suite des autres.

J'ai transformé:

Code:

---

1 2 3 4

void Node::push(Node** mapile,int valeur){ Node* element=new Node(valeur,*mapile); *mapile=element; }

---

en:

Code:

---

1 2 3

void Node::push(Node* &mapile,int valeur){ mapile=new Node(valeur,mapile); }

---

>>La seule grosse différence est que dans le deuxième cas, je fait passer un pointeur sur une référence. Plus exactement, je fais passer la référence du pointeur sur mapile.
Mais j'ai quand même du mal à comprendre la différence entre Node* mapile et Node* &mapile.



La fonction pull est censée rajouter un objet en début de liste.

j'ai aussi transformé ce code :

Code:

---

1 2 3 4 5 6

void Node::pull(Node *ppile,int val){   do{ppile=ppile->next;}while(ppile->next); ppile->data=val; ppile->next=new Node(0,0); }

---

en :

Code:

---

1 2 3 4

void Node::pull(Node *ppile,int val){ do{ppile=ppile->next;}while(ppile->next->next); ppile->next=new Node(val,ppile->next); }

---

En effet, je préfère ce code au premier. Dans les deux cas, on crée en effet qu'un seul nouvel objet. Mais ce que cache le premier, c'est que le pointeur qui est en bout de liste, qui vaut 0, existe deja. Donc quand on fait: new Node(0,0), on crée une nouvelle fin de liste, alors qu'elle existe déjà. Dans le deuxième cas, on la conserve.
On reconnecte simplement la fin de liste au nouvel objet.

que pensez vous de mes modifs?
Merci

Pour la première question, je n'ai vu aucun pointeur sur référence dans ton code: Seulement une référence sur pointeur.

Pour la seconde, j'ai deux remarques:
Premièrement, je supporte totalement ta modif, car je suis contre les "objets de fin" pour les listes chaînées.
Malheureusement, et j'en viens à mon second point, ce code ne prend pas en compte le cas où la liste est vide avant ajout. De plus, tu sautes le premier élément. C'est pourquoi je tends à faire mes fonctions ainsi à la place:

Code:

---

1 2 3 4 5 6 7 8 9 10 11

/*static*/ void Node::pull(Node **ppPremier, int val) { assert(ppPremier != NULL);   Node **ppCourant = ppPremier; while( (*ppCourant ) != NULL ) ppCourant = &( (*ppCourant)->next ); //Pointe sur le pointeur suivant //Maintenant, ppCourant pointe sur le pointeur nul à la fin de la liste   *ppCourant = new Node(val, NULL); }

---

Merci pour la rép

Citation:

---

Pour la première question, je n'ai vu aucun pointeur sur référence dans ton code: Seulement une référence sur pointeur.

---

Je suis ok!

Citation:

---

Premièrement, je supporte totalement ta modif,

---

Ca fait plaisir.

Citation:

---

Malheureusement, et j'en viens à mon second point, ce code ne prend pas en compte le cas où la liste est vide avant ajout

---

ok mais c'est une gestion d'exception. Ce n'est pas le corps de la fonction.

Citation:

---

De plus, tu sautes le premier élément. C'est pourquoi je tends à faire mes fonctions ainsi à la place:

---

Je vais étudier ton code, mais à première vue, tu utilises des pointeurs sur pointeurs. Je veux éviter à tous prix des pointeurs sur pointeurs. J'ai trop de mal a comprendre leurs fonctionnements.
C'est pour cela que j'avais mis une référence.

Citation:

---

De plus, tu sautes le premier élément.

---

je vois ce que tu veux dire. Il faut utiliser deux fois la fonction push avant d'utiliser la fonction pull. C'était trop simple pour être vrai.

Deux autres remarques:
D'après ce Bjarne Sostrup sur son site, il vaut mieux utilisé le pointeur 0 que le pointeur NULL.

De plus, je pense qu'il vaut mieux faire:

Code:

---

*ppCourant=new Node(val,*ppCourant);

---

que

Code:

---

*ppCourant=new Node(val,0);

---

, car sinon, on ne raccroches pas au pointeur 0.

(Moi, je tiens à ce qu'il y ait un 0 à la fin de la liste).

Citation:

---

D'après ce Bjarne Sostrup sur son site, il vaut mieux utilisé le pointeur 0 que le pointeur NULL.

---

En fait, avec le prochain standard, le mieux sera d'utiliser nullptr. De toute façon, dans l'état actuel des choses, on a #define NULL 0 en C++, donc ça ne change pas grand-chose.

Citation:

---

De plus, je pense qu'il vaut mieux faire:

Code:

---

*ppCourant=new Node(val,*ppCourant);

---

que

Code:

---

*ppCourant=new Node(val,0);

---

, car sinon, on ne raccroches pas au pointeur 0.

---

Pour insérer à la fin, les deux sont rigoureusement équivalents. Par contre, le premier code est idéal pour insérer n'importe ou, ce qui fait qu'il est mieux, en effet ;)

Pour l'emploi des pointeurs de pointeurs, il n'y a pas trop le choix malheureusement. Je ne pense pas qu'on puisse facilement employer une référence dans la boucle, vu que les références ne peuvent pas être changées.

Le principe est montré ici: On pointe directement sur le pointeur qu'on modifiera lors de l'insertion, et ce code marche aussi bien pour le premier élément que pour tous les suivants.

Citation:

---

Je ne pense pas qu'on puisse facilement employer une référence dans la boucle, vu que les références ne peuvent pas être changées.

---

C'est pour cette raison qu'on ne pourra jamais avoir qqch comme cela:

Code:

---

1 2 3 4 5

int a=3; int b=4; int *m=&b; &a=&b; &a=m;

---

une référence ne peut pas être une lvalue, vue qu'elle est constant.

De la même manière qu'on ne peut pas avoir:

Code:

---

1 2	int const pp=3; pp=4;

---

Pourtant une fonction, qui renvoie une référence, peut être une lvalue, mais ce n'est pas la même chose.

Au fait, quelqu'un aurait-il le livre Effective C++ de Scott Meyers?
car ce que j'étudie est issu de son livre, et il y a un truc que je n'arrive vraiment pas à comprendre.
pour ceux qui l'ont, il s'agit de l'Item 10. Dans lequel il crée un pool de mémoire.
(Mais comment utilisé ce pool? )

-> fork de la discussion plus générale sur les listes et les piles ici.

@deublete : qu'est ce que tu ne comprends pas ?

Je ne comprends pas certains éléments du code suivant. Il s'agit de l'operateur new d'une classe Airplane.

Déjà, pourquoi fait il une conversion:

Code:

---

1 2	static_cast<Airplane*>(::operator new(BLOCK_SIZE * sizeof(Airplane)));

---

Certes l'opérateur new renvoie qqch de type void*, mais la converstion ne serait-elle pas implicite?

Ensuite, il crée ici un pool de mémoire pour l'allocation sur le tas, par l'opérateur new. Je me demande pourquoi il est nécessaire d'utiliser une liste chaînée, et pas, tout simplement, un tableau??

Merci

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

void * Airplane::operator new(size_t size) { // send requests of the "wrong" size to ::operator new(); // for details, see Item 8 if (size != sizeof(Airplane)) return ::operator new(size); Airplane *p = // p is now a pointer to the headOfFreeList; // head of the free list // if p is valid, just move the list head to the // next element in the free list if (p) headOfFreeList = p->next; else { // The free list is empty. Allocate a block of memory // big enough to hold BLOCK_SIZE Airplane objects Airplane *newBlock = static_cast<Airplane*>(::operator new(BLOCK_SIZE * sizeof(Airplane))); // form a new free list by linking the memory chunks // together; skip the zeroth element, because you'll // return that to the caller of operator new for (int i = 1; i < BLOCK_SIZE-1; ++i) newBlock[i].next = &newBlock[i+1]; // terminate the linked list with a null pointer newBlock[BLOCK_SIZE-1].next = 0; // set p to front of list, headOfFreeList to // chunk immediately following p = newBlock;

---

Alors:

1. Non, en C++ le cast n'est pas implicite: Il ne l'est qu'en C.
2. Le fait de gérer les objets libres comme une liste chaînée a un rapport avec la libération des objets. En gros, il faudrait voir le code de operator delete (et le code complet de operator new) pour plus d'infos.

Voila, la tu as tout:

Code:

---

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

class Airplane { public: // custom memory management static void * operator new(size_t size); ... private: union { AirplaneRep *rep; // for objects in use Airplane *next; // for objects on free list }; // this class-specific constant (see Item 1) specifies how // many Airplane objects fit into a big memory block; // it's initialized below static const int BLOCK_SIZE; static Airplane *headOfFreeList; };

---

Opérateur new:

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

void * Airplane::operator new(size_t size) { // send requests of the "wrong" size to ::operator new(); // for details, see Item 8 if (size != sizeof(Airplane)) return ::operator new(size); Airplane *p = // p is now a pointer to the headOfFreeList; // head of the free list // if p is valid, just move the list head to the // next element in the free list if (p) headOfFreeList = p->next; else { // The free list is empty. Allocate a block of memory // big enough to hold BLOCK_SIZE Airplane objects Airplane *newBlock = static_cast<Airplane*>(::operator new(BLOCK_SIZE * sizeof(Airplane))); // form a new free list by linking the memory chunks // together; skip the zeroth element, because you'll // return that to the caller of operator new for (int i = 1; i < BLOCK_SIZE-1; ++i) newBlock[i].next = &newBlock[i+1]; // terminate the linked list with a null pointer newBlock[BLOCK_SIZE-1].next = 0; // set p to front of list, headOfFreeList to // chunk immediately following p = newBlock; headOfFreeList = &newBlock[1]; } return p; }

---

Constantes statiques:

Code:

---

1 2 3

Airplane *Airplane::headOfFreeList; // these definitions // go in an implemenconst int Airplane::BLOCK_SIZE = 512;

---

Operateur delete:

Code:

---

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

void Airplane::operator delete(void *deadObject, size_t size) { if (deadObject == 0) return; // see Item 8 if (size != sizeof(Airplane)) { // see Item 8 ::operator delete(deadObject); return; } Airplane *carcass = static_cast<Airplane*>(deadObject); carcass->next = headOfFreeList; headOfFreeList = carcass; }

---

Eh bien, c'est bien ce que je pensais, et mes explications tiennent la route.

D'ailleurs, conformément à mes soupçons, la mémoire des blocs n'est jamais vraiment libérée.

Citation:

---

D'ailleurs, conformément à mes soupçons, la mémoire des blocs n'est jamais vraiment libérée.

---

A quoi le vois tu?
Je crois que l'auteur donne une explication:

It would not be difficult to modify Airplane's memory management routines so that the blocks of memory
returned by ::operator new were automatically released when they were no longer in use, but there are two
reasons why you might not want to do it.
The first concerns your likely motivation for tackling custom memory management. There are many reasons why
you might do it, but the most common one is that you've determined (see Item M16) that the default operator new
and operator delete use too much memory or are too slow (or both). That being the case, every additional byte
and every additional statement you devote to tracking and releasing those big memory blocks comes straight off
the bottom line: your software runs slower and uses more memory than it would if you adopted the pool strategy.
For libraries and applications in which performance is at a premium and you can expect pool sizes to be
reasonably bounded, the pool approach may well be best.

C'est simple, je l'ai vu au fait que les blocs ne sont pas eux-mêmes mémorisés en tant que blocs: On en perd la trace après création.

Bien sûr, ce pool de mémoire est différent ce que j'ai l'habitude de faire pour mes besoins, car les besoins sont différents.
Déjà, le pool est global et a une durée de vie illimitée. Mes allocateurs sont généralement optimisés pour la vitesse et non la mémoire, et au lieu du pooling, font plutôt le contraire: La mémoire d'un objet n'est jamais réutilisée ou "libérée" pendant la durée de vie de l'allocateur, et tout est libéré d'un coup à sa destruction (en termes Windows, ce serait l'équivalent de HeapCreate(), N*HeapAlloc(), jamais de HeapFree(), et HeapDestroy() à la fin)

Et si on fait cela :

Code:

---

1 2 3

Airplane *newBlock = (::operator new(BLOCK_SIZE * sizeof(Airplane)));

---

au lieu de cela:

Code:

---

1 2 3

Airplane *newBlock = static_cast<Airplane*>(::operator new(BLOCK_SIZE * sizeof(Airplane)));

---

que se passe t il?

À vue de nez, je dirais une erreur de compilation.