Je n'ai pas réussi à trouver beaucoup d'informations à leur sujet en ligne. Qu'est-ce qu'ils sont et quand sont-ils généralement utilisés ?
Merci.
Je n'ai pas réussi à trouver beaucoup d'informations à leur sujet en ligne. Qu'est-ce qu'ils sont et quand sont-ils généralement utilisés ?
Merci.
Une liste intrusive est une liste où le pointeur vers le nœud de liste suivant est stocké dans la même structure que les données du nœud. C'est normalement une mauvaise chose, car cela lie les données à l'implémentation spécifique de la liste. La plupart des bibliothèques de classes (par exemple, la bibliothèque standard C++) utilisent des listes non intrusives, où les données ne savent rien de l'implémentation de la liste (ou d'un autre conteneur).
En fait, j'aime bien le modèle intrusif.
multi_index_container
mais notez que multi_index_container
présente certaines lacunes qui ne sont pas des problèmes avec les conteneurs intrusifs.Intrusif est BON
...il suffit de savoir ce que l'on fait (ce qui est vrai pour tout conteneur).
Il est surprenant que tant de personnes se trompent complètement (comme la réponse de Ziezi). Les gens semblent compliquer les choses à l'excès alors que c'est vraiment très simple.
Dans une liste chaînée intrusive, il n'y a pas de structure/classe 'Node' explicite. Au lieu de cela, la structure/classe 'Data' elle-même contient un pointeur/référence next et prev vers d'autres Data dans la liste liée.
Par exemple (nœud de liste lié intrusif) :
struct Data {
Data *next;
Data *prev;
int fieldA;
char * fieldB;
float fieldC;
}
Remarquez comment les pointeurs next et prev se trouvent à côté de et s'immiscer sur les champs de données privés de l'entité, comme le champA. Cela "viole" la séparation des préoccupations imposée par les listes liées standard (voir ci-dessous), mais présente l'avantage de réduire considérablement le nombre de déplacements dans la liste pour localiser des nœuds spécifiques et de diminuer les allocations de mémoire.
Dans une liste liée intrusive, la "liste liée" elle-même est souvent virtuelle, il n'est normalement pas nécessaire de créer une structure/classe de liste liée.
Au lieu de cela, vous pouvez simplement stocker un pointeur de tête vers le premier élément de données dans un propriétaire/gestionnaire. Ce gestionnaire contient également des fonctions d'ajout/suppression pour mettre à jour les pointeurs si nécessaire. Pour plus d'informations, voir https://gameprogrammingpatterns.com/spatial-partition.html
Le fait d'avoir une seule paire de pointeurs next/prev implique que chaque objet ne peut appartenir qu'à une seule liste. Cependant, vous pouvez bien sûr ajouter plusieurs paires de pointeurs next/prev si nécessaire (ou définir un tableau de pointeurs next/prev) pour prendre en charge des objets dans plusieurs listes.
Dans une liste chaînée non intrusive (c'est-à-dire standard), les pointeurs next/prev font partie d'une entité "nœud" dédiée et l'entité Data réelle est simplement un champ dans ce nœud.
Par exemple (nœud de liste liée et données non intrusives) :
struct Data {
int fieldA;
char * fieldB;
float fieldC;
}
struct Node {
Node *next;
Node *prev;
Data *data;
}
Remarquez comment les pointeurs next/prev ne pas s'immiscer sur l'entité Data réelle et la séparation des préoccupations est maintenue.
Mise à jour :
Vous pouvez voir d'autres sites tels que https://www.data-structures-in-practice.com/intrusive-linked-lists/ utiliser une structure 'List' (en fait un Node) qui contient des pointeurs next/prev et qui est le seul champ intrusif dans la structure/classe 'Data'.
Cela permet de cacher les pointeurs next/prev des données, mais il est nécessaire d'effectuer une arithmétique de pointeurs simplement pour accéder aux données réelles associées à la liste (nœud).
Cette approche ajoute une complexité inutile à mon avis (par rapport à l'intégration directe des champs suivant/précédent) dans le seul but douteux de cacher les pointeurs suivant/précédent. Si vous avez besoin de listes intrusives, gardez-les aussi simples que possible. (De plus, dans les langages à mémoire gérée, il est difficile ou impossible de faire de l'arithmétique de pointeurs de toute façon).
Les listes intrusives sont des listes où les objets sont eux-mêmes des têtes ou des cellules de listes. Elles sont bonnes ou mauvaises selon le contexte.
À l'intérieur d'un module défini (groupe insécable de classes travaillant ensemble), il peut s'agir du meilleur moyen de lier les relations entre les classes. Ils permettent une gestion directe et complète des relations communes comme l'unicité (ex : pommes n'apparaît pas deux fois dans les arbres de pommes, et cela ne nécessite pas de clé pour cela, et pommes n'appartient pas à deux arbres distincts), ils sont navigables dans les deux sens (accès direct à l'arbre de pommes étant donné une pomme et à pommes étant donné un arbre de pommes). Toutes les opérations de base sont O(1) (pas de recherche dans un conteneur externe).
Les listes intrusives sont TRÈS MAUVAISES entre deux modules. Parce qu'ils seront liés ensemble, et la justification des modules est la gestion de l'indépendance du code.
Voici une brève description qui est également valable pour les listes :
L'objet à stocker contient des informations supplémentaires pour permettre l'intégration dans le conteneur. Exemple :
struct Node { Node\* next; // additional Node\* prev; // information T data; }
1. Pour :
stocke les objets eux-mêmes.
n'implique pas de gestion de la mémoire.
l'itération est plus rapide.
de meilleures garanties d'exception.
la prévisibilité dans l'insertion et la suppression d'objets. (aucune gestion supplémentaire de la mémoire (non prévisible) n'est nécessaire).
une meilleure localisation de la mémoire.
2. Cons :
- contient des données supplémentaires pour l'intégration des conteneurs. (chaque type de magasin doit être adapté (modifié) aux exigences du conteneur).
- attention aux effets secondaires possibles lors de la modification du contenu de l'objet stocké (surtout pour les conteneurs associatifs).
- gestion de la durée de vie de l'objet inséré, indépendamment du conteneur.
- peut être éventuellement éliminé avant d'être effacé du conteneur, ce qui entraîne l'invalidation de l'itérateur.
- les conteneurs intrusifs sont NON-copiables et NON-assignables.
L'objet ne "sait" pas et ne contient pas de détails sur le conteneur dans lequel il doit être stocké. Exemple :
struct Node { T data; }
1. Pour :
- ne contient pas d'informations supplémentaires concernant l'intégration du conteneur.
- la durée de vie de l'objet gérée par le conteneur. (moins complexe).
2. Cons :
- stocker des copies des valeurs transmises par l'utilisateur. (construction in situ possible).
- un objet ne peut appartenir qu'à un seul conteneur. (ou le conteneur doit stocker des pointeurs vers des objets).
- les frais généraux liés au stockage des copies. (comptabilité sur chaque allocation).
les objets non copiables ou non déplaçables ne peuvent pas être stockés dans des conteneurs non intrusifs.- ne peut pas stocker un objet dérivé et conserver son type original. (découpage en tranches - perte du polymorphisme).
Prograide est une communauté de développeurs qui cherche à élargir la connaissance de la programmation au-delà de l'anglais.
Pour cela nous avons les plus grands doutes résolus en français et vous pouvez aussi poser vos propres questions ou résoudre celles des autres.