Collection (type de données)

En programmation informatique, une collection est un regroupement d'un nombre variable d'éléments de données (éventuellement zéro) qui ont une signification commune pour le problème à résoudre et qui doivent être traités ensemble d'une manière contrôlée. En général, les éléments de données sont du même type ou, dans les langages supportant l'héritage, dérivés d'un type ancêtre commun. Une collection est un concept applicable aux types de données abstraits, et ne prescrit pas une implémentation spécifique en tant que structure de données concrète, bien qu'il y ait souvent un choix conventionnel (voir Conteneur pour une discussion sur la théorie des types).

Les listes, les ensembles, les multiensembles, les arbres et les graphes sont des exemples de collections.

Les matrices (ou tables) de taille fixe ne sont généralement pas considérées comme des collections car elles contiennent un nombre fixe d'éléments de données, bien qu'elles jouent souvent un rôle dans la mise en œuvre des collections. Les matrices de taille variable sont généralement considérées comme des collections.^{[citation nécessaire]}

Collections linéaires

De nombreuses collections définissent un ordre linéaire particulier, avec un accès à l'une ou aux deux extrémités. La structure de données réelle qui met en œuvre une telle collection ne doit pas nécessairement être linéaire - par exemple, une file de priorité est souvent mise en œuvre comme un tas, qui est une sorte d'arbre. Parmi les collections linéaires importantes, citons

• les listes ;
• les piles ;
• les files ;
• les files de priorité ;
• les files d'attente à double extrémité ;
• les files de priorité à deux extrémités.

Les listes

