Conteneur (type de données abstrait)

En informatique , un conteneur est une classe ou une structure de données dont les instances sont des collections d'autres objets. En d'autres termes, ils stockent des objets de manière organisée qui suit des règles d'accès spécifiques.

La taille du conteneur dépend du nombre d'objets (éléments) qu'il contient. Les implémentations sous-jacentes (héritées) de divers types de conteneurs peuvent varier en taille, en complexité et en type de langage, mais dans de nombreux cas, elles offrent une certaine flexibilité dans le choix de l'implémentation adaptée à un scénario donné.

Les structures de données de conteneur sont couramment utilisées dans de nombreux types de langages de programmation .

Les conteneurs peuvent être caractérisés par les trois propriétés suivantes :

• accès , c'est-à-dire la manière d'accéder aux objets du conteneur. Dans le cas des tableaux, l'accès se fait avec l'index du tableau. Dans le cas des piles, l'accès se fait selon l' ordre LIFO (dernier entré, premier sorti) et dans le cas des files d'attente, il se fait selon l' ordre FIFO (premier entré, premier sorti) ;
• stockage , c'est-à-dire la manière de stocker les objets du conteneur ;
• traversal , c'est la manière de parcourir les objets du conteneur.

Les classes conteneurs sont censées implémenter des méthodes de type CRUD pour effectuer les opérations suivantes :

• créer un conteneur vide (constructeur) ;
• insérer des objets dans le conteneur ;
• supprimer les objets du conteneur ;
• supprimer tous les objets dans le conteneur (effacer) ;
• accéder aux objets dans le conteneur ;
• accéder au nombre d'objets dans le conteneur (count).

Les conteneurs sont parfois implémentés en conjonction avec des itérateurs .

Les conteneurs peuvent être classés comme conteneurs à valeur unique ou conteneurs associatifs .

Les conteneurs à valeur unique stockent chaque objet indépendamment. Les objets peuvent être consultés directement, par une construction de boucle de langage (par exemple une boucle for ) ou avec un itérateur .

Un conteneur associatif utilise un tableau associatif , une carte ou un dictionnaire, composé de paires clé-valeur, de telle sorte que chaque clé apparaisse au plus une fois dans le conteneur. La clé est utilisée pour trouver la valeur, l'objet, s'il est stocké dans le conteneur. Les conteneurs associatifs sont utilisés dans les langages de programmation comme modèles de classe.

Les types de données abstraits du conteneur incluent :

• Files d'attente FIFO
• Piles LIFO
• Files d'attente prioritaires
• Tables de recherche (LUT)
• Structures de données associées aux clés
  • Ensembles , contenant et indexant des objets par valeur ou par propriété spécifique ;
  • Cartes , associant à chaque clé une « valeur » pour la recherche

Les structures de données courantes utilisées pour implémenter ces types abstraits incluent :

• Les tableaux et leurs dérivés
• Listes chaînées
• Arbres de recherche binaires (BST), en particulier les BST auto-équilibrés
• Tables de hachage

Les boîtes à outils de widgets utilisent également des conteneurs, qui sont des widgets spéciaux pour regrouper d'autres widgets, tels que des fenêtres , des panneaux . Outre leurs propriétés graphiques, ils ont le même type de comportement que les classes de conteneurs, car ils conservent une liste de leurs widgets enfants et permettent d'ajouter, de supprimer ou de récupérer des widgets parmi leurs enfants.

Les abstractions de conteneurs peuvent être écrites dans pratiquement n'importe quel langage de programmation, quel que soit son système de types. Cependant, dans les langages de programmation orientés objet fortement typés , il peut être quelque peu compliqué pour un développeur d'écrire des conteneurs homogènes réutilisables.

En raison des différences entre les types d'éléments, cela entraîne un processus fastidieux d'écriture et de conservation d'une collection de conteneurs pour chaque type d'élément.

De nombreux types élémentaires (par exemple les entiers ou les nombres flottants) sont intrinsèquement incompatibles les uns avec les autres en raison de la taille de la mémoire qu'ils occupent et de leur signification sémantique et nécessitent donc des conteneurs différents (à moins bien sûr qu'ils ne soient mutuellement compatibles ou convertibles). Les langages de programmation modernes proposent diverses approches pour aider à résoudre le problème :

Type de base universel

Un type qui est universellement assignable par n'importe quel autre (par exemple, la classe d'objet racine).

Déprimé ;

Remplacement de classe

Les trois approches précédentes sont utilisées pour les langages faiblement typés ; elles impliquent généralement l’héritage et le polymorphisme partagés par les types.

Types d'union (langage C/C++)

Permet de stocker des types de données de tailles différentes ; il est cependant difficile de garantir quel type est stocké dans une union lors de la récupération et doit être suivi attentivement.

Conversion de type

Modèles ou génériques

Assure la réutilisabilité et la sécurité des types ; peut être considéré comme un héritage inversé. Cependant, cette approche peut nécessiter la mise en œuvre d'une spécialisation de modèle , ce qui est réputé être un processus chronophage étant donné que les types diffèrent dans leurs méthodes.