Discussion :

[deubelte]

Bonjour

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

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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

en:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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

[Médinoc]

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 C++ :

Sélectionner tout - Visualiser dans une fenêtre à part

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

[deubelte]

Merci pour la rép

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!

Premièrement, je supporte totalement ta modif,

Ca fait plaisir.

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.

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.

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.

[deubelte]

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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

que

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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

[Médinoc]

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.

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

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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

que

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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

[deubelte]

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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.

[deubelte]

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

[3DArchi]

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

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

[deubelte]

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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;

[Médinoc]

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.

[deubelte]

Voila, la tu as tout:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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

Operateur delete:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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

[Médinoc]

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.

[deubelte]

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.

[Médinoc]

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)

[deubelte]

Et si on fait cela :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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

au lieu de cela:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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

que se passe t il?

[Médinoc]

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