Dans une liste, l'ordre des éléments de données est important. Les doublons d'éléments de données sont autorisés. Des exemples d'opérations sur des listes sont la recherche d'un élément de données dans la liste et la détermination de son emplacement (s'il est présent), la suppression d'un élément de données de la liste, l'ajout d'un élément de données à la liste à un emplacement spécifique, etc. Si les principales opérations sur la liste sont l'ajout d'éléments de données à une extrémité et le retrait d'éléments de données à l'autre, elle sera généralement appelée file ou FIFO. Si les principales opérations sont l'ajout et le retrait d'éléments de données à une seule extrémité, on parle de pile ou de LIFO. Dans les deux cas, les éléments de données sont maintenus dans la collection dans le même ordre (à moins qu'ils ne soient retirés et réinsérés ailleurs) et ce sont donc des cas particuliers de la collection de listes. D'autres opérations spécialisées sur les listes incluent le tri où, encore une fois, l'ordre des éléments de données est d'une grande importance.

Les piles

Une pile est une structure de données LIFO comportant deux opérations principales : push, qui ajoute un élément au "sommet" de la collection, et pop, qui retire l'élément supérieur.

Les files de priorité

Dans une file de priorité, les traces de l'élément de données minimum ou maximum de la collection sont conservées selon un certain critère d'ordre, et l'ordre des autres éléments de données n'a pas d'importance. On peut imaginer une file de priorité comme une liste qui garde toujours le minimum ou le maximum en tête, tandis que les autres éléments sont conservés dans un sac.

Les collections associatives

D'autres collections peuvent être interprétées comme une sorte de fonction : étant donné une entrée, la collection produit une sortie. Les collections associatives importantes incluent :

• les ensembles ;
• les multiensembles ;
• les tableaux associatifs.

Un ensemble peut être interprété comme un multiensemble spécialisé, qui à son tour est un tableau associatif spécialisé, dans chaque cas en limitant les valeurs possibles - en considérant un ensemble comme représenté par sa fonction caractéristique.

Les ensembles

Dans un ensemble, l'ordre des éléments de données n'a pas d'importance (ou est indéfini) mais les éléments de données en double ne sont pas autorisés. Des exemples d'opérations sur les ensembles sont l'ajout et la suppression d'éléments de données et la recherche d'un élément de données dans l'ensemble. Certains langages prennent directement en charge les ensembles. Dans d'autres, les ensembles peuvent être implémentés par une table de hachage avec des valeurs fictives ; seules les clés sont utilisées pour représenter l'ensemble.

Les multiensembles

Dans un multiensemble (ou sac), comme dans un ensemble, l'ordre des éléments de données n'a pas d'importance, mais dans ce cas, les éléments de données en double sont autorisés. Des exemples d'opérations sur les multiensembles sont l'ajout et la suppression d'éléments de données et la détermination du nombre de doublons d'un élément de données particulier présents dans le multiensemble. Les multiensembles peuvent être transformés en listes par une action de tri.

Les tableaux associatifs

Dans un tableau associatif (ou carte, dictionnaire, table de consultation), comme dans un dictionnaire, une consultation sur une clé (comme un mot) fournit une valeur (comme une définition). La valeur peut être une référence à une structure composée de données. Une table de hachage est généralement une mise en œuvre efficace, et ce type de données est donc souvent appelé "hachage".

Les graphes

Dans un graphe, les éléments de données ont des associations avec un ou plusieurs autres éléments de données dans la collection et sont un peu comme des arbres sans le concept de racine ou de relation parent-enfant, de sorte que tous les éléments de données sont des pairs. Les exemples d'opérations sur les graphes sont les traversées et les recherches qui explorent les associations d'éléments de données à la recherche d'une propriété spécifique. Les graphes sont fréquemment utilisés pour modéliser des situations du monde réel et pour résoudre des problèmes connexes. Un exemple est le Spanning Tree Protocol, qui crée une représentation graphe (ou maillée) d'un réseau de données et détermine quelles associations entre les nœuds de commutation doivent être rompues pour transformer le réseau en arbre et empêcher ainsi les données de tourner en boucle.

Les arbres

Dans un arbre, qui est un type particulier de graphe, un élément de données racine est associé à un certain nombre d'éléments de données qui, à leur tour, sont associés à un certain nombre d'autres éléments de données dans ce qui est fréquemment considéré comme une relation parent-enfant. Chaque élément de données (autre que la racine) a un seul parent (la racine n'a pas de parent) et un certain nombre d'enfants, éventuellement zéro. Des exemples d'opérations sur les arbres sont l'ajout d'éléments de données de manière à maintenir une propriété spécifique de l'arbre pour effectuer un tri, etc. et des traversées pour visiter des éléments de données dans une séquence spécifique.

Les collections d'arbres peuvent être utilisées pour stocker naturellement des données hiérarchiques, qui sont présentées sous forme d'arbre, comme les systèmes de menus et les fichiers dans les répertoires d'un système de stockage de données.

Des arbres spécialisés sont utilisés dans divers algorithmes. Par exemple, le tri par tas utilise un type d'arbre appelé tas.

Concept abstrait et implémentation

Comme décrit ici, une collection et les différents types de collections sont des concepts abstraits. Il existe dans la littérature une confusion considérable entre les concepts abstraits de l'informatique et leurs implémentations spécifiques dans divers langages ou types de langages. Les affirmations selon lesquelles les collections comme les listes, les ensembles, les arbres, etc. sont des structures de données, des types de données abstraits ou des classes doivent être lues en gardant cela à l'esprit. Les collections sont avant tout des abstractions utiles pour formuler des solutions à des problèmes informatiques. Vues sous cet angle, elles conservent des liens importants avec les concepts mathématiques sous-jacents qui peuvent être perdus lorsque l'accent est mis sur l'implémentation.

Par exemple, une file de priorité est souvent mise en œuvre comme un tas, tandis qu'un tableau associatif est souvent mis en œuvre comme une table de hachage, de sorte que ces types abstraits sont souvent désignés par cette mise en œuvre préférée, comme un "tas" ou un "hachage", bien que ce ne soit pas strictement correct.

Implémentations

Certaines collections peuvent être des types de données primitifs dans un langage, comme les listes, tandis que des collections plus complexes sont implémentées comme des types de données composites dans des bibliothèques, parfois dans la bibliothèque standard. En voici quelques exemples :

• C++ : connus sous le nom de "conteneurs", mis en œuvre dans la bibliothèque standard C++ et la Standard Template Library.
• Java : implémentés dans le cadre des collections Java.
• Oracle PL/SQL implémente les collections comme des types définis par le programmeur.
• Python : certains intégrés, d'autres implémentés dans la bibliothèque des collections.

Liens externes

• Apache Commons Collections (en)
• AS3Commons Collections Framework (en) Implémentation ActionScript3 des collections les plus courantes
• CollectionSpy (en) — Un profileur pour le cadre des collections de Java
• Guava (en)
• Mango Java library (en).