DataStructure a più chiavi

Question

Sto cercando una struttura dati che possa cercare con più chiavi. Più facile da spiegare con un esempio:

var myDataStructure = new MultiKeyDataStructure<int, string, MyType>(); 
myDataStructure.Add(1, "some string 1", new MyType()); 
myDataStructure.Add(2, "some string 2", new MyType()); 

var myType = new MyType(); 
myDataStructure.Add(3, "some string 3", myType); 

Tuple<string, MyType> t1 = myDataStructure[1]; 
Tuple<int, MyType> t2 = myDataStructure["some string 1"]; 
Tuple<int, string> t3 = myDataStructure[myType]; 

è qualcosa di simile possibile, e se è così, c'è qualcosa che già esiste per farlo? Come implementeresti qualcosa che tratta tutto come una chiave e restituisce tutte le chiavi associate cercando qualcuno di loro?

Idealmente si sarebbe anche essere consentito di utilizzare qualsiasi numero e/o tipo di parametri:

var myDataStructure = new MultiKeyDataStructure<int, string, Foo, Bar>(); 

Answer 1

Quindi ecco uno che funzionerà esattamente per tre chiavi. È possibile seguire il modello elencato per crearne uno per 4, 5, 6, ecc. Sarebbe un sacco di codice, ma non un compito particolarmente difficile (solo noioso).

Si noti che poiché c'è un dizionario per ciascuna parte della chiave, si userà un bel po 'di memoria; questo è il prezzo che si paga per la flessibilità dell'accesso molto efficace da qualsiasi chiave.

public class MultiKeyDictionary<T1, T2, T3> 
{ 
    private Dictionary<T1, Tuple<T1, T2, T3>> firstLookup = new Dictionary<T1, Tuple<T1, T2, T3>>(); 
    private Dictionary<T2, Tuple<T1, T2, T3>> secondLookup = new Dictionary<T2, Tuple<T1, T2, T3>>(); 
    private Dictionary<T3, Tuple<T1, T2, T3>> thirdLookup = new Dictionary<T3, Tuple<T1, T2, T3>>(); 

    public void Add(Tuple<T1, T2, T3> values) 
    { 
     if (!firstLookup.ContainsKey(values.Item1) && 
      !secondLookup.ContainsKey(values.Item2) && 
      !thirdLookup.ContainsKey(values.Item3)) 
     { 
      firstLookup.Add(values.Item1, values); 
      secondLookup.Add(values.Item2, values); 
      thirdLookup.Add(values.Item3, values); 
     } 
     else 
     { 
      //throw an exeption or something. 
     } 
    } 

    public Tuple<T1, T2, T3> GetFirst(T1 key) 
    { 
     return firstLookup[key]; 
    } 

    public Tuple<T1, T2, T3> GetSecond(T2 key) 
    { 
     return secondLookup[key]; 
    } 

    public Tuple<T1, T2, T3> GetThird(T3 key) 
    { 
     return thirdLookup[key]; 
    } 

    public void RemoveFirst(T1 key) 
    { 
     var values = GetFirst(key); 

     firstLookup.Remove(values.Item1); 
     secondLookup.Remove(values.Item2); 
     thirdLookup.Remove(values.Item3); 
    } 

    public void RemoveSecond(T2 key) 
    { 
     var values = GetSecond(key); 

     firstLookup.Remove(values.Item1); 
     secondLookup.Remove(values.Item2); 
     thirdLookup.Remove(values.Item3); 
    } 

    public void RemoveThird(T3 key) 
    { 
     var values = GetThird(key); 

     firstLookup.Remove(values.Item1); 
     secondLookup.Remove(values.Item2); 
     thirdLookup.Remove(values.Item3); 
    } 
} 

Di seguito è un approccio completamente diverso. Invece di compilare una ricerca per ogni chiave, memorizza tutti i valori in una singola raccolta ed esegue una ricerca lineare per trovare un elemento per una determinata chiave. Avrà O (n) Cerca/Rimuovi ora, ma O (1) Aggiungi. L'implementazione precedente ha O (1) aggiungi, rimuovi e cerca, ma occupa molto più memoria per farlo.

public class MultiKeyDictionary2<T1, T2, T3> 
{ 
    private HashSet<Tuple<T1, T2, T3>> lookup = new HashSet<Tuple<T1, T2, T3>>(); 
    private HashSet<T1> firstKeys = new HashSet<T1>(); 
    private HashSet<T2> secondKeys = new HashSet<T2>(); 
    private HashSet<T3> thirdKeys = new HashSet<T3>(); 

