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.
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 une tableau associatif spĂ©cialisĂ©e, 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 une 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[1].
- Python : certains intégrés, d'autres implémentés dans la bibliothÚque des collections.
Références
- (en) Steven Feuerstein, Bill Pribyl et Chip Dawes, « Oracle PL/SQL Language Pocket Reference », Pocket Reference, Sebastopol, California, O'Reilly Media, Inc. « Collections in PL/SQL »,â (ISBN 978-0-5965-5161-2, lire en ligne, consultĂ© le ) :
« Les collections sont implémentées en tant que TYPE. Comme pour tout type défini par le programmeur, vous devez d'abord définir le type, puis vous pouvez déclarer des instances de ce type. »
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).