Dictionary and KeyValuePair

Question

i have a problem with Dictionary, hope you'll help me.

I have the following declaration:

class MainCollection<TKey1, TKey2, TValue> : Dictionary<KeyValuePair<TKey1, TKey2>, TValue>

The problem is that i cant get an element from this dictionary by TKey1 OR TKey2. Is there a way to get an element only by TKey1 OR TKey2, not TKey1 AND TKey2?

I wrote the following code:

 public TValue GetItemByKey1(TKey1 key)
 {
     MainCollection<int, int, string> Coll = new MainCollection<int, int, string>();
     var value = from s in Coll where s.Key.Key == key select s.Value;
 }

But it already has two issues:

Compilation error: s.Key.Key == key => operator == can not be applied to types int and TKey1
It looks ugly. Even if compilation would be successful I'm not sure that this is the fastest way to get such items. I guess that Dictionary should something better.

How can i solve such errors? I didnt find any related questions here. Thanks in advance!

Why do you think that `TKey1` is `int`? Your code doesn't make sense. — SLaks, Sep 01 '11 at 14:40
Is there a particular reason you're using a KeyValuePair? You could use a simple struct (implementing Equals & GetHashCode) to store the two keys, with public properties to read them? In the above code, since the == operator is statically typed, you'd need to use the Equals method, for the equality test... — Hasanain, Sep 01 '11 at 14:55
Which version of .Net are you using? If .Net 4, use `Tuple` for your key. — IAbstract, Sep 01 '11 at 14:59
See this http://stackoverflow.com/questions/1171913/multi-key-dictionaries-of-another-kind-in-c?lq=1 or http://stackoverflow.com/questions/1504451/how-to-implement-a-multi-index-dictionary — nawfal, Mar 30 '13 at 20:04

jason · Accepted Answer · 2011-09-01T15:04:09.073

Okay, so you want to be able to lookup by TKey1 or TKey2. Then what you want is three dictionaries, one for each of the keys, and then one for the key-pairs.

class Foo<TFirstKey, TSecondKey, TValue> {
    private readonly Dictionary<TFirstKey, List<TValue>> firstDictionary
        = new Dictionary<TFirstKey, List<TValue>>();
    private readonly Dictionary<TSecondKey, List<TValue>> secondDictionary
        = new Dictionary<TSecondKey, List<TValue>>();
    private Dictionary<Tuple<TFirstKey, TSecondKey>, TValue> dictionary
        = new Dictionary<Tuple<TFirstKey, TSecondKey>, TValue>();

    public IEnumerable<TValue> GetByFirstKey(TFirstKey firstKey) {
        return this.firstDictionary[firstKey];
    }

    public IEnumerable<TValue> GetBySecondKey(TSecondKey secondKey) {
        return this.secondDictionary[secondKey];
    }

    public TValue GetByKey(TFirstKey firstKey, TSecondKey secondKey) {
        return this.dictionary[Tuple.Create(firstKey, secondKey)];
    }

    public void Add(TFirstKey firstKey, TSecondKey secondKey, TValue value) {
        this.dictionary.Add(Tuple.Create(firstKey, secondKey), value);
        if(this.firstDictionary.Keys.Contains(firstKey)) {
            this.firstDictionary[firstKey].Add(value);
        }
        else {
            this.firstDictionary.Add(firstKey, new List<TValue> { value });
        }
         if(this.secondDictionary.Keys.Contains(secondKey)) {
            this.secondDictionary[secondKey].Add(value);
        }
        else {
            this.secondDictionary.Add(secondKey, new List<TValue> { value });
        }
    }
}

Note that only lookup by (TFirstKey, TSecondKey) is unique, so you need GetByFirstKey and GetBySecondKey to return collections.

I'll leave the rest of the details to you.

The point is that if you want fast lookups on either key, you need two dictionaries (one for each coordinate of the key-pair). Using one can be made to work by querying the key set, but that's slow (it's linear to search the keys).

Compilation problem, maybe there is a typo? private readonly Dictionary> firstDictionary = new Dictionary>(); — Laserson, Sep 01 '11 at 15:00
@Laserson: Yup, sorry. Typed this in the browser, not in an IDE. I eliminated one other error. Sorry for the mistake. — jason, Sep 01 '11 at 15:05
@Jason - you're welcome! I'm really appreciate your help. Can you please also explain about type casting for IEnumerable GetByFirstKey - should it be casted automatically or should i write some additional functions? — Laserson, Sep 01 '11 at 15:11
@Jason: I see the reason for multiple dictionaries ...for speed, yes. — IAbstract, Sep 01 '11 at 15:21
@Laserson: I'm not sure what type casting you think you need. Can you elaborate? — jason, Sep 01 '11 at 17:28