    public void Add(Tuple<T1, T2, T3> values) 
    { 
     if (lookup.Any(multiKey => object.Equals(multiKey.Item1, values.Item1) || 
      object.Equals(multiKey.Item2, values.Item2) || 
      object.Equals(multiKey.Item3, values.Item3))) 
     { 
      //throw an exception or something 
     } 
     else 
     { 
      lookup.Add(values); 
     } 
    } 

    public Tuple<T1, T2, T3> GetFirst(T1 key) 
    { 
     return lookup.FirstOrDefault(values => object.Equals(values.Item1, key)); 
    } 

    public Tuple<T1, T2, T3> GetSecond(T2 key) 
    { 
     return lookup.FirstOrDefault(values => object.Equals(values.Item2, key)); 
    } 

    public Tuple<T1, T2, T3> GetThird(T3 key) 
    { 
     return lookup.FirstOrDefault(values => object.Equals(values.Item3, key)); 
    } 

    public void RemoveFirst(T1 key) 
    { 
     var values = GetFirst(key); 
     if (values != null) 
      lookup.Remove(values); 
    } 

    public void RemoveSecond(T2 key) 
    { 
     var values = GetSecond(key); 
     if (values != null) 
      lookup.Remove(values); 
    } 

    public void RemoveThird(T3 key) 
    { 
     var values = GetThird(key); 
     if (values != null) 
      lookup.Remove(values); 
    } 
} 

Answer 2

System.Tuple è stato aggiunto con l'utilizzo come chiave del dizionario tenuto a mente. Uso:

var dict = new Dictionary<Tuple<string, int>, DateTime>(); 
dict.Add(Tuple.Create("Louis", 14), new DateTime(1638, 9, 5)); 

Anche se la sintassi Tuple è ingombrante, il metodo factory statica prende gran parte del dolore sul sito di creazione.

Answer 3

La cosa più vicina che si può ottenere è probabilmente un HashSet<Tuple<int, string, MyType>>. Gli hashset controllano automaticamente i duplicati e uno Tuple controlla i valori per le equivalenze.

class MultiKey<T1, T2, T3> : HashSet<Tuple<T1, T2, T3>> 
{ 
    public bool Add(T1 t1, T2 t2, T3 t3) 
    { 
     return this.Add(Tuple.Create(t1, t2, t3)); 
    } 
    public T1 Get(T2 t2, T3 t3) 
    { 
     var match = this.SingleOrDefault(x => x.Item2.Equals(t2) && x.Item3.Equals(t3)); 
     if (match == null) return default(T1); 
     else return match.Item1; 
    } 
    public T2 Get(T1 t1, T3 t3) 
    { 
     var match = this.SingleOrDefault(x => x.Item1.Equals(t1) && x.Item3.Equals(t3)); 
     if (match == null) return default(T2); 
     else return match.Item2; 
    } 
    public T3 Get(T1 t1, T2 t2) 
    { 
     var match = this.SingleOrDefault(x => x.Item1.Equals(t1) && x.Item2.Equals(t2)); 
     if (match == null) return default(T3); 
     else return match.Item3; 
    } 
} 

Usage:

key.Add(1, "Foo", new MyType("foo")); 
key.Add(2, "Bar", new MyType("bar")); 
key.Add(2, "Bar", new MyType("bar")); // Does not add, because it already exists. 
var key1 = key.Get("Bar", new Foo("bar")); // Returns 2 
var defaultKey = key.Get("Bar", new Foo("foo")); // Returns 0, the default value for an int 
var key2 = key.Get(1, new Foo("foo")); // returns "Foo" 

È necessario fare in modo che MyType confronto per l'uguaglianza con i suoi valori, se lo si utilizza con un sacco di new s. In caso contrario, la creazione di una nuova garantirà un valore unico.

Answer 4

Quando mi imbatto in situazioni come questa, mi basta usare due Dizionari piuttosto che cercare di trovare un qualche nuova struttura dati. Ogni dizionario ha una delle possibili chiavi mappate sul valore.

Se si desidera veramente che venga estratto, è sempre possibile creare una classe che utilizza internamente due o più dizionari, a seconda di quanti tipi di chiavi sono necessari.

