Dictionnaires à touches multiples (d'un autre type) en C# ?

Question

Construire sur cette question existe-t-il une solution simple pour avoir un dictionnaire à plusieurs clés où l'une ou l'autre des touches individuellement peut être utilisé pour identifier la valeur ?

ie.

MultikeyDictionary<TKey1, TKey2, TValue> foo;
foo.Add(key1, key2, value);
myValue = foo[key1];
// value == myValue
foo.Remove(key2);
myValue = foo[key1]; // invalid, Exception or null returned

Answer 1

Cet article de blog semble détailler une implémentation plutôt décente.

Classe de dictionnaire générique à clés multiples pour C

MultiKeyDictionary est une classe C# qui englobe et étend l'objet générique Dictionary fourni par Microsoft dans .NET 2.0 et plus. Ce site permet à un développeur de créer un dictionnaire générique générique de valeurs et de référencer la liste de valeurs par le biais de deux clés au lieu de que celle fournie par l'implémentation Microsoft de l'implémentation du Generic Dictionnaire<...>. Vous pouvez voir mon article sur CodeProject (ici), cependant ce code est plus à jour et sans bogue. sans bogue.

Answer 2

Oui, définissez une classe qui ajoute l'objet à une table de hachage interne avec les deux clés,

 public MyClass<k1, k2, T>: Dictionary<object, T>
  {
      private Dictionary<k1, k2> keyMap;
      public new Add(k1 key1Val, k2 key2Val, T object)
      {
         keyMap.Add(key1Val, key2Val);
         base.Add(k2, object)
      }
      public Remove(k1 key1Val) 
      { 
          base.Remove(keyMap[key1Val]); 
          keyMap.Remove(key1Val);
      }
      public Remove(k2 key2Val) 
      { 
        base.Remove(key2Val);
        keyMap.Remove(key2Val);
      }
  }

Answer 3

Pour l'instant, rien n'est intégré dans la BCL .NET pour ce type de collecte.

Je vois deux options :

1. Utilisez un dictionnaire à deux niveaux. Le premier niveau fait correspondre différentes clés à une clé unique commune (disons un GUID), et le second niveau fait correspondre le GUID à la valeur réelle.

2. Créez une classe de clé personnalisée et implémentez Equals() et GetHashCode() de manière à ce que n'importe quel composant de la clé suffise à trouver la clé entière. Vous pourriez ensuite fournir des méthodes d'aide pour construire des instances de la clé en utilisant une seule des valeurs afin de pouvoir effectuer des recherches.

Answer 4

Une autre mise en œuvre simple (et efficace) serait d'utiliser PowerCollections ' Pair<TFirst, TSecond> comme une clé de dictionnaire, quelque chose comme

Dictionary<Pair<TKey1, TKey2>, TValue> foo;
foo.Add(new Pair<TKey1, TKey2>(key1, key2), value);

Paire<> implémente Equals y GetHashCode de manière cohérente, de sorte que vous n'avez pas besoin de recourir à des dictionnaires à plusieurs niveaux (qui sont plus lourds et probablement moins efficaces).

Il y a aussi un Triple<TFirst, TSecond, TThird> si vous avez besoin d'un dictionnaire à 3 touches.

Answer 5

Je trouve de nombreuses réponses inutilement complexes, moins performantes ou tout simplement inutilisables. La meilleure approche serait d'avoir un KeyValuePair<> de la clé secondaire et de la valeur regroupée en tant que Value de l'un ou l'autre des dictionnaires. Cela vous permet de n'avoir qu'une seule recherche pour les opérations de suppression et de mise à jour. Une implémentation simple :

public class DualDictionary<TKey1, TKey2, TValue> : IEnumerable<KeyValuePair<Tuple<TKey1, TKey2>, TValue>>
{
    Dictionary<TKey1, KeyValuePair<TKey2, TValue>> _firstKeys;
    Dictionary<TKey2, KeyValuePair<TKey1, TValue>> _secondKeys;

    public int Count
    {
        get
        {
            if (_firstKeys.Count != _secondKeys.Count)
                throw new Exception("somewhere logic went wrong and your data got corrupt");

            return _firstKeys.Count;
        }
    }

    public ICollection<TKey1> Key1s
    {
        get { return _firstKeys.Keys; }
    }

    public ICollection<TKey2> Key2s
    {
        get { return _secondKeys.Keys; }
    }

    public IEnumerable<TValue> Values
    {
        get { return this.Select(kvp => kvp.Value); }
    }

    public DualDictionary(IEqualityComparer<TKey1> comparer1 = null, IEqualityComparer<TKey2> comparer2 = null)
    {
        _firstKeys = new Dictionary<TKey1, KeyValuePair<TKey2, TValue>>(comparer1);
        _secondKeys = new Dictionary<TKey2, KeyValuePair<TKey1, TValue>>(comparer2);
    }

    public bool ContainsKey1(TKey1 key)
    {
        return ContainsKey(key, _firstKeys);
    }

    private static bool ContainsKey<S, T>(S key, Dictionary<S, KeyValuePair<T, TValue>> dict)
    {
        return dict.ContainsKey(key);
    }

    public bool ContainsKey2(TKey2 key)
    {
        return ContainsKey(key, _secondKeys);
    }

    public TValue GetValueByKey1(TKey1 key)
    {
        return GetValueByKey(key, _firstKeys);
    }

    private static TValue GetValueByKey<S, T>(S key, Dictionary<S, KeyValuePair<T, TValue>> dict)
    {
        return dict[key].Value;
    }

    public TValue GetValueByKey2(TKey2 key)
    {
        return GetValueByKey(key, _secondKeys);
    }

    public bool TryGetValueByKey1(TKey1 key, out TValue value)
    {
        return TryGetValueByKey(key, _firstKeys, out value);
    }

    private static bool TryGetValueByKey<S, T>(S key, Dictionary<S, KeyValuePair<T, TValue>> dict, out TValue value)
    {
        KeyValuePair<T, TValue> otherPairing;
        bool b = TryGetValue(key, dict, out otherPairing);
        value = otherPairing.Value;
        return b;
    }

    private static bool TryGetValue<S, T>(S key, Dictionary<S, KeyValuePair<T, TValue>> dict,
                                          out KeyValuePair<T, TValue> otherPairing)
    {
        return dict.TryGetValue(key, out otherPairing);
    }

    public bool TryGetValueByKey2(TKey2 key, out TValue value)
    {
        return TryGetValueByKey(key, _secondKeys, out value);
    }

    public bool Add(TKey1 key1, TKey2 key2, TValue value)
    {
        if (ContainsKey1(key1) || ContainsKey2(key2))   // very important
            return false;

        AddOrUpdate(key1, key2, value);
        return true;
    }

    // dont make this public; a dangerous method used cautiously in this class
    private void AddOrUpdate(TKey1 key1, TKey2 key2, TValue value)
    {
        _firstKeys[key1] = new KeyValuePair<TKey2, TValue>(key2, value);
        _secondKeys[key2] = new KeyValuePair<TKey1, TValue>(key1, value);
    }

    public bool UpdateKey1(TKey1 oldKey, TKey1 newKey)
    {
        return UpdateKey(oldKey, _firstKeys, newKey, (key1, key2, value) => AddOrUpdate(key1, key2, value));
    }

    private static bool UpdateKey<S, T>(S oldKey, Dictionary<S, KeyValuePair<T, TValue>> dict, S newKey,
                                        Action<S, T, TValue> updater)
    {
        KeyValuePair<T, TValue> otherPairing;
        if (!TryGetValue(oldKey, dict, out otherPairing) || ContainsKey(newKey, dict))
            return false;

        Remove(oldKey, dict);
        updater(newKey, otherPairing.Key, otherPairing.Value);
        return true;
    }

    public bool UpdateKey2(TKey2 oldKey, TKey2 newKey)
    {
        return UpdateKey(oldKey, _secondKeys, newKey, (key1, key2, value) => AddOrUpdate(key2, key1, value));
    }

    public bool UpdateByKey1(TKey1 key, TValue value)
    {
        return UpdateByKey(key, _firstKeys, (key1, key2) => AddOrUpdate(key1, key2, value));
    }

    private static bool UpdateByKey<S, T>(S key, Dictionary<S, KeyValuePair<T, TValue>> dict, Action<S, T> updater)
    {
        KeyValuePair<T, TValue> otherPairing;
        if (!TryGetValue(key, dict, out otherPairing))
            return false;

        updater(key, otherPairing.Key);
        return true;
    }

    public bool UpdateByKey2(TKey2 key, TValue value)
    {
        return UpdateByKey(key, _secondKeys, (key1, key2) => AddOrUpdate(key2, key1, value));
    }

    public bool RemoveByKey1(TKey1 key)
    {
        return RemoveByKey(key, _firstKeys, _secondKeys);
    }

    private static bool RemoveByKey<S, T>(S key, Dictionary<S, KeyValuePair<T, TValue>> keyDict,
                                          Dictionary<T, KeyValuePair<S, TValue>> valueDict)
    {
        KeyValuePair<T, TValue> otherPairing;
        if (!TryGetValue(key, keyDict, out otherPairing))
            return false;

        if (!Remove(key, keyDict) || !Remove(otherPairing.Key, valueDict))
            throw new Exception("somewhere logic went wrong and your data got corrupt");

        return true;
    }

    private static bool Remove<S, T>(S key, Dictionary<S, KeyValuePair<T, TValue>> dict)
    {
        return dict.Remove(key);
    }

    public bool RemoveByKey2(TKey2 key)
    {
        return RemoveByKey(key, _secondKeys, _firstKeys);
    }

    public void Clear()
    {
        _firstKeys.Clear();
        _secondKeys.Clear();
    }

    public IEnumerator<KeyValuePair<Tuple<TKey1, TKey2>, TValue>> GetEnumerator()
    {
        if (_firstKeys.Count != _secondKeys.Count)
            throw new Exception("somewhere logic went wrong and your data got corrupt");

        return _firstKeys.Select(kvp => new KeyValuePair<Tuple<TKey1, TKey2>, TValue>(Tuple.Create(kvp.Key, kvp.Value.Key),
                                                                                      kvp.Value.Value)).GetEnumerator();
    }

    IEnumerator IEnumerable.GetEnumerator()
    {
        return GetEnumerator();
    }
}

Quelques points à noter :

1. Je n'ai mis en œuvre que IEnumerable<> . Je ne pense pas que ICollection<> a du sens ici puisque les noms des méthodes pourraient tous être très différents pour cette structure de collection spéciale. C'est à vous de décider ce qui doit aller à l'intérieur IEnumerable<> .

2. J'ai essayé de faire en sorte que certaines exceptions bizarres soient lancées ici et là - juste pour l'intégrité des données. Juste pour être plus sûr et pour que vous sachiez si jamais mon code a des bogues.

3. J'ai nommé les méthodes de manière à ce qu'elles puissent être compilées même si elles ne le sont pas. Key1 y Key2 sont du même type.

4. Performance : Vous pouvez rechercher Value avec l'un ou l'autre des Key s. Get y Contains ne nécessitent qu'une seule consultation (O(1)). Add nécessite 2 recherches et 2 ajouts. Update nécessite 1 recherche et 2 ajouts. Remove nécessite 3 recherches.