score 1 · Answer 2 · answered Sep 01 '11 at 14:42

Just add a method to the collection itself:

 public TValue GetItemByKey1(TKey1 key)
 {         
     var value = from s in this.Keys where s.Key.Key == key select this[s];
     return value.SingleOrDefault();
 }

You can have a similar method for TKey2.

Note that these lookups will be much slower than a standard dictionary key lookup, since you're iterating the key collection, rather than taking advantage of the hashtable a dictionary would otherwise use.

IAbstract · Answer 3 · 2011-09-01T16:02:39.820

I recommend against using KeyValuePair<TKey, TValue> because KVP is a struct and being a key in the dictionary indicates that the object will be around for a while. I would recommend a Tuple<T1, T2> instead. The benefit is that Tuple is a reference type and you can freely pass around without making copies. Also, Tuple is a readonly object just like the KVPair. Here's the way I would write it:

    class Program
    {
        static void Main(string[] args)
        {
            MainCollection<int, string, DateTime> collection = new MainCollection<int, string, DateTime>();

            collection.Add(Tuple<int, string>.Create(1, "Bob"), new DateTime(1992, 12, 1));
            collection.Add(Tuple<int, string>.Create(2, "James"), new DateTime(1945, 9, 1));
            collection.Add(Tuple<int, string>.Create(3, "Julie"), new DateTime(1976, 7, 15));

            DateTime date;

            date = collection.GetValue(1);
            Console.WriteLine("Bob birthdate: {0}", date);

            date = collection.GetValue("Julie");
            Console.WriteLine("#3 birthdate: {0}", date);

            Console.ReadLine();
        }
    }

    public class MainCollection<TKey1, TKey2, TValue>
    {
        Tuple<TKey1, TKey2> key;
        Dictionary<Tuple<TKey1, TKey2>, TValue> mainCollection = new Dictionary<Tuple<TKey1, TKey2>, TValue>();

        public void Add(Tuple<TKey1, TKey2> Key, TValue Value)
        {
            mainCollection.Add(Key, Value);
        }

        public TValue GetValue(TKey1 Key)
        {
            return mainCollection.Where(k => k.Key.Item1.Equals(Key))
                                 .Select(v => v.Value)
                                 .FirstOrDefault();
        }

        public TValue GetValue(TKey2 Key)
        {
            return mainCollection.Where(k => k.Key.Item2.Equals(Key))
                                 .Select(v => v.Value)
                                 .FirstOrDefault();
        }

    }

    public class Tuple<T1, T2>
    {
        readonly T1 item1;
        readonly T2 item2;

        Tuple(T1 item1, T2 item2)
        {
            this.item1 = item1;
            this.item2 = item2;
        }

        public static Tuple<T1, T2> Create(T1 Item1, T2 Item2)
        {
            return new Tuple<T1, T2>(Item1, Item2);
        }

        public T1 Item1
        { get { return item1; } }

        public T2 Item2
        { get { return item2; } }
    }
}

NOTE: I included a Tuple implementation in case you are not using .Net 4.0

Update:
Converting the MainCollection object to use multiple dictionaries would look like this:

public class MainCollection<TKey1, TKey2, TValue>
{
    Tuple<TKey1, TKey2> key;
    Dictionary<TKey1, Tuple<TKey1, TKey2>> k1Dictionary = new Dictionary<TKey1, Tuple<TKey1, TKey2>>();
    Dictionary<TKey2, Tuple<TKey1, TKey2>> k2Dictionary = new Dictionary<TKey2, Tuple<TKey1, TKey2>>();
    Dictionary<Tuple<TKey1, TKey2>, TValue> mainCollection = new Dictionary<Tuple<TKey1, TKey2>, TValue>();

    public void Add(Tuple<TKey1, TKey2> Key, TValue Value)
    {
        mainCollection.Add(Key, Value);

        k1Dictionary.Add(Key.Item1, Key);
        k2Dictionary.Add(Key.Item2, Key);
    }

    public TValue GetValue(TKey1 Key)
    {
        return mainCollection[k1Dictionary[Key]];
    }

    public TValue GetValue(TKey2 Key)
    {
        return mainCollection[k2Dictionary[Key]];
    }
}

Amazing! It is so pity that i cant make 10 upvotes for your answer! — Laserson, Sep 01 '11 at 15:38
As i see you've also realized an advantage of two dictionaries. Is it possible to rewrite your sample for using with two dictionaries? — Laserson, Sep 01 '11 at 15:51

Dictionary and KeyValuePair

3 Answers3