Answer 5

Dal momento che lei ha detto che si desidera a tempo di compilazione sicurezza di tipo, ci sono una serie di cose che si deve rinunciare:

1. La possibilità di avere un numero qualsiasi di parametri (C# non ha generici variadic)
2. la possibilità di avere più chiavi dello stesso tipo (il compilatore lamentano sovraccarichi ambigue)

Queste due limitazioni possono essere risolti utilizzando un approccio riflessione basata, ma poi si perderebbe la fase di compilazione digitare sicurezza.

Quindi questa è la soluzione si usa, in base alle proprie costrizioni (funziona solo quando tutti i tipi generici sono distinti!)

class TripleKeyDictionnary<TKey1, TKey2, TKey3> 
{ 
    public Tuple<TKey2, TKey3> this[TKey1 key] 
    { 
     get 
     { 
      return _key1Lookup[key]; 
     } 
    } 

    public Tuple<TKey1, TKey3> this[TKey2 key] 
    { 
     get 
     { 
      return _key2Lookup[key]; 
     } 
    } 

    public Tuple<TKey1, TKey2> this[TKey3 key] 
    { 
     get 
     { 
      return _key3Lookup[key]; 
     } 
    } 

    private Dictionary<TKey1, Tuple<TKey2, TKey3>> _key1Lookup = new Dictionary<TKey1, Tuple<TKey2, TKey3>>(); 
    private Dictionary<TKey2, Tuple<TKey1, TKey3>> _key2Lookup = new Dictionary<TKey2, Tuple<TKey1, TKey3>>(); 
    private Dictionary<TKey3, Tuple<TKey1, TKey2>> _key3Lookup = new Dictionary<TKey3, Tuple<TKey1, TKey2>>(); 

    public void Add(TKey1 key1, TKey2 key2, TKey3 key3) 
    { 
     _key1Lookup.Add(key1, Tuple.Create(key2, key3)); 
     _key2Lookup.Add(key2, Tuple.Create(key1, key3)); 
     _key3Lookup.Add(key3, Tuple.Create(key1, key2)); 
    } 
} 

Answer 6

Prima di tutto, purtroppo, non c'è niente di built-in, quindi è necessario implementare qualcosa a mano.

Il problema qui è che non si può avere una classe con un numero imprecisato di tipo generico definizione cioè non esiste qualcosa di simile:

class MultiKeyDictionary<T1, ...> 
{} 

Quindi, o si può decidere di implementare alcuni casi (2 tasti, 3 tasti, ecc., Utilizzando un approccio simile all'implementazione Tuple<>), oppure si dovrebbe rinunciare alla sicurezza del tipo.

Se si decide per il primo approccio, si dovrebbe poter fare qualcosa di simile (ad esempio con 3 chiavi):

class ThreeKeysDict<T1,T2,T3> 
{ 
    var dict1 = new Dictionary<T1,Tuple<T2,T3>>(); 
    var dict2 = new Dictionary<T2,Tuple<T1,T3>>(); 
    var dict3 = new Dictionary<T3,Tuple<T1,T2>>(); 
    public void Add(T1 key1,T2 key2, T3 key3) 
    { 
     dict1.Add(key1,Tuple.Create(key2,key3)); 
     dict2.Add(key2,Tuple.Create(key1,key3)); 
     dict3.Add(key3,Tuple.Create(key1,key2)); 
    } 
    public Tuple<T2,T3> GetByKey1(T1 key1) 
    { 
     return dict1[key1]; 
    } 
    public Tuple<T1,T3> GetByKey2(T2 key2) 
    { 
     return dict2[key2]; 
    } 
    public Tuple<T1,T2> GetByKey3(T3 key3) 
    { 
     return dict3[key3]; 
    } 
} 

La versione non generica sarebbe qualcosa di simile a questo:

class MultiKeyDict 
{ 
    Dictionary<object, object[]>[] indexesByKey; 
    public MultiKeyDict(int nKeys) 
    { 
     indexesByKey = new Dictionary<object, object[]>[nKeys]; 
    } 
    public void Add(params object[] values) 
    { 
     if (values.Length != indexesByKey.Length) 
      throw new ArgumentException("Wrong number of arguments given"); 
     var objects = values.ToArray(); 
     for (int i = 0; i < indexesByKey.Length; i++) 
      this.indexesByKey[i].Add(values[i], objects); 
    } 
    public object[] Get(int keyNum, object key) 
    { 
     return this.indexesByKey[keyNum][key]; 
    } 
} 

Questi due approcci utilizzano entrambi molta memoria se il numero di chiavi diverse cresce (perché adotta un dizionario per ogni chiave).

---

responsabilità:

I pezzi di codici non sono testati e la mancanza di null/out-of-range controllo ecc
Sono solo per darvi l'idea generale.

Answer 7

Non sono sicuro che esista una tale struttura dati, ma è possibile crearne una.

Supponendo/sub-chiavi chiavi saranno unico

Segue la MultiKeyDictionary (usando 2 dizionari interni, uno per le chiavi (come object), e uno per i valori).

public class MultiKeyDictionary<TValue> 
{ 
    private Dictionary<Guid, TValue> values; 
    private Dictionary<Object, Guid> keys; 

    public MultiKeyDictionary() 
    { 
     keys = new Dictionary<Object,Guid>(); 
     values = new Dictionary<Guid,TValue>(); 
    } 
    public IEnumerable<Object> Keys 
    { 
     get { return keys.Keys.AsEnumerable();} // May group according to values here 
    } 

    public IEnumerable<TValue> Values 
    { 
     get { return values.Values;} 
    } 

    public TValue this[object key] 
    { 
     get 
     { 
      if (keys.ContainsKey(key)) 
      { 
       var internalKey = keys[key]; 
       return values[internalKey]; 
      } 
      throw new KeyNotFoundException(); 
     } 
    } 


    public void Add(TValue value,object key1, params object[] keys) // key1 to force minimum 1 key 
    { 
     Add(key1 , value); 
     foreach(var key in keys) 
     { 
     Add (key, value); 
     } 
    } 

    private void Add(Object key, TValue value) 
    { 
     var internalKey = Guid.NewGuid(); 
     keys.Add(key, internalKey); 
     values.Add(internalKey, value);  
    } 
} 

Può essere utilizzato come

MultiKeyDictionary<string> dict = new MultiKeyDictionary<string>(); 
dict.Add("Hello" , 1,2,3,"StringKey"); // First item is value, remaining all are keys 
Console.WriteLine(dict[1]); // Note 1 is key and not intex 
Console.WriteLine(dict[2]); // Note 2 is key and not index 
Console.WriteLine(dict["StringKey"]); 

Answer 8

Come su

class MultiKeyLookup<A, B, C> : IEnumerable<Tuple<A, B, C>> 
{ 
    private readonly ILookup<A, Tuple<B, C>> a; 
    private readonly ILookup<B, Tuple<A, C>> b; 
    private readonly ILookup<C, Tuple<A, B>> c; 
    private readonly IEnumerable<Tuple<A, B, C>> order; 

    public MultiKeyLookup(IEnumerable<Tuple<A, B, C>> source) 
    { 
     this.order = source.ToList(); 
     this.a = this.order.ToLookup(
      o => o.Item1, 
      o => new Tuple<B, C>(o.Item2, o.Item3)); 
     this.b = this.order.ToLookup(
      o => o.Item2, 
      o => new Tuple<A, C>(o.Item1, o.Item3)); 
     this.c = this.order.ToLookup(
      o => o.Item3, 
      o => new Tuple<A, B>(o.Item1, o.Item2)); 
    } 

    public ILookup<A, Tuple<B, C>> Item1 
    { 
     get 
     { 
      return this.a 
     } 
    } 

    public ILookup<B, Tuple<A, C>> Item2 
    { 
     get 
     { 
      return this.b 
     } 
    } 

    public ILookup<C, Tuple<A, B>> Item3 
    { 
     get 
     { 
      return this.c 
     } 
    } 

    public IEnumerator<Tuple<A, B, C>> GetEnumerator() 
    { 
     this.order.GetEnumerator(); 
    } 

    public IEnumerator IEnumerable.GetEnumerator() 
    { 
     this.order.GetEnumerator(); 
    } 
} 

Quale si usa come,

var multiKeyLookup = new MultiKeyLookup(
    new[] { 
     Tuple.Create(1, "some string 1", new MyType()), 
     Tuple.Create(2, "some string 2", new MyType())}); 

var intMatches = multiKeyLookup.Item1[1]; 
var stringMatches = multiKeyLookup.Item2["some string 1"]; 
var typeMatches = multiKeyLookup.Item3[myType];