Liste chaînée - Optimisation de la consommation mémoire

Version imprimable

23/12/2014, 14h15
souki22

Liste chaînée - Optimisation de la consommation mémoire
Bonjour à tous,

J'ai implémenté une structure liste chaînée sous Xcode, et je voudrais optimiser la consommation mémoire de mon code. Voici deux architectures entre lesquelles j'hésite :

- le constructeur par défaut de la classe noeud (resp de la classe liste) initialise le champ de la classe noeud (resp liste) de type noeud* par un NULL

- le constructeur par défaut de la classe noeud (resp de la classe liste) alloue une zone mémoire au champ de la classe noeud (resp liste) de type noeud* avec un new

Pour l'instant je me suis contenté de la première architecture (une initialisation à NULL sans appel à new), et dans le main, je déclare une variable n de type noeud, puis je déclare et initialise un pointeur h de type noeud* sur n en utilisant &. Ce pointeur étant destiné à être la tête d'une liste, je déclare ensuite une liste et l'initialise simultanément avec ce pointeur. Cela donne :
Code:

1 2 3 node<int> n(2); node<int>* h=&n; mylist::list<int> l(h);
Vu que je n'ai utilisé aucun new dans mes constructeurs ni dans le main, mes destructeurs ne contiennent pas de commande delete . C'est ce qu'on m'a appris en tous cas. Merci de m'éclairer si je me trompe ou de compléter ma connaissance là dessus.

Je remarque aussi que lorsque j'ajoute delete head dans le destructeur de liste, tout se passe comme si je l'avais décommenté : même résultat dans la console et pas d'erreur de mémoire lancée par Xcode.

Ma question est : quelle architecture entre les deux que j'ai évoquées ci dessus devrais-je choisir afin d'avoir la meilleur gestion mémoire (pas de perte/fuite de mémoire et consommation minimale de mémoire) ? Y a-t-il une meilleure architecture, dans le sens de la gestion mémoire, que celles que j'ai citées ?

Joyeuses fêtes !
23/12/2014, 14h31
Médinoc

Le code client ne devrait même pas avoir à construire des nœuds, c'est à la liste de faire ça (mais je suis conscient qu'un itérateur peut être un pointeur de nœud, par contre).

Ensuite, selon la façon dont tu gères ton chaînage et la responsabilité de destruction, le destructeur de la liste chaînée peut être plus ou moins complexe. Personnellement je donnerais à la liste la responsabilité de détruire tous les chaînons (et j'aurais sans doute à les gérer explicitement, avec un pointeur nu dans la liste et usages explicites de delete) plutôt que faire le truc bizarre consistant à donner à chaque chaînon la responsabilité de détruire le suivant (ce qui cause une grosse asymétrie quand la liste est doublement chaînée).

C'est ce que j'ai fait effectivement : les destructeurs de la classe Node et de la classe Iterator sont définis par un bloc vide et le destructeur de la classe List parcourt la liste instanciée avec une boucle for et détruit en passant les chaînons. Voici l'interface de mes classes : ...

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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
class node 
{
 
public:
 
    int data;
    node* next;
    node(node* N=NULL):next(N) {}
    node(int value, node* N=NULL):data(value),next(N){}
    ~node(){}
 
};
 
 
 
class iterator 
{
public:
 
    node* current_node;
 
 
    iterator(node* N=NULL):current_node(N){}
    ~iterator(){}
    iterator& operator++();
    iterator operator++(int);
    int& operator*()const;
    bool operator==(const iterator& It) const;
    bool operator!=(const iterator& It) const;
 
};
 
 
 
 class list 
   {
        node* head;
 
    public:
        list():head(NULL){}
        list(int value)
        {
            node* first_node=new node;
            first_node->data=value;
            first_node->next=NULL;
            head=first_node;
        }
 
        size_t length()const;
        iterator begin()const;
        iterator<T> end()const;
        void insert_front(int input) 
        {
            node<T>* to_be_added=new node<T>;
            to_be_added->data=input;
            to_be_added->next=head;
            head=to_be_added;
        } 
        void insert_back(int input) 
        {
            if (head==NULL) 
            {
                node<T>* to_be_added=new node<T>;
                to_be_added->data=input;
                to_be_added->next=NULL;
                head=to_be_added; 
                return;
            }
            //looking for the last element
            node<T>* current=head;
            while (current->next!=NULL)
            {
                current=current->next;
            }
            //now current is the last element of the list
            node<T>* to_be_added=new node<T>;
            to_be_added->data=input;
            to_be_added->next=NULL;
            current->next=to_be_added;
        }   
        ~list()
        {
            for(iterator it=begin();it!=end();)
            {
                iterator tmp=it++;
                delete tmp.current_node;
            }
 
        }
    };

… en espérant ne pas avoir causé de fuites de mémoire ainsi.

24/12/2014, 13h47
Médinoc

Attention, tu devrais déclarer tes constructeurs comme explicit.

Et dans le constructeur de list (et pas mal d'autres endroits, en fait), pourquoi remplis-tu les champs à la main alors que tu as donné à node un constructeur exprès pour ça?

Notes: Personnellement, je suis du genre à penser qu'il est plus difficile de faire une liste chaînée avec des pointeurs intelligents qu'avec des pointeurs nus. Par contre, ça reste difficile. Dans tout ce qui n'a pas spécifiquement le but pédagogique d'apprendre à faire marcher une liste chaînée, je conseillerais d'utiliser std::list<> (ou std::stack<> ou std::deque<>) plutôt que faire sa propre cuisine.