Comment un nœud sentinelle offre-t-il des avantages par rapport à NULL?

Il n’y a aucun avantage avec les sentinelles si vous ne faites que de simples itérations et ne regardez pas les données dans les éléments.

Cependant, il y a un réel avantage à l’utiliser pour les algorithmes de type “find”. Par exemple, imaginez une liste de listes chaînée std::list où vous voulez trouver une valeur spécifique x .

Ce que vous feriez sans sentinelles est:

 for (iterator i=list.begin(); i!=list.end(); ++i) // first branch here { if (*i == x) // second branch here return i; } return list.end(); 

Mais avec les sentinelles (bien sûr, la fin doit être un véritable nœud pour cela …):

 iterator i=list.begin(); *list.end() = x; while (*i != x) // just this branch! ++i; return i; 

Vous voyez qu’il n’y a pas besoin de la twig supplémentaire pour tester la fin de la liste – la valeur est toujours garantie d’être là, donc vous retournerez automatiquement end() si x ne peut pas être trouvé dans vos éléments “valides”.

Pour une autre application intéressante et utile des sentinelles, voir “intro-sort”, l’algorithme de sorting utilisé dans la plupart des implémentations std::sort . Il a une variante cool de l’algorithme de partition qui utilise des sentinelles pour supprimer quelques twigs.

Je pense qu’un petit exemple de code serait une meilleure explication qu’une discussion théorique.

Ce qui suit est le code de suppression de nœud dans une liste de nœuds à double chaînage où NULL est utilisé pour marquer la fin de la liste et où deux pointeurs en first et en last sont utilisés pour contenir l’adresse du premier et du dernier nœud:

 // Using NULL and pointers for first and last if (n->prev) n->prev->next = n->next; else first = n->next; if (n->next) n->next->prev = n->prev; else last = n->prev; 

et c’est le même code où à la place il y a un nœud factice spécial pour marquer la fin de la liste et où l’adresse du premier nœud de la liste est stockée dans le champ next du nœud spécial et où le dernier nœud de la liste est stocké dans le champ prev du nœud factice spécial:

 // Using the dummy node n->prev->next = n->next; n->next->prev = n->prev; 

Le même type de simplification est également présent pour l’insertion de nœuds; par exemple pour insérer le noeud n avant le noeud x (ayant x == NULL ou x == &dummy signifiant insertion en dernière position), le code serait:

 // Using NULL and pointers for first and last n->next = x; n->prev = x ? x->prev : last; if (n->prev) n->prev->next = n; else first = n; if (n->next) n->next->prev = n; else last = n; 

et

 // Using the dummy node n->next = x; n->prev = x->prev; n->next->prev = n; n->prev->next = n; 

Comme vous pouvez le voir, l’approche par nœud factice supprimée pour une liste à double liaison, tous les cas spéciaux et tous les conditionnels.

L’image suivante représente les deux approches pour la même liste en mémoire …

La réponse à votre question (1) se trouve dans la dernière phrase de l’entrée Wikipédia liée: “En tant que nœuds qui seraient normalement liés à NULL, ils sont désormais liés à” nil “(y compris nil). vérifier NULL. “

Normalement, vous devez tester un noeud pour NULL avant d’y accéder. Si, au contraire, vous avez un nœud nil valide, vous n’avez pas besoin de faire ce premier test, en sauvegardant une comparaison et une twig conditionnelle, ce qui peut être coûteux sur les processeurs superscalaires modernes lorsque la twig est mal prédite.

Je vais essayer de répondre dans le contexte de la bibliothèque de modèles standard:

1) Dans un appel à “next ()”, NULL n’indique pas nécessairement la fin de la liste. Que se passe-t-il si une erreur de mémoire s’est produite? Renvoyer un nœud sentinelle est un moyen définitif d’indiquer que la fin de liste s’est produite et non un autre résultat. En d’autres termes, NULL pourrait indiquer une variété de choses, pas seulement la fin de la liste.

2) Ceci est juste une méthode possible: lorsque vous créez votre liste, créez un nœud privé qui n’est pas partagé en dehors de la classe (appelé par exemple “lastNode”). Après avoir détecté que vous avez effectué une itération à la fin de la liste, faites “next ()” renvoyer une référence à “lastNode”. Également avoir une méthode appelée “end ()” renvoie une référence à “lastNode”. Enfin, en fonction de la manière dont vous implémentez votre classe, vous devrez peut-être remplacer l’opérateur de comparaison pour que cela fonctionne correctement.

Exemple:

 class MyNode{ }; class MyList{ public: MyList () : lastNode(); MyNode * next(){ if (isLastNode) return &lastNode; else return //whatever comes next } MyNode * end() { return &lastNode; } //comparison operator friend bool operator == (MyNode &n1, MyNode &n2){ return (&n1 == &n2); //check that both operands point to same memory } private: MyNode lastNode; }; int main(){ MyList list; MyNode * node = list.next(); while ( node != list.end() ){ //do stuff! node = list.next(); } return 0; }