Abstraction des valeurs triées en tant que clé-valeur

Question

J'écris une interface pour une collection d'objets triés. Comme d'habitude, je laisse à l'utilisateur le soin de spécifier comment ces objets sont triés. Cependant, je suis actuellement partagé entre une interface clé-valeur (où la clé de tri est explicitement séparée de la valeur) et une interface valeur uniquement (où la valeur est également la clé de tri, ou l'utilisateur doit gérer une clé de tri séparée en passant une fonction de comparaison).

À mon avis, une interface clé-valeur oblige l'utilisateur à toujours disposer d'une clé distincte de la valeur, même lorsqu'une valeur forme naturellement sa propre clé. Cependant, elle retire à l'utilisateur la responsabilité de la gestion de la clé, ce qui peut conduire à un code utilisateur plus simple et plus propre lors de l'utilisation de mon API. Une interface basée uniquement sur les valeurs permet une représentation plus compacte des valeurs qui sont leur propre clé, mais oblige l'utilisateur à suivre et à gérer ses propres clés dans les cas où il existe une distinction naturelle entre clé et valeur.

Il existe bien sûr des documents qui soutiennent les deux approches, même s'il me semble (je peux me tromper) que les documents plus anciens tendent à préférer une approche basée sur les valeurs uniquement, tandis que les documents plus récents préfèrent une approche basée sur les clés et les valeurs.

Je suis curieux de connaître vos préférences dans des cas comme celui-ci. Sommes-nous parvenus à un stade où l'une est généralement préférée à l'autre ? Si ce n'est pas le cas, qu'utilisez-vous habituellement et pourquoi ?

Answer 1

Vous semblez tiraillé entre ce que l'on appelle (dans différentes langues, avec différentes distinctions, mais essentiellement...)

• Un dictionnaire (une table de hachage ou un hachage)
• Une liste / un tableau

Ces deux types de conteneurs ont des objectifs différents, même si, avec quelques ajustements, il n'y a pas grand-chose qu'une liste puisse faire qu'un dictionnaire ne puisse pas faire. C'est tout simplement parce que le dictionnaire contient plus d'informations.

En général il est mieux vaut être explicite qu'implicite .
Si je vous remets un "2 dollars blue crayon" (une liste), vous en déduirez qu'il s'agit d'un objet ayant les propriétés suivantes : {Price = 2$, Color = blue, Type = Crayon} (Dictionnaire). Cependant, une telle analyse (lorsqu'elle est nécessaire) nécessite à la fois des efforts et une connaissance du domaine ou de la structure implicite des données ; l'approche par dictionnaire permet de traiter l'information de manière générique.

Dans certains cas, les listes sont "meilleures", mais cela est souvent lié à des considérations techniques ou opérationnelles, plutôt qu'à une propriété intrinsèque de l'approche par liste. Par exemple, pour mettre en œuvre des index de recherche avec un simple moteur de texte intégral, il peut être nécessaire de rassembler toutes les propriétés (cela reflète la façon dont l'utilisateur final tape des mots-clés non étiquetés, s'attendant à les trouver dans n'importe quelle propriété).

A recommandation pratique La réponse à la question est d'offrir :

• Une API qui expose l'utilisation et le comportement des listes et des dictionnaires.
• Une implémentation optimisée (en taille et/ou en espace, selon l'endroit où cela importe) qui préserve une partie de l'approche de la liste en termes de performances, au moins jusqu'à ce que le conteneur soit utilisé en tant que dictionnaire.

Sauf si a priori une préoccupation évidente concernant les performances (par exemple : les conteneurs recevront des dizaines de milliers d'éléments, il y aura des milliers d'instances de conteneurs, les conteneurs transiteront par un canal lent, etc. se concentrer d'abord sur l'API Je n'ai pas eu de problème avec l'implémentation, par exemple en la basant sur un dictionnaire. Par la suite, si cela s'avère nécessaire, la mise en œuvre peut être révisée, par exemple avec les deux listes et un schéma de carte.

Une dernière chose : il existe de nombreuses bibliothèques (ou même des constructions linguistiques) qui offrent ce type de conteneurs polymorphes Il est possible de voir s'il en existe un pour votre système/langue cible...

Answer 2

Cela semble répondre à vos besoins. Si aucun secteur clé n'est spécifié, la collection suppose que l'ordre est défini sur les éléments eux-mêmes - ils devraient probablement implémenter IComparable. Dans le cas contraire, si vous avez des éléments qui peuvent théoriquement être comparés de plusieurs façons, vous pouvez spécifier un sélecteur de clé qui renverra une projection d'un élément qui est lui-même IComparable.

Par exemple, si vous avez une classe Personne avec un Nom et un Âge, et que vous souhaitez conserver une liste triée par âge, vous créez la collection de la manière suivante :

new OrderedCollection(person => person.Age) ;

BTW : Jetez un coup d'œil aux collections SortedDictionary et SortedList qui sont fournies avec .Net. Elles pourraient s'avérer utiles.

Answer 3

Tout ce qu'une liste peut faire, un dictionnaire peut le faire, si l'on crée une structure ou un objet enveloppant pour clé+valeur, et si l'on laisse simplement la partie valeur vide. La seule chose qu'un dictionnaire ne peut pas vraiment faire est d'ajouter une valeur d'un type particulier et de répondre directement à une requête GetEnumerator avec un énumérateur qui renvoie ce type. Il serait cependant facile de construire une classe enveloppante autour d'un dictionnaire pour faire cela.

Une différence majeure entre un dictionnaire et une liste réside toutefois dans la manière dont ils traitent les enregistrements dont la partie "Clé" est identique mais pas la partie "Valeur". Bien que je ne sois pas un grand fan de la façon dont le dictionnaire gère les choses (la propriété indexée par défaut utilise la sémantique "replace", tandis que la méthode d'ajout utilise la sémantique "fail-if-exists" ; ma préférence aurait été d'avoir un paramètre de mode pour "add"), il permet de modifier la valeur associée à une clé particulière. Une "liste" ne peut essayer de le faire qu'en supprimant l'ancienne valeur et en en ajoutant une nouvelle, une opération qui peut poser des problèmes sémantiques.